Today's lecture is about propositional logic. It should be review for anyone who took Math 187. Main points (some to be covered later -- we got to point 2): 1. definition of the propositional connectives; similarities and contrasts with standard English usage. 2. The method of truth tables; definition of the notion of "tautology". 3. Definitions of the notions of "entailment" and "equivalence"; these are not propositional connectives, and in particular are not the same as implication and biconditional. 4. Issues of syntax: precedence and grouping; relationships with associative and commutative laws. 5. Algebraic laws for propositional connectives in general. Point 1 (definition of the propositional connectives; similarities and contrasts with standard English usage.) The notation I use here will not be the same as that in the book; it will correspond to the notation in the theorem prover, though (so it won't be useless to learn it :-) All these operations are "truth functional": they are operations on "sentences" or "propositions" which depend only on whether the sentences are true or false. Negation: ~true = false ~false = true or in table format P | ~P ------ T | F F | T Conjunction: true & true = true true & false = false false & true = false false & false = false or in table format P | Q | P & Q ------------- T | T | T T | F | F F | T | F F | F | F Notice that the meanings of English "not" and "and" are very similar to the mwanings of the logical operators. We say that "Snow is white and grass is green" exactly when it is true that snow is white and it is true that grass is green. With "not", the meaning is the same as in English but the grammar is not the same. We don't say "Not grass is green". The circuitous formulation "It is false that grass is green" has the same grammar as the negation operator. In English, sentences like Tom and Mary love ice cream expand to Tom loves ice cream and Mary loves ice cream or even Tom loves ice cream & Mary loves ice cream but there is a non-truth-functional use of "and" one should be careful of: Tom and Mary carried the half-ton safe probably is not equivalent to Tom carried the half-ton safe and Mary carried the half-ton safe. In general, one should be careful about the English habit of linking subjects and predicates with what appear to be propositional connectives; this could be formalized in a logical language, but historically no one has chosen to do this. Disjunction: true | true = true true | false = true false | true = true false | false = false or in table format P | Q | P|Q ------------- T | T | T T | F | T F | T | T F | F | F The meaning of "or" shown above (called "inclusive or" and written and/or in legal documents) is the usual mathematical meaning of "or". This contrasts with English usage, in which "or" often has the meaning found in Each child may have cheese cake or carrot cake in which context we suspect that they need to choose one of these delectable alternatives. We call this "exclusive or" or "xor" for short. true <+> true = false true <+> false = true false <+> true = true false <+> false = false or in table format P | Q | P <+> Q --------------- T | T | F T | F | T F | T | T F | F | F This connective occurs much less often than the connective | of inclusive disjunction, but it does have interesting properties. We do need to bear in mind that the meaning of "or" in mathematical text may be assumed to be "inclusive or" unless we are specifically told that it cannot; the ambiguity or context dependence in standard English is to be eliminated from formal mathematical usage. Implication: true -> true = true true -> false = false false -> true = true false -> false = true or in table format: P | Q | P -> Q -------------- T | T | T T | F | F F | T | T F | F | T We admit the notation P <- Q equivalent in meaning to Q -> P; we could provide tables for this, but we choose not to. The English sentence "if P then Q" or "Q if P" does not usually have this truth functional interpretation (called the "material conditional"). The merit of the mathematical usage is that it makes cases of "if P then Q" which are vague in English usage (what is the truth value of "if 2+2=5 then Napoleon conquered China"? What about "If General Washington crossed the Delaware then 2+2=4"? Something confuses us about sentences like these) have precise truth values. The actual meaning of the conditional in English is a topic of philosophical debate, and we cannot pretend to analyze it here. What we do say is that in our apparently English usage as well as our symbolic usage we mean by "if P then Q" nothing more than "either P is false or Q is true or both" (you can check that this is the meaning expressed by the tables above. There are other forms of "implication" which we will use in mathematics (one of them appears in tomorrow's notes); all of them are precisely defined and rather different from colloquial English usage. The merit of this definition is that it is truth functional (so precisely definable) and meets certain natural expectations as to how it can be used in logical arguments (this will be most easily seen in our later notes on "natural deduction"). Biconditional: In English text, P if and only if Q is abbreviated P iff Q. true <-> true = true true <-> false = false false <-> true = false false <-> false = true or in tabular format P | Q | P <-> Q -------------- T | T | T T | F | F F | T | F F | F | T The sentence P <-> Q is to be true just in case P and Q have the same truth value. The same kinds of comments about the relationship between English usage of "if and only if" and mathematical usage apply as in the case of the conditional, though it is harder to imagine colloquial usage of this phrase. I won't discuss the "nand" and "nor" connectives given in the book here, except to say that the principal interest of these two connectives is that either of them may be used to define _all_ propositional connectives, and that we will write "nand" as ~& and "nor" as ~| in the notes and on the prover (if we need to). Point 2. (The method of truth tables; definition of the notion of "tautology".) All possible behavior of any expression in propositional letters and propositional connectives can be analyzed by constructing a "truth table". For example, we analyze the expression P <-> (P & Q): P | Q | P&Q | P<->(P&Q) ---------------------- T | T | T | T T | F | F | F F | T | F | T F | F | F | T We see that P<->(P&Q) has the same truth table as P->Q (which turns out to be a useful fact).x The method of truth tables is of limited practical usefulness, since an expression with n propositional variables requires a truth table with 2^n rows. A related counting problem is to determine how many truth functions with n arguments there are: an expression with n propositional variables has a truth table with 2^n rows, in each row of which we can insert T or F: there are 2^(2^n) different n-argument truth functions. In particular, there are 2^(2^2) = 2^4 = 16 different binary truth functions. Exercise: list the 16 different truth functions. Are any of the functions we have not listed likely to be useful? Are any of these functions commutative but not associative? Are any of these functions associative but not commutative?