Логика естественных рассуждений - Кулик Б.А.
ISBN 5-7940-0080-5
Скачать (прямая ссылка):
Рассмотрим пример на коллизию парадокса.
Приложение Б. Частично упорядоченные множества
107
Пример Б.З. Дано множество К (возможно, бесконечное) положительных целых чисел, свойства которого определяются следующими суждениями:
(1) Все четные числа К делятся на 3 и не делятся на 7.
(2) Все числа К, которые делятся на 3, не делятся на 5.
(3) Все числа К, которые не делятся на 7, делятся на 5.
Необходимо определить, содержатся ли в множестве К четные числа.
Ясно, что данное множество относится к классу Set. Введем обозначения: N2 — четные числа, TV3 — числа, делящиеся на 3, TVs — числа, делящиеся на 5, Nj — числа, делящиеся на 7. Соответственно Nn обозначим все числа множества К, не делящиеся на целое число т. Тогда для этого примера получим следующую f-структуру:
(1) TV2-(T^TV7);
(2) 7V3-(JVs);
(3) TV7 - (TV5).
При "ручном" анализе мы не будем строить полностью СГ-замыкание, а получим результат, пропуская некоторые шаги вывода всех следствий:
(4) TV3 —>¦ N2 (из посылки (1) по правилу С);
(5) N5 — TV3 (из (2) по правилу С);
(6) TV2 — N2 (из (1), (3), (5), (4) по правилу Г).
Получена коллизия парадокса, из которой следует, что подмножество N2B К может быть только пустым множеством, а множество К может содержать только нечетные числа.
Коллизия парадокса в QC-структуре, не являющейся ^-структурой, может оказаться допустимой коллизией, если с помощью содержательного анализа можно установить, что пара альтернативных литералов, связанных этой коллизией, не равны соответственно 0 и 1.
В интерпретациях QC-структур допустимая коллизия парадокса может быть установлена с помощью сравнения соответствующих элементов. В формальных QC-структурах такое сравнение невозможно, поэтому в них допустимые коллизии парадокса должны присутствовать в составе посылок или следовать из них, в противном случае такая структура по своим свойствам будет соответствовать Е-структурам.
Пример Б.4. Проанализируем формальное представление рассмотренной ранее QC-структуры класса Div, заданной множеством {1,2, 3, 4, 6, 12}. Нетрудно убедиться, что ее можно представить следующим суждением^ Л — (Л, В), где Л = 2, В = 3, 0 = 1,1 = 12. Тогда соответственно Л = 6 и В = 4. Граф QC-структуры и ее СГ-замыкание показаны нарис. Б.1.
108
Приложение Б. Частично упорядоченные множества
а в ab
14 IX
ab ab
Рис. Б.і
Заметим, что контрапозицией суждения типа А —> Л во всех случаях является то же самое суждение. Данной формальной QC-структуре соответствует потенциально бесконечное множество интерпретаций. Приведем некоторые из них.
1) QC-структура класса Div: 0=1;Л=р;В = д;1= plq, где р и q — любые взаимно простые числа.
2) То же, что и предыдущее, но при этом р и q необязательно взаимно простые, і = г, при условии, что р2 и q являются делителями г, a ql — не является.
3) QC-структура класса Dom с координатами класса Nim: 0 = (0, 0); а = (0.3, 0.4); в = (0.2, 0.6); і = (1, 1). В этом случае А = (0.7, 0.6), В = (0.8, 0.4).
Определение Б.8. QC-структуры, в которых отсутствуют недопустимые коллизии, называются корректными, в противном случае — некорректными.
Очевидно, что появление цикла в диаграмме Хассе любой QC-структуры свидетельствует о ее некорректности. Любая коллизия парадокса недопустима в /!-структурах, и определяющим признаком этой коллизии является присутствие пары альтернативных литералов в одной цепи ее диаграммы Хассе. В то же время /!-структура может быть вполне корректной даже в том случае, если пары альтернативных литералов, вызывающие недопустимые коллизии парадокса, содержатся в одной полусвязной компоненте диаграммы Хассе (полусвязной компонентой ориентированного графа называется компонента, которая становится связной при замене всех имеющихся у нее ориентированных связей на неориентированные). Примером является корректная /Г-структура, диаграмма Хассе которой показана на рис. Б.2 и в которой все пары альтернативных литералов содержатся в одной полусвязной компоненте.
Приложение Б. Частично упорядоченные множества
109
При анализе коллизий целесообразно выделить ситуацию, когда в одном элементарном суждении совмещаются коллизии цикла и парадокса, т. е. когда вследствиях QC-структуры содержится пара суждений типа Л -* А и А — А. Такая ситуация вызывает разные последствия в Е-структурах и QC-структурах.
Определение Б. 9. Е-структура Г называется вырожденной, если в ней существует такой литерал А, что для него выполняется А — А и А -» А.
Название обусловлено тем, что в Е-структурах из этой пары суждений следует глобальная коллизия 1 —* 0. Это означает, что вся система состоит только из одного элемента, в котором совмещены наибольший и наименьший элементы ?-структуры. В QC-структурах пара суждений А —* А и А ~* А означает коллизию цикла, но такая коллизия необязательно является глобальной и во многом зависит от соответствующей интерпретации^ Например, в QC-структурах класса Div допустимые коллизии А —»А и А —* А свидетельствуют о том, что наибольший элемент является точным квадратом, определяемым равенством і = А2 или і = (Л)2, а литералы А и А вследствие коллизии цикла представляют в интерпретации данной QC-структуры один и тот же элемент. Если же подобная двойная коллизия считается допустимой в QC-структуре класса Dom, в которой все координаты представлены классом Num, то это означает, что для любой компоненты щ векторов АиА справедливо равенство I1- = 2щ.
