Metode reševanja sistemov logičnih enačb. Logike. Logične funkcije. Reševanje enačb

26.09.2019

Metode reševanja sistemov logične enačbe

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. Predvsem je to sposobnost odločanja logične težave. Naloge B15 na enotnem državnem izpitu so naloge povečane kompleksnosti, saj vsebujejo sisteme logičnih enačb. Lahko izberete različne načine 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.

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








0	0	1	1	0	1

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

Pri 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 nov sistem. 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 enačba spremenljivke bo zapisan v obliki: 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 možne skupne rešitve podana enačba 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.

Predpostavimo, 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.

Spremenljivke	Drevo	Število rešitev
x 1
x 2
x 3

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:

x 1	x 2	(x 1 → x 2)

Ustvarimo tabelo resnic za dve enačbi:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

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, v katerih je dodana ena enota, začenši z zadnji položaj do zapolnitve vseh možnih mest. Lahko se domneva, da splošna rešitev bo imel enako obliko, a da bi ta pristop postal rešitev, je potreben dokaz, da je predpostavka resnična.

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

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

Pojasnilo.

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

Pojasnilo.

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.

Pojasnilo.

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

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

1) iz tabele resnic operacije "implikacija" (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

Pojasnilo.

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.

Pojasnilo.

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

Pojasnilo.

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

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

Vsaka od enačb daje 3 rešitve.

Upoštevajte enačbo A ∧ B = 1, če jo sprejmeta tako A kot B prave vrednote 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.

Pojasnilo.

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.

Pojasnilo.

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?

Pojasnilo.

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 pa poglej tretji pogoj, ki ga 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 nastalo binarno predstavitev vrednosti funkcije X v decimalni številski sistem.

Pojasnilo.

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 biti binarna predstavitev števil, ki se uporabljajo za sestavo stolpcev A, B in C tabele, sestavljena iz 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)

A	IN	Z
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

4) izpolnite stolpce tabele:

A	IN	Z					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

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))?

Pojasnilo.

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(Nočem ...);

2) Upoštevajte, da nas po pogoju zanimajo samo cela števila, zato lahko poskusimo nekako preoblikovati izvirni izraz in tako pridobimo enakovreden stavek ( natančne vrednosti korenine nas sploh ne zanimajo!);

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 domeni je trditev resnična za vsa cela števila, v domeni 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))?

Pojasnilo.

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.

Pojasnilo.

Podvaja nalogo 3584.

Odgovor: 1000

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

Pojasnilo.

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.

Pojasnilo.

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 "implikacija" 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).

Pojasnilo.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ T)) = 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.

Pojasnilo.

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

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

Pojasnilo.

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 je K = 0, dobimo:

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Odgovor: 0011

Znano je, da za cela števila X, Y in Z velja naslednja izjava:

(Z Čemu je enak Z, če je X=25 in Y=48?

Pojasnilo.

Po zamenjavi števil dobimo, da je Z = 47.

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

1) (Z 2) ti preprosti stavki so povezani z operacijo ∧ (AND, konjunkcija), kar pomeni, da jih je treba izvesti hkrati.

3) od ¬(Z+1 24 in od ¬(Z+1 47.

4) od (Z Z Odgovor: 47.

Odgovor: 47

A, B in C so cela števila, za katera velja naslednja izjava:

(C Kakšna je vrednost C, če je A=45 in B=18?

Pojasnilo.

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

Zamenjajmo števila v izraz:

1) (C (C 2) ¬(C+1, C ≥ 44.

3) ¬(C+1, C ≥ 17.

Iz 2) in 1) sledi, da je C

Odgovor: 44

¬(A = B) ∧ ((B A)) ∧ ((A 2C))

Kakšna je vrednost A, če je C = 8 in B = 18?

Pojasnilo.

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

1) ¬(A = B) = 1, to je A ≠ 18 = 1.

2) ((B A)) Uporabite implikacijsko transformacijo: (18 > A) ∨ (16 > A) = 1

3) (A 2C) Uporabite implikacijsko transformacijo: (A > 18) ∨ (A > 16) = 1

Iz 2) in 3) sledi (18 > A) in (A > 16), saj sicer pride do protislovja: A = 17.

Odgovor: 17

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

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

Kakšna je vrednost B, če je A = 45 in C = 18?

Pojasnilo.

Logični "IN" je resničen samo, če so vse izjave resnične.

Naj bo logična funkcija n spremenljivk. Logična enačba izgleda takole:

Konstanta C ima vrednost 1 ali 0.

Logična enačba ima lahko od 0 do različnih rešitev. Če je C enak 1, potem so rešitve vse tiste množice spremenljivk iz tabele resnic, za katere ima funkcija F vrednost true (1). Preostali nizi so rešitve enačbe s C enakim nič. Vedno lahko upoštevate le enačbe oblike:

Res, naj bo dana enačba:

V tem primeru lahko preidemo na ekvivalentno enačbo:

Razmislite o sistemu k logičnih enačb:

Rešitev sistema je niz spremenljivk, na katerem so izpolnjene vse enačbe sistema. V smislu logičnih funkcij je treba za rešitev sistema logičnih enačb najti množico, na kateri je logična funkcija F resnična, ki predstavlja konjunkcijo prvotnih funkcij:

Če je število spremenljivk majhno, na primer manjše od 5, potem ni težko sestaviti tabele resnic za funkcijo, ki nam omogoča, da povemo, koliko rešitev ima sistem in katere so množice, ki zagotavljajo rešitve.

V nekaterih Težave z enotnim državnim izpitom da bi našli rešitve sistema logičnih enačb, število spremenljivk doseže 10. Potem postane izdelava tabele resnic skoraj nemogoča naloga. Reševanje problema zahteva drugačen pristop. Za poljuben sistem enačb ni splošna metoda, drugačen od surove sile, ki omogoča reševanje tovrstnih težav.

Pri nalogah, predlaganih na izpitu, rešitev običajno temelji na upoštevanju posebnosti sistema enačb. Ponavljam, razen preizkusa vseh možnosti za nabor spremenljivk ni splošnega načina za rešitev problema. Rešitev mora biti zgrajena na podlagi specifike sistema. Pogosto je koristno izvesti predhodno poenostavitev sistema enačb z uporabo znanih logičnih zakonov. Še ena uporaben trik Rešitev tega problema je naslednja. Ne zanimajo nas vse množice, temveč samo tiste, na katerih ima funkcija vrednost 1. Namesto konstruiranja polna miza Resnici na ljubo bomo zgradili njegov analog - binarno drevo odločitev. Vsaka veja tega drevesa ustreza eni rešitvi in določa množico, na kateri ima funkcija vrednost 1. Število vej v odločitvenem drevesu sovpada s številom rešitev sistema enačb.

Razložil bom, kaj je binarno odločitveno drevo in kako je zgrajeno na primerih več problemov.

Problem 18

Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 obstaja, ki zadovoljujejo sistem dveh enačb?

Odgovor: Sistem ima 36 različnih rešitev.

Rešitev: Sistem enačb vključuje dve enačbi. Poiščimo število rešitev za prvo enačbo, odvisno od 5 spremenljivk - . Prvo enačbo lahko obravnavamo kot sistem 5 enačb. Kot je bilo prikazano, sistem enačb pravzaprav predstavlja konjunkcijo logičnih funkcij. Velja tudi obratna trditev - konjunkcijo pogojev lahko obravnavamo kot sistem enačb.

Zgradimo drevo odločanja za implikacijo () - prvi člen konjunkcije, ki ga lahko obravnavamo kot prvo enačbo. Tako je videti grafični prikaz tega drevesa

Drevo je sestavljeno iz dveh ravni glede na število spremenljivk v enačbi. Prva raven opisuje prvo spremenljivko. Dve veji te ravni odražata možni vrednosti te spremenljivke - 1 in 0. Na drugi ravni veje drevesa odražajo samo tiste možne vrednosti spremenljivke, za katere enačba oceni kot resnično. Ker enačba podaja implikacijo, veja, ki ima vrednost 1, zahteva, da je na tej veji vrednost 1. Veja, ki ima vrednost 0, generira dve veji z vrednostma, enakima 0 in 1. Konstruirana drevo podaja tri rešitve, od katerih ima implikacija vrednost 1. Na vsaki veji je izpisan ustrezen nabor vrednosti spremenljivk, ki dajejo rešitev enačbe.

Ti nizi so: ((1, 1), (0, 1), (0, 0))

Nadaljujmo z gradnjo odločitvenega drevesa z dodajanjem naslednje enačbe, naslednje posledice. Posebnost našega sistema enačb je v tem, da vsaka nova enačba sistema uporablja eno spremenljivko iz prejšnje enačbe in doda eno novo spremenljivko. Ker ima spremenljivka že vrednosti v drevesu, potem bo na vseh vejah, kjer ima spremenljivka vrednost 1, tudi spremenljivka imela vrednost 1. Za takšne veje se konstrukcija drevesa nadaljuje na naslednjo raven, vendar se ne pojavijo nove veje. Posamezna veja, kjer ima spremenljivka vrednost 0, se bo razvejala v dve veji, kjer bo spremenljivka prejela vrednosti 0 in 1. Tako vsak dodatek nove enačbe glede na njeno specifičnost doda eno rešitev. Izvirna prva enačba:

ima 6 rešitev. Takole izgleda polno drevo rešitve za to enačbo:

Druga enačba našega sistema je podobna prvi:

Edina razlika je v tem, da enačba uporablja spremenljivke Y. Ta enačba ima tudi 6 rešitev. Ker je vsako variabilno rešitev mogoče kombinirati z vsako variabilno raztopino, torej skupno število Obstaja 36 rešitev.

Upoštevajte, da izdelano odločitveno drevo ne poda le števila rešitev (po številu vej), ampak tudi same rešitve, zapisane na vsaki veji drevesa.

Problem 19

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?

Ta naloga je modifikacija prejšnje naloge. Razlika je v tem, da je dodana enačba, ki povezuje spremenljivki X in Y.

Iz enačbe sledi, da ko ima vrednost 1 (ena taka rešitev obstaja), potem ima vrednost 1. Tako obstaja ena množica, na kateri ima in ima vrednosti 1. Ko je enaka 0, je lahko imajo poljubno vrednost, tako 0 kot 1. Zato vsaka množica z , ki je enaka 0, in obstaja 5 takih množic, ustreza vsem 6 množicam s spremenljivkami Y. Zato je skupno število rešitev 31.

Problem 20

Rešitev: Ob upoštevanju osnovnih enakovrednosti zapišemo svojo enačbo kot:

Ciklična veriga implikacij pomeni, da sta spremenljivki enaki, zato je naša enačba enakovredna enačbi:

Ta enačba ima dve rešitvi, če so vse 1 ali 0.

Problem 21

Koliko rešitev ima enačba:

Rešitev: Tako kot v problemu 20 se premaknemo od cikličnih implikacij k identitetam in prepišemo enačbo v obliki:

Zgradimo drevo odločitev za to enačbo:

Problem 22

Koliko rešitev ima naslednji sistem 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 in dekompozicija.

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

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.

Rešitev 2: Ustvarimo tabelo resnic za sistem:








0	0	1	1	0	1

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.

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

Predpostavimo, 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.

	Drevo	Število rešitev
x 1
x 2
x 3
		…

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:

x 1	x 2	(x 1 → x 2)

Ustvarimo tabelo resnic za dve enačbi:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

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 spremenljivke A, B, C, D, E, tj. nove spremenljivke so neodvisne ena 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:

		X1 ≡ X2

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:

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

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

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.

A	IN	Z					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

A	IN	Z					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

A	IN	Z					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1