En algoritme for å konstruere sannheten tabeller av logiske uttrykk

I dag, i denne artikkelen vil bli diskutert i detalj spørsmålet om å bygge en sannhet tabell over logiske uttrykk. Med dette problemet ofte støtt på studenter som gir enhetlig stat eksamen i informatikk. Faktisk er den såkalte boolsk algebra ikke komplisert hvis du kjenner de nødvendige lover, drift og regler for bygging av sannhetstabeller. Dette er spørsmål vi skal gjøre i dag.

Boolsk algebra

logikk algebra basert på enkle logiske uttrykk, som er innbyrdes forbundne operasjoner, og skaper en sammensatt uttrykk. Legg merke til at Boolsk algebra omfatter to binære operasjoner: addisjon og multiplikasjon (og disjunksjon av forbindelse, henholdsvis); en ensartet - inversjon. Alle enkle uttrykket (elementer av en kompleks logisk uttrykk) ta en av to verdier: "1" eller "0", "sann" eller "falsk", "+" eller - henholdsvis "".

algebra logikk er basert på noen relativt enkle aksiomer:

• assosiativitet;
• er kommutativ;
• absorpsjon;
• distributivity;
• addisjonalitet.

Hvis du kjenner disse lovene og sekvens av funksjoner, bygge en sannhet tabell over logiske uttrykk ikke vil føre til noen problemer. Husk at operasjonen må utføres i sekvens: negasjon, multiplikasjon, addisjon, konsekvens, ekvivalens, foregår bare så for å sperre Schiffer eller injunksjon operasjoner. Forresten, for de to siste funksjonene er ingen regler for prioritering, for å implementere dem i den rekkefølgen de er plassert.

Regler for utarbeidelse av tabellen

Konstruere en sannhet tabell over logiske uttrykk bidrar til å løse mange logiske problemer og finne løsninger på komplekse klumpete eksempler. Det er verdt å merke seg at det er noen regler for sin samling.

For å kunne gjøre en logisk bordet, er det nødvendig å begynne å bestemme antall rader. Hvordan gjøre det? Tell antall variabler som utgjør et komplekst uttrykk, og å bruke den enkle formel: A = 2 opphøyd n. Og - dette er antall rader i tabellen satt sammen av sannheten, n - er antall variabler som er en del av en kompleks logisk uttrykk.

Eksempel: komplekse uttrykk inneholder tre variabler (A, B og C), deretter en dårlig merke må bygges i den tredje grad. B er sannheten bordet vi vil ha åtte linjer. Legg en linje for tittelen på kolonnen.

Deretter vender vi oss til vår uttrykk og bestemme rekkefølgen av handlinger utført. Bedre for seg en blyantstrek (en, to, og så videre).

Det neste trinnet vi beregne antall operasjoner. Den resulterende tall - antall kolonner i bordet vårt. Sørg for å legge til enda et antall kolonner som variabler som finnes i dine vilkår, for å fylle de mulige kombinasjoner av variabler.

Deretter må du fylle hetten på bordet vårt. Nedenfor ser du et eksempel på dette.

Nå videre til fylling av mulige kombinasjoner. For to variabler, er de som følger: 00, 01, 10, 11. For tre variabler: 000, 001, 010, 011, 100, 101, 110, 111.

Etter at alle de ovennevnte elementer kan fortsette til beregningen av de gjenværende celler og fylle det resulterende bordet.

eksempel

Vi anser nå eksempel på å konstruere en tabell over logiske uttrykket er sant: inversjonen av A + B * A.

1. Antall variabler 2. Antall grener: 4 + 1 = 5.
2. Utførelsen rekkefølgen av handlinger: den første inversjon, andre forbindelse, motsetninger tredje.
3. Antall kolonner: 3 + 2 = 5.
4. Får en tracing og fylle tabellen.

Som regel høres jobben som dette: "Hvor mange kombinasjoner tilfreds F = 0" eller "i hvilke kombinasjoner F = 1". På det første spørsmålet er svaret - 1, den andre - 00, 01, 11.

Les nøye den jobben som du får. Du kan riktig løse problemet, men å gjøre en feil i å skrive svaret. Igjen jeg trekke oppmerksomheten til rekkefølgen av handlingene:

• fornektelse;
• multiplikasjon;
• tillegg.

oppgave

Konstruere en sannhet tabellen kan bidra til å finne svar på et vanskelig logisk problem. Følg prosessen med utarbeidelse av uttrykk og sannhetstabellen for tilstanden de logiske oppgaver du kan i denne delen av artikkelen.

Gitt fire verdier av A: 1), 7 2) 6, 3), 5, 4) 4. For noen av dem utsagnet "inversjon (mindre A 6) + (mindre enn 5 A)" er falsk?

Vårt første kolonne vil bli fylt med verdier 7, 6, 5, 4 kreves i denne rekkefølge. I neste kolonne, må vi svare på spørsmålet: "Og mindre enn 6" Den tredje kolonnen fylt i det samme, bare nå svaret på spørsmålet: "Og mindre enn 5"

Vi bestemmer rekkefølgen av operasjoner. Husk at fornektelse går foran disjunksjon. Så, neste kolonne vi fylle ut de verdiene som svarer til tilstanden er ikke (A mindre enn 6). Den fjerde vil svare det viktigste spørsmålet av vårt problem. Nedenfor ser du et eksempel på å fylle bordet.

Vær oppmerksom på at vi har tall for svar, er en falsk uttrykk en verdi av A = 5, er dette den tredje versjonen av svaret.