Algorithm ar gyfer adeiladu tablau wirionedd ymadroddion rhesymegol

Heddiw, yn y papur hwn yn cael ei drafod yn fanwl y mater o adeiladu tabl gwirionedd o ymadroddion rhesymegol. Â'r broblem hon yn aml yn dod ar draws fyfyrwyr sy'n rhoi yr arholiad wladwriaeth unedig mewn gwyddoniaeth gyfrifiadurol. Mewn gwirionedd, nid yw'r algebra hyn a elwir yn Boolean yn gymhleth os ydych yn gwybod y deddfau sy'n angenrheidiol, gweithrediadau a rheolau ar gyfer adeiladu tablau gwirionedd. Dyma'r cwestiynau yr ydym yn mynd i'w wneud heddiw.

algebra Boole

algebra rhesymeg yn seiliedig ar ymadroddion rhesymegol syml, sy'n cael eu gweithrediadau rhyng-gysylltiedig, gan greu mynegiant cymhleth. Sylwch fod algebra Boole cynnwys dau gweithrediadau deuaidd: adio a lluosi (a datgysylltiad o cyd, yn y drefn honno); yn unary - gwrthdro. Mae pob mynegiant syml (elfennau o fynegiant rhesymegol cymhleth) yn cymryd un o ddau werth: "1" neu "0", "gwir" neu "ffug", "+" neu "-" yn y drefn honno.

algebra o resymeg yn seiliedig ar ychydig o axioms gymharol syml:

• associativity;
• yn cymudol;
• amsugno;
• distributivity;
• ychwanegedd.

Os ydych yn gwybod na fydd y deddfau hyn a dilyniant o swyddogaethau, gan adeiladu tabl gwirionedd ymadroddion rhesymegol yn achosi unrhyw anawsterau. Dwyn i gof bod yn rhaid i'r llawdriniaeth yn cael ei berfformio yn eu trefn gaeth: negyddu, lluosi, adio, canlyniad, cywerthedd, dim ond wedyn yn mynd yn ei flaen i wahardd Schiffer neu rhesymegol nac gweithrediadau. Gyda llaw, ar gyfer y ddwy swyddogaeth olaf oes unrhyw reolau o flaenoriaeth, er mwyn eu rhoi ar waith yn y drefn y maent yn cael eu lleoli.

Rheolau lunio'r tabl

Adeiladu tabl gwirionedd ymadroddion rhesymegol yn helpu i ddatrys nifer o broblemau rhesymegol ac yn dod o hyd i atebion i enghreifftiau swmpus cymhleth. Mae'n werth nodi bod rhai rheolau eu casgliad.

Er mwyn gwneud yn iawn tabl rhesymegol, mae angen i ddechrau i benderfynu ar y nifer o resi. Sut i wneud hynny? Cyfrif y nifer o newidynnau sy'n rhan mynegiad cymhleth, a defnyddio'r fformiwla syml: A = 2 i'r n pŵer. Ac - mae hyn yn y nifer o resi yn y tabl a luniwyd gan wirionedd, n - yw'r nifer o newidynnau sy'n rhan o fynegiant rhesymegol cymhleth.

Enghraifft: mynegiant cymhleth yn cynnwys tri newidyn (A, B a C), yna rhaid marc gwael yn cael eu hadeiladu yn y trydydd gradd. B yw'r tabl gwirionedd bydd gennym wyth llinell. Ychwanegwch un llinell ar gyfer y teitl y golofn.

Nesaf, rydym yn troi at ein mynegiant ac yn penderfynu ar y drefn o gamau gweithredu a gyflawnir. Gwell trefn ar gyfer eu hunain marc pensil (un, dau, ac yn y blaen).

Y cam nesaf byddwn yn cyfrifo nifer y llawdriniaethau. Y rhif sy'n deillio - y nifer o golofnau yn ein tabl. Byddwch yn siwr i ychwanegu hyd yn oed nifer o golofnau fel newidynnau a gynhwysir yn eich telerau, i lenwi'r gyfuniadau posibl o newidynnau.

Nesaf, mae angen i chi lenwi'r cap ein bwrdd. Isod byddwch yn gweld enghraifft o hyn.

Nawr symud ymlaen i lenwi o gyfuniadau posibl. Ar gyfer dau newidyn, maent fel a ganlyn: 00, 01, 10, 11. Ar gyfer tri newidyn: 000, 001, 010, 011, 100, 101, 110, 111.

Ar ôl y gall yr holl eitemau uchod ymlaen i gyfrifo y celloedd sy'n weddill a llenwi'r tabl sy'n deillio.

enghraifft

Rydym bellach yn ystyried yr enghraifft o adeiladu tabl o'r mynegiant rhesymegol yn wir: mae'r gwrthdroad o A + B * A.

1. Cyfrif newidynnau: 2. Nifer y llinellau: 4 + 1 = 5.
2. Mae'r gorchymyn gweithredu o gamau gweithredu: y gwrthdro cyntaf, ail cyd, trydedd datgysylltiad.
3. Nifer y colofnau: 3 + 2 = 5.
4. Cael olrhain a llenwi bwrdd.

Fel rheol, mae'r swydd yn swnio fel hyn: "Faint o gyfuniadau yn bodloni F = 0" neu "yn yr hyn cyfuniadau F = 1". O ran y cwestiwn cyntaf yr ateb - 1, yr ail - 00, 01, 11.

Yn ofalus, darllenwch y swydd yr ydych yn ei roi. Gallwch ddatrys y broblem yn gywir, ond er mwyn gwneud camgymeriad wrth ysgrifennu'r ymateb. Unwaith eto, hoffwn dynnu eich sylw at y drefn y camau gweithredu:

• gwadu;
• lluosi;
• ychwanegiad.

tasg

Gall Adeiladu tabl gwirionedd yn helpu i ddod o hyd i'r ateb i broblem rhesymegol anodd. Dilynwch y broses o baratoi mynegiant a'r tabl gwirionedd am gyflwr y tasgau rhesymegol y gallwch yn y rhan hon o'r erthygl.

O ystyried pedwar werthoedd A: 1), 7 2) 6, 3), 5, 4) 4. Ar gyfer rhai ohonynt y datganiad "gwrthdroad (llai A 6) + (llai na 5 A)" yn ffug?

Bydd ein golofn gyntaf yn cael ei llenwi â gwerthoedd 7, 6, 5, 4 sy'n ofynnol yn y dilyniant hwn. Yn y golofn nesaf, mae'n rhaid i ni ateb y cwestiwn: "? Ac yn llai na 6" Mae'r drydedd golofn llenwi yn yr un, dim ond yn awr yr ateb i'r cwestiwn: "? Ac yn llai na 5"

Rydym yn penderfynu trefn y gweithrediadau. Cofiwch fod ymwadiad yn cael blaenoriaeth dros datgysylltiad. Felly, nid oedd y golofn nesaf rydym llenwch y gwerthoedd sy'n cyfateb i'r cyflwr yn (A llai na 6). Bydd y pedwerydd ateb y prif gwestiwn ein problem. Isod byddwch yn gweld enghraifft o lenwi y tabl.

Nodwch fod gennym nifer o ymatebion, mynegiant ffug yn werth A = 5, dyma'r trydydd fersiwn o'r ateb.