Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Теорема 1.13. Для каждой пропозициональной формы существует равносильная ей к.н.ф. (не единственная). Можно сформулировать правила для нахождения д.н.ф. и к.н.ф., равносильных заданной форме. Пусть задана форма Л: 1) исключить из А все связки, кроме —i, &, v, 2) добиться, чтобы —1 относилась только к буквам; 3) если раскрыть скобки по первому дистрибутивному закону, то получится д.н.ф.; 4) если сгруппировать выражение в скобки, пользуясь вторым дистрибутивным законом, то получится к.н.ф. Легко доказать следующую теорему. Теорема 1.14. Для того, чтобы пропозициональная форма А была тавтологией, необходимо и достаточно, чтобы равносильная ей к.н.ф. содержала в каждом множителе хотя бы одну букву вместе с отрицанием этой же буквы. По теореме 1.14 можно выяснить, выполнима форма Л или нет. Для этого находим к.н.ф. для -пА, и если найденная к.н.ф. тавтология, то А невыполнима, если же найденная к.н.ф. не тавтология, то А выполнима. § 7. Совершенные нормальные формы Совершенной дизъюнктивной нормальной формой (с.д.н.ф.) пропозициональной формы A(Ai,A2,... ,Ап) называется д.н.ф. этой формы, удовлетворяющая следующим условиям: -нет одинаковых слагаемых; -в каждое слагаемое входят все буквы Ai,A2, •••,Ап один и только один раз (и только они) с отрицанием либо без отрицания. С.д.н.ф. для А можно построить по таблице истинности этой формы. Для этого выбираем строки, где А равна И; пусть это будут строки ki,k2,...,km- Для каждой выбранной строки ki, 1< i< т, строим элементарное произведение {конституенту единицы или полную конъюнкцию) Ki следующим образом. Если в выбранной строке ki буква Aj принимает значение И, то в Ki она входит без отрицания, если же Aj=JI, то в Ki она входит с отрицанием. Дизъюнкция построенных произведений и будет с.д.н.ф., и можно доказать, что эта с.д.н.ф. равносильна А Рассмотрим пример на построение с.д.н.ф. Пусть форма А (А,В,С) ложна тогда и только тогда, когда ложен один и только один из аргументов. Пайти с.д.н.ф. ддяА(А,В,С). Решение. Составим таблицу истинности. Выберем строки, где А принимает значение И, т.е. строки с номерами: 1, 2, 3, 5 и 8. Для первой строки элементарное произведение представляется в виде конъюнкции —A&—S&—\C, для вто- 18