EXERCISES. 1. Let P(x) and Q(x) represent “x is a rational number” and “x is a real number”, respectively

1. Let P(x) and Q(x) represent “x is a rational number” and “x is a real number”, respectively. Symbolize the following sentences:

1.1 Every rational number is a real number.

1.2 Some real numbers are rational numbers.

1.3 Not every real number is a rational number.

2. Let C(x) mean “x is a used-car dealer”, and H(x) mean “x is honest”. Translate each of the following into English:

(Ǝx) C(x);

(Ǝx) H(x);

(∀x)(C(x) → ~H(x));

(Ǝx)(C(x) ʌ H(x)), (Ǝx)(H(x) →C(x)).

3. Let P(x), L(x), R(x, y, z), and E(x) represent “x is a point”, “x is a line”, “z passes through x and y”, and “x = y”, respectively. Translate the following: “For every two points, there is one and only one line passing through both points”.

4. An Abelian group is a set A with a binary operator + that has certain properties. Let P(x, y, z) and E(x, y) represent x + y = z and x = y, respectively. Express the following axioms for Abelian groups symbolically.

a) For every x and y in A, there exists a z in A such that x + y = z (closure).

b) If x + y = z and x + y = w, then z = w (uniqueness).

c) (x + y) + z = x + (y + z) (associativity).

d) X + y = y + x (symmetry).

e) For every x and y in A, there exists a z in A such that x + z = y (right solution).

5. For the following interpretation: D = {a, b},

Determine the truth value of the following formulas:

(∀x)(Ǝy) P(x, y);

(∀x)(∀y) P(x, y);

(Ǝx)(∀y) P(x, y);

(Ǝy) ~P(a, y);

(∀x)(∀y) P(x, y)→P(x, y));

(∀x) P(x, x).

6. Consider the following formula:

A: (Ǝx) P(x)→∀x) P(x).

a) Prove that this formula is always true if the domain D contains only one element.

b) Let D = {a, b}. Find an interpretation over D in which A is evaluated to F.

7. Consider the following interpretation: Domain: D = {1, 2},

Assignment of constants a and b:

Assignment for the function f:

Assignment for predicate P:

Evaluate the truth value of the following formulas in the above interpretation:

P(a, f(a)) ʌ P(b, f(b));

(∀x)(Ǝy) P(y, x);

(∀x)(∀y)(P(x, y) →P(f(x), f(y))).

8. Let F₁ and F₂be as follows:

F₁: (∀x)(P(x) →Q(x)),

F₂: ~Q(a).

Prove that ~P(a) is a logical consequence of F₁ and F₂.

Section 3.3

9. Transform the following formulas into prenex normal forms:

(∀x)(P(x) →(Ǝy) Q(x, y));

(Ǝx)(~((Ǝy)P(x, y)) →((Ǝz) Q(z)→ R(x)));

(∀x)(∀y)((Ǝz)P(x, y, z) ʌ ((Ǝu)Q(x, u) →(Ǝz)Q(y, z))).

Section 3.4

10. Consider the following statements:

F₁: Every student is honest,

F₂: John is not honest.

From the above statements, prove that John is not a student.

11. Consider the following premises:

(1) Every athlete is strong.

(2) Everyone who is both strong and intelligent will succeed in his career.

(3) Peter is an athlete.

(4) Peter is intelligent.

Try to conclude that Peter will succeed in his career.

12. Assume that St. Francis is loved by everyone who loves someone. Also, assume that no one loves nobody. Deduce that St. Francis is loved by everyone.