Нормальные формы для формул алгебры высказываний

Нормальные формы для формул алгебры высказываний Для каждой формулы алгебры высказываний можно указать равносильную ей формулу,  содержащую из логических связок лишь отрицание, конъюнкцию и дизъюнкцию. Для  этого нужно, используя равносильности теоремы 4.4, пункты у), ч), выразить все  имеющиеся в формуле импликации и эквивалентности через отрицание, конъюнкцию и  дизъюнкцию. Так, для формулы  содержащей логических связок  формула  конъюнкцию и дизъюнкцию возможно не одним способом, а многими. К примеру,  рассматриваемая формула равносильна также следующим формулам, содержащим из  логических связок лишь   и  . Выразить данную формулу через отрицание,   и   равносильной ей формулой, не  , будет, например,  Среди всевозможных выражений данной формулы через конъюнкцию, дизъюнкцию и  отрицание некоторые играют важную роль как в алгебре высказываний, так и в ее  приложениях. Рассмотрение таких выражений, называемых совершенными  нормальными формами, и составляет цель настоящего параграфа. Понятие нормальных форм Конъюнктивным одночленом от переменных  этих переменных или их отрицаний. Здесь "или" употребляется в неисключающем  смысле, т.е. в конъюнктивный одночлен может входить одновременно и переменная, и ее  отрицание. Приведем несколько примеров конъюнктивных одночленов:  называется конъюнкция  Дизъюнктивным одночленом от переменных  этих переменных или их отрицаний (и здесь союз "или" употребляется в неисключающем  смысле). Приведем примеры дизъюнктивных одночленов:  называется дизъюнкция Дизъюнктивной нормальной формой называется дизъюнкция конъюнктивных  одночленов, т.е. выражение вида  , где все  конъюнктивными одночленами (не обязательно различными).  Аналогично конъюнктивной нормальной формой называется конъюнкция  дизъюнктивных одночленов  , являются  дизъюнктивными одночленами (не обязательно различными). Будем также называть  дизъюнктивной (конъюнктивной) нормальной формой указанные выражения  при  , где все  . , являются Нормальную форму, представляющую формулу  называть просто нормальной формой этой формулы.  (то есть равносильную  ), будем  Нетрудно понять, что всякая формула обладает как дизъюнктивной, так и  конъюнктивной нормальными формами. В самом деле, всякую формулу можно выразить  через конъюнкцию, дизъюнкцию и отрицание. Используя законы де Моргана (теорема 4.4, пункты р) и с)) и свойство дистрибутивности конъюнкции относительно дизъюнкции  (теорема 4.4, пункт м)), можем преобразовать равносильным образом полученное  выражение к дизъюнкции конъюнктивных одночленов (к дизъюнктивной нормальной  форме). Если же к исходному выражению применить свойство дистрибутивности  дизъюнкции относительно конъюнкции (теорема 4.4, пункт н)), то его можно свести к  конъюнкции дизъюнктивных одночленов (к конъюнктивной нормальной форме). Очевидно, что у данной формулы  дизъюнктивных, так и конъюнктивных нормальных форм. Одни из них более громоздкие  и сложные, другие — более простые.  существует неограниченно много как  Здесь мы можем продолжить до некоторого момента аналогию со школьной алгеброй. В  школьной алгебре выражения типа  умножение) называются одночленами, а выражения типа  (последнее действие — сложение) называются многочленами. В алгебре логики  логическое умножение (конъюнкция) и логическое сложение (дизъюнкция) равноправны  по своим свойствам. Поэтому выражения типа  конъюнктивными одночленами, а выражения типа    одночленами. Образования из одночленов выражений типа (последнее действие в них —     — дизъюнктивными   называются        называются не многочленами, а нормальными формами. На этом аналогия заканчивается. Далее вводятся понятия совершенных нормальных форм — дизъюнктивной и  конъюнктивной. Совершенные нормальные формы Среди множества дизъюнктивных (равно как и конъюнктивных) нормальных форм,  которыми обладает данная формула алгебры высказываний, существует уникальная  форма: она единственна для данной формулы. Это так называемая совершенная  дизъюнктивная нормальная форма (среди конъюнктивных форм — совершенная  конъюнктивная нормальная форма). Определение 5.1. Одночлен (конъюнктивный или дизъюнктивный) от  переменных  пары   или  Нормальная форма (дизъюнктивная или конъюнктивная) от переменных называется совершенной от этих переменных, если в нее входят лишь совершенные  одночлены (конъюнктивные или дизъюнктивные соответственно) от  .  называется совершенным, если в него от каждой     входит только один представитель ( ).    Приведем пример совершенной конъюнктивной нормальной формы от четырех  переменных  Вот несколько примеров совершенных дизъюнктивных нормальных форм: Представление формул алгебры высказываний совершенными дизъюнктивными  нормальными (СДН) формами Введем обозначение, которое будет удобно в дальнейшем: Легко проверить, что  когда  формулы перед теоремой 2.2). , и   тогда и только тогда, когда  , т.е.   тогда и только тогда,   (см. пояснения о значении  Введем еще одно обозначение. Вместо дизъюнкции   будем  . В частности, запись  писать  дизъюнкцию всевозможных выражений (формул)  от переменных  ось  из нулей и единиц. Например,  обозначает  , зависящих  , когда индексы суммирования (дизъюнктирования)   пробегают всевозможные упорядоченные наборы длины  , составленные  Лемма 5.2. Для всякой формулы алгебры высказываний  справедливо разложение   Доказательство. Возьмем произвольный набор из нулей и единиц  , где  левой частях доказываемой равносильности, при  , есть либо 0, либо 1) и вычислим значения формул, стоящих в правой и   (каждое  . С одной стороны, в правой части доказываемого равенства получим . Если для данного конъюнктивного одночлена набор  что представляет собой дизъюнкцию нескольких конъюнктивных одночленов. Каждый  конъюнктивный одночлен характеризуется индексным набором нулей и  единиц  нулей и единиц таков, что  формулы  или  потому на результат дизъюнкции влияния не окажет, а значит, из числа дизъюнктивных  "слагаемых" может быть безболезненно исключен. Только один конъюнктивный  одночлен окажется не равным нулю — тот, что характеризуется таким  , введенному в начале пункта, будем иметь или  . Но тогда и весь данный конъюнктивный одночлен будет равен нулю и    , то согласно определению , или  , или   или набором  которого  будем иметь , который равен взятому в начале набору  , т.е. для  . Только для этого конъюнктивного одночлена  Таким образом, конъюнктивный одночлен, соответствующий индексному  набору  дизъюнкция, потому что, как показано выше, все остальные конъюнктивные одночлены  равны нулю. . Этому же значению равна и вся  , равен  С другой стороны, формула, стоящая в левой части доказываемого равенства, обратится  при  . Набор нулей  и единиц  правой частях равносильности действительно равносильны. Лемма доказана.  был выбран произвольно. Следовательно, формулы в левой и   в то же самое значение  Представление формул алгебры высказываний совершенными дизъюнктивными  нормальными формулами Теорема 5.3 (о представлении формул алгебры высказываний совершенными  дизъюнктивными нормальными формулами).Каждая не тождественно ложная  формула алгебры высказываний от п аргументов имеет единственную (с точностью  до перестановки дизъюнктивных членов) совершенную дизъюнктивную нормальную  форму. Доказательство. Существование. Всякая формула  указанным в предыдущей лемме разложением. Поскольку формула  тождественно ложна, то существуют такие наборы  что  будут обращать в нуль также и конъюнктивные одночлены, входящие в дизъюнкцию и  соответствующие данным индексным наборам. Поэтому все такие одночлены исключим  из дизъюнкции. Итак, в дизъюнкции остаются конъюнктивные одночлены,  соответствующие лишь индексным наборам  которых  вид:  нулей и единиц,   в нуль,  . Тогда разложение для формулы   нулей и единиц, для  . Наборы  , обращающие формулу   обладает   не  принимает следующий где дизъюнкция ("суммирование") ведется по всем индексным наборам  нулей и единиц, для которых  полученной равносильности, есть не что иное, как совершенная дизъюнктивная  нормальная форма от переменных  одночлен  переменная  отрицания в зависимости от значения ее показателя степени). , входящий в дизъюнкцию, совершенен (каждая   входит в него точно один раз: либо сама, либо со знаком    . Выражение, стоящее в правой части  , потому что каждый конъюнктивный  Единственность. Предположим, что некоторая формула  представления совершенными дизъюнктивными нормальными формами:  имеет два  , и  , есть совершенные конъюнктивные одночлены от  где  . Причем, не нарушая общности, считаем, что ни один из  переменных  одночленов   не повторяется в этом наборе, потому что повторяющиеся  одночлены можно исключить ввиду идемпотентности дизъюнкции (теорема 4.4, пункт  ж)). Аналогична ситуация в форме  равносильность . Тогда имеет место   имеет    ,   , например  . Придадим переменным   соответственно. Тогда совершенный конъюнктивный одночлен  Пусть, например, совершенный конъюнктивный одночлен  вид  значения  примет значение 1, и, следовательно, вся совершенная дизъюнктивная нормальная  форма, стоящая в левой части равносильности, станет равна единице. Тогда и правая  часть данной равносильности обратится в единицу, и для набора  значений переменных одна из совершенных элементарных конъюнкций  также станет равной единице. Если  что  случае, когда  когда  совершенная элементарная конъюнкция  элементарных конъюнкций  что любая из совершенных элементарных конъюнкций   встречается среди совершенных  . Тем же самым способом устанавливается,  . Последнее равенство возможно в том и только в том   имеет вид , то доказанное означает,  , что может быть лишь тогда и только тогда,  . Следовательно, , т.е.  . Таким образом,   встречается среди  конъюнкций  одночлены в данных наборах не повторяются, то   встречается среди  , и обратно, любая из совершенных элементарных  . Ввиду того что   и обе части равносильности отличаются самое большее порядком членов дизъюнкции. Доказанная теорема — одна из важнейших в алгебре высказываний. Если вы до конца  разобрали обе части доказательства (существование и единственность), то значит вы  начали понимать категории и методы математической логики как математической науки. Доказательство существования состоит из двух частей: леммы и собственно теоремы.  Доказательство единственности полностью содержится в теореме и не опирается на  лемму. Представление формул алгебры высказываний совершенными конъюнктивными  нормальными (СКН) формами Понятия и теоремы этого пункта носят двойственный характер по отношению к  соответствующим понятиям и теоремам предыдущего пункта. Вводится следующее  обозначение: Легко проверяется, что  когда  ; и   тогда и только тогда, когда  , т.е.  .  тогда и только тогда, Вместо конъюнкции   будем писать  . В частности,  запись  выражений (формул)  когда индексы произведения (конъюнктирования)  упорядоченные наборы длины  , составленные из нулей и единиц. Например,  обозначает дизъюнкцию всевозможных  , зависящих от переменных  ,   пробегают всевозможные Аналогично доказательству леммы 5.2 доказывается лемма 5.4. Лемма 5.4. Для всякой формулы  справедливо разложение  алгебры высказываний  Подобно теореме 5.3 выводится теорема 5.5. Теорема 5.5 (о представлении формул алгебры высказываний совершенными  конъюнктивными нормальными формами). Каждая формула алгебры  высказываний от п переменных, не являющаяся тавтологией, имеет единственную (с точностью до перестановки конъюнктивных членов) совершенную конъюнктивную  нормальную форму. Доказательство этой теоремы можно восстановить, руководствуясь доказательством  теоремы 5.3. Два способа приведения формулы алгебры высказываний к совершенной  нормальной форме Эти два способа проистекают из двух способов задания формулы алгебры высказываний: с помощью таблицы ее значений или с помощью аналитической формы записи. Если формула задана таблицей своих значений, то из доказательств теорем 5.3 и 5.5 о  представлении формул совершенными нормальными формами необходимо вынести  формулу (в некоем обычном понимании смысла этого термина) разложения формулы  алгебры высказываний в совершенную нормальную форму. Для случая СДН­формы эта  формула имеет следующий вид: , где По сути, эта формула описывает правило (алгоритм) отыскания совершенной  дизъюнктивной нормальной формы для данной формулы: нужно выбрать все те  наборы значений ее переменных, на которых формула принимает значение 1; для  каждого такого набора выписать совершенный конъюнктивный одночлен, принимающий  значение 1 на этом наборе и только на нем; полученные совершенные конъюнктивные  одночлены соединить знаками дизъюнкции. Для случая СКН­формы эта формула имеет  вид , где  и, в свою очередь, описывает следующее правило (алгоритм) отыскания  совершенной конъюнктивной нормальной формы для данной формулы: нужно  выбрать все те наборы значений ее переменных, на которых формула принимает  значение 0. Для каждого такого набора выписать совершенный дизъюнктивный  одночлен, принимающий значение 0 на этом наборе и только на нем. Полученные  совершенные дизъюнктивные одночлены соединить знаками конъюнкции. Пример 5.6. Пусть, например, формула  значений:  задана следующей таблицей своих  Таким образом, она принимает значения 1 на следующих наборах значений своих  переменных (или при следующих конкрети­зациях): Запишем предыдущую формулу разложения в СДН­форму для случая  ее в нашей ситуации:  и применим  (5.1) Пример 5.7. Для формулы  Для этого сначала отметим все те наборы значений переменных, на которых она   из предыдущего примера найдем ее СКН­форму. принимает значение 0:  СКН­форму для случая     и применим ее в нашей ситуации:   . Теперь запишем формулу разложения в  (5.2) Еще раз обращаем внимание на то, что для каждой формулы алгебры высказываний  СДН­форма единственна и СКН­форма единственна (если они существуют). СДН­форма (5.1) отмечает все те наборы значений пропозициональных переменных, на которых  данная формула принимает значение 1, а СКН­форма (5.2) отмечает все те наборы  значений пропозициональных переменных, на которых данная формула принимает  значение 0. Тем не менее необходимо отчетливо осознавать, что две полученные  формулы (5.1) и (5.2) равносильны. Так, формула (5.1) принимает значение 0 на тех и  только тех наборах значений переменных, на которых принимает значение 0 и формула  (5.2). Аналогично формула (5.2) принимает значение 1 на тех и только тех наборах  значений переменных, на которых принимает значение 1 формула (5.1). Второй способ приведения формул алгебры высказываний к совершенной нормальной  форме основан на равносильных преобразованиях данной формулы. В этом случае  формула должна быть задана в аналитической форме. Для приведения формулы к  совершенной нормальной форме нужно сначала привести ее к дизъюнктивной (или  конъюнктивной) нормальной форме. Затем нужно продолжить равносильные  преобразования полученных нормальных форм, с тем чтобы довести их до совершенства. В заключение отметим, что одной из сфер применения нормальных форм является та,  где требуется получить аналитическое выражение для формулы алгебры высказываний,  которая задана своей таблицей значений (таблицей истинности), т.е. про которую  известно, на каких наборах она принимает значение 0, а на каких — 1.