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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Если функция f не равна тождественно 0, то, согласно следствию
2, она представима в виде СДНФ. Если же f = 0, то f = xx.
Совершенная дизъюнктивная нормальная форма логической
функции может быть получена из таблицы значений этой функции.
Для этого по каждому единичному набору запишем конъюнкцию
переменных и их отрицаний по следующему правилу. Если в наборе
значение переменной равно 0, то переменную возьмем с отрицанием,
если равно 1, то без отрицания. Из получившихся конъюнкций постро-
им дизъюнкцию.
Пример 4. Построим совершенную дизъюнктивную нормальную
форму функции голосования. Таблица значений для нее построена в
п.1. Наборы, на которых функция равна 1, — это (0,1,1), (1,0,1), (1,1,0),
(1,1,1). Таким образом, СДНФ функции голосования будет иметь вид
: x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
.
Упражнение 3. Найдите СДНФ функции, тождественно равной 1, т.е.
f(x
1
, . . . , x
n
) = 1.
5. Совершенная конъюнктивная нормальная
форма
Во многом совершенно аналогично предыдущему определяется
совершенная конъюнктивная нормальная форма.
Теорема 3. Всякая логическая функция f(x
1
, x
2
, . . . , x
n
) может
быть представлена в виде
f(x
1
, . . . , x
m
, x
m+1
, . . . , x
n
) =
=
V
(α
1
,...,α
m
)
[x
α
1
1
+ . . . + x
α
m
m
+ f(α
1
, . . . , α
m
, x
m+1
, . . . , x
n
)], (4)
где m 6 n, а конъюнкция берется по всем 2
m
наборам значений
(α
1
, . . . , α
m
), α
i
∈ B.
(Это равенство называют разложением в конъюнкцию по m пер-
вым переменным.)
В правой части (4) каждый член конъюнкции представляет со-
бой некоторую дизъюнкцию, и интерес представляют только те дизъ-
юнкции, среди членов которых нет 1. Рассуждая аналогично доказа-
тельству теоремы 1, получим (так как равенство β
α
i
i
= 0 выполняется
только при α
i
= β
i
) :
V
(α
1
,...,α
m
)
[β
α
1
1
+ . . . + β
α
m
m
+ f(α
1
, . . . , α
m
, β
m+1
, . . . , β
n
)] =
= β
β
1
1
+ . . . + β
β
m
m
+ f(β
1
, . . . , β
n
) = f(β
1
, . . . , β
n
).
19

Страницы