Algorithm para sa pagtatayo ng mga talahanayan ng katotohanan ng mga lohikal na expression

Ngayon sa papel na ito, ang pagtatayo ng mga talahanayan ng katotohanan ng lohikal na mga expression ay ituturing na detalyado. Sa problemang ito, kadalasang mayroong mga batang nasa paaralan na pumasa sa isang pinag-isang pagsusulit sa estado sa computer science. Sa katunayan, ang tinatawag na Boolean algebra ay hindi kumplikado kung alam ng isa ang mga kinakailangang batas, pagpapatakbo, at mga patakaran para sa pagtatayo ng mga talahanayan ng katotohanan. Tatalakayin natin ang mga isyung ito ngayon.

Boolean algebra

Ang logic algebra ay batay sa mga simpleng lohikal na expression na naka-link sa pamamagitan ng mga operasyon, na lumilikha ng masalimuot na mga expression. Dapat tandaan na ang Boolean algebra ay naglalaman ng dalawang binary na operasyon: pagpaparami at pagdaragdag (kasabay at disjunction, ayon sa pagkakabanggit); Ang isang unary ay pagbabaligtad. Ang lahat ng mga simpleng expression (elemento ng isang komplikadong lohikal na expression) ay may isa sa dalawang halaga: "1" o "0", "true" o "false", "+" o "-", ayon sa pagkakabanggit.

Ang algebra ng lohika ay batay sa ilang medyo simpleng mga axiom:

• Associativity;
• Commutativity;
• Pagsipsip;
• Distributivity;
• Pagdagdag.

Kung alam mo ang mga batas na ito at ang pagkakasunud-sunod ng pagpapatupad ng mga function, ang pagtatayo ng mga talahanayan ng katotohanan ng mga lohikal na expression ay hindi magiging sanhi ng anumang mga paghihirap. Tandaan na ang mga operasyon ay dapat isagawa sa mahigpit na pagkakasunud-sunod: pagtanggi, pagpaparami, karagdagan, resulta, katumbas, pagkatapos ay pagkatapos ay pumunta sa mga operasyon ng Schiffer bar o ang Pirs arrow. Sa pamamagitan ng paraan, para sa huling dalawang mga function walang patakaran ng priority, execute ang mga ito sa pagkakasunud-sunod kung saan sila matatagpuan.

Mga panuntunan para sa pag-compile ng isang talahanayan

Ang mga talahanayan ng katotohanan sa pagtatayo ng lohikal na mga expression ay tumutulong upang malutas ang maraming mga lohikal na problema at makahanap ng mga solusyon sa mga kumplikadong masalimuot na mga halimbawa. Ito ay nagkakahalaga ng tandaan na mayroong ilang mga patakaran para sa kanilang compilation.

Upang makagawa ng tamang lohikal na talahanayan, kailangan mo munang matukoy ang bilang ng mga hilera. Paano ito gawin? Bilangin ang bilang ng mga variable na bumubuo sa komplikadong expression, at gamitin ang simpleng formula: A = 2 sa lakas ng n. A ay ang bilang ng mga hilera sa talahanayan ng katotohanan na pinagsama-sama, n ang bilang ng mga variable na pumasok sa kumplikadong lohikal na expression.

Halimbawa: ang isang komplikadong expression ay naglalaman ng tatlong mga variable (A, B, at C), kaya ang deuce ay dapat na itataas sa ikatlong kapangyarihan. Sa pinag-isa na talahanayan ng katotohanan ay magkakaroon kami ng walong linya. Magdagdag ng isang linya para sa pamagat ng mga haligi.

Susunod, binuksan namin ang aming expression at tinutukoy ang pagkakasunud-sunod ng mga aksyon na gumanap. Mas mahusay na markahan ang pagkakasunud-sunod gamit ang lapis (isa, dalawa, at iba pa).

Ang susunod na hakbang ay upang mabilang ang bilang ng mga operasyon. Ang nagresultang numero ay ang bilang ng mga hanay sa aming talahanayan. Siguraduhing magdagdag ng maraming mga haligi dahil may mga variable sa iyong expression, upang mapunan ang posibleng mga kumbinasyon ng mga variable.

Pagkatapos ay punan ang header ng aming table. Sa ibaba makikita mo ang isang halimbawa nito.

Ngayon magpunta upang punan ang mga posibleng mga kumbinasyon. Para sa dalawang variable sila ay ang mga sumusunod: 00, 01, 10, 11. Para sa tatlong mga variable: 000, 001, 010, 011, 100, 101, 110, 111.

Matapos matupad ang lahat ng mga punto sa itaas, maaari kang magpatuloy upang kalkulahin at punan ang natitirang mga selula ng nagresultang talahanayan.

Halimbawa:

Ngayon isaalang-alang namin ang isang halimbawa ng pagtatayo ng isang talahanayan ng katotohanan ng isang lohikal na expression: inversion A + B * A.

1. Nagbibilang ng mga variable: 2. Bilang ng mga linya: 4 + 1 = 5.
2. Ang pagkakasunud-sunod ng mga aksyon: ang unang pagbabaligtad, ang ikalawang kasabay, ang ikatlong disjunction.
3. Bilang ng mga haligi: 3 + 2 = 5.
4. Nagsisimula kami upang gumuhit at punan ang talahanayan.

Bilang isang tuntunin, ang ganitong gawain ay ganito: "kung gaano karaming mga kumbinasyon ang nagtagumpay sa kundisyon F = 0" o "sa kung anong mga kumbinasyon F = 1". Sa unang tanong ang sagot ay 1, sa pangalawang - 00, 01, 11.

Maingat na basahin ang atas na ibinigay sa iyo. Maaari mong wastong malutas ang problema, ngunit nagkamali sa pagsulat ng sagot. Muli, iginuhit namin ang iyong pansin sa pagkakasunud-sunod ng mga pagkilos:

• Pagpapalagay;
• Pagpaparami;
• Pagdagdag.

Layunin

Ang pagtatayo ng talahanayan ng katotohanan ay makakatulong upang mahanap ang sagot sa isang mahirap na lohikal na problema. Upang masubaybayan ang proseso ng pagsasama-sama ng isang expression at isang talahanayan ng katotohanan sa pamamagitan ng kondisyon ng isang lohikal na gawain, maaari mong sa seksyon na ito ng artikulo.

Ibinigay ang apat na halaga ng numero A: 1) 7, 2) 6, 3) 5, 4) 4. Saan sa kanila ang sinasabi na "inversion (A mas mababa sa 6) + (Mas mababa sa 5)" ay mali?

Ang aming unang hanay ay mapupuno ng mga halaga 7, 6, 5, 4 sa pagkakasunud-sunod na ito. Sa susunod na hanay, dapat nating sagutin ang tanong: "At mas mababa sa 6?" Ang ikatlong haligi ay napunan sa parehong paraan, ngayon lamang sagutin namin ang tanong: "At mas mababa sa 5?"

Tukuyin ang pagkakasunud-sunod ng mga pagpapatakbo. Natatandaan namin na ang pagtanggi ay nangunguna sa disjunction. Kaya, pinupuno namin ang susunod na hanay na may mga halaga na tumutugma sa kondisyon na hindi (A ay mas mababa sa 6). Ang ikaapat ay sasagutin ang pangunahing tanong ng aming gawain. Sa ibaba maaari mong makita ang isang halimbawa ng pagpuno ng isang talahanayan.

Mangyaring tandaan na mayroon kaming mga numero ng sagot, ang maling pagpapahayag ay nasa A = 5, ito ang pangatlong sagot.