Практическая работа 5
Тема:
Построение СДНФ и СКНФ по таблице истинности, моделирование логической схемы в конструкторе
Цель:
моделирование работы цифровых элементов, реализующих основные логические функции: И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ
Теоретическая часть
Построение СКНФ и СДНФ по таблице истинности
Нормальная форма логической формулы не содержит знаков импликации, эквивалентности и отрицания неэлементарных формул.
Нормальная форма существует в двух видах:
· конъюнктивная нормальная форма (КНФ) -- конъюнкция нескольких дизъюнкций, например, (A∨B¯∨C)∧(A∨C);
· дизъюнктивная нормальная форма (ДНФ) -- дизъюнкция нескольких конъюнкций, например, (A∧B¯∧C)∨(B∧C).
СКНФ Совершенная конъюнктивная нормальная форма (СКНФ) -- это КНФ, удовлетворяющая трем условиям: не содержит одинаковых элементарных дизъюнкций; ни одна из дизъюнкций не содержит одинаковых переменных; каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.
Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.
Правила построения СКНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием
СДНФ Совершенная дизъюнктивная нормальная форма (СДНФ) -- это ДНФ, удовлетворяющая трем условиям: не содержит одинаковых элементарных конъюнкций; ни одна из конъюнкций не содержит одинаковых переменных; каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.
Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом. Правила построения СДНФ по таблице истинности.
Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.
Примеры нахождения СКНФ и СДНФ
Пример 1 Записать логическую функцию по ее таблице истинности:
Решение: Воспользуемся правилом построения СДНФ:
Получим СДНФ:
F(x1, x2, x3)=(x1¯∧x2¯∧x3¯)∨(x1¯∧x2¯∧x3)∨(x1∧x2¯∧x3¯)∨(x1∧x2¯∧x3)∨(x1∧x2∧x3)
Воспользуемся правилом построения СКНФ:
Получим СКНФ: F(x1, x2, x3)=(x1∨x2¯∨x3)∧(x1∨x2¯∨x3¯)∧(x1¯∨x2¯∨x3)
Пример 2
Функция задана таблицей истинности:
Представить эту функцию в виде СДНФ и СКНФ.
Решение:
Запишем логическую функцию в СДНФ.
Для удобства решения добавим к таблице вспомогательный столбец. Используя правило составления СДНФ не забываем вводить знак отрицания для переменных со значением 0. Инвертировать нулевые значения переменных обязательно, т.к. иначе они превратят значения конъюнкций в нули основной функции.
Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ: F(x1,x2,x3,x4)=(x¯∧y¯∧z∧f)∨(x1¯∧x2∧x3¯∧x4¯)∨(x1¯∧x2∧x3∧x4)∨(x1∧x2¯∧x3¯∧x4¯).
Запишем логическую функцию в СКНФ.
Используя правило составления СКНФ не забываем вводить знак отрицания для переменных со значением 1. Инвертировать единичные значения переменных обязательно, т.к. иначе они превратят значения дизъюнкций в единицы основной функции.
Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:
F(x1,x2,x3,x4)=(x1∨x2∨x3∨x4)∧(x1∨x2∨x3∨x4¯)∧(x1∨x2∨x3¯∨x4)∧(x1∨x2¯∨x3∨x4¯)∧(x1∨x2¯∨x3¯∨x4)∧(x1¯∨x2∨x3∨x4¯)∧(x1¯∨x2∨x3¯∨x4)∧(x1¯∨x2∨x3¯∨x4¯)∧(x1¯∨x2¯∨x3∨x4)∧(x1¯∨x2¯∨x3∨x4¯)∧(x1¯∨x2¯∨x3¯∨x4)∧(x1¯∨x2¯∨x3¯∨x4¯)
Порядок выполнения работы
1. Согласно полученному набору единичных значений функции построить для нее СДНФ и СКНФ
2. Привести полученные СДНФ и СКНФ к базису И-НЕ или ИЛИ-не (по заданию)
3. Смоделировать полученные логические функции в конструкторе логических схем