Võrrandi lahendus 1. Liikuge võrrandi kirjutamise eesliite vormile, asendades eituste sümbolid ¬-ga 2. Koostage eritüüpi tõetabeli pealkiri 3. Täitke tõesuse tabeli read kõigi kombinatsioonide jaoks A ja B, asendades X asemel 0 või 1. 4. Genereerige tõesuse tabel X = F (A,B) jaoks 5. Kasutades tõesuse tabelit, määrake vajadusel funktsiooni X tüüp, kasutades SCNF konstrueerimise meetodeid. ja SDNF, mida arutatakse allpool.
Erikujulise tõetabeli konstrueerimine ¬((A+B)·(X A·B))=¬(B+¬(X A))
Tõelisuse tabel X=F(A, B) ABX vastab A VASTUSE implikatsiooni B eitamisele:
Loogiliste seadmete kombineeritud ahelad Põhielemendid (GOST): 1 A B disjunktsioon A B samaväärsus & A B konjunktsioon M2 A B XOR
Loogikaseadmete kombineeritud ahelad Põhielemendid (GOST): 1 A B Implikatsioon & A B Schaefferi element & A B Kaasimplikatsioon 1 A B Webb element
Näidislülitus F 1 & 1 & & 1M2 B A
Skeemide lahendamine 1 Variant - skeemi teisendamine keeruliseks loogiliseks avaldiseks ja seejärel selle lihtsustamine vastavalt loogikaseadustele. Variant 2 – tõetabeli koostamine ja seejärel vajadusel SKNF-i või SDNF-i kaudu ehitamine (vt allpool). Vaatleme teist võimalust, kuna see on lihtsam ja arusaadavam.
Tõetabeli AB A + B + · B B · A + A B A + · · ülesehitus
Tõesustabel F(A, B) ABX vastab A VASTUSE implikatsiooni B eitamisele:
SDNF ja SKNF (definitsioonid) Elementaarkonjunktsioon on mitme muutuja konjunktsioon, mis võetakse eitusega või ilma ning muutujate hulgas võib olla identseid muutujate hulgas võib olla identseid elementaarkonjunktsioonide mis tahes disjunktsioon Nimetagem seda disjunktiivseks normaalvormiks (DNF) Nimetagem mis tahes elementaardisjunktsiooni konjunktsiooni konjunktiivseks normaalvormiks (DNF).
SDNF ja SCNF (definitsioonid) Perfektset disjunktiivset normaalvormi (PDNF) nimetatakse DNF-iks, milles puuduvad identsed elementaarkonjunktsioonid ja kõik konjunktsioonid koosnevad samast muutujate hulgast, milles iga muutuja esineb ainult üks kord (võimalik, et koos eitusega). Perfektne konjunktiivne normaalvorm (PCNF) on CNF, milles identsed elementaardisjunktsioonid puuduvad ja kõik disjunktsioonid koosnevad samast muutujate hulgast, milles iga muutuja esineb ainult üks kord (võimalik, et koos eitusega).
Algoritm SDNF tõesuse tabelist saamiseks 1. Märgi tõesuse tabeli read, mille viimases veerus on 1. 2. Kirjutage iga märgitud rea kohta kõigi muutujate konjunktsioon järgmiselt: kui muutuja väärtus antud rida on 1, siis lisa see muutuja ise konjunktsiooni, kui on 0, siis selle eitus. 3. Seo kõik saadud sidesõnad disjunktsiooniks. Algoritm SCNF-i tõesuse tabelist saamiseks 1. Märgi tõesuse tabeli read, mille viimases veerus on 0. 2. Kirjutage iga märgitud rea jaoks välja kõigi muutujate disjunktsioon järgmiselt: kui muutuja väärtus antud rida on 0, siis kaasa see muutuja ise konjunktsiooni, kui võrdub 1-ga, siis selle eitus. 3. Seo kõik saadud disjunktsioonid konjunktsiooniks.
SKNF konstrueerimise näide XY F(X,Y) Märgi nullid 2. Disjunktsioonid: X + Y 3. Konjunktsioonid: (X + Y) · (X + Y)
Loogikavõrrandisüsteemide lahendamine muutujate muutmise teel
Muutujate asendamise meetodit kasutatakse juhul, kui mõned muutujad sisalduvad võrrandites ainult konkreetse avaldise kujul, mitte midagi muud. Siis saab seda avaldist tähistada uue muutujaga.
Näide 1.
Mitu erinevat loogiliste muutujate x1, x2, x3, x4, x5, x6, x7, x8 väärtuste komplekti on olemas, mis vastavad kõigile allpool loetletud tingimustele?
(x1 → x2) → (x3 → x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
Vastuses ei pea loetlema kõiki muutujate x1, x2, x3, x4, x5, x6, x7, x8 erinevaid väärtuste komplekte, mille puhul see võrdsuste süsteem on täidetud. Vastuseks peate märkima selliste komplektide arvu.
Lahendus:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
Seejärel saame süsteemi kirjutada ühe võrrandi kujul:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunktsioon on 1 (tõene), kui iga operandi väärtus on 1. See on kõik implikatsioonid peavad olema tõesed ja see kehtib kõigi väärtuste puhul, välja arvatud (1 → 0). Need. muutujate y1, y2, y3, y4 väärtuste tabelis ei tohiks üks olla nullist vasakul:
Need. tingimused on täidetud 5 komplekti y1-y4 puhul.
Sest y1 = x1 → x2, siis saavutatakse väärtus y1 = 0 ühel hulgal x1, x2: (1, 0) ja väärtus y1 = 1 – kolmel hulgal x1, x2: (0,0) , (0 ,1), (1.1). Samamoodi y2, y3, y4 jaoks.
Kuna muutuja y1 iga hulk (x1,x2) kombineeritakse iga muutuja y2 komplektiga (x3,x4) jne, korrutatakse muutujate x hulkade arv:
|
Komplektide arv x1…x8 kohta |
||||
Liidame komplektide arvu: 1 + 3 + 9 + 27 + 81 = 121.
Vastus: 121
Näide 2.
Mitu erinevat loogiliste muutujate x1, x2, ... x9, y1, y2, ... y9 väärtuste komplekti on olemas, mis vastavad kõigile allpool loetletud tingimustele?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
Vastuseks pole tarvis loetlege kõik muutujate x1, x2, ... x9, y1, y2, ... y9 erinevad väärtuste komplektid, mille puhul antud võrdussüsteem on täidetud. Vastuseks peate märkima selliste komplektide arvu.
Lahendus:
Teeme muutujate muudatuse:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Süsteemi saab kirjutada ühe võrrandina:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Ekvivalentsus on tõene ainult siis, kui mõlemad operandid on võrdsed. Sellel võrrandil on kaks lahenduste komplekti:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Sest zi = (xi ≡ yi), siis väärtus zi = 0 vastab kahele hulgale (xi,yi): (0,1) ja (1,0) ning väärtus zi = 1 vastab kahele hulgale (xi,yi) ): (0 ,0) ja (1,1).
Siis vastab esimene hulk z1, z2,…, z9 2 9 komplektile (x1,y1), (x2,y2),…, (x9,y9).
Sama number vastab teisele hulgale z1, z2,…, z9. Siis on kokku 2 9 +2 9 = 1024 komplekti.
Vastus: 1024
Loogikavõrrandisüsteemide lahendamine rekursiooni visuaalse määramise meetodil.
Seda meetodit kasutatakse juhul, kui võrrandisüsteem on üsna lihtne ja hulkade arvu suurendamise järjekord muutujate lisamisel on ilmne.
Näide 3.
Mitu erinevat lahendit on võrrandisüsteemil?
¬x9 ∨ x10 = 1,
kus x1, x2, … x10 on loogilised muutujad?
Vastuses pole vaja loetleda kõiki erinevaid väärtuste komplekte x1, x2, ... x10, mille puhul see võrdsuste süsteem on täidetud. Vastuseks peate märkima selliste komplektide arvu.
Lahendus:
Lahendame esimese võrrandi. Disjunktsioon on võrdne 1-ga, kui vähemalt üks selle operandidest on võrdne 1-ga lahendused on komplektid:
Kui x1=0 on kaks väärtust x2 (0 ja 1) ja x1=1 puhul on ainult üks väärtus x2 (1), nii et hulk (x1,x2) on võrrandi lahendus . Kokku on 3 komplekti.
Lisame muutuja x3 ja vaatleme teist võrrandit. See on sarnane esimesega, mis tähendab, et x2=0 korral on x3 kaks väärtust (0 ja 1) ning x2=1 puhul on ainult üks väärtus x3 (1), nii et hulk (x2 ,x3) on võrrandi lahend. Kokku on 4 komplekti.
On hästi näha, et teise muutuja lisamisel lisandub üks komplekt. Need. (i+1) muutujate hulga rekursiivne valem:
N i +1 = N i + 1. Siis saame kümne muutuja jaoks 11 hulka.
Vastus: 11
Erinevat tüüpi loogikavõrrandisüsteemide lahendamine
Näide 4.
Kui palju on loogiliste muutujate x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 erinevaid väärtuste komplekte, mis vastavad kõigile allpool loetletud tingimustele ?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
Vastuseks pole tarvis loetlege kõik muutujate x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 erinevad väärtuste komplektid, mille puhul see võrdsuste süsteem on täidetud.
Vastuseks peate märkima selliste komplektide arvu.
Lahendus:
Pange tähele, et süsteemi kolm võrrandit on erinevatel sõltumatutel muutujate kogumitel ühesugused.
Vaatame esimest võrrandit. Konjunktsioon on tõene (võrdne 1-ga) ainult siis, kui kõik selle operandid on tõesed (võrdsed 1-ga). Järeldus on 1 kõigis korteežides, välja arvatud (1,0). See tähendab, et esimese võrrandi lahenduseks on järgmised hulgad x1, x2, x3, x4, milles 1 ei asu 0-st (5 komplekti) vasakul:
Samamoodi on teise ja kolmanda võrrandi lahendused absoluutselt samad hulgad y1,…,y4 ja z1,…, z4.
Nüüd analüüsime süsteemi neljandat võrrandit: x 4 ∧ y 4 ∧ z 4 = 0. Lahenduseks on kõik hulgad x4, y4, z4, milles vähemalt üks muutujatest on võrdne 0-ga.
Need. x4 = 0 korral sobivad kõik võimalikud hulgad (y4, z4) ja x4 = 1 korral sobivad hulgad (y4, z4), milles on vähemalt üks null: (0, 0), (0,1 ), (1, 0).
|
Komplektide arv |
||||
Komplektide koguarv on 25 + 4*9 = 25 + 36 = 61.
Vastus: 61
Loogikavõrrandisüsteemide lahendamine korduvate valemite konstrueerimise teel
Korduvate valemite konstrueerimise meetodit kasutatakse keeruliste süsteemide lahendamisel, kus hulkade arvu suurendamise järjekord pole ilmne ja puu koostamine on mahtude tõttu võimatu.
Näide 5.
Mitu erinevat loogiliste muutujate x1, x2, ... x7, y1, y2, ... y7 väärtuste komplekti on olemas, mis vastavad kõigile allpool loetletud tingimustele?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
Vastuses ei ole vaja loetleda kõiki muutujate x1, x2, ..., x7, y1, y2, ..., y7 erinevaid väärtuste komplekte, mille puhul see võrdsuste süsteem on täidetud. Vastuseks peate märkima selliste komplektide arvu.
Lahendus:
Pange tähele, et süsteemi kuus esimest võrrandit on identsed ja erinevad ainult muutujate hulgast. Vaatame esimest võrrandit. Selle lahenduseks on järgmised muutujate komplektid:
Tähistame:
kordajate arv (0,0) muutujatel (x1,y1) kuni A 1,
kordajate arv (0,1) muutujatel (x1,y1) kuni B 1,
korduste arv (1,0) muutujatel (x1,y1) kuni C 1,
korduste arv (1,1) muutujatel (x1,y1) kuni D 1 .
kordajate arv (0,0) muutujatel (x2,y2) kuni A 2 ,
korduste arv (0,1) muutujatel (x2,y2) kuni B 2,
korduste arv (1,0) muutujatel (x2,y2) kuni C 2,
korduste arv (1,1) muutujatel (x2,y2) kuni D 2 .
Otsuste puust näeme seda
A 1 = 0, B 1 = 1, C 1 = 1, D 1 = 1.
Pange tähele, et muutujate (x2,y2) hulk (0,0) saadakse muutujate (x1,y1) hulkadest (0,1), (1,0) ja (1,1). Need. A 2 = B 1 + C 1 + D 1.
Hulk (0,1) muutujatel (x2,y2) saadakse muutujate (x1,y1) hulkadest (0,1), (1,0) ja (1,1). Need. B 2 = B 1 + C 1 + D 1.
Sarnaselt argumenteerides märgime, et C 2 =B 1 +C 1 +D 1. D2 = D1.
Seega saame korduvad valemid:
A i+1 = B i + C i + D i
B i+1 = B i + C i + D i
C i+1 = B i + C i + D i
D i+1 = A i +B i + C i + D i
Teeme laua
| Komplektid | Määramine. | Valem |
Komplektide arv |
||||||
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
| (0,0) | A i | A i+1 =B i +C i +D i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B i | B i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C i | C i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D i | D i+1 =D i | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Viimane võrrand (x7 ∨ y7) = 1 on täidetud kõigi hulgaga, välja arvatud need, milles x7=0 ja y7=0. Meie tabelis on selliste komplektide arv A 7.
Siis on komplektide koguarv B 7 + C 7 + D 7 = 127+127+1 = 255
Vastus: 255
Loogikavõrrandisüsteemide lahendamine tabelimeetodite abil loogiliste avaldiste teisendamise teel.See tehnika põhineb tõetabelite kasutamisel ja on mõeldud õpilastele, kes teavad, kuidas loogilisi avaldisi teisendada. Kui õpilased neid meetodeid ei valda, saab neid kasutada ilma teisendusteta. (Kasutame teisendusi). Selle lahendusmeetodi omandamiseks on hädavajalik teada põhiliste loogiliste operatsioonide omadusi: konjunkts, disjunkts, inversioon, implikatsioon ja ekvivalentsus.
Algoritm võrrandisüsteemide lahendamiseks selle meetodi abil:
Teisendage loogiline võrrand ja lihtsustage seda.
Määrake süsteemi võrrandite lahendamise järjekord, kuna enamikul juhtudel on võrrandite järjestikune lahendamine ülalt alla (nagu need süsteemis asuvad), kuid on võimalusi, kui on mugavam ja lihtsam alustada lahendamist alates alt üles.
Koostage muutujate tabel, kus saate määrata esimese (või viimase) muutuja algväärtused.
Kirjutage järjekindlalt üles järgmise muutuja kui võimalikud valikud kõik esimese tähendus.
Pärast eelmise võrrandi lahendamist, liikudes järgmise juurde, pöörake kindlasti tähelepanu sellele, milliseid muutujaid eelmises ja järgmistes võrrandites kasutatakse, kuna eelmiste võrrandite lahendamisel saadud muutujate väärtused antakse edasi valikuvõimalustena. järgmised võrrandid.
Järgmise muutuja juurde liikumisel pöörake tähelepanu saadud lahenduse kogustele, sest otsuste kasvu muster võib tuvastada.
Näide 1.
¬ X1 ˅ X2=1
¬ X2 ˅ X3=1
¬ X3 ˅ X4=1
¬ X9 ˅ X10=1
Alustame X1-ga ja vaatame, milliseid väärtusi see muutuja võib võtta: 0 ja 1.
Seejärel kaalume kõiki neid väärtusi ja vaatame, milline X2 võib olla.
Vastus: 11 lahendust
Näide 2.
( X1X2)˅(¬X1˄¬X2) ˅( X1↔ X3)=1
( X2˄X3)˅(¬X2˄¬X3) ˅( X2↔ X4)=1
(X8˄ X9)˅ (¬X8˄¬X9)˅(X8↔X10)=0
Teisendame valemiga (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B
Saame:
( X1↔ X2) ˅ (X1↔ X3) =1
( X2↔ X3) ˅ (X2↔ X4) =1
( X8↔ X9 (X8↔ X10) =0
Kui X1 =0 - 8 lahendust
Võtame X1=1 ja vaatame, millise väärtuse X2 võib võtta. Nüüd kaalume iga X2 puhul, milliseid väärtusi X3 võib võtta jne.
X1=1 puhul – 8 lahendust
Kokku 8+8=16 lahendust
Vastus. 16 lahendust
Näide 3 .
¬ ( X1↔ X2) ˄ ( X1X3) ˄ (¬X1˅¬X3 )=0
¬ ( X2↔ X3) ˄ (X2 ˅X4) ˄ (¬X2˅¬X4)=0
….
¬ ( X8↔ X9 (X8X10) ˄ (¬X8˅¬X10)=0
Pärast transformatsioone (A˅ B) ˄(¬ A ˅¬ B)= ¬( A ↔ B)
saame:
¬ ( X1↔ X2) ˄ ¬ (X1↔ X3)=0
¬ ( X2↔ X3) ˄ ¬ (X2↔ X4)=0
…..
¬ ( X8↔ X9) ˄ ¬ (X8↔ X10)=0
Võtame X1=0 ja vaatame, mis väärtuse X2 võib võtta. Nüüd kaalume iga X2 puhul, milliseid väärtusi X3 võib võtta jne.
Saime 10 lahendust X1=0 jaoks
Teeme sama X1=1 puhul. Samuti saame 10 lahendust
Kokku:10+10=20
Vastus: 20 lahendust.
Näide 4.
(X1 ˄ X2) ˅ (¬X1 ˄ ¬X2) ˅ (X2 ˄ X3) ˅ (¬X2 ˄¬ X3)=1
(X2 ˄ X3) ˅ (¬X2 ˄ ¬X3) ˅ (X3˄ X4) ˅ (¬X3 ˄¬ X4)=1
….
(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ 10) ˅ (¬Х9 ˄¬ 10) = 0
Teisendame valemite abil. (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B. Saame:
(X1↔ X2) ˅ (X2↔ X3)=1
(X2↔ X3) ˅ (X3↔ X4)=1
(X3↔ X4) ˅ (X4↔ X5)=1
(X4↔ X5) ˅ (X5↔ X6)=1
(X5↔ X6) ˅ (X6↔ X7)=1
(X6↔ X7) ˅ (X7↔ X8)=1
(X7↔ X8) ˅ (X8↔ X9)=1
(X8↔ X9) ˅ (X9↔ X10)=0
Alustame lõpust, sest viimases võrrandis on muutujad määratud üheselt.
Olgu X10=0, siis X9=1, X8=0, X7=0, X6=0 ja järgmised muutujad võivad võtta erinevaid väärtusi. Me kaalume iga.
Kokku 21 lahendust X10=0 jaoks
Nüüd kaaluge X10=1. Samuti saame 21 lahendust
Kokku:21+21=42
Vastus: 42 lahendust
Näide 5.
( X1X2) ˅ (¬X1 ˄ ¬X2) ˅ (¬X3 ˄X4 (X3 ˄ ¬X4)=1
( X3 ˄X4) ˅ (¬X3 ˄ ¬X4) ˅ (¬X5X6) ˅ (X5˄¬X6)=1
( X5X6) ˅ (¬X5˄¬X6) ˅ (¬X7˄X8 (X7˄¬X8)=1
( X7˄X8) ˅ (¬X7˄¬X8) ˅ (¬ X9X10 (X9˄¬X10) =1
Teisendame valemite järgi:(¬ A ˄ B) ˅ ( A ˄ ¬ B)= A↔ ¬ B
( A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B
( X1↔ X2) ˅ (X3 ↔ ¬X4)=1
( X3↔ X4 (X5 ↔ ¬X6)=1
( X5↔ X6) ˅ (X7 ↔ ¬X8)=1
( X7↔ X8 (X9 ↔ ¬X10)=1
Mõelgem, millised väärtused X1 ja X2 võivad võtta: (0,0), (0,1), (1,0), (1,1).
Vaatleme iga võimalust ja vaatame, millised väärtused X3, X4 võivad võtta.
Alates X7, X8 paneme kohe kirja lahenduste arvu, kuna kohe on selge, et kui väärtused on samad (1,1) ja (0,0), siis on järgmistel muutujatel 4 lahendust, ja kui need on erinevad (0,1) ja (1 ,0) – 2 lahendust.
Kokku: 80+80+32=192
Vastus: 192 lahendust
Näide 6.
(X1↔X2) ˅ (X2↔X3)=1
(X2↔X3) ˅ (X3↔X4)=1
(X3↔X4) ˅ (X4↔X5)=1
….
(X8↔X9) ˅ (X9↔X10)=1
Võtame X1=0 ja vaatame, mis väärtuse X2 võib võtta. Nüüd kaalume iga X2 puhul, milliseid väärtusi X3 võib võtta jne.
Näeme teatud mustrit: Järgmiste lahenduste arv on võrdne kahe eelmise summaga.
Sama X1=1 korral saame 89 lahendust
Kokku: 89+89=178 lahendust
Vastus: 178 lahendust
Lahendame selle veel ühel viisil
(X1↔X2) ˅ (X2↔X3)=1
(X2↔X3) ˅ (X3↔X4)=1
(X3↔X4) ˅ (X4↔X5)=1
….
(X8↔X9) ˅ (X9↔X10)=1
Tutvustame asendust:
T 1 =(X1↔X2)
T 2 =(X2↔X3)
T 3 =(X3↔X4)
T 4 =(X4↔X5)
T 5 =(X5↔X6)
T 6 =(X6↔X7)
T 7 =(X7↔X8)
T 8 =(X8↔X9)
T 9 =(X9↔X10)
Saame:
T1T2=1
T2 ˅T3=1
T3˅T4=1
T4T5=1
T5T6=1
T6˅T7=1
T7˅T8=1
T8T9=1
T9T10=1
VõtameT1=1 ja kasutage disjunktsiooni omadusi:
AGA pidagem seda meeles
T 1 =(X1↔X2)
T 2 =(X2↔X3) jne.
Kasutame samaväärsuse omadust ja veendume tabelit vaadates, et see
Kui T = 1, siis saadakse kaks lahendust. Ja kui =0, on üks lahendus.
Seetõttu saame üheliste arvu kokku lugeda ja korrutada 2+ nullide arvuga. Loendamine, ka mustri kasutamine.
Selgub, et üheliste arv = eelmine lahenduste koguarv T ja nullide arv on võrdne eelmise üheliste arvuga
Niisiis. Me saame selle kätte. Kuna üks annab kaks lahendit, siis 34 * 2 = 68 lahendust ühest + 21 lahendust nullist.
Kokku 89 lahendust T=1 jaoks. Sarnaselt saame 89 lahendust T=0 jaoks
Kokku 89+89=178
Vastus: 178 lahendust
Näide 7.
(X1 ↔ X2) ˅ (X3↔ X4) ˄ ¬(X1 ↔ X2) ˅ ¬(X3↔ X4)=1
(X3 ↔ X4 (X5↔ X6) ˄ ¬(X3 ↔ X4) ˅ ¬(X5↔ X6)=1
(X5 ↔ X6) ˅ (X7↔ X8) ˄ ¬(X5 ↔ X6) ˅ ¬(X7↔ X8)=1
(X7 ↔ X8 (X9↔ X10) ˄ ¬(X7 ↔ X8) ˅ ¬(X9↔ X10)=1
Tutvustame asendust:
T1=(X1 ↔ X2)
T2=(X3↔ X4)
T3=(X5↔ X6)
T4=(X7 ↔ X8)
T5=(X9↔ X10)
Saame:
(T1 ˅ T2) ˄ ¬(T1 ˅¬ T2)=1
(T2 ˅ T3) ˄ ¬(T2˅¬ T3)=1
(T3 ˅ T4) ˄ ¬(T3 ˅¬ T4)=1
(T4 ˅ T5) ˄ ¬(T4˅¬ T5)=1
Mõelgem, millised T-d võivad olla:
T1
T2
T3
T4
T5
Kokku
0
1
0
1
0
32
1
0
1
0
1
32
T K ≠T K+1 I T K =T K+2
Saame: 2 5 = 32 T jaoks
Kokku: 32+32=64
Vastus: 64 lahendust.
Valla eelarveline õppeasutus
"Keskkool nr 18"
Baškortostani Vabariigi Salavati linna linnaosa
Loogikavõrrandisüsteemid
aastal arvutiteaduse ühtse riigieksami probleemid
Ühtse riigieksami ülesannete osa “Loogikaalgebra alused” peetakse üheks kõige raskemini ja raskemini lahendatavaks. Selleteemaliste ülesannete keskmine protsent on kõige madalam ja on 43,2.
| Kursuse osa | Keskmine lõpetamise protsent töörühmade lõikes |
| Info kodeerimine ja selle koguse mõõtmine | |
| Teabe modelleerimine | |
| Numbrisüsteemid | |
| Loogika algebra alused | |
| Algoritmiseerimine ja programmeerimine | |
| Info- ja kommunikatsioonitehnoloogia alused |
2018. aasta KIM-i spetsifikatsiooni põhjal sisaldab see plokk nelja erineva raskusastmega ülesannet.
| № ülesandeid | Kontrollitav sisu elemendid | Ülesande raskusaste |
| Oskus koostada tõetabeleid ja loogikalülitusi | ||
| Võimalus otsida teavet Internetist | ||
| Põhimõistete ja seaduspärasuste tundmine matemaatiline loogika | ||
| Oskus konstrueerida ja teisendada loogilisi avaldisi |
Ülesanne 23 on kõrge raskusastmega, seetõttu on selle täitmise protsent madalaim. Ettevalmistatud lõpetajatest (81-100 punkti) täitsid 49,8% keskmise ettevalmistusega lõpetanutest (61-80 punkti) 13,7% õpilastest;
Loogikavõrrandisüsteemi lahendamise edukus sõltub loogikaseaduste tundmisest ja süsteemi lahendamise meetodite täpsest rakendamisest.
Vaatleme loogikavõrrandisüsteemi lahendamist kaardistamismeetodi abil.
(23.154 Poljakov K.Yu.) Mitu erinevat lahendit on võrrandisüsteemil?
((x1 y1 ) (x2 y2 )) (x1 x2 ) (y1 y2 ) =1
((x2 y2 ) (x3 y3 )) (x2 x3 ) (y2 y3 ) =1
((x7 y7 ) (x8 y8 )) (x7 x8 ) (y7 y8 ) =1
Kus x1 , x2 ,…, x8, juures1 ,y2 ,…,y8 - 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.
Lahendus. Kõik süsteemis sisalduvad võrrandid on sama tüüpi ja iga võrrand sisaldab nelja muutujat. Teades x1 ja y1, leiame kõik võimalikud x2 ja y2 väärtused, mis vastavad esimesele võrrandile. Sarnasel viisil arutledes leiame teadaolevate x2 ja y2 hulgast x3, y3, mis rahuldab teist võrrandit. See tähendab, et teades paari (x1, y1) ja määrates paari väärtuse (x2, y2), leiame paari (x3, y3), mis omakorda viib paarini (x4, y4) ja nii edasi.
Leiame kõik esimese võrrandi lahendid. Seda saab teha kahel viisil: koostada tõetabel, põhjendades ja rakendades loogikaseadusi.
Tõe tabel:
| x 1 y 1 | x 2 y 2 | (x 1 y 1) (x2 y2) | (x 1 x2) | (y 1 y2) | (x 1 x2) (y 1 y2) | |||||
Tõetabeli koostamine on töömahukas ja ajaliselt ebaefektiivne, seetõttu kasutame teist meetodit – loogilist arutlust. Korrutis on võrdne 1-ga siis ja ainult siis, kui iga tegur on võrdne 1-ga.
(x1 y1 ) (x2 y2 ))=1
(x1 x2 ) =1
(y1 y2 ) =1
Vaatame esimest võrrandit. Tagajärg on 1, kui 0 0, 0 1, 1 1, mis tähendab (x1 y1)=0 (01), (10), siis paar (x2 y2 ) võib olla mis tahes (00), (01), (10), (11) ja kui (x1 y1) = 1, st (00) ja (11) paar (x2 y2) = 1 võtab samad väärtused (00) ja (11). Jätame sellest lahendusest välja need paarid, mille teine ja kolmas võrrand on valed ehk x1=1, x2=0, y1=1, y2=0.
| (x1 , y1 ) | (x2 , y2 ) |
Paaride koguarv 1+1+1+22= 25
2) (23.160 Polyakov K.Yu.) Mitu erinevat lahendit on loogikavõrrandisüsteemil?
(x 1 (x 2 y 2 )) (y 1 y 2 ) = 1
(x 2 (x 3 y 3 )) (y 2 y 3 ) = 1
...
( x 6 ( x 7 y 7 )) ( y 6 y 7 ) = 1
x 7 y 7 = 1
Lahendus. 1) Võrrandid on sama tüüpi, nii et arutluskäiku kasutades leiame esimese võrrandi kõik võimalikud paarid (x1,y1), (x2,y2).
(x1 (x2 y2 ))=1
(y1 y2 ) = 1
Teise võrrandi lahenduseks on paarid (00), (01), (11).
Leiame esimesele võrrandile lahendused. Kui x1=0, siis x2, y2 - ükskõik, kui x1=1, siis x2, y2 saab väärtuse (11).
Teeme seosed paaride (x1, y1) ja (x2, y2) vahel.
| (x1 , y1 ) | (x2 , y2 ) |
Koostame iga etapi paaride arvu arvutamiseks tabeli.
| 0 |
|||||||
Võttes arvesse viimase võrrandi lahendeid x 7 y 7 = 1, jätame paari (10) välja. Leia lahenduste koguarv 1+7+0+34=42
3)(23.180) Mitu erinevat lahendit on loogikavõrrandisüsteemil?
(x1 x2 ) (x3 x4 ) = 1
(x3 x4 ) (x5 x6 ) = 1
(x5 x6 ) (x7 x8 ) = 1
(x7 x8 ) (x9 x10 ) = 1
x1 x3 x5 x7 x9 = 1
Lahendus. 1) Võrrandid on sama tüüpi, seega leiame arutluskäiku kasutades esimese võrrandi kõik võimalikud paarid (x1,x2), (x3,x4).
(x1 x2 ) (x3 x4 ) = 1
Jätame lahendusest välja paarid, mis jadas annavad 0 (1 0), need on paarid (01, 00, 11) ja (10).
Teeme ühendused paaride vahel (x1,x2), (x3,x4)
Tunni teema: Loogikavõrrandite lahendamine
Hariduslik – loogikavõrrandite lahendamise meetodite õppimine, loogikavõrrandite lahendamise oskuste arendamine ja loogilise avaldise konstrueerimine tõetabeli abil;Arendav – luua tingimused õpilaste kognitiivse huvi arendamiseks, edendada mälu, tähelepanu ja loogilise mõtlemise arengut;
Hariduslik : edendada 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 loogilise algebra põhiseadustega ja õppisime neid seadusi kasutama loogiliste avaldiste lihtsustamiseks.
Vaatame oma kodutööd loogiliste väljendite lihtsustamise kohta:
1. Milline järgmistest sõnadest vastab loogilisele tingimusele:
(esimese tähe konsonant → teise tähe konsonant)٨ (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 järgmist tähistust:
A – esitähe konsonant
B – teise tähe konsonant
S – viimase tähe vokaal
D – eelviimane täishäälik
Teeme väljendi:
Teeme tabeli:
2. Märkige, milline loogiline avaldis on avaldisega samaväärne
Lihtsustame algse avaldise ja pakutud valikute salvestamist:
3. Antud fragmendi avaldise F tõesuse tabelist:
Milline avaldis vastab F-le?
Määrame nende avaldiste väärtused argumentide määratud väärtuste jaoks:
Sissejuhatus tunni teemasse, uue materjali esitamine (30 minutit)
Jätkame loogika põhitõdede uurimist ja meie tänase tunni teemaks on "Loogikavõrrandite lahendamine". Pärast selle teemaga tutvumist õpid põhilisi loogikavõrrandite lahendamise viise, omandad oskused nende võrrandite lahendamiseks loogilise algebra keele abil ning oskuse koostada loogilist avaldist tõetabeli abil.
1. Lahendage loogikavõ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). Nii näiteks vastab rida 1101 sellele, et 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:
Võtame arvesse samu sidesõnu:
Selle tulemusena saame SDNF-i, mis sisaldab 9 sidesõna. Seetõttu on selle funktsiooni tõesuse tabelis väärtus 1 9 reas 2 4 =16 muutujaväärtuste komplekti.
3. Mitu lahendit on võrrandil (vastuses märkige ainult arv)?
Lihtsustame väljendit:
,
3 viis: SDNF ehitus
Võtame arvesse samu sidesõnu:
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 konstrueerimine tõetabeli abil:
Iga 1-st sisaldava tõetabeli rea jaoks koostame argumentide korrutise ja muutujad, mis on võrdsed 0-ga, kaasatakse eitusega korrutisesse ja muutujad, mis on võrdsed 1-ga, kaasatakse eituseta. Soovitud avaldis F koosneb saadud korrutiste 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)
Lahendage võrrand:
Mitu lahendit on võrrandil (vastuses märkige ainult arv)?
Koostage etteantud tõesuse tabeli abil loogiline avaldis ja
seda lihtsustada.