Для заданной булевой функции трех переменных

А) Используя определения булевых операций и правила приоритета, составим таблицу истинности булевой функции f
x y z
0 0 0 1 1 1 0 0 1
0 0 1 1 1 1 1 1 0
0 1 0 1 0 0 0 1 0
0 1 1 1 0 0 1 1 0
1 0 0 0 1 1 1 1 0
1 0 1 0 1 1 0 0 1
1 1 0 0 0 1 1 1 0
1 1 1 0 0 1 0 0 1
Запишем двоичную форму булевой функции:
.
Построим СДНФ заданной функции.
Алгоритм построения СДНФ по таблице истинности функции состоит из трех шагов.
В таблице истинности выбираются наборы, на которых функция принимает значение 1 (единицы).
Для наборов, выбранных на первом шаге, составляются конституенты единицы, в которые переменная входит с инверсией, если в соответствующем наборе она принимает значение 0 (ноль), и без инверсии, если в соответствующем наборе она принимает значение 1 (единицы).
Составляется дизъюнкция построенных на втором шаге конституент единицы.
Получаем СДНФ:
.
Построим СКНФ заданной функции.
Алгоритм построения СКНФ по таблице истинности логической функции содержит три шага.
В таблице истинности функции выбираются наборы, на которых функция принимает значение 0 (нуля).
Для этих наборов составляются конституенты нуля, в которые переменная входит с инверсией, если в наборе она принимает значение единицы, и без инверсии, если в наборе она принимает значение нуля.
Составляется конъюнкция построенных на предыдущем шаге конституент нуля.
Получаем СКНФ:
.
б) Выпишем основные логические законы:
Закон двойного отрицания:
.
Идемпотентность:
, .
Коммутативность:
, .
Ассоциативность:
, .
Дистрибутивность:
, .
Законы де Моргана:
, , , .
Формулы с константами:
,, ,
, , .
Дополнительные равносильности:
,
,
,
,
,
,
,
,
, (законы склеивания),
(законы поглощения),
(закон обобщенного склеивания),
, (законы Блейка-Порецкого).
Используя логические равносильности, преобразуем формулу f к ДНФ (дизъюнктивной нормальной форме) – дизъюнкции конъюнктивных одночленов:
Итак, ДНФ формулы:
.
Во время преобразования формулы была получена также КНФ (конъюнктивная нормальная форма) – конъюнкция дизъюнктивных одночленов:
.
Используя законы склеивания и поглощения, перейдем от ДНФ к СДНФ – совершенной дизъюнктивной нормальной форме:
.
Итак, CДНФ формулы:
.
Используя законы склеивания и поглощения, перейдем от КНФ к СКНФ – совершенной конъюнктивной нормальной форме:
Итак, CКНФ формулы:
.