跳到正文
The Lumenary
九至十二年级Foundations课程已上线

Propositional logic and truth tables

Truth tables, implication with its converse and contrapositive, logical equivalence and tautologies: the logic of 'and', 'or', 'not' and 'if…then' made exact.

math.found.propositional-logic

打开课程 显示到达此主题所需的全部内容

前置知识

True, false, and, or, notSet-builder notation, quantifiers and infinite sets

4 项必需的前置知识（一直追溯到底）

你将学会

  • 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.

定义

  • 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.

定理

  • 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.

常见误解

  • 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.

通向

Proof: direct, contrapositive, contradiction and inductionFirst steps in LeanFirst-order logic

可选发现

  • 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.

学习路径

延伸阅读

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