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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

37
В качестве примера рассмотрим систему S = { }, состоящую из од-
ной четырёхместной булевой функции (x
1
, x
2
, x
3
, x
4
) =
3241
xxxx ∨
.
Установим, можно ли каждую булеву функцию f (x
1
, x
2
, ..., x
n
) пред-
ставить в виде суперпозиции системы S = { }.
Как известно, любую булеву функцию можно задать с помощью
функций конъюнкциия &, дизъюнкции ∨ и отрицания . Выразив отри-
цание и дизъюнкцию через функцию :
α
=
α
∨ 0 =
α
α
∨ α
α
= (α, α, α, α);
α ∨ β =
ββ∨αα
= (
α
, β, β ,
α
) =
= ( (α, α, α, α), β, (β, β, β, β), (α, α, α, α)),
на основании разложения Шеннона и закона де-Моргана можно сделать
заключение о том, что любую булеву функцию f (x
1
, x
2
, ..., x
n
) можно
представить в виде суперпозиции системы S = { }.
В общем случае для установления полноты системы S булевых
функций в двузначной логике P
2
используют следующий критерий.
Критерий полноты Поста–Яблонского. Система булевых функций
S является полной тогда и только тогда, когда она: содержит функцию,
не принадлежащую классу K
0
; содержит функцию, не принадлежащую
классу K
1
; содержит функцию, не принадлежащую классу K
л
; содержит
функцию, не принадлежащую классу K
с
и содержит функцию, не принад-
лежащую классу K
м
.
Определим упомянутые в критерии пять классов булевых функций.
Классом K
0
булевых функций, сохраняющих константу 0, называет-
ся множество булевых функций вида:
K
0
= { f
i
(x
1
, x
2
, ..., x
n
) / f
i
(0, 0, ..., 0) = 0}.
Классом K
1
булевых функций, сохраняющих константу 1, называет-
ся множество булевых функций вида:
K
1
= { f
i
(x
1
, x
2
, ..., x
n
) / f
i
(1, 1, ..., 1) = 1}.
Определим принадлежность функции к классам K
0
и K
1
:
(0, 0, 0, 0) =
0000 ∨
= 1 ∨ 0 = 1, ∉ K
0
,
(1, 1, 1, 1) =
1
1
1
1
∨
= 0 ∨ 0 = 0, ∉ K
1
.
Классом K
л
линейных булевых функций называется множество буле-
вых функций вида:
{ f
i
(x
1
, x
2
, ..., x
n
) / f
i
(x
1
, x
2
, ..., x
n
) = c
0
⊕
∑
=
n
j
jj
xc
1
},

Страницы