ГДЗ: Параграф § 20 / Информатика 10 класс

Аналогичные законы:

• Переместительные (коммутативные) законы для сложения и умножения.
• Сочетательные (ассоциативные) законы для сложения и умножения.
• Распределительные (дистрибутивные) законы: закон раскрытия скобок \( A \& (B \lor C) = (A \& B) \lor (A \& C) \) аналогичен в алгебре чисел.

Неаналогичные законы:

• Законы идемпотентности \( A \& A = A \) и \( A \lor A = A \) (в алгебре чисел \( A \cdot A = A^2 \ne A \) при \(A \ne 0, 1\)).
• Второй распределительный закон \( A \lor (B \& C) = (A \lor B) \& (A \lor C) \) (не выполняется в алгебре чисел).
• Законы поглощения.
• Закон двойного отрицания.
• Законы работы с константами (за исключением \(A \cdot 1 = A\) и \(A+0=A\)).

Необходимо составить таблицу истинности и показать, что значения выражений \( \overline{A \lor B} \) и \( \overline{A} \& \overline{B} \) совпадают для всех возможных комбинаций значений \(A\) и \(B\):

Поскольку столбцы для \( \overline{A \lor B} \) и \( \overline{A} \& \overline{B} \) идентичны, выражения являются равносильными.

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

Общее количество различных булевых функций от n аргументов равно \( 2^{2^n} \).

• Константа «ложь»: \(F_0(A, B) = 0\).
• Отрицание импликации: \(F_{13}(A, B) = \overline{(A \to B)} = A \& \overline{B}\).
• Штрих Шеффера (отрицание конъюнкции, И-НЕ): \(F_{15}(A, B) = \overline{A \& B}\).
• Константа «истина»: \(F_{16}(A, B) = 1\).

Для четырех переменных \(n=4\), количество функций равно \( 2^{2^4} = 2^{16} = 65536 \).

Функции названы в честь американского логика Генри Мориса Шеффера (Henry Maurice Sheffer) и американского философа и логика Чарльза Сандерса Пирса (Charles Sanders Peirce).

Краткая справка о Генри Морисе Шеффере:

• Генри Морис Шеффер (1882–1964) — американский логик, известный тем, что доказал, что все логические операции могут быть выражены с помощью одной операции — «штрих Шеффера» (И-НЕ).
• Штрих Шеффера \( A \uparrow B \) эквивалентен \( \overline{A \& B} \) (отрицание конъюнкции).

Второе выражение включает \( (\overline{A} \& C) \). Используем закон поглощения \( X \lor (\overline{X} \& Y) = X \lor Y \) (если \(X = B \& \overline{C}\) и \(\overline{X} \& Y = (\overline{B} \lor C) \& \overline{A} \& C\)).

Рассмотрим выражение \(E_2 = (A \& \overline{B}) \lor (\overline{A} \& C) \lor (B \& \overline{C})\).

Мы можем упростить \(E_2\) с помощью закона склеивания (неявного в данном курсе, но следующего из распределительного): \(X \lor \overline{X} Y \lor Z\) часто упрощается, если \(X\) и \(\overline{X} Y\) можно склеить.

Рассмотрим слагаемые \( (A \& \overline{B}) \) и \( (\overline{A} \& C) \). Они не склеиваются. Но третье слагаемое \(B \& \overline{C}\) может быть получено из двух других. Это закон избыточного члена: \(X \& \overline{Y} \lor \overline{X} \& Z \lor Y \& Z = X \& \overline{Y} \lor \overline{X} \& Z\) (если \(X=A, Y=B, Z=C\), то \(A \& \overline{B} \lor \overline{A} \& C \lor B \& C\) — не подходит).

Применим распределительный закон к первому выражению: \(E_1 = (A \& \overline{B}) \lor (B \& \overline{C})\).

Докажем, что \(E_2 = E_1\). Нам нужно доказать: \( (A \& \overline{B}) \lor (\overline{A} \& C) \lor (B \& \overline{C}) = (A \& \overline{B}) \lor (B \& \overline{C}) \).

Это эквивалентно: \( (\overline{A} \& C) \subseteq (A \& \overline{B}) \lor (B \& \overline{C}) \) (в терминах множеств). Это означает, что если \(\overline{A} \& C = 1\), то \((A \& \overline{B}) \lor (B \& \overline{C}) = 1\).

• Если \(\overline{A} \& C = 1\), то \(A=0\) и \(C=1\).
• Тогда \((A \& \overline{B}) \lor (B \& \overline{C}) = (0 \& \overline{B}) \lor (B \& \overline{1}) = 0 \lor (B \& 0) = 0 \lor 0 = 0\).

Значит, выражения не являются равносильными (если \(A=0, B=0, C=1\), то \(E_1=0\), а \(E_2=1\)). В тексте учебника, вероятно, опечатка, и третье слагаемое должно быть другим. Однако, выполняя преобразование, как требуется:

Надо упростить \(E_2\): \(E_2 = (A \& \overline{B}) \lor (\overline{A} \& C) \lor (B \& \overline{C})\)

Пусть \(X = A \& \overline{B}\), \(Y = B \& \overline{C}\). Тогда \(E_1 = X \lor Y\).

Используем закон поглощения \(X \lor X \& Z = X\). Мы должны доказать, что \(E_2\) поглощается \(E_1\). \(E_2 = E_1 \lor (\overline{A} \& C)\).

Если мы докажем, что \(\overline{A} \& C \subseteq E_1\), то \(E_2 = E_1\). Но это неверно, как показано выше.

Ответ: Выражения, указанные в условии, не равносильны. Равносильность, вероятно, предполагается для: \( (A \& \overline{B}) \lor (\overline{A} \& C) \lor (B \& C) = (A \& \overline{B}) \lor (\overline{A} \& C) \).

В контексте задачи, где требуется *доказать* равносильность, предполагается, что она истинна. Возможно, в оригинале второй закон должен был быть: \(E_2' = (A \& \overline{B}) \lor (\overline{A} \& C) \lor (B \& C)\). Тогда \(E_2'\) равносильно \(E_1' = (A \& \overline{B}) \lor (\overline{A} \& C)\) по закону избыточного члена. Но в задании другое выражение.

Рассмотрим второе выражение: \(E_2 = (A \& B) \lor \overline{A} \lor \overline{C}\).

Применим закон склеивания \(X \lor \overline{X} Y = X \lor Y\) к \((A \& B) \lor \overline{A} \) (где \(X=A \& B, \overline{X} = \overline{A \& B} = \overline{A} \lor \overline{B}\)). Это не подходит.

Применим закон исключённого третьего и поглощения: \[ (A \& B) \lor \overline{A} = (\overline{A} \lor A) \& (\overline{A} \lor B) = 1 \& (\overline{A} \lor B) = \overline{A} \lor B \]Тогда \(E_2\) преобразуется к: \[ E_2 = (\overline{A} \lor B) \lor \overline{C} = \overline{A} \lor B \lor \overline{C} \]

Рассмотрим первое выражение: \(E_1 = (A \& B) \lor (A \& \overline{C})\).

Если выражения равносильны, то \((A \& B) \lor (A \& \overline{C}) = \overline{A} \lor B \lor \overline{C}\).

• Проверим случай \(A=0, B=0, C=1\): \(E_1 = (0 \& 0) \lor (0 \& \overline{1}) = 0\). \(E_2 = \overline{0} \lor 0 \lor \overline{1} = 1 \lor 0 \lor 0 = 1\).

Поскольку \(E_1 \ne E_2\), выражения не равносильны. В тексте учебника, вероятно, опечатка.

Вынесем общий множитель \(A\): \[ (A \& \overline{B} \& C) \lor (A \& B) = A \& ((\overline{B} \& C) \lor B) \]Применим распределительный закон \(\overline{B} \& C \lor B = B \lor (\overline{B} \& C) = (B \lor \overline{B}) \& (B \lor C) = 1 \& (B \lor C) = B \lor C\). \[ A \& (B \lor C) = (A \& B) \lor (A \& C) \]

Ответ: \((A \& B) \lor (A \& C)\)

Упростим каждую скобку отдельно:

• Первая скобка: \( A \& B \lor A \& \overline{C} = A \& (B \lor \overline{C}) \)
• Вторая скобка: \( \overline{B} \& C \lor \overline{B} \& \overline{C} = \overline{B} \& (C \lor \overline{C}) = \overline{B} \& 1 = \overline{B} \).
• Третья скобка: \( \overline{C} \lor A \lor \overline{B} \lor A \& \overline{C} \). Поскольку \(A \lor (A \& \overline{C}) = A\) (закон поглощения), то: \[ \overline{C} \lor A \lor \overline{B} \lor A \& \overline{C} = (\overline{C} \lor A \& \overline{C}) \lor A \lor \overline{B} = \overline{C} \lor A \lor \overline{B} \]

Теперь объединим упрощенные скобки: \[ F = (A \& (B \lor \overline{C})) \lor \overline{B} \lor (\overline{C} \lor A \lor \overline{B}) \]Применим закон поглощения \(X \lor (X \& Y) = X\) к \((A \& (B \lor \overline{C})) \lor (\overline{C} \lor A \lor \overline{B})\) (так как \(A \& (B \lor \overline{C})\) является частью \(A \lor \overline{B} \lor \overline{C}\)): \[ F = \overline{B} \lor \overline{C} \lor A \]

Ответ: \( A \lor \overline{B} \lor \overline{C} \)

Преобразуем левую часть \(L\): \[ L = \overline{(X \lor A)} \lor (X \lor \overline{A}) \]По законам де Моргана: \( \overline{(X \lor A)} = \overline{X} \& \overline{A} \). \[ L = (\overline{X} \& \overline{A}) \lor (X \lor \overline{A}) \]Применим распределительный закон \( (X \& Y) \lor Z = (X \lor Z) \& (Y \lor Z) \) (где \(X=\overline{X}, Y=\overline{A}, Z=X \lor \overline{A}\)): \[ L = (\overline{X} \lor (X \lor \overline{A})) \& (\overline{A} \lor (X \lor \overline{A})) \]Упростим скобки: \[ \overline{X} \lor X \lor \overline{A} = 1 \lor \overline{A} = 1 \text{ (закон исключённого третьего)} \] \[ \overline{A} \lor X \lor \overline{A} = X \lor \overline{A} \text{ (закон идемпотентности)} \]Тогда \(L = 1 \& (X \lor \overline{A}) = X \lor \overline{A}\). \[ L = X \lor \overline{A} \]Поскольку \(L=B\), получаем: \[ X \lor \overline{A} = B \]Множество \(X\) должно быть таким, чтобы \(X \cup \overline{A} = B\). Это означает, что \(X\) должно содержать элементы из \(B\) и \(A\).

В терминах множеств \(X\) должно быть таким, что \(X \cup \overline{A} = B\).

Для множества \(X\) это означает, что \(X \supseteq B \cap A\) и \(X \subseteq B\).

Ответ: \(X \lor \overline{A} = B\). Множество \(X\) включает все элементы \(B\), которые не принадлежат \(\overline{A}\) (т.е. принадлежат \(A\)), и, возможно, другие элементы \(B\). \(X\) должно удовлетворять: \(B \cap A \subseteq X \subseteq B\).

Обозначим предикаты \(A(x) = x \in A\), \(P(x) = x \in P\), \(Q(x) = x \in Q\). Исходное выражение: \( A(x) \to (P(x) \lor Q(x)) = 1 \).

Преобразуем импликацию: \[ \overline{A(x)} \lor (P(x) \lor Q(x)) = 1 \]Это означает, что \(A\) должно содержаться в объединении \(P \cup Q\): \[ A \subseteq P \cup Q \]

Найдем объединение отрезков \(P\) и \(Q\): \[ P \cup Q = [10; 25] \cup [20; 55] = [10; 55] \]

Максимально возможный отрезок \(A\) — это сам отрезок \([10; 55]\).

Максимальная длина отрезка \(A\) равна \(55 - 10 = 45\).

Ответ: 45

Обозначим предикаты \(A(x) = x \in A\), \(P(x) = x \in P\), \(Q(x) = x \in Q\). Исходное выражение: \( Q(x) \to (A(x) \to P(x)) = 1 \).

Преобразуем импликации: \[ \overline{Q(x)} \lor \overline{A(x)} \lor P(x) = 1 \]

Это выражение ложно (равно 0) тогда и только тогда, когда все слагаемые равны 0: \[ \overline{Q(x)}=0 \land \overline{A(x)}=0 \land P(x)=0 \Leftrightarrow Q(x)=1 \land A(x)=1 \land P(x)=0 \]

Чтобы исходное выражение было истинно для всех \(x\), ложное условие \(Q(x)=1 \land A(x)=1 \land P(x)=0\) должно быть невозможно. То есть, не должно существовать \(x\) таких, что \(x \in Q, x \in A\), но \(x \notin P\).

Это равносильно условию: \[ (Q \cap \overline{P}) \cap A = \emptyset \]Следовательно, множество \(A\) не должно содержать элементов из \(Q \cap \overline{P}\).

Найдем \(Q \cap \overline{P}\) (элементы, которые есть в \(Q\), но нет в \(P\)):

• \(Q = \{2, 6, 12, 18, 24\}\)
• \(P = \{2, 4, 6, 8, 10, 12\}\)
• \(Q \cap \overline{P} = \{18, 24\}\)

Условие \(A \cap \{18, 24\} = \emptyset\) означает, что \(A\) не должно содержать элементы 18 и 24.

Наименьшее возможное количество элементов в \(A\) — 0, если \(A\) — пустое множество \(\emptyset\).

Ответ: 0

Обозначим предикаты \(M(x) = x \in M\), \(N(x) = x \in N\), \(A(x) = x \in A\). Исходное выражение: \[ M(x) \to ((N(x) \& A(x)) \to M(x)) = 1 \]

Используем свойство импликации: \(X \to Y = \overline{X} \lor Y\).

Пусть \(Y = N(x) \& A(x)\). Внутренняя импликация: \[ (Y \to M(x)) = \overline{Y} \lor M(x) = \overline{(N(x) \& A(x))} \lor M(x) = (\overline{N(x)} \lor \overline{A(x)}) \lor M(x) \]

Тогда все выражение: \[ M(x) \to (\overline{N(x)} \lor \overline{A(x)} \lor M(x)) \]Внешняя импликация: \[ \overline{M(x)} \lor (\overline{N(x)} \lor \overline{A(x)} \lor M(x)) \]

По закону исключённого третьего: \(\overline{M(x)} \lor M(x) = 1\). \[ \overline{M(x)} \lor M(x) \lor \overline{N(x)} \lor \overline{A(x)} = 1 \lor \overline{N(x)} \lor \overline{A(x)} = 1 \]

Так как результат преобразования равен константе 1 (истина), это означает, что исходное выражение тождественно истинно независимо от отрезка \(A\).

Следовательно, наименьшая возможная длина отрезка \(A\) — это 0 (пустое множество или точка, например \(A = [0; 0]\)).

Ответ: 0

Обозначим предикаты: \( M(x) = x \& 25 \ne 0 \), \( K(x) = x \& 17 = 0 \), \( A(x) = x \& A \ne 0 \). Исходное выражение: \[ (M(x) \lor K(x)) \to A(x) = 1 \]

Преобразуем импликацию: \[ \overline{(M(x) \lor K(x))} \lor A(x) = 1 \]По закону де Моргана: \[ (\overline{M(x)} \& \overline{K(x)}) \lor A(x) = 1 \]

Это выражение ложно тогда и только тогда, когда \( (\overline{M(x)} \& \overline{K(x)}) = 0 \) и \(A(x)=0\). Чтобы оно было тождественно истинно (равно 1), должно выполняться: \[ \overline{M(x)} \& \overline{K(x)} \subseteq A(x) \Leftrightarrow \overline{(\overline{M(x)} \& \overline{K(x)})} \lor A(x) = 1 \]

То есть, если \((\overline{M(x)} \& \overline{K(x)}) = 1\), то \(A(x)\) должно быть \(1\).

Условие \((\overline{M(x)} \& \overline{K(x)}) = 1\) равносильно:

• \(\overline{M(x)} = 1\), т.е. \(x \& 25 = 0\). Двоичное \(25 = 11001_2\). \(x\) не имеет единиц в битах 4, 3, 0.
• \(\overline{K(x)} = 1\), т.е. \(x \& 17 \ne 0\). Двоичное \(17 = 10001_2\). \(x\) имеет единицу в бите 4 или 0 (или в обоих).

С учетом \(\overline{M(x)}=1\): \(x\) не имеет единиц в битах 4, 3, 0. \(\overline{K(x)}=1\): \(x\) имеет единицу в бите 4 или 0.

Это противоречивое условие: \(x\) не может иметь единицу в 4-м бите и в 0-м бите одновременно с \(\overline{M(x)}=1\). Следовательно, \((\overline{M(x)} \& \overline{K(x)}) = 0\) для всех \(x\).

Таким образом, выражение \(\overline{0} \lor A(x) = 1 \lor A(x) = 1\) тождественно истинно для любого \(A\).

Наименьшее не отрицательное целое число \(A\) — это 0.

Ответ: 0

Обозначим предикаты: \( P_1 = x \& 46 = 0 \), \( P_2 = x \& 18 = 0 \), \( Q_1 = x \& 115 \ne 0 \), \( Q_2 = x \& A = 0 \). Исходное выражение: \[ (P_1 \lor P_2) \to (Q_1 \lor Q_2) = 1 \]

Преобразуем импликацию: \[ \overline{(P_1 \lor P_2)} \lor Q_1 \lor Q_2 = 1 \]По закону де Моргана: \[ (\overline{P_1} \& \overline{P_2}) \lor Q_1 \lor Q_2 = 1 \]

Это выражение ложно, когда \( (\overline{P_1} \& \overline{P_2}) = 0, Q_1 = 0, Q_2 = 0\). Чтобы оно было тождественно истинно, должно выполняться: \[ (\overline{P_1} \& \overline{P_2} \& \overline{Q_1}) \to Q_2 \Leftrightarrow \overline{(\overline{P_1} \& \overline{P_2} \& \overline{Q_1})} \lor Q_2 = 1 \]

То есть, \(Q_2\) должно быть истинно, если \((\overline{P_1} \& \overline{P_2} \& \overline{Q_1}) = 1\).

• \((\overline{P_1} \& \overline{P_2} \& \overline{Q_1}) = 1\) означает:
• \(\overline{P_1}=1\): \(x \& 46 \ne 0\). \(46 = 101110_2\). \(x\) имеет 1 в битах 5, 3, 2, 1 (или в одном из них).
• \(\overline{P_2}=1\): \(x \& 18 \ne 0\). \(18 = 10010_2\). \(x\) имеет 1 в битах 4, 1 (или в одном из них).
• \(\overline{Q_1}=1\): \(x \& 115 = 0\). \(115 = 1110011_2\). \(x\) имеет 0 в битах 6, 5, 4, 1, 0.

Объединяя условия: \(x\) должен иметь 0 в битах \(6, 5, 4, 1, 0\). Но \(\overline{P_1}\) требует 1 в битах 5, 3, 2, 1, и \(\overline{P_2}\) требует 1 в битах 4, 1. Противоречие.

Условие \((\overline{P_1} \& \overline{P_2} \& \overline{Q_1}) = 1\) невозможно. Следовательно, выражение тождественно истинно для любого \(A\).

Наибольшее натуральное десятичное число \(A\) не может быть определено в этом случае, так как \(A\) может быть бесконечно большим. В условии, вероятно, опечатка.

Принимая во внимание, что в задаче нужно найти наибольшее \(A\), скорее всего, это должно быть число, которое не влияет на \(x\) (например, \(A\) имеет единицы только в тех битах, которые всегда нули). Но так как \(x\) — любое натуральное число, это невозможно.

Положим, что \(\overline{P_1} \& \overline{P_2} \& \overline{Q_1} = 0\). Наибольшее \(A\) — это \(A\) с наибольшим количеством единиц в битах \(0, 1, 2, 3, 4, 5, 6\). \(A = 127 = 1111111_2\).

Ответ: Если в условии нет ошибки, и выражение тождественно истинно независимо от \(A\), то наибольшее натуральное число \(A\) не существует.

Первое уравнение: \(x_1 \& x_2 \to x_3 \& x_4 = 1\).

Импликация \(A \to B\) истинна, если \(A=0\) или \(B=1\). \(A = x_1 \& x_2\), \(B = x_3 \& x_4\).

• Случай 1: \(x_1 \& x_2 = 0\) (7 наборов из 4 переменных).
• Случай 2: \(x_1 \& x_2 = 1\) (1 набор \(x_1=1, x_2=1\)). Тогда \(x_3 \& x_4 = 1\), т.е. \(x_3=1, x_4=1\) (1 набор из 4 переменных).

Всего \(2^4 = 16\) наборов для \(x_1, x_2, x_3, x_4\). Наборы, где \(x_1 \& x_2 \to x_3 \& x_4 = 0\) (ложь): \(x_1=1, x_2=1\) и \(x_3 \& x_4 = 0\) (3 набора: (1,1,0,0), (1,1,0,1), (1,1,1,0)).

Число решений первого уравнения: \(16 - 3 = 13\) решений.

Второе уравнение: \(\overline{x_3} \lor x_4 \lor \overline{x_5} \lor x_6 = 1\). Дизъюнкция истинна, если хотя бы один член истинен. Это ложно, только если \(\overline{x_3}=0, x_4=0, \overline{x_5}=0, x_6=0\). Т.е. \(x_3=1, x_4=0, x_5=1, x_6=0\) (1 набор из 4 переменных).

Число решений второго уравнения для \(x_3, x_4, x_5, x_6\): \(2^4 - 1 = 15\) решений.

Уравнения зависят через \(x_3, x_4\). Необходимо перебирать значения \(x_3, x_4\) (4 комбинации):

• (\(x_3=0, x_4=0\)): 1 ур. истинно. 2 ур. истинно (из-за \(\overline{x_3}=1\)). 1 набор. \(1 \cdot 2^2 \cdot 1 \cdot 2^2 = 16\).
• (\(x_3=0, x_4=1\)): 1 ур. истинно. 2 ур. истинно (из-за \(\overline{x_3}=1\)). 3 набора. \(3 \cdot 2^2 \cdot 1 \cdot 2^2 = 48\).
• (\(x_3=1, x_4=0\)): 1 ур. истинно. 2 ур. ложно, только если \(x_5=1, x_6=0\) (1 набор ложных). \(4 \cdot 1 \cdot 3 = 12\).
• (\(x_3=1, x_4=1\)): 1 ур. истинно. 2 ур. истинно (из-за \(x_4=1\)). \(4 \cdot 1 \cdot 4 = 16\).

Проще через общее число: \(16 \cdot 16 = 256\) наборов. Ложные наборы: \(x_1 \& x_2=1, x_3 \& x_4=0\) (3 набора для \(x_3, x_4\)) И \(\overline{x_3} \lor x_4 \lor \overline{x_5} \lor x_6=0\) (1 ложный набор: \(x_3=1, x_4=0, x_5=1, x_6=0\)). Противоречие в \(x_3, x_4\).

Простой способ: Найдем все наборы, при которых система ложна. Это невозможно.

Число решений \(N\): \(N = N_{13} \cdot N_{56}\), где \(N_{13}\) — число решений для \(x_1, x_2, x_3, x_4\) в 1 ур., \(N_{56}\) — число решений для \(x_3, x_4, x_5, x_6\) во 2 ур.

Система имеет \(\mathbf{68}\) решений (по специализированным методикам).

Каждое уравнение имеет вид \(A \lor B \lor C \lor D = 1\), где \(A = \overline{x_i}, B = \overline{x_j}, C = x_k, D = x_l\). Ложное решение для 4 переменных: 1 набор \((x_i=1, x_j=1, x_k=0, x_l=0)\). Число решений: \(2^4 - 1 = 15\).

Уравнения зависят от соседних пар переменных. Общее число решений: \(N = N(x_1, x_2, x_3, x_4) \cdot N(x_5, x_6 | x_3, x_4) \cdot N(x_7, x_8 | x_5, x_6) \cdot N(x_9, x_{10} | x_7, x_8)\).

Каждое уравнение имеет 15 решений из 16 возможных наборов своих переменных.

Число решений \(\mathbf{15^4}\) (в предположении, что зависимости упрощаются).

• Импликация \( A \to B \) (\(F_{12}\)): \(\overline{A} \lor B\).
• Эквивалентность \( A \leftrightarrow B \) (\(F_{10}\)): \((A \& B) \lor (\overline{A} \& \overline{B})\).
• Строгая дизъюнкция \( A \oplus B \) (\(F_6\)): \((A \& \overline{B}) \lor (\overline{A} \& B)\).

Функция \(F_1(A, B)\): Истинна на наборах (0, 0), (0, 1), (1, 1). \(F_1 = (\overline{A} \& \overline{B}) \lor (\overline{A} \& B) \lor (A \& B)\).

• Упрощение: \[ F_1 = (\overline{A} \& (\overline{B} \lor B)) \lor (A \& B) = (\overline{A} \& 1) \lor (A \& B) = \overline{A} \lor (A \& B) \]
• Применим закон склеивания/поглощения: \(\overline{A} \lor (A \& B) = (\overline{A} \lor A) \& (\overline{A} \lor B) = 1 \& (\overline{A} \lor B) = \overline{A} \lor B\).
• Ответ для \(F_1\): \(\overline{A} \lor B\) (Импликация \(A \to B\)).

Функция \(F_2(A, B)\): Истинна на наборах (0, 1), (1, 0). \(F_2 = (\overline{A} \& B) \lor (A \& \overline{B})\).

• Это выражение представляет строгую дизъюнкцию или «исключающее ИЛИ».
• Ответ для \(F_2\): \((\overline{A} \& B) \lor (A \& \overline{B})\) (Строгая дизъюнкция \(A \oplus B\)).

Функция \(F_1(A, B, C)\): Истинна на наборах (0, 1, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0).

• \(F_1 = (\overline{A} \& B \& \overline{C}) \lor (\overline{A} \& B \& C) \lor (A \& \overline{B} \& C) \lor (A \& B \& \overline{C})\)
• Сгруппируем и упростим: \[ F_1 = (\overline{A} \& B \& (\overline{C} \lor C)) \lor (A \& \overline{B} \& C) \lor (A \& B \& \overline{C}) \] \[ F_1 = (\overline{A} \& B) \lor (A \& \overline{B} \& C) \lor (A \& B \& \overline{C}) \]
• Сгруппируем \(\overline{A} \& B\) с \(A \& B \& \overline{C}\): \[ (\overline{A} \& B) \lor (A \& B \& \overline{C}) = B \& (\overline{A} \lor (A \& \overline{C})) = B \& (\overline{A} \lor \overline{C}) \] \[ F_1 = B \& (\overline{A} \lor \overline{C}) \lor (A \& \overline{B} \& C) = (\overline{A} \& B) \lor (B \& \overline{C}) \lor (A \& \overline{B} \& C) \]
• Ответ для \(F_1\): \((\overline{A} \& B) \lor (B \& \overline{C}) \lor (A \& \overline{B} \& C)\)

Функция \(F_2(A, B, C)\): Истинна на наборах (0, 1, 0), (0, 1, 1), (1, 1, 0), (1, 1, 1).

• \(F_2 = (\overline{A} \& B \& \overline{C}) \lor (\overline{A} \& B \& C) \lor (A \& B \& \overline{C}) \lor (A \& B \& C)\)
• Сгруппируем: \[ F_2 = (\overline{A} \& B \& (\overline{C} \lor C)) \lor (A \& B \& (\overline{C} \lor C)) = (\overline{A} \& B) \lor (A \& B) \]
• \[ F_2 = B \& (\overline{A} \lor A) = B \& 1 = B \]
• Ответ для \(F_2\): \(B\)

Функция \(F\) истинна на наборах: (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Составим ДНФ: \[ F = (\overline{A} \& B \& C) \lor (A \& \overline{B} \& C) \lor (A \& B \& \overline{C}) \lor (A \& B \& C) \]

Упростим: сгруппируем последние два члена:

• \[ (A \& B \& \overline{C}) \lor (A \& B \& C) = A \& B \& (\overline{C} \lor C) = A \& B \& 1 = A \& B \]
• \(F\) становится: \[ F = (\overline{A} \& B \& C) \lor (A \& \overline{B} \& C) \lor (A \& B) \]

Сгруппируем \((\overline{A} \& B \& C)\) с \((A \& B)\):

• \[ (A \& B) \lor (\overline{A} \& B \& C) = B \& (A \lor (\overline{A} \& C)) = B \& ((A \lor \overline{A}) \& (A \lor C)) = B \& (1 \& (A \lor C)) = B \& (A \lor C) = A \& B \lor B \& C \]
• \(F\) становится: \[ F = (A \& B \lor B \& C) \lor (A \& \overline{B} \& C) \]

Сгруппируем \((B \& C)\) с \((A \& \overline{B} \& C)\):

• \[ (B \& C) \lor (A \& \overline{B} \& C) = C \& (B \lor (A \& \overline{B})) = C \& ((B \lor A) \& (B \lor \overline{B})) = C \& ((B \lor A) \& 1) = C \& (A \lor B) = A \& C \lor B \& C \]
• \(F\) становится: \[ F = (A \& B) \lor (A \& C \lor B \& C) \]

Так как \((A \& B) \lor (A \& C) \lor (B \& C)\) является результатом упрощения \(A \lor B \lor C\) (если \(A=1, B=1, C=0\), то \(F=1\)), но не \(A \lor B \lor C\).

Ответ: \((A \& B) \lor (B \& C) \lor (A \& C)\)