Смекни!
smekni.com

Логический анализ E-структур с помощью графов (стр. 1 из 3)

Логический Анализ E-структур с помощью графов


Использование графов и у-множеств при логическом выводе в E-структурах позволяет не только упростить процесс получения следствий, но и выполнить другие методы логического анализа рассуждений.

Первое, что сделаем – это представим рассуждение в виде ориентированного графа, в котором отношения включения между множествами представлены как дуги, соединяющие соответствующие литералы. При этом будем считать, что дуги могут быть любой длины и необязательно прямыми. Рассмотрим посылки из условного примера:

1) CÍ

;

2) TÍR;

3)

Í
.

Далее возьмем чистый лист бумаги и выпишем на некотором расстоянии друг от друга все базовые термины нашего рассуждения. При этом мы расположим термины в двух строках: в верхней строке будут все «позитивные» термины (C, S, T, R), а в нижней – все «негативные» термины (

,
,
,
). Кроме того, альтернативные (т.е. отрицающие друг друга) термины (например, S и
) мы расположим строго на одной вертикали. Затем соединим некоторые термины дугами в соответствии с нашими посылками. Тогда получим ориентированный граф, с помощью которого изображается исходная задача (рисунок 1).

Рис. 1Рис. 2


Теперь для каждой посылки мы построим новую дугу, которая будет изображать следствие, полученное с помощью правила контрапозиции. Наш граф дополнится еще тремя дугами (рисунок 2). Правила рисования контрапозиций для нашей схемы весьма просты и соответствуют некоторым принципам симметрии. Сформулируем эти правила:

1) если исходная дуга соединяет литералы в одной строке, то ее контрапозиция должна соединять противоположные литералы на другой строке, при этом дуга должна быть направлена в сторону, противоположную исходной дуге. Например, для дуги

®
мы по этому правилу получаем новую дугу R®S;

2) если исходная дуга наклонная (т.е. соединяет разные строки), то при построении ее контрапозиции мы соединяем линией противоположные литералы (например, для дуги C®

надо соединить линией литералы
и S). После этого надо выбрать такое направление линии (вверх или вниз), чтобы это направление совпадало с направлением исходной дуги. Например, пара литералов на схеме соединяется дугой S®
, так как в этом случае стрелка направлена вниз, так же как и исходная стрелка C®
на схеме.

Дуги со строго вертикальным направлением в нашем примере не появятся. Забегая вперед, отметим, что такие дуги, если они появляются в процессе логического вывода, говорят о том, что в нашем рассуждении содержится коллизия парадокса.

Теперь, когда получены все следствия по правилу контрапозиции, можно приступать к получению новых следствий по правилу транзитивности. Если использовать схему, то этот процесс существенно упрощается. Для этого надо просто построить все пути, содержащиеся в полученном графе (рисунок 2). Сначала надо выбрать литералы, из которых будут строиться эти пути. Начинать нужно с минимальных литералов, т.е. с таких литералов на схеме, в которые не входит ни одна дуга. На схеме имеется два таких литерала: C и T. Построив пути из них, получим

Путь 1: C ®

®
®
; Путь 2: T ® R ® S ®
.

Выберем какую-либо произвольную вершину графа (например, R) и выделим те вершины графа, которые достижимы из R. Для нашего примера из вершины R достижимы вершины S и

.

Теперь, если мы сопоставим понятие достижимости с правилом транзитивности в наших правилах вывода, то придем к следующему правилу, позволяющему получать на наших схемах новые следствия:

Если на схеме вершина Z достижима из вершины Y, то связь Y®Z является либо исходной посылкой, либо следствием нашего рассуждения, полученном по правилу транзитивности.

Посмотрев теперь на рисунок 2, нетрудно убедиться, что все следствия C4 – C9 могут быть также получены с помощью правила достижимости. Еще проще эти следствия можно получить, если выписать в одной строчке каждый из путей. Тогда транзитивные связи и соответственно следствия полученные по правилу транзитивности можно получить, если нарисовать все возможные стрелки, направление которых совпадает с общим направлением пути (рис. 3). На этом рисунке для наглядности исходные посылки обозначены жирными стрелками. Все остальные стрелки обозначают следствия.

Рис. 3

Получение сразу всех возможных следствий из посылок уже вносит некоторый элемент новизны в традиционные системы логического вывода. В Аристотелевской силлогистике все правила предназначены для получения (или проверки) единственного заключения силлогизма (следствия) из двух посылок. Единственное заключение также получают при решении системы из большего числа посылок. Например, в системе Л. Кэрролла единственное заключение получается даже в том случае, если сорит состоит из 9-ти посылок.

Теперь познакомимся с еще одним основным понятием E‑структур. Мы будем рассматривать граф, который получится, если в граф исходной E-структуры добавить все возможные следствия. Пример такого графа показан на рисунке 3. Он играет важную роль в теории E-структур и в силу этого получил специальное название.

Определение 1. CT-замыканием E-структуры называется граф, в котором содержатся все посылки этой структуры и все ее следствия.

Происхождение названия этого графа связано с некоторыми известными понятиями современной математики. В частности, граф, который можно получить из исходного графа с помощью применения правила транзитивности, в теории графов называется транзитивным замыканием данного графа. Поскольку мы используем в E‑структурах при построении CT‑замыкания не только правило транзитивности (T), но и правило контрапозиции (C), то поневоле вынуждены внести некоторые изменения в традиционный термин.

Одним из важных свойств CT-замыкания является то, что оно выполняет роль инварианта для некоторого множества E-структур. Возможны E-структуры с одинаковой совокупностью терминов, но с разными исходными посылками, у которых, тем не менее, CT‑замыкания полностью совпадают. Это говорит о том, что данные E‑структуры логически эквивалентны. Кроме CT‑замыкания в E‑структурах имеются другие инварианты. С ними мы познакомимся позже.

При получении следствий из посылок мы используем свойства отношения включения множеств. Но это отношение является одним из отношений частичного порядка (см. предыдущий раздел). Поэтому мы можем при анализе E-структур использовать все свойства и методы анализа этого отношения.

Предположим, что нам заданы посылки, среди которых содержится некоторый термин, например, "укротители крокодилов", который мы обозначаем каким-либо литералом, например, T. Оказывается, можно не только поставить задачу вывода всех следствий из данных посылок, но и ответить на такой вопрос: "Какими качествами обладают укротители крокодилов?". Ответить на такой вопрос можно, если вывести все следствия по правилу контрапозиции и после этого построить верхний конус для данного литерала. Поскольку все литералы верхнего конуса данного литерала обозначают множества, в которые включено множество, соответствующее данному литералу, то, следовательно, все литералы верхнего конуса обозначают признаки (свойства), которые присущи данному литералу. Например, для задачи из примера 6 получим: TD = {T, R, S,

}. Отсюда, ясно, что укротители крокодилов в рамках заданного рассуждения имеют следующие свойства: они заслуживают уважения, разумны и не являются детьми.

Для закрепления полученных знаний полезно решить самостоятельно еще одну задачу, взятую из книги Л. Кэрролла «История с узелками».

Даны посылки:

1) Все члены палаты общин находятся в здравом рассудке.

2) Все, кто носит титул пэра, никогда не принимают участия в скачках на мулах.

3) Все члены палаты лордов носят титул пэра.

Что из этого следует? Какими свойствами обладают те, кто принимает участи в скачках на мулах?

Указание: рекомендуется ограничить универсум только членами парламента и учесть, что парламент состоит только из двух палат (это, в частности означает, что множество членов палаты лордов является дополнением множества членов палаты общин).