Как аналитически решить задание № 2 из ЕГЭ по информатике

Чтобы решить задание № 2 из ЕГЭ по информатике, нужно построить таблицу истинности логической функции. Это можно сделать как вручную (аналитически), так и написав код. Такое решение задания это шаблонное, его могут выполнить даже те ученики, которые не очень хорошо программируют.

Мы рекомендуем освоить и аналитический способ решения, чтобы суметь адаптироваться к возможным изменениям в задании или просто перепроверить свой ответ вручную. Задания: N2. Таблицы истинности | N2. Таблицы истинности++

Задача 1. Построение таблицы истинности

Ссылка на задачу

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

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

Перейдём к разбору нашего задания.

Функция (¬x→z)∧(w∨¬y)∧¬z(¬x→z)∧(w∨¬y)∧¬z делится на три части, соединённые между собой логическим И (конъюнкцией): ¬x→z¬x→z, w∨¬yw∨¬y и ¬z¬z. Поскольку во фрагменте из условия для всех строчек значение функции равно единице, каждая из этих частей должна быть равна единице. Выражение с конъюнкцией истинно тогда, когда истинны все входящие в него переменные.

Построим таблицы истинности для каждого простого выражения.

¬x→z¬x→z

w∨¬yw∨¬y

Рассмотрим подробнее, как из получившихся двух таблиц сформировать итоговую. В ней останутся только те комбинации значений переменных, при которых функция равна единице. (В следующей задаче сделаем это проще и быстрее.)

Возьмём из получившихся таблиц строки, в которых выражения равны единице, и составим для них все возможные комбинации значений переменных. Например, для x=0,z=1x=0,z=1 надо дописать все возможные комбинации значений переменных ww и yy: w=0,y=0w=0,y=0; w=1,y=0w=1,y=0; w=1,y=1w=1,y=1. Так, для каждой строки из первой таблицы в результате получатся три строки.

Выражение ¬z¬z равно единице тогда, когда переменная zz равна нулю, поэтому возьмём из таблицы истинности только строки с этим значением.

Теперь мы можем поставить переменные на их места в исходном фрагменте таблицы.

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

В первую очередь анализировать нужно уникальные строки, например содержащие только одну единицу при всех остальных нулевых значениях, или столбцы это в них больше всего нулей или единиц.

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

Также только в одном столбце можно записать три нуля (ведь в остальных есть хотя бы одна единица). Это столбец zz.

В первой строке две единицы и два нуля. В построенной нами таблице только одна такая строка. Значит, если одна единица соответствует xx, вторая это переменная ww.

Оставшийся незаполненным столбец соответствует переменной yy.

Важно правильно записать ответ. Нам нужно переписать переменные именно в том порядке, в котором они выстроились при заполнении фрагмента таблицы истинности из условия задачи. В нашем случае это ywxzywxz.

Ответ: ywxzywxz

Задача 2. Построение таблицы истинности

Ссылка на задачу

В отличие от предыдущей задачи, функция состоит из трёх выражений, которые объединены логическим ИЛИ (дизъюнкцией): x∧¬yx∧¬y, y≡zy≡z и ¬w¬w. Во всех строках таблицы значение функции равно нулю. Значит, нам нужно найти такие ситуации, в которых все выражения равны нулю (дизъюнкция ложна только тогда, когда ложны значения всех переменных).

Построим таблицу истинности выражения x∧¬yx∧¬y:

Таблица истинности выражения y≡zy≡z выглядит так:

В обоих выражениях есть переменная yy, поэтому при составлении итоговой таблицы мы должны взять только те комбинации переменных, в которых значения yy будут одинаковыми. Так, паре x=0,y=0x=0,y=0 соответствует z=1z=1, а парам x=0,y=1x=0,y=1 и x=1,y=1x=1,y=1 соответствует z=0z=0. Выражение ¬w¬w равно нулю тогда, когда переменная ww равна единице. Значит, мы просто допишем единицу в столбце ww для всех комбинаций xx, yy и zz. Получится так:

Проанализируем таблицу из условия и расставим переменные на свои места.

Во всех столбцах, кроме первого, есть нули, поэтому именно он соответствует переменной ww, равной единице:

В построенной нами таблице есть одна строка, которая содержит три единицы, а единственный ноль соответствует переменной zz. Следовательно, в таблице из условия можно заполнить только последнюю строку, поэтому переменная zz должна быть во втором столбце:

Теперь мы видим, что в последней незаполненной ячейке должна находиться единица. В построенной нами таблице в строке с двумя единицами одна из них это переменная ww, а вторая это yy. Значит, третий столбец в таблице из условия соответствует переменной yy, а четвёртый это xx.

Ответ: wzyxwzyx

Задача 3. Анализ функции

Ссылка на задачу

В этот раз мы не будем ничего строить, а попробуем восстановить данные только через анализ функции.

1. В этом случае функция содержит логическое И, которое объединяет три простых логических выражения: cc, a∨da∨d и d→bd→b. Во всех известных из условия строках таблицы истинности значение функции равно единице. Нам нужно будет подобрать такое положение переменных, которое обеспечит единицу для каждого из трёх простых выражений
2. Начнём с выражения, которое содержит одну переменную это cc, равную единице. В таблице есть только один столбец, в который можно записать три единицы. Его и обозначим как cc:

3. Обратим внимание на нижнюю строку, которая теперь заполнена полностью. С её помощью мы сможем найти местоположение ещё одной переменной. Для этого будем последовательно подставлять значение 1 каждой из оставшихся переменных: aa, bb и dd. Получим:
a. c=1,a=1c=1,a=1: 1∧(1∨0)∧(0→0)=1∧1∧1=11∧(1∨0)∧(0→0)=1∧1∧1=1
b. c=1,b=1c=1,b=1: 1∧(0∨0)∧(0→1)=1∧0∧1=01∧(0∨0)∧(0→1)=1∧0∧1=0
c. c=1,d=1c=1,d=1: 1∧(0∨1)∧(1→0)=1∧1∧0=01∧(0∨1)∧(1→0)=1∧1∧0=0

Мы видим, что функция равна единице, только если a=1a=1. Значит, мы нашли место для ещё одной переменной:

4. Теперь попробуем с помощью первой строки определить местоположение оставшихся двух переменных. В ней нам неизвестны значения ячеек в первом и третьем столбцах, но мы знаем, что третий это это aa. Также нам известно, что одна из искомых переменных равна нулю (четвёртый столбец).
Попробуем снова посмотреть, какие значения получатся у функции в зависимости от того, где мы разместим переменные bb и dd.

Вариант 1: c=1,b=0c=1,b=0: 1∧(a∨d)∧(d→0)1∧(a∨d)∧(d→0).
В этом случае dd не может быть равна единице, иначе выражение (d→0)(d→0) станет равно нулю. Но если d=0d=0, то aa должна быть равна единице, чтобы выражение a∨da∨d было равно единице. Тогда наша таблица будет выглядеть так:

А это противоречит условию задачи о том, что все строки должны быть различны

Вариант 2: c=1,d=0c=1,d=0: 1∧(a∨0)∧(0→b)1∧(a∨0)∧(0→b).
В этом случае переменная aa также должна быть равна единице, чтобы выражение a∨0a∨0 стало равно ей же. А вот переменная bb, которую мы помещаем в первый столбец, может принять значение 1. Таблица будет выглядеть так:

В этом случае условие, что все строки в таблице должны быть разными, выполняется, а значит, мы нашли место для всех переменных.

Ответ: bcadbcad

Заключение

Чтобы решать задание № 2 аналитически, нужно понимать основы логики и уметь работать с таблицами истинности. Хотя программирование кажется более простым способом справиться с задачей, владение аналитическим методом даёт важные преимущества на экзамене.

Ключевые выводы:

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

2. Помните о свойствах логических операций
   Конъюнкция истинна, только когда все части истинны, дизъюнкция ложна, только когда все части ложны.

3. Ищите уникальные столбцы и строки
   Они помогают быстро определить расположение переменных в таблице. Начинайте анализ с самых очевидных случаев.

4. Проверяйте условие об отсутствии повторяющихся строк
   Это важное ограничение, которое поможет исключить неверные варианты размещения переменных.

5. Будьте внимательны при записи ответа
   Переменные нужно записывать в том порядке, в котором они расположены в исходной таблице из условия.

6. Используйте аналитический метод для проверки
   Даже если вы решаете задачу с помощью программирования, полезно уметь проверить результат вручную.

Владение обоими методами решения, программированием и аналитикой, поможет вам адаптироваться к любым изменениям в формате задания и уверенно справиться с задачами разной сложности. Потренироваться принять эти навыки предлагаем на подборке задач.

Решение задания № 2 по информатике с помощью Python

На ЕГЭ по информатике очень важно уметь решать задачи не только правильно, но и быстро.

Благодаря особенностям синтаксиса 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:

Создаём вложенные циклы для перебора всех возможных комбинаций значений переменных xx, yy, zz и ww. В итоге мы получим 16 комбинаций, точно так же как если бы составляли таблицу истинности вручную.

                F = …
                if F == …:
                    print(w, x, y, z, …)

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

Перенесём функцию из условия в программу

В условии задачи нам дана логическая функция ¬(y→(x≡w))∧(z→x)¬(y→(x≡w))∧(z→x).

У всех операций алгебры логики есть свой эквивалент в языке Python:

Важно: сравнение <= это не импликация, но результат получается такой же:

Поскольку для операций импликации и эквивалентности используется сравнение, важно помнить, что в языке программирования у них более высокий приоритет выполнения, чем у логических операторов and, or и not. При переносе функции в код это нужно учитывать.

Разберём на примере. Дано логическое выражение x∧y≡zx∧y≡z.

Неправильный перенос:

x and y == z  # Выполнится как: x and (y == z)

Правильный перенос:

(x and y) == z  # Сначала x and y, потом сравнение с z

Составим чек-лист, который поможет нам перенести функцию в код без ошибок:

1. Начните записывать выражение с операции с самым низким приоритетом, постепенно переходя к более приоритетным
2. Каждая пара скобок, которая есть в исходном выражении, должна быть поставлена при переносе в программу
3. Как только вы поставили открывающую скобку, сразу поставьте парную ей закрывающую. Так вы избежите множества ошибок
4. Если встретилась инверсия, поставьте круглые скобки и запишите not внутри них

Воспользуемся чек-листом и перенесём функцию из нашей задачи в код:

1. F = (not ) and ()
2. F = (not ()) and ()
3. F = (not (y <= ())) and ()
4. F = (not (y <= (x == w))) and ()
5. 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)

Результат выполнения:

Теперь мы можем расставить переменные ww, xx, yy и zz по столбцам таблицы истинности из условия.

Обратите внимание: только в третьем столбце могут находиться три единицы (в остальных есть хотя бы один ноль). Значит, это столбец yy.

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

Во втором столбце стоят две единицы и один ноль, что соответствует переменной xx. В остальных столбцах должно быть ровно по одной единице, поэтому мы можем заполнить оставшиеся пустыми ячейки первой строки.

В строке с тремя единицами нулю соответствует переменная ww, значит, её мы поместим в первый столбец, а переменную zz в четвёртый.

Ответ: wxyzwxyz

Разбор задачи (альтернативный шаблон)

Рассмотрим ещё один шаблон программы, который позволит немного быстрее написать код для составления таблицы истинности. Этот способ будет полезен тем, кто хочет изучить дополнительные возможности 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 нам не надо писать четыре одинаковых вложенных цикла, в которых можно случайно запутаться и ошибиться.

Перенесём логическую функцию в код:

1. F = () and (not ) and (not )
2. F = (x or (not y)) and (not ) and (not )
3. F = (x or (not y)) and (not (y == z)) and (not )
4. 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)

Результат выполнения:

Теперь расставим переменные по своим местам в исходной таблице истинности:

Только в четвёртый столбец можно записать три нуля, поэтому он соответствует переменной ww:

Только во второй строке может быть одна единица (в остальных уже есть по две), поэтому мы можем указать, что второму столбцу соответствует переменная zz:

В оставшихся нерассмотренными строках содержится по две единицы, но только в одной из этих строк переменная zz равна единице. Это первая строка. Ей соответствует строка в построенной нами таблице, где единице равна ещё и переменная xx. Значит, именно эту переменную мы должны указать в первом столбце таблицы из условия. Тогда в третьем столбце окажется yy:

Ответ: xzywxzyw

Заключение

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

Ключевые выводы

1. Точность с самого начала
   Неправильно перенесённая функция даст неверную таблицу, и никакой анализ уже не поможет. Лучше потратить дополнительные 30 секунд на проверку кода, чем получить неправильный ответ

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

   • Ищите столбцы и строки с уникальным количеством единиц и нулей
   • Используйте процесс исключения для определения переменных
   • Заполняйте таблицу, проверяя логику на каждом шаге

Ваш итоговый чек-лист

• Внимательно переносите логическую функцию, используя таблицу соответствий операций
• Помните о приоритете операций сравнения над логическими операторами
• Не спешите с анализом, методично ищите столбцы с характерными паттернами
• Проверяйте каждый шаг сопоставления переменных с таблицей из условия

Закрепите результат

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

Каждая выполненная задача приближает вас к успешной сдаче ЕГЭ. Не откладывайте, начните практиковаться прямо сейчас!