Глава 3

Булевы функции и их представления

[10/100%]
Показать
LaTeX
Задача 55

Какие подмножества вершин B4\mathbb {B}^{4} соответствуют следующим булевым функциям:

?
(а)

f1(x1,x2,x3,x4)=1⇔x1=0f_{1}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1}=0;

(б)

f2(x1,x2,x3,x4)=1⇔x4=1f_{2}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{4}=1;

(в)

f3(x1,x2,x3,x4)=1⇔x1+x2⩾x3+x4f_{3}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1}+x_{2} \geqslant x_{3}+x_{4};

(г)

f4(x1,x2,x3,x4)=1⇔x1x2=0f_{4}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=1 \Leftrightarrow x_{1} x_{2}=0 или x3x4=1x_{3} x_{4}=1?

Задача 56

Построить таблицы значений для следующих булевых функций:

?
(а)

f1(x1,x2,x3)=1⇔x1+x3⩾x2f_{1}\left(x_{1}, x_{2}, x_{3}\right)=1 \Leftrightarrow x_{1}+x_{3} \geqslant x_{2};

(б)

f2(x1,x2,x3)=1⇔f_{2}\left(x_{1}, x_{2}, x_{3}\right)=1 \Leftrightarrow сумма x1+x2+x3x_{1}+x_{2}+x_{3} чётна;

(в)

f3(x1,x2,x3)=0⇔(x1=x2 или x1=x3)f_{3}\left(x_{1}, x_{2}, x_{3}\right)=0 \Leftrightarrow \left(x_{1}=x_{2} \text{ или } x_{1}=x_{3}\right);

(г)

f4(x1,x2,x3)={x2, если x1=1;x3, иначе. f_{4}\left(x_{1}, x_{2}, x_{3}\right)= \begin{cases} x_{2}, & \text{ если } x_{1}=1 ; \\ x_{3}, & \text{ иначе. }\end{cases}

Задача 57

Для каждой из следующих формул определить её глубину и построить таблицу задаваемой ею функции:

?
(а)

Ψ1=((x1→¬x3)∨(x2⊕x3))\Psi_{1}=\left(\left(x_{1} \rightarrow \neg x_{3}\right) \vee \left(x_{2} \oplus x_{3}\right)\right);

(б)

Ψ2=(¬(x1↑x2)↔(¬x1∧x2))\Psi_{2}=\left(\neg \left(x_{1} \uparrow x_{2}\right) \leftrightarrow \left(\neg x_{1} \wedge x_{2}\right)\right);

(в)

Ψ3=((x2⊕¬x3)∧((x1∨x2)→(x1↔¬x3)))\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);

(г)

Ψ4=((¬x1∧x2)↓(x1→¬x3))\Psi_{4}=\left(\left(\neg x_{1} \wedge x_{2}\right) \downarrow \left(x_{1} \rightarrow \neg x_{3}\right)\right);

(д)

Ψ5=(((x1⊕x2)⊕x3)↑(¬x2↓x3))\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).

Задача 58

Назовём наборы α=(α1,…,αn)∈Bn\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n} и β=(β1,…,βn)∈Bn\beta =\left(\beta_{1}, \ldots , \beta_{n}\right) \in \mathbb {B}^{n} соседними, если они находятся в соседних строках таблицы для функции от nn переменных, то есть представляют двоичные записи чисел iαi_{\alpha } и iβi_{\beta }, для которых ∣iα−iβ∣=1\left|i_{\alpha }-i_{\beta }\right|=1.

Найти количество функций в Pn\mathcal{P}_{n}, которые на каждой паре соседних наборов принимают

?
(а)

одинаковые значения;

(б)

разные значения.

Задача 59

Назовём наборы α=(α1,…,αn)∈Bn\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n} и β=(β1,…,βn)∈Bn\beta =\left(\beta_{1}, \ldots , \beta_{n}\right) \in \mathbb {B}^{n} противоположными, если αi+βi=1\alpha_{i}+\beta_{i}=1 для всякого ii (иначе говоря, αi=1\alpha_{i}=1 в том и только том случае, когда βi=0\beta_{i}=0).

Найти количество функций в Pn\mathcal{P}_{n}, которые на каждой паре противоположных наборов принимают разные значения.

?
Задача 60

Пусть n=2kn=2 k. Назовём набор α=(α1,…,αn)∈Bn\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n} парным, если αi=αk+i\alpha_{i}=\alpha_{k+i} для всех i=1,…,ki=1, \ldots , k, то есть α=α′α′\alpha =\alpha^{\prime } \alpha^{\prime } для некоторого набора α′\alpha^{\prime } размера kk. Найти количество функций в Pn\mathcal{P}_{n}, которые на всех парных наборах принимают одинаковое значение.

?
Задача 61

Администратор базы данных обнаружил, что одна или несколько из трёх записей его базы A,BA, B и CC ошибочна. Он установил, что

?
(а)

если запись BB корректна, то AA ошибочна;

(б)

хотя бы одна запись из пары B,CB, C корректна и хотя бы одна запись из пары A,CA, C корректна;

(в)

если AA ошибочна, то хотя одна из записей BB или CC корректна (но не обе вместе). Описать знания администратора в виде формулы логики высказываний. Может ли он сделать вывод, что запись BB ошибочна? Можно ли достоверно утверждать, что ошибочная запись единственна?

Задача 62

Программист Пётр использовал в своей программе на языке С три целочисленные переменные x,y,zx, y, z. В определённом месте программы он поместил условный оператор:

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

Проанализировав свою программу, Пётр установил, что перед выполнением этого оператора выполнены следующие условия:

?
(а)

если z<0z<0, то x<0x<0 или y⩾0y \geqslant 0;

(б)

x⩾0x \geqslant 0 или y<0y<0;

(в)

если y<0y<0, то хотя бы одна из переменных xx или zz отрицательна, но не обе вместе. Описать знания Петра в виде формулы логики высказываний. Может ли он оптимизировать программу, заменив указанный условный оператор на присваивание x=1\mathrm{x}=1; или на присваивание x=2\mathrm{x}=2;? Если «да», то на какое?

Задача 63

Комитет состоит из пяти членов. Решения принимаются большинством голосов, однако, если председатель голосует «против», то решение не принимается. Построить формулу логики высказываний, зависящую от пяти пропозициональных переменных x1,x2,x3,x4,yx_{1}, x_{2}, x_{3}, x_{4}, y (xix_{i} означает, что ii-й член комитета голосует «за», yy означает, что председатель голосует «за»), значение которой равно 1 тогда и только тогда, когда в результате голосования решение принимается.

?
Задача 64

В каждом из следующих текстов выделить элементарные высказывания, обозначить их пропозициональными переменными и записать формулу логики высказываний, отражающую содержание текста.

?
(а)

Миша решил сделать небольшой ремонт в квартире и поклеить новые обои или покрасить пол. Вместе с обоями нужно будет обновить ламинат, сменить двери и стеклопакет в окне. После покраски пола нужно установить натяжной потолок, новую люстру и мебель. Если обновить ламинат, то тоже придётся покупать новую мебель. Старые обои нельзя оставлять со старой мебелью, а старую мебель — со старой люстрой.

(б)

Если будет мороз, то будет солнечно или при пасмурной погоде пойдёт снег, а если мороза не будет, то будет солнечно или при пасмурной погоде пойдёт дождь. В случае дождя или снега будет сыро, а в случае дождя ещё и грязно. Если будет солнечно, то не будет ни сырости, ни грязи.

(в)

Когда Вова дома, то его кошка ест или спит, а если Вовы нет, то она ещё и играет. Если кошка ест, то нужно купить корм. Если кошка играет, то придётся покупать новую мебель или новые обои. За кормом нужно идти в зоомагазин «Всё для кошки», а за мебелью или обоями — в хозяйственный магазин «Всё для дома». В любой из магазинов придётся ехать на такси. Вова не поедет на такси в магазин «Всё для дома».