Построение таблиц истинности логических выражений — задача ЕГЭ по информатике

Условие, ответ и разбор задачи

Построение таблиц истинности логических выраженийФИПИ

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

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

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

Перем. 1	Перем. 2	Перем. 3	Перем. 4	Функция
???	???	???	???	F
1	0	0	0	1
1	0	0	1	1
1	1	0	1	1

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

Пример. Если бы функция была задана выражением ¬x ∨ y, зависящим от двух переменных: x и y, и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция F истинна.

Перем. 1	Перем. 2	Функция
???	???	F
0	0	1
1	0	1
1	1	1

Тогда первому столбцу соответствовала бы переменная y, а второму столбцу –переменная x. В ответе следовало бы написать: yx.

Ответ:

Решение

Составим таблицу истинности для выражения w ∧ ¬y ∧ (¬z ∨ x), вручную или при помощи языка Python:

print("x y z w")
for x in range(0, 2):
    for y in range(0, 2):
        for z in range(0, 2):
            for w in range(0, 2):
                if w and not(y) and (not(z) or x):
                    print(x, y, z, w)

Далее выпишем те наборы переменных, при которых выражение истинно. В наборах переменные запишем в порядке x, y, z, w. Получим следующие наборы: (0, 0, 0, 1), (1, 0, 0, 1), (1, 0, 1, 1). Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности. В первом столбце нет нулей. Среди переменных во всех трёх наборах равна 1 только w. Следовательно, первый столбец соответствует переменной w. Во втором столбце ровно одна единица. Среди переменных равна 1 ровно в одном наборе только z. Следовательно, второй столбец соответствует переменной z. В третьем столбце нет единиц. Среди переменных во всех трёх наборах равна 0 только y. Следовательно, третий столбец соответствует переменной y. Тогда четвёртый столбец соответствует оставшейся переменной x. Ответ: wzyx. Приведём решение на языке Python.

from itertools import *
def f(x,y,z,w):
    return w and not y and (not z or x)
table = [(1,0,0,0), (1,0,0,1), (1,1,0,1)]
if len(table) == len(set(table)):
    for p in permutations('xyzw'):
        if [f(**dict(zip(p, r))) for r in table] == [1,1,1]:
            print(*p, sep='')

Построение таблиц истинности логических выражений — задача ЕГЭ по информатике

Похожие задачи