Description
Question 1
-
Construct a truth table for the following compound proposition. (q ! :p) $ (p $ q)
-
Show that the following formula is a tautology by using a truth table. ((p _ q) ^ (p ! r) ^ (q ! r)) ! r
Question 2
Show that :p ! (q ! r) and q ! (p _r) are logically equivalent by using logical equivalences. Use tables 6,7 and 8 given under the section ’Propositional Equivalences’ in your textbook and give the reference to the table and the law when you use it. If you attempt to make use of a logical equivalence which is not present in the tables, you need to prove it by logical equivalences listed in tables 6,7 and 8.
Question 3
L(x,y) is de ned by ’x likes y’. Use quanti ers to express the following sentences noting that the domain is all people in the world.
Question 4
Prove the following claim by natural deduction. Use only the natural deduction rules _; ^; !; : intro-duction and elimination. If you attempt to make use of a lemma or equivalence, you need to prove it by natural deduction too.
p; p ! (r ! q); q ! s ‘ :q ! (s _ :r)
Question 5
Prove the following claim by natural deduction. Use only the natural deduction rules _; ^; !; :; 8; 9 introduction and elimination. If you attempt to make use of a lemma or equivalence, you need to prove it by natural deduction too. Note that a is a constant in the formula below.
8x(p(x) ! q(x)); :9zr(z); 9yp(y) _ r(a) ‘ 9zq(z)
-
Regulations
-
-
You have to write your answers to the provided sections of the template answer le given.
-
-
-
Do not write any extra stu like question de nitions to the answer le. Just give your solution to the question. Otherwise you will get 0 from that question.
-
-
-
Late Submission: Not allowed!
-
-
-
Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.
-
-
-
Newsgroup: You must follow the newsgroup (cow.ceng.metu.edu.tr/c/courses-undergrad/ceng223) for discussions and possible updates on a daily basis.
-
-
-
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 odtuclass. Download the given template answer le “the1.tex”. When you nish your exam upload the .tex le with the same name to odtuclass.
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
2