На ЕГЭ по информатике очень важно уметь решать задачи не только правильно, но и быстро.
Благодаря особенностям синтаксиса Python позволяет за короткое время писать программы, которые помогают получить верный ответ на различные задания ЕГЭ, в частности на задание № 2. (Как решать его аналитически, можно прочитать здесь.)
Важно: Python мы используем только для того, чтобы построить таблицу истинности функции из задания. Расставить переменные по местам придётся самостоятельно.
Разбор задачи
Шаблон программы:
print("w x y z F")
for w in 0, 1:
for x in 0, 1:
for y in 0, 1:
for z in 0, 1:
F = …
if F == …:
print(w, x, y, z, …)
Разберём шаблон по частям:
print("w x y z F")
Выводим на экран заголовки столбцов в том порядке, в котором мы будем перебирать значения переменных в программе.
for w in 0, 1:
for x in 0, 1:
for y in 0, 1:
for z in 0, 1:
Создаём вложенные циклы для перебора всех возможных комбинаций значений переменных $x$, $y$, $z$ и $w$. В итоге мы получим 16 комбинаций, точно так же как если бы составляли таблицу истинности вручную.
F = …
if F == …:
print(w, x, y, z, …)
Самая важная часть программы. Сюда мы должны будем записать логическую функцию F = … и с помощью условия отобрать и вывести на экран только те комбинации значений переменных, в которых она принимает интересующие нас значения.
Перенесём функцию из условия в программу
В условии задачи нам дана логическая функция $\lnot (y \to (x \equiv w)) \land (z \to x)$.
У всех операций алгебры логики есть свой эквивалент в языке Python:
Важно: сравнение \<= — это не импликация, но результат получается такой же:
Поскольку для операций импликации и эквивалентности используется сравнение, важно помнить, что в языке программирования у них более высокий приоритет выполнения, чем у логических операторов and, or и not. При переносе функции в код это нужно учитывать.
Разберём на примере. Дано логическое выражение $x \land y \equiv z$.
Неправильный перенос:
x and y == z # Выполнится как: x and (y == z)
Правильный перенос:
(x and y) == z # Сначала x and y, потом сравнение с z
Составим чек-лист, который поможет нам перенести функцию в код без ошибок:
- Начните записывать выражение с операции с самым низким приоритетом, постепенно переходя к более приоритетным
- Каждая пара скобок, которая есть в исходном выражении, должна быть поставлена при переносе в программу
- Как только вы поставили открывающую скобку, сразу поставьте парную ей закрывающую. Так вы избежите множества ошибок
- Если встретилась инверсия, поставьте круглые скобки и запишите not внутри них
Воспользуемся чек-листом и перенесём функцию из нашей задачи в код:
F = (not ) and ()F = (not ()) and ()F = (not (y <= ())) and ()F = (not (y <= (x == w))) and ()F = (not (y <= (x == w))) and (z <= x)
Внесём в шаблон кода эту функцию и дополним условие так, чтобы выводились только те комбинации переменных, при которых функция истинна (так как в данной в условии таблице истинности во всех строках значение функции равно единице).
F = (not (y <= (x == w))) and (z <= x)
if F == 1:
print(w, x, y, z, 1)
Программа целиком:
print("w x y z F")
for w in 0, 1:
for x in 0, 1:
for y in 0, 1:
for z in 0, 1:
F = (not (y <= (x == w))) and (z <= x)
if F == 1:
print(w, x, y, z, 1)
Результат выполнения:
Теперь мы можем расставить переменные $w$, $x$, $y$ и $z$ по столбцам таблицы истинности из условия.
Обратите внимание: только в третьем столбце могут находиться три единицы (в остальных есть хотя бы один ноль). Значит, это столбец $y$.
Во второй и третьей строке в незаполненные ячейки можно записать единицы, так как в получившейся с помощью программы таблице истинности во всех строках минимум две единицы.
Во втором столбце стоят две единицы и один ноль, что соответствует переменной $x$. В остальных столбцах должно быть ровно по одной единице, поэтому мы можем заполнить оставшиеся пустыми ячейки первой строки.
В строке с тремя единицами нулю соответствует переменная $w$ — значит, её мы поместим в первый столбец, а переменную $z$ — в четвёртый.
Ответ: $wxyz$
Разбор задачи (альтернативный шаблон)
Рассмотрим ещё один шаблон программы, который позволит немного быстрее написать код для составления таблицы истинности. Этот способ будет полезен тем, кто хочет изучить дополнительные возможности Python.
Шаблон программы с itertools:
from itertools import product
print("w x y z F")
for w, x, y, z in product([0, 1], repeat=4):
F = …
if F == …:
print(w, x, y, z, …)
Как работает функция product
Функция product позволяет составить комбинации элементов из переданных ей коллекций: строк, списков, множеств и других.
Чтобы воспользоваться этой функцией, её надо подключить в начале программы:
from itertools import product
Разберём, как работает product, на простых примерах:
from itertools import product
for pair in product('ab', '12'):
print(pair)
Результат:
('a', '1')\
('a', '2')\
('b', '1')\
('b', '2')
Функция product создала все возможные комбинации, в которых символы из первой строки попарно сопоставлены с символами из второй.
В функцию можно передать сколько угодно коллекций:
from itertools import product
for threes in product([0, 1], [2, 3], [4, 5]):
print(threes)
Результат:
(0, 2, 4)\
(0, 2, 5)\
(0, 3, 4)\
(0, 3, 5)\
(1, 2, 4)\
(1, 2, 5)\
(1, 3, 4)\
(1, 3, 5)
В этом случае мы получаем все возможные комбинации троек чисел.
Если нам нужно составить комбинации из повторяющихся коллекций, мы можем не писать их все, а использовать параметр repeat. Он покажет, сколько раз входные данные должны быть повторены:
from itertools import product
for fours in product([0, 1], repeat=4):
print(fours)
Результат:
(0, 0, 0, 0)\
(0, 0, 0, 1)\
(0, 0, 1, 0)\
(0, 0, 1, 1)\
(0, 1, 0, 0)\
(0, 1, 0, 1)\
(0, 1, 1, 0)\
(0, 1, 1, 1)\
(1, 0, 0, 0)\
(1, 0, 0, 1)\
(1, 0, 1, 0)\
(1, 0, 1, 1)\
(1, 1, 0, 0)\
(1, 1, 0, 1)\
(1, 1, 1, 0)\
(1, 1, 1, 1)
Посмотрим, в чём отличия нового шаблона от предыдущего:
from itertools import product
Подключаем функцию product из библиотеки itertools, чтобы создать все комбинации значений для наших переменных в одной строке.
for w, x, y, z in product([0, 1], repeat=4):
Вызываем функцию product с параметрами [0, 1] — комбинируемые значения и repeat=4 — количество значений для одной строки.
Чтобы каждой переменной было присвоено одно значение из очередной комбинации, мы записываем их через запятую. Это называется распаковкой в Python (в первую переменную попадает первый элемент в комбинации, во вторую — второй и т. д.).
Важно: переменных должно быть столько же, сколько элементов будет входить в сформированную комбинацию.
Благодаря функции product нам не надо писать четыре одинаковых вложенных цикла, в которых можно случайно запутаться и ошибиться.
Перенесём логическую функцию в код:
F = () and (not ) and (not )F = (x or (not y)) and (not ) and (not )F = (x or (not y)) and (not (y == z)) and (not )F = (x or (not y)) and (not (y == z)) and (not w)
Программа целиком
from itertools import product
print("w x y z F")
for w, x, y, z in product([0, 1], repeat=4):
F = (x or (not y)) and (not (y == z)) and (not w)
if F == 1:
print(w, x, y, z, 1)
Результат выполнения:
Теперь расставим переменные по своим местам в исходной таблице истинности:
Только в четвёртый столбец можно записать три нуля, поэтому он соответствует переменной $w$:
Только во второй строке может быть одна единица (в остальных уже есть по две), поэтому мы можем указать, что второму столбцу соответствует переменная $z$:
В оставшихся нерассмотренными строках содержится по две единицы, но только в одной из этих строк переменная $z$ равна единице. Это первая строка. Ей соответствует строка в построенной нами таблице, где единице равна ещё и переменная $x$. Значит, именно эту переменную мы должны указать в первом столбце таблицы из условия. Тогда в третьем столбце окажется $y$:
Ответ: $xzyw$
Заключение
Задание № 2 ЕГЭ по информатике заключается не только в построении таблицы истинности — оно проверяет умение работать с логическими функциями и анализировать результаты.
Ключевые выводы
-
Точность с самого начала\
Неправильно перенесённая функция даст неверную таблицу, и никакой анализ уже не поможет. Лучше потратить дополнительные 30 секунд на проверку кода, чем получить неправильный ответ -
Анализ — главная сложность\
После построения таблицы начинается самое трудное: сопоставление столбцов с переменными.
- Ищите столбцы и строки с уникальным количеством единиц и нулей
- Используйте процесс исключения для определения переменных
- Заполняйте таблицу, проверяя логику на каждом шаге
Ваш итоговый чек-лист
- Внимательно переносите логическую функцию, используя таблицу соответствий операций
- Помните о приоритете операций сравнения над логическими операторами
- Не спешите с анализом, методично ищите столбцы с характерными паттернами
- Проверяйте каждый шаг сопоставления переменных с таблицей из условия
Закрепите результат
Предлагаем отработать навыки переноса логических функций в код и анализа таблиц истинности с помощью подборки задач. Задания в ней научат вас не ошибаться на каждом этапе решения.
Каждая выполненная задача приближает вас к успешной сдаче ЕГЭ. Не откладывайте, начните практиковаться прямо сейчас!