№1
(x /\ y/\z/\¬w)\/ (x /\ y/\¬z/\¬w)\/ (x /\¬ y/\¬z/\¬w).
Решение
x /\ y/\z/\¬w – x=1, y=1, z=1, w=0;
x /\ y/\¬z/\¬w – x=1, y=1, z=0, w=0;
x /\¬ y/\¬z/\¬w – x=1, y=0, z=0, w=0.
В итоге получаем 6 единиц.
Ответ:
6.
№2 Логическая функция F задается выражением
(¬x /\ y/\¬z/\w)\/ (x /\ y/\z/\¬w)\/ (x /\¬ y/\¬z/\w).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение аналогично решению .
№3 Логическая функция F задается выражением
(x /\ ¬y/\z/\w)\/ (x /\ y/\¬z/\w)\/ (¬x /\ y/\ z/\w).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение аналогично решению .
№4 Логическая функция F задается выражением
(¬x /\ ¬y/\z/\w)\/ (¬x /\ ¬y/\¬z/\w)\/ (¬x /\ y/\ z/\¬w).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение аналогично решению .
№5 Логическая функция F задается выражением
(¬x /\ y/\¬z/\¬w)\/ (x /\ ¬y/\¬z/\¬w)\/ (¬x /\ ¬y/\ z/\¬w).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение аналогично решению .
№6 Логическая функция F задается выражением
(x /\ y/\¬w)\/ (x /\¬ y/\¬z/\¬w).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение
Логическая функция F истина тога, когда истинно хотя бы одно выражение в скобках. Т. к. все переменные в них соединены конъюнкцией, то каждый член должен быть истинным. Выпишем истинные наборы для каждой дизъюнкции.
x /\ y/\¬w – (x=1, y=1, z=1, w=0) и (x=1, y=1, z=0, w=0);
x /\¬ y/\¬z/\¬w – x=1, y=1, z=0, w=0.
В итоге получаем 6 единиц.
№7 Логическая функция F задается выражением
(x /\ y/\z/\¬w)\/ (x /\¬z/\¬w).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение аналогично решению .
№8 Логическая функция F задается выражением
(¬x /\ ¬y/\z/\w)\/ (x /\z/\w).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение аналогично решению .
№9 Логическая функция F задается выражением
(y /\ ¬z /\ ¬w) \/ (¬x /\ ¬y/\¬z/\w).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение аналогично решению .
№10 Логическая функция F задается выражением
(x /\ y /\ ¬z) \/ (¬x /\ ¬y/\¬z).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение аналогично решению .
№11 Логическая функция F задается выражением
¬((¬w/\x) → (y /\ z)) \/ ¬((x /\¬ y)→ (¬z\/¬w)).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение
¬((¬w/\x) → (y /\ z)) – (x=1, y=1, z=0, w=0) и (x=1, y=0, z=1, w=0);
¬((x /\¬ y)→ (¬z\/¬w)) – (x=1, y=0, z=1, w=1).
В итоге получаем 5 единиц.
№12 Логическая функция F задается выражением
¬((¬x\/¬y) → (z \/ w)) \/ ¬((x \/ y)→ (z\/¬w)).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение
Логическая функция F истина тога, когда истинно хотя бы одно выражение в скобках. Т. к. все переменные в них импликацией, то условие ее ложности дает истинность скобок. Следуя примеру, выпишем истинные наборы для каждой скобки.
¬((¬x\/¬y) → (z \/ w)) – (x=1, y=0, z=0, w=0) и (x=0, y=1, z=0, w=0);
¬((x /\¬ y)→ (¬z\/¬w)) – (x=1, y=0, z=0, w=0).
В итоге получаем 3 единиц.
№13 Логическая функция F задается выражением
¬(¬(x\/y) → (¬z\/ w)) \/ ¬(¬(x /\ y)→ (z\/¬w)).
Степан выписал все наборы переменных, для которых это выражение истинно. Сколько единиц написал Степан? В ответе запишите только целое число – количество единиц.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y. Это выражение истинно для трех наборов: (0, 0), (0, 1) и (1, 1). Степан написал 3 единицы.
Решение
Логическая функция F истина тога, когда истинно хотя бы одно выражение в скобках. Т. к. все переменные в них импликацией, то условие ее ложности дает истинность скобок. Следуя примеру, выпишем истинные наборы для каждой скобки.
¬(¬(x\/y) → (¬z\/ w)) – (x=0, y=0, z=1, w=0);
¬(¬(x /\ y)→ (z\/¬w)) – (x=1, y=0, z=0, w=1), (x=0, y=1, z=0, w=1) и
(x=0, y=0, z=0, w=1).
В итоге получаем 6 единиц.
Разбор 2 задания ЕГЭ 2017 года по информатике из проекта демоверсии. Это задание базового уровня сложности. Примерное время выполнения задания 3 минуты.
Проверяемые элементы содержания: умение строить таблицы истинности и логические схемы. Элементы содержания, проверяемые на ЕГЭ: высказывания, логические операции, кванторы, истинность высказывания.
Задание 2:
Логическая функция F
задаётся выражением x
/\¬y
/\ (¬z
\/ w
).
На рисунке приведён фрагмент таблицы истинности функции F
, содержащий все
F
истинна.
Определите, какому столбцу таблицы истинности функции F
соответствует каждая из переменных w
, x
, y
, z
.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример . Если бы функция была задана выражением ¬x \/ y , зависящим от двух переменных: x и y , и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция F истинна.
Тогда первому столбцу соответствовала бы переменная y , а второму столбцу – переменная x . В ответе следовало бы написать: yx .
Ответ: ________
x /\¬y /\ (¬z \/ w )
Конъюнкция (логическое умножение) истинна тогда и только тогда, когда истинны все высказывания. Следовательно переменной х 1 .
Таким образом, переменной x соответствует столбец с переменной 3.
Переменной ¬y должен соответствовать тот столбец, в котором стоит значение 0 .
Дизъюнкция (логическое сложение) двух высказываний истинна тогда и только тогда, когда истинно хотя бы одно высказывание.
Дизъюнкция ¬z \/ w
в данной строке будет истинна только если z=0
, w=1
.
Таким образом, переменной ¬z соответствует столбец с переменной 1 (1 столбец), переменной w соответствует столбец с переменной 4 (4 столбец).
Основано на: демонстрационных вариантах ЕГЭ по информатике за 2015 год, на учебнике Босовой Людмилы Леонидовны
В предыдущей части 1 мы разобрали с вами логические операции Дизъюнкция и Конъюнкция , нам с вами осталось разобрать инверсию и перейти к решению задания ЕГЭ.
Инверсия
Инверсия — логическая операция, которая каждому высказыванию ста-вит в соответствие новое высказывание, значение которого противопо-ложно исходному.
Для записи инверсии используются следующие знаки: НЕ, `¯` , `¬ `
Инверсия определяется следующей таблицей истинности:
Инверсию иначе называют логическим отрицанием.
Любое сложное высказывание можно записать в виде логического выражения — выражения, содержащего логические переменные, знаки логических операций и скобки. Логические операции в логи-ческом выражении выполняются в следующей очерёдности: инвер-сия, конъюнкция, дизъюнкция. Изменить порядок выполнения опе-раций можно с помощью расстановки скобок.
Логические операции имеют следующий приоритет: инверсия, конъюнк-ция, дизъюнкция.
И так, перед нами задание №2 из ЕГЭ по информатике 2015 года
Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы:
x1 x2 x3 x4 x5 x6 x7 x8 F 0 1 0 1 0 1 1 1 1 Каким выражением может быть F?
Значительно облегчает решение задания то, что в каждом варианте сложного выражения F только одна логическая операция: умножение или сложение. В случае умножения /\ если хотя бы одна переменная будет равна нулю, то значение всего выражения F так же должно быть равно нулю. А в случае со сложением V если хотя бы одна переменная будет равна единице, то значение всего выражения F должно быть равно 1.
Тех данных, которые есть в таблице по каждой из 8 переменных выражения F, нам вполне достаточно для решения.
Проверим выражение номер 1:
- ? /\ 1 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 0 )
- по второй строчке таблицы x1=1, х4=0 мы с вами видим что F возможно и может быть равным = 1, если все остальные переменные равны 1 (1 /\ ? /\ ? /\ 1 /\ ? /\ ? /\ ? /\ ? )
- по третьей строчке таблицы x4=1, х8=1 мы с вами видим что F=0 (? /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ 0 ), а в таблице у нас F=1, и это значит, что выражение под номером один нам ТОЧНО НЕ ПОДХОДИТ .
Проверим выражение номер 2:
- по первой строчке таблицы x2=0, х8=1 мы с вами видим что F возможно и может быть равным = 0, если все остальные переменные равны 0 (? V 0 V ? V ? V ? V ? V ? V 0 )
- по второй строчке таблицы x1=1, х4=0 мы с вами видим что F = 1 (1 V ? V ? V 1 V ? V ? V ? V ? )
- по третьей строчке таблицы x4=1, х8=1 мы с вами видим что F возможно и может быть равным = 1, если хотя бы одна из оставшихся переменных будет равна 1 (?
V ?
V ?
V 0
V ?
V ?
V ?
V 0
)
Проверим выражение номер 3:
- по первой строчке таблицы x2=0, х8=1 мы с вами видим что F=0 (? /\ 0 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 1 )
- по второй строчке таблицы x1=1, х4=0 мы с вами видим что F =0 (0 /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ ? ), а в таблице у нас F=1, и это значит, что выражение под номером три нам ТОЧНО НЕ ПОДХОДИТ .
Проверим выражение номер 4:
- по первой строчке таблицы x2=0, х8=1 мы с вами видим что F=1 (? V 1 V ? V ? V ? V ? V ? V 0 ), а в таблице у нас F=0, и это значит, что выражение под номером четыре нам ТОЧНО НЕ ПОДХОДИТ .
В решении задания на едином государственном экзамене вам нужно поступать точно таким же образом: отбрасывать те варианты, которые точно не подходят по тем данным, которые есть в таблице. Оставшийся возможный вариант (как в нашем случае вариант номер 2) и будет правильным ответом.
Источник задания: Решение 2437. ЕГЭ 2017. Информатика. В.Р. Лещинер. 10 вариантов.
Задание 2. Логическая функция F задается выражением . Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных х, у, z.
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала - буква, соответствующая 1-му столбцу, затем - буква, соответствующая 2-му столбцу, затем - буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение.
Перепишем выражение для F с учетом приоритетов операций отрицания, конъюнкции и дизъюнкции:
.
Рассмотрим 4-ю строчку таблицы (1,1,0)=0. Отсюда видно, что на третьем месте должна стоять или переменная y или переменная z, иначе во второй скобке получится 1, что приведет к значению F=1. Теперь рассмотрим 5-ю строчку таблицы (0,0,1)=1. Так как на первом или втором месте должна стоять x, то первая скобка даст 1 только тогда, когда y будет стоять на 3-м месте. Учитывая, что вторая скобка всегда равна 0, то F=1 получается благодаря 1 в первой скобке. Таким образом, получили, что на 3-м месте стоит y. Наконец, рассмотрим 7-ю строчку таблицы (1,0,1)=0. Здесь y=1 и чтобы F=0 необходимо z=0 и x=1, следовательно, x стоит на 1-м месте, а z – на втором.