Задание 2: Построение таблиц истинности логических выражений

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

…

• Отрицание $\neg A$ истинно, когда $A$ ложно.
• Конъюнкция $A \wedge B$ истинна только тогда, когда оба операнда истинны.
• Дизъюнкция $A \vee B$ истинна, если хотя бы один операнд истинен.
• Импликация $A \to B$ ложна ровно в одном случае — когда $A=1$, $B=0$; во всех остальных случаях истинна.
• Эквивалентность $A \equiv B$ истинна, когда $A$ и $B$ равны.
• Число строк полной таблицы истинности с $n$ переменными равно $2^n$.
• Стандартный порядок перечисления наборов — по возрастанию значения двоичного числа, составленного из значений переменных (первая переменная — старший разряд).
• «Неповторяющиеся строки» — условие, что среди показанных строк нет двух одинаковых наборов; это ограничивает число допустимых перестановок столбцов.
• Приоритет операций: сначала $\neg$, затем $\wedge$, затем $\vee$, затем $\to$, затем $\equiv$; скобки меняют порядок вычисления.

1. Определить число переменных $n$ и количество строк фрагмента.
2. Проанализировать формулу: определить, при каком сочетании значений операндов она принимает то значение, которое показано в столбце $F$.
3. Построить (полностью или частично) набор строк, при которых функция принимает нужное значение, в исходном алфавитном порядке переменных.
4. Сравнить количество полученных строк с количеством строк фрагмента — совпадение подтверждает, что это именно те строки.
5. Сопоставить структуру столбцов фрагмента (константы, пары-антонимы, чередование) со структурой, полученной на шаге 3, чтобы определить перестановку переменных.
6. Подставить восстановленное соответствие в формулу и проверить совпадение со всеми строками фрагмента.
7. При неоднозначности использовать условие «строки не повторяются», отбрасывая перестановки, дающие повторы. …