Propositional logic

Propositional logic studies reasoning with whole propositions represented by letters such as $p$ and $q$, 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 $p$ and $q$, one can build $\neg p$ by logical negation, $p\wedge q$ by logical conjunction, $p\vee q$ by logical disjunction, and $p\to q$ by logical implication, then combine these into larger propositional formulas. Parentheses specify the construction: $(p\to q)\wedge p$ 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: $p\vee q$ is true when either or both inputs are true. Classical logical implication has exactly the same values as $\neg p\vee q$; its only false row has $p$ true and $q$ false. These truth conditions are specified in forall x: Calgary, chapter 9.

Evaluate $(p\to q)\wedge p$ 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 $p=\mathrm{T},q=\mathrm{F}$, 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 $p$ receive the same value from the Boolean valuation. With the opposite assignment $p=\mathrm{F},q=\mathrm{T}$, the logical implication is true but the logical conjunction is still false because its second input $p$ is false. Recursive evaluation and exhaustive truth tables are explained in forall x: Calgary, chapter 11.

The last column is always true: $((p\to q)\wedge p)\to q$ is a tautology. This expresses the logical validity of the modus ponens rule: whenever both premises $p\to q$ and $p$ are true, $q$ 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 $(p\to q)\wedge p$, extract both conjuncts, apply the implication elimination rule to obtain $q$, 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 $p\vee \neg p$ is a tautology, $p\wedge \neg p$ is a contradiction, and $p\wedge q$ is satisfiable but not a tautology: it is true only at $p=q=\mathrm{T}$. 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 $p$ means “the switch is closed” and $q$ 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.

A propositional variable is an atomic symbol assigned a truth value by a Boolean valuation. A propositional formula is built from these symbols by logical connectives. The variables carry no quantifiers over individuals; their values may be chosen independently.

From Boolean clauses containing complementary Boolean literals, derive the Boolean clause formed by removing that complementary pair and taking the remaining Boolean literals. For example, resolving $p\vee \neg q$ with $\neg p\vee \neg r$ gives $\neg q\vee \neg r$. Backward proof search with a positive-headed Horn clause and an all-negative query is a restricted use of this rule.

An indivisible statement treated as either true or false. In a labelled transition system, an atomic proposition $p$ holds at state $s$ exactly when $p\in L(s)$.

A propositional formula $\phi$ semantically entails $\psi$ when every Boolean valuation satisfying $\phi$ satisfies $\psi$. Equivalently, $\phi \wedge \neg \psi$ is an unsatisfiable Boolean formula. Deciding semantic entailment is co-NP-complete: a counterexample Boolean valuation certifies failure in polynomial time, while $\theta \mapsto ⟨\theta ,p\wedge \neg p⟩$ reduces unsatisfiability to semantic entailment.

In propositional logic with the usual two truth values, negating a proposition twice preserves its truth value. Thus the complement of a set taken twice, in one fixed universal set, is the original set.

Every finite collection of finite propositional formulas mentions only finitely many Boolean variables. Two Boolean valuations agreeing on those variables satisfy exactly the same formulas. They therefore have the same value under any weighted formula utility representation using that collection.

This observation limits representation over infinite sets. On $\mathbb{N}$, the function indicating whether the selected subset is infinite cannot be represented by a finite rule base: if $F$ is the finite set of mentioned indices, $\varnothing$ and $\mathbb{N}\setminus F$ agree on all those indices but require values zero and one. Completeness claims for finite propositional rule bases must therefore specify a finite underlying set or restrict the functions represented.

A contradiction is an assertion or collection of assumptions from which logical falsity follows. Deriving both a statement $P$ and its logical negation is a standard example. A contradiction under a temporary assumption can establish that assumption's negation; classical proof by contradiction additionally uses this to establish positive conclusions.

Identify classical propositional formulae when their equivalence is provable from a fixed theory. Their equivalence classes form the Lindenbaum algebra: meet and join are induced by conjunction and disjunction, complementation by negation, and the order by provable implication. Provable equivalence is preserved by each connective, so these operations are well-defined; the familiar classical propositional identities make this a Boolean algebra. A homomorphism of lattices to $\{0,1\}$ preserving zero and one also preserves complements and therefore specifies a truth valuation of the atomic propositions. All axioms of the fixed theory represent one. Separating the class of an unprovable formula from one consequently gives a countervaluation, proving the completeness theorem for propositional logic.

Take formulas whose free variables lie among a fixed $n$-tuple and identify them when their universal equivalence follows from $T$. Conjunction, disjunction and negation induce a Boolean algebra; its order is implication modulo $T$. Complete types correspond to ultrafilters and isolated complete types to atoms. For a complete theory in a countable language, finiteness of these algebras for every finite $n$ characterizes countable categoricity.

A propositional theory is a set of propositional formulas, sometimes identified with its deductive closure. It is a consistent set of formulae when contradiction is not derivable from it. The completeness theorem for propositional logic identifies consistency with existence of a satisfying Boolean valuation.

A propositional type is a collection of propositional formulas to be jointly realized by a Boolean valuation. A valuation realizes it when every member is true and omits it when some member is false. For propositional omission arguments, the collection need not itself be consistent.

If a consistent propositional theory locally omits every member of a countable family of propositional types, it has a Boolean valuation omitting them all. One may also impose any finite condition consistent with the theory. Successively extend the condition by a negated member of the next type; local omission preserves consistency. The propositional compactness theorem then supplies the valuation. Countability of the ambient language and decidability of consistency are not needed for this argument.

Relative to a consistent propositional theory $T$, a nonprincipal propositional type has no formula consistent with $T$ that implies every member modulo $T$. Equivalently, for each finite condition $\theta$ consistent with $T$, some member $\sigma$ leaves $T\cup \{\theta ,\neg \sigma \}$ consistent. This is the local omission condition for the extended omitting types theorem for propositional logic.

A propositional formula is built from atomic propositions using logical connectives. Unlike a first-order formula, it has no quantifiers over individuals. A Boolean valuation interprets its atoms as truth values and evaluates its connectives recursively.

A subformula is a constituent propositional formula in a formula's recursive construction, including the whole formula itself. For an atomic variable the only subformula is itself; for $\neg A$, add $\neg A$ to the subformulas of $A$; for a binary connective, add the combined formula to the union of the two operands' subformulas. The set of distinct subformulas can have smaller cardinality than the number of occurrences in the abstract syntax tree when the same expression appears more than once.

A subformula occurrence specifies a particular position in the syntax tree of a formula. Two occurrences can contain the same logical formula while being different nodes. Replacement of one occurrence does not necessarily replace the others.

Subformula replacement is the operation of replacing one specified subformula occurrence by another logical formula. Its preservation of well-formedness is the subformula replacement theorem.

Replacing one designated subformula occurrence in a propositional formula by another propositional formula preserves well-formedness. Induct on the context surrounding the occurrence: at the root the result is the replacement formula; under a connective apply the induction hypothesis to the affected child and rebuild the parent using its formation rule.

Replacing a designated subformula by a logically equivalent formula preserves logical equivalence of the surrounding propositional formulas. For any Boolean valuation the two expressions at the replaced node have the same truth value. Each logical connective preserves this agreement when its other inputs are unchanged. Induction from that node to the root proves agreement of the whole formulas under every valuation.

Every propositional formula generated by a parenthesized grammar has equally many opening and closing parentheses. By structural induction, atomic formulas begin with equal zero counts; negation preserves them; and a parenthesized binary logical connective adds its two subformula counts and one parenthesis of each kind. An optional paired-parenthesis construction also adds one to both counts. This necessary syntactic invariant is useful for checking generated expressions, though equal counts alone do not guarantee correctly nested syntax.

A propositional substitution maps each atomic propositional variable to a propositional formula and extends recursively through every logical connective. Replacements are simultaneous: a variable appearing inside a replacement formula is not replaced again in the same substitution step. Since propositional logic has no variable-binding quantifiers, this operation has no variable-capture problem.

A conjunction containing each of a specified finite collection of Boolean variables exactly once, either positively or negated. It is satisfied by exactly one Boolean valuation of those variables. The minterms for all valuations are mutually exclusive and collectively exhaustive, so they can encode an arbitrary finite table of values.

The displayed identity follows by testing the two possible truth values of $p$. Existentially forgetting $p$ gives $A[p:=\top ]\vee A[p:=\perp ]$. Repeating this operation produces a propositional formula on a specified remaining vocabulary. Logical truth constants are needed if that vocabulary is empty.

If $A⊢B$, eliminate the letters private to $A$ byEvery assignment satisfying $A$ satisfies one disjunct of $C$. If an assignment satisfies $C$, change only the eliminated letters to its witnessing assignment. The modified assignment satisfies $A$ and hence $B$, whose letters were unchanged. Thus $A\models C\models B$, and the propositional completeness theorem gives the two derivations. The interpolant uses only common letters; an empty common vocabulary is handled by logical truth constants.

An implication is derivable from a theory precisely when its conclusion is derivable after adjoining its antecedent. Together with classical contradiction rules, this identifies failure to prove a proposition with consistency after adjoining its negation.

Conditional modus ponens derives $A\to C$ from $A\to B$ and $A\to (B\to C)$. It is the step which translates a modus ponens rule inference when discharging a common assumption. In the case-elimination Hilbert calculus, the third scheme first gives $A\to (\neg B\to C)$; the second scheme combines the two conditionals to give $A\to C$.

In the usual first-order Hilbert system, logical implication discharge requires the appropriate generalization restriction: a variable generalized in the derivation must not be free in the assumption being discharged. Equivalently use a proof system whose generalization rule already forbids variables free in open assumptions. One can first discharge a temporary assumption and then generalize if the quantified variable is not free in the remaining assumptions. Ignoring this side condition would allow deriving universal conclusions from a single arbitrary instance as an open hypothesis.

For standard effective proof presentations, the syntactic deduction theorem and its reverse give effective transformations between proofs in a one-sentence extension and proofs of an implication in the base theory. Arithmetic can verify these transformations, yielding the displayed internal equivalence under the usual representation and proof-predicate hypotheses. It distinguishes internal proof transformations from an unlicensed reflection step taking provability to truth.

Classical propositional logic interprets propositions as true or false and validates principles such as the law of excluded middle and double-negation elimination.

Assume $H=(P\to Q)\to P$ and temporarily assume $\neg P$. A further assumption $P$ yields a contradiction and hence $Q$ by the logical falsity elimination rule; discharge it to obtain $P\to Q$. Applying $H$ gives $P$, contradicting $\neg P$. Discharge the latter assumption to obtain $\neg \neg P$, apply double-negation elimination, and finally discharge $H$. This is a derivation from the primitive classical natural deduction rules. The principle is named for Charles Sanders Peirce.

A tautology is a propositional formula true under every Boolean valuation in classical propositional logic, such as the law of excluded middle $p\vee \neg p$. A primitive proposition $p$ is not a tautology, even if it represents a true statement. See forall x: Calgary, section 12.1.

An argument has logical validity in classical propositional logic when no Boolean valuation makes all premises $\Gamma$ true and the conclusion $A$ false: $\Gamma \models A$. With no premises, $\models A$ says that $A$ is a tautology. See forall x: Calgary, sections 12.4–12.6.

The law of excluded middle asserts that every proposition $A$ satisfies $A\vee \neg A$.

Double-negation elimination is the inference from $\neg \neg A$ to $A$.

A Boolean valuation $v$ assigns each primitive proposition a value in $\{\mathrm{F},\mathrm{T}\}$, equivalently $\{0,1\}$, and extends recursively to every propositional formula using the classical logical connectives. The same primitive proposition always receives the same value within one Boolean valuation. For compound propositional formulas $A$ and $B$,Every other case receives the opposite value. Thus $v(p)=\mathrm{T},v(q)=\mathrm{F}$ gives $v((p\to q)\wedge p)=\mathrm{F}$. A truth table varies the assignment; recursive evaluation computes one row. The truth-functional restriction means that changing what the primitive propositions describe, while retaining their values, cannot change the value of the compound propositional formula. See forall x: Calgary, chapter 9 and section 10.1.

A truth table lists a propositional formula's value for every Boolean valuation of its distinct primitive propositions. With $k$ primitive propositions, there are $2^k$ rows: each independently receives T or F. Evaluate compound columns from their subexpressions using the classical rules for logical connectives. This is exhaustive checking, so a formula true on every row is valid in classical propositional logic.

For a computed example over the natural numbers, let $A(n)$ mean that $n$ is an even number and $B(n)$ mean $n>2$. The choices $n=4,2,3,1$ realize respectively $(A,B)=(\mathrm{T},\mathrm{T}),(\mathrm{T},\mathrm{F}),(\mathrm{F},\mathrm{T}),(\mathrm{F},\mathrm{F})$: all four possible inputs.

The logical implication $A\to B$ and its contrapositive agree on every row; the converse implication $B\to A$ differs on two rows. A truth table therefore checks equivalence or supplies a counterexample. Classical truth conditions are given in forall x: Calgary, section 31.2. These two-valued truth tables do not characterize validity in Intuitionistic propositional logic.

A proposition is a statement to which a logical truth value can be assigned.

A logical connective forms a compound proposition from component propositions; logical truth and logical falsity are the zero-input cases. Logical negation has one input, while logical conjunction, logical disjunction, and logical implication each have two. In classical propositional logic, these logical connectives are truth-functional: their output value is determined by their input values, as listed in a truth table. This does not characterize every kind of logical connective in every logic. See forall x: Calgary, section 10.1.

A binary logical connective true exactly when its two arguments have the same truth value. It is logically equivalent to $(P\to Q)\wedge (Q\to P)$, and hence to $(\neg P\vee Q)\wedge (\neg Q\vee P)$. Its truth table has value one on input pairs $(0,0)$ and $(1,1)$, and zero on $(0,1)$ and $(1,0)$.

Logical implication forms the proposition $A\to B$, read “if $A$, then $B$”. In classical propositional logic, it is false exactly when $A$ is true and $B$ is false. Equivalently, it has the same truth table as $\neg A\vee B$, using logical negation and logical disjunction. A false hypothesis makes the logical implication true regardless of its conclusion; thus it asserts neither the hypothesis nor a causal connection.

For example, for every natural number $n$, divisibility by four implies that $n$ is an even number: $n=4k=2(2k)$. At $n=8$, both statements are true. At $n=6$, the hypothesis is false and the conclusion true; at $n=3$, both are false. The only forbidden case is a multiple of four that is not an even number.

In Intuitionistic propositional logic, a proof of $A\to B$ consists of a construction transforming any proof of $A$ into a proof of $B$. The implication introduction rule proves $B$ under a temporary assumption $A$; the modus ponens rule applies the result when $A$ is available. The classical identification with $\neg A\vee B$ is not generally intuitionistically valid.

For distinct propositional variables, eliminate each right-associated logical implication to obtain $\neg A_n\vee \cdots \vee \neg A_2\vee A_1$. Exactly one Boolean valuation falsifies all these disjuncts: $A_1=0$ and $A_2=\cdots =A_n=1$. Of the $2^n$ assignments, the other $2^n-1$ are satisfying assignments. Left-associated implication chains have a different meaning and need not have the same count.

The contrapositive of a logical implication $A\to B$ reverses the direction and applies logical negation to both sides: $\neg B\to \neg A$. In classical propositional logic they are equivalent, so either can be proved in place of the other. The contrapositive of “divisibility by four implies being an even number” says that a number that is not an even number cannot be divisible by four.

In Intuitionistic propositional logic, $A\to B$ still implies its contrapositive: assumptions $A$ and $\neg B$ would yield $B$ and hence a contradiction. The reverse direction is not generally valid. From $\neg B\to \neg A$ and $A$, one obtains only $\neg \neg B$; obtaining $B$ additionally requires double-negation elimination.

The converse implication of $A\to B$ is $B\to A$. It exchanges hypothesis and conclusion without logical negation. It need not follow from the original logical implication: $n=2$ is an even number but is not divisible by four. Thus “being an even number implies divisibility by four” is false, although the original implication holds for all natural numbers. Proving both directions establishes an “if and only if” statement; proving a contrapositive establishes the original implication classically, without establishing its converse implication.

A logical implication holds whenever its premise is false. For partial correctness, an execution that never terminates supplies no final state violating the postcondition.

The conjunction $A\wedge B$ holds when both $A$ and $B$ hold.

An AND gate computes $a\wedge b=ab$ for bits $a,b$. It is irreversible when only its one-bit output is retained. The Toffoli gate embeds the operation reversibly as $(a,b,c)\mapsto (a,b,c\oplus ab)$; setting $c=0$ preserves the inputs while recording their logical conjunction.

The disjunction $A\vee B$ holds when at least one of $A$ and $B$ holds. Constructively, a proof records which disjunct holds and provides its proof.

A logic gate computing inclusive logical disjunction: its output is one exactly when at least one input is one.

Logical truth is the nullary connective that is always true.

A logical matrix specifies truth values, designated values, and operations interpreting the primitive connectives. To prove nonderivability from an axiom set, it suffices that every axiom instance is designated and every inference rule preserves designation, while the proposed conclusion is not designated under some valuation. The primitive connective symbols need not receive their intended classical meanings: preservation by the displayed rules is what makes the syntactic obstruction valid. Rules with discharged assumptions, such as a deduction theorem for propositional logic, must also preserve consequence for arbitrary assumption sets.

Take ordinary material logical implication on $\{0,1\}$, designate $1$, and interpret negation by the constant-zero operation $N$. Then $A\to (B\to A)$ and $(NB\to A)\to (NA\to B)$ are always designated, and modus ponens rule and logical implication discharge preserve consequence. But $(NB\to NA)\to (A\to B)$ is false for $A=1,B=0$. Thus the first two schemes and the deduction rule do not derive the last scheme. This detects the loss of a genuine classical-negation principle even though all the displayed schemes are tautologies under the usual classical negation.

Logical falsity is the nullary connective with no proof.

In classical propositional logic, a truth value is false or true, encoded by a bit as zero or one. A Boolean valuation assigns these values to primitive propositions and extends to compound propositional formulas through logical connectives.

Natural deduction presents logic through introduction and elimination rules for each logical connective.

Reading an inference rule backwards to replace a desired conclusion by sufficient subgoals. A conjunction goal can be replaced by its two conjuncts using the conjunction introduction rule; an available disjunction can instead lead to two case subgoals using the disjunction elimination rule. Different choices change the organization and sharing of subproofs. Scope and assumption discharge conditions remain obligations even when a rule is applied backwards during proof search.

Adding unused assumptions to the context of a logical derivation. The original derivation still proves the same conclusion because it need not use every available assumption. When eigenvariables are used, rename them first if necessary to preserve the eigenvariable condition for any newly added assumptions. This explains how disjunction elimination with different branch contexts can be written using a common context containing all their assumptions.

Thinning enlarges the assumptions without changing a conclusion. In a predicate-calculus presentation with context-sensitive generalization, a generalization valid before adding an unused assumption may not be replayable with that assumption open. An explicit weakening step nevertheless imports the already proved conclusion. In propositional calculus with only axiom schemes and modus ponens, weakening is admissible by replaying the proof. The need for a separately stated rule depends on how proof dependencies are represented.

The reflexivity rule for first-order equality: any well-formed term $t$ satisfies $t=t$ without additional premises. Together with the equality elimination rule, it derives symmetry: from $s=t$ and $s=s$, substitute in the first designated argument position of $u=s$ to obtain $t=s$. Transitivity follows from $s=t$ and $t=u$ by substitution in the second designated argument position of $s=v$.

Derive each side of a logical biconditional under a temporary assumption of the other, then discharge both assumptions. The surrounding assumptions $\Gamma$ remain. This is equivalent to deriving the two implications and combining them as the two directions of equivalence.

Introduce exclusive or from either $P,\neg Q$ or $\neg P,Q$. To eliminate $P\oplus Q$, derive the same conclusion $K$ in two subproofs, one under $P,\neg Q$ and the other under $\neg P,Q$, then discharge both pairs of case assumptions. These rules express exactly the two disjuncts of the displayed disjunctive normal form. Conjunction introduction and disjunction introduction derive that formula in each elimination branch; conversely disjunction elimination and conjunction elimination supply the two introduction cases. This proves equivalence without adding an unproved truth-table inference to a formal derivation.

From $P$, temporarily assume $\neg P$. Negation elimination rule gives logical falsity; discharge that temporary assumption by negation introduction to obtain $\neg \neg P$. This is valid in Intuitionistic propositional logic, unlike unrestricted double-negation elimination.

A local derivation made under additional temporary assumptions. Its conclusions can be used within their scopes, but exporting a result requires a rule that accounts for those assumptions. Indentation, boxes or explicit assumption labels record that dependency information.

A temporary assumption is introduced for a hypothetical subproof and retained only within that scope. A suitable inference rule can discharge it while forming a conclusion valid under the surrounding assumptions. Its scope must be recorded even when the assumption is unused inside the subproof.

From $\varphi \to (\psi \to \rho )$ infer $(\varphi \to \psi )\to (\varphi \to \rho )$. Assume $\varphi \to \psi$, then assume $\varphi$. Implication elimination rule gives $\psi$ and $\psi \to \rho$, hence $\rho$. Discharge $\varphi$ and then $\varphi \to \psi$ by the implication introduction rule. The original premise and any surrounding assumptions remain available.

From a logical derivation of $\psi$, infer $\varphi \to \psi$ under the same surrounding assumptions. To derive the rule, temporarily assume $\varphi$, retain the available $\psi$, and discharge $\varphi$ by the implication introduction rule. Its being unused is allowed.

From $\exists xA(x)$, reason under a temporary assumption $A(u)$ for a fresh witness $u$. If this yields a conclusion $B$ not containing $u$ free, close the witness subproof and infer $B$. The eigenvariable condition also requires that $u$ not be free in other undischarged assumptions. The rule does not authorize selecting one fixed named object as a witness or allowing the witness to escape its scope.

An eigenvariable condition ensures that a variable chosen as arbitrary or as an existential witness cannot smuggle extra information into a quantifier inference. For the universal quantifier introduction rule, the generalized variable must not occur free in any undischarged assumption. For the existential quantifier elimination rule, the fresh witness must not occur free in the resulting conclusion or in the other undischarged assumptions. Temporary assumptions may contain it if they are discharged before the final inference.

A variable used as an arbitrary parameter in a natural deduction subproof, subject to an eigenvariable condition. For universal introduction, it must be free in no undischarged assumption. For existential elimination, a temporary witness must also be free in no conclusion exported from its subproof. These restrictions distinguish an arbitrary object from one constrained by a special hypothesis.

An invalid quantifier inference that exports a formula still referring freely to a temporary existential witness. From $\exists xS(x)$ one cannot infer $S(v)$ for an independently named object $v$. A two-element interpretation with exactly one $S$-object refutes that inference. Introducing another quantifier after the invalid step does not repair it; the introduction must take place before the witness scope is closed.

Assumption discharge closes a designated temporary assumption together with its dependent subproof. Implication introduction rule turns a logical derivation of $B$ under $A$ into $A\to B$ outside that temporary scope. Negation introduction rule turns a logical derivation of logical falsity under $A$ into $\neg A$. Disjunction elimination rule discharges its separate case assumptions while retaining any surrounding premises.

From logical falsity infer any proposition. This rule permits a contradictory case inside a disjunction elimination rule proof to reach the common required conclusion.

From $s=t$ and $A(s)$, infer $A(t)$ by capture-free substitution. Rewriting in the opposite direction first uses symmetry of equality.

From $A(t)$, infer $\exists xA(x)$ when the substitution is capture-free. The term $t$ supplies a witness.

From $\forall xA(x)$, infer $A(t)$ provided the substitution is free for $x$, meaning no free variable of $t$ becomes captured.

If $A(u)$ is proved and $u$ is not free in any undischarged assumption, infer $\forall xA(x)$, with capture-free replacement. The freshness condition prevents generalizing from a special object.

From $A\leftrightarrow B$, infer $A\to B$ or $B\to A$. Applying the resulting implication requires a further modus ponens rule.

From $A\vee B$ and two subproofs deriving the same conclusion $C$, one under an additional assumption $A$ and the other under an additional assumption $B$, infer $C$ and discharge those two case assumptions. Any other assumptions remain in force.

If each of $A$, $B$ and $C$ separately yields the same conclusion $K$, then $A\vee B\vee C$ yields $K$, with the three case assumptions discharged. For $(A\vee B)\vee C$, first eliminate the outer logical disjunction, using a nested applications of the disjunction elimination rule on the $A\vee B$ branch. For $A\vee (B\vee C)$, nest the second elimination in the other branch. Common surrounding assumptions remain open.

From $A$, infer $A\vee B$; from $B$, infer $A\vee B$.

From $A\wedge B$, infer either $A$ or $B$.

From derivations of $A$ and $B$ under the current assumptions, infer $A\wedge B$.

From a propositional formula and its negation, infer logical falsity. This identifies a contradiction inside a natural deduction derivation; a later negation introduction rule may discharge the assumption that led to it.

If a natural deduction subproof derives logical falsity from a temporary assumption $P$, discharge that assumption to conclude $\neg P$. Other undischarged assumptions remain available. This gives a constructive proof of a negation and does not require double-negation elimination.

The rule with premises $C,D$ and conclusion $C$ retains the first derivation while allowing an unused second assumption. Under the Curry-Howard correspondence, the output term is the first premise term, with the enlarged context. This allows a lambda abstraction whose bound variable does not occur in its body.

From $A\to B$ and $A$, implication elimination derives $B$. Under the Curry-Howard correspondence, this is application: from lambda terms $f:A\to B$ and $a:A$ form $fa:B$.

The implication introduction rule discharges a temporary assumption $A$ from a derivation of $B$, producing $A\to B$. Under the Curry-Howard correspondence, a body $t:B$ under $a:A$ gives the lambda abstraction $\lambda a^A.t:A\to B$. Unused assumptions may also be discharged.

Intuitionistic propositional logic omits unrestricted excluded middle and interprets implication constructively.

A lattice is a partially ordered set in which every pair has a greatest lower bound, called its meet, and a least upper bound, called its join.

In a lattice, joins and meets are the pairwise least upper bounds and greatest lower bounds.

The join of two elements of a lattice is their least upper bound. In a lattice of closed set families, it is the closure of their union.

The meet of two elements of a lattice is their greatest lower bound. For set families ordered by inclusion, it is their intersection whenever that intersection lies in the specified lattice.

A homomorphism between lattices preserves binary joins and meets: $f(x\vee y)=f(x)\vee f(y)$ and $f(x\wedge y)=f(x)\wedge f(y)$. It is order preserving, since $x\le y$ implies $x=x\wedge y$ and hence $f(x)=f(x)\wedge f(y)$. For a map into the two-element lattice, the inverse image of zero is a lattice ideal, and meet preservation says this ideal is prime: if a meet belongs to it, at least one factor does. Conversely the indicator of the complement of a prime lattice ideal preserves both operations. Preservation of distinguished top and bottom elements is an additional requirement for homomorphisms of bounded lattices.

A complete lattice is a partially ordered set in which every subset has a meet and a join, including the empty subset.

Every order-preserving function from a complete lattice to itself has a least and a greatest fixed point. More strongly, its set of fixed points is itself a complete lattice.

A distributive lattice is a lattice in which meet distributes over join and, equivalently, join distributes over meet.

In a distributive lattice,

A Boolean algebra is a bounded distributive lattice in which every element has a complement. Its meet, join, and complement abstract conjunction, disjunction, and negation.

An atom is a minimal nonzero Boolean-algebra element. In a Lindenbaum algebra, its nonempty formula class isolates a complete type. A finite Boolean algebra is the power set of its finite atom set. An infinite atomic Boolean algebra need not contain every union of atoms: the finite-cofinite algebra is a simple counterexample.

On an infinite set $D$, take its finite and cofinite subsets with ordinary union, intersection and complement. Singletons are its atoms. Its Stone space consists of the isolated points of $D$ together with one nonisolated point whose ultrafilter contains all cofinite sets. For countably infinite $D$ this is a countable Boolean algebra with countably many atoms, not the uncountable full power set. It describes two-vector definability over a countably infinite field: dependent directions are isolated atoms and the independent-pair type is the additional nonisolated point.

Every proper lattice ideal of a Boolean algebra extends to a prime lattice ideal. More generally, an ideal disjoint from a lattice filter extends to a prime ideal still disjoint from that filter. This Boolean case of the Stone prime filter theorem is equivalent to the ultrafilter lemma over Zermelo–Fraenkel set theory and is weaker than the axiom of choice.