Глава 1. Алгебраические системы

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

1.1 Множества

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

Множество считается заданным, если указано характеристическое свойство, которым обладают все элементы множества. Если понятию “цифра” или “буква”, “таблица” или “рисунок” соответствуют определенные наборы элементов, то понятию “маленькое число” или “большое входное сопротивление”, “красивая женщина” или “высокий мужчина” соответствуют субъективные оценки. То есть каждый наблюдатель сформирует различные группы чисел или входных сопротивлений, женщин или мужчин и т. п.

Поэтому можно выделить понятия “четкое множество”, элементы которого объективно и однозначно включены в состав множества, и “нечеткое множество”, элементы которого субъективно и неоднозначно включены в состав множества. Такая классификация достаточно условна, но позволяет применять соответствующие математические методы для принятия решений.

1.1.1. Четкие множества

В языках программирования задают типы данных: INTEGER -, целые числа, CHAR – литеры (символы, знаки), STRING – строки, BOOLEAN - логические переменные и др. Так описывают в компьютере характерные свойства отдельных множеств.

Объекты, включаемые в множество, называют его элементами. Например, ’3’ - элемент INTEGER, ‘c’ - элемент CHAR , ‘monday’ – элемент STRING, ‘true’ – элемент BOOLEAN и т. п..

Общим обозначением множества служит пара фигурных скобок ”{”, “}”, между которыми перечисляют элементы множества.

Например, {1, 3, 5, 7}, или {a, b, c, d} или {Иванов, Петров, Сидоров,...}.

На языке pascal для обозначения множества используют прямые скобки “[“ и “]“, между которыми перечисляют элементы множества.

Например, [1, 3, 5, 7], или [‘a’, ‘b’, ‘c’, ‘d’] или [иванов, петров, сидоров,..].

Для обозначения множеств в тексте используют прописные буквы латинского алфавита A, B, C, ...X, Y, Z, а для обозначения его элементов - строчные буквы a, b, c,...x, y, z. Иногда эти буквы используют с индексами из множества натуральных чисел. Например, А₁, А₂, А₃ или а₁, а₂, а₃.

На языках программирования имя или <идентификатор_множества> представляют в виде последовательности букв и/или цифр, но начинающихся с прописной буквы, а имя или <идентификатор_элемента> - в виде последовательности букв и/или цифр, но начинающихся со строчной буквы.

Принадлежность элемента x множеству A обозначают символом ““ – знак принадлежности. Например, xA..

На языке pascal это записывают так: “x in А”, где x - <идентификатор_элемента >, А - <идентификатор_множества>”.

Если элемент х не принадлежит множеству A, то используют символ ““ – знак непринадлежности. Например, хA..

На языке pascal это записывают так: “not(x in А)”.

Порядок перечисления элементов между фигурными скобками произвольный, т.е. {a, b, c, d}={b, c, d, a}, но не допускается неоднократная запись одного элемента среди остальных элементов множества, т. е. {a, a, a, b, b, c, c, d}={a, b, c, d}.

Множество, каждый элемент которого можно индексировать натуральным числом 1,2,... n, называют счетным.

На языке pascal такому элементу присваивают <идентификатор_порядкового_типа>.

Если n конечно, то множество называют конечным.

Например, множество цифр счетно и конечно, а множество целых чисел (INTEGER) – счетно, но не конечно.

На языке pascal, как правило, число элементов множества указывают в диапазоне [1..n].

Число элементов счетного конечного множества A называют его мощностью и обозначают так: |A|=n.

Например, мощность множества цифр равна 10, а мощность множества строчных букв латинского алфавита – 26.

Если все элементы множества A являются также элементами множества B, но не наоборот, то множество A называют подмножеством множества B. Для обозначения этого в тексте используют символ ““ - знак включения: AB.

Например, если А={1, 2, 3} и B={1, 2, 3, 4, 5}, то A есть подмножество B. На языке pascal факт включения множества A в множество B записывают так: AB.

Если AB и BA, то A=B.

Например, если А={1, 2, 3} и B={3, 2, 1}, то A=B.

Если AB и AB, то A называют собственным подмножеством B.

Для обозначения этого в тексте используют символ ““ - знак строгого включения: AB.

Например, если А={1, 2, 3} и B={1, 2, 3, 4, 5}, то AB.

Если хотя бы один элемент множество A не принадлежит множеству B, то множество A не включено в множество B. Для обозначения этого в тексте используют символ ““ - знак невключения: AB.

Например, если А={1, 2, 3, 6} и B={1, 2, 3, 4, 5}, то AB.

На языке pascal факт невключения множества A в множество B записывают так: not(AB).

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

Например, если в решении задач принимают участие два множества А={a, b} и B={b, c, d}, то универсальное множество будет U ={a, b, c, d}.

Множество, элементами которого являются подмножества, называют семейством подмножеств.

Например, С={А, В}={{a, b}, {b, c, d}}.

Пример. Даны множества А={1; 2} и В={{1; 2; 3}, {1; 3}, 1; 2}. Верно ли, что {1; 2}{{1; 2; 3}, {1; 3}, 1; 2}?

Нет, неверно, так как среди элементов множества В нет элемента А={1; 2}, а верно выражение {1; 2}{{1, 2, 3}; {1; 3}; 1; 2}, т.к. элементы множества В формируют подмножество А={1; 2}.

Множество, включающее в себя максимально возможное число подмножеств универсального множества, называют булеаном. Он включает в себя пустое подмножество и множества, сформированные из одного, двух, трех и т.д. до общего числа элементов универсального множества. Булеан обозначают символом B(U).

Например, если U={a, b, c}, то B(U)={, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}}.

На языке pascal булеан описывают как объект множественного типа на основе элементов базового типа.

Например, B(U)=set of (‘a’, ‘b’, ‘c’) = [[], [a], [b], [c], [a,b], [b,c], [a,c], [a,b,c]], где B(U):=<идентификатор_булеана>.

Число элементов булеана B(U) зависит от числа элементов универсального множества U по формуле:

|B(U)|=2^|U|,

где |U| - мощность или число элементов универсального множества, а |B (U)| - мощность или число подмножеств булеана.

Например, если |U|=3, то |B(U)|=2³=8, если |U|=5, то |B(U)|=2⁵=32.

В компьютере для кодирования букв, цифр и символов используют 8 разрядов двоичного кода. Это позволяет сформировать 256 кодовых комбинаций для кодирования букв, цифр и символов.

Описание множества может быть выполнено а) перечислением элементов, b) указанием характерных свойств элементов или c) заданием порождающей процедуры.

При перечислении элементов между фигурными скобками указывают все элементы множества.

Например, ЧИСЛА={1, 2, 3, 4, 5}, БУКВЫ={a, b, c, d, е}, ПРОДУКТЫ_ПИТАНИЯ={‘хлебобулочные_ изделия’, ‘кондитерские_ изделия’, ‘молочные_продукты’, ‘напитки’, ‘фрукты’, ...} и т. п.

При указании характерных свойств элементов между фигурными скобками после указания текущего элемента ‘x’ ставят знак ““, вслед за которым наличие этих свойств описывают логической функцей - Р(х):=”..”. Если при х=’а’ функция Р(‘а’) принимает значение “истина”, то элемент ‘a’ включают в перечень элементов множества, если - “ложь”, то - не включают.

При задании порождающей процедуры между фигурными скобками после указания текущего элемента ‘x’ и знака ““ с помощью оператора присваивания (“x:=<алгебраическое выражение>”) определяют значение элемента, включаемого в множество.

Например, множество нечетных чисел можно задать порождающей процедурой на множестве целых чисел: А={x| x:=(2n-1), где n=1, 2, 3,..}.

Если даны два множества A и B, то упорядоченную пару (x, y), где хA и yB, называют кортеж.

Множество всех кортежей (x, y) множеств A и B называют прямым произведением. Исполнение этой операции обозначают так:

{(x, y) | хA, yB}=(AB),

где “” – символ прямого произведения.

Если A={a; b; c; d; e; f; g; h} и B={1; 2; 3; 4; 5; 6; 7; 8}, то прямое произведение формирует 8^. 8=64 кортежа {(a, 1), (a, 2),..(h, 7), (h, 8)}. Это – описание шахматной доски, а при описании шахматной партии могут участвовать не все позиции шахматной доски. Поэтому любое множество упорядоченных пар (x, y) при описании шахматной партии есть подмножество прямого произведения, т.е.

{(x, y)|xA, yB} (AB).

Прямым произведением нескольких множеств X₁, X₂,...,X_n называют множество всех кортежей

{(x₁, x₂,...x_n)| x₁X₁, x₂X₂, ..., x_nX_n}=(X₁X₂...X_n).

Любое множество (x₁, x₂,...x_n) есть подмножество прямого произведения, т.е.

{(x₁,x₂,...x_n)| x₁X₁, x₂X₂, ..., x_nX_n} (X₁X₂...X_n).

Если X₁=X₂=...=X, то {(x₁, x₂,...x_n)| x_iX} Xⁿ..

Для обозначения кортежа используют круглые скобки, а для замещения его в тексте – символ t, т.е. t=(x₁; x₂;...x_n).

Если множество X_i=, то (X₁X₂...X_i...X_n)=.

Следует обратить внимание, что {}, т. к. ||=0, а |{}|=1.

Каждый элемент кортежа есть его компонента.

Кортеж может содержать повторяющиеся компоненты, но нельзя нарушать заданный порядок компонент.

Например, (x₁, x₁,..x₁)(x₁) и (x₁, x₂,..x_n)(x_n, x₂,..x₁).

Число компонент кортежа определяет его длину или ранг:

|(x₁; x₂;...x_n)|=n.

Если известны мощности множеств |X₁|=m₁, |X₂|=m₂,..|X_n|=m_n, то мощность прямого произведения есть

|(X₁X₂...X_n)|=m_1*m_2*..._*m_n.

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

Например, если дату в документах описывают кортежем (<число>”.”<месяц> ”.”<год>), то при описании множества документов удобно выделить в таблице такую структуру совместимых кортежей.

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

type t=record

element: data

next:t

end.

Специфической операцией, формирующий новый конструктивный объект на множествах, является прямая сумма. Она связывает имя - <идентификатор_множества> - i и его элементы - x, т. е.

{(i, x)| 1 i  n, xX_i}=X₁X₂..X_n.

Прямая сумма породила в языках программирования оператор case для поиска информации в базах данных.