ЦЕЛИ ОБУЧЕНИЯ:
После завершения этого урока студент сможет:

1. Применить алгоритм ДНФ/КНФ к конкретным выражениям для нахождения их конъюнктивных и дизъюнктивных нормальных форм.
2. Понять использование простых и составных переключателей в пропозиционной логике.
3. Определить структуру составных переключателей и черных ящиков.
4. Использовать таблицу истинности для обобщения информации об устройстве.
5. Извлечь ДНФ и КНФ устройства из его таблицы истинности.
6. Спроектировать составной переключатель, выполняющий ту же функцию, что и данное устройство.

СОДЕРЖАНИЕ
АЛГОРИТМ ДНФ/КНФ
АЛГОРИТМ ПОЛУЧЕНИЯ НОРМАЛЬНОЙ ФОРМЫ ИЗ ТАБЛИЦ ИСТИННОСТИ: ЧЕРНЫЕ ЯЩИКИ И СОСТАВНЫЕ ПЕРЕКЛЮЧАТЕЛИ
ПРИМЕРНЫЕ УПРАЖНЕНИЯ

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

Алгоритм ДНФ/КНФ

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

• ШАГ 1: Замените все подвыражения вида (F\rightarrow G) на (\neg F\vee G), аналогично замените (F\leftrightarrow G). Повторяйте этот шаг до тех пор, пока все импликации и двойные импликации не будут устранены.
• ШАГ 2: Устраните двойные отрицания и примените законы Де Моргана, где это возможно. Следует применить следующие замены
  • \neg\neg G \longmapsto G
  • \neg(G\wedge H) \longmapsto (\neg G \vee \neg H)
  • \neg(G\vee H) \longmapsto (\neg G \wedge \neg H)

    Когда больше не останется подвыражений вида \neg\neg G, \neg(G \wedge H) или \neg(G \vee H), перейдите к шагу 3.

• ШАГ 3: Этот шаг разделяется на две части в зависимости от того, хотите ли вы получить ДНФ или КНФ
  • Если вы хотите получить КНФ:

    Используйте \vee-распределение там, где это возможно. То есть, следует применить следующие замены:

    \left.\begin{matrix}G\vee(H\wedge K) \\ \\ (H\wedge K)\vee G \end{matrix} \right\} \longmapsto (G\vee H)\wedge (G\vee K)

    Когда больше не останется выражений вида G\vee(H\wedge K) или (H\wedge K)\vee G, будет получена КНФ.

  • Если вы хотите получить ДНФ:

    Используйте \wedge-распределение там, где это возможно. То есть, следует применить следующие замены:

    \left.\begin{matrix}G\wedge(H\vee K) \\ \\ (H\vee K)\wedge G \end{matrix} \right\} \longmapsto (G\wedge H)\vee (G\vee K)

    Когда больше не останется выражений вида G\wedge(H\vee K) или (H\vee K)\wedge G, будет получена ДНФ.

Примеры

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

1. (A\rightarrow (B\rightarrow A)) [РЕШЕНИЕ]
2. ((A\vee B)\rightarrow(\neg B \wedge A)) [РЕШЕНИЕ]

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

Алгоритм ДНФ/КНФ позволяет нам найти эквивалентное выражение в нормальной форме для любого выражения в пропозиционной логике. Но существуют ситуации, когда у нас нет исходного выражения, с которым можно работать. Это происходит, когда у нас есть результат таблицы истинности некоторого выражения F, структура которого нам неизвестна. Объяснение этого словами — долгий процесс; однако техника лучше всего понимается путем показа примеров ее разработки, поэтому я оставлю несколько примеров, которые я разберу на видео, но сначала вы должны просмотреть следующие понятия:

• Провод: Средство, по которому передается сигнал
• Узел: Точка, где сходятся 3 или более проводов.
• Простой переключатель: Устройство, которое допускает состояния включено (1) и выключено (0), и всегда находится в одном, и только одном из этих состояний. Включенное состояние позволяет сигналу пройти, а выключенное состояние препятствует этому.
• Составной переключатель: Это устройство, состоящее из простых переключателей и проводов.
• Черный ящик: Это любое устройство, внутренняя структура которого не видна.

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

Схема конъюнкции

Схема дизъюнкции

Примерные упражнения

1. Устройство состоит из черного ящика и 4 упорядоченных переключателей. Активация устройства происходит при следующих условиях
   • Условие 1: Оно активируется, если два последовательных переключателя включены. Это условие перестает работать, если три последовательных переключателя включены.
   • Условие 2: Оно активируется, если все переключатели выключены.
   • Исключение: Если предыдущие условия не выполняются, то устройство выключается.

   a) Суммируйте эту информацию в таблице истинности [РЕШЕНИЕ]

   b) Из таблицы истинности извлеките ДНФ и КНФ, которые воспроизводят работу устройства. [РЕШЕНИЕ]

   c) Используйте КНФ или ДНФ, полученные на предыдущем шаге (наиболее простой), для проектирования составного переключателя, выполняющего ту же функцию, что и устройство. [РЕШЕНИЕ]

2. То же самое, что и в предыдущем упражнении, но теперь устройство имеет 5 переключателей. [ЗАДАНИЕ ДЛЯ ЧИТАТЕЛЯ]