Введение
Что такое таблицы истинности, логические функции и операции — всё, что встречается в задании №2 ЕГЭ по информатике, — разбираем в этой статье.
Термины, которые будем использовать:
Основные понятия
Единица в алгебре логики принимает значение «истина», а ноль — «ложь».
- Логическая функция — это функция, принимающая в качестве аргументов только единицы или нули и возвращающая одно из этих двух значений.
- Логическая операция — это простейшая логическая функция, [i]
- Логическая переменная — это переменная, принимающая значение 1 или 0, которая является аргументом логической функции.
- Таблица истинности — это таблица, заполненная 1 и 0, в каждой строке которой описана новая комбинация значений логических переменных и соответствующий ей результат логического выражения.
[i]
которую используют для построения сложных выражений. Например, в математике арифметические знаки («+», «-», «*», «/») используют для составления сложных уравнений. Такую же роль играют логические операции для функций.
[i]
[i]
Каждая логическая функция или операция имеет свою таблицу истинности. Рассмотрим самые популярные из них:
1. Отрицание (инверсия) [i]
Чаще всего в ЕГЭ встречается следующее обозначение: ¬A (читается «не А»). Но можно встретить также обозначение Ā.
Отрицание возвращает противоположное значение исходному, [i]
но так как значений всего два, то единица противоположна нулю, а ноль — единице.
Обрати внимание на таблицу истинности для этой логической операции:
| А | ¬A |
| 1 | 0 |
| 0 | 1 |
Слева обозначается значение логической переменной (значение аргумента для функции), а справа показан результат операции для текущих входных данных.
2. Логическое И (конъюнкция) [i]
Чаще всего в ЕГЭ встречается следующее обозначение: A∩B, читается «А и Б».
Конъюнкция возвращает истину только в том случае, если обе логические переменные принимают значения единицы, в противном случае она вернёт ложь. [i]
| A | B | A∩B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Для двух переменных количество всевозможных комбинаций равняется четырём.
3. Логическое ИЛИ (дизъюнкция) [i]
Чаще всего в ЕГЭ встречается следующее обозначение: A∪B, читается «А или Б».
Дизъюнкция возвращает ложь только в том случае, когда обе переменные принимают значения нулей, в остальных случаях она вернёт истину. [i]
| A | B | A∪B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Как отличить знаки конъюнкции и дизъюнкции
Над знаком ∩ (логическое И) можно поставить только одну букву И, а над знаком ∪ (логическое ИЛИ) можно разместить сразу две.
4. Импликация (следование) [i]
Чаще всего в ЕГЭ встречается следующее обозначение: A→B, читается «Из А следует Б» или «Если А, то Б».
Импликация вернёт ложь только тогда, когда из истины следует ложь, в остальных случаях она вернёт истину. [i]
| A | B | A→B |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Выражение A→B можно раскрыть как ¬A∪B, то есть вместо знака импликации перед первой переменной появляется отрицание, а между ними — логическое ИЛИ.
Это возможно благодаря тому, что таблица истинности для второго выражения совпадает с таблицей истинности для импликации, то есть обе функции при одинаковых входных данных вернут одинаковый результат.
Давай убедимся в этом и составим таблицу истинности в два шага. Сначала выполни операцию отрицание, потом раскрой логическое ИЛИ для каждой из четырёх комбинаций: 00, 01, 10, 11.
Проверь себя:
| А | B | ¬A | B | ¬A∪B |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
5. Эквивалентность (равносильность) [i]
Чаще всего в ЕГЭ встречается следующее обозначение: A≡B, читается «А эквивалентно Б» или «А равносильно Б».
Эквивалентность вернёт истину тогда, когда обе переменные имеют одинаковые значения, оба ложны или оба истинны, в противном случае вернёт ложь. [i]
| A | B | A≡B |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Сопоставление таблиц
Теперь, когда ты имеешь представление о таблицах истинности, мы освоим навык их сопоставления, который пригодится тебе в задании №2 ЕГЭ по информатике.
Тебе дана некоторая функция F (x, y, z) и таблица истинности для неё, в которой были пропущены значения. Твоя задача — заполнить пропуски нужными значениями и понять, какой столбик значений к какой переменной (x, y, z) относится:
| ? | ? | ? | F |
| 1 | 1 | ||
| 0 | 0 | 1 | |
| 0 | 1 |
При этом ты знаешь, что F (x, y, z) возвращает истину при следующих комбинациях:
| x | y | z | F |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
Сравнивать таблицы можно по строкам и столбцам, обрати внимание на вторую таблицу: в первом столбце 3 единицы, во втором — 1, в третьем — 2. А теперь смотри на первую таблицу. В какой столбик мы можем разместить 3 единицы? Только во второй, в остальных нам мешают нули. Значит, там расположена переменная x. Таблица примет вид:
| ? | х | ? | F |
| 1 | 1 | 1 | |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 |
Ты можешь и дальше практиковаться и смотреть по столбцам, чтобы прийти к правильному ответу, но давай попробуем посмотреть по строкам. В первой строке второй таблицы — 100, далее 101 и 111. Очевидно, что строка 111 может быть только первой, иначе нам мешают нули. Первый столбик полностью заполнен, в нём одна единица и два нуля. Значит, это переменная y. Таблица примет вид:
| y | х | ? | F |
| 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 |
Методом исключения последний столбик остаётся за переменной z. Проверь себя и определи, какое значение осталось пропущено.
Следуй этому плану, чтобы решить задание №2 ЕГЭ по информатике:
- Получи все возможные комбинации, при которых логическая функция возвращает истину или ложь.
- Для этого ты можешь написать программу либо проверить все комбинации вручную и найти подходящие.
- Сравни свою таблицу и данную в задании, заполни пропуски, используя алгоритм выше.
- Определи все переменные по заполненным значениям.
Примеры заданий
Задание 1
Миша заполнял таблицу истинности логической функции F = (x ∨ y) ∧¬(y ≡ z) ∧¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. [i]
| ? | ? | ? | ? | F |
| 1 | 1 | 1 | ||
| 0 | 1 | 0 | 1 | |
| 1 | 1 | 0 | 1 |
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. [i]
Получим следующие комбинации с помощью программы на Python:
print(«x y z w»)
for x in range(2):
for y in range(2):
for z in range(2):
for w in range(2):
if (x or y) and (not(y == z)) and (not w):
print(x, y, z, w)
Обращаем внимание на столбик из всех нулей, значит, w стоит в четвёртом столбце исходной таблицы. Переменная z может стоять только в первом столбце, потому что там одна единица. Все пропуски заполнены нулями. Смотрим на строки: только во второй строке одна единица и три нуля, значит, на месте единицы во втором столбце стоит y, третий столбец методом исключения — х.
Ответ: zyxw
Задание 2
Миша заполнял таблицу истинности логической функции F = ¬(x → y) ∨ (z ≡ w) ∨ z, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. [i]
| ? | ? | ? | ? | F |
| 0 | 0 | 0 | ||
| 1 | 0 | |||
| 1 | 0 | 0 |
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. [i]
Получим следующие комбинации с помощью программы на Python:
print(«x y z w»)
for x in range(2):
for y in range(2):
for z in range(2):
for w in range(2):
if not(not(x <= y) or (z == w) or z):
print(x, y, z, w)
Заметим, что все нули можно разместить в первый столбик, все единицы — в последний столбик, значит, первая переменная — z, последняя — w. В нашей таблице есть строка с 1 единицей — это первая строка исходной таблицы. Тогда в третьем столбце будет 010, что соответствует переменной x. Методом исключения второй столбец — это y.
Ответ: zyxw
Заключение
Теперь ты знаешь основную теорию для решения задания №2 ЕГЭ по информатике и обладаешь навыком сопоставления таблиц истинности.
