Math Problems Vault

Problem 55

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

Which subsets of the vertices of $\mathbb {B}^{4}$ correspond to the following Boolean functions:

?

(a)

$f_{1}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1}=0$ ;

(b)

$f_{2}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{4}=1$ ;

(c)

$f_{3}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1}+x_{2} \geqslant x_{3}+x_{4}$ ;

(d)

$f_{4}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1} x_{2}=0$ or $x_{3} x_{4}=1$ ?

Problem 56

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

Construct the truth tables for the following Boolean functions:

?

(a)

$f_{1}\left(x_{1}, x_{2}, x_{3}\right)=1 \Leftrightarrow x_{1}+x_{3} \geqslant x_{2}$ ;

(b)

$f_{2}\left(x_{1}, x_{2}, x_{3}\right)=1 \Leftrightarrow$ the sum $x_{1}+x_{2}+x_{3}$ is even;

(c)

$f_{3}\left(x_{1}, x_{2}, x_{3}\right)=0 \Leftrightarrow \left(x_{1}=x_{2} \text{ or } x_{1}=x_{3}\right)$ ;

(d)

$f_{4}\left(x_{1}, x_{2}, x_{3}\right)= \begin{cases} x_{2}, & \text{ if } x_{1}=1 ; \\ x_{3}, & \text{ otherwise. }\end{cases}$

Problem 57

For each of the following formulas, determine its depth and construct the table of the function it defines:

?

(a)

$\Psi_{1}=\left(\left(x_{1} \rightarrow \neg x_{3}\right) \vee \left(x_{2} \oplus x_{3}\right)\right)$ ;

(b)

$\Psi_{2}=\left(\neg \left(x_{1} \uparrow x_{2}\right) \leftrightarrow \left(\neg x_{1} \wedge x_{2}\right)\right)$ ;

(c)

$\Psi_{3}=\left(\left(x_{2} \oplus \neg x_{3}\right) \wedge \left(\left(x_{1} \vee x_{2}\right) \rightarrow \left(x_{1} \leftrightarrow \neg x_{3}\right)\right)\right)$ ;

(d)

$\Psi_{4}=\left(\left(\neg x_{1} \wedge x_{2}\right) \downarrow \left(x_{1} \rightarrow \neg x_{3}\right)\right)$ ;

(e)

$\Psi_{5}=\left(\left(\left(x_{1} \oplus x_{2}\right) \oplus x_{3}\right) \uparrow \left(\neg x_{2} \downarrow x_{3}\right)\right)$ .

Problem 58

(a)(b)

Call the tuples $\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n}$ and $\beta =\left(\beta_{1}, \ldots , \beta_{n}\right) \in \mathbb {B}^{n}$ neighboring if they occur in adjacent rows of the table for a function of $n$ variables, that is, they represent the binary expansions of numbers $i_{\alpha }$ and $i_{\beta }$ for which $\left|i_{\alpha }-i_{\beta }\right|=1$ .

Find the number of functions in $\mathcal{P}_{n}$ that take, on every pair of neighboring tuples,

?

(a)

equal values;

(b)

different values.

Problem 59

Call the tuples $\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n}$ and $\beta =\left(\beta_{1}, \ldots , \beta_{n}\right) \in \mathbb {B}^{n}$ opposite if $\alpha_{i}+\beta_{i}=1$ for every $i$ (in other words, $\alpha_{i}=1$ if and only if $\beta_{i}=0$ ).

Find the number of functions in $\mathcal{P}_{n}$ that take different values on every pair of opposite tuples.

?

Problem 60

Let $n=2 k$ . Call a tuple $\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n}$ paired if $\alpha_{i}=\alpha_{k+i}$ for all $i=1, \ldots , k$ , that is $\alpha =\alpha^{\prime } \alpha^{\prime }$ for some tuple $\alpha^{\prime }$ of size $k$ . Find the number of functions in $\mathcal{P}_{n}$ that take the same value on all paired tuples.

?

Problem 61

(a)(b)(c)

A database administrator discovered that one or more of the three records $A, B$ and $C$ in his database is erroneous. He established that

?

(a)

if record $B$ is correct, then $A$ is erroneous;

(b)

at least one record of the pair $B, C$ is correct, and at least one record of the pair $A, C$ is correct;

(c)

if $A$ is erroneous, then exactly one of the records $B$ or $C$ is correct (but not both). Express the administrator's knowledge as a formula of propositional logic. Can he conclude that record $B$ is erroneous? Can it be reliably asserted that the erroneous record is unique?

Problem 62

(a)(b)(c)

The programmer Pyotr used three integer variables $x, y, z$ in his C program. At a certain point in the program he placed the conditional statement:

\operatorname {if}(\mathrm{x} * \mathrm{y}>=0| | \mathrm{x} * \mathrm{z}>=0) \mathrm{x}=1 \text{; else } \mathrm{x}=2 \text{; }

Having analyzed his program, Pyotr established that before this statement is executed the following conditions hold:

?

(a)

if $z<0$ , then $x<0$ or $y \geqslant 0$ ;

(b)

$x \geqslant 0$ or $y<0$ ;

(c)

if $y<0$ , then exactly one of the variables $x$ or $z$ is negative, but not both. Express Pyotr's knowledge as a formula of propositional logic. Can he optimize the program by replacing the given conditional statement with the assignment $\mathrm{x}=1$ ; or with the assignment $\mathrm{x}=2$ ;? If ``yes'', with which one?

Problem 63

A committee consists of five members. Decisions are made by majority vote; however, if the chairman votes against'', the decision is not adopted. Construct a formula of propositional logic depending on five propositional variables $x_{1}, x_{2}, x_{3}, x_{4}, y$ ($x_{i}$ means that the $i$-th committee member votes for'', $y$ means that the chairman votes ``for''), whose value equals 1 if and only if the decision is adopted as a result of the vote.

?

Problem 64

(a)(b)(c)

In each of the following texts, pick out the elementary statements, denote them with propositional variables, and write down a formula of propositional logic that captures the content of the text.

?

(a)

Misha decided to do a small renovation in his apartment and either put up new wallpaper or repaint the floor. Along with the wallpaper he will need to replace the laminate flooring, change the door, and replace the window's double-glazed unit. After repainting the floor he needs to install a stretch ceiling, a new chandelier, and new furniture. If the laminate is replaced, new furniture will also have to be bought. Old wallpaper cannot be left with old furniture, and old furniture cannot be left with an old chandelier.

(b)

If it is frosty, it will be sunny, or if it is overcast it will snow; and if it is not frosty, it will be sunny, or if it is overcast it will rain. In case of rain or snow it will be damp, and in case of rain it will also be muddy. If it is sunny, there will be neither dampness nor mud.

(c)

When Vova is home, his cat eats or sleeps, and when Vova is away, it also plays. If the cat eats, food needs to be bought. If the cat plays, new furniture or new wallpaper will have to be bought. For food one must go to the Everything for Cats'' pet shop, and for furniture or wallpaper to the Everything for the Home'' hardware store. Either shop requires taking a taxi. Vova will not take a taxi to the ``Everything for the Home'' shop.