Metoda preslikave za reševanje sistemov logičnih enačb. Logike

Uporaba enačb je v našem življenju zelo razširjena. Uporabljajo se pri številnih izračunih, gradnji konstrukcij in celo športu. Človek je enačbe uporabljal že v pradavnini, od takrat pa se je njihova uporaba le še povečala. V matematiki obstajajo določeni problemi, ki se ukvarjajo s propozicionalno logiko. Če želite rešiti tovrstno enačbo, morate imeti določeno mero znanja: poznavanje zakonov propozicionalne logike, poznavanje tabel resničnosti logičnih funkcij 1 ali 2 spremenljivk, metode za pretvorbo logičnih izrazov. Poleg tega morate poznati naslednje lastnosti logičnih operacij: konjunkcija, disjunkcija, inverzija, implikacija in ekvivalenca.

Vsako logično funkcijo \variables - \lahko določite s tabelo resnic.

Rešimo več logičnih enačb:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Začnimo rešitev z \[X1\] in določimo, katere vrednosti lahko sprejme ta spremenljivka: 0 in 1. Nato bomo preučili vsako od zgornjih vrednosti in videli, kaj je lahko \[X2.\].

Kot je razvidno iz tabele, ima naša logična enačba 11 rešitev.

Kje lahko na spletu rešim logično enačbo?

Enačbo lahko rešite na naši spletni strani https://site. Brezplačni spletni reševalec vam bo omogočil reševanje spletnih enačb katere koli zahtevnosti v nekaj sekundah. Vse kar morate storiti je, da preprosto vnesete svoje podatke v reševalec. Ogledate si lahko tudi video navodila in se naučite reševati enačbo na naši spletni strani. In če imate še vedno vprašanja, jih lahko postavite v naši skupini VKontakte http://vk.com/pocketteacher. Pridružite se naši skupini, vedno vam z veseljem pomagamo.

Metode reševanja sistemov logičnih enačb

Kirgizova E.V., Nemkova A.E.

Lesosibirsk pedagoški inštitut –

podružnica Sibirske zvezne univerze, Rusija

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

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

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

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

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

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

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

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

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

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

Rešitev 2:Ustvarimo tabelo resnic za sistem:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Podani sistem enačb je enakovreden enačbi:

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

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

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

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

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

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

Prepišimo sistem enačb v obliki:

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

Ustvarimo tabelo resnic za dve enačbi:

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

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

Literatura:

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

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

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.
Situacijo otežuje tudi to, da je v tem bloku veliko različnih nalog in ni mogoče izbrati nobene predloge rešitve.
Da bi popravili to situacijo, pedagoška skupnost dokončuje dve glavni metodi za reševanje tovrstnih problemov: reševanje z uporabo bitnih verig (2) in metodo 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. Polyakov, obstaja 38 analiz te vrste problema (4). Nekatere analize nudijo več kot eno rešitev problema.
Pred kratkim so se na enotnem državnem izpitu KIM iz računalništva pojavile 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.
Preden so se pojavile težave z dvema vrstama spremenljivk, so učenci zelo uspešno uporabljali metodo preslikave, po pojavu Y v logičnem izrazu pa sem 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čnih enačb?

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

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

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 metoda 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. Metodološka priporočila za učitelje, pripravljena na podlagi analize tipičnih napak udeležencev 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

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

Lekcija #3. Logike. Logične funkcije. Reševanje enačb

Veliko število problemov enotnega državnega izpita je posvečenih propozicionalni logiki. Za rešitev večine je dovolj poznavanje osnovnih zakonov propozicijske logike, poznavanje resničnostnih tabel logičnih funkcij ene in dveh spremenljivk. Podal bom osnovne zakone propozicijske logike.

1. Komutativnost disjunkcije in konjunkcije:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Distributivni zakon glede disjunkcije in konjunkcije:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negacija negacije:
   ¬(¬a) ≡ a
4. Konsistentnost:
   a ^ ¬а ≡ napačno
5. Ekskluzivno tretje:
   a ˅ ¬а ≡ res
6. De Morganovi zakoni:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Poenostavitev:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ res ≡ a
   a ˄ false ≡ false
8. Absorpcija:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Zamenjava implikacije
   a → b ≡ ¬a ˅ b
10. Zamenjava identitete
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Predstavitev logičnih funkcij

Vsako logično funkcijo n spremenljivk - F(x 1, x 2, ... x n) je mogoče podati s tabelo resnic. Takšna tabela vsebuje 2n nizov spremenljivk, za vsako izmed njih je podana vrednost funkcije na tem nizu. Ta metoda je dobra, kadar je število spremenljivk relativno majhno. Že pri n > 5 postane reprezentacija slabo vidna.

Drugi način je definiranje funkcije z neko formulo z uporabo znanih precej 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, ki prikazujeta, kako se implikacija in identiteta izražata z zanikanjem, konjunkcijo in disjunkcijo.

Pravzaprav je popoln tudi sistem dveh funkcij – negacije in konjunkcije oziroma negacije in disjunkcije. Iz De Morganovih zakonov sledijo ideje, ki omogočajo izražanje konjunkcije z negacijo in disjunkcijo in v skladu s tem izražanje disjunkcije z negacijo in konjunkcijo:

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

Paradoksalno je, da je sistem, sestavljen iz samo ene funkcije, popoln. Obstajata dve binarni funkciji - antikonjunkcija in antidisjunkcija, imenovani Peirceova puščica in Schaefferjeva poteza, ki predstavljata votel sistem.

Osnovne funkcije programskih jezikov običajno vključujejo identiteto, negacijo, konjunkcijo in disjunkcijo. Pri težavah z enotnim državnim izpitom se poleg teh funkcij pogosto najdejo posledice.

Oglejmo si nekaj preprostih problemov, ki vključujejo logične funkcije.

Problem 15:

Podan je delček tabele resnic. Katera od treh navedenih funkcij ustreza temu fragmentu?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ 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) višjo prioriteto in se izvede prej kot disjunkcija (logično seštevanje). Med izračuni lahko opazimo, da imata funkciji s številkama 1 in 2 v tretjem nizu vrednost 1 in zaradi tega ne ustrezata fragmentu.

Problem 16:

Katero od danih števil izpolnjuje pogoj:

(števke, začenši z najpomembnejšo števko, so v padajočem vrstnem redu) → (število - sodo) ˄ (nižja števka - sodo) ˄ (višja števka - liho)

Če je takšnih števil več, navedite največje.

1. 13579
2. 97531
3. 24678
4. 15386

Pogoj je izpolnjen s številko 4.

Prvi dve številki ne izpolnjujeta pogoja, ker je najnižja številka liha. Konjunkcija pogojev je napačna, če je eden od členov konjunkcije napačen. Za tretje število pogoj za najvišjo števko ni izpolnjen. Za četrto številko so izpolnjeni pogoji za nizko in visoko števko številke. Pravi je tudi prvi člen konjunkcije, saj je implikacija resnična, če je njena premisa napačna, kar je v tem primeru.

Problem 17: Dve priči sta povedali naslednje:

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

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

Kakšne sklepe o krivdi A, B in C je mogoče potegniti iz pričevanja?

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

Rešitev: Seveda je odgovor mogoče dati na podlagi zdrave pameti. Toda poglejmo, kako je to mogoče storiti strogo in formalno.

Prva stvar, ki jo je treba storiti, je formalizacija izjav. Vstavimo tri logične spremenljivke - A, B in C, od katerih ima vsaka vrednost true (1), če je ustrezni osumljenec kriv. Nato je pričanje prve priče podano s formulo:

A → (B ˄ ¬C)

Pričanje druge priče je podano s formulo:

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

Izpovedi obeh prič se predpostavljajo kot resnične in predstavljajo konjunkcijo ustreznih formul.

Izdelajmo tabelo resnic za te odčitke:

Povzetek dokazov je resničen samo v enem primeru, kar vodi do jasnega odgovora - A in B sta kriva, C pa je nedolžen.

Iz analize te tabele tudi izhaja, da je pričanje druge priče bolj informativno. Iz resničnosti njegovega pričanja izhajata le dve možni možnosti - A in B sta kriva, C pa je nedolžen ali pa sta A in C kriva, B pa nedolžen. Pričanje prve priče je manj informativno - obstaja 5 različnih možnosti, ki ustrezajo njegovemu pričanju. Izpovedi obeh prič skupaj dajejo jasen 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 izgleda takole:

F(x 1, x 2, …x n) = C,

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

F(x 1, x 2, …x n) = 1

Res, naj bo dana enačba:

F(x 1, x 2, …x n) = 0

V tem primeru lahko preidemo na ekvivalentno enačbo:

¬F(x 1, x 2, …x n) = 1

Razmislite o sistemu k logičnih enačb:

F 1 (x 1, x 2, …x n) = 1

F 2 (x 1, x 2, …x n) = 1

F k (x 1, x 2, …x n) = 1

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

Ф = F 1 ˄ F 2 ˄ … F k

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

Pri nekaterih nalogah USE pri iskanju rešitev 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 ne obstaja nobena splošna metoda razen številčenja, ki omogoča reševanje takšnih problemov.

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. Druga uporabna tehnika za reševanje te težave je naslednja. Ne zanimajo nas vse množice, temveč samo tiste, na katerih ima funkcija Ф vrednost 1. Namesto da bi zgradili popolno tabelo resnic, bomo zgradili njen analog - binarno odločitveno drevo. 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 - x 1, x 2, ...x 5. 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 obratno: konjunkcijo pogojev lahko obravnavamo kot sistem enačb.

Zgradimo odločitveno drevo za implikacijo (x1→ x2) - prvi člen konjunkcije, ki ga lahko obravnavamo kot prvo enačbo. Tako izgleda grafični prikaz tega drevesa:

Drevo je sestavljeno iz dveh ravni glede na število spremenljivk v enačbi. Prva raven opisuje prvo spremenljivko X 1 . 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 X 2, za katere je enačba resnična. Ker enačba podaja implikacijo, veja, na kateri ima X 1 vrednost 1, zahteva, da ima na tej veji X 2 vrednost 1. Veja, na kateri ima X 1 vrednost 0, ustvari dve veji z vrednostmi X 2 enako 0 in 1. Konstruirano drevo določa tri rešitve, na katerih ima implikacija X 1 → X 2 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 implikacije X 2 → X 3 . 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 X 2 že vrednosti v drevesu, bo imela na vseh vejah, kjer ima spremenljivka X 2 vrednost 1, tudi spremenljivka X 3 vrednost 1. Za takšne veje je konstrukcija drevesa nadaljuje na naslednjo stopnjo, vendar se nove veje ne pojavijo. Ena veja, kjer ima spremenljivka X 2 vrednost 0, se bo razvejala v dve veji, kjer bo spremenljivka X 3 prejela vrednosti 0 in 1. Tako vsak dodatek nove enačbe glede na njene posebnosti doda eno rešitev. Izvirna prva enačba:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
ima 6 rešitev. Tukaj je videti celotno drevo odločitev za to enačbo:

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

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

Edina razlika je v tem, da enačba uporablja spremenljivke Y. Ta enačba ima tudi 6 rešitev. Ker lahko vsako rešitev za spremenljivke X i kombiniramo z vsako rešitvijo za spremenljivke Y j, je skupno število rešitev 36.

Upoštevajte, da sestavljeno odločitveno drevo ne poda le števila rešitev (glede na število vej), temveč 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?

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

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 X 1 → Y 1 sledi, da kadar ima X 1 vrednost 1 (ena takšna rešitev obstaja), ima tudi Y 1 vrednost 1. Tako obstaja ena množica, na kateri imata X 1 in Y 1 vrednosti ​​1. Ko je X 1 enak 0, ima lahko Y 1 poljubno vrednost, tako 0 kot 1. Zato vsak niz z X 1 enakim 0 in obstaja 5 takih nizov, ustreza vsem 6 nizom s spremenljivkami Y. Zato je skupno število rešitev 31 .

Problem 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Rešitev: Ob upoštevanju osnovnih enakovrednosti 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) = 1

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

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

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

Problem 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

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

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Zgradimo drevo odločitev za to enačbo:

Problem 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)) = 0

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

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

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

Odgovor: 64

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

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Potem bo prva enačba dobila obliko:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

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

(Y 1 ≡ Y 2) = 0

Če preidemo na tradicionalno obliko, sistem po poenostavitvah zapišemo v obliki:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Odločitveno drevo za ta sistem je preprosto in je sestavljeno iz dveh vej z izmenjujočimi se vrednostmi spremenljivk:

Če se vrnemo k izvirnim spremenljivkam X, upoštevajte, da za vsako vrednost v spremenljivki Y obstajata 2 vrednosti v spremenljivkah X, tako da vsaka rešitev v spremenljivkah Y ustvari 2 5 rešitev v spremenljivkah X. Dve veji ustvarita 2 * 2 5 rešitev, torej je skupno število rešitev 64.

Kot lahko vidite, vsak problem reševanja sistema enačb zahteva svoj pristop. Običajna tehnika je izvajanje enakovrednih transformacij za poenostavitev enačb. Pogosta tehnika je izdelava odločitvenih dreves. Uporabljeni pristop delno spominja na sestavo tabele resnic s to posebnostjo, da niso konstruirane vse množice možnih vrednosti spremenljivk, temveč samo tiste, na katerih funkcija prevzame vrednost 1 (true). Pogosto v predlaganih problemih ni treba zgraditi celotnega odločitvenega drevesa, saj je že na začetni stopnji mogoče vzpostaviti vzorec pojavljanja novih vej na vsaki naslednji ravni, kot je bilo storjeno na primer v problemu 18 .

Na splošno so težave, ki vključujejo iskanje rešitev sistema logičnih enačb, dobre matematične vaje.

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

Takega programa ni težko napisati. Takšen program se bo zlahka spopadel z vsemi nalogami, ki jih ponuja enotni državni izpit.

Nenavadno je, da je naloga iskanja rešitev sistemov logičnih enačb za računalnik težka in izkaže se, da ima računalnik svoje meje. Računalnik se zlahka spopade s problemi, kjer je število spremenljivk 20-30, vendar bo začel dolgo razmišljati o večjih problemih. Dejstvo je, da je funkcija 2 n, ki določa število nizov, eksponenta, ki hitro raste z naraščanjem n. Tako hitro, da navaden osebni računalnik ni kos nalogi, ki ima 40 spremenljivk na dan.

Program v jeziku C# za reševanje logičnih enačb

Pisanje programa za reševanje logičnih enačb je koristno iz več razlogov, četudi samo zato, ker lahko z njim preverite pravilnost lastne rešitve testnih nalog enotnega državnega izpita. Drugi razlog je, da je tak program odličen primer programske naloge, ki izpolnjuje zahteve za naloge kategorije C na enotnem državnem izpitu.

Zamisel o izdelavi programa je preprosta - temelji na popolnem iskanju vseh možnih nizov vrednosti spremenljivk. 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 je treba razvrstiti. Z uporabo osnovnih funkcij jezika C# - negacije, disjunkcije, konjunkcije in identitete, ni težko napisati programa, ki za dano množico spremenljivk izračuna vrednost logične funkcije, ki ustreza logični enačbi ali sistemu enačb. .

V takem programu morate zgraditi zanko na podlagi števila nizov, v telesu zanke z uporabo številke niza oblikovati sam niz, izračunati vrednost funkcije na tem nizu in če ta vrednost 1, potem niz daje rešitev enačbe.

Edina težava, ki se pojavi pri izvajanju programa, je povezana z nalogo generiranja samega nabora vrednosti spremenljivk na podlagi nastavljenega števila. Lepota te težave je v tem, da se ta navidezno težka naloga dejansko skrči na preprost problem, ki se je pojavil že večkrat. Dejansko je dovolj razumeti, da nabor vrednosti spremenljivk, ki ustreza številu i, sestavljen iz ničel in enic, predstavlja binarno predstavitev števila i. Tako se zapletena naloga pridobivanja nabora vrednosti spremenljivk z nastavljenim številom zmanjša na znano nalogo pretvorbe števila v dvojiško.

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

///

///

/// logična funkcija - metoda,

/// katerega podpis določi delegat DF

///

/// število spremenljivk

/// število rešitev

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

bool set = nov bool[n];

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

int p = 0, q = 0, k = 0;

//Dokončaj iskanje po številu nizov

za (int i = 0; i< m; i++)

//Oblikovanje naslednjega sklopa - niz,

//določeno z dvojiško predstavitvijo števila i

za (int j = 0; j< n; j++)

k = (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 zadostni. Osredotočil se bom samo na razlago naslova dane funkcije. Funkcija SolveEquations ima dva vhodna parametra. Zabavni parameter podaja logično funkcijo, ki ustreza enačbi ali sistemu enačb, ki se rešuje. Parameter n določa število zabavnih spremenljivk. Posledično funkcija SolveEquations vrne število rešitev logične funkcije, to je število tistih nizov, na katerih funkcija oceni vrednost true.

Za šolarje je običajno, da ima neka funkcija F(x) vhodni parameter x, ki je spremenljivka aritmetičnega, nizovnega ali logičnega tipa. V našem primeru je uporabljena močnejša zasnova. Funkcija SolveEquations se nanaša na funkcije višjega reda - funkcije tipa F(f), katerih parametri so lahko ne le preproste spremenljivke, ampak tudi funkcije.

Razred funkcij, ki jih je mogoče posredovati kot parameter funkciji SolveEquations, je določen na naslednji način:

delegat bool DF(bool vars);

Ta razred ima v lasti vse funkcije, ki so kot parameter posredovane naboru vrednosti logičnih spremenljivk, ki jih določa matrika vars. Rezultat je logična vrednost, ki predstavlja vrednost funkcije v tem nizu.

Končno je tukaj program, ki uporablja funkcijo SolveEquations za reševanje več sistemov logičnih enačb. Funkcija SolveEquations je del spodnjega razreda ProgramCommon:

razred ProgramCommon

delegat bool DF(bool vars);

statična praznina Main(string args)

Console.WriteLine("In funkcije - " +

Reši enačbe (FunAnd, 2));

Console.WriteLine("Funkcija ima 51 rešitev - " +

Reši enačbe (Zabava51, 5));

Console.WriteLine("Funkcija ima 53 rešitev - " +

Reši enačbe (Zabava53, 10));

statični bool FunAnd(bool vars)

vrni vars && vars;

statični bool Fun51 (bool vars)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

statični bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Takole so videti rezultati rešitve za ta program:

10 nalog za samostojno delo

1. Katere od treh funkcij so enakovredne:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Podan je delček tabele resnic:

Kateri od treh funkcij ustreza ta fragment:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Žirijo sestavljajo tri osebe. Odločitev je sprejeta, če zanjo glasuje predsednik žirije, ki ga podpira vsaj eden od članov žirije. V nasprotnem primeru se odločitev ne sprejme. Konstruirajte logično funkcijo, ki formalizira proces odločanja.
5. X zmaga nad Y, če se štirje meti kovancev trikrat končajo z glavo. Definirajte logično funkcijo, ki opisuje izplačilo X.
6. Besede v stavku so oštevilčene od ena. Šteje se, da je stavek pravilno sestavljen, če so izpolnjena naslednja pravila:
   1. Če se soda beseda konča z samoglasnikom, se mora naslednja beseda, če obstaja, začeti s samoglasnikom.
   2. Če se liha beseda konča s soglasnikom, se mora naslednja beseda, če obstaja, začeti s soglasnikom in končati z samoglasnikom.
      Kateri od naslednjih stavkov je pravilno sestavljen:
   3. Mama je umila Mašo z milom.
   4. Vodja je vedno vzor.
   5. Resnica je dobra, a sreča je boljša.
7. Koliko rešitev ima enačba:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Naštej vse rešitve enačbe:
   (a → b) → c = 0
9. Koliko rešitev ima naslednji sistem enačb:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Koliko rešitev ima enačba:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Odgovori na težave:

1. Funkciji b in c sta enakovredni.
2. Fragment ustreza funkciji b.
3. Naj logična spremenljivka P zavzame vrednost 1, ko predsednik žirije glasuje »za« odločitev. Spremenljivki M 1 in M ​​2 predstavljata mnenja članov žirije. Logično funkcijo, ki določa sprejetje pozitivne odločitve, lahko zapišemo na naslednji način:
   P ˄ (M 1 ˅ M 2)
4. Naj ima logična spremenljivka P i vrednost 1, ko i-ti met kovanca pristane na glavi. Logično funkcijo, ki podaja 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))
5. stavek b.
6. Enačba ima 3 rešitve: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

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, velja druga enakost 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 enačba daje 3 rešitve.

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

Zato je odgovor 9.

Odgovor: 9

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

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

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

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

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

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

4) izpolnite stolpce tabele:

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

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

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

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

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

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

6) pretvorite to število v decimalni sistem:

Odgovor: 171

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

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 (ne želim ...);

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

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

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

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

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

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

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

9) področje resnice izraza je zaprt interval;

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

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

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

Torej je odgovor 2.

Odgovor: 2

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

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

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

Pretvorimo:

(¬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 "implikacije" sledi, da je ta izraz napačen, če in samo, če hkrati

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

4) iz drugega pogoja, , za in dobimo .

Podvaja nalogo

Odgovor: 1000

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

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

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 ∨ Т)) = 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))

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

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 le, če so vse izjave resnične.