Булева алгебра и булевы функции

Булевы функции и их задание, законы булевой алгебры, ДНФ и КНФ, полином Жегалкина, минимизация картами Карно, классы Поста и функциональная полнота.
Большой банк заданий: проходите по блокам, возвращайтесь к тем, где ошиблись.

213 заданий

Как проходить Проверка в конце Отвечаете на все задания, потом смотрите результат и разбор Тренировка Можно проверить каждое задание сразу и взять подсказку

Режим можно поменять и во время прохождения.

Режим

Блок 1. Один верный вариант

Что по определению представляет собой булева функция $n$ переменных и сколько всего различных булевых функций зависит от $n$ аргументов?

Отображение

f: \{0, 1\} \to \{0, 1\}^n

; всего существует

2^n

таких функций. Произвольное подмножество декартова произведения

\{0, 1\} \times \{0, 1\}

; всего существует

n^2

таких функций. Отображение

f: \{0, 1\}^n \to \{0, 1\}

; всего существует

2^{n^2}

таких функций. Отображение

f: \{0, 1\}^n \to \{0, 1\}

, сопоставляющее каждому упорядоченному набору из

n

булевых значений ровно одно значение из множества

\{0, 1\}

; всего существует

2^{2^n}

таких функций.

Каков стандартный приоритет выполнения логических операций при отсутствии скобок в выражении $F(A, B, C) = \neg A \lor B \land C$ и какое значение принимает функция $F$ на наборе $A = 0, B = 0, C = 0$ ?

Сначала

\neg

, затем операции выполняются слева направо (

\lor

, затем

\land

); формула эквивалентна

((\neg A) \lor B) \land C

, и на наборе

(0, 0, 0)

значение

F = 0

. Сначала

\land

, затем

\lor

, и в последнюю очередь унарная инверсия

\neg

; на наборе

(0, 0, 0)

значение

F = 1

. Сначала

\neg

, затем

\land

, затем

\lor

; формула эквивалентна

(\neg A) \lor (B \land C)

, и на наборе

(0, 0, 0)

значение

F = 1

. Сначала

\lor

, затем

\land

, затем

\neg

; формула эквивалентна

\neg(A \lor B) \land C

, и на наборе

(0, 0, 0)

значение

F = 0

Выполните равносильные преобразования формулы $F = \overline{A \to (B \land \overline{C})}$ , избавившись от импликации и применив законы де Моргана и инволюции. Какая из приведённых формул тождественно равна $F$ ?

A \land (\overline{B} \lor C)

A \land \overline{B} \land C

\overline{A} \lor (\overline{B} \land C)

\overline{A} \to (\overline{B} \lor C)

Какая из приведённых формул для функции трёх аргументов $f(A, B, C)$ является корректной конъюнктивной нормальной формой (КНФ), но при этом НЕ является совершенной конъюнктивной нормальной формой (СКНФ)?

(A \lor B \lor \overline{C}) \land (A \lor \overline{B} \lor \overline{C}) \land (\overline{A} \lor \overline{B} \lor C)

(A \lor (B \land C)) \land (\overline{A} \lor C)

(A \lor \overline{B}) \land (\overline{A} \lor B \lor C) \land \overline{C}

\overline{(A \lor B)} \land (\overline{A} \lor B \lor C)

Булева функция $f(A, B, C)$ задана следующей таблицей истинности:

\begin{array}{|c|c|c|c|} \hline A & B & C & f(A, B, C) \\ \hline 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \hline \end{array}

Укажите запись этой функции в СКНФ (совершенной конъюнктивной нормальной форме).

(A \lor B \lor \overline{C}) \land (A \lor \overline{B} \lor \overline{C}) \land (\overline{A} \lor \overline{B} \lor C)

(\overline{A} \land \overline{B} \land C) \lor (\overline{A} \land B \land C) \lor (A \land B \land \overline{C})

(\overline{A} \lor \overline{B} \lor C) \land (\overline{A} \lor B \lor C) \land (A \lor B \lor \overline{C})

(A \lor B \lor C) \land (A \lor \overline{B} \lor C) \land (\overline{A} \lor B \lor C) \land (\overline{A} \lor B \lor \overline{C}) \land (\overline{A} \lor \overline{B} \lor \overline{C})

Булева функция четырёх переменных $f(A, B, C, D)$ задана картой Карно (пустые клетки соответствуют значению $0$ ):

\begin{array}{|c|c|c|c|c|} \hline AB \setminus CD & 00 & 01 & 11 & 10 \\ \hline 00 & 1 & & & 1 \\ \hline 01 & & & & \\ \hline 11 & & & & \\ \hline 10 & 1 & & & 1 \\ \hline \end{array}

Какая формула является минимальной ДНФ для данной функции?

(\overline{A} \land \overline{B} \land \overline{D}) \lor (A \land \overline{B} \land \overline{D})

\overline{A} \land \overline{C}

\overline{B} \land \overline{D}

B \land D

Какое выражение представляет собой полином Жегалкина (алгебраическую нормальную форму, АНФ) для функции прямой импликации $f(A, B) = A \to B$ ?

1 \oplus B \oplus (A \land B)

\overline{A} \oplus B \oplus (\overline{A} \land B)

A \oplus B \oplus (A \land B)

1 \oplus A \oplus (A \land B)

Почему единственная операция штрих Шеффера $f(A, B) = A \uparrow B = \overline{A \land B}$ сама по себе образует функционально полную (и безызбыточную) систему булевых функций $\{\uparrow\}$ согласно теореме (критерию) Поста?

Функция

A \uparrow B

принадлежит только классу самодвойственных функций

S

, которого достаточно для порождения всех остальных классов. Функция

A \uparrow B

не принадлежит ни одному из пяти предполных классов Поста (

T_0, T_1, S, M, L

). Функция

A \uparrow B

одновременно принадлежит всем пяти предполным классам Поста (

T_0, T_1, S, M, L

). Функция

A \uparrow B

сохраняет константы

0

1

(принадлежит

T_0

T_1

), но не является монотонной и линейной.

В каком случае переменная $x_i$ булевой функции $f(x_1, \dots, x_n)$ называется фиктивной?

Если функция тождественно равна нулю независимо от значения переменной

x_i

. Если при

x_i = 0

функция всегда равна 0, а при

x_i = 1

всегда равна 1. Если для всех возможных наборов значений остальных переменных выполняется равенство

f(\dots, x_{i-1}, 0, x_{i+1}, \dots) = f(\dots, x_{i-1}, 1, x_{i+1}, \dots)

. Если для всех возможных наборов значений остальных переменных выполняется неравенство

f(\dots, x_{i-1}, 0, x_{i+1}, \dots) \neq f(\dots, x_{i-1}, 1, x_{i+1}, \dots)

Какое из предложенных выражений является корректной записью закона де Моргана для конъюнкции?

\overline{A \land B} = A \land B

\overline{A \land B} = \overline{A} \lor \overline{B}

\overline{A \land B} = A \lor B

\overline{A \land B} = \overline{A} \land \overline{B}

Упростите выражение $\overline{\overline{A} \lor B}$ , используя законы булевой алгебры (закон де Моргана и закон инволюции).

A \land B

A \land \overline{B}

A \lor \overline{B}

\overline{A} \land B

Какое логическое выражение тождественно равно операции эквивалентности $A \leftrightarrow B$ ?

(A \lor B) \land (\overline{A} \lor \overline{B})

A \land \overline{B} \lor \overline{A} \land B

(A \land B) \lor (\overline{A} \land \overline{B})

\overline{A} \lor B

Какая связь существует между операцией сложения по модулю 2 (XOR, $A \oplus B$ ) и операцией эквивалентности ( $A \leftrightarrow B$ )?

A \oplus B = A \leftrightarrow \overline{B}

, но не являются полной инверсией. Они являются инверсией друг друга:

A \oplus B = \overline{A \leftrightarrow B}

. Они тождественно равны:

A \oplus B = A \leftrightarrow B

. Между ними нет аналитической связи, они принадлежат разным базисам.

Какие операции образуют базис (алгебру) Жегалкина?

Импликация и константа 0:

\{\to, 0\}

. Дизъюнкция, конъюнкция и инверсия:

\{\lor, \land, \neg\}

. Штрих Шеффера и константа 1:

\{|, 1\}

. Сложение по модулю 2, конъюнкция и константа 1:

\{\oplus, \land, 1\}

Каким образом операция инверсии $\overline{A}$ выражается в базисе Жегалкина?

A \oplus 0

A \land 1

A \oplus A

A \oplus 1

Какому условию должна удовлетворять булева функция $f(x_1, x_2, \dots, x_n)$ , чтобы она принадлежала классу $T_0$ (функции, сохраняющие ноль)?

На нулевом наборе аргументов функция должна принимать значение ноль:

f(0, 0, \dots, 0) = 0

. Функция должна содержать в векторе значений равное количество нулей и единиц. При наличии хотя бы одного нуля в наборе аргументов функция должна быть равна нулю. На единичном наборе аргументов функция должна принимать значение ноль:

f(1, 1, \dots, 1) = 0

Принадлежит ли логическая операция дизъюнкции $f(A, B) = A \lor B$ классу $T_1$ (функций, сохраняющих единицу)?

Да, так как на единичном наборе она дает 1:

f(1,1) = 1 \lor 1 = 1

. Нет, так как на нулевом наборе она дает 0:

f(0,0) = 0 \lor 0 = 0

. Да, так как она принимает значение 1 на большинстве наборов. Нет, так как класс

T_1

включает только конъюнкцию и эквивалентность.

Как определяется монотонная булева функция (класс $M$ в критерии Поста)?

Функция, которая на сравнимых наборах не убывает: если

\alpha \le \beta

, то

f(\alpha) \le f(\beta)

. Функция, у которой с ростом числа единиц в наборе значение строго меняется с 0 на 1. Функция, которая на противоположных наборах принимает противоположные значения. Функция, полином Жегалкина которой не содержит конъюнкций.

Какая булева функция называется линейной (принадлежит классу $L$ )?

Функция, таблица истинности которой симметрична относительно центра. Функция, которая может быть выражена только через конъюнкцию и дизъюнкцию. Функция, которая имеет минимальную ДНФ без инверсий. Функция, которая в своем представлении в виде полинома Жегалкина не содержит конъюнкций переменных.

Дана таблица истинности для функции от двух переменных.

\begin{array}{|c|c|c|} \hline A & B & f \\ \hline 0 & 0 & 1 \\ \hline 0 & 1 & 1 \\ \hline 1 & 0 & 0 \\ \hline 1 & 1 & 0 \\ \hline \end{array}

Является ли переменная $B$ существенной для данной функции?

Переменная

B

является существенной только на наборах, где

A=1

. Да, переменная

B

является существенной, так как функция зависит от обоих аргументов. Переменная

B

является фиктивной только на наборах, где

A=0

. Нет, переменная

B

является фиктивной, так как при её изменении значение функции не меняется.

Вычислите выражение $A \oplus B \oplus A$ в алгебре Жегалкина, используя свойства операций.

1

B

0

A \land B

Как выразить операцию дизъюнкции $A \lor B$ через базис Жегалкина $\{\oplus, \land, 1\}$ ?

A \oplus B \oplus (A \land B)

A \land B \oplus 1

(A \oplus 1) \land (B \oplus 1)

A \oplus B

Какая функция называется самодвойственной (класс $S$ )?

Функция, которая на противоположных наборах принимает противоположные значения:

f(x_1, \dots, x_n) = \overline{f}(\overline{x}_1, \dots, \overline{x}_n)

. Функция, которая на противоположных наборах принимает одинаковые значения. Функция, которая при инверсии всех аргументов остается неизменной. Функция, которая сохраняет 0 и 1 одновременно.

Упростите функцию $F = \overline{A \lor (\overline{B} \land C)}$ до формы, в которой отсутствуют инверсии над группами переменных (примените законы де Моргана).

\overline{A} \lor (B \land \overline{C})

A \land (B \lor \overline{C})

\overline{A} \land \overline{B} \lor C

\overline{A} \land (B \lor \overline{C})

Определите принадлежность функции импликации $f(A, B) = A \to B$ классам функций $T_0$ (сохраняющие ноль) и $T_1$ (сохраняющие единицу).

Не принадлежит ни

T_0

, ни

T_1

. Принадлежит

T_0

, но не принадлежит

T_1

. Не принадлежит

T_0

, но принадлежит

T_1

. Принадлежит и

T_0

, и

T_1

Дана булева функция $f(A, B) = (A \land B) \lor (\overline{A} \land B)$ . Проанализируйте её и выберите верное утверждение о существенности её переменных.

Обе переменные

A

B

являются фиктивными. Обе переменные

A

B

являются существенными. Переменная

B

является фиктивной, а переменная

A

— существенной. Переменная

A

является фиктивной, а переменная

B

— существенной.

Является ли функция эквивалентности $f(A, B) = A \leftrightarrow B$ самодвойственной (класс $S$ )?

Да, так как она принимает значение 1 ровно на половине наборов. Нет, так как её полином Жегалкина содержит конъюнкцию. Да, так как при инверсии одного из входов функция всегда инвертируется. Нет, так как на наборах

(0,0)

(1,1)

она принимает одинаковые значения.

Постройте полином Жегалкина для функции $f(A, B) = \overline{A} \land \overline{B}$ (штрих Шеффера инвертированных аргументов, также известный как стрелка Пирса). Какой вид он имеет?

A \land B \oplus A \oplus B \oplus 1

A \land B \oplus 1

A \oplus B \oplus 1

A \land B \oplus A \oplus B

Проверьте функцию сложения по модулю 2 $f(A, B) = A \oplus B$ на монотонность (класс $M$ ). Каков результат?

Функция является монотонной, так как на всех наборах количество единиц строго сбалансировано. Функция не является монотонной, так как

f(0,1) = 1

, но при переходе к большему набору

f(1,1) = 0

(значение убывает). Функция является монотонной, так как

f(0,0) = 0

f(0,1) = 1

(значение возрастает). Функция не является монотонной, так как она не сохраняет единицу:

f(1,1) = 0

Полином Жегалкина для функции штрих Шеффера $f(A, B) = A | B$ имеет вид $1 \oplus A \land B$ . На основании этого полинома определите, принадлежит ли функция классу линейных функций ( $L$ ).

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

A \land B

Как с помощью карт Вейча (Карно) для 4 переменных (A, B, C, D) графически склеиваются восемь единиц, расположенных во всех ячейках двух крайних столбцов (левого и правого)? Какую общую импликанту они образуют, если столбцы маркированы переменной C (средние 2 столбца — это $C=1$ , крайние — $C=0$ )?

Они образуют импликанту

C

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

\overline{B} \land \overline{C}

. Они образуют импликанту

\overline{C}

, так как склеиваются «внахлест» по краям карты (карта Карно представляет собой тор).

Функция задана вектором своих значений $f = (0110)$ . Найдите её полином Жегалкина методом треугольника (или подстановкой). Выберите верный ответ (порядок аргументов $x_1, x_2$ , наборы $00, 01, 10, 11$ ).

x_1 \oplus x_2

x_1 \oplus x_1 \land x_2

1 \oplus x_1 \oplus x_2

x_1 \land x_2

Функция 4 переменных $f(A, B, C, D)$ задана вектором значений, в котором единицы стоят только на позициях 2, 7 и 13 (в десятичном представлении наборов от 0 до 15). Выберите правильную запись её совершенной дизъюнктивной нормальной формы (СДНФ).

\overline{A} \land \overline{B} \land C \land \overline{D} \lor \overline{A} \land B \land C \land D \lor A \land B \land \overline{C} \land D

\overline{A} \land \overline{B} \land C \land \overline{D} \lor \overline{A} \land B \land C \land \overline{D} \lor A \land B \land \overline{C} \land D

(A \lor B \lor \overline{C} \lor D) \land (A \lor \overline{B} \lor \overline{C} \lor \overline{D}) \land (\overline{A} \lor \overline{B} \lor C \lor \overline{D})

A \land B \land \overline{C} \land D \lor A \land \overline{B} \land \overline{C} \land \overline{D} \lor \overline{A} \land \overline{B} \land C \land \overline{D}

Булева функция 4 переменных $f(x_1, x_2, x_3, x_4)$ принимает значение 0 только на наборах 0, 8 и 15. Укажите корректную запись её совершенной конъюнктивной нормальной формы (СКНФ).

(\overline{x}_1 \lor \overline{x}_2 \lor \overline{x}_3 \lor \overline{x}_4) \land (x_1 \lor \overline{x}_2 \lor \overline{x}_3 \lor \overline{x}_4) \land (x_1 \lor x_2 \lor x_3 \lor x_4)

(x_1 \land x_2 \land x_3 \land x_4) \lor (\overline{x}_1 \land x_2 \land x_3 \land x_4) \lor (\overline{x}_1 \land \overline{x}_2 \land \overline{x}_3 \land \overline{x}_4)

\overline{x}_1 \land \overline{x}_2 \land \overline{x}_3 \land \overline{x}_4 \lor x_1 \land \overline{x}_2 \land \overline{x}_3 \land \overline{x}_4 \lor x_1 \land x_2 \land x_3 \land x_4

(x_1 \lor x_2 \lor x_3 \lor x_4) \land (\overline{x}_1 \lor x_2 \lor x_3 \lor x_4) \land (\overline{x}_1 \lor \overline{x}_2 \lor \overline{x}_3 \lor \overline{x}_4)

Функция от 3 переменных задана вектором значений $f = (1001 0110)$ (от набора 000 до 111). Укажите точное множество индексов минтермов, образующих её СДНФ.

\{m_0, m_3, m_4, m_7\}

\{1, 2, 4, 7\}

\{0, 3, 5, 6\}

\{m_1, m_2, m_5, m_6\}

Функция от 3 переменных задана вектором $f = (0110 1001)$ . Выберите корректную запись СКНФ через макстермы $M_i$ .

M_1 \land M_2 \land M_4 \land M_7

M_0 \land M_3 \land M_5 \land M_6

m_0 \lor m_3 \lor m_5 \lor m_6

M_0 \lor M_3 \lor M_5 \lor M_6

Дана функция 4 переменных $f(A,B,C,D)$ , принимающая значение 1 на наборах 5, 6, 7, 13, 14, 15. Карта Карно организована так: строки маркированы $AB$ (в порядке 00, 01, 11, 10), столбцы — $CD$ (00, 01, 11, 10). Найдите минимальную ДНФ после склеивания.

C \land D \lor B \land C

B \land \overline{C} \lor B \land D

\overline{A} \land B \land D \lor A \land B \land D \lor B \land C

B \land D \lor B \land C

Функция 4 переменных задана картой Карно (строки $AB$ : 00, 01, 11, 10; столбцы $CD$ : 00, 01, 11, 10). Единицы находятся во всех 4 ячейках первого столбца ( $CD=00$ ) и во всех 4 ячейках последнего столбца ( $CD=10$ ). На остальных наборах функция равна 0. Укажите минимальную ДНФ.

\overline{C} \land \overline{D} \lor C \land \overline{D}

\overline{C}

\overline{A} \land \overline{B} \land \overline{D}

\overline{D}

Булева функция 3 переменных задана вектором $f = (0110 1001)$ (стандартный порядок аргументов $x_1, x_2, x_3$ от 000 до 111). Постройте её полином Жегалкина. Выберите правильный результат.

1 \oplus x_1 \land x_2 \oplus x_3

x_1 \land x_2 \oplus x_3

x_1 \oplus x_2 \oplus x_3

1 \oplus x_1 \oplus x_2 \oplus x_3

Используя аналитические преобразования (формулы перехода), постройте полином Жегалкина для функции импликации конъюнкции $f(A,B,C) = A \to (B \land C)$ .

1 \oplus A \oplus B \land C

1 \oplus A \land B \land C

1 \oplus A \oplus A \land B \land C

A \oplus B \land C \oplus A \land B \land C

Упростите логическое выражение $F = (A \land B) \lor (A \land \overline{B} \land C) \lor (\overline{A} \land B)$ до минимальной ДНФ, последовательно применяя законы склеивания и поглощения.

B \lor C

A \lor B

B \lor (A \land C)

(A \land B) \lor C

Выполните равносильные преобразования и найдите минимальную форму для функции $F = \overline{(\overline{A} \lor B)} \lor (\overline{A} \land \overline{B})$ .

1

\overline{A} \lor \overline{B}

\overline{B}

\overline{A}

Постройте двойственную функцию $f^*$ для булевой функции $f(x, y, z) = x \land (y \lor \overline{z})$ , используя принцип двойственности.

x \lor (y \land \overline{z})

\overline{x} \land (\overline{y} \lor z)

\overline{x} \lor (\overline{y} \land z)

x \lor (\overline{y} \land z)

Переведите дизъюнктивную нормальную форму $\overline{A} \land B \lor C$ в конъюнктивную нормальную форму (КНФ), используя дистрибутивный закон.

(\overline{A} \lor C) \land (B \lor C)

(A \lor C) \land (\overline{B} \lor C)

(\overline{A} \lor B) \land C

(\overline{A} \land C) \lor (B \land C)

Примените законы де Моргана, чтобы привести инверсию функции $F = (A \lor \overline{B}) \land C$ к дизъюнктивной нормальной форме (ДНФ). То есть найдите ДНФ для $\overline{F}$ .

(\overline{A} \land B) \lor C

\overline{A} \land B \land \overline{C}

\overline{A} \lor B \lor \overline{C}

\overline{A} \land B \lor \overline{C}

Булева функция 4 переменных $f(A,B,C,D)$ задана вектором, где единицы стоят на наборах 0, 2, 5, 7, а безразличные состояния (помечены как $X$ ) — на наборах 8, 10, 13, 15. На остальных наборах функция равна 0. Карта Карно организована в порядке строк $AB$ (00, 01, 11, 10) и столбцов $CD$ (00, 01, 11, 10). Найдите минимальную ДНФ.

\overline{B} \land \overline{D} \lor B \land D

\overline{A} \land \overline{B} \land \overline{D} \lor \overline{A} \land B \land D

\overline{D} \lor B \land D

\overline{A} \land \overline{B} \lor B \land D

Функция задана условиями: $f(A,B,C,D) = 1$ на наборах 1, 3, 4, 6; на наборах 0, 2, 5, 7 её значения не определены (безразличные состояния $X$ ). На остальных наборах (от 8 до 15) функция равна 0. Оптимизируйте функцию с помощью карты Карно, используя доопределение. Какова минимальная ДНФ?

\overline{A} \land \overline{C}

\overline{A} \land D \lor \overline{A} \land B \land \overline{D}

\overline{A} \land \overline{B} \lor \overline{A} \land B

\overline{A}

Проверьте систему функций $F = \{A \land B, A \oplus B, 1\}$ на функциональную полноту по критерию Поста (рассматриваем классы $T_0, T_1, S, M, L$ ). Выберите верное утверждение.

Система не полна, так как обе переменные функции

A \oplus B

фиктивны на нулевом наборе. Система полна, так как для каждого из пяти классов Поста в ней найдётся хотя бы одна функция, не принадлежащая этому классу. Система не полна, так как в ней нет ни одной самодвойственной функции (все функции принадлежат классу

S

). Система не полна, так как функция

A \land B

нелинейна, и поэтому базис построить невозможно.

Проверьте систему функций $F = \{A \leftrightarrow B, \overline{A}\}$ по критерию Поста. Является ли она функционально полной?

Да, система полна, так как эквивалентность не монотонна, а инверсия не сохраняет константы. Нет, система не полна, так как обе функции самодвойственны (содержится в классе

S

). Нет, система не полна, так как обе функции являются линейными (целиком содержится в классе

L

). Да, так как из эквивалентности и инверсии можно напрямую выразить конъюнкцию.

Задана функционально полная система функций $\{A \land B, \overline{A}, 0, 1\}$ . Какая её подсистема образует минимальный (безызбыточный) базис?

\{A \land B, \overline{A}\}

\{A \land B, 0, 1\}

Система уже является безызбыточной.

\{\overline{A}, 0, 1\}

Булева функция 3 переменных $f(A,B,C)$ принимает значение 1 тогда и только тогда, когда ровно две из трёх её переменных равны 1. Синтезируйте эту функцию и выберите её корректную СДНФ.

A \land B \land C \lor A \land B \land \overline{C} \lor \overline{A} \land \overline{B} \land \overline{C}

\overline{A} \land \overline{B} \land C \lor \overline{A} \land B \land \overline{C} \lor A \land \overline{B} \land \overline{C}

(A \lor B \lor \overline{C}) \land (A \lor \overline{B} \lor C) \land (\overline{A} \lor B \lor C)

A \land B \land \overline{C} \lor A \land \overline{B} \land C \lor \overline{A} \land B \land C

Синтезируйте «мажоритарную функцию» от трёх переменных $f(A,B,C)$ , которая равна 1, если большинство (две или три) её переменных равны 1. Выберите её минимальную ДНФ.

A \land B \land C

A \land B \lor A \land C \lor B \land C

A \lor B \lor C

A \land B \land \overline{C} \lor A \land \overline{B} \land C \lor \overline{A} \land B \land C \lor A \land B \land C

Студент пытался перевести выражение $F = \overline{A \to (B \land C)}$ в ДНФ и выполнил следующие шаги:
Шаг 1: $F = \overline{\overline{A} \lor (B \land C)}$ (замена импликации).
Шаг 2: $F = \overline{\overline{A}} \lor \overline{B \land C}$ (закон де Моргана для внешней инверсии).
Шаг 3: $F = A \lor \overline{B} \lor \overline{C}$ (закон инволюции и де Моргана для конъюнкции).
На каком шаге студент совершил первую ошибку и в чём она заключается?

На шаге 2. При применении закона де Моргана к дизъюнкции

\overline{X \lor Y}

получается конъюнкция инверсий

\overline{X} \land \overline{Y}

, а студент ошибочно оставил знак дизъюнкции. Ошибок нет, студент всё выполнил верно. На шаге 1. Импликация

A \to B

равна

A \lor \overline{B}

, поэтому инверсия должна была стоять над правой скобкой. На шаге 3. При применении инволюции к

\overline{\overline{A}}

получается

\overline{A}

, а не

A

Студент проверяет систему $\{A \to B, A \oplus B\}$ на полноту по Посту. Он пишет: «Импликация на наборе (0,0) равна 1, значит она не принадлежит $T_0$ . Сложение по модулю 2 на наборе (0,0) равно 0, значит оно принадлежит $T_0$ . Поскольку в классе $T_0$ находится только одна функция из двух, система является неполной». В чём заключается концептуальная ошибка студента?

Студент неверно вычислил сложение по модулю 2 на наборе (0,0):

0 \oplus 0 = 1

, поэтому обе функции не принадлежат

T_0

. Ошибка в том, что импликация на самом деле принадлежит классу

T_0

, так как

0 \to 0 = 0

. Для полноты системы требуется, чтобы все функции системы не принадлежали классу

T_0

, а не только одна. Для полноты системы по классу

T_0

необходимо, чтобы хотя бы одна функция в системе не принадлежала этому классу. Студент нашёл такую функцию (импликация), значит, тест для класса

T_0

пройден успешно.

Булева функция 4 переменных $f(A, B, C, D)$ задана вектором значений $(0011 1100 0011 1100)$ (наборы от 0000 до 1111 в стандартном лексикографическом порядке). Выявите все фиктивные переменные этой функции.

Переменные

B

C

являются фиктивными. Переменная

C

является фиктивной. Функция не имеет фиктивных переменных. Переменные

A

D

являются фиктивными.

Постройте полином Жегалкина для функции 4 переменных $f(A,B,C,D) = (A \lor B) \land C \land D$ , используя аналитические (эквивалентные) преобразования. Выберите правильный результат.

A \land B \oplus C \land D \oplus A \land B \land C \land D

A \oplus B \oplus C \land D

A \land C \land D \oplus B \land C \land D

A \land C \land D \oplus B \land C \land D \oplus A \land B \land C \land D

Проверьте систему функций $S = \{x \to y, x \oplus y\}$ на полноту по критерию Поста. Можно ли выделить из неё минимальный базис, удалив одну из функций?

Система полна, но ни одну функцию удалить нельзя (система является минимальным базисом). Система неполна, так как обе функции не являются монотонными. Система неполна, так как ни одна из функций не принадлежит классу

T_0

. Система полна, функция

x \to y

является избыточной и её можно удалить.

Проверьте систему, состоящую всего из одной функции $S = \{ x \downarrow y \}$ (стрелка Пирса), на функциональную полноту. Выберите верное утверждение.

Система неполна, так как функция принадлежит классу линейных функций (

L

). Функция полна сама по себе, так как она не принадлежит ни одному из пяти классов Поста. Система полна, потому что функция принадлежит всем пяти классам Поста. Система неполна, так как функция самодвойственна (принадлежит

S

Студент проверяет цепочку равносильных преобразований при минимизации функции $F$ :
$F = \overline{A \to (B \lor \overline{C})} \lor (A \land B)$
Шаг 1: $F = (A \land \overline{B \lor \overline{C}}) \lor (A \land B)$
Шаг 2: $F = (A \land \overline{B} \land C) \lor (A \land B)$
Шаг 3: $F = A \land (\overline{B} \land C \lor B)$
Шаг 4: $F = A \land (C \lor B)$
На каком шаге студент допустил ошибку?

На шаге 1: неверно раскрыто отрицание импликации. На шаге 2: неверно применён закон де Моргана. На шаге 4: нельзя применять правило поглощения таким образом, правильный ответ

A \land \overline{B} \land C

. Ошибок нет, все преобразования абсолютно верны.

Найдите ошибку в следующем рассуждении: «Система $\{1, x \oplus y\}$ полна. Константа 1 не сохраняет нуль ( $1 \notin T_0$ ), а сложение по модулю 2 не сохраняет единицу ( $x \oplus y \notin T_1$ ), не является монотонным и не является самодвойственным. Таким образом, для каждого из пяти классов Поста в системе найдётся функция, которая ему не принадлежит».

Рассуждение полностью корректно, система полна. Ошибка в том, что сложение по модулю 2 сохраняет единицу (

1 \oplus 1 = 1

). Ошибка в том, что обе функции являются линейными (принадлежат классу

L

), поэтому система не перекрывает этот класс и не полна. Ошибка в том, что константа 1 монотонна, а значит система целиком лежит в классе

M

Синтезируйте логическую функцию управления аварийной вентиляцией. Вентиляция включается ( $F=1$ ), если уровень углекислого газа превышен ( $A=1$ ) ИЛИ (присутствуют люди ( $B=1$ ) И окна закрыты ( $C=0$ )). Однако, если сработала пожарная тревога ( $D=1$ ), вентиляция должна быть СТРОГО выключена ( $F=0$ ), чтобы не раздувать пламя. Выберите правильную минимальную ДНФ данной функции.

A \land \overline{D} \lor B \land C \land \overline{D}

A \land \overline{D} \lor B \land \overline{C} \land \overline{D}

(A \lor B \land \overline{C}) \land \overline{D}

A \land D \lor B \land \overline{C} \land D

Функция 5 переменных $f(x_1, x_2, x_3, x_4, x_5)$ (старший разряд $x_1$ , младший $x_5$ ) задана вектором значений из 32 бит, который состоит из чередующихся блоков по 8 одинаковых бит: 8 единиц, 8 нулей, 8 единиц, 8 нулей. Какие переменные являются фиктивными для данной функции?

x_1, x_2, x_5

x_2, x_4, x_5

Фиктивных переменных нет, все существенные.

x_1, x_3, x_4, x_5

Функция 3 переменных $f(x_1, x_2, x_3)$ задана вектором, где на наборах 000 и 001 функция равна 1; на наборах 010 и 011 функция не определена (безразличные состояния $X$ ); на наборах от 100 до 111 функция равна 0. Оптимизируйте её, доопределив $X$ так, чтобы получить минимальную ДНФ. Каким классам Поста принадлежит полученная функция?

Только

M

Функция образует базис (не принадлежит ни одному классу).

S

L

T_0

T_1

Постройте полином Жегалкина для функции $f(x_1, x_2, x_3) = \overline{x_1} \land \overline{x_2} \land x_3$ , используя формулы эквивалентного перехода к базису $\{\oplus, \land, 1\}$ . Выберите правильный результат.

x_3 \oplus x_1 \land x_3 \oplus x_2 \land x_3

x_3 \oplus x_1 \land x_3 \oplus x_2 \land x_3 \oplus x_1 \land x_2 \land x_3

x_1 \oplus x_2 \oplus x_3 \oplus x_1 \land x_2 \land x_3

1 \oplus x_1 \land x_2 \land x_3

Дана система функций $S = \{ x \leftrightarrow y, \overline{x} \}$ . Выберите класс Поста, который целиком содержит данную систему, делая её функционально неполной.

Класс функций, сохраняющих нуль (

T_0

) Класс монотонных функций (

M

) Класс самодвойственных функций (

S

) Класс линейных функций (

L

)

Функция 3 переменных $f(x,y,z)$ задана вектором, содержащим единицы только на наборах 1, 2, 4, 7 (в двоичном виде 001, 010, 100, 111). Минимизируйте её и определите, каким предполным классам Поста принадлежит полученная функция.

Принадлежит

T_0, T_1, S, L

. Принадлежит только

L

. Принадлежит

S, M, L

. Не принадлежит ни одному классу.

Выберите среди предложенных булевых функций ту, полином Жегалкина которой описывает самодвойственную функцию.

x \oplus y \oplus z \oplus x \land y \land z

x \land y \oplus x \land z \oplus y \land z \oplus 1

x \oplus y \oplus x \land y

x \oplus y \oplus z

Студент утверждает: «Если булева функция сохраняет нуль ( $f \in T_0$ ) и сохраняет единицу ( $f \in T_1$ ), то она гарантированно является монотонной ( $f \in M$ )». Выберите функцию, которая является контрпримером, доказывающим ложность этого утверждения.

f(x,y) = x \land y

f(x,y,z) = x \oplus y \oplus z

f(x,y) = x \leftrightarrow y

f(x,y) = x \lor y

Даны две системы функций: $S_1 = \{ x \downarrow y, x \oplus y \}$ и $S_2 = \{ x \lor y, x \oplus y \}$ . Сравните их на функциональную полноту по критерию Поста. Какое утверждение верно?

Обе системы являются функционально полными.

S_1

является функционально полной, а

S_2

— нет.

S_2

является функционально полной, а

S_1

— нет. Обе системы не являются полными.

Булева функция 4 переменных самодвойственна. Известно, что на всех наборах с весом 1 (где ровно одна единица) функция равна 1. Каково её значение на наборах с весом 3 (где ровно три единицы)?

Функция равна 1 на всех наборах с весом 3. Функция равна 0 на всех наборах с весом 3. Функция с такими свойствами не может быть самодвойственной. Значение зависит от конкретной переменной, равной нулю.

Функция 4 переменных $f(A,B,C,D)$ задана картой Карно. Единицы расположены на наборах 0, 1, 4, 5, 8, 9, 12, 13. (Порядок строк $AB$ : 00, 01, 11, 10; порядок столбцов $CD$ : 00, 01, 11, 10). Выберите её минимальную ДНФ.

\overline{A} \land \overline{C} \lor A \land \overline{C}

\overline{C} \land \overline{D} \lor \overline{C} \land D

\overline{D}

\overline{C}

Примените теорему разложения Шеннона по переменной $B$ к логической функции $F(A,B,C) = (A \to B) \oplus C$ . Выберите правильный результат разложения.

B \land C \lor \overline{B} \land (\overline{A} \oplus C)

B \land \overline{C} \lor \overline{B} \land (\overline{A} \oplus C)

B \land (A \oplus C) \lor \overline{B} \land C

B \land \overline{C} \lor \overline{B} \land \overline{C}

Функция 2 переменных задана таблично: $f(0,0)=a_0$ , $f(0,1)=1$ , $f(1,0)=0$ , $f(1,1)=X$ . Найдите такое значение $a_0$ и доопределение $X$ , при которых полином Жегалкина не будет содержать нелинейного слагаемого $xy$ .

a_0 = 0

X = 1

a_0 = 1

X = 0

При любых

a_0

слагаемое

xy

будет присутствовать.

a_0 = 0

X = 0

Студент проверяет функцию $f(x,y,z)$ на монотонность и пишет доказательство: «Я проверил наборы: $f(011)=1$ и $f(001)=0$ . Набор 011 больше 001, значение функции не убывает. Также набор $f(111)=1$ больше $f(101)=1$ , значение не убывает. Поскольку все проверенные мной пары сравнимых наборов не выявили убывания, функция является монотонной». В чём заключается грубая методическая ошибка?

Если

f(111) = f(101) = 1

, это означает стагнацию значения, что нарушает строгое возрастание, поэтому функция не монотонна. Доказательство монотонности требует проверки всех возможных пар сравнимых наборов (или доказательства через аналитическую форму без инверсий). Проверка случайных 2-3 пар не гарантирует монотонности всей функции. Набор 011 не является сравнимым с набором 001, так как они отличаются в разряде

y

. Ошибок нет, если функция не убывает на весе 1->2 и 2->3, она монотонна.

Даны две формы записи функции $f = x \oplus y$ : её минимальная ДНФ и минимальная КНФ. Сравните количество букв (литералов) в обеих минимальных формах. Выберите верное утверждение.

Минимальная ДНФ содержит меньше букв, чем минимальная КНФ. Минимальная КНФ содержит меньше букв, чем минимальная ДНФ. В обеих минимальных формах ровно по 4 буквы, они одинаковы по длине. Функция XOR не может быть выражена в КНФ.

Докажите или опровергните следующее утверждение: «Если булевы функции $f(x,y)$ и $g(x,y)$ обе являются самодвойственными, то функция $h(x,y) = f(x,y) \oplus g(x,y)$ также всегда является самодвойственной». Выберите верный вердикт.

Утверждение истинно, так как класс

S

замкнут относительно операции сложения по модулю 2. Утверждение истинно: инверсии аргументов выносятся за знак XOR по правилам линейной алгебры. Утверждение ложно. Сумма по модулю 2 двух самодвойственных функций всегда даёт функцию, которая принимает одинаковые значения на противоположных наборах (чётную), что прямо нарушает самодвойственность. Утверждение ложно, так как сама функция XOR не является самодвойственной, поэтому она разрушает класс

S

Докажите или опровергните утверждение: «Любая самодвойственная линейная функция от $n$ переменных всегда содержит строго нечётное количество слагаемых в своём полиноме Жегалкина». Выберите правильный вывод.

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

S \cap L

содержит только функцию

f(x) = x

(одно слагаемое). Утверждение ложно. Контрпримером является функция

f(x) = 1 \oplus x

, которая самодвойственна, но содержит чётное (два) число слагаемых.

Вам требуется спроектировать функцию 3 переменных, которая удовлетворяет одновременно трём условиям: 1) является строго монотонной ( $f \in M$ ); 2) является самодвойственной ( $f \in S$ ); 3) существенно зависит от всех трёх переменных. Выберите минимальную ДНФ такой функции.

A \oplus B \oplus C

A \land B \land C \lor \overline{A} \land \overline{B} \land \overline{C}

Функции, удовлетворяющей всем трём условиям, не существует.

A \land B \lor A \land C \lor B \land C

Задана полная система функций $S = \{0, 1, x \land y, x \lor y, x \oplus y \oplus z\}$ . Из неё требуется выделить минимальный базис (подсистему, удаление любой функции из которой делает её неполной). Сколько различных вариантов минимальных базисов можно составить из элементов этой системы?

Ровно 1 вариант. 3 варианта. Ровно 2 варианта. Система уже является минимальным базисом (0 вариантов выделения).

(Задача-головоломка). Восстановите булеву функцию 4 переменных $f(A,B,C,D)$ , если о ней известны следующие факты:

Функция линейна (принадлежит классу $L$ ).
$f(0,0,0,0) = 1$ .
$f(1,0,0,0) = 0$ .
$f(0,1,1,1) = 0$ .
Функция фиктивна по переменной $D$ .
Сколько всего существует булевых функций 4 переменных, которые удовлетворяют абсолютно всем этим условиям одновременно?

Ровно 2 функции. Ровно 1 функция. Таких функций не существует (0 функций). Ровно 4 функции.

Блок 2. Краткий ответ

Если булева функция является самодвойственной ( $f \in S$ ) и сохраняет нуль ( $f \in T_0$ ), какому еще предполному классу Поста она гарантированно принадлежит?

обозначение класса, например T0 или M

Мажоритарная функция от трёх переменных задана формулой $f(x,y,z) = x \land y \lor x \land z \lor y \land z$ . Какому единственному из пяти предполных классов Поста она НЕ принадлежит?

заглавная латинская буква, например S

Введите количество булевых функций от $n$ переменных, которые одновременно сохраняют 0 и 1 (то есть принадлежат пересечению классов $T_0 \cap T_1$ ).

выражение через ^, например 2^(n-1)

Известно, что булевы функции $f$ и $g$ принадлежат классу линейных функций $L$ . Укажите бинарную логическую операцию над этими двумя функциями, которая гарантированно порождает функцию, также принадлежащую классу $L$ .

символ операции или её название

Определите математическую степень полинома Жегалкина для функции дизъюнкции трёх переменных $f(x,y,z) = x \lor y \lor z$ . (Степенью полинома называется максимальное количество переменных в одной конъюнкции с ненулевым коэффициентом).

целое число

Полином Жегалкина функции 3 переменных $f(x_1, x_2, x_3)$ имеет вид $1 \oplus x_1 \oplus x_2 \land x_3$ . Восстановите вектор её значений, если наборы упорядочены в стандартном лексикографическом порядке от 000 до 111.

8 цифр 0 и 1 без пробелов

Функция 4 переменных $f(A,B,C,D)$ задана списком минтермов (номерами единичных наборов в десятичном виде от 0 до 15): $\sum m(1, 3, 5, 7, 9, 11, 13, 15)$ . Минимизируйте её на карте Карно и укажите её минимальную ДНФ.

одна буква

Как называются конъюнкции (импликанты), получаемые на первом этапе метода Квайна-Макласки после выполнения всех возможных операций попарного склеивания и поглощения, которые больше нельзя склеить?

два слова

Как называется дизъюнкция простых импликант (покрытие функции), из которой нельзя удалить ни одну импликанту без изменения (потери покрытия) самой функции?

два слова

Дана булева функция $f(A,B,C) = (A \lor \overline{A}) \land B \land (C \to C)$ . Перечислите все переменные, которые являются фиктивными для данной функции.

{буквы через запятую}

Мажоритарная функция 5 переменных $M_5(x_1, x_2, x_3, x_4, x_5)$ возвращает 1, если большинство её аргументов (т.е. 3, 4 или 5) равны 1. Рассчитайте количество минтермов в её совершенной дизъюнктивной нормальной форме (СДНФ).

целое число

Разложение булевой функции в виде $f(x_1, \dots, x_n) = x_1 \land f(1, x_2, \dots, x_n) \lor \overline{x_1} \land f(0, x_2, \dots, x_n)$ носит имя известного математика. Как называется это разложение?

два слова, например «теорема Пифагора»

Дана функционально полная система булевых функций $S = \{ x \land y, x \lor y, \overline{x}, 0, 1 \}$ . Какое максимальное количество различных минимальных (безызбыточных) базисов можно выделить из элементов этой системы?

целое число

На карте Карно для функции 3 переменных $f(A,B,C)$ (где $A$ задаёт строки, а $BC$ — столбцы) в ячейке, расположенной на пересечении строки $A=1$ и столбца $BC=10$ , находится единица. Укажите десятичный индекс минтерма $m_i$ , соответствующего этой ячейке.

целое число

Найдите значение коэффициента $a_{12}$ в полиноме Жегалкина для булевой функции дизъюнкции $f(x_1, x_2) = x_1 \lor x_2$ .

0 или 1

Упростите логическое выражение $F = A \lor (A \land \overline{B}) \lor (A \land B \land C)$ , последовательно применив закон поглощения до получения кратчайшей формы.

одна буква

Известно, что макстерм является инверсией минтерма. Для функции 3 переменных найдите десятичный индекс макстерма $M_i$ , который тождественно равен инверсии минтерма $m_5$ (то есть $\overline{m_5}$ ).

целое число

Представьте операцию импликации $f(A, B) = A \to B$ в виде полинома Жегалкина и вычислите его значение на наборе $A=1, B=0$ .

0 или 1

Сколько макстермов содержит совершенная конъюнктивная нормальная форма (СКНФ) для функции строгой дизъюнкции (XOR) трёх переменных $f(A,B,C) = A \oplus B \oplus C$ ?

целое число

100

Примените принцип двойственности для построения двойственной функции $f^*$ к функции $f(x,y) = x \lor (x \land y)$ . Упростите полученную двойственную функцию до единственной переменной.

одна буква

101

На карте Карно для 4 переменных ( $A, B, C, D$ ) группа единиц была склеена в одну простую импликанту, которая описывается конъюнкцией из одной переменной: $\overline{B}$ . Сколько единичных ячеек карты покрывает эта импликанта?

целое число

102

Булева функция трёх переменных задана выражением $f(x, y, z) = (x \to y) \land (z \lor \overline{z})$ . Укажите переменную, которая является фиктивной для данной функции.

одна буква

103

При каком значении константы $c \in \{0, 1\}$ функция $f(x, y) = x \land y \oplus c$ будет принадлежать классу Поста $T_0$ (функции, сохраняющие ноль)?

0 или 1

104

Упростите логическое выражение $A \leftrightarrow \overline{A}$ до логической константы.

0 или 1

105

Булева функция $f(x,y,z)$ гарантированно является самодвойственной ( $f \in S$ ). Вычисление функции на наборе $010$ дало результат $f(0,1,0) = 1$ . Какое значение примет эта функция на наборе $101$ ?

0 или 1

106

Булева функция от двух переменных $f(x,y)$ тождественно равна константе 1. Сколько существенных переменных имеет эта функция?

целое число

107

Булева функция от трёх переменных задана аналитически как $f(A,B,C) = A \lor B$ . Перечислите через запятую по возрастанию десятичные индексы минтермов $m_i$ , которые образуют её совершенную дизъюнктивную нормальную форму (СДНФ).

{числа через запятую}

108

В алгоритме Квайна-Макласки на первом этапе происходит попарное склеивание минтермов. Если склеить минтерм, соответствующий набору 1010, с минтермом 1011, какой результат (склеенный терм) получится в стандартной записи, где сокращённая переменная обозначается прочерком '-'?

4 символа из 0, 1 и -

109

Принадлежит ли булева функция $f(x,y,z) = x \oplus y \oplus 1$ классу линейных функций ( $L$ )? Введите 1, если да, и 0, если нет.

0 или 1

110

Рассмотрим систему, состоящую всего из одной функции: $f(x,y,z) = x \land y \land z$ . Каким двум предполным классам Поста (из множества $T_0, T_1, S, M, L$ ) эта функция НЕ принадлежит?

{обозначения классов через запятую}

111

Известно, что булева функция 2 переменных $f(x,y)$ является монотонной (принадлежит классу $M$ ). Вычисление показало, что на наборе $01$ она принимает значение $1$ ( $f(0,1) = 1$ ). Какое значение функция обязана принять на наборе $11$ , чтобы не нарушить условие строгой монотонности?

0 или 1

112

Булева функция задана выражением $f(A,B) = A \land \overline{B}$ . Укажите, принадлежит ли она классу Поста $T_0$ (функции, сохраняющие ноль) и $T_1$ (функции, сохраняющие единицу).

два числа через запятую: сначала для T0, затем для T1 (1 — принадлежит, 0 — нет)

113

Выявите все фиктивные переменные в логическом выражении $F(A,B,C) = (A \oplus B) \oplus (A \leftrightarrow B) \oplus C$ .

{буквы через запятую}

114

Для булевой функции 4 переменных найдите десятичный индекс макстерма $M_i$ , который тождественно является инверсией минтерма $m_0$ (то есть $\overline{m_0}$ ).

целое число

115

Найдите значение коэффициента $a_{123}$ (коэффициент при конъюнкции всех трёх переменных) в полиноме Жегалкина для функции дизъюнкции $f(A,B,C) = A \lor B \lor C$ .

0 или 1

116

Выполните попарное склеивание двух минтермов, заданных двоичными наборами $0101$ и $1101$ , по алгоритму Квайна-Макласки. Запишите полученную импликанту, используя прочерк '-' для поглощённой переменной.

4 символа из 0, 1 и -

117

Сколько единиц (наборов, на которых функция равна 1) содержится в таблице истинности функции 3 переменных $f(A,B,C) = A \to (B \to C)$ ?

целое число

118

Принадлежит ли функция импликации $f(A,B) = A \to B$ классу монотонных функций ( $M$ )? Введите 1, если да, и 0, если нет.

0 или 1

119

Известно, что полином Жегалкина функции $f(x,y)$ имеет вид $1 \oplus x \oplus y \oplus c \cdot x \land y$ , где $c$ — неизвестный логический коэффициент (0 или 1). Вычисление функции на наборе $f(1,1)$ дало результат 1. Найдите значение коэффициента $c$ .

0 или 1

120

Чему равно пересечение любого множества $A$ с его абсолютным дополнением $\overline{A}$ в теории множеств (закон противоречия)?

множество или слова «пустое множество»

121

Даны три конечных множества: $|A| = 2$ , $|B| = 3$ , $|C| = 4$ . Вычислите мощность (количество элементов) их декартова произведения $|A \times B \times C|$ .

целое число

122

Множество состоит ровно из 5 элементов. Сколько всего различных подмножеств (включая пустое подмножество и само исходное множество) можно из него составить? То есть, какова мощность его булеана?

целое число

123

Вычислите точное количество самодвойственных булевых функций (принадлежащих классу $S$ ), которые зависят от 3 переменных.

целое число

124

Вычислите точное количество линейных булевых функций (принадлежащих классу $L$ ), зависящих от 4 переменных.

целое число

125

Сколько простых импликант (первичных терминов, которые невозможно склеить дальше) содержит функция строгой дизъюнкции (XOR) трёх переменных $f(A,B,C) = A \oplus B \oplus C$ ?

целое число

126

Вычислите количество булевых функций от 3 переменных, которые одновременно сохраняют 0 и сохраняют 1 (то есть принадлежат пересечению предполных классов $T_0 \cap T_1$ ).

целое число

127

Образует ли система функций $S = \{A \to B, A \oplus B\}$ функционально полный базис по критерию Поста? Введите 1, если да (полна), и 0, если нет.

0 или 1

128

Докажите, что функция эквивалентности $f(A,B) = A \leftrightarrow B$ не является монотонной, найдя пару сравнимых наборов (запишите их в десятичном виде от 0 до 3), на которых значение функции убывает.

два номера набора через запятую: меньший, затем больший

129

Какая единственная булева функция от одной переменной $x$ одновременно принадлежит всем пяти предполным классам Поста ( $T_0, T_1, S, M, L$ )?

одна буква

130

Булева функция $f(A, B, C, D)$ задана множеством минтермов $f = \{0, 2, 5, 7, 13, 15\}$ и имеет неопределённые (запрещённые) состояния на наборах $X = \{8, 10\}$ . Используя карты Карно, найдите минимальную ДНФ данной функции при оптимальном доопределении. В ответе укажите количество простых импликант, вошедших в финальную минимальную ДНФ.

целое число

131

Синтезируйте комбинационную схему, реализующую функцию логического следования (импликации) $f(A, B) = A \to B$ , используя только логические элементы «штрих Шеффера» (И-НЕ, $x | y$ ). Какое минимальное количество двухвходовых элементов И-НЕ для этого потребуется?
(Подсказка: инверсия переменной $\overline{X}$ реализуется как $X | X$ и требует 1 элемент).

целое число

132

Рассматривается булево уравнение $X \oplus Y = A \land B$ , где $X$ и $Y$ — неизвестные булевы функции от двух переменных $A$ и $B$ . Вычислите, сколько всего существует различных пар функций $(X, Y)$ , являющихся решениями этого уравнения.

целое число

133

Проектируется синхронный 2-разрядный двоичный счётчик на T-триггерах. Состояния счётчика $Q_1 Q_0$ сменяются по циклу: $00 \to 01 \to 10 \to 11 \to 00$ . Триггер меняет своё состояние, если на его вход T подана 1. Запишите функцию возбуждения $T_1$ для старшего разряда $Q_1$ в минимальной ДНФ.

обозначение, например Q1

Блок 3. Несколько верных вариантов

134

Какие из представленных ниже выражений являются строгими примерами Совершенной Конъюнктивной Нормальной Формы (СКНФ) для функции трёх переменных?

Отметьте все верные варианты

(A \land B \land C) \lor (\overline{A} \land \overline{B} \land C)

(A \lor B \lor C) \land (\overline{A} \lor B \lor \overline{C})

\overline{A} \lor \overline{B} \lor \overline{C}

(A \lor \overline{B}) \land (\overline{A} \lor C)

A \land \overline{B} \land C

135

В каком случае переменная $X_i$ булевой функции называется фиктивной?

Отметьте все верные варианты

Если функция тождественно равна 0 при

X_i = 0

. Если функция состоит только из конъюнкций, не содержащих

X_i

. Если изменение значения

X_i

с 0 на 1 не изменяет значение функции ни на одном из наборов остальных переменных. Если её инверсия

\overline{X_i}

не встречается в минимальной ДНФ функции.

136

Выберите правильное определение макстерма (конституенты нуля).

Отметьте все верные варианты

Булева функция, которая принимает значение 1 только на одном наборе. Дизъюнкция всех переменных функции, каждая из которых входит в прямой или инверсной форме, принимающая значение 0 только на одном наборе. Дизъюнкция, содержащая не более

n-1

переменных функции. Конъюнкция всех переменных функции, каждая из которых входит в прямой или инверсной форме.

137

Какая операция из теории множеств соответствует логической конъюнкции (операции И)?

Отметьте все верные варианты

Симметрическая разность (

A \oplus B

) Пересечение (

A \cap B

) Объединение (

A \cup B

) Разность (

A \setminus B

)

138

Примените законы де Моргана для раскрытия инверсии над выражением $\overline{A \lor (B \land C)}$ . Какой вариант является тождественно равным исходному?

Отметьте все верные варианты

\overline{A} \land \overline{B} \land \overline{C}

A \land (\overline{B} \lor \overline{C})

\overline{A} \lor (\overline{B} \land \overline{C})

\overline{A} \land (\overline{B} \lor \overline{C})

139

Какое из выражений демонстрирует правильное применение закона поглощения в булевой алгебре?

Отметьте все верные варианты

Все перечисленные

A \lor (A \land B) = A

A \lor \overline{A} \land B = A \lor B

A \land (A \lor B) = A

140

Какое выражение тождественно равно $A \land B \lor A \land \overline{B}$ согласно закону склеивания?

Отметьте все верные варианты

A \lor B

A

1

B

141

Какой закон позволяет перейти от выражения $A \lor (B \land C)$ к выражению $(A \lor B) \land (A \lor C)$ ?

Отметьте все верные варианты

Закон поглощения Дистрибутивность конъюнкции относительно дизъюнкции Дистрибутивность дизъюнкции относительно конъюнкции Закон склеивания

142

Какая из перечисленных функций принадлежит классу $T_0$ (функций, сохраняющих ноль)?

Отметьте все верные варианты

f(A,B) = A \leftrightarrow B

f(A,B) = A \downarrow B

(стрелка Пирса)

f(A,B) = A \land B

f(A,B) = A \to B

143

Выберите все функции, которые принадлежат классу $T_1$ (сохраняющие единицу).

Отметьте все верные варианты

f(A,B) = A \land B

f(A,B) = A \to B

f(A,B) = A \oplus B

f(A,B) = A \lor B

144

Какие из нижеперечисленных функций являются самодвойственными (принадлежат классу $S$ )?

Отметьте все верные варианты

f(x,y) = x \land y

f(x) = \overline{x}

f(x,y,z) = x \oplus y \oplus z

f(x,y) = x \leftrightarrow y

145

Является ли функция импликации $f(A,B) = A \to B$ монотонной (класс $M$ )?

Отметьте все верные варианты

Да, так как она принимает значение 1 на большем числе наборов. Нет, так как при переходе от набора (0, 0) к набору (1, 0) значение функции убывает с 1 до 0. Да, так как она не содержит инверсий в полиноме Жегалкина. Нет, так как она не сохраняет ноль.

146

Функция 4 переменных задана картой Карно. Единицы расположены строго по четырём углам карты. Какая простая импликанта покрывает эту группу из 4 единиц? (Строки маркированы $AB$ , столбцы $CD$ ).

Отметьте все верные варианты

B \land D

\overline{B} \land \overline{D}

\overline{A} \land \overline{C}

\overline{A} \land \overline{B} \land \overline{C} \land \overline{D}

147

Какое алгебраическое выражение представляет собой полином Жегалкина для операции импликации $A \to B$ ?

Отметьте все верные варианты

A \oplus B \oplus 1

A \oplus A \land B

1 \oplus B \oplus A \land B

1 \oplus A \oplus A \land B

148

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

Отметьте все верные варианты

1010 и 1110 1001 и 0110 0000 и 1111 0101 и 0111

149

Какие из приведённых ниже формул тождественно равны функции строгой дизъюнкции (XOR, $A \oplus B$ )?

Отметьте все верные варианты

\overline{A} \land \overline{B} \lor A \land B

\overline{A \leftrightarrow B}

A \land \overline{B} \lor \overline{A} \land B

(A \lor B) \land (\overline{A} \lor \overline{B})

150

Какие из перечисленных утверждений корректно описывают суть метода Квайна-Мак-Класки при минимизации булевых функций?

Отметьте все верные варианты

Метод гарантирует мгновенное нахождение одной минимальной ДНФ без построения промежуточной сокращённой формы. На первом этапе минтермы разбиваются на группы по количеству единиц (или нулей) в их двоичном представлении. Поглощённая (изменившаяся) переменная при склеивании заменяется прочерком. Склеивание допускается только между минтермами (или импликантами), принадлежащими соседним группам, отличающимся на одну единицу. Результатом первого этапа метода всегда является тупиковая ДНФ.

151

Какова главная цель применения метода Петрика в процессе минимизации булевых функций?

Отметьте все верные варианты

Нахождение совершенной дизъюнктивной нормальной формы (СДНФ) по таблице истинности. Графическое склеивание минтермов на поверхности тора (карте Карно). Преобразование сокращённой ДНФ в совокупность всех тупиковых ДНФ с помощью импликантной матрицы. Поиск фиктивных переменных функции.

152

Выберите верные утверждения относительно простых импликант булевой функции:

Отметьте все верные варианты

Дизъюнкция всех простых импликант функции образует её тупиковую ДНФ. Дизъюнкция всех простых импликант функции образует её сокращённую ДНФ. Любая простая импликанта всегда покрывает ровно один минтерм функции. Простая импликанта — это конъюнкция, из которой нельзя удалить ни одну переменную без того, чтобы она перестала быть импликантой данной функции.

153

В чём заключается основное математическое ограничение карт Карно (диаграмм Вейча) по сравнению с алгебраическими методами (например, методом Квайна-Мак-Класки)?

Отметьте все верные варианты

Карты Карно не позволяют находить минимальные ДНФ, только сокращённые. Карты Карно неприменимы к функциям с неопределёнными состояниями. Использование карт Карно ограничено возможностями визуального восприятия многомерных кубов (эффективны для

n \le 4-5

, редко

6

). Карты Карно могут использоваться только для монотонных функций.

154

Какие из представленных ниже выражений являются булевыми уравнениями, требующими решения относительно неизвестной функции $X$ ?

Отметьте все верные варианты

X \to Y = A \land \overline{B}

X(A, B) = A \oplus B

X \land A \lor \overline{X} \land B = C

A \land B \lor \overline{A} = A \lor B

155

Дано простое булево уравнение: $X \oplus A = B$ , где $X$ — неизвестная функция. Каким образом выражается единственное решение этого уравнения?

Отметьте все верные варианты

X = \overline{A} \lor B

X = A \leftrightarrow B

X = A \oplus B

X = A \land B

156

Выберите верное условие, при котором булево уравнение вида $f(x_1, x_2, \dots, x_n) = 0$ не имеет ни одного решения.

Отметьте все верные варианты

Если функция

f

является самодвойственной. Если функция

f

тождественно равна

1

. Если функция

f

является линейной. Если функция

f

тождественно равна

0

157

Сколько решений (различных пар значений $X, Y \in \{0,1\}$ ) имеет булево уравнение $X \lor Y = 1$ ?

Отметьте все верные варианты

3 1 4 2

158

Какое из определений строго описывает симметрическую булеву функцию от $n$ переменных?

Отметьте все верные варианты

Функция, которая принимает одинаковые значения на противоположных (инверсных) наборах аргументов. Функция, полином Жегалкина которой не содержит конъюнкций. Функция, таблица истинности которой совпадает при чтении сверху вниз и снизу вверх. Функция, значение которой не изменяется при любой перестановке её аргументов.

159

Симметрическая функция от 3 переменных $S(A,B,C)$ задана множеством своих рабочих чисел (a-чисел): $\{0, 3\}$ . Какая из предложенных формул соответствует этой функции?

Отметьте все верные варианты

A \land B \lor B \land C \lor A \land C

A \oplus B \oplus C

A \land B \land C \lor \overline{A} \land \overline{B} \land \overline{C}

\overline{A \lor B \lor C}

160

Какие компоненты однозначно задают пороговую булеву функцию $f(x_1, \dots, x_n)$ ?

Отметьте все верные варианты

Матрица инцидентности. Набор целочисленных весов

w_1, \dots, w_n

для каждой переменной и значение порога

T

. Заданный полином Жегалкина без констант. Множество a-чисел (рабочих чисел).

161

Булева функция $f(A,B,C)$ является пороговой с весами $w_A=1, w_B=2, w_C=1$ и порогом $T=3$ . На каких из перечисленных наборов функция примет значение 1?

Отметьте все верные варианты

(0, 1, 0)

(1, 1, 0)

(0, 1, 1)

(1, 0, 1)

(1, 1, 1)

162

Выберите правильное аналитическое определение производной булевой функции $f(x_1, \dots, x_i, \dots, x_n)$ по переменной $x_i$ : $\frac{\partial f}{\partial x_i}$ .

Отметьте все верные варианты

\frac{\partial f}{\partial x_i} = f(x_i = 1) \land f(x_i = 0)

\frac{\partial f}{\partial x_i} = f(x_i = 1) \to f(x_i = 0)

\frac{\partial f}{\partial x_i} = f(x_i = 1) \lor f(x_i = 0)

\frac{\partial f}{\partial x_i} = f(x_i = 1) \oplus f(x_i = 0)

163

Если булева производная функции $f$ по переменной $x$ тождественно равна нулю ( $\frac{\partial f}{\partial x} \equiv 0$ ), какой вывод можно сделать о роли переменной $x$ в этой функции?

Отметьте все верные варианты

Переменная

x

является фиктивной для функции

f

. Переменная

x

является существенной для функции

f

. Функция

f

является линейной по переменной

x

. Функция

f

тождественно равна нулю.

164

Разложение булевой функции в ряд Тейлора-Маклорена строится на базе булевых производных. Какую известную форму представления функции в булевой алгебре генерирует ряд Маклорена, если разложение производится по всем переменным?

Отметьте все верные варианты

Совершенную дизъюнктивную нормальную форму (СДНФ) Полином Жегалкина Совершенную конъюнктивную нормальную форму (СКНФ) Карту Карно

165

Какое условие является необходимым и достаточным для существования неопределённого интеграла $\int f(X) dx$ от булевой функции $f(X)$ ?

Отметьте все верные варианты

Функция

f(X)

должна быть симметрической. Функция

f(X)

должна быть линейной. Функция

f(X)

должна быть независима от переменной

x

(т.е.

\frac{\partial f}{\partial x} = 0

). Функция

f(X)

должна быть тождественно равна 1.

166

В теории конечных автоматов существует чёткое разделение на автоматы Мили и автоматы Мура. В чём заключается принципиальное отличие функции выходов в автомате Мура по сравнению с автоматом Мили?

Отметьте все верные варианты

В автомате Мура выходной сигнал зависит только от текущего внутреннего состояния автомата, а в автомате Мили — от состояния и от входного сигнала. В автомате Мура выходной сигнал зависит только от входного сигнала, а в Мили — от внутреннего состояния. В автомате Мура нет функции выходов, он является только акцептором (распознавателем). Автомат Мура является асинхронным, а автомат Мили — синхронным.

167

При проектировании триггеров используются различные схемы управления. Какой недостаток асинхронного RS-триггера устраняется в JK-триггере?

Отметьте все верные варианты

В JK-триггере устранена запрещённая комбинация входных сигналов. JK-триггер работает быстрее. JK-триггер имеет только один информационный вход. JK-триггер не требует тактового сигнала (синхронизации).

168

В синхронных цифровых автоматах состояние меняется строго по фронту или срезу специального сигнала. Как называется этот сигнал?

Отметьте все верные варианты

Сигнал сброса (Reset) Информационный сигнал (Data) Тактовый сигнал (Clock / Синхроимпульс) Сигнал разрешения (Enable)

169

Выберите характеристики, которые строго определяют счётный T-триггер.

Отметьте все верные варианты

Имеет два информационных входа. Сохраняет своё состояние при подаче логического 0 на вход T. Устанавливается в 1 независимо от текущего состояния, если T=1. Меняет своё состояние на противоположное при подаче логической 1 на вход T.

170

Бинарное отношение $R$ на множестве $A$ обладает свойствами: 1) $aRa$ для всех $a \in A$ ; 2) если $aRb$ , то $bRa$ ; 3) если $aRb$ и $bRc$ , то $aRc$ . Как называется такое комплексное отношение в теории множеств?

Отметьте все верные варианты

Отношение строгого порядка Отношение толерантности Отношение нестрогого порядка Отношение эквивалентности

171

Какое бинарное отношение соответствует строгому определению «Отношение нестрогого порядка»?

Отметьте все верные варианты

Рефлексивное, симметричное, транзитивное Рефлексивное, антисимметричное, транзитивное Рефлексивное, несимметричное, нетранзитивное Антирефлексивное, асимметричное, транзитивное

172

Выберите формулу комбинаторики, которая вычисляет количество сочетаний из $n$ элементов по $k$ с повторениями (когда элементы могут повторяться).

Отметьте все верные варианты

C_n^k = \frac{n!}{k!(n-k)!}

\overline{A}_n^k = n^k

\overline{C}_n^k = C_{n+k-1}^k = \frac{(n+k-1)!}{k!(n-1)!}

A_n^k = \frac{n!}{(n-k)!}

173

Укажите формулу для вычисления мощности булеана (множества всех подмножеств) для декартова произведения множеств $A$ и $B$ . Известно, что кардинальное число $|A| = n$ , а $|B| = m$ .

Отметьте все верные варианты

2^{n + m}

n \cdot m

2^n \cdot 2^m

2^{n \cdot m}

174

Булева функция $f$ минимизируется методом Петрика. Построена импликантная матрица. Чтобы найти покрытия, составляют логическое уравнение, где для каждого столбца (минтерма) записывается дизъюнкция покрывающих его простых импликант, а затем эти дизъюнкции перемножаются (конъюнкция). Какие математические законы и правила необходимо применить к полученной КНФ, чтобы получить множество всех тупиковых ДНФ?

Отметьте все верные варианты

Правило де Моргана для инверсии всего выражения. Раскрытие скобок по закону дистрибутивности конъюнкции относительно дизъюнкции. Закон поглощения (

P_i \lor P_i \land P_j = P_i

). Переход к полиному Жегалкина. Закон идемпотентности (

P_i \land P_i = P_i

175

Функция задана наборами единиц и наборами безразличных состояний (неопределённостей). Выберите верные утверждения о процессе её минимизации с помощью карт Карно.

Отметьте все верные варианты

Все безразличные состояния обязательно должны быть доопределены как 1, чтобы получить минимальную ДНФ. Наличие неопределённых состояний всегда приводит к тому, что минимальная КНФ будет содержать меньше символов, чем минимальная ДНФ. Безразличное состояние доопределяется как 1 только в том случае, если это позволяет увеличить размер склеиваемого блока единиц (до

2^k

) и тем самым упростить импликанту. Все безразличные состояния, не вошедшие в блоки единиц, автоматически доопределяются как 0.

176

Булева функция 5 переменных $f(v, w, x, y, z)$ представлена на двойной карте Карно (две матрицы $4 \times 4$ , где первая матрица соответствует $v=0$ , а вторая — $v=1$ ). Группа из 8 единиц занимает первую строку в матрице $v=0$ и первую строку в матрице $v=1$ . Какие переменные останутся в простой импликанте после склеивания этой группы? (Строки маркированы $wx$ , столбцы $yz$ ).

Отметьте все верные варианты

v

w

x

w

x

Только

x

y

z

177

Даны две минимальные формы одной и той же булевой функции: МДНФ и МКНФ. Какие утверждения об их сложности (количестве букв/вхождений переменных) являются верными в общем случае?

Отметьте все верные варианты

Для любой булевой функции количество букв в МДНФ строго равно количеству букв в МКНФ. Существуют функции, для которых МДНФ содержит меньше букв, чем МКНФ. Существуют функции, для которых МКНФ содержит меньше букв, чем МДНФ. Если функция самодвойственна, то её МДНФ и МКНФ всегда совпадают по количеству букв.

178

Рассмотрим булево уравнение $X \land Y = 1$ , где $X$ и $Y$ — неизвестные булевы функции от $n$ переменных. Какие утверждения о его решениях являются истинными?

Отметьте все верные варианты

Уравнение имеет бесконечное множество решений. Уравнение имеет ровно одно решение. Решением является только пара тождественных констант:

X \equiv 1

Y \equiv 1

. Уравнение несовместно (не имеет решений).

179

Задано булево уравнение $X \oplus f(A,B) = g(A,B)$ , где $X$ — неизвестная функция. Какое логическое выражение описывает решение этого уравнения относительно $X$ ?

Отметьте все верные варианты

X = f(A,B) \leftrightarrow g(A,B)

Уравнение не всегда имеет решение.

X = f(A,B) \oplus g(A,B)

X = f(A,B) \lor g(A,B)

180

Булево уравнение задано в виде $X \land f(A,B) = g(A,B)$ , где $X$ — неизвестная функция. Какое условие является необходимым и достаточным для разрешимости (наличия хотя бы одного решения) этого уравнения?

Отметьте все верные варианты

На тех наборах, где

f(A,B) = 1

, функция

g(A,B)

должна быть равна 1. На тех наборах, где

f(A,B) = 0

, функция

g(A,B)

также должна быть равна 0.

f(A,B)

g(A,B)

должны быть ортогональны (

f \land g = 0

). Функция

g(A,B)

должна быть тождественным нулём.

181

Решается система булевых уравнений. При переходе к изображающим числам (векторам значений), уравнения сводятся к побитовым операциям над векторами. Если вектор $X = (x_1, x_2, x_3, x_4)$ , а вектор $A = (1, 0, 1, 0)$ и уравнение имеет вид $X \lor A = (1, 1, 1, 0)$ , сколько решений имеет данное векторное уравнение?

Отметьте все верные варианты

4 2 8 1

182

Функция $f(x, y, z)$ является симметрической. Известно, что $f(1, 0, 0) = 1$ и $f(1, 1, 1) = 0$ . Какие из следующих утверждений о значениях функции на других наборах гарантированно истинны?

Отметьте все верные варианты

f(0, 0, 0) = 0

f(1, 1, 0) = 0

f(0, 0, 1) = 1

f(0, 1, 0) = 1

183

Какие параметры полностью и однозначно определяют поведение любой пороговой булевой функции?

Отметьте все верные варианты

Множество рабочих (a-) чисел. Вещественные или целые веса аргументов

w_1, w_2, \dots, w_n

. Величина порога

T

. Структура полинома Жегалкина.

184

Булева функция $f(A, B, C)$ является мажоритарной (равна 1, если большинство аргументов равны 1). Какие из перечисленных свойств характерны для этой функции?

Отметьте все верные варианты

Она является симметрической функцией. Она является пороговой функцией. Она сохраняет константы 0 и 1. Она самодвойственна.

185

Рассматривается множество всех булевых функций от $n$ переменных. Выберите верные соотношения между классами симметрических ( $S_{ym}$ ), пороговых ( $T_{hr}$ ) и монотонных ( $M$ ) функций.

Отметьте все верные варианты

Любая симметрическая функция является пороговой. Функция сложения по модулю 2 (XOR) является симметрической, но не является пороговой. Любая пороговая функция является монотонной (при условии неотрицательности весов). Мажоритарная функция принадлежит пересечению всех трёх классов:

S_{ym} \cap T_{hr} \cap M

186

Как в булевом дифференциальном исчислении определяется производная функции $f(x, y)$ по переменной $x$ (обозначается $\frac{\partial f}{\partial x}$ )?

Отметьте все верные варианты

f(1, y) \lor f(0, y)

f(1, y) \oplus f(0, y)

f(x, y) \oplus f(\overline{x}, y)

\overline{f(1, y)} \land f(0, y)

187

Вычислите булеву производную $\frac{\partial f}{\partial x}$ для функции дизъюнкции $f(x, y) = x \lor y$ . Какие выводы можно сделать из полученного результата?

Отметьте все верные варианты

\frac{\partial f}{\partial x} = y

. Функция чувствительна к изменению

x

только если

y=1

\frac{\partial f}{\partial x} = \overline{y}

. Функция чувствительна к изменению

x

только если

y=0

. Если

y=1

, изменение

x

не влияет на результат (маскирование сигнала).

\frac{\partial f}{\partial x} = 1

. Функция всегда чувствительна к изменению

x

188

Что представляет собой ряд Тейлора-Маклорена в применении к булевым функциям (разложение функции в окрестности нулевого набора)?

Отметьте все верные варианты

Совершенную дизъюнктивную нормальную форму (СДНФ). Полином Жегалкина (алгебраическую нормальную форму). Разложение Шеннона по всем переменным. Карту Карно.

189

При каком обязательном условии существует неопределённый булев интеграл $\int f(X) dx$ от функции $f(X)$ ?

Отметьте все верные варианты

Булева производная подынтегральной функции по переменной интегрирования должна быть равна нулю:

\frac{\partial f}{\partial x} = 0

. Подынтегральная функция

f(X)

не должна зависеть от переменной

x

. Функция

f(X)

должна быть тождественной константой. Функция

f(X)

должна быть симметрической.

190

В теории конечных автоматов, чем принципиально отличается автомат Мили от автомата Мура?

Отметьте все верные варианты

Автомат Мили является синхронным (тактируемым), а автомат Мура — асинхронным. Автомат Мура может быть реализован только на T-триггерах. В автомате Мили функция выходов привязана к переходам (дугам графа), а в автомате Мура — к состояниям (вершинам графа). В автомате Мура выходной сигнал зависит только от текущего состояния памяти, а в автомате Мили — от текущего состояния памяти и от текущего входного сигнала.

191

Выберите характеристики, справедливые для универсального JK-триггера.

Отметьте все верные варианты

Комбинация

J=1, K=1

является запрещённой и ведёт к непредсказуемому состоянию. При подаче

J=1, K=1

состояние триггера инвертируется (режим T-триггера). При подаче

J=1, K=0

триггер устанавливается в состояние 1. При подаче

J=0, K=1

триггер сбрасывается в состояние 0.

192

При синтезе синхронного автомата (например, счётчика) на базе D-триггеров, как строится функция возбуждения $D_i$ для $i$ -го триггера?

Отметьте все верные варианты

D_i

зависит только от тактового сигнала CLK.

D_i = Q_i(t) \oplus Q_i(t+1)

Функция возбуждения

D_i

в точности совпадает с требуемым следующим состоянием триггера

Q_i(t+1)

D_i = 1

, если состояние должно измениться, и

0

, если должно сохраниться.

193

Что означает свойство «гонок» (состязаний) в асинхронных конечных автоматах?

Отметьте все верные варианты

Ситуация, когда два или более элемента памяти (триггера) должны одновременно изменить своё состояние при изменении входного сигнала. Непредсказуемый переход автомата в неверное состояние из-за разброса задержек срабатывания логических элементов. Использование избыточного кодирования состояний (кода Грея) для устранения критических переходов. Увеличение тактовой частоты свыше допустимого предела.

194

Бинарное отношение $R$ задано на множестве целых чисел как $aRb \iff a \le b$ . Какими свойствами обладает это отношение?

Отметьте все верные варианты

Транзитивность Симметричность Антисимметричность Рефлексивность

195

Согласно теореме Кантора, каково соотношение между мощностью любого множества $A$ (даже бесконечного) и мощностью его булеана $B(A)$ (множества всех подмножеств)?

Отметьте все верные варианты

Мощность булеана

B(A)

равна

2^{|A|}

|A| = |B(A)|

для бесконечных множеств.

|A| < |B(A)|

Булеан счётного множества является счётным.

196

Требуется составить расписание экзаменов. Есть 5 различных предметов и 5 дней. Каждый день проводится ровно один экзамен. По какой формуле комбинаторики вычисляется количество возможных вариантов расписания?

Отметьте все верные варианты

Перестановки без повторений:

P_n = n!

Сочетания без повторений:

C_n^k

Размещения с повторениями:

n^k

Факториал числа 5:

5!

197

В теории графов, при каком необходимом и достаточном условии в связном неориентированном мультиграфе существует Эйлеров цикл (замкнутый маршрут, проходящий через каждое ребро ровно один раз)?

Отметьте все верные варианты

Степень каждой вершины графа должна быть чётной. Граф не должен содержать циклов нечётной длины. Граф должен быть деревом. Граф должен быть полным (каждая вершина соединена с каждой).

198

Булева функция $f(v,w,x,y,z)$ задана картой Карно для пяти переменных, состоящей из двух матриц $4\times4$ (левая для $v=0$ , правая для $v=1$ , строки маркированы $wx$ , столбцы $yz$ ). Известно, что единицы расположены в клетках, соответствующих десятичным минтермам $m_0, m_2, m_8, m_{10}, m_{16}, m_{18}, m_{24}, m_{26}$ . Проанализируйте топологию склеивания и выберите все математически строгие (верные) утверждения.

Отметьте все верные варианты

Данные 8 единиц невозможно объединить в одну область (простую импликанту), так как они физически изолированы в разных углах двух матриц. С учётом многомерного «соседства» краёв тора и симметрии матриц

v=0

v=1

, эти единицы образуют единую область склеивания ранга 2 (исключаются 3 переменные). Данная функция является линейной и её полином Жегалкина имеет вид

1 \oplus x \oplus z

. Минимальная ДНФ данной функции состоит из единственной простой импликанты

\overline{x} \land \overline{z}

. Переменные

v

w

y

в данной функции являются существенными, так как именно они задают координаты склеенного блока.

199

Частично определённая (неполностью определённая) булева функция $f(A,B,C,D)$ равна 1 на наборах $N_1 = \{1, 3, 5, 7\}$ и имеет безразличные состояния (запрещённые наборы) на $N_X = \{0, 2, 8, 10, 12, 14\}$ . На остальных наборах функция равна 0. Оцените возможные варианты доопределения наборов из $N_X$ для получения минимальных ДНФ и КНФ. Выберите все истинные утверждения.

Отметьте все верные варианты

При оптимальном доопределении МДНФ равна

\overline{A} \land D

; для этого все наборы из

N_X

можно доопределить нулями. Оптимальным для МДНФ является доопределение наборов

0

2

единицами, а

8, 10, 12, 14

— нулями. В этом случае МДНФ примет вид

\overline{A} \land \overline{B}

. Если доопределить все наборы из

N_X

единицами, полученная МДНФ будет короче, чем если доопределить их нулями. Оптимальное доопределение для МДНФ требует, чтобы наборы

0

2

были доопределены как 1, образуя блок из 8 ячеек

\overline{A}

200

При минимизации функции методом Квайна–Мак-Класки на этапе составления импликантной матрицы Петрика получена следующая конъюнкция дизъюнкций: $F = (P_1 \lor P_2) \land (P_2 \lor P_3) \land (P_1 \lor P_4) \land P_3$ . Какие из приведённых утверждений о тупиковых и минимальных ДНФ являются аналитически верными?

Отметьте все верные варианты

После раскрытия скобок и применения законов поглощения останутся ровно три тупиковые ДНФ. Выражение минимизируется до

(P_1 \land P_3) \lor (P_2 \land P_3 \land P_4)

. Одной из тупиковых ДНФ является сумма импликант

P_1 \lor P_3

. Импликанта

P_3

является ядровой (обязательной) и войдёт в любую тупиковую ДНФ. Функция имеет ровно одну минимальную ДНФ (при условии равной цены всех импликант).

201

Рассматривается система булевых уравнений относительно неизвестной функции $X(A,B)$ : $X \land (A \to B) = A \land B$ $X \lor (A \oplus B) = 1$ Какие утверждения о разрешимости и корнях этой системы являются истинными?

Отметьте все верные варианты

Единственным решением системы является функция эквивалентности

X = A \leftrightarrow B

. Второе уравнение требует, чтобы функция

X

обязательно была равна 1 на наборах, где

A = B

. Функция

X = A \land B

является решением обоих уравнений. Система не имеет ни одного общего решения (несовместна). Первое уравнение имеет множество решений, среди которых есть

X = B

202

Для функции $f(x,y,z)$ задано её разложение по теореме Шеннона: $f(x,y,z) = \overline{x} \land (y \leftrightarrow z) \lor x \land (y \downarrow z)$ . Какими фундаментальными свойствами обладает данная функция? (где $\downarrow$ — стрелка Пирса, $\leftrightarrow$ — эквивалентность).

Отметьте все верные варианты

Функция не монотонна (не принадлежит классу

M

). Функция является линейной и принадлежит классу Поста

L

. Полином Жегалкина этой функции содержит ровно одно слагаемое степени 3 (конъюнкцию

xyz

). Данная функция является самодвойственной (класс

S

). Функция принадлежит классу функций, сохраняющих нуль (

T_0

203

Оценивается функциональная полнота системы функций $S = \{f_1(x,y) = x \land \overline{y}, f_2(x,y) = x \oplus y\}$ . Какие из приведённых утверждений, использующих критерий Поста, являются строгими и безошибочными?

Отметьте все верные варианты

Ни одна из функций системы не принадлежит классу линейных функций

L

, что гарантирует выход из этого класса. Система полна, так как

f_1 \notin T_1, S, M, L

, а

f_2 \notin T_1, S, M

, и совместно они не принадлежат классу

T_0

. Функция

f_1

не сохраняет константы 0 и 1, поэтому она выводит систему из классов

T_0

T_1

. Функция

f_2

является самодвойственной, но

f_1

не самодвойственна, поэтому система не содержится в классе

S

. Система не является функционально полной.

204

Булева производная второго порядка (смешанная производная) определяется как $\frac{\partial^2 f}{\partial x \partial y} = \frac{\partial}{\partial x} \left( \frac{\partial f}{\partial y} \right)$ . Вычислите смешанную производную для функции мажоритарности 3 переменных $f(x,y,z) = xy \lor xz \lor yz$ . Какие утверждения об этой производной являются истинными?

Отметьте все верные варианты

\frac{\partial^2 f}{\partial x \partial y} = 1 \oplus z

. Смешанная производная тождественно равна константе

0

, так как функция симметрична.

\frac{\partial^2 f}{\partial x \partial y} = 1

, что означает абсолютную чувствительность функции к одновременному изменению

x

y

\frac{\partial^2 f}{\partial x \partial y} = \frac{\partial^2 f}{\partial y \partial x}

, так как порядок дифференцирования в булевой алгебре не имеет значения. Значение производной равно

\overline{z}

, что означает зависимость переключения от третьей переменной.

205

Булева функция задана полиномом Жегалкина: $f(x,y,z) = 1 \oplus x \oplus y \oplus z \oplus xy \oplus xz \oplus yz \oplus xyz$ . Выполните преобразование этой алгебраической нормальной формы (АНФ) к дизъюнктивной (ДНФ) или конъюнктивной (КНФ) форме. Какие из следующих выражений тождественно равны $f(x,y,z)$ ?

Отметьте все верные варианты

\overline{x} \land \overline{y} \land \overline{z}

x \downarrow y \downarrow z

(обобщённая стрелка Пирса от трёх переменных)

\overline{x} \lor \overline{y} \lor \overline{z}

\overline{x \lor y \lor z}

x \land y \land z

206

Рассматриваются симметрические булевы функции от трёх переменных. Множество всех таких функций образует замкнутую алгебру относительно операций $\lor, \land, \neg$ . Известны рабочие числа (a-числа) для двух функций: $f_1 = S_{\{0, 2\}}$ и $f_2 = S_{\{1, 2\}}$ . Найдите рабочие числа для сложной функции $F = \overline{f_1 \land \overline{f_2}} \lor (f_1 \oplus f_2)$ . Выберите верное утверждение о функции $F$ .

Отметьте все верные варианты

Функция

F

тождественно равна 1 на всех наборах, её рабочие числа

\{0, 1, 2, 3\}

. Функция

F

равна 0 только на наборах с весом 2. Функция

F

является мажоритарной функцией. Функция

F

совпадает с функцией

S_{\{0, 1, 3\}}

. Рабочие числа функции

F

— это

\{1, 3\}

207

Булева функция задана как пороговая $f(x,y,z) = [w_1, w_2, w_3 ; T]$ с весами $w_1 = 2, w_2 = -1, w_3 = 1$ и порогом $T = 1$ . Какие из следующих утверждений о свойствах этой функции и её эквивалентных представлениях математически точны?

Отметьте все верные варианты

f

монотонна. Минимальная ДНФ:

f = x \lor \overline{y} z

f = y \to (x \lor z)

. Функция

f

— константа.

f

равна 1 ровно на 5 наборах из 8.

208

Симметрическая функция задана как $f(x,y,z) = S_{1,3}(x,y,z)$ . Исследуется её представление в различных формах и принадлежность классам Поста. Выберите все верные утверждения.

Отметьте все верные варианты

f \in L

, но

f \notin S

f \in T_0 \cap T_1

. Полином Жегалкина

f

имеет вид

x \oplus y \oplus z

f \in M

(монотонна).

f \in S

(самодвойственна).

209

Рассматривается система булевых функций $S = \{f_1 = x \downarrow y,\; f_2 = x \to y,\; f_3 = x \lor y\}$ (где $\downarrow$ — стрелка Пирса). Используя критерий Поста, выберите все верные утверждения.

Отметьте все верные варианты

Система полна, так как

f_1 = x \downarrow y

не принадлежит ни одному из пяти предполных классов

T_0, T_1, S, M, L

. Система неполна, так как

f_3 = x \lor y

монотонна и сохраняет 0 и 1.

\{f_1\}

— минимальный базис, поскольку одна функция

f_1

уже образует полную систему.

f_2 = x \to y

является самодвойственной функцией. Полином Жегалкина

f_2 = x \to y

имеет вид

1 \oplus x \oplus xy

210

Даны две системы булевых функций, представленные $\omega$ -наборами в базисе $(x,y)$ :

Система $S_1$ : $\omega = (0, 1, 2, 3)$ .
Система $S_2$ : $\omega = (0, 1, 1, 2)$ .

Выберите все верные утверждения.

Отметьте все верные варианты

В системе

S_1

первая функция

f_1 = x

, вторая

f_2 = y

\omega

-набор

(0,1,2,3)

описывает независимую систему. Системы

S_1

S_2

имеют одинаковой мощности замыкания. В системе

S_2

первая функция

f_1 = x

, вторая

f_2 = \lnot y

\omega

-набор

(0,1,1,2)

описывает независимую систему.

211

К функции $f(x,y,z) = x \oplus y \oplus z$ применяются теоремы разложения Шеннона для ДНФ и КНФ. Выберите все верные утверждения.

Отметьте все верные варианты

Теорема разложения для КНФ:

f = [x + f(0,y,z)] \cdot [\bar{x} + f(1,y,z)]

. Эквивалентная форма для ДНФ:

f = x \cdot f(1,y,z) \oplus \bar{x} \cdot f(0,y,z)

(сложение по модулю 2), так как слагаемые ортогональны. Разложение

f

по

y

даёт

y \cdot (1 \oplus x \oplus z) \oplus \bar{y} \cdot (x \oplus z)

. После последовательного разложения по всем переменным для ДНФ получаем СКНФ. Теорема разложения для ДНФ:

f = x \cdot f(1,y,z) + \bar{x} \cdot f(0,y,z)

212

Для функции $f(x,y,z) = x \oplus y \oplus z \oplus xyz$ вычисляются булевы производные. Выберите все верные утверждения.

Отметьте все верные варианты

\dfrac{\partial^3 f}{\partial x \partial y \partial z} = 0

. Смешанная производная

\dfrac{\partial^2 f}{\partial x \partial y} = \dfrac{\partial^2 f}{\partial y \partial x}

\dfrac{\partial f}{\partial y} = y

\dfrac{\partial f}{\partial z} = 1 \oplus xy

\dfrac{\partial f}{\partial x} = 1 \oplus yz

213

Булева функция $f(x,y,z)$ задана изображающим числом $\#f = 10010110$ (старший разряд соответствует $x$ ). Выберите все верные утверждения о её свойствах и формах представления.

Отметьте все верные варианты

Минимальная ДНФ функции

f

содержит ровно 4 простые импликанты, каждая из которых является минтермом. Функция

f

совпадает с

1 \oplus x \oplus y \oplus z

. Полином Жегалкина функции

f

содержит слагаемое

xyz

f \in S \cap L

f \in T_0 \cap T_1

Нашли ошибку или неточность в задании, ключе или пояснении? Напишите номер задания и что не так. Необязательно