Основы дискретной математики. Щипцов В.В - 24 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

24
1 1 1 1 получаем искомую СДНФ
f(х
1
,х
2
,х
3
)= х
1
⋅х
2
⋅х
3
∨ х
1
⋅х
2
⋅х
3
∨ х
1
⋅х
2
⋅х
3
∨ х
1
⋅х
2
⋅х
3
∨х
1
⋅х
2
⋅х
3
.
Отметим, что конъюнктивные члены, входящие в СДНФ, называются
конституентами единицы.
Совершенная конъюнктивная нормальная форма
Аналогично понятию СДНФ вводится понятие совершенной
конъюнктивной нормальной формы (СКНФ), которая может быть
представлена в виде некоторого числа дизъюнктивных членов, соединенных
знаками конъюнкции.
Правило построения СКНФ булевой функции, заданной таблицей,
формируется следующим образом:
1. Из Таблицы выбираются все наборы аргументов х
1
,х
2
,...,х
n
, для которых
f(х
1
,х
2
,...,х
n
) равна 0.
2. Для каждого из таких наборов составляются дизъюнкции, равные 0.
3. полученные дизъюнкции соединяются знаками конъюнкции.
Составим, например, СКНФ функции f(х
1
,х
2
,х
3
), заданной табл.8. Для
этого заметим, что для наборов, стоящих во 2, 4 и 5-й строках функция
f(х
1
,х
2
,х
3
) равна 0. Образуем из этих наборов дизъюнкции, равные 0: х
1
∨х
2
∨х
3
,
х
1
∨х
2
∨х
3
, х
1
∨х
2
∨х
3
. Тогда искомая СКНФ будет иметь вид
f(х
1
,х
2
,х
3
)= (х
1
∨х
2
∨х
3
) ⋅ (х
1
∨х
2
∨х
3
) ⋅ (х
1
∨х
2
∨х
3
).
Заметим, что дизъюнктивные члены, входящие в СКНФ, называются
конституентами нуля.
§ 2.5. Минимизация формул алгебры логики. Полные системы булевых
функций. Понятие базиса.
Рассмотрим вопрос о возможности представления произвольной булевой
функции в виде комбинации какого-либо фиксированного множества функций.
С этой целью введем понятие
полной
системы функций.
Определение.
Система булевых функций f
1
,f
2
,...,f
m
называется полной,
если любую булеву функцию можно представить в виде формулы через
функции f
1
,f
2
,...,f
m
.
Сама система функций f
1
,f
2
,...,f
m
называется базисом.
Базис называется минимальным
, если удаление хотя бы одной из
входящих в него функций f
i
превращает систему функций в неполную.
Выше было установлено, что любую булеву функцию можно представить
через отрицания, дизъюнкции и конъюнкции, это означает, что система
функций
х, х
1
∨х
2
, х
1
⋅
х
2
(6)

Страницы