De övervägda operationerna på mängder är föremål för vissa lagar som liknar talalgebras välkända elementära lagar. Detta bestämmer namnet uppsättning algebra, som ofta kallas boolesk algebra av mängder, vilket är förknippat med namnet på den engelske matematikern John Boole, som baserade sin logiska forskning på idén om en analogi mellan algebra och logik.

För godtyckliga uppsättningar A, B och C är följande identiteter giltiga (tabell 3.1):

Tabell 3.1

10. Poretskys lag

10'. Poretskys lag

11. Involutionens lag (dubbelt komplement)

Lagarna för mängdalgebra i förhållande till operationerna för korsning () och union () är föremål för principen om dualitet: om det i någon lag är alla korsningstecken ersatta med unionstecken, och alla unionstecken ersätts med korsningstecken , universumtecknet (U) ersätts av det tomma uppsättningstecknet (Ø), och det tomma tecknet är universums tecken, då får vi återigen den korrekta identiteten. Till exempel (i kraft av denna princip) följer det osv.

3.1. Verifiera sanningen av identiteter med Euler-Venn-diagram

Alla lagar för mängdalgebra kan representeras visuellt och bevisas med hjälp av Euler-Venn-diagram. För att göra detta behöver du:

Rita motsvarande diagram och skugga alla uppsättningar på vänster sida av ekvationen. Rita ett annat diagram och gör samma sak för den högra sidan av ekvationen.

Denna identitet är sann om och endast om samma område är skuggat i båda diagrammen. Tre korsande cirklar delar upp hela den universella uppsättningen i åtta regioner (se fig. 3.2):

Denna identitet är sann om och endast om samma område är skuggat i båda diagrammen. När du skriver villkoren för olika exempel används ofta följande notation:

 - från... följer det...;

 - om och bara om... .

Problem 3.1 . Förenkla inställda algebrauttryck:

Lösning.

Uppgift 3 .2 . Bevisa identiteter:

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

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

Lösning.

Problem 3.3 . Bevisa följande samband på två sätt: med hjälp av diagram och med definitionen av jämlikhet mellan mängder.

Lösning.

2. Bevis med definitionen av jämlikhet mellan mängder.

Per definition är mängderna X och Y lika om följande relationer är uppfyllda samtidigt: XY och YX.

Först visar vi det
. Låta X– ett godtyckligt element i uppsättningen
, det vill säga X
. Detta betyder det XU och X
. Av detta följer att XA eller XB. Om X Ah, då XĀ, vilket betyder
. Om XB alltså
, vilket betyder
. Alltså, varje del av uppsättningen.
. är också en del av uppsättningen
Som är

Nu ska vi bevisa motsatsen, det vill säga
. Låta
. Om XĀ alltså XU och XOch det betyder XAB. Det följer att
. Om
, Det XU och XB. Medel, XAB, alltså
. Det följer att varje del av uppsättningen
är också en del av uppsättningen
, det vill säga
.

Medel,
, vilket var det som behövde bevisas.

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

1. Bevis med ett diagram:

Låta XA(BC). Sedan XA och XBC. Om XB alltså XAB, vilket inte motsäger det som sades, vilket betyder X(AB)(AC). Om XС alltså XAC. Därför, X(AB)(AC). Så det har bevisats att A(BC)  (AB)(AC.

Låt det nu X (AB)(AC). Om XAB alltså XA och XB. Det följer att XA och XВС, det vill säga XA(BC). Om XАС alltså XA och XS. Av detta följer att XA och XВС, det vill säga XA(BC). Alltså (AB)(AC) A(BC). Därför är A(BC) = (AB)(AC). Q.E.D.

När vi bevisade tillräcklighet fann vi att AB=. Det är uppenbart att С, så sambandet är bevisat. I bevisningen beaktades det mest allmänna fallet. Vissa andra alternativ är dock möjliga när man konstruerar diagram. Till exempel fallet med likhet AB=C eller
, fallet med tomma uppsättningar och så vidare. Självklart kan det vara svårt att ta hänsyn till alla möjliga alternativ. Därför tror man att bevisningen av samband med hjälp av diagram inte alltid är korrekt.

2. Bevis med definitionen av jämlikhet mellan mängder.

Nödvändighet. Låt ABC och element XA. Låt oss visa att i detta fall kommer ett element i mängden A också att vara ett element i mängden
.

Låt oss överväga två fall: XB eller
.

Om XB alltså XABC, alltså XC, och som en konsekvens av detta,
.

Om
, då
. Behovet har bevisats.

Låt det nu
Och XAB. Låt oss visa att elementet X kommer också att vara en del av uppsättningen C.

Om XAB alltså XA och XB. Sedan
, betyder XS. Tillräcklighet har bevisats.

1. Bevis med ett diagram:

2. Bevis med definitionen av jämlikhet mellan mängder.

Låt AB. Tänk på elementet XB (eller
). Likaledes: XA (eller XĀ). Det vill säga varje del av uppsättningen är också en del av uppsättningen Â. Och detta kan vara fallet om
. Q.E.D.

Problem 3.4. Uttryck de angivna områdena symboliskt och förenkla de resulterande uttrycken.

Lösning.

Det önskade området består av två isolerade delar.

Låt oss kalla dem topp och botten. Uppsättningen de representerar kan beskrivas på följande sätt: M = ( M = ( x XA och XI och XC eller XC och XA och

B).

Från definitionen av operationer på set får vi:

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

Låt oss skriva detta uttryck med hjälp av de grundläggande operationerna - addition, union och skärningspunkt: Det är omöjligt att förenkla detta uttryck, eftersom vi har en förekomst av varje karaktär. Det här är det enklaste formen

av denna formel. M = ( M = ( Detta område kan betraktas som en förening av uppsättningarna A\B\C och ABC. M = ( Per definition M = ( XA och XB och XC eller XA och

I och

1. C).

2. Låt oss förenkla:

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

Problem för oberoende lösning.

Förenkla:

Bevisa med hjälp av diagram, lagarna för mängdalgebra och definitionen av jämlikhet mellan mängder:

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

AB = AB  A=B;

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

Ta reda på om det finns en uppsättning X som uppfyller likheten för något A: AX = A; (svar );.

Kapitel 8 undersökte sådana typer av objekt av icke-numerisk natur som fuzzy och slumpmässiga uppsättningar. Syftet med denna ansökan är att studera djupare egenskaperna hos fuzzy sets och att visa att teorin om fuzzy sets i en viss mening reducerar till teorin om slumpmässiga mängder. För att uppnå detta mål formuleras och bevisas en kedja av teorem.

I det följande antas det att alla luddiga uppsättningar som övervägs är delmängder av samma uppsättning

YP2-1. De Morgans lagar för luddiga uppsättningar

(3)

Som bekant kallas följande identiteter för algebra av mängder Morgans lagar

Sats 1. För fuzzy set gäller följande identiteter:. Till skillnad från det klassiska fallet med relationer (1), består de av fyra identiteter, varav ett par relaterar till operationerna av förening och skärning, och det andra till operationerna av produkt och summa. Liksom relation (1) i mängdalgebra tillåter de Morgans lagar i fuzzy set-algebra en att transformera uttryck och formler som inkluderar negationsoperationer.

P2-2. Distributiv lag för fuzzy set

Vissa egenskaper för setoperationer gäller inte för fuzzy set. Ja, förutom när A- en "klar" uppsättning (dvs. medlemskapsfunktionen tar bara värdena 0 och 1).

Är distributionslagen sann för fuzzy set? Litteraturen säger ibland vagt att "inte alltid". Låt oss vara helt tydliga.

Sats 2.För alla fuzzy set A, B och C

Samtidigt jämlikhet

rättvist om och bara om, för alla

Bevis. Fixa ett godtyckligt element. För att förkorta notationen betecknar vi För att bevisa identitet (4) är det nödvändigt att visa det

Tänk på olika ordningsföljder av tre nummer a, b, c. Låt först Då är den vänstra sidan av relation (6) och den högra sidan, dvs. jämställdhet (6) är sant.

Låt Då i relation (6) till vänster är a till höger, dvs. relation (6) är återigen en jämlikhet.

Om då i relation (6) till vänster är och till höger, dvs. båda delarna matchar igen.

Tre återstående nummerbeställningar a, b, c det finns inget behov av att demontera, eftersom i relation (6) siffrorna b Och c ange symmetriskt. Identitet (4) är bevisad.

Det andra påståendet i sats 2 följer av det faktum att, i enlighet med definitionerna av operationer på fuzzy set (se kapitel 8)

Dessa två uttryck sammanfaller om och endast om, när, vad som krävdes för att bevisas.

Definition 1.Bäraren för en fuzzy uppsättning A är mängden av alla punkter , för vilket

Följd av sats 2.Om bärarna för de fuzzy uppsättningarna B och C sammanfaller med Y, så gäller likhet (5) om och endast om A är en "skarp" (dvs. vanlig, klassisk, inte fuzzy) uppsättning.

Bevis. Efter tillstånd inför alla. Sedan följer det av sats 2 dessa. eller , vilket betyder att A- tydligt set.

P2-3. Luddiga uppsättningar som projektioner av slumpmässiga uppsättningar

Från första början modern teori fuzzyness började diskuteras på 1960-talet om dess förhållande till sannolikhetsteorin. Faktum är att medlemskapsfunktionen för en fuzzy uppsättning liknar en sannolikhetsfördelning. Den enda skillnaden är att summan av sannolikheterna över alla möjliga värden för en slumpvariabel (eller integralen, om uppsättningen av möjliga värden är oräknelig) alltid är lika med 1, och summan S värden för medlemskapsfunktionen (i det kontinuerliga fallet - integralen av medlemskapsfunktionen) kan vara vilket icke-negativt tal som helst. Det finns en frestelse att normalisera medlemsfunktionen, d.v.s. dividera alla dess värden med S(på S 0) för att reducera den till en sannolikhetsfördelning (eller sannolikhetstäthet). Fuzziness-specialister motsätter sig dock med rätta en sådan "primitiv" minskning, eftersom den utförs separat för varje fuzziness (fuzzy set), och definitionerna av vanliga operationer på fuzzy set kan inte överensstämma med det. Det sista uttalandet betyder följande. Låt medlemskapsfunktionerna hos fuzzy sådana omvandlas på det angivna sättet A Och I. Hur förändras medlemsfunktionerna? Installera detta omöjligt i princip. Det sista påståendet blir helt klart efter att ha övervägt flera exempel på par av luddiga uppsättningar med samma värdesummor för medlemskapsfunktioner, men olika resultat av mängdteoretiska operationer på dem, och värdesummorna för motsvarande medlemskapsfunktioner för dessa resultat av mängdteoretiska operationer, till exempel, för skärningspunkter av mängder är också olika.

I verk om fuzzy sets sägs det ganska ofta att teorin om fuzzyness är en självständig gren av tillämpad matematik och inte är relaterad till sannolikhetsteori (se t.ex. en genomgång av litteraturen i monografier). Författare som jämförde fuzzy teori och sannolikhetsteori betonade vanligtvis skillnaden mellan dessa områden av teoretiska och tillämpad forskning. Vanligtvis jämförs axiomatik och applikationsområden jämförs. Det bör omedelbart noteras att argumenten för den andra typen av jämförelser inte har beviskraft, eftersom när det gäller gränserna för tillämpligheten av även en så långvarig vetenskapliga området, som probabilistisk-statistiska metoder finns det olika åsikter om. Låt oss komma ihåg att resultatet av resonemang från en av de mest kända franska matematikerna, Henri Lebesgue, angående gränserna för aritmetikens tillämplighet är följande: "Aritmetiken är tillämplig när den är tillämplig" (se hans monografi).

När man jämför olika axiomatik för fuzzy teori och sannolikhetsteori är det lätt att se att listorna över axiom skiljer sig åt. Av detta följer dock inte alls att ett samband inte kan fastställas mellan dessa teorier, såsom den välkända reduktionen av euklidisk geometri på planet till aritmetik (närmare bestämt till teorin om talsystemet - se, till exempel monografin). Låt oss komma ihåg att dessa två axiomatik - euklidisk geometri och aritmetik - vid första anblicken är väldigt olika.

Man kan förstå önskan hos entusiaster av den nya riktningen att betona den grundläggande nyheten i deras vetenskapliga apparat.

Det är dock lika viktigt att skapa kopplingar mellan det nya tillvägagångssättet och tidigare kända.

Som det visar sig är teorin om luddiga mängder nära besläktad med teorin om slumpmässiga mängder. Redan 1974 visades det i arbetet att luddiga uppsättningar naturligtvis kan betraktas som "projektioner" av slumpmässiga uppsättningar. Låt oss överväga denna metod för att reducera teorin om luddiga mängder till teorin om slumpmässiga mängder.Låta - Definition 2.

(7)

en slumpmässig delmängd av en ändlig mängd Y. En fuzzy mängd B definierad på Y kallas en projektion A och betecknas Proj A om

inför alla A Uppenbarligen varje slumpmässig uppsättning kan korreleras med hjälp av formel (7) med en otydlig uppsättning B = Projekt A.

Det visar sig att det motsatta också är sant. Sats 3.

För varje fuzzy delmängd B av en finit mängd Y finns det en slumpmässig delmängd A av Y så att B = Proj A. Bevis. A Det räcker att ställa in fördelningen av den slumpmässiga mängden . Låta U 1 I- bärare (se definition 1 ovan). Utan förlust av allmänhet kan vi anta det hos vissa m . Låta och element

numrerade i sådan ordning att

Låt oss presentera set För alla andra delmängder X set U låt oss sätta P(A=X)=0 . Sedan elementet y t ingår i setet Y(1), Y(2),..., Y(t) och ingår inte i set Y(t+1),..., Y(m), Att

Av formlerna ovan följer det

Om då, uppenbarligen, sats 3 bevisas. Fördelningen av en slumpmässig mängd med oberoende element, som följer av övervägandena i kapitel 8, bestäms helt av dess projektion. För en ändlig slumpmässig uppsättning av allmän form är detta inte fallet. För att förtydliga ovanstående behöver vi följande teorem. Sats 4. För en slumpmässig delmängd A av en mängd Y från en finit antal element uppsättningar av tal

För varje fuzzy delmängd B av en finit mängd Y finns det en slumpmässig delmängd A av Y så att B = Proj A. Och



uttrycks det ena genom det andra.

I denna formel i den första summan på går igenom alla delar av uppsättningen Y\X, i den andra summan summeringsvariablerna vid 1 Och vid 2 inte sammanfaller och kör även igenom denna uppsättning osv.

En hänvisning till formeln för inkludering och uteslutning kompletterar beviset för sats 4. I enlighet med sats 4 kan en slumpmässig mängd A karakteriseras inte bara av en fördelning utan också av en uppsättning tal Det finns inga andra relationer av jämställdhetstyp i denna uppsättning. Denna uppsättning innehåller siffror, därför är fixering av projektionen av en slumpmässig uppsättning likvärdig med fixering k = Kort(Y) parametrar från(2k-1) A parametrar som anger fördelningen av en slumpmässig uppsättning

i det allmänna fallet.

Följande teorem kommer att vara användbar.. Om Sats 5, Projekt A = B

Att

För att bevisa det räcker det med att använda identiteten från teorin om slumpmässiga mängder, formeln för täckningssannolikheten från kapitel 8, definitionen av negationen av en fuzzy mängd och det faktum att summan av alla P(A= X) är lika med 1.

P2-4. Korsningar och produkter av suddiga och slumpmässiga uppsättningar

Låt oss ta reda på hur operationer på slumpmässiga mängder relaterar till operationer på deras projektioner. I kraft av De Morgans lagar (sats 1) och sats 5 är det tillräckligt att överväga operationen av skärningspunkten mellan slumpmässiga mängder. Sats 6. Om slumpmässiga delmängder A 1 och A 2 av en ändlig mängd y är oberoende, sedan den luddiga uppsättningen är ett verk luddiga uppsättningar

För varje fuzzy delmängd B av en finit mängd Y finns det en slumpmässig delmängd A av Y så att B = Proj A. Projekt A 1 och Proj A 2 .

Det måste visas att för någon

Enligt formeln för sannolikheten att täcka en punkt med en slumpmässig mängd (kapitel 8)

Som bekant kan fördelningen av skärningspunkten för slumpmässiga mängder uttryckas i termer av deras gemensamma fördelning enligt följande:

Av relationerna (9) och (10) följer att täckningssannolikheten för skärningspunkten mellan slumpmässiga mängder kan representeras som en dubbelsumma

(12)

Observera nu att den högra sidan av formel (11) kan skrivas om enligt följande:

Faktum är att formel (11) skiljer sig från formel (12) endast genom att den grupperar termer där skärningspunkten mellan summeringsvariablerna har ett konstant värde. Med hjälp av definitionen av oberoende av slumpmässiga mängder och regeln för att multiplicera summor, får vi att från (11) och (12) följer likheten

För att slutföra beviset för sats 6 räcker det med att återigen hänvisa till formeln för sannolikheten att täcka en punkt med en slumpmässig mängd (kapitel 8). Definition 3. för vilket

Stödet för en slumpmässig mängd C är samlingen av alla dessa elementSats 7.

Jämställdhet För en slumpmässig delmängd A av en mängd Y från en finit sant om och endast om skärningspunkten mellan stöden för de slumpmässiga mängderna

För varje fuzzy delmängd B av en finit mängd Y finns det en slumpmässig delmängd A av Y så att B = Proj A. Det är nödvändigt att ta reda på villkoren under vilka

Då minskar jämställdheten (13) till villkoret

Det är tydligt att relation (14) är uppfylld om och endast om p 2 p 3=0 för alla dvs. det finns inte ett enda element på samma gång Och , och detta motsvarar tomheten i skärningspunkten mellan stöden för slumpmässiga uppsättningar och . Sats 7 är bevisat.

P2-5. Minskning av operationssekvensen på fuzzy set

till en sekvens av operationer på slumpmässiga uppsättningar

Ovan fick vi några kopplingar mellan fuzzy och slumpmässiga uppsättningar. Det är värt att notera att studiet av dessa samband i arbetet (detta arbete utfördes 1974 och rapporterades vid seminariet "Multidimensional statistical analysis and probabilistic modeling of real processes" den 18 december 1974 - se) började med införandet av slumpmässiga uppsättningar i syfte att utveckla och generalisera apparat av fuzzy uppsättningar L. Zadeh. Faktum är att den matematiska apparaten för luddiga uppsättningar inte tillåter oss att ta tillräcklig hänsyn olika alternativ beroenden mellan begrepp (objekt) modellerade med dess hjälp är inte tillräckligt flexibla. För att beskriva den "gemensamma delen" av två otydliga uppsättningar finns det bara två operationer - produkt och korsning. Om den första av dem tillämpas, så antas det faktiskt att mängderna beter sig som projektioner av oberoende slumpmässiga mängder (se sats 6 ovan). Operationen av skärningspunkten lägger också mycket specifika begränsningar på typen av beroende mellan mängder (se sats 7 ovan), och i detta fall har till och med nödvändiga och tillräckliga villkor hittats. Det är önskvärt att ha bredare möjligheter för att modellera beroenden mellan uppsättningar (koncept, objekt). Användningen av den matematiska apparaten av slumpmässiga mängder ger sådana möjligheter.

Syftet med att reducera fuzzy mängder till slumpmässiga är att bakom varje konstruktion av fuzzy mängder se en konstruktion av slumpmängder som bestämmer egenskaperna hos den första, på samma sätt som vi ser en slumpvariabel med en sannolikhetsfördelningstäthet. I det här avsnittet presenterar vi resultat för att reducera algebra för fuzzy mängder till algebra för slumpmässiga mängder.

Definition 4.Sannolikhetsutrymme { W, G, P)vi kallar det delbart om för någon mätbar mängd X G och vilket positivt tal som helst, mindre än P(X), kan vi specificera en mätbar mängd så att

Exempel. Låta vara enhetskuben för en ändlig dimensionell linjärt utrymme, Gär sigmaalgebra för Borel-uppsättningar, och P- Lebesgue-mått. Sedan { W, G, P)- delbart sannolikhetsutrymme.

Således är delbart sannolikhetsutrymme inte exotiskt. En vanlig kub är ett exempel på ett sådant utrymme.

Beviset för påståendet som formulerats i exemplet utförs med hjälp av matematiska standardtekniker, baserat på det faktum att en mätbar mängd kan approximeras så exakt som önskat öppna set, de senare representeras som summan av högst ett räknebart antal öppna bollar, och för bollar kontrolleras delbarheten direkt (volymkroppen är separerad från bollen X av motsvarande plan).

Sats 8.Låt en slumpmässig mängd A ges på ett delbart sannolikhetsutrymme (W, G, P) med värden i mängden av alla delmängder av mängden Y från ett ändligt antal element, och en fuzzy mängd D på Y. Sedan finns det slumpmässiga mängder C 1, C 2, C 3, C 4 på samma sannolikhetsutrymme så att

där B = Proj A.

Bevis. På grund av giltigheten av De Morgans lagar för fuzzy (se sats 1 ovan) och för slumpmässiga mängder, samt sats 5 ovan (om negationer), är det tillräckligt för att bevisa förekomsten av slumpmässiga mängder C 1 Och C 2 .

Betrakta sannolikhetsfördelningen i mängden av alla delmängder av mängden set, motsvarande den slumpmässiga uppsättningen MED sådan att Projekt C = D(det finns i kraft av sats 3). Låt oss bygga en slumpmässig uppsättning C 2 Vi utesluter elementet endast för av samma uppsättning Y så att

och dessutom är resultaten av mängdteoretiska operationer relaterade till liknande relationer

där tecknet betyder att det på platsen i fråga finns en symbol för skärningspunkten mellan slumpmässiga mängder, om det i definitionen av B m finns en skärningssymbol eller en symbol för produkten av otydliga mängder, och följaktligen en symbol för unionen av slumpmässiga mängder, om det i B m finns en unionssymbol eller en symbol för summan av otydliga mängder.

De Morgans lagar är logiska regler fastställda av den skotske matematikern Augustus de Morgan som relaterar par logiska operationer använder logisk negation.

Augustus de Morgan noterade att i klassisk logik är följande relationer giltiga:

inte (A och B) = (inte A) eller (inte B)

inte (A eller B) = (inte A) och (inte B)

I en mer bekant form för oss kan dessa relationer skrivas i följande form:



De Morgans lagar kan formuleras på följande sätt:

I de Morgans lag: Negationen av disjunktionen av två enkla uttalanden är ekvivalent med konjunktionen av negationerna av dessa uttalanden.

II de Morgans lag: Negationen av konjunktionen av två enkla påståenden är ekvivalent med disjunktionen av negationerna av dessa påståenden.

Låt oss överväga tillämpningen av De Morgans lagar med hjälp av specifika exempel.

Exempel 1. Omforma formeln så att det inte finns några negationer av komplexa påståenden.

Låt oss använda De Morgans första lag och få:

Vi tillämpar De Morgans andra lag på negationen av konjunktionen av enkla påståenden B och C, och vi får:

,

Således:

.

Som ett resultat fick vi ett likvärdigt uttalande där det inte finns några negationer av sammansatta uttalanden, och alla negationer avser endast enkla uttalanden.

Du kan kontrollera lösningens giltighet med hjälp av sanningstabeller. För att göra detta kommer vi att sammanställa sanningstabeller för det ursprungliga uttalandet:

och för uttalandet som erhållits som ett resultat av transformationer utförda med hjälp av De Morgans lagar:

.

Tabell 1.

			B.C	A\/B/\C



Som vi ser från tabellerna är den ursprungliga logiska satsen och den logiska satsen erhållen med hjälp av De Morgans lagar likvärdiga. Detta bevisas av det faktum att vi i sanningstabellerna fick identiska värden.

Absorptionssats skriven i två former - disjunktiv och

konjunktiv, respektive:

A + AB = A (16)

A(A + B)=A (17)

Låt oss bevisa det första teoremet. Låt oss ta bokstaven A utanför parentes:

A + AB= A(1 + B)

Enligt sats (3) 1 + B = 1 alltså

A(1 + B) = A 1 = A

För att bevisa den andra satsen, låt oss öppna parenteserna:

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

Resultatet är ett uttryck som just har bevisats.

Låt oss överväga flera exempel på tillämpningen av absorptionssatsen för

förenkling av booleska formler.

Limningssats har också två former - disjunktiv och

konjunktiv:

Låt oss bevisa det första teoremet:

eftersom enligt satser (5) och (4)



För att bevisa den andra satsen, låt oss öppna parenteserna:



Enligt sats (6) följer det:

Enligt absorptionssatsen (16) A+AB = A

Absorptionssatsen, liksom limningssatsen, används vid förenkling

Booleska formler, till exempel:



De Morgans teorem kopplar samman alla tre grundläggande operationer i boolesk algebra

Disjunktion, konjunktion och inversion:

Den första satsen lyder så här: inversionen av en konjunktion är en disjunktion

inversioner. För det andra: inversionen av en disjunktion är en konjunktion av inversioner. Morgans satser kan bevisas med hjälp av sanningstabeller för vänster och höger sida.

De Morgans teorem gäller fler variabler:

Föreläsning 5

Invertera komplexa uttryck

De Morgans teorem gäller inte bara enskilda konjunktioner

eller disjunktioner, men också till mer komplexa uttryck.

Låt oss hitta inversionen av uttrycket AB + CD , presenteras som en disjunktion av konjunktioner. Vi kommer att betrakta inversionen som komplett om negativa tecken endast visas ovanför variablerna. Låt oss presentera följande notation: AB = X;

CD = Y, Sedan

Låt oss hitta och ersätta med uttryck (22):



Således:

Betrakta uttrycket som presenteras i konjunktiv form:

(A + B)(C + D)

Låt oss hitta dess inversion i formen



Låt oss presentera följande notation: A + B = X; C + D =Y, Sedan

Låt oss hitta och ersätta dem i uttrycket

Således:

När du inverterar komplexa uttryck kan du använda följande regel. För att hitta inversionen är det nödvändigt att ersätta konjunktionstecken med disjunktionstecken, och disjunktionstecken med konjunktionstecken, och sätta inversioner över varje variabel:

Konceptet med en boolesk funktion

I i allmänhet funktion (lat. functio - utförande, efterlevnad,

mappning) är en viss regel (lag), enligt vilken varje element i mängden X, representerar värdeintervallet för den oberoende variabeln X, ett specifikt element i uppsättningen tilldelas F,

som hänvisar till värdeintervallet för den beroende variabeln f . När det gäller booleska funktioner X = F = (0,1). Regeln för vilken en funktion specificeras kan vara valfri boolesk formel, till exempel:



Symbol f här betecknar en funktion som är, liksom argumenten för A, B, C, binär variabel.

Argument är oberoende variabler, de kan ta vilket värde som helst - antingen 0 eller 1. Funktionen f - beroende variabel. Dess betydelse bestäms helt av variablernas värden och de logiska sambanden mellan dem.

Huvudsak funktion: för att bestämma dess värde, i allmänhet är det nödvändigt att känna till värdena för alla argument som det beror på. Till exempel beror funktionen ovan på tre argument A, V, S. Om vi ​​tar A = 1 får vi



dvs ett nytt uttryck erhålls som varken är lika med noll eller

enhet. Låt det nu I= 1. Sedan



i detta fall är det inte känt vad funktionen är lika med, noll eller ett.

Låt oss äntligen acceptera MED= 0. Då får vi: f = 0. Om vi ​​alltså i det ursprungliga uttrycket tar A = 1, I= 1, MED = 0, då tar funktionen nollvärdet: f = 0.

Låt oss överväga begreppet en uppsättning variabelvärden .

Om alla argument som en funktion beror på tilldelas några värden, så talar vi om en uppsättning argumentvärden som kan vara

kalla det bara ett set. En uppsättning argumentvärden är en sekvens av nollor och ettor, till exempel 110, där den första siffran motsvarar det första argumentet, det andra till det andra och det tredje till det tredje. Uppenbarligen är det nödvändigt att i förväg komma överens om vad det första, andra eller, säg, femte argumentet är. För att göra detta är det bekvämt att använda det alfabetiska arrangemanget av bokstäver.

Till exempel om

då enligt det latinska alfabetet är det första argumentet R, andra -

Q, tredje - X, fjärde - U. Sedan, baserat på uppsättningen av argumentvärden, är det lätt

hitta värdet på funktionen. Låt till exempel ges uppsättningen 1001. Enligt den

poster dvs på set 1001 är den givna funktionen lika med ett.

Observera igen att uppsättningen argumentvärden är en samling

nollor och ettor. Binära tal är också uppsättningar av nollor och ettor.

Detta väcker frågan: kan inte set betraktas som binära?

tal? Det är möjligt, och i många fall är det mycket bekvämt, särskilt om den binära

Konvertera talet till decimalsystemet. Till exempel om

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

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

d.v.s. den givna mängden är nummer 6 i decimalsystemet.

Om du behöver hitta värdena för argumenten med hjälp av decimaltalet, då

vi fortsätter i omvänd ordning: först konverterar vi decimaltalet till binärt, sedan lägger vi till lika många nollor till vänster som totalt antal siffror är lika med antalet argument, varefter vi hittar värdena på argumenten.

Låt dig till exempel hitta värdena för argumenten A, B, C, D, E, F genom att slå med nummer 23. Vi omvandlar talet 23 till det binära systemet med metoden

dividera med två:

Som ett resultat får vi 23 10 = 10111 2. Detta nummer är femsiffrigt, men totalt

Det finns sex argument, därför måste du skriva en nolla till vänster:

23 10 = 010111 2. Härifrån hittar vi:

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

Hur många set är det totalt om antalet är känt? n argument? Uppenbarligen så många som det finns n-bitars binära tal, dvs 2 n

Föreläsning 6

Ange en boolesk funktion

Vi vet redan ett sätt. Det är analytiskt, det vill säga i form av ett matematiskt uttryck som använder binära variabler och logiska operationer. Utöver detta finns det andra metoder, varav den viktigaste är den tabellformade. Tabellen listar alla möjliga uppsättningar av argumentvärden och anger värdet på funktionen för varje uppsättning. En sådan tabell kallas en korrespondens(sannings)tabell.

Använder funktionen som exempel



Låt oss ta reda på hur man bygger en korrespondenstabell för det.

Funktionen beror på tre argument A, B, C. Därför i tabellen

vi tillhandahåller tre kolumner för argument A,B,C och en kolumn för värdena för funktionen f. Till vänster om kolumn A är det användbart att placera en annan kolumn. I den kommer vi att skriva ner decimaltal som motsvarar mängder om de betraktas som tresiffriga binära tal. Denna decimal

kolumnen introduceras för att underlätta arbetet med tabellen, därför, i princip,

det kan försummas.



Låt oss fylla i tabellen. I raden med LLC-numret står det:

A = B = C = 0.

Låt oss bestämma värdet på funktionen på denna uppsättning:

I kolumn f skriver vi noll på raden med ratten 000.

Nästa uppsättning: 001, dvs. e. A = B = 0, C = 1. Hitta värdet på funktionen

på detta set:

På set 001 är funktionen 1, därför i kolumn f i rad c

Nummer 001 används för att skriva en.

På samma sätt beräknar vi värdena för funktionerna på alla andra uppsättningar och

fyll i hela tabellen.