Logic and Proofs

• Proposition


  Sentence that is either True or False, but not both
• Propositions


  • Washington D.C. is the capital of the USA
  • Quezon City is the capital of the Philippines
  • 1 + 1 = 3
  • 5 + 5 = 10
• Not a proposition
• Compound propositions


  Formed from existing propositions using logical operators
• Logical operators


  • ~ for "not/negation"
  • ^ for "and"
  • V for "or"
  • for "implication/if-then"
  • for "if and only if"
• Compound propositions


  • If it is cloudy, then its going to rain.
  • If it is going to rain, I should take my umbrella.
  • Therefore, if it is cloudy, I should take my umbrella.
• Translating compound propositions


  1. p q

  2. q r

  3. ∴ p r
• Compound propositions


  • If x is 3, then x squared is 9
  • The x cubed is 27, it is necessary that x is 3
• Truth tables


  Displays the relationships between the truth values of propositions
• Negation (¬)


  • The negation of a proposition A (written as ¬A) is false when A is true and is true when A is false
• Conjunction (AND, ∧)


  • The AND operation of two propositions A and B (written as A∧B) is true if both the propositional variable A and B is true
• Disjunction (OR, ∨)


  • The OR operation of two propositions A and B (written as A∨B) is true if at least any of the propositional variable A or B is true
• Implication (if-then, →)


  • An implication A→B is the proposition "if A, then B". It is false if A is true and B is false. The rest cases are true
• Material Equivalence (If and only if, ⇔)


  • Also known as biconditional, A⇔B is bi-conditional logical connective which is true when p and q are same, i.e. both are false or both are true
• Compound propositions


  • (p v q) ^ ~(p q)

  (p ^ ~q) [(p v ~ q) (~p ^ q)]
• If all premises are true but the conclusion is false, the argument is invalid
• Arguments and argument forms

  • If it rains, then the ground is wet.

  It rains,

  Therefore, the ground is wet.
• Tautologies


  A formula which is always true for every value of its propositional variables
• Tautologies


  • Prove [(A→B)∧A]→B is a tautology
• Contradiction


  A formula which is always false for every value of its propositional variables
• Contradiction


  • Prove (A∨B)∧[(¬A)∧(¬B)] is a contradiction
• Contingency


  A formula which has both some true and some false values for every value of its propositional variables
• Contingency


  • Prove (A∨B)∧(¬A) a contingency
• Logical Equivalence


  Denoted by ⇔, if they have the same truth values
• Logical Equivalence rules


  • Double Negation

  2. Commutation

  3. De Morgan's theorem

  4. Association

  5. Distribution

  6. Transposition

  7. Identity laws

  8. Tautology

  9. Material Implication

  10. Material Equivalence

  11. Exportation
• Rules of inference


  • Modus Ponens

  2. Modus tolens

  3. Hypothetical syllogism

  4. Disjunctive syllogism

  5. Constructive Dilemma

  6. Destructive Dilemma

  7. Simplification

  8. Conjunction

  9. Addition
• Rules of inference


  • 1.(r ⇔ ~s) ⊃ (t ⊃ u)

  r ⇔ ~s M.P.

  t ⊃ u

  2.(a ⊃ ~b) . [c ⊃ (d.e)]

  ~~b v ~(d.e) D.D

  ~a v ~c

  3.~[g ⊃ (h v x )] . ~[(j . k) ⊃ l]

  ∴~[g ⊃ (h v x )] Simplification