Привет, друзья! Немного информатики вам в ленту. Частенько у моих учеников возникают трудности с самостоятельным выполнением задания, связанного с заполнением таблица истинности, когда пропущены некоторые значения, а еще неизвестно расположение входящих в функцию аргументов. Такие задачи встречаются в ЕГЭ по информатике и в МЦКО по информатике. Меня немного удивляет, что эти объемные задания стоят первыми (ну в начале же должны быть задачи попроще). Не то, чтобы эта задача какая-то сверх сложная. Тем не менее, объясняются они плохо (слишком кратко). А чтобы человек понял и научился решать такие задачи, нужно хотя бы пару раз разобрать решение очень подробно. Чем я сегодня и займусь, во всяком случае постараюсь сделать это максимально подробно.
Задача
Логическая функция F задаётся выражением ¬ (x ∧y) ∧ (y ∨ z) ∨ ¬w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение:
В нашей логической функции встречаются только операторы логического И (and, ∧ , &, *) и логического ИЛИ (or, |, ∨, +). Так как символы ∧ и ∨ многие путают, то мы немного упростим зрительное восприятие нашей функции, также вспомним таблицы истинности для этих двух операторов:
1. Сначала посмотрим на нашу функцию в общем виде. У нас есть 4 строчку таблицы. И во всех 4-х строчках функция F принимает значение 0. Если дизъюнкция принимает значение 0, это может случиться только в одном случае: когда оба операнда равна 0. Отсюда мы можем сделать определенный вывод, что w должна принимать только значение 1, а, судя по заполненности таблицы истинности, w может быть только во 2-м столбце.
2. Рассмотрим 1-ю строку. Итак, w = 1 и стоит во 2-м столбце. Рассмотрим все комбинации оставшихся чисел 1, 1, 0 для переменных x, y, z. Перебор и проверка этих вариантов дает нам следствие, что z может стоять только в 4-м столбце, т.к. должна принимать значение z = 0 для 1-й строки.
3. Рассмотрим 4-ю строку таблицы. Она наиболее заполнена, но заполнена только единицами. Переменная, которая стоит в 1-м столбце 4-й строки имеет неопределенное значение. Рассмотрение 4-й строки дает нам информацию о том, что в 1-м столбце этой строки должна стоять 1. Но это не дает нам никакой информации будет это x или y.
4. Рассматриваем 2-ю строку таблицы. Мы уже знаем, что z должна стоять в последнем столбце, но не знаем какое у нее должно быть значение. Поэтому перебираем оба случая: при z = 1 и при z = 0. Так как строки таблицы у нас уникальные по условию задачи, то:
Случай 1. при z = 0, в 3-м столбце не может стоять 0 (ибо возникнет совпадение с 3-й строкой таблицы). То есть, при z = 0, в 3-м столбце стоит 1. То есть x и y делят между собой значения 0 и 1. Мы должны перебрать эти варианты.
Случай 2. при z = 1, в 3-м столбце может быть как 0, так и 1. То есть строка не будет совпадать с другими строками. То есть мы уже должны перебрать три различных варианта xy = 00, xy = 01, xy = 11.
Рассмотрев все эти случаи, мы однозначно можем сказать, что нам подходит единственный набор: x = 1, y = 0, z = 0. Откуда мы делаем вывод, что y лежит в 1-м столбце, а x лежит в 3-м столбце.
Ответ: ywxz
Понравилась заметка? Поставьте лайк, подпишитесь на канал! Вам не сложно, а мне очень приятно :)
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram