Grouping does not affect the truth value of a chain of conjunctions. Parentheses can be omitted when only AND connectives appear, justifying the unparenthesized form P∧Q∧R.
Grouping does not affect the truth value of a chain of disjunctions. Parentheses can be omitted when only OR connectives appear, justifying the unparenthesized form P∨Q∨R.
Conjunction distributes over disjunction: a single AND with a parenthesized OR can be rewritten as an OR of two ANDs. This is the core step for converting formulas into Disjunctive Normal Form.
Disjunction distributes over conjunction: a single OR with a parenthesized AND can be rewritten as an AND of two ORs. This is the core step for converting formulas into Conjunctive Normal Form.
Conjoining any proposition with the always-false constant ⊥ yields ⊥. Falsity dominates conjunction: a single false operand forces the entire AND to be false.
Disjoining any proposition with the always-true constant ⊤ yields ⊤. Truth dominates disjunction: a single true operand forces the entire OR to be true.
Every proposition is either true or false — there is no third option. The disjunction of a proposition with its own negation is always true, regardless of the truth value of P.
No proposition can be simultaneously true and false. The conjunction of a proposition with its own negation is always false, regardless of the truth value of P.
Negating a conjunction is equivalent to disjoining the negations of its parts. The negation crosses the parentheses, the connective flips from AND to OR, and each operand is negated.
Negating a disjunction is equivalent to conjoining the negations of its parts. The negation crosses the parentheses, the connective flips from OR to AND, and each operand is negated.
When P already appears at the outer AND, wrapping it together with anything inside an inner OR adds no information — the result simplifies back to P. The inner disjunction is "absorbed" by the outer P.
When P already appears at the outer OR, wrapping it together with anything inside an inner AND adds no information — the result simplifies back to P. The inner conjunction is "absorbed" by the outer P.
From any true proposition P, one may infer the disjunction of P with anything. Adding alternatives to a true claim cannot make it false. Also called the addition rule.
A conditional can be rewritten as a disjunction. The conditional fails only when P is true and Q is false — equivalently, when ¬P is false and Q is false, i.e. when ¬P∨Q is false. In every other case both expressions are true.
A conditional is logically equivalent to its contrapositive — both parts negated and swapped. This equivalence is the basis for proof by contraposition: to prove P→Q, one may instead prove ¬Q→¬P.
The negation of a conditional is a conjunction, not another conditional. To deny "if P then Q" is to assert that P holds while Q fails — the one case in which the implication is broken.
A conditional with a conjunctive antecedent can be rewritten as a chain of conditionals — pulling one conjunct out into a separate hypothesis. Used to convert between curried and uncurried forms of multi-premise rules.
A biconditional asserts both directions of implication at once. To prove P↔Q, one proves P→Q and Q→P separately; this equivalence is the foundation of every "if and only if" proof.
A biconditional is true exactly when both operands share the same truth value — either both true or both false. The disjunction enumerates these two satisfying cases, putting the formula directly into Disjunctive Normal Form.
The negation of a biconditional is the exclusive-or pattern: true when P and Q disagree. The two disjuncts enumerate the two ways disagreement can occur — P true with Q false, or P false with Q true.
The negation of the truth constant is the falsity constant. Tautology and contradiction are duals under negation: applying ¬ to a formula that is always true produces a formula that is always false.
The negation of the falsity constant is the truth constant. Tautology and contradiction are duals under negation: applying ¬ to a formula that is always false produces a formula that is always true.