desktop/inf.jpg mobile/inf.jpg

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

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

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

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

Задача 1

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

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

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

Решение

Заметим, что все скобки и выражения связаны конъюнкцией, для которой сложно получить единицу. Поэтому будет решать от обратного. Посчитаем количество наборов, когда выражение истинно, тогда:

¬(A → F) = 1, тогда $A → F = 0$, следовательно, A = 1, F = 0.

B = 1.

¬C = 1, значит C = 0.

(D → E) = 1, тогда возможно 3 варианта: D = 0, E = 0; D = 0, E = 1; D = 1, E = 1.

Перемножим количество подходящих значений для каждой переменной: A, B, C, F - по одному набору, D и E - 3 набора. Итого:

1 х 3 = 3 набора, для которых вся функция истинна. Но нам нужно, чтобы функция была ложна. Найдём общее количество наборов по формуле $k = 2^N$, где N - количество переменных. У нас 6 переменных, значит всего наборов 64. Из них 3 нам не подходят. Тогда количество подходящих (ложных) наборов:

64 - 3 = 61.

Ответ: 61.

Ответ: 61
Показать решение
Полный курс

Задача 2

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

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

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

Решение

В первой скобке 2 переменных, значит для неё будет 4 набора. Поскольку переменные соединяются дизъюнкцией, выражение ложно ровно в одном случае, а в трёх оставшихся - истинно.

Во второй скобке 3 переменных, значит для неё будет 8 наборов. Поскольку переменные соединяются дизъюнкцией, выражение ложно ровно в одном случае, а в семи оставшихся - истинно.

Конъюнкция ложна, когда хотя бы одна скобка ложна. Рассмотрим 3 случая:

Первая скобка ложна, вторая истинна. Первая скобка ложна в 1 случае из 4, вторая истинна в 7 случаях из 8. Итого 7 · 1 = 7.

Первая скобка истинна, вторая ложна. Первая скобка истинна в 3 случаях из 4, вторая ложна в 1 случае из 4. Итого 1 · 3 = 3.

Первая скобка ложна, вторая ложна. Первая скобка ложна в 1 случае из 4, вторая ложна в 1 случае из 8. Итого 1 · 1 = 1.

Суммарно: 7 + 3 + 1 = 11.

Ответ: 11.

Ответ: 11
Показать решение
Полный курс

Задача 3

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

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

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

Решение

В первой скобке 3 переменных, значит для неё будет 8 наборов. Поскольку переменные соединяются конъюнкцией, выражение истинно ровно в одном случае, а в семи оставшихся - ложно.

Во второй скобке 2 переменных, значит для неё будет 4 набора. Поскольку переменные соединяются конъюнкцией, выражение истинно ровно в одном случае, а в трёх оставшихся - ложно.

Дизъюнкция истинна, когда хотя бы одна скобка истинна. Рассмотрим 3 случая:

Первая скобка ложна, вторая истинна. Первая скобка ложна в 7 случаях из 8, вторая истинна в 1 случае из 4. Итого 7 · 1 = 7.

Первая скобка истинна, вторая ложна. Первая скобка истинна в 1 случае из 8, вторая ложна в 3 случаях из 4. Итого 1 · 3 = 3.

Первая скобка истинна, вторая истинна. Первая скобка истинна в 1 случае из 8, вторая истинна в 1 случае из 4. Итого 1 · 1 = 1.

Суммарно: 7 + 3 + 1 = 11.

Ответ: 11.

Ответ: 11
Показать решение
Полный курс

Задача 4

Дан фрагмент таблицы истинности выражения 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
Показать решение
Полный курс

Задача 5

Логическая функция 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
Показать решение
Полный курс

Задача 6

Логическая функция 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
Показать решение
Полный курс

Задача 7

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

Решение
Ответ: 32
Показать решение
Полный курс

Задача 8

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

Решение
Ответ: 16
Показать решение
Полный курс

Задача 9

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

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

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

Решение
Ответ: 15
Показать решение
Полный курс

Задача 10

Логическая функция 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
Показать решение
Полный курс

Задача 11

Логическая функция 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
Показать решение
Полный курс

Задача 12

Логическая функция 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
Показать решение
Полный курс

Задача 13

Логическая функция 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
Показать решение
Полный курс

Задача 14

Логическая функция 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
Показать решение
Полный курс

Задача 15

Логическая функция 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
Показать решение
Полный курс

Задача 16

Логическая функция 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
Показать решение
Полный курс
Показать еще

Теория для 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 домашних работ с жесткими сроками.
Не готовишься — вылетаешь.

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