Анализ таблиц истинности логических выражений
Скачать 2.43 Mb.
|
Пример задания:Р-22 (демо-2021). Логическая функция F задаётся выражением (x y) ¬(y z) ¬w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Решение (построение таблицы истинности для F = 1): перепишем выражения в виде поскольку имеем логическое произведение значение w обязательно должно быть равно 0, то есть, в столбце w таблицы должны быть все нули; это возможно только в последнем столбце:
теперь определим все комбинации переменных, для которых функция равна 1 (их не должно быть много!) чаще всего в выражении встречается переменная y, поэтому мы сначала примем y = 0, а затем – y = 1. при y = 0 (и w = 0) получаем , что справедливо только при x = 1и z = 1:
при y = 1 (и w = 0) получаем , что справедливо при z = 0 и любом x, это даёт ещё два варианта:
объединим три полученных строки:
видим, что в столбце z должна быть одна единица и два нуля, это возможено только в первой строке исходной таблицы:
при z = 1нужно, чтобы y = 0, поэтому второй столбец – это y, а третий – x:
Ответ: zyxw. Решение (построение таблицы с помощью электронных таблиц, П.Е. Финкель, г. Тимашевск) поскольку во время компьютерного экзамена есть возможность использовать электронные таблицы, можно построить таблицу истинности с их помощью заполняем первую часть таблицы, перечисляя все комбинации переменных в порядке возрастания двоичного кода: для каждой строчки определяем выражения, входящие в логическое произведение, а затем – значение функции: сортируем строки таблицы по столбцу H по убываниию: удаляем строки, где функция равна 0; можно также скрыть вспомогательные столбцы E, F, G: дальше рассуждаем так же, как и при теоретическом решении Ответ: zyxw. Решение (построение таблицы с помощью программы, А.С. Гусев, г. Москва, https://youtu.be/RRL1Wal9ImU): поскольку во время компьютерного экзамена есть возможность использовать среды программирования, для построения частичной таблицы истинности (всех строк, при которых F=1) можно написать переборную программу на Python перебор выполняем во вложенном цикле: for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: # вычисление функции F # вывод (x, y, z, w), если F=1 для вычисления значения функции необходимо понимать, как логические операторы записываются на языке программирования; в Python их можно реализовать следующим образом: ∧ конъюнкция and для языков, где логическое значение True воспринимается как 1, а False – как 0, можно использовать обычное умножение * ∨ дизъюнкция or ¬ отрицания not() ≡ тождество == ⊕ строгая дизъюнкция != → импликация – для импликации в python оператора нет, но импликацию можно преобразовать в дизъюнкцию; например, a → b можно записать как ¬a ∨ b, а это в свою очередь записать как not(a)or b, not a or b или a <= b Запишем нашу функцию на языке программирования: F = (x or y) and not(y == z) and not(w) чтобы выводить не полную таблицу истинности, а только те строки, в которых функция равна 1, добавим условие вывода: if F: # то же самое, что "if F == True:" print(x, y, z, w) Приведём полную программу: print('x y z w') for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: F = (x or y) and not(y == z) and not(w) if F: print(x, y, z, w) после запуска программы получаем все интересующие нас строки: x y z w 0 1 0 0 1 0 1 0 1 1 0 0 дальше рассуждаем так же, как и в приведённом выше теоретичеком решении Ответ: zyxw. Решение (прямой перебор, А. Богданов): в принципе, можно написать программу, которая сразу выдает решение этого задания прямым перебором вариантов Часть 1: https://www.youtube.com/watch?v=yX5oSYtM5E0 Часть 2: https://www.youtube.com/watch?v=eSkrt4KrsmU Ответ: zyxw. |