Noskin Andrej Nikolajevič,
učitelj informatike
najvišja kvalifikacijska kategorija,
Kandidat za vojaške vede, izredni profesor
Licej GBOU št. 1575, Moskva
Optimizirana metoda preslikave za reševanje problema 23 iz Enotnega državnega izpita KIM iz računalništva in IKT
Ena najtežjih nalog na enotnem državnem izpitu KIM je problem 23, v katerem morate najti število različnih nizov vrednosti logičnih spremenljivk, ki izpolnjujejo določen pogoj.
Ta naloga je morda najtežja naloga Enotnega državnega izpita KIM iz računalništva in IKT. Praviloma ga ne obvlada več kot 5 % preiskovancev (1).
Tako majhen odstotek študentov, ki so opravili to nalogo, je razloženo z naslednjim:
- učenci lahko zamenjujejo (pozabljajo) znake logičnih operacij;
- matematične napake v procesu izvajanja izračunov;
- napake v sklepanju pri iskanju rešitve;
- napake v procesu poenostavljanja logičnih izrazov;
- učitelji priporočajo rešitev te težave po opravljenem celotnem delu, saj je verjetnost
napake so zelo velike, »teža« naloge pa je le ena primarna točka.
Poleg tega imajo nekateri učitelji sami težave pri reševanju tovrstnih problemov in zato poskušajo z otroki reševati preprostejše probleme.
Tudi zapleta situacijo je, da je v tem bloku veliko število različne naloge in je nemogoče izbrati predlogo rešitve.
Da bi popravili to situacijo, pedagoška skupnost dokončno oblikuje glavni dve metodi za reševanje problemov te vrste: rešitev z uporabo bitnih verig (2) in metode preslikave (3).
Potreba po izpopolnitvi (optimizaciji) teh metod je posledica dejstva, da se naloge nenehno spreminjajo tako po strukturi kot po številu spremenljivk (samo ena vrsta spremenljivk X, dve vrsti spremenljivk X in Y, tri vrste: X, Y , Z).
Težavnost obvladovanja teh metod za reševanje problemov potrjuje dejstvo, da na spletni strani K.Yu. Polyakova obstaja 38 analiz te vrste problema (4). Nekatere analize nudijo več kot eno rešitev problema.
Zadnje čase na enotnem državnem izpitu KIM iz računalništva so težave z dvema vrstama spremenljivk X in Y.
Optimiziral sem način prikaza in spodbujam svoje študente k uporabi izboljšanega načina.
To daje rezultate. Odstotek mojih učencev, ki se spopadejo s to nalogo, se giblje do 43 % uspešno opravljenih. Praviloma vsako leto od 25 do 33 ljudi iz vseh 11. razredov opravlja enotni državni izpit iz računalništva.
Pred prihodom nalog z dvema vrstama variabilna metoda Učenci so zelo uspešno uporabljali preslikave, vendar sem po pojavu Y v logičnem izrazu začel opažati, da odgovori otrok ne sovpadajo več s testi. Izkazalo se je, da jim ni čisto jasno, kako ustvariti tabelo preslikav z novo vrsto spremenljivke. Potem se mi je porodila misel, da je treba zaradi priročnosti celoten izraz zmanjšati na eno vrsto spremenljivke, kot je primerno za otroke.
To tehniko bom podrobneje predstavil. Zaradi udobja ga bom obravnaval na primeru sistema logičnih izrazov, podanega v (4).
Koliko različnih rešitev ima sistem? logične enačbe
(x 1 ^ y 1)=(¬x 2 V ¬
l 2
)
(x 2 ^ y 2)= (¬
x 3
V ¬
l 3
)
...
(x 5 ^ y 5)
= (¬
x 6
V ¬
l 6
)
rešitev:
1. Iz analize sistema logičnih enačb vidimo, da obstaja 6 spremenljivk X in 6 spremenljivk U. Ker lahko katera koli od teh spremenljivk sprejme samo dve vrednosti (0 in 1), te spremenljivke nadomestimo z 12 spremenljivkami iste vrste, na primer Z.
2. Zdaj pa na novo napišimo sistem z novimi spremenljivkami istega tipa. Težavnost naloge bo skrbno beleženje pri zamenjavi spremenljivk.
(z 1 ^ z 2)=
(¬z 3V¬
z 4
)
(z 3 ^ z 4)=
(¬
z 5
V¬
z 6
)
...
(z 9 ^ z 10)
=
(¬
z 11
V¬
z 12)
3. Sestavimo tabelo, v kateri bomo pregledali vse možnosti z 1 , z 2 , z 3 , z 4 , ker so v prvi logični enačbi štiri spremenljivke, bo imela tabela 16 vrstic (16=2 4); odstranite takšne vrednosti iz tabele z 4 , za katero prva enačba nima rešitve (prečrtana števila).
| 0 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 |
4. Z analizo tabele zgradimo pravilo za prikaz parov spremenljivk (na primer par Z 1 Z 2 =00 ustreza par Z 3 Z 4 = 11) .
5. Izpolnite tabelo tako, da izračunate število parov spremenljivk, za katere ima sistem rešitev. 
6. Seštejte vse rezultate: 9 + 9 + 9 + 27 = 54
7. Odgovor: 54.
Zgornja optimizirana metodologija za reševanje problema 23 iz enotnega državnega izpita KIM je študentom omogočila, da so ponovno pridobili zaupanje in uspešno rešili to vrsto problema.
Literatura:
1. FIPI. Metodična priporočila za učitelje, pripravljeno na podlagi analize tipične napake udeleženci Enotnega državnega izpita 2015 iz INFORMACIJ in IKT. Način dostopa: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf
2. K.Yu. Polyakov, M.A. Roitberg.Sistemi logičnih enačb: rešitev z uporabo bitnih nizov. Revija za informatiko, številka 12, 2014, str. 4-12. Založba"Prvi september", Moskva.3. E.A. Mirončik, Način prikaza. Revija Informatika, številka 10, 2013, str. 18-26. Založba "Prvi september", Moskva.
Reševanje sistemov logičnih enačb s spreminjanjem spremenljivk
Metoda substitucije spremenljivk se uporablja, če so nekatere spremenljivke vključene v enačbe samo v obliki določenega izraza in nič drugega. Nato lahko ta izraz označimo z novo spremenljivko.
Primer 1.
Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, x6, x7, x8 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
(x1 → x2) → (x3 → x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk x1, x2, x3, x4, x5, x6, x7, x8, za katere je izpolnjen ta sistem enakosti. Kot odgovor morate navesti število takih nizov.
rešitev:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
Nato lahko sistem zapišemo v obliki ene enačbe:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Konjunkcija je 1 (true), ko ima vsak operand vrednost 1. To je vsaka od implikacij mora biti resnična in to velja za vse vrednosti razen (1 → 0). Tisti. v tabeli vrednosti spremenljivk y1, y2, y3, y4 ena ne sme biti levo od ničle:
Tisti. pogoji so izpolnjeni za 5 nizov y1-y4.
Ker y1 = x1 → x2, potem je vrednost y1 = 0 dosežena na enem nizu x1, x2: (1, 0), vrednost y1 = 1 pa na treh nizih x1, x2: (0,0) , (0 ,1), (1.1). Enako za y2, y3, y4.
Ker je vsak niz (x1,x2) za spremenljivko y1 kombiniran z vsakim nizom (x3,x4) za spremenljivko y2 itd., se števila nizov spremenljivk x pomnožijo:
|
Število nizov na x1…x8 |
||||
Seštejmo število nizov: 1 + 3 + 9 + 27 + 81 = 121.
odgovor: 121
Primer 2.
Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, ... x9, y1, y2, ... y9 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
V odgovor ni potrebe navedite vse različne nize vrednosti spremenljivk x1, x2, ... x9, y1, y2, ... y9, za katere ta sistem enako Kot odgovor morate navesti število takih nizov.
rešitev:
Spremenimo spremenljivke:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Sistem lahko zapišemo kot eno samo enačbo:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Enakovrednost velja samo, če sta oba operanda enaka. Obstajata dva niza rešitev te enačbe:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Ker zi = (xi ≡ yi), potem vrednost zi = 0 ustreza dvema nizoma (xi,yi): (0,1) in (1,0), vrednost zi = 1 pa dvema nizoma (xi,yi ): (0 ,0) in (1,1).
Potem prvi niz z1, z2,…, z9 ustreza 2 9 nizom (x1,y1), (x2,y2),…, (x9,y9).
Enako število ustreza drugemu nizu z1, z2,…, z9. Potem je skupaj 2 9 + 2 9 = 1024 nizov.
odgovor: 1024
Reševanje sistemov logičnih enačb z metodo vizualnega določanja rekurzije.
Ta metoda se uporablja, če je sistem enačb precej preprost in je vrstni red povečevanja števila nizov pri dodajanju spremenljivk očiten.
Primer 3.
Koliko različnih rešitev ima sistem enačb?
¬x9 ∨ x10 = 1,
kjer so x1, x2, … x10 logične spremenljivke?
Odgovoru ni treba navesti vseh različnih nizov vrednosti x1, x2, ... x10, za katere je ta sistem enakosti izpolnjen. Kot odgovor morate navesti število takih nizov.
rešitev:
Rešimo prvo enačbo. Disjunkcija je enaka 1, če je vsaj eden od njenih operandov enak 1. To je rešitve so sklopi:
Za x1=0 obstajata dve vrednosti x2 (0 in 1), za x1=1 pa samo ena vrednost x2 (1), tako da je množica (x1,x2) rešitev enačbe . Skupaj so 3 kompleti.
Dodajmo spremenljivko x3 in razmislimo o drugi enačbi. Podobno je prvemu, kar pomeni, da za x2=0 obstajata dve vrednosti x3 (0 in 1), za x2=1 pa samo ena vrednost x3 (1), tako da je množica (x2 ,x3) je rešitev enačbe. Skupaj so 4 kompleti.
Preprosto je videti, da se pri dodajanju druge spremenljivke doda en niz. Tisti. rekurzivna formula za število nizov (i+1) spremenljivk:
N i +1 = N i + 1. Potem za deset spremenljivk dobimo 11 nizov.
odgovor: 11
Reševanje sistemov logičnih enačb različnih vrst
Primer 4.
Koliko različnih nizov vrednosti logičnih spremenljivk x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 obstaja, ki izpolnjujejo vse spodaj navedene pogoje ?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
V odgovor ni potrebe naštejte vse različne nize vrednosti spremenljivk x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, za katere je ta sistem enakosti izpolnjen.
Kot odgovor morate navesti število takih nizov.
rešitev:
Upoštevajte, da so tri enačbe sistema enake na različnih neodvisnih nizih spremenljivk.
Poglejmo prvo enačbo. Konjunkcija je resnična (enaka 1) le, če so vsi njeni operandi resnični (enaki 1). Implikacija je 1 za vse tuple razen (1,0). To pomeni, da bodo rešitve prve enačbe naslednje množice x1, x2, x3, x4, v katerih 1 ni levo od 0 (5 skupin):
Podobno bosta rešitvi druge in tretje enačbe popolnoma enaki množici y1,…,y4 in z1,…, z4.
Zdaj pa analizirajmo četrto enačbo sistema: x 4 ∧ y 4 ∧ z 4 = 0. Rešitev bodo vse množice x4, y4, z4, v katerih je vsaj ena od spremenljivk enaka 0.
Tisti. za x4 = 0 so primerne vse možne množice (y4, z4), za x4 = 1 pa so primerne množice (y4, z4), v katerih je vsaj ena ničla: (0, 0), (0,1 ), (1, 0).
|
Število kompletov |
||||
Skupno število nizov je 25 + 4*9 = 25 + 36 = 61.
odgovor: 61
Reševanje sistemov logičnih enačb s konstruiranjem rekurentnih formul
Metoda konstruiranja ponavljajočih se formul se uporablja pri reševanju kompleksnih sistemov, v katerih vrstni red povečevanja števila nizov ni očiten, konstrukcija drevesa pa je nemogoča zaradi volumnov.
Primer 5.
Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, ... x7, y1, y2, ... y7 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk x1, x2, ..., x7, y1, y2, ..., y7, za katere je izpolnjen ta sistem enakosti. Kot odgovor morate navesti število takih nizov.
rešitev:
Upoštevajte, da je prvih šest enačb sistema enakih in se razlikujejo le v nizu spremenljivk. Poglejmo prvo enačbo. Njegova rešitev bodo naslednji nizi spremenljivk:
Označimo:
število tupl (0,0) na spremenljivkah (x1,y1) do A 1,
število tuplov (0,1) na spremenljivkah (x1,y1) do B 1,
število tuplov (1,0) na spremenljivkah (x1,y1) do C 1,
število tupl (1,1) na spremenljivkah (x1,y1) do D 1 .
število tuplov (0,0) na spremenljivkah (x2,y2) do A 2,
število tulp (0,1) na spremenljivkah (x2,y2) do B 2,
število tuplov (1,0) na spremenljivkah (x2,y2) do C 2,
število tork (1,1) na spremenljivkah (x2,y2) do D 2 .
To vidimo iz odločitvenega drevesa
A 1 =0, B 1 =1, C 1 =1, D 1 =1.
Upoštevajte, da je množica (0,0) spremenljivk (x2,y2) pridobljena iz množic (0,1), (1,0) in (1,1) spremenljivk (x1,y1). Tisti. A 2 =B 1 +C 1 +D 1.
Množico (0,1) na spremenljivkah (x2,y2) dobimo iz množic (0,1), (1,0) in (1,1) na spremenljivkah (x1,y1). Tisti. B 2 =B 1 +C 1 +D 1.
Če trdimo podobno, opazimo, da je C 2 =B 1 +C 1 +D 1. D2 = D1.
Tako dobimo ponavljajoče se formule:
A i+1 = B i + C i + D i
B i+1 = B i + C i + D i
C i+1 = B i + C i + D i
D i+1 = A i +B i + C i + D i
Naredimo mizo
| Kompleti | Imenovanje. | Formula |
Število kompletov |
||||||
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
| (0,0) | A i | A i+1 =B i +C i +D i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B i | B i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C i | C i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D i | D i+1 =D i | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Zadnjo enačbo (x7 ∨ y7) = 1 izpolnjujejo vse množice, razen tistih, v katerih je x7=0 in y7=0. V naši tabeli je število takih nizov A 7.
Potem je skupno število nizov B 7 + C 7 + D 7 = 127+127+1 = 255
odgovor: 255
Občinska proračunska izobraževalna ustanova
"Povprečje srednja šolašt. 18"
mestno okrožje mesta Salavat v Republiki Baškortostan
Sistemi logičnih enačb
pri problemih enotnega državnega izpita iz računalništva
Oddelek "Osnove logične algebre" v Naloge enotnega državnega izpita velja za enega najtežjih in slabo rešenih. Povprečni odstotek opravljenih nalog na to temo je najnižji in znaša 43,2.
| Odsek tečaja | Povprečni odstotek dokončanja po skupinah nalog |
| Kodiranje informacij in merjenje njihove količine | |
| Informacijsko modeliranje | |
| Številski sistemi | |
| Osnove logične algebre | |
| Algoritmizacija in programiranje | |
| Osnove informacijskih in komunikacijskih tehnologij |
Na podlagi specifikacije CMM iz leta 2018 ta blok vključuje štiri naloge različne ravni kompleksnost.
| № naloge | Preverljivo vsebinskih elementov | Stopnja težavnosti naloge |
| Sposobnost konstruiranja tabel resnic in logičnih vezij | ||
| Sposobnost iskanja informacij na internetu | ||
| Poznavanje osnovnih pojmov in zakonitosti matematična logika | ||
| Sposobnost konstruiranja in preoblikovanja logičnih izrazov |
Naloga 23 ima visoko težavnostno stopnjo, zato ima najnižji odstotek dokončanja. Med pripravljenimi maturanti (81-100 točk) jih je opravilo 49,8 % srednje pripravljenih maturantov (61-80 točk) 13,7 % študentov, ki te naloge niso opravili.
Uspešnost reševanja sistema logičnih enačb je odvisna od poznavanja zakonitosti logike in od natančne uporabe metod za reševanje sistema.
Razmislimo o reševanju sistema logičnih enačb z metodo preslikave.
(23.154 Polyakov K.Yu.) Koliko različnih rešitev ima sistem enačb?
((x1 l1 ) (x2 l2 )) (x1 x2 ) (l1 l2 ) =1
((x2 l2 ) (x3 l3 )) (x2 x3 ) (l2 l3 ) =1
((x7 l7 ) (x8 l8 )) (x7 x8 ) (l7 l8 ) =1
kje x1 , x2 ,…, x8, pri1 ,y2 ,…,y8 - logične spremenljivke? Odgovoru ni treba navesti vseh različnih nizov vrednosti spremenljivk, za katere velja ta enakost. Kot odgovor morate navesti število takih nizov.
rešitev. Vse enačbe, vključene v sistem, so istega tipa in vsaka enačba vključuje štiri spremenljivke. Če poznamo x1 in y1, lahko najdemo vse možne vrednosti x2 in y2, ki ustrezajo prvi enačbi. Če sklepamo na podoben način, lahko iz znanih x2 in y2 najdemo x3, y3, ki izpolnjujeta drugo enačbo. To pomeni, da poznamo par (x1, y1) in določimo vrednost para (x2, y2), bomo našli par (x3, y3), kar bo posledično vodilo do para (x4, y4) in tako naprej.
Poiščimo vse rešitve prve enačbe. To je mogoče storiti na dva načina: zgraditi tabelo resnic z razmišljanjem in uporabo zakonov logike.
Tabela resnice:
| x 1 y 1 | x 2 y 2 | (x 1 y 1) (x2 y2) | (x 1 x2) | (y 1 y2) | (x 1 x2) (y 1 y2) | |||||
Izdelava tabele resnic je delovno intenzivna in časovno neučinkovita, zato uporabljamo drugo metodo - logično sklepanje. Produkt je enak 1, če in samo če je vsak faktor enak 1.
(x1 l1 ) (x2 l2 ))=1
(x1 x2 ) =1
(l1 l2 ) =1
Poglejmo prvo enačbo. Posledica je enaka 1, ko je 0 0, 0 1, 1 1, kar pomeni (x1 y1)=0 za (01), (10), potem je par (x2 l2 ) je lahko kateri koli (00), (01), (10), (11) in ko je (x1 y1) = 1, to je (00) in (11), par (x2 y2) = 1 prevzame enake vrednosti (00) in (11). Iz te rešitve izločimo tiste pare, pri katerih sta druga in tretja enačba napačni, to je x1=1, x2=0, y1=1, y2=0.
| (x1 , l1 ) | (x2 , l2 ) |
Skupno število parov 1+1+1+22= 25
2) (23.160 Polyakov K.Yu.) Koliko različnih rešitev ima sistem logičnih enačb?
(x 1 (x 2 l 2 )) (l 1 l 2 ) = 1
(x 2 (x 3 l 3 )) (l 2 l 3 ) = 1
...
( x 6 ( x 7 l 7 )) ( l 6 l 7 ) = 1
x 7 l 7 = 1
rešitev. 1) Enačbe so istega tipa, zato bomo s sklepanjem našli vse možne pare (x1,y1), (x2,y2) prve enačbe.
(x1 (x2 l2 ))=1
(l1 l2 ) = 1
Rešitev druge enačbe so pari (00), (01), (11).
Poiščimo rešitve prve enačbe. Če x1=0, potem x2, y2 - poljubno, če x1=1, potem x2, y2 prevzame vrednost (11).
Povežimo para (x1, y1) in (x2, y2).
| (x1 , l1 ) | (x2 , l2 ) |
Ustvarimo tabelo za izračun števila parov na vsaki stopnji.
| 0 |
|||||||
Ob upoštevanju rešitev zadnje enačbe x 7 l 7 = 1, izločimo par (10). Najdemo skupno število rešitve 1+7+0+34=42
3)(23.180) Koliko različnih rešitev ima sistem logičnih enačb?
(x1 x2 ) (x3 x4 ) = 1
(x3 x4 ) (x5 x6 ) = 1
(x5 x6 ) (x7 x8 ) = 1
(x7 x8 ) (x9 x10 ) = 1
x1 x3 x5 x7 x9 = 1
rešitev. 1) Enačbe so istega tipa, zato bomo s sklepanjem našli vse možne pare (x1,x2), (x3,x4) prve enačbe.
(x1 x2 ) (x3 x4 ) = 1
Iz rešitve izločimo pare, ki v zaporedju dajejo 0 (1 0), to so pari (01, 00, 11) in (10).
Povežimo pare (x1,x2), (x3,x4)
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". torej polno drevo Celoten sistem 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 načinom razmišljanja zgradimo drevo rešitev za vse enačbe:
Tako ima sistem enačb le 2 rešitvi.
Odgovor: 2.
Primer 3.
Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1
(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1
(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1
(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1
(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1
rešitev:
Zgradimo drevo rešitev za 1. enačbo:
Razmislite o drugi enačbi:
- Ko je x1=0 : drugi in tretji oklepaj bosta enaka 0; da je prvi oklepaj enak 1, y1=1, z1=1 (tj. v tem primeru - 1 rešitev)
- Ko je x1=1 : prvi oklepaj bo enak 0; drugo oz tretji oklepaj mora biti enak 1; drugi oklepaj bo enak 1, ko je y1=0 in z1=1; tretji oklepaj bo enak 1, ko je y1=1 in z1=0 (tj. v tem primeru - 2 rešitvi).
Podobno velja za preostale enačbe. Zabeležimo nastalo število rešitev za vsako vozlišče drevesa:
Če želite izvedeti število rešitev za vsako vejo, pomnožite dobljena števila posebej za vsako vejo (od leve proti desni).
1 veja: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 rešitev
Veja 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 rešitvi
3. veja: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 rešitve
4. veja: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 rešitev
5. veja: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 rešitev
Seštejmo dobljena števila: skupaj je 31 rešitev.
Odgovor: 31.
3. Naravni prirast števila korenin
V nekaterih sistemih je število korenov naslednje enačbe odvisno od števila korenov prejšnje enačbe.
Primer 1. Koliko različnih nizov vrednosti logičnih spremenljivk x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 obstaja, ki izpolnjujejo vse spodaj navedene pogoje?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Poenostavimo prva enačba:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Nato bo sistem dobil obliko:
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0
¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0
¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0
itd.
Vsaka naslednja enačba ima 2 korena več kot prejšnja.
4 enačba ima 12 korenin;
Enačba 5 ima 14 korenin
Enačba 8 ima 20 korenin.
Odgovor: 20 korenin.
Včasih število korenin raste po Fibonaccijevem zakonu.
Reševanje sistema logičnih enačb zahteva kreativen pristop.
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, kjer so J, K, L, M, N logične spremenljivke?
Razlaga.
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.
Razlaga.
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.
Razlaga.
Prepišimo enačbo z enostavnejšim zapisom operacij:
((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
Razlaga.
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.
Razlaga.
(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.
Razlaga.
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.
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.
Razlaga.
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 vsak 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.
Razlaga.
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?
Razlaga.
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 nastalo binarno predstavitev vrednosti funkcije X v decimalni številski sistem.
Razlaga.
Zapišimo enačbo z enostavnejšim zapisom za operacije:
1) to je izraz s tremi spremenljivkami, zato bodo v tabeli resnic vrstice; 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 | X|
| 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))?
Razlaga.
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 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))?
Razlaga.
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.
Razlaga.
Podvaja nalogo 3584.
Odgovor: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Razlaga.
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.
Razlaga.
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čno.
Odgovor zapišite kot niz štirih znakov: vrednosti spremenljivk P, Q, S, T (v tem vrstnem redu).
Razlaga.
(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.
Razlaga.
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.
Razlaga.
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?
Razlaga.
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?
Razlaga.
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?
Razlaga.
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?
Razlaga.
Logični "IN" je resničen samo, če so vse izjave resnične.