Префиксная нормальная форма.

 

Формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения. В частности, все ТИ-формулы (и все ТЛ-формулы) эквивалентны. Если формулы  и  эквивалентны, то ~  – ТИ-формулы.

Множество ТИ-формул логики предикатов входит в любую теорию, исследование этого множества – важная цель логики предикатов. При этом выделяются две проблемы:

1) получение ТИ-формул (проблема построения порождаящей процедуры для множества ТИ-формул);

2) проверка формулы на истинность (проблема разрешающей процедуры).

В логике предикатов прямой перебор всех переменных может быть невозможен, если предметные переменные имеют бесконечные области определения.

Поэтому в логики предикатов используются различные косвенные приемы, в том числе эквивалентные соотношения, позволяющие выполнить корректные преобразования предикатных формул. В логике (алгебре) предикатов справедливы все эквивалентные соотношения логики (алгебры) высказываний, а также собственные эквивалентные соотношения, включающие связки " и $ (ниже под Y будем понимать переменное высказывание или формулу, не содержащую x):

Ø$ x P (x)~" x Ø P (x).                                                                         (4.1)

Ø" x P (x)~$ x Ø P (x).                                                                         (4.2)

" x ( (x)& (x))~(" x (x)&" x (x)).                                      (4.3)

$ x ( (x)Ú (x))~($ x (x)Ú$ x (x)).                                         (4.4)

" x " y P (x, y)~" y " x P (x, y).                                                              (4.5)

$ x $ y P (x, y)~$ y $ x P (x, y).                                                                (4.6)

" x (P (x)& Y)~(" x P (x)& Y).                                                              (4.7)

" x (P (x)Ú Y)~(" x P (x)Ú Y).                                                               (4.8)

$ x (P (x)& Y)~($ x P (x)& Y).                                                               (4.9)

$ x (P (x)Ú Y)~($ x P (x)Ú Y).                                                                 (4.10)

Указанных соотношений, а также эквивалентных соотношений логики (алгебры) высказываний достаточно для выполнения преобразований формул логики (алгебры) предикатов.

Как и в логике высказываний, в логике предикатов существуют эквивалентные нормальные формы представления любых предикатных формул, в том числе префиксная (или пренексная) нормальная форма.

Префиксной нормальной формой (ПНФ) называется формула, имеющая вид: ... F, где , ,...,  – кванторы; F – формулы, не имеющая кванторов, с операциями {&,Ú,Ø}. В логике предикатов для любой формулы существует эквивалентная ей префиксная нормальная форма.

Процедура получения ПНФ:

2. Используя формулы

~ = ( ® )&( ® ),                                                     (4.11)

® = Ø Ú ,                                                                         (4.12)

заменить операции ®,~ на &,Ú,Ø.

2. Воспользовавшись выражениями (4.1), (4.2), а также правилом двойного отрицания и правилами де Моргана

ØØ P = P,                                                                                             (4.13)

Ø( Ú )=Ø &Ø ,                                                                  (4.14)

Ø( & )=Ø ÚØ ,                                                                  (4.15)

представить предикатную формулу таким образом, чтобы символы отрицания были расположены непосредственно перед символами предикатов.

3. Для формул, содержащих подформулы вида

" x (x)Ú" x (x),   $ x (x)&$ x (x),

ввести новые переменные, позволяющие использовать соотношения (4.7) – (4.10).

4. С помощью формул (4.3) – (4.10) получить формулы в виде ПНФ.

Пример 1. В соответствии с соотношениями (4.3) – (4.4) квантор общности обладает свойством дистрибутивности относительно конъюнкции, а квантор существования – относительно дизъюнкции. Показать, что если в указанных формулах поменять местами кванторы " x и $ x, то полученные при этом соотношения будут верны лишь в одну сторону:

$ x ( (x)& (x))®($ x (x)&$ x (x)),                                      (4.16)

(" x (x)Ú" x (x))®" x ( (x)Ú (x)).                                     (4.17)

 

В соотношениях (4.16) и (4.17) левая часть более сильная, чем правая, поскольку она требует для своей истинности выполнения более жестких условий, чем правая. Так, в левой части (4.16) требуется, чтобы (a) и (a) были истинны для одного и того же a, тогда как в правой части  и  могут быть истинны при различных  и . Что касается (4.17), то здесь требуется, чтобы в левой части хотя бы один предикат выполнялся для всех a Î M; правой части достаточно, чтобы один предикат был истинен там, где ложен другой. В этих рассуждениях, по существу, содержатся доказательства справедливости (4.16) и (4.17).

Из доказанного следует, что в рассмотренных случаях нельзя непосредственно получить ПНФ предикатной формулы. Ее удается построить введением новых переменных:

$ x (x)&$ y (y)~$ x $ y ( (x)& (y)),                                      (4.18)

" x (x)Ú" y (y)~" x " y ( (x)Ú (y)).                                     (4.19)

 

Пример 2. Привести к ПНФ следующую предикатную формулу:

Ø($ x " y (x, y)&$ x " y (x, y)).

 

Поскольку в данной предикатной формуле имеются два высказывания $ x " y (x, y) и $ x " y (x, y), объединенные связкой & и общим отрицанием Ø, то, применив правило де Моргана (4.15) к исходной формуле, получим:

Ø($ x " y (x, y)&$ x " y (x, y)) ~ Ø$ x " y (x, y)ÚØ$ x " y (x, y).

Воспользуемся далее эквивалентным соотношением (4.1):

Ø$ x " y (x, y)ÚØ$ x " y (x, y) ~ " x Ø" y (x, y)Ú" x Ø" y (x, y).

Продолжая перемещение символов отрицания непосредственно к символам предикатов, используем соотношение (4.2):

" x Ø" y (x, y)Ú" x Ø" y (x, y) ~ " x $ y Ø (x, y)Ú" x $ y Ø (x, y).

Так как квантор общности " x не дистрибутивен относительно дизъюнкции Ú, поменяем в каком-либо предикате, например, во втором, переменную x на новую переменную z:

" x $ y Ø (x, y)Ú" x $ y Ø (x, y) ~ " x $ y Ø (x, y)Ú" z $ y Ø (z, y).

Воспользовавшись дважды эквивалентным соотношением (4.8) или соотношением (4.19), получим:

" x $ y Ø (x, y)Ú" z $ y Ø (z, y) ~ " x " z ($ y Ø (x, y)Ú$ y Ø (z, y)).

Поскольку квантор существования $ y дистрибутивен относительно дизъюнкции Ú (см. 4.4), окончательно получим префиксную нормальную форму для исходной предикатной формулы:

" x " z ($ y Ø (x, y)Ú$ y Ø (z, y)) ~ " x " z $ y (Ø (x, y)ÚØ (z, y)).

 

Пример 3. Получить ПНФ предикатной формулы:

" x " y ($ z ( (x, z)& (y, z))®$ u (x, y, u)).

 

Для получения ПНФ удалим из исходной формулы связку ®, используя формулу булевой алгебры (4.12):

" x " y ($ z ( (x, z)& (y, z))®$ u (x, y, u)) ~ " x " y (Ø$ z ( (x, z)& (y, z))Ú$ u (x, y, u)).

Избавимся от отрицания перед квантором $ z, используя (4.1):

" x " y (Ø$ z ( (x, z)& (y, z))Ú$ u (x, y, u)) ~ " x " y (" z Ø( (x, z)& (y, z))Ú$ u (x, y, u)).

Воспользуемся далее правилом де Моргана (4.15):

" x " y (" z Ø( (x, z)& (y, z))Ú$ u (x, y, u)) ~ " x " y (" z (Ø (x, z)ÚØ (y, z))Ú$ u (x, y, u)).

Так как последний предикат не зависит от переменной z, используем соотношение (4.8):

" x " y (" z (Ø (x, z)ÚØ (y, z))Ú$ u (x, y, u)) ~ " x " y " z (Ø (x, z)ÚØ (y, z)Ú$ u (x, y, u)).

Аналогично для вынесения квантора " u (благодаря независимости первых предикатов от переменной u) воспользуемся (4.10):

" x " y " z (Ø (x, z)ÚØ (y, z)Ú$ u (x, y, u)) ~ " x " y " z $ u (Ø (x, z)ÚØ (y, z)Ú (x, y, u)).

Полученная в результате выполненных эквивалентных преобразований формула является ПНФ исходной формулы.

 

 

Пример 4. Получить ПНФ предикатной формулы

(Ø$ u (u)®Ø" y " u (y, u))®" x (x).

 

Для получения ПНФ осуществим эквивалентные преобразования, указывая каждый раз справа номер используемого эквивалентного соотношения:

(Ø$ u (u)®Ø" y " u (y, u))®" x (x) ~                                  по (4.12)

(ØØ$ u (u)ÚØ" y " u (y, u))®" x (x) ~                                по (4.13)

($ u (u)ÚØ" y " u (y, u))®" x (x) ~                                      по (4.12)

Ø($ u (u)ÚØ" y " u (y, u))Ú" x (x) ~                                     по (4.14)

(Ø$ u (u)&ØØ" y " u (y, u))Ú" x (x) ~                                 по (4.13)

(Ø$ u (u)&" y " u (y, u))Ú" x (x) ~                                       по (4.1)

(" u Ø (u)&" y " u (y, u))Ú" x (x) ~                                       по (4.3)

" u (Ø (u)&" y (y, u))Ú" x (x) ~                                            по (4.7)

" u " y (Ø (u)& (y, u))Ú" x (x) ~                                            по (4.8)

" u " y " x (Ø (u)& (y, u)Ú (x)) ~                                            по (4.5)

" x " y " u (Ø (u)& (y, u)Ú (x)).

 

 

Вопросы для самопроверки и упражнения.

 

1. Проиллюстрировать справедливость соотношений (4.16) и (4.17) для предикатов

(x) – “ x – четное число” и (x) – “ x – нечетное число” и недопустимость замены в (4.16) и (4.17) символа ® на ~, т.е. показать, что для данных предикатов указанные соотношения справедливы лишь в одну сторону.

2. Получить ПНФ следующих предикатных формул:

а) $ x " y (x, y)®" x $ y (x, y);

б) ($ x " y (x, y)Ú$ x (x))®$ y " z (y, z);

в) Ø($ x " z (x, z)®$ y $ z (y, z))&Ø$ y $ z (y, z);

г) ($ x " z (x, z)ÚØ" x " y (x, y))®Ø"z (z);

д) (" x $ y " z (x, y, z)ÚØ" y (y))®Ø" x "z (x, z);

е) Ø(" x " y " z Ø (x, y, z)®$ y " z (y, z))&" x "z (x, z);

ж) (" x " y Ø (x, y)®$ x $ y " z (x, y, z))®$z (z);

з) Ø" x $ y Ø (x, y)®(" y " z (y, z)®Ø"z (z));

и) (Ø$ y Ø (y)®Ø" x " y (x, y))®"z (z));

к) Ø(" x " y Ø (x, y)Ú" x $ y (x, y)).

 

 

ВОПРОСЫ КОЛЛОКВИУМА

“ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ”.

 

 

1. Определение высказывания. Сложные высказывания.

 

2. Определение логической формулы.

 

3. Метод установления эквивалентности формул.

 

4. Основные схемы логически правильных рассуждений.

 

5. Определение функции алгебры логики.

 

6. Таблицы истинности унарной и бинарной логических операций.

 

7. Инфиксная и префиксная формы задания логической функции.

 

8. Полнота и базис (определения) в булевой алгебре.

 

9. Классы Поста (определения).

 

10. Полином Жегалкина (способы построения).

 

11. Критерий полноты Поста-Яблонского.

 

12. Свойства функций Шеффера и Вебба (Пирса).

 

13. Основные эквивалентные соотношения (законы) булевой алгебры.

 

14. Определение СДНФ (СКНФ).

 

15. Приведение к ДНФ (КНФ).

 

16. Алгоритмы перехода от табличного задания булевой функции к СДНФ (СКНФ).

 

17. Метод Блейка-Порецкого упрощения СДНФ.

 

18. Указать все булевы функции от 2-х переменных в классах Т ₀, Т ₁, L, S, M.

 

19. Алгебра логики (определение).

 

20. Способы проверки правильности рассуждений.

 

21. Методы построения таблиц истинности для функций алгебры логики от n переменных.

 

22. Принцип двойственности в булевой алгебре.

 

23. Изоморфизм булевых алгебр (определение).

 

24. Соответствия между предикатами, отношениями и функциями.

 

25. Изоморфизм булевых алгебр множеств и двоичных векторов.

 

26. Условия гомоморфизма в алгебре множеств и булевой алгебры.

 

27. Изоморфизм булевых алгебр множеств и логических функций.

 

28. Определение n -местного предиката.

 

29. Кванторы.

 

30. Интерпретация формул логики предикатов.

 

31. Определение модели в логике предикатов.

 

32. Истинность, ложность или выполнимость формул логики предикатов.

 

33. Эквивалентные соотношения в логике предикатов.

 

34. Префиксные нормальные формы (ПНФ) в логике предикатов.

Список литературы