Razmatrane operacije nad skupovima podlež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
1. Zakon identiteta |
|
2. Komutativnost unije |
2'. |
Komutativnost preseka |
3. Asocijativnost udruženja |
3'. |
Asocijativnost ukrštanja |
4. Distributivnost unije u odnosu na raskrsnicu 5. Zakoni akcije sa praznim |
i univerzalni setovi (zakon isključene sredine) |
5'. |
Zakoni akcije sa praznim |
(zakon protivrečnosti) |
6. Zakon sindikalne idempotencije |
6'. Zakon idempotencije raskrsnice |
7. De Morganov zakon |
7'. De Morganov zakon |
8. Zakon eliminacije (apsorpcije) |
8'. Zakon eliminacije (apsorpcije) |
9. Zakon lepljenja |
9'. Zakon o vezivanju |
10. Zakon Poretskog
10'. Poretskyjev zakon
11. Zakon involucije (dvostruki komplement)
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 predstaviti 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. Tri kružnice koje se ukrštaju dijele cijeli univerzalni skup na osam regija (vidi sliku 3.2):
Ovaj identitet je istinit ako i samo ako je ista oblast zasjenjena u oba dijagrama. Prilikom pisanja uslova različitih primjera, često se koristi sljedeća notacija:
- iz... slijedi...;
- ako i samo ako… .
Problem 3.1 . Pojednostavite izraze algebre skupa:
Rješenje.
Zadatak 3 .2 . Dokažite identitete:
(AB)\B = A\B;
A(BC) = 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: XY i YX.
Prvo ćemo to pokazati
. Neka X– proizvoljan element skupa
, odnosno X
. To znači da XU i X
. Iz ovoga proizilazi da XA ili XB. Ako XAh, onda XĀ, što znači
. Ako XB, 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 XU i XA to znači XAB. Iz toga slijedi
. Ako
, To XU i XB. znači, XAB, tj
. Iz toga slijedi da je svaki element skupa
je također element skupa
, odnosno
.
znači,
, što je trebalo dokazati.
A(BC) = (AB)(AC);
1. Dokaz pomoću dijagrama:
Neka XA(BC). Onda XA i XBC. Ako XB, dakle XAB, što nije u suprotnosti sa onim što je rečeno, što znači X(AB)(AC). Ako XS, dakle XAC. dakle, X(AB)(AC). Dakle, dokazano je da je A(BC) (AB)(AC.
Pusti to sada X (AB)(AC). Ako XAB, dakle XA i XB. Iz toga slijedi XA i XVS, tj XA(BC). Ako XAS, dakle XA i XS. Iz ovoga proizilazi da XA i XVS, tj XA(BC). Dakle, (AB)(AC) A(BC). Prema tome, A(BC) = (AB)(AC). Q.E.D.
Prilikom dokazivanja dovoljnosti utvrdili smo da je AB=. 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 AB=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 ABC i element XA. Pokažimo da će u ovom slučaju element skupa A biti i element skupa
.
Razmotrimo dva slučaja: XB ili
.
Ako XB, dakle XABC, tj XC i, kao posljedica toga,
.
Ako
, onda
. Potreba je dokazana.
Pusti to sada
I XAB. Pokažimo da je element Xće također biti element skupa C.
Ako XAB, dakle XA i XB. Pošto
, znači XS. Dovoljnost je dokazana.
1. Dokaz pomoću dijagrama:
2. Dokaz korištenjem definicije jednakosti skupova.
Neka AB. Razmotrite element XB (ili
). Isto tako: XA (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 = ( M = ( x XA i XU i XC ili XC i XA i
B).
Iz definicije operacija nad skupovima dobijamo:
M = ((AB)\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. To je to najjednostavniji oblik
ove formule. M = ( M = ( Ovo područje se može posmatrati kao unija skupova A\B\C i ABC. M = ( Po definiciji M = ( XA i XB i XC ili XA i
U i
1. C).
2. Hajde da pojednostavimo:
(AB)\B = A\B;
Problemi za samostalno rješavanje.
Pojednostavite:
Dokažite pomoću dijagrama, zakona algebre skupova i definicije jednakosti skupova:
3. A(BC) = A\(A\B)(A\C);
AB = AB A=B;
A\B = AB = A.
Saznajte postoji li skup X koji zadovoljava jednakost za bilo koje A: AX = 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 se teorija rasplinutih skupova 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
YP2-1. De Morganovi zakoni za rasplinute skupove
(3)
Kao što je poznato, Morganovi zakoni su sljedeći identiteti algebre skupova
Teorema 1. Za rasplinute skupove vrijede sljedeći identiteti:. 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
Istovremeno 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 je i 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, pošto su u odnosu (6) brojevi b I c ulazite simetrično. Identitet (4) je dokazan.
Druga tvrdnja teoreme 2 proizilazi iz činjenice da, 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 koje
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 uslovu 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 pripadnosti) 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 svaku nejasnost (fazi skup), a definicije običnih operacija na rasplinutim skupovima ne mogu biti u skladu s tim. Neka se funkcije pripadnosti rasplinutih transformišu u naznačenim skupovima 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 naglašavali razliku između ovih područja teorijske i primijenjeno istraživanje. 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, jer u pogledu granica primjenjivosti čak i tako dugogodišnjeg naučna oblast, kao probabilističko-statističke metode, postoje različita mišljenja. 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.Neka - Definicija 2.
(7)
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
pred svima A Očigledno, svaki nasumični skup 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. A Dovoljno je podesiti raspodjelu slučajnog skupa . Neka U 1 IN- nosač (vidi definiciju 1 gore). Bez gubljenja opštosti možemo to pretpostaviti kod nekih m . Neka i elementi
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 ovo razjasnili, potrebna nam je sljedeća teorema. Teorema 4. Za slučajni podskup A skupa Y iz konačnog brojevi elemenata skupovi brojeva
Za bilo koji rasplinuti podskup B konačnog skupa Y, postoji slučajni podskup A od Y takav da je B = Proj A. I
izražavaju se jedno kroz drugo.
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) A parametri koji definiraju distribuciju slučajnog skupa
u opštem slučaju.
Sljedeća teorema će biti korisna.. Ako Teorema 5, 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
Za bilo koji rasplinuti podskup B konačnog skupa Y, postoji slučajni podskup A od Y takav da je B = Proj A. Proj A 1 i Proj A 2 .
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
(12)
Zapazite sada da se desna strana formule (11) može prepisati na sljedeći način:
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. za koje
Podrška za slučajni skup C je skup svih tih elemenataTeorema 7.
Jednakost Za slučajni podskup A skupa Y iz konačnog istinito ako i samo ako je presjek nosača slučajnih skupova
Za bilo koji rasplinuti podskup B konačnog skupa Y, postoji slučajni podskup A od Y takav da je B = Proj A. 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. godine i izvještavan na seminaru “Multidimenzionalna statistička analiza i vjerovatnoća modeliranja realnih procesa” 18. decembra 1974. – vidi) počelo uvođenjem slučajni skupovi za potrebe razvoja i generalizacije aparata rasplinutih skupova L. Zadeh. Činjenica je da nam matematički aparat rasplinutih skupova ne dozvoljava da na adekvatan način uzmemo u obzir razne opcije ovisnosti između koncepata (objekata) modeliranih uz njegovu pomoć nisu dovoljno fleksibilne. Dakle, da bi se opisao “zajednički dio” dva rasplinuta skupa postoje samo dvije operacije – proizvod i presjek. Ako se primijeni prvi od njih, onda se zapravo pretpostavlja da se skupovi ponašaju kao projekcije nezavisnih slučajnih skupova (vidjeti teoremu 6 iznad). Operacija preseka takođe nameće dobro definisana ograničenja na vrstu zavisnosti između skupova (videti teoremu 7 gore), iu ovom slučaju su pronađeni čak i neophodni i dovoljni uslovi. Poželjno je imati šire mogućnosti za modeliranje zavisnosti između skupova (koncepta, objekata). Upotreba matematičkog aparata nasumičnih skupova pruža takve mogućnosti.
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 linearni prostor, 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 otvoreni setovi, potonje su predstavljene kao zbir ne više od prebrojivog broja otvorenih kuglica, a za kuglice se provjerava deljivost direktno (telo zapremine je odvojeno od kuglice X 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 setovi, š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 operacija teorijske skupove 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 na sljedeći način:
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 dvaju jednostavnih iskaza ekvivalentna je disjunkciji 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 iskaz dobijen 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 - disjunktivnu i
konjunktiv:
Dokažimo prvu teoremu:
pošto 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 pojednostavljenja
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 primjenjuje na više varijabli:
Predavanje 5
Invertovanje složenih izraza
De Morganova teorema se ne primjenjuje 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 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
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 funkcija: da biste odredili njegovu 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
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, drugo -
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? n 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.