• PropositionalLogic

Propositional logic is the simplest form of logic. Here the only statements that are considered are propositions, which contain no variables. Because propositions contain no variables, they are either always true or always false.

Examples of propositions:

• 2+2=4. (Always true).
• 2+2=5. (Always false).

Examples of non-propositions:

• x+2=4. (May be true, may not be true; it depends on the value of x.)
• x*0=0. (Always true, but it's still not a proposition because of the variable.)
• x*0=1. (Always false.)

As the last two examples show, it is not enough for a statement to be always true—whether a statement is a proposition or not is a structural property. But if a statement doesn't contain any variables (or other undefined terms), it is a proposition, and as a side-effect of being a proposition it's always true or always false.

1. Operations on propositions

Propositions by themselves are pretty boring. So boring, in fact, that logicians quickly stop talking about actual statements and instead haul out placeholder names for propositions like p, q, or r. But we can build slightly more interesting propositions by combining propositions together using various logical connectives, like:

Negation

The negation of p is written as ¬p, or sometimes -p or p with a line over it. It has the property that it is false when p is true, and true when p is false.

Or

The or of two propositions p and q is written as p ∨ q, (or maybe p \/ q in ASCII) and is true as long as at least one, or possibly both, of p and q is true.¹ This is not always the same as what "or" means in English; in English, "or" often is used for exclusive or which is not true if both p and q are true. For example, if someone says "You will give me all your money or I will stab you with this table knife", you would be justifiably upset if you turn over all your money and still get stabbed. But a logician would not be at all surprised, because the standard "or" in propositional logic is an inclusive or that allows for both outcomes.

And

The and of p and q is written as p ∧ q, (or p /\ q) and is true only when both p and q are true.² This is pretty much the same as in English, where "I like to eat ice cream and I own a private Caribbean island" is not a true statement when made by most people even though most people like to eat ice cream. The only complication in translating English expressions into logical ands is that logicians can't tell the difference between "and" and "but": the statement "2+2=4 but 3+3=6" becomes simply "(2+2=4) ∧ (3+3=6)."

Implication

This is the most important connective for proofs. An implication represents an "if...then" claim. If p implies q, then we write p → q, p ⇒ q, or p ⇒ q, depending on our typographic convention and the availability of arrow symbols in our favorite font. In English, p ⇒ q" is usually rendered as "If p, then q", as in "If you step on your own head, it will hurt." The meaning of p ⇒ q is that q is true whenever p is true, and the proposition p ⇒ q is true provided (a) p is false (in which case all bets are off), or (b) q is true. In fact, the only way for p ⇒ q to be false is for p to be true but q to be false; because of this, p ⇒ q can be rewritten as ¬p ∨ q. So, for example, the statements "If 2+2=5, then I'm the Pope", "If I'm the Pope, then 2+2=4", and "If 2+2=4, then 3+3=6", are all true, provided the if...then is interpreted as implication. Normal English usage does not always match this pattern; instead, if...then in normal speech is often interpreted as the much stronger biconditional (see below).

Biconditional

Suppose that p ⇒ q and q ⇒ p, so that either both p and q are true or both p and q are false. In this case, we write p ⇔ q, p ⇔ q, or p ⇔ q, and say that p holds if and only if q holds. The truth of p ⇔ q is still just a function of the truth or falsehood of p and q; though there doesn't seem any connection between the two sides of the statement, "2+2=5 if and only if I am the Pope" is still true (provided it is not uttered by the Pope). The only way for p ⇔ q to be false is for one side to be true and one side to be false.

The result of applying any of these operations is called a compound proposition.

1.1. Precedence

When reading a logical expression, the order of precedence in the absence of parentheses is negation, and, or, implication, biconditional. So (¬p ∨ q ∧ r ⇒ s ⇔ t) is interpreted as ((((¬p) ∨ (q ∧ r)) ⇒ s) ⇔ t). Or and and are associative, so (p ∨ q ∨ r) is the same as ((p ∨ q) ∨ r) and as (p ∨ (q ∨ r)), and similarly (p ∧ q ∧ r) is the same as ((p ∧ q) ∧ r) and as (p ∧ (q ∧ r)).

Implication is not associative, although the convention is that it binds "to the right", so that a ⇒ b ⇒ c is read as a ⇒ (b ⇒ c); few people ever remember this, so it is usually safest to put in the parentheses. I personally have no idea what p ⇔ q ⇔ r means, so any expression like this should be written with parentheses as either (p ⇔ q) ⇔ r or p ⇔ (q ⇔ r).

2. Truth tables

See RosenBook §§1.1–1.2 or BiggsBook §§3.1–3.3.

3. Tautologies and logical equivalence

A compound proposition that is true no matter what the truth-values of the propositions it contains is called a tautology. For example, p ⇒ p, p ∨ ¬p, and ¬(p ∧ ¬p) are all tautologies, as can be verified by constructing truth tables. If a compound proposition is always false, it's a contradiction. The negation of a tautology is a contradiction and vice versa.

The most useful class of tautologies are logical equivalences. This is a tautology of the form X ⇔ Y, where X and Y are compound propositions. In this case, X and Y are said to be logically equivalent and we can substitute one for the other in more complex propositions. We write X ≡ Y if X and Y are logically equivalent.

To prove a logical equivalence, one either constructs a truth table to show that X ⇔ Y is a tautology, or transforms X to Y using previously-known logical equivalences. Some examples:

p ∧ ¬p ≡ 0: Construct a truth table

and observe that the last two columns are always equal.

p ∨ p ≡ p:

p ⇒ q ≡ ¬p ∨ q: Again construct a truth table

¬(p ∨ q) ≡ ¬p ∧ ¬q: (one of De Morgan's laws).

(p ⇒ r) ∨ (q ⇒ r) ≡ (p ∧ q) ⇒ r. Now things are getting messy, so building a full truth table may take awhile. But we have take a shortcut by using logical equivalences that we've already proved (plus associativity of ∨):

• (p ⇒ r) ∨ (q ⇒ r) ≡ (¬p ∨ r) ∨ (¬q ∨ r) [Using p ⇒ q ≡ ¬p ∨ q twice.] ≡ ¬p ∨ ¬q ∨ r ∨ r [Associativity and commutativity of ∨.] ≡ ¬p ∨ ¬q ∨ r [p ≡ p ∨ p.] ≡ ¬(p ∧ q) ∨ r [De Morgan's law.] ≡ (p ∧ q) ⇒ r [p ⇒ q ≡ ¬p ∨ q.]

This last equivalence is a little surprising. It shows, for example, that if somebody says "It is either the case that if you study you will graduate from Yale with distinction, or that if you join the right secret society you will graduate from Yale with distinction", then this statement (assuming we treat the or as ∨) is logically equivalent to "If you study and join the right secret society, then you will graduate from Yale with distinction." It is easy to get tangled up in trying to parse the first of these two propositions; translating to logical notation and simplifying using logical equivalence is a good way to simplify it.

Over the years, logicians have given names to many logical equivalences. Only a few of these are actually useful to remember. These include de Morgan's laws: ¬(p ∨ q) ≡ (¬p ∧ ¬q) and ¬(p ∧ q) ≡ (¬p ∨ ¬q) (see De_Morgan's_law for more versions of these), commutativity of AND and OR, the equivalence of p ⇒ q and ¬p ∨ q, and the contraposition rule p ⇒ q ≡ ¬q ⇒ ¬p (see below for more about contraposition). Anything else you need you can probably derive from these or by writing out a truth table.

4. Inverses, converses, and contrapositives

The inverse of p ⇒ q is ¬p ⇒ ¬q. So the inverse of "If you take CPSC 202, you will surely die" is "If you do not take CPSC 202, you will not surely die." There is often no connection between the truth of an implication and the truth of its inverse: "If I am Dick Cheney then I am a Republican" does not have the same truth-value as "If I am not Dick Cheney then I am not a Republican", at least according to current polling numbers.

The converse of p ⇒ q is q ⇒ p. E.g. the converse of "If I am Dick Cheney then I am a Republican" is "If I am a Republican then I am Dick Cheney." The converse of a statement is always logically equivalent to the inverse. Often in proving a biconditional (e.g., "I am Dick Cheney if and only if I am a Republican"), one proceeds by proving first the implication in one direction and then either the inverse or the converse.

The contrapositive of p ⇒ q is ¬q ⇒ ¬p; it is logically equivalent to the original implication ("If I am not a Republican then I am not Dick Cheney"). A proof by contraposition proves p implies q by assuming ¬q and then proving ¬p; it is similar but not indentical to an IndirectProof, which assumes ¬p and derives a contradiction.

5. Normal forms

A compound proposition is in conjuctive normal form (CNF for short) if it is obtained by ANDing together ORs of variables or their negations. So for example P, (P∨Q)∧(Q∨R)∧(¬P), and (P∨Q)∧(P∨¬R)∧(¬P∨Q∨S∨T∨¬U) are in CNF, but (P∨Q)∧(P∨¬R)∧(¬P∧Q),(P∨Q)∧(P⇒R)∧(¬P∨Q), and (P∨(Q∧R))∧(P∨¬R)∧(¬P∨Q) are not. Using the equivalence P⇒Q ≡ ¬P∨Q, De Morgan's laws, and the distributive law, it is possible to rewrite any compound proposition in CNF.

CNF formulas are particularly useful because they support resolution (see InferenceRules). Using the tautology (P∨Q)∧(¬P∨R) ⇒ Q∨R, we can construct proofs from CNF formulas by looking for occurrences of some simple proposition and its negation and resolving them. For example, we can compute (P∨Q)∧(P∨¬R)∧(¬P∨Q)∨(¬Q∨R) ⊢ Q∧(P∨¬R)∧(¬Q∨R) ⊢ (P∨¬R)∧R ⊢ P. This style of proof is called a resolution proof. Because of its simplicity it is particularly well-suited for mechanical theorem provers. Such proofs can also encode traditional proofs based on modus ponens: the inference P∧(P⇒Q) ⊢ Q can be rewritten as resolution by expanding ⇒ to get P∧(¬P∨Q) ⊢ Q.

Similarly, a compound proposition is in disjunctive normal form (DNF) if it consists of an OR of ANDs, e.g. (P∧Q)∨(P∧¬R)∨(¬P∧Q). Just as any compound proposition can be transformed into CNF, it can similarly be transformed into DNF.

CategoryMathNotes