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 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.

    a) Everyone likes Burak.

    b) Hazal likes everyone.

    c) Everyone likes someone.

    d) No one likes everyone.

    e) Everyone is liked by someone.

    f) No one likes Burak and Mustafa.

    g) Ceren likes exactly two people.

            h) There is exactly one person whom everyone likes.

            i) No one likes himself or herself.

        j) There is somebody who likes exactly one person besides himself or herself.








1

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

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

        2. 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.

        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.

        5. Newsgroup: You must follow the newsgroup (cow.ceng.metu.edu.tr/c/courses-undergrad/ceng223) for discussions and possible updates on a daily basis.

        6. 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