Metode reševanja sistemov logičnih enačb. Reševanje logičnih enačb

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

Naredimo 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

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 se izvaja 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. Sisteme logičnih enačb lahko rešimo na različne načine. 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.

1. rešitev: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 najdete tiste, za katere je izpolnjen dani sistem enačb. 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 razmišljanju 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.

Sisteme logičnih enačb lahko rešimo na različne načine. 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.

1. rešitev: 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 najdete tiste, za katere je izpolnjen dani sistem enačb. 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:

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, kjer so J, K, L, M, N logične spremenljivke?

rešitev.

Izraz (N ∨ ¬N) torej velja za vsak N

J ∧ ¬K ∧ L ∧ ¬M = 0.

Uporabimo negacijo na obeh straneh logične enačbe in uporabimo De Morganov zakon ¬ (A ∧ B) = ¬ A ∨ ¬ B. Dobimo ¬J ∨ K ∨ ¬L ∨ M = 1.

Logična vsota je enaka 1, če je vsaj ena od njenih sestavnih izjav enaka 1. Zato nastalo enačbo zadovolji katera koli kombinacija logičnih spremenljivk, razen v primeru, ko so vse količine, vključene v enačbo, enake 0. Vsaka od 4 spremenljivke so lahko enake 1 ali 0, zato so vse možne kombinacije 2·2·2·2 = 16. Zato ima enačba 16 −1 = 15 rešitev.

Omeniti velja še, da 15 najdenih rešitev ustreza kateri koli od dveh možnih vrednosti logične spremenljivke N, tako da ima izvirna enačba 30 rešitev.

Odgovor: 30

Koliko različnih rešitev ima enačba?

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

kjer so J, K, L, M, N logične spremenljivke?

Odgovoru ni treba navesti vseh različnih nizov vrednosti J, K, L, M in N, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.

rešitev.

Uporabimo formuli A → B = ¬A ∨ B in ¬(A ∨ B) = ¬A ∧ ¬B

Oglejmo si prvo podformulo:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Oglejmo si drugo podformulo

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Oglejmo si tretjo podformulo

1) M → J = 1 torej,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Združimo:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 torej 4 rešitve.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Združimo:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L torej 4 rešitve.

c) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Odgovor: 4 + 4 = 8.

Odgovor: 8

Koliko različnih rešitev ima enačba?

((K ∨ L) → (L ∧ M ∧ N)) = 0

kjer so K, L, M, N logične spremenljivke? V odgovoru ni treba navesti vseh različnih nizov vrednosti K, L, M in N, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.

rešitev.

Prepišimo enačbo z enostavnejšim zapisom za operacije:

((K + L) → (L M N)) = 0

1) iz tabele resnic operacije "implikacije" (glej prvi problem) sledi, da je ta enakost resnična, če in samo, če hkrati

K + L = 1 in L M N = 0

2) iz prve enačbe sledi, da je vsaj ena od spremenljivk, K ali L, enaka 1 (ali obe skupaj); torej razmislimo o treh primerih

3) če je K = 1 in L = 0, potem je druga enakost izpolnjena za poljubna M in N; ker obstajajo 4 kombinacije dveh logičnih spremenljivk (00, 01, 10 in 11), imamo 4 različne rešitve

4) če je K = 1 in L = 1, velja druga enakost za M · N = 0; obstajajo 3 takšne kombinacije (00, 01 in 10), imamo še 3 rešitve

5) če je K = 0, potem je L = 1 (iz prve enačbe); v tem primeru je druga enakost izpolnjena, ko je M · N = 0; obstajajo 3 takšne kombinacije (00, 01 in 10), imamo še 3 rešitve

6) skupaj dobimo 4 + 3 + 3 = 10 rešitev.

Odgovor: 10

Koliko različnih rešitev ima enačba?

(K ∧ L) ∨ (M ∧ N) = 1

rešitev.

Izraz velja v treh primerih, ko sta (K ∧ L) in (M ∧ N) enaka 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N so enaki 1, K in L pa sta kar koli razen hkrati 1. Zato obstajajo 3 rešitve.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 rešitev.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 rešitve.

Odgovor: 7.

Odgovor: 7

Koliko različnih rešitev ima enačba?

(X ∧ Y ∨ Z) ​​​​→ (Z ∨ P) = 0

kjer so X, Y, Z, P logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti, za katere velja ta enakost. Kot odgovor morate navesti samo število takih nizov.

rešitev.

(X ∧ Y ∨ Z) ​​​​→ (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ​​​​∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Logični ALI je napačen samo v enem primeru: ko sta oba izraza napačna.

torej

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Zato obstaja samo ena rešitev enačbe.

Odgovor: 1

Koliko različnih rešitev ima enačba?

(K ∨ L) ∧ (M ∨ N) = 1

kjer so K, L, M, N logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti K, L, M in N, za katere velja ta enakost. Kot odgovor morate navesti samo število takih nizov.

rešitev.

Logično In je resnično samo v enem primeru: ko so vsi izrazi resnični.

K ∨ L = 1, M ∨ N = 1.

Vsaka enačba daje 3 rešitve.

Razmislite o enačbi A ∧ B = 1, če tako A kot B sprejmeta prave vrednosti v treh primerih, potem ima enačba skupno 9 rešitev.

Zato je odgovor 9.

Odgovor: 9

Koliko različnih rešitev ima enačba?

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

kjer so A, B, C, D logične spremenljivke?

Odgovoru ni treba navesti vseh različnih nizov vrednosti A, B, C, D, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.

rešitev.

Logični "ALI" je resničen, ko je vsaj ena od trditev resnična.

(D ∧ ¬D)= 0 za katerikoli D.

torej

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, kar nam daje 3 možne rešitve za vsako D.

(D ∧ ¬ D)= 0 za kateri koli D, kar nam da dve rešitvi (za D = 1, D = 0).

Torej: skupne rešitve 2*3 = 6.

Skupaj 6 rešitev.

Odgovor: 6

Koliko različnih rešitev ima enačba?

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

kjer so K, L, M, N logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti K, L, M in N, za katere velja ta enakost. Kot odgovor morate navesti samo število takih nizov.

rešitev.

Uporabimo negacijo na obeh straneh enačbe:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Logični ALI velja v treh primerih.

Možnost 1.

K ∧ L ∧ M = 1, potem je K, L, M = 1 in ¬L ∧ M ∧ N = 0. N je poljubno, to je 2 rešitvi.

Možnost 2.

¬L ∧ M ∧ N = 1, potem N, M = 1; L = 0, K poljubno, to je 2 rešitvi.

Zato je odgovor 4.

Odgovor: 4

A, B in C so cela števila, za katera trditev velja

¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).

Čemu je enako B, če je A = 45 in C = 43?

rešitev.

Upoštevajte, da je ta zapletena izjava sestavljena iz treh preprostih

1) ¬(A = B); (A > B)→(B > C); (B > A)→(C > B);

2) ti preprosti stavki so povezani z operacijo ∧ (AND, konjunkcija), to pomeni, da jih je treba izvesti hkrati;

3) iz ¬(A = B)=1 takoj sledi A B;

4) predpostavimo, da je A > B, potem iz drugega pogoja dobimo 1→(B > C)=1; ta izraz je lahko resničen, če in samo če je B > C = 1;

5) torej imamo A > B > C, temu pogoju ustreza samo število 44;

6) za vsak slučaj preverimo še možnost A 0 →(B > C)=1;

ta izraz velja za vsak B; Zdaj pogledamo tretji pogoj in dobimo

ta izraz je lahko resničen, če in samo če je C > B, in tu imamo protislovje, ker ne obstaja takšno število B, za katerega bi bil C > B > A.

Odgovor: 44.

Odgovor: 44

Sestavite tabelo resnic za logično funkcijo

X = (A ↔ B) ∨ ¬(A → (B ∨ C))

v katerem je stolpec vrednosti argumenta A binarna predstavitev števila 27, stolpec vrednosti argumenta B je število 77, stolpec vrednosti argumenta C je število 120. Število v stolpcu je zapisano od zgoraj navzdol od najpomembnejšega do najmanj pomembnega (vključno z ničelnim nizom). Pretvorite dobljeno binarno predstavitev vrednosti funkcije X v decimalni številski sistem.

rešitev.

Zapišimo enačbo z enostavnejšim zapisom za operacije:

1) to je izraz s tremi spremenljivkami, zato bodo v resnični tabeli črte; zato mora binarna predstavitev števil, ki se uporabljajo za sestavo stolpcev tabele A, B in C, sestavljati 8 števk

2) pretvorite številke 27, 77 in 120 v binarni sistem, tako da takoj dodate do 8 števk ničel na začetku številk

3) malo verjetno je, da boste lahko takoj zapisali vrednosti funkcije X za vsako kombinacijo, zato je priročno dodati dodatne stolpce v tabelo za izračun vmesnih rezultatov (glejte spodnjo tabelo)

4) izpolnite stolpce tabele:

vrednost je 1 samo v tistih vrsticah, kjer je A = B

vrednost je 1 v tistih vrsticah, kjer je B ali C = 1

vrednost je 0 samo v tistih vrsticah, kjer je A = 1 in B + C = 0

vrednost je inverzna vrednosti prejšnjega stolpca (0 se nadomesti z 1, 1 pa z 0)

rezultat X (zadnji stolpec) je logična vsota dveh stolpcev in

5) da dobite odgovor, zapišite bite iz stolpca X od zgoraj navzdol:

6) pretvorite to število v decimalni sistem:

Odgovor: 171

Katero je največje celo število X, za katerega velja izjava (10 (X+1)·(X+2))?

rešitev.

Enačba je operacija implikacije med dvema razmerjema:

1) Seveda lahko tukaj uporabite isto metodo kot v primeru 2208, vendar boste morali rešiti kvadratne enačbe (ne želim ...);

2) Upoštevajte, da nas po pogoju zanimajo samo cela števila, zato lahko poskusimo nekako preoblikovati izvirni izraz, tako da dobimo enakovredno izjavo (sploh nas ne zanimajo natančne vrednosti korenin!);

3) Razmislite o neenakosti: očitno je lahko pozitivno ali negativno število;

4) Preprosto je preveriti, ali je v domeni izjava resnična za vsa cela števila , in v domeni - za vsa cela števila (da ne bi prišlo do zmede, je bolj priročno uporabiti nestroge neenakosti in , namesto in );

5) Zato ga je za cela števila mogoče nadomestiti z enakovrednim izrazom

6) domena resnice izraza je zveza dveh neskončnih intervalov;

7) Zdaj razmislite o drugi neenakosti: očitno je, da je lahko tudi pozitivno ali negativno število;

8) V regiji izjava velja za vsa cela števila, v regiji pa za vsa cela števila, zato jo je za cela števila mogoče nadomestiti z enakovrednim izrazom

9) področje resnice izraza je zaprt interval;

10) Podani izraz velja povsod, razen na področjih, kjer in ;

11) Upoštevajte, da vrednost ni več primerna, ker tam in , kar pomeni, da implikacija daje 0;

12) Pri zamenjavi 2, (10 (2+1) · (2+2)) ali 0 → 0, ki izpolnjuje pogoj.

Torej je odgovor 2.

Odgovor: 2

Katero je največje celo število X, za katerega velja trditev

(50 (X+1)·(X+1))?

rešitev.

Uporabimo implikacijsko transformacijo in transformirajmo izraz:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Logični ALI je resničen, ko je resnična vsaj ena logična izjava. Po rešitvi obeh neenačb in ob upoštevanju tega vidimo, da je največje celo število, za katerega je izpolnjena vsaj ena od njiju, 7 (na sliki je pozitivna rešitev druge neenačbe prikazana rumeno, prve pa modro).

Odgovor: 7

Navedite vrednosti spremenljivk K, L, M, N, pri katerih je logični izraz

(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

lažno. Odgovor zapišite kot niz 4 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.

Podvaja nalogo 3584.

Odgovor: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

rešitev.

Uporabimo implikacijsko transformacijo:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Uporabimo negacijo na obeh straneh enačbe:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Preobrazimo:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Zato je M = 0, N = 0, zdaj upoštevajte (¬K ∧ L ∨ M ∧ L):

iz dejstva, da je M = 0, N = 0, sledi, da je M ∧ L = 0, potem je ¬K ∧ L = 1, torej K = 0, L = 1.

Odgovor: 0100

Določite vrednosti spremenljivk K, L, M, N, pri katerih je logični izraz

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

lažno. 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.

Zapišimo enačbo s preprostejšim zapisom operacij (pogoj »izraz je napačen« pomeni, da je enak logični ničli):

1) iz formulacije pogoja sledi, da mora biti izraz napačen samo za en niz spremenljivk

2) iz tabele resnic operacije "implikacije" sledi, da je ta izraz napačen, če in samo, če hkrati

3) prva enakost (logični produkt je enak 1) je izpolnjena, če in samo če in ; iz tega sledi (logična vsota je enaka nič), kar se lahko zgodi samo takrat, ko ; Tako smo že definirali tri spremenljivke

4) iz drugega pogoja, , za in dobimo .

Podvaja nalogo

Odgovor: 1000

Določite vrednosti logičnih spremenljivk P, Q, S, T, pri katerih je logični izraz

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) je napačna.

Odgovor zapišite kot niz štirih znakov: vrednosti spremenljivk P, Q, S, T (v tem vrstnem redu).

rešitev.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Uporabimo implikacijsko transformacijo:

¬Q ∨ S ∨ T = 0 => S = 0, T = 0.

Odgovor: 0100

Določite vrednosti spremenljivk K, L, M, N, pri katerih je logični izraz

(K → M) ∨ (L ∧ K) ∨ ¬N

lažno. 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.

Logični ALI je napačen, če in samo če sta oba stavka napačna.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Uporabimo implikacijsko transformacijo za prvi izraz:

¬K ∨ M = 0 => K = 1, M = 0.

Razmislite o drugem izrazu:

(L ∧ K) ∨ ¬N = 0 (glej rezultat prvega izraza) => L ∨ ¬N = 0 => L = 0, N = 1.

Odgovor: 1001.

Odgovor: 1001

Določite vrednosti spremenljivk K, L, M, N, pri katerih je logični izraz

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

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

Logični "IN" je resničen, če in samo če sta obe izjavi resnični.

1) (K → M) = 1 Uporabite implikacijsko transformacijo: ¬K ∨ M = 1

2) (K → ¬M) = 1 Uporabite implikacijsko transformacijo: ¬K ∨ ¬M = 1

Iz tega sledi, da je K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Uporabimo implikacijsko transformacijo: K ∨ (M ∧ ¬L ∧ N) = 1 iz dejstva, da dobimo K = 0.

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 od 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 razmišljanjem zgradimo drevo odloč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.