Propositional logic
Logic is the grammar of mathematics and computer science. It tells us exactly when a statement is true and when one statement follows from others.
Propositions
A proposition is a statement that is either true or false, such as '7 is prime' or 'it is raining'. Questions and commands are not propositions. We name propositions with letters \(p\), \(q\), \(r\) and combine them with connectives to build compound statements.
Connectives
Negation \(\neg p\) ('not p') flips the truth value. Conjunction \(p \wedge q\) ('p and q') is true only when both are true. Disjunction \(p \vee q\) ('p or q') is true when at least one is true; this inclusive 'or' differs from everyday 'either-or'. Truth tables list the result for every combination of inputs.
The conditional
The conditional \(p \to q\) ('if p then q') is false only when \(p\) is true and \(q\) is false. A promise 'if you finish your homework, you can watch TV' is broken only if homework is finished and TV is refused. When \(p\) is false, the conditional is vacuously true. The biconditional \(p \leftrightarrow q\) is true when both sides match.
p \to q \equiv \neg p \vee qConverse, inverse, contrapositive
From \(p \to q\): the converse is \(q \to p\), the inverse is \(\neg p \to \neg q\), and the contrapositive is \(\neg q \to \neg p\). Only the contrapositive is logically equivalent to the original. 'If it is a dog, it is a mammal' is true; its converse 'if it is a mammal, it is a dog' is false.
Logical equivalence and De Morgan's laws
Two statements are equivalent if they have the same truth table. De Morgan's laws are essential: \(\neg(p \wedge q) \equiv \neg p \vee \neg q\) and \(\neg(p \vee q) \equiv \neg p \wedge \neg q\). 'Not (hungry and tired)' means 'not hungry or not tired'. Programmers use these laws constantly to simplify conditions.
\neg(p \wedge q) \equiv \neg p \vee \neg qTautologies and contradictions
A tautology is always true, such as \(p \vee \neg p\). A contradiction is always false, such as \(p \wedge \neg p\). A statement that is neither is contingent. Valid arguments correspond to tautologies: the premises imply the conclusion in every case.
Predicates and quantifiers
A predicate like \(P(x)\): '\(x\) is even' becomes a proposition when \(x\) is specified. The universal quantifier \(\forall x\, P(x)\) means 'for all \(x\)'; the existential \(\exists x\, P(x)\) means 'there exists an \(x\)'. Negation swaps them: \(\neg\forall x\, P(x) \equiv \exists x\, \neg P(x)\). To disprove 'all primes are odd', one counterexample, 2, suffices.
\neg \forall x\,P(x) \equiv \exists x\,\neg P(x)Worked example
Negate 'every student passed some exam'. In symbols: \(\forall s\, \exists e\, \text{Passed}(s, e)\). Negating swaps both quantifiers and negates the predicate: \(\exists s\, \forall e\, \neg\text{Passed}(s, e)\): 'some student failed every exam'. Careful negation of quantified statements is a key skill in proofs.
Key takeaways
Propositions are true or false; connectives combine them. \(p \to q\) is false only when \(p\) is true and \(q\) false, and is equivalent to its contrapositive. De Morgan's laws distribute negation. Quantifiers \(\forall\) and \(\exists\) swap under negation, and one counterexample disproves a universal claim.
Flashcard
A statement that is true or false
Check your understanding
Which statement is logically equivalent to 'If it rains, the ground is wet'?