Topic 1: Advanced Inference Rules
Q1
Formal Derivation and Validity
(a)
System Verification: Consider a distributed system with the following specifications:
- If the file system is not locked, then new messages are queued.
- If the file system is not locked, then the system is functioning normally, and conversely, if the system is functioning normally, then the file system is not locked.
- If new messages are queued, then they will be sent to the message buffer.
- If the file system is not locked, then new messages will be sent to the message buffer.
- New messages will not be sent to the message buffer.
(b)
The Resolution Rule: The Resolution rule states that from \( p \lor q \) and \( \neg p \lor r
\), we can infer \( q \lor r \).
Using only the Resolution rule and the fact that \( a \to b \equiv \neg a \lor b \), prove that the following set of clauses is inconsistent (unsatisfiable): \[ S = \{ a \lor b, \neg a \lor c, \neg b \lor d, \neg c \lor \neg d \} \]
Using only the Resolution rule and the fact that \( a \to b \equiv \neg a \lor b \), prove that the following set of clauses is inconsistent (unsatisfiable): \[ S = \{ a \lor b, \neg a \lor c, \neg b \lor d, \neg c \lor \neg d \} \]
(c)
Use Propositional Resolution to show that the clauses {p, q}, {¬p, r}, {¬p, ¬r}, {p, ¬q} are not
simultaneously satisfiable.
Q2
Inference with Quantifiers
(a)
Determine whether the following argument is valid. If valid, provide a formal proof involving Universal
Instantiation/Generalization. If invalid, provide a counter-model.
Premises:
Premises:
- \( \forall x (P(x) \to (Q(x) \land S(x))) \)
- \( \forall x (P(x) \land R(x)) \)
(b)
Prove that \( \exists x (P(x) \to Q(x)) \) is logically equivalent to \( (\forall x P(x)) \to (\exists x Q(x))
\).
Hint: This is often counter-intuitive. Expand the implication as a disjunction.
Hint: This is often counter-intuitive. Expand the implication as a disjunction.
Topic 2: Mathematical Induction
Q3
Induction on Derived Structures
(a)
Let \( H_n \) be the \( n \)-dimensional Hypercube graph. The vertices of \( H_n \) are binary strings of
length \( n \). Two vertices are connected if their strings differ in exactly one bit.
Use mathematical induction to prove that the number of edges \( |E| \) in \( H_n \) is exactly \( n \cdot 2^{n-1} \) for all \( n \ge 1 \).
Use mathematical induction to prove that the number of edges \( |E| \) in \( H_n \) is exactly \( n \cdot 2^{n-1} \) for all \( n \ge 1 \).
(b)
Strong Induction: The Fibonacci sequence is defined as \( f_0 = 0, f_1 = 1 \), and \( f_n =
f_{n-1} + f_{n-2} \) for \( n \ge 2 \).
Let \( \phi = \frac{1 + \sqrt{5}}{2} \) be the Golden Ratio. Prove by strong induction that \( f_n > \phi^{n-2} \) for all \( n \ge 3 \).
Let \( \phi = \frac{1 + \sqrt{5}}{2} \) be the Golden Ratio. Prove by strong induction that \( f_n > \phi^{n-2} \) for all \( n \ge 3 \).
Q4
Structural Induction & Sets
Consider the set \( S \subseteq \mathbb{Z} \times \mathbb{Z} \) defined recursively by:
- Base Case: \( (0,0) \in S \).
- Recursive Step: If \( (a,b) \in S \), then \( (a+2, b+3) \in S \) and \( (a+3, b+2) \in S \).
Topic 3: Predicate Logic & Formalization
Q5
Number Theory Definitions
Express the following statements using only standard arithmetic quantifiers \( (\forall,
\exists) \), logical connectives, variables over \( \mathbb{N} \), equality \( (=) \), addition \( (+) \),
multiplication \( (\cdot) \), and the constant \( 1 \). You may not use exponentiation, subtraction, or
division directly (you must define them if needed).
(a)
Perfect Number: A number \( n \) is a perfect number if it is equal to the sum of its proper
divisors.
(Note: You will need to formally express the concept of a sum of a set defined by a predicate, or express it as "there exists a set of divisors..."). Alternatively, express: " \( n \) is perfect" assuming a summation operator \( \sum \) is available.
(Note: You will need to formally express the concept of a sum of a set defined by a predicate, or express it as "there exists a set of divisors..."). Alternatively, express: " \( n \) is perfect" assuming a summation operator \( \sum \) is available.
(b)
Goldbach's Conjecture: Every even integer greater than 2 is the sum of two prime numbers.
Hint: First define a predicate \( Prime(p) \).
Hint: First define a predicate \( Prime(p) \).
(c)
Twin Primes: There are infinitely many pairs of primes that differ by 2.
Q6
Complex Logical Primitives (Armstrong Numbers)
An Armstrong number (or Narcissistic number) of order \( k \) is a number that is the sum of
its own digits each raised to the power of \( k \).
(a) Define a predicate \( Digit(n, i, d) \) which is true if and only if the \( i \)-th decimal digit of \( n \) is \( d \) (where \( i=0 \) is the ones place). Use only basic arithmetic operators (including exponentiation and modulo).
(a) Define a predicate \( Digit(n, i, d) \) which is true if and only if the \( i \)-th decimal digit of \( n \) is \( d \) (where \( i=0 \) is the ones place). Use only basic arithmetic operators (including exponentiation and modulo).
(b)
Using the predicate from (a), formally state: "There exists a 3-digit number that is equal to the sum of the
cubes of its digits."
Q7
Functional Completeness
(a)
Let the logical operator \( \oplus \) denote XOR (Exclusive OR). Prove that the set of operators \( \{ \oplus,
\neg \} \) is not functionally complete.
Hint: Consider the truth table properties or count the number of true outputs for logical functions generated by these operators.
Hint: Consider the truth table properties or count the number of true outputs for logical functions generated by these operators.
(b)
The implication operator is \( \to \). Prove that the set \( \{ \to, F \} \) (where F is the constant False)
is functionally complete.
Hint: Try to construct \( \neg p \) and \( p \lor q \) using only implication and False.
Hint: Try to construct \( \neg p \) and \( p \lor q \) using only implication and False.
Topic 4: Proof Methods & Counter-Examples
Q8
Proof by Contrapositive
(a)
Mersenne Primes: Let \( n \) be an integer greater than 1. Prove the following statement
using the contrapositive approach:
"If \( 2^n - 1 \) is prime, then \( n \) is prime."
(Hint: You need to show that if \( n \) is composite, then \( 2^n - 1 \) is composite. Recall the factorization \( a^k - 1 = (a-1)(a^{k-1} + \dots + 1) \)).
"If \( 2^n - 1 \) is prime, then \( n \) is prime."
(Hint: You need to show that if \( n \) is composite, then \( 2^n - 1 \) is composite. Recall the factorization \( a^k - 1 = (a-1)(a^{k-1} + \dots + 1) \)).
(b)
Let \( A, B, C \) be sets. Prove that \( (A \setminus B) \cap (A \setminus C) \neq \emptyset \implies A
\nsubseteq (B \cup C) \). Use a proof by contrapositive.
Q9
Counter-Examples and Disproofs
(a)
Disprove the converse of Q8(a): "If \( n \) is prime, then \( 2^n - 1 \) is prime."
Find the smallest counter-example \( n \) (where \( n \) is prime) such that \( 2^n - 1 \) is composite.
Find the smallest counter-example \( n \) (where \( n \) is prime) such that \( 2^n - 1 \) is composite.
(b)
Disprove the following claim about predicate logic quantifiers:
\[ \forall x \exists y P(x, y) \implies \exists y \forall x P(x, y) \]
Provide a concrete domain and a definition for predicate \( P(x, y) \) where the premise is true but the
conclusion is false.
Q10
Formalizing Limit Definitions
The formal definition of a limit \( \lim_{x \to a} f(x) = L \) is:
\[ \forall \epsilon > 0, \exists \delta > 0, \forall x (0 < |x - a| < \delta \to |f(x) - L| < \epsilon) \]
(a)
Formally write the logical negation of this statement. Simplify the negation so that no negation operator
appears to the left of a quantifier.
(b)
This negated statement describes the condition where the limit does not equal \( L \).
Explain in plain English (based on your logical derivation) what a "challenger" must produce to prove the
limit is not \( L \).