4.7. Получение таблиц истинности с помощью Пролога

Более мощными возможностями обладает приведенная ниже программа 4.2, позволяющая генерировать таблицы истинности для функций от двух переменных. Эта программа может быть, например, использована для проверки тождественности двух альтернативных форм представления какой-либо функции. В программе используется бинарное отношение X true (YZ) [X истина (YZ)] для проверки истинности функций.

Для демонстрации предлагаемого способа выбраны следующие функции: А = X*Y, В = X + Y и C = X + (для обозначения функций используются большие буквы, что позволяет отличать их от обозначений из табл. 4.8).

Т true ; T истина

F false ; F ложь

Ниже приведен пример использования данной программы:

& all (х у : A true (x у))

[Ответов (больше) нет]

Пролог-система выдает значения х и у, соответствующие только истинным значениям каждой заданной функции. Все остальные значения не рассматриваются. Для функций В и С получены ответы (ТХ, XT) и (ТХ, XF) соответственно. Символ X в ответе означает, что на его месте может находиться как F, так и Т. Таким образом, указанные две последовательности ответов означают, что функции В и С принимают значение истина на множествах значений аргументов (ТТ, TF, FT) и (ТТ, TF, FF) соответственно.

С помощью следующих дополнений в программу 4.2 можно получить множества значений аргументов, для которых функции А, В и С принимают значение ложь.

X false (Y Z) if ; X ложь (Y Z) если

false);

На следующие три вопроса:

1) all (х у : A false (x у)

[Определить все (х у : А ложь (х у))]

2) all (x у : В false (x у))

[Определить все (х у : в ложь (х у))]

3) all (x у : С false (x у))

[Определить все (х у : С ложь (х у))]

будут получены такие ответы:

1) T F

F T

F F

2) F F

3) F T

Заметим, что отношение val (значимо) служит для генерации всех возможных комбинаций значений входных переменных для последующей их проверки с помощью отношения false. Без этого отношения Пролог-система не смогла бы выдать ни одного ответа в тех случаях, когда значением заданных функций является ложь, и отвечала бы пользователю "No more answers ["Ответов больше нет"]. Читатель может убедиться в этом сам, удалив отношения val из программы и повторив запросы.

Можно получить таблицу истинности, ^содержащую не только значения двух переменных, но и соответствующие им значения функций. Определим новое отношение tab (таблица), построенное с помощью отношений true и false. Для этого расширим предыдущую программу и в результате получим программу 4.3:

Т true ; Т истина

x false ; x ложь

Ниже приведены ответы Пролог-системы на запросы, позволяющие получить таблицы истинности для функций А, В и С, включающие в себя третий столбец из значений функций:

1) all (х у z : A tab (x у z))

[Определить все (х у z : А таблица (х у z))]

2) all (х у z) : В tab (x у z))

[Определить все (х у z : В таблица (х у z))]

3) all (x у z) : С tab (x у z))

[Определить все (х у z : С таблица (х у z))]

1)Т Т Т

T F T

F T F

F F F

2) T X T

X T T

F F F

3)T X T

X F T

F T F

Можно убедиться, что полученные таблицы соответствуют функциям А, В и С. Символ X в ответах заменяет одновременно Т и F. Таким образом, строка с одним таким символом соответствует двум обычным строкам. Первые два столбца содержат значения переменных, а последний - значения функций.

Выше было показано, как можно с помощью Пролога исследовать некоторые не всегда очевидные свойства логических функций. В табл. 4.9 приведены уже рассмотренные выше правила алгебры логики.

Таблица 4.9

Упражнение 4.5

Запишите правила логики из табл. 4.9 с помощью операций AND, OR и NOT.

Напомним, что в процессе выполнения логических операций необходимо учитывать их приоритеты. В первую очередь выполняются операции в скобках, затем, в порядке убывания приоритетов, следуют NOT, AND, OR и (в логике) IMPLIES на одном уровне с IFF. С помощью скобок можно изменять порядок вычисления логических выражений. Поэтому, например, выражение p + q*r не равно (р + q)*r.