Основы дискретной математики В.А. Осипова (552659), страница 10
Текст из файла (страница 10)
Аналогично определяется совершенная конъюнктивная нормальная форма. Пусть формула А зависит от списка переменных < Х,„Х;„... ..., Х;„>. Тогда говорят, что А находится в совершенной конъюнктивной нормальной форме (СКНФ) относительно этого списка, если формула А* находится в СДНФ относительно списка переменных < Х;„Хко ..., Х,„> или (эквивалентное определение) если выполняются следующие условия: 1) А находится в КНФ; 2) каждый конъюнктивный член А является й-членной дизъюнкцией, причем на 1-м месте (1 < 1 < Й) этой дизъюнкции обязательно стоит либо переменная Х,„либо ее отрицание — Х;,; 3) все конъюнктивные члены А попарно различны. Пример 2.10.
Формулы Х1 М. Х2Ч- Хз, (Х1 МХ2 Чхз)ьс гс(. Х1 Ч Хз М Хз)вгъ(Х1 Ч - Хз Ч вЂ” Хз) находятся в СКНФ относительно списка переменных < Х1, Хз, Хз >. Теорема 2.6. Пусть формула А зависит от списка переменных < Х;,, Х;„..., Х;, > и А не тождествепно-истинная. Тогда существует такая формула В, что А = В и В находится в СКНФ относительно списка переменнъзх < Х;,, Хз "° Хз„> ° Пусть А уже находится в КНФ. По условию А на какой-то оценке принимает значение Л.
Тогда А* на двойственной оценке принимает значение И и по теореме о СДНФ существует такая формула В1, что А* = В1 и В1 находится в СДНФ. По принципу двойственности В1 = А и В1 находится в СКНФ. Можно доказать эту теорему по аналогии с доказательством теоремы о приведении к СДНФ. При этом применяются равносильности (Х;, У - Хй М С)йо = и, (СЧ Хй)8ь(С М Х;,) э— з С и законы идемпотентности. Теорема 2.7 (о единственности СКНФ). Если В1 и Вз — совершенные конъюнктивные нормальные формы формулы А относительно списка переменных < Х;„Х;„..., Х1в >, то В1 и В2 могут отличаться только порядком своих конъюнктивных членов.
В самом деле, В1 и В2 в условиях теоремы будут СДНФ для формулы А* и могут отличаться (по теореме о единственности СДНФ) только порядком днзъюнктивных членов. Отсюда следует утверждение теоремы, СДНФ н СКНФ можно использовать для распознавания равносильности двух формул. Критерий равносильности: две формулы А1 и А2, зависящие от списка переменных < Х;„Х;„..., Х1в > и не равные тождественно Л (И), равносильны в том и только в том случае, если они приводятся к СДНФ (СКНФ), отпличающимся лишь порядком своих дизъюнктивных (конъюнктиеных) членов.
Если А1 и А2 приводятся к одной СДНФ В, то А1 = В в— е А2. С другой стороны, если А1 — — А2 и В1 — СДНФ для А1, а В2— СДНФ для А2, то В1 = А1 = Аз т. е. В1 будет СДНФ и для Аз, и в силу теоремы о единственности СДНФ В1 должна отличаться от В2 только порядком своих диз"ьюнктивных членов. Поскольку приведение формул к СДНФ (СКНФ) можно проводить автоматически путем последовательных преобразований, то критерий позволяет устанавливать равносильность, не обращаясь к определению и к оценкам. Задачи и упражнения 1. Сколькими способами можно расставить скобки в слове Х1 Э ~Х2 М Х2 Ч Хзъъхз, чтобы получилась формула? 2. Составить таблицы истинности для формул (Х, ~ —,Х2)й(-Х1 ~ Хз) (Х1 2 (Хз Э Х3)) З ((Х1 Э Х2) З (Х1 ~ ХЗ))' 3. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний; а) для того чтобы х было нечетным, достаточно, чтобы х было простым; б) если идет дождь, то дует ветер; в) если дует ветер, то идет дождь; 56 Глава 2.
ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 57 2.2. Булавы Функции г) ветер дует тогда и только тогда, когда идет дождь; д) неверно, что ветер дует тогда и только тогда, когда нет дождя; е) Таня ходит в театр только тогда, когда там показывают пьесу из современной жизни. 4. Доказать равносильности 1 — 6, 8-11 и 13 — 15. 5.
Доказать следующие равносильности: а) (А ~ В) = Ай- В; б) Аз Аь— з - А; в) (А1УВ)й(А У С)й(В1УР)й(С У Р) г— н (АйР) У (ВйС); г) Ай(А ~уС)й(В У С) э— з (АйВ) М (АйС); д) (АйВ) Ч (АйС) М (ВйР) у (СйР) = (А У Р)й(В У С); е) АЧ(- АйВ) =А1уВ. 6. Доказать тождественную истинность формул 1 — 10 (см. п. 2.1.4) и тождественную истинность следующих формул: а) (. АЗ В)З(В~А); б) (- В з — А) э ((- В з А) э В); в) (А З В) З ((С У А) Э (С У В)); г) ((АЗВ) ~А) ЭА; д). АЗ(А~В).
7. Доказать, что если А У В и ~А у'С тождественно-истинны, то и В У С тождественно-истинна. 8. Привести к ДНФ и КНФ следующие формулы: а) (Х1йХ2) ~ (~Х2йХз)~ б) -+ (Х1 У - Х2) З (Хзй. Х1)); в) (- Х1 З-~Х2) (Х2 Хз); г) ((Х, ~Х2) ~(Хз ~ -Х,)) ~(-Х2~--Хз) 9. Привести к СДНФ и СКНФ следующие формулы: а) (Х1й ХзйХз) Ч (Хгй Х1й Хз) и (Х1йХзйХз); б) (Х1йХ2) ~ ( Х1йХз); в) (- Х1 У Хз)й(Х1 З Х2); г) (- Х1 3 - Х2) (Х2 Хз); д) -(Х1 УХз)й(Х1 з Х2). 10. Пусть формула А не содержит никаких логических символов, кроме . Доказать, что А является тождественно- истинной тогда и только тогда, когда каждая переменная входит в А четное число раз.
П. Пусть формула А не содержит никаких логических символов, кроме и . Доказать, что А является тождественно- истинной тогда и только тогда, когда каждая переменная и символ ~ входят в нее четное число раз. 12. Пусть  — множество делителей числа 30, т. е. В = = (1, 2, 3, 5, 6, 10, 15, 30). Определим операцию а 0 Ь как наибольший общий делитель чисел а и Ь, операцию а П Ь как наименьшее общее кратное чисел а и Ь.
Доказать, что множество В с такими операциями 12 и П есть булева алгебра (Указание. 30 Определить а' как —, единичный элемент — 30, нулевой — 1). 2.2. Булевы функции 2.2.1. Представление булевой функции формулой логики высказываний Булевой 4ункцией 1(Х1, Х2, ..., Х„) называется произвольная и-местная функция из множества 10, Ц во множество (О, Ц. Итак, как аргументы булевой функции принимают значения из множества (О, Ц, так и сама функция принимает значения из этого же множества. Всякую булеву функцию от п переменных можно задать таблицей из 2" строк, в которой в каждой строке записывают одну из оценок списка переменных, принимающих значение 0 или 1.
Например, для и = 3 булеву функцию можно задать таблицей 2.9. 1 аллина 2 9 Так как Длина кажДого столбца равна 2", а различХ1 Х2 Хз ПХ1, Х2 Хз) ных столбцов из 0 и 1 длины 1 1 1 1(1, 1, 1) 2" имеется 22, то существу- ,О у(1 1 О) ет точно 22 различных и- местных булевых функций (или булевых функций от п переменных).
Удобно кон- 0 1 1 2 (О, 1, 1) станты 0 и 1 считать нуль- 0 1 0 1(О, 1, 0) местными булевыми функ- 0 1 у(0 О 1) циями (табл. 2.9). 0 0 0 7"(О, О, 0) Пусть истинностному зна- чению И соответствует 1, а истинностному значению Л вЂ” О. Тогда каждой формуле логики высказываний Г можно поставить в соответствие булеву функцию 1. При этом, если формуле г'1 соответствует функция 71, а фОрМуЛЕ г'2 — фуНКцИя ~2 И г'1 = — Г2, тО 2'1 = 62. 58 Глава 2.
ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 2,2, Булавы Функции Составим теперь в новых обозначениях таблицу 2.10 для булевых функций, соответствующих основным логическим операциям. Таблица 2.10. Докажем, что формулы дают нам, по сути дела, все булевы функции, а именно имеет место следующая теорема. Теорема 2.8 (первая теорема о представлении булевой функции). Пусть з'(Х1, Х2, ..., Хь) — М-местная булева функция (й > 1). Если У не равна тождественно О, тпо существует такая формула Е, зависящая отп списка переменньсх < Х1, Х2, ..., Хсс > и находящаяся в СДНФ относитаельно этого списка, что Е выражает собой функцию 1. Формула Е определена однозначно с точностью до перестановки дизъюнктивньсх членов.
Докажем сначала вспомогательное утверждение. При з = 1 под А' будем подразумевать формулу А, а при з = 0 — формулу - А. С каждой оценкой списка тсеременных < зс, в2, ..., вл > будем ассоциировать элементарную конъюнкцию Х1 ' йХ" й йХ'". ь ' Лемма 2.4. Конъюнкция Х" йХ2гй ° ° йХ„'", ассоциированная с оценкой < з1, з2, ..., зь >, обращаетпся в 1 на одной и только на одной оценке списка переменньсх < Х1, Х2, ..., Хь ), а менно на оценке < в1, в2, ..., вь >. В самом деле, на оценке < в1, в2, ..., вл ) формула Х" й йХ2'й йХ„" принимает значение 1, так как каждый ее коньюнктивный член Х," принимает значение 1.
Действительно, возможны два случая: либо вс (1 ( 1 < й) есть 1, и тогда Хс" есть Хс, либо вс есть О, и тогда Х," есть ~Хс. В каждом из этих случаев Хс" на оценке ( в1, зз, ..., вь ) принимает значение 1. С другой стороны, пусть оценка ( 11, 22, ..., 1ь > не совпадает с оценкой < в1, з2, ..., зь ). Тогда при некотором 1 (1 < ~ < й) зс ф 11. Возможны два случая: 1) зс=1,$Р=О; 2) вс=0,11=1.
В первом случае Х," есть Хс, а во втором — Х ' есть Хс. В любом случае Хс" на оценке < 11, 12, ..., ~ь > принимает значение О, а значит, и вся элементарная конъюнкция Х" ЙХ"Й . ЙХ'" принимает значение О. Лемма доказана. 1 2 тс Пусть теперь функция 1(Х1, Х2, ..., Хь) задана таблицей. Выберем из таблицы все строки, соответствующие оценкам, на которых 1 принимает значение 1 (поскольку т" ф О, то такие строки найдутся). Для оценки списка переменных в каждой выбранной строке построим ассоциированную с ней элементарную конъюнкцию и составим дизъюнкцию всех таких конъюнкций.
Полученная формула и будет искомой. Для этого нам нужно доказать следующие два утверждения: 1) если З'(в1, з2, ..., вь) = 1, то Е на оценке < в1, з2, ..., вь > принимает значение 1; 2) если т" (в1, в2, ..., зь) = О, то Г на оценке < з1, з2, ..., зл > принимает значение О. Пусть 1'(в1, з2, ..., зв) = 1. Тогда в таблице для 1 строка, соответствующая оценке ( в1, з2, ..., зь ), находится среди Ъ ест выбранных строк, а значит, элементарная конъюнкция Х' й йХ" й йХаа находится среди дизъюнктивных членов Е. В 2 ' Ь гт гг ал силу леммы 2.4 конъюнкция Х1 йХ2 й ЙХЬ принимает на оценке < з1, в2, ..., вл > значение 1, а вместе с ней и вся формула.
Пусть У(в1, в2, ..., зь) = О. Любой дизъюнктивный член Е имеет вид Хлс'йХ21'й ЙХь", причем оценка < 11, 12, ..., 1ь > каждый раз отличается от оценки < з1, з2, ..., зь >, так как строка, соответствующая оценке < з1, з2, ..., зь >, не могла быть выбранной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
