Учебное пособие: Дискретная математика
Линейность функции можно также определить с помощью следующей теоремы.
Теорема
Жегалкина. Всякая булева функция 
представима
полиномом Жегалкина, т. е. в виде 
, где в каждом наборе (i1,…, ik) все ij различны, а суммирование
ведется по некоторому множеству таких несовпадающих наборов. Представление булевой
функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых.
Полином Жегалкина называется нелинейным (линейным), если он (не) содержит произведения переменных.
Таким образом, линейность булевой функции равносильна линейности соответствующего полинома Жегалкина.
Для получения
полинома Жегалкина булевой функции, находящейся в СДНФ, используются аксиомы
булевой алгебры, аксиомы булева кольца 
и
равенства, выражающие операции 
через
операции этого булева кольца: 
и т. д.
Пример.
Определим линейность функции 
.
Имеем
Полученный полином Жегалкина является нелинейным, и, следовательно, функция f также нелинейна.
Заметим, что
если в эквивалентности 
формулы
являются различными
конституентами единицы, то их произведение 
равно
0, и тогда 
. Следовательно, для
получения полинома Жегалкина из СДНФ можно сразу заменить 
.
Отметим, что каждый класс Поста замкнут относительно операций замены переменных и суперпозиции, т. е. с помощью этих операций из функций, принадлежащих данному классу, можно получить только функции из этого же класса.
Пример.
Определим, к каким классам Поста относится булева функция 
.
Так как f (0,0)=1, а f (1,1)=0, то 
и 
. Поскольку 
, то 
. Так как f (0,0)>f (1,1), то 
. Полином Жегалкина для
функции 
имеет вид 
в силу равенства 
. Поэтому данная функция
нелинейна. Таким образом, можно составить следующую таблицу
Таблица функций
| Функция | Классы | ||||
|
Р0 |
Р1 |
S | М | L | |
| х | у | Нет | Нет | Нет | Нет | Нет |
Теорема Поста. Система F булевых функций тогда и только тогда является полной, когда для каждого из классов P0, P1, S, M, L в системе F найдется функция, не принадлежащая этому классу.
В силу
теоремы Поста функция х | у образует полную систему, т. е. с
помощью штриха Шеффера можно получить любую булеву функцию. В частности, 
.
Система булевых функций называется базисом, если она полна, а удаление любой функции из этой системы делает ее неполной.
Теорема. Каждый базис содержит, не более четырех булевых функций.
Доказательство.
Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме
Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых
не принадлежит ровно одному классу Поста. Пусть f – функция из F, не принадлежащая классу
Р0. Тогда, с одной стороны, f (0,0,…, 0)=1, а, с другой – из 
следует, что f (1,1,…, 1)=1. Это означает, что f не является
самодвойственной функцией, что противоречит предположению.
Пример. Следующие
системы булевых функций являются базисами: 
.
Таблица 7
| Обоснование | Базис |
|
следовательно, |
{И, НЕ} – конъюнктивный базис |
|
следовательно, |
{ИЛИ, НЕ} – дизъюнктивный базис |
|
|
{И, |
|
следовательно, |
– базис Шеффера |
|
следовательно, |
{ |
;
;
;
, 1} – базис Жегалкина
;
; 
;
; 
} – базис ПирсаПример.
Конъюнкции,
то есть все функции вида 
, тоже
составляют замкнутый класс. Очевидно, однако, что, например, функцию, которая
на наборе (0,0,…, 0) имеет значение 1, нельзя представить суперпозицией таких
функций. Таким образом, {И} не является базисом, следовательно, конъюнктивный
базис {И, НЕ} является минимальным.
Рассмотрим более подробно базис Жегалкина.
Алгебра Жегалкина и линейные функции
Алгебра
Жегалкина – это алгебра над множеством двух бинарных булевых функций (И, 
) и нульарной функции 1.
Легко проверить следующие соотношения в этой алгебре:
;
;
;
.
Если в произвольной формуле, включающей только функции базиса Жегалкина, раскрыть скобки, то получим бесскобочную формулу, имеющую вид суммы (по модулю два) произведений, то есть некоторый полином. Он называется полиномом Жегалкина.
Широкий набор базисов открывает большие возможности при решении задач минимизации схем устройств дискретного действия, поскольку из базисных схем с помощью суперпозиций можно составить схему, соответствующую любой булевой функции.
Контрольные вопросы и упражнения
1. Дайте определение полной системе булевых функций.
2. Перечислите классы Поста.
3. Дайте определение двойственной функции. Приведите примеры.
4. Дайте определение самодвойственной функции. Приведите примеры.
5. Постройте полином Жегалкина для функции «стрелка Пирса».
6. Сформулируйте теорему Поста.
7. Что такое базис? Приведите примеры базисов.
3.8 Методы минимизации логических функций
Наиболее употребляемая операция при минимизации функций – это операция склеивания.
AB+ ĀB=B (A+ Ā)=B.
Рассмотрим три наиболее распространенных метода минимизации.
1. Пусть будут заданы номера наборов четырех переменных, на которых логическая функция принимает единичное значение: f (2,5,6,7,10,12,13,14)=1.
Выразим эту логическую функцию в СДНФ (символ конъюнкции писать не будем):
f (0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =
.
На первом этапе минимизации исходную СДНФ можно упростить за счет использования закона склеивания, тогда получим:
.
Обращаем внимание на то, что одну и ту же конституенту (импликанту) можно склеивать с другими конституентами (импликантами) многократно, так как в логике Буля действует закон идемпотентности:
,
поэтому любую конституенту можно размножить.
На втором этапе воспользуемся таблицей Куайна (табл. 8), в соответствии с которой данный метод минимизации получил свое наименование – метод Куайна. В таблице по вертикали перечислены все полученные на первом этапе упрощения импликанты, а по горизонтали – исходные конституенты. Единица в табл. 8 стоит там, где импликанта «накрывает» конституенту. Дело в том, что конституента всегда может быть заменена импликантой или даже отдельным термом по закону поглощения:
Таблица 8
|
|
0010 | 0101 | 0110 | 0111 | 1010 | 1100 | 1101 | 1110 |
| – – 1 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 0 1 – 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 1 1 – | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| – 1 0 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 1 0 – | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 1 – 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
После заполнения таблицы Куайна у нас получилось так, что почти в каждой графе оказалось по две единицы; между тем достаточно иметь одну единицу в графе. Поэтому, по возможности, нужно исключить избыточные единицы. Выбор единиц производится из соображений минимальности числа термов (выбранные единицы затемнены). В итоге оказалось, что можно обойтись только тремя импликантами вместо шести:
.
С помощью таблиц истинности легко проверить, что полученная в МНФ функция воспроизводит все значения исходной функции. Отметим, что в общем случае решений по критерию минимума термов может быть несколько.
2. Не менее
эффективным способом минимизации логических функций является метод сочетания
индексов. Для его изложения составим табл. 9, в графах которой записаны
возможные сочетания индексов. В последней графе выписаны значения функции.
Анализ таблицы начинается слева по столбцам. Принцип исключения i, j‑кода следующий. На
пересечении i‑столбца, например, с сочетанием индексов 23, и j‑строки, например,
3‑ей, находится код 10, что соответствует импликанте 
. Следовательно, в этом
столбце везде, где встречается код 10, т. е. в строках 2, 3, 10 и 11, эти
коды исключаются, поскольку значение функции в 3‑ей строке равно нулю.
Теперь возьмем столбец с сочетанием индексов 124. Здесь во 2‑ой и 6‑ой
строках оставлены коды 010, а в 10‑ой и 14‑ой строках – код 011.
Сделано это потому, что эти коды встречаются только на строках со значением
функции, равным единице. Напротив, код 110 этого же столбца встречается как при
единичных значениях функции, так и при нулевых.
Таблица 9
| n | 1 | 2 | 3 | 4 | 12 | 13 | 14 | 23 | 24 | 34 | 123 | 124 | 134 | 234 | 1234 | y |
| 0 | 0 | 0 | 0 | 0 | 00 | 00 | 00 | 00 | 00 | 00 | 000 | 000 | 000 | 000 | 0000 | 0 |
| 1 | 1 | 0 | 0 | 0 | 10 | 10 | 10 | 00 | 00 | 00 | 100 | 100 | 100 | 000 | 1000 | 0 |
| 2 | 0 | 1 | 0 | 0 | 01 | 00 | 00 | 10 | 10 | 00 | 010 | 010 | 000 | 100 | 0100 | 1 |
| 3 | 1 | 1 | 0 | 0 | 11 | 10 | 10 | 10 | 10 | 00 | 110 | 110 | 100 | 100 | 1100 | 0 |
| 4 | 0 | 0 | 1 | 0 | 00 | 01 | 00 | 01 | 00 | 10 | 001 | 000 | 010 | 010 | 0010 | 0 |
| 5 | 1 | 0 | 1 | 0 | 10 | 11 | 10 | 01 | 00 | 10 | 101 | 100 | 110 | 010 | 1010 | 1 |
| 6 | 0 | 1 | 1 | 0 | 01 | 01 | 00 | 11 | 10 | 10 | 011 | 010 | 010 | 110 | 0110 | 1 |
| 7 | 1 | 1 | 1 | 0 | 11 | 11 | 10 | 11 | 10 | 10 | 111 | 110 | 110 | 110 | 1110 | 1 |
| 8 | 0 | 0 | 0 | 1 | 00 | 00 | 01 | 00 | 01 | 01 | 000 | 001 | 001 | 001 | 0001 | 0 |
| 9 | 1 | 0 | 0 | 1 | 10 | 10 | 11 | 00 | 01 | 01 | 100 | 101 | 101 | 001 | 1001 | 0 |
| 10 | 0 | 1 | 0 | 1 | 01 | 00 | 01 | 10 | 11 | 01 | 010 | 011 | 001 | 101 | 0101 | 1 |
| 11 | 1 | 1 | 0 | 1 | 11 | 10 | 11 | 10 | 11 | 01 | 110 | 111 | 101 | 101 | 1101 | 0 |
| 12 | 0 | 0 | 1 | 1 | 00 | 01 | 01 | 01 | 01 | 11 | 001 | 001 | 011 | 011 | 0011 | 1 |
| 13 | 1 | 0 | 1 | 1 | 10 | 11 | 11 | 01 | 01 | 11 | 101 | 101 | 111 | 011 | 1011 | 1 |
| 14 | 0 | 1 | 1 | 1 | 01 | 01 | 01 | 11 | 11 | 11 | 011 | 011 | 011 | 111 | 0111 | 1 |
| 15 | 1 | 1 | 1 | 1 | 11 | 11 | 11 | 11 | 11 | 11 | 111 | 111 | 111 | 111 | 1111 | 0 |
Итак, все коды на строках, заканчивающихся нулевыми значениями функции, исключаются автоматически. Если эти коды попадают на строки, заканчивающиеся единичным значением функции, то они также не учитываются. Остаются только те коды, которые расположены на строках с единичным значением функции (эти коды затемнены).
