Питон и таблицы истинности

 

Хотите готовиться со мной к ЕГЭ?
Пишите:  ydkras@mail.ru
Немного обо мне.

 

Таблица истинности - это таблица, где перечисляются комбинации аргументов некой логической функции и указывается, какие значения принимает эта функция.

В задаче 2 ЕГЭ по информатике требуется 1) уметь строить таблицы истинности логического выражения и 2) уметь сравнивать построенную таблицу истинности с таблицей, приведенной в условии задачи.

Первый пункт можно выполнить на компьютере, написав несложную (менее 10 строк) программу на Питоне. 

Вообще говоря, в Питоне, как и в паскале, есть специальные логические значения True и False. Но в логических выражениях можно использовать и числа. При этом значение 0 считается ложью, а всё, отличное от нуля - истиной. (Тут создатель Питона позаимствовал идею из С.)

Рассмотрим задачу с сайта "Решу ЕГЭ". В ней требуется сопоставить переменные, входящие в логическую функцию

((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y))

и таблицу

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

Требуется выяснить, какая переменная в таблице обозначена как "переменная 1", "переменная 2" и т.д.

Из последнего столбца видно, что нам нужны те комбинации значений переменных, при которых функция ложна.

Так как в Питоне отсутствует логическая операция импликации, заменяем выражения вроде x → y на эквивалентные выражения not x or y. Операция эквивалентности - это сравнение "==".

Таким образом, наша функция 

((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y))

в Питоне выглядит так:

f =  ((not x or y ) and (not y or w)) or (z == ( x or y))

Чтобы перебрать все возможные комбинации переменных, записываем четыре вложенных цикла вида for x in range(2): (в них переменные принимают значения 0 и 1).

Печатаем строку значений x, y, z, w тогда, когда функция f ложна (т.е. if not f:)

Вот программа, которая вычисляет таблицу истинности и печатает строки значений 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 ) and (not y or w)) or (z == ( x or y))
                if not f: print(x,y,z,w)

Программа печатает следующую таблицу:

0 1 0 0
1 0 0 0
1 0 0 1
1 1 0 0

Столбцы слева направо - это значения переменных x, y, z, w соответственно.

Таким образом, мы очень упростили первую часть задачи - построение таблицы истинности. Осталась вторая часть.

В нашей таблице четыре строки, а в задаче - только три. Следовательно, одна строка в нашей таблице лишняя.

Заметим, что в таблице из задачи пять единиц, а в нашей таблице - шесть. Отсюда вытекают два вывода. Во-первых, мы не можем удалить из нашей таблицу строчку с двумя единицами - тогда у нас их останется четыре, т.е. менее, чем в таблице из задачи.  Во-вторых, при удалении из нашей таблицы строки с одной единицей и в нашей таблице, и в таблице из задачи будет по пять единиц. Следовательно, во всех пустых клетках таблицы из задачи записаны нули.

Самую первую строку из нашей таблицы удалить нельзя: тогда у нас появляется столбец из трёх единиц, а такого столбца в таблица из задачи нет. Убираем вторую строку и получаем следующую таблицу:

0 1 0 0
1 0 0 1
1 1 0 0

В столбце переменной z - только нули. Следовательно, в задаче переменная 3 - это z.

В столбце переменной w только одна единица. Следовательно, переменная w - это переменная 2 в задаче.

Замечаем, что когда переменная w (переменная 2 в задаче) равна 1, то равна 1 также и переменная x (а в задаче это переменная 4). Следовательно, переменная 4 - это x. Оставшаяся переменная 1 - это переменная y.

Итак, наш ответ - ywzx. Именно такой ответ и приводится в задаче.

При записи логических выражений в Питоне можно столкнуться с тем, что выражения вроде (x ≡ ¬z) при буквальном их переводе (x == not z) вызывают синтаксическую ошибку. Чтобы избежать этого, надо либо заключить выражение not z в дополнительные скобки, т.е. написать (x == (not z)). Можно также заменить операцию "равно" на "не равно", т.е. записать это выражение как (x != z).

(c) Ю.Д.Красильников, 2021 г.