Page 1 of 5!CSE 2321 – Foundations I –Prof. Supowit Homework 1 – SOLUTIONS to problems 2 through 4 Note: There are many correct solutions to each question; just one of them is provided here. 1. For each of the following propositions (also known as “Boolean expressions”), prove, by means of a truth table, whether it is a tautology (i.e., it’s always true), a contradiction (it’s never true), or a con tingency (its truth depends on the truth of the variables). (a) P ∨¬P (b) P ∧¬P (c) ¬ P ∧Q( )⇔ ¬P ∨¬Q( ) (d) ¬ P ∧Q( )⇔ ¬P ∧¬Q( ) (e) P ⇒ Q( )⇔ ¬Q ⇔¬P( ) (f) P ∧ Q ∨ R( )( )⇒ P ∧Q( )∨ P ∧ R( )( ) (g) P ∧Q( )⇔ Q( )⇔ Q ⇒ P( ) (h) P ∨Q( )∧ P ∨¬Q( )∧ ¬P ∨Q( )∧ ¬P ∨¬Q( ) (i) P ⇒ Q( )∨ R ⇒ S( )( )⇒ P ∨ R( )⇒ Q ∨ S( )( ) (j) Q ⇒ P( )∨ P ⇒ Q( )( )⇔ P ∨Q( ) 2. State the converse and the contrapositive of each of the following: (a) If it rains then I’m not going. SOLUTION: CONVERSE: If I don’t go, then it must be raining. CONTRAPOSITIVE: If I go, then it’s not raining. (b) Only if Arthur pulls the sword from the stone will he be king. SOLUTION:Page 2 of 5! This one’s a bit more complicated, so here’s a step-by-step solution. Let P = “Arthur pulls the sword from the stone,” and Q = “Arthur will be king.” Then the original sentence may be symbolized as Q ⇒ P. Thus, CONVERSE (P ⇒ Q) If Arthur pulls the sword from the stone then he will be king. CONTRAPOSITIVE (P ⇒ Q): If Arthur fails to pull the sword from the stone, then he won’t be king. Note that the original sentence is logically equivalent to its contrapositive, as always. (c) If you have a straight then you beat two pair. SOLUTION: CONVERSE: If you beat two pair then you must have a straight. CONTRAPOSITIVE: If you can’t beat two pair then you have no straight. (d) You can’t win if you don’t play. SOLUTION: Let P = “You win,” and Q = “You play.”Page 3 of 5! Then the original sentence may be symbolized as Q ⇒ P. CONVERSE (P ⇒ Q): If you didn’t win then you didn’t play. CONTRAPOSITIVE (P ⇒ Q): If you won then you must have played. 3. Let P be the proposition “The semi-finals are on Saturday.” Let Q be the proposition “Walter will bowl in the semi-finals.” Let R be the proposition “Walter’s team wins the quarter-finals.” Using logical connectives, write a Boolean expression that symbolizes each of the following: (a) If the semi-finals are not on Saturday and his team wins the quarter-finals, then Walter will bowl in the semi-finals. SOLUTION: P ∧ R( )⇒ Q! (b) Walter will bowl in the semi-finals only if his team wins the quarter-finals. SOLUTION: Q ⇒ R! (c) The semi-finals are not on Saturday. SOLUTION: P! (d) The semi-finals are on Saturday but Walter won’t bowl in them. SOLUTION: P ∧Q! (e) Either Walter's team wins the quarter-finals, or the semi-finals are on Saturday and Walter won't bowl in them (but not both; that is, the “or” is exlusive).Page 4 of 5! SOLUTION:!!¬ R ⇔ P ∧Q()( )! Translate the following Boolean expressions into English: (f) P ∨Q SOLUTION: The semis are on Saturday or Walter will bowl in them. (g) ¬P ∧ R( )⇒ Q SOLUTION: If Walter’s team wins the quarter-finals and the semis are not on Saturday, then Walter will bowl in them. (h) Q ⇒ P SOLUTION: Walter will bowl in the semis only if they are on Saturday. (i) ¬P ∧ ¬Q SOLUTION: Walter will not bowl in the semis, which are on Saturday. 4. Let ⊕ denote the exclusive-or operation, defined by the truth table P Q P ⊕ Q0 0 00 1 11 0 11 1 0Page 5 of 5!Use the operations ∨, ∧, and ¬ to construct a Boolean expression equivalent to P ⊕ Q. SOLUTION: P ∧Q( )∨ P