Dear everybody, pt. 2
Ian W.
The following are not OK:
1) S <--> {x : phi}. This is not OK because (at this point, anyway)
you don't want to say these two sets are equivalent. You want to say
they are equal. Those two words don't have the same meaning. Think
hard about this before the final exam.
2) S = phi. This is not OK because S is a set and phi is a formula. S
is a thing, and phi is a statement about things. So S and phi can't be
equal.
3) S <--> phi. This is not OK because a thing can't be equivalent to a
statement about things.
4) S = {forall x : phi}. This is not OK because I have no idea what it
means. Maybe you meant to write {x : phi}. I have no idea.
The following are OK:
5) S = {x : phi}. In this case, you are saying S is equal to the set
of all x that satisfy phi. That makes sense because there are things
on either side of the equal sign.
6) e in S <--> phi\{x <- e}. In this case, you are giving necessary
and sufficient conditions for an element to be included in S. This
makes sense because you have formulas on either side of the
equivalence sign. This is also roughly the same as 5, after using the
set equality axiom, the universal conclusion inference rule, and the
member axiom.
Questions?
Ian
Behnam Robatmili
As you may know as a part of my extended office hours, I will discuss
a practice test (appended to this message) on May 12th, 4:00-7:00 p.m.
(WEL 2.256)
Notice that this doesn't mean that your final exam is gonna very
similar to this test! You can think of this test as an extra resource
for your final test preparation in addition to the book, previous
exams, and quizzes, etc. This version of the practice test is
tentative and I will let you know if any correction needed before that
date.
Thanks,
Behnam
1) Prove (Q197 from the book):
((A -> (B v C))
^
(A v C)
^
(C -> ~ B))
->
C
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)).
3) Consider a relation R on A and a variable x. For this problem, 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
2- x has at least one relative
3- x has only one relative
4- x has 2 relatives
5- x has at least two relatives
6- If every relative of x is happy, then x is happy
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))
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))
6) Write down the roster notation for the following sets:
1- {1, 2} union {2, 3}
2- {} union {{}} union ({1, 2} inter {2 5 6})
3- {x + 2: exist y: (Natp y) ^ (3 < y < 10) ^ (x = 2*y)}
4- {x: (Natp x) ^ x < 3} x ps({1, 2})
7) Prove:
1- (A inter B) sube A
2- Asube (A union B)
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
2- Is R a function
3- What is dom(R)
4- What is ran(R). Write the answer in the set notation without using R.
5- Is R reflexive?
6- Is R irreflexive?
7- Is R symmetric?
8- Is R asymmetric?
9- Is R antisymmetric?
10- Is R transitive?
11- Is R total?
12- Is R connected?
13- Is R an equivalence relation?
14- Is R a partial order?
As extra practice, 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?
2- Is R sube AxA?
3- Is R = AxA
4- Find an element that exists in AxA but doesn't exist in AxA?
5- Is there any element that exists in R and not in AxA?
6- If R is a equivalence relation on A, what is [A]/R?
7- If R is a equivalence relation on A, What is [1]/R?
8- If R is a equivalence relation on A, what are the partitions
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)?
2- What is ran(f)? Write the answer in the set notation without using
f.
3- Is f 1:1
4- Is it a theorem that (f: N -> N)?
5- Is f onto N
6- What's (f o f)(5)
7- Find a g such that (f o g) != (g o f)
David S.
R"?
-David
