Смекни!
smekni.com

Дискретная математика (стр. 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. При X12= 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.

Пример. Двойственной к функции

является функция, соответствующая формуле
, т. е.
или
:
. Аналогично
,
.

Принцип двойственности:

Если

,

то

.

Таким образом, функция, двойственная суперпозиции функций, есть соответствующая суперпозиция двойственных функций.

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