Что проверяет задание
Дана логическая функция от нескольких переменных и фрагмент таблицы истинности. Столбцы переменных переставлены: неизвестно, какой столбец какой букве соответствует. Нужно восстановить порядок переменных и записать его строкой букв.
Иногда даны две функции. Тогда в фрагменте есть столбцы значений обеих функций.
Определения
Высказывание, утверждение, которое истинно или ложно. На экзамене это кодируют числами: 1, истина, 0, ложь.
Логическая переменная, переменная, принимающая только значения 0 и 1.
Логическая функция, правило, которое по набору значений переменных выдаёт 0 или 1.
Таблица истинности, полный перечень всех наборов переменных и значения функции на каждом наборе. Для n переменных в полной таблице 2ⁿ строк.
Фрагмент таблицы, несколько строк полной таблицы. Часть клеток может быть скрыта.
Набор, одна строка: конкретные значения переменных (и, если указано, значение функции).
Операции
Приоритет от более сильного к более слабому: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Скобки меняют порядок.
Отрицание ¬A. Меняет значение на противоположное.
Конъюнкция A ∧ B (логическое И). Истинна только когда оба операнда равны 1.
Дизъюнкция A ∨ B (логическое ИЛИ). Ложна только когда оба операнда равны 0.
Импликация A → B. Ложна только в случае A = 1, B = 0. Равносильна ¬A ∨ B.
Эквивалентность A ↔ B (или A ≡ B). Истинна, когда значения A и B совпадают.
Строгая дизъюнкция A ⊕ B (исключающее ИЛИ). Истинна, когда значения различны.
| A | B | ¬A | A ∧ B | A ∨ B | A → B | A ↔ B | A ⊕ B |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
Общий алгоритм решения
- Выписать выражение и список переменных. Зафиксировать приоритет операций.
- Понять, чему равна функция в каждой строке фрагмента: значение может быть дано явно или следовать из условия.
- Перебрать возможные соответствия столбцов буквам. Для каждого соответствия подставить числа из строки в выражение.
- Оставить только те соответствия, при которых все строки фрагмента согласованы с выражением.
- Если скрыты отдельные клетки, при проверке строки перебрать допустимые значения этих клеток.
- Ответ, порядок букв по столбцам таблицы. Порядок самих строк во фрагменте значения не имеет: важна только возможность такого набора.