Предмет дискретной математике

Пример 8.

Пусть M={1, 2, 3, 4, 5, 6}. Задать в явном виде (списком) и матрицей отношение r, заданное на множестве , если r  означает «быть строго меньше».

Отношение r как множество содержит все пары элементов a, b из М такие, что a<b. Тогда

r = {(1, 2), (1,3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)}.

Матрица отношения имеет вид:

.

Определение. Бинарное отношение f называется функцией, если из <x, y>Îf  и <x, z>Îf следует, что y=z.

Поскольку функции являются бинарными отношениями, то две функции f и g равны, если они состоят из одних и тех же элементов. Область определения функции обозначается D_f, а область значений – R_f. Определяются они так же, как и для бинарных отношений.

Если f – функция, то вместо <x, y>Îf пишут y=f(x) и говорят, что y – значение, соответствующее аргументу х, или y – образ элемента х при отображении f. При этом х называется прообразом элемента y.

Определение. Назовем f  n-местной функцией из Х в Y если f:Xⁿ®Y. Тогда пишем y=f(x₁, x₂, …, x_n) и говорим, что y – значение функции при значении аргументов x₁, x₂, …, x_n.

Пусть f:X®Y.

Определение. Функция f называется инъективной, если для любых х₁, х₂, y из y=f(x₁) и y=f(x₂) следует, что x₁=x₂, то есть каждому значению функции соответствует единственное значение аргумента.

Определение. Функция f называется сюръективной, если для любого элемента yÎY существует элемент хÎХ такой, что y=f(x).

Определение. Функция f называется биективной, если f одновременно сюръективна и инъективна.

Рисунок 9 иллюстрирует понятия отношения, функции, инъекции, сюръекции и биекции.

Пример 9.

Рассмотрим три функции, заданные на множестве действительных чисел  и принимающих значение в этом же множестве:

1. функция f(x)=e^x  - инъективна, но не сюръективна;
2. функция f(x)=x³-x – сюръективна, но не инъективна;
3. функция f(x)=2x+1 – биективна.

Определение. Суперпозиция функций – функция, полученная из системы функций f, f₁, f₂, …, f_k некоторой подстановкой функций f₁, f₂, …, f_k во внешнюю функцию f  вместо переменных и переименованиями переменных.

Пример 10.

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

 

1.5. Свойства бинарных отношений.  Специальные бинарные отношения

Определение. Отношение r на множестве Х называется рефлексивным, если для любого элемента хÎХ выполняется хr х.

Определение. Отношение r на множестве Х называется симметричным, если для любых х, уÎХ из хr у следует уr х.

Определение. Отношение r на множестве Х называется транзитивным, если для любых х, у, zÎХ из хr у и уr z следует хr z.

Определение. Рефлексивное, симметричное, транзитивное отношение на множестве Х называется отношением эквивалентности на множестве Х.

Пример 11.

1. Отношение равенства на множестве  целых чисел есть отношение  эквивалентности.

2. Отношение подобия на множестве  треугольников есть отношение  эквивалентности.

3. Отношение «строго меньше»  на множестве действительных  чисел не рефлексивно, не симметрично  и транзитивно на этом множестве.

4. Отношение перпендикулярности  прямых не рефлексивно, симметрично,  не транзитивно.

Пусть r - отношение эквивалентности на множестве Х.

Определение. Классом эквивалентности, порожденным элементом х, называется подмножество множества Х, состоящее из тех элементов yÎY, для которых хrу. Класс эквивалентности, порожденный элементом х, обозначается через [x]:

Определение. Отношение r на множестве Х называется антисимметричным, если для любых х, уÎХ из хr у и уr х следует х=у.

Определение. Рефлексивное, антисимметричное и транзитивное отношение называется отношением частичного порядка на множестве Х.

Пример 12.

1. Отношение «х £ у» на множестве действительных чисел есть отношение частичного порядка.

2. Схема организации подчинения  в учреждении есть отношение  частичного порядка на множестве  должностей.

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

 

1.6. Операции над  бинарными отношениями

Так как отношения на Х задаются подмножествами rÍX´Y, для них определимы те же операции, что и над множествами:

1. Объединение r₁Èr₂: r₁Èr₂={(х, у)| (х, у)Îr₁ или (х, у)Îr₂}.
2. Пересечение r₁Çr₂: r₁Çr₂={(х, у)| (х, у)Îr₁ и (х, у)Îr₂}.
3. Разность r₁\r₂: r₁\r₂={(х, у)| (х, у)Îr₁ и (х, у)Ï r₂}.
4. Дополнение : .
5. Обратное отношение r ^-1: х r ^-1 у тогда и только тогда, когда уrх, r ^-1={(x, y)| (y, x)Îr}.

Пример 13.

Если r - «быть моложе», то r ^-1 – «быть старше».

6. Составное отношение (композиция) r₁ · r₂. Пусть заданы множества М₁, М₂ и М₃ и отношения R₁ Í М₁ ´ М₂ и R₂ Í М₂ ´ М₃. Составное отношение действует из М₁ в М₂ посредством R₁, а затем из М₂ в М₃ посредством R₂, то есть (a, b) Î R₁·R₂,  если существует такое с Î М₂, что (а, с) Î R₁ и (a, c) Î R₂.
7. Транзитивное замыкание r°. Транзитивное замыкание состоит из таких и только таких пар элементов а и b из М, то есть (a, b)Îr°, для которых в М существует цепочка из (k+2) элементов М, k³ 0, что а, с₁, с₂, …c_k, b, между соседними элементами которой выполняется r. Другими словами а r с₁, с₁ r с₂, …, с_k r b.

Пример 14.

Для отношения «быть сыном» транзитивным замыканием является отношение «быть  прямым потомком по мужской линии».

 

1.7. Алгебраические  операции

Пусть дано множество М.

Определение. Говорят, что на М определена бинарная алгебраическая операция, если всякой упорядоченной паре элементов множества М по некоторому закону ставится в соответствие вполне определенный элемент этого же множества.

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

Среди известных бинарных операций, производимых не над числами, можно  отметить векторное умножение векторов пространства, умножение квадратных матриц порядка n, композицию отображений множества Х в себя, теоретико-множественное объединение и пересечение множеств.

	х1	х2	х3	х4
х1	х1	х2	х3	х4
х2	х2	х3	х1	х1
х3	х2	х3	х1	х2
х4	х4	х2	х1	х3

Фактическое задание алгебраической операции на множестве может быть произведено различными методами. Возможно также непосредственное перечисление всех результатов операций для конечных множеств. Его удобно описать с  помощью, так называемой таблицы  Кэли (табл.2). Слева и сверху квадратной таблицы выписывают все элементы множества. На пересечении строки, соответствующей элементу a, и столбца, соответствующего элементу b, записывают результат операции над a и b.

Будем употреблять следующую  терминологию и символику: операцию называть умножением, а результат применения операции к элементам a и b – произведением ab.

Определение. Если для любых элементов a и b множества М справедливо равенство ab = ba, то операцию называют коммутативной.

Определение. Если для любых элементов a, b, c множества М справедливо равенство a(bc) = (ab)c, то операцию называют ассоциативной.

В ряде случаев множество М, на котором  определена алгебраическая операция, обладает единичным элементом, т. е. таким элементом e, что ae = ea = a для всех a из М. Единичный элемент единственен.

Теорема. Если операция, определенная на М, ассоциативна, то результат ее последовательного применения к n элементам множества не зависит от расстановки скобок.

2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

Математическая логика – современный  вид формальной логики, то есть науки, изучающей умозаключения с точки зрения их формального строения.

Вплоть до начала XIX века формальная логика практически не выходила за рамки силлогических умозаключений. Однако, начиная с работ Дж. Буля, можно говорить о превращении ее в математическую логику. Особенности математической логики заключаются в ее математическом аппарате, в преимущественном внимании к умозаключениям, применяемым в самой математике.

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

 

2. 1. Логика высказываний

2. 1.1. Высказывания. Логические связки

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

Высказывания чаще всего обозначают маленькими латинскими буквами  a, b, c, х₁, х₂, …

В логике высказываний интересуются не содержанием, а истинностью или  ложностью высказываний. Истинностные значения – истина и ложь – будем обозначать И и Л соответственно. Множество {И, Л} называется множеством истинностных значений.

Определение. Высказывание называют простым (элементарным), если оно рассматривается как некое неделимое целое (аналогично элементу множества). Сложным (составным) называется высказывание, составленное из простых с помощью логических связок.

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

В дальнейшем значению «истина» будем  ставить в соответствие 1, а «ложь» - 0. Каждой логической операции ставится в соответствие таблица истинности. Таблица истинности выражает значения истинности высказываний в зависимости от значений элементарных высказываний. В дальнейшем буден использовать таблицу истинности для установления истинностных значений сложных высказываний при данных значениях входящих в него элементарных высказываний.

№ набора	a
0	0	1
1	1	0

Определение. Отрицанием высказывания является новое высказывание, истинное только тогда, когда исходное высказывание ложно (табл. 3).

Отрицание обозначается через и читается как «не а», «неверно, что а».

Пример 15.

А – «Степан любит танцевать».

Тогда - «Не верно, что Степан любит танцевать».

№ набора	a	b	aÙb
0	0	0	0
1	0	1	0
2	1	0	0
3	1	1	1

Определение. Конъюнкцией двух высказываний является новое высказывание, которое истинно только тогда, когда оба исходных высказывания истинны (табл. 4).