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

Предмет: Математическая логика, дискретная математика

Раздел: Алгебра логики (логические выражения), нормальные формы логических формул

Задание: Привести данное логическое выражение к дизъюнктивной нормальной форме (ДНФ) и конъюнктивной нормальной форме (КНФ).

Дано выражение:

¬((¬A ∨ A & B & ¬C) ∨ ¬(¬B ∨ C) & (¬A ∨ B))

Алгоритм преобразования в нормальные формы:

Чтобы формулу привести как в ДНФ, так и в КНФ, необходимо пройти через несколько шагов.

Шаг 1. Избавление от эквивалентности и импликации

Так как в заданной формуле нет выражений с эквивалентностью или импликацией, этот шаг можно пропустить.

Шаг 2. Применение правил де Моргана

Нам нужно избавиться от отрицаний перед сложными выражениями и продвинуть отрицания вплоть до атомов с использованием правил де Моргана.

1. Первоначально применим правило де Моргана для внешнего отрицания:

   ¬(X ∨ Y) = ¬X & ¬Y

   Таким образом:

   ¬((¬A ∨ A & B & ¬C) ∨ ¬(¬B ∨ C) & (¬A ∨ B)) = (¬(¬A ∨ A & B & ¬C)) & ¬(¬(¬B ∨ C) & (¬A ∨ B)).

2. Теперь применим правило де Моргана отдельно к каждому подвыражению.

   Первое подвыражение:

   ¬(¬A ∨ (A & B & ¬C)) = ¬¬A & ¬(A & B & ¬C).

   Теперь воспользуемся тем, что ¬¬A = A:

   A & ¬(A & B & ¬C).

   Применим правило де Моргана к отрицанию конъюнкции:

   ¬(A & B & ¬C) = ¬A ∨ ¬B ∨ C.

   Таким образом, первое подвыражение преобразуется в:

   A & (¬A ∨ ¬B ∨ C).

3. Второе подвыражение:

   ¬(¬(¬B ∨ C) & (¬A ∨ B)).

   Сначала воспользуемся правилом де Моргана для отрицания конъюнкции:

   ¬(X & Y) = ¬X ∨ ¬Y.

   Получаем:

   ¬¬(¬B ∨ C) ∨ ¬(¬A ∨ B).

   Теперь упростим:

   (¬B ∨ C) ∨ ¬(¬A ∨ B).

   Применим правило де Моргана к выражению ¬(¬A ∨ B):

   ¬(¬A ∨ B) = ¬¬A & ¬B = A & ¬B.

   В итоге второе подвыражение примет вид:

   (¬B ∨ C) ∨ (A & ¬B).

Шаг 3. Приведение выражений к дистрибутивному виду

Теперь необходимо раскрыть все скобки и преобразовать формулу как в дизъюнктивную, так и в конъюнктивную нормальные формы.

1. Первое подвыражение:

   A & (¬A ∨ ¬B ∨ C).

   Используем дистрибутивное правило:

   A & ¬A = 0, \quad A & ¬B = A & ¬B, \quad A & C = A & C.

   Получаем:

   A & ¬B ∨ A & C.

2. Второе подвыражение:

   (¬B ∨ C) ∨ (A & ¬B).

   Снова используем дистрибутивность:

   ¬B ∨ (C ∨ (A & ¬B)) = ¬B ∨ C.

Шаг 4. Полученные формы

• Дизъюнктивная нормальная форма (ДНФ) — это дизъюнкция конъюнкций:

  (A & ¬B) ∨ (A & C) ∨ (¬B ∨ C).

  Здесь каждая конъюнкция является набором простейших литералов.
• Конъюнктивная нормальная форма (КНФ) — это конъюнкция дизъюнкций: В данном случае мы можем переписать выражение как конъюнкцию нескольким дизъюнкций:

(A ∨ ¬A) & (¬A ∨ ¬C ∨ ¬A).