Formule i zakoni logike

U uvodnoj lekciji o osnove matematičke logike, upoznali smo se s osnovnim pojmovima ovog odjeljka matematike, a sada se tema prirodno nastavlja. Osim novog teoretskog, ili bolje rečeno ne teorijskog, već općeobrazovnog materijala, očekuju nas i praktični zadaci, pa stoga ako ste na ovu stranicu ušli iz tražilice i/ili se slabo vodite materijalom, slijedite gornji link i početi s prethodnim člankom. Osim toga, za praksu nam je potrebno 5 tablice istine logičke operacije koji ja visoko preporučeno prepisati rukom.

NEMOJTE pamtiti, NEMOJTE ispisivati, naime, da ponovo shvatite i prepišete na papir svojom rukom - tako da vam budu pred očima:

- stol NIJE;
- tablica I;
- ILI stol;
- tablica implikacija;
- tablica ekvivalencije.

Vrlo je važno. U principu bi ih bilo zgodno numerirati. "Tablica 1", "Tablica 2" itd., ali sam više puta isticao manu ovakvog pristupa - kako se kaže, u jednom izvoru tablica će biti prva, a u drugom - sto prva. Stoga ćemo koristiti "prirodna" imena. Nastavljamo:

Zapravo, već ste upoznati s konceptom logičke formule. Dat ću vam standardan, ali prilično duhovit definicija: formule algebre iskaza nazivaju se:

1) bilo koje elementarne (jednostavne) izjave;

2) ako su i formule, tada su formule također izrazi oblika
.

Nema drugih formula.

Konkretno, formula je svaka logička operacija, kao što je logičko množenje. Obratite pozornost na drugu točku - to dopušta ponavljajući način "stvaranja" proizvoljno duge formule. Ukoliko - formule, zatim - također formula; budući da su i formule, onda - također formula, itd. Bilo koja elementarna izjava (opet kako je definirano) može se uključiti u formulu više puta.

Formula ne postoji npr. zapis - i ovdje je očita analogija s "algebarskim smećem", iz koje se ne vidi treba li brojeve zbrajati ili množiti.

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

U ovom slučaju elementarni iskazi također igraju ulogu argumenata (nezavisnih varijabli), koji u klasičnoj logici mogu imati 2 vrijednosti: pravi ili Laganje... U nastavku, radi praktičnosti, ponekad ću se pozvati na jednostavne izjave varijable.

Tablica koja opisuje logičku formulu (funkciju) zove se, kao što je već najavljeno, tablica istine... Molim - poznata slika:

Princip formiranja tablice istinitosti je sljedeći: "na ulazu" trebate nabrojati sve moguće kombinacije istine i laži koje mogu uzeti elementarne izjave (argumente). U ovom slučaju formula uključuje dvije tvrdnje, a lako je otkriti da postoje četiri takve kombinacije. "Na izlazu" dobivamo odgovarajuće logičke vrijednosti cijele formule (funkcije).

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

- prvo se izvodi negacija;
- drugo - veznik;
- zatim - disjunkcija;
- zatim implikacija;
- i konačno, ekvivalencija ima najniži prioritet.

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

Redoslijed radnji može se promijeniti na uobičajeni način - sa zagradama:
- ovdje se prije svega izvodi disjunkcija pa tek onda "jača" operacija.

Vjerojatno svi razumiju, ali za svakog vatrogasca: i to dvije različite formule! (i u formalnom i u materijalnom smislu)

Sastavimo tablicu istinitosti za formulu. Ova formula uključuje dva elementarna iskaza i "na ulazu" trebamo navesti sve moguće kombinacije jedinica i nula. Kako bismo izbjegli zabunu i nesporazume, slažemo se navesti kombinacije strogo tim redoslijedom (što zapravo koristim de facto od samog početka):

Formula uključuje dvije logičke operacije, a prema njihovom prioritetu, prije svega, trebate izvesti negacija izjave. Pa, poričemo stupac "pe" - pretvaramo jedinice u nule, a nule u jedinice:

U drugom koraku gledamo stupce i primjenjujemo na njih ILI operacija... Krećući malo naprijed, reći ću da je disjunkcija promjenjiva. (i ista stvar), te se stoga stupci mogu analizirati uobičajenim redoslijedom - s lijeva na desno. Prilikom izvođenja logičkog zbrajanja prikladno je koristiti sljedeće primijenjeno razmišljanje: "Ako postoje dvije nule, stavljamo nulu, ako je barem jedna jedinica jedan":

Tablica istine je izgrađena. Sjetimo se sada dobre stare implikacije:

… Pažljivo, pažljivo… gledamo zadnje stupce…. U propozicionoj algebri takve se formule nazivaju jednako ili identičan:

(tri horizontalne trake su ikona identiteta)

U prvom dijelu lekcije obećao sam izraziti implikaciju kroz osnovne logičke operacije, a ispunjenje obećanja nije se dugo čekalo! Zainteresirani mogu dati smisleno značenje u implikaciju (na primjer, "Ako pada kiša, vani je vlažno") i samostalno analizirati ekvivalentnu izjavu.

Formulirajmo opća definicija: nazivaju se dvije formule ekvivalent (identičan) ako uzimaju iste vrijednosti za bilo koji skup vrijednosti uključenih u ove formule varijabli (elementarni iskazi)... Također se kaže da "Formule su ekvivalentne ako se njihove tablice istine podudaraju" ali ovaj izraz mi se baš i ne sviđa.

Vježba 1

Sastavite tablicu istinitosti za formulu i uvjerite se da je identitet koji poznajete istinit.

Ponovimo još jednom redoslijed rješavanja problema:

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

2) Implikacije su "slabije" od veznika, ali su stavljene u zagrade. Stupac popunjavamo, a zgodno je koristiti sljedeće primijenjeno razmišljanje: "Ako nula slijedi iz jedan, onda stavljamo nulu, u svim ostalim slučajevima - jedan"... Zatim popunjavamo stupac za implikaciju, a istovremeno, Pažnja!- stupci i treba ih analizirati "s desna na lijevo"!

3) I u završnoj fazi ispunite posljednji stupac. I ovdje je zgodno razmišljati ovako: "Ako su u stupcima dvije jedinice, onda stavljamo jednu, u svim ostalim slučajevima - nulu".

Na kraju provjeravamo tablicu istinitosti ekvivalenti .

Osnovne ekvivalencije propozicijske algebre

Upravo smo ih upoznali s dvojicom, ali, naravno, stvar 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 li promjenjivost:

Pravila poznata iz 1. razreda: "Proizvod (zbroj) se ne mijenja od permutacije faktora (pojmova)"... Ali uz svu prividnu elementarnost ovog svojstva, ono nije uvijek točno, posebice je nekomutativno. množenje matrice (općenito, ne mogu se preurediti), a vektorski umnožak vektora- antikomutativno (permutacija vektora podrazumijeva promjenu predznaka).

A osim toga, ovdje ponovno ž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žajnog gledišta, ali se ne može razlikovati sa stajališta formalne istine. ... Svatko od nas poznaje takve studente, a iz etičkih razloga nećemo izgovarati konkretna imena =)

Asocijativnost logičkog množenja i zbrajanja

Ili, ako je "na školski način" - svojstvo kombinacije:

Distributivna svojstva

Imajte na umu da će u drugom slučaju biti netočno govoriti o "otvarajućim zagradama", u određenom smislu ovdje je "fikcija" - uostalom, oni se mogu potpuno ukloniti: budući da množenje je jača operacija.

I opet - ova naizgled "banalna" svojstva nisu ispunjena u svim algebarskim sustavima, i, štoviše, zahtijevaju dokaz (o čemu ćemo vrlo brzo)... Inače, drugi distributivni zakon ne vrijedi ni u našoj "uobičajenoj" algebri. A zapravo:

Zakon idempotencije

Što da radiš, latino...

Izravno neki princip zdrave psihe: "ja i ja sam ja", "ja ili ja sam također ja" =)

Zatim postoji nekoliko sličnih identiteta:

... hmm, nešto na što sam se čak i zaglavio ... pa se sutra probudiš s doktorom filozofije =)

Zakon dvostruke negacije

Eto, ovdje se već nagovještava primjer s ruskim jezikom - svi savršeno dobro znaju da dvije čestice "ne" znače "da". A kako bi se pojačala emocionalna boja poricanja, često se koriste tri "ne":
- čak i sa sićušnim dokazom uspjelo je!

Zakoni apsorpcije

- "Je li postojao dječak?" =)

U pravom identitetu zagrade se mogu izostaviti.

De Morganovi zakoni

Pretpostavimo da je strogi Učitelj (čije ime također 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, ekvivalentnosti su podložne dokazu, koji se provodi na standardni način pomoću tablica istinitosti. Zapravo, već smo dokazali ekvivalentnosti koje izražavaju implikaciju i ekvivalenciju, a sada je vrijeme da konsolidiramo tehniku ​​rješavanja ovog problema.

Dokažimo identitet. Budući da sadrži jednu naredbu, moguće su samo dvije opcije "na ulazu": jedan ili nula. Zatim dodjeljujemo jedan stupac i primjenjujemo na njih pravilo I:

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

Da, ovaj dokaz je primitivan (a netko će reći da je i to "glupo"), ali tipični učitelj matologije će mu se istresti. Stoga ni tako jednostavne stvari ne treba shvaćati olako.

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

Prvo, napravimo tablicu istine za lijevu stranu. Budući da je disjunkcija u zagradama, prvo je izvršimo, nakon čega negiramo stupac:

Zatim napravimo tablicu istine za desnu stranu. I ovdje je sve transparentno - prije svega provodimo više "jakih" negacija, a zatim se primjenjujemo na stupce pravilo I:

Rezultati se poklapaju, pa je identitet dokazan.

Bilo koja ekvivalentnost može se predstaviti kao identično pravoj formuli... Znači da ZA BILO KOJI originalni skup nula i jedinica"Na izlazu" se dobiva strogo jedan. A za to postoji vrlo jednostavno objašnjenje: budući da su tablice istinitosti i iste, onda su, naravno, ekvivalentne. Kombinirajmo, na primjer, ekvivalentom lijevu i desnu stranu upravo dokazanog de Morganovog identiteta:

Ili, ako je kompaktniji:

Zadatak 2

Dokažite sljedeće ekvivalentnosti:

b)

Kratko rješenje na kraju tutoriala. Nismo lijeni! Pokušajte ne samo sastaviti tablice istine, već i jasno formulirati zaključke. Kao što sam nedavno primijetio, zanemarivanje jednostavnih stvari može biti vrlo, vrlo skupo!

Nastavljamo se upoznavati sa zakonima logike!

Da, tako je - već radimo s njima na sve načine:

Pravi na Zove se identično pravoj formuli ili zakon logike.

Na temelju prethodno opravdanog prijelaza s ekvivalencije na identično istinitu formulu, svi gore navedeni identiteti su zakoni logike.

Formula koja preuzima Laž na bilo koji skup vrijednosti varijabli uključenih u njega Zove se identično po lažnoj formuli ili kontradikcija.

Vlasnički primjer kontradikcije starih Grka:
- nijedna izjava ne može biti istinita i lažna u isto vrijeme.

Dokaz je trivijalan:

Samo nule se primaju "na izlazu", dakle, formula vrijedi identično lažno.

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

Nemoguće je obraditi tako opsežnu temu u jednom članku, stoga ću se ograničiti na još nekoliko zakona:

Zakon isključenog trećeg

- u klasičnoj logici, bilo koja izjava je istinita ili lažna, a treće nema. “Biti ili ne biti” je pitanje.

Sami nacrtajte ploču istine i uvjerite se da je identično istinito formula.

Zakon kontrapozicije

O ovom zakonu se aktivno raspravljalo kada smo raspravljali o suštini potrebno stanje, zapamtiti: "Ako je vlažno za vrijeme kiše, onda slijedi da ako je vani suho, onda sigurno nije padala kiša".

Iz ovog zakona također proizlazi da ako je pošteno ravno teorema, zatim izjava, koja se ponekad naziva suprotan teorema.

Ako je istina obrnuto teorem, onda na temelju zakona kontrapozicije, teorem također vrijedi, suprotno obrnuto:

I opet, vratimo se našim informativnim primjerima: za izjave - broj je djeljiv sa 4, - broj je djeljiv sa 2 pravedan ravno i suprotan teoremi ali lažni obrnuto i suprotno obrnuto teoremi. Za "odraslu" formulaciju Pitagorinog teorema, sva 4 "smjera" su istinita.

Zakon silogizma

Također klasici žanra: "Svi hrastovi su drveće, sva stabla su biljke, dakle, svi hrastovi su 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 s formalne točke gledišta ovaj učenik svakako biljka =) ... iako, ako razmislite o tome, pa možda i s neformalnim = )

Sastavimo tablicu istinitosti za formulu. U skladu s prioritetom logičkih operacija, pridržavamo se sljedećeg algoritma:

1) provodimo implikacije i. Općenito govoreći, možete odmah izvršiti 3. implikaciju, ali je s njom prikladnije (i dopušteno!) shvatiti malo kasnije;

2) primijeniti na stupce pravilo I;

3) sada radimo;

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

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


Iz zadnje kolumne mislim da je sve jasno bez komentara:
, po potrebi.

Zadatak 3

Saznajte hoće li sljedeća formula biti zakon logike:

Kratko rješenje na kraju tutoriala. Da, i skoro sam zaboravio – dogovorimo se da početne skupove nula i jedinica navedemo potpuno istim redoslijedom kao u dokazu zakona silogizma. Naravno, linije se mogu preurediti, ali to će uvelike zakomplicirati usporedbu s mojim rješenjem.

Pretvaranje Booleovih formula

Uz njihovu "logičku" svrhu, ekvivalencije se naš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čnoj formuli, onda ga, prema zakonu idempotencije, možete (i trebate) jednostavno napisati umjesto njega. Ako vidite, onda po zakonu apsorpcije, pojednostavite unos. itd.

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

, gdje ih ima (ma koliko komplicirano) formule.

Transformirajmo, na primjer, složenu implikaciju (1. identitet):

Zatim na zagradu primjenjujemo "složeni" de Morganov zakon, dok je, zbog prioriteta operacija, zakon gdje :

Nosači se mogu ukloniti kao unutra je "jači" veznik:

Pa, s komutativnošću općenito, sve je jednostavno - ne trebate ništa ni označavati ... zakon silogizma mi je za nešto upao u dušu :))

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

Izgovorite naglas logički lanac "s hrastom, stablom, biljkom", i shvatit ćete da se značenje zakona nije nimalo promijenilo od prestrojavanja implikacija. Možda je formulacija postala originalnija.

Kao trening, pojednostavimo formulu.

Gdje početi? Prije svega, razumjeti redoslijed radnji: ovdje se negacija primjenjuje na cijelu zagradu, koja je "nešto slabijim" veznikom "pričvršćena" za iskaz. U biti, imamo pred sobom logičan proizvod dva čimbenika:. Od dvije preostale operacije, implikacija ima najniži prioritet, te stoga cijela formula ima sljedeću strukturu:.

U pravilu se prvi korak(i) oslobađaju ekvivalencije i implikacije (ako jesu) i svesti formulu na tri glavne logičke operacije. Što možeš reći…. Logično je.

(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 ikone "obične" jednakosti:

(2) Primjenjujemo de Morganov zakon na vanjske zagrade, gdje.

Asocijativnost

x 1 (x 2 x 3) = (x 1 x 2) x 3;

x 1 Ú (x 2 Ú x 3) = (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) = 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)

Dvaput ne

Konstantna svojstva

x & 1 = x; (zakoni univerzalnog skupa)

x & 0 = 0; (zakoni nultog skupa)

De Morganova pravila (zakoni)

Zakon kontradikcije (komplementarnosti).

Treći (komplementarni) zakon o isključenju

Dokazi svih ovih formula su trivijalni. Jedna od mogućnosti je sastaviti tablice istine za lijevu i desnu stranu i usporediti ih.

Pravila vezanja

Pravilo lijepljenja za elementarne konjunkcije slijedi iz zakona distribucije, 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 zbrojeve slijedi iz zakona raspodjele druge vrste, zakona komplementarnosti i zakona nultog skupa: spoj dviju susjednih rečenica može se zamijeniti jednom osnovnom rečenicom, koja je zajednički dio izvornih klauzula .

Pravilo apsorpcije

Pravilo apsorpcije za zbroj dvaju elementarnih proizvoda slijedi iz zakona raspodjele prve vrste i zakona univerzalnog skupa: disjunkcija dviju elementarnih veznika, od kojih je jedna sastavni dio druge, može se zamijeniti konjunkcijom s manjim brojem operanada .

Pravilo apsorpcije za umnožak elementarnih zbroja slijedi iz zakona distribucije druge vrste i zakona nultog skupa: konjunkcija dviju elementarnih disjunkcija, od kojih je jedna sastavni dio druge, može se zamijeniti elementarnom disjunkcijom s manjim brojem operanada.

Pravilo raspoređivanja

Ovo pravilo definira obrnuto djelovanje lijepljenja.

Pravilo za odvijanje elementarnog proizvoda u logički zbroj elementarnih proizvoda višeg ranga (do r = n, tj. do konstituenata jedinice, kako će biti riječi u nastavku) slijedi iz zakona univerzalnog skupa, distribucija zakon prve vrste i izvodi se u tri faze:

U proširivi elementarni umnožak ranga r uvodi se kao faktori n-r jedinica, gdje je n rang konstituenta jedinice;

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

Sve zagrade su proširene na temelju zakona raspodjele prve vrste, što dovodi do proširenja početnog elementarnog proizvoda ranga r u logički zbroj od 2 n-r konstituenta jedinice.

Pravilo odvijanja elementarnog proizvoda koristi se za minimiziranje funkcija Booleove algebre (FAL).

Pravilo proširenja elementarnog zbroja ranga r na umnožak elementarnih zbroja ranga n (konstituenti nule) slijedi njihove zakone nultog skupa (6) i zakona distribucije druge vrste (14) i izvodi se u tri faze:

U proširivom zbroju ranga r, n-r nula se uvode kao članovi;

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

Dobiveni izraz se transformira na temelju zakona distribucije druge vrste (14) tako da se početni zbroj ranga r pretvara u logički umnožak 2 n-r konstituenta nule.

16. Koncept cjelovitog sustava. Primjeri kompletnih sustava (s dokazom)

Definicija. Skup Booleovih funkcija A naziva se potpuni sustav (u P2) ako se bilo koja Booleova funkcija može izraziti formulom nad A.

Sustav funkcija A = ( f 1, f 1, ..., f m) koji je potpun naziva se osnovu.

Minimalna osnova je osnova za koju se uklanja barem jedna funkcija f 1 formiranje ove osnove transformira sustav funkcija (f 1, f 1, ..., f m) nepotpun.

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

Dokaz. Ako je funkcija algebre logike f drugačija od identične nule, tada se f izražava u obliku savršenog disjunktivnog normalnog oblika, koji uključuje samo disjunkciju, konjunkciju i negaciju. Ako je f ≡ 0, tada je f = x & x. Teorem je dokazan.

Lema. Ako je sustav A potpun, a bilo koja funkcija sustava A može se izraziti formulom preko nekog drugog sustava B, tada je B također potpuni sustav.

Dokaz. Razmotrimo proizvoljnu funkciju algebre logike f (x 1,…, x n) i dva sustava funkcija: A = (g 1, g 2,…) i B = (h 1, h 2,…). Budući da je sustav A potpun, funkcija f se može izraziti kao formula 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. Prolazeći kroz sve funkcije Booleove algebre na ovaj način, dobivamo da je i sustav B potpun. Lema je dokazana.

Teorema. Sljedeći sustavi su potpuni u P 2:

4) (&, ⊕, 1) Zhegalkinova baza.

Dokaz.

1) Poznato je (teorem 3) da je sustav A = (&, V,) potpun. Pokažimo da je sustav B = (V, potpun. Doista, iz de Morganovog zakona (x & y) = (x ∨ y) dobivamo da je x & y = (x ∨ y), odnosno da je konjunkcija izraženo kroz disjunkciju i negaciju, a sve funkcije sustava A izražene su formulama nad sustavom B. Prema lemi, sustav B je potpun.

2) Slično točki 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 sustav je potpun.

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

Teorem je dokazan.

17. Žegalkinova algebra. Svojstva i cjelovitost operacije

Skup Booleovih funkcija definiranih u Zhegalkinovoj bazi S4 = (⊕, &, 1) naziva se Zhegalkinova algebra.

Osnovna svojstva.

1. promjenjivost

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. svojstva konstanti

5.h⊕h = 0 h & h = h
Izjava... Sve ostale Booleove funkcije mogu se izraziti kroz operacije Zhegalkinove algebre:

x → y = 1⊕x⊕xy

x ↓ y = 1⊕x⊕y⊕xy

18.Polynom Zhegalkina. Metode gradnje. Primjer.

Žegalkinov polinom (polinom po modulu 2) u 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 Zhegalkinov polinom ne sadrži produkte zasebnih varijabli, tada se naziva linearna (linearna funkcija).

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

Teorema... Svaka Booleova funkcija je jedinstveno predstavljena kao Zhegalkin polinom.

Ovdje su glavne metode za konstruiranje Zhegalkinovih polinoma u danoj funkciji.

1. Metoda nedefiniranih koeficijenata. Neka je P (x 1, x 2 ... x n) traženi Zhegalkin polinom koji ostvaruje zadanu funkciju f (x 1, x 2 ... x n). Zapišimo to u obrazac

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

Pronađite koeficijente C k. Da bismo to učinili, sekvencijalno dodjeljujemo vrijednosti varijabli x 1, x 2 ... x n iz svakog retka tablice istinitosti. Kao rezultat, dobivamo sustav od 2 n jednadžbi s 2 n nepoznanica, koji ima jedinstveno rješenje. Nakon što smo ga riješili, nalazimo koeficijente polinoma P (X 1, X 2 ... X n).

2. Metoda koja se temelji na transformaciji formula preko skupa spojnica (, &). Napravite formulu F nad skupom spojnica (, &), ostvarujući zadanu funkciju f (X 1, X 2 ... X n). Zatim, posvuda zamijenite podformule oblika A s A⊕1, proširite zagrade koristeći distributivni zakon (vidi svojstvo 3), a zatim primijenite svojstva 4 i 5.

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

Riješenje.
1. (metoda nedefiniranih koeficijenata). Napišimo traženi polinom u obliku:

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

Koristeći tablicu istinitosti implikacije, nalazimo 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 transformacije formula.). Imamo: x → y = xvy = (xy) = (x (y⊕1)) ⊕1 = 1⊕x⊕xy
Imajte na umu da prednost Zhegalkinove algebre (u usporedbi s drugim algebrama) leži u aritmetizaciji logike, što omogućuje vrlo jednostavno izvođenje transformacija Booleovih funkcija. Njegov nedostatak u usporedbi s Booleovom algebrom je glomaznost formula.

Slične informacije.

Razmatrane operacije nad skupovima podliježu određenim zakonima koji nalikuju dobro poznatim elementarnim zakonima algebre brojeva. Ovo definira naziv algebra skupova, koji se često naziva Booleovom algebrom skupova, što se povezuje s imenom engleskog matematičara Johna Boolea, koji je svoje logičke studije temeljio na ideji analogije između algebre i logike.

Za proizvoljne skupove A, B i C vrijede sljedeći identiteti (tablica 3.1):

Tablica 3.1

1. Zakon identiteta
2. Komutativnost unije	2 '. Komutativnost presjeka
3. Asocijativnost udruženja	3 '. Asocijativnost raskrižja
4. Distributivnost unije s obzirom na sjecište	4'. Distributivnost presjeka u odnosu na uniju
5. Zakoni djelovanja s praznim i univerzalni U skupovi (zakon isključenog trećeg)	5'. Zakoni djelovanja s praznim i univerzalni U skupovi (zakon kontradikcije)
6. Zakon idempotencije udruživanja	6 '. Zakon idempotencije raskrižja
7. De Morganov zakon	7 '. De Morganov zakon
8. Zakon eliminacije (apsorpcije)	osam'. Eliminacijski (apsorpcijski) zakon
9. Zakon lijepljenja	devet'. Zakon o vezivanju
10. Poretskyjev zakon	deset'. Poretskyjev zakon
11. Zakon involucije (dvostruki komplement)

Zakoni algebre skupova s ​​obzirom na operacije presjeka () i unije () podliježu načelu dualnosti: ako su u bilo kojem zakonu svi znakovi presjeka zamijenjeni znakovima unije, a svi znakovi unije znakovima presjeka, znak svemira (U) zamjenjuje se znakom praznog skupa (Ø), a prazan znak je znak svemira, tada opet dobivamo ispravan identitet. Na primjer (na temelju ovog principa), proizlazi iz itd.

3.1. Testiranje istinitosti identiteta pomoću Euler-Venn dijagrama

Svi zakoni algebre skupova mogu se vizualizirati i dokazati korištenjem Euler-Venn dijagrama. Za to je potrebno:

Nacrtajte odgovarajući dijagram i osjenčite sve skupove na lijevoj strani jednakosti.

Nacrtajte drugi dijagram i učinite isto za desnu stranu jednadžbe.

Ovaj identitet je istinit ako i samo ako je isto područje zasjenjeno na oba dijagrama.

Napomena 3.1. Dvije kružnice koje se sijeku dijele cijeli univerzalni skup na četiri područja (vidi sliku 3.1)

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

Napomena 3.2. Prilikom snimanja uvjeta različitih primjera često se koristi oznaka:

 - iz ... slijedi ...;

 - ako i samo ako….

Zadatak 3.1 ... Pojednostavite izraze algebre skupa:

Riješenje.

Zadatak 3 .2 ... Dokažite identitete:

(AB) \ B \ u003d A \ B;

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

Riješenje.

Zadatak 3.3 ... Dokažite sljedeće odnose na dva načina: pomoću dijagrama i pomoću definicije jednakosti skupova.

Riješenje.

2. Dokaz korištenjem definicije jednakosti skupova.

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

Pokažimo to prvo
... Neka bude NS- proizvoljan element skupa
, to je NS
... Znači da NSU i NS
... Otuda slijedi da NSA ili NSV. Ako NSA, dakle NSĀ, što znači
... Ako NSB, dakle
, što znači
... Dakle, svaki element skupa.
... je također element skupa
To je

Dokažimo sada suprotno, to jest
... Neka bude
... Ako NSĀ, dakle NSU i NSA, što znači NSAV. Otuda slijedi da
... Ako
, onda NSU i NSV. Sredstva, NSAV, tj
... Otuda slijedi da je svaki element skupa
je također element skupa
, to je
.

Sredstva,
, po potrebi.

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

1. Dokaz dijagramom:

Neka bude NSA (VS). Zatim NSA i NSVS. Ako NSB, dakle NSAV, što nije u suprotnosti s izrečenim, što znači da NS (AV)  (AS). Ako NSS, dakle NSAS. Stoga, NS (AB)  (AC). Dakle, dokazali smo da je A (BC)  (AB)  (AC.

Neka sada NS (AB)  (AC). Ako NSAV, dakle NSA i NSV. Otuda slijedi da NSA i NSVS, tj NSA (VS). Ako NSAS, dakle NSA i NSC. Otuda slijedi da NSA i NSVS, tj NSA (VS). Dakle, (AB)  (AC)  A (BC). Stoga je A (BC) = (AB)  (AC). Q.E.D.

U dokazivanju dovoljnosti dobili smo da je AB = . Očito, C, pa je relacija dokazana. U dokazu je razmatran najopćenitiji slučaj. Međutim, ovdje su moguće još neke opcije prilikom konstruiranja dijagrama. Na primjer, slučaj jednakosti AB = C ili
, slučaj praznih skupova i tako dalje. Očito, može biti teško uzeti u obzir sve moguće opcije. Stoga se vjeruje da dokaz relacija pomoću dijagrama nije uvijek točan.

2. Dokaz korištenjem definicije jednakosti skupova.

Potreba. Neka AVS i element NSA. Pokažimo da će u ovom slučaju element skupa A također biti element skupa
.

Razmotrimo dva slučaja: NSB ili
.

Ako NSB, dakle NSAVS, tj NSS, i kao posljedica toga,
.

Ako
, onda
... Potreba je dokazana.

Neka sada
i NSAV. Pokažimo da je element NS također će biti element skupa C.

Ako NSAV, dakle NSA i NSV. Ukoliko
, sredstva NSC. Dovoljnost je dokazana.

1. Dokaz dijagramom:

2. Dokaz korištenjem definicije jednakosti skupova.

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

Zadatak 3.4. Izrazite označena područja simbolički i pojednostavnite rezultirajuće izraze.

Riješenje.

Područje pretraživanja sastoji se od dva izolirana dijela. Nazovimo ih konvencionalno gornjim i donjim. Mnoštvo koje oni predstavljaju može se opisati na sljedeći način:

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

Iz definicije operacija nad skupovima dobivamo:

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

Napišimo ovaj izraz koristeći osnovne operacije - komplementar, unija i presjek:

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

Ovo područje se može smatrati unijom skupova A \ B \ C i ABC. Po definiciji, M = ( x xA i xB i NSC ili NSA i NSB i NSC). Pojednostavimo:

Zadaci za samostalno rješenje.

1. Pojednostaviti:

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

(AB) \ B \ u003d A \ B;

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

AV = AV  A = V;

A \ B =   AB = A.

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

AX = A; (odgovor );

De Morganovi zakoni su logička pravila koja je ustanovio škotski matematičar Augustus de Morgan koja povezuju parove logičkih operacija pomoću logičke negacije.

Augustus de Morgan je primijetio da su u klasičnoj logici istiniti sljedeći odnosi:

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

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

U nama poznatijem obliku, ti se omjeri mogu zapisati u sljedećem obliku:



De Morganovi zakoni se mogu formulirati na sljedeći način:

I de Morganov zakon: Poricanje disjunkcije dviju jednostavnih iskaza jednako je konjunkciji negacija tih izjava.

II de Morganov zakon: Poricanje spoja dviju jednostavnih tvrdnji jednako je disjunciji negacija tih iskaza.

Razmotrimo primjenu de Morganovih zakona na konkretnim primjerima.

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

Koristeći prvi de Morganov zakon, dobivamo:

da negiramo konjunkciju jednostavnih iskaza B i C, primjenjujemo drugi de Morganov zakon, dobivamo:

,

Tako:

.

Kao rezultat, dobili smo ekvivalentnu izjavu, u kojoj nema poricanja složenih iskaza, a sve negacije se odnose samo na jednostavne iskaze.

Valjanost odluke možete provjeriti pomoću tablica istinitosti. Da bismo to učinili, sastavit ćemo tablice istinitosti za izvornu izjavu:

i za izjavu dobivenu kao rezultat transformacija izvedenih uz pomoć de Morganovih zakona:

.

Stol 1.

			B / \ C	A \ / B / \ C



Kao što možete vidjeti iz tablica, izvorni logički iskaz i logički iskaz dobiven korištenjem de Morganovih zakona su ekvivalentni. O tome svjedoči činjenica da smo u tablicama istinitosti dobili iste skupove vrijednosti.