3.1 Propositions

Basic Skills

1. Identify whether the following statement is a proposition: “Please restart the server.”
2. Let [latex]p[/latex]: “The system is online” and [latex]q[/latex]: “The database is accessible.” Write the compound proposition [latex]p \land q[/latex] in words.
3. A smart home system activates a security alert if the front door is open or the alarm is armed. Let [latex]p[/latex]: “The front door is open” and [latex]q[/latex]: “The alarm is armed”. Construct a truth table for the expression [latex]p \lor q[/latex], and explain what the system does in each case.
4. Determine the truth value of the proposition: “[latex]2 + 2 = 4[/latex] and [latex]5 > 10[/latex].”
5. Translate the following into symbolic logic: “The server is not online, or the database is accessible.”

Applications

6. A login system grants access if the user is authenticated and has admin rights. Let [latex]p[/latex]: “User is authenticated” and [latex]q[/latex]: “User has admin rights.” Write the logic expression and explain when access is granted.
7. In a monitoring system, an alert is triggered if the CPU usage is high or the memory is full. Let [latex]p[/latex]: “CPU usage is high” and [latex]q[/latex]: “Memory is full.” Write the logical expression and describe the alert condition.
8. A smart thermostat turns on the heater if the temperature is below [latex]18^{\circ} C[/latex] and the user is home. Let [latex]p[/latex]: “Temperature [latex]< 18^{\circ} C[/latex]” and [latex]q[/latex]: “User is home.” Write the condition for the heater to turn on.
9. A discount is applied if a customer is a member or has a coupon. Let [latex]p[/latex]: “Customer is a member” and [latex]q[/latex]: “Customer has a coupon.” Write the logic expression and explain when the discount applies.
10. A system logs an error if the network is down and the backup fails. Let [latex]p[/latex]: “Network is down” and [latex]q[/latex]: “Backup fails.” Write the compound proposition and explain its meaning.

Challenge Problems

11. A data center cooling system activates if the temperature is high and the humidity is low. Let [latex]p[/latex]: “Temperature is high” and [latex]q[/latex]: “Humidity is low.” Construct a truth table for the expression [latex]p \land q[/latex], and explain when the cooling system activates.
12. A tautology in logic is a compound statement that is always true, no matter what the truth values of its individual components are. Determine whether the following is a tautology: [latex](p \lor \neg p) \land (q \lor \neg q)[/latex].
13. Given [latex]p[/latex]: “The file is encrypted” and [latex]q[/latex]: “The file is secure,” analyze the truth of the statement: “If the file is encrypted, then it is secure,” when the file is not encrypted but is secure.
14. Construct a real-world scenario where [latex]p \lor q[/latex] is true, but both [latex]p[/latex] and [latex]q[/latex] are false individually. Is this possible? Why or why not?
15. Write pseudocode that evaluates the truth value of [latex]p \land \neg q[/latex] given user input for [latex]p[/latex] and [latex]q[/latex], and explain how it models a real-world decision.

3.2 Conditional Propositions and Logical Equivalence

Basic Skills

16. A smart contract executes a payment only if both the buyer confirms delivery and the seller provides a valid invoice. Let [latex]p[/latex]: “Buyer confirms delivery,” [latex]q[/latex]: “Seller provides a valid invoice,” and [latex]r[/latex]: “Payment is executed.” Construct a truth table for the expression [latex](p \land q) \rightarrow r[/latex] and explain under what conditions the payment is not executed.
17. A system rule states: “If a user logs in, then their session is recorded.” Suppose a user does not log in, but the system still records a session. Is the rule violated? Justify your answer using the truth value of the conditional.
18. Express the contrapositive of the statement: “If the server is online, then the database is accessible.”
19. Without using truth tables, explain why the statement “If the system is secure, then it has a firewall” is logically equivalent to “Either the system is not secure, or it has a firewall.” Use reasoning based on possible real-world scenarios.
20. Write the biconditional form of: “A user is authenticated if and only if they provide valid credentials.”

Applications

21. A company policy states: “If an employee is late, they must notify their manager.” Represent this as a conditional and explain its truth conditions.
22. In a software system, a feature is enabled only if the user has premium access. Write the conditional and its contrapositive.
23. A rule says: “If a customer spends over $100, they get free shipping.” Analyze the logical structure and determine when the rule is violated.
24. Explain why the statement “If 2 is odd, then 5 is prime” is considered true.
25. A student claims: “If I study, I will pass.” What does it mean if they pass without studying?

Challenge Problems

26. A company policy states: “If an employee completes training, then they are granted system access.” Let [latex]p[/latex]: “Employee completes training” and [latex]q[/latex]: “Employee is granted system access”. Construct a truth table for the expression [latex]p \land \neg q[/latex] and explain what this expression represents in terms of policy violation.
27. Determine whether [latex](p \rightarrow q) \land (q \rightarrow r) \rightarrow (p \rightarrow r)[/latex] is a tautology.
28. Construct a real-world example where a conditional is vacuously true.
29. A data policy states: “If a file is confidential, then it must be encrypted.” Let [latex]p[/latex]: “File is confidential” and [latex]q[/latex]: “File is encrypted.” Write the contrapositive of this statement and explain, using a real-world example, why it must be logically equivalent to the original.
30. Write pseudocode that evaluates a conditional and its contrapositive for given truth values.

3.3 Arguments and Rules of Inference

Basic Skills

31. Identify the conclusion in the argument: “If it rains, the ground gets wet. It is raining. Therefore, the ground is wet.”
32. Given the following premises, [latex]p \rightarrow q, r \rightarrow \neg q, r[/latex], determine whether the conclusion [latex]\neg p[/latex] logically follows. Justify your answer using formal rules of inference.
33. Consider the following argument: [latex](p \rightarrow q) \land (r \rightarrow s), \neg q \lor \neg s[/latex]. Can we validly conclude [latex]\neg q \lor \neg r[/latex]? Justify your answer using formal rules of inference and logical equivalences.
34. Write the symbolic form of: “If the user is logged in or is an admin, then access is granted.”
35. Identify the fallacy in: “If I am a teacher, then I work at a school. I work at a school. Therefore, I am a teacher.”

Applications

36. A firewall rule states: “If a device is not trusted, block its traffic.” Use Modus Tollens to reason about a trusted device.
37. In a business rule engine, explain how Modus Ponens is used to trigger actions.
38. A system logs: “If the server is down, then send an alert.” The alert was not sent. What can be inferred?
39. Use Hypothetical Syllogism to combine: “If a user is verified, they can log in. If they can log in, they can access data.”
40. Explain how Disjunctive Syllogism applies to a system that chooses between two backup servers.

Challenge Problems

41. Construct a valid argument using three premises and identify the rule used at each step.
42. Determine if the argument is valid: [latex]p \lor q, \neg p, \neg q \rightarrow r[/latex].
43. Write pseudocode that evaluates the validity of an argument using truth values.
44. Create a real-world scenario that demonstrates the fallacy of affirming the consequent.
45. Prove that [latex](p \rightarrow q) \land (q \rightarrow r) \rightarrow (p \rightarrow r)[/latex] using rules of inference.

3.4 Quantifiers

Basic Skills

46. Translate “All users have passwords” into symbolic logic using quantifiers.
47. Translate “There exists a user who is an admin” into symbolic logic.
48. Identify the domain and predicate in: [latex]\forall x (x > 0 \rightarrow x^2 > 0)[/latex].
49. Let the domain be [latex]\{ 1, 2 \}[/latex] and define the predicate [latex]P(x)[/latex] as [latex]P(1)[/latex] = True, [latex]P(2)[/latex] = False. Construct the truth values of the following statements and determine if they are logically equivalent: [latex]\neg \forall x P(x), \exists x \neg P(x)[/latex]
50. Differentiate between a free and a bound variable in [latex]\forall x (P(x) \lor Q(y))[/latex].

Applications

51. A database query returns true if all records meet a condition. Represent this using a universal quantifier.
52. In a login system, express the condition: “At least one user has not accepted the terms.”
53. Explain how nested quantifiers apply to the statement: “Every user can message at least one other user.”
54. Use quantifiers to describe a system where “There is a super-admin who can access all accounts.”
55. Represent the business rule: “Every customer who places an order receives a confirmation.”

Challenge Problems

56. Prove or disprove the following statement using logical reasoning: [latex]\forall x (P(x) \rightarrow Q(x)) \equiv \forall x (\neg Q(x) \rightarrow \neg P(x))[/latex]. Is this equivalence always true? Justify your answer with a formal argument or counterexample.
57. Construct a truth scenario for [latex]\forall x \exists y P(x, y)[/latex] and explain its meaning.
58. A university claims, “For every student, there exists a course that they enjoy.”
    Another claim is “There exists a course that every student enjoys.” Represent each claim symbolically. Which claim is stronger? Provide a real-world example to show that one does not imply the other.
59. Write pseudocode that checks if all elements in a list satisfy a predicate.
60. Create a real-world example involving nested quantifiers and explain its logic.

3.5 Proofs

Basic Skills

61. Provide one example of each of the terms theorem, lemma, corollary, and axiom from elementary arithmetic.
62. Write a direct proof that the sum of two odd integers is even plus one.
63. Disprove the statement: “For all integers [latex]n[/latex], if [latex]n[/latex] is divisible by [latex]4[/latex], then [latex]n[/latex] is even and odd.”
64. Provide a counterexample to disprove: “All prime numbers are odd.”
65. Write a proof by contradiction to show that there is no smallest positive rational number.

Applications

66. Prove that the product of an even integer and any integer is even.
67. Use proof by cases to show that for any integer [latex]n[/latex], the square of [latex]n[/latex] leaves a remainder of either [latex]0[/latex] or [latex]1[/latex] when divided by [latex]4[/latex].
68. Prove that if [latex]n[/latex] is an integer and [latex]n^{2}[/latex] is divisible by [latex]3[/latex], then [latex]n[/latex] is divisible by [latex]3[/latex].
69. Prove that the sum of any three consecutive integers is divisible by [latex]3[/latex].
70. Use a proof of equivalence to show that an integer [latex]n[/latex] is divisible by [latex]6[/latex] if and only if it is divisible by both [latex]2[/latex] and [latex]3[/latex].

Challenge Problems

71. Prove that if [latex]a[/latex] and [latex]b[/latex] are integers such that [latex]a^{2} + b^{2}[/latex] is even, then both [latex]a[/latex] and [latex]b[/latex] are even or both are odd.
72. Use proof by contradiction to show that there are infinitely many prime numbers.
73. Prove that for any integer [latex]n[/latex], [latex]n^{3} - n[/latex] is divisible by [latex]6[/latex].
74. Construct a proof by cases to show that the absolute value function satisfies [latex]|x| \geq 0[/latex] for all real numbers [latex]x[/latex].
75. Prove that if [latex]n[/latex] is an odd integer, then the remainder when [latex]n^{2}[/latex] is divided by [latex]8[/latex] is [latex]1[/latex].

3.6 Mathematical induction

Basic Skills

76. Explain the difference between weak induction and strong induction. Then, provide an example of a statement that can be proven using strong induction but not easily with weak induction, and outline how the strong induction proof would proceed.
77. Prove by mathematical induction that for all integers [latex]n \geq 1, 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3}[/latex].
78. Prove by mathematical induction that for all integers [latex]n \geq 5, 3^{n} > n^{2}[/latex].
79. Prove by mathematical induction that [latex]1^{2} + 2^{2} + \cdots + n^{2} = \frac{n(n + 1)(2n + 1)}{6}[/latex].
80. Prove by mathematical induction that for all integers [latex]n \geq 1, 5^{n} - 1[/latex] is divisible by 4.

Applications

81. This problem demonstrates how mathematical induction can be used to prove predictable patterns in exponential expressions, which is essential in fields like cryptography, hashing, and algorithm design. Prove by mathematical induction that for all integers [latex]n \geq 1[/latex], the expression [latex]11^{n} - 4^{n}[/latex] is divisible by [latex]7[/latex].
82. Prove using strong induction that every amount of postage of 18 cents or more can be formed using only 7-cent and 11-cent stamps.
83. The application of the following proof is to demonstrate how factorial growth outpaces exponential growth, which is crucial in algorithm analysis and computational complexity when comparing the efficiency and scalability of algorithms. Prove by mathematical induction that for all integers [latex]n \geq 4, n! > 2^{n}[/latex].
84. The application of proving the following is fundamental in computing all possible configurations in areas like binary decision-making, feature selection in machine learning, and generating all possible user permission settings or menu options in software systems. Prove by mathematical induction that the total number of different combinations you can make by choosing any number of items from a group of [latex]n[/latex] distinct items is [latex]2^n[/latex].
85. The application of proving the following is to show how simple arithmetic patterns can model predictable growth, which is useful in computer graphics, memory allocation, and understanding loop behaviour in programming, where square patterns or grid structures are involved. Prove that the sum of the first [latex]n[/latex] odd numbers is [latex]n^{2}[/latex].

Challenge Problems

86. Prove by mathematical induction that [latex]\sum_{k=1}^{n} \frac{1}{k(k + 1)} = \frac{n}{n+1}[/latex].
87. Prove by mathematical induction that for all integers [latex]n \geq 1, 5^{2n} - 1[/latex] is divisible by [latex]24[/latex].
88. Use strong induction to prove that every integer greater than [latex]2[/latex] is either prime or a product of primes.
89. Prove by mathematical induction that for all integers [latex]n \geq 1, \left\lfloor \frac{n+1}{2} \right\rfloor + \left\lfloor \frac{n}{2} \right\rfloor = n[/latex].
90. Prove by mathematical induction that the number of diagonals in an [latex]n[/latex]-gon is [latex]\frac{n(n - 3)}{2}[/latex].