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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

36
Единственному покрытию {a, b} соответствует множество макси-
мальных единичных интервалов I
max
= {0 – – – 0 – –, – 1 – 0 – – –} и тупи-
ковая ДНФ:
f
l
(x
1
, x
2
, ..., x
7
) =
4251
xxxx ∨
,
которая и является минимальной ДНФ нашей слабоопределённой буле-
вой функции:
f
min
(x
1
, x
2
, ..., x
7
) =
4251
xxxx ∨
.
Задачи и упражнения
1. Минимизировать в классе ДНФ слабоопределённую булеву
функцию, заданную перечислением единичных и нулевых интервалов:
а)
−−−
−−−
=
;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
7. ПОЛНОТА
Выясним, какими свойствами должно обладать некоторое множест-
во (система) булевых функций S, чтобы с помощью функций из этого
множества можно было бы выразить любую булеву функцию.
Суперпозицией системы S = {
),,...,,(
1
211 k
xxxϕ ),,...,,(
2
212 k
xxxϕ
…,
),...,,(
21
l
kl
xxxϕ
} функций φ
1
, φ
2
, …, φ
l
называется любая функция f, по-
лученная:
а) из функции
),...,,(
21
j
kj
xxxϕ
переименованием переменных;
б) подстановкой вместо некоторых переменных функции
),...,,(
21
α
α
ϕ
k
xxx
функции
).,...,,(
21
β
β
ϕ
k
xxx
При этом подп. а) и б) могут
применяться многократно.
Система S называется полной системой в k-значной логике P
k
, если
любая функция f ∈ P
k
представима в виде суперпозиции системы S. Пол-
ная система S называется базисом B, если она перестаёт быть полной (те-
ряет полноту) при удалении из неё любой функции.

Страницы