"transitiivuse" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

või [a] ühisosa [b] on tühihulk. Tõestus: Kuna R on sümmeetriline ja transitiivne, näitame, et kui aRb ja suvaline element [a]-st on z, siis sümmeetria tõttu bRa ja aRz ­ transitiivsuse järgi bRz ehk siis z kuulub [b]. Siit nähtub, et [b] on alamhulgaks [a]-le. Analoogselt tõestame, et [a] on alamhulgaks [b]-le. Kui not(aRb), eeldame vastuväiteliselt, et eksisteerib y, mis kuulub korraga nii [a] kui [b]. ­ ehk aRy ja bRy. Sümmeetria tõttu yRb, millest transitiivuse alusel aRb, mis on vasutolus esialgse väitega. Voila! Relatsiooni aste: R on seos hulgal A. R aste Rk on (aR1b = aRb; aR2b, kui aRcRb) aRkb (k>1) on selline relatsioonide järjestus, et (kui c kuulub A) aRc = cR k-1b. Suhete ahel. Tee pikkus elementide vahel graafis. Relatsiooni transitiivne sulund: R on seos hulgal A. R transitiivne sulund on seos R + hulgal A nii, et aR+b kehtib parajasti siis, kui eksisteerib i >= 1 nii, et aRib.