Банк задач по математике

Задача 65

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

?

Задача 66

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

?

Задача 67

(а)(б)(в)(г)

Назовём логическим произведением формулу, имеющую вид $\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$ , будем называть с лагаемыми.

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

?

(а)

если в логическом произведении хотя бы один из сомножителей равен 0, то и всё произведение равно 0 ;

(б)

если в логической сумме хотя бы одно из слагаемых равно 1, то и вся сумма равна 1 ;

(в)

если в логическом произведении $n \geqslant 2$ и есть сомножитель равный 1, то его можно вычеркнуть;

(г)

если в логической сумме $n \geqslant 2$ и есть слагаемое равное 0, то его можно вычеркнуть.

Задача 68

(а)(б)(в)

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

?

(а)

$\neg (x \vee \neg y) \wedge (x \rightarrow \neg y)$ и $\neg x \wedge y$ ;

(б)

$\neg ((x \wedge \neg y) \rightarrow (\neg x \vee z))$ и $x \wedge \neg y \wedge \neg z$ ;

(в)

$(x \oplus y) \rightarrow (x \wedge \neg y)$ и $(\neg x \wedge \neg y) \vee x$ .

Задача 69

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

?

Задача 70

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

?

Задача 71

(а)(б)

Булева функция $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)$ для каждого набора значений переменных. Например, конъюнкция двойственна к дизъюнкции и наоборот.

?

(а)

Доказать, что отношение двойственности симметрично.

(б)

Пусть $f\left(y_{1}, \ldots , y_{m}\right), g_{1}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}\left(x_{1}, \ldots , x_{n}\right)$ — булевы функции и

h\left(x_{1}, \ldots , x_{n}\right)=f\left(g_{1}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}\left(x_{1}, \ldots , x_{n}\right)\right).

Установить следующий принцип двойственности: двойственная функция от суперпозиции функций равна суперпозиции двойственных функций:

h^{*}\left(x_{1}, \ldots , x_{n}\right)=f^{*}\left(g_{1}^{*}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}^{*}\left(x_{1}, \ldots , x_{n}\right)\right).

Задача 72

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

\operatorname {depth}(\Phi )_{\Psi }^{x} \leqslant \operatorname {depth} \Phi +\operatorname {depth} \Psi

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

?

Задача 73

Доказать вторую часть теоремы 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)$ .

?

Задача 74

(а)(б)

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

?

(а)

По произвольной элементарной конъюнкции построить эквивалентную ей совершенную ДНФ с заданным множеством переменных.

(б)

По произвольной элементарной дизъюнкции построить эквивалентную ей совершенную КНФ с заданным множеством переменных.

Задача 75

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

\begin{aligned} f\left(x_{1}, \ldots , x_{k}, x_{k+1}, \ldots ,\right. & \left.x_{n}\right)= \\ & =\bigvee _{\left(\sigma _{1}, \ldots , \sigma _{k}\right) \in \mathbb {B}^{k}} x_{1}^{\sigma _{1}} \wedge \ldots \wedge x_{k}^{\sigma _{k}} \wedge f\left(\sigma _{1}, \ldots , \sigma _{k}, x_{k+1}, \ldots , x_{n}\right). \end{aligned}

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

?

Задача 76

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

?

Задача 77

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

?

Задача 78

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

?

(а)

$\Phi =(((\neg x \wedge \neg y) \rightarrow \neg z) \wedge (x \rightarrow y)), \Psi =((1 \oplus y) \rightarrow (\neg x \wedge (1 \oplus z)))$ ;

(б)

$\Phi =\left(\neg \left(\left(x_{1} \rightarrow x_{2}\right) \vee \neg \left(x_{2} \rightarrow x_{1}\right)\right) \wedge x_{3}\right), \Psi =\neg \left(\left(x_{1} \wedge x_{3}\right) \rightarrow x_{2}\right)$ ;

(в)

$\Phi =\neg (\neg x \wedge y \wedge \neg z) \rightarrow ((y \oplus 1) \wedge ((x \oplus 1) \rightarrow \neg (\neg u \vee z)))$ , $\Psi =(\neg x \vee y) \rightarrow ((\neg u \vee y \vee z) \rightarrow (\neg (x \vee \neg y) \wedge \neg z)) ;$

(г)

$\Phi =(\neg (x \rightarrow (\neg y \rightarrow (x \wedge \neg z))) \wedge (z \vee \neg (x \wedge y)))$ , $\Psi =((x \wedge z) \oplus (x \wedge y \wedge z)) ;$

(д)

$\Phi =(((x \wedge y) \rightarrow \neg z) \wedge (\neg x \rightarrow \neg y)), \Psi =(y \rightarrow (x \wedge (z \oplus 1)))$ ;

(е)

$\Phi =(((x \vee y) \rightarrow \neg z) \wedge ((x \wedge z) \rightarrow y)), \Psi =(z \rightarrow ((x \oplus 1) \wedge \neg y))$ .

Задача 79

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

?

Задача 80

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

?

Задача 81

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

?

Задача 82

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

?

(а)

$\Phi =((z \wedge (x \rightarrow y)) \vee \neg (\neg x \rightarrow z)), \Psi =(x \rightarrow (y \wedge z))$ ;

(б)

$\Phi =\neg (x \rightarrow (y \wedge z)) \wedge (\neg y \vee \neg x)$ , $\Psi =(\neg (x \rightarrow y) \vee z) \wedge \neg ((\neg x \wedge z) \vee (y \wedge z)) ;$

(в)

$\Phi =(((y \wedge z) \rightarrow \neg (x \vee z)) \wedge \neg (\neg y \wedge z \wedge x)), \Psi =(z \rightarrow (\neg y \wedge \neg x))$ ;

(г)

$\Phi =\neg (((x \rightarrow y) \vee \neg z) \wedge x), \Psi =(\neg (z \rightarrow y) \vee \neg x)$ ;

(д)

$\Phi =(\neg ((x \rightarrow y) \vee \neg (y \rightarrow x)) \wedge z), \Psi =\neg ((x \wedge z) \rightarrow y)$ .

Задача 83

(а)(б)(в)(г)

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

?

(а)

$f=(00101100)$ ;

(б)

$f=(11101100)$ ;

(в)

$f=(11000011)$ ;

(г)

$f=(01101011)$ .

Задача 84

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

?

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