Научная литература
booksshare.net -> Добавить материал -> Логика -> Кулик Б.А. -> "Логика естественных рассуждений" -> 45

Логика естественных рассуждений - Кулик Б.А.

Кулик Б.А. Логика естественных рассуждений. Под редакцией Дюка В. А. — СПб.: Невский Диалект, 2001. — 128 c.
ISBN 5-7940-0080-5
Скачать (прямая ссылка): logika-estestvennih-rassujdeniy.djvu
Предыдущая << 1 .. 39 40 41 42 43 44 < 45 > 46 47 48 49 50 51 .. 56 >> Следующая


Определение Б.З. Диаграммой Хассе Г" QC-структуры Г называется структура, представленная как подграф графа Гст, содержащий только его максимальные цепи.

Из определения ясно, что диаграмма Хассе QC-структуры строится после построения ее СГ-замыкания с помощью удаления всех выводимых по правилу транзитивности связей. Но диаграмму Хассе произвольной QC-структуры Г можно построить более простым способом. Этот способ задается на основе следующего утверждения.

Теорема Б.1. Если Гс — структура, построенная из посылок QC-структуры Г с использованием только правила С, то Г" є Г6. Доказательство. Сначала докажем, что для преобразования Гс в Гсг достаточно использовать только правило вывода Т. Ясно, что Гс является симметричной структурой, в которой для каждой цепи A-* В С,

где А, В,С — литералы в Г, существует антицепь С-*...-* В—* А. Поэтому контрапозицию любого элементарного суждения, полученного с использованием правила T в любой цепи структуры Гс, можно получить, используя правило Г в ее антицепи. Отсюда следует достаточность правила Т. Но всякое применение правила транзитивности приводит к образованию цепей, являющихся подцепями исходных цепей. Отсюда

Приложение Б. Частично упорядоченные множества

103

следует, что в г6 содержатся все максимальные цепи г( г. Конец доказательства.

Пример б. 1. Пусть QC-структура г задана суждениями А -* Д С —> D и С -*_(А, Разложим третье суждение на элементарные суждения (С —у А, С -* В) и, используя только правило С, получим Г(, содержащую следующие суждения:

A-* D\ С — Д С—Л; C-B - посылки; D-* A; D-* С; A-* С; В — С — следствия.

Правило транзитивности позволяет добавить к этой структуре еще два новых суждения: В —* D и D -* В. Диаграмма Хассе этой системы содержит множество {С —* Д С -* А; С -* В; D —*¦ С; А -* С; В -* С] элементарных суждений, Если сравнить составы элементарных суждений в г, г6, г" и в г6т, то получим следующие соотношения:

гсгсд Тст и гн ? гс S гсг.

В то же время соотношение г <=. г'7 в данном примере неверно. Это говорит о том, что исходные посылки не независимы, поскольку суждение А — D, содержащееся в исходных посылках г, можно с помощью правил вывода получить из остальных исходных суждений.

Определение Б.4. Минимальным (максимальным) элементом QC-структуры г называется литерал Lm\n (Lmax), для которого отношение X — !min (Lmax ~~* X), где X є Г означает, что X= 0(Х=1).

В QC-структурах обычно (за исключением случая, когда QC-структура представляет собой вполне упорядоченное множество) содержатся два и более минимальных (и соответственно максимальных) элемента. В частности, в QC-структуре из примера Б.1 имеются три минимальных (А, В, D) и три максимальных (А, В, D) элемента. Кроме того, справедливо следующее соотношение.

Теорема Б.2. Если Li — минимальный (максимальный) элемент QC-структуры г, то Li является максимальным (минимальным) ее элементом.

Доказательство. Пусть Li — минимальный элемент. Предположим, что литерал Li не является максимальным элементом. Это означает существование литералаX^l такого, что I, — X. По правилу контрапозиции получаем X ~* Li и, следовательно, X = O. Отсюда следует X=I, что противоречит принятому предположению. Вторая часть теоремы с условием, что Li — максимальный элемент, доказывается аналогично. Конец доказательства.

104_Приложение Б. Частично упорядоченные множества

Стоит отметить, что в доказательстве теоремы Б.2 неявно использовалось равенство 0 = 1, которое не содержится в аксиомах и не доказано. Автору неизвестно, можно ли это равенство доказать, используя введенную выше аксиоматику QC-структур, но даже в случае невозможности такого доказательства ничто не мешает использовать это равенство в качестве еще одного свойства квазидополнения. По крайней мере, в приведенных примерах QC-структур данное соотношение и соотношение 1=0 всегда выполняются.

СГ-замыкание и диаграмму Хассе можно рассматривать как инварианты некоторого множества представлений QC-структур. Вариация этих различных представлений возможна за счет подстановки вместо некоторого множества элементарных исходных суждений их контрапозиции и за счет включения в посылки тех суждений, которые являются следствиями других посылок.

Диаграмма Хассе QC-структуры Г содержит минимальное число элементарных суждений и их контрапозиции, поэтому удаление любой пары из диаграммы Хассе приведет к тому, что применение правил вывода не позволит построить полностью СГ-замыкание исходной структуры. В то же время, если из каждой пары (суждение и его контрапози-ция) в Г" удалять только по одному суждению, то мы получим минимальное множество суждений, из которого с помощью правил вывода Может быть построено СГ-замыкание исходной QC-структуры. Это дает основание для определения третьего инварианта QC-структур.

Определение Б.5. Минимальным порождающим множеством QC-структуры Г называется список пар (элементарное суждение - его контрапозиция), содержащихся в Г".

Минимальное порождающее множество можно использовать для формирования множества минимальных QC-структур, сводимых к одному инварианту. Если из каждой пары этого списка выбрать только одно суждение, то при любом варианте выбора мы получим структуру, у которой СГ-замыкание совпадает с СГ-замыканием исходной QC-структуры. Число таких различных минимальных исходных структур, соответствующих одному и тому же инварианту, равно 2*, где k = п/2 и п — число дуг в диаграмме Хассе Г" QC-структуры Г.
Предыдущая << 1 .. 39 40 41 42 43 44 < 45 > 46 47 48 49 50 51 .. 56 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed