Игошин Математическая логика и теория алгоритмов (1019110), страница 13
Текст из файла (страница 13)
Для случая СКН-формы эта формула имеет вил р(Х Х)н д (НХ! ч...ч Р"Х,), где "Х=~ Х, если Р =О '1. Х, если Р = 1. Р(Рц...,Р)=О и, в свою очередь, описывает следующее правило (алгоритм) отыскания совершенной конъюиктивиой нормальной формы для данной формулы: нужно выбрать все те наборы значений ее переменных, на которых формула принимает значение О. Для каждого такого набора 51 выписать совершенный дизъюнктивный одноклен, принимающий значение О на этом наборе и только на нем. Полученные совершенньи дизъюнктивные однонлены соединить знаками конъюнкции (см. Задачник, )че 2.9, л). Пример 5.б.
Пусть, например, формула Г(Х У, У) задана следующей таблицей своих значений: Таким образом, она принимает значения 1 на следующих наборах значений своих переменных (или при следующих конкретизациях): (О, О, 0), (О, 1, 0), (О, 1, 1), (1, 0„0), (1, 1, 1). Запишем предыдущую формулу разложения в СДН-форму для случая и = 3 и применим ее в нашей ситуации: Г(Х У,У) ге 'ч' (Х л УВ лХ«) и Р(и, Р,т) =1 и (Хъ л Уъ л Уь) ч (Хъ л У~ л Уь) ч (Хъ л У' л У') ч (Х' л Уъ л лУь) ч(Х~л У1 лХ~) н( Хл Ул У)ч( — Хл Ул У) ч ч( Хл У Х) ч (Хл У ~У) ч (Хл Ул У). (5.1) Пример 5.7.
Для формулы Г(Х У, У) из предыдущего примера найдем ее СКН-форму. Для этого сначала отметим все те наборы значений переменных, на которых она принимает значение 0: (О, 0„1), (1, О, 1), (1, 1, 0). Теперь запишем формулу разложения в СКН-форму для случая и = 3 и применим ее в нашей ситуации: Г(Х, У, У) ж Л ("Х ч ЗУ ч «У) = с(а, 1),т) = 0 = (ьХ ч ъУ ч ~У) л ('Х ч ь У ч ~У) л (|Х ч ' У ч ъУ) ге и(Х ч 1' ч -~У) л(. Х ч Уч -~Х) л ( — Хч -1Уч У). (5.2) Еще раз обращаем внимание на то, что для каждой формулы алгебры высказываний СДН-форма единственна и СКН-форма единственна (если они существуют).
СДН-форма (5.1) отмечает все те наборы значений пропозициональных переменных, на которых данная формула принимает значение 1, а СКН-форма (5.2) отме- 52 чает все те наборы значений пропозициональных переменных, на которых данная формула принимает значение О. Тем не менее необходимо отчетливо осознавать, что две полученные формулы (5.1) и (5.2) равносильны. Так, формула (5.1) принимает значение О на тех и только тех наборах значений переменных, на которых принимает значение О и формула (5.2). Аналогично формула (5.2) принимает значение 1 на тех и только тех наборах значений переменных, на которых принимает значение 1 формула (5.1). Второй способ приведения формул алгебры высказываний к совершенной нормальной форме основан на равносильных преобразованиях данной формулы.
В этом случае формула должна быть задана в аналитической форме. Для приведения формулы к совершенной нормальной форме нужно сначала привести ее к дизъюнктивной (или конъюнктивной) нормальной форме. Алгоритм такого приведения подробно рассмотрен в Задачнике, М 2.1, л, 2.2, л. Затем нужно продолжить равносильные преобразования полученных нормальных форм, с тем чтобы довести их до совершенства.
Примеры приведения рассмотрены в Задачнике, )ч«2.3, л, 2.4, л. В заключение отметим, что одной из сфер применения нормальных форм является та, где требуется получить аналитическое выражение для формулы алгебры высказываний, которая задана своей таблицей значений (таблицей истинности), т.е. про которую известно, на каких наборах она принимает значение О, а на каких — 1. Примеры задач приведены в Задачнике, М 2.20, 2.27 — 2.31. й б.
Логическое следование формул Раздел алгебры высказываний, изучающий закономерности логического следования, логического умозаключения„является ее сердцевиной. Именно в этом разделе на данном уровне развития математической логики решается основная задача логики, состоящая в нахождении общих способов установления связей логических значений одних высказываний с логическими значениями других высказываний на основании исследования формальной структуры высказываний. Одно из важнейших предназначений логики состоит в том, чтобы устанавливать, что из чего следует, т.е. устанавливать структуры высказываний, связаннных отношением логического следования (часть общего назначения математики, по выражению Н.Винера, «находить порядок в хаосе, который нас окружает»). Знание этих закономерностей необходимо прежде всего самой математической науке.
С помощью таких знаний происходит доказательство математических теорем и, следовательно, развитие математики. Зто знание важно и для других наук, для систематизации научного знания вообще; да и в повседневной жизни оно служит инструментом рассуждений, обоснований и доказательств. 53 Понятие логического следствия. Когда говорят, что из одного или нескольких предложений А„Аь ..., А следует предложение В, то подразумевают следующее: всякий раз, когда окажутся истинными все предпожения А„Аь ..., А»» истинным будет и предложение В.
Вот примеры таких следований: «Если летом я устроюсь на временную работу (утверждение А), то у меня будут заработанные деньги (утверждение В)», «Если у меня будут заработанные деньги (утверждение В)„то я куплю видеомагнитофон (утверждение С)», «Если днем я не приготовлю уроки на завтра (утверждение А,), и если вечером я пойду в кино (утверждение А,), то завтра я буду не готов к занятиям (утверждение Р)». Установление справедливости приведенных суждений не относится к компетенции математической логики, а осуществляется на основе анализа их содержания и смысла. Задача математической логики (в частности, алгебры высказываний) в вопросах логического следования состоит в том, чтобы указать такие формы высказываний А„Аь ..., А, В, когда последнее высказывание непременно было бы следствием т первых, независимо от конкретного содержания всех этих высказываний.
Формы высказываний выражаются, как нам известно, формулами алгебры высказываний. Итак, теория логического следования (в рамках алгебры высказываний) должна изучать закономерности образования формул Гь Г,, ..., Г, Н, по которым первые т из них связаны с последней отношением логического следования. Вернемся к двум первым суждениям, приведенным в начале пункта: А » В и В » С. Вынесем относительно них следующее умозаключение: «Если А -» В и В » С, то А — > С». Формулировка данного суждения без использования математической символики будет, конечно, неуклюжа.
Поэтому сформулируем его так: «Если высказывание А — > В верно и высказывание  — » С верно, то верно и высказывание А — » С». Нет никаких сомнений в том, что высказанное суждение справедливо. Более того, мы осознаем его справедливость, даже не интересуясь содержанием простейших высказываний А, В и С. Значит, высказывание, имеющее форму Х вЂ” » Х, следует из двух высказываний, имеющих формы Х» Ки У-» У, независимо от того, каковы высказывания Х У и Л Перейдем теперь к точному определению понятия логического следствия и к изучению свойств этого понятия.
Определеиие б.1. Формула Н(Х„..., Х„) называется логическим следствием формул Г,(Хн ..., Х„), ..., Г (Хн ..., Х„), если формула Н(Хь ..., Х„) превращается в истинное высказывание при всякой такой подстановке вместо всех ее пропозициональных переменных Х„..., Х„конкретных высказываний, при которой в истинное высказывание превращаются все формулы Г,(Хь ..., Х), ..., Г (Хь ..., Х). То, что формула Н является логическим следствием формул У;, ..., Г, записывается так: Гь ..., Г ~ Н.
Формулы Вь ..., Г называются лосылками для логического следствия Н. 54 Таким образом, Гн ..., Г ~ Н, если для любых высказываний Аь ..., А„из ЦГ,(Ан ..., А„)) = 1, ..., Х(Г (А„„,, А„)) = 1 следует )„(Н(Аь ..., А„)) = 1. Наконец можно и так сказать о логическом следствии. Составим таблицы истинности для формул гь ..., Г, Н. Предположим, что если в какой-то строке таблицы все формулы рн „,, Г принимают значение 1, то в этой строке непременно и формула Н принимает значение 1.
Это и будет означать, что Н является логическим следствием формул Гь ..., Г„. Из сформулированного определения вытекает четкий алгоритм проверки формул на логическое следование (далее приводится в виде схемы). Рассмотрим его действие для случая, например, трех формул-посылок, зависяших от трех переменных: Г,(Х У, У), р~(Х ?; У), Г,(Х, ); 7) ~ Н(Х, У, У). Все эти формулы должны быть заданы таблицей своих значений: Алгоритм проверки грормул па логическое еледоваиие Алгоритм действует следующим образом.
Он просматривает последовательно по строкам таблицы значений формул Рн Гн Р;, Н. Если хотя бы один элемент нулевой строки а0, ~3м 10 равен О, то без просмотра значения формулы Н в этой строке (т.е. числа г0) происходит пеРеход к пРосмотРУ следУющей стРоки ан ~3н Ть Если все элементы а0, ~3м у0 нулевой строки равны 1, то просматривается значение с0 формулы Н в этой строке. При г0 -- О выдается результат: формула Нне является логическим следствием формул Гь Гн Р~.
При «0 = 1 происходит переход к просмотру следующей строки ан Вн ть И так далее. Если после просмотра последней строки а7, ~~, ун ~, должен произойти переход к просмотру следующей строки, то это означает, что определение логического следования выполнено и формула Н является логическим следствием формул Р~, Гг, Р~. Разберите действие этого алгоритма при решении конкретных задач на логическое следование (см. Задачник, № 1.36). Сопоставьте его с рассмотренным в э 4 алгоритмом проверки формул на равносильность. Пример 6.2. По таблице истинности нескольких формул попытаемся определить, какие из них следуют из каких: Рассмотрим формулы Х, У, (Х л 'г') ~ У, К Из таблицы видно, по имеется только одна строка (б-я), в которой первые три формулы принимают значение 1. В этой строке и формула — 3'также принимает значение 1.
Следовательно, Х У, (Хл 3') -+ У ~ — К Теперь рассматриваем формулы (Х л У) — ~ - У Х вЂ” > У, - (Хл 1 ). Из таблицы видно, что имеется точно пять строк, в которых первые две формулы принимают значение 1, а именно 1-я, 2-я, З-я, 4-я и 6-я. В этих строках третья формула также принимает значение 1. Следовательно, (Х л 1') -э -У, Х вЂ” ~ У ~ — (Х л У).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
