Формы представления логических функций: ДНФ, КНФ, СДНФ и СКНФ

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

Содержание

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

Введение в формы представления логических функций

Формула алгебры логики — это выражение, составленное из переменных и логических операций, применённых к ним. Эти переменные могут принимать различные истинностные значения (1 или 0), что влияет на истинностное значение всей формулы. Таким образом, значение формулы зависит от значений её составных переменных и от выбранной логической структуры, определяемой применяемыми операциями.

Пусть $x$ — булева переменная. Введем обозначение:

$x^{\sigma} = \begin{cases} x, & \text{если } \sigma = 1, \\ \overline{x}, & \text{если } \sigma = 0, \end{cases}$

где параметр $\sigma \in \{0, 1\}$ .

Пусть $x_{1}, x_{2}, \ldots, x_{n}$ — булевы переменные, тогда формулы алгебры логики

$x_{i_{1}}^{\sigma_{1}} \land x_{i_{2}}^{\sigma_{2}} \land \ldots \land x_{i_{q}}^{\sigma_{p}} \quad \text{и} \quad x_{i_{1}}^{\sigma_{1}} \vee x_{i_{2}}^{\sigma_{2}} \vee \ldots \vee x_{i_{q}}^{\sigma_{m}}$

где $i_{q} \in \{1, 2, \ldots, n\}$ , $\sigma_{q} \in \{0, 1\},$ называются соответственно элементарной конъюнкцией и элементарной дизъюнкцией на множестве булевых переменных $\{x_{1}, x_{2}, \ldots, x_{n}\}$ .

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

Для удобства визуального восприятия можно заменить значок конъюнкции на логическое умножение: « $\bullet$ ».

Например, $k_{1} = x_{1}\overline{x}_{2}x_{3}$ — элементарная конъюнкция 3-го ранга; $d_{1} = \overline{x}_{1} \vee x_{2}$ — элементарная дизъюнкция 2-го ранга.

Формы представления логических функций

Логические функции могут быть представлены в различных формах, которые обеспечивают различные способы анализа и использования. Ниже представлены основные формы представления логических функций:

дизъюнктивная нормальная форма (ДНФ);
конъюнктивная нормальная форма (КНФ);
совершенная дизъюнктивная нормальная форма (СДНФ);
совершенная конъюнктивная нормальная форма (СКНФ).

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

Дизъюнктивная нормальная форма (ДНФ)

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

ДНФ для логической функции $f(x_{1}, x_{2}, \ldots, x_{n})$ — это логическое выражение вида:

$f(x_{1}, x_{2}, \ldots, x_{n}) = k_{1} \vee k_{2} \vee \ldots \vee k_{m},$

где каждый $k_{i}$ представляет собой конъюнкцию переменных $x_{1}, x_{2}, \ldots, x_{n}$ или их отрицаний.

Например, формы $x_{1}\overline{x}_{2} \vee x_{3}$ , $x_{3}x_{1} \vee x_{2}\overline{x}_{3}$ , $x_{1}$ , $\overline{x}_{3}$ — дизъюнктивные нормальные формы, а $\overline{x}_{3}(x_{1} \vee x_{2})$ — нет.

Всякая логическая функция, отличная от константы 0, может быть сведена к ДНФ.

Для получения ДНФ необходимо:

записать булеву функцию в виде $\{\vee, \bullet, \overline{\phantom{x}} \}$ ;
с помощью законов де Моргана $\overline{A \land B} \equiv \overline{A} \vee \overline{B}$ ; $\overline{A \vee B} \equiv \overline{A} \land \overline{B}$ освободиться от общих отрицаний (знак отрицания должен стоять над отдельными переменными), если есть необходимость, то воспользоваться законом двойного отрицания $\overline{\overline{A}} = A$ ;
с помощью закона дистрибутивности $A \land (B \vee C) \equiv (A \land B) \vee (A \land C)$ раскрываются все скобки и проводится поглощение.

Полученная форма удовлетворяет определению ДНФ.

Пример. С помощью эквивалентных преобразований привести к ДНФ формулу $f(x, y, z) = (x \downarrow y) \vee z$ .

Решение.

$(x \downarrow y) \lor z \mathop{\equiv}\limits^{15} \overline{(x \lor y)} \lor z \mathop{\equiv}\limits^{8.2} (\overline{x} \, \overline{y}) \lor z.$

Представление булевой функции в виде ДНФ неоднозначно. Например, для функции $f(x, y, z) = (x \downarrow y) \vee z$ , кроме представленной выше, будут равносильные между собой следующие ДНФ: $\overline{x} \, \overline{y} \vee \overline{x}yz \vee xz$ ; $\overline{x} \, \overline{y} \vee yz \vee x\overline{y}z$ .

Совершенная дизъюнктивная нормальная форма (СДНФ)

Если ДНФ функции $f_{1}(x_{1}, x_{2}, \ldots, x_{n})$ от $n$ переменных в каждой своей конъюнкции содержит все $n$ переменных или их отрицания, то это совершенная дизъюнктивная нормальная форма (СДНФ).

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

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

Каждый такой набор переменных соответствует конъюнкции, причем если переменная $x_{i} = 1$ , то $x_{i}$ входит в нее без отрицания, если $x_{i} = 0$ , то $x_{i}$ входит в нее с отрицанием $\overline{x}_{i}$ :

$f(x_{1}, \ldots, x_{n}) = \bigvee_{f(\sigma_{1}, \ldots, \sigma_{n}) = 1} \left( x_{1}^{\sigma_{1}} x_{2}^{\sigma_{2}} \ldots x_{n}^{\sigma_{n}} \right),$

где дизъюнктивная сумма берется по всем наборам $(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{n})$ , для которых $f(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{n}) = 1$ ; $x_{i}^{\sigma_{i}} = x_{i}$ при $\sigma_{i} = 1$ и $x_{i}^{\sigma_{i}} = \overline{x}_{i}$ при $\sigma_{i} = 0$ ; $f(x_{1}, \ldots, x_{n}) \neq 0$ .

Построим СДНФ для функции $F(x_{1}, x_{2}, x_{3}) = (x \downarrow y) \vee z$ по таблице истинности.

$x$	$y$	$z$	$x \downarrow y$	$(x \downarrow y) \vee z$
0	0	0	1	1
0	0	1	1	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	0	0
1	1	1	0	1

СДНФ(F) = $000 \vee 001 \vee 011 \vee 101 \vee 111$ =

$= \overline{x}\,\overline{y}\,\overline{z} \vee \overline{x}\,\overline{y}z \vee \overline{x}yz \vee x\overline{y}z \vee xyz.$

Аналитический вывод для СДНФ состоит из четырех шагов:

привести функцию к виду ДНФ;
каждую конъюнкцию, где меньше чем $n$ переменных, умножить на $1 = x_{i} \vee \overline{x}_{i}$ ;
раскрыть скобки с помощью закона дистрибутивности;
по закону идемпотентности убрать лишнее.

Для функции $F(x_{1}, x_{2}, x_{3}) = (x \downarrow y) \vee z$ аналитический вывод выглядит следующим образом:

$(x \downarrow y) \lor z \mathop{\equiv}\limits^{15} \overline{(x \lor y)} \lor z \mathop{\equiv}\limits^{8.2} \overline{x} \, \overline{y} \lor z \mathop{\equiv}\limits^{4.3}$

$\mathop{\equiv}\limits^{4.3} \overline{x} \, \overline{y} \cdot 1 \lor 1 \cdot 1 \cdot z \mathop{\equiv}\limits^{3.2} \overline{x} \, \overline{y} \cdot (z \lor \overline{z}) \lor (x \lor \overline{x}) \cdot (y \lor \overline{y}) \cdot z \mathop{\equiv}\limits^{7.2}$

$\mathop{\equiv}\limits^{7.2} \overline{x} \, \overline{y} \, z \lor \overline{x} \, \overline{y} \, \overline{z} \lor (x \lor \overline{x}) \cdot (y \, z \lor \overline{y} \, z) \mathop{\equiv}\limits^{7.2}$

$\mathop{\equiv}\limits^{7.2} \overline{x} \, \overline{y} \, z \lor \overline{x} \, \overline{y} \, \overline{z} \lor x \, y \, z \lor \overline{x} \, y \, z \lor x \, \overline{y} \, z \lor \overline{x} \, \overline{y} \, z \mathop{\equiv}\limits^{2.2}$

$\mathop{\equiv}\limits^{2.2} \overline{x} \, \overline{y} \, z \lor \overline{x} \, \overline{y} \, \overline{z} \lor x \, y \, z \lor \overline{x} \, y \, z \lor x \, \overline{y} \, z.$

Обратите внимание: для константы 0 не существует СДНФ, так как нет ни одного набора переменных, на котором она была бы определена, как истинная.

Конъюнктивная нормальная форма (КНФ)

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

КНФ для логической функции $f(x_{1}, x_{2}, \ldots, x_{n})$ — это логическое выражение вида:

$f(x_{1}, x_{2}, \ldots, x_{n}) = d_{1} \land d_{2} \land \ldots \land d_{m},$

где каждый $d_{i}$ представляет собой дизъюнкцию переменных $x_{1}, x_{2}, \ldots, x_{n}$ или их отрицаний.

Например, формы $(x_{1} \vee \overline{x}_{2})x_{3}$ , $x_{1}\overline{x}_{2}(x_{3} \vee x_{1})$ , $\overline{x}_{3}$ , $x_{1}$ , $x_{1} \vee \overline{x}_{3}$ — конъюнктивные нормальные формы, а $x_{1}(x_{1}\overline{x}_{3} \vee x_{2})$ — нет.

Всякая логическая функция, отличная от константы единицы, может быть сведена к КНФ.

Для получения КНФ необходимо:

записать булеву функцию в виде $\{\vee, \bullet, \overline{\phantom{x}} \}$ ;
с помощью законов де Моргана $\overline{A \land B} \equiv \overline{A} \vee \overline{B}$ ; $\overline{A \vee B} \equiv \overline{A} \land \overline{B}$ освободиться от общих отрицаний (знак отрицания должен стоять над отдельными переменными), если есть необходимость, то воспользоваться законом двойного отрицания $\overline{\overline{A}} = A$ ;
с помощью закона дистрибутивности $A \vee (B \land C) \equiv (A \vee B) \land (A \vee C)$ раскрываются все скобки, и проводится поглощение.

Полученная форма удовлетворяет определению КНФ.

Пример. С помощью эквивалентных преобразований привести к КНФ формулу $f(x, y, z) = (x \downarrow y) \vee z$ .

Решение.

Представление булевой функции в виде КНФ неоднозначно. Например, для функции $f(x, y, z) = (x \downarrow y) \vee z$ , кроме представленной выше, будут равносильные между собой следующие КНФ: $(\overline{y} \vee z)(\overline{x} \vee y \vee z)$ ; $(x \vee \overline{y} \vee z)(\overline{x} \vee z)$ .

Совершенная конъюнктивная нормальная форма (СКНФ)

Если КНФ функции $f_{1}(x_{1}, x_{2}, \ldots, x_{n})$ от $n$ переменных в каждой своей дизъюнкции содержит все $n$ переменных либо их отрицания, то это совершенная конъюнктивная нормальная форма (СКНФ).

Каждая функция имеет одну единственную СКНФ, которая может быть получена двумя способами: с помощью аналитического вывода, основанного на анализе структуры функции или путем составления таблицы истинности и последующего выведения СКНФ из неё.

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

Каждый такой набор переменных соответствует дизъюнкции, причем если переменная $x_{i} = 1$ , то $x_{i}$ входит в нее с отрицанием $\overline{x}_{i}$ , если $x_{i} = 0$ , то $x_{i}$ входит в нее без отрицания $x_{i}$ :

$f(x_{1}, \ldots, x_{n}) = \bigwedge_{f(\sigma_{1}, \ldots, \sigma_{n}) = 0} \left( x_{1}^{\overline{\sigma}_{1}} \vee x_{2}^{\overline{\sigma}_{2}} \vee \ldots \vee x_{n}^{\overline{\sigma}_{n}} \right),$

где конъюнктивное произведение берется по всем наборам $(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{n})$ , для которых $f(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{n}) = 0$ ; $x_{i}^{\sigma_{i}} = x_{i}$ при $\sigma_{i} = 0$ и $x_{i}^{\sigma_{i}} = \overline{x}_{i}$ при $\sigma_{i} = 1$ ; $f(x_{1}, \ldots, x_{n}) \neq 1$ .

Построим СКНФ для функции $F(x_{1}, x_{2}, x_{3}) = (x \downarrow y) \vee z$ по таблице истинности.

$x$	$y$	$z$	$x \downarrow y$	$(x \downarrow y) \vee z$
0	0	0	1	1
0	0	1	1	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	0	0
1	1	1	0	1

СКНФ(F) = $\overline{010} \cdot \overline{100} \cdot \overline{110}$ =

$= (x \vee \overline{y} \vee z)(\overline{x} \vee y \vee z)(\overline{x} \vee \overline{y} \vee z).$

Аналитический вывод для СКНФ состоит из пяти шагов:

привести функцию к виду КНФ;
все конъюнкции через второй закон дистрибутивности преобразовать к виду КНФ;
к каждой дизъюнкции, где меньше, чем $n$ переменных, прибавить $0 = x_{i} \cdot \overline{x}_{i}$ ;
убрать скобки с помощью второго закона дистрибутивности;
по закону идемпотентности убрать лишнее.

Для функции $F(x_{1}, x_{2}, x_{3}) = (x \downarrow y) \vee z$ , аналитический вывод СКНФ выглядит следующим образом:

$(x \downarrow y) \vee z \mathop{\equiv}\limits^{15} \overline{x \vee y} \vee z \mathop{\equiv}\limits^{8.2} \overline{x}\,\overline{y} \vee z \mathop{\equiv}\limits^{7.1} (\overline{x} \vee z)(\overline{y} \vee z) \mathop{\equiv}\limits^{4.2} (\overline{x} \vee 0 \vee z)(0 \vee \overline{y} \vee z) \mathop{\equiv}\limits^{3.1}$

$\mathop{\equiv}\limits^{3.1} (\overline{x} \vee y\overline{y} \vee z)(x\overline{x} \vee \overline{y} \vee z) \mathop{\equiv}\limits^{7.1} (\overline{x} \vee y \vee z)(\overline{x} \vee \overline{y} \vee z)(x \vee \overline{y} \vee z)(\overline{x} \vee \overline{y} \vee z) \mathop{\equiv}\limits^{2.1}$

$\mathop{\equiv}\limits^{2.1} (\overline{x} \vee y \vee z)(\overline{x} \vee \overline{y} \vee z)(x \vee \overline{y} \vee z).$

Обратите внимание: для константы 1 не существует СКНФ, так как нет ни одного набора переменных, на котором она была бы определена, как ложная.

Задания для самостоятельной работы

2.6.1. С помощью эквивалентных преобразований привести формулу $(x \leftrightarrow y) \vee (\overline{zx})$ к ДНФ, КНФ; построить СДНФ и СКНФ используя аналитический вывод и таблицу истинности.

2.6.2. С помощью эквивалентных преобразований привести формулу $(x \downarrow \overline{y}) \rightarrow (\overline{z} \vee (xy))$ к ДНФ, КНФ; построить СДНФ и СКНФ используя аналитический вывод и таблицу истинности.

2.6.3. С помощью эквивалентных преобразований привести формулу $(x(y \rightarrow z)) \vee (\overline{z} \vee xy)$ к ДНФ, КНФ; построить СДНФ и СКНФ используя аналитический вывод и таблицу истинности.

2.7.52. С помощью эквивалентных преобразований привести формулу $(xy \rightarrow z) \vee (x \leftrightarrow z)(xy \downarrow z)$ к ДНФ, КНФ; построить СДНФ и СКНФ используя аналитический вывод и таблицу истинности.

2.7.53. С помощью эквивалентных преобразований привести формулу $\left( x|y \right) \rightarrow \left( y \leftrightarrow \overline{z}x \right) \vee \left( \overline{y}\oplus z \right)$ к ДНФ, КНФ; построить СДНФ и СКНФ используя аналитический вывод и таблицу истинности.

2.7.54. С помощью эквивалентных преобразований привести формулу $(xz \downarrow y) \rightarrow \left( \overline{xy} \vee z \right)\left( z\left( x\oplus\overline{y} \right) \right)$ к ДНФ, КНФ; построить СДНФ и СКНФ используя аналитический вывод и таблицу истинности.