Kuidas lahendada loogikavalemeid. Loogikavõrrandisüsteemid informaatika eksami ülesannetes

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: sidesõnad, 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.

Loogikavõrrandisüsteemide lahendamine muutujate muutmise teel

Muutujate muutmise 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 järgmistele 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 alusel see võrdsussü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 saab süsteemi kirjutada ühe võrrandina:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunktsioon on 1 (tõene), kui iga operandi väärtus on 1. See tähendab, 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 tohi ühik 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 saavutatakse kolmel hulgal x1, x2: (0,0) , ( 0,1), (1,1). Samamoodi y2, y3, y4 jaoks.

Kuna muutuja y1 iga hulk (x1,x2) kombineeritakse muutuja y2 iga komplektiga (x3,x4) ja nii edasi, korrutatakse muutujate x hulkade arv:

Liidame komplektide arvu: 1 + 3 + 9 + 27 + 81 = 121.

Vastus: 121

Näide 2

Mitu erinevat tõeväärtuste muutujate x1, x2, ... x9, y1, y2, ... y9 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele 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 korral 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. Selle võrrandi lahendused on kaks komplekti:

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 definitsiooni abil.

Seda meetodit kasutatakse juhul, kui võrrandisüsteem on piisavalt lihtne ja hulkade arvu suurendamise järjekord muutujate lisamisel ilmne.

Näide 3

Kui palju erinevaid lahendeid on võrrandisüsteemil

¬x9 ∨ x10 = 1,

kus x1, x2, ... x10 on tõeväärtuslikud muutujad?

Vastuses ei ole vaja loetleda kõiki erinevaid väärtuste komplekte x1, x2, ... x10, mille jaoks antud võrduste süsteem kehtib. 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 x2 väärtust (0 ja 1) ja x1=1 puhul on ainult üks x2 väärtus (1), siis hulk (x1,x2) on võrrandi lahendus. Ainult 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 x3 (1) väärtus, nii et komplekt ( x2,x3) on võrrandi lahend. Kokku on 4 komplekti.

On hästi näha, et teise muutuja lisamisel lisandub üks komplekt. Need. rekursiivne valem (i+1) muutujate hulkade arvu jaoks:

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

Mitu erinevat tõeväärtuste muutujate x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele 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 loetle kõik erinevad muutujate x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 väärtuste komplektid, mille korral antud võrdussü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 samad.

Mõelge esimesele võrrandile. 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 komplektides, välja arvatud (1,0). See tähendab, et esimese võrrandi lahenduseks on sellised hulgad x1, x2, x3, x4, milles 1 ei asu 0-st (5 komplekti) vasakul:

Samamoodi on teise ja kolmanda võrrandi lahendused täpselt samad y1,…,y4 ja z1,…,z4 komplektid.

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), mis sisaldavad vähemalt ühte nulli: (0, 0), (0,1) , ( 1, 0).

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 lahendamiseks, mille puhul komplektide arvu suurendamise järjekord pole ilmne ja puu ehitamine on mahtude tõttu võimatu.

Näide 5

Mitu erinevat tõeväärtuste muutujate x1, x2, ... x7, y1, y2, ... y7 väärtuste komplekti on olemas, mis vastavad kõigile järgmistele 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 alusel antud võrdsuste süsteem kehtib. Vastuseks peate märkima selliste komplektide arvu.

Lahendus:

Pange tähele, et süsteemi kuus esimest võrrandit on samad ja erinevad ainult muutujate hulgast. Mõelge esimesele võrrandile. Selle lahenduseks on järgmised muutujate komplektid:

Tähistage:

komplektide arv (0,0) muutujatel (x1,y1) kuni A 1 ,

komplektide arv (0,1) muutujatel (x1,y1) kuni B 1 ,

komplektide arv (1,0) muutujatel (x1,y1) C 1 kaudu,

komplektide arv (1,1) muutujatel (x1,y1) D 1 kaudu.

komplektide arv (0,0) muutujatel (x2,y2) kuni A 2 ,

komplektide arv (0,1) muutujatel (x2,y2) B ​​2 kaudu,

komplektide arv (1,0) muutujatel (x2,y2) C 2 kaudu,

komplektide arv (1,1) muutujatel (x2,y2) D 2 kaudu.

Otsuste puust näeme seda

A 1 = 0, B 1 = 1, C 1 = 1, D 1 = 1.

Pange tähele, et muutujate (x2,y2) korteež (0,0) saadakse muutujate (x1,y1) kordadest (0,1), (1,0) ja (1,1). Need. A 2 \u003d 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 \u003d B 1 + C 1 + D 1.

Sarnaselt arutledes märgime, et C 2 \u003d B 1 + C 1 + D 1. D2 = D1.

Seega saame rekursiivsed 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

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

Valla eelarveline õppeasutus

"Keskkool nr 18"

Baškortostani Vabariigi Salavati linna linnaosa

Loogikavõrrandisüsteemid

informaatika eksami ülesannetes

Eksami ülesannete jaotist "Loogikaalgebra alused" peetakse üheks kõige raskemaks ja halvasti lahendatuks. Selle teema ülesannete täitmise keskmine protsent on madalaim ja on 43,2.

KIM 2018 spetsifikatsiooni põhjal sisaldab see plokk nelja erineva keerukusastmega ülesannet.

Ülesanne 23 on kõrge raskusastmega, seetõttu on selle täitmise protsent madalaim. Koolitatud lõpetajatest (81-100 punkti) täitis selle 49,8%, keskmise ettevalmistusega (61-80 punkti) tuleb toime 13,7%, ülejäänud õpilaste rühm seda ülesannet ei täida.

Loogikavõrrandisüsteemi lahendamise edukus sõltub loogikaseaduste tundmisest ja süsteemi lahendamise meetodite täpsest rakendamisest.

Vaatleme loogikavõrrandisüsteemi lahendamist kaardistamismeetodiga.

(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 - Boole'i ​​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 igas võrrandis on neli muutujat. Teades x1 ja y1, leiame kõik võimalikud x2 ja y2 väärtused, mis vastavad esimesele võrrandile. Sarnaselt argumenteerides 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 peal.

Leiame kõik esimese võrrandi lahendid. Seda saab teha kahel viisil: koostada tõetabel, arutledes ja rakendades loogikaseadusi.

Tõe tabel:

Tõetabeli koostamine on töömahukas ja ajaliselt ebaefektiivne, seetõttu kasutame teist meetodit – loogilist arutlust. Korrutis on 1 siis ja ainult siis, kui iga tegur on 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Mõelge esimesele võrrandile. Järgnev on võrdne 1-ga, kui 0 0, 0 1, 1 1, siis (x1 y1)=0 punktides (01), (10), siis paar (x2  y2 ) võib olla mis tahes (00), (01), (10), (11) ja kui (x1 y1)=1, st (00) ja (11) on paaril (x2 y2)=1 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.

Paaride koguarv 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Kui palju erinevaid lahendeid 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, seega arutlusmeetodi abil 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.

Teeme tabeli, et arvutada paaride arv igal etapil.

Võttes arvesse viimase võrrandi lahendeid x 7  y 7 = 1, elimineerime paari (10). Leia lahenduste koguarv 1+7+0+34=42

3)(23.180) Kui palju erinevaid lahendeid 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 arutlusmeetodi abil leiame esimese võrrandi kõik võimalikud paarid (x1,x2), (x3,x4).

(x1  x2 )  (x3  x4 ) = 1

Lahendusest jätame järgnevalt välja paarid, mis annavad 0 (1 0), need on paarid (01, 00, 11) ja (10).

Koostage paaride (x1,x2), (x3,x4) vahelised lingid

Juhend. Klaviatuurilt sisestamisel kasutage järgmisi tavasid:

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 muutujate arv 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 loogikavaldises 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)

• 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.

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

Tehe JA – loogiline korrutamine (konjunktsioon)

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

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

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

Loogikatete ülimuslikkus

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

Täiuslik disjunktiivne normaalvorm

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.

Täiuslik konjunktiivne normaalvorm

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.

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 uutest muutujatest 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:

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 konkreetsetel näidetel.

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:

Pöörake tähelepanu viimasele veerule, see ühtib toimingu tulemusega 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 on võrdne 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.