- The implication introduction rule assumes locally, derives under that assumption, then concludes while discharging the temporary assumption.
- The disjunction elimination rule uses and two local cases: one derives a common conclusion from , and the other derives that same from . It concludes and discharges both case assumptions.
- The negation introduction rule assumes locally and derives logical falsity. Discharging that assumption gives .
The boxes delimit a subproof and identify the lifetime of its temporary assumptions. A result depending on a boxed assumption is available inside that box and its nested boxes; it cannot simply be exported outside. The enclosing rule specifies what may be exported and which assumptions are discharged. Other premises on which the derivation depends remain undischarged. This assumption discharge discipline distinguishes a conditional argument from an unconditional proof.
Write for . The following derives Peirce's law directly from the printed primitive rules, including double-negation elimination:
| Line | Formula | Justification |
|---|---|---|
| 1 | Assume for the final implication | |
| 2 | Assume locally | |
| 3 | Assume inside the scope of 2 | |
| 4 | Negation elimination rule, 2 and 3 | |
| 5 | Logical falsity elimination rule, 4 | |
| 6 | Implication introduction rule, discharging 3–5 | |
| 7 | Implication elimination rule, 1 and 6 | |
| 8 | Negation elimination rule, 2 and 7 | |
| 9 | Negation introduction rule, discharging 2–8 | |
| 10 | Double-negation elimination, 9 | |
| 11 | Implication introduction rule, discharging 1–10 |
Let abbreviate , and group the three equality alternatives on the left. The proof uses the binary disjunction elimination rule twice, so no unproved three-way derived rule is needed.
| Line | Formula | Justification |
|---|---|---|
| 1 | Premise | |
| 2 | Assume for the first implication | |
| 3 | Assume for the second implication | |
| 4 | Assume with fresh witness name | |
| 5 | Universal quantifier elimination rule, 1 | |
| 6 | Assume the first outer case | |
| 7 | Assume the first inner case | |
| 8 | Equality elimination rule, 7 and 4 | |
| 9 | Negation elimination rule, 2 and 8 | |
| 10 | Logical falsity elimination rule, 9 | |
| 11 | Assume the second inner case | |
| 12 | Equality elimination rule, 11 and 4 | |
| 13 | Disjunction introduction rule, left, 12 | |
| 14 | Disjunction elimination rule, 6, 7–10 and 11–13 | |
| 15 | Assume the second outer case | |
| 16 | Equality elimination rule, 15 and 4 | |
| 17 | Disjunction introduction rule, right, 16 | |
| 18 | Disjunction elimination rule, 5, 6–14 and 15–17 | |
| 19 | Existential quantifier elimination rule, 3 and 4–18 | |
| 20 | Implication introduction rule, discharging 3–19 | |
| 21 | Implication introduction rule, discharging 2–20 |
The witness name is absent from and from every assumption remaining after line 19, so the existential elimination is legal. Each equality is used in the forward direction supplied by the printed equality rule. The three named constants need not denote distinct objects: the case proof requires only that they exhaust the domain. This is existential quantification over a finitely named domain followed by exclusion of the first case.
Keep the four given premises in context and assume under label . The modus ponens rule applied to the first two premises gives and . Apply the disjunction elimination rule to as follows.
Under a case assumption , the premise gives by the modus ponens rule. Together with , the negation elimination rule gives , and the supplied logical falsity elimination rule gives . Under the other case assumption , the required conclusion is already available. Discharge both case assumptions with the disjunction elimination rule to conclude .
Finally discharge with the implication introduction rule, giving . The premise is not needed: a derivation is permitted to leave a premise unused.
Use natural deduction with labelled temporary assumptions. Assume under label , then under label , then under label . Two applications of the modus ponens rule give and . The negation elimination rule gives , and the supplied reductio ad absurdum rule discharges to conclude .
Discharge using the implication introduction rule, obtaining under . Discharge with the implication introduction rule, obtainingAll three temporary assumptions have now been discharged; no premise remains.
Assume under label , under label , and under label . A temporary case assumption gives by the modus ponens rule using . A temporary case assumption gives by the modus ponens rule using . The disjunction elimination rule discharges these case assumptions and concludes under .
Apply the implication introduction rule three times, discharging , then , then . The resulting theorem isThe displayed parentheses make explicit the right association of the source formula.
Choose arbitrary fresh variables and assume under label . The conjunction elimination rule gives and . Apply the disjunction elimination rule to the equality disjunction.
In the case , the supplied symmetry rule gives , and the equality elimination rule applied to gives . Disjunction introduction rule gives . In the case , equality elimination rule applied directly to gives ; the other disjunction introduction rule gives the same conclusion . Discharge the two equality case assumptions by disjunction elimination rule.
Discharge with the implication introduction rule. There are now no undischarged assumptions. Use the universal quantifier introduction rule successively for , then , then , yieldingFreshness holds at every generalization because the sole temporary assumption has already been discharged; the arbitrary variables are not tied to any premise.
Only requires a natural deduction proof. Assume . Within that assumption, temporarily assume . By disjunction introduction, obtain ; applying by the implication elimination rule gives . Discharge by the implication introduction rule to derive . Disjunction introduction now gives . Finally discharge by the implication introduction rule:All temporary assumptions are discharged. No classical rule is needed; the same proof works in Intuitionistic propositional logic. The false propositional formula has no proof in this sound natural deduction system.
Keep the premise open. Assume , then temporarily assume . Two applications of the implication elimination rule produce and then , contradicting the temporary . Discharge using the negation introduction rule, then discharge using the implication introduction rule.This natural deduction proof uses only the supplied introduction and elimination rules. Line 6 is an application of the negation elimination rule; no classical contradiction principle is needed.
Propositional logic Created 2026-09-24 Updated 2026-11-05
Propositional logic studies reasoning with whole propositions represented by letters such as and , and propositional formulas built from them using logical connectives. The classical two-valued, truth-functional presentation below assigns each primitive proposition either true or false: each compound value depends only on its component values. This is classical propositional logic; other systems, including Intuitionistic propositional logic, have different semantics and rules.
Starting with and , one can build by logical negation, by logical conjunction, by logical disjunction, and by logical implication, then combine these into larger propositional formulas. Parentheses specify the construction: has logical conjunction as its outermost logical connective. Primitive propositions have no internal structure in this language; a first-order formula can additionally describe objects and quantify over them. The formation rules are given in forall x: Calgary, chapter 6.
The following truth table shows the four basic logical connectives. Logical disjunction is inclusive: is true when either or both inputs are true. Classical logical implication has exactly the same values as ; its only false row has true and false. These truth conditions are specified in forall x: Calgary, chapter 9.
Evaluate from the inside out: first the logical implication, then the outer logical conjunction. The final column also tests the logical implication expressing the modus ponens rule:At , the logical implication is false, so the logical conjunction is false. The abstract syntax tree below separates the construction of the propositional formula from the values propagated through it. Both occurrences of receive the same value from the Boolean valuation. With the opposite assignment , the logical implication is true but the logical conjunction is still false because its second input is false. Recursive evaluation and exhaustive truth tables are explained in forall x: Calgary, chapter 11.
The last column is always true: is a tautology. This expresses the logical validity of the modus ponens rule: whenever both premises and are true, is true. It does not say the premises are true under every Boolean valuation; their logical conjunction is true only on the first row. For a short natural deduction proof outline, assume , extract both conjuncts, apply the implication elimination rule to obtain , then discharge the assumption by the implication introduction rule. See forall x: Calgary, sections 17.3–17.5.
Three tests answer different questions: Boolean satisfiability requires at least one true row, a tautology requires every row true, and a contradiction has every row false. Thus is a tautology, is a contradiction, and is satisfiable but not a tautology: it is true only at . See forall x: Calgary, sections 12.1–12.4.
Propositional logic is useful because an inference pattern can be checked once and reused for many choices of propositions. Its beauty is that a finite truth table completely settles classical truth-functional questions about a fixed propositional formula. But logical validity does not verify real atomic claims. If means “the switch is closed” and means “the lamp is lit”, a valid use of the modus ponens rule still requires establishing its premises about the apparatus; the truth table supplies neither an observation nor a causal explanation. See forall x: Calgary, chapter 2 and chapter 10.
Typed lambda term Created 2026-10-07 Updated 2026-10-31
A typed lambda term carries a type derivation under a context of typed free variables. The rules for variables, abstraction, and application correspond to assumptions, the implication introduction rule, and the implication elimination rule under the Implicational Curry-Howard correspondence. General fixed-point combinators belong to the untyped lambda calculus; self-application cannot be given a finite simple type.

