Exercise 1: Suppose \(x \in \mathbb{Z}\). Show that if \(43x + 3\) is even, then \(x\) is odd.
Exercise 2: Let \(x, y \in \mathbb{R}\). If \(y^3 + yx^2 \leq x^3 + xy^2\) then \(y \leq x\).
Exercise 3: Let \(x, y \in \mathbb{R}\). If \(xy\) is irrational, then \(x\) is irrational or \(y\) is irrational.
Exercise 4: Let \(n \in \mathbb{Z}\). If \(3 \nmid n^2\), then \(3 \nmid n\).
Exercise 5: Let \(x \in \mathbb{R}\). If \(x^5 + 7x^3 + 5x \geq x^4 + x^2 + 8\), then \(x \geq 0\).
In the lectures, you saw the first steps to formally define a proof system. A proof system is built on axioms and rules. We need to define what is the form of propositions and what do the symbols mean. For instance, we need to define (i) what must hold for \(p\) and \(q\) in order to be allowed to write \(p \to q\) and (ii) what is entailed if \(p \to q\) holds.
In particular, you learn in the lectures that in order to “prove” (i.e. be able to write in the proof system) \(p \to q\), we must have a block of “valid” statements which start with “Assume \(p\)” and end with “\(q\)” (see the example below for how to make this formal).
OK, so we know how to generate statements of the form \(p\to q\), how can we use these in a proof? Well, if we know that \(p\) holds and \(p \to q\) then we can define that \(q\) holds as well. Note that we choose \(p \to q\) to mean this.
As you may have noticed these axioms and rules seem trivial. This is intended because we want to formally define the rules for logic, which contains basic notions such as “and” and “or”. Can you think of the formal rules for \(\land\), \(\lor\), \(\neg\), bi-implication and contradiction? The following examples may help you.
Example 1: Show that \(((P \to Q) \land \neg Q) \to \neg P\)
Example 2: Show that \((P \land (\neg P \lor Q)) \to Q\)
Using JAPE: (optional) Using JAPE can help you understand proof systems better.
jape and click File > Open.. and select examples > natural deduction > I2L.jt.Exercise 1: Show that \((P \land (\neg P \lor Q)) \to Q\).
Exercise 2: Find counterexamples to the following:
Exercise 3: Show that \((P \to Q) \to \neg (P \land \neg Q)\).
Exercise 4: Determine which of the following pairs of statements are equivalent (and prove equivalence):
Exercise 5: Show that \((P \to (Q \to R)) \to ((P \to Q) \to (P \to R))\).
Exercise 6: Show that \((P \to Q) \to ((P \to \neg Q)\to \neg P)\).
Exercise 7: Show that \(((P \to Q) \land (Q \to R)) \to (P \to R)\).
Exercise 8: Attempt 1996P1Q2.
Exercise 1: You are on an island with only knights and knaves. Knights always tell the truth and knaves always lie. You hear an islander A making a statement about his friend B: “At least one of us is a knave”. What are A and B?
Exercise 2: You are on an island with only knights and knaves. Knights always tell the truth and knaves always lie. You hear an islander A making a statement about his friend B: “I am a knave or B is a knight”. What are A and B?
Exercise 3: You are on an island with only knights and knaves. There are three islanders A, B, and C. A says “B and C are of the same type”. Then, someone asks C: “Are A and B of the same type?”. What does C answer?
Exercise 4: You are on an island with only knights and knaves. There are three islanders A, B, and C. You ask A: “How many knights are among you?”. A answers, but you cannot make out what they said. So, you ask B: “What did A say?”. B replies: “A said that there is one knight among us”. At this point, C says “Don’t believe B; He is lying”. What are B and C?
Exercise 5: You are a prisoner in a prison with two doors, one leads to liberty and the other leads to death. The prison is guarded by two guards, one always tells the truth and the other always lies. You are allowed one question (with a binary answer), to determine the door to liberty. What would you ask?
Exercise 1: You are given \(n+1\) integers. Prove that there are two integers \(a, b\), such that \(n \vert (a - b)\).
Exercise 2: Let \(n\) be an odd integer and let \(f\) be a permutation of \(\lbrace 1, \ldots , n \rbrace\). Show that \(x\) is even, where:
\[x = (1 - f(1))\cdot (2 - f(2)) \cdot \ldots \cdot (n - f(n))\]Exercise 3: Prove that any collection of \(31\) distinct integers between \(1\) and \(60\) has the property that one integer in the collection divides another integer in the collection.
Exercise 4: Prove that if you place \(5\) points inside an equilateral triangle with side length \(2\), then there will be two of them that will have a distance smaller than \(1\).
Exercise 5: You have placed \(25\) rooks on a chessboard (\(8 \times 8\)). Prove that you can choose \(4\) of them, so that if you remove the rest, they will not attack each other.