Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

5 оказались настолько велики, что она не могла остаться долго без внимания и сейчас в обязательном порядке входит в курс дискретной математики. Прямое произведение множеств Рассмотрим два множества A и B . Прямым произведением множеств А и В (обозначение А  В ) называется множество упорядоченных пар ( а, в ) таких, что a  A, b  B . В частности, если A=B , то такое произведение обозначается A 2 . Аналогично прямым произведением множеств A 1 ,…A n (обозначение A 1  …  A n ) называется множество всех упорядоченных наборов ( a 1 ,…,a n ) длины n таких, что a 1  A 1 ,…, a n  A n . A  …  A обозначается A n . Соответствия и функции Соответствием между множествами А и В называется подмножество G  A  B . Если (a,b)  G , то говорят, что b соответствует а при соответствии G . Проекцией подмножества G  A  B на множество A называется множество элементов a  A таких, что (a,b)  G (обозначение пр A G ). Аналогично пр B G – это множество элементов b  B таких, что (a,b)  G . Множество пр A G называется областью определения соответствия, а множество пр B G – областью значений соответствия. Если пр A G=A, то соответствие называется всюду определенным (в противном случае соответствие называется частичным); если пр B G=B , то соответствие называется сюръективным. Множество всех b  B , соответствующих элементу a  A , называется образом a в B при соответствии G . Множество всех a , которым соответствует b , называется прообразом b в A при соответствии G . Соответствие G называется функциональным (или однозначным), если образом любого элемента из пр A G