Анализ таблиц истинности логических выражений
 Скачать 2.43 Mb.
|
Ещё пример задания:Р-20. Логическая функция F задаётся выражением ((x y) (y z)) ((x w) (w z)). На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Решение (построение таблицы истинности для F = 1): запишем выражение в более понятной форме:  попробуем найти все сочетания переменных, при которых функция равна 1 (их должно быть не очень много) при x = 0 получаем  ; импликация с нулём в левой части всегда истинна (из лжи следует всё, что угодно), поэтому  пусть теперь ещё z = 0, тогда  , что истинно при w = 1 и при любом y; пусть теперь x = 0 и z = 1, тогда  , что истинно при y = 1 и при любом w;из 4 и 5 получаем такие строки в таблице истинности исходной функции:
остаётся рассмотреть случай, когда x = 1, при этом  учитываем, что  и  ; получаем  преобразуем импликацию  , так что  для y = 0 это выражение истинно при (w, z) = (0,0), (0,1) и (1,0), а для y = 1 – только при w = z = 1, это даёт ещё 4 строки в таблице истинности
итак, у нас есть 8 строк в таблице истинности, где функция равна 1:
попробуем сопоставить их с заданными в условии строками:
замечаем, что есть одна характерная строка с тремя единицами; кроме того, поскольку все строки различны, в одной из пустых ячеек должен стоять 0, а во второй – 1 в полученной нами таблице видим единственную строку с тремя единицами, что сразу позволяет определить, что первый столбец – это x, который всегда равен 0:
теперь из оставшихся двух строк остаётся найти 2 строки, значения которых различаются только в одном столбце; под это условие подходит только пара двух верхних строк, они различаются в столбце y – из исходной таблицы видим, что это 4-й столбец также из исходной таблицы видим, что во втором столбце в этих двух строках единицы – это w, тогда третий столбец – это z Ответ: xwzy. Решение (А.Н. Носкин, построение таблицы истинности для F = 1): запишем выражение в более понятной форме: вынесем y за скобки: F = (y*(x+z) ≡ ((x→w)*(w→z)) F = 1, при 0=0 и 1=1. Тогда составим ТИ для левой части выражения равные 0 и 1.
Объединим эти таблицы, подключим переменную w и уберем из таблицы строки, при которых F=0 после подключения переменной w.
Получилось 8 всевозможных решений. Обратим внимание, что по условию у нас нет повторяющихся строк, но в таблице есть строки с тремя одинаковыми ячейками, тогда можно ДОЗАПОЛНИТЬ таблицу истинности исходной функции (желтая заливка) в одну из них вставив 0, в другую 1.
Анализ строк таблицы истинности исходной функции показывает: - строки, состоящей из четырех «1» нет, поэтому ее можно убрать (красная заливка); - только одна строка имеет в ячейках три единицы и один «0». И в ТИ всех решений (желтая заливка) этот «0» будет соответствовать Х в ТИ исходной функции.
Так как мы определили, что первый столбец соответствует Х и содержит только «0», то строки ТИ решений с «1» в столбце Х – удалим (синяя заливка)
и получим ТИ меньшего размера.
Анализ столбцов ТИ исходной функции показывает, что одна «1» в третьем столбце соответствует Z, а в третьей строке ТИ исходной функции две неизвестные переменные противоположны «0» и «1», что соответствует W и Y, так как X и Z уже определены и равны «0» (зеленая заливка)
Ответ: xwzy. Решение (построение таблицы с помощью программы, Б.С, Михлин) print('x y z w') # заголовок таблицы k = 0, 1 # k - кортежконстант (0 - False, 1 - True) for x in k: for y in k: for z in k: for w in k: if (x and y or y and z) == ((not x or w) \ and (not w or z)): # можнокороче: # if ( x * y or y * z ) == ( x <= w)*( w <= z): # '*' вместо ‘and’ print(x, y, z, w) # если F = 1 |