Задача к ЕГЭ по информатике на тему «частично заполненный фрагмент таблицы» №2

Логическая функция $F$ задаётся выражением $((x → y) ≡ (z → w )) ∨ (x ∧ w).$

Ниже представлен фрагмент таблицы истинности функции $F,$ содержащий неповторяющиеся строки, при которых функция $F$ ложна.

|----|----|----|----|---| |???-|???-|???-|???-|F--| |-1--|???-|???-|???-|-0-| |-1--|-1--|???-|???-|-0-| | 1 | 1 | 1 |??? | 0 | -------------------------

Определите, какому столбцу таблицы истинности функции $F$ соответствует каждая переменная $w,$ $x,$ $y,$ $z.$

Решениие руками

В приведенном фрагменте во всех строках $F = 0.$ Функция представляет из себя два операнда дизъюнкции. Так как дизъюнкция ложна, если ложны все высказывания, входящие в нее, то ( $(x → y) ≡ (z → w ))$ = 0 и $x ∧ w = 0.$

Если $((x → y) ≡ (z → w)) = 0,$ то одно из высказываний должно быть ложным, а другое истинным (так как операнды связаны между собой операцией эквивалентности). Каждый из операндов представляет собой импликацию, которая ложна, если из истины следует ложь, и истинна в остальных случаях.

Если $(x → y) = 0,$ то $x = 1,$ $y = 0,$ а $(z → w) = 1.$ Так как $x ∧ w = 0,$ а $x = 1,$ то $w$ должна быть ложна (так как конъюнкция ложна, если ложно хотя бы одно из высказываний, входящих в нее). Тогда чтобы $(z → w)$ была истинна, $z$ тоже должна быть ложна (иначе $1 → 0 = 0).$ Значит, в таком случае $x = 1, y = 0, w = 0, z = 0.$

Если $(x → y) = 1,$ то $(z → w) = 0.$ Значит, $z = 1, w = 0.$ Тогда $x ∧ w = x ∧ 0 = 0$ при любом $x.$ Составим таблицу истинности для $z = 1$ и $w = 0 :$

|--|--|--|---|--| |x-|y-|z-|w--|F-| |0-|0-|1-|0--|0-| |0 |1 |1 |0 |0 | |--|--|--|---|--| |1-|1-|1-|0--|0-| -1--0--1--0---1--

Из таблицы видим, что нам не подходит только последняя строка, так как при таких $x$ и $y$ эквивалентность истинна, следовательно, одно из выражений, входящих в дизъюнкцию, тоже истинно.

Мы разобрали все случаи, при которых функция ложна. Выпишем строки таблицы истинности, где $F = 0.$

|--|--|--|---|--| |x-|y-|z-|w--|F-| |0-|0-|1-|0--|0-| |0 |1 |1 |0 |0 | |1-|1-|1-|0--|0-| |--|--|--|---|--| -1--0--0--0---0--

Таблица 1.

Сопоставим таблицу 1 и фрагмент, приведенный в условии. Рассмотрим данную строку:

|--|--|--|---|--| |x |y |z |w |F | |--|--|--|---|--| -1--1--1--0---0--

В ней все переменные равны 1 и только $w = 0.$ В третьей строке фрагмента из условия тоже есть три единицы и один ноль. Значит, четвертый столбец — это $w.$

Аналогично и с этой строкой:

|x-|y-|z-|w--|F-| |--|--|--|---|--| -0--1--1--0---0--

Во второй строке фрагмента из условия тоже две единицы. Мы уже знаем, что четвертому столбцу соответствует $w,$ значит, третьему столбцу соответствует $x,$ который должен быть равен нулю.

Осталось определить первый и второй столбцы. В фрагменте таблицы истинности из условия первый столбец всегда равен единице. Если внимательно посмотреть на таблицу 1, то можно увидеть, что $z$ равна 1 в трех строках. Остальные переменные равны 1 в двух строках и менее. Значит, $z$ — это первый столбец фрагмента таблицы истинности из условия. Так как переменных всего 4, а три мы уже определили, то второй столбец — это $y.$

Решениие программой

print(’x y z w f’)
for x in range(2):
    for y in range(2):
        for z in range(2):
            for w in range(2):
                f = ((not(x) or y) == (not(z) or w)) or (x and w)
                if f == False:
                    print(x, y, z, w, f)

В результате работы программы получим следующую таблицу:

x y z w f

0 0 1 0 0

0 1 1 0 0

1 0 0 0 0

1 1 1 0 0

В первом столбце должно быть три единицы, значит это однозначно буква $z$ . Во втором столбце точно должно быть минимум две единицы, если посмотреть на строки, где $z$ истина, то на второе место однозначно подходит только $y$ . Так как в третьем столбце должна быть хотя бы одна единица, туда однозначно встаёт только $x$ . Ответ — zyxw.

Ответ: zyxw