Дискретная математика. Кулаков Ю.В - 30 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

d) d)
0 0 0 0 1 1 0 0 0 0
0 0 0 1 0 1 0 0 1 0
0 0 1 0 1 1 0 1 0 0
0 0 1 1 0 1 0 1 1 0
0 1 0 0 1 1 1 0 0 1
0 1 0 1 1 1 1 0 1 1
0 1 1 0 1 1 1 1 0 0
0 1 1 1 0 1 1 1 1 0
Функция (a, b, c, d) не является самодвойственной уже хотя бы потому, что (0, 0, 0, 1) = (1, 1,
1, 0): (a, b, c, d) ∉ K
с
.
Классом K
м
монотонных булевых функций f
i
(x
1
, x
2
, ..., x
n
) называется множество булевых функций
вида
{ f
i
(x
1
, x
2
, ..., x
n
) / ,(),...,,(),...,,(
*
21
**
2
*
1
iinn
σ≥σ↔σσσ≥σσσ
),...,,(),...,,(),...,2,1
21
**
2
*
1
nini
ffni σσσ≥σσσ→= }.
Для тестирования функции (a, b, c, d) на монотонность можно проанализировать распределение
значений функции в соответствующем ей гиперкубе, представленном на рис. 16.
Если в гиперкубе булевой функции найдется хотя бы одно ребро, концам которого сопоставлены
двоичные наборы ),...,,(
**
2
*
1
n
σσσ и ),...,,(
21 n
σσσ такие, что ),...,,(),...,,(
21
**
2
*
1
nn
σσσ≥σσσ и ),...,,(
**
2
*
1
ni
f σσσ < < f
i
(σ
1
,
σ
1
, …, σ
n
), то такая функция не является монотонной. Рассматриваемая булева функция (a, b, c, d) не-
монотонная, поскольку:
(1, 0, 0, 0) ≥ (0, 0, 0, 0),
(1, 0, 0, 0) < (0, 0, 0, 0).
Приведем критерий полноты. Система S булевых функций f
i
является полной тогда и только тогда,
когда она содержит: функцию, не сохраняющую константу 0; функцию, не сохраняющую константу 1;
нелинейную функцию; несамодвойственную функцию и немонотонную функцию.
Используя этот критерий и метод Петрика, получим возможные базисы в
двузначной логике P
2
с нуль-, одно- и двуместными операциями.
Все булевы функции от двух переменных заданы табл. 12.
Таблица 12
Пере-
мен-
ные
Булевы функции
Рис
1111
1011
1101
1110
1001
1010
1100
1000
0
0
1
0
0
0
1
0
0111
0011
0101
0110
0001
0010
0100
0000
0
0
1
1
0
1
1
1

Страницы