Kuidas lahendada arvutiteaduse eksami A ja B osa ülesandeid
Õppetund number 3. Loogika. Loogikafunktsioonid. Võrrandite lahendamine
Suur hulk USE ülesandeid on pühendatud propositsioonide loogikale. Enamiku lahendamiseks piisab propositsiooniloogika põhiseaduste tundmisest, ühe ja kahe muutuja loogiliste funktsioonide tõesuse tabelite tundmisest. Annan propositsiooniloogika põhiseadused.
- Disjunktsiooni ja konjunktsiooni kommutatiivsus:
a ˅ b ≡ b ˅ a
a^b ≡ b^a - Disjunktsiooni ja konjunktsiooni käsitlev distributsiooniseadus:
a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c) - Negatiivne eitus:
¬(¬a) ≡ a - Järjepidevus:
a ^ ¬a ≡ vale - Eksklusiivne kolmas:
a ˅ ¬a ≡ tõsi - De Morgani seadused:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b - Lihtsustamine:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ tõsi ≡ a
a ˄ väär ≡ vale - Imendumine:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a - Implikatsiooni asendamine
a → b ≡ ¬a ˅ b - Identiteedi muutus
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
Loogiliste funktsioonide kujutamine
Mis tahes loogilist funktsiooni n muutujast - F(x 1 , x 2 , ... x n) saab defineerida tõesuse tabeliga. Selline tabel sisaldab 2 n muutujate komplekti, millest igaühe jaoks on määratud selle hulga funktsiooni väärtus. See meetod on hea, kui muutujate arv on suhteliselt väike. Isegi n > 5 korral muutub esitus halvasti nähtavaks.
Teine võimalus on määratleda funktsioon mõne valemiga, kasutades tuntud üsna lihtsaid funktsioone. Funktsioonide süsteemi (f 1 , f 2 , … f k ) nimetatakse täielikuks, kui mis tahes loogilist funktsiooni saab väljendada valemiga, mis sisaldab ainult funktsioone f i .
Funktsioonide süsteem (¬, ˄, ˅) on valmis. Seadused 9 ja 10 on näited sellest, kuidas implikatsiooni ja identiteeti väljendatakse eituse, konjunktsiooni ja disjunktsiooni kaudu.
Tegelikult on ka kahe funktsiooni süsteem täielik – eitus ja konjunktsioon või eitus ja disjunktsioon. Esitused tulenevad De Morgani seadustest, mis võimaldavad konjunktsiooni väljendada eituse ja disjunktsiooni kaudu ning vastavalt väljendada disjunktsiooni eituse ja konjunktsiooni kaudu:
(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)
Paradoksaalselt on ainult ühest funktsioonist koosnev süsteem täielik. On kaks binaarset funktsiooni - antikonjunktsioon ja antidisjunktsioon, mida nimetatakse Pierce'i nooleks ja Schaefferi löögiks, mis esindavad õõnsat süsteemi.
Programmeerimiskeelte põhifunktsioonid hõlmavad tavaliselt identiteeti, eitust, konjunktsiooni ja disjunktsiooni. Eksami ülesannetes on koos nende funktsioonidega sageli ka tähendus.
Vaatame mõnda lihtsat loogiliste funktsioonidega seotud ülesannet.
Ülesanne 15:
Tõetabelist on antud fragment. Milline kolmest antud funktsioonist vastab sellele fragmendile?
| x1 | x2 | x3 | x4 | F |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
- (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
- (¬X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
- ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)
Funktsioon number 3.
Ülesande lahendamiseks on vaja teada põhifunktsioonide tõetabeleid ja silmas pidada toimingute prioriteete. Tuletan meelde, et konjunktsioonil (loogilisel korrutamisel) on kõrgem prioriteet ja seda tehakse enne disjunktsiooni (loogilist liitmist). Arvutamisel on hästi näha, et kolmanda hulga numbritega 1 ja 2 funktsioonid omavad väärtust 1 ja seetõttu ei vasta fragmendile.
Ülesanne 16:
Milline järgmistest numbritest vastab tingimusele:
(numbrid, alustades kõige olulisemast numbrist, lähevad kahanevas järjekorras) → (arv – paaris) ˄ (madalaim number – paaris) ˄ (suurim number – paaritu)
Kui selliseid numbreid on mitu, märkige suurim.
- 13579
- 97531
- 24678
- 15386
Tingimus on täidetud numbriga 4.
Esimesed kaks numbrit ei vasta tingimusele põhjusel, et madalaim number on paaritu. Tingimuste konjunktsioon on väär, kui üks sidesõna terminitest on väär. Kolmanda numbri puhul ei ole kõrgeima numbri tingimus täidetud. Neljanda numbri puhul on täidetud tingimused, mis on seatud numbri väiksemale ja suuremale numbrile. Sidesõna esimene liige on samuti tõene, kuna implikatsioon on tõene, kui selle eeldus on väär, nagu siin on.
Ülesanne 17: Kaks tunnistajat tunnistasid järgmist:
Esimene tunnistaja: kui A on süüdi, siis B on kindlasti süüdi ja C on süütu.
Teine tunnistaja: Kaks on süüdi. Ja üks ülejäänutest on kindlasti süüdi ja süüdi, aga ma ei oska täpselt öelda, kes.
Milliseid järeldusi A, B ja C süü kohta saab tõendite põhjal teha?
Vastus: Tunnistustest järeldub, et A ja B on süüdi, aga C on süütu.
Lahendus: Muidugi võib vastuse anda terve mõistuse põhjal. Kuid vaatame, kuidas seda rangelt ja formaalselt teha.
Esimene asi, mida teha, on avaldused vormistada. Tutvustame kolme Boole'i muutujat A, B ja C, millest igaüks on tõene (1), kui vastav kahtlustatav on süüdi. Seejärel antakse esimese tunnistaja ütlus valemiga:
A → (B ˄ ¬C)
Teise tunnistaja ütlused antakse järgmise valemiga:
A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))
Eeldatakse, et mõlema tunnistaja ütlused vastavad tõele ja kujutavad endast vastavate valemite konjunktsiooni.
Koostame nende näitude jaoks tõetabeli:
| A | B | C | F1 | F2 | F 1 F 2 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Kokkuvõtlikud tõendid vastavad tõele vaid ühel juhul, mis toob kaasa selge vastuse – A ja B on süüdi ning C on süütu.
Ka selle tabeli analüüsist järeldub, et teise tunnistaja ütlused on informatiivsemad. Tema tunnistuse tõesusest järeldub vaid kaks võimalikku varianti – A ja B on süüdi ning C on süütu või A ja C on süüdi ning B on süütu. Esimese tunnistaja ütlused on vähem informatiivsed – tema ütlustele vastavad 5 erinevat varianti. Üheskoos annavad mõlema tunnistaja ütlused ühemõttelise vastuse kahtlustatavate süü kohta.
Loogikavõrrandid ja võrrandisüsteemid
Olgu F(x 1 , x 2 , …x n) n muutuja loogiline funktsioon. Loogiline võrrand on järgmine:
F(x 1, x 2, ... x n) \u003d C,
Konstandi C väärtus on 1 või 0.
Loogilisel võrrandil võib olla 0 kuni 2n erinevat lahendit. Kui C on võrdne 1-ga, siis on lahenditeks kõik need tõesuse tabelist pärit muutujate hulgad, millel funktsioon F saab väärtuse tõene (1). Ülejäänud hulgad on nulliga võrdse C võrrandi lahendid. Alati võime arvestada ainult järgmise kujuga võrrandeid:
F(x 1 , x 2 , …x n) = 1
Tõepoolest, olgu võrrand antud:
F(x 1 , x 2 , …x n) = 0
Sel juhul võite minna samaväärse võrrandi juurde:
¬F(x 1 , x 2 , …x n) = 1
Vaatleme k loogilise võrrandi süsteemi:
F 1 (x 1, x 2, ... x n) \u003d 1
F 2 (x 1, x 2, ... x n) \u003d 1
F k (x 1 , x 2 , …x n) = 1
Süsteemi lahendus on muutujate kogum, millel on täidetud kõik süsteemi võrrandid. Loogiliste funktsioonide osas tuleks loogikavõrrandisüsteemi lahenduse saamiseks leida hulk, millel on tõene loogiline funktsioon Ф, mis esindab algfunktsioonide F konjunktsiooni:
Ф = F 1 ˄ F 2 ˄ … F k
Kui muutujate arv on väike, näiteks alla 5, siis ei ole keeruline koostada funktsiooni Ф tõetabelit, mis võimaldab öelda, mitu lahendust süsteemil on ja millised on lahendusi andvad hulgad.
Mõnes ühtse riigieksami loogikavõrrandisüsteemile lahenduste leidmise ülesandes ulatub muutujate arv väärtuseni 10. Siis muutub tõetabeli koostamine peaaegu lahendamatuks ülesandeks. Probleemi lahendamine nõuab teistsugust lähenemist. Suvalise võrrandisüsteemi jaoks pole peale loendamise ühtegi üldist meetodit, mis võimaldaks selliseid probleeme lahendada.
Eksamil välja pakutud ülesannetes lähtutakse enamasti võrrandisüsteemi eripärade arvestamisest. Kordan, peale muutujate komplekti kõigi variantide loetlemise pole probleemi lahendamiseks üldist viisi. Lahendus tuleb üles ehitada lähtuvalt süsteemi spetsiifikast. Sageli on kasulik läbi viia võrrandisüsteemi esialgne lihtsustamine, kasutades teadaolevaid loogikaseadusi. Veel üks kasulik tehnika selle probleemi lahendamiseks on järgmine. Meid ei huvita kõik hulgad, vaid ainult need, millel funktsiooni Ф väärtus on 1. Täieliku tõetabeli konstrueerimise asemel ehitame selle analoogi - binaarse otsustuspuu. Selle puu iga haru vastab ühele lahendile ja määrab hulga, millel funktsiooni Ф väärtus on 1. Otsustuspuu harude arv langeb kokku võrrandisüsteemi lahendite arvuga.
Mis on binaarne otsustuspuu ja kuidas see on üles ehitatud, selgitan mitme ülesande näidetega.
Probleem 18
Mitu erinevat Boole'i muutujate x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 väärtuste komplekti on olemas, mis rahuldavad kahe võrrandi süsteemi?
Vastus: Süsteemil on 36 erinevat lahendust.
Lahendus: võrrandisüsteem sisaldab kahte võrrandit. Leiame esimese võrrandi lahendite arvu, sõltuvalt 5 muutujast – x 1 , x 2 , …x 5 . Esimest võrrandit võib omakorda käsitleda 5 võrrandisüsteemina. Nagu näidatud, kujutab võrrandisüsteem tegelikult loogiliste funktsioonide konjunktsiooni. Tõene on ka vastupidine väide – tingimuste konjunktsiooni võib käsitleda võrrandisüsteemina.
Koostame konjunktsiooni esimese liikme implikatsiooni (x1→ x2) jaoks otsustuspuu, mida võib pidada esimeseks võrrandiks. Selle puu graafiline kujutis näeb välja järgmine:
Puu koosneb kahest tasemest vastavalt võrrandi muutujate arvule. Esimene tase kirjeldab esimest muutujat X 1 . Selle taseme kaks haru kajastavad selle muutuja võimalikke väärtusi - 1 ja 0. Teisel tasemel kajastavad puu harud ainult neid muutuja X 2 võimalikke väärtusi, mille puhul võrrand võtab tõeseks. Kuna võrrand defineerib implikatsiooni, siis haru, millel X 1 väärtus on 1, eeldab, et X 2 on sellel harul väärtus 1. Haru, mille X 1 väärtus on 0, genereerib kaks haru, mille X 2 väärtus on võrdne 0 ja 1 Konstrueeritud puu määrab kolm lahendit, millele implikatsioon X 1 → X 2 saab väärtuse 1. Igal harul kirjutatakse välja vastav muutujate väärtuste komplekt, mis annab võrrandi lahendi.
Need komplektid on: ((1, 1), (0, 1), (0, 0))
Jätkame otsustuspuu koostamist, lisades järgmise võrrandi, järgmine implikatsioon X 2 → X 3 . Meie võrrandisüsteemi eripära seisneb selles, et süsteemi iga uus võrrand kasutab ühte muutujat eelmisest võrrandist, lisades ühe uue muutuja. Kuna muutujal X 2 on puus juba väärtused, siis kõigil harudel, kus muutuja X 2 väärtus on 1, on muutujal X 3 ka väärtus 1. Selliste harude puhul jätkub puu ehitamine järgmisele tasemele, kuid uusi harusid ei ilmu. Ainus haru, kus muutuja X 2 väärtus on 0, annab haru kaheks haruks, kus muutuja X 3 saab väärtused 0 ja 1. Seega iga uue võrrandi lisamine, arvestades selle spetsiifilisust, lisab ühe. lahendus. Algne esimene võrrand:
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
on 6 lahendust. Selle võrrandi täielik otsustuspuu näeb välja järgmine:
Meie süsteemi teine võrrand on sarnane esimesega:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
Ainus erinevus seisneb selles, et võrrandis kasutatakse muutujaid Y. Ka sellel võrrandil on 6 lahendit. Kuna iga muutuja lahendit X i saab kombineerida iga muutuja lahendiga Y j, on lahenduste koguarv 36.
Pange tähele, et konstrueeritud otsustuspuu ei anna mitte ainult lahenduste arvu (vastavalt harude arvule), vaid ka lahendusi ise, mis on välja kirjutatud puu igale oksale.
Probleem 19
Mitu erinevat tõeväärtuste muutujate x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1
See ülesanne on eelmise ülesande modifikatsioon. Erinevus seisneb selles, et lisatakse veel üks võrrand, mis seob X- ja Y-muutujaid.
Võrrandist X 1 → Y 1 järeldub, et kui X 1 väärtus on 1 (üks selline lahendus on olemas), siis Y 1 on väärtusega 1. Seega on üks hulk, millel on X 1 ja Y 1 väärtused 1. Kui X 1 on 0, võib Y 1-l olla mis tahes väärtus, nii 0 kui ka 1. Seetõttu vastab iga hulk, mille X 1 on 0, ja selliseid komplekte on 5, kõigile 6-le Y muutujaga komplektile. , on lahenduste koguarv 31 .
Probleem 20
(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1
Lahendus: põhilist ekvivalenti meeles pidades kirjutame võrrandi järgmiselt:
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1
Järelduste tsükliline ahel tähendab, et muutujad on identsed, seega on meie võrrand võrdne:
X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1
Sellel võrrandil on kaks lahendit, kui kõik X i on kas 1 või 0.
Probleem 21
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1
Lahendus: nii nagu ülesandes 20, liigume tsüklilistest implikatsioonidest identiteetide juurde, kirjutades võrrandi ümber järgmisel kujul:
(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1
Koostame selle võrrandi jaoks otsustuspuu: 
Probleem 22
Mitu lahendit on järgmisel võrrandisüsteemil?
((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0
((X 3 ≡X 4) ˄ (X5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X5 ≡X 6)) = 0
((X5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0
((X 7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X9 ≡X10)) = 0
Vastus: 64
Lahendus: Liigume 10 muutujalt 5 muutujani, viies sisse järgmise muutujate muudatuse:
Y 1 = (X1 ≡ X 2); Y 2 \u003d (X 3 ≡ X 4); Y3 = (X5 ≡ X 6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);
Siis saab esimene võrrand järgmise kuju:
(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0
Võrrandit saab lihtsustada, kirjutades selle järgmiselt:
(Y 1 ≡ Y 2) = 0
Traditsioonilisele vormile üle minnes kirjutame süsteemi pärast vormi lihtsustusi:
¬(Y 1 ≡ Y 2) = 1
¬(Y 2 ≡ Y 3) = 1
¬(Y 3 ≡ Y 4) = 1
¬(Y 4 ≡ Y 5) = 1
Selle süsteemi otsustuspuu on lihtne ja koosneb kahest harust vahelduvate muutujaväärtustega:
Tulles tagasi algsete X muutujate juurde, pange tähele, et iga muutuja Y väärtus vastab X muutuja 2 väärtusele, seega genereerib iga muutuja Y lahendus X muutujates 2 5 lahendust. Kaks haru genereerivad 2 * 2 5 lahendust , seega on lahenduste koguarv 64.
Nagu näete, nõuab iga võrrandisüsteemi lahendamise ülesanne oma lähenemist. Levinud nipp on võrrandite lihtsustamiseks samaväärsete teisenduste tegemine. Levinud tehnika on otsustuspuude ehitamine. Rakendatud lähenemine sarnaneb osaliselt tõetabeli konstrueerimisega selle eripäraga, et ei konstrueerita mitte kõiki muutujate võimalike väärtuste komplekte, vaid ainult neid, mille puhul funktsioon võtab väärtuse 1 (tõene). Sageli ei ole pakutud probleemide puhul vaja ehitada terviklikku otsustuspuud, kuna juba algstaadiumis on võimalik igal järgmisel tasemel kindlaks teha uute okste ilmumise regulaarsus, nagu tehti näiteks ülesandes 18 .
Üldiselt on loogikavõrrandisüsteemile lahenduste leidmise ülesanded head matemaatilised harjutused.
Kui ülesannet on raske käsitsi lahendada, siis võite ülesande lahendamise usaldada arvutile, kirjutades vastava programmi võrrandite ja võrrandisüsteemide lahendamiseks.
Sellist programmi on lihtne kirjutada. Selline programm saab hõlpsasti hakkama kõigi eksamil pakutavate ülesannetega.
Kummalisel kombel, aga loogikavõrrandisüsteemidele lahenduste leidmise ülesanne on ka arvuti jaoks keeruline, selgub, et arvutil on omad piirid. Arvuti saab hõlpsasti hakkama ülesannetega, kus muutujate arv on 20-30, kuid suuremate ülesannete peale hakkab ta pikalt mõtlema. Asi on selles, et funktsioon 2 n, mis määrab hulkade arvu, on eksponent, mis kasvab kiiresti koos n-ga. Nii kiiresti, et tavaline personaalarvuti ei saa päeva jooksul hakkama 40 muutujaga ülesandega.
C# programm loogikavõrrandite lahendamiseks
Loogikavõrrandite lahendamise programmi kirjutamine on kasulik mitmel põhjusel, kasvõi juba sellepärast, et selle abil saab kontrollida enda lahenduse õigsust USE testi probleemidele. Teine põhjus on see, et selline programm on suurepärane näide programmeerimisprobleemist, mis vastab USE C-kategooria probleemide nõuetele.
Programmi koostamise idee on lihtne – see põhineb kõigi võimalike muutujaväärtuste komplektide täielikul loetlemisel. Kuna antud loogilise võrrandi või võrrandisüsteemi puhul on teada muutujate arv n, siis on teada ka hulkade arv - 2 n , mis tuleb välja sorteerida. Kasutades C# keele põhifunktsioone – eitust, disjunktsiooni, konjunktsiooni ja identiteeti, on lihtne kirjutada programm, mis antud muutujate hulga puhul arvutab loogilisele võrrandile või võrrandisüsteemile vastava loogilise funktsiooni väärtuse.
Sellises programmis peate tsükli koostama komplektide arvu järgi, tsükli põhiosas komplekti numbri järgi moodustama hulga ise, arvutama selle hulga funktsiooni väärtuse ja kui see väärtus on võrdne 1-ni, siis annab hulk võrrandile lahenduse.
Ainus programmi rakendamisel tekkiv raskus on seotud ülesandega moodustada muutujate väärtuste komplekt seatud numbri järgi. Selle ülesande ilu seisneb selles, et see näiliselt keeruline ülesanne taandub tegelikult lihtsale ülesandele, mis on juba korduvalt esile kerkinud. Tõepoolest, piisab, kui mõista, et arvule i vastavate muutujate väärtuste kogum, mis koosneb nullidest ja ühtedest, tähistab arvu i binaarset esitust. Nii et keeruline ülesanne saada muutujate väärtuste kogum seatud arvu järgi taandub üldtuntud probleemiks numbri teisendamiseks kahendsüsteemiks.
Meie probleemi lahendav C#-funktsioon näeb välja selline:
///
/// programm lahenduste arvu lugemiseks
/// loogiline võrrand (võrrandisüsteem)
///
///
/// loogiline funktsioon – meetod,
/// kelle allkirja määrab DF delegaat
///
/// muutujate arv
///
staatiline int Lahendage võrrandid (DF lõbus, int n)
bool set = uus bool[n];
int m = (int)Math.Pow(2, n); //komplektide arv
int p = 0, q = 0, k = 0;
//Täielik loendamine komplektide arvu järgi
jaoks (int i = 0; i< m; i++)
//Järgmise hulga moodustamine — komplekt,
//antud arvu i kahendesitusega
jaoks (int j = 0; j< n; j++)
k = (int)Math.Pow(2, j);
//Arvutage funktsiooni väärtus komplektis
Programmi mõistmiseks loodan, et programmi idee selgitustest ja selle tekstis sisalduvatest kommentaaridest piisab. Peatun vaid ülaltoodud funktsiooni pealkirja selgitusel. Funktsioonil SolveEquations on kaks sisendparameetrit. Fun parameeter määrab loogilise funktsiooni, mis vastab lahendatavale võrrandile või võrrandisüsteemile. Parameeter n määrab muutujate arvu funktsionaalsuses. Selle tulemusena tagastab funktsioon SolveEquations loogilise funktsiooni lahenduste arvu, st komplektide arvu, mille puhul funktsioon hindab tõeseks.
Koolilaste jaoks on tavaks, kui mõne funktsiooni F(x) sisendparameeter x on aritmeetiline, string või loogilist tüüpi muutuja. Meie puhul kasutatakse võimsamat disaini. Funktsioon SolveEquations viitab kõrgemat järku funktsioonidele – F(f) tüüpi funktsioonidele, mille parameetrid võivad olla mitte ainult lihtsad muutujad, vaid ka funktsioonid.
Funktsioonide klass, mida saab funktsioonile SolveEquations parameetrina edastada, on määratletud järgmiselt.
delegeeri bool DF(bool vars);
See klass sisaldab kõiki funktsioone, mis edastatakse parameetrina vars-massiiviga määratud tõeväärtuste muutujate väärtuste komplekt. Tulemuseks on Boole'i väärtus, mis tähistab selle komplekti funktsiooni väärtust.
Kokkuvõtteks annan programmi, milles SolveEquations funktsiooni kasutatakse mitmete loogikavõrrandisüsteemide lahendamiseks. Funktsioon SolveEquations on osa järgmisest ProgramCommon klassist:
klass ProgramCommon
delegeeri bool DF(bool vars);
staatiline tühimik Main (string args)
Console.WriteLine("Funktsioon ja lahendused - " +
Lahenda võrrandid (Lõbus ja 2));
Console.WriteLine("Funktsioonil on 51 lahendust - " +
Lahendage võrrandid (Fun51, 5));
Console.WriteLine("Funktsioonil on 53 lahendust - " +
Lahendage võrrandid (Fun53, 10));
staatiline bool FunAnd(bool vars)
tagastab varie && vars;
staatiline bool Fun51 (bool vars)
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
staatiline bool Fun53 (bool vars)
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && (!((vars == vari) || (vars == vars)));
Selle programmi lahenduse tulemused näevad välja järgmised:
10 ülesannet iseseisvaks tööks
- Millised kolmest funktsioonist on samaväärsed:
- (X → Y) ˅ ¬Y
- ¬(X ˅ ¬Y) ˄ (X → ¬Y)
- ¬X ˄ Y
- Tõetabelist on antud fragment:
| x1 | x2 | x3 | x4 | F |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
Milline kolmest funktsioonist vastab sellele fragmendile:
- (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
- (X 1 → X 3) ˄ X 2 ˅ X 4
- X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
- Žürii koosneb kolmest inimesest. Otsus on tehtud, kui selle poolt hääletab žürii esimees, keda toetab vähemalt üks žürii liige. Vastasel juhul otsust ei tehta. Looge loogiline funktsioon, mis vormistab otsustusprotsessi.
- X võidab Y üle, kui neli mündiviset löövad kolm korda vastu pead. Defineerige boolean funktsioon, mis kirjeldab väljamakset X.
- Lause sõnad nummerdatakse alates ühest. Lause loetakse hästi moodustatuks, kui on täidetud järgmised reeglid:
- Kui paarisarvuline sõna lõpeb vokaaliga, siis järgmine sõna, kui see on olemas, peab algama täishäälikuga.
- Kui paaritu numbriga sõna lõpeb kaashäälikuga, siis järgmine sõna, kui see on olemas, peab algama kaashäälikuga ja lõppema täishäälikuga.
Millised järgmistest lausetest on õiged: - Ema pesi Mašat seebiga.
- Juht on alati eeskujuks.
- Tõde on hea, aga õnn on parem.
- Mitu lahendit on võrrandil:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1 - Loetlege kõik võrrandi lahendid:
(a → b) → c = 0 - Mitu lahendit on järgmisel võrrandisüsteemil:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1 - Mitu lahendit on võrrandil:
(((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1
Vastused ülesannetele:
- Funktsioonid b ja c on samaväärsed.
- Fragment vastab funktsioonile b.
- Olgu boole'i muutuja P väärtuseks 1, kui žürii esimees hääletab otsuse "poolt". Muutujad M 1 ja M 2 esindavad žüriiliikmete arvamust. Loogilise funktsiooni, mis määrab positiivse otsuse vastuvõtmise, saab kirjutada järgmiselt:
P ˄ (M 1 ˅ M 2) - Olgu Boole'i muutuja P i väärtuseks 1, kui i-s mündivise tuleb üles. Loogilise funktsiooni, mis määrab väljamakse X, saab kirjutada järgmiselt:
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4)) - Pakkumine b.
- Võrrandil on 3 lahendit: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a=0; b=1; c=0)
Aasta lõpus selgus, et kolmest eeldusest vastas vaid üks. Millised osakonnad olid aasta lõpus kasumis?
Lahendus. Kirjutame ülesande tingimusest tulenevad eeldused loogiliste väidete kujul: „Kasumi saamine osakonna B järgi ei ole saamise vajalik tingimus
kasum ühiku A ":F 1 (A , B , C ) = A → B järgi
"Kasumi saamisest vähemalt ühe osakonna B ja C poolt ei piisa kasumi teenimiseks osakonnas A": F 2 (A , B , C ) = (B + C ) → A
"Divisjonid A ja B ei teeni samal ajal kasumit": F 3 (A , B , C ) = A B
Tingimusest on teada, et ainult üks kolmest eeldusest vastab tõele. See tähendab, et peame leidma, milline kolmest järgmisest loogilisest avaldisest ei ole identselt vale:
1) F 1F 2F 3
2) F 1F 2F 3
3) F 1F 2F 3
1) (A→ B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0
2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C
3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0
Järelikult osutus aasta lõpus tõeks teine oletus ning valeks esimene ja kolmas.
A=0 |
|||||||||
F1 F2 F3 = A B C= 1 |
|||||||||
siis ja ainult siis, kui B = 0 . |
|||||||||
C=1 |
|||||||||
Seetõttu saab see jaotus C kasumit, kuid divisjonid A ja B ei saa kasumit.
Loogikavõrrandite lahendamine
Riikliku tsentraliseeritud testimise tekstides on ülesanne (A8), milles tehakse ettepanek leida loogilise võrrandi juur. Vaatame näite abil, kuidas selliseid ülesandeid lahendada.
Leidke loogilise võrrandi juur: (A + B )(X AB ) = B + X → A .
Esimene lahendus on tõetabeli koostamine. Koostame võrrandi parema ja vasaku külje tõesuse tabelid ja vaatame, mille jaoks X vastavad nende tabelite viimastes veergudes olevad väärtused.
F1 (A, B, X) = (A+ B) (X AB)
A+B | (A+B)(X AB) | F 1 (A,B,X) |
|||||
F2 (A, B, X) = B + X → A
X→A | F 2 (A,B,X) |
|||||||||
X→A | X→A |
|||||||||
Võrdleme saadud tõesuse tabeleid ja valime need read, milles väärtused F 1 (A , B , X ) ja F 2 (A , B , X ) kattuvad.
F 1 (A,B,X) | F 2 (A,B,X) |
|||
Kirjutame ümber ainult valitud read, jättes alles vaid argumentide veerud. Vaatame muutujat X A ja B funktsioonina.
On ilmne, et X = B → A .
Teine lahendus on asendada võrrandis võrdusmärk samaväärse märgiga ja seejärel lihtsustada saadud loogilist võrrandit.
Edasise töö hõlbustamiseks lihtsustame esmalt loogilise võrrandi paremat ja vasakut külge ning leiame nende eitused:
F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B
F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B
F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A
Asendame oma loogilises võrrandis oleva võrdusmärgi samaväärsuse märgiga:
F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +
+ (X A B+ X A B+ X A B) (B+ X A) =
= (X A B+ X B+ X A B) + (X A B+ X A B) =
Rühmitame selle avaldise loogilised liikmed ümber, võttes tegurid X ja X sulust välja.
X(A B) + X(B+ AB) = X(A B) + X(B+ A) =
Tähista T = A B , siis
X T+ X T= X↔ T.
Seega, et loogilisel võrrandil oleks lahendus: X = A B = B + A = B → A .
Arvuti loogilised elemendid. Funktsionaalskeemide koostamine
Matemaatiline loogika arvutitehnoloogia arenguga oli tihedas seoses arvutitehnoloogia disaini ja programmeerimisega. Loogika algebra leidis algselt laialdast rakendust selle väljatöötamisel relee-kontakt skeemid. Esimene fundamentaalne uurimus, mis juhtis arvutite projekteerimisega tegelevate inseneride tähelepanu võimalusele analüüsida elektriahelaid Boole'i algebra abil, avaldati 1938. aasta detsembris ameeriklase Claude Shannoni artiklis "Relay-Contact Circuits Symbolic Analysis of Relay-Contact Circuits". Pärast seda artiklit ei olnud arvutite kujundamine täielik ilma Boole'i algebra kasutamiseta.
Loogiline element on ahel, mis rakendab disjunktsiooni, konjunktsiooni ja inversiooni loogilisi operatsioone. Kaaluge loogiliste elementide rakendamist elektriliste relee-kontaktahelate kaudu, mis on teile tuttavad kooli füüsikakursusest.
Kontaktide jadaühendus
Kontaktide paralleelühendus
Teeme tabeli ahelate oleku sõltuvuste kohta kontaktide kõigist võimalikest olekutest. Tutvustame tähistust: 1 - kontakt on suletud, vooluringis on vool; 0 - kontakt on avatud, vooluringis puudub vool.
Vooluahela olek koos | Ahela olek paralleeliga |
||
jadaühendus | ühendus |
||
Nagu näete, vastab jadaühendusega vooluahel konjunktsiooni loogilisele toimimisele, kuna voolutugevus vooluringis ilmneb ainult siis, kui kontaktid A ja B on samaaegselt suletud. Rööpühendusega vooluahel vastab loogilise töö disjunktsioonile, kuna vooluahelas puudub vool ainult hetkel, kui mõlemad kontaktid on avatud.
Inversiooni loogiline toimimine realiseeritakse elektromagnetrelee kontaktahela kaudu, mille põhimõtet õpitakse koolifüüsika kursusel. Kontakt x on avatud, kui x on suletud ja vastupidi.
Relee-kontaktelementide kasutamine arvutite loogikalülituste ehitamisel ei ole end õigustanud madala töökindluse, suurte mõõtmete, suure voolutarbe ja väikese kiiruse tõttu. Elektroonikaseadmete (vaakum ja pooljuht) tulek võimaldas ehitada loogilisi elemente kiirusega 1 miljon lülitust sekundis ja rohkem. Pooljuhtide loogilised elemendid töötavad võtmerežiimis sarnaselt elektromagnetreleega. Kogu kontaktahelate kohta esitatud teooria kantakse üle pooljuhtelementidele. Pooljuhtide loogilisi elemente ei iseloomusta mitte kontaktide olek, vaid signaalide olemasolu sisendis ja väljundis.
Mõelge loogilistele elementidele, mis rakendavad põhilisi loogilisi toiminguid:
Inverter – rakendab eituse või inversiooni operatsiooni. Kell | |||||||||||||
inverteril on üks sisend ja üks väljund. Ilmub väljundsignaal | |||||||||||||
kui seda sisendis pole, ja vastupidi. | |||||||||||||
Konjunktor - | |||||||||||||
X1 X2 ... Xn | rakendab sideoperatsiooni. | Konjunktori juures |
|||||||||||
üks väljapääs ja vähemalt kaks sissepääsu. Signaal sisse |
|||||||||||||
väljund kuvatakse siis ja ainult siis |
|||||||||||||
kõik sisendid on signaliseeritud. | |||||||||||||
X2 + ... Xn |
|||||||||||||
Disjunktor – teostab disjunktsioonioperatsiooni. Kell | |||||||||||||
disjunktori üks väljund ja vähemalt kaks | |||||||||||||
Väljundsignaal ei ilmu siis ja ainult siis, kui | |||||||||||||
kui kõik sisendid ei ole signaalitud. | |||||||||||||
Ehitada | funktsionaalne |
||
F(X, Y, Z) = X(Y + Z) | |||
X+Z |
|||
funktsioonile vastav diagramm:
& F(X, Y, Z)
Probleemide lahendamine konjunktiivi-normaali abil
Ja disjunktiiv-normaalne vormid
IN Loogikaülesannete raamatutes on sageli standardülesandeid, kus peate üles kirjutama funktsiooni, mis rakendab redeldiagramm, lihtsustage seda ja koostage selle funktsiooni jaoks tõesuse tabel. Kuidas lahendada vastupidine probleem? Arvestades suvalise tõetabelit, peate ehitama funktsionaalse või releekontakti vooluringi. Selle probleemiga tegeleme täna.
Loogika algebra mis tahes funktsiooni saab esitada kolme operatsiooni kombinatsiooniga: konjunktsioon, disjunktsioon ja inversioon. Vaatame, kuidas see tehtud on. Selleks paneme kirja mitu definitsiooni.
Minterm on funktsioon, mis moodustub teatud arvu muutujate või nende eituste konjunktsioonist. Minterm võtab kõigist võimalikest kogumitest ainsa väärtuse 1
argumendid ja väärtus 0 kõigi teiste jaoks. Näide: x 1 x 2 x 3 x 4 .
Maksterm on funktsioon, mis moodustub teatud arvu muutujate või nende eituste disjunktsioonist. Maxterm võtab ühes võimalikust hulgast väärtuse 0 ja kõigis teistes 1.
Näide: x 1 + x 2 + x 3 .
Funktsioon sisse disjunktiivne normaalvorm(DNF) on mintermide loogiline summa.
Näide: x 1x 2+ x 1x 2+ x 1x 2x 3.
Konjunktiivne normaalvorm(CNF) on elementaarsete disjunktsioonide (maxterms) loogiline korrutis.
Näide: (x 1+ x 2+ x 3) (x 1+ x 2) .
Täiuslik disjunktiivne normaalvorm nimetatakse DNF-iks, mille iga mintermin sisaldab kõiki muutujaid või nende eitusi.
Näide: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3
Täiuslik konjunktiivne normaalvorm nimetatakse CNF-iks, mille igas max-terminis on kõik muutujad või nende eitused.
Näide: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)
Loogilise funktsiooni salvestamine tabelisse
Mis tahes loogilist funktsiooni saab väljendada kui SDNF või SKNF. Vaatleme näiteks tabelis esitatud funktsiooni f.
f(x1, x2, x3) | ||||||||
Funktsioonid G0, G1, G4, G5, G7 on mintermid (vt definitsiooni). Kõik need funktsioonid on kolme muutuja või nende pöördväärtuse korrutis ja saavad väärtuse 1 ainult ühes olukorras. Näha on, et funktsiooni f väärtuseks 1 saamiseks on vaja ühte mintermi. Seetõttu on selle funktsiooni SDNF-i moodustavate mintermide arv võrdne funktsiooni väärtuses olevate üheliste arvuga: f= G0+G1+G4+G5+G7. Seega on SDNF vorm:
f (x 1, x 2, x 3) = x 1 x 2 x 3+ x 1 x 2 x 3+ x 1 x 2 x 3+ x 1 x 2 x 3+ x 1 x 2 x 3.
Samamoodi saab konstrueerida SKNF-i. Tegurite arv võrdub nullide arvuga funktsiooni väärtustes:
f (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .
Seega saab valemina kirjutada iga tabeli kujul antud loogilise funktsiooni.
Algoritm SDNF-i koostamiseks tõesuse tabeli järgi
Teatud on mõne funktsiooni tõesuse tabel. SDNF-i loomiseks peate tegema järgmised sammud:
1. Valige tabelist kõik read, kus funktsioon võtab väärtuse 1.
2. Igale sellisele reale määratakse kõigi argumentide või nende inversioonide konjunktsioon (minterm). Sel juhul sisestab argument, mis võtab väärtuse 0, mintermi koos eitusega ja väärtus 1 sisestab mintermi ilma eituseta.
3. Lõpuks moodustame kõigi saadud minttermide disjunktsiooni. Mintermide arv peab ühtima loogilise funktsiooni ühikute arvuga.
Algoritm SKNF-i koostamiseks tõesuse tabeli järgi
Teatud on mõne funktsiooni tõesuse tabel. SKNF-i loomiseks peate tegema järgmised sammud:
1. Valige kõik tabeliread, kus funktsioon võtab väärtuse 0.
2. Igale sellisele reale on määratud kõigi argumentide või nende inversioonide disjunktsioon (maxterm). Sel juhul kaasatakse argument, mis võtab väärtuse 1, maxtermini koos eitusega ja väärtus 1 kaasatakse eituseta.
3. Lõpuks moodustame kõigi saadud maxterminite konjunktsiooni. Maxterminite arv peab ühtima loogilise funktsiooni nullide arvuga.
Kui nõustume kahest vormist (SDNF või SKNF) eelistama seda, mis sisaldab vähem tähti, siis eelistatakse SDNF-i, kui tõetabeli funktsiooni väärtuste hulgas on neid vähem, SKNF - kui nulle on vähem.
Näide. Antud on kolme muutuja loogilise funktsiooni tõesuse tabel. Looge loogiline valem, mis seda funktsiooni rakendab.
F(A, B, C) |
|||
Valime antud tõesuse tabelist need read, milles funktsiooni väärtus võrdub 0-ga.
F(A, B, C) = (A+ B+ C) (A+ B+ C)
Kontrollime tuletatud funktsiooni, koostades tõesuse tabeli.
Võrreldes esialgset ja lõplikku tõesuse tabelit, võime järeldada, et loogiline funktsioon on õigesti üles ehitatud.
Probleemi lahendamine
1. Kolm õpetajat valivad olümpiaadile ülesanded. Valikus on mitu ülesannet. Iga ülesande kohta avaldab iga õpetaja oma arvamust: lihtne (0) või raske (1) ülesanne. Ülesanne arvatakse olümpiaadi ülesande hulka, kui vähemalt kaks õpetajat on selle raskeks märkinud, aga kui kõik kolm õpetajat peavad seda raskeks, siis selline ülesanne olümpiaadi ülesandesse liiga raskena ei kuulu. Tehke loogiline diagramm seadmest, mis väljastab 1, kui probleem sisaldub olümpiaadi ülesandes ja 0, kui see pole kaasatud.
Koostame soovitud funktsiooni tõesuse tabeli. Meil on kolm sisendmuutujat (kolm õpetajat). Seetõttu on soovitud funktsioon kolme muutuja funktsioon.
Probleemi seisukorda analüüsides saame järgmise tõesuse tabeli:
Ehitame SDNF-i. F(A, B, C) = ABC + ABC + ABC
Nüüd koostame selle funktsiooni loogikaahela.
B ja 1F(A,B,C)
2. Linnaolümpiaad informaatika algkursusel, 2007. a.Koostage kolmekorruselise maja sissepääsu jaoks elektriskeem, et mis tahes korruse lüliti saaks kogu maja valgust sisse või välja lülitada.
Niisiis, meil on kolm lülitit, millega peame valguse sisse ja välja lülitama. Igal lülitil on kaks olekut: kõrge (0) ja madal (1). Oletame, et kui kõik kolm lülitit on asendis 0, on sissepääsu valgus kustunud. Seejärel, kui liigutate mõne kolmest lülitist asendisse 1, peaks sissepääsu tuli süttima. Ilmselgelt kustub sissepääsu valgus, kui viite mõne muu lüliti asendisse 1. Kui kolmas lüliti liigutatakse asendisse 1, süttib sissepääsu valgus. Me koostame tõetabeli.
Siis F(A, B, C) = ABC+ ABC+ ABC+ ABC.
3. Muuda seisukorda | loogikafunktsiooni väärtused | F(A, B, C) = C → | A+B | ||||||||
argumentide B ja C samaaegne muutmine on võrdne: | |||||||||||
A→(B C) | (B C) → A |
||||||||||
A(B C) |
|||||||||||
4) (B C) → A | A→(B C) | ||||||||||
Märge. Selle probleemi edukaks lahendamiseks pidage meeles järgmisi loogilisi valemeid:
x → y= x+ y x y= x y+ x y
x ↔ y= x y + x y
Meile on antud kolme muutuja loogiline funktsioon F 1 (A , B , C ) = C → A + B = C + A B .
Muudame muutujaid B ja C korraga: F 2 (A , B , C ) = F 1 (A , B , C ) = C + A B . Koostame nende kahe funktsiooni tõesuse tabelid:
Analüüsime saadud tabelit. Tabeli kaheksast reast ainult kahel (2. ja 3.) funktsioon oma väärtust ei muuda. Pange tähele, et nendel ridadel muutuja A oma väärtust ei muuda, samas kui muutujad B ja C seda teevad.
Ehitame SKNF-i funktsioone vastavalt järgmistele ridadele:
F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .
A+ (B↔ C) = A+ B C= (B C) → A
Seetõttu on nõutav vastus 4.
4. Loogilise funktsiooni väärtuse muutmise tingimus F (A , B , C ) = C + AB argumentide A ja B muutmisel on võrdne:
1) C+ (A B) | ||||||||||||||||||||||||||||||||||
C + (A B) | TAKSO) |
|||||||||||||||||||||||||||||||||
4) C(A B) | ||||||||||||||||||||||||||||||||||
C → (A B) | ||||||||||||||||||||||||||||||||||
F1 (A,B,C)= | ||||||||||||||||||||||||||||||||||
C+AB | ||||||||||||||||||||||||||||||||||
F 2 (A,B,C)= F 1 ( | C)=A | |||||||||||||||||||||||||||||||||
Me koostame tõetabeli. | ||||||||||||||||||||||||||||||||||
Analüüsime saadud tabelit. Tabeli kaheksast reast ainult kahes (1. ja 7.) muudab funktsioon oma väärtust. Pange tähele, et nendel ridadel muutuja C väärtust ei muuda, muutujad A ja B aga.
Ehitame SDNF-i funktsioone vastavalt järgmistele ridadele:
F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)
Seetõttu on nõutav vastus 2.
Viited
1. Shapiro S.I. Loogika- ja mänguprobleemide lahendamine(loogilised ja psühholoogilised uuringud). - M.: Raadio ja side, 1984. - 152 lk.
2. Šolomov L.A. Diskreetloogika ja arvutusseadmete teooria alused. – M.: Teadus. Ch. toim. füüsiline - matt. lit., 1980. - 400 lk.
3. Pukhalsky G.I., Novoseltseva T.Ya. Diskreetsete seadmete projekteerimine integraallülitustel.: Käsiraamat. - M .: Raadio ja side, 1990.
See materjal sisaldab ettekannet, mis esitab informaatika ühtse riigieksami ülesande B15 (nr 23, 2015) loogikavõrrandite ja loogikavõrrandisüsteemide lahendamise meetodeid. Teadaolevalt on see ülesanne eksami ülesannete hulgas üks raskemaid. Esitlus võib olla kasulik õppetundide läbiviimisel teemal "Loogika" erialaklassides, samuti eksami sooritamiseks valmistumisel.
Lae alla:
Eelvaade:
Esitluste eelvaate kasutamiseks looge Google'i konto (konto) ja logige sisse: https://accounts.google.com
Slaidide pealdised:
Ülesande B15 (loogikavõrrandite süsteem) lahendus Višnevskaja M.P., MAOU "Gümnaasium nr 3" 18. november 2013, Saratov
Ülesanne B15 on arvutiteaduse eksami üks raskemaid !!! Kontrollitakse oskusi: teisendada loogilisi muutujaid sisaldavaid avaldisi; kirjeldage loomulikus keeles loogiliste muutujate väärtuste komplekti, mille puhul antud loogiliste muutujate komplekt on tõene; loenda binaarhulkade arv, mis vastavad antud tingimustele. Kõige raskem, sest pole ametlikke reegleid, kuidas seda teha, on vaja oletada.
Milleta mitte teha!
Milleta mitte teha!
Konventsioonide konjunktsioon: A /\ B , A B , AB , А &B, A ja B disjunktsioon: A \ / B , A + B , A | B , A või B eitus: A , A, mitte A ekvivalent: A B, A B, A B XOR: A B , A xor B
Muutujate asendusmeetod Mitu erinevat Boole'i muutujate x1, x2, ..., x9, x10 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5) ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Vastuses ei pea loetlema kõiki erinevaid komplekte x1, x2, …, x9, x10, mille all antud võrdsuste süsteem on täidetud. Vastuseks peate märkima selliste komplektide arvu (demoversioon 2012)
Lahendus 1. samm. Lihtsustage muutujate muutmisega t1 = x1 x2 t2 = x3 x4 t3 = x5 x6 t4 = x7 x8 t5 = x9 x10 Pärast lihtsustamist: (t1 \/ t2) /\/ (¬t1 ) t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Vaatleme ühte võrranditest: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Ilmselgelt on see =1 ainult siis, kui üks muutujatest on 0 ja teine on 1 XOR-tehte väljendamiseks konjunktsiooni ja disjunktsiooni kaudu kasutame valemit: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1 t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1
2. samm. Süsteemi analüüs .To. tk = x2k-1 ≡ x2k (t1 = x1 x2 ,….), siis iga väärtus tk vastab kahele väärtuste paarile x2k-1 ja x2k, näiteks: tk =0 vastab kahele paarile - (0, 1) ja (1, 0) ning tk =1 on paarid (0,0) ja (1,1).
3. samm. Lahenduste arvu loendamine. Igal t-l on 2 lahendit, t arv on 5. Seega muutujate t jaoks on 2 5 = 32 lahendit. Kuid igale t-le vastab lahenduste paar x, s.t. algses süsteemis on 2*32 = 64 lahendust. Vastus: 64
Osalise lahenduse elimineerimise meetod Mitu erinevat loogiliste muutujate x1, x2, …, x5, y1,y2,…, y5 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele: (x1→ x2)∧(x2→x3)∧ (x3 → x4 )∧(x4 → x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5 → x5 =1. Vastuses pole vaja loetleda kõiki erinevaid hulki x1, x2, ..., x5, y 1, y2, ..., y5, mille puhul see võrdsuste süsteem on täidetud. Vastuseks peate märkima selliste komplektide arvu.
Lahendus. Samm 1. Võrrandite järjestuslahendus x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 kõik tagajärjed on tõesed. Implikatsioon on väär ainult ühel juhul, kui 1 0, kõigil muudel juhtudel (0 0, 0 1, 1 1) tagastab tehe 1. Kirjutame selle tabeli kujul:
Samm 1. Võrrandite järjestiklahend Т.о. х1,х2,х3,х4,х5 jaoks saadakse 6 komplekti lahendusi: (00000), (00001), (00011), (00111), (01111), (11111). Sarnaselt arutledes järeldame, et y1, y2, y3, y4, y5 jaoks on sama lahendite hulk. Sest need võrrandid on sõltumatud, st. neis pole ühiseid muutujaid, siis on selle võrrandisüsteemi lahendus (kolmandat võrrandit arvesse võtmata) 6 * 6 = 36 paari “xe” ja “jah”. Vaatleme kolmandat võrrandit: y5→ x5 =1 Lahenduseks on paarid: 0 0 0 1 1 1 Paar ei ole lahendus: 1 0
Võrdleme saadud lahendeid Kuhu y5 =1, x5=0 ei sobi. selliseid paare on 5. Süsteemi lahendite arv: 36-5= 31. Vastus: 31 Kulus kombinatoorika!!!
Dünaamiline programmeerimismeetod Mitu erinevat lahendust on loogilisel võrrandil x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, kus x 1, x 2, ..., x 6 on loogilised muutujad? Vastus ei pea loetlema kõiki erinevaid muutujaväärtuste komplekte, mille puhul see võrdsus kehtib. Vastuseks peate märkima selliste komplektide arvu.
Lahenduse samm 1. Tingimuse analüüs Võrrandi vasakul küljel on implikatsioonitehted järjestikku kirjutatud, prioriteet on sama. Kirjutage ümber: (((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Iga järgmine muutuja ei sõltu eelmisest, vaid eelmise implikatsiooni tulemusest!
2. samm. Mustri paljastamine Vaatleme esimest implikatsiooni X 1 → X 2. Tõe tabel: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Ühest 0-st saime 2 ühte ja 1-st me sai ühe 0 ja ühe 1. Ainult üks 0 ja kolm 1, see on esimese tehte tulemus.
2. samm. Mustri paljastamine Ühendades x 3 esimese tehte tulemusega, saame: F(x 1 ,x 2) x 3 F(x 1 ,x 2) x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Kahest 0-st - kaks 1-st, igast 1-st (neid on 3) üks 0 ja 1 (3 + 3)
3. etapp. Valemi tuletamine saate teha valemeid nullide arvu N i ja ühtede arvu E i arvutamiseks i muutujatega võrrandi jaoks: ,
Etapp 4. Tabeli täitmine Täidame tabeli i = 6 jaoks vasakult paremale, arvutades ülaltoodud valemite abil nullide ja ühtede arvu; tabelis on näidatud, kuidas järgmine veerg eelmise järgi üles ehitatakse: : muutujate arv 1 2 3 4 5 6 Nullide arv N i 1 1 3 5 11 21 Üheliste arv E i 1 2*1+1= 3 2 *1+3= 5 11 21 43 Vastus: 43
Loogikavaldiste lihtsustusi kasutav meetod Mitu erinevat lahendit on võrrandil ((J → K) → (M N L)) ((M N L) → (¬ J K)) (M → J) = 1 kus J , K, L, M, N on loogilised muutujad? Vastuses ei pea loetlema kõiki erinevaid väärtuste komplekte J , K, L, M ja N, mille puhul see võrdsus kehtib. Vastuseks peate märkima selliste komplektide arvu.
Lahendus Pange tähele, et J → K = ¬ J K Toome sisse muutujate muutuse: J → K=A, M N L =B Kirjutame võrrandi ümber, võttes arvesse muutust: (A → B) (B → A) (M → J)=1 4. (A B) (M → J)= 1 5. Ilmselgelt A B samade A ja B väärtuste korral 6. Vaatleme viimast implikatsiooni M → J = 1 See on võimalik, kui: M = J = 0 M = 0, J = 1 M = J = 1
Lahendus A B , siis M=J=0 korral saame 1 + K=0. Lahendusi pole. M=0, J=1 korral saame 0 + K=0, K=0 ning N ja L - mis tahes, 4 lahendust: ¬ J K = M N L K N L 0 0 0 0 0 1 0 1 0 0 1 1
Lahendus 10. M=J=1 korral saame 0+K=1 *N * L ehk K=N*L, 4 lahendust: 11. Kokku on 4+4=8 lahendust Vastus: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1
Infoallikad: O.B. Bogomolova, D. Yu. Usenkov. B15: uued ülesanded ja uus lahendus // Informaatika, nr 6, 2012, lk. 35 – 39. K.Yu. Poljakov. Loogikavõrrandid // Informaatika, nr 14, 2011, lk. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektrooniline ressurss]. http://kpolyakov.narod.ru/school/ege.htm, [Elektrooniline ressurss].
Tunni teema: Loogikavõrrandite lahendamine
Haridus - loogikavõrrandite lahendamise õppimine, oskuste ja vilumuste kujundamine loogikavõrrandite lahendamiseks ning loogilise avaldise koostamiseks tõetabeli järgi;Haridus - luua tingimused õpilaste kognitiivse huvi arendamiseks, edendada mälu, tähelepanu, loogilise mõtlemise arengut;
Hariduslik : aitab kasvatada oskust kuulata teiste arvamusi, tahte ja visaduse kasvatamine lõpptulemuste saavutamiseks.
Tunni tüüp: kombineeritud õppetund
Varustus: arvuti, multimeediaprojektor, esitlus 6.
Tundide ajal
Põhiteadmiste kordamine ja täiendamine. Kodutööde kontrollimine (10 minutit)
Eelmistes tundides tutvusime loogika algebra põhiseadustega, õppisime neid seadusi kasutama loogikaväljendite lihtsustamiseks.
Vaatame loogiliste avaldiste lihtsustamise kodutööd:
1. Milline järgmistest sõnadest vastab loogilisele tingimusele:
(esimene konsonant → teine kaashäälik)٨ (viimase tähe vokaal → eelviimane tähtvokaal)? Kui selliseid sõnu on mitu, märkige neist väikseim.
1) ANNA 2) MARIA 3) OLEG 4) STEPAN
Tutvustame tähistust:
A on kaashääliku esimene täht
B on kaashääliku teine täht
S on viimane täishäälik
D - eelviimane täishäälik
Teeme väljendi:
Teeme tabeli:
2. Märkige, milline loogiline avaldis on avaldisega samaväärne
Lihtsustame algse väljendi ja pakutud valikute kirjutamist:
3. Avaldise F tõesuse tabeli fragment on antud:
Milline avaldis vastab F-le?
Määrame nende avaldiste väärtused argumentide määratud väärtuste jaoks:
Tunni teemaga tutvumine, uue materjali esitamine (30 minutit)
Jätkame loogika põhitõdede ja tänase tunni "Loogikavõrrandite lahendamine" teema uurimist. Peale selle teemaga tutvumist õpid põhilisi loogikavõrrandite lahendamise viise, omandad oskused nende võrrandite lahendamiseks kasutades loogikalgebra keelt ja oskust koostada tõetabelil loogilist avaldist.
1. Lahendage loogiline võrrand
(¬K M) → (¬L M N) = 0
Kirjutage oma vastus neljast märgist koosneva stringina: muutujate K, L, M ja N väärtused (selles järjekorras). Näiteks rida 1101 vastab K=1, L=1, M=0, N=1.
Lahendus:
Teisendame väljendit(¬K M) → (¬L M N)
Avaldis on väär, kui mõlemad terminid on valed. Teine liige on 0, kui M=0, N=0, L=1. Esimeses liikmes K = 0, kuna M = 0 ja 
.
Vastus: 0100
2. Mitu lahendit on võrrandil (vastuses märkige ainult arv)?
Lahendus: teisenda avaldist
(A+B)*(C+D)=1
A+B=1 ja C+D=1
2. meetod: tõetabeli koostamine
3 viis: SDNF konstruktsioon - funktsiooni täiuslik disjunktiivne normaalvorm - täielike korrapäraste elementaarsidendite disjunktsioon.Teisendame algse avaldise, avame sulud, et saada sidesõnade disjunktsioon:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Täiendame sidesõnu täielikeks sidesõnadeks (kõikide argumentide korrutis), avame sulud:
Mõelge samadele sidesõnadele:
Selle tulemusena saame SDNF-i, mis sisaldab 9 sidesõna. Seetõttu on selle funktsiooni tõesuse tabeli väärtus 1 9 real 2 4 =16 muutujaväärtuste komplektist.
3. Mitu lahendit on võrrandil (vastuses märkige ainult arv)?
Lihtsustame väljendit:
,
3 viis: SDNF ehitus
Mõelge samadele sidesõnadele:
Selle tulemusena saame SDNF-i, mis sisaldab 5 sidesõna. Seetõttu on selle funktsiooni tõesuse tabeli väärtus 1 5 real 2 4 =16 muutujaväärtuste komplekti.
Loogilise avaldise koostamine tõetabeli järgi:
Iga 1-t sisaldava tõetabeli rea jaoks koostame argumentide korrutise ja 0-ga võrdsed muutujad kaasatakse eitusega korrutisesse ja 1-ga võrdsed - ilma eituseta. Soovitud avaldis F koosneb saadud toodete summast. Siis tuleks võimalusel seda väljendit lihtsustada.
Näide: on antud avaldise tõesuse tabel. Looge loogiline avaldis.
Lahendus:3. Kodutöö (5 minutit)
Lahenda võrrand:
Mitu lahendit on võrrandil (vasta ainult arvule)?
Koosta etteantud tõetabeli järgi loogiline avaldis ja
seda lihtsustada.