Discrete Mathematical Structures Summer-2014 Homework #2 Due Mon 06/16/14, 8AM. Solutions 47 Points total. 1) (3 Points) Are the following pairs of propositions equivalent? a) (1 Point) Today is not Tuesday – Today is Monday. Solution:Not equivalent. 'Not Tuesday' is equivalent to 'either Monday, Wednesday, Thursday, Friday, Saturday or Sunday'. b) (1 Point) The book does not cost 3 dollars – The book costs either less than 3 dollars or more than 3 dollars. Solution:Equivalent. c) (1 Point) It is neither windy nor cold in Urbana – It is both not windy and not cold in Urbana. Solution:Equivalent. 2) (10 Points) Which of the following are tautologies? Which are contradictions? a) (2 Points) (p→q)∧(¬q→p) Solution:p=F and q = T make the expression true, p=T and q=F make the expression false. Neither tautology nor contradiction. b) (2 Points) (p→q)∧(¬p→¬q) Solution:Neither tautology nor contradiction. This is basically 'if and only if' relation. c) (2 Points) (p→q)∨(q→p) Solution:Tautology. (q→p) is equivalent to (¬p→¬q), thus we have (p→q)∨(¬p→¬q). If p is false, the left part of 'or' must be true, if p is true, then the right part must be true. d) (2 Points) (p→q)→(q→p) Solution:Neither tautology nor contradiction. Consider the cases p=q=true and (p=false,q=true). e) (2 Points) (p→q)→(¬q→¬p) Solution: It is tautology. 3) (6 Points, 3 Points for each interpretation)You are given the following prepositions: • f - passed the final • m1 - passed midterm1 • m2 - passed midterm2 • h - submitted all your homework. A - get an A. • r - retake the course. Find two logically nonequivalent specifications of the statement below (this demonstrates the possible ambiguity of programming languages) If you pass the final and one of the two midterms then if you have submitted all your homework, then you get an A, else you will have to retake it. Solution: (for each part 3 points, 1 point for weak attempt, 2 for decent attempt, 3 for perfect attempt) (f∧(m1∨ m2))→((h→A)∧(!h→r)) ((!(f∧(m1∨ m2))→r)∧((f∧(m1∨ m2)∧h)→A) • 4) (8 points)Express the following system specifications using propositions. Are these system specifications consistent? “If the file system is not locked, then new messages will be queued. If the file system is not locked, then the system is functioning normally, and conversely, If new messages are not queued, they will be sent to the message buffer. If the file system is not locked, then new messages will be sent to the message buffer. New messages will not be sent to the message buffer.” Solution: Expressing with prepositions (6 Points, 1 point for each predicate, 2 points for the formula): FSL – file system is locked. NMQ – new messages will be queued. NOR – system functioning normally. BUF – new messages are sent to message buffer. (!FSL→NMQ)∧(!FSL→NOR)∧(NOR→!FSL)∧(!NMQ→BUF)∧(!FSL→BUF)∧!BUF. The specifications are consistent (2 Points). The variable assignments are: BUF=false; FSL=true; NMQ=true; NOR=true; 5) (14 Points) 5.1)(4 Points, one point for each correct table) Write down the truth table of the following propositions: Solution: Note that all the four cases below are disjunctions of conjunctions. This is called disjunctive normal form. You'll see that every time we add a conjunction of all three literals, it'll 'turn on' one entry in the truth table. The conclusion is that it's good to use disjunctive normal form to describe a truth table with few rows that contain true value. a) (p∧¬q∧r) p 0 q 0 r 0 value 0 p q r value 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 b) (p∧¬q∧r)∨ (p∧q∧¬r) p q r value 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 c) (p∧¬q∧r)∨ (p∧q∧¬r)∨ (¬p∧¬q∧¬r) p q r value 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 d) (p∧¬q∧r)∨ (p∧q∧¬r)∨(p∧¬q∧¬r)∨ (¬p∧¬q∧¬r) p 0 q 0 r 0 value 1 p q r value 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 5.2)(4 Points, one for each correct table) Write down the truth table of the following propositions: Solution, dually to the case below, here we deal with conjunctive normal form. It's good to describe truth tables with few raws that contain false values. a) (¬p∨¬ q∨¬ r) p q r value 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 b) (¬p∨¬ q∨¬ r)∧(p∨ q∨ ¬r) p q r value 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 c) (¬p∨¬ q∨¬ r)∧(p∨ q∨ ¬r)∧(p∨ ¬q∨ ¬r) p q r value 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 d) (¬p∨¬ q∨¬ r)∧(p∨ q∨ ¬r)∧(p∨ ¬q∨ ¬r)∧(p∨ q∨ r) p q r value 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 5.3) (4 Points, 2 points for each part) You know how to write a truth table for a predicate. Here we ask you to do the inverse process. Write down a predicate with the truth tables given below (you may only use the connectives ¬, ∧, and ∨ ) a) p q r value 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 p q r value 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 Solution: Here we want y ou to use the observations from 5.1 and 5.2 to write the expression in disjunctive normal form: (¬p∧¬q∧¬r)∨ (p∧q∧¬r) b) p q r value 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 Solution: Here we want you to use the observations from 5.1 and 5.2 to write the expression in conjunctive normal form: (¬p∨ q∨ r)∧(p∨ q∨ r) 5.4) (2 Points) Prove that you can express any logic function with only three connectives:¬, ∧, and ∨ . We can represent every logical function as a truth table. And any truth table can be represented in either disjunctive normal form or conjunctive normal for as shown in 5.1 and 5.2, where we use only the three connectives above. End of proof. 6) (6 Points, 2 points for every part.) Without using the truth table, show that the following are tautologies a) [¬p∧(p∨q)]→q ¬p∧(p∨q)≡(¬p∧p)∨(¬p∧q)≡flase [¬p∧(p∨q)]→q ≡ false→q≡¬false∨q≡true∨q≡true b) [(p→q)∧(q→r)]→(p→r) (p→q)∧(q→r)≡(¬p∨q)∧(¬q∨r) (p→r)≡(¬p∨r) [(p→q)∧(q→r)]→(p→r)≡¬((¬p∨q)∧(¬q∨r))∨(¬p∨r)≡(p∧¬q)∨(q∧¬r)∨¬p∨r (p∧¬q)∨(q∧¬r)∨¬p∨r≡((p∧¬q)∨¬p)∨((q∧¬r)∨r)≡((p∨¬p)∧(¬q∨¬p))∨((q∨r)∧(¬r∨r)) ((p∨¬p)∧(¬q∨¬p))∨((q∨r)∧(¬r∨r))≡(¬q∨¬p)∨(q∨r)≡true∨¬p∨r c) [p∧(p→q)]→q [p∧(p→q)]→q≡(¬[p∧(¬p∨q)])∨q≡(¬p∨(p∧¬q))∨q≡((¬p∨p)∧(¬p∨¬q))∨q≡¬p∨¬q∨q≡true

© Copyright 2023 ExpyDoc