17. Функциональное бинарное отношений (функция, отображение). Определение, примеры. Инъекция, сюръекция, биекция. Произведение биективных отображений.

Опр. Бинарное отнош.F определен.на A,B назыв. отображением A,B (функц.со знач.А на В), если для кажд. х А существ.единств. у В, что х и у наход.в отнош. 1) x f y, 2) x f y₁ & x f y₂=> y₁=y₂

Примеры: а) Рассм.бинарн.отнош.на мн-ве 2х+3у=12. у=(12-2х)/3, б) x²+y²=25 на множ. R, в) х – отец, у на множ.людей – не явл.функцион., г) х – сын, у – функциональное бинарное отнош.

Опр. Отображ. f: X->X назыв. Инъективным, если различным эл-там из Х соответ.различн.элемент из У. (x₁ x₂=>F(x₁) F(x₂))

Опр. Отображ. f: X->X назыв. сюрьективным, если кажд.элем.у из У имеет хотяб один прообраз в Х. (y₀ Y, F(x)=y₀) - должно иметь 1 реш.)

Опр. Отображ. f X и Y биективно, если оно и инъективно, и сюръективно. (взаимнооднозначн.отображ. Х на У)

Опр. Произведением отображений f:Х→Y и g:Y →Z называется отображение gf:X→Z  определяемое равенством (gf)(x)=g(f(x)).

18)Отношение эквивалентности, смежные классы. Определение, примеры. Связь с разбиениями множеств.

Опр. Бинарн.отнош. ρ определенное на множ.А наз.отнош.эквивалентности, если оно: 1)рефлексивно, т.е. a ρ a, a A, 2)симметрично, т.е. aρb, bρa, a,b A, 3)транзитивно, т.е. аρb, bρc => aρc; a,b,c A

Пример: отнош.подобия, отнош.учиться в 1ой группе?!, отнош.сравнимости по модулю n.

Опр. Пусть ρна А, тогда {xρa}, а А назыв. смежным классом [a]_ρ.

Отнош.эквивалентности на А определяет разбиение этого мн-ва на смежные мн-ва.

Пример: . Если ad=bc – эквивалентность.

26)Булевы функции. Сднф и скнф. Приложения. Полные системы булевых функций, критерий.

Булевы функции–сложные высказывания, которые рассматриваются как функции, определённые на мн-ве Eⁿ всевозможных значений n булевых переменных (Л и И или 1 и 0)и принимающих значения из множества E. Другими словами, всякая булева функция рассматривается как отображение f: Eⁿ →E. Булевы функции нуля, одной и двух переменных называют элементарными. Функции нуля переменных–это константы 0 и 1.

Конъюнктивной  нормальной  формой (КНФ) называется  конъюнкция  простых дизъюнкций (например, выражение (xVyV )(xVz)(yV ) – КНФ).

Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.Напр., выражение (xVyV )(xVz)(yV ) является СКНФ.

Дизъюнктивной нормальной формой (ДНФ)  называется  дизъюнкция  простых конъюнкций. Например, выражение xy V z является ДНФ.

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

Например, выражение xVy является ДНФ, но не СДНФ. Выражение xyz V x  V yz является СДНФ.

Свойства СДНФ:

1)В ней нет 2-х одинаковых сомножителей.

2)Ни одно слагаемое не содержит 2-х одинаковых множителей.

3)Никакой слагаемое не содержит переменную и его отрицание.

4) В каждом слагаемом в качестве сомножителя содержится либо x_i, либо его отрицание.

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

Критерий Поста: Набор булевых функций K является полным тогда и только тогда, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.