Анализ таблиц истинности логических выражений
Скачать 2.43 Mb.
|
Ещё пример задания:Р-21. Логическая функция F задаётся выражением ((x ¬y) (w z)) (z x). На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Решение (построение таблицы истинности для F = 1): перепишем выражение, раскрыв импликацию по формуле : сначала предположим, что ; в этом случае получаем так как , получим ; при этом значение y может быть любым (1 или 0) теперь пусть , тогда получаем используем распределительный закон: , так что , откуда сразу следует и – единственный вариант! этот единственный вариант, для которого , ОБЯЗАТЕЛЬНО должен быть в приведённой таблице, потому что иначе мы не сможем различить столбцы z и x; это может быть только последняя строчка, куда нужно добавить две единицы:
в остальных строчках должно вполняться равенство , значит x – точно не второй столбец (не подходит вторая строка) предположим, что x – третий столбец, и в свободной ячейке – нуль:
при этом для остальных двух столбцов в этих строчках должно выполняться условие , а оно не может выполняться – при любом варианте в одной строке сумма равна 0; значит x – последний столбец, и в первой строке z = 1:
чтобы разобраться с поcледними двумя столбцами снова вспомним, что при должно выполняться условие ; это возможно только тогда, когда второй столбец – это y, а третий - w Ответ: zywx Решение (А.Н. Носкин, заполнение исходной ТИ и анализ полной таблицы истинности для F = 1): в выражении 4 логических переменных, тогда всех решений будет 16 (24).
подставим набор значений логических переменных и удалим все решения, которые не дают в ответе F = 1
Получаем 7 решений. Анализируя ТИ исходной функции видим, что набора 0 0 0 0 и 1 1 1 1 нет. Уберем их из ТИ решений.
В ТИ решений только одна строка имеет три нуля, тогда сравнивая с ТИ исходной функции видим, что 1 соответствует Y.
ДОЗАПОЛНИМ таблицу истинности исходной функции (желтая заливка) на основе анализа ТИ решений, а именно т.к больше строк с тремя «0» нет, то в первой строке в пустой ячейке будет «1». И раз нет больше строк с двумя «0», то в третьей строке пустые ячейки равны «1».
Анализируя 1ю строку выше приведенной таблице и ТИ решений видим, что строка с двумя «0» всего одна, из которых один нуль известен - это Y, тогда второй это – W;
Далее рассуждая видим, что в ТИ решений (кроме столбца Y) один «0» имеет – Х, тогда последний столбец – это Х, а первый столбец – Z. Ответ: zywx Решение (построение таблицы с помощью программы, Б.С, Михлин) print ('x y w z') # заголовок таблицы (в алфавитном порядке) k = 0, 1 # k - кортежконстант (0 - False, 1 - True) for x in k: for y in k: for w in k: for z in k: if (x and not y or (not w or z)) == (z == x): # можнокороче: # if (x and not y or (w <= z)) == (z == x): print(x, y, w, z) # если F = 1 |