Информатика ЕГЭ 2 задание разбор

2-е задание: «Таблицы истинности» Уровень сложности — базовый, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения — 3 минуты.

Проверяемые элементы содержания: Умение строить таблицы истинности и логические схемы

Плейлист видеоразборов задания на YouTube:

Логическая функция F задается выражением

Ниже приведен фрагмент таблицы истинности функции 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

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)

Язык pascalAbc.net:

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.

Ответ:

Внешняя операция выражения — конъюнкция (∧). Во всех указанных строках таблицы истинности функция принимает значение 0 (ложь). Конъюнкция ложна аж в трех случаях, поэтому проверить на ложь очень затруднительно. Тогда как конъюнкция истинна (= 1) только в одном случае: когда все операнды истинны. Т.е. в нашем случае:
Общая идея дальнейшего решения такова: поскольку внешняя операция — конъюнкция, и результат ее истинен, когда оба сомножителя в скобках будут истинны (=1), то нам необходимо сначала составить все наборы таблицы истинности для обоих сомножителей в скобках. Затем, так как конъюнкция подразумевает пересечение, необходимо сопоставить обе таблицы истинности и выбрать для каждого подходящего набора первого сомножителя подходящий (подходящие) набор (наборы) второго сомножителя. НО! так как у нас в задании известны только наборы для F = 0, то мы сопоставлять будем наборы, которые возвращают ложь. Теперь подробно.
Разобьём исходное выражение на две части и составим таблицу истинности отдельно для двух частей.
Для сомножителя (¬x ∨ y ∨ z): xyzрезультат00010011010101111000101111011111
Получили ложь в одном наборе, так как дизъюнкция (∨) ложна только тогда, когда ложны все операнды.
Для сомножителя (x ∨ ¬z ∨ ¬w): xzwрезультат00010011010101101001101111011111
Соответственно, опять получили ложь в одном наборе, когда ложны все операнды.
Учтем, что нам нужно выбрать и «пересечь» (так как внешняя операция ∧) из всех наборов только те, которые возвращают ложь (так как по заданию известны только строки, где F = 0):

Результат: xwzy

Миша заполнял таблицу истинности функции:

но успел заполнить лишь фрагмент из трех различных ее строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных 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)) <= not(y or w)) then writeln(x:7, y:7, z:7,w:7); end.

Сопоставив их с исходной таблицей, получим результат: 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

Логическая функция F задается выражением

Ниже приведен фрагмент таблицы истинности функции 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

✎ Логические размышления (бескомпьютерный вариант):

Результат: xzwy ✎ Способ 2. Программирование: Язык pascalAbc.net:

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: №FGF ∨ G10002011………132……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: AB101010100101010100……
Итого получаем 8 строк.
Если бы в задании требовалось найти минимальное количество единиц, то мы бы совместили строки со значением = 1, и получили бы значение 4.

Результат: 8

Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 6 единиц.

Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?

Ответ: 256

Полная таблица истинности для каждого из выражений A и B состоит из 2 8 = 256 строк.
В 6 строках результат выражения равен единице, значит в остальных строках — 0.
A ∧ B ложно в том случае, когда:
Во всех случаях там где А=1 может стоять B=0, и тогда результат F = 0. Поскольку нам необходимо найти максимально возможное число нулей, то как раз для всех шести А=1 сопоставим B=0, и наоборот, для всех шести возможных B=1 сопоставим A=0ABF100100100100010010010010000………
Поскольку строк всего 256, то вполне возможно, что все 256 из них возвратят в результате 0

Результат: 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 в том порядке, в котором идут соответствующие им столбцы.

📎📎📎📎📎📎📎📎📎📎