1610906281-8f040f4ba05ddb69404458d6cdcbceff (824381), страница 2
Текст из файла (страница 2)
anÄåêàðòîâî ïðîèçâåäåíèå ìíîæåñòâ. Ïóñòüêàðòîâûì ïðîèçâåäåíèåì ìíîæåñòâAèBAB ìíîæåñòâà. Äå-íàçûâàåòñÿ ìíîæåñòâîA × B = {(a, b) | a ∈ A5= bn .èb ∈ B}.Ïðèìåð. ÏóñòüA = {0, 1}, B = {1, 2}.ÒîãäàA × B = {(0, 1), (0, 2), (1, 1), (1, 2)}.Ïîíÿòèå äåêàðòîâà ïðîèçâåäåíèÿ ìîæåò áûòü îáîáùåíî íà ëþáîå êîíå÷íîå ÷èñëînìíîæåñòâ,n > 2,ñëåäóþùèì îáðàçîì:A1 × A2 × .
. . × An+1 = (A1 × A2 × . . . × An ) × An+1 .Ìîæíî óáåäèòüñÿ ïî èíäóêöèè, ÷òîA1 × A2 × . . . × An = {(a1 , . . . , an ) | a1 ∈ A1Óïîòðåáëÿåòñÿ òàêæå îáîçíà÷åíèåäëÿn > 1.Ïðè ýòîì ñ÷èòàåòñÿ, ÷òîAnè...èan ∈ An }.äëÿ ìíîæåñòâà. . × A},|A × .{zn ðàçA1 = A.Îòíîøåíèÿ íà ìíîæåñòâàõ. Ëþáîå ïîäìíîæåñòâîR ⊆ A1 × A2 × . . . × Aníàçîâåì îòíîøåíèåì íà ìíîæåñòâàõA1 × A2 × . . . × An .(x1 , .
. . , xn ) ∈ R, òî ìû áóäåì ãîâîðèòü, ÷òî ýëåìåíòû x1 , . . . , xnR è â ðÿäå ñëó÷àåâ çàïèñûâàòü ýòîò ôàêò òàê:R(x1 , . . . , xn ).nÎòíîøåíèå R ⊆ A íàçûâàåòñÿ nàðíûì îòíîøåíèåì íà ìíîæåñòâå A. Ïðè n = 1 îíî íàçûâàåòñÿ óíàðíûì , ïðè n = 2 áèíàðíûì ,ïðè n = 3 òåðíàðíûì .Ïóñòü R0 ⊆ A × B è R1 ⊆ B × C . Òîãäà êîìïîçèöèåé îòíîøåíèé R0è R1 íàçûâàåòñÿ îòíîøåíèåÅñëèíàõîäÿòñÿ â îòíîøåíèèR0 ◦ R1 = {(x, z) | äëÿíåêîòîðîãîy , (x, y) ∈ R0è(y, z) ∈ R1 }.Ó íåêîòîðûõ íàèáîëåå ÷àñòî èñïîëüçóåìûõ ñâîéñòâ áèíàðíûõ îòíîøåíèé åñòü ñïåöèàëüíûå íàçâàíèÿ.
Ïðèâåäåì íåêîòîðûå èç íèõ. ÏóñòüR ⊆ A2 .Ðåôëåêñèâíîñòü. ÎòíîøåíèåâûïîëíåíîRðåôëåêñèâíî, åñëè äëÿ ëþáîãî(a, a) ∈ R.Ñèììåòðè÷íîñòü. ÎòíîøåíèåAèça∈A(a, b) ∈ RñëåäóåòR ñèììåòðè÷íî, åñëè äëÿ ëþáûõ a, b ∈(b, a) ∈ R.6Òðàíçèòèâíîñòü. ÎòíîøåíèåAèç(a, b), (b, c) ∈ RR òðàíçèòèâíî, åñëè äëÿ ëþáûõ a, b, c ∈(a, c) ∈ R.ñëåäóåòÀíòèñèììåòðè÷íîñòü. Îòíîøåíèå R àíòèñèììåòðè÷íî, åñëè äëÿ ëþáûõa, b ∈ Aèç(a, b), (b, a) ∈ Rñëåäóåòa = b.Áóäåì ãîâîðèòü, ÷òî áèíàðíîå îòíîøåíèåR⊆Aÿâëÿåòñÿ îòíîøå-íèåì ýêâèâàëåíòíîñòè åñëè îíî ðåôëåêñèâíî, ñèììåòðè÷íî è òðàíçèòèâíî.ÏóñòüR îòíîøåíèå ýêâèâàëåíòíîñòè íà ìíîæåñòâåa ∈ Aýêâèâàëåíòíîñòè ýëåìåíòàíàçûâàåòñÿ ìíîæåñòâîA.
Êëàññîì[a]R = {x ∈A | (x, a) ∈ R}.Âàæíûì ñâîéñòâîì îòíîøåíèé ýêâèâàëåíòíîñòè ÿâëÿåòñÿÒåîðåìà 0.2 (Òåîðåìà î ðàçáèåíèè) Ïóñòüâàëåíòíîñòè íà ìíîæåñòâåíîñòè{[a]R | a ∈ A}A.R îòíîøåíèå ýêâè-Òîãäà ñåìåéñòâî êëàññîâ ýêâèâàëåíò-îáðàçóåò ðàçáèåíèå ìíîæåñòâàA.Èíà÷å ãîâîðÿ, ëþáûå äâà êëàññà ýêâèâàëåíòíîñòè ýëåìåíòîâ ëèáî ñîâïàäàþò ëèáî íå ïåðåñåêàþòñÿ, è îáúåäèíåíèå âñåõ êëàññîâ ýêâèâàëåíòíîñòèåñòü âñå ìíîæåñòâîA. Áèíàðíîå îòíîøåíèåA,R ⊆ A2íàçûâàåòñÿ ÷àñòè÷íûì ïîðÿäêîì íàåñëè îíî ðåôëåêñèâíî, àíòèñèììåòðè÷íî è òðàíçèòèâíî. ×àñòè÷íûéïîðÿäîê íàAa, b ∈ A(a, b) ∈ R, (b, a) ∈íàçûâàåòñÿ ëèíåéíûì ïîðÿäêîì åñëè äëÿ ëþáûõâûïîëíåíî õîòÿ áû îäíî èç ñëåäóþùèõ äâóõ óñëîâèé:R.Ïðèìåðû.R = {(x, y) | x, y ∈ N è x 6 y} ëèíåéíûé ïîðÿäîê, àD = {(x, y) | x, y ∈ N è x äåëèò y} ÷àñòè÷íûé ïîðÿäîê, êîòîðûé íåÿâëÿåòñÿ ëèíåéíûì.ÏóñòüR ⊆ A2 áèíàðíîå îòíîøåíèå íà ìíîæåñòâåA.Îáðàòíûì êíåìó íàçûâàåòñÿ îòíîøåíèåR−1 = {(y, x) | (x, y) ∈ R}.Ïðèìåð.
ÏóñòüR = {(1, 2), (2, 3)}.ÒîãäàÎòîáðàæåíèÿ, ôóíêöèè. Îòíîøåíèåíûì îòîáðàæåíèåì èçáîëåå îäíîãîb∈BAâBòàêîãî, ÷òîR−1 = {(2, 1), (3, 2)}.F ⊆ A×Båñëè äëÿ êàæäîãî(a, b) ∈ F .7íàçûâàåòñÿ ÷àñòè÷-a ∈ AÏðè ýòîì, åñëèñóùåñòâóåò íå(a, b) ∈ F ,òîba è, ïîñêîëüêó b îïðåäåëåíî îäíîçíà÷íî ïîF (a), ò.å., b = F (a).Åñëè ñóùåñòâóåò y òàêîå, ÷òî (x, y) ∈ F , òî ãîâîðÿò, ÷òî çíà÷åíèåF (x) îïðåäåëåíî è çàïèñûâàþò ýòî êàê F (x) ↓. Óòâåðæäåíèå î òîì, ÷òîçíà÷åíèå F (x) íå îïðåäåëåíî çàïèñûâàåòñÿ, êàê F (x) ↑.Îáëàñòüþ îïðåäåëåíèÿ ÷àñòè÷íîãî îòîáðàæåíèÿ F íàçûâàåòñÿ ìíîíàçûâàåòñÿ çíà÷åíèåìa,Fíàîíî îáû÷íî îáîçíà÷àåòñÿæåñòâîdom (F ) = {a | F (a)ïðåäåëåíî}.Åãî îáëàñòüþ çíà÷åíèÿ íàçûâàåòñÿ ìíîæåñòâîrange (F ) = {F (a) | F (a)Åñëèdom (F ) = A,òîFíàçûâàåòñÿ îòîáðàæåíèåì èçòðåáëÿåòñÿ òàêæå òåðìèí ôóíêöèÿ èçfîïðåäåëåíî}.AâAâB.Óïî-B.AnA, òî îáû÷íîãîâîðÿò, ÷òî f nàðíàÿ îïåðàöèÿ íà ìíîæåñòâå A (îáû÷íî ïðè n =1 ãîâîðÿò óíàðíàÿ, ïðè n = 2 áèíàðíàÿ, ïðè n = 3 òåðíàðíàÿÅñëè îòîáðàæåíèå íåêîòîðîãî ìíîæåñòâà âèäàâîïåðàöèÿ).F íàçûâàåòñÿ îòîáðàæåíèåì íà B .F èç A â B íàçûâàåòñÿ ðàçíîçíà÷íûì åñëèäëÿ ëþáîãî b ∈ B ñóùåñòâóåò íå áîëåå îäíîãî a ∈ A òàêîãî, ÷òî b = F (a).Åñëèrange (F ) = B ,òî×àñòè÷íîå îòîáðàæåíèåÓïðàæíåíèå.
Äîêàçàòü, ÷òî ÷àñòè÷íîå îòîáðàæåíèåFèçAâBÿâëÿ-−1 ÿâëÿåòñÿåòñÿ ðàçíîçíà÷íûì òîãäà è òîëüêî òîãäà, êîãäà îòíîøåíèå F÷àñòè÷íûì îòîáðàæåíèåì èçÅñëèFBâA. ðàçíîçíà÷íîå îòîáðàæåíèå èçâçàèìíîîäíîçíà÷íûì îòîáðàæåíèåì èç−1AA íà B ,íà B . Âòî îíî íàçûâàåòñÿýòîì ñëó÷àå ëåãêîF âçàèìíîîäíîçíà÷íîå îòîáðàæåíèå èç B íà A.F : A → B áóäåò îáîçíà÷àòü,÷òî F îòîáðàæåíèå èç A â B ,F : A 99K B áóäåò îáîçíà÷àòü, ÷òî F ÷àñòè÷íîå îòîáðàæåíèåïîêàçàòü, ÷òîÇàïèñüà çàïèñüèçAâB.F : A 99K BÏóñòüèG : B 99K Cêîìïîçèöèåé íàçûâàåòñÿ îòíîøåíèåñëó÷àå îòíîøåíèåF ◦G äâà ÷àñòè÷íûõ îòîáðàæåíèÿ. ÈõF ◦ G.
Ëåãêî ïðîâåðèòü, ÷òî â ýòîìA â C . Çàìåòèì, ÷àñòè÷íîå îòîáðàæåíèå èç÷òî êîìïîçèöèÿ îòîáðàæåíèé âñåãäà ÿâëÿåòñÿ îòîáðàæåíèåì.f , çíà÷åíèÿìè êîòîðîãîx∈Aÿâëÿþòñÿ ìíîæåñòâà Bx , ìû áóäåì èñïîëüçîâàòüSS{Bx | x ∈ A}.x∈A Bx äëÿ ìíîæåñòâàÅñëè èìååòñÿ íåêîòîðîå îòîáðàæåíèåýëåìåíòîâçíà÷åíèå8äëÿîáî-1Àëôàâèòû è ÿçûêè×òî òàêîå ÿçûê âîîáùå âîïðîñ î÷åíü íåïðîñòîé, ýòîìó âîïðîñó ïîñâÿùåíû èññëåäîâàíèÿ â öåëîì ðÿäå íàóê. ßçûêè áûâàþò ðàçíûìè. Ýòîè îáû÷íûå ÿçûêè, ñëóæàùèå äëÿ îáùåíèÿ ëþäåé, áþðîêðàòè÷åñêèå âàðèàíòû åñòåñòâåííûõ ÿçûêîâ, ïðîôåññèîíàëüíûå æàðãîíû, ÿçûêè ïðîãðàììèðîâàíèÿ, ÿçûêè äëÿ ñâÿçè ìåæäó êîìïüþòåðàìè, ÿçûêè æåñòîâ,ÿçûêè èêîíîê íà äèñïëåå êîìïüþòåðà, ÿçûê äîðîæíûõ çíàêîâ, âèäèìîìîæíî â êàêîìòî ñìûñëå ãîâîðèòü î ÿçûêå èñêóññòâà è ò.ï.Çäåñü ìû áóäåì èçó÷àòü ôîðìàëüíûå ÿçûêè.
Ê íàì îòíîñÿòñÿ â ïåðâóþî÷åðåäü ÿçûêè, èñïîëüçóåìûå ïðè ðàáîòå ñ êîìïüþòåðîì (â ÷àñòíîñòèÿçûêè ïðîãðàììèðîâàíèÿ) è ÿçûêè, èñïîëüçóåìûå â ìàòåìàòè÷åñêîé ëîãèêå. Ýòè ÿçûêè ïîääàþòñÿ èçó÷åíèþ ñòðîãèìè ìàòåìàòè÷åñêèìè ìåòîäàìè.Äëÿ òîãî ÷òîáû ãîâîðèòü î ÿçûêå â òî÷íûõ òåðìèíàõ, íåîáõîäèìîïðåæäå âñåãî çàôèêñèðîâàòü àëôàâèò êîíå÷íîå (îáû÷íî íåïóñòîå)A = {a0 , a1 , .
. . , an }. Ïðåäïîëîæèì, ÷òî ìû çàôèêàëôàâèò A. Ïîä ñëîâîì â àëôàâèòå A ìû áóäåììíîæåñòâî ñèìâîëîâñèðîâàëè íåêîòîðûéïîíèìàòü ëþáóþ êîíå÷íóþ öåïî÷êó ñèìâîëîâ èç ýòîãî àëôàâèòà, âêëþ÷àÿ ïóñòîå ñëîâî, íå ñîäåðæàùåå ñèìâîëîâ, è îáîçíà÷àåìîåëÿåòñÿ òàêæå âûðàæåíèå ñëîâî íàä àëôàâèòîì ñëîâà â àëôàâèòå{a, b},A.Λ.Íàïðèìåð,Óïîòðåá-a, abba, Λàíóáûâàþòæåòàêèåñòðàííûåñëîâà, àáðàêàäàáðà, áâãæþðñò{à, á, â,.
. . , ý, þ, ÿ}. Ïóñòü A∗ îáîçíà÷àåò ìíîæåñòâî+âñåõ ñëîâ íàä àëôàâèòîì A, à A îáîçíà÷àåò ìíîæåñòâî âñåõ íåïóñòûõ+ñëîâ íàä àëôàâèòîì A, ò.å., A= A∗ \ {Λ}. Áóäåì îáîçíà÷àòü äëèíóñëîâà α ÷åðåç |α| (ïðè ýòîì êîíå÷íî æå |Λ| = 0).∗Ëþáîå ìíîæåñòâî L ⊆ A áóäåì íàçûâàòü ôîðìàëüíûì ÿçûêîì íàäàëôàâèòîì A.
ñëîâà â àëôàâèòåÎïðåäåëèì íåêîòîðûå îïåðàöèè íàä ñëîâàìè è ÿçûêàìè.Êîíêàòåíàöèÿ ñëîâvw ýòî áèíàðíàÿ îïåðàöèÿ íà ìíîæåñòâå ñëîâ(A∗ )2 â A∗ ), ðåçóëüòàòîì ïðèìåíåíèÿ êîòîðîé êñëîâàì v è w ÿâëÿåòñÿ ñëîâî, ïîëó÷àþùååñÿ ïðèïèñûâàíèåì ê v ñëîâà wñïðàâà, òî åñòü ñëîâî vw . Èíîãäà èñïîëüçóåòñÿ òàêæå îáîçíà÷åíèå v ◦ w .è(òî åñòü îòîáðàæåíèå èçÏðèìåðû. Êîíêàòåíàöèÿ ñëîâ àáðà è êàäàáðà åñòü ñëîâî àáðàêàäàáðà.Îòìåòèì íåêîòîðûå äîñòàòî÷íî î÷åâèäíûå ñâîéñòâà êîíêàòåíàöèè:9•êîíêàòåíàöèÿ ñ ïóñòûì ñëîâîì íå èçìåíÿåò ïåðâîíà÷àëüíîå ñëîâî:Λ ◦ v = v ◦ Λ = v.•êîíêàòåíàöèÿ àññîöèàòèâíà: äëÿ ëþáûõ ñëîâðàâåíñòâîu, v , wâûïîëíåíîu(vw) = (uv)w.Îïåðàöèÿ êîíêàòåíàöèè åñòåñòâåííûì îáðàçîì ðàñøèðÿåòñÿ íà ÿçûêè. Êîíêàòåíàöèÿ ÿçûêîâL0èL1îïðåäåëÿåòñÿ, êàêL0 L1 = {uv | u ∈ L0 , v ∈ L1 }.Ïîíÿòèå ïîäñëîâà.
Ñëîâîβíàçûâàåòñÿ ïîäñëîâîì ñëîâàγ0èγ1â ñëîâîαíàçîâ¼ì òðîéêóα,åñëè ñó-α = γ0 βγ1 . Ïðè ýòîì âõîæäåíèåìhγ0 , β, γ1 i. Íàçîâ¼ì ñàìûì ëåâûìâõîæäåíèåì ïîäñëîâà β â ñëîâî α òàêóþ òðîéêó hγ0 , β, γ1 i ñ íàèìåíüøèìâîçìîæíûì çíà÷åíèåì äëèíû ñëîâà γ0 . Íàïðèìåð ñëîâî áàîáàá èìååò äâàðàçíûõ âõîæäåíèÿ ïîäñëîâà áà: Λ ◦ áà ◦ îáàá è áàî ◦ áà ◦ á. Ïåðâîå èçùåñòâóþò ñëîâàïîäñëîâàβòàêèå, ÷òîíèõ áóäåò ñàìûì ëåâûì âõîæäåíèåì.Ïî àíàëîãèè ñ óìíîæåíèåì ìîæíî îïðåäåëèòü ñòåïåíè ñ íàòóðàëüíûì ïîêàçàòåëåì è äëÿ ñëîâ, à èìåííî:w0 = Λ;wn+1 = wn w,Èëè ìåíåå ôîðìàëüíî:wn = w. .
w}.| .{zn ðàçÎïåðàöèÿ çâåçäî÷êà Êëèíè (èëè ïðîñòî çâåçäî÷êà ). Îíà îïðåäåëÿåòñÿ òàê:L∗ = {w|w = w1 w2 . . . wn ,è äëÿ íåêîòîðûõ ÷àñòíîñòè, äëÿ ëþáîãî ÿçûêàäëÿ íåêîòîðîãîn = 0, 1, 2, . . .w1 , . . . , wn ∈ L}.LâûïîëíåíîΛ ∈ L∗ .Ìû áóäåì èñïîëüçîâàòü òàêæå îïåðàöèè îáúåäèíåíèÿ, ïåðåñå÷åíèÿè äîïîëíåíèÿ ÿçûêîâ. Ïîñêîëüêó â ýòèõ ñëó÷àÿõ ÿçûêè âûñòóïàþò êàêîáûêíîâåííûå ìíîæåñòâà, ñïåöèàëüíî îïðåäåëÿòü ýòè îïåðàöèè íåò ñìûñëà. Ñòîèò òîëüêî îòìåòèòü, ÷òî äîïîëíåíèå ÿçûêàL ⊆ A∗îáû÷íî ïîíè-∗ìàåòñÿ êàê äîïîëíåíèå îòíîñèòåëüíî A , òî åñòü êàê ìíîæåñòâî10A∗ \ L ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
