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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

а)
−−−
−−−
=
;1000,0111,0001интервалахна0
;1101,0011,0111интервалахна1
),...,,(
521
xxxf
б)
−−−−−−
−−−−−−
=
;1011,0001,1011интервалахна0
;1011,0011,1101интервалахна1
),...,,(
621
xxxf
в)
−−−−−−−
−−−−−−−−
=
;0001,000000,0101интервалахна0
;010,0011,010010интервалахна1
),...,,(
721
xxxf
г)
−−−−−
−−−−−−−
=
.0111,011001,101111интервалахна0
;011,00100,011100интервалахна1
),...,,(
721
xxxf
5. ПОЛНОТА
Любую булеву функцию можно представить с помощью операций конъ-
юнкция &, дизъюнкция ∨, отрицание и, быть может, скобок (, ). Выясним, каким свойствам должны
удовлетворять операции, с помощью которых можно выражать любую булеву функцию.
Рассмотрим алгебру вида <M, >, где M – множество булевых функций и (a, b, c, d) =
cbda ∨ .
Установим, можно ли любую булеву функцию f(x
1
, x
2
, ..., x
n
) выразить в виде суперпозиции системы
S = {}, как это возможно для случая системы {∨, &,
}.
Суперпозицией системы S = {
,...),,...,,(),,...,,(
21
212211 kk
xxxxxx
ϕ
ϕ )},...,,(
21
l
kl
xxx
ϕ
называется любая
функция f, полученная:
а) из ),...,,(
21
j
kj
xxxϕ переименованием переменных, S
j
∈ϕ ;
б) подстановкой вместо некоторых переменных функции
),...,,(
21
α
α
ϕ
k
xxx
функций ),...,,(
21
j
kj
xxxϕ ,
S
j
∈ϕϕ
α
,
;
в) с помощью многократного применения п. а) и б).
Система S называется полной в k-значной логике P
k
, если любая функция f ∈ P
k
представима в виде
суперпозиции этой системы, и базисом, если теряется полнота S при удалении хотя бы одной функции.
Выразим дизъюнкцию и отрицание через (a, b, c, d):
α = α ∨ 0 =
α
α
∨ α
α
= (α, α, α, α);
α ∨ β = ββ∨αα = (
α
, β, β ,
α
) =
= ( (α, α, α, α), β, (β, β, β, β), (α, α, α, α)).
Тогда, согласно разложению Шеннона и закону де-Моргана, любую булеву функцию f (x
1
, x
2
, ..., x
n
)
можно выразить в виде суперпозиции системы S = {}.
В общем случае для установления полноты системы S булевых функций f
i
в P
2
используют крите-
рий полноты Поста – Яблонского.
Определим предварительно пять классов булевых функций.
Классом K
0
булевых функций f
i
(x
1
, x
2
, ..., x
n
), сохраняющих константу 0, называется множество бу-
левых функций вида
{ f
i
(x
1
, x
2
, ..., x
n
) / f
i
(0, 0, ..., 0) = 0}.
Классом K
1
булевых функций f
i
(x
1
, x
2
, ... , x
n
), сохраняющих константу 1, называется множество буле-
вых функций вида
{ f
i
(x
1
, x
2
, ..., x
n
) / f
i
(1, 1, ..., 1) = 1}.
Определим принадлежность функции (a, b, c, d) =
cbda ∨ к классам K
0
и K
1
:
(0, 0, 0, 0) =
0000 ∨
= 1 ∨ 0 = 1, (a, b, c, d) ∉ K
0
,
(1, 1, 1, 1) =
1111 ∨
= 0 ∨ 0 = 0, (a, b, c, d) ∉ K
1
.
Классом K
л
линейных булевых функций f
i
(x
1
, x
2
, ..., x
n
) называется множество булевых функций вида
{ f
i
(x
1
, x
2
, ..., x
n
) / f
i
(x
1
, x
2
, ..., x
n
) = c
0
⊕
∑
jj
xc },

Страницы