Propositions and truth functions

A proposition is a statement treated as true or false in classical logic. Negation reverses its truth value. Conjunction requires both component statements to be true. Inclusive disjunction requires at least one to be true and allows both. These are definitions, so a mathematical “or” need not mean the exclusive choice suggested by a restaurant menu. Name the component statements before manipulating a compound sentence; otherwise the meaning can change halfway through a calculation.

For example, let P assert that an integer is even and Q that it is divisible by three. At the integer six, both propositions hold, so their disjunction holds too. At the integer four, only P holds, but the disjunction still holds. Parentheses specify which propositions a connective combines. The negation of a conjunction denies that both hold together; it does not insist that both fail. Testing four truth assignments makes this distinction visible.

The implication “if P, then Q” is false precisely when P is true and Q is false. When P is false, the implication is true under this truth-functional definition. It does not establish a causal connection, a chronological order, or that P ever happens. A theorem about all objects satisfying a hypothesis likewise has no failure at objects outside that hypothesis. This convention makes conditional reasoning compose consistently across different mathematical domains.

The converse exchanges hypothesis and conclusion and generally requires a separate proof. For integers, divisibility by four implies evenness, but evenness does not imply divisibility by four. The integer six separates the two statements. The contrapositive instead negates and reverses both sides; it has exactly the original truth table. Distinguish these transformations before choosing a proof method, because an elegant argument for a converse can still miss the requested theorem completely.

To check a proposed equivalence with two atomic propositions, enumerate all four possible assignments and evaluate both expressions in each row. Agreement in every row proves the equivalence as a statement of propositional logic. A single disagreement refutes it. This finite exhaustiveness is stronger than checking several arithmetic instances, because arithmetic instances might not realize every relevant assignment. A truth table proves a logical pattern, while a theorem can additionally depend on relationships between its mathematical predicates.

Biconditional means that each proposition implies the other. It is true when their truth values agree, including when both are false. A tautology is true on every assignment; a contradiction is false on every assignment. Keep the distinction between the object-language expression and a claim about that expression: writing a biconditional inside a formula differs from explaining that two formulas are equivalent. In either notation, state the range of assignments or objects over which the comparison is intended.