Answers to the practice test
Behnam Robatmili
Here are the answers to the practice test. Please notice:
1) There might be typos or errors in my answers. So if you see
something weird in my answers, bring it up.
2) There are many topics that were not covered in this practice test,
but may be on the final exam. So don't rely on all your resources
including the book, homeworks, quizzes, past exams, your notes, etc.
Thanks and good luck.
Behnam
1) Prove the following formulas or give a counter example:
Q 197)
((A -> (B v C))
^
(A v C)
^
(C -> ~ B))
->
C
{contrapositive}
~C
->
~((A -> (B v C)) ^ (A v C) ^ (C -> ~B))
{hype}
~C
->
~((A -> (B v nil)) ^ (A v nil) ^ (nil -> ~B))
{short circuit}
~C
->
~((A -> B) ^ A)
{implicative disj}
~C
->
~((~A v B) ^ A)
{De morgan, basic}
~C
->
~(A^B)
!!!!
So, lets come up with a counter example: A = t, B = t, C = nil
(t -> t) ^ t ^ t -> nil <-> nil
Q202:
((R ^ ((~P --> ~R) ^ (P --> (S v U)))) --> (S v U))
{Contraposition}
((R ^ (R --> P) ^ (P --> (S v U))) --> (S v U)
{forward chain}
((R ^ P ^ (P --> (S v U))) --> (S v U)
{forward chain}
((R ^ P ^ (S v U)) --> (S v U)
{hyp}
((R ^ P ^ (S v U)) --> t
{short circuit}
t
2) Suppose allones is defined as follows:
(defun allones (x)
(if (endp x) t (and (equal (car x) 1) (allones (cdr x)))))
Prove: (allones x) & (allones y) --> (allones (app x y)).
BC: ~(consp x) -> (allones x) & (allones y) --> (allones (app x y))
Proof:
~(consp x)
->
(allones x) & (allones y) --> (allones (app x y))
={def of allones, def of app, consp-not-endp, if-t}
~(consp x)
->
t & (allones y) --> (allones y)
={short circuit}
~(consp x)
->
(allones y) --> (allones y)
{basic}
t
IS:
(consp x)
^
(allones (cdr x)) & (allones y) --> (allones (app (cdr x) y))
->
(allones x) & (allones y) --> (allones (app x y))
Proof:
(consp x)
^
(allones (cdr x)) & (allones y) --> (allones (app (cdr x) y))
->
(allones x) & (allones y) --> (allones (app x y))
={promotion}
(consp x)
^
(allones (cdr x)) & (allones y) --> (allones (app x (cdr y)))
&
(allones x) & (allones y)
--> (allones (app x y))
={def of allone, def of app, consp-not-endp, if-nil}
(consp x)
^
(allones (cdr x)) & (allones y) --> (allones (app (cdr x) y))
&
(equal (car x) 1)
&
(allones (cdr x)) & (allones y)
--> (allones (cons (car x) (app (cdr x) y))))
={def of allone, def of app, consp-not-endp, if-nil}
(consp x)
^
(allones (cdr x)) & (allones y) --> (allones (app (cdr x) y))
&
(equal (car x) 1)
&
(allones (cdr x)) & (allones y)
--> (allones (cons (car x) (app (cdr x) y))))
={forward chaining, defallones, cons-consp, car-cons, cdr-cons}
(consp x)
^
(allones (app (cdr x) y))
&
(equal (car x) 1)
&
(allones (cdr x)) & (allones y)
-->
(equal (car x) 1)
&
(allones (app (cdr x) y))
={hype 2X}
(consp x)
^
(allones (app (cdr x) y))
&
(equal (car x) 1)
&
(allones (cdr x)) & (allones y)
-->
t & t
=
t
3) Consider a relation R on A and a variable x. We call y a relative
of x if R(x,y) is true.
Also assume a function of arity one, happy, that returns a boolean
property, happiness, of any variable in A.
Formalize the following sentences:
1- x has no relative
~(exit e in A: R(x,e))
or
(forall e in A: ~R(x,e))
2- x has at least one relative
(exist e in A: R(x,e))
3- x has exactly one relative
(exist e in A: R(x,e)) ^ (forall a,b in A: (R(x,a) ^ R(x,b)) -> (a = b))
or
(exist! e in A: R(x,e))
4- x has exactly 2 distinct relatives
(exist e in A: (exist f in A: R(x,e) ^ R(x,f) ^ (e != f)) ^ (forall
a,b,c in A: ((R(x,a) ^ R(x,b) ^ R(x,c)) -> ((a = b) v (b = c) v (a =
c))))
5- x has at least two distinct relatives
(exit e in A: (exist f in A: R(x,e) ^ R(x,f) ^ (e != f)))
6- If every relative of x is happy, then x is happy
(forall e in A: R(x, e)->(happy e)) -> (happy x)
4) Prove:
(forall x: (h x b) -> (f x) = x) ^ (forall y: (exist z: (g z) = y)) ^
(h a b)
-> (exist w: (f (g w) = a))
{forall-hyp, x<-a}
((h a b) -> (f a) = a) ^ (forall y: (exist z: (g z) = y)) ^ (h a b)
-> (exist w: (f (g w) = a))
{forward chain}
((f a) = a) ^ (forall y: (exist z: (g z) = y)) ^ (h a b)
-> (exist w: (f (g w) = a))
{forall-hyp, y <- a}
((f a) = a) ^ (exist z: (g z) = a) ^ (h a b)
-> (exist w: (f (g w) = a))
{exist-hyp}
((f a) = a) ^ ((g z) = a) ^ (h a b)
-> (exist w: (f (g w) = a))
={Rewrite replacing a with (g z) in (f a)}
((f (g z)) = a) ^ ((g z) = a) ^ (h a b)
-> (exist w: (f (g w) = a))
{exist-conc, w <- z}
((f (g z)) = a) ^ ((g z) = a) ^ (h a b)
-> (f (g z) = a)
{hype}
((f (g z)) = a) ^ ((g z) = a) ^ (h a b)
-> t
5) Negate the following formula (incorrect final answer will cost you
points!):
(forall x: (forall y: (P x y z))) -> (exist x: (Q x z))
~(forall x: (forall y: (P x y z))) -> (exist x: (Q x z))
={Imp Disj}
~(~(forall x: (forall y: (P x y z))) v (exist x: (Q x z)))
={De morgan, double negate}
(forall x: (forall y: (P x y z))) ^ ~(exist x: (Q x z))
={quantifier rules}
(forall x: (forall y: (P x y z))) ^ (forall x: ~(Q x z))
6) Write down the roster notation for the following sets:
1- {1, 2} union {2, 3} =
{1, 2, 3}
2- {} union {{}} union ({1, 2} inter {2 5 6}) =
{{}} union {2} = {{} 2}
3- {x + 2: exist y: (Natp y) ^ (3 < y < 10) ^ (x = 2*y)} =
{2*4+2 2*5+2 2*6+2 2*7+2 2*8+2 2*9+2} = {10 12 14 16 18 20}
4- {x: (Natp x) ^ x < 3} x ps({1 2}) =
{0 1 2} x {{} {1} {2} {1 2}} =
{
(0.{}) (0.{1}) (0.{2}) (0.{1 2})
(1.{}) (1.{1}) (1.{2}) (1.{1 2})
(2.{}) (2.{1}) (2.{2}) (2.{1 2})
}
7) Prove:
1- (A inter B) sube A
2- Asube (A union B)
1-
(A inter B) sube A
={subset}
(forall v: (v in (A inter B)) -> (v in A))
={inter}
(forall v: (v in {z: (z in A) ^ (v in B)}) -> (v in A))
={member}
(forall v: ((v in A) ^ (v in B)) -> (v in A))
={basic}
(forall v: t)
{def of forall}
=t
2-
A sube (A union B)
={sube}
(forall v: (v in A) -> (v in (A union B)))
={union}
(forall v: (v in A) -> (v in {z: (z in A) v (z in B)}))
={member}
(forall v: (v in A) -> ((v in A) v (v in B)))
={hyp}
(forall v: (v in A) -> (t v (v in B)))
={short circuit}
(forall v: (v in A) -> t)
={short circuit}
(forall v: t)
{def of forall}
=t
8) For R = {<x.y>: x in N ^ y in N ^ (x = 3*y + 1) }, answer the
following questions with yes and no (incorrect answer will cost you
points!).
1- Is R a relation? Yes
2- Is R a function? Yes
3- What is dom(R) {3v + 1: v in N}
4- What is ran(R). Write the answer in the set notation without using
R. N
5- Is R reflexive? No
6- Is R irreflexive? Yes
7- Is R symmetric? No
8- Is R asymmetric? Yes
9- Is R antisymmetric? Yes
10- Is R transitive? No
11- Is R total? No
12- Is R connected? No
13- Is R an equivalence relation? No. Because it is not (ref, symm ,
tans)
14- Is R a partial order? No. Because it is not (ref, anti, trans)
You can repeat this same problem with different relations such as:
R = {<x.y>: ((natp x) = (natp y))}
R = {<x.y>: ((natp x) != (natp y))}
R = {<x.y>: x in N ^ y in N ^ y < 2*x}
...
9)
Let A = {1, A, 2, B, 3}
Let R = {(1.1) (1.2) (1.3) (2.2) (2.1) (2.3) (3.3) (3.1) (3.2) (A.A)
(A.B) (B.B) (B.A)}
Answer the following questions (incorrect answers will cost you points)
1- How many elements are there in AxA? 25
2- Is R sube AxA? Yes
3- Is R = AxA? No
4- Find an element that exists in AxA and doesn't exist in R? (A.3)
5- Is there any element that exists in R and not in AxA? No
6- If R is a equivalence relation on A, what is [A]/R? {A B}
7- If R is a equivalence relation on A, What is [1]/R? {1 2 3}
8- If R is a equivalence relation on A, what are the partitions
induced by R? {{1 2 3} {A B}}
Notice that according to the definition of partition, that are several
partitions of A. For example {{1 B} {3 A 2}} is also a valid
partitions of A, but the only partition induced by R is {{1 2 3} {A
B}}, which includes equivalence classes induced by R.
10) Let f = {<x, y>: x in N ^ y = x + 1}. Answer the following
questions (incorrect answer will cost you points)
1- What is dom(f)? N
2- What is ran(f)? Write the answer in the set notation without using
f. {v + 1: (v in N)}
3- Is f 1:1? Yes.
4- Is it a theorem that (f: N -> N)? Yes. Because f is a function, and
dom(f) is N and ran(f) is a subset of N
(f: N -> N) <-> (Function(f) ^ (dom (f) = A) ^ (ran (f) sube B))
5- Is f onto N? No. Rangre of f is not equal to N.
6- What's (f o f)(5)? ((5 + 1) + 1) = 7
7- Find a g such that (f o g) != (g o f).
let g = {<x, y>: x in N ^ y = 5}
let x = 1
(f o g)(1) = f(g(1)) = f(5) = 5 + 1 = 6
(g o f)(1) = g(f(1)) = g(1 + 1) = 5