Функция называется сохраняющей нуль, если она равна нулю на нулевом наборе данных.
f(x1, x2, ..., xn) = 0 при всех xi = 0, i = 1, 2, ..., n
Функция называется сохраняющей единицу, если она равна единице на единичном наборе данных.
f(x1, x2, ..., xn) = 1 при всех xi = 1, i = 1, 2, ..., n
Функция называется самодвойственной, если она принимает противоположные значения на противоположных наборах аргументов.
Функция называется монотонной, если выполняется условие
f(x1, x2, …, xn) ³ f(x1’, x2’, …, xn’) при всех xi ³ xi’, i = 1, 2, ..., n
Замечание: если ни одно из условий xi ³ xi’ для всех i от 1 до n или xi £ xi’ для всех i от 1 до n не выполняется, то говорят, что наборы xi и xi’ несравнимы. Пусть , , . Тогда , а и , а также и будут несравнимыми.
Функция называется линейной, если ее можно представить линейным полиномом Жегалкина
,
где a0, a1, ..., an - константы, которые могут принимать значения 0 и 1.
Пример 1. Определим свойства функции логического умножения И
1. Сохраняет нуль, так как f(0, 0) = 0.
2. Сохраняет единицу, так как f(1, 1) = 1.
3. Не является самодвойственной, так как .
4. Монотонна, так как
f(1, 1) f(0, 1),
f(1, 1) f(1, 0),
f(1, 1) f(0, 0),
f(0, 1) f(0, 0),
f(1, 0) f(0, 0),
остальные наборы входных переменных несравнимы.
5. f(x1, x2) = x1x2 не является линейной, так как ее невозможно представить в виде линейного полинома Жегалкина.
Пример 2. Определить свойства логической функции, заданной таблицей
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f
0
1
0
1
0
1
0
1
f(0, 0, 0) = f(1, 0, 0)
f(0, 0, 1) = f(1, 0, 1)
f(0, 1, 0) = f(1, 1, 0)
f(0, 1, 1) = f(1, 1, 1) Þ f не зависит существенно от x1
f(0, 0, 0) = f(0, 1, 0)
f(0, 0, 1) = f(0, 1, 1)
f(1, 0, 0) = f(1, 1, 0)
f(1, 0, 1) = f(1, 1, 1) Þ f не зависит существенно от x2
f(0, 0, 0) ¹ f(0, 0, 1) Þ f существенно зависит от x3
f(0, 0, 0) = 0 Þ f сохраняет ноль
f(1, 1, 1) = 1 Þ f сохраняет единицу
f(0, 0, 0) ¹ f(1, 1, 1)
f(0, 0, 1) ¹ f(1, 1, 0)
f(0, 1, 0) ¹ f(1, 0, 1)
f(0, 1, 1) ¹ f(1, 0, 0) Þ f самодвойственна
f(1, 1, 1) > f(0, 0, 0)
f(1, 1, 0) = f(1, 0, 0)
f(1, 1, 0) = f(0, 1, 0)
f(1, 0, 1) > f(1, 0, 0)
f(1, 0, 1) = f(0, 0, 1)
f(0, 1, 1) > f(0, 1, 0)
f(0, 1, 1) = f(0, 0, 1) Þ f монотонна
Из таблицы значений функции f понятно, что f = x3. Эта запись одновременно является и полиномом Жегалкина для функции f. Данный полином – линейный (так как в нем нет слагаемых, являющихся конъюнкциями нескольких переменных), следовательно, и функция f является линейной.
Пример 3. Определить свойства логической функции, заданной таблицей
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f
1
1
0
1
0
1
0
1
f(0, 0, 0) ¹ f(1, 0, 0) Þ f существенно зависит от x
f(0, 0, 0) ¹ f(0, 1, 0) Þ f существенно зависит от y
f(0, 1, 0) ¹ f(0, 1, 1) Þ f существенно зависит от z
f(0, 0, 0) = 1 Þ f не сохраняет ноль
f(1, 1, 1) = 1 Þ f сохраняет единицу
f(0, 0, 0) = f(1, 1, 1) Þ f не является самодвойственной
f(0, 1, 0) < f(0, 0, 0) Þ f не является монотонной
Получить полином Жегалкина можно из ДСНФ функции. Чтобы упростить данный процесс, попробуем сначала минимизировать нашу функцию, например, с помощью карты Карно.
f(x, y, z) = z +`x`y = z Å`x`y Å`x`y z = z Å (x Å 1)(y Å 1) Å (x Å 1)(y Å 1)z =
= z Å xy Å x Å y Å 1 Å xyz Å xz Å yz Å z = xyz Å xy Å xz Å yz Å x Å y Å 1
Замечание:
Были использованы следующие преобразования:
a + b = a Å b Å ab
`a = a Å 1
a Å a = 0
a Å 0 = a
Полученный полином Жегалкина не является линейным, следовательно, исходная функция f – не линейная.
Контрольные вопросы
1. Если f(x1, x2, ..., xi–1, 0, xi+1, ..., xn) = f(x1, x2, ..., xi–1, 1, xi+1, ..., xn) на одном из наборов данных, можно ли сказать, что функция f не зависит существенно от xi?
2. Можно ли сказать, что функция является самодвойственной, если она принимает противоположные значения на какой-нибудь одной паре противоположных наборов?
3. Является ли истинным следующее неравенство: (1, 0, 1) ³ (0, 1, 0)?
4. Является ли следующий полином Жегалкина линейным: f(x1, x2) = x1 Å x1x2 ?
, 
, 
. Тогда 
, а 
и 
, а также 
будут несравнимыми.
,
.
f(0, 1),