Это задание проверяет умение оперировать логическими выражениями. Если знать основные правила логики, задача решается достаточно просто. Однако при решении вручную это может занять больше времени, чем предусмотрено, поэтому рекомендуется часть задания выполнять с помощью Python.
Пример задания
Логическая функция F задаётся выражением (x ∨ y) → (z ≡ x).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z.
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Анализ
Выражение (x ∨ y) → (z ≡ x) состоит из трёх переменных (x, y и z). Каждая переменная может принимать два значения: 0 или 1. Они все могут быть нулями одновременно, могут быть единицами, а могут принимать различные друг от друга значения. Следовательно, получится 8 возможных комбинаций. Если бы было 4 переменные, то общее количество комбинаций равнялось бы 16.
Решение
Шаг 1, вариант 1 - вручную составить таблицу истинности для функции F
Чтобы построить таблицу истинности, нужно знать, как работают логические операции. Для данного задания нужно знать 5 логических операций:
- Логическое ИЛИ (дизъюнкция)
- Логические И (конъюнкция)
- Равенство (эквивалентность)
- Следование (импликация)
- Отрицание (инверсия)
Для каждой операции существует своя таблица истинности:
Эти таблицы показывают какой результат дадут две переменные, если их связать при помощи логической операции. Например, для логического И потребуется, чтобы и первое и второе значения были истинными, то есть единицами.
Мы можем посмотреть на любую логическую операцию с бытовой точки зрения, приведя пример из жизни. Взять, например, логическое ИЛИ: "Ты пойдёшь гулять, если температура на улице ниже 0 ИЛИ выше 20.". Данное условие можно описать выражением: t < 0 v t > 20, где t – это температура.
Разобьём выражение на части и сведём всё в одну таблицу:
В частично заполненной таблице, данной в задании, результат функции равен нулю, поэтому из получившейся таблицы удаляем все те строки, где функция получилась равной 1. Основная мысль: исключить точно не подходящие строки.
Шаг 1, вариант 2 - программно составить таблицу истинности для функции F
Чтобы автоматизировать построение таблицы истинности, можно написать программу на Python. Для этого нужно правильно заменить логические операции:
- v превратится в or
- ^ превратится в and
- ≡ превратится в ==
- → превратится в <=
- ¬ превратится в not
В результате, программа выведет:
Получилось тоже самое, что при составлении вручную)
Шаг 2 - подбор значений
Переменная 1 – это точно x, так как единственный случай с двумя нулями – это вторая строка.
Посмотрим на вторую строку таблицы истинности функции F. Если Переменная 1 – это x, то Переменной 2 может быть только z, тогда Переменная 3 это y.
Ответ: xzy
__________________________________________________________________________________________
🎓 Хотите больше таких разборов?
Подписывайтесь на наш Telegram-канал и группу в ВК, где мы публикуем бонусные материалы для подготовки к экзаменам и для обучения программированию! 🚀