Лекция: Высказывания и логические операции над ними.

Понятие высказывания.Предметом исследования алгебры высказываний являются высказывания. Но алгебра высказываний не ставит целью их всестороннее изучение. Из многочисленных свойств высказывания алгебру высказываний интересует лишь одно: истинно оно или ложно. Именно это и является определяющим свойством высказывания. Итак, под высказыванием понимается такое предложение, которое либо истинно, либо ложно. Высказывание не может быть одновременно и истинным, и ложным. В дальнейшем будем считать, что имеется первоначальная совокупность некоторых простейших высказываний, называемых элементарными или исходными, о каждом из которых точно известно, истинно оно или ложно. Причем в этой совокупности имеются как истинные высказывания, так и ложные. Примеры предложений, являющихся высказываниями, и предложений, таковыми не являющимися. Договоримся обозначать конкретные высказывания начальными заглавными буквами латинского алфавита А, В, С, D,… или теми же буквами с индексами внизу.

Приведем примеры высказываний, которые будут использованы в

дальнейшем:

А1: «Москва— столица России»;

А2: «Саратов находится на берегу Невы»;

А3: «Все люди смертны»;

А4: «Сократ— человек»;

А5: «7 < 4»;

А6: «Волга впадает в Каспийское море»;

А7: «А. С. Пушкин— великий русский математик»;

А8: «Снег белый».

Обозначив истинное высказывание символом 1, а ложное — 0, введем функцию X, заданную на совокупности всех высказываний и принимающую значения в двухэлементном множестве 0;1, по следующему правилу:

Функция  называется функцией истинности, а значение  Р— логическим значением или значением истинности высказывания Р. Для приведенных высказываний имеем логические значения

Отметим, что в литературе имеются следующие обозначения для истинных высказываний: 1, И, t (от англ. true — истинный) и для ложных высказываний: 0, Л, f (от англ. false — ложный). Из этих обозначений будем использовать 1 и 0. Это обусловлено рядом причин. Во-первых, таблицы истинности для формул алгебры высказываний принимают более лаконичный и стандартизированный вид, так как в этом случае наборы значений пропозициональных переменных можно расположить в порядке возрастания чисел, которые этими наборами закодированы в двоичной системе счисления. Во-вторых, более удобный и математически строгий вид принимают многие формулы и алгоритмы алгебры высказываний. В-третьих, обозначение 0 и 1 принято и более целесообразно в приложениях математической логики к компьютерам и информатике. Из элементарных высказываний с помощью операций над высказываниями или логических связок строят сложные высказывания. Перейдем к точному

описанию таких построений.

Отрицание высказывания. Определение 1.1 Отрицанием высказывания Р называется новое высказывание, обозначаемое Р (читается: «не Р» или «не верно, что Р»), которое истинно, если высказывание Р ложно, и ложно, если

высказывание Р истинно. Другими словами, логическое значение высказывания Р связано с логическим значением высказывания Р, как указано в следующей таблице, называемой таблицей истинности операции трицания:

Здесь может возникнуть вопрос, почему приписывание истинности или ложности высказыванию Р осуществляется именно на основании приведенной таблицы. Конечно, можно ответить, что об определениях не спорят. Но ведь мы желаем построить математическую теорию (алгебру выказываний), которая в какой-то мере отражала бы реально существующий в природе человеческого мышления процесс построения составных высказываний из элементарных и имела бы реальный смысл. Затем мы должны будем развить нашу математическую теорию, а полученные выводы применить в практике мышления и при этом не войти в противоречие с общеизвестными законами мышления. Определение отрицания с помощью приведенной таблицы (как, впрочем, и других логических связок с помощью соответствующих таблиц) появилось как результат длительного опыта, и оно полностью оправдало себя на практике.

Конъюнкция двух высказываний. Определение 1.3. Конъюнкцией двух высказываний Р и Q называется новое высказывание, обозначаемое P  Q (читается: «Р и Q»), которое истинно лишь в единственном случае, когда истинны оба исходных высказывания Р и Q, и ложно во всех остальных случаях. Другими словами, логическое значение высказывания P  Q связано с логическими значениями высказываний Р и Q, как указано в следующей таблице, называемой таблицей истинности операции конъюнкции:

Практика полностью подтвердила, что именно такое распределение значений истинности наиболее соответствует тому смыслу, который придается в процессе мыслительной деятельности связующему союзу «и».

Дизъюнкция двух высказываний. Определение 1.5. Дизъюнкцией двух высказываний Р и Q называется новое высказывание, обозначаемое P  Q (читается «Р или Q»), которое истинно в тех случаях, когда хотя бы одно из высказываний Р или Q истинно, и ложно в единственном случае, когда оба высказывания Р и Q ложны. Другими словами, P  Q — такое высказывание, логическое значение которого связано с логическими значениями исходных высказываний Р и Q так, как указано в следующей таблице, называемой таблицей истинности операции дизъюнкции:

Импликация двух высказываний. Определение 1.7. Импликацией двух высказываний P и Q называется новое высказывание, обозначаемое P  Q (читается: «если Р, то Q», или «из Р следует Q», или «Р влечет Q», или «Р достаточно для Q», или «Q необходимо для Р»), которое ложно в единственном случае, когда высказывание Р истинно, а Q — ложно, а во всех остальных случаях — истинно. Другими словами, логическое значение высказывания P  Q связано с логическими значениями высказываний Р и Q, как указано в следующей таблице, называемой таблицей истинности операции импликации:

В высказывании P Q высказывание Р называется посылкой или антецедентом, а высказывание Q— следствием или консеквентом. При определении импликации с еще большей силой встает вопрос, почему именно такое распределение принято в ее таблице истинности. Последние две строки в ней достаточно хорошо согласуются с нашим пониманием выражения «если..., то...». Их обоснованием могут служить следующие соображения. Импликация призвана отразить процесс рассуждения, умозаключения. Общая характеристика этого процесса следующая. Если мы исходим из истинной посылки и правильно (верно) рассуждаем, то мы приходим к истинному заключению (следствию, выводу). Другими словами, если мы исходили из истинной посылки и пришли к ложному выводу, значит, мы неверно рассуждали. В импликации P Q имеется посылка Р, следствие Q и процесс рассуждения . Процесс рассуждения как раз и моделируется результатом операции P Q. Приведенное соображение служит обоснованием результата 1 0  0, а также результата 11 1. Определенные сомнения возникают при оценке адекватности первых двух строк в таблице, определяющей импликацию. В первой строке при ложной посылке и ложном следствии импликация признается истинной. Следующие два примера добавляют аргументы в пользу такого определения логического значения импликации в этом случае. Рассмотрим такое высказывание: «Если число делится на 5, то и его квадрат делится на 5». Его истинность не вызывает сомнения. В частности, мы могли бы сказать: «Если 10 делится на 5, то 102 делится на 5» или «Если 11 делится на 5, то и 112 делится на 5». В первом из этих высказываний и посылка, и следствие истинны, во втором — и посылка, и следствие ложны. Тем не менее оба этих высказывания истинны. Для большей убедительности второе высказывание можно сформулировать в сослагательной форме: «Если бы 11 делилось на 5, то и 112 делилось бы на 5». Есть утверждения такого типа и в житейской речи, которые признаются вполне нормальными. Например, «Если ты можешь переплыть Черное море, то я — турецкий султан». В пользу второй строки таблицы, когда импликация остается истинной при ложной посылке и истинном следствии, говорит такой пример. Высказывание «Если первое слагаемое делится на 5 и второе слагаемое делится на 5, то и сумма делится на 5», несомненно, истинно. Но, в частности, мы могли бы сказать: «Если 10 делится на 5 и 20 делится на 5, то 30 делится на 5» или «Если 12 делится на 5 и 13 делится на 5, то 25 делится на 5». В первом из этих высказываний и посылка истинна (как конъюнкция двух истинных выражений), и следствие истинно. Во втором же высказывании посылка ложна (как конъюнкция двух ложных высказываний), а следствие истинно. Тем не менее, как мы уже отметили, оба этих высказывания признаются истинными.

Эквивалентность двух высказываний. Определение 1.9. Эквивалентностью двух высказываний Р и Q называется новое высказывание, обозначаемое P  Q (читается: «Р эквивалентно Q», или «Р необходимо и достаточно для Q», или «Р тогда и только тогда, когда Q», или «Р, если и только если Q»), которое истинно в том и только в том случае, когда одновременно оба высказывания Р и Q либо истинны, либо ложны, а во всех остальных случаях — ложно. Другими словами, логическое значение высказывания P  Q связано с логическими значениями высказываний Р и Q, как указано в следующей таблице, называемой таблицей истинности операции эквивалентности:

Общий взгляд на логические операции.Еще раз отметим, что только логические значения или значения истинности, а не их содержание интересуют нас в развиваемой теории. Поэтому каждое из введенных определений (1.1, 1.3, 1.5, 1.7, 1.9) операций над высказываниями можно рассматривать как определение некоторого действия над символами 0 и 1, т.е. как определение некоторой операции на двухэлементном множестве {0,1}. Учитывая два правила действия с символами 0 и 1, определяемые отрицанием, можно записать равенство для вычисления логического значения высказывания Р:

(1.1)

Указанные четыре правила действия с символами 0 и 1, определяемые конъюнкцией, позволяют записать равенство для вычисления логического значения высказывания P  Q :

(1.2)

Аналогично, правила действия с символами 0 и 1, сформулированные в определениях 1.5, 1.7, 1.9, дают возможность записать равенства для вычисления логических значений высказываний P  Q , P Q и P  Q соответственно:

1.3)

(1.4)

(1.5)

Равенства (1.2)… (1.5) можно записать в виде одного соотношения:

, где значок «*» обозначает один из символов

логических операций
35. Формулы алгебры высказываний. Их классификация.

Понятие формулы алгебры высказываний. В формулу вместо переменных X, Y, Z можно подставлять конкретные высказывания, после чего вся формула будет превращаться в некоторое составное высказывание. Переменные, вместо которых можно подставлять высказывания, т.е. переменные, пробегающие множество высказываний, называют пропозициональными переменными, или высказывательными переменными, или переменными высказываниями. Будем обозначать пропозициональные переменные заглавными буквами латинского алфавита Р, Q, R, S, X, Y, Z. Теперь дадим точное определение формулы алгебры высказываний.

Определение 2.1

1.Каждая отдельно взятая пропозициональная переменная есть формула алгебры высказываний.

2.Если F1и F2 — формулы алгебры высказываний, то выражения также являются формулами алгебры высказываний.

3.Никаких других формул алгебры высказываний, кроме получающихся согласно п.1 и 2, нет.

Определения такого типа называются индуктивными. В них имеются прямые пункты (в данном случае п. 1 и п. 2), где задаются объекты, которые в дальнейшем именуются определяемым термином (в данном случае — формулами алгебры высказываний), и косвенный пункт (в данном случае п. 3), в котором говорится, что такие объекты исчерпываются объектами, заданными в прямых пунктах. Среди прямых пунктов имеются базисные пункты (в данном случае п. 1), где указываются некоторые конкретные объекты, именуемые в дальнейшем определяемым термином, и индуктивные пункты (в данном случае п. 2), где даются правила получения определяемых объектов, в частности из объектов, перечисленных в базисных пунктах. В настоящей главе формулы алгебры высказываний будем называть просто формулами. Есть и другие названия для понятия формулы: правильно построенная формула или правильно построенное выражение, но они представляются менее предпочтительными. Само определение формулы, носящее индуктивный характер, на первых порах кажется непривычным. Определения такого типа вам ранее не встречались. Лучшее понимание этого определения наступит, когда вы научитесь применять его для определения того, является или не является формулой последовательность символов (слово), составленная из пропозициональных переменных, символов логических операций и скобок.

К этому полезно добавить следующее. Для каждой формулы должна существовать конечная последовательность всех ее подформул, т.е. такая конечная последовательность, которая начинается с входящих в данную формулу пропозициональных переменных, заканчивается самой этой формулой, и каждый член этой последовательности, не являющийся пропозициональной переменной, есть либо отрицание уже имеющегося члена этой последовательности, либо получается из двух уже имеющихся членов этой последовательности их соединением с помощью одного из знаков заключением полученного выражения в скобки. Такую последовательность всех подформул данной формулы иногда называют порождающей последовательностью для данной формулы. Наличие такой последовательности у логического выражения служит критерием того, что выражение является формулой. Это свойство отличает формулы.

Приведем примеры формул. На основании п.1 определения 2.1 формулами будут пропозициональные переменные: Р, Q, R, X, У, Z. Далее на основании п. 2 того же определения из этих формул построим следующие:

Из построенных формул также на основании п.2 строим еще более сложные формулы:

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

То, что последнее выражение не является формулой, может сначала вызвать недоумение. Но после сопоставления его с п.2 определения 2.1 отмечаем, что в последнем выражении недостает внешних скобок для того, чтобы считать его формулой. Действительно, если бы мы сочли данное выражение формулой, то на основании п.2 формулой было бы и выражение Но оно бессмысленно, потому что неопределенно: неизвестно, какую операцию нужно выполнять первой, импликацию или эквивалентность. А от этого, как можно проверить (проверьте!), будет зависеть логическое значение составного высказывания (см. п.3), получающегося из последнего выражения, если его превратить в формулу указанием последовательности действий и придать пропозициональным переменным X, У и Z конкретные значения (высказывания). Если бы в исходном выражении стояли внешние скобки, т.е. если бы оно было формулой то проделанное в предыдущем абзаце построение привело бы к формуле .

Итак, требование внешних скобок у формулы не является излишним формализмом. Тем не менее внешние скобки придают формуле громоздкость и, если данная формула не входит составной частью в более сложную формулу, не несут никакой информации и смысловой нагрузки. Поэтому внешние скобки в окончательно записанной формуле договариваются опускать. Но если данная формула должна будет войти составной частью в более сложную формулу, то сначала заключаем ее во внешние скобки и только потом отправляем в процедуру построения новой формулы.

Логическое значение составного высказывания. Если в формулу алгебры высказываний вместо пропозициональных переменных X1,..., Xn подставить конкретные высказывания A1,..., An соответственно, то получится некоторое новое составное высказывание . Оно называется конкретизацией формулы на выборе высказываний A1,..., An.

Теорема 2.2. Логическое значение составного высказывания равно значению формулы на наборе логических значений составляющих высказываний A1,..., An, т.е.

Итак, здесь необходимо понять, что логическое значение составного высказывания по существу является значением некоторого (логического) выражения при некотором наборе конкретных значений всех входящих в него (пропозициональных) переменных. При этом пропозициональные переменные могут принимать значения 0 или 1, само выражение принимает значение 0 или 1, и вычисляется это значение (в силу теоремы 2.2) посредством применения к значениям 0 и 1 предписываемых данным выражением логических действий. Логические действия над величинами 0 и 1 выполняются по правилам, определяемым таблицами истинности этих действий (операций) — отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности. Таким образом, мы фактически начинаем иметь дело с некой новой (логической) алгеброй, или алгеброй логики, которая как бы «параллельна» привычной школьной алгебре. Сравним компоненты этих двух алгебр с помощью следующей таблицы:

Составление таблиц истинности для формул. На основании теоремы 2.2 можно для данной формулы алгебры высказываний найти логические значения всех тех высказываний, в которые формула превращается при подстановке вместо всех ее пропозициональных переменных различных конкретных высказываний.

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

Практика составления довольно большого числа таблиц истинности есть наилучший способ прочно запомнить определения логических связок (отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности) и довести до автоматизма выдачу значений любой из этих операций. Это знание необходимо для решения более содержательных задач алгебры высказываний.

Классификация формул алгебры высказываний. Формулы алгебры высказываний подразделяются на следующие типы: выполнимые, тавтологии, опровержимые и тождественно ложные. Формула алгебры высказываний F(X1,...,Xn) называется выполнимой, если некоторая ее конкретизация является истинным высказыванием, т.е. существуют такие конкретные высказывания A1,...,An которые, будучи подставленными в эту формулу вместо переменных X1,..., Xn, соответственно, превращают ее в истинное высказывание. Таким образом, F(X1,...,Xn) выполнима, если существуют такие конкретные высказывания A1,..., An, . Она превращается в истинное высказывание, если, например, вместо пропозициональных переменных Р, Q, R подставить ложные высказывания.

Формула F(X1,...,Xn) называется тавтологией, или тождественно истинной, если она превращается в истинное высказывание при всякой подстановке вместо переменных конкретных высказываний A1,..., An, т.е. если для любых высказываний A1,...,An. Для обозначения тавтологии используется знак, который ставится перед формулой, являющейся тавтологией. Таким образом, запись означает, что формула F(X1,...,Xn) является тавтологией.

Формула F(X1,...,Xn) называется опровержимой, если существуют такие конкретные высказывания A1,...,An, которые превращают данную формулу в ложное высказывание F(A1,...,An), т.е.. Другими словами, опровержимые формулы — это формулы, не являющиеся тавтологиями.

Наконец, формула F(X1,...,Xn) называется тождественно ложной, или противоречием, если для любых конкретных высказываний A1,...,An. Другими словами, тождественно ложные формулы — это такие формулы, которые не являются выполнимыми.
36. Равносильные формулы алгебры высказываний. Нормальные формы формул алгебры высказываний

Понятие равносильности формул. Определение 4.1. Формулы F( X1,..., Xn ) и H (X1,..., Xn)алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них пропозициональных переменных логические значения получающихся из формул F и Н высказываний совпадают. Для указания равносильности формул используют обозначение F @ H. Определение равносильности формул можно записать символически: для любых конкретных высказываний А1,..., An .

Не следует думать, что в обе формулы F, H непременно входят одни и те же переменные. Некоторые из переменных X1,..., Xn могут фактически отсутствовать в любой из них.

Выписывание в предыдущем определении в формулах F и Н одних и тех же пропозициональных переменных обусловлено стремлением сделать записи и рассуждения более краткими и лаконичными. Это замечание следует иметь в виду и далее. Для лучшего усвоения понятия равносильности формул алгоритм проверки на равносильность двух формул F(X, Y, Z) и G(X, Y, Z) можно представить в виде условной схемы (приведена в тексте). Формулы F(X, Y, Z) и G(X, Y, Z) заданы своими таблицами значений:

Признак равносильности формул.Сущность признака состоит в выявлении тесной связи между понятием равносильности формул и понятием тавтологии.

Теорема 4.2 (признак равносильности формул). Две формулы F u Н алгебры высказываний равносильны тогда и только тогда, когда формула F « H является тавтологией: F @ H Û = F « H (4.2)

Отметим, что равносильность формул — это не (логическая) операция над формулами, а отношение между формулами логики высказываний. Это означает, что если F, G — формулы, то выражение F @ G уже не является формулой алгебры высказываний; оно — утверждение о некотором взаимоотношении между формулами F и H, лишь сокращенная (символическая) запись утверждения (высказывания) «F равносильна G» об этих формулах. Это утверждение либо истинно, либо ложно, т.е. F и G либо находятся в отношении равносильности, либо нет. В приведенном далее следствии из теоремы 4.2 устанавливаются некоторые свойства этого отношения между формулами алгебры высказываний. Следствие 4.3. Отношение равносильности между формулами алгебры высказываний:

а)рефлексивно: F @ F ;

б) симметрично: если F1 @ F2 , то F2 @ F1 ;

в) транзитивно: если F1 @ F2 и F2 @ F3, то F1 @ F3

т.е. отношение равносильности является отношением эквивалентности.

Как и всякое отношение эквивалентности, отношение @ разбивает множество, на котором оно задано, на непересекающиеся классы эквивалентных элементов. В данном случае множество всех формул алгебры высказываний распадается на попарно непересекающиеся классы, в каждом из которых находятся равносильные между собой формулы. Один класс, например, образуют все тавтологии, другой — все тождественно ложные формулы; имеется и много других классов.

Лемма 4.5 (о замене). Если G (Y1,...,Ys)@ H (Y1,...,Ys), то для любой формулы алгебры высказываний F(X1,...,Xn)имеет место равносильность F(X1,...,Xi-1,G(Y1,...,Ys),Xi+1,...,Xn@ F(X1,...,Xi-1,H(Y1,...,Ys),Xi+1,...,Xn). Другими словами, если в формуле некоторую ее подформулу заменить на равносильную ей формулу, то полученная формула будет равносильна исходной.

Равносильные преобразования формул.Используя лемму о замене и приведенные в теореме 4.4 равносильности, можем от одной формулы переходить к равносильной ей формуле. Такой переход называется равносильным преобразованием исходной формулы. Равносильные преобразования формул применяются прежде всего для упрощения формул. Равносильные преобразования формул применяются также для приведения формул к специальному виду или к специальной форме (к так называемой совершенной нормальной форме), имеющей исключительно важное значение как в самой алгебре высказываний, так и в ее приложениях.

Замечание 4.7. Отметим, что если некоторая формула является тавтологией, то и всякая равносильная ей формула также является тавтологией: = F и F @ H Þ = H. Сделанное замечание позволяет обнаружить еще одну сферу применения равносильных преобразований: доказательство тождественной истинности тех или иных формул. Для этого данную формулу нужно равносильными преобразованиями свести к формуле, очевидно, являющейся тавтологией.

Понятие нормальных форм.Конъюнктивным одночленом от переменных X1,..., Xn называется конъюнкция этих переменных или их отрицаний. Здесь «или» употребляется в неисключающем смысле, т.е. в конъюнктивный одночлен может входить одновременно и переменная, и ее отрицание. Дизъюнктивным одночленом от переменных X1,..., Xn называется дизъюнкция этих переменных или их отрицаний (и здесь союз «или» употребляется в неисключающем смысле).

Дизъюнктивной нормальной формой называется дизъюнкция конъюнктивных одночленов, т.е. выражение вида K1 Ú K2 Ú… Ú Kp , где все Ki ,i =1,.., p , являются конъюнктивными одночленами (не обязательно различными). Аналогично конъюнктивной нормальной формой называется конъюнкция дизъюнктивных одночленов D1 Ù… Ù Dq , где все Dj , j =1,...,q, являются дизъюнктивными одночленами (не обязательно различными). Будем также называть дизъюнктивной (конъюнктивной) нормальной формой указанные выражения при p =1 (q =1). Нормальную форму, представляющую формулу F (T. е. равносильную F), будем называть просто нормальной формой этой формулы. Нетрудно понять, что всякая формула обладает как дизъюнктивной, так и конъюнктивной нормальными формами. В самом деле, всякую формулу можно выразить через конъюнкцию, дизъюнкцию и отрицание. Если же к исходному выражению применить свойство дистрибутивности дизъюнкции относительно конъюнкции, то его можно свести к конъюнкции дизъюнктивных одночленов (к конъюнктивной нормальной форме). Очевидно, что у данной формулы F существует неограниченно много как дизъюнктивных, так и конъюнктивных нормальных форм. Одни из них более громоздкие и сложные, другие — более простые.

Совершенные нормальные формы.Среди множества дизъюнктивных (равно как и конъюнктивных) нормальных форм, которыми обладает данная формула алгебры высказываний, существует уникальная форма: она единственна для данной формулы. Это так называемая совершенная дизъюнктивная нормальная форма (среди конъюнктивных форм — совершенная конъюнктивная нормальная форма).

Определение 5.1. Одночлен (конъюнктивный или дизъюнктивный) от переменных X1,..., X n называется совершенным, если в него от каждой пары Xi , X1, (i =1,...,n) входит только один представитель ( Xi или Xi ). Нормальная форма (дизъюнктивная или конъюнктивная) от переменных X1,..., X n называется совершенной от этих переменных, если в нее входят лишь совершенные одночлены (конъюнктивные или дизъюнктивные соответственно) от X1,..., X n .

Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами.Введем обозначение, которое будет удобно в дальнейшем:

Введем еще одно обозначение. Вместо дизъюнкции X1 Ú… Ú Xn , будем писать

Лемма 5.2. Для всякой формулы алгебры высказываний F(X1,...,Xn) справедливо разложение

Теорема 5.3 (о представлении формул алгебры высказываний совершенными дизъюнктивными нормальными формулами). Каждая не тождественно ложная формула алгебры высказываний от п аргументов имеет единственную (с точностью до перестановки дизъюнктивных членов) совершенную дизъюнктивную нормальную форму.

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

Вместо конъюнкции X1 Ù ...,Ù Xn будем писать

Лемма 5.4. Для всякой формулы F(X1,...,Xn)алгебры высказываний справедливо разложение

Подобно теореме 5.3 выводится теорема 5.5.

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