Как составить коньюктивную нормальную форму (КНФ) и дизъюнктивную нормальную форму (ДНФ) для логического выражения с примерами

Цели статьи:

Логические выражения являются неотъемлемой частью информатики и математики. Они позволяют описывать различные условия и отношения между объектами и явлениями. Составление КНФ (конъюнктивной нормальной формы) и ДНФ (дизъюнктивной нормальной формы) логического выражения – одна из важных задач в логике и алгебре. В данной статье мы рассмотрим, что такое КНФ и ДНФ, как их составить для логического выражения и приведем примеры.

Что такое КНФ и ДНФ?

Конъюнктивная нормальная форма (КНФ) и дизъюнктивная нормальная форма (ДНФ) – это формы представления логического выражения, в которых используются операции конъюнкции (логическое «И») и дизъюнкции (логическое «ИЛИ»). КНФ представляет выражение в виде конъюнкции набора дизъюнкций, а ДНФ – в виде дизъюнкции набора конъюнкций. Такое представление удобно для работы с выражением и его упрощения.

Как составить КНФ для логического выражения?

Чтобы составить КНФ для логического выражения, необходимо разбить его на элементарные логические функции (операции), затем сформировать дизъюнкцию, объединив эти функции в одно логическое выражение с помощью операции конъюнкции. Если возможно, логические функции приводятся к простейшим формам, например, к функции, содержащей только переменные и их отрицания.

Как составить ДНФ для логического выражения?

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

Определение КНФ и ДНФ

Пример КНФ: (A И B ИЛИ ¬C) И (D ИЛИ E ИЛИ F)

Дизъюнктивная нормальная форма (ДНФ) — это форма представления логических выражений, где они представляются в виде дизъюнкции (логического ИЛИ) нескольких конъюнкций (логического И) литералов или их отрицаний.

Пример ДНФ: (A ИЛИ B ИЛИ C) И (D ИЛИ E ИЛИ ¬F)

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

Как составить КНФ

Для составления КНФ следует выполнить следующие шаги:

1. Приведите логическое выражение к нормальной форме.
2. Разделите все части выражения на простые логические выражения.
3. Представьте каждое простое логическое выражение в виде конъюнкции или дизъюнкции соответствующих булевых переменных и их отрицаний.
4. Объедините все простые логические выражения в одно выражение с использованием конъюнкции.

Например, пусть дано логическое выражение (A ИЛИ B) И (Не C). Сначала приведем его к нормальной форме: A ∧ (¬C) ∧ B. Затем разделим выражение на простые выражения: A, (¬C), B. И, наконец, представим каждое простое логическое выражение в виде КНФ: (A ИЛИ A) ∧ (¬C ИЛИ ¬C) ∧ (B ИЛИ B).

Таким образом, КНФ для данного логического выражения будет: (A ИЛИ A) И (¬C ИЛИ ¬C) И (B ИЛИ B).

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

КНФ (конъюнктивная нормальная форма) представляет собой логическое выражение, состоящее из конъюнкций (ИЛИ) литералов (переменных или их отрицаний). Составление КНФ для логического выражения осуществляется при помощи операций понижения приоритета и заключения в скобки.

Рассмотрим пример, пусть имеется логическое выражение: (A ∨ B) ∧ (C → A). Чтобы составить КНФ для данного выражения, нужно выполнить следующие шаги:

1. Разложить импликацию (→) по формуле: (C → A) = ¬C ∨ A.

2. Применить дистрибутивность (∧ и ∨): (A ∨ B) ∧ (¬C ∨ A) = (A ∧ (¬C ∨ A)) ∨ (B ∧ (¬C ∨ A)).

3. Упростить с помощью законов ассоциативности и дистрибутивности: (A ∧ (¬C ∨ A)) ∨ (B ∧ (¬C ∨ A)) = (A ∨ (B ∧ (¬C ∨ A))).

Таким образом, полученное выражение (A ∨ (B ∧ (¬C ∨ A))) является КНФ для исходного логического выражения (A ∨ B) ∧ (C → A).

Как составить ДНФ

ДНФ (дизъюнктивная нормальная форма) представляет логическое выражение в виде дизъюнкции (логического ИЛИ) различных конъюнкций (логического И). ДНФ позволяет представить все возможные комбинации значений переменных в выражении.

Для составления ДНФ необходимо выполнить следующие шаги:

1. Записать все возможные комбинации значений переменных. Например, если в выражении есть две переменные A и B, то возможные комбинации будут: A=0, B=0; A=0, B=1; A=1, B=0; A=1, B=1.
2. Для каждой комбинации значений переменных выяснить, когда логическое выражение принимает значение 1 (истина).
3. Записать каждую комбинацию значений, для которой выражение принимает значение 1, как конъюнкцию этих значений. Например, если для комбинации A=1, B=0 выражение принимает значение 1, то записываем эту комбинацию как A∧¬B.
4. Соединить все конъюнкции (комбинации значений переменных, для которых выражение принимает значение 1) с помощью дизъюнкции (логического ИЛИ).

Пример:

Дано логическое выражение: A ∧ (B ∨ C)

Шаг 1: Все возможные комбинации значений переменных A, B и C:

Шаг 2: Определяем значения выражения для каждой комбинации:

Шаг 3: Записываем ДНФ по выражению:

A∧¬B∧¬C ∨ A∧¬B∧C ∨ A∧B∧¬C ∨ A∧B∧C

Таким образом, ДНФ для данного логического выражения будет A∧¬B∧¬C ∨ A∧¬B∧C ∨ A∧B∧¬C ∨ A∧B∧C.

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

Рассмотрим пример: дано логическое выражение F = (А ИЛИ Б) И НЕ(С И D).

Для составления ДНФ выполним следующие шаги:

1. Раскроем скобки: F = (А ИЛИ Б) И НЕ(С И D) = (А ИЛИ Б) И (НЕС И НЕD).
2. Запишем таблицу истинности для (А ИЛИ Б) и (НЕС И НЕD):
• (А ИЛИ Б):
• • А Б Результат
  • 0 0 0
  • 0 1 1
  • 1 0 1
  • 1 1 1
• (НЕС И НЕD):
• • С D Результат
  • 0 0 1
  • 0 1 0
  • 1 0 0
  • 1 1 0
3. Получаем ДНФ:
• Для (А ИЛИ Б):
• (А ИЛИ Б) = АБ + АНЕБ + НЕАБ
• Таким образом, (А ИЛИ Б) = АБ + АНЕБ + НЕАБ
• Для (НЕС И НЕD):
• (НЕС И НЕD) = НЕСНЕD
• Таким образом, (НЕС И НЕD) = НЕСНЕD
• Совмещаем получившиеся слагаемые:
• Таким образом, ДНФ для выражения F = (А ИЛИ Б) И НЕ(С И D):
• Ф = (АБ + АНЕБ + НЕАБ)И(НЕСНЕD)

В результате мы составили ДНФ для логического выражения F = (А ИЛИ Б) И НЕ(С И D). Это выражение удобно использовать для определения условий, при которых функция принимает значение 1.