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

Этот инвариант, составленный из половины суждений диаграммы Хассе, назван минимальным множеством посылок E-структуры. Почему минимальным? А потому что исходная E-структура может содержать посылки, которые на самом деле логически следуют из остальных посылок. Если эту E-структуру дополнить всеми следствиями, получаемыми с помощью правила C, а потом преобразовать полученную систему в диаграмму Хассе, то мы, сравнивая исходные посылки с суждениями диаграммы Хассе, сможем найти «лишние» (т.е. выведенные из других посылок) посылки среди исходных.

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

A®

; ® ; C® ; C® .

Строим граф с посылками (рисунок 3) и к каждой посылке достраиваем контрапозицию (рисунок 2, 3)

Рис. 3Рис. 4

Присмотревшись внимательно к графу на рисунке 4, мы увидим, что дуга A®

соединяет литералы, между которыми имеется путь A® ® . Отсюда следует, что система не независима и посылка A® является следствием других посылок (C® и ® ). Чтобы из графа на рисунке 4 получить диаграмму Хассе данной структуры, нужно изъять из этого графа дугу A® и ее контрапозицию D® .

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