Введение в схемы, автоматы и алгоритмы

Предварительные сведения

Разбить на страницы
Показывать лекцию целиком

Булевы функции от n переменных

Булевы функцииВ отечественной литературе их также часто называют функциями алгебры логики . названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций - их аргументы и значения могут принимать всего два значения. С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.

Обозначим через $$B$$ двухэлементное множество $$\{0,1\}$$. Тогда $$B^n=\underbrace{B\times B \times \ldots \times B}_{n}$$ - это множество всех двоичных последовательностей (наборов, векторов) длины $$n$$. Булевой функцией от $$n$$ переменных (аргументов) называется любая функция $$f(x_1,\ldots, x_n): B^n \rightarrow B$$. Каждый из ее аргументов $$x_i, \ 1 \leq i \leq n,\$$ может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из $$B^n$$ также может быть 0 или 1. Обозначим через $$\mathcal{P}_n$$ множество всех булевых функций от $$n$$ переменных. Нетрудно подсчитать их число: $$|\mathcal{P}_n | = 2^{2^n}$$.

Имеется несколько различных способов представления и интерпретации булевых функций. В этом разделе мы рассмотрим табличное представление, а также представление с помощью логических формул. В лекциях 2 и 3 будет рассмотрено еще два способа представления булевых функций: логические схемы и упорядоченные бинарные диаграммы решений.

Табличное представление

Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц. Таблица для функции $$f(x_1, \ldots, x_n)$$ имеет $$n+1$$ столбец. В первых $$n$$ столбцах указываются значения аргументов $$x_1, \ldots, x_n$$, а в $$(n+1)$$ -ом столбце значение функции на этих аргументах - $$f(x_1,\ldots , x_n)$$.

Табличное представление функции $$f(x_1, \ldots, x_n)$$
$$x_1$$   .  .  .   $$x_{n-1}$$    $$x_n$$ $$f(x_1,\ldots x_{n-1}, x_n)$$

$$0$$   .  .  .   $$0$$    $$0$$

$$0$$   .  .  .   $$0$$    $$1$$

$$0$$   .  .  .   $$1$$    $$0$$

.  .  .  .  .  .

$$1$$   .  .  .   $$1$$    $$1$$

$$f(0, \ldots, 0,0)$$

$$f(0, \ldots, 0,1)$$

$$f(0, \ldots, 1,0)$$

$$\ldots$$

$$f(1, \ldots, 1,1)$$

Наборы аргументов в строках обычно располагаются в лексикографическом порядке: $$(\alpha_1, \ldots, \alpha_n) \prec (\beta_1, \ldots, \beta_n)\ \Leftrightarrow$$ существует такое $$i \in [1,n]$$, что при $$j < i\ \alpha_j = \beta_j$$, а $$\alpha_i < \beta_i$$. Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, ... , а последняя - $$2^n-1$$.

При больших $$n$$ табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблица с 1024 строками. Но для малых $$n$$ оно достаточно наглядно.

Булевы функции от 1-ой и 2-х переменных

Перечислим вначале все булевы функции от 1-ой переменной $$x_1$$. Как мы знаем, их всего четыре.

  • $$f_1(x_1)= 0$$ - константа 0;
  • $$f_2(x_1)= 1$$ - константа 1;
  • $$f_3(x_1)= x_1$$ - тождественная функция;
  • $$f_4(0)=1, f_4(1)=0$$. Эта функция называется отрицанием $$x_1$$ и обозначается $$\neg x_1$$ (используется также обозначение $$\overline{x}_1$$, а в языках программирования эта функция часто обозначается как $$NOT x_1$$ ).
    •

    В следующей таблице представлены наиболее используемые 12 (из 16) функций от 2-х переменных.

    Булевы функции от 2-х переменных
    $$x_1$$    $$x_2$$ $$f_1$$ $$f_2$$ $$f_3$$ $$f_4$$ $$f_5$$ $$f_6$$ $$f_7$$ $$f_8$$ $$f_9$$ $$f_{10}$$ $$f_{11}$$ $$f_{12}$$

    0  0

    0  1

    1  0

    1  1

    0

    0

    0

    0

    1

    1

    1

    1

    0

    0

    1

    1

    1

    1

    0

    0

    0

    1

    0

    1

    1

    0

    1

    0

    0

    0

    0

    1

    0

    1

    1

    1

    1

    1

    0

    1

    0

    1

    1

    0

    1

    0

    0

    1

    1

    1

    1

    0

    Многие из этих функций часто считаются "элементарными" и имеют собственные обозначения.

  • $$f_1(x_1,x_2)= 0$$ - константа 0;
  • $$f_2(x_1, x_2)= 1$$ - константа 1;
  • $$f_3(x_1,x_2)= x_1$$ - функция, равная 1-му аргументу;
  • $$f_4(x_1,x_2)= \neg x_1$$ - отрицание $$x_1$$ ;
  • $$f_5(x_1,x_2)= x_2$$ - функция, равная 2-му аргументу;
  • $$f_6(x_1,x_2)= \neg x_2$$ - отрицание $$x_2$$ ;
  • $$f_7(x_1,x_2)= (x_1 \wedge x_2)$$ - конъюнкция, читается " $$x_1$$ и $$x_2$$ " (используются также обозначения $$(x_1 x_2)$$, $$(x_1x_2)$$, $$\min(x_1,x_2)$$ и $$(x_1$$ AND $$x_2$$ ));
  • $$f_8(x_1,x_2)= (x_1 \vee x_2)$$ - дизъюнкция, читается " $$x_1$$ или $$x_2$$ " (используются также обозначения $$(x_1 + x_2)$$, $$\max(x_1x_2)$$ и $$(x_1$$ OR $$x_2$$ ));
  • $$f_9(x_1,x_2)= (x_1 \rightarrow x_2)$$ - импликация, читается " $$x_1$$ влечет $$x_2$$ " или "из $$x_1$$ следует $$x_2$$ " (используются также обозначения $$(x_1 \supset x_2)$$, и ( IF $$x_1$$ THEN $$x_2$$ ));
  • $$f_{10}(x_1,x_2)= (x_1 + x_2)$$ - сложение по модулю 2, читается " $$x_1$$ плюс $$x_2$$ " (используется также обозначение $$(x_1 \oplus x_2)$$ );
  • $$f_{11}(x_1,x_2)= (x_1 \sim x_2)$$ - эквивалентность, читается " $$x_1$$ эквивалентно (равносильно) $$x_2$$ " (используется также обозначение $$(x_1 \equiv x_2)$$ );
  • $$f_{12}(x_1,x_2)= (x_1 | x_2)$$ - штрих Шеффера (антиконъюнкция), иногда читается как "не $$x_1$$ и $$x_2$$ ".
    •

    В качестве элементарных функций будем также рассматривать 0-местные функции-константы 0 и 1.

    Отметим, что функции $$f_1(x_1,x_2)$$ и $$f_2(x_1,x_2)$$ фактически не зависят от значений обоих аргументов, функции $$f_3(x_1,x_2)$$ и $$f_4(x_1,x_2)$$ не зависят от значений аргумента $$x_2$$, а функции $$f_5(x_1,x_2)$$ и $$f_6(x_1,x_2)$$ не зависят от значений аргумента $$x_1$$.

    Определение 1.1. Функция $$f(x_1,\ldots, x_i,\ldots, x_n)$$ не зависит от аргумента $$x_i$$, если для любого набора значений $$\sigma_1,\ldots,\sigma_{i-1},\sigma_{i+1},\ldots, \sigma_n$$ остальных аргументов $$f$$ имеет место равенство

    $$f(\sigma_1,\ldots,\sigma_{i-1},0,\sigma_{i+1},\ldots, \sigma_n)= f(\sigma_1,\ldots,\sigma_{i-1},1,\sigma_{i+1},\ldots, \sigma_n).$$

    Такой аргумент $$x_i$$ называется фиктивным. Аргументы, не являющиеся фиктивными, называются существенными.

    Функции $$f_1(x_1,\ldots, x_n)$$ и $$f_2(x_1,\ldots, x_m)$$ называются равными, если функцию $$f_2$$ можно получить из функции $$f_1$$ путем добавления и удаления фиктивных аргументов.

    Например, равными являются одноместная функция $$f_3(x_1)$$ и двухместная функция $$f_3(x_1,x_2)$$, так как вторая получается из первой добавлением фиктивного аргумента $$x_2$$. Мы не будем различать равные функции и, как правило, будем использовать для обозначения равных функций одно и то же имя функции. В частности, это позволяет считать, что во всяком конечном множестве функций все функции зависят от одного и того же множества переменных.

    Формулы

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

    Мы будем рассматривать формулы, построенные над множеством элементарных функций $$\mathcal{B}=\{ 0, 1, \neg, \wedge, \vee, \rightarrow, +, \sim,\ | \}$$. Все эти функции, кроме констант, называются логическими связками или логическими операциями. При этом для 2-местных функций из этого списка будем использовать инфиксную запись, в которой имя логической связки помещается между 1-ым и 2-ым аргументами.

    Зафиксируем некоторое счетное множество переменных $$V=\{ X_1, X_2, \ldots \}$$. Определим по индукции множество формул над $$\mathcal{B}$$ с переменными из $$V$$. Одновременно будем определять числовую характеристику $$dep(\Phi)$$ формулы $$\Phi$$, называемую ее глубиной, и множество ее подформул.

    Определение 1.2. а) Базис индукции. 0, 1 и каждая переменная $$X_i \in V$$ является формулой глубины 0, т.е. $$dep(X_i)= dep(0)= dep(1)=0$$. Множество ее подформул состоит из нее самой.

    б) Шаг индукции. Пусть $$\Phi_1$$ и $$\Phi_2$$ - формулы, $$\circ \in \{ \wedge, \vee, \rightarrow, +, \sim,\ | \}$$. Тогда выражения $$\Phi= \neg \Phi_1$$ и $$\Phi= ( \Phi_1 \circ \Phi_2)$$ являются формулами. При этом $$dep(\neg \Phi_1)=1 + dep( \Phi_1)$$, а $$dep((\Phi_1 \circ \Phi_2))=1 + \max\{dep( \Phi_1), dep( \Phi_2)\}$$. Множество подформул $$\Phi$$ включает саму формулу $$\Phi$$ и для $$\Phi= \neg \Phi_1$$ все подформулы формулы $$\Phi_1$$, а для $$\Phi= ( \Phi_1 \circ \Phi_2)$$ все подформулы формул $$\Phi_1$$ и $$\Phi_2$$.

    Каждой формуле $$\Phi(X_1,\ldots, X_n)$$ сопоставим булеву функцию, которую эта формула задает, используя индукцию по глубине формулы.

    Базис индукции. Пусть $$dep(\Phi)=0$$. Тогда $$\Phi = X_i \in V$$ или $$\Phi =c \in \mathcal{B}$$ В первом случае $$\Phi$$ задает функцию $$f_{\Phi}(X_i)=X_i$$, во втором - функцию, тождественно равную константе $$c$$.

    Шаг индукции. Пусть $$\Phi$$ - произвольная формула глубины $$dep(\Phi)= k+1$$. Тогда $$\Phi(X_1,\ldots, X_n)= \neg \Phi_1(X_1,\ldots, X_n)$$ или $$\Phi(X_1,\ldots, X_n)= ( \Phi_1(X_1,\ldots, X_n) \circ \Phi_2(X_1,\ldots, X_n))$$ для некоторой булевой связки $$\circ \in \{ \wedge, \vee, \rightarrow, +, \sim,\ | \}$$. Так как $$\max \{dep( \Phi_1), dep( \Phi_2)\} \leq k$$, то формулам $$\Phi_1$$ и $$\Phi_2$$ соответствующие функции $$f_1(X_1,\ldots, X_n)$$ и $$f_2(X_1,\ldots, X_n)$$ уже сопоставлены. Тогда формула $$\neg\Phi_1$$ задает функцию $$f_{\Phi} =\neg f_1(X_1,\ldots, X_n)$$, а формула $$\Phi(X_1,\ldots, X_n)= ( \Phi_1(X_1,\ldots, X_n) \circ \Phi_2(X_1,\ldots, X_n))$$ задает функцию $$f_{\Phi} = f_1(X_1,\ldots, X_n) \circ f_2(X_1,\ldots, X_n)$$.

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

    Пример 1.1. Например, для формулы$$\Phi_1= ( (X_1 \vee \neg\neg X_2)\rightarrow (X_3 + (X_1 \wedge \neg X_2)))$$ функция $$f_{\Phi_1}$$ задается выделенным столбцом $$\rightarrow$$ следующей таблицы.

    Функция $$f_{\Phi_1}$$
    $$X_1$$   $$X_2$$   $$X_3$$ $$((X_1$$    $$\vee$$    $$\neg$$ $$\neg$$    $$X_2)$$ $$\rightarrow$$ $$(X_3$$    $$+$$    $$(X_1$$    $$\wedge\$$    $$\neg$$ $$X_2)))$$

    0 0 0

    0 0 1

    0 1 0

    0 1 1

    1 0 0

    1 0 1

    1 1 0

    1 1 1

     0  0  0 1  0

     0  0  0 1  0

     0  1  1 0  1

     0  1  1 0  1

     1  1  0 1  0

     1  1  0 1  0

     1  1  1 0  1

     1  1  1 0  1

    1

    1

    0

    1

    1

    0

    0

    1

    0  0  0  0  1  0

    1  1  0  0  1  0

    0  0  0  0  0  1

    1  1  0  0  0  1

    0  1  1  1  1  0

    1  0  1  1  1  0

    0  0  1  0  0  1

    1  1  1  0  0  1

    Каждая строка этой таблицы задает процесс вычисления функции $$f_{\Phi_1}$$ на соответствующих аргументах изнутри-наружу: вместо каждого вхождения переменной в формулу подставляется ее значение, затем в полученной формуле, состоящей из констант и булевых связок, последовательно вычисляются значения самых внутренних функций ( подформул ), для которых уже определены значения их аргументов, до тех пор, пока не будет получено значение всей формулы.

    Эквивалентность булевых формул

    Определение 1.3. Булевы формулы $$\Phi$$ и $$\Psi$$ называются эквивалентными, если соответствующие им функции $$f_{\Phi}$$ и $$f_{\Psi}$$ равны.

    Обозначение: $$\Phi \equiv \Psi$$. Эквивалентные формулы называют также тождественно равными, а выражения вида $$\Phi \equiv \Psi$$ логическими тождествами.

    Таким образом, эквивалентные формулы являются различными заданиями одной и той же булевой функции. Ниже мы приводим ряд пар эквивалентных формул (тождеств), отражающих существенные свойства логических операций и важные соотношения между различными операциями. Они часто позволяют находить для булевых функций по одним задающим их формулам более простые формулы. Большинство из приводимых тождеств имеют собственные имена. Часто их называют законами логики.

    Пусть $$\circ$$ - это одна из функций $$\wedge, \vee, +$$. Для этих трех функций выполнены следующие две эквивалентности (законы ассоциативности и коммутативности).

    (1) Ассоциативность:$$((X_1 \circ X_2) \circ X_3) \equiv (X_1 \circ(X_2 \circ X_3))$$ (2) Коммутативность:$$(X_1 \circ X_2) \equiv (X_2 \circ X_1 ))$$ (3) Дистрибутивные законы:$$((X_1 \vee X_2) \wedge X_3) \equiv ((X_1 \wedge X_3)\vee (X_2 \wedge X_3))$$ $$((X_1 \wedge X_2) \vee X_3) \equiv ((X_1 \vee X_3)\wedge (X_2 \vee X_3))$$ $$((X_1 + X_2) \wedge X_3) \equiv ((X_1 \wedge X_3)+ (X_2 \wedge X_3))$$ (4) Двойное отрицание:$$\neg (\neg X) \equiv X$$ (5) Законы де Моргана (внесение отрицания внутрь скобок):$$\neg (X_1 \vee X_2) \equiv (\neg X_1 \wedge \neg X_2)$$ $$\neg (X_1 \wedge X_2) \equiv (\neg X_1 \vee \neg X_2)$$ (6) Законы упрощения:$$(X \wedge X) \equiv X \hspace{20mm} (X \vee X) \equiv X$$ $$(X \wedge \neg X) \equiv 0 \hspace{20mm} (X \vee \neg X) \equiv 1$$ $$(X \wedge 0) \equiv 0 \hspace{20mm} (X \vee 0) \equiv X$$ $$(X \wedge 1) \equiv X \hspace{20mm} (X \vee 1) \equiv 1$$ Некоторые законы упрощения имеют собственные названия: эквивалентности в первой строке называются законами идемпотентности, $$(X \wedge \neg X) \equiv 0$$ - это закон противоречия, $$(X \vee \neg X) \equiv 1$$ - это закон исключенного третьего.

    Следующие две эквивалентности позволяют выразить импликацию и сложение по модулю 2 через дизъюнкцию, конъюкцию и отрицание.$$(X_1 \rightarrow X_2) \equiv (\neg X_1 \vee X_2)$$ $$(X_1 + X_2) \equiv (( X_1 \wedge \neg X_2)\vee (\neg X_1\wedge X_2))$$

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

    Соглашения об упрощенной записи формул. Законы ассоциативности показывают, что значения формул, составленных из переменных и одних операций конъюнкции, не зависят от расстановки скобок. Поэтому вместо формул $$(X_1 \wedge X_2) \wedge X_3)$$ и $$(X_1 \wedge (X_2 \wedge X_3))$$ мы будем для упрощения писать $$(X_1 \wedge X_2 \wedge X_3)$$. Аналогично, будем использовать выражения $$(X_1 \vee X_2 \vee X_3)$$ и $$(X_1 + X_2 + X_3)\$$ для сокращения формул, состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно. Будем также опускать внешние скобки в записи формулы, если ее внешней функцией является одна из функций $$\wedge, \vee, +, \rightarrow$$.

    Таким образом, с использованием этих соглашений формула $$(((X \vee Y)\vee(Z \wedge \neg X))\rightarrow ((Y + Z)+\neg X))$$ может быть записана как $$(X \vee Y \vee (Z \wedge \neg X))\rightarrow (Y + Z+\neg X)$$.

    Дизъюнктивные и конъюнктивные нормальные формы

    Имеется ряд специальных подклассов формул, позволяющих задавать все булевы функции. В этом разделе мы определим два таких подкласса функций, использующих только операции $$\wedge, \vee$$ и $$\neg$$.

    Пусть $$\mathbf{X}=\{X_1,\ldots, X_n\}$$ - это множество пропозициональных переменных. Введем для каждого $$i=1,...,n$$ обозначения: $$X_i^0= \neg X_i$$ и $$X_i^1= X_i$$. Формула $$X_{i_1}^{\sigma_1}\wedge X_{i_2}^{\sigma_2}\wedge \ldots \wedge X_{i_k}^{\sigma_k}$$ ( $$X_{i_1}^{\sigma_1}\vee X_{i_2}^{\sigma_2}\vee \ldots \vee X_{i_k}^{\sigma_k}$$ ), в которой $$\sigma_{i_j} \in \{0,1\}$$ и все переменные разные, т.е. $$X_{i_j} \neq X_{i_r}$$ при $$j \neq r$$, называется элементарной конъюнкцией (элементарной дизъюнкцией).

    Определение 1.4.Формула $$\mathcal{D}$$ называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид $$\mathcal{D}= K_1 \vee K_2\vee \ldots \vee K_r$$, где каждая формула $$K_j\ ( j=1,...,r)$$ - это элементарная конъюнкция. $$\mathcal{D}$$ называется совершенной ДНФ, если в каждую из ее конъюнкций $$K_j$$ входят все $$n$$ переменных из $$\mathbf{X}$$. Аналогично, формула $$\mathcal{C}$$ называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций, т.е. $$\mathcal{C}= D_1 \vee D_2\vee \ldots \vee D_r$$, где каждая формула $$D_j\ ( j=1,...,r)$$ - это элементарная дизъюнкция. Она является совершенной КНФ, если в каждую $$D_j$$ входят все $$n$$ переменных из $$\mathbf{X}$$.

    Рассмотрим произвольную булеву функцию $$f(X_1,\ldots,X_n)$$, зависящую от переменных из $$\mathbf{X}$$. Oбозначим через $$N_f^+$$ множество наборов значений переменных, на которых $$f$$ принимает значение 1, а через $$N_f^-$$ множество наборов, на которых $$f$$ принимает значение 0, т.е. $$N_f^+= \{(\sigma_1,\ldots, \sigma_n)\ |\ f(\sigma_1,\ldots, \sigma_n)=1\}$$ и $$N_f^-= \{(\sigma_1,\ldots, \sigma_n)\ |\ f(\sigma_1,\ldots, \sigma_n)=0\}$$. Определим по этим множествам две формулы:$$\mathcal{D}_f = \bigvee_{(\sigma_1,\ldots, \sigma_n)\in N_f^+} (X_1^{\sigma_1}\wedge X_2^{\sigma_2}\wedge \ldots \wedge X_n^{\sigma_n})$$ и$$\mathcal{C}_f = \bigwedge_{(\sigma_1,\ldots, \sigma_n)\in N_f^-} (X_1^{\neg\sigma_1}\vee X_2^{\neg\sigma_2}\vee \ldots \vee X_n^{\neg\sigma_n})$$

    Теорема 1.1.

    (1) Если функция $$f$$ не равна тождественно 0, то формула $$\mathcal{D}_f$$ - это совершенная ДНФ, задающая функцию $$f$$.

    (2) Если функция $$f$$ не равна тождественно 1, то формула $$\mathcal{C}_f$$ - это совершенная КНФ, задающая функцию $$f$$.

    Пример 1.2. Например, для функции $$f_{\Phi_1}$$, представленной в таблице 1.1 совершенная ДНФ равна $$\mathcal{D}= (\neg X_1 \wedge \neg X_2 \wedge \neg X_3) \vee (\neg X_1 \wedge \neg X_2 \wedge X_3) \vee$$ $$(X_1 \wedge X_2 \wedge \neg X_3) \vee ( X_1 \wedge \neg X_2 \wedge \neg X_3) \vee ( X_1 \wedge X_2 \wedge X_3)$$, а ее совершенная КНФ: $$\mathcal{C}=(X_1 \vee \neg X_2 \vee X_3) \wedge (\neg X_1 \vee X_2 \vee \neg X_3) \wedge (\neg X_1 \vee \neg X_2 \vee X_3)$$.

    Отметим, что совершенные ДНФ и КНФ часто являются чересчур сложными и длинными представлениями булевых функций. В нашем примере $$f_{\Phi_1}$$ может быть задана более простой ДНФ: $$\mathcal{D}_1= (\neg X_1 \wedge \neg X_2 ) \vee ( X_2 \wedge X_3)\vee (X_1 \wedge \neg X_2 \wedge \neg X_3)$$.

    Графы

    Мы часто сталкиваемся с задачами, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками ( вершинами ), а связи - линиями ( ребрами ), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Приведем основные определения.

    Граф (ориентированный) - это пара $$(V, E)$$, где $$V$$ - конечное множество вершин (узлов, точек) графа, а $$E$$ - некоторое множество пар вершин, т.е. подмножество множества $$V \times V$$ или бинарное отношение на $$V$$. Элементы $$E$$ называют ребрами (дугами, стрелками, связями). Для ребра $$e= (u,v) \in E$$ вершина $$u$$ называется началом $$e$$, а вершина $$v$$ - концом $$e$$, говорят, что ребро $$e$$ ведет из $$u$$ в $$v$$.

    В графе полустепень исхода вершины - это число исходящих из нее ребер, а полустепень захода - это число входящих в данную вершину ребер.

    Заметим, что в графе может быть ребро вида $$(u,u)$$, называемое петлей.

    Пример 1.3. На рис. 1.1 приведен пример графа $$G_1=(V_1, E_1)$$. Здесь $$V_1=\{ a,b,c,d\}, E_1=\{ (a,b), (a,c), (b,b), (b,d), (d,a)\}$$, В графе $$G_1$$ ребро $$(b,b)$$ является петлей, полустепень исхода вершины $$a$$ равна 2, а полустепень захода для нее равна 1.

    (рис 1.1) Граф G1

    Во многих приложениях с вершинами и ребрами графов связывается некоторая дополнительная информация. Обычно она представляется с помощью функций разметки вершин и ребер.

    Определение 1.6.

    Размеченный граф - это граф $$G= (V, E)$$, снабженный одной или двумя функциями разметки вида: $$l: V \rightarrow M$$ и $$c: E \rightarrow L$$, где $$M$$ и $$L$$ - множества меток вершин и ребер, соответственно.

    Упорядоченный граф - это размеченный граф $$G= (V, E)$$, в котором ребра, выходящие из каждой вершины $$v \in V$$, упорядочены, т.е. помечены номерами $$0, \ldots, k_v-1$$, где $$k_v$$ - полустепень исхода $$v$$, т.е. $$k_v =|\{ w\ |\ (v,w) \in E\}|$$.

    Упорядоченный граф с полустепенью исхода вершин $$\leq 2$$ называется бинарным.

    В качестве множества меток ребер $$L$$ часто выступают числа, задающие "веса", "длины", "стоимости" ребер. Графы с такой разметкой часто называют взвешенными.

    Часто на одном множестве объектов определено несколько различных бинарных отношений. Для представления такой ситуации служат мультиграфы.

    Определение 1.7. Мультиграф $$G= (V, E)$$ состоит из конечного множества вершин $$V$$ и мультимножества ребер $$E$$, состоящего из пар вершин $$(u,v) \in V \times V$$, в которое эти пары могут входить по нескольку раз.

    Обычно несколько ребер, соединяющих одну и ту же пару вершин, различаются метками - именами соответствующих бинарных отношений. В лекциях 4-6 мультиграфы будут использоваться для представления диаграмм конечных автоматов.

    Во многих случаях естественно не различать графы, отличающиеся лишь именами (порядком) вершин.

    Определение 1.8. Изоморфизм графов. Два графа $$G_1= (V_1, E_1)$$ и $$G_2= (V_2, E_2)$$ называются изоморфными, если между их вершинами существует взаимно однозначное соответствие $$\varphi: V_1 \rightarrow V_2$$ такое, что для любой пары вершин $$u, v$$ из $$V_1$$ ребро $$(u,v) \in E_1 \ \Leftrightarrow\ $$ ребро $$(\varphi(u), \varphi(v)) \in E_2$$.

    Для изоморфизма размеченных графов требуется также совпадение меток соответствующих вершин: $$l_1(v) = l_2(\varphi(v))$$ и/или ребер: $$c_1((u,v)) = c_2((\varphi(u), \varphi(v)) )$$.

    Многие приложения графов связаны с изучением путей между их вершинами.

    Определение 1.9.

    Путь в ( мульти ) графе - это последовательность ребер вида $$e_1=(v_1,v_2),e_2=(v_2,v_3), \ldots , e_{n-1}=(v_{n-1},v_n)$$. Этот путь ведет из начальной вершины $$v_1$$ в конечную вершину $$v_n$$ и имеет длину $$n-1$$. В этом случае будем говорить, что $$v_n$$ достижима из $$v_1$$. Будем считать, что каждая вершина достижима сама из себя путем длины 0. Путь в графе (не мультиграфе!) можно также определять как соответствующую последовательность вершин: $$(v_1,v_2,v_3, \ldots , v_{n-1},v_n)$$, где $$(v_i,v_{i+1})\in E$$ при $$i=1,2,\ldots, n-1$$.

    Путь назывется простым, если все ребра и все вершины на нем, кроме, быть может, первой и последней, различны.

    Циклом в графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл $$(v_1,v_2, \ldots , v_{n-1},v_n=v_1)$$ называется простым, если в нем нет одинаковых вершин, кроме первой и последней, т.е. если все вершины $$v_2, \ldots , v_{n-1}$$ различны.

    Если в графе нет циклов, то он называется ациклическим.

    Следующее утверждение непосредственно следует из определений.

    Лемма 1.1.Если в графе $$G$$ имеется путь из вершины $$u$$ в вершину $$v$$, то в нем имеется и простой путь из $$u$$ в $$v$$.

    Деревья

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

    Определение 1.10. Граф $$G=(V,E)$$ называется деревом, если

  • в нем есть одна вершина $$r \in E$$, в которую не входят ребра ; она называется корнем дерева ;
  • в каждую из остальных вершин входит ровно по одному ребру ;
  • все вершины достижимы из корня.
    •

    На рисунке 2 показан пример дерева $$G_1$$

    С ориентированными деревьями связана богатая терминология, пришедшая из двух источников: ботаники и области семейных отношений.

    Корень - это единственная вершина, в которую не входят ребра, листья - это вершины, из которых не выходят ребра. Путь из корня в лист называется ветвью дерева. Высота дерева - это максимальная из длин его ветвей. Глубина вершины - это длина пути из корня в эту вершину. Для вершины $$v \in V$$, подграф дерева $$T=(V,E)$$, включающий все достижимые из $$v$$ вершины и соединяющие их ребра из $$E$$, образует поддерево $$T_v$$ дерева $$T$$ с корнем $$v$$.. Высота вершины $$v$$ - это высота дерева $$T_v$$. Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.

    (рис 1.2) Дерево G1

    Если из вершины $$v$$ ведет ребро в вершину $$w$$, то $$v$$ называется отцом $$w$$, а $$w$$ - сыном $$v$$ (в последнее время в ангоязычной литературе употребляется асексульная пара терминов: родитель - ребенок). Из определения дерева непосредственно следует, что у каждой вершины кроме корня имеется единственный отец. Если из вершины $$v$$ ведет путь в вершину $$w$$, то $$v$$ называется предком $$w$$, а $$w$$ - потомком $$v$$. Вершины, у которых общий отец, называются братьями или сестрами.

    Пример 1.4. В дереве на рис. 1.2 вершина $$c$$ является корнем, вершины $$a, b, f, g, k$$ - листья. Путь $$c,d,h,k$$ - одна из ветвей дерева $$G_1$$. Вершина $$d$$ является отцом (родителем) вершин $$e, g$$ и $$h$$, а каждая из этих вершин - ее сыном (ребенком). Между собой вершины $$e, g$$ и $$h$$ являются братьями (сестрами). Глубина $$d$$ равна 1, а высота - 2. Высота всего дерева $$G_1$$ равна 3.

    Для деревьев часто удобно использовать следующее индуктивное определение.

    Определение 1.11. Определим по индукции класс графов $$\mathcal{D}$$, называемых деревьями. Одновременно для каждого из них определим выделенную вершину - корень.

  • Граф $$T_0=(V,E)$$, с единственной вершиной $$V=\{ v\}$$ и пустым множеством ребер $$E=\emptyset$$ является деревом (входит в $$\mathcal{D}$$ ). Вершина $$v$$ называется корнем этого дерева.
  • Пусть графы $$T_1=(V_1,E_1), \ldots , T_k= (V_k, E_k)$$ с корнями $$r_1 \in V_1, \ldots, r_k \in V_k$$ принадлежат $$\mathcal{D}$$, а $$r_0$$ - новая вершина, т.е. $$r_0 \notin \bigcup_{i=1}^k V_i$$. Тогда классу $$\mathcal{D}$$ принадлежит также следующий граф $$T = (V, E)$$, где $$V= \{ r_0\} \cup \bigcup_{i=1}^k V_i$$, $$E = \{ (r_0, r_i)\ |\ i=1, \ldots , k\} \cup \bigcup_{i=1}^k E_i$$. Корнем этого дерева является вершина $$r_0$$.
  • Других графов в классе $$\mathcal{D}$$ нет.
    •

    Рисунок 1.3 иллюстрирует это определение.

    (рис 1.3) Индуктивное определение ориентированных деревьев

    Определения ориентированных деревьев 1.10 и 1.11 эквивалентны.

    Выделим еще один класс графов, обобщающий деревья, ациклические графы. Два вида таких размеченных графов будут использованы далее для представления булевых функций. У этих графов может быть несколько корней - вершин, в которые не входят ребра, и в каждую вершину может входить несколько ребер, а не одно, как у деревьев.

    Дерево называется бинарным или двоичным, если у каждой его внутренней вершины имеется не более двух сыновей, причем ребра, ведущие к ним помечены двумя разными метками (обычно используются метки из пар: "левый" - "правый", 0 - 1, $$+$$ $$-$$ - и т.п.)

    Бинарное дерево называется полным, если у каждой его внутренней вершины имеется два сына и все его ветви имеют одинаковую длину.
    Страницы:

    Булевы функции от n переменных

    Булевы функцииВ отечественной литературе их также часто называют функциями алгебры логики . названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций - их аргументы и значения могут принимать всего два значения. С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.

    Обозначим через $$B$$ двухэлементное множество $$\{0,1\}$$. Тогда $$B^n=\underbrace{B\times B \times \ldots \times B}_{n}$$ - это множество всех двоичных последовательностей (наборов, векторов) длины $$n$$. Булевой функцией от $$n$$ переменных (аргументов) называется любая функция $$f(x_1,\ldots, x_n): B^n \rightarrow B$$. Каждый из ее аргументов $$x_i, \ 1 \leq i \leq n,\$$ может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из $$B^n$$ также может быть 0 или 1. Обозначим через $$\mathcal{P}_n$$ множество всех булевых функций от $$n$$ переменных. Нетрудно подсчитать их число: $$|\mathcal{P}_n | = 2^{2^n}$$.

    Имеется несколько различных способов представления и интерпретации булевых функций. В этом разделе мы рассмотрим табличное представление, а также представление с помощью логических формул. В лекциях 2 и 3 будет рассмотрено еще два способа представления булевых функций: логические схемы и упорядоченные бинарные диаграммы решений.

    Табличное представление

    Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц. Таблица для функции $$f(x_1, \ldots, x_n)$$ имеет $$n+1$$ столбец. В первых $$n$$ столбцах указываются значения аргументов $$x_1, \ldots, x_n$$, а в $$(n+1)$$ -ом столбце значение функции на этих аргументах - $$f(x_1,\ldots , x_n)$$.

    Табличное представление функции $$f(x_1, \ldots, x_n)$$
    $$x_1$$   .  .  .   $$x_{n-1}$$    $$x_n$$ $$f(x_1,\ldots x_{n-1}, x_n)$$

    $$0$$   .  .  .   $$0$$    $$0$$

    $$0$$   .  .  .   $$0$$    $$1$$

    $$0$$   .  .  .   $$1$$    $$0$$

    .  .  .  .  .  .

    $$1$$   .  .  .   $$1$$    $$1$$

    $$f(0, \ldots, 0,0)$$

    $$f(0, \ldots, 0,1)$$

    $$f(0, \ldots, 1,0)$$

    $$\ldots$$

    $$f(1, \ldots, 1,1)$$

    Наборы аргументов в строках обычно располагаются в лексикографическом порядке: $$(\alpha_1, \ldots, \alpha_n) \prec (\beta_1, \ldots, \beta_n)\ \Leftrightarrow$$ существует такое $$i \in [1,n]$$, что при $$j < i\ \alpha_j = \beta_j$$, а $$\alpha_i < \beta_i$$. Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, ... , а последняя - $$2^n-1$$.

    При больших $$n$$ табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблица с 1024 строками. Но для малых $$n$$ оно достаточно наглядно.

    Булевы функции от 1-ой и 2-х переменных

    Перечислим вначале все булевы функции от 1-ой переменной $$x_1$$. Как мы знаем, их всего четыре.

  • $$f_1(x_1)= 0$$ - константа 0;
  • $$f_2(x_1)= 1$$ - константа 1;
  • $$f_3(x_1)= x_1$$ - тождественная функция;
  • $$f_4(0)=1, f_4(1)=0$$. Эта функция называется отрицанием $$x_1$$ и обозначается $$\neg x_1$$ (используется также обозначение $$\overline{x}_1$$, а в языках программирования эта функция часто обозначается как $$NOT x_1$$ ).
    •

    В следующей таблице представлены наиболее используемые 12 (из 16) функций от 2-х переменных.

    Булевы функции от 2-х переменных
    $$x_1$$    $$x_2$$ $$f_1$$ $$f_2$$ $$f_3$$ $$f_4$$ $$f_5$$ $$f_6$$ $$f_7$$ $$f_8$$ $$f_9$$ $$f_{10}$$ $$f_{11}$$ $$f_{12}$$

    0  0

    0  1

    1  0

    1  1

    0

    0

    0

    0

    1

    1

    1

    1

    0

    0

    1

    1

    1

    1

    0

    0

    0

    1

    0

    1

    1

    0

    1

    0

    0

    0

    0

    1

    0

    1

    1

    1

    1

    1

    0

    1

    0

    1

    1

    0

    1

    0

    0

    1

    1

    1

    1

    0

    Многие из этих функций часто считаются "элементарными" и имеют собственные обозначения.

  • $$f_1(x_1,x_2)= 0$$ - константа 0;
  • $$f_2(x_1, x_2)= 1$$ - константа 1;
  • $$f_3(x_1,x_2)= x_1$$ - функция, равная 1-му аргументу;
  • $$f_4(x_1,x_2)= \neg x_1$$ - отрицание $$x_1$$ ;
  • $$f_5(x_1,x_2)= x_2$$ - функция, равная 2-му аргументу;
  • $$f_6(x_1,x_2)= \neg x_2$$ - отрицание $$x_2$$ ;
  • $$f_7(x_1,x_2)= (x_1 \wedge x_2)$$ - конъюнкция, читается " $$x_1$$ и $$x_2$$ " (используются также обозначения $$(x_1 x_2)$$, $$(x_1x_2)$$, $$\min(x_1,x_2)$$ и $$(x_1$$ AND $$x_2$$ ));
  • $$f_8(x_1,x_2)= (x_1 \vee x_2)$$ - дизъюнкция, читается " $$x_1$$ или $$x_2$$ " (используются также обозначения $$(x_1 + x_2)$$, $$\max(x_1x_2)$$ и $$(x_1$$ OR $$x_2$$ ));
  • $$f_9(x_1,x_2)= (x_1 \rightarrow x_2)$$ - импликация, читается " $$x_1$$ влечет $$x_2$$ " или "из $$x_1$$ следует $$x_2$$ " (используются также обозначения $$(x_1 \supset x_2)$$, и ( IF $$x_1$$ THEN $$x_2$$ ));
  • $$f_{10}(x_1,x_2)= (x_1 + x_2)$$ - сложение по модулю 2, читается " $$x_1$$ плюс $$x_2$$ " (используется также обозначение $$(x_1 \oplus x_2)$$ );
  • $$f_{11}(x_1,x_2)= (x_1 \sim x_2)$$ - эквивалентность, читается " $$x_1$$ эквивалентно (равносильно) $$x_2$$ " (используется также обозначение $$(x_1 \equiv x_2)$$ );
  • $$f_{12}(x_1,x_2)= (x_1 | x_2)$$ - штрих Шеффера (антиконъюнкция), иногда читается как "не $$x_1$$ и $$x_2$$ ".
    •

    В качестве элементарных функций будем также рассматривать 0-местные функции-константы 0 и 1.

    Отметим, что функции $$f_1(x_1,x_2)$$ и $$f_2(x_1,x_2)$$ фактически не зависят от значений обоих аргументов, функции $$f_3(x_1,x_2)$$ и $$f_4(x_1,x_2)$$ не зависят от значений аргумента $$x_2$$, а функции $$f_5(x_1,x_2)$$ и $$f_6(x_1,x_2)$$ не зависят от значений аргумента $$x_1$$.

    Определение 1.1. Функция $$f(x_1,\ldots, x_i,\ldots, x_n)$$ не зависит от аргумента $$x_i$$, если для любого набора значений $$\sigma_1,\ldots,\sigma_{i-1},\sigma_{i+1},\ldots, \sigma_n$$ остальных аргументов $$f$$ имеет место равенство

    $$f(\sigma_1,\ldots,\sigma_{i-1},0,\sigma_{i+1},\ldots, \sigma_n)= f(\sigma_1,\ldots,\sigma_{i-1},1,\sigma_{i+1},\ldots, \sigma_n).$$

    Такой аргумент $$x_i$$ называется фиктивным. Аргументы, не являющиеся фиктивными, называются существенными.

    Функции $$f_1(x_1,\ldots, x_n)$$ и $$f_2(x_1,\ldots, x_m)$$ называются равными, если функцию $$f_2$$ можно получить из функции $$f_1$$ путем добавления и удаления фиктивных аргументов.

    Например, равными являются одноместная функция $$f_3(x_1)$$ и двухместная функция $$f_3(x_1,x_2)$$, так как вторая получается из первой добавлением фиктивного аргумента $$x_2$$. Мы не будем различать равные функции и, как правило, будем использовать для обозначения равных функций одно и то же имя функции. В частности, это позволяет считать, что во всяком конечном множестве функций все функции зависят от одного и того же множества переменных.

    Формулы

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

    Мы будем рассматривать формулы, построенные над множеством элементарных функций $$\mathcal{B}=\{ 0, 1, \neg, \wedge, \vee, \rightarrow, +, \sim,\ | \}$$. Все эти функции, кроме констант, называются логическими связками или логическими операциями. При этом для 2-местных функций из этого списка будем использовать инфиксную запись, в которой имя логической связки помещается между 1-ым и 2-ым аргументами.

    Зафиксируем некоторое счетное множество переменных $$V=\{ X_1, X_2, \ldots \}$$. Определим по индукции множество формул над $$\mathcal{B}$$ с переменными из $$V$$. Одновременно будем определять числовую характеристику $$dep(\Phi)$$ формулы $$\Phi$$, называемую ее глубиной, и множество ее подформул.

    Определение 1.2. а) Базис индукции. 0, 1 и каждая переменная $$X_i \in V$$ является формулой глубины 0, т.е. $$dep(X_i)= dep(0)= dep(1)=0$$. Множество ее подформул состоит из нее самой.

    б) Шаг индукции. Пусть $$\Phi_1$$ и $$\Phi_2$$ - формулы, $$\circ \in \{ \wedge, \vee, \rightarrow, +, \sim,\ | \}$$. Тогда выражения $$\Phi= \neg \Phi_1$$ и $$\Phi= ( \Phi_1 \circ \Phi_2)$$ являются формулами. При этом $$dep(\neg \Phi_1)=1 + dep( \Phi_1)$$, а $$dep((\Phi_1 \circ \Phi_2))=1 + \max\{dep( \Phi_1), dep( \Phi_2)\}$$. Множество подформул $$\Phi$$ включает саму формулу $$\Phi$$ и для $$\Phi= \neg \Phi_1$$ все подформулы формулы $$\Phi_1$$, а для $$\Phi= ( \Phi_1 \circ \Phi_2)$$ все подформулы формул $$\Phi_1$$ и $$\Phi_2$$.

    Каждой формуле $$\Phi(X_1,\ldots, X_n)$$ сопоставим булеву функцию, которую эта формула задает, используя индукцию по глубине формулы.

    Базис индукции. Пусть $$dep(\Phi)=0$$. Тогда $$\Phi = X_i \in V$$ или $$\Phi =c \in \mathcal{B}$$ В первом случае $$\Phi$$ задает функцию $$f_{\Phi}(X_i)=X_i$$, во втором - функцию, тождественно равную константе $$c$$.

    Шаг индукции. Пусть $$\Phi$$ - произвольная формула глубины $$dep(\Phi)= k+1$$. Тогда $$\Phi(X_1,\ldots, X_n)= \neg \Phi_1(X_1,\ldots, X_n)$$ или $$\Phi(X_1,\ldots, X_n)= ( \Phi_1(X_1,\ldots, X_n) \circ \Phi_2(X_1,\ldots, X_n))$$ для некоторой булевой связки $$\circ \in \{ \wedge, \vee, \rightarrow, +, \sim,\ | \}$$. Так как $$\max \{dep( \Phi_1), dep( \Phi_2)\} \leq k$$, то формулам $$\Phi_1$$ и $$\Phi_2$$ соответствующие функции $$f_1(X_1,\ldots, X_n)$$ и $$f_2(X_1,\ldots, X_n)$$ уже сопоставлены. Тогда формула $$\neg\Phi_1$$ задает функцию $$f_{\Phi} =\neg f_1(X_1,\ldots, X_n)$$, а формула $$\Phi(X_1,\ldots, X_n)= ( \Phi_1(X_1,\ldots, X_n) \circ \Phi_2(X_1,\ldots, X_n))$$ задает функцию $$f_{\Phi} = f_1(X_1,\ldots, X_n) \circ f_2(X_1,\ldots, X_n)$$.

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

    Пример 1.1. Например, для формулы$$\Phi_1= ( (X_1 \vee \neg\neg X_2)\rightarrow (X_3 + (X_1 \wedge \neg X_2)))$$ функция $$f_{\Phi_1}$$ задается выделенным столбцом $$\rightarrow$$ следующей таблицы.

    Функция $$f_{\Phi_1}$$
    $$X_1$$   $$X_2$$   $$X_3$$ $$((X_1$$    $$\vee$$    $$\neg$$ $$\neg$$    $$X_2)$$ $$\rightarrow$$ $$(X_3$$    $$+$$    $$(X_1$$    $$\wedge\$$    $$\neg$$ $$X_2)))$$

    0 0 0

    0 0 1

    0 1 0

    0 1 1

    1 0 0

    1 0 1

    1 1 0

    1 1 1

     0  0  0 1  0

     0  0  0 1  0

     0  1  1 0  1

     0  1  1 0  1

     1  1  0 1  0

     1  1  0 1  0

     1  1  1 0  1

     1  1  1 0  1

    1

    1

    0

    1

    1

    0

    0

    1

    0  0  0  0  1  0

    1  1  0  0  1  0

    0  0  0  0  0  1

    1  1  0  0  0  1

    0  1  1  1  1  0

    1  0  1  1  1  0

    0  0  1  0  0  1

    1  1  1  0  0  1

    Каждая строка этой таблицы задает процесс вычисления функции $$f_{\Phi_1}$$ на соответствующих аргументах изнутри-наружу: вместо каждого вхождения переменной в формулу подставляется ее значение, затем в полученной формуле, состоящей из констант и булевых связок, последовательно вычисляются значения самых внутренних функций ( подформул ), для которых уже определены значения их аргументов, до тех пор, пока не будет получено значение всей формулы.

    Эквивалентность булевых формул

    Определение 1.3. Булевы формулы $$\Phi$$ и $$\Psi$$ называются эквивалентными, если соответствующие им функции $$f_{\Phi}$$ и $$f_{\Psi}$$ равны.

    Обозначение: $$\Phi \equiv \Psi$$. Эквивалентные формулы называют также тождественно равными, а выражения вида $$\Phi \equiv \Psi$$ логическими тождествами.

    Таким образом, эквивалентные формулы являются различными заданиями одной и той же булевой функции. Ниже мы приводим ряд пар эквивалентных формул (тождеств), отражающих существенные свойства логических операций и важные соотношения между различными операциями. Они часто позволяют находить для булевых функций по одним задающим их формулам более простые формулы. Большинство из приводимых тождеств имеют собственные имена. Часто их называют законами логики.

    Пусть $$\circ$$ - это одна из функций $$\wedge, \vee, +$$. Для этих трех функций выполнены следующие две эквивалентности (законы ассоциативности и коммутативности).

    (1) Ассоциативность:$$((X_1 \circ X_2) \circ X_3) \equiv (X_1 \circ(X_2 \circ X_3))$$ (2) Коммутативность:$$(X_1 \circ X_2) \equiv (X_2 \circ X_1 ))$$ (3) Дистрибутивные законы:$$((X_1 \vee X_2) \wedge X_3) \equiv ((X_1 \wedge X_3)\vee (X_2 \wedge X_3))$$ $$((X_1 \wedge X_2) \vee X_3) \equiv ((X_1 \vee X_3)\wedge (X_2 \vee X_3))$$ $$((X_1 + X_2) \wedge X_3) \equiv ((X_1 \wedge X_3)+ (X_2 \wedge X_3))$$ (4) Двойное отрицание:$$\neg (\neg X) \equiv X$$ (5) Законы де Моргана (внесение отрицания внутрь скобок):$$\neg (X_1 \vee X_2) \equiv (\neg X_1 \wedge \neg X_2)$$ $$\neg (X_1 \wedge X_2) \equiv (\neg X_1 \vee \neg X_2)$$ (6) Законы упрощения:$$(X \wedge X) \equiv X \hspace{20mm} (X \vee X) \equiv X$$ $$(X \wedge \neg X) \equiv 0 \hspace{20mm} (X \vee \neg X) \equiv 1$$ $$(X \wedge 0) \equiv 0 \hspace{20mm} (X \vee 0) \equiv X$$ $$(X \wedge 1) \equiv X \hspace{20mm} (X \vee 1) \equiv 1$$ Некоторые законы упрощения имеют собственные названия: эквивалентности в первой строке называются законами идемпотентности, $$(X \wedge \neg X) \equiv 0$$ - это закон противоречия, $$(X \vee \neg X) \equiv 1$$ - это закон исключенного третьего.

    Следующие две эквивалентности позволяют выразить импликацию и сложение по модулю 2 через дизъюнкцию, конъюкцию и отрицание.$$(X_1 \rightarrow X_2) \equiv (\neg X_1 \vee X_2)$$ $$(X_1 + X_2) \equiv (( X_1 \wedge \neg X_2)\vee (\neg X_1\wedge X_2))$$

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

    Соглашения об упрощенной записи формул. Законы ассоциативности показывают, что значения формул, составленных из переменных и одних операций конъюнкции, не зависят от расстановки скобок. Поэтому вместо формул $$(X_1 \wedge X_2) \wedge X_3)$$ и $$(X_1 \wedge (X_2 \wedge X_3))$$ мы будем для упрощения писать $$(X_1 \wedge X_2 \wedge X_3)$$. Аналогично, будем использовать выражения $$(X_1 \vee X_2 \vee X_3)$$ и $$(X_1 + X_2 + X_3)\$$ для сокращения формул, состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно. Будем также опускать внешние скобки в записи формулы, если ее внешней функцией является одна из функций $$\wedge, \vee, +, \rightarrow$$.

    Таким образом, с использованием этих соглашений формула $$(((X \vee Y)\vee(Z \wedge \neg X))\rightarrow ((Y + Z)+\neg X))$$ может быть записана как $$(X \vee Y \vee (Z \wedge \neg X))\rightarrow (Y + Z+\neg X)$$.

    Дизъюнктивные и конъюнктивные нормальные формы

    Имеется ряд специальных подклассов формул, позволяющих задавать все булевы функции. В этом разделе мы определим два таких подкласса функций, использующих только операции $$\wedge, \vee$$ и $$\neg$$.

    Пусть $$\mathbf{X}=\{X_1,\ldots, X_n\}$$ - это множество пропозициональных переменных. Введем для каждого $$i=1,...,n$$ обозначения: $$X_i^0= \neg X_i$$ и $$X_i^1= X_i$$. Формула $$X_{i_1}^{\sigma_1}\wedge X_{i_2}^{\sigma_2}\wedge \ldots \wedge X_{i_k}^{\sigma_k}$$ ( $$X_{i_1}^{\sigma_1}\vee X_{i_2}^{\sigma_2}\vee \ldots \vee X_{i_k}^{\sigma_k}$$ ), в которой $$\sigma_{i_j} \in \{0,1\}$$ и все переменные разные, т.е. $$X_{i_j} \neq X_{i_r}$$ при $$j \neq r$$, называется элементарной конъюнкцией (элементарной дизъюнкцией).

    Определение 1.4.Формула $$\mathcal{D}$$ называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид $$\mathcal{D}= K_1 \vee K_2\vee \ldots \vee K_r$$, где каждая формула $$K_j\ ( j=1,...,r)$$ - это элементарная конъюнкция. $$\mathcal{D}$$ называется совершенной ДНФ, если в каждую из ее конъюнкций $$K_j$$ входят все $$n$$ переменных из $$\mathbf{X}$$. Аналогично, формула $$\mathcal{C}$$ называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций, т.е. $$\mathcal{C}= D_1 \vee D_2\vee \ldots \vee D_r$$, где каждая формула $$D_j\ ( j=1,...,r)$$ - это элементарная дизъюнкция. Она является совершенной КНФ, если в каждую $$D_j$$ входят все $$n$$ переменных из $$\mathbf{X}$$.

    Рассмотрим произвольную булеву функцию $$f(X_1,\ldots,X_n)$$, зависящую от переменных из $$\mathbf{X}$$. Oбозначим через $$N_f^+$$ множество наборов значений переменных, на которых $$f$$ принимает значение 1, а через $$N_f^-$$ множество наборов, на которых $$f$$ принимает значение 0, т.е. $$N_f^+= \{(\sigma_1,\ldots, \sigma_n)\ |\ f(\sigma_1,\ldots, \sigma_n)=1\}$$ и $$N_f^-= \{(\sigma_1,\ldots, \sigma_n)\ |\ f(\sigma_1,\ldots, \sigma_n)=0\}$$. Определим по этим множествам две формулы:$$\mathcal{D}_f = \bigvee_{(\sigma_1,\ldots, \sigma_n)\in N_f^+} (X_1^{\sigma_1}\wedge X_2^{\sigma_2}\wedge \ldots \wedge X_n^{\sigma_n})$$ и$$\mathcal{C}_f = \bigwedge_{(\sigma_1,\ldots, \sigma_n)\in N_f^-} (X_1^{\neg\sigma_1}\vee X_2^{\neg\sigma_2}\vee \ldots \vee X_n^{\neg\sigma_n})$$

    Теорема 1.1.

    (1) Если функция $$f$$ не равна тождественно 0, то формула $$\mathcal{D}_f$$ - это совершенная ДНФ, задающая функцию $$f$$.

    (2) Если функция $$f$$ не равна тождественно 1, то формула $$\mathcal{C}_f$$ - это совершенная КНФ, задающая функцию $$f$$.

    Пример 1.2. Например, для функции $$f_{\Phi_1}$$, представленной в таблице 1.1 совершенная ДНФ равна $$\mathcal{D}= (\neg X_1 \wedge \neg X_2 \wedge \neg X_3) \vee (\neg X_1 \wedge \neg X_2 \wedge X_3) \vee$$ $$(X_1 \wedge X_2 \wedge \neg X_3) \vee ( X_1 \wedge \neg X_2 \wedge \neg X_3) \vee ( X_1 \wedge X_2 \wedge X_3)$$, а ее совершенная КНФ: $$\mathcal{C}=(X_1 \vee \neg X_2 \vee X_3) \wedge (\neg X_1 \vee X_2 \vee \neg X_3) \wedge (\neg X_1 \vee \neg X_2 \vee X_3)$$.

    Отметим, что совершенные ДНФ и КНФ часто являются чересчур сложными и длинными представлениями булевых функций. В нашем примере $$f_{\Phi_1}$$ может быть задана более простой ДНФ: $$\mathcal{D}_1= (\neg X_1 \wedge \neg X_2 ) \vee ( X_2 \wedge X_3)\vee (X_1 \wedge \neg X_2 \wedge \neg X_3)$$.

    Графы

    Мы часто сталкиваемся с задачами, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками ( вершинами ), а связи - линиями ( ребрами ), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Приведем основные определения.

    Граф (ориентированный) - это пара $$(V, E)$$, где $$V$$ - конечное множество вершин (узлов, точек) графа, а $$E$$ - некоторое множество пар вершин, т.е. подмножество множества $$V \times V$$ или бинарное отношение на $$V$$. Элементы $$E$$ называют ребрами (дугами, стрелками, связями). Для ребра $$e= (u,v) \in E$$ вершина $$u$$ называется началом $$e$$, а вершина $$v$$ - концом $$e$$, говорят, что ребро $$e$$ ведет из $$u$$ в $$v$$.

    В графе полустепень исхода вершины - это число исходящих из нее ребер, а полустепень захода - это число входящих в данную вершину ребер.

    Заметим, что в графе может быть ребро вида $$(u,u)$$, называемое петлей.

    Пример 1.3. На рис. 1.1 приведен пример графа $$G_1=(V_1, E_1)$$. Здесь $$V_1=\{ a,b,c,d\}, E_1=\{ (a,b), (a,c), (b,b), (b,d), (d,a)\}$$, В графе $$G_1$$ ребро $$(b,b)$$ является петлей, полустепень исхода вершины $$a$$ равна 2, а полустепень захода для нее равна 1.

    (рис 1.1) Граф G1

    Во многих приложениях с вершинами и ребрами графов связывается некоторая дополнительная информация. Обычно она представляется с помощью функций разметки вершин и ребер.

    Определение 1.6.

    Размеченный граф - это граф $$G= (V, E)$$, снабженный одной или двумя функциями разметки вида: $$l: V \rightarrow M$$ и $$c: E \rightarrow L$$, где $$M$$ и $$L$$ - множества меток вершин и ребер, соответственно.

    Упорядоченный граф - это размеченный граф $$G= (V, E)$$, в котором ребра, выходящие из каждой вершины $$v \in V$$, упорядочены, т.е. помечены номерами $$0, \ldots, k_v-1$$, где $$k_v$$ - полустепень исхода $$v$$, т.е. $$k_v =|\{ w\ |\ (v,w) \in E\}|$$.

    Упорядоченный граф с полустепенью исхода вершин $$\leq 2$$ называется бинарным.

    В качестве множества меток ребер $$L$$ часто выступают числа, задающие "веса", "длины", "стоимости" ребер. Графы с такой разметкой часто называют взвешенными.

    Часто на одном множестве объектов определено несколько различных бинарных отношений. Для представления такой ситуации служат мультиграфы.

    Определение 1.7. Мультиграф $$G= (V, E)$$ состоит из конечного множества вершин $$V$$ и мультимножества ребер $$E$$, состоящего из пар вершин $$(u,v) \in V \times V$$, в которое эти пары могут входить по нескольку раз.

    Обычно несколько ребер, соединяющих одну и ту же пару вершин, различаются метками - именами соответствующих бинарных отношений. В лекциях 4-6 мультиграфы будут использоваться для представления диаграмм конечных автоматов.

    Во многих случаях естественно не различать графы, отличающиеся лишь именами (порядком) вершин.

    Определение 1.8. Изоморфизм графов. Два графа $$G_1= (V_1, E_1)$$ и $$G_2= (V_2, E_2)$$ называются изоморфными, если между их вершинами существует взаимно однозначное соответствие $$\varphi: V_1 \rightarrow V_2$$ такое, что для любой пары вершин $$u, v$$ из $$V_1$$ ребро $$(u,v) \in E_1 \ \Leftrightarrow\ $$ ребро $$(\varphi(u), \varphi(v)) \in E_2$$.

    Для изоморфизма размеченных графов требуется также совпадение меток соответствующих вершин: $$l_1(v) = l_2(\varphi(v))$$ и/или ребер: $$c_1((u,v)) = c_2((\varphi(u), \varphi(v)) )$$.

    Многие приложения графов связаны с изучением путей между их вершинами.

    Определение 1.9.

    Путь в ( мульти ) графе - это последовательность ребер вида $$e_1=(v_1,v_2),e_2=(v_2,v_3), \ldots , e_{n-1}=(v_{n-1},v_n)$$. Этот путь ведет из начальной вершины $$v_1$$ в конечную вершину $$v_n$$ и имеет длину $$n-1$$. В этом случае будем говорить, что $$v_n$$ достижима из $$v_1$$. Будем считать, что каждая вершина достижима сама из себя путем длины 0. Путь в графе (не мультиграфе!) можно также определять как соответствующую последовательность вершин: $$(v_1,v_2,v_3, \ldots , v_{n-1},v_n)$$, где $$(v_i,v_{i+1})\in E$$ при $$i=1,2,\ldots, n-1$$.

    Путь назывется простым, если все ребра и все вершины на нем, кроме, быть может, первой и последней, различны.

    Циклом в графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл $$(v_1,v_2, \ldots , v_{n-1},v_n=v_1)$$ называется простым, если в нем нет одинаковых вершин, кроме первой и последней, т.е. если все вершины $$v_2, \ldots , v_{n-1}$$ различны.

    Если в графе нет циклов, то он называется ациклическим.

    Следующее утверждение непосредственно следует из определений.

    Лемма 1.1.Если в графе $$G$$ имеется путь из вершины $$u$$ в вершину $$v$$, то в нем имеется и простой путь из $$u$$ в $$v$$.

    Деревья

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

    Определение 1.10. Граф $$G=(V,E)$$ называется деревом, если

  • в нем есть одна вершина $$r \in E$$, в которую не входят ребра ; она называется корнем дерева ;
  • в каждую из остальных вершин входит ровно по одному ребру ;
  • все вершины достижимы из корня.
    •

    На рисунке 2 показан пример дерева $$G_1$$

    С ориентированными деревьями связана богатая терминология, пришедшая из двух источников: ботаники и области семейных отношений.

    Корень - это единственная вершина, в которую не входят ребра, листья - это вершины, из которых не выходят ребра. Путь из корня в лист называется ветвью дерева. Высота дерева - это максимальная из длин его ветвей. Глубина вершины - это длина пути из корня в эту вершину. Для вершины $$v \in V$$, подграф дерева $$T=(V,E)$$, включающий все достижимые из $$v$$ вершины и соединяющие их ребра из $$E$$, образует поддерево $$T_v$$ дерева $$T$$ с корнем $$v$$.. Высота вершины $$v$$ - это высота дерева $$T_v$$. Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.

    (рис 1.2) Дерево G1

    Если из вершины $$v$$ ведет ребро в вершину $$w$$, то $$v$$ называется отцом $$w$$, а $$w$$ - сыном $$v$$ (в последнее время в ангоязычной литературе употребляется асексульная пара терминов: родитель - ребенок). Из определения дерева непосредственно следует, что у каждой вершины кроме корня имеется единственный отец. Если из вершины $$v$$ ведет путь в вершину $$w$$, то $$v$$ называется предком $$w$$, а $$w$$ - потомком $$v$$. Вершины, у которых общий отец, называются братьями или сестрами.

    Пример 1.4. В дереве на рис. 1.2 вершина $$c$$ является корнем, вершины $$a, b, f, g, k$$ - листья. Путь $$c,d,h,k$$ - одна из ветвей дерева $$G_1$$. Вершина $$d$$ является отцом (родителем) вершин $$e, g$$ и $$h$$, а каждая из этих вершин - ее сыном (ребенком). Между собой вершины $$e, g$$ и $$h$$ являются братьями (сестрами). Глубина $$d$$ равна 1, а высота - 2. Высота всего дерева $$G_1$$ равна 3.

    Для деревьев часто удобно использовать следующее индуктивное определение.

    Определение 1.11. Определим по индукции класс графов $$\mathcal{D}$$, называемых деревьями. Одновременно для каждого из них определим выделенную вершину - корень.

  • Граф $$T_0=(V,E)$$, с единственной вершиной $$V=\{ v\}$$ и пустым множеством ребер $$E=\emptyset$$ является деревом (входит в $$\mathcal{D}$$ ). Вершина $$v$$ называется корнем этого дерева.
  • Пусть графы $$T_1=(V_1,E_1), \ldots , T_k= (V_k, E_k)$$ с корнями $$r_1 \in V_1, \ldots, r_k \in V_k$$ принадлежат $$\mathcal{D}$$, а $$r_0$$ - новая вершина, т.е. $$r_0 \notin \bigcup_{i=1}^k V_i$$. Тогда классу $$\mathcal{D}$$ принадлежит также следующий граф $$T = (V, E)$$, где $$V= \{ r_0\} \cup \bigcup_{i=1}^k V_i$$, $$E = \{ (r_0, r_i)\ |\ i=1, \ldots , k\} \cup \bigcup_{i=1}^k E_i$$. Корнем этого дерева является вершина $$r_0$$.
  • Других графов в классе $$\mathcal{D}$$ нет.
    •

    Рисунок 1.3 иллюстрирует это определение.

    (рис 1.3) Индуктивное определение ориентированных деревьев

    Определения ориентированных деревьев 1.10 и 1.11 эквивалентны.

    Выделим еще один класс графов, обобщающий деревья, ациклические графы. Два вида таких размеченных графов будут использованы далее для представления булевых функций. У этих графов может быть несколько корней - вершин, в которые не входят ребра, и в каждую вершину может входить несколько ребер, а не одно, как у деревьев.

    Дерево называется бинарным или двоичным, если у каждой его внутренней вершины имеется не более двух сыновей, причем ребра, ведущие к ним помечены двумя разными метками (обычно используются метки из пар: "левый" - "правый", 0 - 1, $$+$$ $$-$$ - и т.п.)

    Бинарное дерево называется полным, если у каждой его внутренней вершины имеется два сына и все его ветви имеют одинаковую длину.
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^