Файл: Учебника по курсу Основы дискретной математики и логики.pdf

Теперь получим сокращенную ДНФ из построенной СДНФ с помощью законов склеивания.
Для более короткой записи и наглядности вместо символов переменных будем работать только с их значениями. Поскольку закон склеивания можно применять только к простым конъюнкциям, отличающимся одной переменной, склеивать можно наборы, различающиеся только одной позицией. Поэтому, выписывая единичные наборы данной булевой функции в таблицу, будем разбивать их на группы в соответствии с количеством единиц в наборах. В первую группу берем набор без единиц, во вторую – наборы с одной единицей, в третью – с двумя единицами, в четвертую – с тремя единицами, в пятую – с четырьмя единицами. Некоторые группы могут быть пустыми. Теперь для применения формулы склеивания достаточно просмотреть все возможные пары наборов, входящих в соседние группы.
В первой полосе таблицы поместим исходные единичные наборы функции. Каждый набор из первой группы проверим на возможность склеивания с каждым набором из второй группы. Затем каждый набор из второй группы проверим на возможность склеивания с каждым набором из третьей группы и т. д. Наборы, которые участвовали в склеивании, отметим крестиком. Во второй полосе таблицы поместим результаты склеивания наборов из первой полосы. Далее аналогичным образом проводим склеивание наборов из второй полосы, записывая результаты в третью полосу, и т. д. После того как процедура склеивания будет завершена, все простые импликанты, находящиеся в таблице, не будут помечены крестиком.
Выписав эти импликанты, мы получим сокращенную ДНФ.
Слайд 132
Так как склеивание проводилось максимально возможное количество раз, то некоторые импликанты могут быть излишними. Для того чтобы получить минимальную дизъюнктивную нормальную форму из сокращенной

ДНФ, будем использовать следующую таблицу, называемую матрицей
Квайна. Ее строки – это исходные единичные наборы функции, столбцы – простые импликанты. На пересечении строки и столбца ставится единица, если значение импликанты на данном наборе равно единице.
Нам необходимо выбрать минимальное количество столбцов так, чтобы они обеспечили единицу в каждой строке. Анализ начинаем с тех строк, в которых одна единица, например, с пятой строки. Выделяем эту единицу, и первая импликанта будет ядровой, затем выделяем все единицы первого столбца. Следующей берем восьмую строку, в которой также одна единица, и четвертая импликанта будет ядровой. Затем рассматриваем последнюю строку и отбираем пятую импликанту. В результате неотмеченной осталась только первая строка, в которой две единицы. Значит, можно взять любую из второй и третьей импликант. В итоге мы получаем две минимальные ДНФ.
Они имеют сложность, равную количеству символов переменных в формуле, т. е. сложность девять.
Слайд 133
Рассмотрим еще один способ получения минимальной ДНФ. Он основан на применении карт Карно́, позволяющих достаточно просто работать с большими выражениями. Карта Карно́ – графический способ минимизации переключательных булевых функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения.
Карта Карно представляет собой перестроенную соответствующим образом таблицу истинности булевой функции. Она может рассматриваться как плоская развертка n[эн]-мерного булева куба. Карты Карно́ применяются для минимизации СДНФ и СКНФ.

Карты Карно были изобретены в 1952 Эдвардом Вейчем и усовершенствованы в 1953 Морисом Карно́, физиком из «Bell Labs»[белл лебс], и были призваны помочь упростить цифровые электронные схемы.
В карту Карно наборы значений булевых переменных заносятся из таблицы истинности, при этом они упорядочиваются с помощью кода Грея.
В этом коде каждый следующий набор отличается от предыдущего только одной позицией.
Карта Карно для функции n[эн] переменных представляет собой таблицу, содержащую две в степени n[эн] ячеек. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4[четыре на четыре] виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4[четыре на четыре] являются соседними, и соответствующие им термы можно склеивать. На слайде представлены карты Карно для функций от трех, четырех и пяти переменных.
Далее будут рассмотрены примеры применения карт Карно для минимизации СДНФ для функций трех и четырех переменных.
Слайд 134
Покажем, как используются карты Карно для минимизации СДНФ для функции трех переменных.
Обратимся к примеру, представленному на слайде. Возьмем шаблон карты Карно для трех переменных и расставим в таблице значения заданной функции. Например, пересечение первой строки и первого столбца дает набор (0, 0, 0)[ноль ноль ноль], и функция на этом наборе принимает значение один.
При отыскании минимальной ДНФ задача состоит в том, чтобы покрыть все единицы прямоугольниками, размеры которых выражаются степенями

двойки. Точнее, нас интересуют прямоугольники размеров 2×2[два на два],
1×2[один на два], 1×4[один на четыре] и т. п. Итак, покрываем все единицы прямоугольниками как можно больших размеров, при этом само количество прямоугольников должно быть минимальным.
Теперь необходимо для каждого прямоугольника записать соответствующую импликанту. Начнем с прямоугольника 2×2[два на два], он объединяет две строки, в которых переменная х[икс] принимает разные значения, следовательно, в результате склейки получится конъюнкция, не содержащая х[икс]. Аналогично уходит переменная z[зет], так как в третьем и четвертом столбцах она принимает разные значения. Переменная y[игрек] в этих столбах принимает значение один, а значит, в искомую импликанту будет входить y[игрек].
Найдем импликанту для второго прямоугольника. Во втором и третьем столбцах разные значения принимает переменная y[игрек], поэтому в импликанте она отсутствует, переменная х[икс] принимает значение ноль, а значит, в импликанту переменная х[икс] войдет с отрицанием, переменная
z[зет] принимает значение один, она войдет в импликанту без отрицания.
Дизъюнкция двух построенных импликант дает минимальную ДНФ.
Слайд 135
Рассмотрим пример применения карт Карно для минимизации СДНФ для функции четырех переменных.
Обратимся к примеру, представленному на слайде. Возьмем шаблон карты Карно для четырех переменных и разместим в таблице значения функции.
Как отмечалось выше, карты Карно можно рассматривать как плоскую развертку n[эн]-мерного булева куба, поэтому первая и последняя строки считаются соседними, первый и последний столбцы также считаются соседними. Следовательно, единицы, стоящие в угловых ячейках таблицы, можно объединять в один прямоугольник.

Покроем все единицы прямоугольниками. Начнем с единиц, которые стоят в углах таблицы. Им соответствует прямоугольник размера 2×2. Для единицы, стоящей во второй строке и первом столбце, существует только одна возможность для изображения прямоугольника. Незатронутыми остались единицы в третьем столбце, их следует объединить с единицами второго столбца.
В результате у нас получилось три прямоугольника. Для каждого из них необходимо записать импликанту. Первый прямоугольник объединяет первую и четвертую строки, которые отличаются значениями переменной
x[икс], а переменная y[игрек] в этих строках принимает значение нуль.
Следовательно, в импликанту войдет y[игрек] со знаком отрицания. В то же время этот прямоугольник объединяет первый и последний столбец, которые отличаются значениями переменной z[зет], а переменная t[тэ] в этих столбцах принимает значение нуль. Значит, в импликанту войдет t[тэ] со знаком отрицания.
Второй и третий прямоугольники объединяют первую и вторую строки, которые отличаются значениями переменной y[игрек], а переменная х[икс] в этих строках принимает значение нуль. Следовательно, в импликанты запишем х[икс] под знаком отрицания. Второй прямоугольник, объединяя первый и второй столбец, во вторую импликанту дает z[зет] с отрицанием.
Анализируя третий прямоугольник, видим, что в соответствующую импликанту войдет переменная t[тэ]. Дизъюнкция полученных импликант образует минимальную ДНФ.
Слайд 136
Тема 4.4. Понятие полноты системы булевых функций.
Теорема Жегалкина. Замкнутые классы. Теорема о полноте
Система A[а] функций алгебры логики называется полной во множестве всех булевых функций, если любую функцию алгебры логики можно выразить формулой над A[а]. Другими словами, система полна, если

каждую булеву функцию можно задать формулой, в которой задействованы только функции данной системы.
С одной из таких систем мы уже знакомы. Поскольку любую булеву функцию можно выразить через операции дизъюнкции, конъюнкции и отрицания, то система, образованная этими функциями, является полной.
Приведенная лемма позволяет на основе полноты некоторой системы булевых функций доказывать полноту других систем. Для этого достаточно показать, что функции полной системы выражаются через функции второй системы.
Далее будут рассмотрены различные примеры полных систем.
Слайд 137
Рассмотрим примеры доказательств полноты систем функций.
Докажем полноту систем 1–4. Система 1 отличается от известной полной системы тем, что в ней отсутствует операция конъюнкции.
Следовательно, для доказательства полноты системы 1 достаточно показать, что конъюнкцию можно выразить через отрицание и дизъюнкцию, а для этого, как известно, используются законы де Моргана.
Аналогично для доказательства полноты системы 2 с помощью законов де Моргана выражаем дизъюнкцию через отрицание и конъюнкцию.
Для доказательства полноты системы 3 используем полную систему 2 и выражаем операции этой системы – конъюнкцию и отрицание – через операцию штрих Шеффера. Справедливость приведенных равенств следует из таблиц истинности соответствующих функций.
Для доказательства полноты системы 4 используем полную систему 2.
Поскольку в систему 4 входит конъюнкция, то остается только отрицание выразить через сумму по модулю два и единицу.

Слайд 138
Полином – это синоним слова «многочлен». Полином Жегалкина представляет собой запись булевой функции только с помощью тождественной единицы, операций конъюнкции и сложения по модулю два.
Определение полинома Жегалкина дается с помощью понятия монотонной конъюнкции. Отметим, что частным случаем монотонной конъюнкции является константа один.
Как видно из приведенного на слайде определения, полином
Жегалкина представляет собой сумму по модулю два различных монотонных конъюнкций. Частным случаем многочлена Жегалкина является константа ноль.
Поскольку система функций, содержащая конъюнкцию, сумму по модулю два и тождественную единицу, является полной, то всякая булева функция представляется в виде полинома Жегалкина. Более того, можно доказать, что такое представление единственно.
Слайд 139
Рассмотрим методы получения полинома Жегалкина для функций, заданных формулой или таблично. Для нахождения полинома Жегалкина функции, заданной формулой, нужно выразить все встречающиеся в данном выражении булевы функции через сумму по модулю два и конъюнкцию.
Затем, пользуясь свойствами функций, максимально упростить полученное выражение.
Обратимся к примеру, представленному на слайде. Исходная функция представляет собой конъюнкцию одной отрицаемой переменной и дизъюнкции. Выполним преобразования, приводящие эту формулу к полиному Жегалкина. Сначала выразим дизъюнкцию через сумму по модулю два. Затем последнее слагаемое в скобках заменим нулем, который в дальнейшем можно отбросить. Далее выразим отрицание через сумму по модулю два и единицу. Затем применим закон дистрибутивности, раскроем

скобки и приведем подобные слагаемые. Осталось еще раз применить закон дистрибутивности и получить полином Жегалкина.
Слайд 140
Если булева функция задана с помощью ее таблицы истинности, то существуют два способа построения соответствующего ей полинома
Жегалкина. Первый из них основан на использовании совершенной дизъюнктивной нормальной формы данной функции.
Для получения многочлена Жегалкина из СДНФ нужно заменить дизъюнкцию элементарных конъюнкций на сумму по модулю два. В получившемся выражении вместо каждой отрицаемой переменной надо записать сумму по модулю два этой переменной без знака отрицания и единицы. В результате указанных преобразований мы получим формулу, представленную на слайде. Сумма в ней понимается как сумма по модулю два. Суммирование осуществляется по всем наборам, на которых функция равна единице.
Приведенная здесь формула показывает, как устроен полином
Жегалкина для функции трех аргументов. Она допускает обобщение на случай любого числа переменных.
Слайд 141
Покажем на примере, как применяется приведенная формула для получения полинома Жегалкина таблично заданной функции.
Обратимся к функции, представленной на слайде. Данная функция на пяти наборах принимает значение, равное единице. Следовательно, при записи полинома Жегалкина в сумме будет пять слагаемых. В скобках к каждой переменной прибавляется отрицание ее значения в соответствующем наборе. Сначала вычисляем отрицания констант и отбрасываем нули в суммах по модулю два. Затем раскрываем скобки, используя закон дистрибутивности. Далее приводим подобные слагаемые. Если одно и то же выражение встречается в сумме четное число раз, то в результате оно

пропадает. Если же слагаемое участвует в сумме нечетное число раз, то оно остается в результирующей сумме.
Окончательно получаем многочлен Жегалкина, содержащий пять слагаемых.
Слайд 142
Второй способ получения полинома Жегалкина называется методом неопределенных коэффициентов. Для функции трех переменных существуют восемь различных монотонных конъюнкций. Каждая из них может входить или нет в полином Жегалкина данной функции. Коэффициенты полинома принимают значения нуль или единица, они показывают, входит ли соответствующая конъюнкция в полином Жегалкина данной функции. Для определения коэффициентов используем значения функции на каждом наборе значений переменных.
Возьмем первый набор 0-0-0[ноль ноль ноль], подставим в формулу функции f[эф] вместо переменных их значения, упростим и приравняем полученное выражение значению функции на этом наборе. В результате определяем значение коэффициента a
0
[а нулевое].
Проделаем аналогичную операцию для каждого набора, подставляя в получаемые выражения уже найденные коэффициенты. Восемь наборов позволяют однозначно определить восемь неизвестных коэффициентов.
Подставляя их в формулу функции f[эф], получаем окончательный ответ.
Слайд 143
Важным понятием теории булевых функций является понятие замкнутого класса. Оно определяется с помощью операции замыкания.
Пусть А[а] – произвольная система функций алгебры логики.
Замыканием множества А[а] называется совокупность всех булевых функций, которые можно задать с помощью функций данного множества.
Обозначение операции замыкания приведено на слайде.
Отметим основные свойства операции замыкания.

Суть первого свойства заключается в том, что всякое множество является частью своего замыкания.
Данное свойство вытекает непосредственно из определения операции замыкания.
Второе свойство – это свойство монотонности. Оно говорит о том, что если множество