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

На написание этой статьи у копирайтера, редактора, контент-менеджера и эксперта-математика ушло 30 человеко-часов.

Основные понятия и обозначения

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

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

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

Прежде чем перейти к построению СКНФ и СДНФ, рассмотрим основные понятия:

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

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

Построение СКНФ начинается с анализа строк таблицы истинности, где логическая функция принимает значение «0». 

1. Определите строки с нулевым значением функции. Выпишите все строки таблицы, в которых значение функции равно 0.
2. Постройте дизъюнкты (минтермы). Для каждой строки, где функция равна 0, формируется дизъюнкт. Если переменная принимает значение 1, записывается ее отрицание; если переменная 0 — сама переменная. Например, если в строке переменные A = 1 и B = 0, то минтерм будет выглядеть как .
3. Объедините все дизъюнкты конъюнкцией. Получившиеся дизъюнкты объединяются с помощью операции конъюнкции, формируя окончательное выражение для СКНФ.

Пример:

Рассмотрим функцию двух переменных A и B, где таблица истинности имеет следующие строки:

A = 0, B = 0 → F = 1

A = 0, B = 1 → F = 0

A = 1, B = 0 → F = 1

A = 1, B = 1 → F = 0

Здесь функция равна 0 во второй и четвертой строках. Соответствующие минтермы:

• Вторая строка (A = 0, B = 1): .
• Четвертая строка (A = 1, B = 1): .
• СКНФ для функции будет: .

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

Построение СДНФ основано на строках таблицы истинности, где функция равна «1».

1. Определите строки с единичным значением функции. Запишите все строки, в которых значение функции равно 1.
2. Постройте конъюнкты (макстермы). Для каждой строки, где функция равна 1, формируется конъюнкт. Если переменная в строке принимает значение 0, записывается ее отрицание, если 1 — сама переменная. Например, если в строке переменные A = 1 и B = 0, то конъюнкт будет .
3. Объедините все конъюнкты дизъюнкцией (операция «ИЛИ»). Полученные конъюнкты объединяются с помощью операции дизъюнкции, образуя окончательное выражение для СДНФ.

Пример:

Рассмотрим ту же функцию с таблицей истинности:

A = 0, B = 0 → F = 1   

A = 0, B = 1 → F = 0   

A = 1, B = 0 → F = 1   

A = 1, B = 1 → F = 0

Здесь функция равна 1 в первой и третьей строках. Соответствующие макстермы:

• Первая строка (A = 0, B = 0):  .
• Третья строка (A = 1, B = 0):  .
• СДНФ для функции: .

Практические советы по построению СКНФ и СДНФ

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

1. Начинайте с составления таблицы истинности

Чтобы построить СКНФ и СДНФ, всегда начинайте с таблицы истинности. Это позволит четко увидеть, в каких строках логическая функция принимает значения 1 или 0 и, соответственно, определить строки для построения конъюнктов и дизъюнктов. 

2. Внимательно следите за логикой формирования минтермов и макстермов

Для построения СКНФ используйте строки, где функция равна 0, создавая минтермы с соответствующими переменными. В минтермах переменные, равные 1, заменяются на их отрицание, а переменные, равные 0, записываются как есть.

Для СДНФ используйте строки, где функция принимает значение 1, создавая макстермы. Здесь переменные, равные 1, записываются без изменений, а переменные, равные 0, заменяются на их отрицание. Внимательно следите за каждым значением переменной, чтобы не запутаться.

3. Обозначайте переменные четко и последовательно

Для упрощения используйте одинаковое обозначение переменных и их отрицаний во всех минтермах и макстермах. Например, если A = 1 и B = 0, то записывайте это как , а не  и .

4. Объединяйте выражения с помощью конъюнкции и дизъюнкции правильно

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

5. Перепроверьте выражение

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

6. Используйте таблицы истинности или программы для проверки

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

7. По возможности упростите конечное выражение

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

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

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