Propositional Logic - Key Properties

The fundamental semantic properties of propositional formulas classify them according to their truth behavior across all possible valuations.

DefinitionTautology, Contradiction, Contingency

Let $\phi$ be a propositional formula.

$\phi$ is a tautology (or valid) if $\phi$ is true under every truth assignment. We write $\models \phi$ .
$\phi$ is a contradiction (or unsatisfiable) if $\phi$ is false under every truth assignment.
$\phi$ is contingent (or satisfiable) if $\phi$ is true under at least one truth assignment.

ExampleClassic Tautologies

The following formulas are tautologies:

Law of Excluded Middle: $p \lor \neg p$
Law of Non-Contradiction: $\neg(p \land \neg p)$
Modus Ponens: $(p \land (p \to q)) \to q$
Law of Syllogism: $((p \to q) \land (q \to r)) \to (p \to r)$

Each can be verified by constructing a truth table with all possible assignments to the propositional variables.

DefinitionLogical Equivalence

Two formulas $\phi$ and $\psi$ are logically equivalent, written $\phi \equiv \psi$ , if they have the same truth value under every truth assignment. Equivalently, $\phi \equiv \psi$ if and only if $\phi \leftrightarrow \psi$ is a tautology.

Important logical equivalences include:

\begin{align} \text{De Morgan's Laws:} \quad &\neg(p \land q) \equiv \neg p \lor \neg q \\ &\neg(p \lor q) \equiv \neg p \land \neg q \\ \text{Implication:} \quad &p \to q \equiv \neg p \lor q \\ \text{Contrapositive:} \quad &p \to q \equiv \neg q \to \neg p \\ \text{Distributivity:} \quad &p \land (q \lor r) \equiv (p \land q) \lor (p \land r) \end{align}

DefinitionLogical Consequence

A formula $\psi$ is a logical consequence of formulas $\phi_1, \ldots, \phi_n$ , written $\phi_1, \ldots, \phi_n \models \psi$ , if every truth assignment that makes all of $\phi_1, \ldots, \phi_n$ true also makes $\psi$ true.

Remark

The relationship between tautology and logical consequence is fundamental: $\phi_1, \ldots, \phi_n \models \psi$ if and only if $(\phi_1 \land \cdots \land \phi_n) \to \psi$ is a tautology. This connects semantic consequence with the validity of implications.

These properties allow us to reason about formulas without computing truth tables explicitly, forming the basis for efficient logical reasoning and proof systems.