Задание 2 ЕГЭ информатика

1. Введение

Во втором задании ЕГЭ нужно работать с логическим выражением и фрагментом его таблицы истинности.

Обычно дана функция от переменных x, y, z, w и несколько строк таблицы, но не указано, какой переменной соответствует каждый столбец.

Задача — определить правильный порядок переменных.

Для выполнения задания нужно:

знать основные логические операции;
уметь переводить логическое выражение на Python;
понимать, как устроена таблица истинности;
сравнивать полученные наборы 0 и 1 с фрагментом из условия;
определять, какой столбец соответствует каждой переменной.

Самый удобный способ решения — небольшой перебор на Python: программа находит подходящие наборы, а мы сопоставляем их с таблицей.

Общий принцип решения задания №2

2. Решение задачи базовым кодом

Перед кодом нужно знать, как логические операции записываются в Python.

В математике	Название	В Python
¬	Отрицание	`not`
∧	Конъюнкция	`and`
∨	Дизъюнкция	`or`
→	Импликация	`<=`
≡	Эквиваленция	`==`

Важно: <= можно использовать как импликацию, потому что в таблицах истинности переменные принимают значения 0 и 1.

Для четырёх переменных существует всего 2⁴ = 16 комбинаций, поэтому их удобно перебрать четырьмя циклами.

for x in 0, 1:
    for y in 0, 1:
        for z in 0, 1:
            for w in 0, 1:
                F = # выражение из условия
                if F == 0:
                    print(x, y, z, w)

Каждый цикл перебирает 0 и 1 для своей переменной. В строку F записываем выражение из условия, например:

F = ((x or y) <= z) or (y == w) or z

Если в таблице во всех строках F = 0, выводим только такие наборы. Если F = 1 — меняем проверку на if F == 1.

Пример вывода:

После этого начинается главная часть: сопоставление полученных строк со столбцами таблицы из условия.

3. Как правильно расставить переменные в таблице?

Сначала ищем самые заметные признаки.

Полностью одинаковые значения

Если у переменной во всех найденных строках стоит только 0 или только 1, её столбец часто можно определить сразу.

Например, если z = 0 во всех строках, ищем столбец таблицы, который может целиком состоять из нулей.

Количество нулей и единиц

Если постоянного столбца нет, сравниваем, сколько нулей и единиц встречается у каждой переменной. Такой рисунок часто уникален и позволяет быстро найти нужный столбец.

Используем уже найденные переменные

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

Не переносим вывод Python в таблицу слева направо: столбцы в условии стоят в неизвестном порядке.

Сначала ищем самый заметный столбец, затем определяем остальные.

4. Какие прототипы могут встретиться?

Принцип решения один и тот же:

получаем подходящие строки → сравниваем их с условием → определяем расположение переменных.

Отличается только сложность сопоставления.

Прототип 1. Базовый

Сложность: минимальная. Количество строк, выведенных программой, совпадает с количеством строк в условии — ничего отбрасывать не нужно.

Условие

Миша заполнял таблицу истинности логической функции

F = ((x ∨ y) → z) ∨ (y ≡ w) ∨ z

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

1	2	3	4
0	1
1		1	0
	1	1	0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе запишите буквы подряд в том порядке, в котором идут соответствующие им столбцы.

Для функции из условия используем код:

for x in 0, 1:
    for y in 0, 1:
        for z in 0, 1:
            for w in 0, 1:
                F = ((x or y) <= z) or (y == w) or z
                if F == 0:
                    print(x, y, z, w)

Получаем:

Шаг 1. Находим z

В выводе Python в столбце z во всех трёх строках стоит 0. Значит в таблице из условия столбец z не может содержать ни одной известной единицы.

В 1-м столбце уже есть 1 во второй строке, во 2-м — единицы в первой и третьей строках, в 3-м — единицы во второй и третьей.

Только 4-й столбец не содержит известной единицы: там стоят пропуск, 0 и 0.

Поэтому 4-й столбец = z.

Почему 4-й столбец сразу определяется как z

Шаг 2. Используем вторую и третью строки

После того как 4-й столбец определён как z, во 2-й строке условия единицы стоят в 1-м и 3-м столбцах, а в 3-й строке — во 2-м и 3-м.

Среди результатов Python только две строки имеют по две единицы при z = 0:

1 0 0 1
1 1 0 0

В первой единицы стоят у x и w, во второй — у x и y.

Именно эти две строки должны соответствовать второй и третьей строкам условия.

3-й столбец равен 1 в обеих строках условия. В двух подходящих строках Python единственная переменная, равная 1 в обоих случаях, — x.

Поэтому 3-й столбец = x.

Шаг 3. Различаем w и y

Теперь остаются 1-й и 2-й столбцы — это w и y.

Возможны два варианта. Проверяем их по первой строке условия, где стоят 0 в 1-м столбце и 1 во 2-м.

Если 1-й = y, а 2-й = w, первая строка потребует y = 0 и w = 1.

Такой набор есть только в строке:

1 0 0 1

Но она уже должна использоваться второй или третьей строкой. Это нарушит условие о трёх различных строках.

Значит:

1-й = w;
2-й = y.

Первая строка тогда соответствует набору:

0 1 0 0

и все три строки различны.

Как из двух строк с двумя единицами получить x, а затем различить w и y

1 столбец → w
2 столбец → y
3 столбец → x
4 столбец → z

Ответ: wyxz

Короткий алгоритм

Получить строки с нужным значением F.
Найти столбец с постоянным значением.
Сопоставлять не отдельные клетки, а целые строки и их наборы единиц.
Если остаётся два варианта — проверить их по ещё не использованной строке.

Прототип 2. Лишние строки

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

Условие

Миша заполнял таблицу истинности логической функции

F = ¬(x ∨ y) ∧ ¬w ∨ ¬(z ∨ w) ∧ y

2	3	4	F
1			1
	1		1
1		1	1

Программа выдаёт четыре строки:

Шаг 1. Находим строку с двумя единицами

В третьей строке условия уже стоят две единицы: во 2-м и 4-м столбцах.

Среди результатов Python только одна строка вообще содержит две единицы:

1 1 0 0

Следовательно, третья строка условия соответствует:

x = 1
y = 1
z = 0
w = 0

Значит 2-й и 4-й столбцы — это x и y в неизвестном пока порядке.

Почему начинаем именно с третьей строки

Шаг 2. Находим z и w

После первого шага 1-й и 3-й столбцы должны быть z и w.

Во второй строке условия в 3-м столбце стоит 1.

Но в выводе Python w = 0 во всех четырёх строках. Поэтому 3-й столбец не может быть w.

Значит:

3-й = z;
оставшийся 1-й = w.

Единица в 3-м столбце сразу отличает z от w

Шаг 3. Различаем x и y

Осталось определить 2-й и 4-й столбцы.

Предположим, что 2-й = x. Тогда в первой строке условия x = 1.

В выводе Python x = 1 только в строке:

1 1 0 0

Но эта строка уже используется третьей строкой условия.

Получились бы две одинаковые строки, а по условию все три строки различны.

Значит 2-й ≠ x.

Следовательно, 2-й = y, а 4-й = x.

Шаг 4. Убираем лишнюю строку

Теперь соответствия определены полностью:

1-й = w;
2-й = y;
3-й = z;
4-й = x.

Первая строка условия соответствует:

0 1 0 0

вторая:

0 0 1 0

третья:

1 1 0 0

Строка:

0 0 0 0

не понадобилась ни разу.

Именно она является лишней — мы не угадывали её заранее, она осталась после полного сопоставления.

Проверка x/y и определение лишней строки

1 столбец → w
2 столбец → y
3 столбец → z
4 столбец → x

Ответ: wyzx

Короткий алгоритм

Начать с строки, где известно больше всего значений.
После каждого найденного столбца сужать оставшиеся варианты.
Обязательно учитывать, что строки из условия различны.
Лишней считать только строку, которая не использовалась после полного сопоставления.

Прототип 3. В столбце F есть и 0, и 1

Сложность: во фрагменте одновременно встречаются F = 0 и F = 1. Поэтому нельзя вывести только одну группу строк — нужно рассматривать значения функции вместе с наборами переменных.

Условие

Миша заполнял таблицу истинности логической функции

F = ¬(w → ¬(x → y)) ∧ (¬x → (¬y ≡ z))

1	2	3	4	F
	1	1	1	0
		0	0	1
0			0	1

Выводим все комбинации вместе со значением F:

print('x y z w F')

for x in 0, 1:
    for y in 0, 1:
        for z in 0, 1:
            for w in 0, 1:
                F = (not (w <= (not (x <= y)))) and ((not x) <= ((not y) == z))
                print(x, y, z, w, int(F))

Шаг 1. Работаем только со строками F = 1

В условии две строки имеют F = 1. Поэтому сначала выписываем только результаты Python с F = 1:

Во всех четырёх строках w = 1.

Значит в любой строке условия с F = 1 столбец w не может содержать известный 0.

В 1-м столбце есть 0 в третьей строке, в 3-м — 0 во второй строке, в 4-м — 0 сразу в обеих строках F = 1.

Только во 2-м столбце нет известного нуля.

Поэтому 2-й столбец = w.

Почему по строкам F = 1 сразу находится w

Шаг 2. Находим 4-й столбец

Во второй и третьей строках условия F = 1 и в 4-м столбце стоит 0.

Эти строки различны, поэтому выбранная переменная должна принимать 0 как минимум в двух разных строках F = 1.

4-й столбец не может быть y: среди строк F = 1 значение y = 0 встречается только один раз.

Проверим z.

При z = 0 подходят две строки:

0 1 0 1
1 1 0 1

В обеих y = 1.

Тогда известный 0 в 3-м столбце второй строки и известный 0 в 1-м столбце третьей строки пришлось бы оба объяснять переменной x.

Но x не может одновременно занимать два разных столбца.

Значит 4-й ≠ z.

Остаётся x.

Поэтому 4-й столбец = x.

Почему 4-й столбец не может быть y или z и остаётся x

Шаг 3. Различаем y и z

Теперь известно:

2-й = w;
4-й = x.

Для двух строк F = 1 с x = 0 остаются ровно два набора:

0 0 1 1
0 1 0 1

Поэтому 1-й и 3-й столбцы — это y и z, но их порядок пока неизвестен.

Используем первую строку условия, где F = 0 и стоят значения:

? 1 1 1

Предположим, что 3-й = y.

Тогда в этой строке:

x = 1
w = 1
y = 1

При z = 0 и при z = 1 функция даёт F = 1, а в условии F = 0.

Получаем противоречие.

Следовательно:

3-й = z;
1-й = y.

Первая строка становится:

y = 0
w = 1
z = 1
x = 1

то есть:

x = 1
y = 0
z = 1
w = 1

Для этого набора F действительно равно 0 — всё совпало.

Строка с F = 0 окончательно различает y и z

1 столбец → y
2 столбец → w
3 столбец → z
4 столбец → x

Ответ: ywzx

Короткий алгоритм

Сначала разделить анализ по значениям F.
Искать переменные с постоянным значением внутри одной группы.
Проверять кандидатов на столбец по всем известным клеткам сразу.
Если остаётся неоднозначность — использовать строку с другим значением F как дополнительную проверку.

5. Автокод

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

Условие

Миша заполнял таблицу истинности логической функции

F = ¬(w → (x ≡ y)) ∧ (z → x)

1	2	3	4	F
	0	1	0	1
0			0	1
	1	1		1

from itertools import *

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

for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):
    table = ((a1, 0, 1, 0),
             (0, a2, a3, 0),
             (a4, 1, 1, a5))

    if len(set(table)) == len(table):
        for i in permutations('xyzw'):
            if [F(**dict(zip(i, line))) for line in table] == [1, 1, 1]:
                print(i)

Что делает каждая часть?

from itertools import *

Подключает функции для перебора вариантов.

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

Логическое выражение из условия записывается как функция Python.

for a1, a2, a3, a4, a5 in product([0, 1], repeat=5):

a1–a5 — пустые клетки. product() перебирает для них все комбинации из 0 и 1.

table = ((a1, 0, 1, 0),
         (0, a2, a3, 0),
         (a4, 1, 1, a5))

Это фрагмент таблицы из условия: известные значения оставляем, пропуски заменяем на a1, a2 и т. д.

if len(set(table)) == len(table):

Проверяет, что строки различны. set(table) удаляет повторы; если количество строк не изменилось, условие выполнено.

for i in permutations('xyzw'):

Перебирает все 24 возможных порядка переменных по четырём столбцам.

F(**dict(zip(i, line)))

Связывает столбцы с буквами и подставляет значения конкретной строки в функцию F.

if [F(**dict(zip(i, line))) for line in table] == [1, 1, 1]:

Проверяет значения F для всех строк. Список справа должен полностью совпадать со столбцом F из условия.

Если всё совпало, print(i) выводит найденный порядок переменных.

Ответ: yxwz

Видео разбор

В данном видео так-же есть разборы всех основных прототипов второй задачи

1. Введение

2. Решение задачи базовым кодом

3. Как правильно расставить переменные в таблице?

Полностью одинаковые значения

Количество нулей и единиц

Используем уже найденные переменные

4. Какие прототипы могут встретиться?

Прототип 1. Базовый

Условие

Шаг 1. Находим z

Шаг 2. Используем вторую и третью строки

Шаг 3. Различаем w и y

Короткий алгоритм

Прототип 2. Лишние строки

Условие

Шаг 1. Находим строку с двумя единицами

Шаг 2. Находим z и w

Шаг 3. Различаем x и y

Шаг 4. Убираем лишнюю строку

Короткий алгоритм

Прототип 3. В столбце F есть и 0, и 1

Условие

Шаг 1. Работаем только со строками F = 1

Шаг 2. Находим 4-й столбец

Шаг 3. Различаем y и z

Короткий алгоритм

5. Автокод

Условие

Что делает каждая часть?

Видео разбор

Читайте также

Задание 25 ЕГЭ информатика

Задание 22 ЕГЭ информатика

Задание 3 ЕГЭ информатика