Assignment 1 Solution

Problem 1 (Undertsamding implication) [20 marks] Let p; q be two Boolean variables. By de nition, the implication p! q is true if and only if p is false or q is true. Based on that, we have established the following practical tautologies:




(p! q) () (:q ! : p)



(p $ q) () ((p! q) ^ (q ! p))



Would these two tautologies still be true if we were changing the truth value of the implication p! q to that of




p ^ q?



p _ q?



Justify your answer. Another way of phrasing the question would be the following. Wuld the above tautologies still be tautologies if we were




repacing ! with ^?



repacing ! with _?

















































































































Problem 2 (Proving theorems!) [20 marks] For each of the following


statements, translate it into predicate logic and prove it, if the statement is


true, or disprove it, otherwise: 如果是错的你要反驳他 证明其为虚假的
任意两个偶数 都能找到一个
1.
for any two even integers, there exists a third integer (even or odd)


the double of which is equal to the sum of the rst two integers.
数的double 是他们的sum




2.
for any two odd integers, there exists a third integer (even or odd) the
for any two even int, the double of


triple of which is equal to the sum of the rst two integers.
a third int is equal the sum







Problem 3 (Finding a treasure!) [20 marks] In the back of an old cup-board you discover a note signed by a pirate famous for his bizarre sense of humour and love of logical puzzles. In the note he wrote that he had hid-den treasure somewhere on the property. He listed ve true statements and challenged the reader to use them to gure out the location of the treasure.




If there is an old shipwreck near the beach, then the treasure is buried under a coconut palm tree.



There is a coconut palm tree growing either at the far end of the island or near the cave.



Either there is a shipwreck near the beach, or the treasure is hidden in a cave.



If there is a coconut palm tree at the far end of the island, then there is no shipwreck on the beach



There is no coconut palm tree near the cave.



Problem 4 (Deciding consistency) [20 marks] A set of propositions is consistent if there is an assignment of truth values to each of the propo-sitional variables, that makes all propositions true. Is the following set of propositions consistent?




The system is in multiuser state if and only if it is operating normally.



If the system is operating normally, the kernel is functioning.



The kernel is not functioning or the system is in interrupt mode.



If the system is not in multiuser state, then it is in interrupt mode.



The system is in interrupt mode.



Problem 5 (Deciding satis ability) [20 marks] Let p; q; r be three Boolean variables. For each of the following propositional formulas determine whether it is satis able or not.




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



2. p ^ (q _ :p) ^ (:q _ :p)









2