Нормальная форма логической функции – если логическая функция представлена дизъюнкцией, конъюнкцией и инверсией.
Элементарная конъюнкция – конъюнкция конечного множества логических переменных и их инверсий.
Элементарная дизъюнкция – дизъюнкция конечного множества логических переменных и их инверсий.
Ранг элементарной конъюнкции или дизъюнкции – число аргументов ее образующих.
Примеры
Элементарная конъюнкция третьего порядка
Элементарная дизъюнкция второго порядка
Конъюнктивная нормальная форма (КНФ) содержит элементарные дизъюнкции, связанные между собой операциями конъюнкции.
Дизъюнктивная нормальная форма (ДНФ) содержит элементарные конъюнкции, связанные между собой операциями дизъюнкции.
Примеры
Совершенная конъюнктивная нормальная форма (СКНФ):
1) нет двух элементарных дизъюнкций;
2) ни одна элементарная дизъюнкция не содержит двух одинаковых переменных;
3) ни одна элементарная дизъюнкция не содержит переменную вместе с ее инверсией;
4) все дизъюнкции имеют один и тот же ранг.
Совершенная дизъюнктивная нормальная форма (СДНФ)
Алгоритм образования СКНФ и СДНФпо таблице истинности
1. Выделить в таблице истинности все строки, в которых функция принимает значения 0.
1. Выделить в таблице истинности все строки, в которых функция принимает значения 1.
2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные:
а) если значение переменной равно 0, то записывается сама переменная,
б) если значение переменной равно 1, то записывается инверсия этой переменной.
2. Для каждого выбранного набора записать элементарные конъюнкции, содержащие переменные:
а) если значение переменной равно 0, то записывается инверсия этой переменной,
б) если значение переменной равно 1, то записывается сама переменная.
3. Соединить элементарные дизъюнкции знаком конъюнкции.
3. Соединить элементарные конъюнкции знаком дизъюнкции.
ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при которых тело находится под действием заданной системы сил...
Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...
Ваготомия. Дренирующие операции Ваготомия – денервация зон желудка, секретирующих соляную кислоту, путем пересечения блуждающих нервов или их ветвей...
Билиодигестивные анастомозы Показания для наложения билиодигестивных анастомозов:
1. нарушения проходимости терминального отдела холедоха при доброкачественной патологии (стенозы и стриктуры холедоха)
2. опухоли большого дуоденального сосочка...