Propositional Logic and Boolean Functions

Prove that the number of $k$-dimensional faces in an $n$-dimensional cube equals $F(n, k)=C_{n}^{k} \cdot 2^{n-k}$. Find the total number $F(n)$ of faces of an $n$-dimensional cube.

Let $\bar{a}=\left(a_{1}, a_{2}, \ldots , a_{n}\right)$ and $\bar{b}=\left(b_{1}, b_{2}, \ldots , b_{n}\right)$ be two tuples (two points) of the $n$-dimensional unit cube $\mathbb {B}^{n}$. The Hamming distance between $\bar{a}$ and $\bar{b}$ is the number $H(\bar{a}, \bar{b})=\sum_{i=1}^{n}\left|a_{i}-b_{i}\right|$. Prove that this distance satisfies the following properties:

Let $\bar{a}, \bar{b} \in \mathbb {B}^{n}$ be points of the $n$-dimensional unit cube, $H(\bar{a}, \bar{b})=k$. Prove that then

Let in the sequence of vectors

each next element be obtained from the previous one by replacing one of the zeros with a one. Prove that the system of equations $H\left(\bar{x}, \bar{a}^{(i)}\right)=k_{i}$, $i=0, \ldots , n, k_{i} \in \omega$, has at most one solution in $\mathbb {B}^{n}$.

Find the vertices of the unit cube $\mathbb {B}^{5}$ that are at the indicated distances from the vertices $(0,0,0,0,0),(1,0,0,0,0),(1,1,0,0,0),(1,1,1,0,0),(1,1,1,1,0)$, $(1,1,1,1,1)$ respectively:

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

Construct truth tables for the following Boolean functions:

Let us call a flip-flop a Boolean function $T$ of several arguments for which $T(q, 0, \ldots , 0)=q$ holds for any $q \in \mathbb {B}$. Write out all possible

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

Determine which of the following formulas of propositional logic are identically true:

The table shown in fig. 115 shows the encoding of the decimal digits from 0 to 9 by means of four propositional variables $A, B, C, D \in \mathbb {B}$. Combinations of values of $A, B, C$ and $D$ not listed in the table are erroneous codes. Which of the following Boolean formulas define the set of all erroneous codes:

Using the code table from the previous problem and assuming that the code is not erroneous, construct a formula with four variables $A, B, C$ and $D$ that will have value 1 if and only if the encoded number

The variables $(A_{1}, B_{1}, C_{1}, D_{1})$ and $(A_{2}, B_{2}, C_{2}, D_{2})$ encode the numbers $x_{1}$ and $x_{2}$ respectively (see problem 115). Assuming that neither code is erroneous, write a formula that will have value 1 if and only if

The variables $(C_{1}, D_{1})$ and $(C_{2}, D_{2})$ encode the numbers $x_{1}$ and $x_{2}$ respectively from the set $\left\{ 0,1,2,3\right\}$ (see problem 115). Write formulas $p_{A}, p_{B}, p_{C}$ and $p_{D}$ whose values encode the product of these numbers.

Which of the following conditions can be expressed by Boolean formulas in the variables $x_{1}, x_{2}, x_{3}, x_{4}$, using only the logical connectives $\wedge$ and $\vee$?

Let us 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}$ adjacent if they occur in adjacent rows of the table for a function of $n$ variables, that is, they represent the binary representations of the 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 on every pair of adjacent tuples take

Find the number of $n$-ary Boolean functions taking value 1 on exactly $k$ tuples.

Find the number of functions in $\mathcal{P}_{n}$ that change their value whenever any argument is changed.

Find the number of functions in $\mathcal{P}_{n}$ that are commutative in every pair of arguments, that is, whose value does not change under a permutation of arbitrary arguments.

Let us 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.

Let $n=2 k$. Let us call the 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.

Determine how many three-place Boolean functions in total can be constructed using at most one connective from tables 1 and 2 on p. 36, and moreover using it at most once.

Let $F$ be a finite set of Boolean functions, and $\varepsilon$ a positive, arbitrarily small constant. Prove that for sufficiently large $n$, formulas over $F$ with fewer than $2^{n} / n$ symbols can represent at most $2^{2^{n}} / n^{1-\varepsilon }$ Boolean functions. Thus, almost all Boolean functions can only be represented by "long" formulas.

An argument $x_{i}$ of a Boolean function $f$ is called dummy (fictitious) if the value of $f$ never changes when the value of $x_{i}$ is changed. Find the number of $n$-ary Boolean functions with no dummy arguments, for $n=2,3,4$.

By induction on the construction of the formula $\Phi$, prove the inequality

Give an example where the inequality is strict.

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

The programmer Peter used three integer variables $x, y, z$ in his C program. At a certain point in the program he placed the conditional statement: if $(\mathrm{x} * \mathrm{y}>=0| | \mathrm{x} * \mathrm{z}>=0)$ $\mathrm{x}=1$; else $\mathrm{x}=2$; Having analyzed his program, Peter established that before this statement is executed the following conditions hold:

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.

In each of the following texts identify the elementary statements, denote them by propositional variables, and write a formula of propositional logic reflecting the content of the text.

Detective Sh. Holmes suspects three persons of committing a crime: $A, B$ and $C$. He has established that

Detective E. Poirot suspects three persons of committing a crime: $A, B$ and $C$. They gave the following testimony: - $A$: if $B$ is the criminal, then $C$ is innocent; - $B$: if $A$ is guilty, then $C$ is also the criminal; - $C$: $A$ is the criminal. E. Poirot has established that (а) if $A$ told the truth, then $B$ lied, and (б) $C$'s testimony is false. Describe E. Poirot's knowledge as a formula of propositional logic and construct its truth table. Can he conclude that $B$ is the criminal? Could the criminal have been alone?

Suppose that in every zoo that has lions and rhinoceroses there are no giraffes; in every zoo that has rhinoceroses and no giraffes there are lions; finally, in every zoo that has lions and giraffes there are also rhinoceroses. Do you think there can exist a zoo in which there are lions but neither giraffes nor rhinoceroses?

Anna, Beatrice, and Vera once discovered that they were all wearing identical jeans. It is known that Anna has jeans with pockets, narrow jeans, and faded jeans without pockets; Beatrice has jeans without pockets and faded narrow jeans with pockets. And finally, Vera has flared jeans and blue narrow jeans with pockets. What do their identical jeans look like?

A student who knew English poorly went on an internship in England. He needed to get to Manchester. He hitchhiked on the highway and stopped a car in which there were a father, a mother, and a daughter, who answered his question about their trip. He translated each phrase they said in two different ways and could not decide what the phrase actually meant. Here is what they said (the second possible meaning is given in parentheses).

Father: we are heading to Manchester (we are coming from Newcastle). Mother: we are not heading to Manchester, and we are coming from Newcastle (we did not stop in Liverpool and we are coming from Newcastle).

Daughter: we are not coming from Newcastle (we stopped in Liverpool). Should the student get into this car?

Lewis Carroll, the author of the widely known book "Alice in Wonderland" (it is less well known that he was a mathematician), liked to pose the following puzzle consisting of four statements: "One of two things: either the culprit left in a carriage, or the witness was mistaken. If the culprit had an accomplice, then he left in a carriage. The culprit had neither an accomplice nor a key; or he had both an accomplice and a key. The culprit had a key." What conclusion can be drawn from this?

A professor of economics formulated three rules for the students: