Алгебра логики

ЗАДАЧА · 3 БАЛЛА

1. Восстановление функции по условию

Для трёх логических переменных $A$, $B$ и $C$ функция принимает значение 1 тогда и только тогда, когда истинны ровно два из трёх высказываний. Запишите функцию через операции НЕ, И и ИЛИ в виде дизъюнкции конъюнкций.

8 СТРОК · 3 БАЛЛА

2. Таблица для импликации и эквивалентности

Заполните пропуски в таблице истинности функции $F=(A\to B)\leftrightarrow (B\to A)$. В каждой строке вычисляйте сначала значения двух импликаций, затем эквивалентность.

5 УТВЕРЖДЕНИЙ · 2 БАЛЛА

3. Свойства логических операций

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

1. Импликация $A\to B$ ложна только при $A=1$ и $B=0$.ИстинаЛожь
2. Выражение $A\vee \neg A$ ложно при обоих значениях переменной $A$.ИстинаЛожь
3. Операция эквивалентности истинна, если значения её операндов совпадают.ИстинаЛожь
4. Выражение $A\cdot 0$ имеет значение 1 при $A=1$.ИстинаЛожь
5. Для любых значений $A$ и $B$ выполняется $A\vee B=B\vee A$.ИстинаЛожь

ЗАДАЧА · 3 БАЛЛА

4. Упрощение логического выражения

Упростите выражение $F=(A\vee B)\cdot (A\vee \neg B)$ и запишите результат, используя минимальное число операций. Приведите основные шаги преобразования.

8 СТРОК · 3 БАЛЛА

5. Проверка равносильности формул

Заполните пропуски и определите, равносильны ли выражения $F=\neg (A\cdot B)$ и $G=\neg A\vee \neg B$. В последнем столбце укажите результат сравнения значений функций.

5 УТВЕРЖДЕНИЙ · 2 БАЛЛА

6. Чтение таблиц истинности

Определите истинность утверждений по правилам построения таблиц истинности. Не выполняйте преобразования, если утверждение можно проверить непосредственно по определению операции.

1. Для функции от четырёх переменных таблица истинности содержит 16 строк наборов значений.ИстинаЛожь
2. В таблице истинности функции от трёх переменных достаточно проверить 3 набора значений.ИстинаЛожь
3. Если функция принимает значение 1 на каждом наборе, она является тождественно истинной.ИстинаЛожь
4. У двух разных логических формул не может быть одинаковой таблицы истинности.ИстинаЛожь
5. Столбец сложного выражения строят после вычисления его подвыражений.ИстинаЛожь

ЗАДАЧА · 3 БАЛЛА

7. Анализ условия с ограничениями

Высказывания $A$, $B$ и $C$ означают: $A$ — сервер доступен, $B$ — включено резервное питание, $C$ — есть подключение к сети. Система выдаёт предупреждение, если сервер недоступен или одновременно отсутствуют резервное питание и подключение к сети. Запишите логическую функцию предупреждения и найдите её значение при $A=1$, $B=0$, $C=0$.

8 СТРОК · 3 БАЛЛА

8. Функция большинства

Заполните таблицу для функции $F=(A\cdot B)\vee (A\cdot C)\vee (B\cdot C)$. Эта функция принимает значение 1, если истинны хотя бы два из трёх высказываний.

5 УТВЕРЖДЕНИЙ · 2 БАЛЛА

9. Равносильные преобразования

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

1. Выражения $A\vee (A\cdot B)$ и $A$ равносильны.ИстинаЛожь
2. Выражения $A\cdot (A\vee B)$ и $A\vee B$ равносильны для любых $A$ и $B$.ИстинаЛожь
3. Выражение $\neg \neg A$ равносильно $A$.ИстинаЛожь
4. Выражение $A\vee (B\cdot C)$ всегда равносильно $(A\vee B)\cdot C$.ИстинаЛожь
5. Выражение $(A\vee B)\cdot (\neg A\vee B)$ равносильно $B$.ИстинаЛожь

ЗАДАЧА · 4 БАЛЛА

10. Построение СДНФ по таблице

Логическая функция трёх переменных принимает значение 1 только на наборах $(A,B,C)=(0,1,0)$, $(1,0,1)$ и $(1,1,1)$. Запишите её совершенную дизъюнктивную нормальную форму и укажите значение функции на наборе $(1,1,0)$.