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

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

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

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

1) C ;

2) TR;

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, то связь YZ является либо исходной посылкой, либо следствием нашего рассуждения, полученном по правилу транзитивности.

Посмотрев теперь на рисунок 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 получим: T = {T, R, S, }. Отсюда, ясно, что укротители крокодилов в рамках заданного рассуждения имеют следующие свойства: они заслуживают уважения, разумны и не являются детьми.

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

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

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

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

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

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

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

При разработке и реализации алгоритмов и программ анализа рассуждений используется не наглядное изображение E‑структуры, а ее представление в виде некоторых соответствий. Эти соответствия состоят из множества пар, в которых первым элементом является литерал, а вторым элементом – множество литералов. Например, пары ( , {A, C}) и (C, ) могут быть элементами такого соответствия. Число таких пар в каждом соответствии равно числу литералов в структуре. Одним из таких часто используемых соответствий является соответствие "Верхние конусы", которое содержит множество пар типа (литерал, верхний конус этого литерала).

Еще одним возможным соответствием является "CT-замыкание". Оно состоит из множества пар вида (литерал, множество литералов, достижимых из этого литерала).

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

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

Предположим, что E-структура R задана своими исходными посылками. Выделим какую-либо из этих посылок (например, AB) и представим, что вместо нее в E-структуру R введена в качестве посылки ее контрапозиция (т.е. посылка ). В этом случае суждение AB будет уже не исходной посылкой R, а ее следствием, но в CT-замыкании структуры R обе эти посылки будут присутствовать и в первом, и во втором случае. При этом окажется, что и все CT-замыкание E-структуры R при такой замене останется неизменным.

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

Таким образом, если нас интересуют в E-структуре не следствия из ее исходных посылок, а вся структура в целом с коллизиями или без оных, то мы можем считать инвариантом E-структуры ее CT‑замыкание.

Возьмем в качестве примера сорит Кэрролла.

Все опытные люди компетентны;

Дженкинс всегда допускает грубые ошибки в работе;

Все компетентные люди не допускают грубых ошибок в работе.

Сделаем в нем следующие изменения:

1) первую и третью посылки заменим на их контрапозиции;