Math Problems Vault

Problem 157

Prove the equivalences for $\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}

?

Problem 158

(a)(b)

Determine how many, out of $n$ variables $x_{1}, \ldots , x_{n}$ and their negations, one can form

?

(a)

non-equivalent elementary conjunctions containing exactly $k$ elements and not containing the same variable two or more times;

(b)

non-equivalent elementary conjunctions in total.

Problem 159

Prove equalities (3) and (4): for every tuple of argument values $\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).

?

Problem 160

(a)(b)

Propose procedures for solving the following problems:

?

(a)

Given an arbitrary elementary conjunction, construct an equivalent perfect DNF with a given set of variables.

(b)

Given an arbitrary elementary disjunction, construct an equivalent perfect CNF with a given set of variables.

Problem 161

Prove that for all $k \leqslant n$ every Boolean function $f \in \mathcal{P}_{n}$ can be represented in the form

\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}

Such a representation is called the expansion of $f$ with respect to $x_{1}, \ldots , x_{k}$ . For $k=n$ it gives the perfect DNF (3).

?

Problem 162

Propose a method for simultaneously constructing equivalent DNF and CNF for an arbitrary formula $\Phi$ of propositional logic, using induction on the construction of $\Phi$ .

?

Problem 163

(a)(b)(c)

Using the basic equivalences, construct equivalent perfect DNF and CNF for the following formulas:

?

(a)

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

(b)

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

(c)

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

Problem 164

(a)(b)(c)

Convert the following DNFs into equivalent perfect DNFs:

?

(a)

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

(b)

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

(c)

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

Problem 165

(a)(b)(c)

Convert the following CNFs into equivalent perfect CNFs:

?

(a)

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

(b)

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

(c)

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

Problem 166

Give an example of a three-place Boolean function $f$ possessing the following property: if in the perfect DNF for $f$ conjunctions are replaced by disjunctions and disjunctions by conjunctions, one obtains a perfect CNF for $f$ .

?

Problem 167

(a)(b)(c)

Using the basic equivalences, convert the following DNFs into CNFs:

?

(a)

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

(b)

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

(c)

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

Problem 168

The function $f(x, y, z)$ is given by the following sequence of eight zeros and ones under a lexicographic ordering of the arguments: $f=(10111010)$ . Determine which of the following elementary conjunctions are implicants and which of them are minimal implicants for the function $f$ :

?

(a)

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

(b)

$\neg z$ ;

(c)

$x \wedge \neg y$ ;

(d)

$\neg x \wedge y$ ;

(e)

$\neg y$ ;

(f)

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

Problem 169

Prove that a minimal DNF consists of minimal implicants.

?

Problem 170

Prove that the perfect, reduced, and minimal DNF for the function odd $\left(x_{1}, \ldots , x_{n}\right)=x_{1} \oplus \cdots \oplus x_{n}$ coincide and have $2^{n-1}$ elementary conjunctions of length $n$ .

?

Problem 171

Prove that the reduced DNF for the function odd from problem 170 on the previous page consists of the largest number of elementary conjunctions among functions with $n$ variables.

?

Problem 172

The tuples of values of the three arguments $x, y$ and $z$ of Boolean functions are ordered lexicographically. Their values are given by the following sequences of eight zeros and ones. For each of them determine the perfect DNF and CNF and the reduced DNF:

?

(a)

$f=(10110011)$ ;

(b)

$f=(00111001)$ ;

(c)

$f=(11101011)$ ;

(d)

$f=(00111011)$ ;

(e)

$f=(00010111)$ ;

(f)

$f=(01110101)$ .

Problem 173

Find equivalent reduced DNFs and prove the equivalence of the following pairs of formulas:

?

(a)

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

(b)

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

(c)

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

(d)

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

(e)

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

(f)

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

Problem 174

Suppose the DNF $\mathcal{D}$ contains no negations and the absorption laws are not applicable to it. Prove that $\mathcal{D}$ is a reduced DNF.

?

Problem 175

Give an example of a DNF $\mathcal{D}$ and a minimal implicant $C$ for it such that $C$ is not part of any conjunction from $\mathcal{D}. \circledast$

?