Homework 1 Solution

Description

Question 1

1. Determine if the following compound propositions are a tautology, a contradiction or neither one of them. Construct a truth table for each proposition.

(a) ((p ! q) $ (p ^ :r)) ! :(q ^ r)

(b) :((p _ q) ^ (p ! q) _ (q ! :p))

2. Determine if the following predicate logic arguments are valid or invalid. Explain why you think the argument is valid or invalid. You do not need to make a formal proof for these questions. (Hint: Using counterexamples might be bene cial.)

(a) 9xP (x) ^ 9xQ(x) ! 9x(P (x) ^ Q(x))

(b) 8xP (x) ! 9xP (x)

Question 2

Show that (:p _ p) ! ((p ^ :q) ! 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

Let W (x) be \x works in the lab”, Older(x; y) be \x is older than y”, P hd(x) be \x is a Phd. student”, Has CS Degree(x) be “x has a CS degree”, Knows(x; y) be \x knows y”.

Use these predicates to express the following statements using quanti ers 8 and 9.

1. Everybody works in the lab has a CS degree.

2. All Phd. students working in the lab knows each other.

3. Cenk is the oldest person working in the lab.

3. Everyone working in the lab is a Phd. student except for Selen.

3. Not all the people working in the lab knows everyone working in the lab.

3. There are at most two Phd. students.

3. There are at least three people older than Gizem.

3. There is exactly one person who is doing Phd. and working in the lab.

Question 4

Prove the following by using only the natural deduction rules for _; ^; !; and : introduction and elimi-nation.

Any other rules/lemmas used should be proven by natural deduction as well.

(p ! r) _ (q ! r) ‘ (p ^ q) ! r

Question 5

Prove the following by using only the natural deduction rules for _; ^; !; and : introduction and elimi-nation.

Any other rules/lemmas used should be proven by natural deduction as well.

(:p _ :q) ‘ (p ^ q) ! r

Question 6

Prove the following by using only the natural deduction rules for _; ^; !; :; 8; and 9 introduction and elimination. Any other rules/lemmas used should be proven by natural deduction as well.

8x(P (x) ! (Q(x) ! R(x))); 9x(P (x)); 8x(:R(x)) ‘ 9x(:Q(x))

• Regulations

• 1. You have to write your answers to the provided sections of the template answer le given.

• 2. Late Submission: Not allowed!

• 3. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to university regulations.

• 4. Newsgroup: You must follow the newsgroup https://cow.ceng.metu.edu.tr/News/ for discus-sions and possible updates on a daily basis.

• 5. Evaluation: Your latex le will be converted to pdf and evaluated by course assistants. The

.tex le will be checked for plagiarism automatically using “black-box” technique and manually by assistants, so make sure to obey the speci cations.

• Submission

Submission will be done via COW. Download the given template answer le “the1.tex”. When you nish your exam upload the .tex le with the same name to COW.

Note: You cannot submit any other les. Don’t forget to make sure your .tex le is successfully compiled in Inek machines using the command below.

$ pdflatex the1.tex

3