Description

CENG223
Discrete Computational Structures
Take Home Exam 1

Question 1
a) Construct a truth table for the following compound proposition.
(q →¬p) ↔ (p ↔¬q)
b) Show that whether the following conditional statement is a tautology by using a truth table.
[(p ∨ q) ∧ (r → p) ∧ (r → q)] → r
Question 2
Show that (p → q) ∧ (p → r) and (¬q ∨¬r) →¬p 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.
Question 3

1) Everybody has a mother.
2) Everybody has a father and a mother.
3) Whoever has a mother has a father.
4) Sam is a grandfather.
5) All fathers are parents.
6) All husbands are spouses.
7) No uncle is an aunt.
8) All brothers are siblings.
9) Nobody’s grandmother is anybody’s father.
10) Alex is Ali’s brother-in-law.
1

11) Alex has at least two children.
Question 4 12) Everybody has at most one mother.
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.
a) p → q,r → s ` (p ∨ r) → (q ∨ s)
b) ` (p → (r →¬q)) → ((p ∧ q) →¬r)
Question 5
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.
a) ∀xP(x) ∨∀xQ(x) `∀x(P(x) ∨ Q(x))
b) ∀xP(x) → S `∃x(P(x) → S)
1 Regulations
1. You have to write your answers to the provided sections of the template answer file given.
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!
2 Submission
Submission will be done via odtuclass. Download the given template answer file ”the1.tex”. When you finish your exam, archive .tex file with any external package file that you use it and upload it to odtuclass as an archive file named eXXXXXXX.tar (7-digit student number). Note: Don’t forget to make sure your .tex file is successfully compiled in Inek machines using the command below. $ pdflatex the1.tex
2