LogEqSolver

Программа для решения систем логических уравнений (23 задание ЕГЭ по информатике)

• Описание
• Инструкция
• Запуск
• Алгоритм работы
• Примеры

---

Описание

Скрипт для решения систем логических уравнений. Позволяет вывести все наборы решений и их количество.

Инструкция

Для работы программы нужно выписать все уравнения системы. Каждое уравнение задается на новой строке. Пример:

(x1 * y1) = (!x2 + !y2)
(x2 * y2) = (!x3 + !y3)
(x3 * y3) = (!x4 + !y4)
(x4 * y4) = (!x5 + !y5)
(x5 * y5) = (!x6 + !y6)

Для задания логических операций используйте следующие символы:

• ! Отрицание
• + Дизъюнкция
• * Конъюнкция
• = Эквивалентность
• - Импликация

Запуск

Для работы с программой введите следующую команду в консоли

python LogSystems.py path

где path путь до файла с системой

Также вы можете импортировать библиотеку в python файле

from LogSystems import *

s = LogSystems(path) # path - путь до файла с системой
s.solve()

Алгоритм работы

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

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

Примеры

Все примеры взяты с сайта К.Полякова

((x1 - x2) - (x3 - x4)) = 1
((x3 - x4) - (x5 - x6)) = 1
# ответ: 40

(x1 * y1) = (!x2 + !y2)
(x2 * y2) = (!x3 + !y3)
(x3 * y3) = (!x4 + !y4)
(x4 * y4) = (!x5 + !y5)
(x5 * y5) = (!x6 + !y6)
# ответ: 54

((x1 = x2) + (x3 = x4)) * ( !((x1 = x2) - (x3 = x4))) = 1
((x5 = x6) + (x7 = x8)) * ( !((x5 = x6) - (x7 = x8))) = 1
((x1 = x2) + (x7 = x8)) * ( !((x1 = x2) - (x7 = x8))) = 1
((x5 = x6) + (x3 = x4)) * ( !((x5 = x6) - (x3 = x4))) = 1
(x9 = x10) = 1
# ответ: 32

(x1 + x2) * ((x1 * x2) - x3) * (!x1 + y1) = 1
(x2 + x3) * ((x2 * x3) - x4) * (!x2 + y2) = 1
(x3 + x4) * ((x3 * x4) - x5) * (!x3 + y3) = 1
(x4 + x5) * ((x4 * x5) - x6) * (!x4 + y4) = 1
(x5 + x6) * ((x5 * x6) - x7) * (!x5 + y5) = 1
(x6 + x7) * ((x6 * x7) - x8) * (!x6 + y6) = 1
(x7 + x8) * (!x7 + y7) = 1
(!x8 + y8) = 1
# ответ: 61