Таблица истинности питон егэ

Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 2022. Сегодня разоблачим второе задание!

Кто незнаком с основными логическими операциями, можете посмотреть прошлогоднюю статью по заданию 2 из ЕГЭ по информатике.

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

Будем перебирать для каждой логической переменной все возможные варианты в программе. А логическая переменная всего два значения может принимать: 1 или 0 (истину или ложь). Таким образом, если к примеру у нас 4 переменные, мы получим 24=16 различных комбинаций.

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

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

Логическая операция Представление в Питоне
Отрицание ¬ not()
Логическое умножение ∧ and
Логическое сложение ∨ or
Следование A ⟶ B not(A) or B
Равносильность ≡ ==

Перейдём к практике решения задач задания 2 с помощью языка программирования Python.

Задача (Классическая)

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

(w → z) ∧ ((y → x) ≡ (z → y)),

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

ЕГЭ по информатике 2022 - задание 2 (классическая задача)

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

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

Пример. Функция F задана выражением ¬x / y, зависящим от двух
переменных, а фрагмент таблицы имеет следующий вид.

ЕГЭ по информатике 2022 - задание 2 (пример)

В этом случае первому столбцу соответствует переменная y, а второму
столбцу – переменная x. В ответе следует написать: yx.

Решение:

Решать задачу будем с помощью шаблона на языке Python (Питон).

print('x y z w')
for x in range(0, 2):
    for y in range(0, 2):
        for w in range(0, 2):
            for z in range(0, 2):
                if (not(w) or z) and ((not(y) or x) == (not(z) or y)):
                    print(x, y, z, w)

В задаче у нас 4 переменные, значит, формируем 4 вложенных цикла. В каждом цикле перебираем все возможные значения для конкретной переменной. Мы перебираем значения 0 и 1.

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

Четыре вложенных цикла проверяют все возможные варианты (24 = 16 вариантов), и мы получим таблицу истинности, почти такую же, как нам и дали в условии задачи.

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

Запустим программу, и на экране распечатается табличка:

ЕГЭ по информатике 2022 - задание 2 (таблица истинности)

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

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

ЕГЭ по информатике 2022 - задание 2 (классическая задача решение)

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

Второй столбец принадлежит переменной w, только там могут быть все нули.

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

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

Получается, что в третий столбец идёт z, а в четвёртый y

Ответ: xwzy

Посмотрим, как решать задачи второго задания из ЕГЭ по информатике, когда функция выдаёт нули в таблице истинности.

Задача (Классическая, закрепление)

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

ЕГЭ по информатике 2022 - задание 2 (классическая задача 2)

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

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

Пример. Функция F задана выражением ¬x / y, зависящим от двух
переменных, а фрагмент таблицы имеет следующий вид.

ЕГЭ по информатике 2022 - задание 2 (пример)

В этом случае первому столбцу соответствует переменная y, а второму
столбцу – переменная x. В ответе следует написать: yx.

Решение:

Воспользуемся программой на языке Python.

print('x y z w')
for x in range(0, 2):
    for y in range(0, 2):
        for w in range(0, 2):
            for z in range(0, 2):
                if not( not(( x == (not(y)) )) or ((x and w) == z) ):
                    print(x, y, z, w)

От прошлой программы эта программа отличается только функцией!

В таблице видим, что функция должна выдавать ноль. Поэтому в условии мы функцию «оборачиваем» в not().

После == операцию not() мы заключили в скобки, чтобы не было синтаксической ошибки.

Получаем следующую таблицу истинности:

ЕГЭ по информатике 2022 - задание 2 (таблица истинности 2)

Разгадаем, где какая переменная находится.

ЕГЭ по информатике 2022 - задание 2 (классическая задача решение)

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

Получается, что второй столбец достаётся переменной z.

В первом столбце должно быть две единицы. На эту роль подходит переменная y.

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

А в последний столбец идёт переменная w по остаточному принципу.

Ответ: yzxw

А как Питон справится с более сложной функцией из примерного варианта ЕГЭ по информатике?

Задача (Сложная функция)
Логическая функция F задаётся выражением ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

ЕГЭ по информатике - задание 2 мощнейший метод

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

ЕГЭ по информатике - задание 2 (лёгкая задача) пример

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Источник задачи сайт решу ЕГЭ: https://inf-ege.sdamgia.ru/

Решение:

Запрограммируем функцию на языке Python.

print('x y z w')
for x in range(0, 2):
    for y in range(0, 2):
        for w in range(0, 2):
            for z in range(0, 2):
                if not( ((not(x) or y) and (not(y) or w)) or (z == (x or y)) ):
                    print(x, y, z, w)

Запустим программу и расставим переменные по своим местам.

ЕГЭ по информатике 2022 - задание 2 (сложная функция, решение)

Переменная z может быть только в третьем столбце.

Во второй столбец идёт переменная w, только этот столбец может иметь одну единицу.

Посмотрим на строчку, где у w стоит единица. В этой же строчке и у x единица. Значит, x идёт в последний столбец, а y в первый столбец.

Ответ: ywzx

Тот же шаблон работает, когда у нас во втором задании три переменные.

Задача (Три переменные)

(№ 1608) Логическая функция F задаётся выражением (¬x ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z)

ЕГЭ по информатике 2022 - задание 2 (три переменных)

На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

Источник задачи сайт К. Ю. Полякова: https://kpolyakov.spb.ru/

Решение:

Для трёх переменных шаблон на Питоне отлично работает.

print('x y z')
for x in range(0, 2):
    for y in range(0, 2):
        for z in range(0, 2):
               if (not(x) and z) or (not(x) and not(y) and not(z)):
                    print(x, y, z)

Здесь и так понятно, куда какая переменная идёт.

ЕГЭ по информатике 2022 - задание 2 (с тремя переменными, решение)

Ответ: yxz

Посмотрим, как решать задачи из второго задания ЕГЭ по информатике, когда в таблице истинности разные значения у функции F.

Задача (Разные значения функции)

Логическая функция F задаётся выражением (¬a ∨ b ∨ ¬c) ∧ (b ∨ ¬c). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

ЕГЭ по информатике 2022 - задание 2 (разные значения функции)

В ответе напишите буквы a, b, c в том порядке, в котором идут соответствующие им столбцы (без разделителей).

Источник задачи сайт К. Ю. Полякова: https://kpolyakov.spb.ru/

Решение:

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

print('a b c')
for a in range(0, 2):
    for b in range(0, 2):
        for c in range(0, 2):
               if (not(a) or b or not(c)) and (b or not(c)):
                    print(a, b, c)

ЕГЭ по информатике 2022 - задание 2 (разные значения функции, решение)

В таблице 6 строчек, в которых главная функция превращается в единицу. Далее эти строчки и будем рассматривать. У нас тоже получилось 6 строчек.

Переменная a имеет три единицы. Это второй столбец, потому что там три единицы.

Переменная b имеет четыре единицы, значит, она расположена в первом столбце.

Переменной c достаётся последний столбец.

Ответ: bac

Ещё одна интересная задача для подготовки к ЕГЭ по информатике 2022.

Задача(С подвохом)

Логическая функция F задаётся выражением a ≡ b ∨ b → c.

ЕГЭ по информатике 2022 - задание 2 (задача с подвохом)

На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

Источник задачи группа Евгения Джобса: https://vk.com/inform_web

Решение:

Подвох заключается в том, что если мы переведём бездумно функцию на язык Питон, то получится a==b or not(b) or c. Но у нас существуют приоритеты для логических операций, которые описаны в прошлогодней статье по подготовке к ЕГЭ по информатике.

В начале должно обрабатываться или, которое было изначально. Затем должно обработаться следование, а потом равносильность. А если мы переведём формулу бездумно, порядок будет не правильный.

Операцию b ∨ b можно представить, как просто b. Ведь, если b принимает значение 0, тогда будет 0 ∨ 0 = 0. Если значение будет 1, то 1 ∨ 1 = 1. Поэтому формулу можно переписать следующим образом:

a ≡ b → c

a == (not(b) or c)

В предыдущих задачах нам не приходилось думать над приоритетами, потому что везде были расставлены скобки. И в основном они уже расставлены в задачах второго задания из ЕГЭ по информатике.

Дальше решаем как обычно.

print('a b c')
for a in range(0, 2):
    for b in range(0, 2):
        for c in range(0, 2):
               if a == (not(b) or c):
                    print(a, b, c)

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

ЕГЭ по информатике 2022 - задание 2 (задача с подвохом, решение)

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

В строчке, где у a ноль, так же ноль и у переменной c. Значит, во второй столбец идёт переменная c. Если мы ноль поставим в первой строчке в первом столбце, то получится первый столбец из всех нулей. А такого у нас в таблице истинности нет.

Тогда переменная b в первом столбце.

Ответ: bca

слишком много лишних скобок ни к чему. Код очень грязный

А есть какой-нибудь простой код, который смог бы помочь с таким заданием: «Сколькими способами можно поставить в соответствие переменные w, x, y, z столбцам таблицы истинности функции F, опираясь на информацию из данного фрагмента?», или же в данном случае нужно самому подбирать комбинации?

Доброго времени суток, есть вопрос про операции в последней задаче. Вот там написано что b ∨ b можно представить как b. А если будет b ∧ b, то это можно будет представить как b? И можете объяснить почему?

Как в циклах идут переменные, это не важно. Это просто перебор всех возможных вариантов.

Володя, b ∧ b = b, эти формулы приведены в материале, на который я даю ссылку в начале статьи.

Характеристика задания

1. Тип ответа: запись правильной последовательности букв.

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

3. Уровень сложности задания: базовый.

4. Примерное время выполнения: (3) минуты.

5. Количество баллов: (1).

6. Требуется специальное программное обеспечение: не обязательно.

7. Задание проверяет умение работать с логическими переменными, выполнять логические операции, строить таблицы истинности.

Пример задания

Николай заполнял таблицу истинности логической функции (F)

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

(F)

(1)

(1)

(1)

(0)

(0)

(1)

(0)

(1)

(0)

(1)

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

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

Как решать задание?

Данное задание можно решать несколькими способами: путём логических рассуждений; использовать электронные таблицы (+) логические рассуждения; с помощью программирования.

Мы рассмотрим вариант решения с помощью языка программирования Python.

Вспомнить основные логические операции можно тут.

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

Законы алгебры логики можно вспомнить тут.

Вспомним управляющие конструкции в Python:

цикл с параметром

for  переменная  in  диапазон:

тело цикла

for (y) in (0), (1):

тело цикла

условие

if  условие  then:

действия, если условие истинно

else:

действия, если условие ложно

if (C>D):

print (‘истина‘)

else:

print (‘ложь‘)

Запись логических операций на Python

Название операции

Запись на Python

конъюнкция

(and)

дизъюнкция

(or)

отрицание

(not)

импликация

(<=)

тождество

(==)

Напишем программу

Запуск программы

Скриншот 04-07-2022 225605.jpg Полученный результат необходимо сравнить с таблицей из условия

Сопоставим полученную таблицу истинности с таблицей из условия. Нам необходимо сравнивать условие с результатами, как по строкам, так и по столбцам, отыскивая некоторые закономерности и невозможности. Заметим, что столбец (y) содержит в себе три единицы, что может быть только в третьем столбце таблицы из условия. Четвёртый столбик таблицы из условия также можем дополнить единицей, и к этому столбику подходят как (z), так и (w).

Теперь проанализируем строки. В первой строке получилось три единицы, что соответствует четвёртой строке результата программирования, дополняем нулём первую строку. В третьей строке у нас два нуля, поэтому добавляем единицу. Проверяем, чтобы сошлось по строке. Заполним второй столбец, допишем единицу. Этот столбец как раз и будет являться (x). Остаётся проанализировать столбцы (1) и (4).

Рассмотрим первую строку: (x = 0), (y = 1), (z = 0), следовательно, (z) — это четвёртый столбик, а (w) — первый.

Скриншот 19-06-2022 013313.jpg

Рис. (1). Ход решения

Ответ: (wxyz).

Источники:

Рис. 1. © ЯКласс.

Изображения. © ЯКласс.

Питон и таблицы истинности

Хотите готовиться со мной к ЕГЭ?
Пишите: 
ydkras@mail.ru
Немного обо мне.

Таблица истинности — это таблица, где перечисляются комбинации аргументов некой логической функции и указывается, какие значения принимает эта функция.

В задаче 2 ЕГЭ по информатике требуется 1) уметь строить таблицы истинности логического выражения и 2) уметь сравнивать построенную таблицу истинности с таблицей, приведенной в условии задачи.

Первый пункт можно выполнить на компьютере, написав несложную (менее 10 строк) программу на Питоне. 

Вообще говоря, в Питоне, как и в паскале, есть специальные логические значения True и False. Но в логических выражениях можно использовать и числа. При этом значение 0 считается ложью, а всё, отличное от нуля — истиной. (Тут создатель Питона позаимствовал идею из С.)

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

((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y))

и таблицу

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
??? ??? ??? ??? F
1 1 0
1 0
1 1 0

Требуется выяснить, какая переменная в таблице обозначена как «переменная 1», «переменная 2» и т.д.

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

Так как в Питоне отсутствует логическая операция импликации, заменяем выражения вроде x → y на эквивалентные выражения not x or y. Операция эквивалентности — это сравнение «==».

Таким образом, наша функция 

((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y))

в Питоне выглядит так:

f =  ((not x or y ) and (not y or w)) or (z == ( x or y))

Чтобы перебрать все возможные комбинации переменных, записываем четыре вложенных цикла вида for x in range(2): (в них переменные принимают значения 0 и 1).

Печатаем строку значений x, y, z, w тогда, когда функция f ложна (т.е. if not f:)

Вот программа, которая вычисляет таблицу истинности и печатает строки значений x, y, z и w, когда функция f имеет значение «ложь»:

 for x in range(2):
    for y in range(2):
        for z in range(2):
            for w in range(2):
                f =  ((not x or y ) and (not y or w)) or (z == ( x or y))
                if not f: print(x,y,z,w)

Программа печатает следующую таблицу:

0 1 0 0
1 0 0 0
1 0 0 1
1 1 0 0

Столбцы слева направо — это значения переменных x, y, z, w соответственно.

Таким образом, мы очень упростили первую часть задачи — построение таблицы истинности. Осталась вторая часть.

В нашей таблице четыре строки, а в задаче — только три. Следовательно, одна строка в нашей таблице лишняя.

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

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

0 1 0 0
1 0 0 1
1 1 0 0

В столбце переменной z — только нули. Следовательно, в задаче переменная 3 — это z.

В столбце переменной w только одна единица. Следовательно, переменная w — это переменная 2 в задаче.

Замечаем, что когда переменная w (переменная 2 в задаче) равна 1, то равна 1 также и переменная x (а в задаче это переменная 4). Следовательно, переменная 4 — это x. Оставшаяся переменная 1 — это переменная y.

Итак, наш ответ — ywzx. Именно такой ответ и приводится в задаче.

При записи логических выражений в Питоне можно столкнуться с тем, что выражения вроде (x ≡ ¬z) при буквальном их переводе (x == not z) вызывают синтаксическую ошибку. Чтобы избежать этого, надо либо заключить выражение not z в дополнительные скобки, т.е. написать (x == (not z)). Можно также заменить операцию «равно» на «не равно», т.е. записать это выражение как (x != z).

(c) Ю.Д.Красильников, 2021 г.

Для логических операций приняты следующие обозначения:

Демонстрационный вариант ЕГЭ 2022

Миша заполнял таблицу истинности логической функции F
¬(y → (x ≡ w)) / (z → x),
но успел заполнить лишь фрагмент из трёх различных её строк, даже
не указав, какому столбцу таблицы соответствует каждая из переменных
w, x, y, z.

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

Решение:

Решать задачу будем с помощью шаблона на языке Python.

  1. Выводим строку ‘x y w z’, что бы было понятно, в каком столбце какая переменная.
  2. У нас четыре переменных, поэтому формируем четыре вложенных цикла for для переменных x, y, w, z. В каждом цикле перебираем все возможные варианту для 0 и 1.
  3. В условии прописываем нашу функцию, которая должна выдавать True (смотрим таблицу)
  4. Выводим результат print(x,y,w,z) и запускаем программу.
  5. Включаем логику 🙂 и опираться лишь на количество нулей и единиц в строчках или столбцах, определяем где находятся переменные в таблице исходника.

Задание 2

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

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

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

Решение:

Составить таблицу истинности для выражения (¬ х ∨ y)  ∧ (x ≡ ¬z) ∧ w нам поможет Python.

Phyton построил нам таблицу для функции, при которых данное выражение равно 1. Получили следующие наборы (см. рисунок). Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

Можем смело поставить единицы в пустые ячейки таблицы. Три единицы по вертикали имеет переменная w. Два нуля по вертикали только у переменной х. По горизонтали, в строке с двумя единицами, одна для w, вторая для z, а y определился сам. ВСЁ!

Ответ: yzxw

Понравилась статья? Поделить с друзьями:
  • Таблица истинности егэ тренажер
  • Таблица истинности для егэ
  • Таблица ирнк егэ
  • Таблица инфинитивов в русском языке егэ
  • Таблица баллов по егэ по обществу