Mathematical logic studies how truth values combine. A proposition is a declarative sentence that is either true or false. A question, command, or open sentence such as x + 2 = 5 is not yet a proposition unless a value or quantifier fixes its meaning.
How do the main connectives change truth values?
The negation ¬p reverses p. A conjunction p ∧ q is true only when both parts are true. A disjunction p ∨ q is true when at least one part is true. The implication p → q is false only when p is true and q is false; it does not claim that p causes q.
Truth tables test every possible case
Two propositions produce four rows: TT, TF, FT, and FF. Comparing the final columns proves equivalence. De Morgan's law ¬(p ∧ q) ≡ ¬p ∨ ¬q holds because both expressions have the same truth value in every row, not because they merely agree in one example.
Evaluate a logical row
Toggle p and q to inspect conjunction, implication, and the negation of the conjunction.
Translating a conditional statement
“If an integer is divisible by 4, then it is even” has p = “divisible by 4” and q = “even”. Its converse swaps the parts and is false: an even integer such as 6 need not be divisible by 4. The contrapositive ¬q → ¬p is equivalent to the original statement.
Tautology, contradiction, and valid argument
A tautology is true in every row; a contradiction is false in every row. An argument is valid when no row makes all premises true and the conclusion false. Validity concerns structure, while the truth of premises is a separate question.
Propositions, open sentences, and classical principles
A proposition is a declarative sentence with exactly one truth value. “7 is prime” is true and “10 is odd” is false. Questions and commands are not propositions. The expression x + 1 = 0 is open because its truth depends on x; it becomes true for x = −1 and false for x = 2. The law of non-contradiction prevents the same proposition from being both true and false in the same setting, while the law of excluded middle allows no third classical truth value.
Connectives and compound propositions
Letters such as p, q, and r stand for simple propositions. The main connectives are conjunction p ∧ q, inclusive disjunction p ∨ q, negation ¬p, implication p → q, and biconditional p ↔ q. Parentheses matter: ¬p ∨ q negates only p, whereas ¬(p ∨ q) negates the whole disjunction.
How to read the truth table
A conjunction is true only when both parts are true. An inclusive disjunction is true when at least one part is true. An implication is false only for T → F: the condition occurs but the promised conclusion fails. A biconditional is true when its two parts have the same truth value.
| p | q | p ∧ q | p ∨ q | p → q | p ↔ q |
|---|---|---|---|---|---|
| V | V | V | V | V | V |
| V | F | F | V | F | F |
| F | V | F | V | V | F |
| F | F | F | F | V | V |
How many rows does a truth table need?
With n simple propositions there are 2ⁿ assignments. Two propositions require 2² = 4 rows; three require 2³ = 8. For p, q, and r, let p change in blocks of four rows, q in blocks of two, and r every row. This lists every assignment exactly once.
Worked example, column by column
Evaluate (p → q) ∨ r. First create eight rows because there are three variables. Next compute p → q; it is false only where p is true and q is false. Finally combine that intermediate column with r using ∨. Every row with r true gives a true final value. When r is false, the result matches p → q. Only p = T, q = F, r = F gives false, so the formula is contingent rather than a tautology.
Negation, equivalence, and classification
Negation swaps true and false. De Morgan’s laws state that ¬(p ∧ q) is equivalent to ¬p ∨ ¬q, and ¬(p ∨ q) to ¬p ∧ ¬q. A tautology has only true values in its final column, such as p ∨ ¬p. A contradiction has only false values, such as p ∧ ¬p. A mixture is a contingency. One counterexample with true premises and a false conclusion is enough to invalidate an argument.
From everyday language to a testable logical form
Logical analysis starts by separating declarative propositions from open sentences, questions, and commands. A proposition has a truth value. An open sentence such as x > 4 does not have one until x is fixed or quantified. Translating the sentence correctly matters more than filling a truth table quickly.
The inclusive or used in propositional logic allows both parts to be true. An implication p implies q claims that no case has p true and q false; it does not claim that q causes p. The converse q implies p and the inverse not p implies not q are different statements. The contrapositive not q implies not p is logically equivalent to the original implication.
Operator scope must be explicit. Negating a conjunction produces a disjunction of the negations, and negating a disjunction produces a conjunction. Parentheses show whether a connective applies to one proposition or to an entire compound expression.
A truth table is a complete test because it includes every assignment. With n simple propositions there are two to the n rows. A tautology is true on every row, a contradiction is false on every row, and a contingency has both values. An argument is valid when no row makes all premises true and the conclusion false.
Build only the columns you need
List the simple propositions, count the rows, and create columns from the innermost parentheses outward. For an argument, inspect only rows where every premise is true. For equivalence, compare the two final columns row by row instead of relying on how similar the expressions look.
Solved exercise 1: negate a compound statement
- Define the propositions
Let p mean “the integer is even” and q mean “the integer is positive”. The original statement is p and q.
- Negate the whole statement
The negation says that it is not true that both conditions hold.
- Apply De Morgan’s law
Move the negation to each simple proposition and change and to or.
- Interpret the result
The correct wording is “the integer is not even or it is not positive”. The or is inclusive, so both failures are allowed.
Solved exercise 2: test modus tollens
- Write the argument
The premises are p implies q and not q; the proposed conclusion is not p.
- Count the assignments
There are two simple propositions, so four rows are enough.
- Search for a counterexample
On every row where p implies q and not q are both true, q is false and p must also be false. No row has true premises and a false conclusion.
- Classify the reasoning
The associated conditional is a tautology, so modus tollens is valid. This does not license affirming the consequent, which has a different form.
How to audit a truth-table solution
Check the row count before evaluating any connective. For three propositions, eight rows are required.
Then check the single false case of implication, the scope of every negation, and the difference between inclusive disjunction and exclusive everyday usage. One row with true premises and a false conclusion is enough to refute validity; many true rows cannot repair that counterexample.
