Как составить таблицу истинности в питоне

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

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

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

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

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

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

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

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

и таблицу

Требуется выяснить, какая переменная в таблице обозначена как «переменная 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 г.

If you don’t mind providing the number of variables of the function (I think it is possible to get but I don’t know how at this moment). I have the following:

from itertools import product
B = {0,1}
varNames= ["r","s","t","u","v","w","x","y","z"]

def booltable(f,n):
    vars = varNames[-n:]
    header = vars + ["f"]
    table = [*reversed([*map(lambda input: [*input,f(*input)], product(B,repeat=len(vars)))])]
    return [header] + table

If you want to have your 1’s at the top (like I do), just reverse the answer.

return [*reversed([*map(lambda input: [*input,f(*input)],product(B,repeat=len(vars)))])]

Here is an example of how to use it, functions are defined using bitwise operations.

• x | y — bitwise or of x and y
• x ^ y — bitwise exclusive or of x and y
• x & y — bitwise and of x and y
• ~x — the bits of x inverted

# Example function
def aBooleanFunction(x,y,z):
    return (x | y) ^ ~(x ^ z) % 2
    
# Run
display(booltable(aBooleanFunction,3))

The output is:

[['x', 'y', 'z', 'f'],
 [1, 1, 1, 0],
 [1, 1, 0, 1],
 [1, 0, 1, 0],
 [1, 0, 0, 1],
 [0, 1, 1, 1],
 [0, 1, 0, 0],
 [0, 0, 1, 0],
 [0, 0, 0, 1]]

You can then parse this to a table in whatever format you want using, for example, tabulate.

Чтобы не парсить выражение, можно привлечь Питон вычислять введённую функцию и заполнять таблицу истинности. Для этого завести класс, который будет представлять переменные в выражении, и у него переопределить соответствующие операторы. А дальше инициализировать переменные всеми возможными значениями и получать результат введённой функции для каждого набора значений переменных при помощи штатной функции eval().

import re

class BoolVar:
    def __init__(self, value):
        self.value = value
        #print("INIT =", value)

    # '-' — возражения "нет"
    def __neg__(self):
        return BoolVar(not self.value)

    # '+' — дизъюнкция "или"
    def __add__(self, other):
        return BoolVar(self.value or other.value)

    # '*' — конъюнкция "и"
    def __mul__(self, other):
        return BoolVar(self.value and other.value)

    # '>' — импликация "если ..., тогда"
    def __gt__(self, other):
        return BoolVar((not self.value) or other.value)

    # '=' — эквивалентность "ровно"
    def __eq__(self, other):
        return BoolVar(self.value == other.value)
    
    # строковое представление значения
    def __str__(self):
        return "True" if self.value else "False"

    def __format__(self, format_spec):
        return format(str(self), format_spec)

infunc = input('Enter your function: ')
# в питоне знак эквивалентности - это '==', так что заменяем
infunc = infunc.replace("=", "==")
# находим переменные в функции, т.е. просто буквы
# set() делает этот набор уникальным, ну и сортируем
variables = sorted(set(re.findall(r"[A-Za-z]", infunc)))
# или так, если надо без использования регулярных выражений
# variables = sorted(set([c for c in infunc if c.isalpha()]))

# просто красивое оформление для таблицы
header = [""]*2
for key in variables:
    header[0] += "-"*7 + "+"
    header[1] += f"   {key}   |"
header[0] += "-+" + "-"*7
header[1] += " | Result"
print("n".join(header + header[0:1]))
    
vars_for_eval = {}
# вариантов входных значений для таблицы - 2 в степени кол-ва переменных
for variant in range(1 << len(variables)):
    # заполняем входной словарь c представлением переменных 
    # в виде экземпляров нашего класса для функции eval()
    # key идут в прямом порядке, а i - в обратном
    for i, key in reversed(list(enumerate(reversed(variables)))):
        # используем биты этого числа для инициализыции булевых значений 
        vars_for_eval[key] = BoolVar(variant & (1 << i))
        # вывод строки таблицы истинности
        print(f" {vars_for_eval[key]:<5}", end=" |")
    # вычисляем результат
    result = eval(infunc, {}, vars_for_eval)
    print(f" | {result:<5}")

print(header[0])

Оно даже чего-то считает:

D:ProgrammingPython1>python bools.py
Enter your function: a+b
-------+-------+-+-------
   a   |   b   | | Result
-------+-------+-+-------
 False | False | | False
 False | True  | | True
 True  | False | | True
 True  | True  | | True
-------+-------+-+-------

D:ProgrammingPython1>python bools.py
Enter your function: -x=y
-------+-------+-+-------
   x   |   y   | | Result
-------+-------+-+-------
 False | False | | False
 False | True  | | True
 True  | False | | True
 True  | True  | | False
-------+-------+-+-------

D:ProgrammingPython1>python bools.py
Enter your function: -p+(p*q)=q
-------+-------+-+-------
   p   |   q   | | Result
-------+-------+-+-------
 False | False | | False
 False | True  | | True
 True  | False | | True
 True  | True  | | True
-------+-------+-+-------

Кстати, программу заодно можно использовать как калькулятор.

D:ProgrammingPython1>python bools.py
Enter your function: 55*23-16**5//16
-+-------
 | Result
-+-------
 | -64271
-+-------

Вероятно, вы хотите сделать что-то вроде этого:

from itertools import product
for p in product((True, False), repeat=len(variables)):
    # Map variable in variables to value in p
    # Apply boolean operators to variables that now have values
    # add result of each application to column in truth table
    pass

Но внутренняя часть цикла for — самая сложная часть, поэтому удачи.

Это пример того, что вы будете перебирать в случае трех переменных:

>>> list(product((True, False), repeat=3))
[(True, True, True), (True, True, False), (True, False, True), (True, False, False), (False, True, True), (False, True, False), (False, False, True), (False, False, False)]