Boolean Logic
Propositional logic fundamentals
Overview
This example shows how to set up boolean logic in Formall and prove basic theorems like the law of excluded middle, De Morgan's laws, and double negation.
Basic Setup
Boolean setup
Complete boolean logic foundation
Law of Excluded Middle
For any proposition P, either P is true or not(P) is true:
Excluded middle
Proof that P ∨ ¬P is always true
Double Negation
not(not(P)) = P for any proposition:
Double negation
Proof that ¬¬P ↔ P
De Morgan's Laws
not(and(P, Q)) = or(not(P), not(Q)):
De Morgan
Proof of ¬(P ∧ Q) ↔ (¬P ∨ ¬Q) by case analysis
Tips for Boolean Proofs
- Case analysis — use nested
ifto cover all combinations - Contradiction — assume the opposite and derive
falseandtruefor the same expression - Substitution — proofs with nested angle brackets chain substitutions
For boolean types with only two values, proofs often reduce to checking all 2ⁿ cases.