Source: Homework 02, Foundations of Computer Science (Purdue)
Tags: propositional logic, truth values, De Morgan's law, conditional statements, contrapositive, converse, inverse, direct proof, proof by contradiction, proof by contrapositive, counterexample, biconditional proof, even odd parity, CS 18200, discrete math
Difficulty: Intermediate | Prerequisites: Propositional connectives (∧, ∨, →, ¬), truth tables, basic algebra with integers.
Once you can write logical statements, you need to evaluate them and prove things about them. This material covers two related skills: determining truth values from given information (propositional reasoning), and constructing formal proofs about numbers and equations. These are the tools you will use in every proof-based course from here forward, including algorithms, theory of computation, and formal verification. You should already be comfortable with truth tables and basic integer arithmetic.
Propositional reasoning uses De Morgan's laws and implication rules to extract truth values from compound statements. Proof techniques (direct proof, contrapositive, contradiction, counterexample) are strategies for establishing or refuting mathematical claims. Most biconditional proofs split into two directions, each using whichever technique is cleanest.
De Morgan's laws (propositional)
¬(p ∨ q) ≡ ¬p ∧ ¬q, and ¬(p ∧ q) ≡ ¬p ∨ ¬q. Negating a compound statement flips the connective and negates each part. Think of it as: negation turns OR into AND and AND into OR, while negating everything inside.
Conditional (implication)
p → q. Read "if p then q." True in every case except when p is true and q is false. In simple terms, a conditional only fails when the hypothesis holds but the conclusion does not.
Contrapositive
The contrapositive of p → q is ¬q → ¬p. These are logically equivalent: proving one proves the other. This is the single most useful equivalence in proof writing.
Converse
The converse of p → q is q → p. The converse is not logically equivalent to the original. A true statement can have a false converse. Students mix this up with the contrapositive constantly.
Inverse
The inverse of p → q is ¬p → ¬q. Also not equivalent to the original. The inverse is the contrapositive of the converse.
Biconditional
p ↔ q, read "p if and only if q." True when p and q have the same truth value. Equivalent to (p → q) ∧ (q → p). Proving a biconditional almost always means proving both directions separately.
Direct proof
To prove p → q directly: assume p is true, then use definitions, algebra, and known results to derive that q must also be true.
Proof by contrapositive
To prove p → q: instead prove ¬q → ¬p. Assume ¬q, derive ¬p. Since the contrapositive is equivalent, this proves the original.
Proof by contradiction
To prove a statement S: assume ¬S, derive a logical contradiction (something that cannot be true). Since the assumption leads to impossibility, S must be true.
Proof by counterexample (disproof)
To disprove a universal claim "for all x, P(x)": find one specific x where P(x) is false. One concrete example is sufficient.
When you are given that certain compound statements are true, you can work out the truth values of individual propositions by breaking the compounds apart.
Worked example (Problem 5 pattern):
Given these are all true:
¬(p ∨ ¬q)
¬(q → r)
¬r
Start with what is simplest. From ¬r: r is false.
From ¬(p ∨ ¬q), apply De Morgan's: ¬p ∧ q. So p is false and q is true.
From ¬(q → r): recall q → r ≡ ¬q ∨ r. Its negation is q ∧ ¬r. So q is true and r is false. This is consistent with what we already found.
Conclusion: p is false, q is true, r is false. We can definitively say p is false, not true. All three statements agree, no contradiction arises, and p = F is the only consistent assignment.
The method: peel apart each statement using De Morgan's and implication rewriting, collect what each tells you about individual variables, check for consistency.
Given a true conditional p → q, two related forms come up on nearly every exam.
The contrapositive ¬q → ¬p is valid.
If "n > 1 → n² > 1" is true, then its contrapositive "n² ≤ 1 → n ≤ 1" is also true. They are the same logical claim, just written backwards with everything negated.
The converse q → p is not necessarily valid.
From "n > 1 → n² > 1," the converse would be "n² > 1 → n > 1." This is a separate claim that may or may not be true. Here it fails: n = −2 gives n² = 4 > 1, but n = −2 is not greater than 1.
The exam will test whether you can distinguish these. The contrapositive is always equivalent. The converse is a separate statement that requires its own proof.
To disprove "the equation 3x² + 2y² = 22 has no positive integer solutions," you need to find positive integers x and y that satisfy it.
Try small values systematically:
x = 1: 3(1) + 2y² = 22, so 2y² = 19. Not an integer solution.
x = 2: 3(4) + 2y² = 22, so 12 + 2y² = 22, so 2y² = 10, so y² = 5. Not a perfect square.
x = 1, y = 1: 3 + 2 = 5. No.
x = 1, y = 2: 3 + 8 = 11. No.
x = 1, y = 3: 3 + 18 = 21. No.
x = 2, y = 1: 12 + 2 = 14. No.
x = 2, y = 2: 12 + 8 = 20. No.
x = 2, y = 3: 12 + 18 = 30. Too large.
Keep going. Try to check whether the claim is actually true or if a solution exists. If 3x² + 2y² = 22 has no solutions, you would need to argue exhaustively (all x where 3x² < 22, meaning x ≤ 2, have been checked, and all feasible y values fail). That exhaustive check above covers all positive integer cases (x can only be 1 or 2 since 3(3²) = 27 > 22), so the statement "no positive integer solutions" stands.
The lesson: for disproof, you exhibit one counterexample. For proving a negative, you either do an exhaustive check (when the search space is finite and small) or use algebraic/modular arguments.
A biconditional "P ↔ Q" requires proving both P → Q and Q → P. The homework proves: "121x + 23 is even if and only if x is odd."
Direction 1 (←): If x is odd, then 121x + 23 is even. (Direct proof)
Assume x is odd. By definition, x = 2k + 1 for some integer k.
Then 121x + 23 = 121(2k + 1) + 23 = 242k + 121 + 23 = 242k + 144 = 2(121k + 72).
Since 121k + 72 is an integer, 121x + 23 is even by definition.
The structure: assume the hypothesis, substitute the definition, do algebra, arrive at the conclusion's definition.
Direction 2 (→): If 121x + 23 is even, then x is odd. (Proof by contrapositive)
The contrapositive is: if x is not odd (i.e., x is even), then 121x + 23 is not even (i.e., odd).
Assume x is even. Then x = 2k for some integer k.
121x + 23 = 121(2k) + 23 = 242k + 23 = 2(121k + 11) + 1.
Since 121k + 11 is an integer, 121x + 23 is odd by definition.
This proves the contrapositive, which is equivalent to the original direction.
The pattern for even/odd proofs: substitute the definition (2k for even, 2k + 1 for odd), simplify, and factor the result into the form 2m (even) or 2m + 1 (odd).
Implication rewrite:
p → q ≡ ¬p ∨ q
Negation of an implication:
¬(p → q) ≡ p ∧ ¬q
Contrapositive equivalence:
p → q ≡ ¬q → ¬p
Biconditional split:
p ↔ q ≡ (p → q) ∧ (q → p)
Even/odd definitions:
n is even: n = 2k for some integer k
n is odd: n = 2k + 1 for some integer k
Proof by contrapositive is how most security arguments work: rather than proving "if the system is configured correctly, it is secure" directly, you show "if the system is insecure, then it was misconfigured." The logic is identical, but the contrapositive direction is often easier to reason about.
Counterexamples are the foundation of software testing. Every failing test case is a counterexample to the claim "this program works correctly on all inputs."
Students confuse the contrapositive (¬q → ¬p, equivalent to the original) with the converse (q → p, not equivalent). If you remember only one thing from this section, remember that the contrapositive flips and negates, while the converse only flips.
Assuming ¬(p → q) means ¬p → ¬q. The negation of an implication is p ∧ ¬q (the hypothesis is true and the conclusion is false), not the inverse.
Treating "if and only if" as one implication. A biconditional requires two separate proofs, one in each direction. Forgetting the second direction is forfeiting half the marks.
In even/odd proofs, writing x = 2k without specifying "for some integer k." The integer k must be introduced; without it, the expression is not grounded.
⚠️ Distinguishing contrapositive from converse is tested directly and is embedded in multi-part proof questions. Be able to identify each instantly.
⚠️ Even/odd direct proofs are a staple of early exams. Memorise the substitution pattern: assume the definition, substitute, simplify, identify the form.
⚠️ Proof by contrapositive is the go-to when a direct proof feels awkward. If you are stuck proving p → q directly, try ¬q → ¬p.
⚠️ Counterexample questions are easy marks if you are systematic. Check small cases methodically rather than guessing.
True or false: The converse of a true conditional is always true. False. The converse is a separate claim.
Fill in the blank: ¬(q → r) is equivalent to ___ ∧ ___. q ∧ ¬r.
True or false: To prove p ↔ q, it suffices to prove p → q alone. False. You must prove both directions.
If x = 2k + 1 and you compute 5x + 3, is the result even or odd? 5(2k + 1) + 3 = 10k + 5 + 3 = 10k + 8 = 2(5k + 4). Even.
Q: Given ¬(p ∧ q) is true and q is true, what can you conclude about p?
A: By De Morgan's, ¬(p ∧ q) ≡ ¬p ∨ ¬q. Since q is true, ¬q is false. For the disjunction ¬p ∨ ¬q to be true, ¬p must be true. Therefore p is false.
Q: State the contrapositive of "If n is prime and n > 2, then n is odd."
A: If n is not odd (i.e., n is even), then n is not prime or n ≤ 2.
Q: Prove directly that if n is an even integer, then n² is even.
A: Assume n is even, so n = 2k for some integer k. Then n² = (2k)² = 4k² = 2(2k²). Since 2k² is an integer, n² is even.
Q: Disprove the statement "For all integers n, if n² is even then n is even" restricted to the domain of positive integers. Can you actually disprove it?
A: You cannot disprove it, because it is true. If n² is even, then n must be even (proof by contrapositive: if n is odd, n = 2k+1, then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd). There is no counterexample.
Q: Prove by contrapositive: if 3n + 7 is even, then n is odd.
A: Contrapositive: if n is even, then 3n + 7 is odd. Assume n = 2k. Then 3(2k) + 7 = 6k + 7 = 6k + 6 + 1 = 2(3k + 3) + 1, which is odd.
Proof techniques here are the same ones used in mathematical induction (the next major topic in most discrete math courses). Induction adds one more layer: proving the base case and proving the implication P(k) → P(k+1), which is just a direct or contrapositive proof of a conditional.
The contrapositive/converse distinction also reappears in probability (Bayes' theorem addresses the "converse probability" problem) and in formal logic courses when studying inference rules like modus tollens.
propositional logic, truth values, compound statements, De Morgan's laws, conditional, implication, contrapositive, converse, inverse, biconditional, if and only if, iff, direct proof, proof by contrapositive, proof by contradiction, counterexample, disproof, even and odd integers, parity proof, integer proof, CS 18200, discrete mathematics, Purdue, logic expressions, proof techniques, modus ponens, modus tollens