При этом число cTpyjryPHbix элементов назовем мощностью множества или карДинальным числом; введем для него обозначение #. В у казанных выше примерах

ФА-= 10, #.4=5. (2.5)

В случае = \ А назовем синглетоном. Множество с конечным #• назове! конечным множеством, все элементы в таком множестве ]>иожно записать так, как в формулах (2,3) и (2.4), но, например- в случае натуральных или вещественных чисел, т е. бесксвечных множеств, этого сделать нельзя. При этом часто исиользуют способ записи, при котором справа от вертика/ 1Ьной черты записывают все свойства множества. Наприм-*Р> формулу (2.4) можно записать в виде

А = {jcjc-четное число больше О и меньше 9}. (2.6)

Кроме того, для об значения понятия в виде рисунка часто используют диагра1-1Ы Венна (рис. 2.1).

Помимо указань:» способов для определения понятий четкого множества существует способ определения с помощью характерис ической функции. Характеристическая функция х 4, определ.>1щая множество А в полном пространстве X, представл>*т собой отображение, для которого X есть область определения, а {О, 1} (двузначное шюжество из О и 1) есть об лас гь значений:

1л-Х{й, 1}

ГО. хфА,

При этом {х)= 1, "1И элемент х удовлетворяет свойствам А, и О, если не удовл-творяет. Следовательно, если отложить X на горизонтальнй, а {О, 1} на вертикальной оси, то получим графическа представление, показанное на рис. 2.2.

В полном пространстве X можно рассматривать различные множества, напИмер А с некоторыми свойствами и 5 с другими свойствами Объединение всех таких множеств называется степенным множеством и обозначается 2*. Например, пусть

X = {а. h. с], (2.8)

тогда степенное множество есть

2 = (0, {а}, {Ь}. {с-}, {а, Ь}, {Ь, с], {с, а}, X).

Рис, 2.1. Представление множе- Рис. 2.2. Определение множества с помощью диаграммы ства с помощью характеристи-

Веина.

ческой функции.

(2.9)

Здесь 0-специальное множество, в котором нет элементов, оно называется пустым множеством. Его характеристическая функция

и(х) = 0 для VjceX. (2.10)

Ьдесь V называется квантором всеобщности, его можно читать словом «всех». (Кроме него есть квантор существования 3 в смысле «существует...».) Эти кванторы часто используются в логике и искусственном интеллекте. В отличие от пустого множества характеристическая функция полного множества X имеет вид

1х{х)=1 для УхвХ. (2.11)

Кроме того, для мощности множества в общем случае справедливо утверждение

#1* = 2*. (2.12)

Это можно легко вывести из формул (2.8) и (2.9).

Теперь изучим некоторые операции над множествами (рис. 2.3). Прежде всего, отношение вложения множеств: если элементы А обязательно являются элементами В, то А называется подмножеством В (или 5-надмножеством А), что обозначается как А с: В (А с: В справедливо также при А = = В; если А < В, яо А В, то А называется собственным подмножеством В). Если определить А с: В через характеристическую функцию, то получим следующее неравенство:

Хл(х)Хв(х) для хеХ. (2.13)

Для отношения вложения множеств с можно доказать

АГ\В

Рис. 2.3. Вложение (а), дополнение (б), произведение (в) и сумм! множеств (г).

(2.14

(2.15

(2.16

справедливость трех свойств:

1) рефлексивность

е2. Ас: А;

2) антисимметричность \/А, Ве2, А В, А-А = В;

3) транзитивность УЛ, В, Се!, Ad В, В с СА с С.

Можно сказать, что (2, с) образует частично упорядоченное множество, или POSET (Для отношения вложени» множеств обычно для произвольных А. В не всегда справед ливо А с В или В а А, поэтому наше множество не является линейно упорядоченным или полностью упорядоченным множеством.)

В POSET (2*, с:) представляют интерес унарные и бинар ные операции. Это операции дополнения множества /V пересечения множеств Аи В{А П В) и объединения множесп А и В. Графически их можно пояснить с помощью диаграш

Венна на рис. 2.3, в, г. С помощью характеристических функций операции можно определить следующим образом:

глСА-глА для V.reZ, (2.17)

X.4nfiW = WAb(>c) для хвХ, (2.18)

bnfiW = X.4()VbW для VxeX. (2.19)

Здесь Д и \/ называются операциями взятия минимума и максимума, т.е. взятия наименьшего и наибольшего значений.

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

1) закон идемпотенции

А А = А, A\S А = А\

2) закон коммутативности АВ=ВА, А\В=В\]А\

3) закон ассоциативности .4 П (В П С) = (.4 П Д) П С, .4 и (5 и q = и Д) и С;

4) закон абсорбции

А {А\] В) = A\i(A В) = А\

5) закон дистрибутивности

п (д и q = (.4 Л Д) и ( п q, и (5 п q = и Д) п ( и q;

6) закон комплементарности А А = A\S А = Х.

(2.20) (2.21)

(2.22) (2.23)

(2.24) (2.25)

" От английских слов partially ordered xt-Прим. перев.

В общем случае POSET, удовлетворяющее четырем свойствам (идемпотентности, коммутативности, ассоциативности и абсорбции), называется решеткой; решетка, удовлетворяющая закону дистрибутивности,-дистрибутивной решеткой, а дистрибутивная решетка, удовлетворяющая закону комплементарности,- комплементарной дистрибутивной решеткой. Кроме того, комплементарная дистрибутивная решетка известна как булева решетка или булева алгебра.

Таким образом, понятие точного множества (2", с, п , U ) можно обсуждать в рамках булевой алгебры.

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

1) двойное отрицание

А = А. (2.26)

2) закон де Моргана

{А П Ву А и В", (А и В)" = А П ff. (2.27)

2.2. ТОЧНАЯ ЛОГИКА

Ниже мы рассмотрим точную логику (логику компьютеров или двузначную булеву алгебру) как основу для изучения нечеткой логики. Речь пойдет о двузначном мире «да» и «нет» или «истина» и «ложь»; на уровне аппаратных средств рассматривают значения напряжений О и 5 В, но в общем случае можно представить два значения {О, 1}.

Итак, можно считать, что компьютеры состоят из после-довательностных схем, указанных на рис. 2.4. Каждая из п входных переменных и каждая из т выходных переменных в некоторый момент времени имеют одно из двух значений: О или 1. Кроме того, эти переменные изменяются одновременно по базовому сигналу управления, называемому тактовым импульсом. Если отнощение входов и выходов записать в виде функции, то получим

ydt+l)=fj{x,{t), x,{t), хМ

уЛЧУ2{Ч---,УШ]=\,..;т. (2.28)

Здесь переменные правой части включают также yj(t), т.е.

Входы T,lt} о-

т {0.1}

Компьютер

паследовательностная схема

-комбинаторная схема * память

Тактовые ги~1 П П П- {0,1}

Выходы

импульсы t-1 t ti-1 "•

Рис. 2.4. Последовательностная схема.

это так называемая рекурсивная формула, поэтому в следующий момент времени t + 1 все выходные значения yj{t + 1) определяются в зависимости от предыстории всех входов до текущего момента времени t.

Если изменения значений с течением времени фиксировать с помощью функции памяти, можно обсуждать отношения входов и выходов в фиксированный момент времени. Таким образом, сместив на второй план временные факторы, с помощью комбинаторных схем можно реализовать только отношения входов и выходов (рис. 2.5). Формулы комбинаторных схем с п входами и т выходами можно записать в виде

yj=fj(Xi, х.....x„),J= 1, ш.

(2.29)

Здесь т выходных переменных, но их уже можно рассматривать по отдельности одну за другой, поэтому без ограничения общности можно считать число выходов равным 1. Другими словами, можно рассматривать и входов и один выход. При этом отношение входов и выхода можно обозначить как

/:{0, 1Г{0, 1},

{Xi.X2. ...,X„)\-y=f(Xi, Х2.....Х„).

(2.30)

Такая функция /называется булевой функцией и переменных, а ее конкретная реализация-комбинаторной схемой.

Прежде всего рассмотрим наиболее простой случай и = 1:

/:{0, 1}-{0, 1}

(2.31)

хУ =f(x).

Как показано на рис. 2.6, б, в этом случае существуют четыре

Рис. 2.5. Комбинаторная схема.