Metode in metode reševanja logičnih enačb. Reševanje logičnih enačb v matematiki

Obstaja več načinov za reševanje sistemov logičnih enačb. To je redukcija na eno enačbo, izdelava tabele resnic in dekompozicija.

Naloga: Rešite sistem logičnih enačb:

Razmislimo metoda redukcije na eno enačbo . Ta metoda vključuje preoblikovanje logičnih enačb tako, da so njihove desne strani enake vrednosti resnice (to je 1). Če želite to narediti, uporabite operacijo logičnega zanikanja. Nato, če enačbe vsebujejo zapletene logične operacije, jih nadomestimo z osnovnimi: "IN", "ALI", "NE". Naslednji korak je združitev enačb v eno, enakovredno sistemu, z uporabo logične operacije "IN". Po tem bi morali preoblikovati nastalo enačbo na podlagi zakonov logične algebre in pridobiti specifično rešitev sistema.

Rešitev 1: Uporabite inverzijo na obeh straneh prve enačbe:

Predstavljajmo si implikacijo skozi osnovni operaciji "ALI" in "NE":

Ker so leve strani enačb enake 1, jih lahko združimo z operacijo »IN« v eno enačbo, ki je enakovredna izvirnemu sistemu:

Prvi oklepaj odpremo po De Morganovem zakonu in preoblikujemo dobljeni rezultat:

Nastala enačba ima eno rešitev: A =0, B=0 in C=1.

Naslednja metoda je sestavljanje tabel resnic . Ker imajo logične količine samo dve vrednosti, lahko preprosto pregledate vse možnosti in med njimi poiščete tiste, za katere je dani sistem enačb izpolnjen. To pomeni, da zgradimo eno skupno tabelo resnic za vse enačbe sistema in poiščemo črto z zahtevanimi vrednostmi.

Rešitev 2: Ustvarimo tabelo resnic za sistem:

Vrstica, za katero so izpolnjeni pogoji naloge, je označena s krepkim tiskom. Torej A=0, B=0 in C=1.

Pot razgradnja . Ideja je popraviti vrednost ene od spremenljivk (nastaviti jo na 0 ali 1) in s tem poenostaviti enačbe. Nato lahko popravite vrednost druge spremenljivke in tako naprej.

Rešitev 3: Naj bo A = 0, potem:

Iz prve enačbe dobimo B = 0, iz druge pa C = 1. Rešitev sistema: A = 0, B = 0 in C = 1.

Na Enotnem državnem izpitu iz računalništva je zelo pogosto treba določiti število rešitev sistema logičnih enačb, ne da bi našli same rešitve; za to obstajajo tudi določene metode. Glavni način za iskanje števila rešitev sistema logičnih enačb jezamenjava spremenljivk. Najprej morate vsako od enačb čim bolj poenostaviti na podlagi zakonov logične algebre, nato pa kompleksne dele enačb nadomestiti z novimi spremenljivkami in določiti število rešitev novega sistema. Nato se vrnite k zamenjavi in ​​določite število rešitev zanjo.

Naloga: Koliko rešitev ima enačba (A →B) + (C →D) = 1? Kjer so A, B, C, D logične spremenljivke.

rešitev: Vstavimo nove spremenljivke: X = A →B in Y = C →D. Ob upoštevanju novih spremenljivk bo enačba zapisana kot: X + Y = 1.

Disjunkcija je resnična v treh primerih: (0;1), (1;0) in (1;1), medtem ko sta X in Y implikaciji, to pomeni, da je resnična v treh primerih in napačna v enem. Zato bo primer (0;1) ustrezal trem možnim kombinacijam parametrov. Primer (1;1) – bo ustrezal devetim možnim kombinacijam parametrov izvirne enačbe. To pomeni, da so skupne možne rešitve te enačbe 3+9=15.

Naslednji način za določitev števila rešitev sistema logičnih enačb je binarno drevo. Oglejmo si to metodo na primeru.

Naloga: Koliko različnih rešitev ima sistem logičnih enačb:

Podani sistem enačb je enakovreden enačbi:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.

Pretvarjajmo se, da x 1 – je res, potem iz prve enačbe dobimo to x 2 tudi res, od drugega - x 3 =1 in tako naprej, dokler x m= 1. To pomeni, da je niz (1; 1; …; 1) m enot rešitev sistema. Naj zdaj x 1 =0, potem iz prve enačbe imamo x 2 =0 oz x 2 =1.

Kdaj x 2 res, dobimo, da so tudi preostale spremenljivke resnične, to pomeni, da je množica (0; 1; ...; 1) rešitev sistema. pri x 2 =0 to razumemo x 3 =0 oz x 3 = in tako naprej. Če nadaljujemo z zadnjo spremenljivko, ugotovimo, da so rešitve enačbe naslednji nizi spremenljivk (m +1 rešitev, vsaka rešitev vsebuje m vrednosti spremenljivk):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Ta pristop je dobro ponazorjen z izgradnjo binarnega drevesa. Število možnih rešitev je število različnih vej sestavljenega drevesa. Lahko vidimo, da je enako m +1.

V primeru težav pri sklepanju raziskave in gradbeništvorešitev, s katerimi lahko iščete rešitev uporabo tabele resnic, za eno ali dve enačbi.

Prepišimo sistem enačb v obliki:

Ustvarimo tabelo resnic ločeno za eno enačbo:

Ustvarimo tabelo resnic za dve enačbi:

Občinska proračunska izobraževalna ustanova

"Srednja šola št. 18"

mestno okrožje mesta Salavat v Republiki Baškortostan

Sistemi logičnih enačb

pri problemih enotnega državnega izpita iz računalništva

Oddelek "Osnove algebre logike" v nalogah enotnega državnega izpita velja za enega najtežjih in težko rešljivih. Povprečni odstotek opravljenih nalog na to temo je najnižji in znaša 43,2.

Na podlagi specifikacije KIM 2018 ta blok vključuje štiri naloge različnih težavnostnih stopenj.

Naloga 23 ima visoko težavnostno stopnjo, zato ima najnižji odstotek dokončanja. Med pripravljenimi maturanti (81-100 točk) jih je opravilo 49,8 % srednje pripravljenih maturantov (61-80 točk) 13,7 % študentov, ki te naloge niso opravili.

Uspešnost reševanja sistema logičnih enačb je odvisna od poznavanja zakonitosti logike in od natančne uporabe metod za reševanje sistema.

Razmislimo o reševanju sistema logičnih enačb z metodo preslikave.

(23.154 Polyakov K.Yu.) Koliko različnih rešitev ima sistem enačb?

((x1  l1 )  (x2  l2 ))  (x1  x2 )  (l1  l2 ) =1

((x2  l2 )  (x3  l3 ))  (x2  x3 )  (l2  l3 ) =1

((x7  l7 )  (x8  l8 ))  (x7  x8 )  (l7  l8 ) =1

Kje x1 , x2 ,…, x8, pri1 ,y2 ,…,y8 - logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.

rešitev. Vse enačbe, vključene v sistem, so istega tipa in vsaka enačba vključuje štiri spremenljivke. Če poznamo x1 in y1, lahko najdemo vse možne vrednosti x2 in y2, ki ustrezajo prvi enačbi. Če sklepamo na podoben način, lahko iz znanih x2 in y2 najdemo x3, y3, ki ustreza drugi enačbi. To pomeni, da poznamo par (x1, y1) in določimo vrednost para (x2, y2), bomo našli par (x3, y3), kar bo posledično vodilo do para (x4, y4) in tako naprej.

Poiščimo vse rešitve prve enačbe. To je mogoče storiti na dva načina: zgraditi tabelo resnic z razmišljanjem in uporabo zakonov logike.

Tabela resnice:

Izdelava tabele resnic je delovno intenzivna in časovno neučinkovita, zato uporabljamo drugo metodo - logično sklepanje. Produkt je enak 1, če in samo če je vsak faktor enak 1.

(x1  l1 )  (x2  l2 ))=1

(x1  x2 ) =1

(l1  l2 ) =1

Poglejmo prvo enačbo. Posledica je enaka 1, ko je 0 0, 0 1, 1 1, kar pomeni (x1 y1)=0 za (01), (10), potem je par (x2  l2 ) je lahko kateri koli (00), (01), (10), (11) in ko je (x1 y1) = 1, to je (00) in (11), par (x2 y2) = 1 prevzame enake vrednosti (00) in (11). Iz te rešitve izločimo tiste pare, pri katerih sta druga in tretja enačba napačni, to je x1=1, x2=0, y1=1, y2=0.

Skupno število parov 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Koliko različnih rešitev ima sistem logičnih enačb?

(x 1  (x 2  l 2 ))  (l 1  l 2 ) = 1

(x 2  (x 3  l 3 ))  (l 2  l 3 ) = 1

...

( x 6  ( x 7  l 7 ))  ( l 6  l 7 ) = 1

x 7  l 7 = 1

rešitev. 1) Enačbe so istega tipa, zato bomo s sklepanjem našli vse možne pare (x1,y1), (x2,y2) prve enačbe.

(x1  (x2  l2 ))=1

(l1  l2 ) = 1

Rešitev druge enačbe so pari (00), (01), (11).

Poiščimo rešitve prve enačbe. Če x1=0, potem x2, y2 - poljubno, če x1=1, potem x2, y2 prevzame vrednost (11).

Povežimo para (x1, y1) in (x2, y2).

Ustvarimo tabelo za izračun števila parov na vsaki stopnji.

Ob upoštevanju rešitev zadnje enačbe x 7  l 7 = 1, izločimo par (10). Poiščite skupno število rešitev 1+7+0+34=42

3)(23.180) Koliko različnih rešitev ima sistem logičnih enačb?

(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

rešitev. 1) Enačbe so istega tipa, zato bomo s sklepanjem našli vse možne pare (x1,x2), (x3,x4) prve enačbe.

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

Iz rešitve izločimo pare, ki v zaporedju dajejo 0 (1 0), to so pari (01, 00, 11) in (10).

Povežimo pare (x1,x2), (x3,x4)

Tema lekcije: Reševanje logičnih enačb

Razvojni - ustvariti pogoje za razvoj kognitivnega interesa učencev, spodbujati razvoj spomina, pozornosti in logičnega mišljenja;

Poučna : spodbujati sposobnost poslušanja mnenj drugih, negovanje volje in vztrajnosti za doseganje končnih rezultatov.

Vrsta lekcije: kombinirani pouk

Oprema: računalnik, multimedijski projektor, predstavitev 6.

Med poukom

Ponavljanje in obnavljanje osnovnega znanja. Preverjanje domače naloge (10 minut)

V prejšnjih urah smo se seznanili z osnovnimi zakoni logične algebre in se naučili uporabljati te zakone za poenostavljanje logičnih izrazov.

Preverimo domačo nalogo o poenostavljanju logičnih izrazov:

1. Katera od naslednjih besed izpolnjuje logični pogoj:

(soglasnik prve črke→ soglasnik druge črke)٨ (samoglasnik zadnje črke → samoglasnik predzadnje črke)? Če je takih besed več, navedite najmanjšo izmed njih.

1) ANNA 2) MARIJA 3) OLEG 4) STEPAN

Vstavimo naslednji zapis:

A – soglasnik prve črke

B – soglasnik druge črke

S – zadnji samoglasnik

D – predzadnji samoglasnik

Ustvarimo izraz:

Naredimo tabelo:

2. Označite, kateri logični izraz je enakovreden izrazu

Poenostavimo snemanje izvirnega izraza in predlaganih možnosti:

3. Podan je fragment resničnostne tabele izraza F:

Določimo vrednosti teh izrazov za podane vrednosti argumentov:

Uvod v temo lekcije, predstavitev novega gradiva (30 minut)

Še naprej preučujemo osnove logike in tema naše današnje lekcije je "Reševanje logičnih enačb." Po študiju te teme se boste naučili osnovnih načinov reševanja logičnih enačb, pridobili spretnosti za reševanje teh enačb z uporabo jezika logične algebre in sposobnost sestavljanja logičnega izraza z uporabo tabele resnic.

1. Rešite logično enačbo

(¬K M) → (¬L M N) =0

Odgovor zapišite kot niz štirih znakov: vrednosti spremenljivk K, L, M in N (v tem vrstnem redu). Tako na primer vrstica 1101 ustreza dejstvu, da je K=1, L=1, M=0, N=1.

rešitev:

Preoblikujemo izraz(¬K  M) → (¬L  M  N)

Izraz je napačen, če sta oba izraza napačna. Drugi člen je enak 0, če je M =0, N =0, L =1. V prvem členu je K = 0, ker je M = 0 in
.

Odgovor: 0100

2. Koliko rešitev ima enačba (pri odgovoru navedite le število)?

Rešitev: transformirajte izraz

(A +B )*(C +D )=1

A + B = 1 in C + D = 1

2. način: sestavljanje tabele resnic

Preoblikujemo prvotni izraz, odpremo oklepaje, da dobimo disjunkcijo veznikov:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Dopolnimo veznike do popolnih veznikov (zmnožek vseh argumentov), ​​odpremo oklepaje:

Upoštevajmo enake veznike:

Kot rezultat dobimo SDNF, ki vsebuje 9 konjunkcij. Zato ima tabela resnic za to funkcijo vrednost 1 v 9 vrsticah 2 4 =16 nizov vrednosti spremenljivk.

3. Koliko rešitev ima enačba (pri odgovoru navedite le število)?

Poenostavimo izraz:

,

3 način: izgradnja SDNF

Upoštevajmo enake veznike:

Kot rezultat dobimo SDNF, ki vsebuje 5 konjunkcij. Zato ima tabela resnic za to funkcijo vrednost 1 na 5 vrstic 2 4 =16 nizov vrednosti spremenljivk.

Sestavljanje logičnega izraza z uporabo tabele resnic:

za vsako vrstico tabele resnic, ki vsebuje 1, sestavimo produkt argumentov, pri čemer so spremenljivke enake 0 vključene v produkt z negacijo, spremenljivke enake 1 pa brez negacije. Želeni izraz F bo sestavljen iz vsote dobljenih produktov. Potem, če je mogoče, je treba ta izraz poenostaviti.

Primer: podana je resničnostna tabela izraza. Sestavite logični izraz.

3. Domača naloga (5 minut)

Reši enačbo:

Koliko rešitev ima enačba (pri odgovoru navedite le število)?

S pomočjo podane tabele resnic sestavite logični izraz in

poenostavite.

Metode reševanja sistemov logičnih enačb

Sistem logičnih enačb lahko rešite na primer z uporabo tabele resnic (če število spremenljivk ni preveliko) ali z uporabo odločitvenega drevesa, tako da najprej poenostavite vsako enačbo.

1. Metoda zamenjave spremenljivke.

Uvedba novih spremenljivk vam omogoča poenostavitev sistema enačb in zmanjšanje števila neznank.Nove spremenljivke morajo biti neodvisne druga od druge. Po rešitvi poenostavljenega sistema se moramo vrniti k prvotnim spremenljivkam.

Oglejmo si uporabo te metode na posebnem primeru.

Primer.

((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

rešitev:

Uvedimo nove spremenljivke: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Pozor! Vsaka od spremenljivk x1, x2, ..., x10 mora biti vključena le v eno izmed novih spremenljivk A, B, C, D, E, tj. nove spremenljivke so neodvisne druga od druge).

Potem bo sistem enačb videti takole:

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

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

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

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

Zgradimo drevo odločitev za nastali sistem:

Upoštevajte enačbo A=0, tj. (X1≡ X2)=0. Ima 2 korena:

Iz iste tabele je razvidno, da ima tudi enačba A=1 2 korena. Uredimo število korenin na odločitvenem drevesu:

Če želite najti število rešitev ene veje, morate pomnožiti število rešitev na vsaki ravni. Leva veja ima 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 rešitev; tudi desna veja ima 32 rešitev. Tisti. celoten sistem ima 32+32=64 rešitev.

Odgovor: 64.

2. Metoda sklepanja.

Težavnost reševanja sistemov logičnih enačb je v okornosti celotnega odločitvenega drevesa. Metoda sklepanja vam omogoča, da ne zgradite celotnega drevesa, ampak razumete, koliko vej bo imelo. Oglejmo si to metodo na konkretnih primerih.

Primer 1. Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?

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

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, za katere je ta sistem enakosti izpolnjen. Kot odgovor morate navesti število takih nizov.

rešitev:

Prva in druga enačba vsebujeta neodvisne spremenljivke, ki so povezane s tretjim pogojem. Zgradimo drevo rešitev za prvo in drugo enačbo.

Za predstavitev drevesa rešitev za sistem prve in druge enačbe je treba vsako vejo prvega drevesa nadaljevati z drevesom za spremenljivke pri . Tako zgrajeno drevo bo vsebovalo 36 vej. Nekatere od teh vej ne zadoščajo tretji enačbi sistema. Na prvem drevesu označimo število vej drevesa"y" , ki zadoščajo tretji enačbi:

Naj pojasnimo: za izpolnitev tretjega pogoja, ko je x1=0, mora obstajati y1=1, tj. vse veje drevesa."X" , kjer je x1=0 mogoče nadaljevati samo z eno vejo iz drevesa"y" . In samo za eno vejo drevesa"X" (desno) se prilegajo vse veje drevesa"y". Tako celotno drevo celotnega sistema vsebuje 11 vej. Vsaka veja predstavlja eno rešitev izvirnega sistema enačb. To pomeni, da ima celoten sistem 11 rešitev.

Odgovor: 11.

Primer 2. Koliko različnih rešitev ima sistem enačb?

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

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

………………

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

(X1 ≡ X10) = 0

kjer so x1, x2, …, x10 logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.

rešitev: Poenostavimo sistem. Sestavimo tabelo resnic za del prve enačbe:

Bodite pozorni na zadnji stolpec, ujema se z rezultatom akcije X1 ≡ X10.

Po poenostavitvi dobimo:

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

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

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

……

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

(X1 ≡ X10) = 0

Razmislite o zadnji enačbi:(X1 ≡ X10) = 0, tj. x1 ne sme sovpadati z x10. Da je prva enačba enaka 1, mora biti enakost resnična(X1 ≡ X2)=1, tj. x1 se mora ujemati z x2.

Zgradimo drevo rešitev za prvo enačbo:

Razmislite o drugi enačbi: za x10=1 in za x2=0 oklepajmora biti enako 1 (tj. x2 sovpada z x3); za x10=0 in za x2=1 oklepaj(X2 ≡ X10)=0, kar pomeni oklepaj (X2 ≡ X3) mora biti enako 1 (tj. x2 sovpada z x3):

S tem načinom razmišljanja zgradimo drevo rešitev za vse enačbe:

Tako ima sistem enačb le 2 rešitvi.

Odgovor: 2.

Primer 3.

Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?

(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

rešitev:

Zgradimo drevo rešitev za 1. enačbo:

Razmislite o drugi enačbi:

• Ko je x1=0 : drugi in tretji oklepaj bosta enaka 0; da je prvi oklepaj enak 1, y1=1, z1=1 (tj. v tem primeru - 1 rešitev)
• Ko je x1=1 : prvi oklepaj bo enak 0; drugo oz tretji oklepaj mora biti enak 1; drugi oklepaj bo enak 1, ko je y1=0 in z1=1; tretji oklepaj bo enak 1, ko je y1=1 in z1=0 (tj. v tem primeru - 2 rešitvi).

Podobno velja za preostale enačbe. Zabeležimo nastalo število rešitev za vsako vozlišče drevesa:

Če želite izvedeti število rešitev za vsako vejo, pomnožite dobljena števila posebej za vsako vejo (od leve proti desni).

1 veja: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 rešitev

Veja 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 rešitvi

3. veja: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 rešitve

4. veja: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 rešitev

5. veja: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 rešitev

Seštejmo dobljena števila: skupaj je 31 rešitev.

Odgovor: 31.

3. Naravni prirast števila korenin

V nekaterih sistemih je število korenov naslednje enačbe odvisno od števila korenov prejšnje enačbe.

Primer 1. Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?

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

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

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

Poenostavimo prva enačba:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Nato bo sistem dobil obliko:

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

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

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

itd.

Vsaka naslednja enačba ima 2 korena več kot prejšnja.

4 enačba ima 12 korenin;

Enačba 5 ima 14 korenin

Enačba 8 ima 20 korenin.

Odgovor: 20 korenin.

Včasih število korenin raste po Fibonaccijevem zakonu.

Reševanje sistema logičnih enačb zahteva kreativen pristop.

Metode reševanja sistemov logičnih enačb

Kirgizova E.V., Nemkova A.E.

Lesosibirsk pedagoški inštitut –

podružnica Sibirske zvezne univerze, Rusija

Sposobnost doslednega razmišljanja, prepričljivega sklepanja, postavljanja hipotez in zavračanja negativnih zaključkov ne pride sama od sebe; to veščino razvija znanost logike. Logika je veda, ki preučuje metode za ugotavljanje resničnosti ali napačnosti nekaterih trditev na podlagi resničnosti ali napačnosti drugih trditev.

Obvladovanje osnov te znanosti je nemogoče brez reševanja logičnih problemov. Preverjanje razvoja spretnosti za uporabo znanja v novi situaciji poteka s prehodom. Zlasti je to sposobnost reševanja logičnih problemov. Naloge B15 na Enotnem državnem izpitu so naloge povečane kompleksnosti, saj vsebujejo sisteme logičnih enačb. Obstaja več načinov za reševanje sistemov logičnih enačb. To je redukcija na eno enačbo, izdelava tabele resnic, dekompozicija, zaporedna rešitev enačb itd.

Naloga:Rešite sistem logičnih enačb:

Razmislimo metoda redukcije na eno enačbo . Ta metoda vključuje preoblikovanje logičnih enačb tako, da so njihove desne strani enake vrednosti resnice (to je 1). Če želite to narediti, uporabite operacijo logičnega zanikanja. Nato, če enačbe vsebujejo zapletene logične operacije, jih nadomestimo z osnovnimi: "IN", "ALI", "NE". Naslednji korak je združitev enačb v eno, enakovredno sistemu, z uporabo logične operacije "IN". Po tem bi morali preoblikovati nastalo enačbo na podlagi zakonov logične algebre in pridobiti specifično rešitev sistema.

Rešitev 1:Uporabite inverzijo na obeh straneh prve enačbe:

Predstavljajmo si implikacijo skozi osnovni operaciji "ALI" in "NE":

Ker so leve strani enačb enake 1, jih lahko združimo z operacijo »IN« v eno enačbo, ki je enakovredna izvirnemu sistemu:

Prvi oklepaj odpremo po De Morganovem zakonu in preoblikujemo dobljeni rezultat:

Nastala enačba ima eno rešitev: A= 0, B =0 in C =1.

Naslednja metoda je sestavljanje tabel resnic . Ker imajo logične količine samo dve vrednosti, lahko preprosto pregledate vse možnosti in med njimi poiščete tiste, za katere je dani sistem enačb izpolnjen. To pomeni, da zgradimo eno skupno tabelo resnic za vse enačbe sistema in poiščemo črto z zahtevanimi vrednostmi.

Rešitev 2:Ustvarimo tabelo resnic za sistem:

Vrstica, za katero so izpolnjeni pogoji naloge, je označena s krepkim tiskom. Torej A =0, B =0 in C =1.

Pot razgradnja . Ideja je popraviti vrednost ene od spremenljivk (nastaviti jo na 0 ali 1) in s tem poenostaviti enačbe. Nato lahko popravite vrednost druge spremenljivke in tako naprej.

Rešitev 3: Pustiti A = 0, potem:

Iz prve enačbe dobimo B =0, od drugega pa C=1. Rešitev sistema: A = 0, B = 0 in C = 1.

Uporabite lahko tudi metodo zaporedno reševanje enačb , pri čemer na vsakem koraku doda eno spremenljivko v obravnavani niz. Za to je potrebno transformirati enačbe tako, da so spremenljivke vnesene po abecednem vrstnem redu. Nato zgradimo drevo odločitev in mu zaporedno dodajamo spremenljivke.

Prva enačba sistema je odvisna samo od A in B, druga enačba pa od A in C. Spremenljivka A ima lahko 2 vrednosti 0 in 1:

Iz prve enačbe sledi, da , torej kdaj A = 0 in dobimo B = 0, za A = 1 pa imamo B = 1. Torej ima prva enačba dve rešitvi glede na spremenljivki A in B.

Pokažimo drugo enačbo, iz katere določimo vrednosti C za vsako možnost. Ko je A =1, implikacija ne more biti napačna, to pomeni, da druga veja drevesa nima rešitve. pri A= 0 dobimo edino rešitev C= 1 :

Tako smo dobili rešitev sistema: A = 0, B = 0 in C = 1.

Na Enotnem državnem izpitu iz računalništva je zelo pogosto treba določiti število rešitev sistema logičnih enačb, ne da bi našli same rešitve; za to obstajajo tudi določene metode. Glavni način za iskanje števila rešitev sistema logičnih enačb je zamenjava spremenljivk. Najprej morate vsako od enačb čim bolj poenostaviti na podlagi zakonov logične algebre, nato pa kompleksne dele enačb nadomestiti z novimi spremenljivkami in določiti število rešitev novega sistema. Nato se vrnite k zamenjavi in ​​določite število rešitev zanjo.

Naloga:Koliko rešitev ima enačba ( A → B ) + (C → D ) = 1? Kjer so A, B, C, D logične spremenljivke.

rešitev:Uvedimo nove spremenljivke: X = A → B in Y = C → D . Ob upoštevanju novih spremenljivk bo enačba zapisana kot: X + Y = 1.

Disjunkcija velja v treh primerih: (0;1), (1;0) in (1;1), medtem ko X in Y je implikacija, kar pomeni, da je resnična v treh primerih in napačna v enem. Zato bo primer (0;1) ustrezal trem možnim kombinacijam parametrov. Primer (1;1) – bo ustrezal devetim možnim kombinacijam parametrov izvirne enačbe. To pomeni, da so skupne možne rešitve te enačbe 3+9=15.

Naslednji način za določitev števila rešitev sistema logičnih enačb je binarno drevo. Oglejmo si to metodo na primeru.

Naloga:Koliko različnih rešitev ima sistem logičnih enačb:

Podani sistem enačb je enakovreden enačbi:

( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.

Pretvarjajmo se, dax 1 – je res, potem iz prve enačbe dobimo tox 2 tudi res, od drugega -x 3 =1 in tako naprej, dokler x m= 1. Torej je množica (1; 1; …; 1) od m enot je rešitev sistema. Naj zdajx 1 =0, potem iz prve enačbe imamox 2 =0 oz x 2 =1.

Kdaj x 2 res, dobimo, da so tudi preostale spremenljivke resnične, to pomeni, da je množica (0; 1; ...; 1) rešitev sistema. prix 2 =0 to razumemo x 3 =0 oz x 3 = in tako naprej. Če nadaljujemo z zadnjo spremenljivko, ugotovimo, da so rešitve enačbe naslednji nizi spremenljivk ( m +1 rešitev, v vsaki raztopini m spremenljive vrednosti):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Ta pristop je dobro ponazorjen z izgradnjo binarnega drevesa. Število možnih rešitev je število različnih vej sestavljenega drevesa. Preprosto je videti, da je enak m +1.

V primeru težav pri sklepanju in gradnji odločitvenega drevesa lahko poiščete rešitev z uporabo tabele resnic, za eno ali dve enačbi.

Prepišimo sistem enačb v obliki:

Ustvarimo tabelo resnic ločeno za eno enačbo:

Ustvarimo tabelo resnic za dve enačbi:

Nato lahko vidite, da je ena enačba resnična v naslednjih treh primerih: (0; 0), (0; 1), (1; 1). Sistem dveh enačb je resničen v štirih primerih (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). V tem primeru je takoj jasno, da obstaja rešitev, sestavljena samo iz ničel in več m rešitve, pri katerih se dodaja ena enota naenkrat, začenši z zadnjega mesta, dokler niso zapolnjena vsa možna mesta. Lahko se domneva, da bo splošna rešitev imela enako obliko, a da bi tak pristop postal rešitev, je potreben dokaz, da je predpostavka pravilna.

Če povzamem vse zgoraj navedeno, bi vas rad opozoril na dejstvo, da vse obravnavane metode niso univerzalne. Pri reševanju vsakega sistema logičnih enačb je treba upoštevati njegove značilnosti, na podlagi katerih je treba izbrati način reševanja.

Literatura:

1. Logični problemi / O.B. Bogomolov – 2. izd. – M.: BINOM. Laboratorij znanja, 2006. – 271 str.: ilustr.

2. Polyakov K.Yu. Sistemi logičnih enačb / Poučno-metodični časopis za učitelje računalništva: Informatika št. 14, 2011.