Ш.И._Галиев_МЛ_и_ТА_2004

§ 8. Нормальны* формы

Известно, что в математическом анализе грели всевоамшкных [функций выделяют элементарные (основные) функции: степенные, показательные. тригонометрические и т.п Среди пропозициональных

получать более сложные.

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

Примеры элементарно сумм: А, Л-/В, AVBJ IAVC.

Примеры элементарны* произведений: h А&В, 1i&C&A&3. Легкодоказатьследующие теоремы,

Теорема 1,7. Чтобы элементарная сумма сына тавтолагией| (общезначимой формулой), необходимо * дооаточио, чтобы в ней: содержалась хотя быодна пара слагаемых, из которых одно есть яеко-1 гора* буква, а другое-отрицание этойбуквы. I

-------------------------------------- ^-]

Теорема l.S. Для того, чтобы элементарное произведете А было противоречие™, необходимо и достаточно, чтобы в нем содержалась хотя бы одна пара множителей, из которых один ницжитель является отрицанием другого.

Дизъюнктивной нормальной формой (й.н.ф.) называется дизъ­ юнкция элементарных произведений Одно элементарное ироизведгниг тоже будем счигать д.аф. Примеры л нф.: AV~}B , Avfl&C,

Теорема /.9.	Для каждой пропорциональной формы сугцест-j
в у « т р а в	н о с и л ь н _а я	е_ й д . н .j ф

Доказательств, Ранее было покшано, чти для любой формы существует равносильная ей форма, содержащая т&ико евюки

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

Пример. Пусть задана формула 1[А*8)&С. Исключим связку s,

1 {(^=S)A{5=.i))&C,

BvA))&C.

Теперь добьемся, чтобы 1 относилась только к пропозициональным буквам:

(A&'l BvHb~A)kC.

Раскрыо скобки, получим Л&1 fl&CvS&"U&C'. Последнее и ecu, д.и.ф. Подученная д,н.ф., очевидно, равносильна следующей Л-Н.ф. Лк1 Bfi-Cv vTi&B&Cv^&U № гримера видно, 'tro д.н.ф., равносильная заданной форме, определяете* неслинствснкым образом.

П

Теорема 1.10. Для того, чтобы форма А была противоречием, необходимо и достаточно, чтобы равносильная ей д.н.ф. епдгржмя в »ажлом слагаемом xoia бы одну пару мнижителей, ю которых один - некоторая пропозициональная буква, а второй - отрицание этой бук-

Доказательство. Пусть для А равносильной ей д.н.ф. является форма

B iv B 2v...vBt(^ ^ !).

(, i0)

где В,( i< i£ it) гсть элементарное произведение.

Дюъюниш (1.10) будет противоречием тогда и только тогда, когда будет противоречием каждая В, (Is И к). & - элементарное про­ изведение и по георгмв 1.8 будет противоречием тогда и толькотогда. когда содержит хотя бы одну гару множителей, из которых один - некоторая буква, s втаоой - отрицание этой буквы. Теорема доказана.

Сиедствуе 1 1. Форма А будет выполнимой, если равносиль­ ная еЯ д.п.ф, содгржит хо1м бы одно слагаемое, в котором пет таких

множителей, что один из	их - пекпгорая пропозициональная буква, а
друюй множитель —«грицайне этой буквы.
Пропозициональная форма называется конъюнктивной нор-
мананой формой	если она представляет собой конъюнкцию
элементарных сумм. Лепс	доказать следующую теорему.
Теорема 1.11. Для каждой пропозициональной		формы
существует равносильная	Я к.н.ф. (неедииственная).
Молено сформулировать прааила дня нахождение		д.н.ф

ик.н.ф., равносильных задалной форме. Пустьзадана форма4;

1)исключить т А в е связки, кроме "1. &, v;

2)добиться, чтобы 1 относилась только к пропозициональным

буквам;

33

3)сспи раскрыть иобки по первому дистрибутивному закону, то получитсяд.н.ф.;

4)если сгруппировать выражение в скобки, пользуясь вторым дистрибутивнымзаконом, то получитсяк.н.ф.

Лепи доказатьследующуютеэрому.

Гепрема 1.12. Для того, чтобы пропозициональная ферма А I была тавтологией, необходимо и достаточно, чтобы равносильная ейI

к.н.ф. содержала в каждом множителе хотя	5ь( одну буквуВ
вместе с отрицаниемэтой »е буквы.	|

По теореме 1.!2можно выяснитьвыполнима формам или нет. Для jroro находим клф. для "Ы иесли найденная к.н.ф. - тавтология, то А не выполнима, если же найденная к.и.ф. не тавтология, то форма л выполнима.

§ 9. Совершенные нормальные формы

Совершенной дипютшвнаИ нормальной формой (с.б.н.ф.)

пропошииональиой формы A(A\,Ai....At) называется д.н.ф. згой фор­

мы, удовлетворяющаяследующим условиям:
-	нет одинаковыхслагаемых;	буквы Ai,Ai,...,A„ один
- в	кавдое слагаемое входят все
и только один раз (и только очи) с отрицаниемirHfio flei отрицании.
С.д,н.ф. для А можно построить по таблице тминноегн этой
формы. Для этого выбираем строки, где А равна И: пусть это будут
	строки	Для каждой выбранной

S	й т, строим
е	[ноиетшпуенму едннл^ы) К,}
следующим образам, если в выбранной

нек, букваAj принимает чяачение И, и вК, онавходят без отрицания, если не A;-J7, то я К, она вотдет с отрицанием. Дизыошцня попроенных произведений и

доказать, чтоэтаедн.ф.равносильна4.

Рассмотрим пример на построение ад.н.ф. Пусть форма

из аргументов. Найти г,д.н.ф, лля/1(,4,8,С).

Р еш г н не. Составим таблицу истинности.

Выберем строки, гле А принимает эначениг И, т.е. строки с номерами; 1, 2,3,5 и 8, Для первой «рока элементарное произведе­ ние нрыюгм;м«гс*в виде конъюнкции А&] В*£"1с,Я1Швторой14&1 в&С Построив таким образом Элементарные произведения для этих строк, получим : д.н.ф :

1/1&1s& lcvli&l e&cv'U&B&lcw&l fi*ltw&s& c. Второй метод нахождения е.л.н.ф, - метол раанооильиых прб-

образокпинЙ, который состоит в следующем. Для заданной формы А находии д.н.ф. (которая всегда существует) ипусть д.к.ф. равна:

D|vDjV...vD„(ma)),

гле Д(1< ййч) - элементарное лроюасдепие. Построенная д.н.ф. можетудовлетворять требуемымусловием, тогда эгос.д нф.

Ьсли в D, входит некоторая буква вместе с ее отрицанием, то А - противоречие и из д.и.ф. Д можно исключить, Если при такпн процедуре нужно спбросить все елвгаечые ге! д.н.ф., то А - противо­ речие ис.д ||,ф. не существует,

то шыенаем Г», на равнпсмпьиущ: (ДД A,i-KD.&U,).

Таким образом, добиваемся, чтобы каждое слагяемое содержала псеаргументы формыА

Если в полученной форме окажутся одинаковые слагаемые, то оставляемтолько одно из ник. Врезультате получи* с.д.н.ф.

Совершенной конъюнктивной нормальной фпрм/ift (г.кнф.)

пропспициоиппьиой формы .4(A|,^i. ,,Aa) называема к.н.ф. этой фор­ мы. удовлетворяющая следующий условиям.

-нетлдиияновых множителей;

-в каждый множитель входе] все буквы из пропозициональ­ ной формыА один и только олин раз (и только они) с сарица-

инек. либо без отрицании.

35

С.к.н,ф. для пропозиция альной формыА ожко построить но таблице истинности этой формы. Ляг этого вы ираем строки, где А-Л. Для каждойстроки, гдеА Л, строим элитен ариую ьумиу (тон- ституенту нуля) К‘ следуюн» 1 образом. Если в выбракной отроке буквам, принимает значение//, то в 1? DM иходет с отрицанием.если Ay'Л, то А, входит в С 6и отрицания ЕСопыо кии* построенных конспи}гитпула «будетс.к.н.г

Рассмотрим пример аа построенив с.к.н.ф для рассмотренной пропозициональнойформы.

Решение. Таблица истин! ости уже построена. Выберем ироки.

гдеА принимает значение Я, т.	. строки номера?*и: 4, б и7. Ди чет-
вертой строки элементарная су	ма (конегшуента нуля) лредешаляет-

ся в виде А\Р\ S v t.' для шестои в виде; ’ ЛvBv^ С, а для седьмой - ~\Av\BvC, 8 результат: получи«с.к.аф.:

(/Jv'ISv lO^l^vBvlQ&fl^vlflvQ.

Второй метод построения с.к.и.ф. - метод равносильных пре­ образований-заключается в следующем.

Для задапнин формы А находим к.н.ф, ноторая имеет вцо K^KiA &К,,, затемдобиваемся зыпо.ше11и»>етмш1ы«ус1ишив.

Если в jУ, входит некоторая буква вместе с ее отрицанием, то К, -тавтология и из к.н.ф. мкожительХ можно исключить. Если при такой процедуре нужно отбросить все мпоягигели m к.н.ф.. го А - тавтологкяис.к.н.ф, несуществует.

Если некоторый множитель к.н.ф., налример А*,, не содержит буквуА, то вводим еесогласно равносильности

Таким обриам, добииаеьая, чтобы каждый множигель и.н.ф, содержал зга гргучешы исходнойформы4

Если в некотором множителе окажутся одинаковые слагаемые, то оставляем голью одни из них F.cjih я полученной |[>орме окажется одинаковые множители, то оставляемтолько один из них. В результа­ те получим с.к|].ф.

36

§ 10. Вопросы и темы для самицроверки
1. Высказывание, логические операции 1, Д, v,	=, их опре­
деления итаблицы иститости.

2.Пропозициональные формы или формулы логики высказы­ ваний, определение, примеры. Упрощение записей пропозициональ­ ных форм.

3.Методы составления таблиц ис-шнности.

4. Тавтологии (общезначимые формулы), противоречия. Две теоремы о •тавтологиях.

I 5. Равносильность пропозициональных форм (формул логики высказываний), свойства отношения равносильности.

б. Важнейшие пары равносильных пропозициональных форм (запишите).

7 Зависимости между пропозициональными связками. Дие теоремы о выражении прошкиционпльных форм с помощью форм,

8.Закон двойственности.

9.Выполнимые пропозициональные формы. Кик моемо

выяснитьвыполнимость пропозициональной формы?

10, Элементарные суммыи произведения, нх свойства.

11.Нормальные формы(д.н.ф. и к.н.ф.), Алгоритм нахождения к.(1.ф.; единственна ли к.н.ф. длх заданнойформы?

12.Выяснение общезначимости пропозициональной формы па

к.н.ф.

13, Совершенная коиышжлшш нормальная форма (с.к.н.ф.). Алгоритмы нахождения с.к.н.ф.

37

14. Для какдай ли пропозициональной формы существуем р носильная ейс.х.н.ф- Единственнали с.к.н.ф. для заданной форты?

Еа« еы хдодак науятася тают, та смело вхабшг вво^.ае^уматенсутгатяртшл'.М’ т. тэрешайжш.

Д.Па*»

§11. Упражнения

!.Какие из следующих предложений являются аыскачьгяанш-

*) 2x2=4;

б) 2 —простоечисло; в) городПарижнажилится в Алии,

г) 3>5;
д) 3+5;
е)3зг=2;
ж)	числа вида 2М, где р - простое чикло, назовем числами
Мсрсекна;
з) остаток от деления яа 7 числи 3, возведенного в степень
123456 789, равенб,
и) является ли число		)234SS7$9>876S432J11111111111
простым?
1.	Следующие предложения являются составными высказ

ниями. Найдите их простые компоненты, т е. такие виссазыпания, которыеуже непостроены из каких-либодругих высказываний:

а) 7- простоечисло инедедичи на5;

б) число 2Ш13 - I - простое и его запись содержит более 3376

в) города СамараиКазань расположены наберегу Волги; г) слово «алгоритм», которое иногда пишут «алгорифм», проис­

ходи от имени арабскогоматематика аль-Хорезми, который в IX его-

л в распространение существовавших

|ДОв вычисления;

д) числа вида aba bob делится ни"7, ток как такое число является произведением чисел ab и ЮШ.асомвджитель 10101 кратен 7.

3. Пуоь А и В обозначаю! соответственно «Андрей - студент» и «Борис - студент». Запишите приведенные далее высказывании в символической форме, г. е. используя только обозначения для высказываний (А,й), символы V, =>,= искобки:

а) Андрей - студент и Ьориснестудеш;

б) Борис - студент, аАндрей-не студент; в) Андрей и Борис обане студенты; г) Андрей или Борис - студент;

д) либо Андрейстудент, либо Борис - гтуде!гг; е) ни Агарей, ии Борис не студенты; ж) Андрей не студент и Борис не студент;

з) неверно, что Андрей иБорис оба студенты; и) Андрей студенттогдаи толькотогда, когда Борис студент.

4. Пусть С обозначает' «Снег белый», a D - «Дааждь; два четыре». Сформулируйте словесно каждое из следующих выгга-

а) C&D;	<5)С&(~О);
B)(lQ&(]£>);	r)Cv(l £>);
д) '(C&D);	t) '(CvD);
ж.) \(lC)v(l £>)),	%)(C&(li>)5v((l0&D).

5. Составьте таблицы истинности для высказшанин:

a)(^a(1S))vB;	fiH(U>vO)&4;
в) (.44(1 B))vC;	г) Лу(МС).

6. Запишите следующие высказывания в синкопической форме, употребляя заглавные латинские буквы д.и обозначения атомарных высказываний, г. е.таких высказываний, которыеуже не построены из каких-либо других высказываний:

39

а) для того, чтобы число а бьито нечетным, достаточно, ггобыа былопростым;

б) iwm а мрочиг числи, то а' - кечегнав;

е) необходимым условием делимости числа на 4 является делимость егот»2;

г) еслиа положительно, то я* положительно; д) Игорь или шхольник, или студент, но он не студент, мичкг,

оншкольник; с) (л-1)!+1 леделится нал, еслип - непростое число;

ж) необходимым к достаточным условием делимости числа а на6шяется делкчость его на 2и 3;

з) для того, чтобы число а делилось на 6, достаточно чтобы о делилось на 36;

и) Фкоре.ши ходит а кино только в том случае, когда там пока-

?. Пусть А, В обозначают некоторые высказывания. Запишите следующие высказывания вс-иммлическойформе:

а)Л достаточнодля 5; б) В необходимодляА; а) В тогда, когдаЛ;

I1) Втолькотогда, когдftА; д)&з£нети.4; е) А лишьтогда, когдаВ,

ж)Атогда итолько тогда, когдаS; %)Атогла, KorjaJ;

я)А необходимо идостаточно для В; к)Л если S;

л)А необходимое следствие изВ; м)Лпри условии, что В; н)А влечетВ;

о) в случаев имеет место Я; п) нетолькоА, но иВ; р) какА,так и13,

40