7.4. Пряма, обернена, протилежна теореми.

Необхідна й достатня умови

Розглянемо чотири теореми:

(Т1): ; (Т2): ;

(Т3): ; (Т4): .

Визначення 7.15. Дві теореми, у яких умова першої є висновком другої, а висновок першої є умовою другої, називають взаємно оберненими одна до одної.

Якщо одну з теорем назвати прямою, то інша буде оберненою. Серед наведених теорем Т1-Т4 теореми Т1 і Т2, а також теореми Т3 і Т4 — взаємно обернені.

У загальному випадку пряма й обернена теореми не рівнозначні, тобто одна з них може бути істинною, а інша — хибною. Так, теорема “Якщо чотирикутник є прямокутником, то його діагоналі рівні” — правильна, а обернена теорема “Якщо в чотирикутнику діагоналі рівні, то чотирикутник є прямокутником”— неправильна (можна розглянути рівнобічну трапецію).

Визначення 7.16. Дві теореми, в яких умова і висновок однієї є запереченням відповідно умови й висновку іншої, називають взаємно протилежними.

Серед наведених теорем Т1-Т4 теореми Т1 і Т3, а також теореми Т2 і Т4 — взаємно протилежні. Протилежними до наведених вище теорем є відповідно такі теореми: “Якщо чотирикутник не є прямокутником, то його діагоналі не рівні” (неправильна) і “Якщо в чотирикутнику діагоналі не рівні, то чотирикутник не є прямокутником” (правильна).

Зауважимо, що теореми Т1 і Т4, а також теореми Т2 і Т3 завжди еквівалентні. Як приклад, покажемо це для Т1 і Т4 (для Т2 і Т3 — аналогічно):

;

;

;

.

Із таких еквівалентностей випливає, що якщо доведено теорему Т1, то доведено й теорему Т4, аналогічно, якщо доведено теорему Т2, то доведено й теорему Т3.

Розглянемо теорему Т1 . Множиною істинності предиката є множина . Тоді множиною хибності цього предиката буде множина . Множина буде порожньою лише в тому випадку, коли . Таким чином, предикат є істинним у тому і тільки в тому випадку, коли . При цьому кажуть, що предикат є логічним наслідком предиката , а також, що предикат є достатньою умовою для предиката , а предикат є необхідною умовою для предиката . Так, в теоремі “Якщо х — натуральне число, то воно додатне” предикат “х — додатне число” є логічним наслідком предиката “х — натуральне число”. При цьому предикат “х — натуральне число” є достатньою умовою для предиката “х — додатне число”.

У математиці часто трапляється, що взаємно обернені теореми Т1 і Т2 істинні водночас. Це можливо за умови, коли . При цьому з теореми Т1 випливає, що умова є достатньою для , а з теореми Т2 випливає, що умова є необхідною для . Отже, якщо теореми Т1 і Т2 істинні, то умова є необхідною й достатньою для (також у цьому разі є необхідною й достатньою для ). Оскільки висловлювання Т1 і Т2 істинні, тобто , то буде істинним висловлювання .

7.5. Випереджальні нормальні форми

В алгебрі логіки й алгебрі висловлювань використовуються дві нормальні форми — ДНФ і КНФ. У логіці предикатів вводиться ще третя нормальна форма, яку називають випереджальною нормальною формою (ВНФ).

Визначення 7.17. Зведеною формою називають формулу, в якій із логічних символів використовують тільки логічні символи кон’юнкції ( ), диз’юнкції ( ) й заперечення ( ), причому символ заперечення міститься тільки перед символами предикатів.

Приклад 7.14. Формули , , , є зведеними формулами логіки предикатів; формули , — не зведені.

Для будь-якої формули логіки предикатів існує еквівалентна їй зведена форма; множини вільних і зв’язаних змінних у цих формул однакові.

Визначення 7.18. Зведену форму називають випереджальною (префіксною, пренексною, попередньою) нормальною формою (ВНФ), якщо вона взагалі не містить символів кванторів або ж усі символи кванторів стоять на початку формули, тобто формула має вигляд , де — або , або , або порожній символ ( ), — формула, яка не містить кванторів. Послідовність символів кванторів називають префіксом даної формули, а формула — її матрицею.

Для кожної формули існує еквівалентна їй випереджальна нормальна форма.

Приклад 7.15. Наведемо приклади формул, поданих у випереджальній нормальній формі (ВНФ): , , .

Алгоритм побудови ВНФ для довільної формули логіки предикатів.

1. Подати логічні операції імплікації ( ) й еквівалентності ( ) через операції кон’юнкції ( ), диз’юнкції ( ) й заперечення ( ), скориставшись еквівалентностями:

;

або .

2. Для перенесення символа заперечення всередину формули до символів предикатів можна скористатися законом заперечення , законами де Моргана , і перенесенням квантора через заперечення , .

3. У випадку необхідності перейменувати зв’язані змінні.

4. Використовуючи еквівалентності щодо винесення квантора за дужки, винести квантори на початок формули.

Приклад 7.16. а). Для формули побудуємо її ВНФ. Послідовно застосовуючи закони еквівалентності, матимемо:

(поданння еквівалентності

через , , );

(перенесення квантора через заперечення).

На цьому етапі одержано зведену форму; виконаємо еквівалентні перетворення щодо винесення кванторів на початок формули:

(дистрибутивний закон для квантора

існування при диз’юнкції);

(перейменування зв’язаних змінних);

(винесення квантора за дужки);

(винесення квантора за дужки).

Отже, для заданої формули ми одержали ВНФ:

.

б). Побудуємо ВНФ для формули :

(поданння імплікації через , );

(перенесення квантора через заперечення);

(закон де Моргана);

(перенесення квантора через заперечення);

(закон заперечення);

(перейменування зв’язаної змінної х в );

(винесення квантора за дужки).

Для формули побудовано її ВНФ:

.

в). Побудуємо ВНФ для формули :

(закон де Моргана);

(перенесення квантора через

заперечення);

(перейменування зв’язаної

змінної х в );

(винесення квантора за дужки);

(винесення квантора за дужки);

Для формули побудовано її ВНФ:

.

Випереджальні нормальні форми застосовують у процедурах пошуку доведень теорем у численні предикатів.