Примеры записи математических предложений формулами логики предикатов

I. Арифметика.

Пусть N – множество натуральных чисел с нулем. N ={0, 1, 2,...}.

Рассмотрим два предиката:

S(x, y, z)= u Û x + y = z.

P(x, y, z)= u Û x × y = z.

=< N, S⁽³⁾, P⁽³⁾>, s=<S⁽³⁾, P⁽³⁾>

1. x =1;

2. х – четное число;

3. x =2;

4. y \ x;

5. x – простое число;

6. x, y – простые числа близнецы;

7. x < y;

8. $ бесконечно много простых чисел близнецов.

1. e (x)=и Û x =1 Û" y (y × x = y) Û " y P(y, x, y).

2. Ч (x)=и Û $ y S(y, y, x).

3. x =2 Û x =1+1 Û $ z (z =1 & x = z + z) Û

$ z (z =1 & S(z, z, x)) Û $ z (e(z) & S(z, z, x))Û $ z " y (P(y, z, y) & S(z, z, x)).

4. D (x, y)=и Û y \ x Û $ z (y × z = x) Û $ z P(y, z, x).

5. Pr (x)=и Û x ¹1 & (" y " z P(y, z, x) ® e(y)eÚ(z)) Û &((" y)(" z)(P(y, z, x) ® ((" u) P(y, u, u)Ú(" v) P(z, v, v)))).

6. Б (x, y)=и Û Pr(x) & Pr(y) & (y - x =2) Û

Pr(x) & Pr(y) & $ z (z =2 & S(x, z, y)) Û

Pr(x) & Pr(y) & ($ z $ t e(t) & S(t, t, z) & S(x, z, y)).

7. x < y Û $ z (x + z = y) Û $ z S(х, z, y).

8. " z $ x $ y Б(x, y)&$ t S(z, t, x).

Истинность этой формулы не известна

Т.1: Сложение натуральных чисел коммутативно.

" x " y " u (S(x, y, u) ® S(y, x, u)).

" x, y Î N

(x + y = y + x)

Пусть x + y = u,

тогда y + x=u.

Т.2: Сложение натуральных чисел ассоциативно.

" x " y " z " u " v " w

(S(x, y, u) & S(u, z, v)&

S(y, z, w) ® S(x, w, v))

" x, y, z

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

Обозн.: x + y = u

y + z = w

u + z = v

x + w = v

u, v, w