ЦЕЛИ ОБУЧЕНИЯ:
К концу этого занятия студент сможет:

1. Запомнить определение литерала и конъюнктивной и дизъюнктивной нормальных форм.
2. Идентифицировать структуры выражения в КНФ и ДНФ.
3. Использовать КНФ или ДНФ для упрощения пропозициональных логических выражений.

СОДЕРЖАНИЕ
ОПРЕДЕЛЕНИЕ ЛИТЕРАЛА
ОПРЕДЕЛЕНИЕ НОРМАЛЬНЫХ ФОРМ
ТЕОРЕМА О НОРМАЛЬНЫХ ФОРМАХ

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

Определение Литерала

Литерал — это любое атомарное выражение или его отрицание. В зависимости от этого, различают положительные и отрицательные литералы. Например, A является положительным литералом, а \neg A — отрицательным литералом.

Определение Нормальных Форм

Выражение F находится в нормальной форме конъюнктивной (КНФ), если оно может быть записано как конъюнкция дизъюнкций литералов, то есть:

\displaystyle F=\bigwedge_{i=1}^n \left( \bigvee_{j=1}^m L_{ij}\right)

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

\displaystyle F=\bigvee_{i=1}^n \left(\bigwedge_{j=1}^m L_{ij}\right)

Теорема о Нормальных Формах

Все выражения пропозициональной логики эквивалентны выражению в ДНФ и КНФ.

ДОКАЗАТЕЛЬСТВО:

Это можно доказать с помощью индукции по сложности формул F.

• Базовый случай: Если F — атомарное выражение, его можно записать одновременно в КНФ и ДНФ, потому что: F\equiv F_D \equiv F_C, где F_C:=((F\vee F)\wedge (F\vee F)) и F_D:=((F\wedge F)\vee (F\wedge F))
• Индукционный шаг: Пусть G и H — произвольные выражения, для которых теорема верна; то есть существуют H_C и G_C в КНФ, и H_D и G_D в ДНФ, такие что:

  G\equiv G_D \equiv G_D

  H\equiv H_D \equiv H_D

  Следовательно, мы можем записать:

  \displaystyle G_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} ; \displaystyle G_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC}

  \displaystyle H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{HD} ; \displaystyle H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{HC}

  Без потери общности, если F:= \neg G, тогда, используя теорему о подстановке и обобщённые законы Де Моргана, мы получаем:

  \displaystyle F:= \neg G \equiv \left\{ \begin{matrix} \neg G_D := \neg \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \equiv\bigwedge_{i=1}^n \neg \bigwedge_{j=1}^m L_{ij}^{GD} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GD} \\ \\ \neg G_C := \neg \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \neg \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GC} \end{matrix}\right.

  С другой стороны, если F:=G\wedge H, то по теореме о подстановке:

  \displaystyle F:=G\wedge H \equiv G_C \wedge H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \wedge \bigwedge_{i=1}^{n^\prime} \bigvee_{j=1}^{m^\prime} L_{ij}^{HC}

  Это конъюнктивная нормальная форма. И аналогично, если F:=H\vee G,, тогда:

  \displaystyle F:=G\wedge H \equiv G_D \vee H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \vee \bigvee_{i=1}^{\overline{n}} \bigwedge_{j=1}^{\overline{m}} L_{ij}^{HD}

  То есть, это дизъюнктивная нормальная форма.

  Следовательно, индукция завершена, и все выражения в пропозициональной логике могут быть записаны в КНФ и ДНФ.

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