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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

0 0 1 0 1 0 1 1
0 1 0 0 1 1 0 1
0 1 1 1 1 1 1 1
При задании булевой функции f (x
1
, x
2
, ..., x
n
), не равной 0, дизъюнкцией конституент используется
разложение Шеннона:
i
i
n
i
n
f
n
n
xxxxf
σ
=
=σσσ
σσσ
∨=
1
1),...,
2
,
1
(
которыхна
),,...,
2
,
1
(
наборамвсемпо
21
&),...,,(
,
где
i
i
n
i
x
σ
=1
& − конституента;
i
i
x
σ
− первичный терм, определяемый выражением
=σ
=σ
=
σ
;0при
;1при
ii
ii
i
x
x
x
i
∨ −
операция дизъюнкция; & − операция конъюнкция;
_
− операция отрицание.
Операции дизъюнкция ∨, конъюнкция & и отрицание
_
заданы
табл. 3, 4 и 5.
Таблица 3 Таблица 4 Таблица 5
x
1
x
2
x
1
∨ x
2
x
1
x
2
x
1
& x
2
x
x
0 0 0 0 0 0 0 1
0 1 1 0 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1
Приведем основные законы, которым удовлетворяют заданные операции:
− идемпотентности дизъюнкции и конъюнкции
a ∨ a = a, a & a = a;
− коммутативности дизъюнкции и конъюнкции
a ∨ b = b ∨ a, a & b = b & a;
− ассоциативности дизъюнкции и конъюнкции
a ∨ (b ∨ c) = (a ∨ b) ∨ c, a & (b & c) = (a & b) & c;
− дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъ-
юнкции
a & (b ∨ c) = a & b ∨ a & c, a ∨ (b & c) = (a ∨ b) & (a ∨ c);
− двойного отрицания
aa = ;
− де-Моргана
baba &=∨ , baba ∨=& ;
− склеивания
ababa =∨ && ,
ababa =∨∨ )(&)(
;
− поглощения
a ∨ a & b = a, a & (a ∨ b) = a;
− действий с константами 0 и 1
a ∨ 0 = a, a & 0 = 0, a ∨ 1 = 1,
a & 1 = a, 1=∨ aa , 0& =aa .
Для рассматриваемого примера булевой функции f(x
1
, x
2
, x
3
) задание в виде дизъюнкции
конституент имеет вид:

Страницы