Випереджені нормальні форми
У логіці висловлювань були введені дві нормальні форми: кон’юнктивна і диз’юнктивна. В аксіоматичній системі логік вводиться третя нормальна форма, яку називають випередженою нормальною формою.
Означення 4.2.1.Формула Ф у логіці предикатів знаходиться у випередженій нормальній формі (ВНФ) тоді і тільки тоді, коли вона може бути зображена у вигляді ( )… (
) (А), де (
) є або (
х), або (
х) і всі
різні для різних і = 1, …, п, а А – формула, що не містить квантора. Приставку (
) називають префіксом, а А – матрицею формули Ф. Якщо формула А залежить від вільної змінної х, то це записується як А (х), якщо ні, то – А.
Теорема 4.2.1.Для будь-яких формул F, G, H теорії числення першого порядку справедливі такі еквівалентності:
а)
х F(x)
х (
F (x));
б)
х F(x)
х (
F(x));
в) х F(x)
G
х (F(x)
G);
х F(x)
G
х (F(x)
G);
г) х F(x)
G
х (F(x)
G);
х F(x)
G
х (F(x)
G);
д) х F(x)
х Н (х)
х (F(x)
Н (х));
е) х F(x)
х Н (х)
х (F(x)
Н (х));
є) х F(x)
х Н (х)
х
у (F(x)
Н (у));
ж) х F(x)
х Н (х)
х
у (F(x)
Н (у)).
Доведення . Виконаємо доведення еквівалентності.
а)
х F(x)
х (
F(x)). Нехай r – довільна інтер-претація на деякій області R. Якщо
(
х F(x)) істинна в інтерпретації r, то
х F(x) хибна в r. Це означає, що існує такий елемент k(x)
R, для якого F ( k (x) ) хибна, або те саме, що
F (k (x) ) істинна в r. Отже,
х (
F(x)) істинна в r.
Якщо (
х F(x)) хибна в r, то
х F(x) істинна в r. Це означає, що F(x) виконується на всіх послідовностях із R або що
F(x) не виконується на жодній такій послідовності з R. Отже,
х (
F(x)) хибна в r. Таким чином,
(
х F(x))
х (
F(x)).
Доведення еквівалентності б) аналогічне доведенню еквівалентності а).
Доведемо еквівалентність в) х F(x)
G
Û х (F(x)
G). Нехай маємо
хF(x)
G
(
хF(x))→ →G
х (
F(x)) → G.
Отже,
1) х (
F(x)) → G – гіпотеза;
2) F(x) →
х (
F(x)) – правило 7;
3) F(x) → G – транзитивність із 1) і 2) ;
4) x (
F(x) → G)
x (F(x)
G) – загальнозначність із 3).
І навпаки:
1) x (F(x)
G)
x (
F(x) → G) – гіпотеза ;
2) F(x) → G – правило 6 із 1;
3) ( F(x) → G) → (
G → F(x)) ‒ тавтологія ;
4) G → F(x) – МР із 2) і 3) ;
5) x (
G → F(x)) – узагальнення із 4 ;
6) х (
G → F(x)) → (
G →
х F(x)) – схема аксіом АП5 ;
7) G →
x F(x) – МР із 5 і 6 ;
8) ( G →
xF(x)) → (
x F(x) → G) – тавтологія ;
9)
x F(x) → G
x F(x)
G – МР із 7) і 8).
Доведемо спочатку першу еквівалентність г).
1) х F(x)
G
х (
F(x)) → G – гіпотеза ;
2) ( F(x)) → G – правило 6 ;
3) ( F(x)) → G) →
х (
F(x) → G) – правило 7 ;
4) х (
F(x)
G)
х (F(x)
G) – МР із 2) і 3).
І навпаки:
1) х (
F(x) → G) – гіпотеза;
2) х (
F(x) → G) → (
F(x) → G) – правило 7 ;
3) F(x) → G – МР із 1) і 2) ;
4) x (
F(x)) →
F(x) – правило 6 ;
5) x (
F(x)) → G
x (
F(x))
G
х (F(x))
G – транзитивність із 3) і 4).
Доведення інших еквівалентностей із в) і г) тепер легко випливає із законів де Моргана.
x F(x)
G
(
x F(x)
G)
Û (( х
F(x))
G
(
х (
F(x)
G)
Û (
х
(F(x)
G)
x (F(x))
G).
x F(x)
G
(
x F(x)
G)
Û( х (
F(x))
G)
(
х (
F(x)
G)
Û
(
х
(F(x)
G)
x (F(x)
G).
Аналогічно доводяться й інші еквівалентності із г).
Доведення решти еквівалентностей пропонуються як вправи.
Теорема доведена.
Із теореми 4.2.1 випливає такий метод побудови ВНФ. Для зведення формули Ф до випередженої нормальної форми використовують такі дії:
а) вилучення логічних зв’язок “ →” і “ ” :
А В = (А → В)
(В → А) ; А → В =
А
В ;
б) вилучення і перенесення знака “ ” всередину формул:
(
x F(x)) =
х (
F(x));
(
х F(x)) =
= x (
F(x));
F = F;
в) перенесення кванторів:
Q x Р(х) G = Q x (F(x)
G);
Q x Р(х) G = Q x (F(x)
G);
х F(x)
х Н (х) =
х (F(x)
Н (х));
х F(x)
х Н (х) =
х (F(x)
Н (х));
Q1 х F(x)
х Н (х) =
х
у (F(x)
Н (у));
Q1 х F(x)
х Н (х) =
х
у (F(x)
Н (у)).
Виходячи із методу побудови ВНФ, алгоритм отримання випередженої нормальної форми матиме такі кроки.
1. Вилучити логічні зв’язки еквіваленції “ ” та імплікації “ →” за допомогою правил а).
2. Перенести знак операції заперечення “ ” всередину формул, користуючись правилами:
(F
G) =
F
G;
(F
G) =
F
G, і правилами б).
3. Виконати перейменування пов’язаних змінних, якщо є така необхідність.
4. Винести квантори на початок формули, використовуючи правила в).
Обґрунтуванням цього алгоритму є твердження, що безпосередньо випливає з теореми 4.2.1.
Теорема 4.2.2. Алгоритм випередженої нормальної форми перетворює будь-яку формулу А теорії числення предикатів першого порядку АП в таку формулу В, яка знаходиться у ВНФ, що ├ А В у ПL.
Приклад 4.2.1. Звести формулу х F(x) →
х Н (х) до ВНФ.
Розв’язання. Користуючись кроками 1, 2, 4 алгоритму, отримаємо
х F(x) →
х Н (х) =
(
х F(x))
х Н (х) =
= х (
F(x))
х Н (х) =
х (
F(x)
Н (х)).
Приклад 4.2.2.Отримати ВНФ для формули
х
у
z (Р (х, у)
Р(у, z)) →
z R(x, y, z).
Розв’язання. Користуючись кроками 1, 2, 3, 4 алгоритму, отримаємо
х
у
z (Р (х, у)
Р (у, z)) →
z R(x, y, z) =
=( z
y (
z (Р(х, у)
Р(у, z))
z R(х, у, z) =
= x
y
z (
Р(х, у)
Р(у, z))
u R(х, у, и) =
= x
y
z
u (
Р(х, у)
Р(у, z)
R(х, у, и)).
Оскільки матриця А формули Ф не містить кванторів, то її можна подати у кон’юнктивній нормальній формі (КНФ). Формула Р знаходиться у кон’юнктивній нормальній формі, якщо вона має вигляд Р = …
,
де =
…
, і кожне
‒ це атомарна формула або її заперечення.