Algoritme foar it bouwen fan wierheidtalen fan logyske útdrukkingen

Hjoeddedei yn dit papier sil de oanlis fan wierheidtalen fan logyske útdrukken yn detail beskôge wurde. Mei dit probleem binne der faak skoalbern dy't in unifoarme state eksam passe yn kompjûterwittenskip. Yn 't feil is de saneamde Boolean algebra net komplisearre as men de nedige wetten, operaasjes en regels foar it bouwen fan wierheidtalen ken. Wy sille hjoed dizze problemen oanpasse.

Booleaanske algebra

De logyske algebra is basearre op ienfâldige logyske útdrukkingen dy't tegearre troch operaasjes keppele binne en komplekse útdrukkings meitsje. It moat bepaald wurde dat de Boolean-algebra twa binêre operaasjes befettet: ferdieling en oanfolling (ferbân en disjunksje, respektivelik); Ien ynearren is in inversion. Alle ienfâldige útdrukkingen (eleminten fan in komplekse logyske útdrukking nimme ien fan twa wearden: "1" of "0", "wier" of "falsk", "+" of "-" respektivelik.

De algebra fan 'e logika is basearre op in pear frij ienfâldige aksiomos:

• Ferieniging;
• Commutativiteit;
• Absorption;
• Distributiviteit;
• Additionality.

As jo dizze wetten en de oarder fan útfiering fan funksjes kenne, sil de bou fan wierheidtalen fan logyske útjeften gjin problemen feroarsaakje. Ferjit net dat operaasjes yn stringende folchoarder útfierd wurde moatte: ôflevering, ferdieling, oanfolling, konsekwinsje, lykweardigens, allinich gean nei de operaasjes fan de Schiffer-bar of it pyls Pirs. By de wei, foar de lêste twa funksjes is der gjin rjocht fan prioriteit, fiere se yn 'e oarder wêryn't se sitte.

Rules foar kompilearjen fan in tafel

It oanlizzen fan in wierheid tafel fan logyske ekspresjes helpt oplosse protte logyske problemen en fine oplossings foar komplekse grut foarbylden. It is it wurdich te wizen dat der guon regels binne foar har kompilaasje.

Om korrekt in logyske tafel te meitsjen, moatte jo earst it oantal rigen befetsje. Hoe dit te dwaan? Kies it tal fariabelen dy't de komplekse ekspresje foarmje en brûke de ienfâldige formule: A = 2 nei de krêft fan n. A is it oantal rigen yn 'e wierstafel dy't kompilearre is, n is it oantal fariabelen dy't de komplekse logyske ekspresje ynfiere.

Foarbyld: in komplekse ekspresje befettet trije fariabelen (A, B, en C), dus moat de deuce opheven wurde nei de tredde krêft. Yn 'e gearstalling fan de wierheid hawwe wy acht rigels. In rigel taheakje foar de titel fan de kolommen.

Dan folgje wy nei ús útdrukking en bepale de folchoarder fan 'e aksje dy't útfierd wurde. It is better om de oarder te markearjen mei in pearel (ien, twa en sa).

De folgjende stap is it tal operaasjes te learen. It resultaat nûmer is it oantal kolommen yn ús tabel. Soargje derfan safolle kolommen as jo fariabelen yn jo útdrukking taheakje, mooglik mooglike kombinaasjes fan fariabelen befetsje.

Dan folje de koptekst fan ús tafel. Hjirûnder sjogge jo in foarbyld fan dit.

Nim no om de mooglike kombinaasjes te folle. Foar twa fariabelen sille se folgje: 00, 01, 10, 11. Foar trije fariabelen: 000, 001, 010, 011, 100, 101, 110, 111.

Nei allegear binne de boppeste punten foltôge, kinne jo trochgean om de oerbleaune sellen te kalkulearjen en te folle fan it resultaat tafel.

Foarbyld:

No sjogge wy in foarbyld fan it bouwen fan in wierstafel fan in logyske útdrukking: ynkomming A + B * A.

1. Ferfangende fariabelen: 2. Oantal rigels: 4 + 1 = 5.
2. De oarder fan 'e aksjes: de earste ynvers, de twadde ferbûn, de tredde disjunksje.
3. Oantal kolommen: 3 + 2 = 5.
4. Wy begjinne om de tafel te tekenjen en te folle.

As regel klinkt de opdracht sa: "hoefolle kombinaasjes befetsje de betingst F = 0" of "yn wat kombinaasjes F = 1". Op de earste fraach is it antwurd 1, op it twadde - 00, 01, 11.

Lês opsichtich de opdracht dy't jo jûn wurde. Jo kinne it probleem korrekt oplosse, mar meitsje in fersin om it antwurd te skriuwen. Nochris tekenje jo oandacht foar de oarder fan 'e aksjes:

• Negaasje;
• Multiplikaasje;
• Addition.

Objective

Bouwe in wierheidtabel kin helpe om it antwurd te finen op in swier logysk probleem. Om it proses te spoaren om in ekspresje en in wierstafel te kompilearjen troch de betingst fan in logyske taak, kinne jo yn dizze seksje fan it artikel.

Mei't fjouwer wearden fan it nûmer A: 1) 7, 2) 6, 3) 5, 4) 4. Foar hokker fan har is it wurd "ynvers (A minder as 6) + (A less than 5)" is falsk?

Us earste kolom sil folge wurde mei de wearden 7, 6, 5, 4 yn dizze folchoarder. Yn 'e folgjende kolom moatte wy de fraach beantwurdzje: "En minder dan 6?" De tredde kolom is folge op deselde manier, allinich beäntwurdzje wy de fraach: "En minder dan 5?"

Bestimming de ôfdieling fan operaasjes. Wy tinke dat de ôfwizing de foargonger hat oer disjunksing. Dêrmei folje wy de folgjende kolom mei wearden dy't oerienkomme mei de kondysje net (A is minder as 6). De fjirde sil de haadfragen fan ús taak beantwurdzje. Hjirûnder kinne jo in foarbyld sjen fan it filling fan in tafel.

Tink derom dat wy an antwurd-nûmers hawwe, de falske ekspresje sil by A = 5 wêze, dit is it tredde antwurd.