Элементы математической логики. Фролов И.С. - 31 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Теорема 2. Каждая логическая функция может быть единствен-
ным образом представлена в виде многочлена Жегалкина стандартного
вида.
Так как система функций Σ
(5)
полна, то любую логическую функ-
цию можно представить формулой над {1, ∧, ⊕}. Далее, в силу комму-
тативности и ассоциативности ∧, ⊕ и дистрибутивности ∧ относительно
⊕, эту формулу можно преобразовать к виду (2).
Для доказательства единственности покажем, что число всех ло-
гических функций от n аргументов и число многочленов Жегалкина с
n аргументами совпадают между собой. Во-первых, |Λ(n)| = 2
2
n
(пред-
ложение 1 § 2). С другой стороны, число возможных циклических сла-
гаемых в выражении (2) равно количеству подмножеств {i
1
, . . . , i
s
} из
n чисел {1, . . . , n}, включая пустое подмножество ∅, которому соответ-
ствует первое слагаемое. Поскольку каждый коэффициент c
i
1
,...,i
s
равен
0 или 1, искомое число многочленов Жегалкина равно 2
2
n
.
Существует ряд способов построения многочлена Жегалкина для
заданной логической функции.
Пример 5. Найдем многочлен Жегалкина для x
1
∨ x
2
методом
неопределенных коэффициентов. Запишем
x
1
∨ x
2
= α
0
⊕ α
1
x
1
⊕ α
2
x
2
⊕ α
3
x
1
x
2
,
где α
i
∈ {0, 1} (0 6 i 6 3) — неопределенные коэффициенты.
При x
1
= x
2
= 0 имеем x
1
∨ x
2
= 0 = α
0
. При x
1
= 0 , x
2
= 1
имеем x
1
∨ x
2
= 1 = α
0
⊕ α
2
, т.е. α
2
= 1. При x
1
= 1 , x
2
= 0 имеем
x
1
∨ x
2
= 1 = α
0
⊕ α
1
, т.е. α
1
= 1. При x
1
= x
2
= 1 имеем x
1
∨ x
2
= 1 =
= α
0
⊕ α
1
⊕ α
2
⊕ α
3
, откуда α
3
= 1.
В результате получаем
x
1
∨ x
2
= x
1
⊕ x
2
⊕ x
1
x
2
.
Пример 6. Используем предыдущий пример, чтобы найти мно-
гочлен Жегалкина для импликации: x
1
⇒ x
2
= x
1
∨ x
2
=
= x
1
⊕x
2
⊕x
1
x
2
= (x
1
⊕1) ⊕x
2
⊕(x
1
⊕1)x
2
= x
1
⊕1 ⊕x
2
⊕x
1
x
2
⊕x
2
=
= 1 ⊕ x
1
⊕ x
1
x
2
(так как два одинаковых циклических слагаемых вза-
имно уничтожаются).
Пример 7. Поскольку при xy = 0 справедливо x ∨ y = x ⊕ y,
то для совершенной дизъюнктивной нормальной формы имеет ме-
сто K
1
∨ K
2
∨ . . . ∨ K
n
= K
1
⊕ K
2
⊕ . . . ⊕ K
n
. Применим это замеча-
ние к x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
= x
1
x
2
x
3
⊕ x
1
x
2
x
3
⊕ x
1
x
2
x
3
= x
1
x
2
x
3
⊕
⊕(x
1
⊕1)(x
2
⊕1)x
3
⊕(x
1
⊕1)x
2
(x
3
⊕1) = x
1
x
2
x
3
⊕x
1
x
2
⊕x
1
x
3
⊕x
2
⊕x
3
(проверьте!).
30

Страницы