Description

CENG223
Discrete Computational Structures
Homework 1

Question 1
Construct a truth table for the following propositions:
1. (¬q ∧ (p → q)) →¬p
2. ((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r)
Question 2
Show that (p → q) ∨ (p → r) and (¬q ∧¬r) →¬p are logically equivalent. You should use tables 6, 7, and 8 given in pages 27 and 28 of your textbook.
In each step give the reference to the law OR the table.
Question 3
1. Let D(x) be “x is a dog”, C(x) be “x is a cat”, and Friends(x,y) be “x and y are friends”, where x and y represent animals.
Translate the following into English statements.
(a) ∀x(C(x) →∃y(D(y) ∧ Friends(x,y)))
(b) ∃x(C(x) ∧∀y(D(y) → Friends(x,y)))
2. Let Chef(x) be “x is a chef”, Customer(x) be “x is a customer”, Meal(x) be “x is a meal”, Knows(x,y) be ”x knows y”, Cooks(x,y) be “Chef x can cook meal y”, Eats(x,y) be “x can eat meal y”.
Use these predicates to express the following statements using quantifiers ∀ and ∃.
(a) Only customers can eat meals. (b) Not all chefs can cook every meal.
(c) There are some customers who can eat every meal cooked by a certain chef.
(d) Every chef knows a chef who can cook the meals he/she cannot cook.
1
Question 4
Show that

cannot be a deduction rule in a sound deductive system. (Hint: Show a counterexample)
Question 5
Prove the following by using only the natural deduction rules for ∨,∧,→, and ¬ introduction and elimination along with the biconditional-introduction rule,

Any other rules/lemmas used should be proven by natural deduction as well.
p → q,q → r,r → p ` (p ←→ q) ∧ (p ←→ r)
Question 6
Prove the following by using only the natural deduction rules for ∨,∧,→,¬,∀, and ∃ introduction and elimination. Any other rules/lemmas used should be proven by natural deduction as well.
∀x(Q(x) → R(x)),∃x(P(x) → Q(x)),∀xP(x) ` ∃x(P(x) ∧ R(x))
1 Regulations
1. You have to write your answers to the provided sections of the template answer file given.
2. Late Submission: Not allowed.
4. Updates & Announces: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and possible updates.
2 Submission
Submission will be done via COW. Download the given template answer file ”the1.tex”. When you finish your exam upload the .tex file with the same name to COW.
Note: You cannot submit any other files. Don’t forget to make sure your .tex file is successfully compiled in Inek machines using the command below.
$ pdflatex the1.tex
2