Saada oma head tööd teadmistebaasi on lihtne. Kasutage allolevat vormi

Hea töö saidile">

Üliõpilased, magistrandid, noored teadlased, kes kasutavad teadmistebaasi oma õpingutes ja töös, on teile väga tänulikud.

Teosest pole veel HTML-versiooni.
Teoste arhiivi saate alla laadida klikkides alloleval lingil.

Sarnased dokumendid

Matemaatilise loogika põhimääratlused, Boole'i ​​ja samaväärsed funktsioonid. Üldmõisted Boole'i ​​algebra. Zhegalkini algebra: väited ja predikaadid. Definitsioon formaalne teooria. Algoritmide teooria elemendid, rekursiivsed funktsioonid, Turingi masin.

loengute kursus, lisatud 08.08.2011


Põhilised mõtlemise vormid: mõisted, hinnangud, järeldused. George Boole'i ​​essee, mis uuris üksikasjalikult loogilist algebrat. Väite tõeväärtus (st tõde või vale). Loogilised operatsioonid inversioon (eitus) ja konjunktsioon.

esitlus, lisatud 14.12.2016


Hulkade ja nendega tehtavate operatsioonide graafiline tõlgendamine. Matemaatiline loogika, Boole'i ​​algebra. Täiuslik konjunktiivne normaalvorm. Ekvivalentvalemid ja nende tõestus. Süsteemi täielikkus Boole'i ​​funktsioonid. Predikaatloogika, graafiteooria.

loeng, lisatud 12.01.2009


Boole'i ​​algebra tekkimise ajalugu, lausearvutuse süsteemi areng. Meetodid kompleksi tõe või vääruse tuvastamiseks loogilisi väiteid kasutades algebralised meetodid. Disjunktsioon, konjunktsioon ja eitus, tõetabelid.

esitlus, lisatud 22.02.2014


Ruutmaatriksid ja määrajad. Koordinaatide lineaarruum. Süsteemiuuringud lineaarvõrrandid. Maatriksite algebra: nende liitmine ja korrutamine. Geomeetriline pilt kompleksarvud ja neid trigonomeetriline vorm. Laplace'i teoreem ja alus.

koolitusjuhend, lisatud 03.02.2009


Positiivsete (looduslike) arvude teooria põhikontseptsioon. Aritmeetiliste tehete kiirkirja arendamine. Jagatavuse sümbolkeel. Võrdluste omadused ja algebra. Võimude võrdluse tõstmine. Ümber ruudustamist. Fermat' väike teoreem.

esitlus, lisatud 06.04.2014


Süsteemid digitaalne töötlemine teavet. Boole algebra mõiste. Loogikatete tähistused: disjunktsioon, konjunktsioon, inversioon, implikatsioon, ekvivalentsus. Boole algebra seadused ja identiteedid. Loogilised põhitõed ARVUTI. Struktuurivalemite teisendamine.

esitlus, lisatud 11.10.2014

nime saanud Volžski ülikool. Tatištševa.

Loengud edasi matemaatiline loogika ja algoritmide teooria.

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 binaarset laiendust (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 tuleb leida hulk, millel f saab väärtuse 1. 1 on 7. kohal ja numeratsioon leksikograafilises järjekorras algab 0-st, siis on vaja leida 6 kahendlaiend. Seega saab 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 rakendamine seda funktsiooni.

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 asendame näiteks x 3 ∆x 4, siis saame uus funktsioon neljast muutujast: (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.

Kompaktsemaks salvestuseks keerukad funktsioonid tutvustame järgmisi konventsioone : 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 asetatakse sulud järgmisel viisil: ((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 , V 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 assotsiatiivsuse omadus 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 digivormis arvuti arvud on 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. klass lineaarsed funktsioonid, st. 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. Klass monotoonsed funktsioonid. 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 . Nad ütlevad, et see on funktsionaalne täielik süsteem S Moodustavad Boole'i ​​funktsioonid 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 ehitada aluseid elementaarfunktsioonidest vastavalt järgmine reegel. Valides suvalise Boole'i ​​elementaarfunktsiooni ja täiendades seda vajadusel teiste funktsioonidega, nii et need kõik koos rahuldaksid funktsionaalse täielikkuse teoreemi. 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 realiseeriva valemi kirjutamiseks antud funktsioon.

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 disjunkt 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) tabelis sisalduvad vastavad konkreetsele nullide ja ühtede komplektile, mis 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 see valem Esmalt taandame DNF-ile.

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 arvutamisel pole mitte ainult teoreetiline, vaid ka suur praktiline tähtsus. Näiteks paljudes kaasaegsed programmid graafilise liidesega komplekside koostamiseks loogilisi tingimusi kasutatakse tabelikujulist visuaalset vormi: lahtritesse kirjutatakse tingimused ja ühe veeru lahtrid loetakse ühendatuks konjunktsiooniga ja veerge disjunktsiooniga ühendatuks, st 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 2 n 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 seda funktsiooni esindav ja omav DNF väikseim number muutujate esinemised.

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 y-tähe kõrvale jättes saame implikandi 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õesuse tabelit. Kui eemaldame vähendatud DNF-ist kõik mittevajalikud implicandid, saame DNF-i nimega ummiktee.

Pange tähele, et funktsiooni esitus tupik-DNF-ina üldine juhtum 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 (by graafiline esitus vertikaalselt eraldatud või horisontaaljoon võttes arvesse vastupidiste äärmuslike rakkude 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. Iga rühm peaks sisaldama maksimaalne arv rakud, 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. meetod ebakindlad koefitsiendid. 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õrrandi süsteemi 2 n tundmatuga, ainus otsus. 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 teha üsna lihtsalt. Selle puuduseks Boole'i ​​algebraga võrreldes on valemite kohmakus.

IV peatükk. avaldused. Predikaadid.

§4.1. avaldused.

Loogika algebra koostamisel kasutasime funktsionaalne lähenemine. 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 helistame deklaratiivne lause mille kohta saab üheselt öelda, kas see on teatud 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 oleme tegemas üleminekut uus tase abstraktsioonid, seda tüüpi üleminek, 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). Kohapealne predikaat n (n-kohaline predikaat) on defineeritud ainevaldkond 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).

§4.3. Kvantorid ja nende omadused.

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

V peatükk. Formaalsed teooriad.

§5.1. Formaalse teooria definitsioon.

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 lõplik 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.

§5.2. Lausearvutus.

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).

§5.3. Deduktsiooni teoreem. IV täielikkus.

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.

§5.4. Teoreemide automaatne tõestamine.

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.

§5.5. Lahutusmeetod IW-s.

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. disjunkt 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.

VI peatükk. Algoritmide teooria elemendid.

§6.1. Algoritmi määratlus.

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.

§6.2. Turingi masin.

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 määratud 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.

q 0	…	q i	…	q m
…
a u	q s a rS
…

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. Konstrueerime 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 |.

§6.3. Rekursiivsed funktsioonid

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".

§6.4. Algoritmiliselt lahendamatud probleemid.

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 .

§6.5. Algoritmid ja nende keerukus.

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õiks arvata, et praeguse põlvkonna digitaalarvutusmasinate tohutu arvutuskiiruse kasv 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 asjaolule, 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 kordamiskonstant (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.-

KIRJANDUS.

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.

Matemaatiline loogika ja algoritmide teooria – Loengute kursus
Sissejuhatus.

1. 
   Eesmärk.

See kursus aitab arendada teadmisi ja oskusi, mis moodustavad arvutiteaduse valdkonna probleemide püstitamiseks ja lahendamiseks vajaliku teoreetilise aluse, et õigesti mõista arvutusstruktuuride, algoritmide ja infotöötlusprogrammide loomisel tekkivaid piiranguid.

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 selleks loogiliste ahelate minimeerimine, mis on tänapäeval kaotanud oma tähtsuse.

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. Vaid 10 aastat tagasi olid kõik tehnilised ajakirjad täis artikleid 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, on leidnud praktilist rakendust tänapäevases tehnoloogias. 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. Infosüsteemide projekteerimise ja analüüsi praktilised probleemid on lähtepunktiks ning formaalne aparaat on vahend nende probleemide süstemaatiliseks lahendamiseks. 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. Selle kursuse omandamiseks peab üliõpilane 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;

Tuvastada loomulikus keeles evidentsiaalses arutluses loogiline struktuur, konstrueerida 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. Loogikas on õiged arutlusmeetodid 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 on sõnastatud väidete vormis. 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. Ožegovi S.I. selgitavas sõnastikus. Ö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.

Matemaatilisest loogikast sai matemaatika haru, mis alguses tundus väga abstraktne ja praktilistest rakendustest lõpmatult kaugel. 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 digitaalsete seadmete projekteerimisel. 1950. aastal. Matemaatilise loogika roll kaasaegse mikroprotsessortehnoloogia arendamisel on äärmiselt oluline: seda kasutatakse arvutiriistvara projekteerimisel, kõigi programmeerimiskeelte arendamisel ja diskreetsete automaatikaseadmete projekteerimisel.

Suure panuse matemaatilise loogika arendamisse andsid erinevate riikide teadlased: Kaasani ülikooli professor Poretsky P.S., de-Morgan, Peirce, Turing, Kolmogorov A.N., Heidel K. jt.

1.4 Enesekontrolli küsimused.

1. Sõnasta kursuse eesmärgid

Matemaatiline loogika ja algoritmide teooria

Lektor: A. L. Semenov

1. loeng

Sissejuhatus 1

Matemaatilise loogika ja algoritmide teooria probleem 1

Matemaatilise loogika ja algoritmide teooria matemaatilised tulemused 2

Kaasaegne tsivilisatsioon ja MLiTA 2 roll

Matemaatika konstrueerimine. Hulgateooria 5

Programm matemaatilised uuringud matemaatiline tegevus- Gilberti 9

Üldine idee 9

Hilberti programmi tulemused 12

Hulgateooria keel ja aksioomid. I. Näited 12

Loogilised sümbolid ja nende tähendus (semantika) 12

Näiteid hulkade olemasolu aksioomidest 13

Sissejuhatus

Matemaatilise loogika ja algoritmide teooria probleem

Matemaatilise loogika ja algoritmide teooria abil lahendatud ülesanne on luua matemaatiliste definitsioonide ja teoreemide süsteem, mis võimaldab matemaatiliselt kirjeldada ja uurida järgmisi inimtegevuse liike:

• 
  Teoreemide tõestamine ja matemaatiliste mõistete määratlemine
• 
  Matemaatiliste objektide vaheliste seoste kirjeldus
• 
  Eksperimentaalselt kindlaks tehtud väidete, hüpoteeside jms tagajärgede saamine.
• 
  Määratud omaduste ja funktsioonidega seadmete (mehaanilised, elektroonilised jne) projekteerimine.
• 
  Formaalsete juhiste loomine ja rakendamine (algoritmide ja programmide kirjeldus ja rakendamine)
• 
  Nõutava tulemuse kirjelduse ja selle tulemuse saavutamiseks loodud algoritmi vahelise vastavuse loomine (õigsuse tõend)

Matemaatiline loogika ja algoritmide teooria annavad loetletud tegevustele (matemaatilised, täpsed) korrektsuse kriteeriumid.

Matemaatilise loogika ja algoritmide teooria matemaatilised tulemused

Selle uuringu läbiviimisega saame tulemusi, mis on seotud:

1. 
   Hulgad ja seosed, mida saab konkreetses keeles kirjeldada
2. 
   Tõestatavate valemite komplektid
3. 
   Tõeliste valemite komplektid (üksiga 2 on põhimõtteline erinevus)
4. 
   Matemaatiliste struktuuride hulgad, milles antud hulga valemid on tõesed
5. 
   Funktsioonide klassid, mis arvutatakse algoritmide abil
6. 
   Algoritmi olemasolu, mis määrab valemite tõesuse või tõestatavuse
7. 
   Arvutuslik keerukus
8. 
   Objektide keerukus

jne.

Kaasaegne tsivilisatsioon ja MLiTA roll

Märkimisväärne edasiminek inimkonna arengus on seotud masinate loomisega materiaalsete objektide töötlemiseks, energia vastuvõtmiseks ja edastamiseks (kasutavad need masinad), transpordivahendite, valgustuse jms loomisega.

Sajandeid on inimestel olnud idee luua masinaid, mis töötaksid mitte aine ja energiaga, vaid infoobjektidega. Pealegi loodi ja isegi töötasid edukalt sellised masinad, näiteks masin, mis võimaldab sooritada aritmeetilisi tehteid – liitmismasin (B. Pascal).

20. sajandi esimesel poolel kirjeldati üldistavalt, milliseid võimalikke meetodeid teabe formaalseks töötlemiseks inimeste poolt. 20. sajandi keskpaigaks avastati füüsikalised põhimõtted, mis võimaldasid luua seadmeid, mis suudavad salvestada palju informatsiooni ja seda väga kiiresti töödelda. Loodi universaalsed seadmed – arvutid, mis suudavad teha kõike, mida inimene formaalselt suudab, aga palju kiiremini kui inimene.

Väga üldistavalt võib öelda, et matemaatiline loogika loob aluse teoreetilisele matemaatikale ja algoritmide teooria arvutuspraktikale (arvutite kasutamisele). Täpsem uurimine näitab aga, et paljud matemaatilise loogika saavutused on leidnud rakendust infotehnoloogiate arendamisel ja rakendamisel ning algoritmilised kaalutlused on olulised ka puhta matemaatika erinevates osades.

Ajaloo verstapostid

Olulised hetked kaasaegsete ideede väljatöötamisel selle kohta, mis on matemaatilised tõendid ja arvutused, olid saksa matemaatikute saavutused. XIX lõpus- 20. sajandi algus

Eriti oluline oli David Hilberti (23.01.1862 – 14.01.1943) kõne II rahvusvahelisel matemaatikute kongressil (Pariis, 1900). Seal sõnastas ta 23 nn. Hilberti ülesanded olid tolleaegse matemaatika ja 20. sajandi matemaatika arengu jaoks kõige olulisemad. Mõned Hilberti probleemid olid konkreetse matemaatilise väite tõesuse kindlakstegemise küsimus, teisi võiks nimetada pigem ettepanekuks mingisuguse uurimisprogrammi läbiviimiseks.

Hilberti loendi ülesanded I, II, X on seotud matemaatilise loogika ja algoritmide teooriaga.

Aastatuhande seitsmest matemaatilisest ülesandest esimene puudutab samuti meie ainet (see ei kuulunud Hilberti ülesannete hulka).

Kursusel käsitletakse ülalmainitud probleeme matemaatilise loogika ja algoritmide teooria vallas ning tänapäevast vaadet neile.

Organisatsioonilised märkused

Kursuse autorid usuvad, et parim viis matemaatika õppimiseks ja matemaatikuks saamiseks on ise matemaatikaga tegelemine. Matemaatikute all mõistame siinkohal kõiki, kelle professionaalse tegevuse (ja paljude jaoks kogu elu) oluliseks osaks on matemaatiliste tegevusmeetodite abil matemaatiliste objektidega töötamine. Nii on üles ehitatud märkimisväärne osa tegevusest näiteks infotehnoloogia vallas. “Matemaatika tegemise” all peame silmas ülesannete lahendamist ja ennekõike mitte neid, mida kõige sagedamini lahendatakse koolis või ülikooli esimesel kursusel matemaatilise analüüsi käigus. Peame silmas ülesandeid, mille puhul on vaja midagi uut välja mõelda. Muidugi peaksid paljud neist ülesannetest uue matemaatikavaldkonna valdamisel olema lihtsad ja ammu lahendatud, kuid need ei erine põhimõtteliselt probleemidest, mida professionaalne matemaatik ja programmeerija peab lahendama.

Seda tüüpi probleeme, millest praegu räägime, sõnastatakse nii loengutes kui ka kursuse harjutustes. Kõik sõnastatud ülesanded ei ole täiesti lihtsad. Veelgi enam: osa neist on matemaatikas üsna hiljuti lahendatud, on neid, mis on veel lahendamata, ja teised, millel pole üldse lahendust (aga mida on kasulik lahendada).

Soovitame teil kogu kursuse jooksul tegeleda probleemide lahendamisega ja arutada neid oma juhendajaga (ja loomulikult ka omavahel). See:

• 
  Aitab paremini mõista loengute sisu ja kogu matemaatikavaldkonda, millega kursus on seotud
• 
  Parem on eksamiks valmistuda ja see osaliselt “sooritada” (kursuse käigus tekkinud probleemide lahendamine “arvestatakse” sulle eksamil, sellest räägivad Su õpetajad lähemalt)
• 
  Proovige ennast paljutõotavas matemaatika valdkonnas ja võib-olla valige see ülikoolis oma erialaks, mis võib olla kasulik teie töös pärast ülikooli.

Teine koht, kus probleeme lahendatakse ja nende lahendusi arutatakse, on noorematele õpilastele mõeldud matemaatilise loogika ja arvutiteaduse proseminar. Seal pakutakse teile koos lihtsate ülesannetega, mis võimaldavad teil mõista asja olemust, kohe pakkuda nii keerulisi kui ka lahendamata ülesandeid.

Järgmise loengu materjalid pannakse üles internetti kodulehele http://lpcs.math.msu.su/vml2013/

Lisaks neile saab kursuse sisuga tutvuda raamatutest:

• 
  N.K. Vereshchagin, A. Shen, Loengud matemaatilisest loogikast ja algoritmide teooriast, toim. MCCME (mccme.ru)
• 
  I. A. Lavrov, L. L. Maksimova, Ülesanded hulgateoorias, matemaatilises loogikas ja algoritmide teoorias,

mis on saadaval ka Internetis.

Lõpuks viimane asi. Matemaatilise loogika ja algoritmide teooria üheks rakendatavaks tulemuseks on matemaatilise tegevuse erinevate komponentide automatiseerimine. Eelkõige saab automatiseerida teatud tüüpi matemaatiliste tõendite kontrollimist. Sellise automatiseerimise valdkond laieneb loomulikult pidevalt tänu automatiseerimisalgoritmide endi arengule, matemaatikute paremale arusaamisele nende algoritmide rakendamisest, kogemuste kogunemisest ja arvutusvõimekuse kasvust. Tänapäeval on kõige populaarsem ja tõhusam arvutusraamistik tõendite kontrollimise automatiseerimiseks Coq. Meie osakond viib läbi Coqi teemalise töötoa, kus saab õppida seda keskkonda kasutama, ette kujutada selle võimalusi ja piiranguid.

Matemaatika konstrueerimine. Hulgateooria

Kaasaegne matemaatika struktuur, eriti selle õpetamise viis ülikoolides, põhineb hulgateoorial. Nüüd tuletame meelde selle teooria mõningaid põhikontseptsioone.

Komplektide määratlemiseks kasutatakse sageli lokkis trakse. Nende sisse saab paigutada kõik antud hulga elemendid: (2, 14, 5.4) või kirjeldada seda erilisel viisil: (x|x on reaalarv ja sin(x)>0).

Kasutame hulgaoperatsioonide jaoks järgmist tähistust: elemendi kuuluvus hulka ∊, hulkade kaasamine ⊂, liit ∪, ristmik ∩, erinevus \.

Olgu meil kaks objekti x,y. Tellitud paar x; y> nimetatakse objektiks, millest unikaalselt taastatud x, y, teisisõnu: x; y> = x′; y′> → ( x = x′ y = y′).

Töö x X y kaks komplekti x Ja y on kõigi järjestatud paaride kogum u; v>, kus u ∊ x Ja v ∊ y.

Samamoodi tellitud n-ki objektid ja n aste x n komplektid x. Sellega võib kokku leppida x 1 on x.

Hulkadevaheline seos x, y nimetatakse nende toote mis tahes alamhulka x X y.

n-kohalik suhe võtteplatsil x kutsutakse mis tahes alamhulka n-selle komplekti aste.

Suhtumine f vahel x Ja y nimetatakse funktsiooniks x V y, kui seose mis tahes kahe elemendi esimeste komponentide kokkulangevusest f järgneb viimaste kokkulangevus.

Funktsiooni domeen on selle esimeste komponentide kogum.

Kui funktsiooni domeen on pärit x V y langeb kokku x, siis öeldakse, et funktsioon kuvab x V y ja kirjutada f : x → y. Kuvatakse palju kõiki funktsioone x V y, tähistatud y x .

Funktsioon f : x → y nimetatakse bijektsiooniks vahel x Ja y, või bijektsioon alates x V y või isomorfism x Ja y, kui elementide teiste komponentide kokkulangemisest f sellest järeldub, et esimesed elemendid langevad kokku ja lisaks ka teised elemendid f moodustavad kogu komplekti y. Isomorfseid hulki nimetatakse ka ekvivalentseteks hulkadeks.

Hulka nimetatakse loendatavaks, kui see on samaväärne loomuliku jadaga.

Ülesanne. Tõesta, et naturaalrea iga alamhulk on võrdne kas selle alglõiguga (mis on sama, mis mõned selle elemendid) või kogu naturaaljadaga.

Sõnastatud viimases ülesandes põhiline tähelepanek–, et osa võib olla terviku suhtes isomorfne, tundub teise kursuse üliõpilastele ilmselt triviaalne. Kuid see oli üks esimesi hulgateooria avastusi.

Lõplikke hulki saab võrrelda suuruse järgi. Kui üks on isomorfne teise alamhulgaga, on sellel vähem elemente. Millal lõpmatu hulk see on vale. Seda olukorda kirjeldas Galileo Galilei järgmises dialoogis, mida me esitame lühendiga:

Vestlused Jamatemaatilisedtõend, kahe uue kohtateadusharud,seotud TomehaanikaJakohalik liikumine

signora Galileo Galilei Lyncheo, filosoof ja esimene matemaatik Tema rahulik Kõrgus Toscana suurhertsog

Salviati. ...kõikide arvude – ruutude ja mitteruutude – arv kokku on suurem kui ruutude arv eraldi; pole see?

Simplicio. Ma ei saa sellele vastu vaielda.

Salviati. Ruute on sama palju kui juuri, kuna igal ruudul on oma juur ja igal juurel oma ruut; ühelgi ruudul ei saa olla rohkem kui üks juur ja ühelgi juurel ei saa olla rohkem kui üks ruut.

Sagredo. Mida tuleb teha, et sellest olukorrast väljapääs leida?

Salviati. Ma ei näe võimalust muuks lahenduseks kui tunnistada, et võrdsuse omadusi, nagu ka suuremat ja väiksemat suurusjärku, ei eksisteeri seal, kus on tegemist lõpmatusega, ja need on rakendatavad ainult lõplike suuruste puhul. Seega, kui Signor Simplicio pakub mulle ebavõrdseid ridu ja küsib, kuidas on võimalik, et suurem neist ei sisalda rohkem punkte kui vähemal, siis vastan talle, et neid pole rohkem, mitte vähem ja mitte sama palju, vaid igas lõpmatu arv.

Kuid isegi lõpmatute hulkade hulgas on teatud järjekord, nagu näitab järgmine teoreem, mille Cantor on samuti ilma tõestuseta teatanud ja mida peagi tõestasid ka teised saksa matemaatikud.

Cantori-Bernsteini teoreem. Olgu komplektide vahel bijektsioon A ja komplekti alamhulk B, samuti bijektsioon komplekti vahel B ja komplekti alamhulk A. Siis komplektid A Ja B- võimsuselt võrdne.

Ülesanne. Tõesta Cantori-Bernsteini teoreem.

Ülesanne. Kas on võimalik võrrelda mingeid komplekte kardinaalsuse poolest, st kas vastab tõele, et mis tahes A Ja B, või A võrdselt võimas alamhulk B, või B võrdselt võimas alamhulk A?

Funktsioonide hulgast tõstame esile omadused– funktsioonid, mis võtavad ainult väärtused 0 ja 1. Iga omadus määrab seose – elementide hulga, mille väärtus on 1. Iga funktsioon f : x → B kutsutakse iseloomulik(peal x). Pange tähele, et meie tähistustes ja kokkuleppes B=(0,1)=2. Seega on kõigi iseloomulike funktsioonide kogum sisse lülitatud x saab tähise B x või 2 x .

Ülesanne. Konstrueerige isomorfism karakteristlike funktsioonide hulga vahel x ja paljud komplekti alamhulgad x.

Ülesanne. Tõesta, et ühegi hulga alamhulkade hulk ei ole sellega isomorfne.

Lahendusidee [Cantor Diagonal]. Olgu isomorfism G : x → 2 x on olemas. Vaatleme iga elemendi puhul y meie paljudest x selle vastav alamhulk G(y). Kas me saame elementidest x koguda alamhulk C, mis erineks komplektist G(y) "elemendil y» ? Või mis on sama asi, kuidas konstrueerida üks iseloomulik funktsioon f C , mis erineks komplekti iseloomulikust funktsioonist G (y) "punktis y» igal juhul y?

Kui x on naturaalarvude hulk, siis saab tõestus selgeks graafiline vorm. Helistame numbrile y, mis läheb iseloomulikku funktsiooni f, funktsiooni number f.

Argument Funktsioon nr.	0	1	2	3	4	…
0	1	0	0	1	0
1	1	1	0	1	0
2	1	0	0	1	1
3	0	0	0	1	0
4	0	1	0	1	0

………

Selles tabelis numbriga real n tühjendatud iseloomulik funktsioon numbriga n. Tabelis ei ole funktsiooni, mis saadakse selle diagonaalist, muutes 1 väärtuseks 0 ja 0 väärtuseks 1 (eitamistehing).

Ülesanne. Tõesta, et reaalarvude hulk on võrdne naturaalrea alamhulkade hulgaga.

Matemaatilise tegevuse uurimisprogramm – Hilbert

Üldine idee

David Hilbert omab ideed matemaatikast kui matemaatiliselt kirjeldatud tegevusvaldkonnast, teadlikkust matemaatilise tegevuse uurimise tähtsusest, kasutades matemaatika enda vahendeid, ja sellise uurimistöö programmi - Hilberti programmi - esitlust.

Hilberti matemaatikaõppe programme saab esitada järgmiselt:

• 
  Matemaatikat saab kujutada süsteemina
  • 
    aksioomid – väited, mida aktsepteerime tõestena ja
  • 
    tõendamise reeglid – uute väidete saamine.
• 
  Matemaatilise tegevuse praktika peaks meid veenma, et valitud süsteem võimaldab konstrueerida kõik vajalikud tõendid. Ideaalis võib juhtuda, et iga matemaatilist väidet saab selle süsteemi abil tõestada või ümber lükata. (Seda omadust nimetatakse täielikkus.)
• 
  Mõned matemaatilised tõendid on "eriti jõulised ja veenvad". Nende hulka kuuluvad näiteks aritmeetilised arvutused. Ainult neid kasutades saate veenduda, et matemaatika jaoks valitud süsteem ei võimalda teil saada vastuolusid. (Seda omadust nimetatakse järjepidevus.) Pealegi võib selguda, et matemaatika täielikkust saab tõestada ka lihtsa, arusaadava ja veenva põhjendusega.

Täielikkuse omaduse kasulikkus on selge. Reeglina otsime matemaatilist väidet tõestades samal ajal selle ümberlükkamist. Tahaks olla kindel, et selline tegevus viib lõpuks tulemusteni ja see on “ainult” meie võimete ja aja küsimus. Hilbert uskus: "See on usk iga lahendatavusse matemaatiline probleem on meile suureks abiks meie töös; kuuleme enda sees pidevat üleskutset: siin on probleem, otsi lahendust. Saate selle leida puhta mõtlemise kaudu; sest matemaatikas pole Ignorabimust!

Pange tähele, et järjepidevuse omadus on palju olulisem. A priori võiks ette kujutada teaduslik teooria, milles vastuolu asub kusagil perifeerias ja on seotud mõne ebaolulise probleemiga. Kuid kõigi suuremate süsteemide disain matemaatiline tõestus on selline, et ühe vastuolu tõestatavus (näiteks asjaolu, et mõne kahe korrutis on väga suured numbrid võrdne mõne kolmanda ja teise neljandaga) viib kohe iga matemaatilise väite tõestatavuseni. Vastuolu ei saa "lokaliseerida".

Esimesed sammud Hilberti programmi eesmärkide saavutamiseks tehti juba enne selle sõnastamist. Pealegi järgnes programm neist loogiliselt. Need on sammud.

Tõestus. Loogika. 19. sajandi lõpus sai selgeks, kuidas arutlussüsteemi vormistada. See vormistamine viidi lõpule Gottlob Frege (8.11.1848 - 26.07.1925) töödes.

Hulgateooria. Teine matemaatika saavutus 19. sajandi lõpul oli arusaam, et kogu matemaatikat saab esitada ühtselt hulkadena (nagu tänapäevases matemaatika kursused ja meenutasime eespool). Seda tehti Georg Cantori (3.03.1845 - 6.01.1918) töödes.

Seega ei jäänud muud üle kui valida sobiv süsteem aksioomid ja jätkake järjepidevuse ja täielikkuse tõestamise teed. Lootus selliseid tõendeid lihtsate ja usaldusväärsete vahenditega hankida seostus järgmisega. Aksioomide ja tõestusreeglite kasutamine näeb üsna välja lihtne protsess valemitega töötamine. Valemid ise on lihtsad objektid, sümbolite ahelad. Matemaatika tundub mänguna, nagu näiteks male. Oletame, et peame tõestama, et mõni positsioon males on võimatu. Põhimõtteliselt - seda saab muidugi kõiksugu läbi käies malemängud. Kuid võite ette kujutada rohkem lihtne arutluskäik, mis põhineb näiteks sellel, et väljale ei lisata tükke, et piiskopid on heledad ja tumedad ruudud jne. Sellises arutluskäigus ei kasutata suure tõenäosusega reaalarve, integraale ja veelgi keerulisemaid matemaatilisi objekte.

Süsteem aksioomid hulgateooria jaoks ehitati peamiselt 20. sajandi esimestel kümnenditel, esimene tänapäevasele lähedane formuleering kuulus Ernst Zermelole (27.7.1871 ‒ 21.5.1953) ja ilmus tema sulest 1908. aastal.

Hilberti programmi tulemused

Mis Hilberti programmiga hiljem juhtus? Sõnastame selle nüüd lühidalt ja järgmisel kursusel selgitame seda lähemalt.

Ühest küljest viidi programm edukalt ellu:

• 
  Aksiomaatiline hulgateooria on aluseks kaasaegne matemaatika.
• 
  Eelkõige moodustati kolmekümnendatel aastatel rühm matemaatikuid kollektiivse pseudonüümi N. Bourbaki all. Maksimaalselt sellest loominguline tegevus toimus 1950. ja 60. aastatel. See rühm esitles järjekindlalt ja süstemaatiliselt olulist osa kaasaegsest matemaatikast, mis on üles ehitatud hulgateooria alusel.

Samal ajal ebaõnnestus programm põhimõtteliselt:

• 
  Matemaatika ei ole täielik ega saa olla täielik.
• 
  Matemaatika järjepidevust ei saa kindlaks teha mitte ainult mõne usaldusväärse veenva vahendiga.

Selle asutas Kurt Gödel (28.04.1906 – 14.01.1978) 1930. aastatel.

Hulgateooria keel ja aksioomid.I. Näited

Matemaatika (hulgateooria) tõestussüsteemi formuleerimist alustame loogilise keele kirjeldusega.

Loogilised sümbolid ja nende tähendus (semantika)

Tõeväärtused: sümbolid I (tõene), L (väär) või sümbolid 1, 0. Kahe sümboli 0 ja 1 komplekti tähistame B-ga.

Loogilised operatsioonid:(mitte, eitus), (ja, konjunktsioon), (või, disjunktsioon), → (järgneb, implikatsioon), ≡ (ekvivalentsus) rakendatakse sümbolitele 1 (I) ja 0 (A) ning nende rakendamise tulemus on kirjeldatud järgmises tabelis:

A	B	A	AB	AB	A → B	A ≡ B
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

Kvantorid, millega olete ka muidugi tuttav - x (olemas x ), y (kellegi jaoks y )

Näiteid hulkade olemasolu aksioomidest

Hulgateooria mitmed aksioomid on väited hulkade olemasolu kohta, kaasa arvatud need, mis on moodustatud teistest hulkadest.

Hulgadest rääkimiseks, eelkõige nendega seotud aksioomide sõnastamiseks, on vaja loogiliste sümbolite hulka lisada hulgateooriaga seotud sümbolid. Kuidas kirjutada mida x – tühi komplekt, st komplekt, millel pole elemente? Näiteks nii:

y (­ y ∊ x ) (igaühele ­ y see pole tõsi y kuulub x )

Vajasime liikmesümbolit ∊. Lisame selle meie keele tähestikusse.

Et meil oleks millestki rääkida, oleks hea vähemalt ühe komplekti olemasolus kindel olla. Alustame tühjast (Ø):

x y (­ y ∊ x ) [Tühja hulga aksioom.]

Tahame defineerida mõned konkreetsed hulgad, hulkade omadused jne. Soovime tutvustada nende jaoks tähistusi.

• 
  Tühja hulka loeme nulliks.
• 
  Kuidas saada järgmine number numbrist n? Lisage kõigile elementidele n ikka lihtsalt n. See tähendab, et kaalume järgmise elemente n nummerdab kõik elemendid alates n ja edasi n. Kõik saadud elemendid moodustavad komplekti N:
  • 
    1 on (0)
  • 
    2 on (0,1) = (0, (0))

Ülesanne. Mitu elementi on arvus (hulgas) 5? Ja seda külluses n?

Sel viisil konstrueeritud loomuliku jada olemasolu tagab järgmine aksioom. Arusaadavuse hõlbustamiseks jagasime selle osadeks ja kommenteerisime seda (in nurksulud) need osad:

s (u (u ∊ s v (v ∊ u )) [nagusvõite võtta loomuliku seeriaN; see sisaldabu - null]

u (u ∊ s → [ Sest igasuguseid asju u alates s ]

v (v ∊ s [tuleb olemav alatess , ]

w (w ∊ v ≡ (w ∊ u w = u ))))) [kõrvalu ] [ Lõpmatuse aksioom ]
Kuid seda aksioomi saab rahuldada mitte ainult looduslikud seeriad, vaid ka muud komplektid

Ülesanne. Milline näiteks?

Ülesanne. Kuidas saame täpselt kirjeldada looduslikke seeriaid, mille oleme konstrueerinud?

IN matemaatilised konstruktsioonid kasutatakse tehteid komplektidega. Juba alustatud teed mööda tuleb lisada aksioomid, mis garanteerivad nende toimingute tulemuste olemasolu. Siin on veel üks näide:

usv(w(w ∊ v →w ∊ u) ≡ v ∊ s) [Kraadi aksioom]

Ülesanne. Kontrollige, kas viimane valem tähendab tähenduslikult mis tahes antud hulga kõigi alamhulkade hulga olemasolu.

Muidugi vajame näiteks komplekti, mis on kahe andme ristumiskoht jne.

Eespool hakkasime järk-järgult komplekte ehitama. Selge on, kuidas seda teed jätkata, näiteks konstrueerida täisarvude hulk, seejärel ratsionaalarvud, täisarvupaaride kogumina, millel on mingi ekvivalentsusseos, seejärel reaalarvude hulk jne.