Задание 2. Алгебра логики. Таблицы истинности. ЕГЭ 2020 по информатике

За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: базовый.
Средний процент выполнения: 65.9%
Ответом к заданию 2 по информатике может быть цифра (число) или слово.

Теория к 2 заданию: читать

Задачи для практики

Задача 1

Дан фрагмент таблицы истинности выражения F:

x1 x2 x3 x4 x5 x6 x7 x8 F
0 0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0 0
0 1 0 1 0 1 1 0 1
0 1 1 0 0 1 0 1 0
1 0 0 0 1 1 0 0 0
1 0 0 1 0 0 0 1 1
1 0 0 1 1 0 0 0 0
1 0 1 1 1 0 1 1 1
1 1 0 1 1 1 0 1 1
1 1 0 1 1 1 1 1 1

Сколько строк таблицы удовлетворяют выражению: F = (x1 ∨ x2 ∨ x3) ∧ x4 ∧ (x5 ∨ x6 ∨ x7) ∧ x8?

Решение

Данное выражение является конъюнкцией четырёх выражений. Конъюнкция нескольких высказываний истинна тогда и только тогда, когда истинными являются все входящие в неё высказывания. Следовательно, x4 = 1, x8 = 1 и в наборах значений переменных (x1, x2, x3), (x5, x6, x7) должна быть хотя бы одна 1.

Этим условиям удовлетворяют три последние строки таблицы. В каждой из этих строк значение функции F = 1. Следовательно, эти строки удовлетворяют заданному логическому выражению.

Чтобы остальные строки удовлетворяли заданному выражению, значение F должно быть равно 0. В таблице количество таких строк равно 5.

Всего значения 8 строк таблицы удовлетворяют заданному выражению.

Ответ: 8
Показать решение

Задача 2

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

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

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

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

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

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

Решение

Преобразуем исходное выражение.

(¬x → y) ∧ (z → y) = (x ∨ y) ∧ (¬z ∨ y) = y ∨ (x ∧ ¬z).

Так как дизъюнкция ложна только в том случае, когда ложны оба высказывания, входящие в неё, то переменной y должен соответствовать тот столбец, в котором значение 0 стоит в тех же строках, что и в столбце F. Следовательно, переменной y соответствует третий столбец.

Рассмотрим строку, в которой значение функции отличается от значения переменной y. Такой строкой является четвёртая снизу. Здесь переменная y = 0, а значение функции F = 1. Это означает, что x ∧ ¬z = 1. В рассматриваемой строке значение первого столбца 0, а второго 1. Пусть x = 0, z = 1. При этих значениях логическое выражение x ∧ ¬z ложно, что не соответствует табличному значению функции F = 1. Следовательно, x = 1, z = 0. Значит, первый столбец соответствует переменной z, а второй—x.

Ответ: zxy
Показать решение

Задача 3

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

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

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

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

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

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

Решение

Преобразуем исходное выражение.

(x ∧ ¬y) ∨ (x ∧ z) = x ∧ (¬y ∨ z).

Так как конъюнкция истинна только в том случае, когда истинны оба высказывания, входящие в неё, то переменной x должен соответствовать тот столбец, в котором значение 1 стоит в тех же строках, что и в столбце F. Следовательно, переменной x соответствует второй столбец.

Рассмотрим четвёртую снизу строку. Здесь переменная x = 1, а значение функции F = 0. Это означает, что ¬y ∨ z = 0. В рассматриваемой строке значение первого столбца 1, а третьего 0. Пусть y = 0, z = 1. При этих значениях логическое выражение ¬y ∨ z истинно, что не соответствует табличному значению функции F = 0. Следовательно, y = 1, z = 0. Значит, первый столбец соответствует переменной y, а третий — z.

Ответ: yxz
Показать решение

Задача 4

Каждое из логических выражений A и B зависит от одного и того же набора из 5 переменных. В таблицах истинности обоих выражений в столбцах значений стоит ровно по 16 единиц в каждой таблице. Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A → ¬B?

Решение
Ответ: 32
Показать решение

Задача 5

Каждое из логических выражений A и B зависит от одного и того же набора из 5 переменных. В таблицах истинности обоих выражений в столбцах значений стоит ровно по 16 единиц в каждой таблице. Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A → B?

Решение
Ответ: 16
Показать решение

Задача 6

Каждое из логических выражений A и B зависит от одного и того же набора из 6 переменных. В таблицах истинности обоих выражений совпадает ровно 15 строк. Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A → ¬B?

Решение
Ответ: 15
Показать решение

Задача 7

Дано логическое выражение, зависящее от 6 логических переменных:

¬(A → F) ∧ B ∧ ¬C ∧ (D → E).

Сколько существует различных наборов значений переменных, при которых выражение ложно?

Решение
Ответ: 61
Показать решение

Задача 8

Дано логическое выражение, зависящее от 6 логических переменных:

(¬A → F) ∨ (¬B ∧ C ∧ D ∧ ¬E).

Сколько существует различных наборов значений переменных, при которых выражение ложно?

Решение
Ответ: 15
Показать решение

Задача 9

Дано логическое выражение, зависящее от 5 логических переменных:

$(A ∨ ¬B) ∧ (¬C ∨ D ∨ ¬E)$.

Сколько существует различных наборов значений переменных, при которых выражение ложно?

Решение
Ответ: 11
Показать решение

Задача 10

Дано логическое выражение, зависящее от 5 логических переменных:

(¬A ∧ B ∧ C) ∨ (¬D ∧ ¬E).

Сколько существует различных наборов значений переменных, при которых выражение истинно?

Решение
Ответ: 11
Показать решение

Задача 11

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

        F
1 0 0 0 0
1 1 0 0 0
1 1 1 0 0

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

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

    F
1 0 0
0 1 1
0 0 1
1 1 1

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

Решение
Ответ: yxzw
Показать решение

Задача 12

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

        F
1 0 0 0 1
1 1 0 0 1
1 1 1 0 1

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

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

    F
1 0 0
0 1 1
0 0 1
1 1 1

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

Решение
Ответ: yzxw
Показать решение

Задача 13

Логическая функция F задаётся выражением (y ∧ (w → x)) → g. Во фрагменте таблицы истинности приведены все строки, при которых значение функции F ложно. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, w, g.

        F
0 0 0 1 0
1 0 0 1 0
1 0 1 1 0

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

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

    F
1 0 0
0 1 1
0 0 1
1 1 1

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

Решение
Ответ: xgwy
Показать решение

Задача 14

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

        F
0 1 0 0 0
0 1 0 1 0
0 1 1 1 0

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

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

    F
1 0 0
0 1 1
0 0 1
1 1 1

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

Решение
Ответ: gwxy
Показать решение

Задача 15

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

        F
0 0 0 1 1
1 0 0 1 1
1 0 1 1 1

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

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

    F
1 0 0

тогда 1-му столбцу соответствовала бы переменная y, а 2-му столбцу — переменная x. В ответе следовало бы написать: yx.

Решение
Ответ: zwxy
Показать решение

Задача 16

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

        F
0 0 0 1 0
1 0 0 1 0
1 0 1 1 0

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

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

    F
1 0 0

тогда 1-му столбцу соответствовала бы переменная y, а 2-му столбцу — переменная x. В ответе следовало бы написать: yx.

Решение
Ответ: xwzy
Показать решение

Задача 17

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

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

        F
0 0 1 0 0
0 0 1 1 0
1 0 1 1 0

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

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

    F
1 0 0

тогда 1-му столбцу соответствовала бы переменная y, а 2-му столбцу — переменная x. В ответе следовало бы написать: yx.

Решение
Ответ: zyxw
Показать решение

Задача 18

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

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

        F
1 1 0   0
1     1 0
    0 1 0

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

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

    F
1 0 0

тогда 1-му столбцу соответствовала бы переменная y, а 2-му столбцу — переменная x. В ответе следовало бы написать: yx.

Решение
Ответ: wyzx
Показать решение

Задача 19

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

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

        F
1   0   0
  0   0 0
  0 1   0

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

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

    F
1 0 0

тогда 1-му столбцу соответствовала бы переменная y, а 2-му столбцу — переменная x. В ответе следовало бы написать: yx.

Решение
Ответ: zxyw
Показать решение

Задача 20

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

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

        F
0 1     0
    1 0 0
1   0   0

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

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

    F
1 0 0

тогда 1-му столбцу соответствовала бы переменная y, а 2-му столбцу — переменная x. В ответе следовало бы написать: yx.

Решение
Ответ: ywzx
Показать решение
Показать еще

Теория для 2 задания ЕГЭ по информатике


Основная тема задания №2 — алгебра логики. С неё и начнём. Для успешного решения номера вам важно знать 3 теоретических момента:

  1. Основные логические операции
  2. Порядок логических операций
  3. Законы логики

Основные логические операции

1. Инверсия «НЕ»
Логическое отрицание
Обозначения: ¬А, Ā
Меняет значение на противоположное

Таблица истинности для инверсии
Таблица истинности для инверсии

2. Конъюнкция «И»
Логическое умножение
Обозначения: А∧В, А & В, А и В, AB
Принимает значение «истина», когда все значения единицы.
Хотя бы один 0 обнуляет всё.

Таблица истинности для конъюнкции
Таблица истинности для конъюнкции

3. Дизъюнкция «ИЛИ»
Логическое сложение
Обозначения: А∨В, А | В, А или В
Принимает значение «истина», когда хотя бы одна единица. «Ложь», когда все нули.

Таблица истинности для дизъюнкции
Таблица истинности для дизъюнкции

4. Импликация "Если, то"
Следование
Обозначения: А→В, А => В
Из истины следует истина, из лжи что угодно

Таблица истинности для импликации
Таблица истинности для импликации

5. Эквивалентность «Равны»
Тождество
Обозначения: А≡В, А <=> В
Иcтина, когда значения одинаковы. Ложь, когда различны

Таблица истинности для эквивалентности
Таблица истинности для эквивалентности

Порядок логических операций

  1. Действия в скобках
  2. Инверсия
  3. Конъюнкция
  4. Дизъюнкция
  5. Импликация
  6. Эквивалентность

Законы логики

Законов логики существует огромное количество, но именно для ЕГЭ достаточно знать 10 законов из данной таблицы. Некоторые из них очевидные, некоторые придётся выучить.

Законы логики
Законы логики

Практика

Основных вариантов решения два: логические рассуждения, либо построение таблицы истинности. Иногда проще решать первым методом, иногда вторым.

Первый метод. Логические рассуждения.

Пример:

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

Статистика выполнения задания 13 ЕГЭ по профилю по годам

Решение:

Итоговая функция всегда истинна для нашей таблицы (единички в значениях F). Заметим, что в последнюю очередь выполняются две конъюнкции, значение которых будет = 1 только тогда, когда значение каждого выражение равно 1.

Вывод:
y = 1
(x → z) = 1
¬w = 1,а значит w = 0

y всегда 1, такой столбик лишь один: y — переменная 4
w всегда 0, такой столбик лишь один: w — переменная 2

Для x и z остаётся переменная 1 и переменная 3. Осталось определится с порядком.
(x → z) = 1, значит не может быть набора, когда x = 1, а z = 0.
Во второй строчке перем1 = 1, а перем3 = 0. Следовательно, z — переменная 1, x — переменная 3.

z — переменная 1
w — переменная 2
x — переменная 3
y — переменная 4
Ответ: zwxy

Второй метод. Таблица истинности

Пример:

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

Решение:

Итоговая функция всегда равна нулю. Между скобками дизъюнкция, значит обе скобки должны быть ложными. Рассмотрим каждую скобку отдельно:

y → w = 0

¬x ∧ z = 0

Объединяем все переменные в одну таблицу:

Соотносим её с таблицей из условия:
y — переменная 4
w — переменная 2
x — переменная 1
z — переменная 3
Ответ: xwzy

Готовим к ЕГЭ на 85+ баллов и побеждаем лень

Каждый месяц 12 онлайн-занятий в дружелюбной атмосфере + 16 домашних работ с жесткими сроками.
Не готовишься — вылетаешь.

Подробнее о курсе