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

Задача 157

Доказать эквивалентности при $\sigma , \tau \in \mathbb {B}, \sigma \neq \tau$

1^{\sigma } \equiv \sigma ; \quad 0^{\sigma } \equiv \neg \sigma ; \quad \sigma ^{\sigma } \equiv 1 ; \quad \sigma ^{\tau } \equiv 0. \tag {5}

?

Задача 158

(а)(б)

Определить, сколько из $n$ переменных $x_{1}, \ldots , x_{n}$ и их отрицаний можно составить

?

(а)

неэквивалентных элементарных конъюнкций, содержащих ровно $k$ элементов и не содержащих одну и ту же переменную два или более раз;

(б)

всего неэквивалентных элементарных конъюнкций.

Задача 159

Доказать равенства (3) и (4): для каждого набора значений аргументов $\sigma_{1}, \ldots , \sigma_{n}$ выполнено

f\left(\sigma _{1}, \ldots , \sigma _{n}\right)=\mathcal{D}_{f}\left(\sigma _{1}, \ldots , \sigma _{n}\right)=\mathcal{C}_{f}\left(\sigma _{1}, \ldots , \sigma _{n}\right).

?

Задача 160

(а)(б)

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

?

(а)

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

(б)

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

Задача 161

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

\begin{aligned} f\left(x_{1}, \ldots ,\right. & \left.x_{k}, x_{k+1}, \ldots , x_{n}\right)= \\ & \quad =\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$ из него получается совершенная ДНФ (3).

?

Задача 162

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

?

Задача 163

(а)(б)(в)

Используя основные эквивалентности, построить для следующих формул эквивалентные совершенные ДНФ и КНФ:

?

(а)

$\Phi_{1}=((x \uparrow y) \vee (z \oplus x)) \rightarrow \neg y$ ;

(б)

$\Phi_{2}=((\neg x \oplus z) \rightarrow (x \vee y)) \wedge (\neg x \rightarrow \neg y)$ ;

(в)

$\Phi_{3}=(((z \vee x) \oplus y) \vee (x \rightarrow \neg z)) \wedge z$ .

Задача 164

(а)(б)(в)

Преобразовать следующие ДНФ в эквивалентные совершенные ДНФ:

?

(а)

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

(б)

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

(в)

$x \vee (\neg x \wedge z) \vee (y \wedge z) \vee (\neg x \wedge \neg y)$ .

Задача 165

(а)(б)(в)

Преобразовать следующие КНФ в эквивалентные совершенные КНФ:

?

(а)

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

(б)

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

(в)

$(\neg x \vee z) \wedge (y \vee z) \wedge (\neg x \vee \neg y)$ .

Задача 166

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

?

Задача 167

(а)(б)(в)

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

?

(а)

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

(б)

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

(в)

$x \vee (\neg x \wedge z) \vee (\neg x \wedge y \wedge z) \vee (\neg x \wedge \neg y \wedge \neg z)$ .

Задача 168

Функция $f(x, y, z)$ , задана следующей последовательностью восьми нулей и единиц при лексикографическом упорядочении аргументов: $f=(10111010)$ . Определить, какие из следующих элементарных конъюнкций являются импликантами и какие из них минимальными импликантами для функции $f$ :

?

(а)

$\neg x \wedge y \wedge z$ ;

(б)

$\neg z$ ;

(в)

$x \wedge \neg y$ ;

(г)

$\neg x \wedge y$ ;

(д)

$\neg y$ ;

(е)

$x \wedge \neg z$ . $\circledast$

Задача 169

Доказать, что минимальная ДНФ состоит из минимальных импликантов.

?

Задача 170

Доказать, что совершенная, сокращённая и минимальная ДНФ для функции odd $\left(x_{1}, \ldots , x_{n}\right)=x_{1} \oplus \cdots \oplus x_{n}$ совпадают и имеют $2^{n-1}$ элементарных конъюнкций длины $n$ .

?

Задача 171

Доказать, что сокращённая ДНФ для функции odd из задачи 170 на предыдущей странице состоит из наибольшего количества элементарных дизъюнкций среди функций с $n$ переменными.

?

Задача 172

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

?

(а)

$f=(10110011)$ ;

(б)

$f=(00111001)$ ;

(в)

$f=(11101011)$ ;

(г)

$f=(00111011)$ ;

(д)

$f=(00010111)$ ;

(е)

$f=(01110101)$ .

Задача 173

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

?

(а)

$\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))$ .

Задача 174

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

?

Задача 175

Привести пример ДНФ $\mathcal{D}$ и минимального импликанта $C$ для неё таких, что $C$ не является частью какой-то конъюнкции из $\mathcal{D}. \circledast$

?

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