Дискретная математика (стр. 5 из 10)
J =
.Представим, например, в виде полинома выражение вида 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.Пример. Двойственной к функции
является функция, соответствующая формуле 
, т. е. 
или 
: 
. Аналогично 
, 
.Принцип двойственности:
Если
,то
.Таким образом, функция, двойственная суперпозиции функций, есть соответствующая суперпозиция двойственных функций.
Этот принцип удобен при нахождении двойственных функций, представленных формулами, содержащими лишь конъюнкции, дизъюнкции и отрицание. В этом случае в исходной формуле конъюнкции заменяются на дизъюнкции, а дизъюнкции – на конъюнкции. Таким образом, ДНФ соответствует КНФ, КНФ – ДНФ, СДНФ – СКНФ, СКНФ – СДНФ.