An algorithm chokuvaka chokwadi yematafura musoro mashoko

Nhasi, ari papepa ichi ichakurukurwa zvakadzama nyaya rokuvaka tafura inonzwisisika mashoko chokwadi. With dambudziko iri kakawanda vakasangana vadzidzi kupa vabatane mamiriro bvunzo computer nesayenzi. Kutaura zvazviri, vanonzi Boolean nemasvomhu haasi kunzwisisa kana uchiziva zvakakodzera mitemo, akavhiyiwa uye nemitemo chokuvaka chokwadi pamatafura. Ndivo mibvunzo tiri kuita nhasi.

Boolean nemasvomhu

Kufunga nemasvomhu kwakavakirwa nyore musoro mashoko, izvo interconnected amabasa, kutanga kunzwisisa mashoko. Cherechedza kuti Boolean nemasvomhu unotora maviri binary akavhiyiwa: Kuwedzera uye chokuwanziridza (uye disjunction pamusoro pachiimbwa, ukuwo); munhu unary - inversion. All nyore okuti (zvemamiriro kunzwisisa musoro kutaura) tora mumwe tsika mbiri: "1" kana "0", "chokwadi" kana "nhema", "+" kana "-" azvaitwa.

nemasvomhu nomufungo kunobva mashoma husina axioms:

• associativity;
• ndiyo commutative;
• Absorção de Água;
• distributivity;
• additionality.

Kana muchiziva zvinhu mitemo uye kutevedzana mitambo, kuvaka tafura inonzwisisika mashoko chokwadi haungavhenekeri chero matambudziko. Yeuka kuti mudzimu zvinofanira kuitwa enderana urongwa: negation, chokuwanziridza, Uyezve, mugumisiro, yokuenzana, chete ipapo mberi akanomira Schiffer kana musoro kana kushandiswa. Panzira, nokuti okupedzisira maviri mashandiro vasiri nemitemo pakutanga, kuti pave navo kuti yavanofanira dziri.

Mitemo vaigadzirira tafura

Kugadzira tafura inonzwisisika mashoko chokwadi kunobatsira kugadzirisa zhinji matambudziko musoro uye kuwana zvinogadzirisa kunzwisisa kura mienzaniso. Zvinokosha kucherechedza kuti pane zvimwe mitemo muunganidzwa yavo.

Kuti zvakanaka kugadzira musoro tafura, zvinokosha kutanga kuona uwandu pemitsara. How kuzviita? Nhamba variables hunoumba kunzwisisa mashoko, uye kushandisa mano payakavakirwa: A = 2 kuti simba n. Uye - Ndiko kuwanda mitsara iri tafura rakanyorwa nechokwadi, N - inhamba variables kuti tiri chikamu kunzwisisa musoro kutaura.

Muenzaniso: kunzwisisa mashoko ine variables matatu (A, B uye C), zvino chiratidzo akaipa anofanira yakavakwa dhigirii rechitatu. B ndiro tafura chokwadi tichava mitsetse masere. Wedzerai rwonzi nokuda wenyaya mbiru.

Next, isu kuna kutaura kwedu uye kuona hurongwa yezviito anoitwa. Nani kuti pachavo penzura mucherechedzo (rimwe, vaviri, uye zvichingodaro).

Danho rinotevera isu ngaaverenge nhamba remapazi. The zvichiguma nhamba - nhamba mbiru patafura yedu. Iva nechokwadi kuti kuwedzera kunyange vanoverengeka mbiru sezvo variables zviri nemashoko enyu, kuzadza zvichibvira mubatanidzwa variables.

Next, unofanira vazadze chivharo patafura yedu. Below muchiona muenzaniso uyu.

Zvino mberi kune zvinodiwa zvichibvira mubatanidzwa. For variables maviri, vari sezvinotevera: 00, 01, 10, 11. Kuti zvitatu variables: 000, 001, 010, 011, 100, 101, 110, 111.

Mushure yose yataurwa pamusoro apa zvinhu zvinogona mberi kuti kuverenga kwamakamuri yasara uye wakazadza zvichiguma tafura.

muenzaniso

We funga zvino muenzaniso rokuvaka patafura musoro okuti ichokwadi; asi inversion pakati A + B * A.

1. Count variables: 2. Nhamba mitsetse: 4 + 1 = 5.
2. The kuuraya hurongwa nezviito: ari inversion wokutanga, pachiimbwa wechipiri, disjunction wechitatu.
3. Nhamba Columns: 3 + 2 = 5.
4. Kuwana Kuongororwa uye akazadza tafura.

Kazhinji, basa rinonzwika seizvi: "mubatanidzwa vangani zvinogutsa F = 0" kana "pane chii anofambidzana F = 1". On mubvunzo wokutanga mhinduro - 1, wechipiri - 00, 01, 11.

Nyatsoongorora verenga basa kuti uri kupiwa. Unogona nemazvo kugadzirisa dambudziko, asi kuti kukanganisa kunyora kwacho. Zvakare I kuswedera wako afunge sezvakarayirwa zviito:

• rupokano;
• chokuwanziridza;
• Uyezve.

basa

Kugadzira tafura chokwadi kunogona kubatsira kuwana mhinduro akaoma musoro dambudziko. Teverai muitiro rokugadzirira rwekutaura netafura chokwadi kuti ezvinhu akanyatsorongwa mabasa zvaunokwanisa chino nyaya.

Kupiwa tsika mana A: 1), 7 2) 6, 3), 5, 4) 4. Nokuti vamwe vavo okuti "inversion (duku A 6) + (asingasviki 5 A)" ndeyenhema?

Mbiru redu rokutanga ichazara tsika 7, 6, 5, 4 hunodiwa kutevedzana uku. Munyaya inotevera mbiru, tinofanira kupindura mubvunzo: "? Uye asingasviki 6" Wechitatu mbiru akazadzwa iroro, chete zvino mhinduro yomubvunzo wokuti: "? Uye asingasviki 5"

We kuona kutevedzana remapazi. Yeuka kuti kuramba kunofanira kuva panzvimbo yokutanga pamusoro disjunction. Saka, mangwana mbiru isu zadza tsika kuti anoenderana mamiriro haisi (A asingasviki 6). Wechina ichapindura mubvunzo chikuru dambudziko redu. Below muchiona muenzaniso rokuzadza tafura.

Tapota cherechedza kuti tine nhamba mhinduro, wenhema mashoko ari ukoshi A = 5, ichi ndicho rechitatu shanduro mhinduro.