Proofs

Goal: Formulate the premises in propositional logic and derive a valid conclusion step-by-step using standard rules of inference.

Step-by-Step Derivation:

1. Define Propositional Variables:
   • $C$: "The research will be completed on time."
   • $F$: "The project is funded."
   • $E$: "We will buy new equipment."
   • $R$: "The grant is renewed."
2. Translate Premises:
   • P1: $\lnot C$
   • P2: $F \to E$
   • P3: $E \to C$
   • P4: $\lnot R \lor F$
3. Apply Rules of Inference:

   Step	Expression	Justification
   1	$F \to E$	Premise P2
   2	$E \to C$	Premise P3
   3	$F \to C$	Hypothetical Syllogism (from Steps 1 & 2)
   4	$\lnot C$	Premise P1
   5	$\lnot F$	Modus Tollens (from Steps 3 & 4)
   6	$\lnot R \lor F$	Premise P4
   7	$\lnot R$	Disjunctive Syllogism (from Steps 5 & 6)

Conclusion: The grant was not renewed ($\lnot R$). ∎

Goal: Formulate the argument using propositional logic and evaluate its validity and soundness.

Step-by-Step Analysis:

1. Define Variables: Let $p$ be the proposition "$1+1=11$" and $q$ be the proposition "7 is odd."
2. Translate the Argument:
   • Premise 1: $p \to q$
   • Premise 2: $\lnot q$ (since "7 is even" is equivalent to "7 is not odd")
   • Conclusion: $\lnot p$ (since "$1+1 \neq 11$")
3. Evaluate Validity (Form): By the rule of Modus Tollens, from $p \to q$ and $\lnot q$, we can validly deduce $\lnot p$. Thus, the argument is logically valid.
4. Evaluate Soundness (Truth of Premises):
   • $p$ is false, so the conditional $p \to q$ is vacuously true.
   • $q$ is false, so the premise $\lnot q$ is true.
   • Since all premises are true in reality, the argument is also sound, and the conclusion ($\lnot p$) must be true (which it is, since $1+1 \neq 11$). ∎

Goal: For each statement, formulate the premise-conclusion structure and identify the rule of inference used.

Step-by-Step Analysis:

• (a) The university is not closed today. If it snows, the university will close. Therefore, it did not snow today.
  • Let $C$ = "university is closed", $S$ = "it snows".
  • Premises: $\lnot C$, $S \to C$. Conclusion: $\lnot S$.
  • Structure: $\lnot C, S \to C \therefore \lnot S$.
  • Rule of Inference: Modus Tollens (MT).
• (b) If I stay in the sun too long, I sunburn. If I go swimming, I stay too long. Therefore, if I swim, I sunburn.
  • Let $W$ = "swim", $S$ = "stay in sun too long", $B$ = "sunburn".
  • Premises: $S \to B$, $W \to S$. Conclusion: $W \to B$.
  • Structure: $W \to S, S \to B \therefore W \to B$.
  • Rule of Inference: Hypothetical Syllogism (HS). ∎

Goal: Translate the English statements into propositional logic and deduce a valid conclusion.

Step-by-Step Derivation:

1. Define Variables: Let $H$ = "I play hockey", $S$ = "I am sore", and $W$ = "I use the whirlpool".
2. Formulate Premises:
   • P1: $H \to S$
   • P2: $S \to W$
   • P3: $\lnot W$
3. Apply Rules of Inference:
   • From P1 ($H \to S$) and P2 ($S \to W$), by Hypothetical Syllogism, we derive $H \to W$.
   • From $H \to W$ and P3 ($\lnot W$), by Modus Tollens, we derive $\lnot H$.

Conclusion: I did not play hockey ($\lnot H$). ∎

Goal: Formulate the statements and apply inference rules to obtain the final conclusion.

Step-by-Step Derivation:

1. Define Variables: Let $W$ = "I win the lottery", $C$ = "I am clever", and $L$ = "I am lucky".
2. Formulate Premises:
   • P1: $\lnot W$
   • P2: $C \lor L$
   • P3: $L \to W$
3. Apply Rules of Inference:
   • From P3 ($L \to W$) and P1 ($\lnot W$), by Modus Tollens, we derive $\lnot L$.
   • From P2 ($C \lor L$) and $\lnot L$, by Disjunctive Syllogism, we derive $C$.

Conclusion: I am clever ($C$). ∎

Goal: Formulate the arguments and apply rules of inference step-by-step to find the conclusion.

Step-by-Step Derivation:

1. Define Variables: Let $T$ = "Tony trains", $G$ = "Tony uses a gadget", $S$ = "Tony is stronger", and $D$ = "Tony defeats villains".
2. Formulate Premises:
   • P1: $T \lor G$
   • P2: $T \to S$
   • P3: $\lnot D$
   • P4: $S \to D$
3. Apply Rules of Inference:
   • From P4 ($S \to D$) and P3 ($\lnot D$), by Modus Tollens, we derive $\lnot S$.
   • From P2 ($T \to S$) and $\lnot S$, by Modus Tollens, we derive $\lnot T$.
   • From P1 ($T \lor G$) and $\lnot T$, by Disjunctive Syllogism, we derive $G$.

Conclusion: Tony used a gadget ($G$). ∎

Goal: Analyze each argument structure and determine whether it represents a valid rule of inference or a logical fallacy.

Analysis:

• (a) If $n > 1$ then $n^2 > 1$. Suppose $n^2 > 1$. Then $n > 1$.
  • Let $p$ = "$n > 1$" and $q$ = "$n^2 > 1$".
  • Structure: $p \to q$, $q \therefore p$.
  • This is the fallacy of affirming the consequent.
  • Counterexample: Set $n = -2$. The premise $p \to q$ is true, and the assumption $q$ ($(-2)^2 = 4 > 1$) is true, but the conclusion $p$ ($-2 > 1$) is false. Hence, the argument is invalid.
• (b) If $n > 3$ then $n^2 > 9$. Suppose $n^2 \leq 9$. Then $n \leq 3$.
  • Let $p$ = "$n > 3$" and $q$ = "$n^2 > 9$". Note that $\lnot q$ is "$n^2 \leq 9$" and $\lnot p$ is "$n \leq 3$".
  • Structure: $p \to q$, $\lnot q \therefore \lnot p$.
  • This follows the rule of Modus Tollens. Hence, the argument is valid. ∎

Goal: Formulate the categorical syllogism and evaluate its logical validity.

Step-by-Step Analysis:

1. Define Predicates: Let $G(x)$ be "$x$ has garbage collection" and $S(x)$ be "$x$ is slow." Let the constant $\text{C}$ represent the programming language C.
2. Translate Premises and Conclusion:
   • Premise 1: $\forall x \, (G(x) \to S(x))$
   • Premise 2: $\lnot G(\text{C})$
   • Conclusion: $S(\text{C})$
3. Evaluate the Argument Form:
   • Instantiating Premise 1 for C yields $G(\text{C}) \to S(\text{C})$.
   • Combined with Premise 2 ($\lnot G(\text{C})$), the argument structure is: $$G(\text{C}) \to S(\text{C}), \quad \lnot G(\text{C}) \quad \therefore S(\text{C})$$
   • This is the fallacy of denying the antecedent. The fact that C does not use garbage collection does not imply it cannot be slow for other reasons.

Conclusion: The argument is invalid (a logical fallacy). ∎

Goal: Formulate the compound argument in propositional logic and check its validity using rules of inference.

Step-by-Step Derivation:

1. Define Variables: Let $H$ = "hacked", $U$ = "user error", and $D$ = "design flaw".
2. Translate Premises:
   • P1: $H \to (U \lor D)$
   • P2: $H$
   • P3: $\lnot D$
3. Apply Rules of Inference:

   Step	Expression	Justification
   1	$H \to (U \lor D)$	Premise P1
   2	$H$	Premise P2
   3	$U \lor D$	Modus Ponens (from Steps 1 & 2)
   4	$\lnot D$	Premise P3
   5	$U$	Disjunctive Syllogism (from Steps 3 & 4)

Conclusion: The argument is valid. ∎

Goal: Construct a formal derivation for the quantified conclusion $\forall x\, (R(x) \land S(x))$ from the given premises.

Formal Proof:

1. Let $c$ be an arbitrary element in the domain of discourse.

2. Step	Expression	Justification
   1	$\forall x\, (P(x) \land R(x))$	Premise 2
   2	$P(c) \land R(c)$	Universal Instantiation from Step 1
   3	$P(c)$	Simplification from Step 2
   4	$R(c)$	Simplification from Step 2
   5	$\forall x\, (P(x) \to (Q(x) \land S(x)))$	Premise 1
   6	$P(c) \to (Q(c) \land S(c))$	Universal Instantiation from Step 5
   7	$Q(c) \land S(c)$	Modus Ponens from Steps 3 & 6
   8	$S(c)$	Simplification from Step 7
   9	$R(c) \land S(c)$	Conjunction from Steps 4 & 8
   10	$\forall x\, (R(x) \land S(x))$	Universal Generalization from Step 9 (since $c$ was arbitrary)

Hence, the claim is proved. ∎

Goal: Prove directly that $m+p$ is even given that $m+n$ and $n+p$ are even integers.

Proof (Direct):

1. Use definition of even integers: Since $m+n$ and $n+p$ are even, there exist integers $a$ and $b$ such that: $$m + n = 2a$$ $$n + p = 2b$$
2. Express $m+p$ algebraically: Add the two equations together: $$(m+n) + (n+p) = 2a + 2b$$ $$m + p + 2n = 2(a+b)$$ Isolate $m+p$ by subtracting $2n$ from both sides: $$m + p = 2a + 2b - 2n$$ $$m + p = 2(a + b - n)$$
3. Show $m+p$ is even: Since $a, b,$ and $n$ are integers, their algebraic combination $k = a+b-n$ is also an integer. Thus, we can write $m+p = 2k$ for some integer $k$. By definition of even numbers, $m+p$ is even. ∎

Goal: Evaluate the truth of the universal statement and write a formal proof or disproof.

Disproof (by Counterexample):

1. To disprove the universal statement "for all irrational $a, b$, the product $ab$ is irrational," it suffices to show a single pair of irrational numbers whose product is rational.
2. Let $a = \sqrt{2}$ and $b = \sqrt{2}$.
3. We know that $\sqrt{2}$ is irrational (by classic contradiction proof).
4. Compute their product: $$ab = \sqrt{2} \cdot \sqrt{2} = (\sqrt{2})^2 = 2$$
5. The number 2 is a rational number since it can be expressed as $2/1$, where $2, 1 \in \mathbb{Z}$.

Since we found a counterexample, the statement is false. ∎

Goal: Prove that if the product of two integers $mn$ is even, then at least one of the integers must be even.

Proof (by Contraposition):

1. State the Contrapositive: The contrapositive of $P \to (Q \lor R)$ is $\lnot(Q \lor R) \to \lnot P$, which by De Morgan's Law is: $$\lnot Q \land \lnot R \to \lnot P$$ "If $m$ is odd and $n$ is odd, then the product $mn$ is odd."
2. Assume the antecedent of the contrapositive: Assume $m$ and $n$ are both odd integers. By definition, there exist integers $a$ and $b$ such that: $$m = 2a + 1$$ $$n = 2b + 1$$
3. Compute the product $mn$: $$mn = (2a+1)(2b+1) = 4ab + 2a + 2b + 1$$ Factor out a 2 from the first three terms: $$mn = 2(2ab + a + b) + 1$$
4. Conclude: Since $a, b$ are integers, $k = 2ab + a + b$ is an integer. Thus, $mn = 2k + 1$, which is the definition of an odd number. Since the contrapositive statement is true, the original statement holds. ∎

Goal: Prove that picking any 3 socks from a drawer containing only blue and black socks guarantees a matching pair of the same color.

Proof (by Pigeonhole Principle):

1. Identify Pigeons and Pigeonholes:
   • Let the "pigeons" ($N$) be the pulled socks: $N = 3$.
   • Let the "pigeonholes" ($k$) be the colors of the socks (blue and black): $k = 2$.
2. Apply the Principle: Since $N = 3 > 2 = k$, the Pigeonhole Principle states that at least one pigeonhole must contain at least: $$\lceil N/k \rceil = \lceil 3/2 \rceil = 2 \text{ pigeons.}$$
3. Conclude: This means at least 2 of the pulled socks must share the same color. Therefore, a matching pair is guaranteed. ∎

Goal: Prove that in any selection of 25 days, at least 3 days must belong to the same month.

Proof (by Pigeonhole Principle):

1. Identify Pigeons and Pigeonholes:
   • Let the "pigeons" ($N$) be the days: $N = 25$.
   • Let the "pigeonholes" ($k$) be the months of the year: $k = 12$.
2. Apply the Generalized Pigeonhole Principle: The principle states that if $N$ items are distributed into $k$ bins, then at least one bin must contain at least: $$\lceil N/k \rceil \text{ items.}$$ Calculate: $$\lceil 25/12 \rceil = \lceil 2.0833 \rceil = 3 \text{ items.}$$
3. Conclude: At least 3 days must fall in the same month. ∎

Goal: Show that statements (i), (ii), and (iii) are logically equivalent by proving the cycle of implications: (i) $\implies$ (ii) $\implies$ (iii) $\implies$ (i).

Proof:

• Part 1: Prove (i) $\implies$ (ii).
  • Assume $a < b$. Add $a$ to both sides of the inequality: $$a + a < a + b \implies 2a < a + b$$
  • Divide by 2: $$a < \frac{a+b}{2} \quad \text{which is equivalent to} \quad \frac{a+b}{2} > a.$$
• Part 2: Prove (ii) $\implies$ (iii).
  • Assume $\frac{a+b}{2} > a$. Multiply by 2: $$a + b > 2a \implies b > a \quad \text{(or } a < b).$$
  • Now, we show $\frac{a+b}{2} < b$. Start from $a < b$ and add $b$ to both sides: $$a + b < b + b \implies a + b < 2b$$
  • Divide by 2: $$\frac{a+b}{2} < b.$$
• Part 3: Prove (iii) $\implies$ (i).
  • Assume $\frac{a+b}{2} < b$. Multiply by 2: $$a + b < 2b$$
  • Subtract $b$ from both sides: $$a < b.$$

Since the cycle of implications is complete, the three statements are equivalent. ∎

Goal: Define the methodology of proof by contraposition, and apply it to prove the given statement.

Solution:

1. (a) Explanation: To prove an implication $P \to Q$ by contraposition, we instead prove the logically equivalent statement $\lnot Q \to \lnot P$. We assume the negation of the conclusion ($\lnot Q$) and show that the negation of the hypothesis ($\lnot P$) must follow.
2. (b) Proof:
   • State the Contrapositive: "If $n$ is even (not odd), then $n^2 - 6n + 5$ is odd (not even)."
   • Assume the antecedent of the contrapositive: Let $n$ be an even integer. Therefore, $n = 2k$ for some integer $k$.
   • Evaluate the expression $n^2 - 6n + 5$: Substitute $n = 2k$ into the expression: $$n^2 - 6n + 5 = (2k)^2 - 6(2k) + 5 = 4k^2 - 12k + 5$$ Separate the constant 5 as $4 + 1$: $$= 4k^2 - 12k + 4 + 1 = 2(2k^2 - 6k + 2) + 1$$
   • Conclude: Since $2k^2 - 6k + 2$ is an integer, $n^2 - 6n + 5$ is of the form $2m+1$ for some integer $m$. By definition, the expression is odd. By the principle of contraposition, the original statement is proven. ∎

Goal: Prove the closed-form summation formula using mathematical induction for all $n \geq 1$.

Proof (by Induction):

1. Define the Proposition: Let $P(n)$ be the statement: $$1^3 + 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$
2. Base Case ($n=1$):
   • LHS $= 1^3 = 1$.
   • RHS $= \left(\frac{1(1+1)}{2}\right)^2 = (1)^2 = 1$.
   • Since LHS $=$ RHS, $P(1)$ is true.
3. Inductive Hypothesis (IH): Assume that $P(k)$ is true for some arbitrary integer $k \geq 1$: $$1^3 + 2^3 + \cdots + k^3 = \left(\frac{k(k+1)}{2}\right)^2$$
4. Inductive Step: We must show that $P(k+1)$ is true, i.e.: $$\sum_{i=1}^{k+1} i^3 = \left(\frac{(k+1)(k+2)}{2}\right)^2$$ Expand the summation for $k+1$: $$\sum_{i=1}^{k+1} i^3 = \left( \sum_{i=1}^{k} i^3 \right) + (k+1)^3$$ Substitute the inductive hypothesis (IH) into the sum: $$= \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 = \frac{k^2(k+1)^2}{4} + (k+1)^3$$ Factor out the common term $(k+1)^2$: $$= (k+1)^2 \left[ \frac{k^2}{4} + (k+1) \right] = (k+1)^2 \left[ \frac{k^2 + 4k + 4}{4} \right]$$ Recognize the numerator as a perfect square: $k^2 + 4k + 4 = (k+2)^2$: $$= (k+1)^2 \frac{(k+2)^2}{4} = \left(\frac{(k+1)(k+2)}{2}\right)^2$$ This matches the expression for $P(k+1)$.
5. Conclusion: Since both the base case and the inductive step hold, by the Principle of Mathematical Induction, $P(n)$ is true for all $n \geq 1$. ∎

Goal: Prove the inequality $2^n > n^2$ for all integers $n \geq 5$ using mathematical induction.

Proof (by Induction):

1. Base Case ($n=5$):
   • LHS $= 2^5 = 32$.
   • RHS $= 5^2 = 25$.
   • Since $32 > 25$, the base case holds.
2. Inductive Hypothesis (IH): Assume that $2^k > k^2$ holds for some arbitrary integer $k \geq 5$.
3. Inductive Step: We must show that $2^{k+1} > (k+1)^2$. LHS of the statement at $k+1$: $$2^{k+1} = 2 \cdot 2^k$$ Substitute the inductive hypothesis ($2^k > k^2$): $$2^{k+1} > 2k^2$$ We now need to show that $2k^2 \geq (k+1)^2$ for $k \geq 5$: $$2k^2 \geq k^2 + 2k + 1 \iff k^2 - 2k - 1 \geq 0$$ Rewrite as: $$(k-1)^2 - 2 \geq 0$$ Since $k \geq 5$, the minimum value of $(k-1)^2 - 2$ is $(4)^2 - 2 = 14 > 0$. Therefore, $2k^2 \geq (k+1)^2$ is always true for $k \geq 5$. Thus: $$2^{k+1} > 2k^2 \geq (k+1)^2 \implies 2^{k+1} > (k+1)^2$$
4. Conclusion: By the Principle of Mathematical Induction, the inequality holds for all $n \geq 5$. ∎

Goal: Formally prove program correctness using loop invariants.

Proof:

1. Define the Loop Invariant: Let the invariant $I$ be: $$s = \sum_{j=1}^{i-1} j = \frac{(i-1)i}{2} \quad \text{and} \quad 1 \leq i \leq n+1$$
2. Verify Initialization (Base Case): Before the loop starts, $i=1$ and $s=0$. Substitute $i=1$ into the invariant formula: $$s = \frac{(1-1)\cdot 1}{2} = 0$$ The invariant holds.
3. Verify Maintenance (Inductive Step): Assume $I$ is true before an iteration of the loop, and the loop guard $i \leq n$ holds. Let the state values at the start of the iteration be $s$ and $i$. The loop body performs the updates: $$s' = s + i$$ $$i' = i + 1$$ We must show the new state satisfies the invariant $s' = \frac{(i'-1)i'}{2}$. $$s' = s + i = \frac{(i-1)i}{2} + i \quad \text{[by inductive assumption]}$$ $$= \frac{i^2 - i + 2i}{2} = \frac{i^2 + i}{2} = \frac{i(i+1)}{2}$$ Since $i' = i + 1$, we have $i = i' - 1$. Substituting this in: $$s' = \frac{(i'-1)i'}{2}$$ Also, since $1 \leq i \leq n$, we have $2 \leq i' \leq n+1$. Thus, the loop invariant is maintained.
4. Verify Termination: The loop terminates when the guard $i \leq n$ becomes false. Since $i$ starts at 1 and increases by 1 each step, the loop must terminate exactly when $i = n+1$. Substituting $i = n+1$ into the loop invariant: $$s = \frac{(n+1-1)(n+1)}{2} = \frac{n(n+1)}{2} = 1 + 2 + \cdots + n$$ Thus, when the program terminates, it returns the correct sum. ∎