Fazni i nasumični skupovi. Apsorpcija, lijepljenje i de Morganove teoreme Dokazati jedan od De Morganovih zakona

Razmatrane operacije nad skupovima podliježu određenim zakonima koji liče na dobro poznate elementarne zakone algebre brojeva. Ovo određuje ime set algebra, koji se često naziva Booleovom algebrom skupova, š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 vrijede 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 sjecišta zamijenjeni znakovima unije, a svi znakovi unije su zamijenjeni znakovima sjecišta , znak univerzuma (U) se zamjenjuje znakom praznog skupa (Ø), a znak praznog je znak univerzuma, tada opet dobijamo ispravan identitet. Na primjer (na osnovu ovog principa), slijedi, 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. Da biste to uradili potrebno vam je:

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

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

Ovaj identitet je istinit ako i samo ako je ista oblast zasjenjena u 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 snimanja uslova razni primjeriČesto se koriste notacije:

 - iz... slijedi...;

 - ako i samo ako… .

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

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

Rješenje.

2. Dokaz korištenjem definicije jednakosti skupova.

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

Prvo ćemo to pokazati
. Neka X– proizvoljan element skupa
, to je X
. To znači da XU i X
. Iz ovoga proizilazi da XA ili XB. Ako XOh, onda XĀ, što znači
. Ako XB, dakle
, što znači
. Dakle, svaki element skupa.
. je također element skupa
To je

Sada ćemo dokazati suprotno, to jest
. Neka
. Ako XĀ, dakle XU i XA to znači XAB. Iz toga slijedi
. Ako
, To 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 pomoću dijagrama:

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

Pusti to sada X (AB)(AC). Ako XAB, dakle XA i XB. Iz toga slijedi XA i XVS, tj XA(BC). Ako XAS, dakle XA i XS. Iz ovoga proizilazi da 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 utvrdili smo da je AB=. Očigledno je da je S, pa je veza dokazana. U dokazu je razmatran najopštiji slučaj. Međutim, moguće su i neke druge opcije prilikom konstruisanja dijagrama. Na primjer, slučaj jednakosti AB=C ili
, slučaj praznih skupova i tako dalje. Očigledno, može biti teško uzeti u obzir sve moguće opcije. Stoga se vjeruje da dokazivanje odnosa pomoću dijagrama nije uvijek ispravno.

2. Dokaz korištenjem definicije jednakosti skupova.

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

Razmotrimo dva slučaja: XB ili
.

Ako XB, dakle XABC, tj XC i, kao posljedica toga,
.

Ako
, onda
. Potreba je dokazana.

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

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

1. Dokaz pomoću dijagrama:

2. Dokaz korištenjem definicije jednakosti skupova.

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

Problem 3.4. Izrazite označena područja simbolički i pojednostavite rezultirajuće izraze.

Rješenje.

Željeno područje se sastoji od dva izolirana dijela. Nazovimo ih gornji i donji. Skup koji oni predstavljaju 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B i XC ili XA i XU i XC). Hajde da pojednostavimo:

Problemi 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 = AB  A=B;

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

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

AX = A; (odgovor );

Poglavlje 8 ispitalo je takve tipove objekata nenumeričke prirode kao što su rasplinuti i slučajni skupovi. Svrha ove aplikacije je da dublje prouči svojstva rasplinutih skupova i pokaže da teorija rasplinutih skupova u u određenom smislu svodi na teoriju slučajnih skupova. Da bi se postigao ovaj cilj, formulisan je i dokazan lanac teorema.

U nastavku se pretpostavlja da su svi rasplinuti skupovi koji se razmatraju podskupovi istog skupa Y.

P2-1. De Morganovi zakoni za rasplinute skupove

Kao što je poznato, sljedeći identiteti algebre skupova nazivaju se Morganovi zakoni

Teorema 1.Za rasplinute skupove vrijede sljedeći identiteti:

(3)

Dokaz teoreme 1 sastoji se od direktne provjere valjanosti relacija (2) i (3) izračunavanjem vrijednosti funkcija pripadnosti rasplinutih skupova uključenih u ove relacije na osnovu definicija datih u 8. poglavlju.

Nazovimo identitete (2) i (3) De Morganovi zakoni za rasplinute skupove. Za razliku od klasičnog slučaja relacija (1), one se sastoje od četiri identiteta, od kojih se jedan par odnosi na operacije unije i presjeka, a drugi na operacije proizvoda i zbira. Poput relacije (1) u algebri skupova, de Morganovi zakoni u algebri rasplinutih skupova omogućavaju transformaciju izraza i formula koje uključuju operacije negacije.

P2-2. Distributivni zakon za rasplinute skupove

Neka svojstva skupova operacija ne vrijede za rasplinute skupove. Da, osim kada A- "oštar" skup (tj. funkcija članstva uzima samo vrijednosti 0 i 1).

Da li je distributivni zakon istinit za rasplinute skupove? U literaturi se ponekad nejasno navodi da „ne uvijek“. Budimo potpuno jasni.

Teorema 2.Za bilo koje rasplinute skupove A, B i C

U isto vrijeme jednakost

pošteno ako i samo ako, za sve

Dokaz. Popravi proizvoljan element. Da bismo skratili zapis, označavamo Da bismo dokazali identitet (4), potrebno je to pokazati

Razmotrite različite redoslijed tri broja a, b, c. Neka je prva Tada lijeva strana relacije (6) a desna strana, tj. jednakost (6) je tačna.

Neka je Tada na relaciji (6) lijevo a desno, tj. relacija (6) je opet jednakost.

Ako je tada na relaciji (6) lijevo i desno, tj. oba dijela se ponovo poklapaju.

Tri preostale narudžbe brojeva a, b, c nema potrebe za rastavljanjem, jer su u odnosu (6) brojevi b I c ulazite simetrično. Identitet (4) je dokazan.

Druga tvrdnja teoreme 2 proizilazi iz činjenice da je, u skladu sa definicijama operacija nad rasplinutim skupovima (vidi Poglavlje 8)

Ova dva izraza se poklapaju ako i samo ako, kada, ono što je trebalo dokazati.

Definicija 1.Nosač rasplinutog skupa A je skup svih tačaka , za koji

Korolar teoreme 2.Ako se nosioci rasplinutih skupova B i C poklapaju sa Y, onda jednakost (5) vrijedi ako i samo ako je A „oštar” (tj. običan, klasičan, a ne rasplinut) skup.

Dokaz. Po stanju pred svima. Tada iz teoreme 2 slijedi da one. ili , što znači da A- jasan set.

P2-3. Fazni skupovi kao projekcije slučajnih skupova

Od samog početka moderna teorija 1960-ih se o nejasnoći počelo raspravljati o njenom odnosu sa teorijom vjerovatnoće. Činjenica je da funkcija pripadnosti rasplinutog skupa liči na raspodjelu vjerovatnoće. Jedina razlika je u tome što je zbroj vjerovatnoća nad svim mogućim vrijednostima slučajne varijable (ili integrala, ako je skup mogućih vrijednosti nebrojiv) uvijek jednak 1, a zbir S Vrijednosti funkcije pripadnosti (u kontinuiranom slučaju - integral funkcije članstva) mogu biti bilo koji nenegativan broj. Postoji iskušenje normalizacije funkcije članstva, tj. podijeliti sve njegove vrijednosti sa S(kod S 0) da se svede na distribuciju verovatnoće (ili gustinu verovatnoće). Međutim, stručnjaci za fuzziness s pravom prigovaraju takvoj „primitivnoj“ redukciji, budući da se ona provodi posebno za svaki fuzziness (fazi skup), a definicije običnih operacija nad rasplinutim skupovima ne mogu biti konzistentne s njim. Posljednja izjava znači sljedeće. Neka se funkcije pripadnosti rasplinutih skupova transformišu u skupove naznačenih načina A I IN. Kako se transformiraju funkcije članstva? Instalirajte ovo u principu nemoguće. Posljednja tvrdnja postaje potpuno jasna nakon razmatranja nekoliko primjera parova rasplinutih skupova s ​​istim zbrojima vrijednosti funkcija pripadnosti, ali različitim rezultatima teoretskih operacija na njima i sumama vrijednosti odgovarajućih funkcija pripadnosti jer su ovi rezultati teoretskih operacija, na primjer, za sjecišta skupova također različiti.

U radovima o rasplinutim skupovima prilično se često navodi da je teorija rasplinutosti samostalna grana primijenjene matematike i da nije povezana s teorijom vjerovatnoće (vidi, na primjer, pregled literature u monografijama). Autori koji su upoređivali fuzzy teoriju i teoriju vjerovatnoće obično su isticali razliku između ovih područja teorijskog i primijenjenog istraživanja. Obično se uspoređuje aksiomatika i upoređuju se područja primjene. Odmah treba napomenuti da argumenti za drugu vrstu poređenja nemaju dokaznu snagu, budući da postoje različita mišljenja o granicama primjenjivosti čak i tako davno utemeljene naučne oblasti kao što su probabilističke statističke metode. Podsjetimo, rezultat rasuđivanja jednog od najpoznatijih francuskih matematičara Henrija Lebesguea o granicama primjenjivosti aritmetike je sljedeći: „Aritmetika je primjenjiva kada je primjenjiva“ (vidi njegovu monografiju).

Kada se porede različite aksiomatike fuzzy teorije i teorije verovatnoće, lako je uočiti da se liste aksioma razlikuju. Iz ovoga, međutim, uopće ne slijedi da se ne može uspostaviti veza između ovih teorija, kao što je dobro poznata redukcija euklidske geometrije na ravni na aritmetiku (tačnije, na teoriju brojevnog sistema - vidi, na primjer, monografija). Podsjetimo da su ove dvije aksiomatike - euklidska geometrija i aritmetika - na prvi pogled vrlo različite.

Može se razumjeti želja entuzijasta novog pravca da naglase temeljnu novinu svog naučnog aparata. Međutim, podjednako je važno uspostaviti veze između novog pristupa i ranije poznatih.

Kako se ispostavilo, teorija rasplinutih skupova je usko povezana sa teorijom slučajnih skupova. Još 1974. godine u radu je pokazano da se rasplinuti skupovi prirodno mogu smatrati „projekcijama“ slučajnih skupova. Razmotrimo ovu metodu svođenja teorije rasplinutih skupova na teoriju slučajnih skupova.

Definicija 2.Neka - slučajni podskup konačnog skupa Y. Fazi skup B definisan na Y naziva se projekcija A i označava se kao Proj A ako

(7)

pred svima

Očigledno, svaki nasumični skup A može biti u korelaciji pomoću formule (7) sa rasplinutim skupom B = Proj A. Ispostavilo se da je i suprotno.

Teorema 3. Za bilo koji rasplinuti podskup B konačnog skupa Y, postoji slučajni podskup A od Y takav da je B = Proj A.

Dokaz. Dovoljno je podesiti raspodjelu slučajnog skupa A. Neka U 1- nosač IN(vidi definiciju 1 gore). Bez gubljenja opštosti možemo to pretpostaviti kod nekih m i elementi U 1 numerisana takvim redosledom da

Hajde da predstavimo skupove

Za sve ostale podskupove X setovi U stavimo P(A=X)=0. Od elementa y t uključeno u set Y(1), Y(2),…, Y(t) i nije uključen u setovi Y(t+1),…, Y(m), To Iz gornjih formula proizilazi da Ako je onda, očigledno, teorema 3 dokazana.

Raspodjela slučajnog skupa sa nezavisnim elementima, kao što slijedi iz razmatranja u poglavlju 8, u potpunosti je određena njegovom projekcijom. Za konačan slučajni skup opšte forme to nije slučaj. Da bismo razjasnili gore navedeno, potrebna nam je sljedeća teorema.

Teorema 4. Za slučajni podskup A skupa Y iz konačnog brojevi elemenata skupovi brojeva I izražavaju se jedno kroz drugo.

Dokaz. Drugi skup se izražava u terminima prvog na sljedeći način:



Elementi prvog skupa mogu se izraziti kroz drugi pomoću formule uključivanja i isključenja iz formalne logike, prema kojoj

U ovoj formuli u prvom zbroju at prolazi kroz sve elemente skupa Y\X, u drugom zbroju varijable sumiranja u 1 I u 2 ne poklapaju se i takođe prolaze kroz ovaj skup, itd. Pozivanje na formulu uključivanja i isključenja dovršava dokaz teoreme 4.

U skladu sa teoremom 4, slučajni skup A može se okarakterisati ne samo distribucijom, već i skupom brojeva U ovom skupu nema drugih relacija tipa jednakosti. Ovaj skup uključuje brojeve; stoga je fiksiranje projekcije slučajnog skupa ekvivalentno fiksiranju k = kartica (Y) parametri iz (2k-1) parametri koji definiraju distribuciju slučajnog skupa A Uglavnom.

Sljedeća teorema će biti korisna.

Teorema 5. Ako Projekt A = B, To

Da bismo to dokazali, dovoljno je koristiti identitet iz teorije slučajnih skupova, formulu za vjerovatnoću pokrivanja iz poglavlja 8, definiciju negacije rasplinutog skupa i činjenicu da je zbir svih P(A= X) je jednako 1.

P2-4. Presjeci i proizvodi rasplinutih i slučajnih skupova

Hajde da saznamo kako se operacije nad slučajnim skupovima odnose na operacije nad njihovim projekcijama. Na osnovu De Morganovih zakona (teorema 1) i teorema 5, dovoljno je razmotriti operaciju preseka slučajnih skupova.

Teorema 6. Ako su nasumični podskupovi A 1 i A 2 konačnog skupa y su nezavisne, a zatim rasplinuti skup je djelo rasplinuti skupovi Proj A 1 i Proj A 2 .

Dokaz. Mora se pokazati da za bilo koje

Prema formuli za vjerovatnoću pokrivanja tačke slučajnim skupom (poglavlje 8)

Kao što je poznato, distribucija presjeka slučajnih skupova može se izraziti kroz njihovu zajedničku distribuciju na sljedeći način:

Iz relacija (9) i (10) slijedi da se vjerovatnoća pokrivanja za presjek slučajnih skupova može predstaviti kao dvostruki zbir

Zapazite sada da se desna strana formule (11) može prepisati na sljedeći način:

(12)

Zaista, formula (11) se razlikuje od formule (12) samo po tome što grupiše članove u kojima presjek varijabli sumiranja poprima konstantnu vrijednost. Koristeći definiciju nezavisnosti slučajnih skupova i pravilo za množenje zbira, dobijamo da iz (11) i (12) slijedi jednakost

Da bismo dovršili dokaz teoreme 6, dovoljno je još jednom se osvrnuti na formulu za vjerovatnoću pokrivanja tačke slučajnim skupom (poglavlje 8).

Definicija 3. Podrška za slučajni skup C je skup svih tih elemenata za koji

Teorema 7.Jednakost

istinito ako i samo ako je presjek nosača slučajnih skupova I prazan.

Dokaz. Potrebno je saznati pod kojim uslovima

Tada se jednakost (13) svodi na uvjet

Jasno je da je relacija (14) zadovoljena ako i samo ako p 2 p 3=0 za sve, tj. ne postoji nijedan element koji bi istovremeno I , a to je ekvivalentno praznini presjeka nosača slučajnih skupova i . Teorema 7 je dokazana.

P2-5. Redukcija niza operacija na rasplinutim skupovima

na niz operacija na slučajnim skupovima

Gore smo dobili neke veze između rasplinutih i slučajnih skupova. Vrijedi napomenuti da je proučavanje ovih veza u radu (ovaj rad obavljen 1974. i izvještavan na seminaru „Multidimenzionalni Statistička analiza i probabilističko modeliranje realnih procesa" 18. decembra 1974. - vidi) započeo je uvođenjem slučajnih skupova sa ciljem razvoja i generalizacije aparata rasplinutih skupova od strane L. Zadeha. Činjenica je da matematički aparat rasplinutih skupova ne omogućava da se na adekvatan način uzmu u obzir različite varijante zavisnosti između koncepata (objekata) modeliranih uz njegovu pomoć nije dovoljno fleksibilno. Dakle, za opisivanje „zajedničkog dijela“ dva rasplinuta skupa postoje samo dvije operacije – proizvod i presjek. prvi od njih se primjenjuje, onda se zapravo pretpostavlja da se skupovi ponašaju kao projekcije nezavisnih slučajnih skupova (vidi teoremu 6 gore). Operacija presjeka također nameće dobro definirana ograničenja na tip zavisnosti između skupova (vidi teoremu 7 iznad) , a u ovom slučaju su nađeni čak i potrebni i dovoljni uslovi.Poželjno je imati šire mogućnosti za modeliranje zavisnosti između skupova (koncepta, objekata). Takve mogućnosti pruža upotreba matematičkog aparata slučajnih skupova.

Svrha redukcije fazi skupova na nasumične je da se iza bilo koje konstrukcije rasplinutih skupova vidi konstrukcija slučajnih skupova koja određuje svojstva prvog, na isti način kao što vidimo slučajnu varijablu sa gustinom raspodjele vjerovatnoće. U ovom odeljku predstavljamo rezultate o redukciji algebre rasplinutih skupova na algebru slučajnih skupova.

Definicija 4.Prostor vjerovatnoće { W, G, P)nazivamo ga djeljivim ako za bilo koji mjerljivi skup X G i bilo koji pozitivan broj, manji od P(X), možemo specificirati mjerljiv skup takav da

Primjer. Neka je jedinična kocka konačno-dimenzionalnog linearnog prostora, G je sigma algebra Borelovih skupova, i P- Lebesgueova mjera. Onda { W, G, P)- deljivi prostor verovatnoće.

Dakle, deljivi prostor verovatnoće nije egzotičan. Obična kocka je primjer takvog prostora.

Dokaz tvrdnje formulirane u primjeru izvodi se korištenjem standardnih matematičkih tehnika, zasnovanih na činjenici da se mjerljivi skup može aproksimirati onoliko precizno koliko se želi otvorenim skupovima, pri čemu se potonji predstavljaju kao zbir ne više od prebrojivog broja otvorenih kuglica, a za kuglice se provjerava deljivost direktno (od lopte X tijelo zapremine odvojeno odgovarajućom ravninom).

Teorema 8.Neka je slučajni skup A dat na deljivom prostoru verovatnoće (W, G, P) sa vrijednostima u skupu svih podskupova skupa Y iz konačnog broja elemenata, i rasplinutim skupom D na Y. Tada postoje nasumični skupovi C 1, C 2, C 3, C 4 na istom prostoru vjerovatnoće tako da

gdje je B = Proj A.

Dokaz. Zbog valjanosti De Morganovih zakona za rasplinute (vidi teoremu 1 gore) i za slučajne skupove, kao i gornju teoremu 5 (o negacijama), dovoljno je dokazati postojanje slučajnih skupova C 1 I C 2 .

Razmotrimo distribuciju vjerovatnoće u skupu svih podskupova skupa U, što odgovara slučajnom skupu WITH takav da Projekt C = D(postoji na osnovu teoreme 3). Hajde da napravimo nasumični skup C 2 Isključujemo element samo za istog skupa Y tako da

i, pored toga, rezultati teorijskih operacija skupova povezani su sličnim relacijama

pri čemu znak znači da se na dotičnom mjestu nalazi simbol presjeka slučajnih skupova, ako u definiciji B m postoji simbol ukrštanja ili simbol proizvoda rasplinutih skupova, i, shodno tome, simbol unija slučajnih skupova, ako u B m postoji simbol unije ili simbol zbira rasplinutih skupova.

De Morganovi zakoni su logična pravila koja je uspostavio škotski matematičar Augustus de Morgan i koja povezuju parove logičke operacije koristeći logičku negaciju.

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

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

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

U nama poznatijem obliku, ovi odnosi 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.

Razmotrimo primjenu De Morganovih zakona na konkretnim primjerima.

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

Koristimo De Morganov prvi zakon i dobijemo:

Primjenjujemo De Morganov drugi zakon na negaciju konjunkcije jednostavnih iskaza B i C i dobivamo:

,

ovako:

.

Kao rezultat, dobili smo ekvivalentnu izjavu u kojoj 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, sastavit ćemo tablice istinitosti za originalnu izjavu:

i za tvrdnju dobijenu kao rezultat transformacija izvršenih korištenjem De Morganovih zakona:

.

Tabela 1.

			B/\C	A\/B/\C



Kao što vidimo iz tabela, originalni logički iskaz i logički iskaz dobiven korištenjem De Morganovih zakona su ekvivalentni. O tome svjedoči činjenica da smo u tabelama istinitosti dobili identične skupove vrijednosti.

Teorema apsorpcije pisano u dva oblika - disjunktivnom i

konjunktiv, odnosno:

A + AB = A (16)

A(A + B)=A (17)

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

A + AB= A(1 + B)

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

A(1 + B) = A 1 = A

Da bismo dokazali drugu teoremu, otvorimo 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

konjunktiv:

Dokažimo prvu teoremu:

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



Da bismo dokazali drugu teoremu, otvorimo zagrade:



Prema teoremi (6) slijedi:

Prema teoremi apsorpcije (16) A+AB = A

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

Booleove formule, na primjer:



De Morganova teorema povezuje sve tri osnovne operacije Bulove algebre

Disjunkcija, konjunkcija i inverzija:

Prva teorema glasi ovako: inverzija konjunkcije je disjunkcija

inverzije. Drugo: inverzija disjunkcije je konjunkcija inverzija. Morganove teoreme mogu se dokazati korištenjem tablica istinitosti za lijevu i desnu stranu.

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

Predavanje 5

Invertovanje složenih izraza

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

ili disjunkcija, ali i na složenije izraze.

Nađimo inverziju izraza AB + CD , predstavljeno kao disjunkcija veznika. Smatraćemo da je inverzija završena ako se negativni predznaci pojavljuju samo iznad varijabli. Hajde da uvedemo sljedeću notaciju: AB = X;

CD = Y, Onda

Nađimo i zamijenimo u izraz (22):



ovako:

Razmotrimo izraz predstavljen u konjunktivnom obliku:

(A + B)(C + D)

Nađimo njegovu inverziju u obliku



Hajde da uvedemo sljedeću notaciju: A + B = X; C + D =Y, Onda

Hajde da ih pronađemo i zamenimo u izraz

ovako:

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

Koncept Booleove funkcije

IN općenito, funkcija (lat. functio - izvršenje, usklađenost,

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

koji se odnosi na raspon vrijednosti zavisne varijable f . U slučaju Booleovih funkcija X = F = (0,1). Pravilo kojim se specificira funkcija može biti bilo koja Booleova formula, na primjer:



Simbol f ovdje označava funkciju 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 funkcije: da bi se odredila njena vrijednost, općenito je potrebno znati vrijednosti svih argumenata o kojima ona ovisi. Na primjer, gornja funkcija ovisi o tri argumenta A, V, S. Ako uzmemo A = 1, dobijamo



tj. dobija se novi izraz koji nije ni jednak nuli ni

jedinica. Pusti to sada IN= 1. Onda



tj. u ovom slučaju se ne zna čemu je funkcija jednaka, nuli ili jedinici.

Hajde da konačno prihvatimo WITH= 0. Tada dobijamo: f = 0. Dakle, ako u originalnom izrazu uzmemo A = 1, IN= 1, WITH = 0, tada će funkcija uzeti nultu vrijednost: f = 0.

Hajde da razmotrimo koncept skupa varijabilnih vrijednosti .

Ako se svim argumentima od kojih funkcija ovisi dodijele neke vrijednosti, onda govorimo 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 koji je prvi, drugi ili recimo peti argument. Da biste to učinili, prikladno je koristiti abecedni raspored slova.

Na primjer, ako

onda je prema latiničnom alfabetu prvi argument R, sekunda -

Q, treći - X, četvrti - U. Tada je, na osnovu skupa vrijednosti argumenata, lako

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

bilježi tj. na skupu 1001 data funkcija je jednaka jedan.

Imajte na umu ponovo da je skup vrijednosti argumenata zbirka

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

Ovo postavlja pitanje: zar se skupovi ne mogu smatrati binarnim?

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

Pretvorite broj u decimalni sistem. 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 je broj 6 u decimalnom sistemu.

Ako trebate pronaći vrijednosti argumenata pomoću decimalnog broja, onda

nastavljamo obrnutim redoslijedom: prvo konvertujemo decimalni broj u binarni, a zatim dodajemo onoliko nula na lijevo koliko ukupan broj cifara jednak je broju argumenata, nakon čega nalazimo vrijednosti argumenata.

Neka, na primjer, trebate pronaći vrijednosti argumenata A, B, C, D, E, F biranjem broja 23. Konvertujemo broj 23 u binarni sistem koristeći metodu

dijeljenje sa dva:

Kao rezultat, dobijamo 23 10 = 10111 2. Ovaj broj ima pet cifara, ali ukupno

Postoji šest argumenata, stoga morate napisati jednu nulu na lijevoj strani:

23 10 = 010111 2. Odavde nalazimo:

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

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

Predavanje 6

Određivanje logičke funkcije

Već znamo jedan način. Analitičan je, odnosno u obliku matematičkog izraza koji koristi binarne varijable i logičke operacije. Osim ove, postoje i druge metode, od kojih je najvažnija tabela. Tabela navodi sve moguće skupove vrijednosti argumenata i specificira vrijednost funkcije za svaki skup. Takva tabela se zove tabela korespondencije (istine).

Koristeći funkciju kao primjer



Hajde da saznamo kako da napravimo tabelu korespondencije za to.

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

nudimo 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 njemu ćemo zapisati decimalne brojeve koji odgovaraju skupovima ako se smatraju trocifrenim binarnim brojevima. Ova decimala

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

može se zanemariti.



Hajde da popunimo tabelu. U redu sa brojem DOO piše:

A = B = C = 0.

Odredimo vrijednost funkcije na ovom skupu:

U koloni f upisujemo nulu u liniju sa 000.

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

na ovom setu:

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

Broj 001 se koristi za pisanje jednog.

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

popuniti celu tabelu.

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)

Dva puta br

Svojstva konstanti

x & 1 = x; (zakoni univerzalnog skupa)

x & 0 = 0; (null set zakona)

De Morganova pravila (zakoni)





Zakon protivrečnosti (komplementarnosti)

Zakon o isključenju trećeg (komplementarnost)

Dokazi svih ovih formula su trivijalni. Jedna od opcija je da se konstruišu tabele istinitosti leve i desne strane i uporede.

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 zakona raspodjele 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 preuzimanja

Pravilo apsorpcije za zbir dva elementarna 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 proizvod elementarnih suma slijedi iz zakona raspodjele druge vrste i zakona nultog skupa: konjunkcija dviju elementarnih disjunkcija, od kojih je jedna komponenta druge, može se zamijeniti elementarnom disjunkcijom koja ima manji broj operanada.

Pravilo raspoređivanja

Ovo pravilo definira radnju suprotnu od 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, zakon raspodjele prve vrste i provodi se u tri faze:

U proširenom elementarnom proizvodu ranga r se uvodi kao faktori n-r jedinica, gdje je n rang konstituenata jedinice;

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

Sve zagrade su proširene na osnovu zakona raspodjele prve vrste, što dovodi do proširenja originalnog elementarnog proizvoda ranga r u logički zbir 2 n-r konstituenata jedinice.

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 suma ranga n (sastav nule) slijedi zakone nultog skupa (6) i zakona raspodjele druge vrste (14) i provodi se u tri faze:

U prošireni zbir ranga r uvodimo kao članove n-r nula;

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

Rezultirajući izraz se transformira na osnovu zakona raspodjele druge vrste (14) na način da se originalni zbir ranga r pretvara u logički proizvod 2 n-r konstituenta nule.

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

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

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

Minimalna osnova je osnova za koju se uklanja barem jedna funkcija f 1, formirajući ovu osnovu, transformiše sistem funkcija (f 1 , f 1 ,…, f m) nepotpuno.

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

Dokaz. Ako funkcija logičke algebre f nije identično nula, tada se f izražava u obliku savršenog disjunktivnog normalnog oblika, koji 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 logičku algebarsku funkciju 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. Na ovaj način, prolazeći kroz sve funkcije algebre logike, nalazimo da je sistem B također potpun. Lema je dokazana.

Teorema. Sljedeći sistemi su kompletirani u P2:

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

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 disjunkcijom i negaciju, a sve funkcije sistema A su izražene formulama nad sistemom B. Prema lemi, sistem B je potpun.

2) Slično kao u tački 1: (x ∨ y) = x & y ⇔ x ∨ y =(x & y) i iz leme 2 slijedi istinitost iskaza u tački 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.Zhegalkin algebra. Svojstva poslovanja i kompletnost

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

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

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 druga je linearna funkcija.

Teorema. Svaka Booleova funkcija je predstavljena u obliku Zhegalkinovog polinoma na jedinstven način.

Predstavimo glavne metode za konstruisanje Zhegalkin polinoma iz date funkcije.

1. Metoda neodređenih koeficijenata. Neka je P(x 1 ,x 2 ... x n) željeni Žegalkinov polinom koji ostvaruje datu funkciju f(x 1 ,x 2 ... x n). Zapišimo to 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, sekvencijalno dodjeljujemo 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 jedinstveno rešenje. Nakon što smo ga riješili, nalazimo koeficijente polinoma P(X 1 ,X 2 ... X n).

2. Metoda zasnovana na transformaciji formula preko skupa veziva (,&). Napravite formulu F preko skupa konekcija (,&) koji realizuje datu funkciju f(X 1 ,X 2 ... X n). Zatim zamijenite podformule oblika A sa A⊕1 svuda, otvorite 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

Rješenje.
1. (metoda neodređenih koeficijenata). Zapišimo traženi polinom u obliku:

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

Koristeći tabelu 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 konzistentno 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 odnosu na druge algebre) aritmetizacija logike, koja omogućava da se transformacije Bulovih funkcija izvode prilično jednostavno. Njegova mana u odnosu na Bulovu algebru je glomaznost formula.




Povezane informacije.