Description
1. Let D be the set of all students at your school. Let M(s) be “s is a math major”, let C(s) be
“s is a Computer Science student” and let E(s) be “s is an engineering student”. Express
each of the following statements using quantifiers, variables and the predicates M(s),
C(s) and E(s).
a. No Computer Science students are engineering students (2 marks)
b. Some Computer Science students are also math majors (2 marks)
2. Given the following Prolog database entries:
sibling(paul,ann).
sibling(jim,jo).
sibling(jim,jacob).
son(bob,jane).
son(tom,paul).
son(bob,jim).
nephew(X,Y) :- son(X,Z),sibling(Z,Y).
Explain whether the following queries succeed or fail, and state what each query returns
if it succeeds. Please show how you arrive at your answer (2 marks)
a. |?- nephew(U,jo).
b. |?- nephew(tom, ann).
3.
a. Use the laws for negating existential statements to derive the following rule:
~(∃x∈D (∃y∈E (P(x,y)))) ≡ ∀x∈D (∀y∈E (~P(x,y))) (1 mark)
b. Some of the arguments stated below are valid by universal modus ponens or
universal modus tollens; others are invalid and exhibit the converse or
inverse error. State which are valid and which are invalid. Justify your
answers. (5 marks)
i. All cheaters sit in the back row.
Monty sits in the back row.
Therefore, Monty is a cheater.
ii. All honest people pay their taxes.
Darth is not honest.
Therefore, Dart does not pay his taxes.
iii. Any sum of two rational numbers is rational.
The sum r+s is rational.
Therefore, the numbers r and s are rational.
iv. For all students x, if x studies discrete mathematics, then x is good at
logic.
Tarik studies discrete mathematics.
Therefore, Tarik is good at logic.
v. If compilation of a computer program produces error messages, then
the program is not correct.
Compilation of this program does not produce error messages.
Therefore, this program is correct.
4. In the domain of natural numbers (N – all integers greater than or equal to 1), how would
you translate these English statements into quantified statements. Use P(x) for “x is
prime” and Q(x) for “x is even”. You may use the <,> and = symbols for any x and y. (3
marks)
a. Some primes are even.
b. All even numbers are greater than 1.
c. There is no prime less than 3.
5. Find the free variables in the following formulas. If a variable appears more than
once in the formula, be clear about which occurrence of the free variable you are
referencing. (2 marks)
a. p(x)∧~r(y,a)
b. ∃x.r(x,y)
6. Proof by generalization from generic particular that the sum of an odd integer and an
even integer is odd. (3 marks)
