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

Логический Анализ 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-структуры называется граф, в котором содержатся все посылки этой структуры и все ее следствия.

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