ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5246
Скачиваний: 10
11
Правило суммы.
Если
из
множества
S
подмножество
А
можно
выбрать
m
способами
,
а
подмножество
В
,
отличное
от
А
, n
способами
,
и
при
этом
выборы
А
и
В
таковы
,
что
взаимно
исклю
-
чают
друг
друга
и
не
могут
быть
получены
одновременно
,
то
вы
-
бор
из
S
множества
Α∪Β
можно
получить
m + n
способами
.
Правило
суммы
в
терминах
теории
множеств
:
если
даны
m-
множество
S
и
n-
множество
Т
(
элементами
которых
являются
в
нашем
случае
выбранные
подмножества
),
то
при
S
∩Τ=∅
объе
-
динение
S
∪Τ
будет
(m+n)-
множеством
.
Правило произведения.
Если
из
множества
S
подмножест
-
во
А
может
быть
выбрано
m
способами
,
а
после
каждого
такого
выбора
можно
n
способами
выбрать
подмножество
В
,
то
выбор
А
и
В
в
указанном
порядке
можно
осуществить
m
×
n
способами
.
В
терминах
теории
множеств
это
правило
соответствует
произведе
-
нию
множеств
:
если
S
является
m-
множеством
,
а
Т
есть
n-
множество
,
то
S
×
T
окажется
(m
×
n)-
множеством
.
Отображения.
В
последующем
будут
использованы
три
спо
-
соба
отображения
:
некоторого
множества
S
в
некоторое
другое
множество
Т
,
множества
S
на
множество
Т
и
множества
S
на
себя
.
Отображение
α
множества
S
в
множество
Т
называется
со
-
ответствие
между
ними
,
при
котором
каждому
элементу
s
∈
S
со
-
поставлен
единственный
элемент
t= s
α∈Τ
.
Элемент
s
α
называет
-
ся
образом
элемента
s
при
отображении
α
.
Два
отображения
α
и
β
равны
,
если
s
α
=s
β
для
всех
s
∈
S.
Отображением
α
множества
S
на
множество
Т
характеризу
-
ется
тем
,
что
всякий
элемент
t
∈
T
оказывается
образом
данного
или
нескольких
элементов
s
∈
S.
В
частности
,
если
различным
s
∈
S
соответствуют
различные
образы
,
то
отображение
α
называется
однозначным
,
или
(1–1)-
отображением
.
Отображением
α
множества
S
на
себя
называется
отображе
-
ние
,
при
котором
образом
является
элемент
того
же
множества
,
т
.
е
.
когда
s
α∈
S
для
всех
s
∈
S.
Примером
такого
отображения
служат
перестановки
.
Отношения
.
Это
один
из
способов
задания
взаимосвязей
между
элементами
множества
.
Наиболее
изученными
являются
унарные
и
бинарные
отношения
.
12
Унарные
(
одноместные
)
отношения
отражают
наличие
ка
-
кого
-
то
определённого
признака
R (
свойства
и
т
.
п
.)
у
элементов
множества
S (
например
, «
быть
отличником
»
на
множестве
сту
-
дентов
группы
).
Тогда
все
такие
элементы
а
из
множества
S ,
ко
-
торые
отличаются
данным
признаком
R,
образуют
некоторое
подмножество
из
S ,
называемое
унарным
отношением
R,
т
.
е
.
а
∈
R
и
R
⊆
S.
Бинарные
(
двухместные
)
отношения
используются
для
оп
-
ределения
каких
-
то
взаимосвязей
,
которыми
характеризуются
па
-
ры
элементов
в
множестве
S (
так
на
множестве
людей
могут
быть
заданы
,
например
,
бинарные
отношения
«
жить
в
одном
городе
»,
«
учиться
в
одном
университете
»
и
т
.
п
.).
Тогда
все
пары
(a,b)
эле
-
ментов
из
S ,
между
которыми
имеет
место
данное
отношение
R ,
образуют
подмножество
пар
из
множества
всех
возможных
пар
элементов
S
×
S= S
2
,
называемое
бинарным
отношением
R,
т
.
е
. (a,
b)
∈
R,
при
этом
R
⊆
S
×
S.
Бинарные
(
двухместным
)
отношения
R
могут
рассматри
-
ваться
как
подмножество
пар
(a, b)
∈
R
множеств
S
1
×
S
2
,
т
.
е
.
R
⊆
S
1
×
S
2.
При
этом
множество
S
1
называют
областью
определе
-
ния
отношения
R ,
множество
S
2
–
областью
значений
.
В
общем
случае
могут
рассматриваться
n-
отношения
,
на
-
пример
отношения
между
тройками
элементов
–
трёхместные
(
тернарные
)
отношения
и
т
.
д
.
Если
a, b
находятся
в
отношении
R ,
это
записывается
как
a R b .
Отношение порядка.
Множество
называется
упорядочен
-
ным
,
если
для
любой
пары
элементов
можно
установить
отноше
-
ние
порядка
(
выражаемое
через
понятия
«
больше
», «
меньше
»,
«
содержится
в
», «
содержит
», «
предшествует
», «
следует
за
»
и
обо
-
значаемое
символами
≤
,
≥
,
⊆
,
⊇
).
Две
r-
выборки
а
=(
а
1
,
а
2
, ... ,
а
r
)
и
в
=(
в
1
,
в
2
, ... ,
в
r
)
называются
упорядоченными
,
если
а
=
в
лишь
при
условии
,
что
а
i
=
в
i
, i=1,2, ... ,
r ,
и
неупорядоченными
,
если
а
=
в
лишь
при
условии
,
что
каждое
а
i
равно
некоторому
в
i
, i,j=1,2, ... , r.
Отношение
порядка
формально
вводится
посредством
акси
-
ом
:
1)
а
≤а
для
любого
а
∈
S (
рефлексивность
);
13
2)
если
а
,
в
∈
S
и
а
≤в
,
и
в
≤а
,
то
а
=
в
(
антисимметричность
или
равенство
);
3)
если
а
≤в
и
в
≤с
,
то
а
≤с
(
транзитивность
),
а
,
в
,
с
∈
S).
Всякое
отношение
,
удовлетворяющее
этим
трем
аксиомам
,
является
отношением
нестрогого
порядка
.
Если
отношение
антирефлексивно
,
антисимметрично
,
тран
-
зитивно
,
его
называют
отношением
строгого
порядка
.
Например
,
отношения
«
быть
не
старше
»
на
множестве
людей
, «
быть
не
больше
»
на
множестве
натуральных
чисел
–
нестрогий
порядок
;
отношения
«
быть
моложе
», «
быть
прямым
потомком
»
на
множестве
людей
–
строгий
порядок
.
Элементы
a,b
∈
S
сравнимы
по
отношению
порядка
R
на
множестве
S ,
если
выполняется
a R b
или
b R a.
Множество
S ,
на
котором
задано
отношение
порядка
,
может
быть
:
-
полностью
упорядоченным
множеством
,
если
любые
два
элемента
из
S
сравнимы
по
отношению
порядка
.
В
таком
случае
говорят
,
что
отношение
R
задаёт
полный
порядок
на
множестве
S.
Например
,
отношение
«
быть
не
старше
»
задаёт
полный
поря
-
док
на
множестве
людей
;
-
частично
упорядоченным
множеством
–
в
противном
слу
-
чае
.
При
этом
говорят
,
что
отношение
R
задаёт
на
множестве
S
частичный
порядрк
.
Например
,
отношение
«
быть
начальником
»
задаёт
на
множестве
сотрудников
организации
частичный
поря
-
док
,
так
как
для
пары
сотрудников
одного
отдела
данное
отно
-
шение
не
выполняется
:
они
не
сравнимы
по
данному
отношению
.
Введем
еще
одно
алгебраическое
понятие
,
которое
нам
по
-
надобится
в
последующем
.
Пусть
задано
множество
М
элементов
произвольной
природы
.
Определение 1.
Говорят
,
что
в
множестве
М
определена
ал
-
гебраическая
операция
,
обозначаемая
произвольным
символом
•
,
+,
∗
,
если
∀а
,
в
∈Μ
однозначным
образом
определен
результат
применения
этой
операции
.
Определение 2.
Множество
М
,
замкнутое
относительно
не
-
которой
алгебраической
операции
называется
группоидом
,
т
.
е
.
∀а
,
в
∈Μ
имеет
место
а
∗в
=
с
∈М
.
14
Определение 3.
Группоид
М
называется
полугруппой
отно
-
сительно
рассматриваемой
операции
,
если
эта
алгебраическая
операция
ассоциативна
,
т
.
е
.
∀а
,
в
,
с
∈Μ
имеет
место
(
а
∗в
)
∗с
=
=
а
∗
(
в
∗с
).
Определение 4.
Элемент
0
∈М
называется
нулем
полугруп
-
пы
,
если
∀а∈Μ
имеет
место
0
∗а
=
а
.
Определение 5.
Полугруппа
называется
коммутативной
,
ес
-
ли
∀а
,
в
∈Μ
имеет
место
а
∗в
=
в
∗а
.
Определение 6.
Множество
R
называется
кольцом
,
если
в
нем
определены
две
операции
−
сложение
и
умножение
,
обе
коммута
-
тивные
,
ассоциативные
,
а
также
связанные
законом
дистрибутивно
-
сти
,
причем
сложение
обладает
обратной
операцией
–
вычитанием
.
Не
останавливаясь
подробно
на
определении
кольца
,
рас
-
смотрим
одно
из
его
обобщений
.
Определение 7.
Множество
К
с
заданными
на
нем
опера
-
циями
«+» (
сложение
)
и
«
∗
» (
умножение
)
называется
полуколь
-
цом
,
если
:
1)
К
образует
относительно
сложения
коммутативную
полу
-
группу
с
«0»;
2)
К
является
группоидом
относительно
умножения
;
3)
∀а∈К
, 0
∗Х
=
Х
∗
0 = 0.
Одним
из
примеров
полукольца
является
множество
целых
чисел
относительно
обычных
операций
сложения
и
умножения
.
Примером
кольца
также
является
булева
алгебра
В
={0,1}
из
двух
элементов
:
0+0=0; 0
∗
0=0
∗
1=1
∗
0=0;
0+1=1+0=1+1=1; 1
∗
1=1.
Наиболее
общим
способом
задания
полукольца
является
за
-
дание
системы
образующих
элементов
и
соотношений
.
Наиболее
общим
способом
задания
полукольца
является
за
-
дание
системы
образующих
(
порождающих
)
элементов
и
соотно
-
шений
.
Образующие
(
порождающие
)
элементы
универсальной
ал
-
гебры
A –
15
подмножество
X
элементов
универсальной
алгебры
,
такое
,
что
минималь
ная
подалгебра
A,
содержащая
Х
,
есть
сама
A.
Универсальная
алгебра
−
непустое
множество
,
на
котором
заданы
некоторые
алгебраические
операции
.
Перечень
всех
символов
,
соответствующих
элементам
мно
-
жества
,
называется
его
алфавитом
,
а
неопределённый
символ
,
который
может
становиться
любым
элементом
множества
,
назы
-
вают
логической
переменной
.
По
отношению
к
логической
пере
-
менной
каждый
частный
символ
является
его
значением
.
Более
строго
можно
сказать
,
что
алфавит
–
любая
конечная
система
символов
.
Символы
,
составляющие
алфавит
,
называют
буквами
.
Например
,
рассмотрим
множество
М
={
ξ,η
,
ζ,θ,
0}.
Здесь
{
ξ,η
,
ζ,θ,
0} –
алфавит
,
ξ,η
,
ζ,θ,
0 –
буквы
.
Определение 8.
Будем
называть
Словом
некоторую
конеч
-
ную
запись
,
составленную
из
элементов
,
знаков
,
операций
и
ино
-
гда
скобок
.
Словом
являются
,
во
-
первых
,
сами
элементы
.
Далее
слова
определяются
рекурсивно
,
т
.
е
.
если
известно
,
что
ω
1
и
ω
2
−
слова
,
то
ω
1
+ω
2
и
ω
1
∗ω
2
−
слова
и
т
.
д
.
Определение 9.
Множество
всех
слов
,
рассмотренное
отно
-
сительно
операций
«+»
и
«
∗
»,
которые
обладают
всеми
тремя
свойствами
из
определения
полукольца
,
называются
свободным
полукольцом
над
системой
образующих
М
.
В
свободном
полукольце
,
вообще
говоря
,
никакие
два
слова
не
тождественны
в
данном
полукольце
,
т
.
е
.
постулируется
,
на
-
пример
,
что
ω
1
=
ω
2
,
где
ω
1
и
ω
2
некоторые
слова
,
то
это
равенство
называется
соотношением
в
свободном
полукольце
.
В
свою
оче
-
редь
соотношение
порождает
набор
соотношений
−
следствий
из
исходного
.
Например
,
если
наложено
соотношение
ω
1
=
ω
2
,
то
и
ω
1
+
ω
2
=
ω
1
+
ω
1
,
и
ω
1
∗ω
2 =
ω
1
∗ω
1
.
Определение 10.
Система
или
набор
соотношений
называет
-
ся
набором
определяющих соотношений
,
если
все
остальные
соотношения
,
имеющиеся
в
данном
полукольце
являются
следст
-
вием
данного
соотношения
.