PM ✱1: formulas, the theorems of ✱1, truth tables
DefinitionPM_core_star1_systemDRAFT — part of an in-progress public formalization of Principia Mathematica; it may still change, and every change is dated in the project's change log.
The primitive apparatus of Whitehead and Russell's Principia Mathematica, ✱1 (Vol. I, 1910, pp. 98–101), as a deep embedding.
- Formulas : propositional variables, negation and disjunction , PM's two primitive ideas.
- Defined connectives, as PM's definitions: (✱1·01), (✱3·01; PM writes ), (✱4·01).
- Theorems of ✱1: the least set of formulas containing the primitive propositions
for all formulas , and closed under the rule ✱1·1: from and infer . 4. Truth tables: the two-valued value of a formula under a valuation, the variables of a formula, and the decidable test that a formula is a tautology.
The card of each numbered proposition of ✱1–✱5 states that its formula is a theorem of ✱1 in this sense.
Formalization Note PM states the primitive propositions with real variables and a rule of substitution; here they are schemas over arbitrary formulas, which has the same effect (✱1·11).
Source: PM.Basic.
-- PM/Basic.lean at 2e43991fec42, without its theorems (skeleton subtraction);
-- generated by scripts/prove2me/export.py; every command kept is copied verbatim.
/-
Principia Mathematica ✱1–✱5 — deep embedding.
Primitive ideas (✱1): negation `∼` and disjunction `∨`; propositional variables.
Definitions are macros (PM: "= Df" is a typographical convenience, not a proposition):
✱1·01 p ⊃ q . = . ∼p ∨ q
✱3·01 p . q . = . ∼(∼p ∨ ∼q)
✱4·01 p ≡ q . = . p ⊃ q . q ⊃ p
Primitive propositions: ✱1·1 (inference / modus ponens), ✱1·2 Taut, ✱1·3 Add, ✱1·4 Perm,
✱1·5 Assoc, ✱1·6 Sum. Substitution (✱1·11-style use of real variables) is built in by stating
the axioms as schemas over arbitrary formulas. ✱1·7–✱1·72 (elementary-proposition formation)
are the well-formedness of `F` itself.
-/
namespace PM
inductive F where
| var : String → F
| neg : F → F
| or : F → F → F
deriving DecidableEq, Repr, Inhabited
@[reducible] def F.imp (p q : F) : F := .or (.neg p) q -- ✱1·01
@[reducible] def F.and (p q : F) : F := .neg (.or (.neg p) (.neg q)) -- ✱3·01
@[reducible] def F.iff (p q : F) : F := F.and (F.imp p q) (F.imp q p) -- ✱4·01
inductive Thm : F → Prop where
| mp {p q : F} : Thm p → Thm (F.imp p q) → Thm q -- ✱1·1
| taut (p : F) : Thm (F.imp (.or p p) p) -- ✱1·2
| add (p q : F) : Thm (F.imp q (.or p q)) -- ✱1·3
| perm (p q : F) : Thm (F.imp (.or p q) (.or q p)) -- ✱1·4
| assoc (p q r : F) : Thm (F.imp (.or p (.or q r)) (.or q (.or p r))) -- ✱1·5
| sum (p q r : F) : Thm (F.imp (F.imp q r) (F.imp (.or p q) (.or p r))) -- ✱1·6
/-- Two-valued semantics, for soundness and counter-models. -/
def F.eval (v : String → Bool) : F → Bool
| .var s => v s
| .neg p => !(p.eval v)
| .or p q => p.eval v || q.eval v
end PM
namespace PM
/-- Variables of a formula, and a decidable truth-table check (an independent re-implementation of
dots.py's tautology test, run by Lean's kernel). -/
def F.vars : F → List String
| .var s => [s]
| .neg p => p.vars
| .or p q => (p.vars ++ q.vars).eraseDups
def assignments : List String → List (String → Bool)
| [] => [fun _ => false]
| x :: xs => (assignments xs).flatMap fun v => [fun s => if s == x then false else v s, fun s => if s == x then true else v s]
def F.isTaut (p : F) : Bool := (assignments p.vars.eraseDups).all fun v => p.eval v
end PM