Perfekt disjunktiv normalform
Perfekt disjunktiv normalform (PDNF) är en av formerna för att representera en funktion av logikens algebra (boolesk funktion) i form av ett logiskt uttryck. Det är ett specialfall av DNF som uppfyller följande tre villkor [1] :
- den har inte identiska termer (elementära konjunktioner);
- det finns inga återkommande variabler i varje term;
- varje term innehåller alla variabler som den booleska funktionen beror på (varje variabel kan inkluderas i termen antingen i direkt eller invers form).
Vilken boolesk formel som helst som inte är identiskt falsk kan reduceras till SDNF, och på ett unikt sätt, det vill säga för alla tillfredsställande funktioner hos den logiska algebra, finns det en egen SDNF, och den enda [2] .
Kort teori
DNF är "summan av produkter", och AND-operationen (konjunktion) fungerar som "multiplikationsoperationen", och ELLER-operationen (disjunktion) fungerar som "additions"-operationen. Faktorer är olika variabler och de kan inkluderas i produkten både i direkt och invers form.
Nedan är ett exempel på en DNF:
Generellt sett kan en DNF innehålla upprepade termer, och varje term kan innehålla upprepade faktorer, till exempel:
Ur en matematisk synvinkel är sådan kloning meningslös, eftersom i boolesk algebra, multiplicera vilket uttryck som helst med sig självt och addera uttrycket till sig självt inte ändrar resultatet ( ), men att lägga till ett uttryck med sin egen invers och multiplicera med sin egen inversion ger konstanter ( ). I det sista uttrycket kan du ta bort upprepade termer och faktorer enligt följande:
Av denna anledning används DNF med upprepade termer och faktorer vanligtvis endast för hjälpändamål, till exempel vid analytisk transformation av uttryck.
SDNF är den kanoniska formen för att representera en boolesk funktion som en DNF, där upprepningar av termer och faktorer är förbjudna. Dessutom måste varje term innehålla alla variabler (i direkt eller invers form).
Nedan är ett exempel på SDNF:
Meningen med SDNF är det
- för varje specifik funktion är dess SDNF unik och entydig;
- SDNF har en en-till-en-korrespondens med sanningstabellen för en funktion. Varje term i SDNF motsvarar en rad i sanningstabellen, där funktionen är lika med en. Således är antalet termer i SDNF lika med antalet enhetsvärden som en boolesk funktion tar i sin definitionsdomän;
- SDNF erhålls elementärt från sanningstabellen för funktionen;
- SDNF är bekvämt som basuttryck för att minimera en funktion, det är särskilt lätt att hitta termer som är lämpliga för att "limma" i den.
Exempel på att hitta SDNF
För att få SDNF för en funktion krävs att den kompilerar dess sanningstabell . Ta till exempel en av sanningstabellerna:
| 0 | 0 | 0 | ett |
| 0 | 0 | ett | ett |
| 0 | ett | 0 | ett |
| 0 | ett | ett | 0 |
| ett | 0 | 0 | 0 |
| ett | 0 | ett | 0 |
| ett | ett | 0 | ett |
| ett | ett | ett | 0 |
I cellerna i resultatet är endast de kombinationer markerade som bringar det logiska uttrycket till tillståndet ett. Vidare beaktas värdena på variabler, där funktionen är lika med 1. Om värdet på en variabel är lika med 0, skrivs den med inversion. Om värdet på variabeln är 1, då ingen inversion.
Den första raden innehåller 1 i det angivna fältet. Värdena för alla tre variablerna är noterade, dessa är:
Nollvärden - här representeras alla variabler av nollor - skrivs i det slutliga uttrycket av inversen av denna variabel. Den första medlemmen av SDNF av den övervägda funktionen ser ut så här:
Andra medlemsvariabler:
i detta fall kommer att representeras utan inversion:
Sålunda analyseras alla celler . Den perfekta DNF för denna funktion kommer att vara disjunktionen av alla resulterande termer (elementära konjunktioner ).
Den perfekta DNF för denna funktion är:
Se även
Anteckningar
- ↑ Vinogradova M.S., Tkachev S.B. booleska funktioner. - M . : Förlag av MSTU im. N.E. Bauman, 2007. - 32 sid.
- ↑ Matematisk logik . - Perm: Publishing House of PSTU, 1998. - 17 sid. Arkiverad 9 april 2016 på Wayback Machine