ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
И совершенная конъюнктивная нормальная форма
Возникает вопрос, можно ли установить какую-нибудь закономерную связь между структурой формулы и ее семантикой, между ее логической формой и логическим содержанием? Оказывается, что такая связь существует и можно указать простой метод, позволяющий по виду формулы, приведенной к некоторой стандартной форме, судить о том, тождественно-истинная она или нет. Условимся называть элементарной дизъюнкцией формулу, которая имеет вид A 1 Ú A 2 Ú...Ú An, где n ³ 1, a Ai, (i £ n) есть либо переменная, либо отрицание переменной. Например, формула р Ú q Ú ~ r Ú p Ú ~ q Ú r — элементарная дизъюнкция, формула же (p Ù q) Ú r Ú р элементарной дизъюнкцией не является, так как ее первый дизъюнктивный член не есть ни переменная, ни отрицание переменной. Теорема. Элементарная дизъюнкция тождественно-истинна, тогда и только тогда, когда в ней содержится хотя бы одна пара дизъюнктивных членов, из которых один есть некоторая переменная, а другой — ее отрицание. Доказательство. В самом деле, элементарная дизъюнкция, содержащая такую пару, либо уже имеет вид Е Ú ~ E Ú D, где Е — переменная, а D — элементарная дизъюнкция (которой может и не быть), либо ей можно придать этот вид в результате применения правила замены по равносильности (4). Так как подформула Е Ú ~ E тождественно-истинная, то согласно (49') вся элементарная дизъюнкция Е Ú ~ E Ú D тождественно-истинная формула, независимо от того, истинна или ложна подформула D. Наличие переменной и ее отрицания не только достаточное, но и необходимое условие тождественной истинности элементарной дизъюнкции. Действительно, допустим, что в элементарной дизъюнкции такой пары нет. Придадим каждой переменной, не стоящей под знаком отрицания, значение «ложь», а каждой переменной, стоящей под знаком отрицания, значение «истина». Тогда каждый из дизъюнктивных членов получает значение «ложь», а, следовательно, вся элементарная дизъюнкция имеет значение «ложь» и не является тождественно-истинной формулой. Определение. Формула логики высказываний имеет конъюнктивную нормальную форму (КНФ), если она имеет вид В 1 Ù В 2Ù...Ù Вm, где В 1, В 2,..., Вm — элементарные дизъюнкции и m ³ 1. Например, формула p Ù (~ q Ú r) Ù ~ s Ù (~ p Ú q) имеет конъюнктивную нормальную форму. Любая формула логики высказываний в результате ряда равносильных замен может быть приведена к конъюнктивной нормальной форме. Формулу, равносильную данной и имещую конъюнктивную нормальную форму, будем называть конъюнктивной нормальной формой данной формулы. Для того чтобы формулу привести к КНФ, необходимо вначале с помощью известной процедуры привести ее к нормальной форме. Затем каждую подформулу вида (A Ú(B Ù C)) согласно равносильности (6) и каждую подформулу вида ((B Ú C) Ú A) согласно равносильности (6') заменить фоpмyлoй ((A Ú B) Ù (A Ú C)). Формула имеет КНФ, если она имеет нормальную форму и в ней нет подформул вида (A Ú(B Ù C)) и ((B Ú C) Ú A). Рассмотрим процесс приведения формулы к КНФ на следующем примере. Пусть дана формула (~ p Ù q) ® (p «~ r). Приведем ее вначале к нормальной форме: ~(~ p Ù q) Ú (p «~ r); ~(~ p Ù q) Ú ((~ p Ú ~ r) Ù (~~ r Ú p)); (~~ p Ú ~ q) Ú ((~ p Ú ~ r) Ù (~~ r Ú p)). (p Ú ~ q) Ú ((~ p Ú ~ r) Ù (r Ú p)). Затем с помощью равносильности (6) получаем формулу (p Ú ~ q Ú ~ p Ú ~ r) Ù (p Ú ~ q Ú r Ú p), которая имеет КНФ. Формула не единственным образом представима в КНФ. Например, формула p «q имеет следующие представления в КНФ: (~ р Ú q) Ù (~ q Ú р); (~ р Ú q) Ù (~ q Ú р Ú r) Ù (~ q Ú р Ú ~ r); (p Ú ~ q) Ù (q Ú ~ q) Ù (q Ú ~ p). Приводя формулу к КНФ, мы будем в дальнейшем пользоваться следующими сокращенными способами преобразования формул. Так, если знак отрицания стоит перед конъюнкцией [дизъюнкцией], содержащей более двух конъюнктов [дизъюнктов], как, например, в формулах ~(А Ù В Ù С) [~(А Ú В Ú С)], ~(А Ù В Ù С Ù D) [~(А Ú В Ú С Ú D)] и т.д., то мы не будем восстанавливать скобки и дважды, трижды и т. д. применять правило замены по равносильностям (10) [(11)], а сразу будем писать формулы (~ А Ú ~ В Ú ~ С) [(~ А Ù ~ В Ù ~ С)], (~ А Ú ~ В Ú ~ С Ú ~ D) [(~ А Ù ~ В Ù ~ С Ù ~ D)] и т. д., т. е. пользоваться обобщенными законами де Моргана: ~(A 1 Ù A 2 Ù... Ù Аn) равносильно ~ A 1 Ú ~ A 2 Ú...Ú ~ Аn; ~(A 1 Ú A 2 Ú...Ú Аn) равносильно ~ A 1 Ù ~ A 2 Ù...Ù ~ Аn. Далее, если в формуле встречаются подформулы вида (А Ù В) Ú (C Ù D), (А Ù В) Ú (С Ù D Ù Е) и т. п., то вместо того, чтобы дважды, трижды и т. д. применять правило замены по равносильности (6) и (6') и писать, например, в первом случае сначала формулу ((А Ù В) Ú С) Ù ((А Ù В) Ú D), а затем (С Ú А) Ù (С Ú В) Ù (D Ú А) Ù (D Ú В), будем сразу писать последнюю формулу, т. е. пользоваться обобщенным законом дистрибутивности дизъюнкции относительно конъюнкции: (A 1 Ù... Ù Аm) Ú (В 1Ù...Ù Вn) равносильно (В 1Ú A 1) Ù...Ù (В 1Ú Аm)Ù...Ù (Вn Ú A 1) Ù...Ù (Вn Ú Аm). Кроме того, мы не будем писать перед подформулами двойных отрицаний, если последние появятся в ходе преобразований, так как согласно процедуре приведения формулы к КНФ все двойные отрицания должны быть устранены. Формула, имеющая КНФ, тождественно-истинна тогда и только тогда, когда тождественно-истинны все ее конъюнктивные члены, т. е. когда каждая элементарная дизъюнкция содержит хотя бы одну пару дизъюнктов, из которых один есть некоторая переменная, а другой — ее отрицание. Таким образом, по виду некоторой формулы в КНФ можно судить о том, тождественно-истинна она или нет. Например, пусть дана формула (р ® ~ q) «(q ® ~ р). Приводим ее к КНФ: (~(р ® ~ q) Ú (q ® ~ р)) Ù (~(q ® ~ р) Ú (р ® ~ q)); (~(~ р Ú ~ q) Ú (~ q Ú ~ р)) Ù (~(~ q Ú ~р) Ú(~ p Ú ~ q)); ((р Ù q) Ú (~ q Ú ~ р)) Ù ((q Ù р) Ú(~ p Ú ~ q)); (~ q Ú ~ p Ú p) Ù (~ q Ú ~ p Ú q) Ù (~ p Ú ~ q Ú q) Ù (~ p Ú ~ q Ú p). Можно видеть, что все конъюнктивные члены КНФ данной формулы содержат некоторую переменную одновременно со знаком отрицания и без него. Следовательно, данная формула тождественно-истинная. Каждая не тождественно-истинная формула имеет КНФ, которая называется совершенной. Определение. Совершенной конъюнктивной нормальной формой (СКНФ) некоторой формулы называется такая ее КНФ, которая удовлетворяет следующим условиям: а) в ней нет двух одинаковых конъюнктивных членов (одинаковыми считаются такие конъюнктивные члены, которые получаются один из другого в результате замены по равносильности (4)); б) ни в одном конъюнктивном члене нет двух одинаковых дизъюнктов; в) ни в одном конъюнктивном члене нет таких двух дизъюнктов, из которых один есть переменная, а другой — отрицание этой переменной; г) в каждом конъюнктивном члене содержатся все переменные данной формулы. Для того чтобы привести формулу к СКНФ, необходимо: 1) известным уже способом привести ее к КНФ; 2) на основании равносильностей (2), (4) и (8) устранить из КНФ повторяющиеся конъюнкты, т. е. из всех имеющихся одинаковых конъюнктивных членов оставить один и вычеркнуть остальные; 3) на основании равносильностей (4) и (9) устранить все повторения в конъюнктивных членах КНФ, т. е. из всех имеющихся одинаковых дизъюнктов оставить один и вычеркнуть остальные; 4) на основании равносильностей (2), (4) и (47) устранить из КНФ те конъюнктивные члены, которые являются тождественно-истинными элементарными дизъюнкциями; 5) ко всем тем конъюнктивным членам, в которых отсутствует какая-нибудь из содержащихся в данной формуле переменных Е, на основании равносильности (50) приписать знак дизъюнкции и вслед за ним тождественно-ложную конъюнкцию (Е Ù ~ Е), а затем применить правило замены по равносильности (6). Эту процедуру повторять до тех пор, пока не окажется, что в каждый конъюнктивный член входят все переменные, содержащиеся в данной формуле; 6) если в получившейся КНФ снова появились одинаковые конъюнктивные члены, то надо устранить повторения. Пусть, например, к СКНФ нужно привести формулу ((p ® q) Ù ~(~ r Ù ~ p) Ù (~ q ® r))Ú р. Вначале приведем ее к КНФ: ((~ p Ú q) Ù (r Ú p) Ù (q Ú r)) Ú p; ((p Ú ~ p Ú q) Ù (p Ú r Ú p) Ù (p Ú q Ú r)). Затем вычеркиваем первый конъюнктивный член и устраняем повторения во втором. Получаем формулу (p Ú r) Ù (p Ú q Ú r). Так как в первом конъюнктивном члене отсутствует переменная q, то присоединяем к нему знаком дизъюнкции формулу (q Ù ~ q): (р Ú r Ú (q Ù ~ q)) Ù (р Ú q Ú r). Воспользовавшись законом дистрибутивности дизъюнкции относительно конъюнкции, получаем формулу (р Ú r Ú q) Ù (р Ú r Ú ~ q) Ù (р Ú q Ú r). Устраняем один из одинаковых конъюнктивных членов и получаем формулу в СКНФ: (р Ú r Ú q) Ù (р Ú r Ú ~ q). Упражнения I. Привести к КНФ следующие формулы и проверить, являются они тождественно-истинными или нет: 1) р ® ((р ® q) ® q); 2) ((р ® q) Ù (r ® s)) ® ((р Ù r) ® (q Ù s)); 3) (р ® q) ® ((р Ù r) ® (q Ù r)); 4) (р ® (q Ù r)) «((р ® q) Ù (р ® r)); 5) ((р ® q) Ú (р ® r)) ® (р ® (q Ú r)); 6) (p «q) ® ((p «r) ® (q «r)). 7) ((p Ú ~ q) ® r) ® (p Ù r); 8) (p Ú r) ® ((q Ù ~ r) ® p); 9) (p ® q) ® (~ q ® (p Ú r)); 10) (p ® r) ® ~(q ® (q ® r)). II. Привести к СКНФ следующие формулы: 1) (р ® q) Ú ~(~ q Ú r); 2) ((~(р ® q) ® q) Ú ~ q) Ú (р Ù r); 3) (p «q) ® ((p «r) ® (q «r)). 4) ((p Ú ~ q) ® r) ® (p Ù r); 5) ~ (p Ú r) ® ~ ((q Ù ~ r) ® ~ p); 6) (p ® q) ®~ ((q ® p) Ú r); 7) ~ (p ® r) ® ~(q Ú (q ® r)).
Не нашли, что искали? Воспользуйтесь поиском:
|