СДНФ (совершенная дизъюнктивная нормальная форма) и СКНФ (совершенная конъюктивная нормальная форма) — это важные понятия в логике и булевой алгебре. Построение СДНФ и СКНФ по таблице истинности позволяет наглядно представить логическое выражение в форме, удобной для дальнейшего анализа и преобразований.
Таблица истинности показывает все возможные комбинации значений переменных и значения логического выражения при этих значениях. На основании таблицы истинности можно построить СДНФ и СКНФ с помощью следующих шагов.
1. Для построения СДНФ ищем все строки таблицы истинности, в которых результат равен 1. Для каждой такой строки формируем дизъюнкцию от значений переменных, где 1 заменяется на переменную, а 0 заменяется на отрицание переменной. Полученные дизъюнкции объединяем в конъюкцию — это и будет СДНФ. Например, если в таблице истинности есть строки (011, 101, 110), то СДНФ будет выглядеть так: (A ¬ B & C) ∨ (¬ A & B & ¬ C) ∨ (¬ A & ¬ B & C).
2. Для построения СКНФ ищем все строки таблицы истинности, в которых результат равен 0. Для каждой такой строки формируем конъюкцию от значений переменных, где 0 заменяется на переменную, а 1 заменяется на отрицание переменной. Полученные конъюкции объединяем в дизъюнкцию — это и будет СКНФ. Например, если в таблице истинности есть строки (000, 010, 100, 111), то СКНФ будет выглядеть так: (A & B & C) ∨ (A & ¬ B & C) ∨ (¬ A & B & C) ∨ (¬ A & ¬ B & ¬ C).
Что такое СДНФ и СКНФ?
СДНФ представляет собой дизъюнкцию конъюнкций переменных и их отрицаний, в которой каждая конъюнкция соответствует единице таблицы истинности логической функции. Проще говоря, СДНФ позволяет описать данную логическую функцию в виде отдельных условий, при которых она принимает значение 1.
СКНФ, напротив, представляет собой конъюнкцию дизъюнкций переменных и их отрицаний, в которой каждая дизъюнкция соответствует нулю таблицы истинности логической функции. То есть, СКНФ позволяет описать данную логическую функцию в виде комбинации условий, при которых она принимает значение 0.
Использование СДНФ и СКНФ позволяет упростить работу с логическими функциями, представлять их в более понятной и компактной форме, а также проводить различные операции с этими функциями, такие как упрощение, сравнение и доказательства эквивалентности.
Приведение логической функции к СДНФ и СКНФ является важным этапом в алгоритмах анализа и синтеза цифровых схем, построении таблиц истинности и выполнении других операций в области логического программирования.
Таблица истинности является основным методом для построения СДНФ и СКНФ, поэтому понимание этих форм и их использование может существенно улучшить понимание и решение задач в области логики и вычислительных систем.
СДНФ и СКНФ: основные понятия
СДНФ представляет собой дизъюнкцию всех элементарных конъюнкций, в которых каждое значение аргумента сочетается с функцией по отдельности. Другими словами, каждая элементарная конъюнкция в СДНФ соответствует одной строке таблицы истинности, где функция принимает значение 1.
СКНФ, напротив, представляет собой конъюнкцию всех элементарных дизъюнкций, в которых каждое значение аргумента сочетается с функцией по отдельности. Каждая элементарная дизъюнкция в СКНФ соответствует одной строке таблицы истинности, где функция принимает значение 0.
Одна и та же функция может быть записана как в СДНФ, так и в СКНФ. Описание функции в СДНФ позволяет выделить все положительные значения функции, а в СКНФ – все нулевые значения. Оба этих вида записи позволяют представить функцию в виде логических операторов И, ИЛИ и НЕ, что упрощает анализ и дальнейшую работу с функциями.
Как построить СДНФ по таблице истинности
Для построения СДНФ по таблице истинности нужно рассмотреть все строки таблицы, где значение функции равно 1, и составить дизъюнкцию литералов этих строк.
Рассмотрим пример таблицы истинности:
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Для данной таблицы истинности фукнции F построим СДНФ. Рассмотрим строки, где значение функции F равно 1:
- строка 2: A=0, B=0, C=1;
- строка 4: A=0, B=1, C=1;
- строка 5: A=1, B=0, C=0;
- строка 6: A=1, B=0, C=1;
- строка 7: A=1, B=1, C=0.
Соответственно, СДНФ для данной функции F будет выглядеть следующим образом:
F = (A’ * B’ * C) + (A’ * B * C) + (A * B’ * C’) + (A * B’ * C) + (A * B * C’)
Таким образом, мы построили СДНФ по таблице истинности для данной логической функции.
Построение СКНФ по таблице истинности
Для построения СКНФ (совершенной конъюнктивной нормальной формы) по таблице истинности булевой функции необходимо выполнить следующие шаги:
- Анализируем полученную таблицу истинности, ищем строки, в которых функция принимает значение «1».
- Для каждой строки, в которой функция принимает значение «1», формируем конъюнкцию соответствующих ей литералов. Литералом может быть или переменная функции, или её отрицание.
- Объединяем все конъюнкции, полученные на предыдущем шаге, с помощью дизъюнкции.
- Полученная СКНФ будет эквивалентна исходной функции, так как она имеет значение «1» только в тех строках, где исходная функция также равна «1».
Для наглядности можно использовать таблицу, в которой строки будут соответствовать примененным конъюнкциям, а столбцы — переменным функции. В клетках таблицы вместо переменных будут указаны их значения соответствующие строкам. Значение «1» показывает, что данный литерал присутствует в данной конъюнкции, а значение «0» говорит о том, что литерал в данной конъюнкции отрицается.
| Переменная A | Переменная B | Конъюнкция |
|---|---|---|
| 0 | 0 | A̅ ∧ B̅ |
| 0 | 1 | A̅ ∧ B |
| 1 | 0 | A ∧ B̅ |
| 1 | 1 | A ∧ B |
В данном примере построена СКНФ для функции с двумя переменными A и B. Значения литералов в строках таблицы соответствуют значениям перемнных. Например, в строке 1 значение переменной A равно 0, а значение переменной B равно 0, поэтому в соответствующей конъюнкции присутствуют отрицания обеих переменных (A̅ и B̅).
Таким образом, СКНФ по таблице истинности позволяет представить булевую функцию в виде конъюнкции дизъюнкций литералов, принимающих значение «1» на соответствующих строках таблицы истинности.
Примеры построения СДНФ и СКНФ
Для наглядности рассмотрим примеры построения СДНФ и СКНФ по таблице истинности.
Пример 1:
Рассмотрим таблицу истинности функции f(x, y, z) = x + y * z.
| x | y | z | f(x, y, z) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
СДНФ (совершенная дизъюнктивная нормальная форма) для функции f(x, y, z) = x + y * z будет выглядеть следующим образом:
f(x, y, z) = (!x * !y * !z) + (!x * !y * z) + (x * !y * !z) + (x * y * z)
СКНФ (совершенная конъюнктивная нормальная форма) для функции f(x, y, z) = x + y * z будет выглядеть следующим образом:
f(x, y, z) = (x + y + z) * (!x + !y + z) * (!x + y + !z) * (x + !y + !z)
Пример 2:
Рассмотрим таблицу истинности функции f(x, y, z) = (x + !y) * (!x + z).
| x | y | z | f(x, y, z) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
СДНФ (совершенная дизъюнктивная нормальная форма) для функции f(x, y, z) = (x + !y) * (!x + z) будет выглядеть следующим образом:
f(x, y, z) = (x * !y * !z) + (x * !y * z) + (!x * !y * z) + (!x * y * !z)
СКНФ (совершенная конъюнктивная нормальная форма) для функции f(x, y, z) = (x + !y) * (!x + z) будет выглядеть следующим образом:
f(x, y, z) = (x + !y + z) * (x + y + !z) * (!x + !y + z)