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

Доказать, что из формулы $\Phi$ следует формула $\Psi$ тогда и только тогда, когда $\Phi \wedge \Psi \equiv \Phi$, тогда и только тогда, когда $\Phi \vee \Psi \equiv \Psi$.

Проверить все приведённые в параграфе 4.1 эквивалентности 1)-9), непосредственно построив истинностные таблицы для функций, представляемых их левыми и правыми частями.

Девять эквивалентностей (здесь $\Phi$, $\Psi$, $\Theta$ — произвольные формулы):

1. Ассоциативность: $(\Phi \wedge \Psi ) \wedge \Theta \equiv \Phi \wedge (\Psi \wedge \Theta )$; $(\Phi \vee \Psi ) \vee \Theta \equiv \Phi \vee (\Psi \vee \Theta )$; $(\Phi \oplus \Psi ) \oplus \Theta \equiv \Phi \oplus (\Psi \oplus \Theta )$.

2. Коммутативность: $\Phi \wedge \Psi \equiv \Psi \wedge \Phi$; $\Phi \vee \Psi \equiv \Psi \vee \Phi$; $\Phi \oplus \Psi \equiv \Psi \oplus \Phi$.

3. Дистрибутивность: $(\Phi \vee \Psi ) \wedge \Theta \equiv (\Phi \wedge \Theta ) \vee (\Psi \wedge \Theta )$; $(\Phi \wedge \Psi ) \vee \Theta \equiv (\Phi \vee \Theta ) \wedge (\Psi \vee \Theta )$; $(\Phi \oplus \Psi ) \wedge \Theta \equiv (\Phi \wedge \Theta ) \oplus (\Psi \wedge \Theta )$.

4. Законы де Моргана: $\neg (\Phi \vee \Psi ) \equiv \neg \Phi \wedge \neg \Psi$; $\neg (\Phi \wedge \Psi ) \equiv \neg \Phi \vee \neg \Psi$.

5. Закон двойного отрицания: $\neg \neg \Phi \equiv \Phi$.

6. Идемпотентность: $\Phi \wedge \Phi \equiv \Phi$; $\Phi \vee \Phi \equiv \Phi$.

7. Законы для констант: $\Phi \wedge \neg \Phi \equiv 0$; $\Phi \vee \neg \Phi \equiv 1$; $\Phi \wedge 0 \equiv 0$; $\Phi \vee 0 \equiv \Phi$; $\Phi \wedge 1 \equiv \Phi$; $\Phi \vee 1 \equiv 1$.

8. $\Phi \rightarrow \Psi \equiv \neg \Phi \vee \Psi$.

9. $\Phi \oplus \Psi \equiv (\Phi \wedge \neg \Psi ) \vee (\neg \Phi \wedge \Psi ) \equiv (\Phi \vee \Psi ) \wedge (\neg \Phi \vee \neg \Psi )$.

Назовём логическим произведением формулу, имеющую вид $\Phi_{1} \wedge \Phi_{2} \wedge \ldots \wedge \Phi_{n}$. Её подформулы $\Phi_{i}, 1 \leqslant i \leqslant n$, будем называть сомножителями. Аналогично, логической суммой назовём формулу вида $\Phi_{1} \vee \Phi_{2} \vee \ldots \vee \Phi_{n}$. Её подформулы $\Phi_{i}, 1 \leqslant i \leqslant n$, будем называть слагаемыми.

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

Используя основные тождества, доказать эквивалентность следующих пар формул.

Пусть интерпретация $J$ отличается от интерпретации $I$ только тем, что $J(x)=I(\Theta )$. Индукцией по построению формулы $\Phi$ доказать, что $J(\Phi )=I\left((\Phi )_{\Theta }^{x}\right)$.

Доказать предложение 19 на стр. 81.

Предложение 19: Если в двух эквивалентных формулах $\Phi$ и $\Psi$ заменить пропозициональную переменную $x$ на формулу $\Theta$, то полученные формулы снова будут эквивалентными: если $\Phi \equiv \Psi$, то $(\Phi )_{\Theta }^{x} \equiv (\Psi )_{\Theta }^{x}$.

Булева функция $f^{*}\left(x_{1}, \ldots , x_{n}\right)$ называется двойственной к функции $f\left(x_{1}, \ldots , x_{n}\right)$, если $f^{*}\left(x_{1}, \ldots , x_{n}\right)=\neg f\left(\neg x_{1}, \ldots , \neg x_{n}\right)$ для каждого набора значений переменных. Например, конъюнкция двойственна к дизъюнкции и наоборот.

Индукцией по построению формулы $\Phi$ доказать неравенство

Привести пример, когда неравенство будет строгим.

Напомним обозначение: для формулы $\Phi$ и $\sigma \in \left\{ 0,1\right\}$ пишем $\Phi^{\sigma } = \Phi$, если $\sigma = 1$, и $\Phi^{\sigma } = \neg \Phi$, если $\sigma = 0$; отсюда $1^{\sigma } \equiv \sigma$, $0^{\sigma } \equiv \neg \sigma$, $\sigma^{\sigma } \equiv 1$ и $\sigma^{\tau } \equiv 0$ при $\sigma \neq \tau$ (формула (7)). Для булевой функции $f\left(x_1, \ldots , x_n\right)$ определим

Теорема 21: Пусть $f$ — булева функция. 1) Если $f$ не равна тождественно нулю, то $\mathcal{D}_{f}$ — совершенная ДНФ, задающая функцию $f$. 2) Если $f$ не равна тождественно единице, то $\mathcal{C}_{f}$ — совершенная КНФ, задающая функцию $f$. (Первая часть доказана в тексте; вторая часть — это данная задача.)

Доказать вторую часть теоремы 21 на стр. 84 : для каждого набора значений аргументов $\sigma_{1}, \ldots , \sigma_{n}$ выполнено $f\left(\sigma_{1}, \ldots , \sigma_{n}\right)=\mathcal{C}_{f}\left(\sigma_{1}, \ldots , \sigma_{n}\right)$.

Предложить процедуры для решения следующих задач:

Доказать, что для всех $k \leqslant n$ каждую булеву функцию $f \in \mathcal{P}_{n}$ можно представить в виде

Такое представление называется разложением $f$ по $x_{1}, \ldots , x_{k}$. При $k=n$ из него получается совершенная ДНФ из теоремы 21 на стр. 84.

Как изменить процедуру приведения к совершенной ДНФ, чтобы в результате получить процедуру приведения к совершенной КНФ?

Предложить метод одновременного построения эквивалентных ДНФ и КНФ для произвольной формулы $\Phi$ логики высказываний, используя индукцию по построению $\Phi$.

Найти эквивалентные сокращённые ДНФ и доказать эквивалентность следующих пар формул:

Допустим, ДНФ $\mathcal{D}$ не содержит отрицаний и к ней не применимы законы поглощения. Доказать, что $\mathcal{D}$ является сокращённой ДНФ.

Доказать эквивалентности (8)-(11).

1. $\neg x \equiv (x \oplus 1)$.

2. $\left(x_{1} \wedge x_{2}\right) \equiv \left(x_{1} x_{2}\right)$.

3. $\left(x_{1} \vee x_{2}\right) \equiv \left(x_{1} x_{2} \oplus x_{1} \oplus x_{2}\right)$.

4. $\left(x_{1} \oplus x_{2}\right)\left(x_{3} \oplus x_{4}\right) \equiv \left(x_{1} x_{3} \oplus x_{1} x_{4} \oplus x_{2} x_{3} \oplus x_{2} x_{4}\right)$.

Доказать равенства (12) и (13).

Используя основные эквивалентности и тождества (8)-(11), найти эквивалентные приведённые многочлены Жегалкина и доказать эквивалентность следующих пар формул:

Найти многочлены Жегалкина (методом неопределённых коэффициентов и с помощью матрицы $J$) для следующих функций $f(x, y, z)$. Считаем, что наборы аргументов функций упорядочены лексикографически и значения на них задаются последовательностью 8 нулей и единиц:

Найти булеву функцию от $n$ переменных, у которой приведённый многочлен Жегалкина имеет наибольшую длину.