1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 2
Текст из файла (страница 2)
. . , xn, è ïèøóò R(x1, . . . , xn), èíà÷å ãîâîðÿò,÷òî ïðåäèêàò R ëîæåí íà ýëåìåíòàõ x1 , . . . , xn , è ïèøóò ¬R(x1 , . . . , xn ).Ëþáîå ïîäìíîæåñòâî R ⊆ An íàçûâàåòñÿ n-ìåñòíûì îòíîøåíèåì (ïðåäèêàòîì)Îïðåäåëåíèå.íà ìíîæåñòâå A.Îïðåäåëåíèå.ÊîìïîçèöèåéÎïðåäåëåíèå.Îáðàòíûì îòíîøåíèåì ê îòíîøåíèþ R ⊆ A × B íàçûâàåòñÿ îòíî-îòíîøåíèé R1 ⊆ A × B è R2 ⊆ B × C íàçûâàåòñÿîòíîøåíèå R1 ◦ R2 = {ha, ci | ∃b(ha, bi ∈ R1 è hb, ci ∈ R2 )}.øåíèå R−1 = {hb, ai | ha, bi ∈ R}.ôóíêöèåé (îòîáðàæåíèåì)Îòíîøåíèå f ⊆ A × B íàçûâàåòñÿ, åñëèäëÿ ëþáîãî a ∈ A ñóùåñòâóåò íå áîëåå îäíîãî b ∈ B òàêîãî, ÷òî ha, bi ∈ f .Äëÿ äàííîãî a ∈ A, åñëè ñóùåñòâóåò b ∈ B ñî ñâîéñòâîì ha, bi ∈ f , òî ãîâîðÿò, ÷òîf (a)b, è ïèøóò f (a) ↓, â ïðîòèâíîì ñëó÷àå ãîâîðÿò, ÷òîf (a), è ïèøóò f (a) ↑.f íàçûâàåòñÿ ìíîæåñòâî dom(f ) = {a ∈ A | f (a) ↓}.f íàçûâàåòñÿ ìíîæåñòâî range(f ) = {f (a) | a ∈ A, f (a) ↓}.Îïðåäåëåíèå.çíà÷åíèåîïðåäåëåíî è ðàâíîçíà÷åíèåíå îïðåäåëåíîÎáëàñòüþ îïðåäåëåíèÿÎáëàñòüþ çíà÷åíèéÇàïèñü f : A → B îçíà÷àåò, ÷òî äëÿ íåêîòîðûõ ìíîæåñòâ X, Y îòíîøåíèå f ⊆ X × Y ÿâëÿåòñÿ ôóíêöèåé òàêîé, ÷òî dom(f ) = A è range(f ) ⊆ B .
Ïðèýòîì ãîâîðÿò, ÷òî f ÿâëÿåòñÿA B.Îïðåäåëåíèå.ôóíêöèåé èç âèíúåêòèâíîéÃîâîðÿò, ÷òî ôóíêöèÿ f : A → B ÿâëÿåòñÿ, è ïèøóòf : A −−→ B , åñëè äëÿ ëþáîãî b ∈ B ñóùåñòâóåò íå áîëåå îäíîãî a ∈ A òàêîãî, ÷òîf (a) = b.Îïðåäåëåíèå.1−17 2. Àëôàâèòû è ôîðìàëüíûå ÿçûêèÃîâîðÿò, ÷òî ôóíêöèÿ f : A → B ÿâëÿåòñÿf : A −→ B , åñëè range(f ) = B .Îïðåäåëåíèå.íàñþðúåêòèâíîé, è ïèøóòáèåêòèâíîé, è ïèøóòÃîâîðÿò, ÷òî ôóíêöèÿ f : A → B ÿâëÿåòñÿf : A −−→ B , åñëè f îäíîâðåìåííî èíúåêòèâíà è ñþðúåêòèâíà.Îïðåäåëåíèå.1−1íàêîìïîçèöèÿÅñëè f ⊆ A×B , g ⊆ B×C ôóíêöèè, òî èõf ◦g ⊆ A×Cîïðåäåëÿåòñÿ êàê êîìïîçèöèÿ îòíîøåíèé. Ëåãêî âèäåòü, ÷òî f ◦ g òîæå ÿâëÿåòñÿôóíêöèåé.Îïðåäåëåíèå.Îïðåäåëåíèå.1−1Åñëè f : A −−→ B áèåêòèâíàÿ ôóíêöèÿ, òîíàf îïðåäåëÿåòñÿ êàê îáðàòíîå îòíîøåíèå.
Ëåãêî âèäåòü, ÷òî f1−1âèäà f −1 : B −−→ A.−1−1íàÎïðåäåëåíèå.îáðàòíàÿ ôóíêöèÿÿâëÿåòñÿ áèåêöèåé-ìåñòíîé ÷à-Ôóíêöèÿ âèäà f : X → A, ãäå X ⊆ An íàçûâàåòñÿ nA.ñòè÷íîé ôóíêöèåé íàÇàìåòèì, ÷òî ñóùåñòâóþò òîëüêî äâà âèäà 0-ìåñòíûõ ÷àñòè÷íûõ ôóíêöèé ýòî ëèáî íèãäå íå îïðåäåëåííàÿ ôóíêöèÿ f = ∅, ëèáî ôóíêöèÿ âèäà f ={h∅, ai} äëÿ íåêîòîðîãî a ∈ A. Âî âòîðîì ñëó÷àå ìû áóäåì íàçûâàòü ôóíêöèþ êîíñòàíòîé è îòîæäåñòâëÿòü å¼ ñ ýëåìåíòîì a, ò. å. f = a.Çàìå÷àíèå. 2.Àëôàâèòû è ôîðìàëüíûå ÿçûêè áîëüøèíñòâå ñëó÷àåâ äàííûå, ñ êîòîðûìè ðàáîòàþò àëãîðèòìû, ïðåäñòàâëÿþòñÿ ââèäå ñëîâ íåêîòîðîãî ÿçûêà.
Àëãîðèòìû ïîäîáíîãî âèäà ìîæíî íàçâàòü.Íàïðèìåð, âñå àëãîðèòìû èç ñëåäóþùåé ãëàâû áåçóñëîâíî ÿâëÿþòñÿ ñëîâàðíûìè.Áîëåå òîãî, îïèñàíèå ñàìèõ àëãîðèòìîâ, êàê ïðàâèëî, îñóùåñòâëÿåòñÿ ñ ïîìîùüþñïåöèàëüíîãî òåêñòà, êîòîðûé îáû÷íî íàçûâàþò.Ïîíÿòèÿ ñëîâà, ÿçûêà è òåêñòà èìåþò î÷åíü øèðîêèé ñïåêòð çíà÷åíèé, âûõîäÿùèé çà ðàìêè ìàòåìàòè÷åñêîé íàóêè. Ìû áóäåì ðàáîòàòü òîëüêî ñ, ò. å. ñ ÿçûêàìè, êîòîðûå ïîääàþòñÿ ôîðìàëüíîìó îïèñàíèþ â ðàìêàõ òåîðèè ìíîæåñòâ è êîòîðûå ìîæíî èçó÷àòü, èñïîëüçóÿ ñòðîãèå ìàòåìàòè÷åñêèå ìåòîäû.ñëîâàðíûìèïðîãðàììîéôîðìàëüíûìèÿçûêàìèÀëôàâèòîìáóäåì íàçûâàòü ëþáîå íåïóñòîå êîíå÷íîå ìíîæåñòâîA = {a0 , . . .
, an }. Ýëåìåíòû àëôàâèòà ïðèíÿòî íàçûâàòü, èëè.Îïðåäåëåíèå.áóêâàìèñèìâîëàìèÑëîâîì äëèíû n â àëôàâèòå A ìû áóäåì íàçûâàòü ëþáîé êîðòåæha1 , a2 , . . . , an i äëèíû n, ãäå a1 , . . . , an áóêâû àëôàâèòà A. Ñëîâà îáû÷íî çàïèñûâàþò â âèäå a1 a2 . . . an . Ïóñòîå ñëîâî ∅ íå ñîäåðæèò íè îäíîé áóêâû, èìååò äëèíó 0Îïðåäåëåíèå.è îáîçíà÷àåòñÿ ÷åðåç Λ. äàëüíåéøåì çàïèñü ñëîâà â âèäå a1 a2 .
. . an ïîäðàçóìåâàåò, â ÷àñòíîñòè, ÷òî ïðè n = 0 ýòî ñëîâî ïóñòî. Ýòî æå ñîãëàøåíèå ðàñïðîñòðàíÿåòñÿ íà êîíå÷íûåêîðòåæè è êîíå÷íûå ìíîæåñòâà, ò. å. ha1 , . . . , an i = {a1 , . . . , an } = ∅ ïðè n = 0.Çàìå÷àíèå.Ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå A, âêëþ÷àÿ ïóñòîå ñëîâî, îáîçíà÷àåòñÿ ÷åðåç A . Ìíîæåñòâî âñåõ íåïóñòûõ ñëîâ â àëôàâèòå A îáîçíà÷àåòñÿ ÷åðåçA+ , ò.
å. A+ = A∗ \ {Λ}.Îïðåäåëåíèå.∗8Ãëàâà I. Ïðåäâàðèòåëüíûå ñâåäåíèÿÎïðåäåëåíèå.Äëèíà ñëîâà w ∈ A∗ îáîçíà÷àåòñÿ ÷åðåç |w|.ïîäñëîâîìâõîæäåíèåìÑëîâî u íàçûâàåòñÿñëîâà v , åñëè ñóùåñòâóþò ñëîâà w1è w2 òàêèå, ÷òî v = w1 uw2 , ïðè ýòîìïîäñëîâà u â ñëîâî v íàçîâåìóïîðÿäî÷åííóþ òðîéêó hw1 , u, w2 i. Îòìåòèì, ÷òî îäíî è òî æå ñëîâî u ìîæåò èìåòüíåñêîëüêî ðàçëè÷íûõ âõîæäåíèé â ñëîâî v .Îïðåäåëåíèå.ïðåôèêñîì ñëîâà v, åñëè v = uw äëÿ íåêîòîðîãîñóôôèêñîì ñëîâà v, åñëè v = wu äëÿ íåêîòîðîãî w.Ñëîâî u íàçûâàåòñÿñëîâà w. Ñëîâî u íàçûâàåòñÿÎïðåäåëåíèå.Ââåäåì ñëåäóþùèå îïåðàöèè íàä ñëîâàìè â àëôàâèòå A:(à)u è v íàçûâàåòñÿ ñëîâî uv , ïîëó÷åííîå ïðèïèñûâàíèåì êñëîâó u ñëîâà v ñïðàâà.(á)u îïðåäåëÿåòñÿ èíäóêöèåé ïî n ∈ ω ñëåäóþùèì îáðàçîì: u0 = Λ,n+1nu= u u.(â)u = a1 a2 .
. . an , ãäå a1 , a2 , . . . , an áóêâû àëôàâèòà A, íàçûâàRåòñÿ ñëîâî u = an . . . a2 a1 .Îïðåäåëåíèå.Êîíêàòåíàöèåé ñëîâÑòåïåíü ñëîâàÎáðàùåíèåì ñëîâàÏðèìåð. Êîíêàòåíàöèåé ñëîâ aaba è abb ÿâëÿåòñÿ ñëîâî aabaabb. Åñëè òåïåðü âçÿòüêîíêàòåíàöèþ òåõ æå ñëîâ, íî â äðóãîì ïîðÿäêå, òî ïîëó÷èòñÿ ñëîâî abbaaba. Ñëîâî aab ÿâëÿåòñÿ ïîäñëîâîì ñëîâà aabaabb, ïðè÷åì îíî èìååò äâà âõîæäåíèÿ: ïåðâîåâõîæäåíèå íà÷èíàåòñÿ ñî 1-ãî ñèìâîëà ñëîâà, à âòîðîå ñ 4-ãî ñèìâîëà. Îáðàùåíèåìñëîâà abb áóäåò ñëîâî bba.
Ñòåïåíÿìè ñëîâà aaba ÿâëÿþòñÿ ñëîâà Λ, aaba, aabaaaba,aabaaabaaaba è ò. ä. Ïðè ýòîì êàæäîå ñëîâî èç äàííîé ïîñëåäîâàòåëüíîñòè ÿâëÿåòñÿïðåôèêñîì âñåõ ïîñëåäóþùèõ ñëîâ.Îïðåäåëåíèå.àëôàâèòîì A.Ëþáîå ïîäìíîæåñòâî L ⊆ A∗ íàçûâàåòñÿôîðìàëüíûì ÿçûêîì íàäÂâåäåì ñëåäóþùèå îïåðàöèè íàä ÿçûêàìè â àëôàâèòå A:(à)L1 ∪ L2 èL1 ∩ L2 ÿçûêîâ L1 è L2 îïðåäåëÿþòñÿ êàêîáû÷íûå òåîðåòèêî-ìíîæåñòâåííûå îáúåäèíåíèå è ïåðåñå÷åíèå.(á)ÿçûêà L íàçûâàåòñÿ ÿçûê L = A∗ \ L.(â)L1 è L2 íàçûâàåòñÿ ÿçûê L1 L2 = {uv | u ∈ L1 , v ∈ L2 }.(ã)L îïðåäåëÿåòñÿ èíäóêöèåé ïî n ∈ ω ñëåäóþùèì îáðàçîì: L0 ={Λ}, Ln+1 = Ln L.S n(ä)îò ÿçûêà L íàçûâàåòñÿ ÿçûê L∗ =L .
Äðóãèìè ñëîâàìè,Îïðåäåëåíèå.Îáúåäèíåíèåïåðåñå÷åíèåÄîïîëíåíèåìÊîíêàòåíàöèåé ÿçûêîâÑòåïåíü ÿçûêàÇâ¼çäî÷êîé Êëèíèn∈ωL∗ = {w | w = w1 w2 . . . wn äëÿ íåêîòîðûõ n ∈ ω è w1 , w2 , . . . , wn ∈ L}. ÷àñòíîñòè, âñåãäà èìååò ìåñòî Λ ∈ L∗ (ïðè n = 0).Çàìå÷àíèå. Çàìåòèì, ÷òî îïðåäåëåíèå çâ¼çäî÷êè Êëèíè ñîãëàñóåòñÿ ñ ââåä¼íûìâûøå îáîçíà÷åíèåì A∗ . Çâ¼çäî÷êà Êëèíè îò àëôàâèòà ýòî è åñòü ìíîæåñòâî âñåõñëîâ â äàííîì àëôàâèòå.Ñ ïîìîùüþ ââåä¼ííûõ îïåðàöèé ìîæíî îïðåäåëÿòü ôîðìàëüíî òå ÿçûêè,êîòîðûå èçíà÷àëüíî èìåþò íåôîðìàëüíîå îïèñàíèå.Íàïðèìåð, ÿçûê âñåõ ñëîâ â àëôàâèòå A = {a, b}, èìåþùèõ õîòÿ áû îäíî âõîæäåíèå áóêâû a, ñîâïàäàåò ñ ÿçûêîì {b}∗ {a}{a, b}∗ .
Äåéñòâèòåëüíî, â ëþáîì òàêîì ñëîâåìîæíî âûäåëèòü ïåðâîå âõîæäåíèå áóêâû a, ò. å. ïðåäñòàâèòü â âèäå bn aw, ãäå n ∈ ω ,Ïðèìåð. 3. Ýëåìåíòû êîìáèíàòîðèêè9w íåêîòîðîå ñëîâî â àëôàâèòå A. Ñ äðóãîé ñòîðîíû, ëþáîå ñëîâî âèäà bn aw ëåæèòâ ÿçûêå {b}∗ {a}{a, b}∗ .Äðóãîé ïðèìåð ýòî ÿçûê âñåõ ñëîâ ÷¼òíîé äëèíû â òîì æå àëôàâèòå, êîòîðûéìîæíî ïðåäñòàâèòü êàê {aa, ab, ba, bb}∗ . Äåéñòâèòåëüíî, ñëîâî w èìååò ÷¼òíóþ äëèíóòîãäà è òîëüêî òîãäà, êîãäà åãî ìîæíî ïðåäñòàâèòü â âèäå w = w1 .
. . wn äëÿ íåêîòîðîãî n ∈ ω è íåêîòîðûõ ñëîâ wi , êàæäîå èç êîòîðûõ èìååò äëèíó 2, ò. å. êàæäîåwi ∈ {aa, ab, ba, bb}.Îòñþäà ñëåäóåò, ÷òî ÿçûê âñåõ ñëîâ íå÷¼òíîé äëèíû ìîæíî ïîëó÷èòü êàê äîïîëíåíèå ïðåäûäóùåãî ÿçûêà, ò. å. {a, b}∗ \ {aa, ab, ba, bb}∗ , à ÿçûê âñåõ ñëîâ ÷¼òíîé äëèíû, ñîäåðæàùèõ áóêâó a, ìîæíî ïîëó÷èòü, èñïîëüçóÿ îïåðàöèþ ïåðåñå÷åíèÿ({b}∗ {a}{a, b}∗ ) ∩ {aa, ab, ba, bb}∗ .ßçûê âñåõ ñëîâ ÷¼òíîé äëèíû, ñîäåðæàùèõ áóêâó a, ìîæíî ïîëó÷èòü è äðóãèìñïîñîáîì, à èìåííî êàê ÿçûê {bb}∗ {aa, ab, ba}{aa, ab, ba, bb}∗ . 3.Ýëåìåíòû êîìáèíàòîðèêè êîìáèíàòîðíûõ çàäà÷àõ êàê ïðàâèëî íåîáõîäèìî ïîäñ÷èòàòü êîëè÷åñòâî âîçìîæíûõ êîìáèíàöèé îáúåêòîâ, óäîâëåòâîðÿþùèõ îïðåäåë¼ííûì óñëîâèÿì.
Äëÿ ôîðìóëèðîâêè è ðåøåíèÿ òàêèõ çàäà÷ èñïîëüçóþòñÿ ðàçëè÷íûå ìàòåìàòè÷åñêèå ìîäåëèêîìáèíàòîðíûõ êîíôèãóðàöèé.Äëÿ ïåðå÷èñëåíèÿ ìíîæåñòâà ðàçëè÷íûõ êîíôèãóðàöèé ÷àñòî èñïîëüçóþòñÿè, èìåþùèå ñëåäóþùèé åñòåñòâåííûé ñìûñë. Äîïóñòèì, ñóùåñòâóþò íåêîòîðûå âîçìîæíîñòè ïîñòðîåíèÿ êîìáèíàòîðíûõ êîíôèãóðàöèé. Åñëè ýòè âîçìîæíîñòè âçàèìíî èñêëþ÷àþò äðóã äðóãà, òî èõ êîëè÷åñòâà ñëåäóåò ñêëàäûâàòü. Åñëè æå ýòè âîçìîæíîñòè íåçàâèñèìû, òî èõ êîëè÷åñòâà ñëåäóåòïåðåìíîæàòü. Ñôîðìóëèðóåì äàííûå ïðèíöèïû ôîðìàëüíî.âèëî ñóììû ïðàâèëî ïðîèçâåäåíèÿïðà-Åñëè A êîíå÷íîå ìíîæåñòâî, òî ÷åðåç kAk áóäåì îáîçíà÷àòü êîëè÷åñòâî ýëåìåíòîâ â í¼ì.Îïðåäåëåíèå.åñëè ìíîæåñòâî êîíôèãóðàöèé A èìååò âèä A = A1 ∪ A2, ãäåA1 ∩ A2 = ∅, ò.å. êîíôèãóðàöèè èç A1 è A2 èñêëþ÷àþò äðóã äðóãà, òî kAk =kA1 k + kA2 k.åñëè ìíîæåñòâî êîíôèãóðàöèé A èìååò âèä A = A1 ×A2,ò.å.
êîíôèãóðàöèè èç A1 è A2 íå çàâèñÿò äðóã îò äðóãà, òî kAk = kA1k · kA2k.Ïðàâèëî ñóììû:Ïðàâèëî ïðîèçâåäåíèÿ:Ðàññìîòðèì íåêîòîðûå áàçèñíûå ðåçóëüòàòû êîìáèíàòîðèêè, èñïîëüçóÿ â êà÷åñòâå êîìáèíàòîðíûõ êîíôèãóðàöèé ñåìåéñòâà êîíå÷íûõ ôóíêöèé ñ îïðåäåëåííûìèñâîéñòâàìè.Ïóñòü X , Y êîíå÷íûå ìíîæåñòâà, kXk = k, kY k = n. ×èñëîâñåõ ôóíêöèé âèäà f : X → Y ðàâíî nk .Äîêàçàòåëüñòâî.
Ìîæíî ñ÷èòàòü, ÷òî X = {1, . . . , k}, Y = {1, . . . , n}. Çàäàíèå ïðî-Ïðåäëîæåíèå 3.èçâîëüíîé ôóíêöèè f : X → Y ðàâíîñèëüíî âûáîðó çíà÷åíèé f (1), . . . , f (k) â ìíîæåñòâå {1, . . . , n}. Êàæäîå èç ýòèõ çíà÷åíèé âûáèðàåòñÿ íåçàâèñèìî îò äðóãèõ n ñïîñîáàìè. Îòñþäà, èñïîëüçóÿ ïðàâèëî ïðîèçâåäåíèÿ, ïîëó÷àåì, ÷òî êîëè÷åñòâî òàêèõôóíêöèé ðàâíî nk .10Ãëàâà I. Ïðåäâàðèòåëüíûå ñâåäåíèÿÊîìáèíàòîðíàÿ êîíôèãóðàöèÿ èç ïðåäëîæåíèÿ 3 ðàâíîñèëüíà çàäà÷åïîäñ÷åòà ÷èñëà ñïîñîáîâ ðàçìåùåíèÿ k ïðåäìåòîâ ïî n ÿùèêàì (áåç îãðàíè÷åíèé).Çàìå÷àíèå.×èñëî âñåõ ïîäìíîæåñòâ n-ýëåìåíòíîãî ìíîæåñòâà ðàâíî 2n.Äîêàçàòåëüñòâî. Êàæäîå ïîäìíîæåñòâî A ìíîæåñòâà {1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
