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

Задание 2 (базовый уровень): сопоставить переменные столбцам таблицы истинности по фрагменту.

Задание 2 даёт логическую функцию F от нескольких переменных и фрагмент её таблицы истинности с перепутанными столбцами. Нужно определить, какому столбцу (x, y, z, w) соответствует какая переменная.

Что проверяет задание

Формулировка стандартная: «Дано логическое выражение F(x, y, z, w). В таблице приведён фрагмент таблицы истинности, но заголовки столбцов переменных перепутаны. Определите, какому столбцу соответствует каждая переменная». По сути это проверка умения строить и читать таблицу истинности.

Ручной метод

Классический «бумажный» способ:

1. Найти наборы, на которых F принимает «редкое» значение (например, F=1 встречается всего в паре строк) — их проще анализировать.
2. Подставить эти наборы в формулу и понять, какие значения переменных их дают.
3. Сопоставить с фрагментом таблицы и восстановить соответствие столбцов.

Метод рабочий, но требует аккуратности и времени. На КЕГЭ надёжнее построить полную таблицу истинности программой и сравнить с фрагментом.

Машинный метод: полная таблица

Разберём пример. Пусть F = (x ∧ ¬y) ∨ (z ≡ w). Построим полную таблицу и отберём строки, где F принимает редкое значение — по ним легко сопоставить столбцы из фрагмента.

from itertools import product

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

# печатаем строки, где F = 0 (их обычно мало - удобно сравнивать с фрагментом)
print("x y z w | F")
for x, y, z, w in product([0, 1], repeat=4):
    val = int(F(x, y, z, w))
    if val == 0:
        print(f"{x} {y} {z} {w} |  {val}")

Вывод:

x y z w | F
0 0 0 1 |  0
0 0 1 0 |  0
0 1 0 1 |  0
0 1 1 0 |  0
1 1 0 1 |  0
1 1 1 0 |  0

Теперь, если в задании фрагмент содержит, например, строки со значением F=0 и известными значениями в перепутанных столбцах, мы просто ищем строку нашей полной таблицы с тем же набором значений и читаем, какая переменная где стоит.

Алгоритм сопоставления столбцов

В реальном задании фрагмент содержит и значения переменных в перепутанных столбцах (Кол1, Кол2, Кол3), и значение самой функции F в этой строке. Действуем так: перебираем все 6 возможных назначений переменных столбцам и оставляем то, при котором F, вычисленная по формуле, во всех строках совпадает с указанным в таблице значением.

from itertools import permutations

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

# фрагмент задания: (К1, К2, К3, F) — значения перепутанных столбцов и сама функция
fragment = [
    (0, 0, 0, 0),
    (0, 1, 0, 0),
    (0, 1, 1, 1),
]

for perm in permutations(("x", "y", "z")):   # какому столбцу какая переменная
    ok = True
    for row in fragment:
        assign = dict(zip(perm, row[:3]))     # связываем столбцы с переменными
        if F(assign["x"], assign["y"], assign["z"]) != row[3]:
            ok = False
            break
    if ok:
        print("К1 =", perm[0], " К2 =", perm[1], " К3 =", perm[2])

Вывод:

К1 = x  К2 = y  К3 = z

Программа перебрала все варианты «столбец → переменная» и нашла единственный, при котором F по формуле в каждой строке совпала со значением из таблицы. Это и есть искомое соответствие. Важно, что функция F должна быть несимметрична по переменным (здесь x и y входят по-разному) — иначе ответ не будет единственным.

Ускорение: анализ «редкого» значения

Перебор перестановок надёжен, но есть и быстрый аналитический приём, который полезно понимать. Идея: найти набор, на котором функция принимает редкое значение (например, конъюнкция нескольких условий равна 1 лишь на одном наборе), и по нему восстановить переменные. Скажем, если F = (¬x ∧ y ∧ ¬z), то F=1 ровно на одном наборе x=0, y=1, z=0 — и строка фрагмента с F=1 сразу выдаёт все значения. Программа помогает найти такие «опорные» строки:

from itertools import product

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

ones = [(x, y, z) for x, y, z in product([0, 1], repeat=3) if F(x, y, z) == 1]
print("наборы, где F=1:", ones)
print("таких наборов:", len(ones))

Вывод:

наборы, где F=1: [(0, 1, 0)]
таких наборов: 1

Когда F=1 встречается лишь однажды, задача решается без перебора перестановок: значения переменных читаются напрямую из единственной строки фрагмента с F=1. Этот приём экономит время, если функция «почти всегда ложна» (одна конъюнкция) или «почти всегда истинна» (одна дизъюнкция).

Подсчёт строк с F=1 — мини-задача в задании 2

Иногда подвопрос звучит как «на скольких наборах F истинно». Это считается одной строкой:

from itertools import product

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

count = sum(int(F(*vals)) for vals in product([0, 1], repeat=4))
print("наборов, где F=1:", count, "из", 2**4)

Вывод:

наборов, где F=1: 10 из 16

Типичные ловушки

• Неверный приоритет в формуле. Записывая F в Python, расставляйте скобки явно — особенно вокруг импликаций ((not a) or b).
• Эквивалентность ≡ — это ==. В Python пишите z == w, а не z = w.
• Перепутанные столбцы. Сопоставлять нужно именно столбцы переменных, а не значения F — F во фрагменте обычно уже дано.
• Несколько подходящих? Если перебор даёт два варианта, перепроверьте все строки фрагмента — корректная задача всегда имеет единственное соответствие.

Итог

• Задание 2 — это восстановление соответствия «столбец → переменная» по фрагменту таблицы.
• Надёжный метод КЕГЭ: построить полную таблицу истинности и/или перебрать все перестановки переменных программой.
• Записывая формулу в Python, ставьте скобки и помните: импликация = (not a) or b, эквивалентность = a == b.