Справочник

Построение СКНФ и СДНФ по таблице истинности

Оглавление
Время чтения:  5 минут
2 407

Для любой логической формулы можно построить бесконечное количество равносильных ей формул. Для этого потребуется произвести некоторое количество тождественных преобразований. Одной из главных задач в алгебре логики является нахождение канонических форм формул. Проще говоря таких, которые построены по одному канону (правилу).

Форма представления какой-либо логической функции будет считаться нормальной, если она выражена через конъюнкцию, дизъюнкцию, а также отрицание переменных. Среди всех нормальных форм можно выделить совершенно нормальные. Это тот случай, когда функция может быть записана только одним единственным способом.

Классы СКНФ и СДНФ

В при решении задач в алгебре логики особая роль отводится классам конъюнктивных и дизъюнктивных совершенно нормальных форм. Они основаны на стандартных понятиях элементарной конъюнкции и дизъюнкции.

Определение 1 — 2

Элементарной конъюнкцией принято называть формулу в том случае, когда она представляет собой конъюнкцию любого количества переменных, которые берутся без отрицания либо с отрицанием. При этом одночленной элементарной конъюнкцией считается только одна единственная переменная либо ее отрицание.

Элементарной дизъюнкцией называют формулу при условии, что она будет являться дизъюнкцией некоторого любого количества переменных и отрицаний, при этом она может быть и одночленной.

СКНФ

Форма любой логической формулы нормального типа не может содержать знаки эквивалентности, импликации, а также отрицания неэлементарных формул. Она может существовать только в двух видах:

  • КНФ – конъюнктивная нормальная форма, представляющая собой конъюнкцию нескольких дизъюнкций. К примеру, \[(A \vee \bar{B} \vee C) \wedge(A \vee C)\];
  • ДНФ – дизъюнктивная нормальная форма, которая является дизъюнкцией нескольких конъюнкций. К примеру, \[(A \wedge \bar{B} \wedge C) \vee(A \wedge C)\].
Определение 3

Совершенной конъюнктивной нормальной формой (СКНФ) называют КНФ, удовлетворяющую нескольким условиям:

  1. В ней не содержится двух и более элементарных дизъюнкций;
  2. Во всех дизъюнкциях отсутствуют одинаковые переменные;
  3. Каждая ДНФ содержит в себе все переменные из входящих в нее КНФ.

Любую булеву формулу, не являющуюся тождественной истиной, можно представить в виде СКНФ.

Правила построения СКНФ

В алгебре логики для любого набора переменных, при котором конечное значение функции становится нулевым, можно записать сумму. При этом переменные, имеющие числовые значение больше единицы, должны браться с отрицательным знаком.

Построение должно осуществляться по следующему алгоритму:

  1. В таблице нужно отметить такие наборы переменных, при которых \[f=1\].
  2. Для каждого выбранного набора переменных записываем КНФ, при этом если значение какой-либо из них равно 1, то она включается в неизменном виде, иначе – ее отрицание.
  3. На последнем этапе все полученные конъюнкции следует связать операциями дизъюнкции.

СНДФ

Определение 4

Совершенной дизъюнктивной нормальной формой (СНДФ) называют удовлетворяющую нескольким условиям ДНФ. Всего должно выполняться три условия:

  1. В ДНФ не должно содержаться двух и более одинаковых СКНФ.
  2. Ни в одной из конъюнкций не должно содержаться одинаковых переменных.
  3. В каждой элементарной КНФ должны содержаться все переменные, входящих в нее ДНФ, при этом их порядок должен полностью совпадать.

Любую булеву формулу в алгебре логики, не являющуюся тождественно ложной, можно представить в виде СНДФ, но только в одном единственном виде.

Правила построения СДНФ

Если существует определённый набор переменных, при котором значение функции равно единице, то можно записать произведения, учитывая, что переменные, значение которых больше нуля, нужно брать с отрицанием.

Алгоритм построения будет следующим:

  1. В таблице отмечаются все те наборы переменных, при которых \[f=0\]
  2. Для каждого отмеченного набора всех переменных записывается ДНФ, при этом если значение какой-либо из них равно нулю, то включается сама переменная, в любом другом случае ее нужно инвертировать.
  3. В конце все полученные дизъюнкции связываются друг с другом операциями конъюнкции.

Нет времени решать самому?

Наши эксперты помогут!

Контрольная

| от 300 ₽ |

Реферат

| от 500 ₽ |

Курсовая

| от 1 000 ₽ |

Примеры нахождения СКНФ и СДНФ

Рассмотрим несколько примеров нахождения СКНФ и СДНФ с помощью данных таблицы истинности.

Примеры 1 — 2

Необходимо по таблице истинности записать логическую функцию.

Примеры нахождения СКНФ и СДНФ 1

Решение. Для того чтобы выполнить задачу будем использовать правило построения СДНФ.

Примеры нахождения СКНФ и СДНФ 2

Получим СДНФ, которая имеет следующий вид:

\[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)\]
Далее будем действовать согласно правилу построения СКНФ:

Примеры нахождения СКНФ и СДНФ 3

В результате получим:

\[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)\]


 

Требуется представить функцию, которая задана в таблице в виде СДНФ и СКНФ.

Примеры нахождения СКНФ и СДНФ 4

Решение: Для начала запишем в СНДФ заданную логическую функцию. Чтобы было проще, добавим еще один вспомогательный столбец. Руководствуемся правилом составления СДНФ и учитываем, что требуется ввести знак отрицания, если значение переменной будет нулевым. Это нужно для того, чтобы они не превратили в нули основной функции значение конъюнкции.

Примеры нахождения СКНФ и СДНФ 5

Значения, которые получились во вспомогательном столбце соединяем знаком дизъюнкции, в результате чего получаем искомую логическую функцию, которая примет следующий вид:

\[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. Если пренебречь инвертированием единичных значений, то они могут превратить ДНФ в единицы основных функций.

Примеры нахождения СКНФ и СДНФ 6

Все полученные нами значения во вспомогательном столбце соединяем знаком конъюнкции и в итоге получаем логическую функцию в следующем виде.
\[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)\]
После рассмотрения примеров построения СДНФ и СКНФ с использованием таблицы истинности, стал понятен принцип построения логических функций.