Каноническая форма булевой функции
Каноническая форма булевой функции — это однозначная запись функции через полные наборы переменных: минтермы используют для построения совершенной дизъюнктивной нормальной формы, а макстермы — для совершенной конъюнктивной нормальной формы. Такая запись особенно удобна, когда функция задана таблицей истинности и требуется восстановить её формулу.
Основные понятия
Пусть задана булева функция \(F(x_1,x_2,\ldots,x_n)\), аргументы которой принимают значения 0 или 1. В таблице истинности имеется \(2^n\) строк — по одной для каждого набора значений переменных. Каноническая форма строится так, чтобы каждый набор был представлен отдельным элементом формулы.
Полным набором называют конъюнкцию или дизъюнкцию, в которую входят все переменные функции, причём каждая переменная встречается ровно один раз — либо сама, либо с отрицанием. Например, \(x\cdot\overline{y}\cdot z\) — полный конъюнктивный набор, а \(x\vee\overline{y}\vee z\) — полный дизъюнктивный набор.
Минтерм — конъюнкция всех переменных функции, принимающая значение 1 ровно на одном полном наборе. Если в строке таблицы переменная равна 1, в минтерм записывают её без отрицания; если равна 0 — с отрицанием. Страница «Минтерм» объясняет это правило подробнее.
Макстерм — дизъюнкция всех переменных функции, принимающая значение 0 ровно на одном полном наборе. Для макстерма правило противоположное: переменную со значением 0 записывают без отрицания, а переменную со значением 1 — с отрицанием. См. «Макстерм».
Совершенная дизъюнктивная нормальная форма
Совершенная дизъюнктивная нормальная форма, или СДНФ, — это дизъюнкция минтермов. Чтобы получить её из таблицы истинности, выбирают строки, в которых \(F=1\), и для каждой такой строки составляют минтерм. Затем все полученные минтермы соединяют операцией ИЛИ.
В записи через номера используют обозначение \(F=\Sigma m(i_1,i_2,\ldots)\), где \(i_1,i_2,\ldots\) — номера строк, в которых функция равна 1. Нумерация обычно начинается с 0 и соответствует двоичному числу, составленному из значений переменных в порядке \(x_1x_2\ldots x_n\).
Для каждой строки таблицы, где \(F=1\), выпишите минтерм. Значения 1 замените переменными без отрицания, значения 0 — отрицанными переменными. Соедините все минтермы знаком \(\vee\).
Совершенная конъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма, или СКНФ, — это конъюнкция макстермов. Для её построения выбирают строки, в которых \(F=0\), составляют по ним макстермы и соединяют макстермы операцией И.
В сокращённой записи используют \(F=\Pi M(j_1,j_2,\ldots)\), где указаны номера строк с нулевым значением функции. В отличие от СДНФ, здесь рассматриваются именно нулевые строки.
Для каждой строки таблицы, где \(F=0\), выпишите макстерм. Значения 0 замените переменными без отрицания, значения 1 — отрицанными переменными. Соедините все макстермы знаком \(\wedge\).
| Значение переменной в строке | В минтерме | В макстерме |
|---|---|---|
| 0 | \(\overline{x}\) | \(x\) |
| 1 | \(x\) | \(\overline{x}\) |
Какой минтерм соответствует набору \((x,y,z)=(1,0,1)\)?
Алгоритм и разобранный пример
Рассмотрим функцию трёх переменных \(F(x,y,z)\), заданную таблицей истинности. Нумеруем строки двоичными кодами \(xyz\): от \(000\) до \(111\).
| x | y | z | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Единицы стоят в строках с номерами 1, 3, 4 и 7. Поэтому СДНФ будет состоять из четырёх минтермов. Нули стоят в строках 0, 2, 5 и 6, поэтому СКНФ будет состоять из четырёх макстермов.
Для рассмотренной таблицы \(F=\Sigma m(1,3,4,7)=\Pi M(0,2,5,6)\). Первая запись обозначает СДНФ по единичным строкам, вторая — СКНФ по нулевым строкам.
Свойства канонической формы
Канонические формы являются частным случаем нормальных форм. В СДНФ каждый элемент — минтерм, а между элементами стоит дизъюнкция. В СКНФ каждый элемент — макстерм, а между ними стоит конъюнкция. Внутри минтерма действует И, внутри макстерма — ИЛИ.
Для фиксированного порядка переменных СДНФ и СКНФ булевой функции определяются её таблицей истинности однозначно. Разные перестановки слагаемых или множителей дают ту же форму, но новых наборов в ней быть не должно.
Если функция равна 1 на всех наборах, её СДНФ содержит все \(2^n\) минтермов, а СКНФ пуста и равна 1. Если функция равна 0 на всех наборах, её СКНФ содержит все макстермы, а СДНФ пуста и равна 0.
1. В СДНФ выбирают строки с \(F=0\) вместо строк с \(F=1\). 2. Для макстерма применяют правило минтерма: это меняет результат. 3. Пропускают переменную — такой набор уже не является полным. 4. Путают номер строки: двоичный код \(xyz\) нужно переводить в десятичное число в том же порядке переменных. 5. При записи СКНФ используют \(\vee\) между скобками вместо \(\wedge\).
Подставьте в минтерм его набор: он должен дать 1. Подставьте тот же набор в любой другой минтерм — должен получиться 0. Для макстерма проверка обратная: на своём наборе он равен 0, на остальных — 1.
Как не перепутать обозначения
- СДНФ ищет единицы таблицы и соединяет минтермы знаком \(\vee\).
- СКНФ ищет нули таблицы и соединяет макстермы знаком \(\wedge\).
- В минтерме 1 — без черты, 0 — с чертой.
- В макстерме 0 — без черты, 1 — с чертой.
- Каждый минтерм и макстерм содержит все переменные ровно по одному разу.
Проверь себя
Главное
- Каноническая форма строится непосредственно по таблице истинности.
- СДНФ — дизъюнкция минтермов, составленная по строкам с \(F=1\).
- СКНФ — конъюнкция макстермов, составленная по строкам с \(F=0\).
- В минтерме единица записывается без отрицания, а в макстерме — с отрицанием; для нуля правила обратны.
- Записи \(\Sigma m\) и \(\Pi M\) содержат номера единичных и нулевых строк соответственно.