Лекции по дискретна математика


Категория на документа: Математика


1. Множества.

Въвеждаме понятието множество като съвкупност от елементи;
елементите могат да бъдат протоелементи – всеки реален или измислен математически обект, който не е множество – или самите те могат да бъдат добре дефинирани множества;
едно множество е добре дефинирано, ако се знае кои са
елементите му, т.е. те са дефинирани преди това;
нека М е множество; ще отбелязваме x  M, ако обектът x е елемент на M или x  M, ако x не е елемент на М; ако М е добре дефинирано множество, то за всеки обект x е изпълнено точно едно от x  M,
x  M;
ще казваме, че множествата A и B са равни, когато са съставени от едни и същи елементи, бележим A = B;
един начин за задаване на множество е чрез изреждане на елементите в него, разделени със запетая между фигурни скоби;
оттук нататък всички множества ще считаме, че са добре дефинирани; целта е да се изгради непарадоксална логика (например парадокс на Ръсел);

Аксиоми за множествата:
А.1. (аксиома за обема) нека A и B са множества;
ако за всеки обект x имаме: x  A  x  B, то A = B;
неформално аксиомата за обема гласи, че едно множество еднозначно се определя от принадлежността на неговите елементи;

Следствие: две множества са равни, когато са съставени от едни и същи елементи, без значение редът на елементите или дали те се повтарят; например { a, a, b } = { a, b }, { a, b} = { b, a} ;

Мета-теорема: Дадени са множества A и B; твърди се, че A = B;
Доказателство: за всеки елемент a  A показваме, че a  B;
за всеки елемент b  B показваме, че b  A;
от аксиомата за обема  A = B;

А.2. (аксиома за отделянето)
нека М е множество;
въвеждаме понятието предикат P (x) ( x  M ) – параметризиран въпрос с два възможни отговора (true – истина и false – лъжа), при това отговорът зависи от параметъра x;
аксиомата твърди, че ако M = { x | P (x) = true, x  M } , то M е множество; M се нарича подмножество на М (или още M
съдържа M); бележим M  M ( M  M); ако M  M пишем
M  M ( M  M);

означаваме с  множеството, което не съдържа елементи, т.е. за всеки обект x, x  ;

Теорема: За всяко множество M имаме: M  M и   M (наричат се тривиални подмножества на множеството М);
Доказателство: нека t (x) е предикатът, който е тъждествено истина (true); тогава M = { x | t (x) = true, x  M}  M е подмножество на M;
нека f (x) е предикатът, който е тъждествено лъжа (false); тогава
 = { x | f (x) = true, x  M }   е подмножество на M;

нека M е множество; нека P (X) е предикат, верността на който е проверима за всяко X  M;
казваме, че множеството M1 е минимално по включване със свойството P, ако P (M1) = true и за всяко M2  M1 имаме P (M2) = false;
казваме, че множеството M1 е максимално по включване със свойството P, ако P (M1) = true и за всяко M2, M1  M2  M имаме
P (M2) = false;

Операции с множества
A, B – множества;
- обединение на A и B означаваме A  B = { x | x  A или x  B }
- сечение на A и B означаваме A  B = { x | x  A и x  B }
- разлика на A и B означаваме A B = { x | x  A и x  B }
- симетрична разлика на A и B означаваме
A  B = { x | (x  A и x  B) или (x  A и x  B) }
в повечето разсъждения ще считаме, че всички множества, които се разглеждат са подмножества на множеството U, което ще наричаме универсално множество (универсум);



Сподели линка с приятел:





Яндекс.Метрика
Лекции по дискретна математика 9 out of 10 based on 2 ratings. 2 user reviews.