Бесплатный интенсив по информатике
3 огненных вебинара, домашние задания, беседа курса, личный кабинет, связь с преподавателем и
многое другое.
Курс стартует 6 ноября.
Подробнее об интенсиве
Задание 2. Алгебра логики. Таблицы истинности. ЕГЭ 2025 по информатике
Средний процент выполнения: 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.
Или при помощи программы на С++:
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
bool f(int A, int B, int C, int D, int E, int F){
return (!(!A || F) && B && !C && (!D || E));
}
int main() {
int count = 0;
for (int A = 0; A <= 1; ++A)
for (int B = 0; B <= 1; ++B)
for (int C = 0; C <= 1; ++C)
for (int D = 0; D <= 1; ++D)
for (int E = 0; E <= 1; ++E)
for (int F = 0; F <= 1; ++F)
if (f(A, B, C, D, E, F) == false)
count++;
cout << count;
return 0;
}
Ответ: 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.
Задача 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.
Задача 4
Логическая функция 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-му столбцу; затем букву, соответствующую последнему столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение
Строим таблицу истинности для логической функции любым способом и находим наборы, при которых функция ложна. Например, при помощи программы:
bool f(int x, int y, int z, int w){
return (((x && z) || !x) && !w && y);
}
int main() {
cout << "x y z w F" << endl;
for (int x = 0; x <= 1; ++x)
for (int y = 0; y <= 1; ++y)
for (int z = 0; z <= 1; ++z)
for (int w = 0; w <= 1; ++w)
if (f(x, y, z, w) == true)
cout << x << " " << y << " "
<< z << " " << w << " " << f(x, y, z, w) << endl;
return 0;
}
Получили наборы:
x y z w F
0 1 0 0 1
0 1 1 0 1
1 1 1 0 1
Начинаем сопоставление с исходной тбалицей:
1) столбец без единиц четвёртый в таблице из условия - это W
2) столбец с одной единицей третий в исходной таблице - это X
3) столбей с тремя единицами - это Y
4) столбец с двумя единицами - это Z
Результат: YZXW
Задача 5
Логическая функция 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-му столбцу; затем букву, соответствующую последнему столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение
Строим таблицу истинности для логической функции любым способом и находим наборы, при которых функция ложна. Например, при помощи программы:
bool f(int x, int y, int z, int w){
return ((!y || w) || (!x && z));
}
int main() {
cout << "x y z w F" << endl;
for (int x = 0; x <= 1; ++x)
for (int y = 0; y <= 1; ++y)
for (int z = 0; z <= 1; ++z)
for (int w = 0; w <= 1; ++w)
if (f(x, y, z, w) == false)
cout << x << " " << y << " "
<< z << " " << w << " " << f(x, y, z, w) << endl;
return 0;
}
Получили наборы:
x y z w F
0 1 0 0 0
1 1 0 0 0
1 1 1 0 0
Начинаем сопоставление с исходной тбалицей:
1) столбец без единиц второй в таблице из условия - это W
2) столбец с одной единицей третий в исходной таблице - это Z
3) столбей с тремя единицами - это Y
4) столбец с двумя единицами - это X
Результат: xwzy
Задача 6
Дан фрагмент таблицы истинности выражения 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 строк таблицы удовлетворяют заданному выражению.
Задача 7
Логическая функция 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.
Или при помощи программы на С++:
Выводим только ложные наборы, потому что их меньше
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
bool f(int x, int y, int z){
return ((x || y) && (!z || y));
}
int main() {
cout << "x y z F" << endl;
for (int x = 0; x <= 1; ++x)
for (int y = 0; y <= 1; ++y)
for (int z = 0; z <= 1; ++z)
if (f(x, y, z) == false)
cout << x << " " << y << " "
<< z << " " << f(x, y, z) << endl;
return 0;
}
Задача 8
Логическая функция 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.
Решение
Задача 9
Логическая функция 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.
