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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Следствие 1. Для любой логической функции имеет место
f(x
1
, x
2
, . . . , x
n
) = (x
1
+ f(0, x
2
, . . . , x
n
))(x
1
+ f(1, x
2
, . . . , x
n
)).
Следствие 2. Если функция f не совпадает с 1, то
f(x
1
, . . . , x
n
) =
^
f(α
1
,...,α
n
)=0
(x
α
1
1
+ . . . + x
α
n
n
), (5)
где конъюнкция берется по всем наборам (α
1
, . . . , α
n
), на которых зна-
чение функции f равно 0.
Правая часть формулы (5), в которой функция f представлена в
виде разложения в конъюнкцию по всем переменным, называется со-
вершенной конъюнктивной нормальной формой (сокращенно СКНФ)
функции f.
Совершенная конъюнктивная нормальная форма логической
функции также может быть получена из таблицы значений этой функ-
ции.
Для этого по каждому нулевому набору запишем дизъюнкцию
переменных и их отрицаний по следующему правилу. Если в наборе
значение переменной равно 0, то переменную возьмем без отрицания,
если равно 1, то с отрицанием. Из получившихся дизъюнкций построим
конъюнкцию.
Пример 5. Вернемся к функции голосования (см. примеры 1 и
4). Наборы, на которых функция равна 0, — это (0,0,0), (0,0,1), (0,1,0),
(1,0,0). В соответствии с правилом, СКНФ будет иметь вид : (x
1
+ x
2
+
x
3
)(x
1
+ x
2
+ x
3
)(x
1
+ x
2
+ x
3
)(x
1
+ x
2
+ x
3
).
Упражнение 4. Найдите СКНФ функции, тождественно равной 0, т.е.
f(x
1
, . . . , x
n
) = 0.
20

Страницы