НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

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

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

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

Программа 4.2

Т true ; T истина

A true if ; А истина если

Х true and ; X истина И

Y true ; Y истина

В true if ; В истина если

(either X true or Y true); (X истина ИЛИ Y истина)

С true if ; С истина если

(either X true or Y false ; (X истина ИЛИ Y ложь)

F false ; F ложь

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

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

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

Т Т

No (more) answers

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

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

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

Т X

X T

No (more) answers

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

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

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

Т X

X F

No (more) answers

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

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

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

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

Y val and ; Y значимо И

Z val and ; Z значимо И

nor (X true (Y Z) ; HE (X истина (Y Z))

X val if ; X значимо, если

(either X true or X ; (X истина ИЛИ Х ложь)

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:

Программа 4.3

Т true ; Т истина

A true (X Y) fi ; А истина (X Y), если

X true and ; X истина И

Y true ; Y истина

В true (X Y) if ; В истина (X Y), если

(either X true or Y ; (X истина ИЛИ Y ложь)

true)

С true (X Y) if ; С истина (X Y), если

X true (Y Z x) if ; X истина (Y Z x), если

X true (Y Z) and ; X истина (Y Z) И

x true ; x истина

X val if ; X значимо, если

(either X true or X ; (X истина ИЛИ Х ложь)

false)

X tab (Y Z x) if ; X таблица (Y Z x), если

(either X true (Y Z x) or X false (Y Z x)) ; (X истина (Y Z x) ИЛИ X ложь (Y Z x))

F false ; F ложь

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

Y val and ; Y значимо И

Z val and ; Z значимо И

not (X true (Y Z)) ; HE (X (Y Z)

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

X false (Y Z) and ; X ложь (Y Z) И

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.9

Упражнение 4.5

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

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

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru
Поможем с курсовой, контрольной, дипломной
1500+ квалифицированных специалистов готовы вам помочь