Игошин Математическая логика и теория алгоритмов (1019110), страница 12
Текст из файла (страница 12)
Совершенные нормальные формы. Среди множества дизъюнктивных (равно как и конъюнктивных) нормальных форм, которыми обладает данная формула алгебры высказываний, существует уникальная форма: она единственна для данной формулы. Это так называемая совершенная дизъюнктивная нормальная форма (среди конъюнктивных форм — совершенная конъюнктивная нормальная форма). Определение 5.1.
Одночлен (конъюнктивный или дизъюнктивный) от переменных Хь Хъ ..., Х„называется совершенным, если в него от каждой пары Хь — Х; (! = 1, 2, ..., л) входит только один представитель (Х; или ~Х;). Нормальная форма (дизъюнктивная или конъюнктивная) от переменных Х„Хъ ..., Х„называется совершенной от этих переменных, если в нее входят лишь совершенные одночлены (конъюнктивные или дизъюнктивные соответственно) от Хь Хъ ..., Х. Приведем пример совершенной конъюнктивной нормальной формы от четырех переменных Хн Хъ Хъ Х,: (Х~ ч Х~ ч Хз ч Х4) л л( Х, - Х, ч Хз ч Х) л (Х, ч Х2 ч Хз ч Х4).
Вот несколько примеров совершенных дизъюнктивных нормальных форм: (Хл У) ч ч (- Хл У) ч (Хл —,У), (Хл Ул -У) ч ( Хл Ул -~У) ч (Хл — Ул л У) ч (Х л — У л — У) ч (Х л У л У), (Х~ л Х2 л Хз л Х4) ч (-~Х~ л л -~Х2 л Хз л Х4) ч (Х~ л Х2 л -~Хз л Х4). Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами.
Введем обозначение, которое будет удобно в дальнейшем: Х , если а=1, Х, если а = О. Легко проверить, что О = 1, О' = 0„1 = О, 1' = 1, т.е. Х" = 1 тогда и только тогда, когда Х = а, и Х' = О тогда и только тогда, когда Хи а(см. пояснения о значении формулы перед теоремой 2.2). Введем еще одно обозначение. Вместо дизьюнкции Х, ч Х~ ч ... ч ч Х„будем писать ~l,.",Хе В частности, запись ~~<, „ь,,„> Н(Х,, ..., Х„ан ...,а„) обозначает дизъюнкцию всевозможных выражений (формул) Н(Х„..., Х„, а,, ...,а„), зависящих от переменных Хь ..., Х„, когда индексы суммирования (дизъюнктирования) а„..., а„пробегают всевозможные упорядоченные наборы длины и, составленные из нУлей и единиц. НапРимеР, Х/<, а>(Х'" л Хр) = (Х~ л л Уп) ч (Ха л У') ч (Х' л Уе) ч (Х' л Р) = ( Хл У) ч ( Хл У) ч(Х л -~У) ч (Х л У).
47 Лемма 5.3. Дгя всякой 4ормуяы алгебры высказываний Г(Хь Хъ ..., Х») справедливо разложение Г(Хп Хъ ..., Х») =- ~/ (Р(ао ан ..., и») л Х,'"~ л Хт л ... л Х,',* ). (аь аъ ..., о») Д о к а з а т е л ь от в о. Возьмем произвольный набор из нулей и единиц «и «ъ ..., «„(каждое «ь где 1 < 1 < и, есть либо О, либо 1) и вычислим значения формул, стоящих в правой и левой частях доказываемой равносильности, при Х, = «о Х, = «з ° ° °, «» = «». С одной стороны„в правой части доказываемого равенства получим (» 0Хь сь2, ...
сь») л «~' л «~ л ... л «»"), (аь аъ ..., а») что представляет собой дизъюнкцию нескольких конъюнктивных одночленов. Каждый конъюнктивный одночлен характеризуется индексным набором нулей и единиц а„аъ ..., а». Если для данного конъюнктивного одночлена набор аь а,, ..., а„нулей и единиц таков, что а, ~ «о или аз ~ «и ..., или сь„е «», то согласно определению формулы Х", введенному в начале пункта, будем иметь или «'," = О, или «"2 = О, ..., или «„= О. Но тогда и весь данный конъюнктивный одночлен будет равен нулю и потому на результат дизъюнкции влияния не окажет, а значит, из числа дизъюнктивных «слагаемых» может быть безболезненно исключен. Только один конъюнктивный одночлен окажется не равным нулю — тот, что характеризуется таким набором (ан аъ ..., а»), который равен взятому в начале набору («„«ъ ..., «„), т.е.
для которого а, = «о а, = «,, ..., а» = «». Только для этого конъюнктивного одночлена будем иметь Г(ап аъ ..., а») л «;> л «'2 л ... л «'„" = Г(«о «ъ ..., «») л л «4| л «1г л л «»" = г(«ь «ъ ..., «») л 1 л 1 л ... л 1 = Г(«ь «ъ ..., «»). Таким образом, конъюнктивный одночлен, соответствующий индексному набору («„«„..., «„), равен Г(«ь «ъ ..., «„). Этому же значению равна и вся дизъюнкция, потому что, как показано выше, все остальные конъюнктивные одночлены равны нулю. С другой стороны, формула, стоящая в левой части доказываемого равенства, обратится при Х, = «и Х = «ъ ..., Х» = «„в то же самое значение Г(«ь «ъ ..., «„). Набор нулей и единиц «1, «ъ ..., «» был выбран произвольно.
Следовательно, формулы в левой и правой частях равносильности действительно равносильны. Лемма доказана. (1 Теорема 5.3 (о представлении формул алгебры высказываний совершенными дизъюнктивными нормальными формулами). Каждая не тождественно ложная формула алгебры высказываний от и аргументов имеет единственную (с точностью до перестановки дизьюнктивных членов) совершенную дизъюнктивную нормальную форму. До казател ьство.
Сувеествование. Всякая формула Г(Хп Хн ..., Х») обладает указанным в предыдущей лемме разложением. Поскольку формула Г(Хь Хъ ..., Х„) не тождественно ложна, то существуют такие наборы (аь аъ ..., а„) нулей и единиц, что Р'(аь аъ ..., а„) = 1. Наборы (ин ан ..., и„), обращающие формулу Г в нуль, будут обращать в нуль также и конъюнктивные одночлены, входящие в дизъюнкцию и соответствующие данным индексным наборам. Поэтому все такие одночлены исключим из дизьюнкции. Итак, в дизъюнкции остаются конъюнктивные одночлены, соответствующие лишь индексным наборам (а„аъ ..., а„) нулей и единиц, для которых Г(аь аъ ..., а„) = !.
Тогда разложение для формулы Гпринимает следующий вид: Г(Хь Хъ ..., Х„) га ~/ ((Г(аь аъ...,а„) л Х,"' л Х2~~ л ... л ~х )) га (аь аз, ..., а„) Г(аь аь ..., а„) = 1 — (Х,"~ лХ"2 л...лХ„" ), Г(аь аь ..., о«) = ! где дизьюнкция («суммирование») ведется по всем индексным наборам (аь аъ ..., а„) нулей и единиц, для которых Г(а„аъ ..., а„) = = 1.
Выражение, стоящее в правой части полученной равносильности, есть не что иное, как совершенная дизъюнктивная нормальная форма от переменных Х„Х, ..., Х„, потому что каждый конъюнктивный одночлен Х;~ л Х' л...л Х„, входящий в дизъюнкцию, совершенен (каждая переменная Х„Х,, ..., Х„входит в него точно один раз: либо сама, либо со знаком отрицания в зависимости от значения ее показателя степени).
Едимствекиость. Предположим, что некоторая формула Г(Хн Хъ ..., Х„) имеет два представления совершенными дизъюнктивными нормальными формами: Г(Хо Хъ ..., Х„) я К~ '«'Кт м ... н К« ', Г(Хь Х,, ..., Х„) гв К,* ~ Кз' '« ... '«К,*, где К, 1 < ! < д, и К,*, 1 < ( < г, есть совершенные конъюнктивные одночлены от переменных Хь Хъ ..., Х„. Причем, не нарушая общности, считаем, что ни один из одночленов К„К,, ..., К«не повторяется в атом наборе, потому что повторяющиеся одйочлены можно исключить ввиду идемпотентности дизъюнкции (теорема 4.4, ж). Аналогична ситуация в форме К*, ~ К2 ~~ ... ~~ К,*.
Тогда имеет место равносильность К, «Кз г ... «К,мК*, ~~ К2* „, «К,*. Пусть, например, совершенный конъюнктивйый одночлен К, имеет вид К, — = (Х, л Х 2 л ... л Х„" ). Придадим переменным Х„ Хъ ..., Х„значения а„аъ ..., а» соответственно. Тогда совершенный конъюнктивный одночлен К, примет значение 1, и, следовательно, вся совершенная дизъюнктивная нормальная форма„стоящая в левой части равносильности, станет равна единице. Тогда и правая часть данной равносильности обратится в единицу, и для набора а„аь ..., а„значений переменных одна из совершенных элементарных конъюнкций К*, например К,*, также станет равной единице.
Если К," имеет вид К,* н (Хй л Х1Н л ... л ХМ ), то доказанное означает, что аР' л аР22 л ... л а~ = 1. Последнее равенство возможно в том и только в том случае, когда ар' = 1, аа22 = 1, ..., а~" = 1, что может быть лишь тогда и только тогла, когда !3~ = аь !3з — — а2, ..., !3„= а„. Следовательно, К,* и (Х, л Х 2 л л ... л Х„), т.е. К,* = К,.
Таким образом, совершенная элементарная конъюнкция К, встречается среди совершенных элементарных конъюнкций К*„К2, ..., К„*. Тем же самым способом устанавливается, что любая из совершенных элементарных конъюнкций К„Къ ..., К встречается среди К*„К2, ..., К„*, и обратно, любая из совершенных элементарных конъюнкций К*„К2, ..., К„" встречается среди Кь Кь ..., Ке. Ввиду того что одночлены в данных наборах не повторяются, то и = г и обе части равносильности К, ч К, ч „. ч К, = К*, ч К~*ч ... ч К,* отличаются самое большее порядком членов дизъюнкции.
П Доказанная теорема — одна из важнейших в алгебре высказываний. Если вы до конца разобрали обе части доказательства (существование и единственность), то значит вы начали понимать категории и методы математической логики как математической науки. Доказательство существования состоит из двух частей: леммы и собственно теоремы. Доказательство единственности полностью содержится в теореме и не опирается на лемму.
Представление формул алгебры высказываний совершенными конъюнктивными нормальными (СКН) формами. Понятия и теоремы этого пункта носят двойственный характер по отношению к соответствующим понятиям и теоремам предыдущего пункта. Вводится следующее обозначение: Х, если !3 = 1, 1 Х, если !3 = О. Легко проверяется, что аО = 0„'0 = 1, а1 = 1, '1 = О, т.е. ВХ= 1 тогда и только тогда, когда Х~ !3; и ВХ= 0 тогда и только тогда, когда Х= !3. Вместо конъюнкции Х, л Х2 л ... л Х„будем писать л,".,Хь В частности, запись Ан, ~ > Н(Х„..., Х, !3ь ..., !3„) обозначаетдизьюнкцию всевозможных выражений (форьгул) ~(Хь " «л~ !3ь " ~ !3и) зависящих от переменных Хь ..., Х„, когда индексы произведения (конъюнктирования) )3ь ..., )3„пробегают всевозможные упорядоченные наборы длины п, составленные из нулей и единиц.
Например, Аы н(Х ч ~Х) = (Х ч '1) л (Хч ' У) л (Хч 'Г) л (Хч ч ' 1') = (Х ч )') л (Х ч -~ У) л (-1Х ч У) л ( — Хч -11'). Аналогично доказательству леммы 5.2 доказывается лемма 5.4. 50 Лемма 5.4. Для всякой формулы Г(Хь Хз, ..., Х„) алгебры высказывании справедливо разложение Р(Хп Хг ", Хи) = Л (РЩ Рз "., Рп) ч йХ, ч газ ч ... ч ЫХ„). (Р~ Р» - Р.) Подобно теореме 5.3 выводится теорема 5.5.
Теорема 5.5 (о представлении формул алгебры высказываний совершенными конъюнктивными нормальными формами). Каждая формула алгебры высказываний от и переменных, не являющаяся тавтологией, имеет единственную (с точностью до перестановки коньюнктивных членов) совершенную коньюнктивную нормальную форму. Доказательство этой теоремы можно восстановить, руководствуясь доказательством теоремы 5.3. Два способа приведения формулы алгебры высказываний к совершенной нормальной форме. Эти два способа проистекают из двух способов задания формулы алгебры высказываний: с помощью таблицы ее значений или с помошью аналитической формы записи. Если формула задана таблицей своих значений, то из доказательств теорем 5.3 и 5.5 о представлении формул совершенными нормальными формами необходимо вынести формулу (в некоем обычном понимании смысла этого термина) разложения формулы алгебры высказываний в совершенную нормальную форму.
Для случая СДН-формы эта формула имеет следуюший вид: Г(Хь ...,Х„)н ч (Х,'"' и...п Хи"), где Х'"=! 1 Х, если а=1, 1- Х, если а = О. р(а, ...,а„) =1 По сути, эта формула описывает правило (алгорииии) отыскания совершенной дизьюнктивной нормальной формы для данной формулы: нужно выбрать все те наборы значений ее переменных, на которых формула принимает значение 1; для каждого такого набора выписать совершенный коньюнктивный одночлен, принимающий значение 1 на этом наборе и только на нем; полученные совершенные коньюнктивные одночлены соединить знаками дизьюикции (см. Задачник, Мо 2.6, л).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
