Основы дискретной математики В.А. Осипова (552659), страница 12
Текст из файла (страница 12)
Рассмотрим метод построения минимальной ДНФ на основе сокращенной ДНФ. пусть функцию у(хи хз, ..., х„) не равную тождественно нулю выражает формула Е, находящаяся в СДНФ относительно переменных Хы Х2, ..., Х„. Допустимой конъюнкцией для формулы Р(ХМ Хз, ..., Х„) называется такая элементарная конъюнкция С со списком переменных < Хы Хз, ..., Ха > такая, что С У г' = Р.
Допустимая конъюнкция называется простой, если после удаления из нее хотя бы одной переменной или отрицания переменной, оставшаяся элементарная конъюнкция перестает быть допустимой. Дизъюнкция всех простых конъюнкций для формулы Р'(Хы Хз, ..., Х„) называется сокращенной ДНФ.
Этот раздел написан Н, П. Яшиной. 3 — 2952 Осипова бб Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 2.2. Булевы функции Из определения следует, что сокращенная ДНФ для данной формулы является единственной. Покажем, что сокращенная ДНФ г1 выражает булеву функцию з (Хм Хг, ..., Х„). Из единственности представления функции формулой в СДНФ следует, что элементарная конъюнкция С, содержащая все переменные < Хм Хг, ..., Х„> является допустимой тогда и только тогда, когда она входит в СДНФ. Простой конъюнкцией может быть или сама С или конъюнкция С' из переменных и отрицаний переменных, входящих в С (быть может не всех).
В силу коммутативности конъюнкции можно представить С = С'йС". По закону поглощения С' ч (С'&Сз) = С' и, следовательно, г' = Гь Отсюда Г1 выражает функцию 1(ХИ Хг,, Х„) и называется сокращепной ДНФ для функции 1. Построение сокращенной ДНФ разбивается на следующие этапы. 1, Применим к формуле Г, находящейся в СДНФ относительно списка переменных < Хы Хг, ..., Х„> закон обобщенного расщепления; (А&В)у (Ай В) ив э (А&В)'у(А& В) у А до тех пор, пока это возможно.
Получим формулу Р = Г. 2. Применим к формуле Р закон поглощения АМ (АйВ) = А. Получим сокращенную ДНФ. Пример 2.14. Построим сокращенную ДНФ для булевой функции Х(ХИ Хг, Хз), заданной СДНФ Г = (Х1&Хг&Хз) У (Хг&Хгй Хз)Ч (Хгй- Хгй- Хз)М 'у'(- Х1йХг&Хз) у ( Хгй. ХгйХз). Последовательно применяя преобразования этапов 1 и 2, получим: Г = (Х1&Хг&Хз) 'У (Х1йХгй. Хз) М (Х1&.
Хгй. Хз)М М (. Хг&Хг&Хз) М (- Х|й. Хг&Хз)У У (Х1 &Хг) Ч (Хг&Хз) М (Хг& Хз)''У (- Х1&Хз) =— - =(Х1&Хг) Ч (Хг&Хз) Ч (Х1&'"Хз) М ( "Х1&Хз) Для построения минимальной ДНФ используем следующую теорему, которую приведем без доказательства. Теорема 2.10. Минимальная ДНФ, выраэсающая булеву функцию ~, является диззюнкцией нескольких (в частности, всех) дизвюнктивных членов сокращенной ДНФ для ~. Из этой теоремы следует, что для нахождения минимальной ДНФ, выражающей булеву функцию 1, достаточно перебрать все ДНФ, дизъюнктивные члены которых являются дизъюнктинными членами сокращенной ДНФ для ~ и выбрать среди этих ДНФ вЂ” ДНФ с наименьшим числом выскззывательных переменных.
Но такой перебор может оказаться очень трудоемким. Так, если сокращенная ДНФ для 1 содержит и дизъюнктивных членов, то всего придется перебрать 2 — 1 ь ДНФ. Для сокращения перебора воспользуемся следующей процедурой. Пусть г"(Хм Хг, ..., Х ) — булеза функция, г =— С1у 'уСг у ' уСь — сокращенная ДНФ для у, где Сз, Сг, ..., Сь— элементарные конъюнкции. Элементарная конъюнкция С; (1 < 1 < 1) называется яесократимой, если су|цествует оценка < зм зг, ..., за > списка переменных < Хп Хг, ..., Ха >, такая, что на этой оценке С;=1; Сд — — 0 при г'~ (1,2, ..., Й)~(з), газ'.
(2.2) Из условия (2.2) следует, что несократимая элементарная конъюнкция обязательно войдет в минимальную ДНФ. Тогда число вариантов перебора можно уменьшить за счет отбрасывания элементарных конъюнкций, не являющихся несократимыми. Проверку условия (2.2) легко осуществить, составив таблицу значений для булевых функций, соответствующих элементарным конъюнкциям С1 Сг ..., Сье Пример 2.15.
Определим минимальную ДНФ, выражающую булеву функцию 1 из примера 2.14. Сокращенная ДНФ имеет вид (Х1&Хг) М (Хг&Хз) М (Х1& Хз) У( Х1&Хз). Проверим для каждого дизъюнктивного члена сокращенной ДНФ выполнение условия (2.2). Для этого составим таблицу 2.3. Логика предикагов Задачи и упражнения 68 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ значений булевых функций, соответствующих элементарным конъюнкциям.
Таблица 243. Из таблицы 2.13 следует, что несократимыми элементарными конъюнкциями являются Хг3г- Хз и -Х144Хз, которые войдут в минимальную ДНФ в качестве элементарных дизъюнкций. Но 1(1, 1, 1) = 1, а значение ДНФ на оценке с 1, 1, 1 > равно О. Перебором получаем две минимальные ДНФГ (ХгйХ2) Ч (Х1&- Хз) М (- Х1ЫХз) и (Х23 Хз) У (Х,3 -Хз) ~ (-Х,3 Хз). 1. Указать формулы в СДНФ и СКНФ, выражающие следующие функции: а) ~(хы хз, хз), равную 1 тогда и только тогда, когда большинство переменных равно 1; б) 1(Хы Хз, Хз, Х4), равную 1 тогда и только тогда, когда Х1 + Хз + Хз + Х4 > 4. 2. Выразить с помощью суперпозиции: а) З через 1, +, б) 34, 'и' через З, -; в) — через О,:); г) —, й, и через ~ (здесь ~ — функция Шеффера Х~У Хй У); д) —, ги,, У через о (здесь о — функция Вебба Х о У Х»'-У).
3. Представить многочленом Жегалкина: а) Х З У; б) Х У. 4. Найти минимальную ДНФ для булевой функции ДХм Лз, Хз), которая равна 1 только на оценках с 1, 1, .1 >, < 1, О, 1 >, < О, О, 1 >, < О, О, О >. 2.3. Логика предикатов В логике высказываний сами высказывания рассматриваются как целое, истинное или ложное суждение, структура высказываний, их содержание не учитываются. В то же время мы постоянно встречаемся с такими рассуждениями, которые существенно зависят от структуры содержащихся в них предложений.
Например, в рассуждениях «Всякий друг Ивана есть друг Петра; Сидор не есть друг Петра; следовательно, Сидор не есть друг Ивана» или «Простое число два — четное; следовательно, существуют простые четные числа» корректность умозаключений основана на внутренней структуре самих предложений и на смысле слов «всякий» и «существует». Для анализа рассуждений такого типа оказывается недостаточно логики высказываний и возникает необходимость в расширении этой логической системы. Расширением логики высказываний является логика предикатов, содержащая логику высказываний в качестве своей части. 2.3.1. Предикаты, кванторы.
Формулы логики предикатов Рассмотрим предложения, зависящие от параметров, например: «л — «гетное число», «х меньше у», «х + у = и», «ив отец у», «л и у — братья» и т. п. Если х, у, и в первых трех предложениях заменить некоторыми числами, то получим определенные высказывания, которые могут быть истинными или ложными. Например: «3 — четное число», «2 меньше 5», «3+2 = 7». Последние два предложения выражают родственные отношения между членами семьи и также превращаются в определенные высказывания, истинные или ложные, при замене х и у именами членов этой семьи: «Иван — отец Петра», «Иван и Олег — братья».
Предложения такого типа называются предикатами. Точнее, пРедикатом Р(хм жз, ..., ха) называетсЯ фУнкциЯ, пеРеменные 71 70 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 2 3 Логика предикатоа которой принимают значения из некоторого множества М, а сама она принимает два значения: И (ястинное) и Л (ложное), т. е.
Р(х1, хг, ..., х„): М" — + (И, Л). Предикат от н аргументов называют н-местным предикатом. Множество М значений переменных определяется обычно математическим контекстом. Предикаты обозначаются большими буквами латинского алфавита. Иногда бывает удобно указывать число переменных у предикатов. В таких случаях у символов предикатов пишут верхний индекс, который и указывает число аргументов, напри- меР: Р" (х1, хг, ..., ха) — и-местный пРеДикат. ВысказываниЯ . Р(а) е считаются нуль-местными предикатами.
Над предикатами можно производить обычные логические операции. В результате получаются новые предикаты. Пример 2.16. 1. Пусть Р1 )(х) означает предикат «х делится на два», (1) Я (х) — предикат «х делится на три». Тогда выражение г~(1) е Р (х)ЙЯ (х) означает предикат «х делится на два и х (1)' ' (1) делится на три», т. е. определяет предикат делимости на 6. 2.
Пусть Я ) (х, у) означает предикат «х = у». Он принимает (г) значение И тогда и только тогда, когда х = у. В этом случае выражение — Б(г)(х, х) Э уг)(х, у) определяет предикат, принимающий значение И при любых х и у. Кроме операции логики высказываний будем применять еще операции связывания квантором. Квантор общности. Пусть Р(х) — некоторый предикат, принимающий значение И или Л для каждого элемента х множества М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
