Задание 2: таблицы истинности

Учимся за минуту определять, какой столбец таблицы — это переменная x, какой — y, а какой — z, имея лишь обрывок таблицы истинности.

Задание 2 ЕГЭ — по нескольким строкам таблицы истинности логической функции восстановить соответствие между безымянными столбцами переменных и буквами в формуле.

В задании 2 дана логическая функция от трёх-четырёх переменных, например $F = (x \land y) \lor (\neg y \equiv z)$, и кусок её таблицы истинности. Но столбцы с переменными перемешаны и подписаны нейтрально — Перем1, Перем2, Перем3. Нужно сказать, в каком порядке идут $x$, $y$, $z$. Полная таблица для трёх переменных содержит $2^3 = 8$ строк, но в задании дают всего 3–4 строки, где функция равна 1 (или равна 0). Этого достаточно.

Зачем это нужно

Навык читается шире, чем один тип задачи: вы тренируетесь быстро считать значение булевой формулы и рассуждать «от противного» — какие наборы делают её истинной. Это та же логика, что и в схемотехнике, в условиях if и в SQL-фильтрах WHERE. На экзамене задание стоит 1 балл, но решается за пару минут, если знать приём.

Главный приём: считаем строки-кандидаты

Идея простая. Возьмём формулу и переберём все 8 наборов значений $(x,y,z)$. Отметим те, где $F=1$. В таблице нам дали несколько строк, где $F=1$ — значит, набор значений переменных в каждой такой строке обязан совпасть с одним из «истинных» наборов формулы. Дальше сопоставляем столбцы.

Разберём на функции

$$F = (\neg x \land y) \lor z.$$

Построим её таблицу истинности (порядок строк — стандартный, от 000 к 111):

Истинных наборов пять: 001, 010, 011, 101, 111. Теперь пусть в задании дан такой фрагмент (столбцы перемешаны, F=1 во всех строках):

Сопоставляем по столбцам

Смотрим, чем выделяется каждый столбец среди истинных наборов формулы {001, 010, 011, 101, 111}. Удобно считать, в каком столбце переменная чаще равна 1 или 0. Переменная $x$ в истинных наборах принимает значения 0,0,0,1,1 — три нуля. Переменная $z$ равна 1 во всех истинных наборах, кроме 010, то есть 1,0,1,1,1 — четыре единицы. Это самый «единичный» столбец.

В нашем фрагменте по столбцам: Перем1 даёт 1,1,0; Перем2 даёт 0,1,1; Перем3 даёт 0,0,1. Столбец Перем3 — самый «нулевой» (две нуля из трёх). Сверим строки целиком. Тройка (Перем1, Перем2, Перем3) первой строки — (1,0,0). Среди истинных наборов формулы такого набора 100 нет! Значит, прямое прочтение неверно, и порядок столбцов другой. Это и есть суть задачи: подобрать перестановку столбцов так, чтобы каждая строка фрагмента стала одним из истинных наборов.

Переберём: пусть Перем1=$z$, Перем2=$x$, Перем3=$y$. Тогда строка (1,0,0) читается как $z{=}1, x{=}0, y{=}0$, то есть набор $(x,y,z)=(0,0,1)=001$ — он истинный, отлично. Вторая строка (1,1,0): $z{=}1,x{=}1,y{=}0 \Rightarrow (1,0,1)=101$ — истинный. Третья (0,1,1): $z{=}0,x{=}1,y{=}1 \Rightarrow (1,1,0)=110$. Но 110 у формулы даёт $F=0$ — противоречие. Значит, и эта гипотеза неверна.

Возьмём Перем1=$x$, Перем2=$z$, Перем3=$y$. Строка (1,0,0): $x{=}1,z{=}0,y{=}0 \Rightarrow 100$, F=0 — мимо. Пробуем Перем1=$y$, Перем2=$x$, Перем3=$z$. Строка (1,0,0): $y{=}1,x{=}0,z{=}0 \Rightarrow (0,1,0)=010$ — истинный. Строка (1,1,0): $y{=}1,x{=}1,z{=}0 \Rightarrow (1,1,0)=110$, F=0 — мимо. Остаётся Перем1=$y$, Перем2=$z$, Перем3=$x$: (1,0,0)$\Rightarrow y{=}1,z{=}0,x{=}0 = 010$ ✓; (1,1,0)$\Rightarrow y{=}1,z{=}1,x{=}0=011$ ✓; (0,1,1)$\Rightarrow y{=}0,z{=}1,x{=}1=101$ ✓. Все три строки истинны. Ответ: Перем1 = y, Перем2 = z, Перем3 = x.

Как это работает

Перестановок столбцов для трёх переменных всего $3! = 6$, для четырёх — $4! = 24$. Перебор кажется большим, но почти все варианты отсекаются на первой же строке: если набор не попал в множество истинных, гипотезу выбрасываем. Поэтому на практике вы проверяете 2–4 перестановки. Чтобы не строить полную таблицу, формулу часто можно «прочесть» хитрее: найти, какая переменная при $F=1$ ведёт себя жёстко. Например, в импликации $a \Rightarrow b$ ложь бывает только при $a{=}1,b{=}0$; в дизъюнкции с одинокой переменной $z$ эта переменная «тянет» функцию к 1. Такие наблюдения сужают поиск без полной таблицы.

Аккуратный способ — посчитать всё программой: перебрать наборы, отобрать истинные и затем найти подходящую перестановку столбцов фрагмента.

from itertools import permutations

def F(x, y, z):
    return int(((not x) and y) or z)

true_sets = [(x, y, z) for x in (0, 1) for y in (0, 1) for z in (0, 1) if F(x, y, z)]
fragment = [(1, 0, 0), (1, 1, 0), (0, 1, 1)]  # столбцы Перем1, Перем2, Перем3

for perm in permutations("xyz"):
    ok = True
    for row in fragment:
        d = dict(zip(perm, row))
        if (d["x"], d["y"], d["z"]) not in true_sets:
            ok = False
            break
    if ok:
        print("Перем1, Перем2, Перем3 =", perm)

Вывод:

Перем1, Перем2, Перем3 = ('y', 'z', 'x')

Ещё один разбор: функция с эквивалентностью

Пусть $F = \neg(x \equiv y) \lor z$, и дан фрагмент из строк, где $F=0$. Ложь у дизъюнкции бывает только когда оба слагаемых ложны: $\neg(x \equiv y){=}0$ и $z{=}0$. Первое означает $x \equiv y$ истинно, то есть $x=y$. Значит, при $F=0$ всегда $z{=}0$ и $x=y$. Сразу понятно: столбец с переменной $z$ — это тот, где во всех данных строках стоит 0. А два других столбца в каждой строке равны между собой (это $x$ и $y$, их между собой различить помогает уже сама формула, если она несимметрична по $x$ и $y$). Так наблюдение о структуре формулы экономит перебор.

Частые ошибки

• Путают, какие строки даны — с $F=1$ или с $F=0$. Проверять надо вхождение строки в правильное множество: истинных или ложных наборов.
• Считают значение формулы по неверному приоритету операций. Помните порядок: сначала $\neg$, затем $\land$, затем $\lor$, последними $\Rightarrow$ и $\equiv$. Скобки в условии — закон.
• Останавливаются на первой перестановке, которая прошла одну строку. Гипотезу подтверждают ВСЕ данные строки, иначе она неверна.
• Забывают, что у симметричных по паре переменных функций (например $x \land y$) различить эти две переменные по таблице иногда нельзя — тогда в ответе допустимы оба порядка; на ЕГЭ формулу подбирают так, чтобы ответ был единственным.

Итоги

• Постройте (или «прочитайте») множество наборов, где функция истинна — это эталон для сверки.
• Перебирайте перестановки столбцов; каждую отбрасывайте на первой же строке, которая не попадает в эталон.
• Структура формулы (импликация ложна лишь при 1→0; одинокая переменная в дизъюнкции; $x=y$ при эквивалентности) резко сужает перебор.
• Правильная перестановка — та, которую подтверждают все данные строки.