Grafično reševanje sistemov logičnih enačb. Načini reševanja sistemov logičnih enačb

V tem gradivu je predstavljena predstavitev metod za reševanje logičnih enačb in sistemov logičnih enačb v nalogi B15 (št. 23, 2015) izpita iz informatike. Znano je, da je ta naloga ena najtežjih med USE nalogami. Predstavitev je lahko uporabna pri izvajanju pouka na temo "Logika" v specializiranih razredih, pa tudi pri pripravi na izpit.

Prenesi:

Predogled:

Če želite uporabiti predogled predstavitev, si ustvarite Google račun (račun) in se prijavite v njega: https://accounts.google.com

Drsni napisi:

Rešitev naloge B15 (sistemi logičnih enačb) MP Višnevskaja, MAOU "Gimnazija št. 3" 18. november 2013, Saratov

Naloga B15 je ena najtežjih na izpitu iz računalništva !!! Spretnosti so preizkušene: transformacijski izrazi, ki vsebujejo logične spremenljivke; v naravnem jeziku opišite niz vrednosti logičnih spremenljivk, za katere je dani niz logičnih spremenljivk resničen; prešteti število binarnih nizov, ki ustrezajo določenim pogojem. Najtežja stvar, ker Uradnih pravil o tem, kako to storiti, ni.

Brez česar ne moreš!

Legenda veznika: A / \\ B, A  B, AB, A & B, A in B ločitev: A \\ / B, A + B, A | Negacija B, A ali B:  A, A, ne ekvivalent: A  B, A  B, A  B izključno "ali": A  B, A xor B

Metoda spreminjanja spremenljivk Koliko različnih sklopov vrednosti logičnih spremenljivk x1, x2, ..., x9, x10 obstaja, ki izpolnjujejo vse naslednje pogoje: ((x1 ≡ x2) \\ / (x3 ≡ x4)) / \\ (¬ (x1 ≡ x2) \\ / ¬ (x3 ≡ x4)) \u003d 1 ((x3 ≡ x4) \\ / (x5 ≡ x6)) / \\ (¬ (x3 ≡ x4) \\ / ¬ (x5 ≡ x6)) \u003d 1 ((x5 ≡ x6) ) \\ / (x7 ≡ x8)) / \\ (¬ (x5 ≡ x7) \\ / ¬ (x7 ≡ x8)) \u003d 1 ((x7 ≡ x8) \\ / (x9 ≡ x10)) / \\ (¬ (x7 ≡ x8) \\ / ¬ (x9 ≡ x10)) \u003d 1 V odgovoru ni treba naštevati vseh različnih nizov x1, x2, ..., x9, x10, pod katerimi je dani sistem enakosti zadovoljen. Kot odgovor morate navesti število takšnih nizov (demo različica 2012)

Korak rešitve 1. Poenostavite s spreminjanjem spremenljivk t1 \u003d x1  x2 t2 \u003d x3  x4 t3 \u003d x5  x6 t4 \u003d x7  x8 t5 \u003d x9  x10 Po poenostavitvi: (t1 \\ / t2) / \\ (¬t1 \\ / ¬ t2) \u003d 1 (t2 \\ / t3) / \\ (¬t2 \\ / ¬ t3) \u003d 1 (t3 \\ / t4) / \\ (¬t3 \\ / ¬ t4) \u003d 1 (t4 \\ / t5) / \\ ( ¬t4 \\ / ¬ t5) \u003d 1 Razmislite o eni od enačb: (t1 \\ / t2) / \\ (¬t1 \\ / ¬ t2) \u003d 1 Očitno je, da je 1 le, če je ena od spremenljivk 0, druga pa 1. Uporabljamo formulo za izražanje operacije XOR v smislu veznika in disjunkcije: (t1 \\ / t2) / \\ (¬t1 \\ / ¬ t2) \u003d t1  t2 \u003d ¬ (t1 ≡ t2) \u003d 1 ¬ (t1 ≡ t2) \u003d 1 ¬ ( t2 ≡ t3) \u003d 1 ¬ (t3 ≡ t4) \u003d 1 ¬ (t4 ≡ t5) \u003d 1

2. korak. Sistemska analiza ¬ (t1 ≡ t2) \u003d 1 ¬ (t2 ≡ t3) \u003d 1 ¬ (t3 ≡ t4) \u003d 1 ¬ (t4 ≡ t5) \u003d 1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 0 T .to. tk \u003d x2k-1 ≡ x2k (t1 \u003d x1  x2,….), potem vsaka vrednost tk ustreza dvema paroma vrednosti x2k-1 in x2k, na primer: tk \u003d 0 ustreza dvema paroma - (0,1) in (1, 0) in tk \u003d 1 sta par (0,0) in (1,1).

Step3. Štetje števila rešitev. Vsak t ima 2 rešitvi, število t - 5. Tako. za spremenljivke t obstajata 2 5 \u003d 32 rešitev. Toda vsak t ustreza paru rešitev x, tj. originalni sistem ima 2 * 32 \u003d 64 rešitev. Odgovor: 64

Način odprave dela rešitev Koliko različnih sklopov vrednosti logičnih spremenljivk x1, x2,…, x5, y1, y2,…, y5 obstaja, ki izpolnjujejo vse naslednje pogoje: (x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4 ) ∧ (x4 → x5) \u003d 1; (y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) \u003d 1; y5 → x5 \u003d 1. V odgovoru ni treba naštevati vseh različnih nizov x1, x2,…, x5, y 1, y2,…, y5, za katere velja dani sistem enakosti. Kot odgovor morate navesti število takšnih nizov.

Odločba. Korak 1. Sekvenčna rešitev enačb h1 1 0 x2 1 0 1 h3 1 0 1 1 h4 1 0 1 1 1 x5 1 0 1 1 1 1 Prva enačba je veznik več operacij implikacij, enakih 1, tj. vsaka od posledic je resnična. Posledica je napačna samo v enem primeru, ko je 1  0, v vseh drugih primerih (0  0, 0  1, 1  1) pa se operacija vrne 1. Zapišemo to v obliki tabele:

Korak 1. Sekvenčna rešitev T.o. Za x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111) smo dobili 6 sklopov raztopin. Če se podobno trdimo, pridemo do zaključka, da za y1, y2, y3, y4, y5 obstaja enak nabor rešitev. Ker te enačbe so neodvisne, tj. nimajo skupnih spremenljivk, potem bo rešitev tega sistema enačb (brez upoštevanja tretje enačbe) 6 * 6 \u003d 36 parov "x" in "igrykov". Razmislite o tretji enačbi: y5 → x5 \u003d 1 Rešitev je parov: 0 0 0 1 1 1 Ni rešitev za par: 1 0

Primerjajmo dobljene raztopine, kjer y5 \u003d 1, x5 \u003d 0 ne ustreza. takih parov 5. Število rešitev sistema: 36-5 \u003d 31. Odgovor: 31 Kombinatorika je bila potrebna !!!

Metoda dinamičnega programiranja Koliko različnih rešitev ima logična enačba x 1 → x 2 → x 3 → x 4 → x 5 → x 6 \u003d 1, pri čemer so x 1, x 2,…, x 6 logične spremenljivke? V odgovoru ni treba naštevati vseh različnih nizov spremenljivih vrednosti, za katere velja ta enakost. Kot odgovor morate navesti količine takšnih sklopov.

Korak rešitve 1. Analiza stanja Na levi strani enačbe so implicirane operacije zaporedno, prednost je enaka. Prepišite: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 \u003d 1 NB! Vsaka naslednja spremenljivka ni odvisna od prejšnje, temveč od rezultata prejšnje implikacije!

2. korak. Razkrivanje vzorca Razmislite o prvi implikaciji, X 1 → X 2. Tabela resnice: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Iz ene 0 smo dobili 2 enoti, od 1 pa eno 0 in ena 1. Samo ena 0 in tri 1, to je rezultat prve operacije.

2. korak. Razkrivanje vzorca Po priključitvi x 3 na rezultat prve operacije dobimo: F (x 1, x 2) x 3 F (x 1, x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Od dveh 0 - dva 1, od vsakega 1 (od tega 3), po en 0 in 1 (3 + 3)

Korak 3. Izpeljava formule. lahko napišete formule za izračun števila ničel N i in števila enot E i za enačbo s spremenljivkami i,

Korak 4. Izpolnjevanje tabele Izpolnimo tabelo za i \u003d 6 od leve proti desni, izračunamo število ničel in enak po zgornjih formulah; tabela prikazuje, kako je sestavljen naslednji stolpec glede na prejšnji :: število spremenljivk 1 2 3 4 5 6 Število ničel N i 1 1 3 5 11 21 Število enot E i 1 2 * 1 + 1 \u003d 3 2 * 1 + 3 \u003d 5 11 21 43 Odgovor: 43

Metoda z uporabo poenostavitev logičnih izrazov Koliko različnih rešitev ima enačba ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) \u003d 1 kjer so J, K, L, M, N logične spremenljivke? V odgovoru ni treba naštevati vseh različnih nizov vrednosti J, K, L, M in N, za katere velja ta enakost. Kot odgovor morate navesti število takšnih nizov.

Rešitev Upoštevajte, da je J → K \u003d ¬ J  K Uvedite spremembo spremenljivk: J → K \u003d A, M  N  L \u003d B Prepišite enačbo ob upoštevanju spremembe: (A → B)  (B → A)  (M → J) \u003d 1 4. (A  B)  (M → J) \u003d 1 5. Očitno je A  B za enaki vrednosti A in B 6. Upoštevaj zadnjo implikacijo M → J \u003d 1 To je mogoče, če: M \u003d J \u003d 0 M \u003d 0, J \u003d 1 M \u003d J \u003d 1

Rešitev Ker A  B, potem za M \u003d J \u003d 0 dobimo 1 + K \u003d 0. Ni rešitev. Za M \u003d 0, J \u003d 1, dobimo 0 + K \u003d 0, K \u003d 0, N in L pa sta kateri koli, 4 rešitve: ¬ J  K \u003d M  N  LKNL 0 0 0 0 0 1 0 1 0 0 1 1

Rešitev 10. Z M \u003d J \u003d 1 dobimo 0 + K \u003d 1 * N * L ali K \u003d N * L, 4 rešitve: 11. Skupaj ima 4 + 4 \u003d 8 rešitev Odgovor: 8 KNL 0 0 0 0 0 1 0 1 0 1 1 1

Viri informacij: O.B. Bogomolova, D.Yu. Usenkov. В15: nove naloge in nova rešitev Informatika, št. 6, 2012, str. 35 - 39. K.Yu. Polyakov. Logične enačbe // Informatika, št. 14, 2011, str. 30–35. http://ege-go.ru/zadania/grb/b15/, [Elektronski vir]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronski vir].

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

Constant C ima vrednost 1 ali 0.

Logična enačba ima lahko od 0 do različnih rešitev. Če je C enak 1, so rešitve vse tiste množice spremenljivk iz tabele resnice, na katerih funkcija F prevzame vrednost true (1). Preostali nizi so rešitve enačbe s C, ki je enaka nič. Vedno lahko upoštevate samo enačbe obrazca:

Dejansko naj bo enačba dana:

V tem primeru lahko preidete na enakovredno enačbo:

Razmislimo o sistemu k logičnih enačb:

Rešitev sistema je niz spremenljivk, na katerih so izpolnjene vse enačbe sistema. V smislu logičnih funkcij je za rešitev sistema logičnih enačb treba najti niz, na katerem je logična funkcija F resnična in predstavlja veznik izvirnih funkcij:

Če je število spremenljivk majhno, na primer manjše od 5, potem ni težko sestaviti tabele resnice za funkcijo, ki nam omogoča povedati, koliko rešitev ima sistem in kakšne so množice, ki dajejo rešitve.

V nekaterih težavah USE pri iskanju rešitev v sistemu logičnih enačb število spremenljivk doseže 10. Nato konstrukcija tabele resnice postane skoraj nerešljiv problem. Za rešitev težave je potreben drugačen pristop. Za poljubni sistem enačb ne obstaja nobena splošna metoda razen naštevanja, ki omogoča reševanje takšnih problemov.

V težavah, predlaganih za izpit, rešitev običajno temelji na upoštevanju posebnosti sistema enačb. Ponavljam, razen če naštejem vse možnosti za niz spremenljivk, ni splošnega načina za rešitev težave. Rešitev mora biti zgrajena na podlagi posebnosti sistema. Pogosto je koristno izvesti predhodno poenostavitev sistema enačb z uporabo znanih zakonov logike. Druga uporabna tehnika za reševanje tega problema je naslednja. Ne zanimajo nas vsi sklopi, ampak samo tisti, pri katerih ima funkcija vrednost 1. Namesto, da zgradimo popolno tabelo resnice, bomo zgradili njen analog - drevo binarnih odločitev. Vsaka veja tega drevesa ustreza eni rešitvi in \u200b\u200bdoloča niz, na katerem ima funkcija vrednost 1. Število vej v odločitvenem drevesu sovpada s številom rešitev sistema enačb.

Pojasnil bom, kaj je binarno odločitveno drevo in kako je zgrajeno s primeri več nalog.

Naloga 18

Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ustreza sistemu dveh enačb?

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

Rešitev: Sistem enačb vključuje dve enačbi. Najdemo število rešitev za prvo enačbo glede na 5 spremenljivk -. Prvo enačbo lahko posledično štejemo za sistem 5 enačb. Kot je razvidno, sistem enačb dejansko predstavlja sklop logičnih funkcij. Velja tudi obratna trditev - vezanje pogojev je mogoče obravnavati kot sistem enačb.

Sestavimo odločitveno drevo za implikacijo () - prvi izraz veznika, ki ga lahko štejemo za prvo enačbo. Tako izgleda grafična podoba tega drevesa.

Drevo je sestavljeno iz dveh nivojev glede na število spremenljivk v enačbi. Prva raven opisuje prvo spremenljivko. Dve veji te stopnje odražata možne vrednosti te spremenljivke - 1 in 0. Na drugi ravni veje drevesa odražajo samo tiste možne vrednosti spremenljivke, za katere je enačba resnična. Ker enačba definira implikacijo, mora veja, na kateri ima vrednost 1, imeti na tej veji vrednost 1. Veja, na kateri ima vrednost 0, ustvari dve veji z vrednostima, enakima 0 in 1. Sestavljeno drevo definira tri rešitve, na katerih implikacija prevzame vrednost 1. Na vsako vejo se zapiše ustrezen niz vrednosti spremenljivk, ki daje rešitev enačbi.

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

Nadaljujmo z gradnjo odločitvenega drevesa tako, da dodamo naslednjo enačbo in naslednjo implikacijo. Posebnost našega sistema enačb je v tem, da vsaka nova enačba v sistemu uporablja eno spremenljivko iz prejšnje enačbe, pri čemer dodamo eno novo spremenljivko. Ker ima spremenljivka v drevesu že vrednosti, potem bo na vseh vejah, kjer ima spremenljivka vrednost 1, spremenljivka tudi vrednost 1. Za take veje se gradnja dreves nadaljuje na naslednjo raven, vendar se ne pojavijo nove veje. Edina veja, pri kateri ima spremenljivka vrednost 0, se razveje na 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. Celotno drevo odločitve za to enačbo izgleda takole:

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

Razlika je le v tem, da enačba uporablja spremenljivke Y. Ta enačba ima tudi 6 rešitev. Ker je mogoče vsako spremenljivo raztopino kombinirati z vsako spremenljivo raztopino, je skupno število rešitev 36.

Upoštevajte, da konstruirano odločitveno drevo daje ne samo število rešitev (po številu vej), ampak tudi same rešitve, zapisane na vsako vejo drevesa.

Dodelitev 19

Koliko različnih nizov vrednosti za logične spremenljivke x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 je izpolnjenih vseh spodaj navedenih pogojev?

Ta naloga je sprememba prejšnje naloge. Razlika je v tem, da je za povezavo spremenljivk X in Y dodana druga enačba.

Iz enačbe izhaja, da ima vrednost 1 (obstaja ena takšna rešitev), potem ima vrednost 1. Tako obstaja en niz, na katerem in imata vrednosti 1. Ko je enak 0, ima lahko poljubno vrednost, tako 0 kot in 1. Zato vsakemu nizu, ki je enak 0, in obstaja 5 takih nizov, ustreza vseh 6 nizov s spremenljivkami Y. Zato je skupno število rešitev 31.

Dodelitev 20

Rešitev: Ob spominu na osnovno enakovrednost zapišemo svojo enačbo kot:

Ciklična veriga implikacij pomeni identiteto spremenljivk, zato je naša enačba enakovredna enačbi:

Ta enačba ima dve rešitvi, kadar sta vsi 1 ali 0.

Dodelitev 21

Koliko rešitev ima enačba:

Rešitev: Tako kot v problemu 20 prehajamo iz cikličnih implikacij na identitete, enačbo prepisujemo v obliko:

Zgradimo drevo odločitve za to enačbo:

Naloga 22

Koliko rešitev ima naslednji sistem enačb?

Kako rešiti nekatere težave v oddelkih A in B izpita iz računalništva

Lekcija št. 3 Logika. Logične funkcije. Reševanje enačb

Logiki izjav je namenjenih veliko število problemov USE. Za rešitev večine zadostuje poznavanje osnovnih zakonov logike predloga, poznavanje tabel resnic o logičnih funkcijah ene in dveh spremenljivk. Tu so osnovni zakoni logike predloga.

Komutativnost disjunkcije in veznika:
a ˅ b ≡ b ˅ a
a ^ b ≡ b ^ a
Porazdelitveno pravo glede ločitve in veznika:
a ˅ (b ^ c) ≡ (a ˅ b) ^ (a ˅ c)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Negacija negacije:
¬ (¬a) ≡ a
Doslednost:
a ^ ¬a ≡ napačno
Ekskluzivno tretje:
a ˅ ¬a ≡ res
De Morganovi zakoni:
¬ (a ˅ b) ≡ ¬a ˄ ¬b
¬ (a ˄ b) ≡ ¬a ˅ ¬b
Poenostavitev:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ res ≡ a
a ˄ false ≡ false
Absorpcija:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a
Nadomestitev posledic
a → b ≡ ¬a ˅ b
Zamenjava identitete
a ≡ b ≡ (a ˄ b) ˅ (¬a ˄ ¬b)

Zastopanje logične funkcije

Vsako logično funkcijo n spremenljivk - F (x 1, x 2,… x n) lahko podate s tabelo resnice. Taka tabela vsebuje 2 n nizov spremenljivk, za katere je podana vrednost funkcije na tem nizu. Ta metoda je dobra, kadar je število spremenljivk relativno majhno. Tudi pri n\u003e 5 postane reprezentacija slabo vidna.

Drug način je določiti funkcijo po neki formuli z uporabo dobro znanih dokaj preprostih funkcij. Sistem funkcij (f 1, f 2, ... f k) se imenuje popoln, če je katero koli logično funkcijo mogoče izraziti s formulo, ki vsebuje samo funkcije f i.

Sistem funkcij (¬, ˄, ˅) je dokončan. Zakon 9 in 10 sta primera, kako se implikacija in identiteta izražata s pomočjo negacije, konjunkcije in disjunkcije.

Pravzaprav je popoln tudi sistem dveh funkcij - negacija in veznica ali negacija in disjunkcija. Iz de Morganovih zakonov sledijo predstavitve, ki omogočajo izražanje veznika z negacijo in disjunkturo ter v skladu s tem izražanje disjunkcije z negacijo in veznikom:

(a ˅ b) ≡ ¬ (¬a ˄ ¬b)
(a ˄ b) ≡ ¬ (¬a ˅ ¬b)

Paradoksalno je, da je sistem, sestavljen iz samo ene funkcije, dokončan. Obstajata dve binarni funkciji, antikonjunkcija in anti disjunkcija, imenovana puščica Peirce in poteza Schaeffer, ki predstavljata votel sistem.

Osnovne funkcije programskih jezikov običajno vključujejo identiteto, negacijo, vezništvo in ločevanje. Pri nalogah izpita se skupaj s temi funkcijami pogosto srečujejo posledice.

Oglejmo si nekaj preprostih logičnih nalog.

Problem 15:

Podana je drobnica tabele resnice. Katera od zgornjih treh funkcij ustreza temu odseku?

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

(X 1 → X 2) ˄ ¬ X 3 ˅ X 4
(¬ X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Funkcija številka 3.

Če želite rešiti težavo, morate poznati tabele resnic osnovnih funkcij in si zapomniti prednostne naloge operacij. Naj vas spomnim, da ima konjunkcija (logično množenje) večjo prednost in se izvaja pred ločitvijo (logično seštevanje). Pri izračunu je enostavno opaziti, da imata funkcije s števkama 1 in 2 v tretjem nizu vrednost 1 in zato ne ustrezajo fragmentu.

Problem 16:

Katera od danih številk izpolnjuje pogoj:

(števke, začenši z najpomembnejšo števko, gredo v padajočem vrstnem redu) → (število enakomerno) ˄ (najmanj pomembna številka - sodo) ˄ (najpomembnejša številka - liho)

Če je takih številk več, navedite največjo.

13579
97531
24678
15386

Pogoj izpolnjuje številka 4.

Prvi dve številki ne izpolnjujeta pogoja iz razloga, ker je najmanj pomembna številka liho. Veznik pogojev je napačen, če je eden od pogojev veznika napačen. Pogoj za najpomembnejšo številko ni izpolnjen za tretjo številko. Za četrto številko so izpolnjeni pogoji, naloženi za nižje in višje števke števila. Prav tako je resničen prvi izraz veznika, saj je implikacija resnična, če je njena predpostavka napačna, kar se zgodi v v tem primeru.

Problem 17: Dve priče so izjavile naslednje:

Prva priča: Če je A kriv, potem je B še bolj kriv, C pa nedolžen.

Druga priča: Dva sta kriva. In točno eden od preostalih je kriv in kriv, ampak ne morem točno povedati, kdo točno.

Kakšne ugotovitve o krivdi A, B in C lahko izluščite iz pričevanja?

Odgovor: Iz pričevanja izhaja, da sta A in B krivi, C pa nedolžen.

Rešitev: Odgovor je seveda možen na podlagi zdrave pameti. Toda poglejmo, kako je to mogoče storiti strogo in formalno.

Prva stvar je formalizacija izjav. Uvedimo tri logične spremenljivke - A, B in C, od katerih vsaka drži (1), če je kriv ustrezni osumljenec. Potem se izpoved prve priče poda s formulo:

A → (B ˄ ¬C)

Izpoved druge priče je podana s formulo:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Pričevanja obeh prič se domnevajo, da sta resnična in predstavljata povezavo ustreznih formul.

Zgradimo tabelo resnice za te odčitke:

A	B	C	Ž 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Povzetek pričevanja je resničen le v enem primeru, kar vodi do nedvoumnega odgovora - A in B sta kriva, C pa nedolžna.

Iz analize te tabele tudi izhaja, da je izpoved druge priče bolj informativne narave. Iz resnice njegovega pričevanja izhajata samo dve možni možnosti - A in B sta kriva, C pa nedolžna ali A in C kriv, B pa nedolžen. Pričevanje prve priče je manj informativno - 5 različnih možnosti ustreza njegovemu pričanju. Izpovedi obeh prič skupaj dajeta nedvoumen odgovor o krivdi osumljencev.

Logične enačbe in sistemi enačb

Naj bo F (x 1, x 2,… x n) logična funkcija n spremenljivk. Logična enačba je:

F (x 1, x 2, ... x n) \u003d S,

Constant C ima vrednost 1 ali 0.

Logična enačba ima lahko od 0 do 2 n različnih rešitev. Če je C enak 1, so rešitve vse tiste množice spremenljivk iz tabele resnice, na katerih funkcija F prevzame vrednost true (1). Preostali nizi so rešitve enačbe s C, ki je enaka nič. Vedno lahko upoštevate samo enačbe obrazca:

F (x 1, x 2, ... x n) \u003d 1

Dejansko naj bo enačba dana:

F (x 1, x 2, ... x n) \u003d 0

V tem primeru lahko preidete na enakovredno enačbo:

¬F (x 1, x 2, ... x n) \u003d 1

Razmislimo o sistemu k logičnih enačb:

F 1 (x 1, x 2, ... x n) \u003d 1

F 2 (x 1, x 2, ... x n) \u003d 1

F k (x 1, x 2, ... x n) \u003d 1

Rešitev sistema je niz spremenljivk, na katerih so izpolnjene vse enačbe sistema. V smislu logičnih funkcij je za rešitev sistema logičnih enačb treba najti niz, na katerem je logična funkcija Φ resnična in predstavlja veznik izvirnih funkcij F:

Ф \u003d F 1 ˄ F 2 ˄… F k

Če je število spremenljivk majhno, na primer manjše od 5, potem ni težko sestaviti tabele resnice za funkcijo Φ, ki nam omogoča povedati, koliko rešitev ima sistem in kakšne so množice, ki dajejo rešitve.

V težavah, predlaganih za izpit, rešitev običajno temelji na upoštevanju posebnosti sistema enačb. Ponavljam, razen če naštejem vse možnosti za niz spremenljivk, ni splošnega načina za rešitev težave. Rešitev mora biti zgrajena na podlagi posebnosti sistema. Pogosto je koristno izvesti predhodno poenostavitev sistema enačb z uporabo znanih zakonov logike. Druga uporabna tehnika za reševanje tega problema je naslednja. Ne zanimajo nas vsi sklopi, ampak samo tisti, na katerih ima funkcija Φ vrednost 1. Namesto, da zgradimo popolno tabelo resnice, bomo konstruirali njen analog - binarno drevo odločitev. Vsaka veja tega drevesa ustreza eni rešitvi in \u200b\u200bdoloča niz, na katerem ima funkcija F vrednost 1. Število vej v odločitvenem drevesu sovpada s številom rešitev sistema enačb.

Pojasnil bom, kaj je binarno odločitveno drevo in kako je zgrajeno s primeri več nalog.

Naloga 18

Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ustreza sistemu 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 prve enačbe glede na 5 spremenljivk - x 1, x 2,… x 5. Prvo enačbo lahko posledično štejemo za sistem 5 enačb. Kot je razvidno, sistem enačb dejansko predstavlja vezanje logičnih funkcij. Velja tudi obratna trditev - vezanje pogojev je mogoče obravnavati kot sistem enačb.

Zgradimo drevo odločitve za implikacijo (x1 → x2) - prvi izraz veznika, ki ga lahko štejemo za prvo enačbo. Tako izgleda grafični prikaz tega drevesa:

Drevo je sestavljeno iz dveh nivojev glede na število spremenljivk v enačbi. Prva raven opisuje prvo spremenljivko X 1. Dve veji te stopnje odražata možne vrednosti te spremenljivke - 1 in 0. Na drugi ravni veje drevesa odražajo le tiste možne vrednosti spremenljivke X 2, za katere je enačba resnična. Ker enačba določa pomen, veja, na kateri je X 1, zahteva, da je na tej veji X 2 1. Veja, na kateri je X 1 0, ustvari dve veji z X2 vrednostima 0 in 1 Konstruirano drevo definira tri rešitve, na katerih implikacija X 1 → X 2 prevzame vrednost 1. V vsako vejo je zapisan ustrezen niz vrednosti spremenljivk, ki daje rešitev enačbi.

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

Nadaljujemo z gradnjo drevesa odločitve tako, da dodamo naslednjo enačbo, naslednjo implikacijo X 2 → X 3. Posebnost našega sistema enačb je v tem, da vsaka nova enačba v sistemu uporablja eno spremenljivko iz prejšnje enačbe, pri čemer dodamo eno novo spremenljivko. Ker ima spremenljivka X 2 v drevesu že vrednosti, potem bo na vseh vejah, kjer ima spremenljivka X2 vrednost 1, tudi spremenljivka X 3 vrednost 1. Za take veje se konstrukcija dreves nadaljuje na naslednjo raven, vendar se ne pojavijo nove veje. Edina veja, pri kateri ima spremenljivka X 2 vrednost 0, se razveja na dve veji, kjer bo spremenljivka X 3 dobila vrednosti 0 in 1. Vsako dodajanje nove enačbe glede na njeno specifičnost doda eno rešitev. Izvirna prva enačba:

(x1 → x2) / \\ (x2 → x3) / \\ (x3 → x4) / \\ (x4 → x5) \u003d 1
ima 6 rešitev. Celotno drevo odločitve za to enačbo izgleda takole:

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

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

Razlika je le v tem, da enačba uporablja spremenljivke Y. Ta enačba ima tudi 6 rešitev. Ker je vsako rešitev za spremenljivke X i mogoče kombinirati z vsako raztopino za spremenljivke Y j, je skupno število rešitev 36.

Upoštevajte, da konstruirano odločitveno drevo daje ne samo število rešitev (po številu vej), ampak tudi same rešitve, zapisane na vsako vejo drevesa.

Dodelitev 19

Koliko različnih nizov vrednosti za logične spremenljivke x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 je izpolnjenih vseh spodaj navedenih pogojev?

(x1 → x2) / \\ (x2 → x3) / \\ (x3 → x4) / \\ (x4 → x5) \u003d 1
(y1 → y2) / \\ (y2 → y3) / \\ (y3 → y4) / \\ (y4 → y5) \u003d 1
(x1 → y1) \u003d 1

Ta naloga je sprememba prejšnje naloge. Razlika je v tem, da je za povezavo spremenljivk X in Y dodana druga enačba.

Iz enačbe X 1 → Y 1 izhaja, da kadar ima X 1 vrednost 1 (ena taka rešitev obstaja), potem ima Y 1 tudi vrednost 1. Tako obstaja en niz, na katerem imata X 1 in Y 1 vrednosti 1. Za X 1, ki je enak 0, ima Y 1 lahko poljubno vrednost, tako 0 kot 1. Torej, vsak niz z X 1 je enak 0 in obstaja 5 takih nizov, vseh 6 nizov s spremenljivkami Y ustreza. ...

Dodelitev 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) \u003d 1

Rešitev: Ob spominu na osnovno enakovrednost zapišemo svojo enačbo kot:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) \u003d 1

Ciklična veriga implikacij pomeni identiteto spremenljivk, zato je naša enačba enakovredna enačbi:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 \u003d 1

Ta enačba ima dve rešitvi, kadar so vsi X i enaki 1 ali 0.

Dodelitev 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) \u003d 1

Rešitev: Tako kot v problemu 20 prehajamo iz cikličnih implikacij na identitete, enačbo prepisujemo v obliko:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) \u003d 1

Zgradimo drevo odločitve za to enačbo:

Naloga 22

Koliko rešitev ima naslednji sistem enačb?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅ (¬ (X 1 ≡X 2) ˄ ¬ (X 3 ≡X 4)) \u003d 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅ (¬ (X 3 ≡X 4) ˄ ¬ (X 5 ≡X 6)) \u003d 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅ (¬ (X 5 ≡X 6) ˄ ¬ (X 7 ≡X 8)) \u003d 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅ (¬ (X 7 ≡X 8) ˄ ¬ (X 9 ≡X 10)) \u003d 0

Odgovor: 64

Rešitev: Premaknite se z 10 spremenljivk na 5 spremenljivk z uvedbo naslednje spremembe spremenljivk:

Y 1 \u003d (X 1 ≡ X 2); Y2 \u003d (X3-X4); Y 3 \u003d (X 5 ≡ X 6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);

Potem bo prva enačba dobila obliko:

(Y 1 ˄ Y 2) ˅ (YY 1 ˄ ¬Y 2) \u003d 0

Enačbo lahko poenostavimo tako, da zapišemo kot:

(Y 1 ≡ Y 2) \u003d 0

Če preidemo na tradicionalni obrazec, po poenostavitvah v obrazce zapišemo sistem:

¬ (Y 1 ≡ Y 2) \u003d 1

¬ (Y 2 ≡ Y 3) \u003d 1

¬ (Y 3 ≡ Y 4) \u003d 1

¬ (Y 4 ≡ Y 5) \u003d 1

Drevo odločitve za ta sistem je preprosto in je sestavljeno iz dveh vej z izmeničnimi spremenljivimi vrednostmi:

Če se vrnete k izvirnim spremenljivkam X, upoštevajte, da vsaka vrednost spremenljivke Y ustreza dvema vrednostima spremenljivk X, zato vsaka rešitev v spremenljivkah Y ustvari 2 5 rešitev v spremenljivkah X. Dve veji ustvarjata 2 * 2 5 rešitev, tako da je skupno število rešitev 64.

Kot lahko vidite, je vsak problem za reševanje sistema enačb potreben svoj pristop. Običajna tehnika je izvajanje enakovrednih transformacij za poenostavitev enačb. Pogosta tehnika je tudi gradnja dreves odločitev. Uporabljeni pristop delno spominja na konstrukcijo tabele resnice s to posebnostjo, da niso zgrajene vse skupine možnih vrednosti spremenljivk, ampak le tiste, na katerih funkcija prevzame vrednost 1 (res). V predlaganih težavah pogosto ni treba sestaviti celovitega odločitvenega drevesa, saj je na začetni stopnji mogoče ugotoviti pravilnost pojavljanja novih podružnic na vsaki naslednji stopnji, kot je bilo to storjeno na primer v problematiki 18.

Na splošno so problemi iskanja sistema logičnih enačb dobre matematične vaje.

Če je težavo težko rešiti ročno, lahko rešitev težave zaupate računalniku tako, da napišete ustrezen program za reševanje enačb in sistemov enačb.

Pisanje takšnega programa ni težko. Takšen program se zlahka spopade z vsemi nalogami, ki jih ponuja izpit.

Nenavadno je, a težava iskanja rešitev sistemov logičnih enačb je za računalnik tudi težavna, izkaže se, da ima računalnik svoje meje. Računalnik se lahko preprosto spopade z nalogami, kjer je število spremenljivk 20-30, vendar bo začel razmišljati o večjih nalogah še dolgo. Bistvo je, da je funkcija 2 n, ki določa število nizov, eksponent, ki hitro narašča s povečanjem n. Tako hitro, da se navaden osebni računalnik ne more spoprijeti z nalogo s 40 spremenljivkami na dan.

C # program za reševanje logičnih enačb

Program za reševanje logičnih enačb je koristno napisati iz več razlogov, pa čeprav samo z njegovo pomočjo lahko preverite pravilnost lastne rešitve težav s testom USE. Drugi razlog je, da je tak program odličen primer težave s programiranjem, ki izpolnjuje zahteve za težave kategorije C na izpitu.

Ideja o gradnji programa je preprosta - temelji na popolnem naštevanju vseh možnih nizov spremenljivih vrednosti. Ker je za dano logično enačbo ali sistem enačb znano število spremenljivk n, je znano tudi število nizov - 2 n, ki jih želite razvrstiti. Z osnovnimi funkcijami jezika C # - negacijo, disjunkturo, veznico in identiteto je enostavno napisati program, ki za dani niz spremenljivk izračuna vrednost logične funkcije, ki ustreza logični enačbi ali sistemu enačb.

V takšnem programu morate cikel sestaviti po številu nizov, v telesu cikla po nastavljeni številki, sami oblikovati množico, izračunati vrednost funkcije na tem množici in če je ta vrednost enaka 1, potem niz daje rešitev enačbi.

Edina težava, ki nastane pri izvajanju programa, je povezana z nalogo oblikovanja nabora spremenljivih vrednosti po nastavljeni številki. Lepota te naloge je v tem, da je ta na videz težka naloga dejansko omejena na preprosto nalogo, ki se je že večkrat pojavila. Dejansko je dovolj, da razumemo, da množica vrednosti spremenljivk, ki ustreza številu i, sestavljena iz ničel in ena, predstavlja binarni zapis številke i. Torej težka naloga pridobitve niza vrednosti spremenljivk iz določenega števila se zmanjša na dobro znano nalogo pretvorbe števila v binarni sistem.

Tako izgleda funkcija v C #, ki rešuje naš problem:

///

/// program za štetje številnih rešitev

/// logična enačba (sistem enačb)

///

/// boolova funkcija - metoda,

/// katerega podpis nastavi pooblaščenec DF

///

/// število spremenljivk

/// število odločitev

statični int SolveEquations (zabava DF, int n)

bool set \u003d nov bool [n];

int m \u003d (int) Math.Pow (2, n); // število sklopov

int p \u003d 0, q \u003d 0, k \u003d 0;

// Celotna iteracija nad številom nizov

za (int i \u003d 0; i< m; i++)

// Oblikovanje naslednjega niza - niz,

// podana z binarnim prikazom števila i

za (int j \u003d 0; j< n; j++)

k \u003d (int) Math.Pow (2, j);

// Izračunajte vrednost funkcije na množici

Za razumevanje programa upam, da so razlage ideje programa in komentarji v njegovem besedilu dovolj. Podrobneje se bom zadrževal le na razlagi naslova dane funkcije. Funkcija SolveEquations ima dva vhodna parametra. Parameter fun določa logično funkcijo, ki ustreza enačbi ali sistemu enačb, ki jih je treba rešiti. Parameter n določa število spremenljivk za zabavo. Kot rezultat, funkcija SolveEquations vrne število rešitev logični funkciji, torej število tistih nizov, na katerih funkcija oceni, da je res.

Za šolarje je običajno, če je vhodni parameter x neke funkcije F (x) spremenljivka aritmetične, nizke ali logične vrste. V našem primeru se uporablja močnejša konstrukcija. Funkcija SolveEquations se nanaša na funkcije višjega reda - funkcije tipa F (f), katerih parametri so lahko ne samo enostavne spremenljivke, ampak tudi funkcije.

Razred funkcij, ki jih lahko kot parameter posredujemo funkciji SolveEquations, je opredeljen na naslednji način:

delegat bool DF (bool vars);

V tem razredu so vse funkcije, ki so kot parameter posredovale niz vrednosti logičnih spremenljivk, ki jih poda matrika vars. Rezultat je logična vrednost, ki predstavlja vrednost funkcije v tem nizu.

Na koncu bom dal program, v katerem se funkcija SolveEquations uporablja za reševanje več sistemov logičnih enačb. Funkcija SolveEquations je del spodaj navedenega razreda ProgramCommon:

razred ProgramCommon

delegat bool DF (bool vars);

statična praznina Main (string args)

Console.WriteLine ("Funkcije in odločitve -" +

SolveEquations (FunAnd, 2));

Console.WriteLine ("Funkcije 51 rešitev -" +

SolveEquations (Fun51, 5));

Console.WriteLine ("Funkcije 53 rešitev -" +

SolveEquations (Fun53, 10));

statični bool FunAnd (bool vars)

vrniti vars && vars;

statični bool Fun51 (bool vars)

f \u003d f && (! vars || vars);

statični bool Fun53 \u200b\u200b(bool vars)

f \u003d f && ((vars \u003d\u003d vars) || (vars \u003d\u003d vars));

f \u003d f && (! ((vars \u003d\u003d vars) || (vars \u003d\u003d vars)));

Tu so videti rezultati rešitve za ta program:

10 nalog za samostojno delo

Katera od treh funkcij je enakovredna:
1. (X → Y) ˅ ¬Y
2. ¬ (X ˅ ¬Y) ˄ (X → ¬Y)
3. ¬X ˄ Y
Poda se delček tabele resnice:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Kateri od treh funkcij ustreza ta delček:

(X 1 ˅XX 2) ˄ (X 3 → X 4)
(X 1 → X 3) ˄ X 2 ˅ X 4
X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
Žirijo sestavljajo trije ljudje. Odločitev je sprejeta, če zanjo glasuje predsednik žirije, ki ga podpira vsaj eden od članov žirije. V nasprotnem primeru se ne sprejme nobena odločitev. Sestavite logično funkcijo, ki formalizira postopek odločanja.
X zmaga nad Y, če s štirimi meti kovanca tri glave izpadejo. Določite boolovo funkcijo, ki opisuje dobitke X.
Besede v stavku so oštevilčene in se začnejo z eno. Stavek velja za dobro oblikovan, če so izpolnjena naslednja pravila:
1. Če se enakomerna beseda v oštevilčevanju konča z samoglasnikom, se mora naslednja beseda, če obstaja, začeti z samoglasnikom.
2. Če se nešteta beseda v oštevilčevanju konča s soglasnikom, se mora naslednja beseda, če obstaja, začeti s soglasnikom in se končati z samoglasnikom.
  Kateri od naslednjih stavkov je dobro oblikovan:
3. Mama je umivala Mašo z milom.
4. Vodja je vedno zgled.
5. Resnica je dobra, a sreča je boljša.
Koliko rešitev ima enačba:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) \u003d 1
Naštejte vse rešitve enačbe:
(a → b) → c \u003d 0
Koliko rešitev ima naslednji sistem enačb:
X 0 → X 1 ˄ X 1 → X 2 \u003d 1
X 2 → X 3 ˄ X 3 → X 4 \u003d 1
X 5 → X 6 ˄ X 6 → X 7 \u003d 1
X 7 → X 8 ˄ X 8 → X 9 \u003d 1
X 0 → X 5 \u003d 1
Koliko rešitev ima enačba:
(((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 \u003d 1

Odgovori na težave:

Funkciji b in c sta enakovredni.
Odlomek ustreza funkciji b.
Naj logična spremenljivka P prevzame vrednost 1, ko predsednik žirije glasuje za "odločitev". Spremenljivki M 1 in M \u200b\u200b2 predstavljata mnenje članov žirije. Logično funkcijo, ki določa sprejem pozitivne odločitve, lahko zapišemo na naslednji način:
P ˄ (M 1 ˅ M 2)
Naj boolova spremenljivka P i prevzame vrednost 1, ko "glave" izpadejo med metanjem i-tega kovanca. Logično funkcijo, ki nastavi izplačilo X, lahko zapišemo na naslednji način:
¬ ((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4))
Ponudba b.
Enačba ima 3 rešitve: (a \u003d 1; b \u003d 1; c \u003d 0); (a \u003d 0; b \u003d 0; c \u003d 0); (a \u003d 0; b \u003d 1; c \u003d 0)

Načini reševanja sistemov logičnih enačb

Kirgizova E.V., Nemkova A.E.

Lesosibirski pedagoški inštitut -

podružnica Sibirske zvezne univerze, Rusija

Sposobnost doslednega razmišljanja, razmišljanje z dokazi, gradnja hipotez, zavračanje negativnih zaključkov ne pride samo po sebi, to veščino razvija znanost o logiki. Logika je veda, ki proučuje metode ugotavljanja resnice ali napačnosti nekaterih trditev, ki temeljijo na resnici ali lažnosti drugih trditev.

Obvladovanje osnov te znanosti je nemogoče brez reševanja logičnih problemov. Preverjanje oblikovanja veščin za uporabo svojega znanja v novih razmerah poteka mimo. Zlasti je to sposobnost reševanja logičnih težav. Naloge B15 pri izpitu so naloge večje zapletenosti, saj vsebujejo sisteme logičnih enačb. Obstajajo različni načini reševanja sistemov logičnih enačb. To je redukcija na eno enačbo, izgradnja tabele resnice, razgradnja, zaporedna rešitev enačb itd.

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

Razmislite 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). Za to se uporablja delovanje logične negacije. Potem, če so v enačbah 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 narediti pretvorbo nastale enačbe na podlagi zakonov logične algebre in dobiti specifično rešitev v sistemu.

1. rešitev:Uporabite obratno na obe strani prve enačbe:

Posledice predstavljamo z osnovnimi operacijami "ALI", "NE":

Ker je leva enačba enaka 1, jih lahko z operacijo "IN" združite v eno enačbo, ki je enaka prvotnemu sistemu:

Odpremo prvo oklepaj v skladu z de Morganovim zakonom in dobimo rezultat:

Tako dobljena enačba ima eno rešitev:A \u003d 0, B \u003d 0 in C \u003d 1.

Naslednja pot je gradnja tabel resnice ... Ker imata logične vrednosti le dve vrednosti, lahko preprosto poiščete vse možnosti in med njimi najdete tiste, za katere je dani sistem enačb izpolnjen. To pomeni, da sestavimo eno skupno tabelo resnice za vse enačbe v sistemu in poiščemo vrstico z želenimi vrednostmi.

2. rešitev: Sestavimo tabelo resnice za sistem:








0	0	1	1	0	1

Vrstica, za katero so izpolnjeni pogoji naloge, je poudarjena krepko. Torej A \u003d 0, B \u003d 0 in C \u003d 1.

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

3. rešitev:Naj bo A \u003d 0, potem:

Iz prve enačbe dobimoB \u003d 0, od drugega - C \u003d 1. Sistemska rešitev: A \u003d 0, B \u003d 0 in C \u003d 1.

Uporabite lahko tudi metodo zaporedna rešitev enačb , pri vsakem koraku dodate eno spremenljivko v obravnavani niz. Če želite to narediti, je treba enačbe preoblikovati tako, da se spremenljivke vnesejo po abecednem vrstnem redu. Nato zgradimo drevo odločitev, ki mu zaporedno dodajamo spremenljivke.

Prva enačba v sistemu je odvisna samo od A in B, druga enačba pa na A in C. Spremenljivka A lahko sprejme dve vrednosti 0 in 1:

Iz prve enačbe izhaja, da je , torej za A \u003d 0 in dobimo B \u003d 0, za A \u003d 1 pa B \u003d 1. Torej, prva enačba ima dve rešitvi za spremenljivki A in B.

Naredimo drugo enačbo, iz katere določimo vrednosti C za vsako možnost. Pri A \u003d 1 implikacija ne more biti napačna, torej druga veja drevesa nima rešitve. KdajA \u003d 0 dobimo edino rešitevC \u003d 1 :

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

Na izpitu iz računalništva je pogosto treba določiti število rešitev v sistemu logičnih enačb, ne da bi sami našli rešitve, za to obstajajo tudi določene metode. Glavni način iskanja števila rešitev sistema logičnih enačb je sprememba spremenljivk... Najprej je treba čim bolj poenostaviti vsako enačbo na podlagi zakonov logične algebre, nato pa zapletene dele enačb nadomestiti z novimi spremenljivkami in določiti število rešitev novega sistema. Nato se vrnite na zamenjavo in določite število rešitev zanjo.

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

Odločba:Uvedimo nove spremenljivke:X \u003d A → B in Y \u003d C → D ... Enačba bo ob upoštevanju novih spremenljivk zapisana kot:X + Y \u003d 1.

Odstopanje velja v treh primerih: (0; 1), (1; 0) in (1; 1), medtem koX in Y je implikacija, torej je resnična v treh primerih in napačna v enem. Zato bo primer (0; 1) ustrezal trem možnim kombinacijam parametrov. Zadeva (1; 1) - bo ustrezala devetim možnim kombinacijam parametrov prvotne enačbe. To pomeni, da obstaja 3 + 9 \u003d 15 možnih rešitev te enačbe.

Naslednji način za določitev števila rešitev sistema logičnih enačb je binarno drevo... Upoštevajmo to metodo s primerom.

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

Dani sistem enačb je enak 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 \u003d 1 in tako naprej do x m \u003d 1. Od tod množica (1; 1; ...; 1) odm enote je rešitev sistema. Naj zdajx 1 \u003d 0, potem iz prve enačbe, ki jo imamox 2 \u003d 0 oz x 2 =1.

Kdaj x 2 resnično ugotovimo, da so tudi druge spremenljivke resnične, torej da je množica (0; 1;…; 1) rešitev sistema. Kdajx 2 \u003d 0 to dobimo x 3 \u003d 0 oz x 3 \u003d, in tako naprej. Nadaljujemo z zadnjo spremenljivko, ugotovimo, da so rešitve enačbe naslednji nizi spremenljivk (m +1 raztopina, v vsaki raztopinim vrednosti spremenljivk):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Ta pristop dobro ponazorimo z gradnjo binarnega drevesa. Število možnih rešitev je število različnih vej zgrajenega drevesa. Zlahka je videti, da je enakm +1.

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

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

Naredimo sistem enačb v obliki:

In sestavimo tabelo resnice ločeno za eno enačbo:

x 1	x 2	(x 1 → x 2)

Sestavimo tabelo resnice 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)*

Nadalje lahko vidite, da ena enačba drži 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 iz nekaj ničel in več mraztopine, v katere je dodana ena enota, od zadnjega mesta do zapolnitve vseh možnih mest. Lahko se domneva, da bo splošna rešitev enaka oblika, vendar za tak pristop, da postane rešitev, potrebuje dokaz, da je predpostavka resnična.

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

Literatura:

1. Logične naloge / O.B. Bogomolov - 2. izd. - M .: BINOM. Laboratorij znanja, 2006. - 271 str .: bol.

2. Polyakov K.Yu. Sistemi logičnih enačb / Izobraževalno-metodični časopis za učitelje informatike: Informatika №14, 2011

Obstajajo različni načini reševanja sistemov logičnih enačb. Zmanjšanje je na eno enačbo, gradnja tabele resnice in razkroj.

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

1. rešitev:Uporabite obratno na obe strani prve enačbe:

Posledice predstavljamo z osnovnimi operacijami "ALI", "NE":

Ker je leva enačba enaka 1, jih lahko z operacijo "IN" združite v eno enačbo, ki je enaka prvotnemu sistemu:

Odpremo prvo oklepaj v skladu z de Morganovim zakonom in dobimo rezultat:

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

2. rešitev: Sestavimo tabelo resnice za sistem:








0	0	1	1	0	1

Vrstica, za katero so izpolnjeni pogoji naloge, je poudarjena krepko. Torej A \u003d 0, B \u003d 0 in C \u003d 1.

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

3. rešitev:Naj bo A \u003d 0, potem pa:

Iz prve enačbe dobimo B \u003d 0, iz druge - C \u003d 1. Sistemska rešitev: A \u003d 0, B \u003d 0 in C \u003d 1.

Na izpitu iz računalništva je pogosto treba določiti število rešitev v sistemu logičnih enačb, ne da bi sami našli rešitve, za to obstajajo tudi določene metode. Glavni način iskanja števila rešitev sistema logičnih enačb jesprememba spremenljivk... Najprej je treba čim bolj poenostaviti vsako enačbo na podlagi zakonov logične algebre, nato pa zapletene dele enačb nadomestiti z novimi spremenljivkami in določiti število rešitev novega sistema. Nato se vrnite na zamenjavo in določite število rešitev zanjo.

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

Odločba:Uvedimo nove spremenljivke: X \u003d A → B in Y \u003d C → D. Enačba bo ob upoštevanju novih spremenljivk zapisana kot: X + Y \u003d 1.

Ločitev je resnična v treh primerih: (0; 1), (1; 0) in (1; 1), medtem ko sta X in Y implikacija, torej je resnična v treh primerih in napačna v enem. Zato bo primer (0; 1) ustrezal trem možnim kombinacijam parametrov. Zadeva (1; 1) - bo ustrezala devetim možnim kombinacijam parametrov prvotne enačbe. To pomeni, da obstaja 3 + 9 \u003d 15 možnih rešitev te enačbe.

Naslednji način za določitev števila rešitev sistema logičnih enačb je binarno drevo... Upoštevajmo to metodo s primerom.

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

Dani sistem enačb je enak 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 \u003d 1 in tako naprej do x m \u003d 1. Torej je množica (1; 1;…; 1) m enot rešitev za sistem. Naj zdaj x 1 \u003d 0, potem iz prve enačbe, ki jo imamo x 2 \u003d 0 oz x 2 =1.

Kdaj x 2 resnično ugotovimo, da so tudi druge spremenljivke resnične, torej da je množica (0; 1;…; 1) rešitev sistema. Kdaj x 2 \u003d 0 to dobimo x 3 \u003d 0 oz x 3 \u003d, in tako naprej. 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):