85576 (597811), страница 4
Текст из файла (страница 4)
Представим, например, в виде полинома выражение вида X1
X2. Для этого проведем следующие рассуждения.
Пусть
X1 X2 = aX1X2+bX1+cX2+k,
где а, b, с, k – неопределенные коэффициенты.
При X1 = X2 = 0 имеем k = 0. При Х1 = 1, X2= 0 имеем b= 1. При Х1= 0, Х2= 1 имеем с= 1. При X1=Х2= 1 имеем а + b + с = 1, т. е. а = -1. Таким образом, получаем:
X1 X2 = – X1X2+ X1+ X2.
СПНФ образуется путем замены в СДНФ: на + и 
на
1 
х.
,
,
В последнем случае выражение для 
легко можно упростить, если раскрыть скобки и взаимно сократить все одинаковые слагаемые, входящие в формулу четное число раз:
.
Подобное упрощение, которое называется минимизацией логической функции, можно осуществить и по отношению к СДНФ и СКНФ.
Таблица 6
| | | | y |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 |
Применение законов алгебры логики позволяет найти более компактные аналитические выражения для заданной функции у, т. е. минимальную дизъюнктивную нормальную форму 
. Приведем соответствующие формы представления функции у, заданной табл. 6:
,
и для СКНФ, т. е. минимальную КНФ:
.
После того, как найдены минимальные нормальные формы (МНФ), их рекомендуется проверить на всех наборах аргументов 
. Переменные или 
часто называют термами. Именно полный набор из n термов образует конституенту. В процессе же минимизации некоторые термы из конституент пропадут. Тогда оставшуюся часть дизъюнкта или конъюнкта называют импликантой.
Как мы только что убедились на примере, импликанты появляются в результате склейки смежных конституент, различающихся одним термом.
Контрольные вопросы и упражнения
1. Дайте определение логической функции многих переменных.
2. Что такое вектор значений булевой функции? Приведите пример построения таблицы истинности логической функции многих переменных.
3. Сколько существует булевых функций от n переменных?
4. Что такое ДНФ и КНФ?
5. Каков алгоритм построения СДНФ? Приведите пример построения СДНФ.
6. Каков алгоритм построения СКНФ? Приведите пример построения СКНФ.
7. Составьте СКНФ и СДНФ для функции 
.
8. Приведите пример построения СПНФ.
3.7 Некоторые замкнутые классы (классы Поста). Понятие базиса
Система булевых функций {f1, f2,…, fm} называется полной, если любая булева функция может быть выражена через функции f1, f2,…, fm с помощью суперпозиций.
Пусть К0={f1(x1,…,xk1), f2(x1,…,xk2),…, fm(x1,…,xkm)} – конечная система булевых функций. Функция f называется элементарной суперпозицией (суперпозицией ранга 1) функций f1, f2,…, fm, если f может быть получена одним из следующих способов:
а) переименованием некоторой переменной xj какой-нибудь функции fi;
б) подстановкой некоторой функции 
вместо какой-либо переменной xj любой из функций 
.
Суперпозиции ранга 1 образуют класс функций К1. Класс функций, получающийся из функций класса Ks-1 суперпозицией ранга s‑1 с помощью элементарных суперпозиций, называется классом функций Ks суперпозиций ранга s. Суперпозициями функций из К0 называются функции, входящие в какой-то из классов Ks.
Согласно введенным определениям, можно говорить, что система булевых функций полна. Тогда любую булеву функцию можно представить в виде многочлена от своих переменных.
В современном компьютере цифрами являются ноль и единица. Следовательно, команды, которые выполняет процессор, суть булевы функции. Мы уже видели, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие 
. Далее рассмотрим вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающие тем свойством, что с их помощью можно выразить все другие функции. Рассмотрим некоторые замкнутые классы (классы Поста), их пять.
1. Класс функций, сохраняющих константу нуль (обозначается T0 или P0):
T0:={f | f (0,0,…, 0)=0}.
К этому классу относятся, например, функции 
; 
; 
; 
.
2. Класс функций, сохраняющих константу единица (обозначается T1 или P1):
T1:={f | f (1,1,…, 1)=1}.
К нему относятся все нечетные функции.
3. Класс самодвойственных функций (обозначается T* или S):
T*:={f | f*};
Пример 
и 
.
Функция 
называется двойственной по отношению к функции 
, если 
. Двойственная функция получается из исходной при замене значений всех переменных, а также значений функции на противоположные, т. е. в таблице истинности нужно заменить 0 на 1, 1 на 0.
Пример. Двойственной к функции 
является функция, соответствующая формуле 
, т. е. 
или 
: 
. Аналогично 
, 
.
Принцип двойственности:
Если 
,
то 
.
Таким образом, функция, двойственная суперпозиции функций, есть соответствующая суперпозиция двойственных функций.
Этот принцип удобен при нахождении двойственных функций, представленных формулами, содержащими лишь конъюнкции, дизъюнкции и отрицание. В этом случае в исходной формуле конъюнкции заменяются на дизъюнкции, а дизъюнкции – на конъюнкции. Таким образом, ДНФ соответствует КНФ, КНФ – ДНФ, СДНФ – СКНФ, СКНФ – СДНФ.
Пример. 
,
если 
, то и 
.
Функция называется самодвойственной, если 
.
Пример. Покажем, что формула 
задает самодвойственную функцию.
Убедимся, что на всех противоположных наборах значений переменных 
и 
формула принимает противоположные значения. Действительно, составим таблицу истинности:
|
| x | y | z |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 |
Получаем 
, 
, 
, 
.
4. Класс монотонных функций (обозначается TM или M):
, где 
, 
, 
, 
.
5. Класс линейных функций (обозначается TL или L):
.
Эквивалентность является линейной функцией 
. Стрелка Пирса – нет, 
.
, 
, 
,…, 
,
т. е.
, 
,…, 
. (7)
Таким образом, проверка линейности сводится к нахождению коэффициентов 
по формулам (7) и сопоставлению таблиц истинности данной формулы 
и полученной формулы 
.
Пример. Проверим, является ли линейной функция . Имеем 
, 
, 
. Таким образом, 
. Сопоставляя таблицы истинности формул и 
, убеждаемся, что они не совпадают. Вывод: функция нелинейна.
Линейность функции можно также определить с помощью следующей теоремы.
Теорема Жегалкина. Всякая булева функция представима полиномом Жегалкина, т. е. в виде 
, где в каждом наборе (i1,…, ik) все ij различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов. Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых.
Полином Жегалкина называется нелинейным (линейным), если он (не) содержит произведения переменных.
Таким образом, линейность булевой функции равносильна линейности соответствующего полинома Жегалкина.
Для получения полинома Жегалкина булевой функции, находящейся в СДНФ, используются аксиомы булевой алгебры, аксиомы булева кольца 
и равенства, выражающие операции 
через операции этого булева кольца: 
и т. д.
Пример. Определим линейность функции 
.
Имеем
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
