Teorema apsorpcije pisano u dva oblika - disjunktivnom i

konjunktiv, odnosno:

A + AB \u003d A (16)

A(A + B)=A (17)

Dokažimo prvu teoremu. Izvadimo slovo A iz zagrada:

ALI + AB \u003d A (1 + B)

Prema teoremi (3) 1 + B = 1, dakle

A(1 + B) = A 1 = A

Da bismo dokazali drugu teoremu, širimo zagrade:

A(A + B) = A A + AB = A + AB

Rezultat je izraz koji je upravo dokazan.

Razmotrimo nekoliko primjera primjene teoreme apsorpcije za

pojednostavljenje Bulovih formula.

Teorema lepljenja također ima dva oblika - disjunktivni i

konjunktiva:

Dokažimo prvu teoremu:

budući da prema teoremama (5) i (4)

Da bismo dokazali drugu teoremu, otvaramo zagrade:

Prema teoremi (6), dakle:

Prema teoremi apsorpcije (16) A + AB \u003d A

Teorema apsorpcije, kao i teorema lijepljenja, primjenjuje se prilikom pojednostavljivanja

booleove formule, na primjer:

De Morganova teorema povezuje sve tri osnovne operacije booleove algebre

Disjunkcija, konjunkcija i inverzija:

Prva teorema glasi kako slijedi: inverzija konjunkcije je disjunkcija

inverzije. Drugo, inverzija disjunkcije je konjunkcija inverzija. Morganove teoreme možete dokazati koristeći tablice istinitosti za lijevu i desnu stranu.

De Morganova teorema se također primjenjuje na više varijable:

Predavanje 5

Invert složeni izrazi

De Morganova teorema se ne primjenjuje samo na pojedinačne konjunkcije

ili disjunkcija, ali i na složenije izraze.

Nađimo inverzni izraz AB + CD , predstavljeno kao disjunkcija veznika. Inverzija će se smatrati završenom ako su negativni predznaci samo iznad varijabli. Hajde da uvedemo notaciju: AB = X;

CD=Y onda

Pronađite i zamijenite u izraz (22):

Na ovaj način:

Razmotrimo izraz predstavljen u konjunktivnom obliku:

(A + B) (C + D)

Nađimo njegovu inverziju u obliku

Hajde da uvedemo notaciju: A + B = X; C + D \u003d Y, onda

Pronađite i zamijenite ih u izraz

Na ovaj način:

Prilikom invertiranja složenih izraza, možete koristiti sljedeće pravilo. Da biste pronašli inverziju, potrebno je zamijeniti znakove konjunkcije znakovima disjunkcije, a znakove disjunkcije znakovima konjunkcije, te staviti inverzije preko svake varijable:

Koncept Booleove funkcije

AT u opštem slučaju, funkcija (lat. functio - izvedba, usklađenost,

preslikavanje) je određeno pravilo (zakon), prema kojem svaki element skupa x, što je raspon nezavisne varijable X, određeni element skupa je dodijeljen F,

što se podrazumijeva kao raspon vrijednosti zavisne varijable f . U slučaju logičkih funkcija X=F = (0,1). Pravilo kojim je funkcija specificirana može biti bilo koja Booleova formula, na primjer:

Simbol f ovdje je funkcija koja je, poput argumenata A, B, C, binarna varijabla.

Argumenti su nezavisne varijable, mogu uzeti bilo koju vrijednost - 0 ili 1. Funkcija f - zavisna varijabla. Njegovo značenje je u potpunosti određeno vrijednostima varijabli i logičkim vezama između njih.

glavna karakteristika funkcija: da bi se odredila njena vrijednost, općenito, potrebno je znati vrijednosti svih argumenata o kojima ona ovisi. Na primjer, gornja funkcija ovisi o tri argumenta A, V, S. Ako uzmemo A = 1, onda dobijamo

tj. dobije se novi izraz, koji nije jednak ni nuli ni

jedinica. Pusti sada AT= 1. Onda

tj. u ovom slučaju nije poznato da li je funkcija jednaka nuli ili jedinici.

Konačno, uzmimo OD= 0. Tada dobijamo: f = 0. Dakle, ako uzmemo A = 1 u originalnom izrazu, AT= 1, OD = 0, tada će funkcija uzeti nultu vrijednost: f= 0.

Razmislite pojam skupa varijabilnih vrijednosti .

Ako se svim argumentima o kojima funkcija ovisi dodijele određene vrijednosti, onda se govori o skupu vrijednosti argumenata koji se mogu

nazovi to samo set. Skup vrijednosti argumenata je niz nula i jedinica, na primjer, 110, gdje prva znamenka odgovara prvom argumentu, druga drugom, a treća trećem. Očigledno, potrebno je unaprijed dogovoriti šta je prvi, drugi ili recimo peti argument. Da biste to učinili, prikladno je koristiti abecedni raspored slova.

Na primjer, ako

onda je prema latinici prvi argument R, sekunda -

Q, treći - x, četvrti - U. Tada je, po skupu vrijednosti argumenata, lako

pronaći vrijednost funkcije. Neka je, na primjer, dat skup 1001. Prema njegovom

zapisa, tj. na skupu 1001, data funkcija je jednaka jedan.

Imajte na umu ponovo da je skup vrijednosti argumenata skup

nule i jedinice. Binarni brojevi su takođe skupovi nula i jedinica.

Ovo postavlja pitanje - da li se skupovi mogu smatrati binarnim

brojevi? Moguće je i u mnogim slučajevima je vrlo zgodno, posebno ako je binarno

pretvoriti broj u decimalni. Na primjer, ako

A = 0, B = 1, C = 1, D = 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

tj. dati skup ima broj 6 u decimalu.

Ako želite pronaći vrijednosti argumenata po decimalnom broju, onda

djelujemo obrnutim redoslijedom: prvo prevedemo decimalni broj u binarni, a zatim dodamo toliko nula s lijeve strane tako da ukupan broj bitova bio jednak broju argumenata, nakon čega nalazimo vrijednosti argumenata.

Neka je, na primjer, potrebno pronaći vrijednosti argumenata A, B, C, D, E, F skupom sa brojem 23. Konvertujemo broj 23 u binarni sistem metodom

dijeljenje sa dva:

Kao rezultat, dobijamo 23 10 = 10111 2 . Ovo je petocifreni broj, i to ukupno

postoji šest argumenata, dakle, jedna nula mora biti napisana na lijevoj strani:

23 10 = 010111 2 . Odavde nalazimo:

A = 0, B = 1, C = 0, D = 1, E = 1, F = 1.

Koliko ima skupova ako je broj poznat P argumenti? Očigledno, onoliko koliko ima n-bitnih binarnih brojeva, tj. 2 n

Predavanje 6

Postavljanje Booleove funkcije

Već znamo jedan način. Analitičan je, odnosno u obliku matematičkog izraza koji koristi binarne varijable i logičke operacije. Osim toga, postoje i drugi načini, od kojih je najvažniji tabelarni. U tabeli su navedeni svi mogući skupovi vrijednosti argumenata, a za svaki skup je naznačena vrijednost funkcije. Takva tabela se zove tabela korespondencije (istine).

Na primjeru funkcije

Hajde da shvatimo kako da napravimo tabelu za traženje za to.

Funkcija ovisi o tri argumenta A, B, C. Dakle, u tabeli

obezbediti tri kolone za argumenti A,B,C i jedan stupac za vrijednosti funkcije f. Lijevo od kolone A, korisno je postaviti još jednu kolonu. U njega ćemo pisati decimalne brojeve koji odgovaraju skupovima, ako ih smatramo trocifrenim binarnim brojevima. Ova decimala

stupac je uveden radi praktičnosti rada sa tablicom, stoga, u principu,

može se zanemariti.

Popunjavamo tabelu. Red sa brojem LLC preduzeća glasi:

A = B = C = 0.

Definirajmo vrijednost funkcije na ovom skupu:

U kolonu f upisujemo nulu u red sa skupom 000.

Sljedeći set: 001, tj. e. A = B = 0, C = 1. Pronađite vrijednost funkcije

na ovom setu:

Na skupu 001, funkcija je jednaka 1, dakle, u koloni f u redu sa

broj 001 zapisujemo jedinicu.

Slično, izračunavamo vrijednosti funkcija na svim ostalim skupovima i

popuni celu tabelu.

Asocijativnost

x 1 (x 2 x 3) \u003d (x 1 x 2) x 3;

x 1 Ú (x 2 Ú x 3) \u003d (x 1 Ú x 2) Ú x 3.

komutativnost

x 1 x 2 = x 2 x 1

x 1 Ú x 2 = x 2 Ú x 1

Distributivnost konjunkcije u odnosu na disjunkciju

x 1 (x 2 Ú x 3) \u003d x 1 x 2 Ú x 1 x 3.

Distributivnost disjunkcije u odnosu na konjunkciju

x 1 Ú(x 2 × x 3) = (x 1 Úx 2) × (x 1 Úx 3). *

Idempotencija (tautologija)

Dva puta br

Konstantna svojstva

x & 1 = x; (zakoni univerzalnog skupa)

x & 0 = 0; (zakoni nula)

Pravila (zakoni) de Morgan

Zakon protivrečnosti (adicionalnosti)

Zakon o isključenju sredine (dodatni)

Dokazi svih ovih formula su trivijalni. Jedna od opcija je da se napravi tabela istinitosti lijevog i desnog dijela i uporedi.

Pravila lepljenja

Pravilo lijepljenja za elementarne konjunkcije slijedi iz distributivnog zakona, zakona komplementarnosti i zakona univerzalnog skupa: disjunkcija dvaju susjednih veznika može se zamijeniti jednim elementarnim veznikom, koji je zajednički dio izvornih veznika .

Pravilo lijepljenja za elementarne sume slijedi iz distributivnog zakona druge vrste, zakona komplementarnosti i zakona nultog skupa: konjunkcija dviju susjednih disjunkcija može se zamijeniti jednom elementarnom disjunkcijom, koja je zajednički dio originalnih disjunkcija .

Pravilo apsorpcije

Pravilo apsorpcije za zbir dva elementarna proizvoda slijedi iz distributivnog zakona prve vrste i zakona univerzalnog skupa: disjunkcija dva elementarna veznika, od kojih je jedan sastavni dio drugi, može se zamijeniti konjukcijom s manje operanada .

Pravilo apsorpcije za proizvod elementarnih suma proizilazi iz distributivnog zakona druge vrste i zakona nultog skupa: konjunkcija dvije elementarne disjunkcije, od kojih je jedna sastavnica druge, može se zamijeniti elementarnom disjunkciju koja ima manje operanada.

Pravilo raspoređivanja

Ovo pravilo definira obrnutu akciju lijepljenja.

Pravilo za proširenje elementarnog proizvoda u logički zbir elementarnih proizvoda višeg ranga (u granici do r = n, tj. do konstituenata jedinice, o čemu će biti riječi u nastavku) slijedi iz zakona univerzalnog skupa , distributivni zakon prve vrste, a provodi se u tri faze:

Elementarni proizvod ranga r koji treba razviti se uvodi kao faktori n-r jedinica, gdje je n rang konstituenata jedinice;

Svaka jedinica je zamijenjena logičkim zbrojem neke varijable koja nije prisutna u originalnom elementarnom proizvodu i njenom negacijom: x i v `x i = 1;

Sve zagrade su proširene na osnovu distributivnog zakona prve vrste, što dovodi do proširenja originalnog elementarnog proizvoda ranga r u logički zbir od 2 n-r jedinične konstituenta.

Elementarno pravilo proširenja proizvoda koristi se za minimiziranje funkcija logičke algebre (FAL).

Pravilo za proširenje elementarnog zbira ranga r na proizvod elementarnih zbira ranga n (konstituent nula) slijedi njihove zakone nultog skupa (6) i distributivnog zakona druge vrste (14) i izvodi se u tri faze:

U proširivi zbir ranga r uvodimo kao sabirke n-r nula;

Svaka nula je predstavljena kao logički proizvod neke varijable koja nije prisutna u početnoj sumi i njenoj negaciji: x i·` x i = 0;

Rezultirajući izraz se transformira na osnovu distributivnog zakona druge vrste (14) na način da se početni zbir ranga r odvija u logički proizvod od 2 n-r nula konstituenta.

16. Koncept kompletnog sistema. Primjeri kompletnih sistema (sa dokazom)

Definicija. Skup funkcija logičke algebre A naziva se kompletan sistem(u P2) ako se bilo koja funkcija algebre logike može izraziti formulom nad A.

Funkcijski sistem A=( f 1 , f 1 ,…, f m) koji je potpun se zove osnovu.

Minimalna osnova je takva osnova za koju se uklanja barem jedna funkcija f1, koji čini ovu osnovu, transformiše sistem funkcija (f 1 , f 1 ,…, f m) u nepotpunom.

Teorema. Sistem A = (∨, &, ) je potpun.

Dokaz. Ako funkcija logičke algebre f nije identično nula, tada se f izražava kao savršena disjunktivna normalna forma, koja uključuje samo disjunkciju, konjunkciju i negaciju. Ako je f ≡ 0, onda je f = x & x . Teorema je dokazana.

Lemma. Ako je sistem A potpun, a bilo koja funkcija sistema A može se izraziti formulom preko nekog drugog sistema B, onda je B također potpun sistem.

Dokaz. Razmotrimo proizvoljnu funkciju logičke algebre f (x 1 , …, x n) i dva sistema funkcija: A = (g 1 , g 2 , …) i B = (h 1 , h 2 , …). Zbog činjenice da je sistem A kompletan, funkcija f se može izraziti formulom nad njim:

f (x 1 , …, x n) = ℑ

gdje je g i = ℜ i

odnosno funkcija f je predstavljena kao

f (x 1 , …, x n)=ℑ[ℜ1,ℜ2,...]

drugim riječima, može se predstaviti formulom nad B. Nabrajajući na ovaj način sve funkcije algebre logike, dobijamo da je i sistem B potpun. Lema je dokazana.

Teorema. Sljedeći sistemi su kompletni u P 2:

4) (&, ⊕ , 1) Žegalkinova baza.

Dokaz.

1) Poznato je (teorema 3) da je sistem A = (&, V, ) potpun. Pokažimo da je sistem B = ( V, . Zaista, iz de Morganovog zakona (x& y) = (x ∨ y) dobijamo da je x & y = (x ∨ y), odnosno da je konjunkcija izražena kroz disjunkciju i negaciju, a sve funkcije sistema A su izražene formulama nad sistemom B. Prema lemi, sistem B je potpun.

2) Slično kao kod tačke 1: (x ∨ y) = x & y ⇔ x ∨ y =(x & y) i Lema 2 implicira istinitost stavke 2.

3) x | y=(x&y), x | x = x; x & y = (x | y) = (x | y) | (x | y) i prema lemi 2 sistem je potpun.

4) x = x ⊕1 i prema lemi 2 sistem je potpun.

Teorema je dokazana.

17. Žegalkinova algebra. Svojstva i kompletnost operacije

Skup Booleovih funkcija definiranih u Žegalkinovoj bazi S4=(⊕,&,1) naziva se Zhegalkin algebra.

Osnovna svojstva.

1. komutativnost

h1⊕h2=h2⊕h1 h1&h2=h2&h1

2. asocijativnost

h1⊕(h2⊕h3)=(h1⊕h2)⊕h3 h1&(h2&h3)=(h1&h2)&h3

3. distributivnost

h1&(h2⊕h3)=(h1&h2)⊕(h1&h3)

4. konstantna svojstva

5. h⊕h=0 h&h=h
Izjava. Kroz operacije Zhegalkinove algebre, sve ostale Booleove funkcije mogu se izraziti:

x→y=1⊕x⊕xy

x↓y=1⊕x⊕y⊕xy

18. Žegalkin polinom. Metode izgradnje. Primjer.

Zhegalkin polinom (polinom po modulu 2) iz n varijable x 1 ,x 2 ... x n naziva se izraz oblika:

c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n ,

gdje konstante C k mogu imati vrijednosti 0 ili 1.

Ako Zhegalkin polinom ne sadrži proizvode pojedinačnih varijabli, onda se naziva linearnim (linearna funkcija).

Na primjer, f=x⊕yz⊕xyz i f 1 =1⊕x⊕y⊕z su polinomi, a potonji je linearna funkcija.

Teorema. Svaka Booleova funkcija je predstavljena kao Zhegalkin polinom na jedinstven način.

Predstavimo glavne metode za konstruisanje Zhegalkin polinoma date funkcije.

1. Metoda neodređenih koeficijenata. Neka je P(x 1 ,x 2 ... x n) traženi Žegalkinov polinom koji se ostvaruje za ovu funkciju f(x 1 ,x 2 ... x n). Zapisujemo ga u formu

P=c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n

Nađimo koeficijente C k . Da bismo to učinili, uzastopno dajemo vrijednosti varijabli x 1 ,x 2 ... x n iz svakog reda tablice istinitosti. Kao rezultat, dobijamo sistem od 2 n jednačina sa 2 n nepoznatih, koji ima jedina odluka. Rješavajući ga, nalazimo koeficijente polinoma P(X 1 ,X 2 ... X n).

2. Metoda zasnovana na transformaciji formula preko skupa veziva (,&). Napravite formulu F preko skupa veza (,&) koji realizuju datu funkciju f(X 1 ,X 2 ... X n). Zatim svugdje zamjenjujemo podformule oblika A sa A⊕1, otvaramo zagrade koristeći distributivni zakon (vidi svojstvo 3), a zatim primjenjujemo svojstva 4 i 5.

Primjer. Konstruirajte Zhegalkin polinom funkcije f(X,Y)=X→Y

Rješenje.
1. (metoda neizvjesnih koeficijenata). Zapisujemo traženi polinom u obliku:

P=c 0 ⊕c 1 x⊕c 2 y⊕c 12 xy

Koristeći tabelu istinitosti implikacije, dobijamo to

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

Odakle sukcesivno nalazimo, C 0 =1, C 1 =1, C 2 =0, C 12 =1

Prema tome: x→y=1⊕X⊕XY.

2. (Metoda pretvaranja formula.). Imamo: x→y=xvy=(xy)=(x(y⊕1)) ⊕1=1⊕x⊕xy
Imajte na umu da je prednost Zhegalkinove algebre (u poređenju sa drugim algebrama) aritmetizacija logike, koja omogućava da se transformacije Booleovih funkcija obavljaju prilično jednostavno. Njegova mana u odnosu na Bulovu algebru je glomaznost formula.

Slične informacije.

De Morganovi zakoni su logička pravila koja je ustanovio škotski matematičar Augustus de Morgan koja povezuju parove logičkih operacija koristeći logičku negaciju.

Augustus de Morgan je primijetio da su sljedeće relacije istinite u klasičnoj logici:

ne (A i B) = (ne A) ili (ne B)

ne (A ili B) = (ne A) i (ne B)

U nama poznatijem obliku, ovi omjeri se mogu napisati u sljedećem obliku:

De Morganovi zakoni se mogu formulisati na sledeći način:

I de Morganov zakon: Negacija disjunkcije dva jednostavna iskaza je ekvivalentna konjunkciji negacija ovih iskaza.

II de Morganov zakon: Negacija konjunkcije dva jednostavna iskaza je ekvivalentna disjunciji negacija ovih iskaza.

Razmotrite primjenu de Morganovih zakona na konkretnim primjerima.

Primjer 1 Transformirajte formulu tako da nema negacija složenih iskaza.

Koristimo prvi de Morganov zakon, dobijamo:

primijenimo drugi de Morganov zakon na negaciju konjunkcije jednostavnih iskaza B i C, dobićemo:

,

ovako:

.

Kao rezultat, dobili smo ekvivalentan iskaz u kojem nema negacija složenih iskaza, a sve negacije se odnose samo na jednostavne iskaze.

Ispravnost rješenja možete provjeriti pomoću tablica istinitosti. Da bismo to učinili, sastavljamo tablice istinitosti za originalnu izjavu:

i za iskaz dobijen kao rezultat transformacija izvršenih korištenjem de Morganovih zakona:

.

Tabela 1.

Kao što vidimo iz tabela, originalni logički iskaz i logički iskaz dobijen uz pomoć de Morganovih zakona su ekvivalentni. O tome svjedoči činjenica da smo u tabelama istinitosti dobili iste skupove vrijednosti.

Formule i zakoni logike

U uvodnoj lekciji o osnove matematičke logike, upoznali smo se sa osnovnim pojmovima ovog odsjeka matematike, a sada tema dobiva prirodan nastavak. Pored novog teorijskog, bolje rečeno, čak ni teorijskog - već općeobrazovnog materijala, čekamo i praktični zadaci, i stoga ako ste na ovu stranicu došli iz tražilice i/ili ste loše orijentirani u materijalu, slijedite gornji link i počnite od prethodnog članka. Osim toga, za vježbu nam je potrebno 5 tabele istine logičke operacije koji ja toplo preporučujem prepisati rukom.

NEMOJTE pamtiti, NE štampajte, naime, još jednom shvatite i prepišite na papir svojom rukom - tako da vam budu pred očima:

– tabela NE;
- tabela I;
– ILI tabela;
– tabela implikacija;
- Tabela ekvivalencije.

To je veoma važno. U principu, bilo bi zgodno da ih numerišemo "Tabela 1", "Tabela 2" itd., ali sam više puta isticao manu ovog pristupa - kako se kaže, u jednom izvoru tabela će biti prva, a u drugom - sto prva. Stoga ćemo koristiti "prirodna" imena. Nastavljamo:

U stvari, već ste upoznati s konceptom logičke formule. Dat ću standardno, ali prilično duhovito definicija: formule propozicijske algebre se nazivaju:

1) bilo koje elementarne (jednostavne) izjave;

2) ako su i formule, onda su formule i izrazi oblika
.

Nema drugih formula.

Konkretno, formula je svaka logička operacija, kao što je logičko množenje. Obratite pažnju na drugu tačku - to dozvoljava rekurzivno način da se "kreira" proizvoljno duga formula. Zbog su formule, onda je i formula; budući da su i formule, onda - takođe formula, itd. Bilo koja elementarna izjava (opet po definiciji) može unijeti formulu više puta.

Formula ne je, na primjer, rekord - i ovdje postoji očigledna analogija sa "algebarskim smećem", iz koje nije jasno da li brojeve treba sabirati ili množiti.

Logička formula se može zamisliti kao logička funkcija. Napišimo isti veznik u funkcionalnom obliku:

Elementarni iskazi u ovom slučaju također igraju ulogu argumenata (nezavisnih varijabli), koji u klasičnoj logici mogu imati 2 vrijednosti: tačno ili False. U daljem tekstu, radi pogodnosti, ponekad ću nazivati ​​jednostavne izjave varijable.

Tablica koja opisuje logičku formulu (funkciju) naziva se, kao što je već spomenuto, tabela istine. Molim vas - poznata slika:

Princip formiranja tabele istinitosti je sledeći: "na ulazu" treba da navedete sve moguće kombinacije istine i laži koje elementarni prijedlozi (argumenti) mogu prihvatiti. U ovom slučaju formula uključuje dva iskaza, a lako je otkriti da postoje četiri takve kombinacije. “Na izlazu” dobijamo odgovarajuće logičke vrijednosti ​​cijele formule (funkcije).

Moram reći da se "izlaz" ovdje pokazao "u jednom koraku", ali u općenitom slučaju logička formula je složenija. I u takvim "teškim slučajevima" potrebno je promatrati redosled izvođenja logičkih operacija:

- prvo se vrši negacija;
- drugo - konjunkcija;
- zatim - disjunkcija;
- zatim implikacija ;
- i, konačno, najniži prioritet ima ekvivalent.

Tako, na primjer, unos podrazumijeva da prvo treba izvršiti logičko množenje, a zatim - logičko zbrajanje:. Baš kao u "običnoj" algebri - "prvo množimo, a onda sabiramo."

Redoslijed radnji se može promijeniti na uobičajeni način - zagrade:
- ovdje se prije svega vrši disjunkcija, a tek onda "jaka" operacija.

Vjerovatno svi razumiju, ali za svaki slučaj vatrogasac: i to dva različita formule! (i formalno i sadržajno)

Napravimo tabelu istinitosti za formulu. Ova formula uključuje dva elementarna iskaza i „na ulazu“ moramo navesti sve moguće kombinacije jedinica i nula. Kako bismo izbjegli zabunu i nedosljednosti, slažemo se da navedemo kombinacije striktno tim redosledom (koji zapravo koristim de facto od samog početka):

Formula uključuje dvije logičke operacije, a prema njihovom prioritetu, prije svega, morate izvršiti negacija izjave. Pa, negiramo kolonu "pe" - pretvaramo jedinice u nule, a nule u jedinice:

U drugom koraku gledamo kolone i primjenjujemo se na njih OR operacija. Gledajući malo unapred, reći ću da je disjunkcija promenljiva (i ista stvar), te se stoga kolone mogu analizirati uobičajenim redoslijedom - s lijeva na desno. Prilikom izvođenja logičkog sabiranja zgodno je koristiti sljedeće primijenjeno razmišljanje: “Ako postoje dvije nule, stavljamo nulu, ako je barem jedna jedinica, stavljamo jedan”:

Tabela istine je napravljena. A sada se prisjetimo dobre stare implikacije:

…pažljivo-pažljivo…pogledajte zadnje kolone…. U propozicionoj algebri takve formule se nazivaju ekvivalentno ili identičan:

(tri horizontalne linije su ikona identiteta)

U 1. dijelu lekcije obećao sam da ću izraziti implikaciju kroz osnovne logičke operacije, a ispunjenje obećanja nije se dugo čekalo! Oni koji žele mogu da unesu smisleno značenje u implikaciju (npr. "Ako pada kiša, vani je vlažno") i samostalno analizirati ekvivalentnu izjavu.

Hajde da formulišemo opšta definicija: pozivaju se dvije formule ekvivalent (identičan), ako uzimaju iste vrijednosti za bilo koji skup vrijednosti uključenih u ove formule varijabli (elementarni iskazi). I oni to kažu "formule su ekvivalentne ako su njihove tabele istinitosti iste", ali ne volim ovu frazu.

Vježba 1

Napravite tabelu istinitosti za formulu i uvjerite se da je identitet koji poznajete istinit.

Ponovimo proceduru za rješavanje problema:

1) Budući da formula uključuje dvije varijable, bit će 4 moguća skupa nula i jedinica ukupno. Zapisujemo ih gore navedenim redoslijedom.

2) Implikacije su „slabije“ od veznika, ali se nalaze u zagradama. Popunjavamo kolonu, a zgodno je koristiti sljedeće primijenjeno rezonovanje: "ako nula proizlazi iz jedan, onda stavljamo nulu, u svim ostalim slučajevima - jedan". Zatim popunite kolonu za implikaciju i istovremeno, Pažnja!– kolone i treba ih analizirati “s desna na lijevo”!

3) I u završnoj fazi, popunite zadnju kolonu. I ovdje je zgodno raspravljati ovako: “ako su u kolonama dvije jedinice, onda stavljamo jedan, u svim ostalim slučajevima - nula”.

I na kraju, provjeravamo tabelu istinitosti ekvivalencije .

Osnovne ekvivalencije propozicione algebre

Upravo smo ih upoznali sa dvojicom, ali stvar, naravno, nije ograničena samo na njih. Ima dosta identiteta, a ja ću navesti najvažnije i najpoznatije od njih:

Komutativnost konjunkcije i komutativnost disjunkcije

komutativnost je permutacija:

Poznata pravila iz 1. razreda: “Od preraspodjele faktora (termina), proizvod (zbir) se ne mijenja”. Ali uz svu prividnu elementarnost ovog svojstva, to je daleko od uvijek istinito, posebno je nekomutativno množenje matrice (u principu, ne mogu se preurediti), a unakrsni proizvod vektora– antikomutativno (permutacija vektora podrazumijeva promjenu predznaka).

Osim toga, ovdje još jednom želim naglasiti formalizam matematičke logike. Tako, na primjer, fraze "Učenik je položio ispit i pio" i "Učenik je pio i položio ispit" različit sa sadržajne tačke gledišta, ali se ne može razlikovati sa stanovišta formalne istine. ... Svako od nas poznaje takve studente, a iz etičkih razloga nećemo imenovati konkretna imena =)

Asocijativnost logičkog množenja i sabiranja

Ili, ako je "školski stil" asocijativno svojstvo:

Distribution Properties

Imajte na umu da će u drugom slučaju biti netačno govoriti o "otvaranju zagrada", na neki način, ovdje je "fikcija" - na kraju krajeva, oni se mogu potpuno ukloniti: množenje je jača operacija.

I opet, ova naizgled "banalna" svojstva daleko su od toga da budu zadovoljena u svim algebarskim sistemima, i, osim toga, zahtijevaju dokaz (o čemu ćemo vrlo brzo pričati). Inače, drugi distributivni zakon ne važi čak ni u našoj „običnoj“ algebri. I zaista:

Zakon idempotencije

Šta da se radi latino....

Samo neki princip zdrave psihe: "ja i ja sam ja", "ja ili ja sam isto ja" =)

A evo nekoliko sličnih identiteta:

...pa, nešto sam čak i spustio slušalicu... pa se sutra probudiš sa doktoratom =)

Zakon dvostruke negacije

Pa, ovdje se već nagovještava primjer sa ruskim jezikom - svi dobro znaju da dvije čestice "ne" znače "da". A kako bi se poboljšala emocionalna boja poricanja, često se koriste tri „ne“:
- čak i sa malo dokaza da je uspelo!

Zakoni apsorpcije

- Je li to bio dječak? =)

U pravom identitetu zagrade se mogu izostaviti.

De Morganovi zakoni

Pretpostavimo da je strog učitelj (čije ime takođe znaš :)) polaže ispit ako - Učenik je odgovorio na 1. pitanje i – Učenik je odgovorio na 2. pitanje. Zatim izjava u kojoj se to navodi Student ne položio ispit, bit će ekvivalentno izjavi - Student ne odgovorio na 1. pitanje ili na 2. pitanje.

Kao što je gore navedeno, ekvivalencije su podložne dokazu, koji se standardno provodi pomoću tablica istinitosti. Zapravo, već smo dokazali ekvivalentnosti koje izražavaju implikaciju i ekvivalenciju, a sada je vrijeme da popravimo tehniku ​​rješavanja ovog problema.

Dokažimo identitet. Budući da uključuje jednu naredbu, tada su moguće samo dvije opcije „na ulazu“: jedan ili nula. Zatim dodjeljujemo jednu kolonu i primjenjujemo se na njih pravilo I:

Kao rezultat, "na izlazu" se dobiva formula, čija se istinitost poklapa s istinitošću izjave. Ekvivalencija je dokazana.

Da, ovaj dokaz je primitivan (a neko će reći da je "glupo"), ali tipičan nastavnik matematike će mu istresti dušu. Stoga se čak ni prema takvim jednostavnim stvarima ne treba odnositi s prezirom.

Sada se uvjerimo, na primjer, u valjanost de Morganovog zakona.

Prvo, napravimo tabelu istine za lijevu stranu. Pošto je disjunkcija u zagradama, prvo je izvodimo, nakon čega negiramo stupac:

Zatim sastavljamo tabelu istinitosti za desnu stranu. I ovdje je sve transparentno - prije svega izvodimo više "jakih" negativa, a zatim primjenjujemo na stupce pravilo I:

Rezultati su se poklopili, tako da je identitet dokazan.

Bilo koja ekvivalentnost se može predstaviti kao identično istinita formula. To znači da ZA BILO KOJI početni skup nula i jedinica"na izlazu" se dobija striktno jedinica. A za to postoji vrlo jednostavno objašnjenje: pošto se tablice istinitosti i poklapaju, onda su, naravno, ekvivalentne. Kombinirajmo, na primjer, lijevi i desni dio upravo dokazanog de Morganovog identiteta ekvivalentnošću:

Ili, kompaktnije:

Zadatak 2

Dokažite sljedeće ekvivalentnosti:

b)

Kratko rješenje na kraju lekcije. Nemojmo biti lijeni! Pokušajte ne samo napraviti tablice istine, već i jasno formulisati zaključke. Kao što sam nedavno primetio, zanemarivanje jednostavnih stvari može biti veoma, veoma skupo!

Nastavljamo da se upoznajemo sa zakonima logike!

Da, potpuno tačno - već radimo s njima uveliko:

Tačno at , zove se identično istinita formula ili zakon logike.

Na osnovu prethodno opravdanog prelaska sa ekvivalencije na identično istinitu formulu, svi gore navedeni identiteti su zakoni logike.

Formula koja uzima vrijednost Lazi at bilo koji skup vrijednosti varijabli uključenih u njega, zove se identično lažna formula ili kontradikcija.

Karakteristični primjer kontradikcije starih Grka:
Nijedna izjava ne može biti istinita i lažna u isto vrijeme.

Dokaz je trivijalan:

“Izlaz” je dobio isključivo nule, dakle, formula je zaista identično lažno.

Međutim, svaka kontradikcija je takođe zakon logike, posebno:

Nemoguće je obraditi tako veliku temu u jednom članku, pa ću se ograničiti na još samo nekoliko zakona:

Zakon isključene sredine

- u klasičnoj logici, svaka izjava je istinita ili lažna, i ne postoji treći način. “Biti ili ne biti” – to je pitanje.

Napravite sopstvenu tabelu istine i uverite se da jeste identično istinito formula.

Zakon kontrapozicije

Ovaj zakon se aktivno preuveličavao kada smo raspravljali o suštini neophodno stanje, zapamtite: „Ako je napolju vlažno za vreme kiše, onda sledi da ako je napolju suvo, onda definitivno nije padala kiša“.

Takođe iz ovog zakona proizilazi da ako je pošteno ravno teorema, zatim iskaz, koji se ponekad naziva suprotno teorema.

Ako je istina obrnuto teorema, onda na osnovu zakona kontrapozicije, teorema također vrijedi, suprotno obrnuto:

I vratimo se našim smislenim primjerima: za izjave - broj je djeljiv sa 4, - broj je djeljiv sa 2 fer ravno i suprotno teoreme, ali netačne obrnuto i suprotno obrnuto teoreme. Za "odraslu" formulaciju Pitagorine teoreme, sva 4 "smjera" su tačna.

Zakon silogizma

Takođe klasik žanra: „Svi hrastovi su drveće, svako drveće su biljke, stoga su svi hrastovi biljke“.

Pa, ovdje bih opet želio primijetiti formalizam matematičke logike: ako naš strogi Učitelj misli da je određeni Učenik hrast, onda je sa formalne tačke gledišta, ovaj Učenik svakako biljka =) ... iako, ako razmislite o tome, može biti i iz neformalnog = )

Napravimo tabelu istinitosti za formulu. U skladu sa prioritetom logičkih operacija, pridržavamo se sljedećeg algoritma:

1) izvršiti implikacije i . Uopšteno govoreći, možete odmah izvršiti 3. implikaciju, ali je s njom pogodnije (i dozvoljeno!) shvatite malo kasnije

2) primijeniti na stupce pravilo I;

3) sada izvršavamo;

4) i u završnom koraku primijeniti implikaciju na stupce i .

Slobodno kontrolirajte proces kažiprstom i srednjim prstom :))


Iz zadnje kolumne mislim da je sve jasno bez komentara:
, što je trebalo dokazati.

Zadatak 3

Saznajte je li sljedeća formula zakon logike:

Kratko rješenje na kraju lekcije. Da, i skoro sam zaboravio - hajde da se dogovorimo da navedemo početne skupove nula i jedinica potpuno istim redosledom kao u dokazu zakona silogizma. Naravno, linije se mogu preurediti, ali to će otežati pomirenje sa mojim rješenjem.

Pretvaranje Booleovih formula

Pored njihove "logičke" svrhe, ekvivalentnosti se široko koriste za transformaciju i pojednostavljenje formula. Grubo govoreći, jedan dio identiteta može se zamijeniti drugim. Tako, na primjer, ako naiđete na fragment u logičkoj formuli, onda, prema zakonu idempotencije, možete (i trebali biste) jednostavno napisati umjesto njega. Ako vidite , onda, prema zakonu apsorpcije, pojednostavite notaciju na . I tako dalje.

Osim toga, postoji još jedan važna stvar: identiteti vrijede ne samo za elementarne propozicije, već i za proizvoljne formule. Na primjer:

, gdje ih ima (kompleksno koliko god želite) formule.

Transformirajmo, na primjer, kompleksnu implikaciju (1. identitet):

Nadalje, na zagradu primjenjujemo „složeni“ de Morganov zakon, dok je, zbog prioriteta operacija, zakon , gdje :

Zagrade se mogu ukloniti, jer unutra se nalazi "jači" veznik:

Pa, s komutativnošću, generalno, sve je jednostavno - ne morate ništa ni označavati ... nešto mi je potonulo u dušu zakon silogizma :))

Dakle, zakon se može prepisati u zamršenijem obliku:

Izgovorite naglas logički lanac „sa hrastom, drvetom, biljkom“ i shvatićete da se suštinsko značenje zakona nije nimalo promenilo od prestrojavanja implikacija. Je li da je formulacija postala originalnija.

Kao trening, pojednostavljujemo formulu.

Gdje početi? Prije svega, da shvatimo redoslijed radnji: ovdje se negacija primjenjuje na cijelu zagradu, koja je "učvršćena" sa iskazom "malo slabijim" veznikom. U suštini, imamo pred sobom logički proizvod dva faktora: . Od dvije preostale operacije, implikacija ima najniži prioritet, te stoga cijela formula ima sljedeću strukturu: .

U pravilu se na prvom koraku (koracima) oslobodite ekvivalencije i implikacije (ako jesu) i svesti formulu na tri osnovne logičke operacije. Šta da kažem…. Logično.

(1) Koristimo identitet . I u našem slučaju.

Nakon toga obično slijedi "demontaža" sa zagradama. Prvo cijelo rješenje, pa komentari. Da ne bih dobio "maslac ulje", koristit ću "uobičajene" ikone jednakosti:

(2) Mi primjenjujemo de Morganov zakon na vanjske zagrade, gdje je .

Razmatrane operacije nad skupovima podliježu određenim zakonima, koji podsjećaju na dobro poznate elementarne zakone algebre brojeva. Ovo definiše ime set algebra, koji se često naziva algebra Bulove skupove, što se povezuje s imenom engleskog matematičara Johna Boolea, koji je svoje logičko istraživanje zasnovao na ideji analogije između algebre i logike.

Za proizvoljne skupove A, B i C, istiniti su sljedeći identiteti (tabela 3.1):

Tabela 3.1

Zakoni algebre skupova u odnosu na operacije presjeka () i unije () podliježu principu dualnosti: ako su u bilo kojem zakonu svi znakovi presjeka zamijenjeni znakovima unije, a svi znakovi unije su znakovi sjecišta , znak svemira (U) zamjenjuje se znakom praznog skupa (Ø), a znak praznog - znakom svemira, tada opet dobijamo ispravan identitet. Na primjer (na osnovu ovog principa), proizlazi iz itd.

3.1. Provjera istinitosti identiteta korištenjem Euler-Venn dijagrama

Svi zakoni algebre skupova mogu se vizualno prikazati i dokazati korištenjem Euler-Venn dijagrama. Za ovo vam je potrebno:

Nacrtajte odgovarajući dijagram i zasenčite sve skupove na lijevoj strani jednačine.

Nacrtajte drugi dijagram i uradite isto za desnu stranu jednačine.

Ovaj identitet je istinit ako i samo ako je ista oblast zasjenjena na oba dijagrama.

Napomena 3.1. Dva kruga koji se ukrštaju dijele cijeli univerzalni skup na četiri regije (vidi sliku 3.1)

Napomena 3.2. Tri kružnice koje se ukrštaju dijele cijeli univerzalni skup na osam regija (vidi sliku 3.2):

Napomena 3.2. Prilikom pisanja uslova različitih primjera, često se koristi notacija:

 - iz ... slijedi ...;

 - ako i samo ako...

Zadatak 3.1 . Pojednostavite izraze algebre skupa:

Rješenje.

Zadatak 3 .2 . Dokažite identitete:

(AB)\B = A\B;

A(BC) = A\(A\B)(A\C).

Rješenje.

Zadatak 3.3 . Dokažite sljedeće relacije na dva načina: koristeći dijagrame i koristeći definiciju jednakosti skupova.

Rješenje.

2. Dokaz pomoću definicije jednakosti skupova.

Po definiciji, skupovi X i Y su jednaki ako su simultano zadovoljene sljedeće relacije: XY i YX.

Hajde da prvo to pokažemo
. Neka X je proizvoljan element skupa
, to je X
. To znači da XU i X
. Otuda to sledi XA ili XB. Ako a XAh, onda XĀ, što znači
. Ako XB, dakle
, što znači
. Dakle, svaki element skupa.
. je također element skupa
To je

Sada dokazujemo obrnuto, to jest
. Neka
. Ako a XĀ, dakle XU i XA, što znači XAB. Otuda to sledi
. Ako
, onda XU i XB. znači, XAB, tj
. Iz toga slijedi da je svaki element skupa
je također element skupa
, to je
.

znači,
, što je trebalo dokazati.

A(BC) = (AB)(AC);

1. Dokaz sa dijagramom:

Neka XA(BC). Onda XA i XBC. Ako a XB, dakle XAB, što nije u suprotnosti sa onim što je rečeno, što znači da X(AB)(AC). Ako XC, dakle XAC. shodno tome, X(AB)(AC). Dakle, dokazali smo da je A(BC)  (AB)(AC.

Pusti sada X (AB)(AC). Ako a XAB, dakle XA i XB. Otuda to sledi XA i XVS, tj XA(BC). Ako XAC, dakle XA i XC. Otuda to sledi XA i XVS, tj XA(BC). Dakle, (AB)(AC) A(BC). Prema tome, A(BC) = (AB)(AC). Q.E.D.

Prilikom dokazivanja dovoljnosti dobili smo da je AV=. Očigledno je da je S, pa je relacija dokazana. U dokazu je razmatran najopštiji slučaj. Međutim, još uvijek postoje neke opcije prilikom konstruiranja dijagrama. Na primjer, slučaj jednakosti AB \u003d C ili
, slučaj praznih skupova i tako dalje. Očigledno je da je teško uzeti u obzir sve moguće opcije. Stoga se vjeruje da dokaz relacija pomoću dijagrama nije uvijek tačan.

2. Dokaz pomoću definicije jednakosti skupova.

Need. Neka ABC i element XA. Pokažimo da će u ovom slučaju element skupa A biti i element skupa
.

Razmotrite dva slučaja: XU ili
.

Ako a XB, dakle XABC, tj XC, i kao rezultat,
.

Ako
, zatim i
. Potreba je dokazana.

Pusti sada
i XAB. Pokažimo da je element Xće također biti element skupa C.

Ako a XAB, dakle XA i XB. Zbog
, znači XC. Dovoljnost je dokazana.

1. Dokaz sa dijagramom:

2. Dokaz pomoću definicije jednakosti skupova.

Neka AB. Razmotrite element XB (ili
). Slično: XA (ili XĀ). Odnosno, svaki element skupa je također element skupa Ā. I to može biti slučaj ako
. Q.E.D.

Zadatak 3.4. Izrazite simbolički naznačena područja i pojednostavite rezultirajuće izraze.

Rješenje.

Pretraženo područje se sastoji od dva izolirana dijela. Nazovimo ih gornji i donji. Skup koji oni prikazuju može se opisati na sljedeći način:

M = ( x xA i XU i XC ili XC i XA i XB).

Iz definicije operacija nad skupovima dobijamo:

M = ((AB)\C)(C\A\B).

Napišimo ovaj izraz koristeći osnovne operacije - sabiranje, uniju i presjek:

Nemoguće je pojednostaviti ovaj izraz, jer imamo jedno pojavljivanje svakog znaka. Ovo je najjednostavniji oblik ove formule.

Ovo područje se može posmatrati kao unija skupova A\B\C i ABC. Po definiciji, M = ( x xA i xU i XC ili XA i XU i XC). Hajde da pojednostavimo:

Zadaci za samostalno rješavanje.

1. Pojednostavite:

2. Dokažite pomoću dijagrama, zakona algebre skupova i definicije jednakosti skupova:

(AB)\B = A\B;

A(BC) = A\(A\B)(A\C);

AB \u003d AB  A \u003d B;

A \ B \u003d   AB \u003d A.

3. Saznajte postoji li skup X koji za bilo koje A zadovoljava jednakost:

AX \u003d A; (odgovor );