Math Problems Vault

Problem 141

Prove that the formula $\Phi$ implies the formula $\Psi$ if and only if $\Phi \wedge \Psi \equiv \Phi$ , if and only if $\Phi \vee \Psi \equiv \Psi . \quad \circledast$

?

Problem 142

Verify all the basic equivalences given at the beginning of the section by directly constructing truth tables for the functions represented by their left- and right-hand sides.

?

Problem 143

(a)(b)(c)(d)

Let us call a logical product a formula of the form $\Phi_{1} \wedge \Phi_{2} \wedge \ldots \wedge \Phi_{n}$ . We will call its subformulas $\Phi_{i}, 1 \leqslant i \leqslant n$ , factors. Similarly, let us call a logical sum a formula of the form $\Phi_{1} \vee \Phi_{2} \vee \ldots \vee \Phi_{n}$ . We will call its subformulas $\Phi_{i}$ , $1 \leqslant i \leqslant n$ , terms.

Show that the following rules for transforming logical products and sums can be derived from the basic identities:

?

(a)

if in a logical product at least one of the factors equals 0, then the whole product equals 0;

(b)

if in a logical sum at least one of the terms equals 1, then the whole sum equals 1;

(c)

if in a logical product $n \geqslant 2$ and there is a factor equal to 1, then it can be struck out;

(d)

if in a logical sum $n \geqslant 2$ and there is a term equal to 0, then it can be struck out.

Problem 144

(a)(b)(c)

Using the basic identities, prove the equivalence of the following pairs of formulas.

?

(a)

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

(b)

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

(c)

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

Problem 145

Derive the absorption laws using the previous equivalences.

?

Problem 146

Prove the following equivalences:

?

(a)

$\Phi \rightarrow 0 \equiv \neg \Phi$ ;

(b)

$1 \rightarrow \Phi \equiv \Phi$ ;

(c)

$(\Phi \rightarrow \Psi ) \rightarrow \Psi \equiv \Phi \vee \Psi$ ;

(d)

$\neg \Phi \rightarrow \Phi \equiv \Phi$ ;

(e)

$(\Phi \rightarrow \Phi ) \rightarrow \Phi \equiv \Phi$ ;

(f)

$\Phi \leftrightarrow \Psi \equiv (\Phi \rightarrow \Psi ) \wedge (\Psi \rightarrow \Phi ) ;$

(g)

$~ \Phi \vee (\neg \Phi \wedge \Psi ) \equiv \Phi \vee \Psi$ ;

(h)

$(\Phi \rightarrow \Psi ) \oplus (\Psi \rightarrow \Phi ) \equiv \Phi \oplus \Psi$ .

(i)

$\Phi \rightarrow (\Psi \vee \Theta ) \equiv (\Phi \wedge \neg \Theta ) \rightarrow \Psi$ ;

(j)

$(\Phi \wedge \Theta ) \rightarrow \Psi \equiv \Phi \rightarrow (\Psi \vee \neg \Theta )$ .

Problem 147

Using the basic identities, prove that the following formulas are identically true:

?

(a)

$(x \rightarrow (y \rightarrow x))$

(b)

$((x \wedge y) \rightarrow x)$

(c)

$(x \rightarrow (x \vee y))$

(d)

$((x \rightarrow \neg y) \rightarrow \neg (x \wedge y))$

(e)

$(((x \rightarrow y) \wedge (y \rightarrow z)) \rightarrow (x \rightarrow z))$

(f)

$(((x \rightarrow y) \vee (x \rightarrow z)) \rightarrow (x \rightarrow (y \vee z)))$

(g)

$((x \rightarrow y) \rightarrow ((x \rightarrow \neg y) \rightarrow \neg x))$

(h)

$((x \rightarrow (y \rightarrow z)) \rightarrow ((x \rightarrow y) \rightarrow (x \rightarrow z)))$

Problem 148

Suppose that the interpretation $J$ differs from the interpretation $I$ only in that $J(x)=I(Θ)$ . By induction on the construction of the formula $\Phi$ , prove that $J(\Phi )=I\left((\Phi )_{\Theta }^{x}\right)$ .

?

Problem 149

Prove that if $\Phi \equiv \Psi$ , then $(\Phi )_{\Theta }^{x} \equiv (\Psi )_{\Theta }^{x}$ .

?

Problem 150

(a)(b)

Let the formulas $\Phi_{0}$ and $\Phi_{1}$ be obtained from the formula $\Phi$ by replacing the variable $x_{i}$ with 0 and 1 respectively. Prove that the formula $\Phi$ is equivalent to each of the following:

?

(a)

$\left(\neg x_{i} \wedge \Phi_{0}\right) \vee \left(x_{i} \wedge \Phi_{1}\right) ;$

(b)

$\left(\neg x_{i} \rightarrow \Phi_{0}\right) \wedge \left(x_{i} \rightarrow \Phi_{1}\right)$ .

Problem 151

(a)(b)

A Boolean function $f^{*}\left(x_{1}, \ldots , x_{n}\right)$ is called dual to a function $f\left(x_{1}, \ldots , x_{n}\right)$ if $f^{*}\left(x_{1}, \ldots , x_{n}\right)=\neg f\left(\neg x_{1}, \ldots , \neg x_{n}\right)$ for every tuple of values of the variables. For example, conjunction is dual to disjunction and vice versa.

?

(a)

Prove that the duality relation is symmetric.

(b)

Let $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)$ be Boolean functions and

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

Establish the following duality principle: the dual function of a superposition of functions equals the superposition of the dual functions:

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

Problem 152

(a)(b)(c)(d)

Construct the dual functions for the functions

?

(a)

$\neg$ ,

(b)

→,

(c)

$\oplus$ ,

(d)

↑.

Problem 153

(a)(b)(c)

Construct the dual functions for the functions given by the following formulas:

?

(a)

$(x \rightarrow \neg (\neg y \oplus x \oplus z))$ ;

(b)

$((x \uparrow y) \oplus (\neg x \rightarrow z))$ ; $\circledast$

(c)

$((x \vee \neg y) \rightarrow (\neg x \downarrow y))$ .

Problem 154

(a)(b)(c)

?

(a)

Prove that among 20 formulas in the variables $x_{1}, x_{2}$ there will always be two that are equivalent.

(b)

Is it true that among 20 formulas in the variables $x_{1}, x_{2}$ there will always be three that are pairwise equivalent?

(c)

Suppose there are $k$ formulas in $n$ variables $x_{1}, \ldots , x_{n}$ . We need to choose several pairwise equivalent formulas. What number of such formulas can be guaranteed to be found?

Problem 155

Let us call a formula $\Phi$ (and the function it defines) implicative if it is obtained by some placement of parentheses in the string $x_{1} \rightarrow x_{2} \rightarrow \cdots \rightarrow x_{n-1} \rightarrow x_{n}$ . Prove that

?

(a)

every implicative formula takes value 1 on at least one tuple;

(b)

every implicative formula takes value 0 on at least one tuple;

(c)

for every implicative formula with $n \geqslant 2$ variables and every value $\sigma_{k}$ of the variable $x_{k}$ , it is possible to extend $\sigma_{k}$ to a tuple of values $\bar{\sigma }$ of all the variables on which the formula has value 1;

(d)

every implicative function has no dummy arguments;

(e)

no two distinct implicative formulas are equivalent.

Problem 156

Prove that a function $f$ can be obtained from some implicative function $g$ by substitution of variables:

f\left(x_{1}, \ldots , x_{n}\right)=g\left(x_{i_{1}}, \ldots , x_{i_{m}}\right)

if and only if $f$ is given by a formula of the form $x_{i} \vee \Psi$ for some variable $x_{i}$ .

?