Informaatika ühtne riigieksam loogikavõrrandite lahendusmeetodid. Loogikavõrrandite lahendamine matemaatikas

Kuidas lahendada mõningaid ülesandeid arvutiteaduse eksami A ja B osas

Õ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. Toon välja propositsiooniloogika põhiseadused.

1. Disjunktsiooni ja konjunktsiooni kommutatiivsus:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Disjunktsiooni ja konjunktsiooni käsitlev distributsiooniseadus:
   a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negatiivne eitus:
   ¬(¬a) ≡ a
4. Järjepidevus:
   a ^ ¬a ≡ vale
5. Eksklusiivne kolmas:
   a ˅ ¬a ≡ tõsi
6. De Morgani seadused:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Lihtsustamine:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ tõsi ≡ a
   a ˄ väär ≡ vale
8. Imendumine:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Implikatsiooni asendamine
   a → b ≡ ¬a ˅ b
10. 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. Representatsioonid 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. IN KASUTAGE ülesandeid koos nende funktsioonidega kaasneb 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

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Funktsioon number 3.

Ülesande lahendamiseks on vaja teada põhifunktsioonide tõetabeleid ja silmas pidada tehte 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.

1. 13579
2. 97531
3. 24678
4. 15386

Tingimuse täidab number 4.

Esimesed kaks numbrit ei vasta tingimusele põhjusel, et väikseim 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.

Probleem 17: Kaks tunnistajat tunnistasid järgmiselt:

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 tuleneb ainult kaks asja. võimalikud variandid A ja B on süüdi ja C on süütu või A ja C on süüdi ja B on süütu. Esimese tunnistaja ütlused on vähem informatiivsed - neid on 5 erinevaid valikuid vastab tema tunnistusele. Ü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 võrrandi C lahendid, null. 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 funktsioonile Ф tõesuse tabelit, mis võimaldab öelda, mitu lahendust süsteemil on ja millised on lahendusi andvad hulgad.

Mõnes loogikavõrrandisüsteemile lahenduste leidmise ühtse riigieksami ü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 üldine viis, mis erineb loendamisest, mis võimaldab 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 peegeldavad 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 määratleb implikatsiooni, nõuab haru, millel X 1 väärtus on 1, seda, et X 2 sellel harul oleks 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 defineerib kolm lahendit, millele implikatsioon X 1 → X 2 saab väärtuse 1. Igale harule kirjutatakse vastav muutujate väärtuste komplekt, mis annab võrrandi lahendi.

Need komplektid on: ((1, 1), (0, 1), (0, 0))

Jätkame otsustuspuu ehitamist, 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 haru. 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 lahendused ise, mis on igale puu harule välja kirjutatud.

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 tuleneb, 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 võrdub 0, võib Y 1 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. Peamist ekvivalentsust 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

Mõjutuste 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: 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 tasandil 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 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 C-kategooria probleemide nõuetele USE-s.

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 komplekti 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 hulga arvu järgi moodustama hulga ise, arvutama selle hulga funktsiooni väärtuse ja kui see väärtus on võrdne 1-ga, siis annab hulk võrrandi lahendi.

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. Seega taandatakse keerukas probleem muutujate väärtuste kogumi saamiseks määratud arvu järgi numbrite kahendsüsteemiks teisendamise üldtuntud probleemiks.

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

/// lahenduste 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 piisab programmi idee selgitustest ja kommentaaridest selle tekstis. 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 tõeväärtuslik 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 - " +

Lahenda 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

1. Millised kolmest funktsioonist on samaväärsed:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. 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:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Žürii koosneb kolmest inimesest. Otsus on langetatud, 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.
5. X võidab Y üle, kui neli mündiviset löövad kolm korda vastu pead. Defineerige boolean funktsioon, mis kirjeldab väljamakset X.
6. Lause sõnad nummerdatakse alates ühest. Lause loetakse hästi moodustatuks, kui on täidetud järgmised reeglid:
   1. Kui paarisarvuline sõna lõpeb vokaaliga, siis järgmine sõna, kui see on olemas, peab algama täishäälikuga.
   2. 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:
   3. Ema pesi Mašat seebiga.
   4. Juht on alati eeskujuks.
   5. Tõde on hea, aga õnn on parem.
7. Mitu lahendit on võrrandil:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Loetlege kõik võrrandi lahendid:
   (a → b) → c = 0
9. 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
10. Mitu lahendit on võrrandil:
    (((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Vastused ülesannetele:

1. Funktsioonid b ja c on samaväärsed.
2. Fragment vastab funktsioonile b.
3. 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)
4. 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))
5. Pakkumine b.
6. Võrrandil on 3 lahendit: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a=0; b=1; c=0)

Loogikavõrrandisüsteemide lahendamise meetodid

Pärast iga võrrandi lihtsustamist saate lahendada loogiliste võrrandite süsteemi, kasutades näiteks tõesuse tabelit (kui muutujate arv ei ole liiga suur) või otsustuspuud.

1. Muutujate muutmise meetod.

Uute muutujate kasutuselevõtt võimaldab võrrandisüsteemi lihtsustada, vähendades tundmatute arvu.Uued muutujad peavad olema üksteisest sõltumatud. Pärast lihtsustatud süsteemi lahendamist on vaja uuesti naasta algsete muutujate juurde.

Mõelge selle meetodi rakendamisele konkreetse näite puhul.

Näide.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Lahendus:

Tutvustame uusi muutujaid: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Tähelepanu! Iga nende muutuja x1, x2, …, x10 peab sisalduma ainult ühes uues muutujad A, B, C, D, E, st. uued muutujad on üksteisest sõltumatud).

Siis näeb võrrandisüsteem välja selline:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Ehitame saadud süsteemist otsustuspuu:

Vaatleme võrrandit A=0, s.o. (X1≡ X2) = 0. Sellel on 2 juurt:

		X1 ≡ X2

Samast tabelist on näha, et ka võrrandil A \u003d 1 on 2 juurt. Korraldame juurte arvu otsustuspuul:

Ühe haru lahenduste arvu leidmiseks tuleb igal tasandil lahenduste arv korrutada. Vasakul harul on 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 lahendust; paremal harul on samuti 32 lahendust. Need. kogu süsteemis on 32+32=64 lahendust.

Vastus: 64.

2. Arutlusmeetod.

Loogiliste võrrandite süsteemide lahendamise keerukus seisneb täieliku otsustuspuu mahukuses. Arutlusmeetod võimaldab teil mitte ehitada tervet puud täielikult, kuid samal ajal mõista, mitu oksa sellel on. Vaatleme seda meetodit konkreetsete näidete põhjal.

Näide 1 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

Vastuses ei pea loetlema kõiki muutujate x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 erinevaid väärtuste komplekte, mille puhul antud võrdsuste süsteem on täidetud. Vastuseks peate märkima selliste komplektide arvu.

Lahendus:

Esimene ja teine ​​võrrand sisaldavad sõltumatuid muutujaid, mis on seotud kolmanda tingimusega. Koostame esimese ja teise võrrandi jaoks otsustuspuu.

Süsteemi otsustuspuu kujutamiseks esimesest ja teisest võrrandist on vaja jätkata esimese puu iga haru muutujate puuga juures . Sel viisil ehitatud puul on 36 oksa. Mõned neist harudest ei rahulda süsteemi kolmandat võrrandit. Märkige esimesele puule puu okste arv"at" , mis vastavad kolmandale võrrandile:

Täpsustame: kolmanda tingimuse täitmiseks x1=0 peab olema y1=1, st kõik puu oksad"X" , kus x1=0 saab jätkata ainult ühe oksaga puust"at" . Ja ainult ühe puuoksa jaoks"X" (paremal) sobivad kõik puu oksad"at". Seega sisaldab kogu süsteemi täielik puu 11 haru. Iga haru esindab ühte lahendust algsele võrrandisüsteemile. Seega on kogu süsteemil 11 lahendust.

Vastus: 11.

Näide 2 Kui palju erinevaid lahendeid on võrrandisüsteemil

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10) = 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬X10) = 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬X10) = 1

(X1 ≡ X10) = 0

kus x1, x2, …, x10 on tõeväärtuslikud muutujad? Vastus ei pea loetlema kõiki erinevaid muutujaväärtuste komplekte, mille puhul see võrdsus kehtib. Vastuseks peate märkima selliste komplektide arvu.

Lahendus: Lihtsustame süsteemi. Koostame esimese võrrandi osa tõesuse tabeli:

		X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)

Pöörake tähelepanu viimasele veerule, see ühtib toimingu tulemusega X1 ≡ X10.

X1 ≡ X10

Pärast lihtsustamist saame:

(X1 ≡ X2) ∨ (X1 ≡ X10) = 1

(X2 ≡ X3) ∨ (X2 ≡ X10) = 1

(X3 ≡ X4) ∨ (X3 ≡ X10) = 1

……

(X9 ≡ X10) ∨ (X9 ≡ X10) = 1

(X1 ≡ X10) = 0

Mõelge viimasele võrrandile:(X1 ≡ X10) = 0, s.o. x1 ei tohiks olla sama mis x10. Et esimene võrrand oleks võrdne 1-ga, peab võrdus kehtima(X1 ≡ X2) = 1, st. x1 peab ühtima x2-ga.

Ehitame esimese võrrandi jaoks otsustuspuu:

Vaatleme teist võrrandit: x10=1 ja x2=0 puhul sulgpeab olema võrdne 1-ga (st x2 on sama mis x3); x10=0 ja x2=1 sulg(X2 ≡ X10) = 0, seega sulg (X2 ≡ X3) peab olema võrdne 1-ga (st x2 on sama kui x3):

Sel viisil argumenteerides koostame kõigi võrrandite jaoks otsustuspuu:

Seega on võrrandisüsteemil ainult 2 lahendit.

Vastus: 2.

Näide 3

Mitu erinevat tõeväärtuste muutujate x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Lahendus:

Koostame 1. võrrandi otsustuspuu:

Mõelge teisele võrrandile:

• Kui x1 = 0 : teine ​​ja kolmas sulg on 0; et esimene sulg oleks võrdne 1-ga, peab y1=1, z1=1 (st antud juhul - 1 lahendus)
• Kui x1 = 1 : esimene sulg on 0; teiseks või kolmas sulg peab olema võrdne 1-ga; teine ​​sulg on võrdne 1-ga, kui y1=0 ja z1=1; kolmas sulg võrdub 1-ga, kui y1=1 ja z1=0 (st antud juhul - 2 lahendust).

Samamoodi ka ülejäänud võrrandite puhul. Pange tähele puu iga sõlme jaoks saadud lahenduste arvu:

Iga haru lahenduste arvu teadasaamiseks korrutame saadud arvud iga haru jaoks eraldi (vasakult paremale).

1 haru: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 lahendus

2 haru: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 lahendust

3. haru: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 lahendust

4 haru: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 lahendust

5 haru: 2 ⋅ 2 ⋅ 2 ⋅ 2 = 16 lahendust

Lisame saadud arvud: kokku 31 lahendust.

Vastus: 31.

3. Regulaarne juurte arvu suurendamine

Mõnes süsteemis sõltub järgmise võrrandi juurte arv eelmise võrrandi juurte arvust.

Näide 1 Mitu erinevat tõeväärtuste muutujate x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele tingimustele?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Lihtsustama esimene võrrand:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Seejärel võtab süsteem järgmise kuju:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4) = 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

Jne.

Igal järgmisel võrrandil on 2 juurt rohkem kui eelmisel.

4 võrrandil on 12 juurt;

Võrrandil 5 on 14 juurt

8 võrrandil on 20 juurt.

Vastus: 20 juurt.

Mõnikord kasvab juurte arv vastavalt Fibonacci arvude seadusele.

Loogikavõrrandisüsteemi lahendamine nõuab loomingulist lähenemist.

Olgu n muutuja loogiline funktsioon. Loogiline võrrand on järgmine:

Konstandi C väärtus on 1 või 0.

Loogilisel võrrandil võib olla 0 kuni erinevate lahenditeni. 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:

Tõepoolest, olgu võrrand antud:

Sel juhul võite minna samaväärse võrrandi juurde:

Vaatleme k loogilise võrrandi süsteemi:

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 konjunktsiooni:

Kui muutujate arv on väike, näiteks alla 5, siis ei ole keeruline koostada funktsioonile tõesuse tabelit, mis võimaldab öelda, mitu lahendust süsteemil on ja millised on lahendusi andvad hulgad.

Mõnes loogikavõrrandisüsteemile lahenduste leidmise ühtse riigieksami ü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 muud üldist meetodit peale loendamise, 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 on funktsiooni väärtus 1. Täieliku tõetabeli koostamise asemel ehitame selle analoogi – binaarse otsustuspuu. Selle puu iga haru vastab ühele lahendile ja määrab hulga, millel on funktsiooni väärtus 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 - . 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 otsustuspuu implikatsiooni () jaoks - sidesõna esimene liige, mida võib pidada esimeseks võrrandiks. Selle puu graafiline pilt näeb välja järgmine

Puu koosneb kahest tasemest vastavalt võrrandi muutujate arvule. Esimene tase kirjeldab esimest muutujat. Selle taseme kaks haru kajastavad selle muutuja võimalikke väärtusi - 1 ja 0. Teisel tasemel kajastavad puu harud ainult neid muutuja võimalikke väärtusi, mille puhul võrrand võtab tõeseks. Kuna võrrand defineerib implikatsiooni, nõuab haru, millel selle väärtus on 1, selle haru väärtust 1. Haru, mille väärtus on 0, genereerib kaks haru väärtustega 0 ja 1. Konstrueeritud puu defineerib kolm lahendit, kus implikatsioon saab väärtuse 1. Igal harul kirjutatakse välja vastav muutujate väärtuste komplekt, mis annab võrrandile lahendi.

Need komplektid on: ((1, 1), (0, 1), (0, 0))

Jätkame otsustuspuu loomist, lisades järgmise võrrandi, järgmise järelmõju. 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 on puus juba väärtused, siis kõigil harudel, kus muutuja väärtus on 1, on muutuja väärtus ka 1. Selliste harude puhul jätkub puu ehitamine järgmisele tasemele, kuid uusi oksi ei ilmu. Ainus haru, kus muutuja väärtus on 0, annab haru kaheks haruks, kus muutuja saab väärtused 0 ja 1. Seega iga uue võrrandi lisamine, arvestades selle spetsiifilisust, lisab ühe lahendi. Algne esimene võrrand:

on 6 lahendust. Selle võrrandi täielik otsustuspuu näeb välja järgmine:

Meie süsteemi teine ​​võrrand on sarnane esimesega:

Ainus erinevus seisneb selles, et võrrandis kasutatakse muutujaid Y. Ka sellel võrrandil on 6 lahendit. Kuna iga muutujalahendust saab kombineerida iga muutujalahendusega, on lahenduste koguarv 36.

Pange tähele, et konstrueeritud otsustuspuu ei anna mitte ainult lahenduste arvu (vastavalt harude arvule), vaid ka lahendused ise, mis on igale puu harule välja kirjutatud.

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?

See ülesanne on eelmise ülesande modifikatsioon. Erinevus seisneb selles, et lisatakse veel üks võrrand, mis seob X- ja Y-muutujaid.

Võrrandist tuleneb, et kui selle väärtus on 1 (üks selline lahendus on olemas), siis on sellel väärtus 1. Seega on üks hulk, millel ja mille väärtused on 1. Kui see on võrdne 0-ga, võib sellel olla mis tahes väärtus, nii 0 kui ka 1. Seetõttu vastab iga hulk, mis on võrdne 0-ga ja selliseid hulki on 5, kõigile 6-le muutujatega Y. Seetõttu on lahenduste koguarv 31.

Probleem 20

Lahendus. Peamist ekvivalentsust meeles pidades kirjutame võrrandi järgmiselt:

Mõjutuste tsükliline ahel tähendab, et muutujad on identsed, seega on meie võrrand võrdne:

Sellel võrrandil on kaks lahendit, kui kõik on kas 1 või 0.

Probleem 21

Mitu lahendit on võrrandil:

Lahendus: nagu ülesandes 20, liigume tsüklilistest implikatsioonidest identiteetide juurde, kirjutades võrrandi ümber järgmisel kujul:

Koostame selle võrrandi jaoks otsustuspuu:

Probleem 22

Mitu lahendit on järgmisel võrrandisüsteemil?

Võrrandite kasutamine on meie elus laialt levinud. Neid kasutatakse paljudes arvutustes, konstruktsioonide ehitamisel ja isegi spordis. Inimene on võrrandeid kasutanud juba iidsetest aegadest ja sellest ajast alates on nende kasutamine ainult suurenenud. Matemaatikas on teatud ülesanded, mis on pühendatud väidete loogikale. Seda tüüpi võrrandi lahendamiseks peab teil olema teatud hulk teadmisi: teadmised lauseloogika seadustest, teadmised 1 või 2 muutuja loogiliste funktsioonide tõesuse tabelitest, loogiliste avaldiste teisendamise meetodid. Lisaks peate teadma järgmisi loogikatehete omadusi: konjunktsioonid, disjunktsioonid, inversioonid, implikatsioonid ja ekvivalentsused.

Mis tahes loogilist funktsiooni väärtusest \ muutujad - \ saab määrata tõesuse tabeliga.

Lahendame mõned loogilised võrrandid:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Alustame lahendust \[X1\]-ga ja määrame, milliseid väärtusi see muutuja võib võtta: 0 ja 1. Järgmiseks kaaluge kõiki ülaltoodud väärtusi ja vaadake, mis \[X2.\] võib sel juhul olla

Nagu tabelist näha, on meie loogilisel võrrandil 11 lahendust.

Kust saab Internetis loogilise võrrandi lahendada?

Võrrandi saate lahendada meie veebisaidil https: //. Tasuta veebilahendaja võimaldab teil sekunditega lahendada mis tahes keerukusega võrguvõrrandi. Kõik, mida pead tegema, on lihtsalt sisestada oma andmed lahendajasse. Samuti saate vaadata videojuhendit ja õppida võrrandit lahendama meie veebisaidil. Ja kui teil on küsimusi, võite neid küsida meie Vkontakte grupis http://vk.com/pocketteacher. Liituge meie grupiga, aitame teid alati hea meelega.

Teenindusülesanne. Interneti-kalkulaator on mõeldud loogilise avaldise tõesuse tabeli koostamine.
Tõetabel – tabel, mis sisaldab kõiki võimalikke sisendmuutujate kombinatsioone ja neile vastavaid väljundväärtusi.
Tõetabelis on 2n rida, kus n on sisendmuutujate arv ja n+m veerud, kus m on väljundmuutujad.

Juhend. Klaviatuurilt sisestamisel kasutage järgmisi tavasid:

tõeväärtuslik väljend:

Vahetabelite väljund tõetabeli jaoks
SKNF hoone
SDNF ehitus
Zhegalkini polünoomi konstrueerimine
Veitch-Carnot kaardi ehitamine
Boole'i ​​funktsiooni minimeerimine

Näiteks loogiline avaldis abc+ab~c+a~bc tuleb sisestada järgmiselt: a*b*c+a*b=c+a=b*c
Andmete sisestamiseks loogilise diagrammi kujul kasutage seda teenust.

Loogikafunktsiooni sisestusreeglid

1. Kasutage v asemel + märki (disjunktsioon, VÕI).
2. Enne loogilist funktsiooni ei pea te funktsiooni tähistust täpsustama. Näiteks F(x,y)=(x|y)=(x^y) asemel tippige lihtsalt (x|y)=(x^y) .
3. Maksimaalne summa muutujad on 10 .

Arvuti loogikaahelate projekteerimine ja analüüs viiakse läbi matemaatika spetsiaalse osa - loogika algebra - abil. Loogika algebras saab eristada kolme peamist loogilist funktsiooni: "EI" (eitamine), "AND" (konjunktsioon), "OR" (disjunktsioon).
Mis tahes loogilise seadme loomiseks on vaja määrata iga väljundmuutuja sõltuvus praegusest sisendmuutujast, sellist sõltuvust nimetatakse lülitusfunktsiooniks või loogikalgebra funktsiooniks.
Loogikaalgebra funktsiooni nimetatakse täielikult määratletuks, kui kõik 2 n selle väärtust on antud, kus n on väljundmuutujate arv.
Kui kõik väärtused pole määratletud, nimetatakse funktsiooni osaliselt määratletuks.
Seadet nimetatakse loogiliseks, kui selle olekut kirjeldatakse loogikaalgebra funktsiooni abil.
Loogikaalgebra funktsiooni esitamiseks kasutatakse järgmisi meetodeid:
Algebralisel kujul on võimalik loogiliste elementide abil koostada loogilise seadme diagramm.


Joonis 1 – loogilise seadme skeem

Kõik loogika algebra operatsioonid on määratletud tõetabelid väärtused. Tõelisuse tabel määrab toimingu sooritamise tulemuse kõik võimalik x algsete väidete loogilised väärtused. Toimingute rakendamise tulemust kajastavate valikute arv sõltub loogilises avaldises olevate väidete arvust. Kui loogikaavaldises olevate väidete arv on N, siis tõesuse tabelis on 2 N rida, kuna võimalikke argumentide väärtusi on 2 N erinevat kombinatsiooni.

Toiming NOT – loogiline eitus (inversioon)

Loogilist operatsiooni EI rakendata ühele argumendile, mis võib olla kas lihtne või keeruline loogiline avaldis. Operatsiooni tulemus EI OLE järgmine:

• kui algne avaldis on tõene, on selle eituse tulemus väär;
• kui algne avaldis on väär, siis on selle eituse tulemus tõene.

Järgmisi kokkuleppeid EI aktsepteerita eitamistoimingu jaoks:
mitte A, Ā, mitte A, ¬A, !A
Eitustoimingu tulemus EI ole määratud järgmise tõesuse tabeliga:

A	mitte A
0	1
1	0

Eitustehte tulemus on tõene, kui algne väide on väär, ja vastupidi.

Operatsioon VÕI – loogiline liitmine (disjunktsioon, liit)

Loogiline VÕI-operatsioon täidab kahe lause kombineerimise funktsiooni, mis võib olla kas lihtne või keeruline loogiline avaldis. Avaldusi, mis on loogilise operatsiooni algsed, nimetatakse argumentideks. Operatsiooni VÕI tulemus on avaldis, mis on tõene siis ja ainult siis, kui vähemalt üks algsetest avaldistest on tõene.
Kasutatud tähistused: A või B, A V B, A või B, A||B.
VÕI-toimingu tulemus määratakse järgmise tõesuse tabeli abil:
Operatsiooni VÕI tulemus on tõene, kui A on tõene või B on tõene või A ja B on tõesed, ja väär, kui nii A kui ka B on väärad.

Tehe JA – loogiline korrutamine (konjunktsioon)

Loogikatehe JA täidab kahe väite (argumendi) lõikumisfunktsiooni, mis võib olla kas lihtne või keeruline loogiline avaldis. Operatsiooni JA tulemus on avaldis, mis on tõene siis ja ainult siis, kui mõlemad algsed avaldised on tõesed.
Kasutatud sümbolid: A ja B, A Λ B, A & B, A ja B.
Tehte JA tulemus määratakse järgmise tõesuse tabeli abil:

A	B	A ja B
0	0	0
0	1	0
1	0	0
1	1	1

Tehte JA tulemus on tõene siis ja ainult siis, kui väited A ja B on mõlemad tõesed ja väärad kõigil muudel juhtudel.

Operatsioon "IF-THEN" - loogiline tagajärg (implikatsioon)

See toiming ühendab kaks lihtsat loogilist avaldist, millest esimene on tingimus ja teine ​​on selle tingimuse tagajärg.
Rakendatud nimetused:
kui A, siis B; A tõmbab B-d ligi; kui A, siis B; A → B.
Tõe tabel:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Tagajärje (implikatsiooni) tehte tulemus on väär ainult siis, kui eeldus A on tõene ja järeldus B (tagajärg) on ​​väär.

Toiming "A siis ja ainult siis, kui B" (ekvivalentsus, samaväärsus)

Kohaldatav tähistus: A ↔ B, A ~ B.
Tõe tabel:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Modulo 2 liitmisoperatsioon (XOR, eksklusiivne või range disjunktsioon)

Kasutatud tähistus: A XOR B, A ⊕ B.
Tõe tabel:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Ekvivalentsustehe tulemus on tõene ainult siis, kui nii A kui ka B on mõlemad tõesed või mõlemad väärad.

Loogikatete ülimuslikkus

• Toimingud sulgudes
• Inversioon
• Sidesõna (&)
• Disjunktsioon (V), välistav VÕI (XOR), mooduli 2 summa
• Implikatsioon (→)
• Samaväärsus (↔)

Täiuslik disjunktiivne normaalvorm

Valemi täiuslik disjunktiivne normaalvorm(SDNF) on sellega samaväärne valem, mis on elementaarsidendite disjunktsioon, millel on järgmised omadused:

1. Iga valemi loogiline liige sisaldab kõiki muutujaid, mis sisalduvad funktsioonis F(x 1 ,x 2 ,...x n).
2. Kõik valemi loogilised terminid on erinevad.
3. Ükski loogiline termin ei sisalda muutujat ja selle eitust.
4. Ükski loogiline termin valemis ei sisalda sama muutujat kaks korda.

SDNF-i saab hankida kas tõetabelite või samaväärsete teisenduste abil.
Iga funktsiooni jaoks on SDNF ja SKNF üheselt määratletud kuni permutatsioonini.

Täiuslik konjunktiivne normaalvorm

Valemi täiuslik konjunktiivne normaalvorm (SKNF) on sellega samaväärne valem, mis on elementaardisjunktsioonide konjunktsioon, mis vastab järgmistele omadustele:

1. Kõik elementaardisjunktsioonid sisaldavad kõiki muutujaid, mis sisalduvad funktsioonis F(x 1 ,x 2 ,...x n).
2. Kõik elementaarsed disjunktsioonid on erinevad.
3. Iga elementaarne disjunktsioon sisaldab muutujat üks kord.
4. Ükski elementaarne disjunktsioon ei sisalda muutujat ja selle eitust.