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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

(Это равенство называют разложением в дизъюнкцию по m пер-
вым переменным.)
Покажем, что для любого набора значений переменных x
1
, x
2
,. . . ,
x
n
значения левой и правой частей совпадают. Подставим в правую
часть равенства (1) произвольный набор значений β
1
, β
2
, . . . , β
n
. Так
как для каждого i (1 6 i 6 m) равенство β
α
i
i
= 1 выполняется только
при α
i
= β
i
, получим
W
(α
1
,...,α
m
)
β
α
1
1
. . . β
α
m
m
f(α
1
, . . . , α
m
, β
m+1
, . . . , β
n
) =
= β
β
1
1
. . . β
β
m
m
f(β
1
, . . . , β
n
) = f(β
1
, . . . , β
n
).
Пример 3. При m = 2, n = 3 для произвольной логической функ-
ции f получим
f(x
1
, x
2
, x
3
) =
= x
1
x
2
f(0, 0, x
3
) + x
1
x
2
f(0, 1, x
3
) + x
1
x
2
f(1, 0, x
3
) + x
1
x
2
f(1, 1, x
3
). (2)
Упражнение 2. Примените формулу (2) к функции голосования, предвари-
тельно упростив g(0, 0, x
3
), g(0, 1, x
3
) и т.д.
Следствие 1. Для любой логической функции имеет место
f(x
1
, x
2
, . . . , x
n
) = x
1
f(0, x
2
, . . . , x
n
) + x
1
f(1, x
2
, . . . , x
n
).
Вытекает из теоремы 1 при m = 1.
Следствие 2. Если функция f не совпадает с 0, то
f(x
1
, . . . , x
n
) =
_
f(α
1
,...,α
n
)=1
x
α
1
1
. . . x
α
n
n
, (3)
где дизъюнкция берется по всем наборам (α
1
, . . . , α
n
), на которых зна-
чение функции f равно 1.
Вытекает из теоремы 1 при m = n.
Разложение (3), в котором функция f представлена в виде дизъ-
юнкции членов x
α
1
1
. . . x
α
n
n
, называется совершенной дизъюнктивной
нормальной формой (сокращенно СДНФ) функции f.
Формула, содержащая только функции дизъюнкции, конъюнкции
и отрицания, называется булевой формулой.
Теорема 2. Всякая логическая функция может быть представ-
лена в виде булевой формулы ( т.е. выражается через функции ∨, ∧ и
¬).
18

Страницы