Math Problems Vault

Problem II.2.1

Show that to each formula $A$ of the algebra of propositions one can assign a function $\varphi (A)$ of the algebra of logic such that

A_{1} \sim A_{2} \Leftrightarrow \varphi (A_{1}) = \varphi (A_{2}).

?

Problem II.2.2

How many functions of the algebra of logic in $n$ variables are there?

?

Problem II.2.3

(a)(b)(c)

Find all essential variables of the following functions:

?

(a)

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

(b)

$(x \& y) \vee \neg x$ ;

(c)

$(x \supset (y \supset z)) \supset ((x \supset y) \supset (x \supset z))$ .

Problem II.2.4

Express by means of superpositions:

?

(a)

and $\supset$ in terms of $\vee$ and $\neg$ ;

(b)

$\vee$ and $\supset$ in terms of and $\neg$ ;

(c)

and $\vee$ in terms of $\supset$ and $\neg$ ;

(d)

, $\vee$ , $\supset$ , $\neg$ in terms of $\mid$ ;

(e)

$\neg$ in terms of $\supset$ and 0;

(f)

$\neg$ in terms of $+$ and 1;

(g)

$\vee$ in terms of $\supset$ .

Problem II.2.5

Prove that $C_{1}, C_{0}, L, D$ and $M$ are distinct closed classes, different from $C$ .

?

Problem II.2.6

(a)(b)(c)

Prove that it is impossible to express by means of superpositions:

?

(a)

$\neg$ in terms of , $\vee$ , $\supset$ and $\equiv$ ;

(b)

$\supset$ in terms of , $\vee$ ;

(c)

in terms of $\vee$ , $\supset$ .

Problem II.2.7

(a)(b)

?

(a)

Prove that for every function $f(x, x_{1}, \ldots , x_{n})$ the equality holds:

f(x, x_{1}, \ldots , x_{n}) = (x \cdot f(1, x_{1}, \ldots , x_{n})) \vee (\neg x \cdot f(0, x_{1}, \ldots , x_{n})).

(b)

Let $n \geq i \geq 1$ . Prove that every function $f(x_{1}, \ldots , x_{n})$ of the algebra of logic can be represented in the form

f(x_{1}, \ldots , x_{i}, x_{i + 1}, \ldots , x_{n}) = \bigvee _{\varepsilon _{1}, \ldots , \varepsilon _{i}} (x_{1}^{\varepsilon _{1}} \cdot \ldots \cdot x_{i}^{\varepsilon _{i}}) \cdot f(\varepsilon _{1}, \ldots , \varepsilon _{i}, x_{i + 1}, \ldots , x_{n}),

where $\varepsilon_{j} \in \left\{ 0, 1\right\}$ , $x_{j}^{0} = \neg x_{j}$ , $x_{j}^{1} = x_{j}$ .

Problem II.2.8

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

Prove the completeness of the systems of functions:

?

(a)

$\left\{ \& , \vee , \neg \right\}$ ;

(b)

$\left\{ \vee , \neg \right\}$ ;

(c)

$\left\{ \& , \neg \right\}$ ;

(d)

$\left\{ \supset , \neg \right\}$ .

Problem II.2.9

(a)(b)

Prove the incompleteness of the systems of functions:

?

(a)

$\left\{ \& , \vee , \supset \right\}$ ;

(b)

$\left\{ \neg \right\}$ .

Problem II.2.10

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

Prove the completeness of the systems of functions:

?

(a)

$\left\{ \mid \right\}$ ;

(b)

$\left\{ \downarrow \right\}$ (here $\downarrow = \neg (x \vee y)$ );

(c)

$\left\{ \supset , 0\right\}$ ;

(d)

$\left\{ +, \vee , 1\right\}$ .

Problem II.2.11

(a)(b)

Prove that:

?

(a)

$\left\{ +, \cdot , 1\right\}$ is a complete system of functions;

(b)

every function $f(x_{1}, \ldots , x_{n})$ is uniquely representable by a Zhegalkin polynomial, i.e., in the form:

\varepsilon _{0} + \sum _{k \geq 1} \sum _{1 \leq i_{1} < \ldots < i_{k} \leq n} \varepsilon _{i_{1} \ldots i_{k}} x_{i_{1}} \cdot \ldots \cdot x_{i_{k}},

where $\varepsilon_{0}, \varepsilon_{i_{1} \ldots i_{k}} \in \left\{ 0, 1\right\}$ .

Problem II.2.12

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

Show that the following systems of functions are independent:

?

(a)

$\left\{ \neg , \equiv \right\}$ ;

(b)

$\left\{ \neg , +\right\}$ ;

(c)

$\left\{ \equiv , +\right\}$ ;

(d)

$\left\{ \equiv , \vee \right\}$ .

Problem II.2.13

(a)(b)(c)

Show the completeness and independence of the following systems of functions:

?

(a)

$\left\{ \supset , /\right\}$ , where $x / y = \neg (y \supset x)$ ;

(b)

$\left\{ 0, 1, [\cdot , \cdot , \cdot ]\right\}$ , where $[x, y, z] = (y \& x) \vee (\neg y \& z)$ ;

(c)

$\left\{ \equiv , \vee , 0\right\}$ .

Problem II.2.14

Show that $\equiv , +$ do not form a complete system of functions. Determine all possible ways of making this system a complete system of independent functions by adding one function of at most 2 arguments.

?

Problem II.2.15

Which system consisting of a single 2-ary function is complete? Find all such systems.

?

Problem II.2.16

(a)(b)

Give an example of a complete system of functions:

?

(a)

consisting of a single 3-ary function;

(b)

consisting of a single $n$ -ary function ( $n \geq 2$ ).

Problem II.2.17

Prove that a finite complete subsystem can be extracted from every complete system of functions.

?

Problem II.2.18

Prove that:

?

(a)

$\left\{ \& , \supset \right\}$ is a basis for $C_{1}$ ;

(b)

$\left\{ \& , +\right\}$ is a basis for $C_{0}$ ;

(c)

$\left\{ \vee , \& , 0, 1\right\}$ is a basis for $M$ ;

(d)

$\left\{ 0, \equiv \right\}$ is a basis for $L$ ;

(e)

$\left\{ \neg , xy + xz + yz\right\}$ is a basis for $D$ .

Problem II.2.19

Prove that the classes $C_{1}, C_{0}$ are precomplete classes.

?

Problem II.2.20

(a)(b)

Prove that:

?

(a)

from any nonmonotone function together with the functions 0 and 1, one can obtain the function $\neg$ by superpositions;

(b)

the class $M$ is a precomplete class.

Problem II.2.21

(a)(b)

Prove that:

?

(a)

from any non-self-dual function together with the function $\neg$ , one can obtain the functions 0 and 1 by superpositions;

(b)

the class $D$ is a precomplete class.

Problem II.2.22

(a)(b)

Prove that:

?

(a)

from any nonlinear function together with the functions 0, 1, $\neg$ , one can obtain the function by superpositions;

(b)

the class $L$ is a precomplete class.

Problem II.2.23

Prove that every closed class $K \neq C$ is contained in some precomplete class.

?

Problem II.2.24

Prove that a system of functions is complete if and only if it is not contained in any of the precomplete classes.

?

Problem II.2.25

Prove that there are no precomplete classes other than $C_{1}, C_{0}, L, D$ and $M$ (E.Post's theorem).

?

Problem II.2.26

Prove that every basis of $C$ contains at most four functions.

?

Problem II.2.27

(a)(b)(c)

Let $T$ and $T_{1}$ be terms representing some functions of the algebra of logic, and let $\varepsilon (T, x)$ be the formula of set theory defined at the end of the introductory part of the section. Prove that:

?

(a)

$\varepsilon ((T \vee T_{1}), x) \Leftrightarrow (\varepsilon (T, x) \vee \varepsilon (T_{1}, x))$ ;

(b)

$\varepsilon ((T \& T_{1}), x) \Leftrightarrow (\varepsilon (T, x) \& \varepsilon (T_{1}, x))$ ;

(c)

$\varepsilon (\neg T, x) \Leftrightarrow \neg \varepsilon (T, x)$ .

Problem II.2.28

(a)(b)(c)

Prove that in set theory:

?

(a)

$Z(\neg T) = -Z(T)$ , where $-Z = U \backslash Z$ ;

(b)

$Z(T \vee T_{1}) = Z(T) \cup Z(T_{1})$ ;

(c)

$Z(T \& T_{1}) = Z(T) \cap Z(T_{1})$ .

Problem II.2.29

Prove that in set theory

\varepsilon (T, x) \Leftrightarrow x \in Z(T).

?

Problem II.2.30

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

Suppose the function $f$ is representable by the term $T$ , and $g$ by the term $T_{1}$ . Prove that:

?

(a)

if $f(a_{1}, \ldots , a_{k}) = g(a_{1}, \ldots , a_{k})$ for all $a_{1}, \ldots , a_{k}$ , then in set theory the identity $Z(T) = Z(T_{1})$ holds;

(b)

if $(f(a_{1}, \ldots , a_{k}) \supset g(a_{1}, \ldots , a_{k})) = 1$ for all $a_{1}, \ldots , a_{k}$ , then in set theory the relation $Z(T) \subseteq Z(T_{1})$ holds;

(c)

if $f(a_{1}, \ldots , a_{k}) = 1$ for all $a_{1}, \ldots , a_{k}$ , then in set theory the identity $Z(T) = U$ holds;

(d)

if $f(a_{1}, \ldots , a_{k}) = 0$ for all $a_{1}, \ldots , a_{k}$ , then in set theory the identity $Z(T) = \emptyset$ holds.

Problem II.2.31

Prove that if the function $f(a_{1}, \ldots , a_{k})$ is representable by the term $T$ and $Z(T) = U$ for all arbitrary $Z_{1}, \ldots , Z_{k} \subseteq U$ , then $f(a_{1}, \ldots , a_{k}) = 1$ for all $a_{1}, \ldots , a_{k}$ .

?

Problem II.2.32

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

On the basis of which identities of the algebra of logic can the following theorems of set theory be obtained:

?

(a)

$(X \cup Y) \cup Z = X \cup (Y \cup Z)$ ;

(b)

$X \cap Y = Y \cap X$ ;

(c)

$-(X \cap Y) = -X \cup -Y$ ;

(d)

$-(-X) = X$ ?

Problem II.2.33

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)