Задание №2. Короткий конспект
Основные правила операций и короткий порядок решения: столбцы, пропуски, различие строк и запись ответа.
Нужно определить, какой переменной соответствует каждый столбец таблицы. Порядок переменных один и тот же во всех строках. F обозначает результат вычисления и в ответ не входит.
Опорные значения
| Известно | Что из этого следует |
|---|---|
| \neg A = 0 / \neg A = 1 | A = 1 / A = 0 |
| A \land B = 1 | Обе части равны 1 |
| A \lor B = 0 | Обе части равны 0 |
| A \to B = 0 | A = 1, B = 0 |
| A \equiv B = 1 / A \equiv B = 0 | Значения равны / различаются |
Если результат И равен 0, хотя бы одна часть равна 0, а другая может быть любой. Если результат ИЛИ равен 1, хотя бы одна часть равна 1, а другая может быть любой.
A \to B = \neg A \lor B; \neg(A \to B) = A \land \neg B.
\neg(A \land B) = \neg A \lor \neg B; \neg(A \lor B) = \neg A \land \neg B.
Порядок решения
Без скобок операции обычно выполняются в порядке \neg , \land , \lor , \to , \equiv . Скобки или отдельное правило из условия могут задавать другой порядок.
- Определить нужное значение F и последнюю операцию в формуле.
- Найти, какие значения переменных дают нужное F. При переборе для n переменных проверяются 2^n наборов: 8 для трёх переменных, 16 для четырёх.
- Сравнить найденные наборы с заполненными клетками и определить переменные в столбцах. В пустой клетке может оказаться 0 или 1.
- Заполнить пропуски. Проверить, что в каждой строке формула даёт нужное F, а порядок переменных во всех строках одинаков. Если по условию строки различны, после заполнения они должны отличаться хотя бы одним значением переменной.
- Записать буквы по столбцам исходной таблицы слева направо. Формат записи задаётся в условии.
Если в таблице нет пропусков и перечислены все подходящие наборы, столбцы можно сравнить по числу единиц. Если в двух столбцах единиц поровну, нужен другой признак. При наличии пропусков итоговое число единиц пока неизвестно.
Запись в Python
\neg A: not A; A \land B: A and B; A \lor B: A or B; A \to B: ((not A) or B); A \equiv B: (A == B). Если вместо A или B стоит выражение, оно заключается в скобки.
Возможные ловушки
- Пропуск принят за ноль. Пример с полностью пустым столбцом: EGE-02-0198 ↗.
- Отрицание целой скобки заменено отрицанием одной переменной. Пример с отрицанием импликации: EGE-02-0145 ↗.
- Строки, названные в условии различными, после заполнения стали одинаковыми. Пример: EGE-02-0003 ↗.
- Ответ записан в порядке букв формулы или программы, а не столбцов условия. Пример требований к записи ответа: EGE-02-0106 ↗.