Рівносильність формул

Нехай формули F і G мають одну й ту саму множину вільних змінних.

Означення 4. Формули F і G є рівносильними в заданій інтерпретації, якщо на будь-якому наборі значень вільних змінних вони набувають однакових значень (тобто якщо формули виражають у цій інтерпретації один і той самий предикат). Формули F і G є рівносильними на множині М, якщо вони рівносильні у всіх інтерпретаціях, заданих на множині М. Формули F і G є рівносильними (в логіці предикатів), якщо вони рівносильні на всіх множинах.

Наведемо кілька правил переходу від одних формул до інших, рівносильних ім. Для формул логіки предикатів зберігаються всі рівносильності та правила рівносильних перетворень логіки висловлювань. Крім того, справедливі такі правила.

1. Перенесення квантора через заперечення. Нехай А – формула, що містить вільну змінну x. Тоді справджуються рівносильності

А(x)  (x) (x); (2)

А(x)  (x) (x). (3)

Доведемо спочатку рівносильність (2). Нехай x₁, …, x_n – множина (може бути порожньою) всіх вільних змінних формули A, відмінних від x. Нехай M_f = (M, f) – довільна інтерпретація. Доведемо, що на будь-якому наборі значень своїх вільних змінних <a₁, …, a_n>, a_i  M, формули А(x) й (x) (x) набувають однакових значень істинності.

Можливі два випадки:

а) для будь-якого елемента a  M = 1;

б) для будь-якого елемента a₀  M = 0.

У першому випадку для будь-якого елемента a  M маємо = 0. Звідси за означенням = 0. З іншого боку, в цьому випадку = 1.Звідси = 0.

У другому випадку для елемента a₀  M маємо = 1. Звідси = 1. З іншого боку, в цьому випадку = 0.Звідси = 1. Рівносильність (2) доведено.

Доведемо рівносильність (3). Застосуємо рівносильність (2) до формули (x). Тоді

(x)  (x) (x)  (x)A(x).

Звідси

A(x)  (x)  (x)A(x).

2. Винесення квантора за дужки. Нехай формула A(x) містить вільну змінну x, формула В не містить змінної x й обидві вони задовольняють п.3 означення формул. Тоді

(x)(A(x)  B)  (x)A(x)  B;

(x)(A(x)  B)  (x)A(x)  B;

(x)(A(x)  B)  (x)A(x)  B;

(x)(A(x)  B)  (x)A(x)  B.

Доведемо першу з цих рівностей (інші доводяться аналогічно).

Нехай , …, – усі вільні змінні формули (x)(A(x)  B). Тоді вони ж будуть усіма вільними змінними формули (x)A(x)  B.

Розглянемо довільну інтерпретацію з множиною M. Нехай <a₁, …, a_n>, a_i  M – довільний набір значень вільних змінних , …, . Оскільки формула В не містить змінної x, можна визначити значення цієї формули в наборі <a₁, …, a_n> (точніше, в його частині, що стосується вільних змінних формули В).

Якщо = 0, то = 0 і для будь-якого елемента a з множини M у наборі значень <a, a₁, …, a_n> своїх вільних змінних x, , …, формула A(x)  B набуває значення 0. Звідси = 0. Якщо = 1, то для будь-якого елемента а з множини М у наборі <a, a₁, …, a_n> формули A(x)  B й A(x) набувають однакових істинностей. Звідси = = .

Зазначимо, що якщо не вимагати, щоб формула В не містила змінної x, то будуть справджуватися тільки дві рівносильності:

(x)(A(x)  B(x))  (x)A(x)  (x)B(x);

(x)(A(x)  B(x))  (x)A(x)  (x)B(x).

3. Переставлення однойменних кванторів. Для кванторів  та  маємо:

(y)(x)A(x, y)  (x)(y)A(x, y);

(x)(y)A(x, y)  (y)(x)A(x, y).

4. Перейменування зв’язаних змінних. Замінюючи зв’язану змінну формули A іншою змінною, що не входить у цю формулу, у кванторі й усюди в області його дії дістаємо формулу, рівносильну A.

Це твердження доводиться за довжиною формули.

Під довжиною формули розумітимемо загальну кількість символів предикатів, логічних символів та символів кванторів, які входять до неї. Так, формула

(x₁) (x₁, x₂)  (x₃) (x₃)

має довжину 5.

Формули, в яких із логічних символів застосовуються тільки символи , , , причому символ зустрічається лише перед символами предикатів, називаються зведеними.

Приклад 5. З наведених нижче формул

1. (x₁)  (x₁, x₂),

2. (x₁) (x₁)  (x₂) (x₂, x₃),

3. (x₁)  ( x₂),

4. (x₁) (x₁)  (x₂) (x₂),

5. (x₂)  (x₁)

перші дві формули – зведені, а інші не є зведеними.

Правильна така теорема.

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

Така зведена формула називається зведеною формою заданої формули.

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

Приклад 6. Розглянемо такі формули

1. (x₁)(x₂)( (x₁)  (x₁, x₂)) – нормальна формула.

2. (x₁) (x₁)  (x₂) (x₂) – зведена формула, що не є нормальною.

Мають місце такі твердження.

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

2. Для будь-якої формули існує рівносильна їй нормальна формула.