CMPS 211 Homework Assignment 2, Fall 2014

American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 Please solve the following exercises and submit BEFORE 8:00 am of Tuesday 23 September. Exercise 1 (10 points) Are these system specifications consistent? “If the file system is locked, then new messages will be neither queued nor sent to a buffer. If the file system is not locked, then new messages will be queued. If the file system is locked, then the system is not functioning normally, and conversely. If new messages are not queued, then they will be sent to the message buffer. New messages will not be sent to the message buffer.” Exercise 2 (10 points) In the beginning of the semester, Amy was newly assigned to a room in the university dorms with 3 other girls: Laura, Dianna and Nivine. After spending the first day in the dorm, Amy got her ring stolen, so she called the head of security guards in the university. The guard held the 3 other girls as suspects for robbing Amy. However, each of the 3 denied that they stole the ring. Laura also stated that Amy was a friend of Dianna and that Nivine disliked and envied Amy. Dianna on the other hand stated that she had not met Amy yet and that she was in her hometown the day Amy was robbed. Finally, Nivine said that she saw both Laura and Dianna with Amy the day of the robbing and that either Laura or Dianna must have robbed Amy. Can you determine who the thief was if a) one of the three girls was guilty, the two innocent girls were telling the truth, but the statements of the guilty girl may or may not have been true? b) innocent girls did not lie? Exercise 3 (10 points) Find the output of each of these combinatorial circuits. a) American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 b) Exercise 4 (10 points) Show that each of these conditional statements is a tautology by using truth tables. a) (p→r) → [(p→q)∨ (q→r)] b) (p∧q) → [(p→q)∨¬q] c) [(p∧q)∧(¬r→q)] → p d) [(q→r)∧ (p∧q)∧ (p→r)]→p Exercise 5 (10 points) Show that each conditional statement in Exercise 4 is a tautology without using truth tables. Exercise 6 (10 points) Consider the logical operations NOR. The proposition p NOR q is true when neither p nor q is true; and it is false otherwise. The propositions p NOR q is denoted by p ↓ q. a) Construct a truth table for the logical operator NOR. b) Show that p ↓ q is logically equivalent to ¬(p∨q). Exercise 7 (10 points) Show that if p, q, and r are compound propositions such  that p and q are logically equivalent and q and r are logically equivalent, then p and r are logically equivalent. Exercise 8 (10 points) Show that the negation of an unsatisfiable compound proposition is a tautology and the American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 14/15 negation of a compound proposition that is a tautology is unsatisfiable. Exercise 9 (10 points) Determine whether each of these compound propositions is satisfiable. a) (p∨¬r∨¬s)∧(¬p ∨ ¬q ∨ ¬s)∧(p∨¬q∨¬s)∧ (p ∨ q ∨ ¬s) ∧ (p∨q∨¬r) b) (¬p ∨ ¬r ∨ ¬s)∧(p∨q∨¬s)∧(p∨¬q∨ s)∧(¬p∨¬q∨r)∧(p ∨ ¬r ∨ ¬s)∧( ¬p ∨ q ∨ ¬r) c) (q∨r∨s)∧(p∨¬q∨¬s)∧(p∨q∨¬s)∧(¬p∨r∨s)∧(p∨q∨r)∧( ¬p∨¬q∨¬r)∧(¬p ∨ r ∨ ¬s)∧ (¬p ∨ ¬q ∨ s) Exercise 10 (10 points) a) Show that the biconditionals operation is associative, i.e., (p_1 ↔ p_2) ↔ p_3 is equivalent to p_1 ↔ (p_2 ↔ p_3) (b) What is the meaning of p_1 ↔ p_2 ↔ ... ↔ p_n?