Дискретная математика. Прокушев Л.А. - 19 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

17
и ,хyхyхyхy↓= ↓=∨
а функцию f
14
(штрих Шеффера) – формулами:
| и | .хy х y хy хy=∨ =
Формулы, представляющие одну и ту же функцию, называются экви-
валентными, или равносильными, что обозначается знаком равенства:
814
,(, )
.
fxyxyfxухуху==∨ =∨=
Алгеброй булевых функций будем называть множество всех конечно-
местных булевых функций, рассматриваемое вместе с заданными на нем
операциями отрицания, конъюнкции и дизъюнкции, т. е. алгебра вида
(P
n
,
−, &,
∨
), где P
n
– множество n-местных булевых функций.
Пусть буквы латинского алфавита (с индексами или без них) обозна-
чают произвольные элементы булевой алгебры (булевы функции). Од-
ной из основных задач булевой алгебры является установление тожде-
ственных соотношений вида A(x, y, z, …) = B(x, y, z, …), где через А и В
обозначены формулы булевой алгебры. Для упрощения формул вводят-
ся следующие правила:
1) соблюдается старшинство операций (отрицание, конъюнкция и
дизъюнкция), а при необходимости изменить порядок действий приме-
няются скобки;
2) знак конъюнкции (умножения) может быть опущен;
3) отрицание над всем выражением позволяет не заключать его в скобки;
4) при выполнении подряд одноименных операций скобки можно
опускать.
Правила и законы булевых операций аналогичны свойствам опера-
ций алгебры множеств, рассмотренным выше:
Ассоциативность (возможность опускать скобки):
а) х(уz) = (xу)z = xyz б) (1)
Коммутативность (перестановка операндов):
а) ху = ух б) (2)
Идемпотентность (отсутствие степеней и коэффициентов):
а) хх = х б) (3)
Дистрибутивность конъюнкции относительно дизъюнкции:
(4)
Дистрибутивность дизъюнкции относительно конъюнкции:
(5)
Закон двойного отрицания: x = x (6)
( v ) v v ( v ) v v xy zx yz xyz
==
v v xyyx
=
v xxx
=
( v ) v xy z xy z
=
v ( v ) v ( v )xyz xy xz
=

Страницы