Определение 4.1.
Обозначение: $$\Phi \equiv \Psi$$.
Таким образом,
Пусть $$\hat{}$$ - это одна из функций $$\wedge , \vee , +$$.
Для этих трех функций выполнены следующие две
Некоторые
Следующие две
Проверку правильности этих эквивалентностей оставляем читателям (см. задачу 4.1).
(X1 + X2 + X3)
для сокращения формул, состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно.Таким образом, с использованием этих соглашений формула
$$(((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).$$Из определения
пусть формула $$\alpha$$ является
Применяя этот принцип и используя 0, то получим Y. Эту цепочку
В этой цепочке вспомогательные номера под знаками эквивалентности
указывают, с помощью какой группы
Выведем еще несколько важных логических
Действительно,
$$X \vee (X \wedge \Phi) \underset{(6)}{\equiv} (X \wedge 1) \vee(X \wedge \Phi) \underset{(3)}{\equiv} X \wedge (1 \vee \Phi) \underset{(2,6)}{\equiv} X \wedge 1 \underset{(6)}{\equiv}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$$,
называется
Определение 4.2. Dj (j=1,...,r)
- это Dj
входят все n переменных из $$\mathbf{X}$$.
Рассмотрим произвольную булеву функцию f(X1,...,Xn)
, зависящую
от переменных из $$\mathbf{X}$$. Oбозначим через Nf+
множество наборов значений переменных, на которых f принимает значение 1, а через Nf-
множество наборов, на которых 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})$$Теорема 4.1.
f не равна тождественно 0, то
формула $$\mathcal{D}_f$$ - это f.f не равна тождественно 1, то
формула $$\mathcal{C}_f$$ - это f.Доказательство получается непосредственным вычислением значения каждой из указанных формул с учетом того, что для любого $$\sigma \in \{ 0, 1\}$$ имеют место равенства: $$1^{\sigma } = \sigma$$ и $$0^{\sigma } = \neg \sigma$$ (см. задачу 4.4).
Следствие 4.1.1.
Каждая
Приведенные выше формулы для $$\mathcal{D}_f$$ и $$\mathcal{C}_f$$ позволяют
эффективно строить f (Каким образом?). Можно ли получить такие специальные
представления по произвольной формуле, задающей f, не выписывая ее
полной таблицы? Приводимая ниже процедура позволяет это сделать, используя
Процедура Приведение к
Вход: формула $$\Phi,$$ включающая функции $$\neg , \wedge , \vee , \to$$ и +.
+
на $$\neg , \wedge$$ и $$\vee.$$Поскольку каждая из формул $$\Phi _{1}$$, $$\Phi _{2}$$ имеет
меньшую глубину, чем формула $$\Phi '$$, то предположим по индукции, что для них
уже построены эквивалентные
Тогда в случае (а) имеем:
$$\Phi^\prime \equiv (K_1^1 \vee \ldots \vee K_1^r)\wedge (K_2^1 \vee \ldots \vee K_2^s)\underset{(3)}{\equiv}\\(K_1^1\wedge K_2^1)\vee \ldots \vee (K_1^i\wedge K_2^j)\vee \ldots \vee (K_1^r\wedge K_2^s)$$Каждый член $$(K_1^i\wedge K_2^j)$$ этой дизъюнкции представляет собой
конъюнкцию переменных и их отрицаний. Применяя эквивалентности групп (1), (2) и
(6), можно удалить из нее повторения переменных, после чего она превратится
в некоторую (i,j), 1 <= i <= r, 1 <= j <= s, и удалив, если
потребуется, константы 0,
мы получим
В случае (б) формула $$\Phi^\prime \equiv (K_1^1 \vee K_1^2\vee \ldots \vee K_1^r)\vee (K_2^1 \vee K_2^2\vee \ldots \vee K_2^s)$$
сама уже является
Ki (i=1,..., m)
, эквивалентную Ki
, а затем устраним повторения одинаковых
конъюнкций.Из формулировок эквивалентностей (7) и (8) непосредственно вытекает
Предложение 4.1.
На этапе (1) процедуры при последовательном выполнении преобразований
(7), а затем - (8), до тех пор, пока ни одно из них не применимо, полученная
в результате формула не будет содержать функций $$\to$$ и +.
Доказательство этого предложения оставляем в виде упражнения (см. задачу 4.7).
Следующее утверждение гарантирует корректность этапа (2).
Предложение 4.2. На этапе (2) процедуры при любом порядке выполнения преобразований групп (4) и (5) до тех пор, пока ни одно из них не применимо, в полученной в результате формуле все знаки отрицания будут стоять непосредственно перед переменными.
Перед доказательством этого утверждения введем некоторые обозначения. Напомним, что в определениях 3.2 и 3.3 для каждой формулы $$\Phi$$ была определена ее глубина $$dep(\Phi )$$. Например, формула $$\Phi =\neg (X+Y)\to (\neg (X \vee \neg Z)\wedge Y)$$, построенная над системой $$F=\{ \vee , \wedge , \neg , \to , +\}$$, имеет глубину $$dep(\Phi )=5$$.
Пусть $$\Phi$$ - это формула над $$F=\{ \vee , \wedge , \neg \}$$.
Определим для каждой ее "отрицательной"
Доказательство предложения 4.2 проведем индукцией по высоте формул.
Базис индукции. Если $$H(\Phi )=0$$, то либо в $$\Phi$$ нет отрицаний, либо все отрицания находятся непосредственно перед переменными. Следовательно, $$\Phi$$ удовлетворяет требованию предложения 4.2.
Шаг индукции. Предположим, что при n <= k для всех
формул высоты n Предложение 4.2 выполнено.
Пусть $$\Phi$$ - произвольная формула высоты $$H(\Phi )= k+1$$. Докажем
наше утверждение для нее. Поскольку $$H(\Phi )\ge 1$$, то $$\Phi$$ содержит хотя бы одну отрицательную n=k+1, что завершает индукционный шаг и все доказательство.
Рассмотрим применение процедуры приведения к
Пример 4.1. Пусть формула $$\Phi= ((\neg X\vee Z) \rightarrow (Y \rightarrow (X + Z)))$$.
На (1)-ом этапе процедуры получаем следующую цепочку эквивалентностей:
$$\Phi \underset{(7)}{\equiv} \neg (\neg X\vee Z) \vee (Y \rightarrow (X + Z))\underset{(7)}{\equiv} \neg (\neg X\vee Z) \vee (\neg Y \vee (X+Z)) \underset{(8)}{\equiv}\\ \neg (\neg X\vee Z) \vee (\neg Y \vee ((X \wedge \neg Z) \vee (\neg X \wedge Z))).$$На (2)-ом этапе вносим отрицание внутрь первой скобки и получаем формулу
$$\Phi^\prime=(\neg \neg X \wedge \neg Z)\vee (\neg Y \vee ((X \wedge \neg Z) \vee (\neg X \wedge Z)))$$Устранив двойное отрицание, получим
$$\Phi^{\prime\prime}=( X \wedge \neg Z)\vee (\neg Y \vee ((X \wedge \neg Z) \vee (\neg X \wedge Z))).$$Нетрудно видеть, что это уже
Эта
Подставив эти формулы в $$\Phi _{1}$$ и устранив повторения конъюнкций,
получим
Мы видим, что
Следствие 4.1.2.
Для каждой булевой функции от n переменных, не равной
тождественно 0,
существует единственная с точностью до перестановки конъюнкций и переменных
внутри конъюнкций
Это следствие позволяет предложить следующую
X вхождения переменных в каждую
конъюнкцию, а затем лексикографически упорядочить между собой конъюнкции,
входящие в $$\Phi '$$ и $$\Psi '$$. Пусть в
результате получатся Замечание. Аналогичную процедуру можно построить с использованием
Напомним, что мы рассматриваем K принимает значение 1. Нетрудно понять, что это множество содержит 2(n-k)
наборов, в которых каждая из входящих в K переменных $$X_{i_r}\ (1 \leq r\leq k)$$
имеет фиксированное значение $$\sigma _{r}$$, а значения остальных (n-k) переменных произвольны.
Определение Пусть f - произвольная K называется f, если $$N_K^+ \subseteq N_f^+$$.
K называется f, если для любой L из условия $$N_K^+ \subseteq N_L^+\subseteq N_f^+$$ следует, что $$N_K^+ = N_L^+$$.
f называется дизъюнкция всех
Из этого определения непосредственно следует, что f единственна (с точностью до порядка f.
Примером
D,
используя процедуру, называемую
(П3): $$(X\wedge K_1) \vee (\neg X \wedge K_2) \equiv (X\wedge K_1) \vee (\neg X \wedge K_2) \vee (K_1\wedge K_2) $$
слева направо при условии, что конъюнкция $$(K_{1} \wedge K_{2})$$ непротиворечива, т.е. не содержит одновременно некоторую переменную и ее отрицание. (Заметим, что на этом этапе число(П1): $$X \vee (X\wedge K) \equiv X$$.
Затем удалить повторные вхождения конъюнкций.Теорема 4.2. В результате применения метода Блейка к произвольной
Доказательство
Пусть после (1)-го этапа процедуры D функции f
преобразовалась
в D1
. Покажем, что
для всякой допустимой для f K в D1
найдется такая
конъюнкция K', что $$N_K^+ \subseteq N_{K'}^+$$.
Доказательство проведем возвратной индукцией по числу переменных
в K.
Базис индукции. Пусть K содержит все n
переменных из $$\mathbf{X}$$. Тогда $$N_K^+$$ состоит из единственного
набора и,
поскольку $$N_K^+ \subseteq N_{D_1}^+$$, то в $$D_1$$
сущетсвует конъюнкция K', для которой $$N_K^+ \subseteq N_{K'}^+$$.
Шаг индукции. Пусть для некоторого k < n утверждение
верно для всех f конъюнкций, содержащих
не менее (k+1) -ой переменной. Докажем, что оно верно и для k переменными.
Пусть f K
содержит k переменных и пусть $$X \in \mathbf{X}$$ -
переменная, не входящая в K. Тогда обе f и
по предположению индукции для них в $$\Phi _{1}$$ найдутся такие $$K_1^{\prime}$$ и $$K_2^{\prime}$$, что $$N_{K_1}^+ \subseteq N_{K_1'}^+$$ и $$N_{K_2}^+ \subseteq N_{K_2'}^+$$.
Если хотя бы одна из них не содержит X, то ее можно выбрать в
качестве K'. В противном случае, их можно представить в виде $$K_1^{\prime}= (X \wedge K_1^{\prime\prime})$$ и $$K_2^{\prime}= (\neg X \wedge K_2^{\prime\prime})$$.
При этом $$N_{K}^+ \subseteq N_{K_1"}^+$$ и $$N_{K}^+ \subseteq N_{K_2"}^+ $$.
Поскольку все преобразования вида (П3) выполнены, то D1
тогда содержит и конъюнкцию $$K^{\prime}= (K_1^{\prime\prime}\wedge K_2^{\prime\prime})$$,
для которой $$N_{K}^+ \subseteq N_{K'}^+$$.
Заметим, что если K f, то $$N_{K}^+ = N_{K'}^+$$. Таким образом,
все D1
.
Теперь, чтобы завершить доказательство теоремы, нужно
показать, что на этапе (2) из D1
будут удалены все немаксимальные D1
.)
Пример 4.2. Применим f(X1,X2,X3)
,
принимающей значение 1 на наборах множества $$N_f^+=\{(001), (010), (011), (101)\}$$.
Ее
После применения преобразований (П3) на (1)-ом этапе получим
$$D_1= (\neg X_1\wedge \neg X_2 \wedge X_3)\vee (\neg X_1\wedge X_2 \wedge \neg X_3)\vee (\neg X_1\wedge X_2 \wedge X_3)\vee\\ ( X_1\wedge \neg X_2 \wedge X_3)\vee (\neg X_2\wedge X_3) \vee (\neg X_1 \wedge X_2) \vee (\neg X_1 \wedge X_3)$$После поглощений (П1) на втором этапе останется
Заметим, что она не является самой короткой f,
т.к. $$D_2\equiv (\neg X_2\wedge X_3) \vee (\neg X_1 \wedge
X_2)
$$.
Определение 4.4. FJ={ 0, 1, *, +}
(здесь * - это другое обозначение конъюнкции)
Таким образом, каждый + и * справедливы * связывает аргументы сильнее, чем +
Нетрудно проверить, что справедливы следующие эквивалентности:
$$\begin{array}{lrcl} (J1) \neg X \equiv (X+ 1),\\ (J2) (X_1 \wedge X_2) \equiv (X_1*X_2),\\ (J3) (X_1 \vee X_2) \equiv (X_1*X_2 + X_1 +X_2),\\ (J4) (X_1 + X_2)*(X_3 + X_4) \equiv (X_1*X_2 + X_1*X_3 + X_2*X_3 + X_2*X_4) . \end{array}$$Из этих эквивалентностей и теоремы 4.1 легко получить первую часть следующего утверждения.
Теорема 4.3.
Для любой
Доказательство Существование такого многочлена следует из того,
что для любой + и *, а (J4) - перемножать получившиеся после такой замены многочлены.
Для доказательства единственности представления подсчитаем
число различных Xi1 * ... * Xik
,
где 1 <= i1 < ... < ik <= n
.
Таких конъюнкций столько же, сколько подмножеств множества $$\mathbf{X}=\{X_1,\ldots, X_n\}$$, т.е. 2n
.
(Конъюнкция, соответствующая пустому подмножеству переменных равна 1).
Упорядочим их произвольным образом (например, лексикографически): $$K_1, K_2,\ldots, K_{2^n}$$.
Tогда каждый
где каждый из коэффициентов $$\alpha _{i}$$ равен 0 или 1. Следовательно,
число n переменных. Поэтому каждая функция задается в
точности одним
Пример 4.3. Пусть функция f(X1,X2,X3)
задается
Сначала заменяем $$\wedge$$ на *, а затем,применяя
эквивалентность (J1), устраняем отрицания и получаем:
Перемножив по правилам (J4), получим:
$$\Phi \equiv (X_1*X_2+X_1) \vee (X_1* X_2 *X_3 + X_1*X_2 + X_2*X_3+ X_2)$$Эквивалентность (J3) позволяет устранить $$\vee:$$
$$\Phi \equiv (X_1*X_2+X_1) *(X_1* X_2 *X_3 + X_1*X_2 +\\+ X_2*X_3+X_2)+ (X_1*X_2+X_1) + \\+(X_1* X_2 *X_3 + X_1*X_2 + X_2*X_3+X_2).$$Снова, используя (J4), перемножим первые две скобки и устраним повторения переменных в конъюнкциях:
$$\Phi \equiv (X_1* X_2 *X_3 + X_1*X_2 +X_1*X_2*X_3+\\+X_1* X_2 *X_3 +X_1*X_2 +X_1* X_2 *X_3 +X_1*X_2 +X_1*X_2 )+\\+ (X_1*X_2+X_1) + (X_1* X_2 *X_3 + X_1*X_2 + X_2*X_3+X_2).$$Упростим эту сумму, используя эквивалентности: $$X + X \equiv 0$$ и $$X + 0 \equiv X$$. В результате получим
эквивалентный исходной
Если функция f(X1, ..., Xn)
задана таблично, то для построения реализующего ее i -ому набору значений переменных $$\sigma_i=(\sigma_i^1, \ldots, \sigma_i^n)$$ в таблице
положительную конъюнкцию $$K_i=\bigwedge_{\sigma_i^j=1} X_j$$ переменных, равных 1 в этом
наборе.
В частности, K1 - пустая конъюнкция, K2 = Xn,
K3 = Xn-1,
K4 = (Xn * Xn-1).
и т.д. Тогда для получения нужного
Подставляя в это равенство значения переменных из набора $$\sigma _{i},\ i = 1, \dots , 2^{n}$$,
мы получим 2n 2n
неизвестных коэффициентов $$\alpha _{i}$$. Решив эту систему, получим требуемый
Пример 4.4. Рассмотрим в качестве примера функцию f(X1, ..., Xn), заданную
следующей таблицей.
X1
|
X2
|
X3
|
f(X1, X2, X3)
|
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1. | 1 | 1 |
В этом представлении в индексах у коэффициентов $$\alpha$$ перечислены переменные, входящие в соответствующие конъюнкции.
Последовательно подставляя значения переменных и f из таблицы,
получаем:
Следовательно, функция f(X1, X2, X3) представляется
Задача 4.1. Проверьте все приведенные в лекции 4 эквивалентности (1) - (8), непосредственно вычисляя функции, представляемые их левыми и правыми частями.
Задача 4.2. Назовем логическим произведением формулу вида $$\Phi_1 \wedge \Phi_2 \wedge \ldots \wedge \Phi_n$$ (в этом выражении
использованы соглашения о сокращении записи!). Ее
Покажите, что из
n >= 2 и есть сомножитель, равный 1, то его можно вычеркнуть.n >= 2 и есть слагаемое, равное 0, то его можно вычеркнуть.Задача 4.3. Используя
Задача 4.4. Докажите теорему 4.1, проверив, что для любого набора значений аргументов $$\sigma_1, \ldots , \sigma_n$$ выполнены равенства $$f( \sigma_1, \ldots , \sigma_n) = \mathcal{D}_f( \sigma_1, \ldots , \sigma_n)$$ и $$f( \sigma_1, \ldots , \sigma_n) = \mathcal{C}_f( \sigma_1, \ldots , \sigma_n) $$.
Задача 4.5.
Задача 4.6.
Докажите, что для любого k <= n каждую булеву функцию $$f \in \mathcal{P}_n$$ можно представить в виде
Такое представление называется разложением $$f$$ по $$X_1, \ldots, X_k$$.
При k=n из него получается
Задача 4.7. Докажите предложение 4.1, используя индукцию по общему количеству функций $$\to$$ и + в формуле.
Задача 4.8. Как изменить (3)-ий, (4)-ый и (5)-ый этапы процедуры "Приведение к
Задача 4.9. Найти эквивалентные
Задача 4.10. Используя
Задача 4.11. Найти сокращенную дизъюнктивную нормальную форму и
f=(0010 1100)f=(1110 1100)f=(1100 0011)f=(0110 1011)Определение 4.1.
Обозначение: $$\Phi \equiv \Psi$$.
Таким образом,
Пусть $$\hat{}$$ - это одна из функций $$\wedge , \vee , +$$.
Для этих трех функций выполнены следующие две
Некоторые
Следующие две
Проверку правильности этих эквивалентностей оставляем читателям (см. задачу 4.1).
(X1 + X2 + X3)
для сокращения формул, состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно.Таким образом, с использованием этих соглашений формула
$$(((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).$$Из определения
пусть формула $$\alpha$$ является
Применяя этот принцип и используя 0, то получим Y. Эту цепочку
В этой цепочке вспомогательные номера под знаками эквивалентности
указывают, с помощью какой группы
Выведем еще несколько важных логических
Действительно,
$$X \vee (X \wedge \Phi) \underset{(6)}{\equiv} (X \wedge 1) \vee(X \wedge \Phi) \underset{(3)}{\equiv} X \wedge (1 \vee \Phi) \underset{(2,6)}{\equiv} X \wedge 1 \underset{(6)}{\equiv}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$$,
называется
Определение 4.2. Dj (j=1,...,r)
- это Dj
входят все n переменных из $$\mathbf{X}$$.
Рассмотрим произвольную булеву функцию f(X1,...,Xn)
, зависящую
от переменных из $$\mathbf{X}$$. Oбозначим через Nf+
множество наборов значений переменных, на которых f принимает значение 1, а через Nf-
множество наборов, на которых 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})$$Теорема 4.1.
f не равна тождественно 0, то
формула $$\mathcal{D}_f$$ - это f.f не равна тождественно 1, то
формула $$\mathcal{C}_f$$ - это f.Доказательство получается непосредственным вычислением значения каждой из указанных формул с учетом того, что для любого $$\sigma \in \{ 0, 1\}$$ имеют место равенства: $$1^{\sigma } = \sigma$$ и $$0^{\sigma } = \neg \sigma$$ (см. задачу 4.4).
Следствие 4.1.1.
Каждая
Приведенные выше формулы для $$\mathcal{D}_f$$ и $$\mathcal{C}_f$$ позволяют
эффективно строить f (Каким образом?). Можно ли получить такие специальные
представления по произвольной формуле, задающей f, не выписывая ее
полной таблицы? Приводимая ниже процедура позволяет это сделать, используя
Процедура Приведение к
Вход: формула $$\Phi,$$ включающая функции $$\neg , \wedge , \vee , \to$$ и +.
+
на $$\neg , \wedge$$ и $$\vee.$$Поскольку каждая из формул $$\Phi _{1}$$, $$\Phi _{2}$$ имеет
меньшую глубину, чем формула $$\Phi '$$, то предположим по индукции, что для них
уже построены эквивалентные
Тогда в случае (а) имеем:
$$\Phi^\prime \equiv (K_1^1 \vee \ldots \vee K_1^r)\wedge (K_2^1 \vee \ldots \vee K_2^s)\underset{(3)}{\equiv}\\(K_1^1\wedge K_2^1)\vee \ldots \vee (K_1^i\wedge K_2^j)\vee \ldots \vee (K_1^r\wedge K_2^s)$$Каждый член $$(K_1^i\wedge K_2^j)$$ этой дизъюнкции представляет собой
конъюнкцию переменных и их отрицаний. Применяя эквивалентности групп (1), (2) и
(6), можно удалить из нее повторения переменных, после чего она превратится
в некоторую (i,j), 1 <= i <= r, 1 <= j <= s, и удалив, если
потребуется, константы 0,
мы получим
В случае (б) формула $$\Phi^\prime \equiv (K_1^1 \vee K_1^2\vee \ldots \vee K_1^r)\vee (K_2^1 \vee K_2^2\vee \ldots \vee K_2^s)$$
сама уже является
Ki (i=1,..., m)
, эквивалентную Ki
, а затем устраним повторения одинаковых
конъюнкций.Из формулировок эквивалентностей (7) и (8) непосредственно вытекает
Предложение 4.1.
На этапе (1) процедуры при последовательном выполнении преобразований
(7), а затем - (8), до тех пор, пока ни одно из них не применимо, полученная
в результате формула не будет содержать функций $$\to$$ и +.
Доказательство этого предложения оставляем в виде упражнения (см. задачу 4.7).
Следующее утверждение гарантирует корректность этапа (2).
Предложение 4.2. На этапе (2) процедуры при любом порядке выполнения преобразований групп (4) и (5) до тех пор, пока ни одно из них не применимо, в полученной в результате формуле все знаки отрицания будут стоять непосредственно перед переменными.
Перед доказательством этого утверждения введем некоторые обозначения. Напомним, что в определениях 3.2 и 3.3 для каждой формулы $$\Phi$$ была определена ее глубина $$dep(\Phi )$$. Например, формула $$\Phi =\neg (X+Y)\to (\neg (X \vee \neg Z)\wedge Y)$$, построенная над системой $$F=\{ \vee , \wedge , \neg , \to , +\}$$, имеет глубину $$dep(\Phi )=5$$.
Пусть $$\Phi$$ - это формула над $$F=\{ \vee , \wedge , \neg \}$$.
Определим для каждой ее "отрицательной"
Доказательство предложения 4.2 проведем индукцией по высоте формул.
Базис индукции. Если $$H(\Phi )=0$$, то либо в $$\Phi$$ нет отрицаний, либо все отрицания находятся непосредственно перед переменными. Следовательно, $$\Phi$$ удовлетворяет требованию предложения 4.2.
Шаг индукции. Предположим, что при n <= k для всех
формул высоты n Предложение 4.2 выполнено.
Пусть $$\Phi$$ - произвольная формула высоты $$H(\Phi )= k+1$$. Докажем
наше утверждение для нее. Поскольку $$H(\Phi )\ge 1$$, то $$\Phi$$ содержит хотя бы одну отрицательную n=k+1, что завершает индукционный шаг и все доказательство.
Рассмотрим применение процедуры приведения к
Пример 4.1. Пусть формула $$\Phi= ((\neg X\vee Z) \rightarrow (Y \rightarrow (X + Z)))$$.
На (1)-ом этапе процедуры получаем следующую цепочку эквивалентностей:
$$\Phi \underset{(7)}{\equiv} \neg (\neg X\vee Z) \vee (Y \rightarrow (X + Z))\underset{(7)}{\equiv} \neg (\neg X\vee Z) \vee (\neg Y \vee (X+Z)) \underset{(8)}{\equiv}\\ \neg (\neg X\vee Z) \vee (\neg Y \vee ((X \wedge \neg Z) \vee (\neg X \wedge Z))).$$На (2)-ом этапе вносим отрицание внутрь первой скобки и получаем формулу
$$\Phi^\prime=(\neg \neg X \wedge \neg Z)\vee (\neg Y \vee ((X \wedge \neg Z) \vee (\neg X \wedge Z)))$$Устранив двойное отрицание, получим
$$\Phi^{\prime\prime}=( X \wedge \neg Z)\vee (\neg Y \vee ((X \wedge \neg Z) \vee (\neg X \wedge Z))).$$Нетрудно видеть, что это уже
Эта
Подставив эти формулы в $$\Phi _{1}$$ и устранив повторения конъюнкций,
получим
Мы видим, что
Следствие 4.1.2.
Для каждой булевой функции от n переменных, не равной
тождественно 0,
существует единственная с точностью до перестановки конъюнкций и переменных
внутри конъюнкций
Это следствие позволяет предложить следующую
X вхождения переменных в каждую
конъюнкцию, а затем лексикографически упорядочить между собой конъюнкции,
входящие в $$\Phi '$$ и $$\Psi '$$. Пусть в
результате получатся Замечание. Аналогичную процедуру можно построить с использованием
Напомним, что мы рассматриваем K принимает значение 1. Нетрудно понять, что это множество содержит 2(n-k)
наборов, в которых каждая из входящих в K переменных $$X_{i_r}\ (1 \leq r\leq k)$$
имеет фиксированное значение $$\sigma _{r}$$, а значения остальных (n-k) переменных произвольны.
Определение Пусть f - произвольная K называется f, если $$N_K^+ \subseteq N_f^+$$.
K называется f, если для любой L из условия $$N_K^+ \subseteq N_L^+\subseteq N_f^+$$ следует, что $$N_K^+ = N_L^+$$.
f называется дизъюнкция всех
Из этого определения непосредственно следует, что f единственна (с точностью до порядка f.
Примером
D,
используя процедуру, называемую
(П3): $$(X\wedge K_1) \vee (\neg X \wedge K_2) \equiv (X\wedge K_1) \vee (\neg X \wedge K_2) \vee (K_1\wedge K_2) $$
слева направо при условии, что конъюнкция $$(K_{1} \wedge K_{2})$$ непротиворечива, т.е. не содержит одновременно некоторую переменную и ее отрицание. (Заметим, что на этом этапе число(П1): $$X \vee (X\wedge K) \equiv X$$.
Затем удалить повторные вхождения конъюнкций.Теорема 4.2. В результате применения метода Блейка к произвольной
Доказательство
Пусть после (1)-го этапа процедуры D функции f
преобразовалась
в D1
. Покажем, что
для всякой допустимой для f K в D1
найдется такая
конъюнкция K', что $$N_K^+ \subseteq N_{K'}^+$$.
Доказательство проведем возвратной индукцией по числу переменных
в K.
Базис индукции. Пусть K содержит все n
переменных из $$\mathbf{X}$$. Тогда $$N_K^+$$ состоит из единственного
набора и,
поскольку $$N_K^+ \subseteq N_{D_1}^+$$, то в $$D_1$$
сущетсвует конъюнкция K', для которой $$N_K^+ \subseteq N_{K'}^+$$.
Шаг индукции. Пусть для некоторого k < n утверждение
верно для всех f конъюнкций, содержащих
не менее (k+1) -ой переменной. Докажем, что оно верно и для k переменными.
Пусть f K
содержит k переменных и пусть $$X \in \mathbf{X}$$ -
переменная, не входящая в K. Тогда обе f и
по предположению индукции для них в $$\Phi _{1}$$ найдутся такие $$K_1^{\prime}$$ и $$K_2^{\prime}$$, что $$N_{K_1}^+ \subseteq N_{K_1'}^+$$ и $$N_{K_2}^+ \subseteq N_{K_2'}^+$$.
Если хотя бы одна из них не содержит X, то ее можно выбрать в
качестве K'. В противном случае, их можно представить в виде $$K_1^{\prime}= (X \wedge K_1^{\prime\prime})$$ и $$K_2^{\prime}= (\neg X \wedge K_2^{\prime\prime})$$.
При этом $$N_{K}^+ \subseteq N_{K_1"}^+$$ и $$N_{K}^+ \subseteq N_{K_2"}^+ $$.
Поскольку все преобразования вида (П3) выполнены, то D1
тогда содержит и конъюнкцию $$K^{\prime}= (K_1^{\prime\prime}\wedge K_2^{\prime\prime})$$,
для которой $$N_{K}^+ \subseteq N_{K'}^+$$.
Заметим, что если K f, то $$N_{K}^+ = N_{K'}^+$$. Таким образом,
все D1
.
Теперь, чтобы завершить доказательство теоремы, нужно
показать, что на этапе (2) из D1
будут удалены все немаксимальные D1
.)
Пример 4.2. Применим f(X1,X2,X3)
,
принимающей значение 1 на наборах множества $$N_f^+=\{(001), (010), (011), (101)\}$$.
Ее
После применения преобразований (П3) на (1)-ом этапе получим
$$D_1= (\neg X_1\wedge \neg X_2 \wedge X_3)\vee (\neg X_1\wedge X_2 \wedge \neg X_3)\vee (\neg X_1\wedge X_2 \wedge X_3)\vee\\ ( X_1\wedge \neg X_2 \wedge X_3)\vee (\neg X_2\wedge X_3) \vee (\neg X_1 \wedge X_2) \vee (\neg X_1 \wedge X_3)$$После поглощений (П1) на втором этапе останется
Заметим, что она не является самой короткой f,
т.к. $$D_2\equiv (\neg X_2\wedge X_3) \vee (\neg X_1 \wedge
X_2)
$$.
Определение 4.4. FJ={ 0, 1, *, +}
(здесь * - это другое обозначение конъюнкции)
Таким образом, каждый + и * справедливы * связывает аргументы сильнее, чем +
Нетрудно проверить, что справедливы следующие эквивалентности:
$$\begin{array}{lrcl} (J1) \neg X \equiv (X+ 1),\\ (J2) (X_1 \wedge X_2) \equiv (X_1*X_2),\\ (J3) (X_1 \vee X_2) \equiv (X_1*X_2 + X_1 +X_2),\\ (J4) (X_1 + X_2)*(X_3 + X_4) \equiv (X_1*X_2 + X_1*X_3 + X_2*X_3 + X_2*X_4) . \end{array}$$Из этих эквивалентностей и теоремы 4.1 легко получить первую часть следующего утверждения.
Теорема 4.3.
Для любой
Доказательство Существование такого многочлена следует из того,
что для любой + и *, а (J4) - перемножать получившиеся после такой замены многочлены.
Для доказательства единственности представления подсчитаем
число различных Xi1 * ... * Xik
,
где 1 <= i1 < ... < ik <= n
.
Таких конъюнкций столько же, сколько подмножеств множества $$\mathbf{X}=\{X_1,\ldots, X_n\}$$, т.е. 2n
.
(Конъюнкция, соответствующая пустому подмножеству переменных равна 1).
Упорядочим их произвольным образом (например, лексикографически): $$K_1, K_2,\ldots, K_{2^n}$$.
Tогда каждый
где каждый из коэффициентов $$\alpha _{i}$$ равен 0 или 1. Следовательно,
число n переменных. Поэтому каждая функция задается в
точности одним
Пример 4.3. Пусть функция f(X1,X2,X3)
задается
Сначала заменяем $$\wedge$$ на *, а затем,применяя
эквивалентность (J1), устраняем отрицания и получаем:
Перемножив по правилам (J4), получим:
$$\Phi \equiv (X_1*X_2+X_1) \vee (X_1* X_2 *X_3 + X_1*X_2 + X_2*X_3+ X_2)$$Эквивалентность (J3) позволяет устранить $$\vee:$$
$$\Phi \equiv (X_1*X_2+X_1) *(X_1* X_2 *X_3 + X_1*X_2 +\\+ X_2*X_3+X_2)+ (X_1*X_2+X_1) + \\+(X_1* X_2 *X_3 + X_1*X_2 + X_2*X_3+X_2).$$Снова, используя (J4), перемножим первые две скобки и устраним повторения переменных в конъюнкциях:
$$\Phi \equiv (X_1* X_2 *X_3 + X_1*X_2 +X_1*X_2*X_3+\\+X_1* X_2 *X_3 +X_1*X_2 +X_1* X_2 *X_3 +X_1*X_2 +X_1*X_2 )+\\+ (X_1*X_2+X_1) + (X_1* X_2 *X_3 + X_1*X_2 + X_2*X_3+X_2).$$Упростим эту сумму, используя эквивалентности: $$X + X \equiv 0$$ и $$X + 0 \equiv X$$. В результате получим
эквивалентный исходной
Если функция f(X1, ..., Xn)
задана таблично, то для построения реализующего ее i -ому набору значений переменных $$\sigma_i=(\sigma_i^1, \ldots, \sigma_i^n)$$ в таблице
положительную конъюнкцию $$K_i=\bigwedge_{\sigma_i^j=1} X_j$$ переменных, равных 1 в этом
наборе.
В частности, K1 - пустая конъюнкция, K2 = Xn,
K3 = Xn-1,
K4 = (Xn * Xn-1).
и т.д. Тогда для получения нужного
Подставляя в это равенство значения переменных из набора $$\sigma _{i},\ i = 1, \dots , 2^{n}$$,
мы получим 2n 2n
неизвестных коэффициентов $$\alpha _{i}$$. Решив эту систему, получим требуемый
Пример 4.4. Рассмотрим в качестве примера функцию f(X1, ..., Xn), заданную
следующей таблицей.
X1
|
X2
|
X3
|
f(X1, X2, X3)
|
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1. | 1 | 1 |
В этом представлении в индексах у коэффициентов $$\alpha$$ перечислены переменные, входящие в соответствующие конъюнкции.
Последовательно подставляя значения переменных и f из таблицы,
получаем:
Следовательно, функция f(X1, X2, X3) представляется
Задача 4.1. Проверьте все приведенные в лекции 4 эквивалентности (1) - (8), непосредственно вычисляя функции, представляемые их левыми и правыми частями.
Задача 4.2. Назовем логическим произведением формулу вида $$\Phi_1 \wedge \Phi_2 \wedge \ldots \wedge \Phi_n$$ (в этом выражении
использованы соглашения о сокращении записи!). Ее
Покажите, что из
n >= 2 и есть сомножитель, равный 1, то его можно вычеркнуть.n >= 2 и есть слагаемое, равное 0, то его можно вычеркнуть.Задача 4.3. Используя
Задача 4.4. Докажите теорему 4.1, проверив, что для любого набора значений аргументов $$\sigma_1, \ldots , \sigma_n$$ выполнены равенства $$f( \sigma_1, \ldots , \sigma_n) = \mathcal{D}_f( \sigma_1, \ldots , \sigma_n)$$ и $$f( \sigma_1, \ldots , \sigma_n) = \mathcal{C}_f( \sigma_1, \ldots , \sigma_n) $$.
Задача 4.5.
Задача 4.6.
Докажите, что для любого k <= n каждую булеву функцию $$f \in \mathcal{P}_n$$ можно представить в виде
Такое представление называется разложением $$f$$ по $$X_1, \ldots, X_k$$.
При k=n из него получается
Задача 4.7. Докажите предложение 4.1, используя индукцию по общему количеству функций $$\to$$ и + в формуле.
Задача 4.8. Как изменить (3)-ий, (4)-ый и (5)-ый этапы процедуры "Приведение к
Задача 4.9. Найти эквивалентные
Задача 4.10. Используя
Задача 4.11. Найти сокращенную дизъюнктивную нормальную форму и
f=(0010 1100)f=(1110 1100)f=(1100 0011)f=(0110 1011)
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.