6.042J/18.062J 4. Propositional Logic

1 February 10, 2010 Albert R Meyer The Logic of Propositions lec 2W.1 February 10, 2010 Albert R Meyer There are 5 regular solids. True 6 False lec 2W.2 Propositional (Boolean) Logic A proposition is either True or False Example: Non-examples: Wake up! Where am I? February 10, 2010 Albert R Meyer G → (S ∨ J) True even if a Greek carries both a Sword and a Javelin Greeks carry Swords or Javelins lec 2W.3 English to Math February 10, 2010 Albert R Meyer G → (B ⊕ C) English to Math Greeks carry Bronze or Copper swords Bronze or Copper but not both lec 2W.4 February 10, 2010 Albert R Meyer Definition of OR P Q P OR Q T T T T F T F T T F F F The value of (P OR Q) is T iff P is T, or Q is T, or both are T. Truth Table for OR lec 2W.5 F iff both P,Q are F February 10, 2010 Albert R Meyer Definition of XOR P Q P XOR Q T T F T F T F T T F F F The value of (P XOR Q) is T iff exactly one of P and Q is T. Truth Table for XOR lec 2W.6 2 February 10, 2010 Albert R Meyer Definition of AND P Q P AND Q T T T T F F F T F F F F The value of (P AND Q) is T iff both P and Q are T. Truth Table for AND lec 2W.7 February 10, 2010 Albert R Meyer Definition of NOT P NOT(P) T F F T The NOT(P) is T iff P is F. Truth Table for NOT (P) lec 2W.8 February 10, 2010 Albert R Meyer Truth Assignments A truth assignment assigns a value T or F to each propositional variable. Computer scientists call assignment of values to variables an environment. If we know the environment, we can find the value of a propositional formula. lec 2W.9 February 10, 2010 Albert R Meyer Evaluation in an Environment Example: Suppose environment, v, assigns v(P) = T, v(Q)= T, v(R) = F. Truth value of ( (P AND Q) ) OR (R XOR ( Q)) T T F T F F T F F lec 2W.10 ¬ ¬ February 10, 2010 Albert R Meyer Equivalence Two propositional formulas are equivalent iff they have the same truth value in all environments. lec 2W.11 February 10, 2010 Albert R Meyer F T T T F F T F F T T T Q P T F F F DeMorgan’s Law lec 2W.13 is equivalent to F F F T T T F F T F T F ¬(P ∨Q)3 February 10, 2010 Albert R Meyer F T T T F F T F F T T T Q P T F F F DeMorgan’s Law lec 2W.14 is equivalent to F F F T T T F F T F T F Same final column, so equivalent --proof by Truth Table ¬(P ∨Q) February 10, 2010 Albert R Meyer Definition of IMPLIES P Q P→Q T T T T F F F T T F F T The value of (P IMPLIES Q) is F iff P is T and Q is F. Truth Table for IMPLIES (→) lec 2W.15 February 10, 2010 Albert R Meyer A True Implication (1=-1) IMPLIES (I am Pope) We reasoned correctly to reach the false conclusion lec 2W.16 February 10, 2010 Albert R Meyer A True Implication (1=-1) IMPLIES (I am Pope) We reasoned correctly to reach the false conclusion lec 2W.17 February 10, 2010 Albert R Meyer A True Implication (1=-1) IMPLIES (I am Pope) We reasoned correctly to reach the false conclusion from the false hypothesis. lec 2W.18 February 10, 2010 Albert R Meyer A True Implication (1=-1) IMPLIES (I am Pope) We reasoned correctly to reach the false conclusion from the false hypothesis. lec 2W.19 4 February 10, 2010 Albert R Meyer lec 2W.20 A True Implication (1=-1) IMPLIES (I am Pope) The whole implication is true, even though both conclusion & hypothesis are false. February 10, 2010 Albert R Meyer Satisfiability & Validity A formula is satisfiable iff it is true in some environment . A formula is valid iff it is true in all environments. lec 2W.21 February 10, 2010 Albert R Meyer Verifying Valid, Satisfiable Truth table size doubles with each additional variable --exponential growth. Makes truth tables impossible when there are hundreds of variables. (In current digital circuits, there are millions of variables.) February 10, 2010 Albert R Meyer Efficient Test for Satisfiability? The P=NP? question is equivalent to asking if there is an efficient (polynomial rather than exponential time) procedure to check satisfiability. February 10, 2010 Albert R Meyer Java Logical Expression if ((x>0) || (x <= 0 && y>100))  (more code) lec 2W.38 OR AND February 10, 2010 Albert R Meyer half adder from http://en.wikipedia.org/wiki/Adder_(electronics) lec 2W.40 Digital Logic 5 February 10, 2010 Albert R Meyer A B cin d cout full adder s c lec 2W.41 Digital Logic February 10, 2010 Albert R Meyer lec 2W.42 Team Problems Problems 1—4 MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.