Теоретическая часть

1. Логические операции. Формулы логики. Таблица истинности. Дизъюнктивная и конъюнктивная нормальные формы

Формулы логики высказываний

Определим понятие формулы логики высказываний.

Определение. Алфавитом называется любое непустое множество. Элементы этого множества называются символами данного алфавита. Словом в данном алфавите называется произвольная конечная последовательность символов (возможно пустая).

Алфавит логики высказываний содержит следующие символы:

высказывательные переменные;

логические символы;

символы скобок.

Определение. Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:

любая высказывательная переменная – формула;

если А и В – формулы, то Ø А, А Ù В, АÚ В, А® В, АÅ В, А»В, А ï В, А ¯ В – формулы;

только те слова являются формулами, для которых это следует из 1) и 2).

Определение. Подформулой формулы А называется любая ее часть, которая сама является формулой.

Логические операции

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

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

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

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

Конъюнкция обозначается или a& b и читается как «a и b», «a, но b», «a, а b».

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

Дизъюнкция обозначается через и читается как «a или b».

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

Импликация обозначается a® b и читается как «если a, то b»; «из а следует b». При этом a называется посылкой или условием, b – следствием или заключением

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

Эквивалентность обозначается a» b и читается как «a эквивалентно b».

Таблица истинности — это таблица, описывающая логическую функцию.

Таблица истинности выражает значения истинности высказываний в зависимости от значений элементарных высказываний. Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность. Например, в двузначной логике они могут принимать значения «истина» либо «ложь». Табличное задание функций встречается не только в логике, но для логических функций таблицы оказались особенно удобными, и с начала XX века за ними закрепилось это специальное название. Особенно часто таблицы истинности применяются в булевой алгебре и в аналогичных системах многозначной логики.

Нормальные формы

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

Иногда будем допускать в элементарной конъюнкции наличие повторов элементов.

Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция попарно различных элементарных конъюнкций.

Иногда будем допускать в ДНФ наличие повторов элементов.

Пример 25.

Следующие формулы находятся в ДНФ: .

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

Иногда будем допускать в элементарной дизъюнкции наличие повторов элементов.

Определение. Конъюнктивной нормальной формой (КНФ) называется конъюнкция попарно различных элементарных дизъюнкций.

Иногда будем допускать в КНФ наличие повторов элементов.

2. Законы логики. Равносильные преобразования

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

Рассмотрим основные равносильности логики высказываний.

Пусть А, В, С – произвольные формулы. Тогда справедливы следующие свойства логических операций (табл. 11):

Таблица 11

1. Идемпотентность
А Ù А = А	А Ú А = А
2. Коммутативность
А Ù В = В Ù А	А Ú В = В Ú А
3. Ассоциативность
А Ù (В Ù С) = (А Ù В) Ù С	А Ú (В Ú С) = (А Ú В) Ú С
4. Правила поглощения
А Ù (А Ú В) = А	А Ú (А Ù В) = А
5. Дистрибутивность
А Ù (В Ú С) = (А Ù В) Ú (А Ù С)	А Ú (В Ù С) = (А Ú В) Ù (А Ú С)
6. Правила де Моргана
7. Свойства констант
А Ù 1 = А А Ù 0 = 0	А Ú 0 = А А Ú 1 = 1
8. Закон исключения третьего и закон противоречия
9. Снятие двойного отрицания
10. Формулы расщепления (склеивания)
11. Связь дизъюнкции, конъюнкции, отрицания и импликации
12. Выражение эквивалентности

Любая из этих равносильностей легко может быть доказана с помощью таблицы истинности.

3. Понятие булева вектора (двоичного вектора). Соседние векторы. Противоположные векторы. Единичный N-мерный куб.

4. Понятие булевой функции (функции алгебры логики). Способы задания булевой функции. Проблема представления булевой функции в виде формулы логики.

Булевой функцией f(x₁, x₂, …, x_n) называется n-местная функция, аргументы которой принимают значения во множестве {0, 1} и сама функция принимает значения в этом же множестве.

Всякую булеву функцию от n переменных можно задать таблицей из 2ⁿ строк, в которой в каждой строке записывают одну из оценок списка переменных, принимающих значение 0 или 1.

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

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

Существует ровно различных булевых функций от n переменных. Константы 0 и 1 считают нуль-местными булевыми функциями.

Утверждение. Каждой формуле логики высказываний соответствует некоторая булева функция.

Теорема. Пусть f(x₁, x₂, …, x_k) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x₁, x₂, …, x_n и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.

Теорема 2. Пусть f(x₁, x₂, …, x_k) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x₁, x₂, …, x_k и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.

5. Понятие совершенной ДНФ. Методика представления булевой функции в виде совершенной ДНФ.

Совершенные нормальные формы

Определение. Совершенной дизъюнктивной формулой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой:

различны все члены дизъюнкции;

различны все члены каждой конъюнкции;

ни одна конъюнкция не содержит одновременно переменную и отрицание этой переменной;

каждая конъюнкция содержит все переменные, входящие в формулу,

Теорема. Пусть f(x₁, x₂, …, x_k) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x₁, x₂, …, x_n и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.

6. Понятие совершенной КНФ. Методика представления булевой функции в виде совершенной КНФ.

Определение. Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:

различны все члены конъюнкции;

различны все члены каждой дизъюнкции;

ни одна дизъюнкция не содержит переменную вместе с отрицанием этой переменной;

каждая дизъюнкция содержит все переменные, входящие в исходную формулу

Теорема 2. Пусть f(x₁, x₂, …, x_k) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x₁, x₂, …, x_k и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.

7. Понятие минимальной ДНФ. Методика представления булевой функции в виде минимальной КНФ.

Определение. Минимальной ДНФ (МДНФ) функции f(x₁, x₂, …, x_n) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими ДНФ, реализующими функцию f.

8. Операция двоичного сложения и ее свойства. Многочлен Жегалкина. Методика представления булевой функции в виде многочлена Жегалкина.

9. Полнота множества функций. Важнейшие замкнутые классы. Теорема Поста.

10. Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество; количество подмножеств конечного множества. Теоретико-множественные диаграммы. Операции над множествами и их свойства.

Множество – простейшее, неопределенное понятие. Совокупность элементов рассматриваемых как единое целое – множество. Объекты из которых состоит множество называют элементами данного множества. Множества обозначают большими буквами латинского алфавита, элементы – малыми. При задании множеств перечислением обозначения элементов обычно заключают в фигурные скобки и разделяют запятыми. Перечислением можно задавать только конечные множества (число элементов множества конечно, в противном случае множество называется бесконечным). М={1, 2, 3, 4} Бесконечные множества задаются характеристическим предикатом или порождающей процедурой: - характеристический предикат; Числа Фибоначчи задаются условиями (порождающей процедурой): а₁=1, а₂=2, a_n=a_n-1+a_n-2 для n> 2.

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

Подмножество – множество А называется подмножеством множества В и обозначается АсВ, если любой элемент множества А принадлежит множеству В.

Два множества считаются равными если они состоят из одних и тек же элементов: А = В. Множество U называется универсальным, то есть все рассматриваемые множества являются его подмножеством

Диаграммы Эйлера-Венна – геометрические представления множеств. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри его – кругов (или каких-нибудь других замкнутых фигур), представляющих множества. Фигуры должны пересекаться в наиболее общем случае, требуемом в задаче, и должны быть соответствующим образом обозначены. Точки, лежащие внутри различных областей диаграммы, могут рассматриваться как элементы соответствующих множеств. Имея построенную диаграмму, можно заштриховать определенные области для обозначения вновь образованных множеств.

Определение. Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (рис. 1):

Определение. Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат одновременно как множеству А, так и множеству В (рис. 2):

Определение. Разностью множеств А и В называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 3):

Определение. Симметрической разностью множеств А и В называется множество элементов этих множеств, которые принадлежат либо только множеству А, либо только множеству В (рис. 4):

Определение. Абсолютным дополнением множества А называется множество всех тех элементов, которые не принадлежат множеству А (рис. 5):

1. Коммутативность объединения	1’. Коммутативность пересечения
2. Ассоциативность объединения	2’. Ассоциативность пересечения
3. Дистрибутивность объединения относительно пересечения	3’. Дистрибутивность пересечения относительно объединения
4. Законы действия с пустым и универсальным множествами	4’. Законы действия с пустым и универсальным множествами
5. Закон идемпотентности объединения	5’. Закон идемпотентности пересечения
6. Закон де Моргана	6’. Закон де Моргана
7. Закон поглощения	7’. Закон поглощения
8. Закон склеивания	8’. Закон склеивания
9. Закон Порецкого	9’. Закон Порецкого
10. Закон двойного дополнения

11. Понятие множества. Декартова степень множества.

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

Пара объектов а, в называется упорядоченной если на ней введен порядок, то есть известно какой объект первый и второй. Обозначение: < а, в>, {а, в} – неупорядоченная пара.

Упорядоченная пара < а, в> = упорядоченной паре < с, d> тогда и только тогда когда а = с, в = d

Пусть даны два множества А и В произвольных. Декартовым произведением А на В (AxB) называется множество всех упорядоченных пар < а, в> таких что а пренадлежит множеству А, в принадлежит В.

AxB = {< a.b> | a c A. b c B}

12. Понятие множества. Соответствие между теоретико-множественными и логическими операциями.

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

13. Понятие предиката. Область определения и область истинности предиката. Обычные логические операции над предикатами.

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

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

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

Одноместным предикатом Р(х) на­зывается произвольная функция переменного х, опреде­ленная на множестве М и принимающая значения из

множества {1, 0}.

Множество М, на котором определен предикат P(х), называется областью определения предиката.

Множество всех элементов х Î М, при которых преди­кат принимает значение «истина», называется множеством истинности предиката Р(х), то есть множество истиннос­ти предиката Р(х) - это множество 1р = {х| х Î М, Р(х) = 1}.

Предикаты, так же, как высказывания, принимают два значения истина и ложь (1, 0), поэтому к ним применимы все операции логики высказываний. Определение: Конъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х)LQ{x), который принимает значение «истина» при тех и только тех зна­чениях х Î М, при которых каждый из предикатов при­нимает значение «истина», и принимает значение «ложь» во всех остальных случаях.

Областью истинности предиката P(x)LQ(x) является общая часть областей истинно­сти предикатов Р(х) и Q(x), то есть: I_PLQ = Iр Ç Iq. Определение. Дизъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х)V Q(x), который принимает значение «ложь» при тех и только тех значе­ниях х Î М, при которых каждый из предикатов при­нимает значение «ложь» и принимает значение «истина»во всех остальных случаях.

Областью истинности предиката Р(х)V Q(x) является объединение областей истинности предикатов Р(х) и Q(x), то есть: I_PVQ = Iр È Iq.

Определение. Отрицанием предиката Р(х) назы­вается новый предикат, который принимает значе­ние «истина» при всех значениях х Î М, при которых предикат Р(х) принимает значение «ложь», и принима­ет значение «ложь» при тех значениях х Î М, при кото­рых предикат Р(х) принимает значение «истина».

Определение. Импликацией предикатов Р{х) и Q(х) называется новый предикат Р(x)® Q(x), который является ложным при тех и только тех значениях х Î М, при которых одновременно Р(х) принимает значение «истина», a Q(x) - значение «ложь» и принимает значе­ние «истина» во всех остальных случаях.

14. Понятие предиката.

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

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

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

Одноместным предикатом Р(х) на­зывается произвольная функция переменного х, опреде­ленная на множестве М и принимающая значения из

множества {1, 0}.

Множество М, на котором определен предикат P(х), называется областью определения предиката.

Множество всех элементов х Î М, при которых преди­кат принимает значение «истина», называется множеством истинности предиката Р(х), то есть множество истиннос­ти предиката Р(х) - это множество 1р = {х| х Î М, Р(х) = 1}.

15. Кванторные операции над предикатами.

Пусть имеется предикат Р(х), определенный на мно­жестве М. Если а с М, то при подстановке а вместо х в предикат Р(х) получится высказыва­ние Р(а). Такое высказывание называется единичным. Наряду с образованием из предикатов единичных выс­казываний в логике предикатов рассматривается еще две операции, которые превращают одноместный пре­дикат в высказывание.

Определение 8. Пусть Р(х) – предикат, определен­ный на множестве М. Под выражением понима­ют высказывание, истинное, когда Р(х) тождественно истинный на множестве М предикат, и ложное в против­ном случае. Это высказывание уже не зависит от х. Со­ответствующее ему словесное выражение будет: «Для вся­кого х Р(х) истинно». Символ называют квантором всеобщности.

Переменную х в предикате Р(х) называ­ют свободной (ей можно придавать различные значения из М), в высказывании переменную х называют связанной квантором .Определение 9. Пусть Р(х) – предикат, определенный на множестве М. Под выражением понимают выс­казывание, которое является истинным, если существует хотя бы один элемент , для которого Р(х) истинно, и ложным в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение будет: «Существует х, при котором Р(х) истинно». Сим­вол называют квантором существования. В высказы­вании переменная х связана квантором .Пример 5. Пусть на множестве N натуральных чисел задан предикат Р(х): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания: – «Все натуральные числа кратны 5»; – «Су­ществует натуральное число, кратное 5». Очевидно, пер­вое из этих высказываний ложно, а второе истинно.

Ясно, что высказывание истинно только в том единственном случае, когда Р(х) – тождественно истинный предикат, а высказывание ложно толь­ко в том единственном случае, когда Р(х) – тождествен­но ложный предикат.

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

16. Понятие предиката. Понятие предикатной формулы; свободные и связанные переменные.

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

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

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

Одноместным предикатом Р(х) на­зывается произвольная функция переменного х, опреде­ленная на множестве М и принимающая значения из

множества {1, 0}.

Множество М, на котором определен предикат P(х), называется областью определения предиката.

Множество всех элементов х Î М, при которых преди­кат принимает значение «истина», называется множеством истинности предиката Р(х), то есть множество истиннос­ти предиката Р(х) - это множество 1р = {х| х Î М, Р(х) = 1}.

17. Понятие предиката.

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

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

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

Одноместным предикатом Р(х) на­зывается произвольная функция переменного х, опреде­ленная на множестве М и принимающая значения из

множества {1, 0}.

Множество М, на котором определен предикат P(х), называется областью определения предиката.

Множество всех элементов х Î М, при которых преди­кат принимает значение «истина», называется множеством истинности предиката Р(х), то есть множество истиннос­ти предиката Р(х) - это множество 1р = {х| х Î М, Р(х) = 1}.

18. Построение отрицаний к предикатам, содержащим кванторные операции.

19. Понятие бинарного отношения; примеры бинарных отношений. Диаграмма бинарного отношения.

Пусть А и В - множества. Выражение вида (а, в), где и , называется упорядоченной парой. Бинарным отношением называется любое множество упорядоченных пар. Пусть даны два множества А и В. Бинарным отношением на паре множеств А и В называется любое подмножество декартова произведения А на В. R c AxB. Определение 1.1. Декартовым произведением множеств А и В называется множество Аx В всех упорядоченных пар (а, в) таких, что а А, в В.

Определение 1.2. Соответствием между множествами А и В (или соответствием из А в В) называется любое подмножество декартова произведения АxВ. Если множества А и В совпадают, то соответствие между множествами А и В называют также бинарным отношением на множестве А. Хорошо известными примерами отношений из школьного курса математики являются:

на множестве целых чисел Z отношения " делится", " делит", " равно", " больше", " меньше", " взаимно просты";

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

на множестве окружностей плоскости " пересекаются", " касаются", " концентричны".

20. Понятие бинарного отношения. Рефлексивные бинарные отношения. Симметричные бинарные отношения. Транзитивные бинарные отношения.

Пусть А и В - множества. Выражение вида (а, в), где и , называется упорядоченной парой. Бинарным отношением называется любое множество упорядоченных пар. Пусть даны два множества А и В. Бинарным отношением на паре множеств А и В называется любое подмножество декартова произведения А на В. R c AxB.

Свойства бинарных отношений: Пусть R – бинарное отношение на множестве А, А=О. R c AxA. 1) R называется рефлексивным, если Ja c R (то есть R содержит диагональ множества А). 2) R называется антирефлексивным, если пересечение R и диагонали множества A – пусто. 3) R называется симметричным, если вместе с каждой упорядоченной парой R содержит также инверсную с ней. Инверсной парой называется (х, у) по отношению к (у, х). Упорядоченные пары (х, у) и (у, х) наз-ся взаимноинверсными. (х, у) R (у, х) R или хRу уRх. 4) R называется антисимметричным, если оно не содержит никаких двух различных взаимноинверсных пар. хRх можно. xRy и yRx х=у. 5) R называется транзитивным, если для любых трёх элементов множества А: х, у, z из того, что хRу и уRz хRz. 6) R называется связным, еслидля любых двух х, у А выполняется хотя бы одно из трёх условий: хRу, уRх, х=у.

21. Понятие бинарного отношения. Отношение эквивалентности; теорема о разбиении множества на классы эквивалентности.

Пусть А и В - множества. Выражение вида (а, в), где и , называется упорядоченной парой. Бинарным отношением называется любое множество упорядоченных пар. Пусть даны два множества А и В. Бинарным отношением на паре множеств А и В называется любое подмножество декартова произведения А на В. R c AxB. Бинарное отношение R на множестве A называется отношением эквивалентности на A, если R рефлексивно, симметрично и транзитивно. Семейство непустых подмножеств множества А называется разбиением множества А, если объединение всех подмножеств этого семейства совпадает с множеством А и при этом различные подмножества данного семейства не пересекаются. Теорема: Пусть А не пустое множество, R- отношение эквивалентности на множестве А. Тогда фактор-множество А/ R – есть разбиение множества А. Доказательство:

22. Понятие отображения. Взаимооднозначные (биективные) отображения. Операция композиции отображений и ее свойства.

Пусть А и Б не пустые множества R c AxB. Бинарное отношение на паре множеств А и Б называется функцией (отображением) из А в Б если для каждого элемента а из множества А сушествует единственный элемент в из множества В (а, в принадлежит R).

Обозначение: f g h

Пусть f фунция из А в В. Для любого а из множества А, сушествует единстьвенный в из множества В: (а, в) принадлежит R, (а, в) принадлежит f. в = F(а) в – образ элемента а при отображении F, а – прообраз элемента в. Образ всегда один, прообраз один, F: А --» В

F = {(а, f(а) /а принадлежит А} Равными мы считаем функции, если они ровны как отношения (Бинарные), то есть g: A--»В и f: A--»В, f = g тогда и только тогда, если для любого а из множества А: f(a) = g(a)

f – называется инъективной если она переводит разные элементы в разные.

f – называется сюръективной функцией если любой элемент в из множества В имеет хотя бы один прообраз.

f – называется биективной если она одновременно еньективна и сюръективна.

f – называется биекцией если любой в из множества В имеет ровно один прообраз.

Биекция это взаимно однозначные отображения.

Определение

Данное множество является функцией из А в С и называется композицией функций