Solutions

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

Download Report