12.Операции логики высказываний
Необходимые сведения из математической логики приведены в книге [5]. В данном параграфе мы напишем интерпретатор формул логики высказываний LOGIC.
Программа LOGIC будет обрабатывать приказы двух видов:
1. определения формул,
2. вычисления формул.
Поскольку большие формулы всегда можно разбить на подформулы, предполагается, что каждый приказ подготавливается отдельной строкой.
Приказ определения формул имеет формат
e.n '=' e.0
где e.n - имя переменной, е.0 - формула логики высказываний.
В результате выполнения этого приказа запоминается определение формулы.
Приказ вычисления формул имеет формат
е.0
где е.0 - произвольная формула логики высказываний.
В результате выполнения этого приказа происходит вычисление формулы е.0 . Предполагается, что формула е.0 может содержать любые переменные.
Формула логики высказываний состоит из переменных, знаков операций, скобок и констант. Значения всех переменных по умолчанию предполагаются равными истине.
В качестве знаков логических операций выберем следующие:
.And. - конъюнкция,
.Or. - дизъюнкция,
.Imp. - импликация,
.Not. - отрицание.
Константу "истина" будем обозначать через "1", "ложь" - через "0".
Старшинство операций определим в следующем порядке: отрицание, конъюнкция, дизъюнкция, импликация. Впрочем, всегда можно использовать скобки.
Признаком конца приказов служит приказ
END
ПРИМЕР. Пусть мы хотим вычислить значение формулы
(а .And. (b .Or. с)) .Imp. ((а .And. b) .Or. (а .And. с))
при а = 0, b = 0, c = 1.
Тогда можно подготовить такие приказы:
F1 = A .And. (B .Or. C) F2 = (A .And. B) .Or. (A .And. C) F = F1 .Imp. F2 A = 0 B = 0 F END
B результате вычисления формулы F напечатается
= 1
Текст интерпретатора формул логики высказываний приведен в logic.ref.
Функция Wwod осуществляет ввод одной карты, убирание на ней всех пробелов, удобные для работы замены, а затем спаривание скобок.
Функции LOGIC и Begin организуют ввод приказов и проверку на окончание. Каждый приказ обрабатывается функцией Rab.
Выполнение приказа-определения заключается в закапывании под именем e.N формулы е.0.
Выполнение приказа-вычисления осуществляет функция Wich, которая анализирует формулу и строит функциональные термы для вычисления логических операций (функции Imp, Or, Amd, Not).
Предложение
(e.1) = <Wich e.1>;
осуществляет вхождение внутрь скобок.
Отметим, что все приказы-определения запоминаются и их можно использовать в дальнейшем. Например, для того, чтобы вычислить значение формулы из предыдущего примера, при а = 0, b = 0, c = 0, достаточно набрать приказы:
с=0
F
B результате будет напечатано:
= 1
Объясните, как происходит присвоение переменным значения "1" по умолчанию.
З А Д А Ч А. Напишите рефал-программу приведения формулы логики высказываний к конъюктивно и дизъюктивно нормальным формам.
З А Д А Ч А. Напишите функцию-предикат определения тождественной истинности формул логики высказываний.
З А Д А Ч А. Напишите функцию-предикат определения равносильности двух формул.
З А Д А Ч А. Расширьте возможности программы LOGIC. Например, добавьте возможность определения и вычисления логических функций от каких-то переменных.