This practice test was created by Behnam Robatmili for Moore's CS 313k Intro to 
Logic, Sets, and Functions class.  It's hosted here as a courtesy to those 
involved.

Prove the following forumlas or give a counter example
1) (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)