En algoritm för att konstruera sanningstabeller av logiska uttryck

Idag, i detta dokument kommer att diskuteras i detalj frågan om att bygga en sanningstabell logiska uttryck. Med detta problem ofta stött på studenter som ger enad stat examen i datavetenskap. I själva verket är det så kallade Boolean algebra inte komplex om du känner till nödvändiga lagar, verksamhet och regler för att konstruera sanningstabeller. Dessa är de frågor som vi kommer att göra i dag.

Boolean algebra

logik algebra baserad på enkla logiska uttryck, som är sammankopplade operationer, vilket skapar ett komplext uttryck. Notera att Boolesk algebra innefattar två binära operationer: addition och multiplikation (och disjunktion av samband, respektive); en unär - inversion. Alla enkla uttryck (element av en komplex logiskt uttryck) ta ett av två värden: "1" eller "0", "sann" eller "falsk", "+" eller "-" respektive.

algebra av logik bygger på några relativt enkla axiom:

• associativitet;
• är kommutativ;
• absorption;
• distributivity;
• additionalitet.

Om du känner till dessa lagar och sekvens av funktioner, bygga en sanningstabell logiska uttryck inte kommer att orsaka några svårigheter. Minns att operationen måste utföras i sekvens: negation, multiplikation, addition, följd, likvärdighet, fortsätter endast sedan till bar Schiffer eller logisk eller operationer. Förresten, för de två sista funktionerna finns inga regler prioritets att genomföra dem i den ordning i vilken de är belägna.

Regler utarbetandet av tabellen

Konstruera en sanningstabell logiska uttryck hjälper till att lösa många logiska problem och hitta lösningar på komplexa skrymmande exempel. Det är värt att notera att det finns vissa regler för deras sammanställning.

För att kunna göra en logisk tabell, är det nödvändigt att börja bestämma antalet rader. Hur man gör det? Räkna antalet variabler som utgör en komplex uttryck, och använda den enkla formeln: A = 2 till effekt n. Och - detta är antalet rader i tabellen sammanställts av sanning, n - är antalet variabler som ingår i ett komplext logiskt uttryck.

Exempel: komplext uttryck innehåller tre variabler (A, B och C), sedan ett dåligt märke skall byggas i den tredje graden. B är sanningstabellen kommer vi att ha åtta rader. Tillsätt en rad om titeln kolumnen.

Därefter vänder vi oss till vårt uttryck och bestämma i vilken ordning åtgärder som utförs. Bättre ordning sig en blyertsmarkering (en, två, och så vidare).

Nästa steg beräknar vi antalet operationer. Denna siffra - antalet kolumner i vårt bord. Var noga med att lägga till ännu ett antal kolumner som variabler som ingår i dina villkor, för att fylla möjliga kombinationer av variabler.

Därefter måste du fylla locket på vårt bord. Nedan ser du ett exempel på detta.

Nu vidare till fyllning av möjliga kombinationer. För två variabler, de är följande: 00, 01, 10, 11. För tre variabler: 000, 001, 010, 011, 100, 101, 110, 111.

Efter det att alla de ovan nämnda produkter, kan fortsätta till beräkningen av de återstående cellerna och fylla erhållen tabell.

exempel

Vi anser nu exempel på att konstruera en tabell över det logiska uttrycket är sant: invertering av A + B * A.

1. Räkna variabler: 2. Antal rader: 4 + 1 = 5.
2. Utförandet ordning åtgärder: den första inversion, andra samband, disjunktion tredje.
3. Antal kolumner: 3 + 2 = 5.
4. Att få en spårning och fylla tabellen.

Som regel låter jobbet så här: "Hur många kombinationer uppfyller F = 0" eller "i vilka kombinationer F = 1". På den första frågan är svaret - en, den andra - 00, 01, 11.

Läs noga igenom det jobb som du får. Du kan korrekt lösa problemet, men att göra ett misstag skriftligen svaret. Återigen vill jag göra er uppmärksamma på ordningen på åtgärder:

• förnekande;
• multiplikation;
• tillsats.

uppgift

Konstruera en sanningstabell kan hjälpa till att hitta svaret på en svår logiska problem. Följ processen för beredningen av uttryck och sanningstabellen för tillståndet hos de logiska uppgifter du kan i den här delen av artikeln.

Ges fyra värden på A: 1), 7 2) 6, 3), 5, 4) 4. För några av dem uttalandet "inversion (mindre A 6) + (mindre än 5 A)" är falskt?

Vår första kolumnen kommer att fyllas med värden 7, 6, 5, 4 som krävs i denna sekvens. I nästa kolumn, måste vi svara på frågan: "Och mindre än sex" Den tredje kolumnen fylls på i samma, men nu svaret på frågan: "Och mindre än 5"

Vi bestämmer sekvensen av operationer. Kom ihåg att förnekande har företräde framför disjunktion. Så är nästa kolumn vi fyller i de värden som motsvarar villkoret inte (A mindre än 6). Den fjärde kommer att besvara huvudfrågan om vårt problem. Nedan ser du ett exempel på att fylla i tabellen.

Observera att vi har fler svar, är ett falskt uttryck ett värde av A = 5, är detta den tredje versionen av svaret.