Sissejuhatus.
Eesmärk.
Diskreetse matemaatika kursuse uued osad, kuigi neid rakendatakse haridusprogrammide ja loengusarjade kujul, ei eksisteeri veel monograafiate kujul, vähemalt vene keeles, kuna tehnikaülikoolide diskreetse matemaatika kursus on keskendunud vanadele rakendusprobleemidele, insenerid pidid lahendama . Eelkõige oli matemaatilises loogikas see minimeerimine loogikaahelad, mis on tänapäeval kaotanud oma aktuaalsuse.
Huvitav on märkida, et loogiliste ahelate sünteesi teooria, mis on ühe põlvkonna teadlaste silme all läbinud peaaegu täieliku "bioloogilise tsükli", on väga õpetlik näide sellest, kuidas tehnikateaduste harud, mis on vähe seotud fundamentaalteadustega. teadus on väga vastuvõtlik vananemisele. 10 aastat tagasi kõik tehnikaajakirjad olid täidetud artiklitega loogikaahelate minimeerimise ja sünteesi kohta. Enamik teadlaste väljatöötatud minimeerimismeetodeid on nüüdseks unustatud ja praktikas ei nõuta neid. Ja need ideed, mida tol ajal peeti puhtalt teoreetiliseks, leidsid praktilise rakenduse moodne tehnoloogia. Näiteks hägusloogika, Petri võrgud ja algoritmiteooria on ajaproovile vastu pidanud ning neid kasutatakse laialdaselt erinevates küberneetika ja programmeerimise valdkondades, nagu süsteemide programmeerimine, arvutuslik keerukus ja tehisintellekt.
Ja algoritmide teooriast sai diskreetse matemaatika keskne osa. Erinevalt enamikust venekeelsetest monograafiatest esitatakse loengutes need küsimused aga praktiliste inseneriprobleemide lahendamise vahendina.
Nagu teate, muutuvad iga kümnendi järel radikaalselt arvutite riistvarakomponendid, operatsioonisüsteemid, juurdepääsutööriistad ja programmid ise. Nende aluseks olevad struktuurid ja algoritmid jäävad aga muutumatuks palju kauem. Neid aluseid hakati rajama tuhandeid aastaid tagasi, kui töötati välja formaalne loogika ja töötati välja esimesed algoritmid.
Matemaatiline loogika ja algoritmide teooria kuuluvad traditsiooniliselt fundamentaalteaduste hulka ning arvatakse, et neil on praktikaga vähe seost ja neid on raske mõista. Tõepoolest, kui J. Boole lõi Boole'i algebra matemaatilise aparaadi, ei leidnud see pikka aega praktilist rakendust, kuid 20. sajandil võimaldas just see matemaatiline aparaat projekteerida kõiki arvutikomponente. Järelikult on esimene neist eelarvamustest arvutitehnoloogia arenguga edukalt ümber lükatud.
Mis puudutab eelarvamusi selle distsipliini mõistmise raskuste kohta, siis see tuleneb suuresti asjaolust, et matemaatikud kirjutasid matemaatikute jaoks raamatuid matemaatilise loogika ja algoritmide teooria kohta.
Nüüd, kui arvutustehnika võimalused on kordades kasvanud ja personaalarvuteid endid on palju rohkem kui neid, kes oskavad neid tõhusalt kasutada, on arusaamine, mida tänapäevase arvutustehnoloogia abil teha saab ja mida mitte. erakordne tähtsus.
Algoritmide üldteooria näitas, et on probleeme, mis on lahendamatud, olenemata arvutusvõimsuse võimsusest, ja selle kiiresti arenev haru - arvutusliku keerukuse teooria - viib järk-järgult arusaamiseni, et on probleeme, mis on lahendatavad. kuid objektiivselt keerukad ja nende keerukus võib osutuda mõneti absoluutses mõttes, s.t. tänapäevastele arvutitele praktiliselt kättesaamatu.
See kursus seadis järgmised eesmärgid:
1. Esitage kõik käsitletavad küsimused võimalikult lihtsalt, kuid mitte lihtsamalt, kui kõrgelt kvalifitseeritud spetsialistile nõutakse.
2. Praktilised probleemid Infosüsteemide projekteerimine ja analüüs on lähtepunktiks ning formaalne aparaat on vahend süstemaatiline lahendus need probleemid. Meie sügav veendumus on, et õpilane ei ole anum, mida tuleb täita, vaid tõrvik, mis tuleb süüdata.
3. Kursuse iga osa sisaldab enesetesti küsimusi. Assimilatsiooniks see kursusõpilane on kohustatud vastama kõigile neile küsimustele.
Selle kursuse omandamise tulemusena peaks üliõpilane asjakohaste teoreetiliste osade selge mõistmise alusel suutma:
Rakendada lihtsaimat tüüpi teabe loogilist teisendust loogiliste funktsioonide suvalises aluses;
Tõendava arutluskäigu esiletõstmine loomulik keel loogiline struktuur, koostada formaalsed tõestusskeemid ja kontrollida nende õigsust.
1.2 Loogilised esitused
Loogilised esitused - uuritava süsteemi, protsessi, nähtuse kirjeldus komplekti kujul keerulised avaldused koosnevad lihtsad (elementaarsed) väited Ja loogilised sidemed
nende vahel. Loogilisi esitusi ja nende komponente iseloomustavad teatud omadused ja nende üle lubatud teisenduste kogum (tehted, järeldusreeglid jne), rakendades formaalses (matemaatikas) väljatöötatuid. loogika õiged meetodid arutluskäik – loogikaseadused.
Õpitakse väidete formaalse esitamise meetodeid (reegleid), olemasolevatest uute väidete konstrueerimist loogiliselt õigete teisenduste abil, aga ka väidete tõesuse või vääruse tuvastamise meetodeid (meetodeid). matemaatiline loogika. Kaasaegne matemaatiline loogika sisaldab kahte peamist osa: väidete loogika ja katab selle predikaadiloogika(joonis 1.1), mille konstrueerimiseks on kaks lähenemist (keelt), mis moodustavad kaks formaalse loogika varianti: loogika algebra Ja loogiline arvutus. Nende formaalse loogika keelte põhimõistete vahel on üks-ühele vastavus. Nende isomorfismi tagab lõpuks aluseks olevate lubatavate teisenduste ühtsus.
Riis. 1.1
Traditsiooniliste loogikaharude peamised objektid on väited.
avaldus - deklaratiivne lause (avaldus, kohtuotsus), o mille kohta on mõttekas öelda, et see tõsi või vale. Kõik teaduslikud teadmised(füüsika, keemia, bioloogia jt seadused ja nähtused, matemaatilised teoreemid jne), igapäevaelu sündmused, majanduses ja juhtimisprotsessides tekkivad olukorrad sõnastatakse väidetena. Imperatiivsed ja küsivad laused ei ole väited.
Näited väidetest: “Kaks korda kaks on neli”, “Me elame 21. sajandil”, “Rubla on Venemaa rahaühik”, “Aljoša on Olegi vend”, “Ühendamis-, ristumis- ja liitmistehted on Boole'i toimingud kogumitel ”, “Inimene on surelik” , “Tingimuste kohtade ümberpaigutamine ei muuda summat”, “Täna on esmaspäev”, “Kui sajab, siis tuleb vihmavari kaasa võtta.”
Et nende lausetega edaspidi väidetena opereerida, peame igaühe puhul teadma, kas see on tõene või väär, s.t. tunne neid tõeväärtus (tõde). Pange tähele, et mõnel juhul sõltub väite tõesus või väärus sellest, millist konkreetset tegelikkust (süsteemi, protsessi, nähtust) me selle abil kirjeldada püüame. Sel juhul öeldakse, et antud väide on antud tõlgenduses (kontekstis) tõene (või väär). Lisaks eeldame, et kontekst on antud ja väitel on teatud tõeväärtus.
1.3 Arenenud matemaatilise loogika ajalugu
Loogika kui teadus kujunes välja 4. sajandil. eKr. Selle lõi Kreeka teadlane Aristoteles.Sõna "loogika" pärineb kreekakeelsest sõnast "logos", mis ühelt poolt tähendab "sõna" või "ekspositsiooni" ja teiselt poolt mõtlemist. IN seletav sõnastik Ožegova S.I. Öeldakse: "Loogika on mõtlemise seaduste ja selle vormide teadus." 17. sajandil Saksa teadlane Leibniz kavatses luua uue teaduse, mis oleks "tõe arvutamise kunst" . Selles loogikas oleks Leibnizi järgi igal väitel vastav sümbol ja arutluskäigul oleks arvutuste vorm. See Leibnizi idee, mis ei vastanud tema kaasaegsete arusaamadele, ei levinud ega arenenud ning jäi geniaalseks oletuseks.
Alles 19. sajandi keskel. Leibnizi ideed kehastas iiri matemaatik George Boole, kes kirjutas 1854. aastal teose “Mõtteseaduste uurimine”, mis pani aluse loogika algebrale, milles kehtivad tavalise algebra seadustega sarnased seadused, kuid tähed seda teevad. ei tähista numbreid, vaid väiteid. Boole'i algebra keeles saab kirjeldada arutluskäiku ja “arvutada” selle tulemusi. Kuid see ei hõlma kõiki arutluskäike, vaid ainult teatud tüüpi. , Seetõttu peetakse Boole'i algebrat propositsiooniarvutuseks.
Boole’i loogikalgebra oli uue teaduse – matemaatilise loogika – embrüo. Seevastu Aristotelese loogikat nimetatakse traditsiooniliseks formaalseks loogikaks. Nimetus “matemaatiline loogika” peegeldab selle teaduse kahte tunnust: esiteks on matemaatiline loogika loogika, mis kasutab matemaatika keelt ja meetodeid; teiseks äratavad matemaatilise loogika ellu matemaatika vajadused.
19. sajandi lõpus. Georg Cantori loodud hulgateooria tundus olevat usaldusväärne alus kogu matemaatikale, sealhulgas matemaatilisele loogikale, vähemalt lausearvutuse (Boole'i algebra) jaoks, sest Selgus, et Cantori algebra (hulgateooria) on isomorfne Boole algebraga.
Matemaatiline loogika ise muutus matemaatika haruks, mis alguses tundus kõrgeim aste abstraktne ja lõpmatult kaugel praktilistest rakendustest. See valdkond ei jäänud aga kauaks "puhaste" matemaatikute pärusmaaks. 20. sajandi alguses. (1910) Vene teadlane Ehrenfest P.S. tõi välja võimaluse kasutada Boole'i algebra aparatuuri telefonisuhtluses kommutatsiooniahelate kirjeldamiseks. Aastatel 1938–1940 ilmusid peaaegu samaaegselt Nõukogude teadlase V. I. Šestakovi, Ameerika teadlase Shannoni ning Jaapani teadlaste Nakashima ja Hakazawa tööd matemaatilise loogika rakendamisest digitaaltehnoloogias. Nõukogude teadlane M. A. Gavrilov avaldas NSV Liidus esimese monograafia, mis oli pühendatud matemaatilise loogika kasutamisele digitaalseadmete projekteerimisel. 1950. aastal. Matemaatilise loogika roll kaasaegse mikroprotsessortehnoloogia arengus on äärmiselt oluline: seda kasutatakse arvutiriistvara projekteerimisel, kõigi programmeerimiskeelte arendamisel ja diskreetsete automaatikaseadmete projekteerimisel.
Teadlased andsid suure panuse matemaatilise loogika arendamisse erinevad riigid: Kaasani ülikooli professor Poretsky P.S., de-Morgan, Pierce, Turing, Kolmogorov A.N., Heidel K. jt.
1.4 Enesekontrolli küsimused.
1. Sõnasta kursuse eesmärgid
nime saanud Volžski ülikool. Tatištševa.
Loengud matemaatilisest loogikast ja algoritmide teooriast.
Koostanud: dotsent S.V. Kaverin.
I peatükk. Loogika algebra.
§1.1. Boole'i funktsiooni definitsioon.
Boole'i funktsioon y=f(x1,x2,…,xn)alates P muutujad x 1 , x 2 ,...,x n on mis tahes funktsioon, milles argumendid ja funktsioon võivad võtta väärtuse kas 0 või 1, s.t. Boole'i funktsioon on reegel, mille järgi suvaline nullide ja ühtede hulk
(x 1 ,x 2 ,...,x n) on määratud väärtusele 0 või 1.
Boole'i funktsioonid nimetatud ka loogika algebra funktsioonid, binaarfunktsioonid ja lülitusfunktsioonid.
Boole'i funktsioon alates n muutujaid saab määrata tõetabeli abil, milles argumentide väärtuste komplektid on järjestatud nende arvude järgi kasvavas järjekorras : Esiteks värbamine käib, mis tähistab 0 kahendlaiendit (see hulk on nummerdatud 0-ga); siis tuleb hulk, mis on 1, siis 2, 3 jne kahendlaiendus. Viimane komplekt koosneb n ühikut ja on arvu 2 kahendlaiend n-1 (seda komplektide paigutuse järjekorda kutsutakse leksikograafiline järjekord). Arvestades, et loendus algab 0-st ja Boole'i funktsiooni väärtus võib olla kas 0 või n
1, järeldame, et on ainult 22 erinevat Boole'i funktsiooni n muutujad. Seega on kahe muutuja Boole'i funktsiooni näiteks 16, kolmest 256 jne.
Näide 1.1.1.(hääletus) . Vaatleme seadet, mis salvestab teatud resolutsiooni vastuvõtmise "kolmeliikmelise komitee" poolt. Iga komisjoni liige vajutab otsuse kinnitamisel oma nuppu. Kui enamus liikmetest hääletab poolt, on otsus vastu võetud. See salvestatakse salvestusseadmega. Seega rakendab seade funktsiooni f(x,y,z ) , mille tõetabelil on vorm
| x | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| y | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| z | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| f(x,y,z) | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Boole'i funktsioon määratakse unikaalselt ka siis, kui loetletakse kõik korteid, mille väärtus on 0, või loetletakse kõik korteid, millel on väärtus 1. Näites saadud funktsioon f saab määrata ka järgmise võrdussüsteemiga: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.
Boole'i funktsiooni väärtuste vektor y=f(x 1 ,x 2 ,…,x n) on järjestatud kogum funktsiooni f kõigist väärtustest, milles väärtused on järjestatud leksikograafilises järjekorras. Näiteks määrake kolme muutuja f funktsioon väärtuste vektoriga (0000 0010) ja peate leidma hulga, millel f saab väärtuse 1. 1 on 7. kohal ja numeratsioon on sissepoole leksikograafiline järjekord algab 0-st, siis peame leidma 6 kahendlaiendi. Seega võtab funktsioon f hulgal (110) väärtuse 1.
§1.2. Elementaarsed Boole'i funktsioonid.
Boole'i funktsioonide hulgast paistavad silma nn elementaarsed Boole'i funktsioonid, mille abil saab kirjeldada mis tahes arvu muutujatega mis tahes Boole'i funktsiooni.
1. Kutsutakse Boole'i funktsiooni f(x 1 ,x 2 ,…,x n), mis võtab kõigi nullide ja ühtede hulgast väärtuse 1 konstant 1 või identset ühikut. Määramine : 1 .
2. Kutsutakse Boole'i funktsiooni f(x 1 ,x 2 ,…,x n), mille väärtus on 0 kõikidel nullide ja ühtede hulgast konstant 0, või identne null. Määramine : 0 .
3. Eitamine on ühe muutuja Boole'i funktsioon, mis on määratletud järgmise tõesuse tabeliga
Muud nimed : loogiline korrutis (korrutis); loogiline "ja".
Nimetused : x&y, xÿy, x⁄y, min(x,y).
5. Disjunktsioon
Muu nimi : loogiline tagajärg. Nimetused : xØy, xfly, xy.
7. Samaväärsus on kahe muutuja Boole'i funktsioon, mis on määratletud järgmise tõesuse tabeliga
Muu nimi : anti-ekvivalentsus. Nimetused : x∆y, x+y.
9. Schaefferi insult on Kahe muutuja Boole'i funktsioon, mis on määratletud järgmise tõesuse tabeliga
Muu nimi : disjunktsiooni eitus, loogiline “mitte-või”, Webb-funktsioon.
Määramine : x∞y ; funktsiooni Webb jaoks - x±y.
Kommenteeri. Tähistusega seotud sümbolid Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ elementaarsed funktsioonid nimetame neid ühendusteks või operatsioonideks.
§1.3. Boole'i funktsioonide määramine elementaarfunktsioonide abil.
Kui asendate mõned Boole'i funktsioonid muutujate asemel loogiliste funktsioonidega, on tulemuseks uus Boole'i funktsioon nimega superpositsioon asendusfunktsioonid (kompleksfunktsioon). Superpositsiooni abil saate saada keerukamaid funktsioone, mis võivad sõltuda mis tahes arvust muutujatest. Boole'i funktsioonide kirjutamist nimetame elementaarseteks Boole'i funktsioonideks valem selle funktsiooni rakendamine.
Näide 1.3.1. Olgu antud elementaarne Boole'i funktsioon x¤y. Asendame funktsiooni x asemel funktsiooni x 1 ∞x 2. Saame kolme muutuja funktsiooni (x 1 ∞x 2)¤y. Kui muutuja y asemel asendada näiteks x 3 ∆x 4, siis saame uue nelja muutuja funktsiooni: (x 1 ∞x 2)¤(x 3 ∆x 4). Ilmselgelt saame sel viisil Boole'i funktsioonid, mida väljendatakse elementaarsete Boole'i funktsioonide kaudu.
Tulevikku vaadates märgime seda ükskõik milline Boole'i funktsiooni saab esitada elementaarfunktsioonide superpositsioonina.
Keeruliste funktsioonide kompaktsemaks kirjutamiseks tutvustame järgmisi kokkuleppeid: : 1) välimised sulud on välja jäetud; 2) esimesena sooritatakse sulgudes olevad toimingud; 3) loetakse, et sidemete prioriteet väheneb järgmises järjekorras : Ÿ, ⁄, ¤, Ø, ~. Samaväärsete konnektiivide ja ülejäänud konnektiivide (∆,|,∞) puhul tuleks praegu panna sulud.
Näited 1.3.2. Valemis x⁄y¤z on sulud paigutatud järgmiselt: ((x⁄y)¤z), sest operatsioon ⁄ on meie kokkuleppe kohaselt tugevam kui operatsioon ¤.
1. Valemis x¤y~zØx asetatakse sulud järgmiselt: ((x¤y)~(zØx))
2. Valemis (x∆y)~zØxy¤Ÿz asetatakse sulud järgmiselt: ((x∆y)~(zØ((xy)¤(Ÿz)))).
3. Valem xØyØz, järgides meie kokkulepet, pole õigesti kirjutatud, sest sulgude asetamine annab tulemuseks kaks erinevaid funktsioone: ((xØy)Øz) ja (xØ(yØz)).
§1.4. Olulised ja mitteolulised muutujad.
Boole'i funktsioon y=f(x 1 ,x 2 ,…,x n) oleneb oluliselt muutujast x k kui selline väärtuste kogum on olemas a 1 ,a 2 ,…,a k - 1, a k+1, a k + 2 ,…, a n et f (a 1,a 2,…,a k-1 , 0 ,a k+1,a k+2,…,a n) π f (a 1,a 2,…,a k-1 , 1 ,a k+1,a k+2,…,a n).
Sel juhul x k nimetatakse oluliseks muutujaks , muidu x k nimetatakse ebaoluliseks (näiv) muutujaks . Teisisõnu, muutuja on ebaoluline, kui selle muutmine ei muuda funktsiooni väärtust.
Näide 1.4.1. Olgu Boole'i funktsioonid f 1 (x 1 ,x 2) ja f 2 (x 1 ,x 2) defineeritud järgmise tõesuse tabeliga:
| x 1 | x 2 | f 1 (x 1, x 2) | f 2 (x 1, x 2) |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
Nende funktsioonide jaoks muutuja x 1 - on oluline ja muutuja x 2 ei ole oluline.
Ilmselt ei muuda Boole'i funktsioonid oma väärtusi ebaolulisi muutujaid sisestades (või eemaldades). Seetõttu käsitletakse edaspidi Boole'i funktsioone kuni ebaoluliste muutujateni (näites võime kirjutada: f 1 (x 1 , x 2) = x 1, f 2 (x 1, x 2) = Ÿx 1).
§1.5. Tõe tabelid. Samaväärsed funktsioonid.
Teades elementaarfunktsioonide tõesuse tabeleid, saate arvutada selle valemi rakendatava funktsiooni tõesuse tabeli.
Näide 1.5.1. F1=x 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)
Seega rakendab valem F1 disjunktsiooni. Näide 1.5.2. F2 = x 1 ⁄x 2 Øx 1
Seega rakendab valem F3 disjunktsiooni.
Kutsutakse Boole'i funktsioone f1 ja f2 samaväärne, kui igal komplektil ( a 1 ,a 2 ,…, a n) nullid ja ühed, funktsioonide väärtused langevad kokku. Samaväärsete funktsioonide tähistus on järgmine : f1=f2.
Toodud näidete 1-3 järgi saame kirjutada
X 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)=x 1 ¤x 2 ¤;
X 1 ⁄x 2 Øx 1 =1;
((x 1 ⁄x 2) ∆x 1) ∆x 2 =x 1 ¤x 2.
§1.6. Põhilised vasted.
Antud ekvivalendid on sageli kasulikud Boole'i funktsioonidega töötamisel.
Allpool H, H1, H2,... tähistavad mõningaid Boole'i funktsioone.
1. Topelteituse seadus: H = H.
2. Idempotentsus
3. Kommutatiivsus:
H1*H2=H2*H1, kus sümbol * tähendab ühte konnektiividest &, ¤, ∆,
4. Assotsiatiivsus:
H1*(H2*H3)=(H1*H2)*H3, kus sümbol * tähendab ühte konnektiividest &, ¤, ∆, ~.
5. Jaotus:
H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).
6. De Morgani seadused:
H1& H2 = H1 ∨ H2, H1∨ H2 = H1 & H2.
7. Ülevõtmise reeglid:
H1¤(H2&H3)=H1, H1&(H2¤H3)=H1
8. Liimimise seadused:
H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.
9. Inversiooniseadused: H ∨ H = 1, H & H = 0.
10. Konstantidega tehte reeglid:
H¤1=1, H&1=H, H¤0=H, H&0=0.
Ülaltoodud ekvivalentide tõesuse kontrollimiseks piisab, kui koostada vastavad tõesuse tabelid.
Pange tähele, et toimingu assotsiatiivsus võimaldab seda toimingut laiendada mis tahes arvule muutujatele. Nii et näiteks märge x¤у¤z¤w on õige, sest mis tahes sulgude paigutus annab sama funktsiooni. Operatsiooni kommutatiivne olemus võimaldab teil valemis muutujaid vahetada. Näiteks x⁄y⁄z⁄w=w⁄y⁄x⁄z.
§1.7. Funktsionaalne täielikkus.
Tüüpilises kaasaegses digitaalarvutis on numbrid 0 ja 1. Seetõttu on protsessori poolt täidetavad käsud Boole'i funktsioonid. Allpool näitame, et iga Boole'i funktsiooni rakendatakse konjunktsiooni, disjunktsiooni ja eituse kaudu. Järelikult on võimalik ehitada vajalik protsessor, mille käsutuses on konjunktsiooni, disjunktsiooni ja eitust realiseerivad elemendid. See osa on pühendatud sellele, et vastata küsimusele: kas on (ja kui jah, siis milliseid) muid Boole'i funktsioonide süsteeme, millel on omadus, et neid saab kasutada kõigi teiste funktsioonide väljendamiseks.
Tutvustame mitmeid funktsioonide klasse.
1. Funktsioonide klass, mis säilitavad konstanti 0, s.o. selliseid funktsioone
2. Funktsioonide klass, mis säilitavad konstanti 1, s.o. selliseid funktsioone
3. Ise-duaalfunktsioonide klass, s.o. sellised funktsioonid y=f(x 1 ,x 2 ,…,x n) nii, et f(x 1 , x 2 ,… , x n) = f(x 1 , x 2 ,… , x n) .
4. Lineaarfunktsioonide klass, s.o. sellised funktsioonid y=f(x 1 ,x 2 ,…,x n), mida saab esitada kujul f(x 1 ,x 2 ,…,x n)=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆… ∆ c n x n, kus c 0, c 1, c 2 ...koefitsiendid, mis võivad saada väärtuseks 0 või 1.
5. Monotoonsete funktsioonide klass. Nullide ja ühtede hulgal Bn =((x 1 ,x 2 ,…,x n):x i œ(0,1),i=1,2,…,n) esitame osalise järjekorra järgmiselt:
(a 1 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) kui ja ainult kui a 1 § b 1 , a 2 § b 2,…,a n § b n. Funktsiooni f(x 1, x 2,..., x n) nimetatakse monotoonseks, kui mis tahes kahe B n elemendi puhul nii, et
(a 1 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) järeldub, et f( a 1 ,a 2 ,...,a n)§f( b 1 ,b 2 ,...,b n).
Kutsutakse Boole'i funktsioonide süsteemi S, mille superpositsioon võib esindada mis tahes Boole'i funktsiooni funktsionaalselt täielik . Öeldakse, et moodustub funktsionaalselt terviklik Boole'i funktsioonide süsteem S alus loogilises ruumis. Baasi S nimetatakse minimaalne , kui mõne funktsiooni eemaldamine sellest muudab selle süsteemi mittetäielikuks.
Täielikkuse kriteerium (postituse teoreem) . Boole'i funktsioonide süsteem S on täielik siis ja ainult siis, kui see sisaldab vähemalt ühte funktsiooni: mittesäiliv konstant 0, mittesäilitav konstant 1, mitte-duaalne, mittelineaarne ja mittemonotoonne.
Tabel 1.7 näitab elementaarsete Boole'i funktsioonide omadusi (sümbol * tähistab omadust, mis antud funktsioonil on).
Kasutades Posti teoreemi ja tabelit 1.7, saab järgmise reegli järgi ehitada elementaarfunktsioonidest aluseid. Valides mis tahes elementaarse Boole'i funktsiooni ja vajadusel täiendades seda teiste funktsioonidega nii, et need kõik koos rahuldavad teoreemi umbes funktsionaalne täielikkus. Selle aluse funktsioonide kaudu saame väljendada Kõik muud Boole'i funktsioonid.
Ehitame mõned rakendustes sageli kasutatavad alused.
Tabel 1.7
| Nimi | Määramine | Säilitamatus konstandid |
Säilitamatus konstandid |
Samodvoys kehtivus |
||
| Konst.0 | 0 | * | * | |||
| Konst.1 | 1 | * | * | |||
| Negatiivne | Ÿ | * | * | * | ||
| Kongyun. | & | * | * | |||
| Disjunktsioon. | ¤ | * | * | |||
| Kaudne. | Ø | * | * | * | * | |
| Samaväärne. | ~ | * | * | * | ||
| Summa mod_2 järgi | ∆ | * | * | * | ||
| | | * | * | * | * | * | |
| Pierce'i nool | ∞ | * | * | * | * | * |
1. Funktsioonide süsteem S1=(Ÿ,⁄,¤) moodustab aluse. Boole'i funktsiooni taandamiseks vormiks, mis sisaldab ainult aluse S1 konnektiive, võivad olla kasulikud järgmised ekvivalentsid: x → y = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , xy = x ∨ y , x ↓ y = x & y .
2. Aluse moodustab süsteem S2=(Ÿ,&). Suvaline funktsioon saab esmalt taandada vormiks, mis sisaldab konnektiivi S1-st ja seejärel
kasuta seost x ∨ y = x ⋅ y.
3. Süsteem S3=(Ÿ,¤) moodustab aluse. Suvalise funktsiooni saab esmalt taandada vormiks, mis sisaldab konnekive S1-st ja seejärel
kasuta seost x ⋅ y = x ∨ y.
4. Aluse moodustab süsteem S4=(1,&,∆). Suvalise funktsiooni saab esmalt taandada vormiks, mis sisaldab konnektiivisid S1-st ja seejärel kasutada seoseid x = 1⊕ x, x ∨ y = x ⊕ y ⊕ x ⋅ y.
5. Aluse moodustab süsteem S5=(|). Suvalise funktsiooni saab esmalt taandada vormiks, mis sisaldab konnekive S2-st ja seejärel kasutada seoseid x ⋅ y = x y , x = xx .
6. Aluse moodustab süsteem S6=(∞). Suvalise funktsiooni saab esmalt taandada vormiks, mis sisaldab konnekive S3-st ja seejärel
kasuta seoseid x ∨ y = x ↓ y, x = x ↓ x.
7. Aluse moodustab süsteem S7=(Ø,0).
Näide 1.7.1. Kirjutage funktsioon x¨(y∆z) alusele S1=(Ÿ,⁄,¤). x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⊕ z)
II peatükk. Boole'i algebra.
Kõigi baasis sisalduvate tõeväärtuste hulk S1=( ÿ, &, ⁄} vormi Boole'i algebra. Seega kirjutatakse Boole'i algebras kõik valemid kolme konnektiivi abil: Ÿ, &, ¤. Osaliselt uurisime selle algebra omadusi I peatükis (vt näiteks põhiekvivalentse). See peatükk käsitleb Boole'i algebra omadusi ja seetõttu käsitleme selles peatükis ainult kolme funktsiooni: ÿ, &, ⁄.
§2.1. Tavalised vormid.
Normaalvormid on süntaktiliselt ühemõtteline viis valemi kirjutamiseks, mis rakendab antud funktsiooni.
Kui x on loogiline muutuja ja σœ(0,1), siis avaldist x σ = x, kui σσ == 10 või x σ = 10 kui x x =≠σσ , nimetatakse x täheks . Tähti x ja Ÿx nimetatakse kontrastideks. Konjunkt disjunktne nimetatakse tähtede disjunktsiooniks. Näiteks valemid x ⋅ y ⋅ z ja x ⋅ y ⋅ x ⋅ x on konjunktid, valemid x ∨ y ∨ z ja x ∨ y ∨ x on disjunktid ning valem z on nii konjunkt kui ka disjunkt.
Disjunktiivne normaalvorm (DNF) nimetatakse lõpliku arvu sidendite disjunktsiooniks .
Konjunktiivne normaalvorm (CNF) nimetatakse lõpliku arvu kõrvallausete konjunktsiooniks .
Lihtsamalt öeldes: DNF on korrutiste summa ja CNF on loogiliste summade korrutis. Näited.
1. xÿy¤yÿz¤x on DNF (toodete summa).
2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z on CNF (summade korrutis).
3. x ∨ y ∨ z ∨ w on DNF ja CNF (samaaegselt).
4. x ⋅ y ⋅ z ⋅ w on DNF ja CNF (samaaegselt).
5. (x¤x¤y)·(y¤z¤x)·z on CNF.
6. x⋅y⋅z ja x⋅y⋅x⋅x on DNF-id.
7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z ei ole tavavorm (mitte DNF ega CNF).
Olgu funktsioon f kirjutatud alusesse S1. See funktsioon vähendatakse normaalsele kujule järgmiselt:
1) kasutame De Morgani seadusi valemi teisendamiseks selliseks vormiks, kus negatiivsed märgid on seotud ainult üksikute muutujatega;
2) rakendame topeltnegatiivide eemaldamise reeglit: ŸŸx=x;
H1&(H2¤H3)=(H1&H2)¤(H1&H3) , ja teine jaotusseadus taandamiseks CNF-iks. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).
Igal Boole'i funktsioonil võib olla lõpmatu arv DNF- ja CNF-esitusi. Näiteks kasutades täiendavalt inversiooniseadusi ja konstantidega tehtereegleid, on võimalik tagada, et igas üksikus konjunktis või disjunktis ei esine ükski muutuja rohkem kui üks kord (kas ise või selle eitus).
Näide 2.1.1. DNF-i taandamiseks kasutame esimest jaotusseadust.
x⋅y⋅x⋅y⋅z⋅(y∨z)=x⋅y⋅(x∨y∨z)⋅(y∨z)=(x⋅y⋅x∨x⋅y⋅y∨x⋅y ⋅z)⋅(y∨z)= on CNF
= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = - see on veel üks CNF
X ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⋅ = y
X ⋅ y ⋅ z ∨ x ⋅ y ⋅ z on DNF
Näide 2.1.2. CNF-i taandamiseks on vaja kasutada teist jaotusseadust.
x ∨ y ⋅ x ⋅ y ∨ z = x ∨ y ⋅ (x ⋅ y ⋅ z) = x ∨ y ⋅ (x ∨ y) ⋅ z =
X∨y⋅z⋅(x∨y)=(x∨y⋅z)⋅(x∨x∨y)=(x∨y)⋅(x∨z)⋅(1∨y)=
= (x ∨ y) ⋅ (x ∨ z) on CNF
§2.2. Täiuslikud normaalvormid.
Kui normaalvormi igas liikmes on esindatud kõik muutujad (kas ise või nende eitused) ja igas üksikus konjunktis või disjunktsioonis esineb mõni muutuja täpselt ühe korra (kas ise või selle eitus), siis seda vormi nimetatakse täiuslik normaalvorm (SDNF või SCNF). Näited: Olgu antud kolme muutuja f(x,y,z) funktsioon.
1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z on täiuslik DNF.
2. (x ∨ y ∨ z) ⋅(x ∨ y ∨ z) ⋅(x ∨ y ∨ z) on täiuslik CNF.
3. (x ∨ y) ⋅ (x ∨ z) ei ole täiuslik CNF, sest näiteks esimene summa ei sisalda muutujat z.
4. xÿyÿz on täiuslik DNF. Teoreem 2.2.1.
1. Igal Boole'i funktsioonil, mis ei ole identselt null, on ainult üks SDNF kuni terminite asukohani.
2. Igal Boole'i funktsioonil, mis ei ole 1-ga identne, on ainult üks SCNF kuni terminite asukohani.
Tõestame teoreemi konstruktiivselt järgmise ülesande lahendusena: Selle tõesuse tabeli abil konstrueerige SDNF.
Vaatleme lahendust tabelis (tabel 2.2) toodud funktsiooni f(x,y,z) näitel n=3 korral.
Näide 2.2.1. Selle tõesuse tabeli (tabel 2.2) abil konstrueerige SDNF.
Tabel 2.2
| x | y | z | põhilised sidesõnad |
f(x,y,z) |
| 0 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 0 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 1 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 1 | x ⋅ y ⋅ z | 1 |
Põhilised sidesõnad (või koostisosad_1) sisalduvad tabelis vastavad kindlale nullide ja ühtede hulgale, mille võtavad muutujad x,y,z. Koostisosad ehitatakse_ 1 vastavalt järgmisele reeglile: muutuja sisaldub korrutises endas, kui ta võtab antud hulgal väärtuse 1, vastasel juhul sisaldub selle eitus korrutises. Nii et näiteks hulgal (0,0,1) saavad muutujad x,y väärtuseks 0 ja seetõttu sisalduvad nende eitused korrutises ning muutuja z saab väärtuse 1 ja seetõttu sisaldub see korrutises endas . Antud hulga (0,0,1) korral on koostisosa_1 võrdne x ⋅ y ⋅ z .
Ilmselgelt on side x ⋅ y ⋅ z võrdne 1-ga ainult hulgal
(0,0,0) ja x ⋅ y ⋅ z on komplektis 1 (0,0,1) jne. (vt tabelit). Järgmisena pange tähele, et kahe põhikonjunktsiooni disjunktsioon on võrdne 1-ga täpselt kahel hulgal, mis vastavad neile põhikonjunktsioonidele. Näiteks funktsioon x ⋅ y ⋅ z¤x ⋅ y ⋅ z on võrdne 1-ga ainult kahes hulgas - (0,0,0) ja (0,0,1) ning kõigis teistes hulkades 0. Samamoodi on kolme põhikonjunktsiooni disjunkts võrdne 1-ga täpselt kolmel hulgal, mis vastavad neile põhiliitetele jne.
See. saame reegel: SDNF-i ehitamiseks peaksite valima read, milles funktsioon on võrdne 1-ga, ja seejärel võtma vastavate põhisidendite disjunktsiooni, saame soovitud SDNF-i. Meie näite puhul on meil x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .
Ülesanne. Selle tõesuse tabeli abil koostage SCNF.
Põhiseadus_0 nullide ja ühtede hulk (mis võtavad muutujad x,y,z) konstrueeritakse järgmiselt: muutuja kaasatakse disjunktsiooni endasse, kui ta võtab selle hulga väärtuse 0 , vastasel juhul sisaldab teos selle eitust.
SKNF-i ehitamise reegel: tuleks valida read, milles funktsioon on võrdne 0 , ja seejärel võtke vastavate koostisosade konjunkt_0. Tulemuseks on soovitud SCNF. Seega on meie näites f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .
Kommenteeri. Täiusliku CNF-funktsiooni f konstrueerimiseks piisab, kui konstrueerida funktsiooni f jaoks täiuslik DNF ja siis
Koostame oma näite jaoks SCNF-i märkuse põhjal. 1. Ehitame eitamiseks SDNF-i.
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z
2. Kasutame de Morgani seadusi f = f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z = x ⋅ y⋅ z&x ⋅ y⋅z&x ⋅ = z ⋈ ⋅ = z ) ⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .
Kirjeldatud meetod SDNF-i (ja SCNF-i) leidmiseks tõetabeli abil on sageli töömahukam kui järgmine algoritm.
1. SDNF-i leidmiseks Esmalt taandame selle valemi DNF-iks.
2. Kui mingi side K (st K on teatud arvu muutujate või nende eituste korrutis) ei sisalda näiteks muutujat y, siis asendame selle sidesõna ekvivalentse valemiga K&(y ∨ y) ja rakendades jaotusseadus, esitame saadud valemi DNF-ile; kui puuduvaid muutujaid on mitu, siis igale neist lisame konjunktsioonile vastava vormi valemi (y ∨ y).
3. Kui saadud DNF sisaldab ühiku mitut identset koostisosa, siis jätame neist ainult ühe. Tulemuseks on SDNF.
Kommenteeri: SCNF-i konstrueerimine lauseks, mis ei sisalda näiteks muutujat juures lisame valemi kujul y⋅ y, s.t. Asendame selle disjunkti ekvivalentse valemiga D ∨ y⋅ y ja rakendame distributiivsuse 2. seadust.
Näide 2. 2. 2. Koostage funktsiooni f jaoks samaväärsete teisenduste abil SDNF.
f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x x ⋅ y ⋅ z x y y z y ⋅ z ⋅ x y ⋅ z ⋅ x =
TAGANEMINE.
SDNF-i arvutamine pole mitte ainult teoreetiline, vaid ka suure praktilise tähtsusega. Näiteks paljudes kaasaegsed programmid graafilise liidesega kasutatakse keerukate loogiliste tingimuste loomiseks visuaalset vormi tabeli kujul: tingimused kirjutatakse lahtritesse ja ühe veeru lahtrid loetakse sidesõnaga ühendatuks ja veerud ühendatuks disjunktsiooni teel, see tähendab, et nad moodustavad DNF-i (või vastupidi, sel juhul saadakse CNF). Eelkõige on nii loodud QBE (Query-byExample) graafiline liides, mida kasutatakse DBMS-i päringute tegemisel loogiliste tingimuste formuleerimiseks.
Algoritm 2.2.1. SDNF ehitus
Sissepääs: vektor X: stringi massiiv – muutuja identifikaatorid, maatriks V: massiiv 0..1 kõigist erinevatest muutujaväärtuste komplektidest,
vektor F: 0..1 vastava funktsiooni väärtuse massiiv.
Väljumine: sümbolite jada, mis moodustab antud funktsiooni SDNF-i valemi kirje.
f:= vale(märk disjunktsiooni vasakpoolse operandi olemasolust) jaoks i alates 1juurde 2n teha
kui F[i] = 1 siis kui f siis
saagikus"¤" (disjunktsioonimärgi lisamine valemile; operaator saagikus m trükib
sümbol m) muidu f:= tõsi
lõpp kui g:= vale(märk sidesõna vasakpoolse operandi olemasolust) jaoks j alates 1juurde n tee kui g siis
saagikus"⁄" (lisades valemile sidemärgi)
muidu g: =tõene
lõpp, kui kui V ( muutuja identifikaatori lisamine valemisse
§2.3. DNF-i minimeerimine Quine'i meetodil.
Igal valemil on lõplik number muutujate esinemised. Muutuja esinemine viitab kohale, mille muutuja valemis hõivab. Ülesanne on leida antud Boole'i funktsiooni f jaoks DNF, mis seda funktsiooni esindab ja millel on väikseim muutujate arv.
Kui x on loogiline muutuja ja σœ(0,1), siis avaldis x σ =xx, kui kui σσ== 10 .
helistas kiri . Konjunkt nimetatakse tähtede sidesõnaks. Näiteks valemid x ⋅ y ⋅ z ja x ⋅ y ⋅ x ⋅ x on sidesõnad . Elementaarkorrutis on side, milles iga muutuja ei esine rohkem kui üks kord (kas ise või selle eitus).
Valemit f1 nimetatakse implicantne valemid f , kui f1 on elementaarkorrutis ja f 1 ⁄ f = f 1, s.o. ehk valemitele vastavate funktsioonide puhul kehtib võrratus f 1 § f. Nimetatakse valemi f implikant f1 lihtne , kui pärast f1 mis tahes tähe kõrvalejätmist ei saada valemit, mis oleks valemi f implikant.
Näide 2.3.1 . Leiame valemi f=xØy kõik implikandid ja lihtsad implikandid . Muutujatega elementaarseid tooteid on kokku 8 X Ja u. Selguse huvides on allpool toodud nende tõetabelid:
| x | y | xØy | x ⋅ a | x ⋅ a | x ⋅ a | x ⋅ a | x | y | x | y | |||||||
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |||||||
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |||||||
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | |||||||
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | |||||||
Tõetabelitest järeldame, et valemid x ⋅ y , x ⋅ y , x ⋅ y , x ,y - kõik valemi xØy implikandid ning nendest implikantidest on valemid x ja y lihtsad (valem x ⋅ y näiteks ei ole lihtne implikant, kuna tähe y kõrvale jättes saame implikant x).
Lühendatult DNF nimetatakse antud valemi (funktsiooni) kõigi algimplikantide disjunktsiooniks. .
Teoreem 2.3.1. Iga Boole'i funktsiooni, mis ei ole konstant 0, saab esitada stenogrammi DNF-ina.
Näites 2.3.1 on valemile xØy vastav funktsioon esitatud valemiga x ∨ y, mis on selle lühend DNF.
Vähendatud DNF võib sisaldada täiendavaid implicante, mille eemaldamine ei muuda tõetabelit. Kui eemaldame vähendatud DNF-ist kõik mittevajalikud implicandid, saame DNF-i nimega tupiktee.
Pange tähele, et funktsiooni esitus tupik-DNF-ina on üldiselt mitmetähenduslik. Valides kõigi tupikvormide hulgast, annab kõige väiksema muutujate esinemissagedusega vorm minimaalne DNF (MDNF).
Kaaluge meetodit Quina, et leida antud Boole'i funktsiooni esindav MDNF. Määratleme järgmised kolm toimingut:
1. täielik liimimisoperatsioon : f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;
2. osaline liimimisoperatsioon:
f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;
3. elementaarneeldumise toiming f ⋅ x σ ∨ f = f , σ ∈ (0,1) .
Teoreem 2.3.2(Quine'i teoreem). Kui SDNF funktsiooni põhjal teostame kõik võimalikud mittetäieliku liimimise ja seejärel elementaarse neeldumise toimingud, siis on tulemuseks vähendatud DNF, st kõigi lihtsate implikantide disjunktsioon.
Näide 2.3.2. Olgu funktsioon f(x,y,z) antud täiusliku DNF-iga f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Seejärel tehes kahes etapis kõik võimalikud mittetäieliku liimimise ja seejärel elementaarse neeldumise toimingud, saame
f 
Seega on funktsiooni f lühendatud DNF valem y¤x·z.
Praktikas on igas etapis mittetäielike liimimistoimingute tegemisel võimalik mitte kirjutada nende toimingutega seotud termineid, vaid kirjutada ainult kõigi võimalike täielike liimimiste ja sidendite tulemused, mis ei ole seotud ühegi liimimisega.
Näide 2. 3. 3. Olgu funktsioon f(x,y,z) antud täiusliku DNF-iga f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .
Seejärel liimimise ja seejärel elementaarse neeldumise toiminguid sooritades on meil
f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ z
Vähendatud DNF-ist minimaalse DNF-i saamiseks kasutatakse Quine'i maatriksit , mis on üles ehitatud järgmiselt. Tabeli veerupealkirjad sisaldavad täiusliku DNF-i ühiku koostisosi ja reapealkirjad sisaldavad saadud lühendatud DNF-i lihtsaid implikante. Tabelis tähistavad tärnid neid ridade ja veergude lõikekohti, mille reapäises olev konjunkt sisaldub üksuse koostisosas, milleks on veerupäis.
Näiteks 2.3.3. Quine'i maatriksil on vorm
Ummik-DNF-is valitakse minimaalne arv lihtsaid implikante, mille disjunktsioon säilitab kõik ühiku koostisosad, st Quine'i maatriksi iga veerg sisaldab tärni ristumiskohas reaga, mis vastab ühele valitud implicandid. Minimaalseks DNF-iks valitakse tupik-DNF, millel on väikseim muutujate esinemissagedus.
Näites 2.3.3, kasutades Quine'i maatriksit, leiame, et antud funktsiooni minimaalne DNF on x ⋅ y ¤ x ⋅ z.
Kommenteeri.
kasutage f =f ja De Morgani seadusi.
§ 2.4. Carnot kaardid.
Teine viis väikese arvu muutujatega lihtsate implicantvalemite saamiseks (ja seega ka minimaalse DNF-i leidmiseks) põhineb nn Carnot' kaartide kasutamisel.
Carnot' kaart on eritüüp tabel, mis lihtsustab minimaalsete vormide leidmist ja mida kasutatakse edukalt, kui muutujate arv ei ületa kuut. Karnaugh' kaardid funktsioonide jaoks, mis sõltuvad n muutujast, on ristkülik, mis on jagatud 2 n lahtriks. Diagrammi iga lahter on seotud binaarse n-mõõtmelise hulgaga. Tõetabelist antud funktsiooni f väärtused sisestatakse nõutavatesse ruutudesse, kuid kui lahter vastab 0-le, jääb see tavaliselt tühjaks.
Tabelis 2.4.1. näitab näidet kolmest muutujast sõltuva funktsiooni Karnaugh' kaardi märkimisest. Kaardi neli alumist lahtrit vastavad binaarsetele komplektidele, milles muutuja x võtab väärtuse 1, vastavad neli ülemist lahtrit komplektidele, milles muutuja x võtab väärtuse 0. Neli lahtrit, mis moodustavad kaardi parema poole, vastavad hulgale, milles muutuja y; võtab väärtuse 1 jne. Tabelis 2.4.2. Näidatud on Karnaugh' kaardi märgistus n=4 muutuja jaoks.
Minimaalse DNF-i konstrueerimiseks teostame liimimisprotseduur "1". Koos kleepuvad väärtused "1" vastavad naaberlahtritele, st. lahtrid, mis erinevad ainult ühe muutuja väärtuse poolest (graafilisel pildil vertikaalse või horisontaalse joonega eraldatud, võttes arvesse vastassuunaliste äärmuslike lahtrite lähedust).
"1" liimimise protsess taandub Karnaugh' kaardi üksikute lahtrite ühendamisele rühmadesse ja järgida tuleb järgmisi reegleid;
1. Ühte rühma kuuluvate lahtrite arv tuleb väljendada 2 kordsena, s.o. 2 m kus m=0,1,2,...
2. Igas 2 m rakust koosnevasse rühma kuuluvas lahtris peab rühmas olema m naaberrakku.
3. Iga lahter peab kuuluma vähemalt ühte rühma.
4. Igas rühmas peaks olema maksimaalne arv lahtreid, st. ükski rühm ei tohiks sisalduda teises rühmas.
5. Rühmade arv peaks olema minimaalne.
Lugemisfunktsioon f vastavalt liimimisrühmale viiakse läbi järgmiselt: muutujad, mis salvestavad samad väärtused liimimisrühma lahtrites sisenevad nad konjunktsiooni ja väärtused 1 vastavad muutujatele endale ja väärtused 0 vastavad nende eitustele.
Esitame mallid, mis aitavad luua katteid 1 (me loeme muutujaid samadeks, kuid me ei kirjuta neid). Märkimise lihtsustamiseks me muutujaid ei märgi, kuigi säilitame nende tähistused nagu tabelites 2.4.1, 2.4.2.
| 1 | 1 |
| 1 | 1 |
| F=Ÿy&x | |
| 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 |
| 1 | 1 | 1 |
| 1 |
F=Ÿz&Ÿy f=Ÿx&y
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
F=Ÿx&z f=y&w F=Ÿx&Ÿy
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||
| 1 | 1 |
F=Ÿy&Ÿw f=Ÿy&Ÿz F=Ÿz&Ÿx
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | ||||
| 1 | 1 | 1 | 1 |
F=y&z&w f=Ÿy&Ÿz&Ÿw F=x&y&Ÿz
| 1 | ||
| 1 | ||
| 1 | 1 | 1 |
| 1 |
Näide 2.4.1. Ehitage MDNF.
Kõigepealt vaatame, kas seal on katteid_ 1 16-st lahtrist, mis katavad vähemalt ühte katmata 1. Selliseid katteid pole. Liigume edasi 8 raku katetele. Vaatame, kas 8-st lahtrist on 1 kaaned, mis katavad vähemalt ühe katmata 1. Selliseid katteid pole. Liigume edasi 4 raku katetele. Vaatame, kas on olemas kaaned 1-st 4-st, mis katavad vähemalt ühe katmata 1. Selliseid katteid on kaks. Liigume edasi 2 raku katetele. Sellist katet on ainult üks. Seega said kõik 1 kaetud. Järgmisena vaatame, kas saame osa katteid eemaldada, nii et kõik üksused jääksid kaetud. Lõpus kirjutame välja MDNF: f =x⋅z∨y⋅w∨y⋅z⋅w.
Kommenteeri. Funktsiooni f minimaalse CNF-i konstrueerimiseks piisab funktsiooni f minimaalse DNF-i konstrueerimisest ja seejärel
kasutage f =f ja De Morgani seadusi.
III peatükk. Zhegalkini algebra.
Zhegalkini baasis S4=(∆,&,1) defineeritud Boole'i funktsioonide hulka nimetatakse Zhegalkini algebraks.
Põhiomadused.
1. kommutatiivsus
H1∆H2=H2∆H1, H1&H2=H2
2. assotsiatiivsus
H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)
3. distributiivsus
H1&(H2∆H3)=(H1&H2)∆(H1&H3);
4. konstantide H&1=H, H&0=0, H∆0=H omadused;
5. H∆H=0, H&H=H.
Väide 3.1.1. Kõiki teisi Boole'i funktsioone saab väljendada Zhegalkini algebra tehte abil:
Ÿx=1∆x, x¤y=x∆y∆xy, x~y=1∆x∆y, xØy=1∆x∆xy, x∞y=1∆x∆y∆xy, x|y= 1∆xy.
Definitsioon. Zhegalkini polünoom (polünoomi moodul 2) n muutujaga x 1 ,x 2 ,…,x n on avaldis kujul c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…xn,x1x2, kus konstant on võib võtta väärtused 0 või 1.
Kui Zhegalkini polünoom ei sisalda üksikute muutujate korrutisi, siis nimetatakse seda lineaarseks (lineaarfunktsioon).
Näiteks f=x∆yz∆xyz ja f1=1∆x∆y∆z on polünoomid, teine on lineaarfunktsioon.
Teoreem 3.1.1. Iga Boole'i funktsioon on esitatud Zhegalkini polünoomi kujul ainulaadsel viisil.
Toome välja peamised meetodid Zhegalkini polünoomide konstrueerimiseks antud funktsioonist.
1. Ebakindla koefitsiendi meetod . Olgu P(x 1 ,x 2 ,…,x n) soovitud Žegalkini polünoom, mis realiseerib antud funktsiooni f(x 1 ,x 2 ,…,xn). Kirjutame selle vormi
P= c 0 ∆c 1 x 1 ∆c 2 x 2 ∆…∆c n x n ∆c 12 x 1 x 2 ∆…∆c12… n x 1 x 2 …x n .
Leiame koefitsiendid k-ga. Selleks omistame igast tõesuse tabeli reast järjestikku muutujatele x 1 , x 2 ,…, x n väärtused. Selle tulemusena saame 2 n võrrandist koosneva süsteemi 2 n tundmatuga, millel on kordumatu lahendus. Olles selle lahendanud, leiame polünoomi P(x 1 ,x 2 ,…,xn) koefitsiendid.
2. Meetod, mis põhineb valemite teisendamisel konnektiivide komplekti kaudu ( ÿ,&}. Koostage mingi valem Ф üle konnektiivide hulga (Ÿ,&), realiseerides antud funktsiooni f(x 1 ,x 2 ,…,x n). Seejärel asendage kõikjal vormi A alamvalemid A∆1-ga, avage jaotusseaduse abil sulud (vt omadus 3) ja seejärel rakendage atribuudid 4 ja 5.
Näide 3.1.1. Koostage funktsiooni f(x,y)=xØy jaoks Zhegalkini polünoom.
Lahendus. 1 . (määramata koefitsientide meetod). Kirjutame vormile nõutud polünoomi
P(x,y)= c 0 ∆c 1 x∆c 2 y∆c 12 xy Tõetabeli kasutamine
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| xØy | 1 | 1 | 0 | 1 |
leiame, et f(0,0)=P(0,0)= c 0 =1, f(0,1)=P(0,1)= c 0 ∆ c 2 =1, f(1,0) =P(1,0)= c 0 ∆c 1 =0, f(1,1)=P(1,1)= c 0 ∆c 1 ∆c 2 ∆c 12 =1
Sealt, kust me järjekindlalt leiame, c 0 =1, c 1 =1, c 2 =0, c 12 =1. Seetõttu xØy=1∆x∆xy (võrdle väitega 3.1).
2. (Valemi teisendusmeetod.) Meil on
x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .
Pange tähele, et Zhegalkini algebra eeliseks (võrreldes teiste algebratega) on loogika aritmetiseerimine, mis võimaldab Boole'i funktsioonide teisendusi sooritada üsna lihtsalt. Selle puuduseks Boole'i algebraga võrreldes on valemite kohmakus.
IV peatükk. avaldused. Predikaadid.
§4.1. avaldused.
Loogika algebra koostamisel kasutasime funktsionaalset lähenemist. Seda algebrat oleks aga võimalik konstruktiivselt konstrueerida. Esmalt määratlege uurimisobjektid (väited), tutvustage nende objektidega tehteid ja uurige nende omadusi. Andkem ametlikud määratlused.
Öeldes Nimetagem deklaratiivset lauset, mille kohta saab üheselt öelda, kas see on konkreetsel ajahetkel tõene (väärtus I või 1) või väär (väärtus L või 0). Näiteks “5 on algarv”, “Esc-klahvi vajutatud” jne. Konnektiivide "mitte", "ja", "või", "kui,... siis", "kui ja ainult siis" kasutamine (need vastavad tehtele "Ÿ", "&", "¤", "Ø" , “~” » vastavalt, saab koostada keerukamaid väiteid (lauseid). Nii konstrueeritakse propositsioonialgebra.
Keeruliste väidete salvestamise lihtsustamiseks tuuakse sisse konnektiivide ülimuslikkus: “Ÿ”, “&”, “¤”, “Ø”, “~”, mis aitab ära jätta mittevajalikud sulud.
Lihtlauseid nimetame propositsioonimuutujateks.
Tutvustame valemi mõistet.
1. Propositsioonimuutujad on valemid.
2. Kui A, B on valemid, siis avaldised ŸA, A⁄B, A¤B, AØB, A~B on valemid.
3. Valemid on ainult lõigete 1 ja 2 kohaselt koostatud avaldised.
Kutsutakse valemit, mis võtab kõigi propositsioonimuutujate väärtuste jaoks väärtuse JA tautoloogia (või üldiselt kehtiv), ja kutsutakse valem, mis võtab kõigi propositsioonimuutujate väärtuste jaoks väärtuse A vastuoluline (või võimatu)
Propositsioonialgebra omaduste kirjeldus on sarnane Boole'i algebra vastavate funktsioonide kirjeldusega ja jätame need välja.
§4.2. Predikaadid. Loogilised operatsioonid predikaatidega.
Selle peatüki uurimisobjektiks on predikaadid – suvaliste hulkade vastendamine väidete kogumiks. Tegelikult teeme ülemineku uuele abstraktsioonitasemele, sama tüüpi üleminekule, mis tehti koolis – reaalarvude aritmeetikalt arvfunktsioonide algebrale.
Definitsioon 2.1 Olgu x 1 ,x 2 ,…,xn suvalise iseloomuga muutujate sümbolid. Nimetame neid muutujaid teemamuutujateks. Olgu muutujate hulgad (x 1 ,x 2 ,…,x n) kuuluvad hulka M=(M1,M2,…Mn), mida me nimetame teemavaldkonnaks (st x i œM i, kus Mi nimetatakse domeeniks muutuja xi määratlusest). Kohapredikaat n (n-kohaline predikaat), mis on defineeritud teemaalal M, on loogiline funktsioon, mis võtab kas väärtuse JA või väärtuse L.
Näide 4.2.1. D(x1,x2) = "Naturaalarv x1 jagatakse (ilma jäägita) naturaalarvuga x2." - paaride hulgal määratletud kahekohaline predikaat naturaalarvud M=NäN. Ilmselgelt D(4,2) = ja D(3,5) = 0.
Näide 4.2.2. Q(x) ==“x 2<-1, хœR» - одноместный предикат, определенный на множестве reaalarvud M=R. On selge, et Q(1) = А, Q(5) = А ja üldiselt on predikaat Q(x) identselt väär, s.t.
Q(x) = А kõigi xœR jaoks.
Näide 4.2.3. B(x,y,z) = “x 2 +y 2 M-ga defineeritud predikaati P nimetatakse identselt tõeseks, kui see võtab subjekti muutujate mis tahes väärtuste jaoks väärtuse AND; Predikaati P nimetatakse identselt vääraks, kui see võtab subjekti muutujate mis tahes väärtuste jaoks väärtuse A. Predikaat Q näitest 4.2.2. on samamoodi vale. Kuna predikaadid on funktsioonid, mille väärtus on lausekomplektis, kus sisestatakse loogilised toimingud, on need toimingud loomulikult predikaatide jaoks määratletud. Olgu P ja Q M defineeritud predikaadid. Siis 1. ¬P(x, x,…, x n) = P(x, x,…, x) ∧ 1 2 n 1 2 n ∧ 1 2 n 3. (P ∨ Q) (x 1 , x 2 ,…, x n) = P(x 1 , x 2 ,…, x n) ∨ Q(x 1 , x 2 ,…, x n) 4. (P → Q)(x 1 ,x 2,…,x n) = P(x 1,x 2,…,x n) → Q(x 1 ,x 2,…,x n) Predikaadid P ja Q, defineeritud kohta M nimetatakse ekvivalentseteks (kirjutage P=Q), kui P(x 1 ,x 2 ,…,xn)=Q(x 1 ,x 2 ,…,xn) mis tahes hulga (x 1 ,x 2 ,…, x n) korral )
aine muutujad M .
Teoreem 4.2.1 M-ga defineeritud n-arvuliste predikaatide hulk moodustab Boole'i predikaatalgebra. Seega kehtivad nende puhul põhiekvivalentsused (vt §1.6). Olgu P(x 1 ,x 2 ,…,xn) n-aarne predikaat, mis on defineeritud punktis M. Fikseerime x i = a. Defineerime (n-1)-aarse predikaadi Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) järgmiselt: Q(x 1 ,x 2 ,…,xk-1,xk +1, xn)=P(x1,x2,…,xk1, a,xk+1,xn). Nad ütlevad, et predikaat Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) saadakse predikaadist P(x 1 ,x 2 ,…,xn), fikseerides i-väärtuse. th muutuja: x i = a
. Definitsioon
4.3.1
. Olgu P(x) unaarpredikaat. Seostagem sellega lause tähisega "xP(x) (loe "iga x P(x) jaoks"), mis on tõene siis ja ainult siis, kui P(x) on identselt tõene predikaat. Väide "xP(x) öeldakse olevat , et see saadakse predikaadist P, lisades muutujale x universaalse kvantori. Definitsioon 4.3.2. Olgu P(x) unaarpredikaat. Seostagem see lausega $xP(x) (loe “on x P(x)”), mis on väär siis ja ainult siis, kui P(x) on identselt vale predikaat. Väide $xP(x) saadakse väidetavalt predikaadist P, ühendades muutujale x eksistentsiaalse kvantori. Märkus 1. Kvantorite sümbolid " ja $ on vastavalt ümberpööratud ladina tähed A ja E, mis on ingliskeelsete sõnade esimesed tähed Kõik- Kõik, Olemas- olemas. Märkus 2. Väiteid võib pidada predikaatideks, mis ei sisalda muutujaid, see tähendab 0-kohalisi predikaate (või mis tahes paikkonna predikaate). Olgu P(x 1 ,x 2 ,…,xn) n-aarne predikaat, mis on defineeritud punktis M. Fikseerime selles muutujate x 1 ,x 2 ,…,x k-1 ,x k väärtused +1,xn. Saadud unaarsele predikaadile Q(x k) ühendame universaalse (eksistentsi) kvantori ja saame väite. Seega seostatakse universaalsuse (olemasolu) kvantorit kasutava väitega muutujate fikseeritud väärtuste komplekt x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n. See (n-1)-aarne muutujate x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n predikaat on saadud algsest predikaadist P(x 1 ,x 2 ,…, x n) lisades k-ndasse muutujasse kvantori universaalsuse (olemasolu). Seda predikaati tähistatakse järgmiselt: "x kuni P(x 1 ,x 2 ,…,x n) ($x kuni P(x 1 ,x 2 ,…,x n)). K-nda muutuja kohta (mida enam ei eksisteeri) nad ütlevad, et see on seotud universaalsuse (eksistentsi) kvantoriga. Näide 4.3.1. Olgu D(x1,x2) = "Naturaalarv x1 jagub (ilma jäägita) naturaalarvuga x2." - kahekohaline predikaat. Määrakem selle muutujatele järjestikku kvantorid. Selge see 1) "x1"x2D(x1,x2)=0 2) "x2"x1D(x1,x2)=0 3) $x1 $x2D(x1,x2)=1 4) $x2$x1D(x1,x2)=1 5) "x1$x2D(x1,x2)=1 6) $x2"x1D(x1,x2)=1 7) $x1"x2D(x1,x2) =0 8) "x1$x2D(x1,x2)=1. Seega (võrreldes viimase näite 7 ja 8) tõestasime teoreemi: Tavaliselt järjestatakse konnektiivid ja kvantaatorid prioriteedi järgi järgmiselt: Ÿ, ", $, &, ¤, Ø, ~. Teoreem 4.3.1. Vastupidised kvantorid üldiselt ei pendelda. Teoreem 4.3.2.(kvantorit sisaldavad põhiekvivalentsid) Esinevad järgmised ekvivalentsused: 1. De Morgani seadused ∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x) 2. Kommutatiivsus ∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y) 3. Distributiivsus ∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x) 4. Kvantorite tegevuse piirangud ∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y) 5. Iga kahekohalise predikaadi jaoks ∃y∀xP(x,y) →∀x∃yP(x,y) =1 Formaalne teooria(või arvutus)
Y- See: 1. komplekt A
tegelaste kujunemine tähestik
;
1.
trobikond F
sõnad tähestikus A, F
à A
mida nimetatakse valemid
;
3. alamhulk B
valemid, B
à F
,
mida nimetatakse aksioomid; 4. palju suhteid R
nimega valemite komplektil järeldusreeglid. Palju sümboleid A
võib olla piiratud või lõpmatu. Tavaliselt kasutatakse sümbolite moodustamiseks lõplikku tähtede kogumit, millele vajadusel määratakse indeksiteks naturaalarvud. Palju valemeid F
tavaliselt antakse induktiivse definitsiooniga, näiteks formaalse grammatika abil. Reeglina on see komplekt lõpmatu. Komplektid A
Ja F
ühiselt kindlaks määrata keel
,
või allkiri
,
formaalne teooria. Paljud aksioomid B
võib olla lõplik või lõpmatu. Kui aksioomide hulk on lõpmatu, siis reeglina määratakse see lõpliku aksioomiskeemide komplekti ja reeglite abil konkreetsete aksioomide genereerimiseks aksioomiskeemist. Palju järeldusreegleid R
, reeglina muidugi. Niisiis, arvutus Y seal on neli (A, F, B, R)
. Tuletamise teel arvutuses Y on valemite F 1 ,F 2 ,…,Fn jada nii, et iga k (1§k§n) korral on valem Fk kas arvutuse Y aksioom või mis tahes eelneva järeldusreegliga saadud valemi otsene tagajärg . Valemit G nimetatakse arvutuse Y teoreemiks (tuletatav Y-s või tõestatav Y-s), kui on olemas järeldus F 1 ,F 2 ,…,F n ,G, mida nimetatakse valemi G tuletuseks või selle tõestuseks. teoreem G. See on kirjutatud järgmiselt: F 1,F 2,…,F n + G. Arvestus Y helistas järjekindel, kui kõik selle valemid pole tõestatavad. Järjepidevuse definitsiooni võib anda veel: Arvutust nimetatakse järjepidevaks, kui valemid F ja ŸF (F eitus) ei ole selles üheaegselt tuletatavad. Arvestus Y helistas täielik(või piisav), kui iga tõene väide M vastab teoreemile Y
. Formaalne teooria Y helistas otsustatav, kui on olemas algoritm, mis mis tahes teooria valemi puhul määrab, kas see valem on teoreem Y või mitte. Formaalarvutuse mõistet kasutades defineerime propositsiooniarvutuse (PS). Tähestik IW koosneb 1. kirju A, B, Q, R, P ja teised, võimalusel koos indeksitega (mida nimetatakse propositsioonimuutujateks), 2. loogilised sümbolid(sidemed) Ÿ, &, ¤, Ø, 3. abistav tegelased
(,). Palju valemeid IV määratakse induktiivselt: 1. kõik lausemuutujad on IV valemid; 2. kui A, B on valemid IV ,
toŸA, A⁄B, A¤B, AØB - valemidIV ;
3. avaldis on IV valem siis ja ainult siis, kui seda saab määrata punktide "1" ja abil Seega konstrueeritakse suvaline IV valem propositsioonimuutujatest, kasutades konnektiivisid Ÿ, ⁄, ¤, Ø. Edaspidi jätame valemite kirjutamisel mõned sulud välja, kasutades samu kokkuleppeid, mis eelmises peatükis. Aksioomid IV on järgmised valemid (mis tahes valemite A, B, C jaoks) 2. (AØB)Ø((AØ(BØC))Ø(AØC)); 5. (AØB)Ø((AØC)Ø(AØ(B⁄C))); 8. (AØC)Ø((BØC)Ø((A¤B)ØC)); 9. (AØB)Ø((AØŸB)ØŸA); Neid valemeid nimetatakse IV aksioomiskeemideks .
Konkreetsete valemite asendamisel mis tahes skeemiga saadakse aksioomiskeemi erijuhtum. Järelduste reegel IE-s kehtib järeldusreegel (modus ponens): kui A ja AØB on tuletatavad valemid, siis on tuletatav ka B Sümboolselt on see kirjutatud nii: A, A B →
B
. Näiteks kui väited A⁄B ja A⁄BØ(AØC) on tuletatavad, siis on ka väide AØC tuletatav järeldamisreegli järgi. Valem G on tuletatav valemitest F 1 ,F 2 ,…,F n (tähistatud F 1 ,F 2 ,…,F n +G), kui on olemas valemite jada F 1 ,F 2,… ,F k ,G , milles mis tahes valem on kas aksioom või kuulub valemite F 1,F 2,...,F n loendisse (nimetatakse hüpoteesideks) või saadakse eelmistest valemitest vastavalt reeglile järeldus. Valemi G tuletatavus "(tähistatud +G-ga) on samaväärne tõsiasjaga, et G on IV teoreem. Näide 5.2.1. Näitame, et valem AØA on tuletatav IV. Selleks koostame selle valemi tuletise: 1) aksioomis 2 asendage B AØA-ga, C asendage A-ga. Saame aksioomi (AØ(AØA))Ø((AØ((AØA)ØA))Ø(AØA)); 2) aksioomis 1 asendame B A-ga. Saame AØ(AØA); 3) 1-st ja 2-st vastavalt modus ponens'ile järeldame (AØ((AØA)ØA))Ø(AØA); 4) aksioomis 1 asendame B AØA-ga. Saame AØ((AØA)ØA); 5) lõigetest. 3 ja 4 on järeldamisreegli kohaselt + AØA tõene. Teoreem 5.2.1. 1. Kui F 1 ,F 2 ,…,Fn,A,B on IV valemid, Г=(F 1 ,F 2 ,…,Fn), Г+A, siis Г,B+A. (saate hüpoteeside arvu suurendada). 2. Kas ja ainult siis, kui F 1 ,F 2 ,…,F n +A, kui F 1 ⁄F 2 ⁄…⁄F n +A (paljude hüpoteeside taandamine üheks hüpoteesiks). Teoreem 5.3.1. (deduktsiooni teoreem) Kui Г,B+A, siis Г+BØA, kus Г on teatud valemite hulk Г=(F 1 ,F 2 ,…,F n ). Järeldus 5.3.1. Siis ja ainult siis, kui F 1 ,F 2 ,…,F n +A, millal Tõestus. Olgu F 1 ,F 2 ,…,F n +A. Seejärel saame deduktsiooniteoreemi rakendades F 1 ,F 2 ,…,F n-1 +F n ØA. Samamoodi F 1 ,F 2 ,…,F n-2 +F n 1Ø(F n ØA) jne. Jätkates protsessi vajalik arv kordi, saame F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…) Piisavuse tõestamiseks eeldame, et +B, kus B=F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Kasutame teoreemi 5.2.1 punkti 1: F1 +B .
Järeldusreegli järgi saame F 1 + (F 2 Ø…Ø(F n-1 Ø(F n ØA))…), Siis on n sammu järel F 1 ,F 2 ,…,F n +A . Seega, tänu järeldusele 5.3.1., taandub valemi A tuletatavuse kontrollimine valemitest F 1,F 2,…,F n valemi tõestatavuse kontrollimiseks. F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Tuletame meelde, et valemit A nimetatakse identselt tõeseks (või tautoloogiaks), kui valemi A väärtus on võrdne ühega propositsioonimuutujate mis tahes väärtuste komplekti korral. Järgnev teoreem taandab valemi tõestatavuse kontrolli selle identse tõesuse kontrollimisele. Teoreem 5.3.2. (täielikkuse kohta). Valem A on tõestatav siis ja ainult siis, kui A on identselt tõene (tautoloogia): +A ‹ A-tautoloogia. Seega, et teha kindlaks, kas valem on tõestatav, piisab selle tõesuse tabeli koostamisest. Teatavasti on tõetabeli koostamiseks tõhus algoritm ja seetõttu IV lahendatav. Näide 5.3.1. Tõestame, et P+P. Deduktsiooni teoreemi järgi on see võrdne +(PØP). Täielikkuse teoreemi järgi omakorda piisab tõestamisest, et (РØР) on tautoloogia. Valemi (РØР) tõesuse tabeli koostamine ,
Oleme veendunud, et (РØР) on identselt tõsi ja seega tõestatav. Teoreem 5.3.3. (järjepidevuse kohta). IW arvutus on järjepidev. Tõestus. Täielikkuse teoreemi kohaselt ei ole ükski valem, mis ei ole identselt tõene, IW-s tõestatav. Näiteks on selline valem valem A⁄(ŸA). Valemite hulka Г nimetatakse vastuoluline
,
kui Г+А⁄(ŸА) .
Kui Г on vastuoluline valemite hulk, tähistame seda fakti Г+-ga. avaldus
5.3.1.
Valem A on tuletatav valemite hulgast Г siis ja ainult siis, kui hulk Г»(ŸA) on vastuoluline. Automaatne teoreemide tõestamine on loogilise programmeerimise, tehisintellekti ja teiste programmeerimise kaasaegsete suundade nurgakivi. Üldiselt ei pruugi olla algoritmi, mille abil saaks suvalise valemi A abil pärast lõplikku arvu samme kindlaks teha, kas A on arvutuses Y tuletatav või mitte. Mõne lihtsa formaalse teooria (näiteks lausearvutus) ja mõne lihtsa valemiklassi (näiteks ühe unaarse predikaadiga rakendatud predikaatarvutus) jaoks on aga teoreemide automaatse tõestamise algoritmid teada. Allpool toome lausearvutuse näitel välja lahutusmeetodi põhitõed - klassikaline ja samas populaarne teoreemide automaatse tõestamise meetod. Tuletame meelde, et kui x on loogiline muutuja ja σœ(0,1), siis avaldis x σ = xx kui σσ == 10 või x σ = 10 kui x x =≠σσ , nimetatakse kiri. Nimetatakse tähti x ja Ÿx vastandlik.
Konjunkt nimetatakse tähtede sidesõnaks. disjunktne nimetatakse tähtede disjunktsiooniks. Olgu D 1 = B 1 ∨ A, D 2 = B 2 ∨ A kõrvallaused. Lause B 1 ¤B 2 nimetatakse otsustav klauslid D 1 ja D 2 tähega A ning tähistatakse res A (D 1 ,D 2). Lausete D 1 ja D 2 lahusti on mõne tähega lahusti ja seda tähistatakse res(D 1 ,D 2). Ilmselgelt res(A,ŸA)=0. Tõepoolest, sest A=A¤0 ja ŸA=ŸA¤0, siis res(A,ŸA)=0¤0=0. Kui klauslid D 1 ja D 2 ei sisalda vastandlikke märke, siis pole neil lahusteid. Näide 5.5.1. Kui D 1 =A¤B¤C, D 2 = A ∨ B ∨ Q, siis res A (D 1 ,D 2)=B¤C¤ B ¤Q, res B (D 1 ,D 2)=A¤C¤A¤Q, resC(D 1 ,D 2) ei eksisteeri. avaldus 5.5.1. Kui res(D 1 ,D 2) on olemas, siis D 1 ,D 2 + res(D 1 ,D 2). Olgu S=(D 1 ,D 2 ,…,Dn) kõrvallausete hulk. Valemite F 1 ,F 2 ,…,F n jada nimetatakse S resoluutseks tuletamiseks, kui iga valemi F k puhul on täidetud üks järgmistest tingimustest: 2. on j, k
Teoreem 5.5.1.
(lahutusmeetodi täielikkuse kohta). Klauslite hulk S on vastuoluline siis ja ainult siis, kui S-st on tehtud resolutiivne järeldus, mis lõpeb numbriga 0. Pange tähele, et lahutusmeetodit saab kasutada valemi F tuletatavuse kontrollimiseks antud valemite hulgast F 1,F 2,…,F n. Tõepoolest, tingimus F 1 ,F 2 ,…,F n +F on samaväärne tingimusega F 1 ,F 2 ,…,F n ,ŸF+ (paljud valemid on vastuolulised), mis omakorda on samaväärne tingimusega Q+, kus Q=F 1 ⁄F 2 ⁄…⁄F n ⁄(ŸF). Vähendame valemi Q väärtuseks CNF: Q=D 1 ⁄D 2 ⁄...⁄Dm, siis Q+ ‹D 1 ⁄D 2 ⁄...⁄Dm+ ‹ D 1 ,D 2 ,...,D m + . Seega taandub F 1 ,F 2 ,...,F n +F tuletatavuse kontrollimise ülesanne punktide hulga S=(D 1 ,D 2 ,...,D m ) mittevastavuse kontrollimisele. , mis on samaväärne S-i määratud järelduse 0 olemasoluga. Näide 5.5.2. Kontrollige eraldusvõime meetodit kasutades suhet AØ(BØC), CDØE, ŸFØD&(Ÿ)E + AØ(BØF). Vastavalt avaldusele 5.3.1. vaja kontrollida paljude valemite vastuolu S = (AØ(BØC), CDØE, ŸFØD&(Ÿ)E, Ÿ(AØ(BØF))). Esitame kõik valemid alates. S KNF-ile: S = (A ∨ B ∨ C, C ⋅ D ∨ E, F ∨ D ⋅ E, A ∨ B ∨ F) == (A ∨ B ∨ C, C ∨ D ∨ E, (F ∨ D) ⋅ (F) ∨ E), A ⋅ B ⋅ F) . Seega saame osade hulga S = (A ∨ B ∨ C, C ∨ D ∨ E,F ∨ D,F ∨ E,A,B, F) Teeme 0-ga lõppevast S-st resoluutse järelduse: 1. res A (A ∨ B ∨ C,A) = B ∨ C ; 2. res B (B ∨ C,B) = C ; 3. res D (C ∨ D ∨ E,F ∨ D) = C ∨ E ∨ F ; 4. res E (C ∨ E ∨ F, F ∨ E) = C ∨ F ; 5. res C (C, C ∨ F) = F ; 6. res(F, F) = 0 . Seega järeldame, et valem AØ(BØF) on tuletatav valemite hulgast AØ(BØC), CDØE, ŸFØD&(Ÿ)E. Pange tähele, et lahutusmeetodist piisab, et avastada antud klauslikomplekti S võimalikku rahuldatavust. Selleks kaasame hulka S kõik S-st lahutavate mahaarvamiste teel saadud klauslid. Lahutusmeetodi täielikkuse teoreemist see järgneb Järeldus 5.5.1. Kui klauslite hulk S sisaldab kõigi selle elementide lahusteid, siis S on rahuldav siis ja ainult siis, kui 0–S. Modernsuse iseloomulikuks jooneks on arvutite laialdane kasutamine probleemide (ülesannete) lahendamisel erinevates inimtegevuse valdkondades. Probleem tuleb aga esmalt lahendada algoritmiliselt, s.t. tuleb anda formaalne ettekirjutus, mida järgides saab lõpptulemuse kõikide teatud tüüpi ülesannete lahendamiseks (see on intuitiivne, mitte range algoritmi kontseptsioon). Näiteks kahe naturaalarvu suurima ühisjagaja leidmise algoritm a, b, järgnevalt: 1) laiendage numbrit a põhitegurite järgi; 2) korrake sammu 1 jaoks b
Ja minge 3. sammu juurde; 3) koostada laiendustest ühiste algtegurite korrutis A Ja b indeksitega, mis on võrdsed laiendustesse kaasamise indeksitest väikseima. Pärast selle näite analüüsimist märgime algoritmi kõige olulisemad omadused (omadused): 1.
Massi iseloom- algoritmi rakendatavus mitte ühele probleemile, vaid probleemide klassile. 2.
Diskreetsus- algoritmi selge jaotus üksikuteks etappideks (sammudeks). 3.
Determinism- selline täitmisetappide korraldus, kus on alati selge, kuidas ühest etapist teise üle minna. 4.
Jäseme- konkreetse probleemi lahendamiseks algoritmi rakendamisel tulemuse saamiseks viiakse läbi algoritmi piiratud sammude jada: Pange tähele, et kui algoritmi olemasolu iseenesest toimib tõestuseks algoritmi olemasolust, siis selle puudumise tõestamiseks on vaja algoritmi ranget matemaatilist määratlust. Algoritmi kontseptsiooni vormistamise katsed viisid selle loomiseni Turingi masinad, kui mingi kujuteldav seade, mis algoritmi rakendab. Teine samm algoritmi mõiste määratlemisel oli välimus rekursiivsed funktsioonid ,
kui funktsioonid, mis formaliseerivad algoritmi mõiste ja rakendavad intuitiivset arvutatavuse kontseptsiooni. Peagi avastati, et rekursiivsete funktsioonide hulk langeb kokku Turingi masinatel arvutatavate funktsioonide hulgaga. Seejärel ilmunud uued mõisted, mis väitsid, et nad seletavad algoritmi mõistet, osutusid samaväärseteks Turingi masinatel arvutatavate funktsioonidega ja seega ka rekursiivsete funktsioonidega. Käimasoleva arutelu selle üle, mis on algoritm, tulemuseks oli väide, mida nüüd nimetatakse Churchi teesiks. Kiriku tees. Algoritmi mõiste ehk arvutatavus mõne mehaanilise seadme poolt langeb kokku Turingi masinate arvutatavuse mõistega (ja seega ka rekursiivse funktsiooni mõistega). Teisisõnu, algoritm on protsess, mida saab esitada funktsionaalse diagrammiga ja realiseerida mõne Turingi masinaga. Turingi masin on (abstraktne) seade, mis koosneb lindist, juhtseadmest ja lugemispeast. Lint on jagatud rakkudeks. Igas lahtris on täpselt üks märk väline tähestik
A=(
a 0,
a 1,…,
a n). Mõni sümbol (tähistame seda Ÿ
) tähestikku A nimetatakse tühjaks ja iga lahtrit, mis sisaldab praegu tühja tähemärki, nimetatakse tühjaks lahtriks (sel hetkel). Eeldatakse, et lint on mõlemas suunas potentsiaalselt piiramatu. Juhtseade igal ajahetkel on mingis hulka kuuluvas olekus q j Q=(q 0, q 1,..., q m)(m=l). Hulk Q kutsutakse sisemine tähestik
.
Üks neist tingimustest (tavaliselt q 0) nimetatakse lõplikuks ja mõnda muud (tavaliselt q 1) - algustäht. Lugemispea liigub mööda linti nii, et igal ajahetkel skaneerib see täpselt ühe lindi lahtri. Pea saab lugeda vaadeldava lahtri sisu ja kirjutada sellesse vaadeldava sümboli asemel mõne uue sümboli välisest tähestikust A(võib-olla sama). Töötamise ajal muudab juhtseade olenevalt olekust, milles see asub ja pea poolt vaadatavast sümbolist, oma sisemist olekut q. Seejärel annab see peale käsu trükkida jälgitavasse lahtrisse välisest tähestikust teatud märk A, ja seejärel käsib pead kas paigal püsima või ühe lahtri paremale liigutama või ühe lahtri vasakule. Kui masin on lõppseisundis, lakkab töötamast. Konfiguratsioon lindil (või masinasõnal) nimetatakse hulgaks, mille moodustavad: 1) järjestus a
mina (1)
,a
mina (2)
,...,a
on) tähemärgid välisest tähestikust A, salvestatud lindirakkudesse, kus a
i
(1)
.- vasakpoolsesse esimesse lahtrisse kirjutatud sümbol jne. (mis tahes sellist järjestust nimetatakse Ühesõnaga), 2) sisemälu olek q r ; 3) number k tajutav rakk. Kirjutame masina konfiguratsiooni järgmiselt: a ,a ,..., a a i(r) a ,a ,..., a i(1) i(2) i(r−1) q r i(r+1) i(r+2) i(s) Siin r- tajutav lahter tõstetakse esile murdosana. Kui masin, olles sisemises olekus q i, aktsepteerib sümboliga lahtrit a u, kirjutab sellele lahtrile järgmisel ajahetkel sümboli a r, läheb sisemisse olekusse qs ja liigub mööda linti, siis öeldakse, et masin täidab käsku q i a u
Æ
q s a r S, kus sümbol S võib võtta ühe järgmistest väärtustest: -1 – nihutada pead vasakule; +1 - pea nihe paremale; 0 – pea jääb paigale. Kutsutakse välja kõigi Turingi masina töö määravate käskude (kvintide) loend programm see auto. Masina programm on sageli täpsustatud tabeli kujul. Nii et ülalkirjeldatud olukorra jaoks ristmikul tabelis read a
u ja veerg q i jääb seisma q s a r S(vt tabel 6.2.1) Tabel 6.2.1. Kui programmis on autod paarile (
q i ,a u
)
viis puudu, siis joone ristumiskohas tabelis a u ja veerg q i lisatakse kriips. Niisiis, Turingi masin on definitsiooni järgi, komplekt M=(A,Q,P), Kus A- väline tähestik, K- siseolekute tähestik, P- programm. Kui masin, olles alustanud tööd mõne lindile kirjutatud sõnaga P, jõuab lõppolekusse, siis kutsutakse seda selle sõna kohta kohaldatav. Selle töö tulemuseks on lindile salvestatud sõna lõppseisundis. Vastasel juhul öeldakse, et masin ei ole sõna R puhul rakendatav. Näide 6.2.1. Ehitame Turingi masina, mis liidab naturaalarvud, mis on kirjutatud unaararvude süsteemis (see tähendab, et need on kirjutatud ühe sümboliga |.
Näiteks 5=|||||.). Lahendus. Mõelge tähestikule A
= {|, +, ⁄}. Masin määratakse järgmise programmiga: Kirjutame algussõnale üles konfiguratsioonid, mis tekivad järjestikku selle masina töötamise ajal ||+ ||| , st. 2+3. Siin kasutame konfiguratsiooni salvestamisel järgmist kokkulepet: masina asukoha olek kirjutatakse vaadeldava tähe taha paremale sulgudesse. Näide 6.2.2. Ehitage Turingi masin, mis kahekordistab unaararvude süsteemis kirjutatud naturaalarvusid. Lahendus. Ehitame vajaliku masina tähestikus A=(|, α, ⁄). Sellise masina programm võib välja näha järgmine: Rakendame saadud masina sõnale ||
. Uue tähe α kasutuselevõtt ja esialgsete asendamine |
α-l võimaldab originaali eristada |
ja uus (määratud) |
. osariik q 1 pakub asendust |
kohta α ,
olek q 2 pakub α otsingut ,
mõeldud asendamiseks |
ja masina peatamine juhul, kui α-d ei tuvastata, q 3 tagab valmimise |
juhul, kui α asendati |.
Leppigem selles lõigus sellega kokku 1. naturaalarvude hulk N sisaldab 0 (null), s.o. N=(0,1,2,3,...); 2. vaadeldavad funktsioonid f=f(x 1 ,x 2 ,…,x n) on defineeritud ainult siis, kui muutujad võtavad väärtused N-st, st. xiœN; 3. funktsioonide väärtuste vahemik DŒN; 4. vaadeldavad funktsioonid f=f(x 1 ,x 2 ,…,x n) on osaliselt defineeritavad, s.t. pole määratletud kõigi naturaalarvude komplektide jaoks. Tutvustame arvesse lihtsad funktsioonid o(x)=0, s(x)=x+1,
I m n (x 1,..., x n)
=
x m Neid funktsioone saab arvutada sobiva mehaanilise seadme (näiteks Turingi masina) abil. Määratleme operaatorid, mis konstrueerivad ühe või mitme antud funktsiooni põhjal uusi funktsioone. Superpositsiooni operaator. Olgu k muutuja funktsioon f(x 1 ,x 2 ,…,x k) ja k funktsiooni f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n) antud n muutujat. Funktsioonide f,f 1 ,…,f k superpositsioon on funktsioon j(x 1 ,x 2 ,…,x n)= f(f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1) ,x 2,…,x n)) Ütleme, et funktsioon j saadakse superpositsioonioperaatori S k+1 rakendamisel funktsioonidele f,f 1 ,…,f k ja kirjutades j=S k+1 (f,f 1 ,…,f k) Näiteks S 2 (s, o)=s(o(x)), st. funktsioon, mis on identselt võrdne 1-ga ja S 2(s,s)=s(s(x)) on funktsioon y(x)=x+2. Primitiivne rekursioonioperaator. Olgu antud funktsioonid g(x 1 ,x 2 ,…,x n) ja h(x 1 ,x 2 ,…,x n+2). Koostame funktsiooni f(x 1 ,x 2 ,…,x n+1) Olgu väärtused x 1 ,x 2 ,…,x n fikseeritud. Siis eeldame: f(x 1 ,x 2 ,…,x n ,0)= g(x 1 ,x 2 ,…,x n) f 1 (x 1 ,x 2 ,…,xn,y+1)= h(x1,x2,…,xn,y, f(x1,x2,…,xn,y)) Need võrdsused defineerivad funktsiooni f(x 1 ,x 2 ,…,x n+1) üheselt. Funktsiooni f nimetatakse funktsiooniks, mis saadakse primitiivse rekursioonioperaatori R abil. Kasutatakse tähistust f=R(g,h). Funktsiooni induktiivne määratlus (mis on näidatud primitiivse rekursioonioperaatoris) pole matemaatikas haruldane. Näiteks 1) naturaalse astendajaga aste määratakse induktiivselt: a
0
=1, a n+ 1
=a n
ÿ a
; 2) faktoriaal: 0!=1, (n+1)!= n!ÿ(n+1) jne. Definitsioon. Funktsioonid, mida on võimalik saada kõige lihtsamast o(x)=0, s(x)=x+1, I m n (x 1 ,..., x n) = x m, rakendades superpositsioonitehteid ja primitiivset rekursiooni lõplik arv kordi kutsutakse primitiivselt rekursiivne. Kontrollime, kas funktsioon u(x,y)=x+y on primitiivne rekursiivne. Tõepoolest, meil on: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. See on primitiivne rekursiooniskeem, kuna x= I 1 1 (x) ja u(x,y)+1=s(u(x,y))=S 2 (s,u). Siin g(x)= I 1 1 (x) ja h(x,y,u)=s(u)=S 2 (s, I 3 3). Samamoodi on tõestatud, et funktsioonid m(x,y)=xÿy, d(x,y)=x y (eeldame definitsiooni järgi 0 0 =1), fakt(x)=x! ja paljud teised on primitiivselt rekursiivsed. Märge; et primitiivselt rekursiivsed funktsioonid on kõikjal määratletud (st defineeritud nende argumentide kõigi väärtuste jaoks). Tõepoolest, kõige lihtsamad funktsioonid o, s, I m n on kõikjal defineeritud ning superpositsiooni ja primitiivsete rekursioonioperaatorite rakendamine kõikjal määratletud funktsioonidele annab ka kõikjal määratletud funktsioone. Nii et selline funktsioon nagu = x − y, kui x ≥ y< y f(x,y) ei eksisteeri, kui x ei saa olla primitiivselt rekursiivne. Meil ei ole siin õigust arvestada funktsiooni f(x,y)=x-y, kuna funktsiooni väärtused peavad olema naturaalarvud (seetõttu mitte negatiivsed). Siiski võib kaaluda funktsiooni ÷ y = 0x − y, kui x x<≥y.y Kontrollime, kas see on primitiivselt rekursiivne. Esmalt tõestame, et funktsioon j(x)=xπ1 on primitiivne rekursiivne. Tõepoolest, j(0) = 0. j(y+1)=(y+1)π1=y, mis toimib funktsiooni xπ1 primitiivse rekursiooniskeemina. Lõpuks, xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) on xπy primitiivne rekursiooniskeem. Primitiivsetest rekursiivsetest funktsioonidest oluliselt laiem funktsioonide klass on rekursiivsete funktsioonide klass (vt definitsiooni allpool). Kirjanduses nimetatakse neid funktsioone ka osaliselt rekursiivne .
Nende määramiseks tutvustame veel ühte operaatorit. Minimeerimise operaator. Olgu antud funktsioon f(x 1 ,x 2 ,… ,x n ,x n+1). Fikseerime mõned esimese n muutuja väärtused x 1 ,x 2 ,… ,x n ja arvutame f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1 ), f(x 1 ,x 2 ,… ,x n ,2) jne. Kui y on väikseim naturaalarv, mille puhul f(x 1 ,x 2 ,… Xn,y)=x n+1 (st väärtused f(x1,x2,…,xn,0), f(x1,x2,…,xn,1),…,f(x) 1, x 2,… X n ,y-1) on kõik olemas ja ei ole võrdsed xn +1-ga), siis paneme g(x 1 ,x 2 ,… Xn,xn+1)=y. Seega g(x1,x2,…,xn,xn+1)=min(y|f(x1,x2,…,xn,y)=x n+1). Kui selline y ei, siis arvestame, et f(x 1 ,x 2 ,… ,x n ,x n+1) ei ole defineeritud. Seega on võimalikud kolm juhtumit: 1. f(x1,x2,…,xn,0), f(x1,x2,…,xn,1),…,f(x1,x2,…,xn,y-1) on olemas ja ei ole võrdsed xn +1 ja f(x 1 ,x 2 ,…,x n ,y)=x n+1 ; 2. f(x1,x2,…,xn,0), f(x1,x2,…,xn,1),…,f(x1,x2,…,xn,y-1) eksisteerivad ja ei ole võrdsed xn +1-ga, kuid f(x 1 ,x 2 ,…,x n ,y) ei eksisteeri; 3. f(x 1 ,x 2 ,… ,x n ,i) eksisteerivad kõigi iœN jaoks ja erinevad xn +1-st. Kui esineb 1. juhtum, siis g(x 1 ,x 2 ,… ,x n ,x n+1)=y ja kui 2. või 3. juhtum, siis g(x 1 ,x 2 ,… ,x n , x n +1) pole määratletud. Sel viisil saadud funktsioon g on saadud f-st, kasutades minimeerimisoperaatorit M. Kirjutame g = Mf. Minimeerimisoperaator on pöördfunktsiooni operaatori ilmne üldistus. Üldistus on üsna sügav, kuna funktsioon f ei pea olema üks-ühele (muutujas x n+1) Definitsioon. Funktsioonid, mida saab tuletada kõige lihtsamatest o(x)=0, s(x)=x+1,
I m n (x 1,..., x n)
= x m superpositsioonitehtete, primitiivse rekursiooni ja minimeerimisoperaatorite rakendamine piiratud arv kordi nimetatakse korduv. Rekursiivsete funktsioonide klass on laiem kui primitiivsete rekursiivsete funktsioonide klass, kasvõi sellepärast, et see ei sisalda ainult kõikjal määratletud funktsioone. Tõestame näiteks, et funktsioon = x − y, kui x ≥ y< y f(x,y) ei eksisteeri, kui x on rekursiivne. Tõepoolest, f(x,y)=min(z| y+z=x) ja varem tehti kindlaks, et funktsioon u(x,y)=x+y on primitiivselt rekursiivne. Rekursiivsed funktsioonid peegeldavad meie intuitiivset arusaama funktsioonidest, mida mõni mehaaniline seade suudab arvutada. Eelkõige on need Turingi masinatel arvutatavad (vt eelmist lõiku). Vastupidi, iga Turingi masinal arvutatav funktsioon on rekursiivne. Me ei hakka seda fakti kontrollima, kuna see võtaks liiga palju aega ja ruumi. Täieliku tõestuse võib leida näiteks A. I. Maltsevi raamatust “Algoritmid ja rekursiivsed funktsioonid”. Pange tähele, et mitte iga loomulike argumentide funktsioon ei ole rekursiivne, isegi mitte iga üksiku argumendi funktsioon. Mitterekursiivsete funktsioonide olemasolu on algoritmiliselt lahendamatute probleemide esinemise "matemaatiline põhjus". Matemaatika erinevates harudes esineb algoritmiliselt lahendamatuid ülesandeid, s.t. probleeme, millele lahendusalgoritmi pole ja mitte sellepärast, et seda pole veel leiutatud, vaid sellepärast, et see on põhimõtteliselt võimatu. Loomulikult tuleb algoritmi mõista Turingi masinate ja rekursiivsete funktsioonide tähenduses. Sõnastame ühe neist probleemidest Turingi masina seiskamise probleem. Turingi masin on objekt, mis on määratletud piiratud arvu parameetritega. Kõik osalised vastendused ühest lõplikust hulgast teise saab tõhusalt ümber nummerdada. Seetõttu saab igale Turingi masinale määrata numbri (naturaalarvu). Olgu T(n) Turingi masin arvuga n. Mõned masinad, mis hakkavad tühjal lindil sõitma, peatuvad lõpuks ja mõned töötavad lõputult. Tekib probleem: naturaalarvu n andmisel tehke kindlaks, kas tühjale lindile käivitatud Turingi masin T(n) peatub või mitte. See ülesanne algoritmiliselt otsustamatu. See tähendab, et automaatset protseduuri pole ,
iga n puhul otsustab, kas masin T(n) peatub või mitte. See ei välista meil konkreetse masina puhul kindlaks teha, kas see seiskub või mitte. Ei ole ühtegi meetodit, mis lahendaks selle kõigi masinate jaoks korraga .
Kuidas leida probleemi lahendamiseks tõhus algoritm? Ja kui algoritm leitakse, siis kuidas saab seda võrrelda teiste sama probleemi lahendavate algoritmidega? Kuidas hinnata selle kvaliteeti? Sedalaadi küsimused pakuvad huvi nii programmeerijatele kui ka andmetöötluse teoreetilise õppega seotud isikutele. Algoritmide hindamiseks on palju kriteeriume. Kõige sagedamini huvitab meid sisendandmete suurenedes probleemi lahendamiseks vajaliku aja ja mälumahu kasvu järjekord. Soovime iga konkreetse ülesandega seostada numbri, mida nimetatakse selle suuruseks ,
mis väljendaks sisendandmete hulga mõõtu. Näiteks maatriksi korrutamise probleemi suurus võib olla tegurimaatriksite suurim suurus. Algoritmile kuluvat aega funktsioonina probleemi suurusest nimetatakse aja keerukus see algoritm. Nimetatakse selle keerukuse käitumist piiris probleemi suuruse suurenemisel asümptootiline aja keerukus
.
Samamoodi saame määratleda mahtuvuslik keerukus ja asümptootiline mahtuvuslik keerukus. Algoritmi asümptootiline keerukus määrab lõpuks selle algoritmiga lahendatavate probleemide suuruse. Kui algoritm töötleb n suurusega sisendeid ajas cÿn 2 , kus c -
mingi konstant, siis nad ütlevad, et selle algoritmi ajaline keerukus on O(n 2) (loe “järgus en square”). Võib arvata, et praeguse digitaalse põlvkonna kaasa toonud tohutu arvutuskiiruse kasv arvutid, vähendab tõhusate algoritmide tähtsust. Juhtub aga vastupidi. Kuna arvutusmasinad lähevad järjest kiiremaks ja saame lahendada suuremaid probleeme, määrab just algoritmi keerukus masina kiiruse kasvades saavutatava probleemi suuruse suurenemise. Oletame, et meil on viis algoritmi A1,A2,…,A5 järgmiste ajaliste keerukusega: Siin on ajaline keerukus ajaühikute arv, mis on vajalik n suuruse sisendi töötlemiseks. Olgu ajaühikuks üks millisekund (1sek=1000 millisekundit). Siis suudab algoritm A1 töödelda 1000 suurust sisendit ühe sekundiga, A5 aga mitte suuremat kui 9 suurust sisendit. Tabelis. 6.5.1. Antakse nende ülesannete suurused, mida saab lahendada ühe sekundi, ühe minuti ja ühe tunni jooksul nende viie algoritmi abil. Tabel 6.5.3. Oletame, et järgmise põlvkonna arvutid on 10 korda kiiremad kui praegune. Tabelis 6.5.2. näitab, kuidas suureneb probleemide maht, mida saame selle kiiruse suurenemise tõttu lahendada. Pange tähele, et algoritmi A5 puhul suurendab kümnekordne kiiruse suurendamine lahendatava ülesande suurust vaid kolme ühiku võrra (vt tabeli 6.5.2 viimast rida), algoritmi A3 puhul aga ülesande suurust rohkem kui kolmekordseks. . Tabel 6.5.4. Kiiruse suurendamise efekti asemel vaatleme nüüd tõhusama algoritmi kasutamise mõju. Pöördume tagasi tabeli 6.5.1 juurde. Kui võtta võrdluse aluseks 1 minut, siis asendades algoritmi A4 algoritmiga A3, saame lahendada 6 korda suurema ülesande ja asendades A4 A2-ga. ,
saate lahendada 125 korda suurema ülesande. Need tulemused on palju muljetavaldavamad kui 10-kordse kiirusega saavutatud 2-kordne paranemine. Kui võtta võrdluse aluseks 1 tund, osutub erinevus veelgi olulisemaks. Sellest järeldame, et algoritmi asümptootiline keerukus on oluline algoritmi kvaliteedi näitaja ja meede, mis tõotab muutuda veelgi olulisemaks koos järgneva arvutuskiiruse suurenemisega. Vaatamata sellele, et siin on põhitähelepanu pööratud koguste kasvujärjekorrale, tuleb mõista, et algoritmi keerukuse suurel kasvujärjekorral võib olla väiksem korduvkonstant (konstant c O(f(x))) definitsioonis, kui mõne teise algoritmi keerukuse suurenemise väike järk. Sel juhul võib väikeste probleemide puhul eelistada kiiresti kasvava keerukusega algoritmi – võib-olla isegi kõigi meid huvitavate probleemide puhul. Oletame näiteks, et algoritmide A1, A2, A3, A4, A5 ajaline keerukus on tegelikult vastavalt 1000n, 100nÿlog(n), 10n2, n3 ja 2. n Siis on A5 parim 2§n§9, A2 - suurusega ülesannete jaoks 10§n§58, A1 - at 59§n§1024 ja A1- mille n>1024.- 1. F.A. Novikov. Diskreetne matemaatika programmeerijatele./ St. Petersburg: Peter, 2001, 304С. 2. S.V. Sudoplatov, E.V. Ovtšinnikova. Diskreetse matemaatika elemendid./ M., INFRA-M, Novosibirsk, NSTU kirjastus, 3. Y.M.Erusalimsky. Diskreetne matemaatika / M., “Ülikooliraamat”, 2001, 279 lk. 4. A. Aho, J. Hopcroft, J. Ullman. Arvutusalgoritmide konstrueerimine ja analüüs. / M., Mir, 1979, 536С. 5. V.N.Nefedov, V.A.Osipova Diskreetse matemaatika kursus./ M., MAI kirjastus, 1992, 264P.§4.3. Kvantorid ja nende omadused.
V peatükk. Formaalsed teooriad.
§5.1. Formaalse teooria definitsioon.
§5.2. Lausearvutus.
§5.3. Deduktsiooni teoreem. IV täielikkus.
§5.4. Teoreemide automaatne tõestamine.
§5.5. Lahutusmeetod IW-s.
VI peatükk. Algoritmide teooria elemendid.
§6.1. Algoritmi määratlus.
§6.2. Turingi masin.
q 0
…
q i
…
q m
…
a u
q
s
a
rS
…
§6.3. Rekursiivsed funktsioonid
§6.4. Algoritmiliselt lahendamatud probleemid.
§6.5. Algoritmid ja nende keerukus.
KIRJANDUS.