Propositional logic and truth tables

Se basa en

Requisitos previos obligatorios, hasta el fondo: 4

Aprenderás a

• Build truth tables for compound statements and use them to test logical equivalence.
• Distinguish an implication from its converse, inverse and contrapositive.
• Negate compound and quantified statements, including implications.

Definición

• P → Q is false only when P is true and Q is false.
• Two formulas are logically equivalent if they have the same truth value under every assignment of truth values to their variables.
• A tautology is a formula that is true under every assignment.

Teorema

• P → Q is logically equivalent to its contrapositive ¬Q → ¬P, but not to its converse Q → P.
• De Morgan's laws: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
• ¬(P → Q) ≡ P ∧ ¬Q.

Errores frecuentes

• Thinking an implication with a false hypothesis is false; it is true.
• Treating the converse of an implication as equivalent to it.
• Reading 'if P then Q' as claiming that P causes Q.

Conduce a

Descubrimientos opcionales

• Computational complexity Deciding whether a propositional formula is satisfiable (SAT) was the first problem proved NP-complete (Cook–Levin theorem).
• Type theory and propositions as types In constructive logic and type theory, a proof of P → Q is a method turning proofs of P into proofs of Q, and P ∨ ¬P is not assumed as a law.

Itinerarios de aprendizaje

• Accelerated secondary progression
• Adult beginner pathway
• Computer science and formal methods

Lecturas complementarias

• Daniel J. Velleman, How to Prove It: A Structured Approach (1994)
• Herbert B. Enderton, A Mathematical Introduction to Logic (1972)