Построение СКНФ и СДНФ по таблице истинности
Для любой логической формулы можно построить бесконечное количество равносильных ей формул. Для этого потребуется произвести некоторое количество тождественных преобразований. Одной из главных задач в алгебре логики является нахождение канонических форм формул. Проще говоря таких, которые построены по одному канону (правилу).
Форма представления какой-либо логической функции будет считаться нормальной, если она выражена через конъюнкцию, дизъюнкцию, а также отрицание переменных. Среди всех нормальных форм можно выделить совершенно нормальные. Это тот случай, когда функция может быть записана только одним единственным способом.
Классы СКНФ и СДНФ
В при решении задач в алгебре логики особая роль отводится классам конъюнктивных и дизъюнктивных совершенно нормальных форм. Они основаны на стандартных понятиях элементарной конъюнкции и дизъюнкции.
Элементарной конъюнкцией принято называть формулу в том случае, когда она представляет собой конъюнкцию любого количества переменных, которые берутся без отрицания либо с отрицанием. При этом одночленной элементарной конъюнкцией считается только одна единственная переменная либо ее отрицание.
Элементарной дизъюнкцией называют формулу при условии, что она будет являться дизъюнкцией некоторого любого количества переменных и отрицаний, при этом она может быть и одночленной.
СКНФ
Форма любой логической формулы нормального типа не может содержать знаки эквивалентности, импликации, а также отрицания неэлементарных формул. Она может существовать только в двух видах:
- КНФ – конъюнктивная нормальная форма, представляющая собой конъюнкцию нескольких дизъюнкций. К примеру, \[(A \vee \bar{B} \vee C) \wedge(A \vee C)\];
- ДНФ – дизъюнктивная нормальная форма, которая является дизъюнкцией нескольких конъюнкций. К примеру, \[(A \wedge \bar{B} \wedge C) \vee(A \wedge C)\].
Совершенной конъюнктивной нормальной формой (СКНФ) называют КНФ, удовлетворяющую нескольким условиям:
- В ней не содержится двух и более элементарных дизъюнкций;
- Во всех дизъюнкциях отсутствуют одинаковые переменные;
- Каждая ДНФ содержит в себе все переменные из входящих в нее КНФ.
Любую булеву формулу, не являющуюся тождественной истиной, можно представить в виде СКНФ.
Правила построения СКНФ
В алгебре логики для любого набора переменных, при котором конечное значение функции становится нулевым, можно записать сумму. При этом переменные, имеющие числовые значение больше единицы, должны браться с отрицательным знаком.
Построение должно осуществляться по следующему алгоритму:
- В таблице нужно отметить такие наборы переменных, при которых \[f=1\].
- Для каждого выбранного набора переменных записываем КНФ, при этом если значение какой-либо из них равно 1, то она включается в неизменном виде, иначе – ее отрицание.
- На последнем этапе все полученные конъюнкции следует связать операциями дизъюнкции.
СНДФ
Совершенной дизъюнктивной нормальной формой (СНДФ) называют удовлетворяющую нескольким условиям ДНФ. Всего должно выполняться три условия:
- В ДНФ не должно содержаться двух и более одинаковых СКНФ.
- Ни в одной из конъюнкций не должно содержаться одинаковых переменных.
- В каждой элементарной КНФ должны содержаться все переменные, входящих в нее ДНФ, при этом их порядок должен полностью совпадать.
Любую булеву формулу в алгебре логики, не являющуюся тождественно ложной, можно представить в виде СНДФ, но только в одном единственном виде.
Правила построения СДНФ
Если существует определённый набор переменных, при котором значение функции равно единице, то можно записать произведения, учитывая, что переменные, значение которых больше нуля, нужно брать с отрицанием.
Алгоритм построения будет следующим:
- В таблице отмечаются все те наборы переменных, при которых \[f=0\]
- Для каждого отмеченного набора всех переменных записывается ДНФ, при этом если значение какой-либо из них равно нулю, то включается сама переменная, в любом другом случае ее нужно инвертировать.
- В конце все полученные дизъюнкции связываются друг с другом операциями конъюнкции.
Нет времени решать самому?
Наши эксперты помогут!
Контрольная
| от 300 ₽ |
Реферат
| от 500 ₽ |
Курсовая
| от 1 000 ₽ |
Примеры нахождения СКНФ и СДНФ
Рассмотрим несколько примеров нахождения СКНФ и СДНФ с помощью данных таблицы истинности.
Необходимо по таблице истинности записать логическую функцию.
Решение. Для того чтобы выполнить задачу будем использовать правило построения СДНФ.
Получим СДНФ, которая имеет следующий вид:
\[F\left(x_{1}, x_{2}, x_{3}\right)=\left(\overline{x_{1}} \wedge \overline{x_{2}} \wedge \overline{x_{3}}\right) \vee\left(\overline{x_{1}} \wedge \overline{x_{2}} \wedge x_{3}\right) \vee\left(x_{1} \wedge \overline{x_{2}} \wedge \overline{x_{3}}\right) \vee\left(x_{1} \wedge\right.\left.\overline{x_{2}} \wedge x_{3}\right) \vee\left(x_{1} \wedge x_{2} \wedge x_{3}\right)\]
Далее будем действовать согласно правилу построения СКНФ:
В результате получим:
\[F\left(x_{1}, x_{2}, x_{3}\right)=\left(x_{1} \wedge \overline{x_{2}} \wedge x_{3}\right) \wedge\left(x_{1} \wedge \overline{x_{2}} \wedge \overline{x_{3}}\right) \wedge\left(\overline{x_{1}} \wedge \overline{x_{2}} \wedge x_{3}\right)\]
Требуется представить функцию, которая задана в таблице в виде СДНФ и СКНФ.
Решение: Для начала запишем в СНДФ заданную логическую функцию. Чтобы было проще, добавим еще один вспомогательный столбец. Руководствуемся правилом составления СДНФ и учитываем, что требуется ввести знак отрицания, если значение переменной будет нулевым. Это нужно для того, чтобы они не превратили в нули основной функции значение конъюнкции.
Значения, которые получились во вспомогательном столбце соединяем знаком дизъюнкции, в результате чего получаем искомую логическую функцию, которая примет следующий вид:
\[F\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=(\bar{x} \wedge \bar{y} \wedge z \wedge f) \vee\left(\overline{x_{1}} \wedge \overline{x_{2}} \wedge \overline{x_{3}} \wedge \overline{x_{4}}\right) \vee\left(\overline{x_{1}} \wedge x_{2} \wedge x_{3} \wedge\right.\left.x_{4}\right) \vee\left(x_{1} \wedge \overline{x_{2}} \wedge \overline{x_{3}} \wedge \overline{x_{4}}\right)\]
После этого потребуется записать логическую функцию в СКНФ. Для этого используем правило ее составления и вводим знаки отрицания для тех переменных, значение которых равно 1. Если пренебречь инвертированием единичных значений, то они могут превратить ДНФ в единицы основных функций.
Все полученные нами значения во вспомогательном столбце соединяем знаком конъюнкции и в итоге получаем логическую функцию в следующем виде.
\[F\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=\left(x_{1} \vee x_{2} \vee x_{3} \vee x_{4}\right) \wedge\left(x_{1} \vee x_{2} \vee x_{3} \vee \overline{x_{4}}\right) \wedge\left(x_{1} \vee x_{2} \vee\right.\\\left.\overline{x_{3}} \vee x_{4}\right) \wedge\left(x_{1} \vee \overline{x_{2}} \vee x_{3} \vee \overline{x_{4}}\right) \wedge\left(x_{1} \vee \overline{x_{2}} \vee \overline{x_{3}} \vee x_{4}\right) \wedge\left(\overline{x_{1}} \vee x_{2} \vee x_{3} \vee\right.\\\left.\overline{x_{4}}\right) \wedge\left(\overline{x_{1}} \vee x_{2} \vee \overline{x_{3}} \vee x_{4}\right) \wedge\left(\overline{x_{1}} \vee x_{2} \vee \overline{x_{3}} \vee \overline{x_{4}}\right) \wedge\left(\overline{x_{1}} \vee \overline{x_{2}} \vee x_{3} \vee x_{4}\right) \wedge\\\left(\overline{x_{1}} \vee \overline{x_{2}} \vee x_{3} \vee \overline{x_{4}}\right) \wedge\left(\overline{x_{1}} \vee \overline{x_{2}} \vee \overline{x_{3}} \vee x_{4}\right) \wedge\left(\overline{x_{1}} \wedge \overline{x_{2}} \wedge \overline{x_{3}} \wedge \overline{x_{4}}\right)\]
После рассмотрения примеров построения СДНФ и СКНФ с использованием таблицы истинности, стал понятен принцип построения логических функций.
Выполнение любых работ по информатике
Популярные статьи
Устройства для вывода информации
Автоматизированные системы управления
ГИС: понятие, функции, виды
Информационно-коммуникационные технологии