Главная страница

Анализ таблиц истинности логических выражений


Скачать 2.43 Mb.
НазваниеАнализ таблиц истинности логических выражений
Дата16.03.2022
Размер2.43 Mb.
Формат файлаdoc
Имя файлаege2.doc
ТипДокументы
#399283
страница4 из 32
1   2   3   4   5   6   7   8   9   ...   32

Ещё пример задания:


Р-20. Логическая функция F задаётся выражением

((xy)  (yz))  ((xw)  (wz)).

На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

?

?

?

?

F

0

1

1

1

1

0

1

0




1

0

1

0




1

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Решение (построение таблицы истинности для F = 1):

  1. запишем выражение в более понятной форме:

  2. попробуем найти все сочетания переменных, при которых функция равна 1 (их должно быть не очень много)

  3. при x = 0 получаем ; импликация с нулём в левой части всегда истинна (из лжи следует всё, что угодно), поэтому

  4. пусть теперь ещё z = 0, тогда , что истинно при w = 1 и при любом y;

  5. пусть теперь x = 0 и z = 1, тогда , что истинно при y = 1 и при любом w;

  6. из 4 и 5 получаем такие строки в таблице истинности исходной функции:

    x

    y

    z

    w

    F

    0

    0

    0

    1

    1

    0

    1

    0

    1

    1

    0

    1

    1

    0

    1

    0

    1

    1

    1

    1

  7. остаётся рассмотреть случай, когда x = 1, при этом

  8. учитываем, что и ; получаем

  9. преобразуем импликацию , так что

  10. для y = 0 это выражение истинно при (w, z) = (0,0), (0,1) и (1,0), а для y = 1 – только при w = z = 1, это даёт ещё 4 строки в таблице истинности

    x

    y

    z

    w

    F

    1

    0

    0

    0

    1

    1

    0

    0

    1

    1

    1

    0

    1

    0

    1

    1

    1

    1

    1

    1

  11. итак, у нас есть 8 строк в таблице истинности, где функция равна 1:

x

y

z

w

F

0

0

0

1

1

0

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

1

0

1

0

1

1

1

1

1

1

попробуем сопоставить их с заданными в условии строками:

?

?

?

?

F

0

1

1

1

1

0

1

0




1

0

1

0




1

  1. замечаем, что есть одна характерная строка с тремя единицами; кроме того, поскольку все строки различны, в одной из пустых ячеек должен стоять 0, а во второй – 1

  2. в полученной нами таблице видим единственную строку с тремя единицами, что сразу позволяет определить, что первый столбец – это x, который всегда равен 0:

    x

    y

    z

    w

    F

    0

    0

    0

    1

    1

    0

    1

    0

    1

    1

    0

    1

    1

    0

    1

    0

    1

    1

    1

    1

  3. теперь из оставшихся двух строк остаётся найти 2 строки, значения которых различаются только в одном столбце; под это условие подходит только пара двух верхних строк, они различаются в столбце y – из исходной таблицы видим, что это 4-й столбец

  4. также из исходной таблицы видим, что во втором столбце в этих двух строках единицы – это w, тогда третий столбец – это z

  5. Ответ: xwzy.

Решение (А.Н. Носкин, построение таблицы истинности для F = 1):

  1. запишем выражение в более понятной форме:

  2. вынесем y за скобки: F = (y*(x+z) ≡ ((x→w)*(w→z))

  3. F = 1, при 0=0 и 1=1. Тогда составим ТИ для левой части выражения равные 0 и 1.

y

x

z

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0




y

x

z

1

0

1

1

1

0

1

1

1

  1. Объединим эти таблицы, подключим переменную w и уберем из таблицы строки, при которых F=0 после подключения переменной w.

    y

    x

    z

    w

    0

    0

    0

    1

    0

    1

    0

    0

    0

    1

    0

    1

    0

    1

    1

    0

    1

    0

    0

    1

    1

    0

    1

    0

    1

    0

    1

    1

    1

    1

    1

    1

  2. Получилось 8 всевозможных решений.

  3. Обратим внимание, что по условию у нас нет повторяющихся строк, но в таблице есть строки с тремя одинаковыми ячейками, тогда можно ДОЗАПОЛНИТЬ таблицу истинности исходной функции (желтая заливка) в одну из них вставив 0, в другую 1.

    ?

    ?

    ?

    ?

    F

    0

    1

    1

    1

    1

    0

    1

    0

    1

    1

    0

    1

    0

    0

    1

  4. Анализ строк таблицы истинности исходной функции показывает:

- строки, состоящей из четырех «1» нет, поэтому ее можно убрать (красная заливка);

- только одна строка имеет в ячейках три единицы и один «0». И в ТИ всех решений (желтая заливка) этот «0» будет соответствовать Х в ТИ исходной функции.

y

x

z

w

0

0

0

1

0

1

0

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

1

1

  1. Так как мы определили, что первый столбец соответствует Х и содержит только «0», то строки ТИ решений с «1» в столбце Х – удалим (синяя заливка)

y

x

z

w

0

0

0

1

0

1

0

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

1

1

и получим ТИ меньшего размера.

y

x

z

w

0

0

0

1

1

0

0

1

1

0

1

0




  1. Анализ столбцов ТИ исходной функции показывает, что одна «1» в третьем столбце соответствует Z, а в третьей строке ТИ исходной функции две неизвестные переменные противоположны «0» и «1», что соответствует W и Y, так как X и Z уже определены и равны «0» (зеленая заливка)

y

x

z

w

0

0

0

1

1

0

0

1

1

0

1

0




  1. Ответ: 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
1   2   3   4   5   6   7   8   9   ...   32


написать администратору сайта