Laws of logic and rules of inference_

(p ∧ (p ⇒ q)) ⇒ q

Modus ponens (Latin for “the mode that affirms”) is the most basic rule of inference in propositional logic. It states that from an implication p ⇒ q and the truth of p we may conclude q. Its truth table shows that (p ∧ (p ⇒ q)) ⇒ q is a tautology: there is no row where the premises are true and the conclusion is false.

((p ⇒ q) ∧ ¬q) ⇒ ¬p

Modus tollens (“the mode that denies”) is the rule of inference that, from an implication p ⇒ q and the negation of its consequent ¬q, concludes the negation of the antecedent ¬p. It is the reasoning behind every refutation: if a theory predicts something that does not happen, the theory is false. The formula ((p ⇒ q) ∧ ¬q) ⇒ ¬p is a tautology.

((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r)

The hypothetical syllogism (also called transitivity of implication) lets you chain conditionals: if p ⇒ q and q ⇒ r, then p ⇒ r. It is the rule that makes chained reasoning possible, and the formula ((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r) is a three-variable, eight-row tautology.

((p ∨ q) ∧ ¬p) ⇒ q

The disjunctive syllogism (also called modus tollendo ponens) starts from a disjunction p ∨ q and the negation of one of its parts, ¬p, to conclude the other, q. It is the reasoning of “ruling out options”: if there are only two possibilities and one is eliminated, the remaining one must hold. The formula ((p ∨ q) ∧ ¬p) ⇒ q is a tautology.

(((p ⇒ q) ∧ (r ⇒ s)) ∧ (p ∨ r)) ⇒ (q ∨ s)

The constructive dilemma is a four-variable rule of inference: from p ⇒ q, r ⇒ s and p ∨ r we conclude q ∨ s. It is a modus ponens “in parallel”: we know p or r happens, and each has its consequence, so one of the consequences must happen. The full formula is a 16-row tautology.

¬(p ∧ q) ⇔ (¬p ∨ ¬q)

The first De Morgan law states that negating “p and q” is the same as asserting “not p or not q”. Formally, ¬(p ∧ q) ⇔ (¬p ∨ ¬q) is a tautology: both columns agree in all four rows. It is one of the most used equivalences for simplifying logical expressions and conditions in code.

¬(p ∨ q) ⇔ (¬p ∧ ¬q)

The second De Morgan law says that negating “p or q” is equivalent to asserting “not p and not q”: ¬(p ∨ q) ⇔ (¬p ∧ ¬q). It captures the only way a disjunction can be false: both parts must be false. Like the first law it is a tautology and an essential tool for simplifying negated conditions.

(p ⇒ q) ⇔ (¬q ⇒ ¬p)

The contrapositive (or transposition) law states that “if p then q” says exactly the same as “if not q then not p”. The formula (p ⇒ q) ⇔ (¬q ⇒ ¬p) is a tautology. It is the basis of proof by contrapositive and the reason modus tollens is valid.

(p ⇒ q) ⇔ (¬p ∨ q)

The material implication law says the conditional p ⇒ q is equivalent to the disjunction ¬p ∨ q: “if p then q” is the same as “not p, or q”. This equivalence, a tautology, lets you eliminate the ⇒ operator from any formula and explains why an implication with a false antecedent is true.

(p ⇔ q) ⇔ ((p ⇒ q) ∧ (q ⇒ p))

The biconditional p ⇔ q (“p if and only if q”) is defined as the conjunction of the two implications p ⇒ q and q ⇒ p. The formula (p ⇔ q) ⇔ ((p ⇒ q) ∧ (q ⇒ p)) is a tautology and explains why “if and only if” proofs always have two parts.

(p ⊕ q) ⇔ ((p ∨ q) ∧ ¬(p ∧ q))

Exclusive disjunction or XOR (p ⊕ q) is true when exactly one of the two propositions is true. It is defined from the basic operators as “p or q, and not (p and q)”: (p ⊕ q) ⇔ ((p ∨ q) ∧ ¬(p ∧ q)) is a tautology. It is the everyday “or” when we mean “one or the other”.

((p ∧ q) ⇒ r) ⇔ (p ⇒ (q ⇒ r))

The exportation law states that “if p and q, then r” is equivalent to “if p, then (if q, then r)”. The formula ((p ∧ q) ⇒ r) ⇔ (p ⇒ (q ⇒ r)) is a three-variable tautology. It turns several hypotheses into a chain of conditionals and is the logical version of currying in functional programming.

(p ∧ (q ∨ r)) ⇔ ((p ∧ q) ∨ (p ∧ r))

Conjunction distributes over disjunction exactly as multiplication distributes over addition in arithmetic. It lets you factor a formula out or expand it without changing its truth value, and it is one of the basic tools for converting expressions into normal form.

(p ∨ (q ∧ r)) ⇔ ((p ∨ q) ∧ (p ∨ r))

This law is the twin of the distributive law of ∧ over ∨, and it is surprising because arithmetic has no counterpart: a + (b · c) is not equal to (a + b) · (a + c). In logic, however, both directions are valid and each is proved with an eight-row table.

(p ∨ (p ∧ q)) ⇔ p

Absorption is the simplification law par excellence: when one alternative is already contained in another, it is redundant. The formula p ∨ (p ∧ q) reduces to plain p, whatever q says, and its truth table confirms it in all four rows.

(p ∧ p) ⇔ p

Idempotence expresses something that looks obvious but is worth stating formally: asserting the same thing twice adds no information. Both p ∧ p and p ∨ p are equivalent to p, a property that sets logic apart from arithmetic, where a + a is not a.

(p ∧ q) ⇔ (q ∧ p)

Commutativity says that the order of the operands does not change the truth value of a conjunction or a disjunction. It feels so natural that it is used without thinking, but it pays to know exactly which operators satisfy it: the conditional, for one, does not commute.

¬¬p ⇔ p

Double negation states that negating a proposition twice returns the original proposition. It is one of the simplest laws of classical logic and, at the same time, one of the most debated: intuitionistic logic rejects it precisely because of its philosophical consequences.

p ∨ ¬p

The law of excluded middle states that every proposition is either true or false, with no third possibility. Formally, p ∨ ¬p is a tautology: the most frequently cited example of a formula that is true in every row of its truth table.

¬(p ∧ ¬p)

The law of non-contradiction states that no proposition can be true and false at the same time. Its formalisation, ¬(p ∧ ¬p), is a tautology, and it is the foundation on which the consistency of any formal system rests.

((p ⇒ q) ⇒ p) ⇒ p

Peirce's law is a remarkable curiosity: a classical tautology written purely with conditionals, without a single negation. Its statement, ((p ⇒ q) ⇒ p) ⇒ p, looks baffling at first sight, but the truth table confirms it in all four rows.

((p ⇒ q) ∧ q) ⇒ p

Affirming the consequent is the most common formal fallacy because it looks so much like modus ponens. The difference is crucial: here the conclusion of the implication is affirmed in order to deduce its condition, and that is invalid. The truth table proves it: the formula is a contingency, not a tautology.

((p ⇒ q) ∧ ¬p) ⇒ ¬q

Denying the antecedent is the other major formal fallacy tied to the conditional. It consists in believing that if the condition fails, the consequence must fail too. The truth table shows the reasoning is invalid: the formula is a contingency.