Propositional calculus

• Equivalent operators and tautologies
  • Using symbolic logic, we can express logical arguments using algebraic formulas.
  
  
  • This is called propositional calculus.
  
  
  • A formula in symbolic logic is expressed using the equivalence operator, <=>.
  
  
  
  • Example: we proved that ¬ (P /\ Q) <=> (¬ P) \/ (¬ Q).
  
  
  • There are two ways to think of this:
    • The expression to the left of <=> always has the same truth values as the expression to the right of <=>, regardless of the truth values of P and Q. (Practically, one writes the truth tables for both operators and shows they are the same.)
    • The entire expression is always true, regardless of the truth values of P and Q. An expression that is always true is called a tautology. (One writes the truth table for the entire expression at once.)
  
  
  • Example: truth table for ¬(P /\ Q) <=> (¬P) \/ (¬Q)
    

    P	Q	¬ (P /\ Q) <=> (¬ P) \/ (¬ Q)
    T	T	T
    T	F	T
    F	T	T
    F	F	T

    
    So this expression is a tautology.
  
  
  • Let us denote the statement which is always "true" by the symbol T, and the symbol which is always "false" by the symbol F.
    
    Then any tautology is equivalent to T, and any contradiction is equivalent to F. So for example: (P \/ ¬P)) <=> T
    (Either P is true or P is false)
    
    (P /\ ¬P) <=> F
    (P cannot be both true and false)
    
• Logical formulas
  These formulas all come from looking at part of the truth tables for "and" and "or".
  

  P/\P <=> P P\/P <=> P	(idempotent)
  P\/F <=> P P\/T <=> T P/\F <=> F P/\T <=> P	(identity)

  
  All of the following formulas may be proven using truth tables.
  (Prove the distributivity law on the board)
  

  ¬(¬P) <=> P	(double negative)
  P/\Q <=> Q/\P P\/Q <=> Q\/P (P<=>Q) <=> (Q<=>P)	(commutativity)
  (P/\Q)/\R <=> P/\(Q/\R) (P\/Q)\/R <=> P\/(Q\/R)	(associativity)
  (P/\Q)\/R <=> (P\/R)/\(Q\/R) (P\/Q)/\R <=> (P/\R)\/(Q/\R)	(distributivity)
  ¬(P/\Q) <=> (¬P)\/(¬Q) ¬(P\/Q) <=> (¬P)/\(¬Q)	(DeMorgan laws)
  P=>Q <=> ¬(P/\¬Q) P=>Q <=> ¬P\/Q	(implication)
  P=>Q <=> ¬Q=>¬P	(contrapositive)