En algoritme til at konstruere sandhedstabeller af logiske udtryk

I dag, i dette papir vil blive diskuteret i detaljer spørgsmålet om at konstruere en sandhed tabel over logiske udtryk. Med dette problem ofte stødt studerende, der giver den forenet stat eksamen i datalogi. Faktisk er den såkaldte boolsk algebra er ikke kompliceret, hvis du kender de nødvendige love, drift og regler for at konstruere sandhedstabeller. Det er de spørgsmål, vi kommer til at gøre i dag.

boolsk algebra

logik algebra baseret på simple logiske udtryk, som er indbyrdes forbundne operationer, hvilket skaber en kompleks udtryk. Bemærk, at Boolean algebra omfatter to binære operationer: addition og multiplikation (og disjunktion af forbindelse, henholdsvis); en unær - inversion. Alle enkle udtryk (elementer af et komplekst logisk udtryk) tage en af to værdier: "1" eller "0", "sand" eller "falsk", "+" eller "-" hhv.

algebra for logik er baseret på nogle få relativt simple aksiomer:

• associativitet;
• er kommutativ;
• absorption;
• distributivitet;
• additionalitet.

Hvis du kender disse love og sekvens af funktioner, der bygger en sandhed tabel over logiske udtryk vil ikke forårsage nogen problemer. Husk på, at operationen skal udføres i streng rækkefølge: negation, multiplikation, addition, konsekvens, ækvivalens, fortsætter først derefter til bar Schiffer eller logisk eller operationer. Af den måde, for de sidste to funktioner er ingen regler for prioritering, at gennemføre dem i den rækkefølge, som de er placeret.

Regler for opstilling af bordet

Konstruktion af en sandhed tabel over logiske udtryk er med til at løse mange logiske problemer og finde løsninger på komplekse voluminøse eksempler. Det er værd at bemærke, at der er nogle regler for deres kompilering.

For at kunne lave en logisk tabel, er det nødvendigt at begynde at bestemme antallet af rækker. Hvordan man gør det? Tæl antallet af variabler, der udgør en kompleks udtryk, og bruge den enkle formel: A = 2 til potensen n. Og - det er antallet af rækker i tabellen udarbejdet af sandhed, n - er antallet af variabler, der indgår i et komplekst logisk udtryk.

Eksempel: komplekst udtryk indeholder tre variabler (A, B og C), derefter en dårlig varemærke skal bygges i tredje grad. B er sandheden bordet vil vi have otte linjer. Tilføj en linje til titlen af kolonnen.

Dernæst vender vi os til vores udtryk og bestemme rækkefølgen af handlinger, der udføres. Bedre ordre for sig selv en blyant mærke (en, to, og så videre).

Det næste skridt vi beregne antallet af operationer. Det endelige antal - antallet af kolonner i vores bord. Vær sikker på at tilføje endnu et antal kolonner som variabler, der er indeholdt i dine vilkår, for at fylde de mulige kombinationer af variabler.

Dernæst skal du udfylde hætten af vores bord. Nedenfor kan du se et eksempel på dette.

Nu videre til fyldning af mulige kombinationer. For to variabler, de er som følger: 00, 01, 10, 11. For tre variable: 000, 001, 010, 011, 100, 101, 110, 111.

Efter at alle de ovennævnte elementer kan fortsætte til beregningen af de resterende celler og fylde den resulterende tabel.

eksempel

Vi betragter nu eksemplet med at konstruere en tabel over det logiske udtryk er sandt: inversion af A + B * A.

1. Tæl variabler: 2. Antal linier: 4 + 1 = 5.
2. Udførelse rækkefølge handlinger: den første inversion, anden sammenholdt, disjunction tredjedel.
3. Antal kolonner: 3 + 2 = 5.
4. Kom en opsporing og påfyldning bord.

Som regel jobbet lyder sådan her: "Hvor mange kombinationer opfylder F = 0" eller "i hvilke kombinationer F = 1". På det første spørgsmål er svaret - 1, den anden - 00, 01, 11.

Læs omhyggeligt det job, du får. Du kan korrekt løse problemet, men at lave en fejl skriftligt svar. Endnu en gang jeg henlede opmærksomheden på rækkefølgen af handlinger:

• benægtelse;
• multiplikation;
• tilføjelse.

opgave

Konstruktion af en sandhed tabel kan hjælpe med at finde svaret på et vanskeligt logisk problem. Følg processen med udarbejdelse af udtryk og sandheden tabellen for tilstanden af de logiske opgaver, du kan i dette afsnit af artiklen.

Givet fire værdier af A: 1), 7 2) 6, 3), 5, 4) 4. For nogle af dem udsagnet "inversion (mindre A 6) + (mindre end 5 A)" er falsk?

Vores første kolonne vil blive fyldt med værdier 7, 6, 5, 4 kræves i denne sekvens. I den næste kolonne, skal vi besvare spørgsmålet: "Og mindre end 6" Den tredje søjle fyldt i den samme, men nu svaret på spørgsmålet: "Og mindre end 5"

Vi bestemme rækkefølgen af operationer. Husk, at benægtelse forrang for disjunktion. Så næste kolonne vi udfylde de værdier, der svarer til den tilstand er ikke (A mindre end 6). Den fjerde vil besvare hovedspørgsmålet om vores problem. Nedenfor kan du se et eksempel på at udfylde skemaet.

Bemærk, at vi har antallet af reaktioner, en falsk udtryk er en værdi af A = 5, dette er den tredje version af svaret.