Задачі до теми „Логіка і числення предикатів”

За допомогою предикатів, їх алгебри, операцій квантування може бути формалізована мова математичних означень, тверджень і доведень.

При застосуванні операцій квантування важливі такі закони де Моргана:

= x (x);

= x (x).

Приклад 1. Ввівши предикати, формалізувати:

а) означення обмеженої та необмеженої функцій;

б) означення парної функції і функції, яка не є парною.

Розв’язування 1а). Розглянемо двомісний предикат p(x, A) = „|f(x)|  A”, де предметною областю є множина M = D_f  ( – множина додатних дійних чисел). Означення обмеженості функції є результатом квантування предиката A x p(x, A), (x, A)  M.

Запишемо означення необмеженої функції, яка є запереченням означення обмеженої функції. Скористаємося законами де Моргана

= A x (x, A), (x, A)  M,

(x, A) = „|f(x)| > A”.

Розв’язування 1б). Розглянемо предикати p(x) = „–x  D_f”, q(x) = „f(x) = –f(x)”, x  D_f.

Означення парної функції: x (p(x)  q(x)), x  D_f.

Означення функції, яка не є парною: = x = x ( (x)  (x)).

Приклад 2. Довести, що тотожно істинними є такі формули:

а) x (p(x)  q(x)) ~ x p(x)  x q(x);

б) x (p(x)  q(x)) ~ x p(x)  x q(x);

в) x (p(x)  q(x)) x p(x)  x q(x);

г) x p(x)  x q(x)  x (p(x)  q(x)).

Розв’язування 2а). Нехай ліва частина тотожності істинна для деяких p і q. Тоді для довільного x  M істинне p(x)  q(x), тому p(x) і q(x) однозначно істинне для довільного x, і, отже, x p(x)  x q(x) істинне. Якщо ж ліва частина тотожності хибна, то для деякого x хибне або p(x), або q(x) і права частина також хибна.

Приклад 3. Ввівши предикати, формалізувати означення:

а) непарної функції;

б) несиметричної функції;

в) границі функції в точці;

г) неперервної функції в точці;

д) нескінченно малої функції.

Записати означення, які є запереченням означень в пунктах а) – д).

Розв’язування 3г). Розглянемо інтерпретацію M_f = (M, f), де M – множина дійсних чисел; f – відповідність, що зіставляє із предикатними символами P(x, ), R(), S(x, ) предикати P(x, ): |x – x₀| < ; R():  > 0; S(x, ): |f(x) – f(x₀)| < . Тут x₀ – довільний фіксований елемент відрізка [a, b]. Тоді твердження про те, що функція f(x) є неперервною в точці x₀ записується формулою

()()(x)((R()  P(x, ))  S(x, )).

Розв’язування 3д). Розглянемо інтерпретацію M_f = (M, f), де M – множина дійсних чисел; f – відповідність, що зіставляє з предикатними символами P(x, ), Q(x, ) та R() предикати P(x, ): |x – x₀| < ; Q(x, ): |f(x)| < ; R():  > 0. Тут x₀ – довільний фіксований елемент відрізка [a, b]. Тоді твердження про те, що функція f(x) є нескінченно малою при x  x₀, записується формулою

()()(x)((R()  P(x, ))  Q(x, )).

Приклад 4. Ввівши предикати, формалізувати велику теорему Ферма: „Для довільного цілого n > 2 не існує натуральних чисел x, y, z, які задовольняють рівняння xⁿ + yⁿ = zⁿ”.

Розв’язування. Розглянемо такі предикати:

p(x) = „x – натуральне число”,

q(n) = „n > 2 ”,

r(x, y, z, n) = „xⁿ + yⁿ = zⁿ”, (x, y, z, n)  (N  N  N  N).

Тоді теорема Ферма має такий вигляд:

x y z n (p(x)  p(y)  p(z)  q(n)  (x, y, z, n)).

Приклад 5. Ввести одномісні предикати на відповідних областях і записати з їх допомогою у вигляді логіки предикатів такі висловлювання:

а) довільне натуральне число, яке ділиться на 12, ділиться на 2, 3;

б) жителі Швейцарії обов’язково володіють або французькою, або італійською, або німецькою мовами;

в) неперервна на інтервалі [0, 1] функція зберігає знак або набуває нульового значення.

Приклад 6. Ввести предикати на відповідних областях предметних змінних:

а) якщо a – корінь многочлена від однієї змінної з дійсними коефіцієнтами, то - також корінь цього многочлена;

б) між довільними двома точками на прямій лежить, принаймні, одна точка, яка з ними не збігається;

в) через дві різні точки проходить єдина пряма;

г) через три точки, що не лежать на одній прямій, проходить одна площина;

д) кожний студент виконав, принаймні, одну лабораторну роботу.