Description
Question 1 (15 pts)
a) Show that whether the following statement is a tautology or a contradiction by using a truth
table. (5pts)
(p ∧ q) ↔ (¬p ∨ ¬q)
b) Show that p → ((q ∨ ¬q) → (p ∧ q)) and (¬p ∨ q) are logically equivalent. Use tables 6, 7 and 8
given under the section ”Propositional Equivalences” in the course textbook and give the reference to
the table and the law in each step. REMARK: You can use ¬T ≡ F directly. (10 pts)
Question 2 (30 pts)
Assume the following:
W(x, y) : x works on project y.
S(x, y) : x supervises project y.
A(x, y) : x is the advisor of y.
F(x, y) : x funds project y.
Translate the following sentences into predicate logic using ∨, ∧, →, ¬, ∀, ∃. You are not allowed to use
any other predicate symbols. f and g are 5 points, while all others are 4 points each. (Note: You can
use constants to denote individuals or specific projects like Ali or P).
a) Every student works on a project.
b) Not all projects are funded.
c) Instructor Ali is the advisor of all the students that work on project P.
d) B¨u¸sra works on a project that is funded by TUBITAK.
e) Some supervisors supervise more than one project.
f) No two students work on the same project.
g) Exactly two students work on some project.
1
Question 3 (15 pts)
Prove the following claims by natural deduction. Use only the natural deduction rules ∨, ∧, →, ¬,
introduction and elimination. If you attempt to make use of a lemma or equivalence, you need to
prove it by natural deduction too.
p → q,(q ∧ ¬r) → s, ¬s ⊢ p → r
Question 4 (20 pts)
Ekin has four children: Ay¸se, Barı¸s, Can and Duygu. They make the following claims:
Ay¸se: We went to park.
Barı¸s: If we played hide and seek, then we did not eat candy.
Can: If we went to park, then we both ate candy and played games.
Duygu: If we played games, then we played hide and seek.
Ekin knows that three of them are telling truth but Barı¸s is lying. Help her to prove this by using
natural deduction. Use the following clauses;
p: We went to park.
q: We ate candy.
r: We played games.
s: We played hide and seek.
Question 5 (20 pts)
Prove the following claim by natural deduction. Use only the natural deduction rules ∨, ∧, →, ¬, ∀, ∃
introduction and elimination. If you attempt to make use of a lemma or equivalence, you need to
prove it by natural deduction too.
∀x(P(x) → (Q(x) → R(x))), ∃x(P(x)), ∀x(¬R(x)) ⊢ ∃x(¬Q(x))
1 Regulations
1. You have to write your answers to the provided sections of the template answer file given.
Handwritten solutions will not be accepted.
2. Do not write any extra stuff like question definitions to the answer file. Just give your solution
to the question. Otherwise you will get 0 from that question.
3. Late Submission: Not allowed!
4. Cheating: We have zero tolerance policy for cheating. People involved in cheating will
be punished according to the university regulations. .tex file will be checked for plagiarism.
5. Submit a single PDF file named eXXXXXXX.pdf (7-digit student number).
6. You may ask your questions in the course forum or by sending a mail to ”mduymus@ceng.metu.edu.tr”.
2
