Propositional Logic

There are several reasons that one studies computer-oriented deductivelogics. Such logics have played an important role in natural languageunderstanding systems, in intelligent database theory, in expert systems,and in automated reasoning systems, for example. Deductivelogics have even been used as the basis of programming languages, atopic we consider in this book. Of course, deductive logics have beenimportant long before the invention of computers, being key to thefoundations of mathematics as well as a guide in the general realm ofrational discourse.

What is a deductive logic? It has two major components, a formallanguage and a notion of deduction. A formal language has a syntaxand semantics, just like a natural language. The first formal language wepresent is the propositional logic.

We first give the syntax of the propositional logic.

• Alphabet

1. Statement Letters: P, Q, R, P1, Q1, R1, ....

2. Logical Connectives: [conjunction], [disjunction], [logical not], [right arrow], [left and right arrow].

3. Punctuation: (,).

• Well-formed formulas (wffs), or statements

1. Statement letters are wffs (atomic wffs or atoms).

2. If A and B are wffs, then so are

([logical not]A), (A [disjunction] B), (A [conjunction] B), (A [right arrow] B), and (A [left and right arrow] B).

Convention. For any inductively defined class of entities we will assumea closure clause, meaning that only those items created by (often repeateduse of) the defining rules are included in the defined class.

We will denote statement letters with the letters P, Q, R, possiblywith subscripts, and wffs by letters from the first part of the alphabetunless explicitly noted otherwise. Statement letters are considered to benon-logical symbols.

We list the logical connectives with their English labels. (The negationsymbol doesn't connect anything; it only has one argument. However,for convenience we ignore that detail and call all the listed logicalsymbols "connectives.")

[logical not] negation

[conjunction] and

[disjunction] or

[right arrow] implies

[left and right arrow] equivalence

Example. ((([logical not]P) [conjunction] Q) [right arrow] (P [right arrow] Q)).

A formal language, like a natural language, has an alphabet and anotion of grammar. Here the grammar is simple; the wffs (statements)are our sentences. As even our simple example shows, the parenthesesmake statements very messy. We usually simplify matters by forgoingtechnically correct statements in favor of sensible abbreviations. Wesuppress some parentheses by agreeing on a hierarchy of connectives.However, it is always correct to retain parentheses to aid quick readabilityeven if rules permit further elimination of parentheses. We also willuse brackets or braces on occasion to enhance readability. They are to beregarded as parentheses formally.

We give the hierarchy with the tightest binding connective on top.

[logical not]

[disjunction], [conjunction]

[right arrow], [left and right arrow]

We adopt association-to-the-right.

A [right arrow] B [right arrow] C is (A [right arrow] (B [right arrow] C)).

Place the parentheses as tightly as possible consistent with the existingbindings, beginning at the top of the hierarchy.

Example. The expression [logical not] P [conjunction] Q [right arrow] P [right arrow] Q represents the wff

((([logical not]P) [conjunction] Q) [right arrow] (P [right arrow] Q)).

A more readable expression, also called a wff for convenience, is

([logical not]P [conjunction] Q) [right arrow] (P [right arrow] Q).

1.1 Propositional Logic Semantics

We first consider the semantics of wffs by seeing their source as naturallanguage statements.

English to formal notation.

Example 1. An ongoing hurricane implies no class meeting, so if nohurricane is ongoing then there is a class meeting.

Use: H: there is an ongoing hurricane

C: there is a class meeting

Formal representation.

(1) A

(2) (H [right arrow] [logical not]C) [right arrow] ([logical not]H [right arrow] C)

(3) (H [right arrow] [logical not]C) [conjunction] [(H [right arrow] [logical not]C) [right arrow] ([logical not]H [right arrow] C)]

The first representation is technically correct (ignoring the "use" instruction),but useless. The idea is to formalize a sentence in as fine-grainedan encoding as is possible with the logic at hand. The secondand third representations do this.

Notice that there are three different English expressions encodedby the implies symbol. "If ... then" and "implies" directly translateto the formal implies connective. "So" is trickier. If "so" implies thetruth of the first clause, then wff (3) is preferred as the clause is assertedand connected by the logical "and" symbol to the implication.The second interpretation simply reflects that the antecedent of "so"(supposedly) implies the consequent. This illustrates that formalizingnatural language statements is often an exercise in guessing the intentof the natural language statement. The task of formalizing informalstatements is often best approached by creating a candidate wff andthen directly replacing the statement letters by the assigned Englishmeanings and judging how successfully the wff captures the intent ofthe informal statement. One does this by asserting the truth of thewff and then considering the truth status of the component parts.For example, asserting the truth of wff (3) forces the truth of the twocomponents of the logical "and" by the meaning of logical "and." Weconsider the full "meaning" of implication shortly. One should tryalternate wffs if there is any question that the wff first tried is notclearly satisfactory. Doing this in this case yields representations (2) and(3). Which is better depends on one's view of the use of "so" in thissentence.

Aside: For those who suspect that this is not a logically true formula,you are correct. We deal with this aspect later.

Example 2. Either I study logic now or I go to the game. If I study logicnow I will pass the exam but if I go to the game I will fail the exam.Therefore, I will go to the game and drop the course.

Use: L: I study logic now

G: I go to the game

P: Ipass theexam

D: I drop the...