Как решать 2 задание егэ информатика через excel
Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.
Рабочие листы и материалы для учителей и воспитателей
Более 2 500 дидактических материалов для школьного и домашнего обучения
Столичный центр образовательных технологий г. Москва
Получите квалификацию учитель математики за 2 месяца
от 3 170 руб. 1900 руб.
Количество часов 300 ч. / 600 ч.
Успеть записаться со скидкой
Форма обучения дистанционная
- Онлайн
формат - Диплом
гособразца - Помощь в трудоустройстве
Видеолекции для
профессионалов
- Свидетельства для портфолио
- Вечный доступ за 120 рублей
- 311 видеолекции для каждого
(базовый уровень, время – 3 мин)
Тема: Анализ таблиц истинности логических выражений.
Умение строить таблицы истинности и логические схемы.
1.5.1. Высказывания, логические операции, кванторы, истинность высказывания
1.1.6. Умение строить модели объектов, систем и процессов в виде таблицы истинности для логического высказывания
К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике ( Ù , Ú ,¬), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает Ù и Ú . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение). В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек ( Ù , Ú ,¬), что еще раз подчеркивает проблему.
Что нужно знать :
условные обозначения логических операций
A → B импликация (следование)
A º B эквивалентность (равносильность)
операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:
иногда для упрощения выражений полезны формулы де Моргана:
если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», «импликация», и самая последняя – «эквивалентность»
таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных
если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных);
логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)
логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)
логическое следование (импликация) А→В равна 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно
эквивалентность А º B равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1
Решение задач второго типа в MS Excel
1. Составить таблицу входных значения, перечисляя все комбинации переменных в порядке возрастания двоичного кода. Для этого подсчитать n число переменных в исходном выражении, выписать наборы входных переменных. Количество наборов входных переменных 2 n .
2. Для каждой строки находим логическое решение. Для этого:
· Подсчитать общее число логических операций в выражении;
· Установить последовательность выполнения логических операций с учетом скобок и приоритетов.
3. Выполнить поиск значения функции, отсортировать данное значение по искомой части (1 или 0).
2-е задание: «Таблицы истинности»
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.
Проверяемые элементы содержания: Умение строить таблицы истинности и логические схемы
Плейлист видеоразборов задания на YouTube:
Логическая функция F задается выражением
(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w)
Ниже приведен фрагмент таблицы истинности функции F, содержащей все наборы аргументов, при которых функция F ложна.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
Перем.1 | Перем.2 | Перем.3 | Перем.4 | F |
. | . | . | . | F |
0 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 |
В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.
Ответ: xwzy
-
Отобразим перебор всех значений использующихся в выражении переменных (всю таблицу истинности). Поскольку в выражении используются 4 переменных, то строк таблицы будет 2 4 =16:
print('x y z w') for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: F = (not(x) or y or z) and (x or not(z) or not(w)) if not(F): print(x, y, z, w)
begin writeln('x':7, 'y':7, 'z':7,'w':7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not x or y or z) and (x or not z or not w)) then writeln(x:7, y:7, z:7,w:7); end.
Ответ:
-
✎ Способ 3. Логические размышления:
- Внешняя операция выражения — конъюнкция (∧). Во всех указанных строках таблицы истинности функция принимает значение 0 (ложь). Конъюнкция ложна аж в трех случаях, поэтому проверить на ложь очень затруднительно. Тогда как конъюнкция истинна (= 1) только в одном случае: когда все операнды истинны. Т.е. в нашем случае:
- Общая идея дальнейшего решения такова: поскольку внешняя операция — конъюнкция, и результат ее истинен, когда оба сомножителя в скобках будут истинны (=1), то нам необходимо сначала составить все наборы таблицы истинности для обоих сомножителей в скобках. Затем, так как конъюнкция подразумевает пересечение, необходимо сопоставить обе таблицы истинности и выбрать для каждого подходящего набора первого сомножителя подходящий (подходящие) набор (наборы) второго сомножителя. НО! так как у нас в задании известны только наборы для F = 0, то мы сопоставлять будем наборы, которые возвращают ложь. Теперь подробно.
- Разобьём исходное выражение на две части и составим таблицу истинности отдельно для двух частей.
- Для сомножителя (¬x ∨ y ∨ z):
x y z результат 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 - Получили ложь в одном наборе, так как дизъюнкция (∨) ложна только тогда, когда ложны все операнды.
- Для сомножителя (x ∨ ¬z ∨ ¬w):
x z w результат 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 - Соответственно, опять получили ложь в одном наборе, когда ложны все операнды.
- Учтем, что нам нужно выбрать и «пересечь» (так как внешняя операция ∧) из всех наборов только те, которые возвращают ложь (так как по заданию известны только строки, где F = 0):
Результат: xwzy
Разбор 2 задания ЕГЭ вариант № 4, 2019 Информатика и ИКТ Типовые экзаменационные варианты (10 вариантов), С.С. Крылов, Т.Е. Чуркина:
Миша заполнял таблицу истинности функции:
(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w)
но успел заполнить лишь фрагмент из трех различных ее строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z:
Перем.1 | Перем.2 | Перем.3 | Перем.4 | F |
. | . | . | . | F |
1 | 1 | 0 | ||
1 | 0 | 0 | ||
1 | 1 | 0 | 0 |
Определите, какому столбцу таблицы соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.
Ответ: ywxz
-
✎ Способ 1. Логические размышления (бескомпьютерный вариант):
- Решим задание методом построения полной таблицы истинности.
- Посчитаем общее количество строк в таблице истинности и построим ее:
Результат: ywxz
✎ Способ 2. Программирование:
begin writeln('x':7, 'y':7, 'z':7,'w':7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not z and (x xor y))
Сопоставив их с исходной таблицей, получим результат: ywxz
print ('x y z w') for x in 0,1: for y in 0,1: for z in 0,1: for w in 0,1: F=(not z and not(x==y))<=(not(y or w)) if not F: print (x,y,z,w)
Результат: ywxz
Решение 2 задания ЕГЭ по информатике (диагностический вариант экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков):
Логическая функция F задается выражением
¬a ∧ b ∧ (c ∨ ¬d)
Ниже приведен фрагмент таблицы истинности функции F, содержащей все наборы аргументов, при которых функция F истинна.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c, d.
Перем.1 | Перем.2 | Перем.3 | Перем.4 | Функция |
. | . | . | . | F |
0 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 1 |
В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.
Ответ: cbad
Логическая функция F задаётся выражением ¬x ∨ y ∨ (¬z ∧ w).
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.
Перем. 1 | Перем. 2 | Перем. 3 | Перем. 4 | Функция |
. | . | . | . | F |
1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 |
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Ответ: xzwy
begin writeln('x ','y ','z ','w '); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not(not x or y or(not z and w)) then writeln(x:7,y:7,z:7,w:7); end.
Логическая функция F задаётся выражением
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы.
Перем.1 | Перем.2 | Перем.3 | Перем.4 | F |
. | . | . | . | F |
0 | 0 | 0 | ||
0 | 1 | 0 | 1 | 0 |
1 | 0 | 0 |
Ответ: xwzy
Задания для тренировки
Каждое из логических выражений F и G содержит 5 переменных. В таблицах истинности выражений F и G есть ровно 5 одинаковых строк, причем ровно в 4 из них в столбце значений стоит 1.
Сколько строк таблицы истинности для выражения F ∨ G содержит 1 в столбце значений?
Ответ: 31
- Поскольку в каждом из выражений присутствует 5 переменных, то эти 5 переменных порождают таблицу истинности из 32 строк: т.к. каждая из переменных может принимать оно из двух значений (0 или 1), то различных вариантов с пятью переменными будет 2 5 =32, т.е. 32 строки.
- Из этих 32 строк для каждого выражения (и F и G) мы знаем наверняка только о 5 строках: 4 из них истинны (=1), а одна ложна (=0).
- Вопрос стоит о количестве строк = 1 для таблицы истинности выражения F ∨ G. Данной выражение — дизъюнкция, которая ложна только в одном случае — если F = 0 и одновременно G = 0
- В исходных таблицах для каждого выражения F и G мы знаем о существовании только одного 0, т.е. в остальных строках может быть 1. Т.о. для каждого выражения и F и G в 31 строке могут быть единицы (32-1=31), а лишь в одной — ноль.
- Тогда для выражения F ∨ G только в одном случае будет 0, когда и F = 0 и G = 0:
№ F G F ∨ G 1 0 0 0 2 0 1 1 … … … 1 32 … … 1 - Соответственно, истинными будут все остальные строки:
Результат: 31
Каждое логическое выражение A и B зависит от одного и того же набора из 7 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы.
Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?
Ответ: 8
- Полная таблица истинности для каждого из выражений A и B состоит из 2 7 = 128 строк.
- В четырех из них результат равен единице, значит в остальных — 0.
- A ∨ B истинно в том случае, когда либо A = 1 либо B = 1, или и A и B = 1.
- Поскольку А = 1 только в 4 случаях, то чтобы получить максимальное количество единиц в результирующей таблице истинности (для A ∨ B), расположим все единицы т.и. для выражения A так, чтобы они были в строках, где B = 0, и наоборот, все строки, где B = 1, поставим в строки, где A = 0:
A B 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 … … - Итого получаем 8 строк.
- Если бы в задании требовалось найти минимальное количество единиц, то мы бы совместили строки со значением = 1, и получили бы значение 4.
Результат: 8
Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 6 единиц.
Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?
Ответ: 256
Результат: 256
Дан фрагмент таблицы истинности выражения F.
x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Каким из приведённых ниже выражений может быть F?
1) ¬x1 ∧ x2 ∧ ¬x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
2) x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
4) x1 ∨ ¬x2 ∨ x3 ∨ x4 ∨ ¬x5 ∨ ¬x6 ∨ x7
Ответ: 1
- В первом внешняя операция (выполняется последней) — конъюнкция. Начнем рассмотрение с нее. Соответственно, проверяем выражение по строке второй, там где функция = 1, так как в таком случае все аргументы выражения должны быть истинными (см. таблицу истинности для конъюнкции).
- Если мы подставим в эту строку все аргументы выражения, то функция действительно возвращает истину. Т.е. это выражение подходит:
Результат: 1
Дано логическое выражение, зависящее от 5 логических переменных:
(¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5) ∧ (x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5)
Сколько существует различных наборов значений переменных, при которых выражение истинно?
Ответ: 2
- Поскольку выражение включает 5 переменных, то таблица истинности состоит из 2 5 = 32 строк.
- Внешней операцией (последней) является конъюнкция (логическое умножение), а внутри скобок — дизъюнкция (логическое сложение).
- Обозначим первую скобку за А, а вторую скобку за B. Получим выражение A ∧ B.
- Найдем сколько нулей существует для таблицы истинности данного выражения:
Теперь рассмотрим каждый случай отдельно:
¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5 = 0
и
x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 = 0.
Результат: 2
Дан фрагмент таблицы истинности для выражения F:
x1 | x2 | x3 | x4 | x5 | x6 | F |
0 | 0 | 1 | 1 | 0 | 0 | 1 |
0 | 0 | 0 | 0 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 1 | 0 |
Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x3 не совпадает с F.
Ответ: 62
- Полная таблица истинности будет иметь 2 6 = 64 строк (т.к. 6 переменных).
- 4 строки нам известны: в них x3 два раза не совпадает с F.
- Неизвестных строк:
- В неизвестных строках x3 может не совпадать с F, кроме того, в двух известных строках x3 не совпадает с F. Соответственно максимально возможное число строк с несовпадающими x3 и F, будет:
Результат: 62
Дан фрагмент таблицы истинности для выражения F:
x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
0 | 0 | 0 | |||||
0 | 0 | 1 | |||||
1 | 1 | 1 |
Каким выражением может быть F?
1) x1 ∧ (x2 → x3) ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
2) x1 ∨ (¬x2 → x3) ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
3) ¬x1 ∧ (x2 → ¬x3) ∧ x4 ∧ ¬x5 ∧ x6 ∧ x7
4) ¬x1 ∨ (x2 → ¬x3) ∨ x4 ∨ x5 ∨ x6 ∧ x7
Ответ: 4
- Рассмотрим отдельно каждое выражение и найдем последнюю операцию, которая должна быть выполнена (внешнюю).
Результат: 4
Логическая функция F задается выражением
(y → x) ∧ (y → z) ∧ z.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
№ | Перем. 1 | Перем. 2 | Перем. 3 | Функция |
---|---|---|---|---|
. | . | . | F | |
1 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 1 | 0 |
3 | 0 | 1 | 0 | 1 |
4 | 0 | 1 | 1 | 1 |
5 | 1 | 0 | 0 | 0 |
6 | 1 | 0 | 1 | 0 |
7 | 1 | 1 | 0 | 0 |
8 | 1 | 1 | 1 | 1 |
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
Тут говорится что задача на умение строить таблицы истинности и логические схемы (обратите внимание - строить, а не читать и не ещё что-то). Элементы содержания и уровни подготовки посмотрим в кодификатору по кодам 1.5.1 и 1.1.6 соответственно.
Требуется знать про логические операции, "кванторы" (тоже название операций, но с другим подтекстом), уметь строить (опять) таблицы истинности.
Про алгебру логики (про ту часть, которая нужна в школе) я написал статью , стоит с ней ознакомиться, даже если Вам всё по логике вещей ясно.
Несколькими годами ранее, задание на второй позиции было другим. Там требовалось определять, подходит ли функция под таблицу истинности. В общем-то ничего не изменилось, кроме того, что подбор стал чуть труднее: вместо четырёх явно записанных вариантов, которые надо было перебрать тогда, стало 24 варианта, которые ещё надо самому записать.
Дополнительно осложняется дело тем, что в некоторых ячейках таблицы нет чисел, то есть, это может быть любая или даже каждая строка таблицы, в которых остальные цифры совпадают.
Метод грубой силы
С первым заданием сработал такой метод, стоило лишь выписать числа по порядку. Это тогда сэкономило нам кучу времени и памяти на формулы, избавило нас от серьёзных рисков что-то перепутать. Можно попытаться решить и это задание таким же методом. Для этого достаточно составить полную таблицу истинности для высказывания (сделать за Мишу его работу), и определить, какой столбец куда подходит.
Сразу видно, что в условии нам дали все три строки с "нулями", и других нет. Осталось лишь определить, какие куда подойдут.
И строки, и столбцы в "дано" перемешаны как попало. В нашей таблице тоже можно переставлять как пожелаем, но только одна конфигурация совпадёт с данной нам таблицей. Таких перестановок 144 штуки. Большое, но вполне себе конечное поле. Кстати, есть и закономерности. Есть уникальный столбец, где два нуля (он точно x), и одно это скидывает нам число перестановок всего до 12 (3 столбца свободно переставляются и можно менять местами две строки. Ну, а если заметить, что в оставшихся столбцах по одному нулю, а в столбце w - ни одного, то вообще перестановок только четыре.
Совпадает правая нижняя. Ответ: xwzy
Метод красив и привлекателен своей простотой. Даже если не использовать хитрые приёмы снижения количества вариантов, то он всё равно работает на 100%. Гарантированно верный результат даёт всего лишь умение строить таблицы истинности.
Другие методы
На этом можно было бы и закончить, но, к сожалению, этот метод очень трудоёмкий. Только на первом этапе необходимо выполнить 6*16=96 логических вычислений. Если заглянем в спецификацию, то увидим, что авторы считают, что на это задание можно потратить (открыл, прочитал, понял, решил, проверил, записал ответ) всего лишь 3 минуты. Большинство других методов сводятся к попыткам сократить количество вычислений до минимума (желательно до 6*3=18) или ещё меньше.
Рекомендуется, в первую очередь, использовать законы алгебры логики. Их очень много, но в этом задании используется всего три.
Во всех вторых заданиях даются выражения, где два последних действия одинаковые. Это либо конъюнкция , либо дизъюнкция , либо импликация (крайне редко, но зато бывает в других заданиях). Чем так интересны эти три действия? Взгляните на их таблицы истинности:
Сюда ещё можно добавить стрелку Пирса и штрих Шеффера, но их в школе не проходят. У них есть одна уникальная строка. В конъюнкции - первая строка (там ВСЕ столбцы по "1"), а в остальных строках справа - "нули". В дизъюнкции, наоборот, в последней строке везде "0", а в остальных справа "единицы". Вторая строка импликации тоже, бывает, используется, не будем о ней забывать.
Есть правило, закон, определение или как хотите, что
сложное высказывание, составленное из любого количества выражений, соединённых конъюнкцией, истинно только тогда, когда истинны одновременно все входящие в него выражения.
Аналогично с дизъюнкцией, только там "ложно" надо писать. С импликацией чуть сложнее.
Это правило используется для того, чтобы из 144 перестановок получить куда меньше. Например, мы видим (и так будет всегда в ЕГЭ), что везде должны получиться нули и имеет место дизъюнкция - это последняя строка. Значит, при всех входящих, ВСЕ простые высказывания (x /\ ¬ y) и (x ≡ z) и даже (¬ w) должны получаться ложными. А чтобы увидеть, когда какое будет ложным, надо иметь приличный опыт работы с такими вещами.
Но теперь, после такого правила, нам остаётся анализировать 3 высказывания отдельно, а не одно, составленное из трёх. А это, скажу Вам наперёд, куда проще. И самое простое - (¬ w). Даже не имея большого опыта, можно сказать, что оно будет ложным только тогда, когда w будет "1". В столбце w просто не может стоять нулей.
Такой шаг из 144 вариантов оставил нам всего 36, а это уже кое что. И пока ещё вычислений (явных) мы не делали. Так можно и вообще до одной перестановки сократить. Методик таких масса, они есть в интернете, и мы их сейчас рассматривать не будем, как самостоятельные.
Важно, что в сложнейшем переборе из 144 вариантов мы существенно снижаем количество вариантов каждымкаждым ходом.
Стратегия подготовки
Я рекомендую в первую очередь тренироваться составлять таблицы истинности. Если нарешивать по сборникам, то начинать стоит именно с метода грубой силы , составляя полные таблицы истинности. Это кажется нерентабельным, но будет очень полезным : по мере составления таблиц вы увидите закономерности, близкие именно вам и получите такой метод, который подойдёт персонально для вас.
Лучше всего искать способы ускорить построение таблиц истинности.
Хитрые ходы, размышления и прочие методы, которые описаны в разных ютьюбах, стоит смотреть уже после того, как вы будете уверенно выполнять это задание (пусть и дольше 3х минут) с помощью таблицы истинности.
Здравствуйте, дорогие друзья! Сегодня разберём, как решать второе задание из ЕГЭ по информатике 2020.
Во втором задании ЕГЭ по информатике у нас обычно есть логическая функция, которая зависит от логических переменных. Логические переменные могут принимать только два значения: 0 (Ложь) или 1 (Истина).
С логическими переменными можно производить логические операции. При решении второго задания из ЕГЭ по информатике необходимо твёрдо знать каждую логическую операцию, и давайте рассмотрим их.
- () - операции в скобках
- ¬ - логическое отрицание
- ∧ - логическое умножение
- ∨ - логическое сложение
- ⟶ - следование
- ≡ - равнозначность
Ещё соотношения:
Передём к решению задач из ЕГЭ по информатике
Логическая функция F задаётся выражением z ∧ ¬y ∧ (w → x). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Видим, что у функции основным действием является логическое умножение. По таблице видно, что функция имеет значение только 1 . Логическое умножение даёт 1 (единицу) тогда, когда каждое выражение равно 1 (единице). Значит каждое выражение в нашей функции должно равняться единице.
Отсюда видно, что переменная z должна всегда быть равна 1 (единице). Это первый столбец. Отрицание y тоже должно быть 1 (единицей), тогда просто y всегда будет 0 (нулём). Это второй столбец.
Осталось определить положение w и x. Здесь делаем предположение, что в третьем столбце стоит w, а в 4-ом x. Проверяем построчно и видим, что во второй строчке при таком расположении из 1 следует 0, что в итоге приводит выражение (w → x) в 0, а у нас это выражение всегда должно быть 1 (единицей). Значит, мы предположение сделали неверное, и получается x - это третий столбец, а w - четвёртый.
Задача 2 (средний уровень)
Логическая функция F задаётся выражением (x ∧ ¬y) ∨ (y ≡ z) ∨ w.
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Определяем главную логическую операцию ("главную скрипку"), которая соединяет разные выражения. Видим, что это логическое сложение.
Во всех строчках таблицы функция принимает значение 0 (ноль). Значит, и каждое выражение должно принимать значение 0 (ноль).
Самым слабым звеном является переменная w, потому что она стоит одна. Переменная w должна равняться всегда 0(нулю) - этому условию может удовлетворить только третий столбец. Значит w стоит на третьем месте.
Следующим слабым звеном является равносильность. Она должна "выдавать" 0 (ноль). Равносильность "выдаёт" 0 (ноль), когда переменные разные!
Проанализируем первый и второй столбец. В третьей строчке, и там, и там, стоит 1 (единица). Значит, первый и второй столбец не могут быть одновременно y и z (или z и y).
Рассмотрим второй и четвёртый столбец. Вторая строчка содержит одинаковое значение 0 (ноль), и там, и там. Значит, второй и четвёртый столбец не могут быть одновременно y и z (или z и y).
Таким образом, y и z (или z и y) будут столбцы первый и четвёртый! И теперь можно расставить недостающие значения в этих столбцах. Расставляем, чтобы были разные значения, а второй столбец получается x.
Осталось разобраться с z и y. Обратимся к первому выражению (x ∧ ¬y) и посмотрим на третью строчку. Если в четвёртом столбце будет стоять y, то отрицание на y превратит ноль(ноль) в 1(единицу) в четвёртой строчке. Тогда окажется, что у x - 1 и ¬y - 1, и выражение (x ∧ ¬y) тоже получится 1(единицей). А у нас каждое выражение должно равняться 0(нулю). Получается y будет стоять в первом столбце, а z в четвёртом.
Тогда ответ будет равен yxwz.
Ответ: yxwz
Мощнейший метод для решения второго задания из ЕГЭ по информатике
Задача 3 (хороший уровень)
Логическая функция F задаётся выражением ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
"Главной скрипкой" в нашей функции является логическое сложение, потому что соединяет два выражения ((x → y ) ∧ (y → w)) и (z ≡ ( x ∨ y)).
Тогда каждое выражение должно равняться 0(нулю).
Теперь кульминация мощнейшего метода. У нас всего 4 переменных. Выпишем все комбинации для 4-х переменных. Таблица будет точно такая же, как мы писали в первом задании (её очень легко составить). Всего получается 16 комбинаций (16 = 2 4 ).
Теперь отметим зелёным плюсом те строчки, которые обращают выражение ((x → y ) ∧ (y → w)) в 0(ноль). Следующий шаг: Отметим галочкой те строчки, которые обращают в ноль второе выражение (z ≡ ( x ∨ y)) (Мы должны искать среди тех, которые уже отмечены плюсом).
При небольшой тренировке анализ подобных выражений занимает сущие секунды!
У нас получается 4 строчки, которые удовлетворяют нашей функции:
Отсюда видно, что переменная z может быть равна только 0(нулю)! Значит, она занимает третий столбец, потому что в остальных столбцах есть хотя бы одна 1(единица).
Переменная w имеет только одну 1(единицу). Значит, её ставим во второй столбец, потому что в первом и четвёртом уже по 2 единицы минимум, а третий уже занят z.
Теперь находим строчку c 1(единицей) в переменной w (Таблица данная в условии задачи) Кто в этой строчке будет иметь единицу (кроме w) - будет x! Это четвёртый столбец! Значит, x - это четвёртый столбец. Переменной y - достаётся первый столбец
Ответ: ywzx.
На этом всё! Сегодня рассмотрели теорию и основные методы для эффективного решения второго задания из ЕГЭ по информатике!
Пока!
Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 2022. Сегодня разоблачим второе задание!
Кто незнаком с основными логическими операциями, можете посмотреть прошлогоднюю статью по заданию 2 из ЕГЭ по информатике.
В этой статье будут раскрыты методики решения 2 задания через язык программирования Питон.
Будем перебирать для каждой логической переменной все возможные варианты в программе. А логическая переменная всего два значения может принимать: 1 или 0 (истину или ложь). Таким образом, если к примеру у нас 4 переменные, мы получим 2 4 =16 различных комбинаций.
Кто знаком с мощнейшим методом для 2 задания из ЕГЭ по информатике, о котором я рассказывал в прошлогодней статье, тот поймёт, что мы будем применять тот же самый мощнейший метод, но автоматизированный с помощью питона.
Нам нужно будет запрограммировать логическую функцию на языке Питон. Вот таблица, которая поможет это сделать.
Перейдём к практике решения задач задания 2 с помощью языка программирования Python.
Миша заполнял таблицу истинности логической функции F
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.
Решать задачу будем с помощью шаблона на языке Python (Питон).
В задаче у нас 4 переменные, значит, формируем 4 вложенных цикла. В каждом цикле перебираем все возможные значения для конкретной переменной. Мы перебираем значения 0 и 1.
Функция должна выдавать всегда 1 (единицу, истину). Внутри всех циклов прописываем условие, которое срабатывает как раз на истину. В этом условии прописываем нашу функцию. Если наша функция будет выдавать истину, то мы распечатаем значения переменных, при которых это произошло. Если функция будет выдавать ложь, значит, ничего распечатано не будет.
Четыре вложенных цикла проверяют все возможные варианты (2 4 = 16 вариантов), и мы получим таблицу истинности, почти такую же, как нам и дали в условии задачи.
Так же вверху печатаем названия переменных, чтобы знать, какие значения каким переменным принадлежат.
Запустим программу, и на экране распечатается табличка:
В получившийся табличке может быть больше строчек, чем в условии. Так же при поиске переменных нельзя опираться на порядок, в котором идут нули и единицы в нашей табличке. А можно опираться лишь на количество нулей и единиц в строчках или столбцах.
Можно вычеркнуть первую строчку и последнюю, потому что в таблице, которую дали в условии, в каждой строчке есть хотя бы один ноль и хотя бы одна единица.
Сразу видно, что первый столбец принадлежит переменной x, только там могут быть все единицы.
Второй столбец принадлежит переменной w, только там могут быть все нули.
У нас остались две пустые клеточки в самой таблице. Нам нужно где-то поставить единицу, а где-то ноль, потому что у нас остались столбцы с двумя единицами и одним нулём, а так же с двумя нулями и одной единицей. Если мы в третий столбец поставим единицу, а в четвёртый ноль, то первая строчка и вторая будут совпадать.
А в условии сказано, что строки не должны повторяться. Поэтому нужно ноль и единицу расставить наоборот.
Получается, что в третий столбец идёт z, а в четвёртый y
Ответ: xwzy
Посмотрим, как решать задачи второго задания из ЕГЭ по информатике, когда функция выдаёт нули в таблице истинности.
Задача (Классическая, закрепление)
Миша заполнял таблицу истинности функции (x ≡ ¬y) → ((x ∧ w) ≡ z), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.
Воспользуемся программой на языке Python.
От прошлой программы эта программа отличается только функцией!
В таблице видим, что функция должна выдавать ноль. Поэтому в условии мы функцию "оборачиваем" в not().
После == операцию not() мы заключили в скобки, чтобы не было синтаксической ошибки.
Получаем следующую таблицу истинности:
Разгадаем, где какая переменная находится.
Последнюю строку из нашей таблицы можно вычеркнуть, потому что, если мы вычеркнем другую строку, то не получится столбца, где все три единицы, а он должен быть.
Получается, что второй столбец достаётся переменной z.
В первом столбце должно быть две единицы. На эту роль подходит переменная y.
В нашей таблице нет строчки, где все единицы, значит, во второй строчке в пустом окошке выставляем ноль. И в этой строчке нулём обладает переменная x. Следовательно, в третьем столбце будет находится x.
А в последний столбец идёт переменная w по остаточному принципу.
Ответ: yzxw
А как Питон справится с более сложной функцией из примерного варианта ЕГЭ по информатике?
Задача (Сложная функция)
Логическая функция F задаётся выражением ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Запрограммируем функцию на языке Python.
Запустим программу и расставим переменные по своим местам.
Переменная z может быть только в третьем столбце.
Во второй столбец идёт переменная w, только этот столбец может иметь одну единицу.
Посмотрим на строчку, где у w стоит единица. В этой же строчке и у x единица. Значит, x идёт в последний столбец, а y в первый столбец.
Ответ: ywzx
Тот же шаблон работает, когда у нас во втором задании три переменные.
(№ 1608) Логическая функция F задаётся выражением (¬x ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z)
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
Для трёх переменных шаблон на Питоне отлично работает.
Здесь и так понятно, куда какая переменная идёт.
Ответ: yxz
Посмотрим, как решать задачи из второго задания ЕГЭ по информатике, когда в таблице истинности разные значения у функции F.
Задача (Разные значения функции)
Логическая функция F задаётся выражением (¬a ∨ b ∨ ¬c) ∧ (b ∨ ¬c). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.
В ответе напишите буквы a, b, c в том порядке, в котором идут соответствующие им столбцы (без разделителей).
Когда такая ситуация, что функция имеет различные значения в таблице, мы можем проверить, какие значения переменных дают единицу у всей функции. А потом проверить, какие значения выдают ноль у всей функции, если это потребуется.
В таблице 6 строчек, в которых главная функция превращается в единицу. Далее эти строчки и будем рассматривать. У нас тоже получилось 6 строчек.
Переменная a имеет три единицы. Это второй столбец, потому что там три единицы.
Переменная b имеет четыре единицы, значит, она расположена в первом столбце.
Переменной c достаётся последний столбец.
Ещё одна интересная задача для подготовки к ЕГЭ по информатике 2022.
Логическая функция F задаётся выражением a ≡ b ∨ b → c.
На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.
Подвох заключается в том, что если мы переведём бездумно функцию на язык Питон, то получится 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)
В предыдущих задачах нам не приходилось думать над приоритетами, потому что везде были расставлены скобки. И в основном они уже расставлены в задачах второго задания из ЕГЭ по информатике.
Дальше решаем как обычно.
Последнюю строчку можно вычеркнуть из нашей таблицы, т.к. у нас в каждой строчке есть хотя бы один ноль.
Последний столбец занимает переменная a, т.к. только в последний столбец может влезть две единицы.
В строчке, где у a ноль, так же ноль и у переменной c. Значит, во второй столбец идёт переменная c. Если мы ноль поставим в первой строчке в первом столбце, то получится первый столбец из всех нулей. А такого у нас в таблице истинности нет.
Читайте также: