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 contingency 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 semifinals 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 Q 0 0 0 0 1 1 1 0 1 1 1 0 Page 5 of 5 Use the operations and to construct a Boolean expression equivalent to P Q SOLUTION P Q P Q