Материал: Алгебра_кортежей

Глава 1. Основные математические структуры

… если между людьми возникают разногласия, достаточно было бы только сказать "Вычислим!", чтобы … стало ясно, кто прав.

Г.В. Лейбниц

Приводится обзор средств логического анализа, некоторые из них исторически сыграли важную роль в формировании этого направления, другие применяются в современных программных системах в таких областях, как искусственный интеллект и системный анализ. Подобные средства можно разделить на две категории: 1) системы на основе формального подхода; 2) алгебраические системы. В теории формальных систем, помимо классических логик (силлогистика, логика высказываний, логика предикатов и т.д.), активно развиваются неклассические логики (логика умолчаний, немонотонная логика и т.п.). Неклассические логики часто используются при моделировании и анализе модифицируемых рассуждений (рассуждений с гипотезами и абдуктивными заключениями), однако авторы придерживаются мнения, что на компьютере такого рода задачи целесообразно решать алгебраически с применением операций и законов алгебры множеств. Последующие главы посвящены подробному изложению этого подхода к логическому анализу.

Вкачестве алгебраических систем, обеспечивающих решение широкого круга задач логического анализа, рассматриваются алгебра множеств и алгебра логики (алгебра высказываний), которые относятся к классу булевых алгебр [Скорняков, 1982] (см. Введение), а также теория отношений.

1.1.Алгебра множеств

Внастоящее время алгебра множеств редко используется как инструмент логического анализа. Во многом это обусловлено подрывом доверия к правомерности "множественного" подхода после того, как на рубеже XIX и XX были сформулированы парадоксы теории множеств. Обнаружение таких парадоксов породило у многих логиков и математиков уверенность в том, что "наивное" понятие множества противоречиво в принципе. Здесь мы будем

придерживаться точки зрения, согласно которой парадоксы, связанные с

15

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

Основными понятиями алгебры множеств считаются множество и элемент. Соотношение между ними называется отношением принадлежности и обозначается знаком " ". Запись b A переводится с символического языка как "b есть элемент множества A" или "элемент b принадлежит множеству A". Если известны все элементы множества (например, a, b и c), то общепринята такая запись множества:

A = {a, b, c}.

Вэтом случае элементы множества принято заключать в фигурные скобки. Множества можно задать двумя способами: с помощью формулировки характерных признаков (например, множество K содержит неотрицательные четные числа, не превышающие числа 8) или перечислением элементов

(например, K = {0, 2, 4, 6, 8}).

Всовременной математике нет четкого определения отношения принадлежности. В алгебре множеств этой неопределенности можно избежать, если считать, что оно связывает два разных типа объектов

("элемент" "множество"), но ни в коем случае не должно быть связи типа "множество" "множество". Заметим, что именно эта нечеткость в определении отношения принадлежности приводит к парадоксам теории множеств.

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

" " – строго включено; " " – включено или равно.

Запись A B означает, что множество A включено в множество B, т.е. все элементы множества A являются одновременно элементами множества

B, причем невозможно равенство этих множеств. Запись A B означает, что множество A включено во множество B, но они могут быть равными.

16

Изображение отношения включения (A B) с помощью диаграмм Эйлера показано на рис. 1.1.

Рис. 1.1. Отношение строгого включения

Если множества заданы с помощью перечисления элементов, то отношение включения (или невключения) одного множества в другое можно легко установить, если сравнить элементы этих множеств. Например, если заданы три множества P = {a, b, c, d, e}; Q ={b, d, a}; R ={a, c, f}, то, сравнивая элементы этих множеств, можно утверждать, что Q P, но отношение R P для данных множеств неверно, так как элемент f из множества R не принадлежит множеству P. В случаях, когда число элементов слишком велико или бесконечно, отношение включения можно иногда установить, используя свойства этих множеств. Например, если даны два бесконечных множества положительных целых чисел N2 (числа, кратные 2) и N6 (числа, кратные 6), то нетрудно доказать, не прибегая к поэлементной проверке, что N6 N2.

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

Множества A и B равны, если справедливо как A B, так и B A. Заметим, что в теории множеств это утверждение – доказанная теорема.

Если множества связаны отношениями A B или A B, то A называют подмножеством B. Среди всех возможных подмножеств произвольного множества A обязательно содержится также и само множество A. Другими словами, для любого множества A всегда справедливо A A.

Еще один интересный и полезный частный случай множества – пустое множество, не содержащее никаких элементов (обозначается " "). Его математический смысл раскрывается в следующем предложении, которое можно отнести к аксиомам алгебры множеств: Пустое множество включено в любое множество.

17

В математических рассуждениях, когда надо доказать, что при заданных условиях множество X не существует (или существует), сводят доказательство существования к доказательству отношения X = (или X ). Часто такой метод позволяет намного упростить доказательство.

Если множество задано перечислением элементов, то можно записать совокупность всех подмножеств этого множества. Например, для множества A = {a, b, c} такая совокупность состоит из восьми подмножеств:

, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.

Доказано простое соотношение, позволяющее узнать общее количество всех возможных подмножеств множества, содержащего ровно N элементов. Оказывается, что для любого N это количество равно 2N. Например, для нашего множества A = {a, b, c} число всех возможных подмножеств равно 23.

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

Система множеств есть некоторая совокупность подмножеств заданного множества, принятого за универсум. Например, для множеств планет, комет, звезд и т.д. в качестве универсума можно принять множество астрономических объектов. Для универсума нет общепринятых обозначений. Далее мы будем обозначать его символом U.

Перейдем к операциям. Начнем с операции дополнения, которая может быть определена только тогда, когда для системы множеств задан универсум.

Определение 1.1. Дополнением множества A называется множество A, содержащее все элементы универсума, которые не являются элементами множества A.

В логике дополнению множества соответствует связка "не". Например "не красный" – любой возможный цвет, кроме красного. Обычно дополнение множества обозначается с помощью черты над символьным обозначением

этого множества. Например, Rik обозначает дополнение множества Rik .

Пример 1.1. Пусть U = {a, b, c, d} и P = {a, c}. Тогда P = {b, d}.

Определение 1.2. Пересечение множеств A и B – это множество C, которое содержит все элементы, принадлежащие одновременно как A, так и B.

18

Операция пересечения множеств обозначается символом " ". Символически определение 1.2 можно записать как формулу

C = A B.

Например, пересечение множества всех студентов данного вуза и множества всех участников КВН – это множество всех студентов данного вуза, участвующих в КВН. Другой пример: пересечение множества всех чисел, делящихся на 2, и множества всех чисел, делящихся на 3, есть множество всех чисел, делящихся на 6.

В логике операции пересечения соответствует логическая связка "И" (обозначается как или ). Если речь идет об объектах со свойствами P или Q, то логическая формула P Q означает, что речь идет только об объектах, которым присущи оба этих свойства.

Пример 1.2. Пусть A = {a, b, c, d} и P = {a, c, f}. Тогда A P = {a, c}.

Возможна ситуация, когда два множества не содержат общих элементов. Тогда пересечение этих множеств – пустое множество. Например, для

Q = {a, c,} и R = {b, d} Q R = .

Определение 1.3. Объединением множеств A и B называется множество C, все элементы которого принадлежат хотя бы одному из этих множеств.

Операция объединения множеств обозначается символом " ". Символически определение 1.3 можно записать как формулу C = A B.

В логике операции объединения соответствует логическая связка "ИЛИ" (обозначается " "). Если речь идет об объектах со свойствами P или Q, то логическая формула P Q означает, что речь идет только об объектах, которым присуще хотя бы одно из этих свойств. Причем допускается, что объекты, обладающие обоими свойствами, также относятся к этому классу объектов.

Пример 1.3. Пусть A = {a, b, c, d} и P = {a, c, f}. Тогда A P = {a, b, c, d, f}.

Операции дополнения, пересечения и объединения являются основными операциями алгебры множеств. Ниже приведены операции, которые называются производными операциями. Это означает, что их можно выразить с помощью основных операций.

Определение 1.4. Разность множеств A и B есть множество C = A \ B, которое содержит только элементы множества A, не принадлежащие

19