Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.
Проверяемые элементы содержания: Умение строить таблицы истинности и логические схемы
Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ
Логическая функция 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 переменных, то строк таблицы будет 24=16:
- Далее обе скобки исходного выражения необходимо записать в виде логического выражения, каждую — в отдельном столбце. Также в отдельном столбце добавьте формулу итоговой функции F:
xwzy
-
✎ Способ 2. Программирование:
- В результате будут выведены значения для
F=0
:
Язык python:
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) |
x y z w 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
xwzy
Язык 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. |
F=0
:x y z w False False True True False True True True True False False False True False False True
false
= 0, True
= 1Ответ:
xwzy
-
✎ Способ 3. Логические размышления:
- Внешняя операция выражения — конъюнкция (∧). Во всех указанных строках таблицы истинности функция принимает значение 0 (ложь). Конъюнкция ложна аж в трех случаях, поэтому проверить на ложь очень затруднительно. Тогда как конъюнкция истинна (= 1) только в одном случае: когда все операнды истинны. Т.е. в нашем случае:
(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w) = 1 когда: 1. (¬x ∨ y ∨ z) = 1 И 2. (x ∨ ¬z ∨ ¬w) = 1
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 | результат |
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 |
x | y | z | w | F |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
x | y | z | w | F |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
x | ??? | ??? | ??? | F |
0 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 |
x | y | z | w | F |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
x | ??? | ??? | y | F |
0 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 |
x | y | z | w | F |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
x | w | z | y | F |
0 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 |
Результат: xwzy
📹 Видео (бескомпьютерный вариант)
Миша заполнял таблицу истинности функции:
(¬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. Логические размышления (бескомпьютерный вариант):
- Решим задание методом построения полной таблицы истинности.
- Посчитаем общее количество строк в таблице истинности и построим ее:
4 переменных -> 24 = 16 строк
(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w) 1. Избавимся от импликации: ¬(¬z ∧ ¬(x ≡ y)) ∨ ¬(y ∨ w) 2. Внесем знак отрицания в скобки (закон Де Моргана): (z ∨ (x ≡ y)) ∨ (¬y ∧ ¬w) = 0 1 часть = 0 2 часть = 0 * Исходное выражение должно быть = 0. Дизъюнкция = 0, когда оба операнда равны 0.
(z ∨ (x ≡ y)) = 0 когда z = 0 и x ≡ y = 0 ¬y ∧ ¬w = 0 когда: 1. ¬y = 0 ¬w = 0 2. ¬y = 1 ¬w = 0 3. ¬y = 0 ¬w = 1
x | y | w | z | F |
0 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 0 |
y | w | x | z | F |
1 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 0 |
Результат: ywxz
✎ Способ 2. Программирование:
- В результате будут выведены значения для F=0:
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. |
x y z w False True False False False True False True True False False True
false
= 0, True
= 1Сопоставив их с исходной таблицей, получим результат: 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) |
F=0
:x y z w 0 1 0 0 0 1 0 1 1 0 0 1
Сопоставив их с исходной таблицей, получим результат:
Результат: ywxz
📹 Видео (бескомпьютерный вариант)
📹 Видеорешение на RuTube здесь
📹 Видео (excel)
📹 Видеорешение на RuTube здесь
📹 Видео (программирование)
📹 Видеорешение на RuTube здесь
Логическая функция 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
📹 Видео (бескомьпютерный вариант)
📹 Видеорешение на RuTube здесь
Логическая функция 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
-
✎ Логические размышления (бескомпьютерный вариант):
- Внешним действием (последним выполняемым) в исходном выражении является дизъюнкция:
¬x ∨ y ∨ (¬z ∧ w)
x1 | x2 | F |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
¬x
= 1 или 0, y
= 1 или 0, ¬z ∧ w
= 1 или 0).¬x
= 0, иными словами x
= 1. Значит первый столбец соответствует переменной x
. Перем. 1 | Перем. 2 | Перем. 3 | Перем. 4 | Функция |
x | ??? | ??? | ??? | F |
1 | 0 | 0 | 0 | 0 |
y
= 0. Значит четвертый столбец соответствует переменной y
. Перем. 1 | Перем. 2 | Перем. 3 | Перем. 4 | Функция |
x | ??? | ??? | y | F |
1 | 1 | 1 | 0 | 0 |
¬z ∧ w
должно равняться 0, чтобы функция была ложной. Конъюнкция истинна только тогда, когда оба операнда истинны (=1); в нашем случае функция должна быть ложной, но пойдем от обратного. Если ¬z
= 1, т.е. z
= 0, а w
= 1, то это неверно для нашего случая. Значит всё должно быть наоборот: z
= 1, а w
= 0. Таким образом столбец второй соответствует z
, а столбец третий — w
. x | z | w | y | F |
1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 |
Результат: 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. |
📹 Видео (бескомпьютерный вариант)
📹 Видеорешение на RuTube здесь
Логическая функция F задаётся выражением
(x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w
Определите, какому столбцу таблицы истинности функции 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
📹 Видео (бескомпьютерный вариант)
📹 Видеорешение на RuTube здесь
Задания для тренировки
Каждое из логических выражений F и G содержит 5 переменных. В таблицах истинности выражений F и G есть ровно 5 одинаковых строк, причем ровно в 4 из них в столбце значений стоит 1.
Сколько строк таблицы истинности для выражения F ∨ G содержит 1 в столбце значений?
Ответ: 31
- Поскольку в каждом из выражений присутствует 5 переменных, то эти 5 переменных порождают таблицу истинности из 32 строк: т.к. каждая из переменных может принимать оно из двух значений (0 или 1), то различных вариантов с пятью переменными будет 25=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 |
32 - 1 = 31
Результат: 31
Каждое логическое выражение A и B зависит от одного и того же набора из 7 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы.
Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?
Ответ: 8
- Полная таблица истинности для каждого из выражений A и B состоит из 27 = 128 строк.
- В четырех из них результат равен единице, значит в остальных — 0.
- A ∨ B истинно в том случае, когда либо A = 1 либо B = 1, или и A и B = 1.
- Поскольку А = 1 только в 4 случаях, то чтобы получить максимальное количество единиц в результирующей таблице истинности (для A ∨ B), расположим все единицы т.и. для выражения A так, чтобы они были в строках, где B = 0, и наоборот, все строки, где B = 1, поставим в строки, где A = 0:
- Итого получаем 8 строк.
- Если бы в задании требовалось найти минимальное количество единиц, то мы бы совместили строки со значением = 1, и получили бы значение 4.
A | B |
1 | 0 |
1 | 0 |
1 | 0 |
1 | 0 |
0 | 1 |
0 | 1 |
0 | 1 |
0 | 1 |
0 | 0 |
… | … |
Результат: 8
Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 6 единиц.
Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?
Ответ: 256
- Полная таблица истинности для каждого из выражений A и B состоит из 28 = 256 строк.
- В 6 строках результат выражения равен единице, значит в остальных строках — 0.
- A ∧ B ложно в том случае, когда:
A ∧ B = 0 если: 1. A = 0, B = 1 2. B = 0, A = 1 3. A = 0 и B = 0
- Во всех случаях там где А=1 может стоять B=0, и тогда результат F = 0. Поскольку нам необходимо найти максимально возможное число нулей, то как раз для всех шести А=1 сопоставим B=0, и наоборот, для всех шести возможных B=1 сопоставим A=0
- Поскольку строк всего 256, то вполне возможно, что все 256 из них возвратят в результате 0
A | B | F |
1 | 0 | 0 |
1 | 0 | 0 |
1 | 0 | 0 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 1 | 0 |
0 | 1 | 0 |
0 | 1 | 0 |
0 | 0 | 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, так как в таком случае все аргументы выражения должны быть истинными (см. таблицу истинности для конъюнкции).
- Если мы подставим в эту строку все аргументы выражения, то функция действительно возвращает истину. Т.е. это выражение подходит:
- Но проверим на всякий случай остальные.
- Второе выражение проверяем по первой и третьей строке, так как основная операция — дизъюнкция — ложна только в том случае, если все аргументы ложны (см. таблицу истинности для дизъюнкции). Проверяя по первой строке, сразу видим, что x1 в ней равен 1. В таком случаем функция будет = 1. Т.е. это выражение не подходит:
- Третье выражение проверяем по второй строке, так как основная операция — конъюнкция — возвратит истину только тогда, когда все операнды равны 1. Видим, что x1 = 0, соответственно функция будет тоже равна 0. Т.е. выражение нам не подходит:
- Четвертое выражение проверяем по первой и третьей строкам. В первой строке x1 = 1, т.е. функция должна быть равна 1. Т.е. выражение тоже не подходит:
- Таким образом, ответ равен 1.
Результат: 1
Дано логическое выражение, зависящее от 5 логических переменных:
(¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5) ∧ (x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5)
Сколько существует различных наборов значений переменных, при которых выражение истинно?
1) 0
2) 30
3) 31
4) 32
Ответ: 2
- Поскольку выражение включает 5 переменных, то таблица истинности состоит из 25 = 32 строк.
- Внешней операцией (последней) является конъюнкция (логическое умножение), а внутри скобок — дизъюнкция (логическое сложение).
- Обозначим первую скобку за А, а вторую скобку за B. Получим выражение A ∧ B.
- Найдем сколько нулей существует для таблицы истинности данного выражения:
A B F 1. 0 0 0 2. 0 1 0 3. 1 0 0
Теперь рассмотрим каждый случай отдельно:
¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5 = 0
и
x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 = 0.
32 - 2 = 30, что соответствует номеру 2
Результат: 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
- Полная таблица истинности будет иметь 26 = 64 строк (т.к. 6 переменных).
- 4 строки нам известны: в них x3 два раза не совпадает с F.
- Неизвестных строк:
64 - 4 = 60
60 + 2 = 62
Результат: 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
- Рассмотрим отдельно каждое выражение и найдем последнюю операцию, которая должна быть выполнена (внешнюю).
1 выражение:
(((x1 ∧ (x2 → x3) ∧ ¬x4) ∧ x5) ∧ x6) ∧ ¬x7
(((x1 ∨ (¬x2 → x3) ∨ ¬x4) ∨ ¬x5) ∨ x6) ∨ ¬x7
(((¬x1 ∧ (x2 → ¬x3) ∧ x4) ∧ ¬x5) ∧ x6) ∧ x7
Результат: 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 в том порядке, в котором идут соответствующие им столбцы.
Ответ: yzx
- Сначала необходимо рассмотреть логическую операцию, которую мы будем выполнять в последнюю очередь — это логическое И (конъюнкция) или ∧. То есть внешнюю операцию:
(y → x) ∧ (y → z) ∧ z
(y → x) ∧ (y → z) ∧ z = 1 если: 1. (y → x) = 1 2. (y → z) = 1 3. z = 1
№ | Перем. 1 | Перем. 2 | Перем. 3 | Функция |
---|---|---|---|---|
3 | 0 | 1 | 0 | 1 |
№ | Перем. 1 | Перем. 2 | Перем. 3 | Функция |
---|---|---|---|---|
_ | ??? | z | ??? | F |
№ | Перем. 1 | z | Перем. 3 | Функция |
---|---|---|---|---|
4 | 0 | 1 | 1 | 1 |
y | z | x | F |
Результат: yzx
Павел
Почему в задании 2_9 подходит 4 вариант? Ведь если проверить по таблице вторую линию то там x7=0 при том, что последнее действие в выражении (…/\x7) никак не может получиться истина.
admin
Конъюнкция с x7 — это как раз-таки далеко не последнее действие, это же умножение. Последнее действие другое. Поставьте обычные математические действия: ¬x1 + … + x4 + x5 + x6 * x7 и выполните задание
Дарья
Добрый день!
в Задание 2_6 почему не учитываются наборы, когда В=1 и А=0. Их будет 4 штуки. Получается 8+4=12?
admin
Да, не совсем понятно объяснила. Исправила. Спасибо 🙂
Марина
В задании 2_1 фраза
«вторая переменная равна 0, а первая обязательно должна быть равна 1» — ошибочный вывод для импликации, которая должна быть истинна
admin
Спасибо! исправлено
Alex_Borodin
В задании 2_4 ответ 6, хотя такого варианта нет. В подробном решении ответ правильный.
admin
Спасибо! исправлено