Основы дискретной математики В.А. Осипова (552659), страница 11
Текст из файла (страница 11)
В силу леммы 2.4 каждая такая элементарная конъюнкция обращается в 0 на оценке < в1, в2, ..., зз >, а значит, и вся формула Е обращается в 0 на этой оценке, что и требовалось доказать. Пример 2.11. Для функции, заданной табл. 2.11, соответ- 61 2.2. Булавы функции ствующей формулой будет Таблица 2.11. 60 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ (Х1ЙХзб Хз) ~ (Х1е -.Хзй--Хз) у (--Х1ЙХзйХз)~у и (- Х1бс- Х244Хз).
Докажем единственность. Пусть Г1 и Гз — две формулы, выражающие функцию 1, находящиеся в СДНФ относительно списка < Х1, Хз, ..., Хь > и существенно различные, т. е, либо в Г1 есть элементарная конъюнкция, не содержащаяся в Гз, либо в Гз есть элементарная конъюнкция, не содержащаяся в Г1. Рассмотрим, например, первый случай. Если Х~'асХ2'Й ЙХ.4 — элементарная конъюнкция, содержащаяся в Г1, но не в Гз, то Она будет ассоциирована с оценкой < з1, зз, ..., ЗЬ >. Любая элементарная конъюнкция, содержащаяся в Гаь будет ассоциирована с некоторой другой оценкой. Поэтому на оценке < з1, зз, ..., зь > любая такая конъюнкция примет значение О, а следовательно, и вся формула Г2 примет значение О. С другой стороны, на этой оценке Х'"йХзмй йХ~," примет значение 1, а поэтому и формула Г1 примет значение 1.
Тогда Г1 и Га будут выражать собой различные булевы функции, откуда и следует единственность формулы. 3 а м е ч а н и е 2.1. Из теоремы 2.8 следует доказанное ранее (см. теорему 2.4) утверждение, что для любой не тождественно-ложной формулы А су4пествует равносильная ей формула Г в СДНФ. Однако мы доказали тогда более сильное утверждение, а именно, что 1 может быть получена из А с помощью равносильных преобразований. 3 а м е ч а н и е 2.2. Теперь легко доказать утверждение о единственности СДНФ для некоторой формулы А. В самом деле, если А выражает булеву функцию ~(Х1, Хз, ..., Хь), то и любая СДНФ для А должна (в силу равносильности) выражать собой ту же функцию. Поэтому все эти СДНФ должны совпадать с точностью до порядка элементарных конъюнкций.
Аналогично можно доказать, что булевы функции представимы формулами в СКНФ. Теорема 2.9 (вторая теорема о представлении булевой функции). Пусть |'(Х1, Х2, ..., Хь) — И-местная булева функция (й > 1), не равная тоокдественно 1. Существует такая формула Г, зависящая от списка переменных < Х1, Хз, ... ь Х > и находящаяся в СКНФ относительно этого списка, что Г выраэюает собой 2" (Х1, Х2, ..., Хь). Формула Г определена однозначно с точностью до перестановки конъюнктивных членов.
Перечислим все булевы функции от двух переменных. Та- 22 ких функций существует 22 = 16. Две функции сохраняют постоянное значение: ЯХ, У) = 0; 52(Х, У) = 1. Четыре функции существенно зависят только от одного из аргументов: 1з(Х, У) = Х; 14(Х, У) = У; 1з(Х~ У) = Х; 1е(Х, У) = У.
Следующие четыре функции принимают значение 1 точно на одной оценке; в СДНФ этих функций должна быть только одна элементарная конъюнкция: ЯХ, У) = ХасУ (оценка (1, 1)); ~з(Х, У) = ХЙУ (оценка (О, 1)); 1э(Х, У) = Хас У (оценка (1, 0)); 1'1о(Х, У) = - Хй-У (оценка (О, 0)). Последняя функция называется иногда функцией Шеффера и обозначается иногда Х~У.
Двойственными этим четырем функциям являются функции ~п(Х, У) = Х Ч У; ~12(Х, У) = Х Ъ' У = Х Э У; ,11з(Х, У) = Х у' У = У з Х; 1"14(Х, У) = . Х у' У. Все эти функции на трех оценках принимают значение 1 и только на одной оценке — значение О, а именно: на (О, 0), (1, 0), (О, 1), (1, 1) соответственно. Последняя из них называется функцией Вебба и обозначается Х о У. Наконец, имеются две функции, существенно зависящие от каждого из аргументов и принимающие на двух оценках значение 0 и на двух — значение 1: 11з(Х, У) = = (ХъсУ) у' (. Хас-У) = Х У (на оценках (1, 1), (О, О) функция принимает значение 1); ~1е(Х, У) = (- ХъсУ) Ъ' (Хъс- У) (на 2.2.
Булавы функции Таблица 2.12, 62 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ оценках (О, 1), (1, О) функция принимает значение 1). Последняя функция соответствует разделительному «или». Она называется также сложением по модулю 2 и обозначается Х + У. Как видим, рассмотренные функции попарно различны, так что наше перечисление является исчерпывающим. 2.2.2.
Полные системы булевых функций Система булевых функций (11, 1'2, ..., ~„Д называется полной, если любая булева функция может быть выражена через функции ~1, Ь, ..., Х„с помощью суперпозиций (т, е. составления сложных Функций). Определим понятие суперпозиции функций.
Пусть Х =(ИХ1 Хз " Хь)~Ь(Х1:Х2 " Хь) ". ..., У (Х„, Х„..., Хь )) конечная система булевых функций. Функция Г" называется суперпозицией ранга 1 (или элементарной суперпозицией) функций Ь, Ь, ..., г;„, если 1" может быть получена одним из следующих способов: а) переименованием некоторой переменной Х какой-нибудь функции 1;, т. е. ~ = ЯХ1, Х2, ..., Х, 1, У, Х,,1, ..., Хь,), где У может совпасть с любой переменной; б) подстановкой некоторой функции Я (1 < 1 < т) вместо какой-либо переменной Х любой из функций 11 б Хо, т.
е. 1 = 11(Х1, Х2, ..., Хг' 1, Я(Х1, Х2, ..., Хь,), Хг+1, ..., Х1ч). Суперпозиции ранга 1 образуют класс функций Х1. Класс функций, получающийся из функций класса Х' 1 суперпозиций ранга г — 1 с помощью элементарных суперпозиций, называется классом функций Л" суперпозиций ранга т. Суперпозициями функций из Ло называются функции, входящие в какой-либо из классов Л'. Несложно доказывается следующее утверждение 2.3.
Пусть система (11, Ь, .", гт) — полная и любая из функций 11, у2, ..., ~„, может быть выражена с помои1ъю суперпозиций через функции д1, д2, ..., д1. Тогда система (д1, д2, ..., д1) тоже полная. Пример 2.12. Докажем полноту следующих систем функций: а) (-, Й, М); б) 1-, Ч); в) (-, Й); г) (-, з). Полнота системы (, Й, 'у') непосредственно следует из теорем 2.8 и 2.9. Для доказательства полноты системы (, Ч) воспользуемся полнотой системы (, Й, Н) и утверждением 2.3, где в роли функций Ь, 12, уз выступают соответственно —, Й, ч, а в роли функций д1, д2 — (, г').
Тогда Г1 = д1 и Ь = Х1ЙХ2 = -(- Х1 '4 -Х2), т. е. функция 12 выражена через д1 и дг, а гз = 92. Полнота системы (, Й) доказывается аналогично предыдущему случаю с использованием равносильности Х1 Ч Х2 = ( Х1Й Х2). Для доказательства полноты системы (-, ~~ воспользуемся полнотой системы (-, ~l) и утверждением 2.3, где в роли функций ~1 и Ь выступают соответственно ., ~/, а в роли функций д1, дг — —, ~. Тогда 11 = д1,,62 = Х1'у Х2 = Х1 Э Хг.
В разделе 2.2.1 была определена функция Х+ У вЂ” сложение по модулю 2. Запишем таблицу истинности для этой функции (см. табл. 2.12). Иногда удобнее вместо символа Й писать символ или вообще опускать его, как это делается в арифметике. Тогда функцию ХЙУ можно записать как Х У или просто ХУ. Таблица истинности для этой функции также содержится в табл. 2.12. „, Рассмотрим теперь систему функций (+в з Ц. Это полная система, что следует из утверждения 2,3, полноты системы (-, ) и равносильности — Х = Х + 1. По таблицам истинности б4 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ (2.1) 4) Х (У+Я)=Х У+Х Я; 5) О+Х=Х; 6)О Х=О; 7) 1.Х = Х. Заметим, что все тождества, кроме 3) и 3'), выражают свойства, аналогичные свойствам арифметического сложения и умножения. Следовательно, в силу полноты системы (+,, 1) и тождеств 1) — 2), 1') — 2'), 4) — 7) любую булеву функцию можно представить в виде многочлена от своих переменных.
Много леном ?Кегалкина называется многочлен, являющийся суммой константы 0 и 1 и различных одночленов, в которые все переменные входят не выше чем в первой степени: Х в Хат Х в + ау Е пРичем на каждом набоРе < гп «2, ..., гь > все гу (2 = 1, 2, ..., 1с) различны, ау Е (О, 1). Воспользовавшись тождествами 3) и 3'), можно доказать, что каждая булеза функция может быть представлена многочленом Жегалкина. Поскольку число различных булевых функций от и переменных равно 22 и число различных многочленов ?Кегалкина от и переменных также равно 22, то представление булевой функции многочленом Жегалкина единственно.
Пример 2.13. Представим многочленами Жегалкина функции Х У У и Х У У У 2: Х У У = — (- ХЙ- У) = (Х + 1) (У + 1) + 1 = = ХУ+ Х+ У+ 1+ 1 = ХУ+ Х+ У; ХУУчг = ХУг+ХУ+Хг+УИ+Х+У+г. Утверждение 2.3 дает лишь достаточное условие полноты системы булевых функций, а установление критерия полноты системы булевых функций выходит за рамки этой книги.
нетрудно проверить, что выполняются тождества (часть нз них уже проверена при доказательстве основных равносильностей): 1) Х+У=У+Х; 1) Х У=У Х; 2) (Х+У)+к =Х+(У+Я); 2') (Х У).й=Х (У Я); 3) Х+ Х = 0; 3') Х Х = Х; 2.2. Булевы функции 2.2.3, Минимизация в классе дизъюнктивных нормальных форм ' При решении практических задач возникает вопрос о реализации булевой функции в виде некоторой «простойа формулы, содержащей наименьшее число высказывательных переменных. Выше было доказано, что произвольная булева функция может быть представлена формулой в дизъюнктивной и конъюнктивной нормальной форме.
Равносильными преобразованиями можно получить формулу, содержащую меньше, чем исходная, число переменных. Например: а) (Х13ъХ2) ' ' (Х1й- Хй) = ХИ б) (Х2ЙХ2) УХ1 =— Х~,. в) (Х14ъХ2) У (Х2ЙХз) = Х1й(Х2 У Хз). Заметим, что последнее преобразование выводит формулу из класса дизъюнктивных нормальных форм.
Рассмотрим задачу минимизации формулы в классе ДНФ. Дизъюнктивная нормальная форма называется з«инимальпой, если она содержит наименьшее общее число вхождений высказывательных переменных по сравнению со всеми равносильными ей дизъюнктивными нормальными формами. Следовательно, минимальную ДНФ данной формулы можно найти, перебрав конечное число равносильных ей ДНФ и выбрав среди них ту, которая содержит минимальное число переменных. Однако при большом числе переменных такой перебор практически невыполним. Существуют эффективные способы нахождения минимальной ДНФ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
