Анализ таблиц истинности логических выражений
 Скачать 2.43 Mb.
|
Ещё пример задания:Р-16. Логическая функция F задаётся выражением (x y ) (y z). Ниже приведён фрагмент таблицы истинности. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z?
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы. Решение: Выражение представляет собой логическое произведение имплкаций. Поэтому для его истинности обе импликации должны быть истинны. Расмотрим верхнюю строчку таблицы, где функция принимает значение 1. Здесь одна из переменных равна 0, а две другие равны 1. Нулю в этой строке может быть равна только переменная x, так как при y = 0 получаем (1 0 ) (0 1) = 0 1 = 0 а при z = 0 имеем (1 1 ) (1 0) = 1 0 = 0, то есть эти два варианта не подходят. Таким образом, второй стоблец – x. Теперь рассматриваем вторую строку, где мы должны получить 0. Мы уже знаем, что второй столбец – x, поэтому во второй строке x = 0, и (0 y ) (y z) = 0. Первая импликация 0 y = 1 независимо от значения y. Поэтому для того, чтобы все выражение было равно 0, нужно обеспечить y z = 0. Это условие сразу даёт y = 1 и z = 0. Поэтому третий столбец – y, а первый – z. Ответ: zxy. Ещё пример задания (М.В. Кузнецова):Р-15. Логическая функция F задаётся выражением (x ¬y ¬z) (¬x y). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z?
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Решение (М.В. Кузнецова, через СКНФ и сопоставление таблиц истинности): Запишем заданное выражение в более простых обозначениях:  Функция задана в виде КНФ (конъюнктивной нормальной формы), которую можно привести к СКНФ, используя известные тождества алгебры логики:  ,  и распределительный закон для операции «И»  . Вторую дизъюнкцию дополним недостающей переменной z:  СКНФ:  Каждая дизъюнкция в СКНФ соответствует строке таблицы истинности, в которой F=0. Используя полученную СДНФ, делаем вывод: в таблице истинности имеется 3 строки, где F=0, заполним их:
В таблице, приведенной в задании, рассмотрим строки, где F=0:
Сравнивая столбцы этих таблиц, делаем выводы: во втором (синем) столбце таблицы задания находится y (одна единица), в первом (жёлтом) столбце таблицы задания находится z (в двух строках z=y), в последнем (зелёном) столбце таблицы задания находится x (где z=y, там x=¬y). Ответ: zyx. Решение (Л.Л. Воловикова, через уравнение): Так как между скобками стоит операция И, решим уравнение:  Чтобы функция была равна 1, нужно чтобы каждая скобка была равна 1. Уравнение  имеет 3 решения:
Подставим найденные решения в первую скобку и найдем полный набор решений уравнения:
Сопоставляем найденное решение со строками исходной таблицы, в которых функция F=1:
Есть одна строка, где две переменных равна 1, а одна – нулю, это строка 3 в последней таблице и строка 4 в предпоследней, поэтому первый столбец соответствует z Далее видим, что в столбце у в предпоследней таблице три единицы, а в последней таблице три единицы только во втором столбце, поэтому второй столбец – y, а третий – x. Ответ: zyx. |
