Дискретная математика. Громов Ю.Ю - 25 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

25
5. БУЛЕВЫ ФУНКЦИИ. СПОСОБЫ ЗАДАНИЯ.
МИНИМИЗАЦИЯ В КЛАССЕ ДНФ
Функция f (x
1
, x
2
, ..., x
n
), значением которой может быть 0 или 1, от n
переменных, каждая из которых может принимать значения 0 или 1, на-
зывается булевой функцией от n переменных. При этом единица соответ-
ствует значению «истина», а ноль − значению «ложь».
Булеву функцию от n переменных можно задать различными спосо-
бами: таблицей, дизъюнкцией конституент, гиперкубом и перечислением
десятичных эквивалентов.
При табличном задании булевой функции f (x
1
, x
2
, ..., x
n
) строят пря-
моугольную таблицу размером (2
n
+ 1) × (n + 1), первую строку которой
заполняют идентификаторами переменных и обозначением самой функ-
ции, а оставшиеся 2
n
строки − всевозможными комбинациями значений
переменных и соответствующими значениями функции. Например, с по-
мощью табл. 2 задана одна из возможных булевых функций трёх пере-
менных.
При задании булевой функции f (x
1
, x
2
, ..., x
n
), не равной 0, дизъюнк-
цией конституент используется разложение Шеннона:
i
n
n
i
n
i
f
n
xxxxf
σ
=
=σσσ
σσσ
∨=
1
1)...,,,(
которыхна
),,...,,(
наборамвсемпо
21
&),...,,(
21
21
,
где
i
i
n
i
x
σ
=1
&
− конституента;
i
i
x
σ
− пер-
вичный терм, определяемый как
=σ
=σ
=
σ
.0при
,1при
ii
ii
i
x
x
x
i
Здесь операции дизъюнкция ∨,
конъюнкция & и отрицание опре-
делены традиционно, как показано в
табл. 3, 4 и 5.
Таблица 2
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1

Страницы