## 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)