Homework #2
KEY –
Answers in red
Look in text and briefly review the following topics under functions:
reflexive, symmetric, transitive
composition of
as a mapping of values in the domain to values in the range
Write the answers to the problems below. You may write them directly on a printed copy of the sheet (or key them in before printing it). I have provided some information which may be helpful. Consult your texts if you need more help.
Related implications that can be formed from p → q
The proposition q → p is called the converse of p → q
The contrapositive of p→q is the proposition q’ → p’
The proposition of p’ → q’ is called the inverse of p → q
Problem #1 - State the converse, contrapositive, and the inverse of each of these inplications: (1.1 #22)
a. If it snows tonight, then I will stay at home.
If I stay home, then
it will snow tonight
If I do not
stay at thime, then it will not snw tonight
If it does
not snow tonight, then I will not stay home
b. I go to the beach whenever it is a sunny summer day.
Whenever
I go to the beach, it is a sunny
summer day
Whenever i do not go to the beach, it
is not a sunny summer day
Whenever it is not a sunny day, I do
not go to the beach
c.
When I stay up late, it is necessary that I
sleep until
If I sleep until
If I do not sleep
until
If I don’t stay up late, then I don’t
sleep until
“System specifications should not contain conflicting requirements. If they did there would be no way to develop a system that satisfies all specifications. Consequently, propositional expressions representing these specifications need to be consistent. That is, there must be an assignment of true values to the variables in the expressions that makes all the expressions true.” (Rosen, p. 11)
Problem #2 - Are these system specifications
consistent? (show
a formal proof of an inconsistency)
(1.1 #46)
Whenever the system software is being upgraded, users cannot access the file system.
If the users can access the file system, then they can save new files.
If users cannot save new files, then the system software is not being upgraded.
yes
Problem #3 – Find the dual of each of these propositions (1.2 # 30 b and c)
a. (p Ù q Ù r) ∨ s
( p ∨ q ∨ r
) Ù s
b. (p ∨ F ) Ù (q ∨ T)
( p Ù T) ∨ (q Ù F)
Problem #4 - Show that p NAND q is logically equivalent to ¬ (p Ù
q)
|
p |
q |
p|q |
p Ù q |
¬ (p Ù q) |
|
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
Problem #5 – Express the negation of these propositions using quantifiers, and then express the negation in English. (1.3 # 32)
a. Some drivers do not obey the speed limit.
All drivers obey the
speed limit
b. All Swedish movies are serious
Some Swedish movies are not serious
c. No one can keep a secret
Some people can keep
a secret.
Problem #6 – Evaluate these quantities (2.4 #36 b,d)
a. 144 mod 7
4
b. 199 mod 19
9
Problem #7 - Complete the bolded row in the table we started in class using implications, negations, conjunctions, or disjunctions of the propositions p and q.
|
decimal |
values |
--> |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
|
p |
q |
(pÙp’) |
pÙq |
(p→q)’ |
p |
|
q |
(p xor q) |
p∨q |
(p∨q)’ |
(P→Q)Ù(Q→P) |
Q’ |
|
P’ |
p→q |
(pÙq)’ |
(pVp’) |
|
23 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
22 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
21 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
20 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |