Sistemet e ekuacioneve logjike. Logjikat. Funksionet logjike. Zgjidhja e ekuacioneve

Detyrë shërbimi. Llogaritësi në internet është krijuar për ndërtimi i një tabele të së vërtetës për një shprehje logjike.
Tabela e së vërtetës - një tabelë që përmban të gjitha kombinimet e mundshme të variablave hyrëse dhe vlerat e tyre përkatëse të daljes.
Tabela e së vërtetës përmban 2n rreshta, ku n është numri i variablave hyrëse dhe n+m janë kolona, ​​ku m janë variablat e daljes.

Udhëzim. Kur hyni nga tastiera, përdorni konventat e mëposhtme:

shprehje boolean:

Prodhimi i tabelave të ndërmjetme për tabelën e së vërtetës
Ndërtimi i SKNF
Ndërtimi i SDNF
Ndërtimi i polinomit Zhegalkin
Ndërtimi i hartës Veitch-Carnot
Minimizimi i funksionit Boolean
Për shembull, shprehja logjike abc+ab~c+a~bc duhet të futet kështu: a*b*c+a*b=c+a=b*c
Për të futur të dhëna në formën e një diagrami logjik, përdorni këtë shërbim.

Rregullat e hyrjes së funksionit logjik

  1. Përdorni shenjën + në vend të v (ndarje, OSE).
  2. Përpara funksionit logjik, nuk keni nevojë të specifikoni përcaktimin e funksionit. Për shembull, në vend të F(x,y)=(x|y)=(x^y) thjesht do të shkruani (x|y)=(x^y) .
  3. Shuma maksimale variablat është 10.

Dizajni dhe analiza e qarqeve logjike kompjuterike kryhet me ndihmën e një seksioni të veçantë të matematikës - algjebrës së logjikës. Në algjebrën e logjikës, mund të dallohen tre funksione kryesore logjike: "JO" (negacion), "DHE" (lidhëz), "OR" (ndarje).
Për të krijuar ndonjë pajisje logjike, është e nevojshme të përcaktohet varësia e secilës prej variablave të daljes nga variablat e hyrjes aktuale, një varësi e tillë quhet një funksion komutues ose një funksion i algjebrës logjike.
Një funksion algjebër logjik quhet plotësisht i përcaktuar nëse jepen të gjitha 2 n vlerat e tij, ku n është numri i ndryshoreve dalëse.
Nëse jo të gjitha vlerat janë përcaktuar, funksioni quhet pjesërisht i përcaktuar.
Një pajisje quhet logjike nëse gjendja e saj përshkruhet duke përdorur një funksion të algjebrës së logjikës.
Metodat e mëposhtme përdoren për të përfaqësuar funksionin e algjebrës logjike:
Në formën algjebrike, është e mundur të ndërtohet një diagram i një pajisjeje logjike duke përdorur elementë logjikë.


Figura 1 - Diagrami i një pajisjeje logjike

Të gjitha veprimet e algjebrës së logjikës janë të përcaktuara tabelat e së vërtetës vlerat. Tabela e së vërtetës përcakton rezultatin e kryerjes së një operacioni për të gjitha të mundshme x vlerat logjike të deklaratave origjinale. Numri i opsioneve që pasqyrojnë rezultatin e zbatimit të operacioneve do të varet nga numri i deklaratave në shprehjen logjike. Nëse numri i pohimeve në shprehjen logjike është N, atëherë tabela e së vërtetës do të përmbajë 2 N rreshta, pasi ka 2 N kombinime të ndryshme të vlerave të mundshme të argumentit.

Operacioni NOT - mohim logjik (inversion)

Operacioni logjik NUK zbatohet për një argument të vetëm, i cili mund të jetë ose një shprehje logjike e thjeshtë ose komplekse. Rezultati i operacionit NUK është si më poshtë:
  • nëse shprehja origjinale është e vërtetë, atëherë rezultati i mohimit të saj do të jetë i rremë;
  • nëse shprehja origjinale është e rreme, atëherë rezultati i mohimit të saj do të jetë i vërtetë.
Konventat e mëposhtme NUK pranohen për operacionin e mohimit:
jo A, Ā, jo A, ¬A, !A
Rezultati i operacionit të mohimit NUK përcaktohet nga tabela e mëposhtme e së vërtetës:
Ajo A
0 1
1 0

Rezultati i operacionit të mohimit është i vërtetë kur deklarata origjinale është e rreme, dhe anasjelltas.

Operacioni OSE - shtesa logjike (ndarje, bashkim)

Operacioni logjik OSE kryen funksionin e kombinimit të dy deklaratave, të cilat mund të jenë ose një shprehje logjike e thjeshtë ose komplekse. Deklaratat që janë fillestare për një operacion logjik quhen argumente. Rezultati i operacionit OR është një shprehje që do të jetë e vërtetë nëse dhe vetëm nëse të paktën një nga shprehjet origjinale është e vërtetë.
Emërtimet e përdorura: A ose B, A V B, A ose B, A||B.
Rezultati i operacionit OR përcaktohet nga tabela e mëposhtme e së vërtetës:
Rezultati i operacionit OR është i vërtetë kur A është e vërtetë, ose B është e vërtetë, ose të dyja A dhe B janë të vërteta dhe false kur A dhe B janë të rreme.

Operacioni DHE - shumëzim logjik (lidhëz)

Operacioni logjik AND kryen funksionin e kryqëzimit të dy pohimeve (argumenteve), të cilat mund të jenë ose një shprehje logjike e thjeshtë ose komplekse. Rezultati i veprimit AND është një shprehje që është e vërtetë nëse dhe vetëm nëse të dyja shprehjet origjinale janë të vërteta.
Simbolet e përdorura: A dhe B, A Λ B, A & B, A dhe B.
Rezultati i operacionit AND përcaktohet nga tabela e mëposhtme e së vërtetës:
ABA dhe B
0 0 0
0 1 0
1 0 0
1 1 1

Rezultati i veprimit AND është i vërtetë nëse dhe vetëm nëse pohimet A dhe B janë të dyja të vërteta dhe të gabuara në të gjitha rastet e tjera.

Operacioni "NËSE-THEN" - pasojë logjike (nënkuptim)

Ky veprim lidh dy shprehje të thjeshta logjike, nga të cilat e para është kusht dhe e dyta është pasojë e kësaj gjendjeje.
Emërtimet e aplikuara:
nëse A, atëherë B; A tërheq B; nëse A atëherë B; A → B.
Tabela e së vërtetës:
ABA→B
0 0 1
0 1 1
1 0 0
1 1 1

Rezultati i veprimit të pasojës (nënkuptimit) është i rremë vetëm kur premisa A është e vërtetë dhe përfundimi B (pasoja) është i gabuar.

Operacioni "A nëse dhe vetëm nëse B" (ekuivalenca, ekuivalenca)

Emërtimi i aplikueshëm: A ↔ B, A ~ B.
Tabela e së vërtetës:
ABA↔B
0 0 1
0 1 0
1 0 0
1 1 1

Operacioni i shtimit të Modulo 2 (XOR, ekskluziv ose, ndarje strikte)

Shënimi i përdorur: A XOR B, A ⊕ B.
Tabela e së vërtetës:
ABA⊕B
0 0 0
0 1 1
1 0 1
1 1 0

Rezultati i një operacioni të ekuivalencës është i vërtetë vetëm nëse të dyja A dhe B janë të dyja të vërteta ose të dyja false.

Përparësia e veprimeve logjike

  • Veprimet në kllapa
  • Përmbysja
  • Lidhëza (&)
  • Disjunction (V), Ekskluzive OR (XOR), modulo 2 sum
  • Implikimi (→)
  • Ekuivalenca (↔)

Forma normale e përsosur ndarëse

Forma normale e përsosur ndarëse e një formule(SDNF) është një formulë ekuivalente me të, e cila është një ndarje e lidhëzave elementare, e cila ka vetitë e mëposhtme:
  1. Çdo term logjik i formulës përmban të gjitha variablat e përfshirë në funksionin F(x 1 ,x 2 ,...x n).
  2. Të gjitha termat logjike të formulës janë të ndryshme.
  3. Asnjë term logjik nuk përmban një ndryshore dhe mohimin e saj.
  4. Asnjë term logjik në një formulë nuk përmban të njëjtën variabël dy herë.
SDNF mund të merret ose duke përdorur tabela të së vërtetës ose duke përdorur transformime ekuivalente.
Për çdo funksion, SDNF dhe SKNF përcaktohen në mënyrë unike deri në një ndryshim.

Forma normale e përsosur lidhore

Forma normale e përsosur konjuktive e një formule (SKNF)është një formulë ekuivalente me të, e cila është një lidhje e ndarjeve elementare që plotëson vetitë e mëposhtme:
  1. Të gjitha ndarjet elementare përmbajnë të gjitha ndryshoret e përfshira në funksionin F(x 1 ,x 2 ,...x n).
  2. Të gjitha ndarjet elementare janë të dallueshme.
  3. Çdo ndarje elementare përmban një ndryshore një herë.
  4. Asnjë ndarje elementare nuk përmban një ndryshore dhe mohimin e saj.

Si të zgjidhni disa probleme në seksionet A dhe B të provimit të shkencave kompjuterike

Mësimi numër 3. Logjika. Funksionet logjike. Zgjidhja e ekuacioneve

Një numër i madh detyrash USE i kushtohen logjikës së propozimeve. Për të zgjidhur shumicën e tyre, mjafton të njihen ligjet bazë të logjikës propozicionale, njohja e tabelave të së vërtetës së funksioneve logjike të një dhe dy ndryshoreve. Do të jap ligjet bazë të logjikës propozicionale.

  1. Komutativiteti i disjunksionit dhe lidhëzës:
    a ˅ b ≡ b ˅ a
    a^b ≡ b^a
  2. Ligji shpërndarës në lidhje me ndarjen dhe lidhjen:
    a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
    a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
  3. Negacion negativ:
    ¬(¬a) ≡ a
  4. Konsistenca:
    a ^ ¬a ≡ e rreme
  5. E treta ekskluzive:
    a ˅ ¬a ≡ e vërtetë
  6. Ligjet e De Morganit:
    ¬(a ˅ b) ≡ ¬a ˄ ¬b
    ¬(a ˄ b) ≡ ¬a ˅ ¬b
  7. Thjeshtimi:
    a ˄ a ≡ a
    a ˅ a ≡ a
    a ˄ e vërtetë ≡ a
    a ˄ e rreme ≡ e rreme
  8. Absorbimi:
    a ˄ (a ˅ b) ≡ a
    a ˅ (a ˄ b) ≡ a
  9. Zëvendësimi i nënkuptimit
    a → b ≡ ¬a ˅ b
  10. Ndryshimi i identitetit
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Paraqitja e funksioneve logjike

Çdo funksion logjik i n variablave - F(x 1 , x 2 , ... x n) mund të përcaktohet nga një tabelë e vërtetësisë. Një tabelë e tillë përmban 2 n grupe variablash, për secilën prej të cilave specifikohet vlera e funksionit në këtë grup. Kjo metodë është e mirë kur numri i variablave është relativisht i vogël. Edhe për n > 5, përfaqësimi bëhet dobët i dukshëm.

Një mënyrë tjetër është përcaktimi i funksionit me një formulë, duke përdorur funksione të njohura mjaft të thjeshta. Sistemi i funksioneve (f 1 , f 2 , … f k ) quhet i plotë nëse ndonjë funksion logjik mund të shprehet me një formulë që përmban vetëm funksione f i .

Sistemi i funksioneve (¬, ˄, ˅) është i plotë. Ligjet 9 dhe 10 janë shembuj se si implikimi dhe identiteti shprehen përmes mohimit, lidhjes dhe ndarjes.

Në fakt, sistemi i dy funksioneve është gjithashtu i plotë - mohimi dhe lidhja ose mohimi dhe disjunksioni. Përfaqësimet rrjedhin nga ligjet e De Morgan që lejojnë shprehjen e një lidhjeje përmes mohimit dhe ndarjes dhe, në përputhje me rrethanat, shprehjen e një ndarjeje përmes mohimit dhe lidhjes:

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

Në mënyrë paradoksale, një sistem i përbërë nga vetëm një funksion është i plotë. Ekzistojnë dy funksione binare - antikonjunksioni dhe antidisjunksioni, të quajtur shigjeta e Pierce-it dhe goditja e Schaeffer-it, që përfaqësojnë një sistem të zbrazët.

Funksionet themelore të gjuhëve të programimit zakonisht përfshijnë identitetin, mohimin, lidhjen dhe ndarjen. Në detyrat e provimit, krahas këtyre funksioneve, shpesh ka edhe një implikim.

Le të shohim disa detyra të thjeshta që lidhen me funksionet logjike.

Detyra 15:

Jepet një fragment i tabelës së së vërtetës. Cili nga tre funksionet e dhëna i korrespondon këtij fragmenti?

x1 x2 x3 x4 F
1 1 0 0 1
0 1 1 1 1
1 0 0 1 0
  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)

Karakteristika numër 3.

Për të zgjidhur problemin, duhet të njihni tabelat e vërtetësisë së funksioneve bazë dhe të mbani parasysh prioritetet e operacioneve. Më lejoni t'ju kujtoj se lidhëza (shumëzimi logjik) ka një përparësi më të madhe dhe kryhet para disjunksionit (mbledhja logjike). Gjatë llogaritjes, shihet lehtë se funksionet me numrat 1 dhe 2 në grupin e tretë kanë vlerën 1 dhe për këtë arsye nuk korrespondojnë me fragmentin.

Detyra 16:

Cili nga numrat e mëposhtëm plotëson kushtin:

(shifrat, duke filluar me shifrën më domethënëse, shkojnë në rend zbritës) → (numri - çift) ˄ (shifra më e ulët - çift) ˄ (shifra më e lartë - tek)

Nëse ka disa numra të tillë, tregoni më të madhin.

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

Kushti plotësohet nga numri 4.

Dy numrat e parë nuk e plotësojnë kushtin për arsye se shifra më e ulët është tek. Lidhja e kushteve është e rreme nëse një nga termat e lidhjes është i rremë. Për numrin e tretë, kushti për shifrën më të lartë nuk plotësohet. Për numrin e katërt, plotësohen kushtet e vendosura në shifrat e vogla dhe të mëdha të numrit. Termi i parë i lidhëzës është gjithashtu i vërtetë, pasi një nënkuptim është i vërtetë nëse premisa e tij është e gabuar, gjë që është rasti këtu.

Problemi 17: Dy dëshmitarë dëshmuan si më poshtë:

Dëshmitari i parë: Nëse A është fajtor, atëherë B është sigurisht fajtor dhe C është i pafajshëm.

Dëshmitari i dytë: Dy janë fajtorë. Dhe një nga të tjerët është padyshim fajtor dhe fajtor, por nuk mund të them saktësisht se kush.

Çfarë përfundimesh për fajësinë e A, B dhe C mund të nxirren nga provat?

Përgjigje: Nga dëshmia rezulton se A dhe B janë fajtorë, por C është i pafajshëm.

Zgjidhja: Sigurisht, përgjigja mund të jepet bazuar në sens të përbashkët. Por le të shohim se si mund të bëhet kjo në mënyrë rigoroze dhe formale.

Gjëja e parë që duhet të bëni është të zyrtarizoni deklaratat. Le të prezantojmë tre variabla Boolean, A, B dhe C, secila prej të cilave është e vërtetë (1) nëse i dyshuari përkatës është fajtor. Pastaj dëshmia e dëshmitarit të parë jepet me formulën:

A → (B ˄ ¬C)

Dëshmia e dëshmitarit të dytë jepet me formulën:

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

Dëshmitë e të dy dëshmitarëve supozohen të jenë të vërteta dhe përfaqësojnë lidhjen e formulave përkatëse.

Le të ndërtojmë një tabelë të së vërtetës për këto lexime:

A B C F1 F2 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

Provat përmbledhëse janë të vërteta vetëm në një rast, duke çuar në një përgjigje të qartë - A dhe B janë fajtorë, dhe C është i pafajshëm.

Nga analiza e kësaj tabele del gjithashtu se dëshmia e dëshmitarit të dytë është më informuese. Vetëm dy gjëra rrjedhin nga e vërteta e dëshmisë së tij. opsionet e mundshme A dhe B janë fajtorë dhe C është i pafajshëm, ose A dhe C janë fajtorë dhe B është i pafajshëm. Dëshmia e dëshmitarit të parë është më pak informative - ka 5 opsione të ndryshme që korrespondojnë me dëshminë e tij. Së bashku, dëshmitë e të dy dëshmitarëve japin një përgjigje të qartë për fajësinë e të dyshuarve.

Ekuacionet logjike dhe sistemet e ekuacioneve

Le të jetë F(x 1 , x 2 , …x n) një funksion logjik i n variablave. Ekuacioni logjik është:

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

Konstanta C ka vlerën 1 ose 0.

Një ekuacion logjik mund të ketë nga 0 deri në 2n zgjidhje të ndryshme. Nëse C është e barabartë me 1, atëherë zgjidhjet janë të gjitha ato grupe variablash nga tabela e së vërtetës në të cilat funksioni F merr vlerën true (1). Grupet e mbetura janë zgjidhje të ekuacionit për C të barabartë me zero. Ne gjithmonë mund të marrim parasysh vetëm ekuacionet e formës:

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

Në të vërtetë, le të jepet ekuacioni:

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

Në këtë rast, mund të shkoni në ekuacionin ekuivalent:

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

Konsideroni një sistem k ekuacionesh logjike:

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

Zgjidhja e sistemit është një grup variablash në të cilat plotësohen të gjitha ekuacionet e sistemit. Për sa i përket funksioneve logjike, për të marrë një zgjidhje për sistemin e ekuacioneve logjike, duhet gjetur një grup në të cilin funksioni logjik Ф është i vërtetë, duke përfaqësuar lidhjen e funksioneve origjinale F:

Ф = F 1 ˄ F 2 ˄ … F k

Nëse numri i variablave është i vogël, për shembull, më pak se 5, atëherë nuk është e vështirë të ndërtohet një tabelë e vërtetësisë për funksionin Ф, e cila ju lejon të thoni sa zgjidhje ka sistemi dhe cilat janë grupet që japin zgjidhje.

Në disa detyra të Provimit të Unifikuar të Shtetit për gjetjen e zgjidhjeve për një sistem ekuacionesh logjike, numri i variablave arrin vlerën 10. Më pas, ndërtimi i një tabele të së vërtetës bëhet një detyrë pothuajse e pazgjidhshme. Zgjidhja e problemit kërkon një qasje të ndryshme. Për një sistem arbitrar ekuacionesh, nuk ka asnjë mënyrë të përgjithshme, përveç numërimit, që lejon zgjidhjen e problemeve të tilla.

Në problemet e propozuara në provim, zgjidhja zakonisht bazohet në marrjen parasysh të specifikave të sistemit të ekuacioneve. E përsëris, përveç numërimit të të gjitha varianteve të një grupi variablash, nuk ka asnjë mënyrë të përgjithshme për të zgjidhur problemin. Zgjidhja duhet të ndërtohet në bazë të specifikave të sistemit. Shpesh është e dobishme të kryhet një thjeshtësim paraprak i një sistemi ekuacionesh duke përdorur ligjet e njohura të logjikës. Një teknikë tjetër e dobishme për zgjidhjen e këtij problemi është si më poshtë. Ne nuk jemi të interesuar për të gjitha grupet, por vetëm ato në të cilat funksioni Ф ka vlerën 1. Në vend që të ndërtojmë një tabelë të plotë të së vërtetës, ne do të ndërtojmë analogun e saj - një pemë binar vendimi. Çdo degë e kësaj peme i përgjigjet një zgjidhjeje dhe specifikon një bashkësi në të cilën funksioni Ф ka vlerën 1. Numri i degëve në pemën e vendimit përkon me numrin e zgjidhjeve të sistemit të ekuacioneve.

Çfarë është një pemë e vendimeve binare dhe si është ndërtuar, unë do të shpjegoj me shembuj të disa detyrave.

Problemi 18

Sa grupe të ndryshme vlerash të variablave boolean x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ka që plotësojnë një sistem me dy ekuacione?

Përgjigje: Sistemi ka 36 zgjidhje të ndryshme.

Zgjidhje: Sistemi i ekuacioneve përfshin dy ekuacione. Le të gjejmë numrin e zgjidhjeve për ekuacionin e parë, në varësi të 5 ndryshoreve – x 1 , x 2 , …x 5 . Ekuacioni i parë mund të konsiderohet si një sistem prej 5 ekuacionesh. Siç është treguar, sistemi i ekuacioneve përfaqëson në të vërtetë një lidhje funksionesh logjike. Deklarata e kundërt është gjithashtu e vërtetë - lidhja e kushteve mund të konsiderohet si një sistem ekuacionesh.

Le të ndërtojmë një pemë vendimi për nënkuptimin (x1→ x2), termi i parë i lidhëzës, i cili mund të konsiderohet si ekuacioni i parë. Ja si duket paraqitja grafike e kësaj peme:

Pema ka dy nivele variablat e ekuacionit. Niveli i parë përshkruan variablin e parë X 1 . Dy degë të këtij niveli pasqyrojnë vlerat e mundshme të kësaj variabli - 1 dhe 0. Në nivelin e dytë, degët e pemës pasqyrojnë vetëm ato vlera të mundshme të ndryshores X 2 për të cilat ekuacioni merr vlerën e vërtetë. Meqenëse ekuacioni përcakton një nënkuptim, dega në të cilën X 1 ka vlerën 1 kërkon që X 2 të ketë vlerën 1 në atë degë. Dega në të cilën X 1 ka vlerën 0 gjeneron dy degë me vlera X 2 të barabarta me 0 dhe 1 Pema e ndërtuar specifikon tre zgjidhje, mbi të cilat implikimi X 1 → X 2 merr vlerën 1. Në secilën degë, shkruhet grupi përkatës i vlerave të variablave, i cili i jep zgjidhje ekuacionit.

Këto grupe janë: ((1, 1), (0, 1), (0, 0))

Le të vazhdojmë ndërtimin e pemës së vendimit duke shtuar ekuacionin e mëposhtëm, nënkuptimin e mëposhtëm X 2 → X 3 . Specifikimi i sistemit tonë të ekuacioneve është se çdo ekuacion i ri i sistemit përdor një ndryshore nga ekuacioni i mëparshëm, duke shtuar një ndryshore të re. Meqenëse ndryshorja X 2 tashmë ka vlera në pemë, atëherë në të gjitha degët ku ndryshorja X 2 ka vlerën 1, ndryshorja X 3 do të ketë gjithashtu vlerën 1. Për degë të tilla, ndërtimi i pemës vazhdon të niveli tjetër, por nuk shfaqen degë të reja. E vetmja degë ku ndryshorja X 2 ka vlerën 0 do të japë një degë në dy degë, ku ndryshorja X 3 do të marrë vlerat 0 dhe 1. Kështu, çdo shtim i një ekuacioni të ri, duke pasur parasysh specifikën e tij, shton një zgjidhje. Ekuacioni i parë origjinal:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
ka 6 zgjidhje. Ja se si duket pema e plotë e vendimit për këtë ekuacion:

Ekuacioni i dytë i sistemit tonë është i ngjashëm me të parën:

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

I vetmi ndryshim është se ekuacioni përdor variabla Y. Ky ekuacion gjithashtu ka 6 zgjidhje. Meqenëse çdo zgjidhje ndryshore X i mund të kombinohet me çdo zgjidhje variabël Y j, atëherë numri total zgjidhjet është 36.

Vini re se pema e ndërtuar e vendimeve jep jo vetëm numrin e zgjidhjeve (sipas numrit të degëve), por edhe vetë zgjidhjet, të shkruara në secilën degë të pemës.

Problemi 19

Sa grupe të ndryshme vlerash të variablave boolean x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ka që plotësojnë të gjitha kushtet e mëposhtme?

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

Kjo detyrë është një modifikim i detyrës së mëparshme. Dallimi është se shtohet një ekuacion tjetër që lidh variablat X dhe Y.

Nga ekuacioni X 1 → Y 1 rrjedh se kur X 1 ka vlerën 1 (një zgjidhje e tillë ekziston), atëherë Y 1 ka vlerën 1. Kështu, ekziston një grup në të cilin X 1 dhe Y 1 kanë vlerat ​​1. Me X 1 të barabartë me 0, Y 1 mund të ketë çdo vlerë, si 0 ashtu edhe 1. Prandaj, çdo grup me X 1 është i barabartë me 0, dhe ka 5 grupe të tilla, korrespondon me të 6 grupet me ndryshore Y. Prandaj , numri i përgjithshëm i zgjidhjeve është 31 .

Problemi 20

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

Zgjidhje: Duke kujtuar ekuivalencën bazë, e shkruajmë ekuacionin tonë si:

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

Zinxhiri ciklik i implikimeve do të thotë që variablat janë identikë, kështu që ekuacioni ynë është i barabartë me:

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

Ky ekuacion ka dy zgjidhje kur të gjitha X i janë ose 1 ose 0.

Problemi 21

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

Zgjidhja: Ashtu si në problemin 20, kalojmë nga implikimet ciklike në identitete duke rishkruar ekuacionin në formën:

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

Le të ndërtojmë një pemë vendimi për këtë ekuacion:

Problemi 22

Sa zgjidhje ka sistemi i mëposhtëm i ekuacioneve?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0

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

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

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

Përgjigje: 64

Zgjidhja: Le të kalojmë nga 10 variabla në 5 variabla duke prezantuar ndryshimin e mëposhtëm të variablave:

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

Atëherë ekuacioni i parë do të marrë formën:

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

Ekuacioni mund të thjeshtohet duke e shkruar atë si:

(Y 1 ≡ Y 2) = 0

Duke kaluar në formën tradicionale, ne e shkruajmë sistemin pas thjeshtimeve në formën:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Pema e vendimit për këtë sistem është e thjeshtë dhe përbëhet nga dy degë me vlera të ndryshueshme të alternuara:


Duke u kthyer në variablat origjinale X, vini re se çdo vlerë e ndryshores Y korrespondon me 2 vlera të ndryshoreve X, kështu që çdo zgjidhje në variablat Y gjeneron 2 5 zgjidhje në variablat X. Dy degë gjenerojnë zgjidhje 2 * 2 5 , pra numri i përgjithshëm i zgjidhjeve është 64.

Siç mund ta shihni, çdo detyrë për zgjidhjen e një sistemi ekuacionesh kërkon qasjen e vet. Një truk i zakonshëm është kryerja e transformimeve ekuivalente për të thjeshtuar ekuacionet. Një teknikë e zakonshme është ndërtimi i pemëve të vendimit. Qasja e aplikuar i ngjan pjesërisht ndërtimit të një tabele të vërtetësisë me veçorinë që nuk janë ndërtuar të gjitha grupet e vlerave të mundshme të variablave, por vetëm ato mbi të cilat funksioni merr vlerën 1 (e vërtetë). Shpesh në problemet e propozuara nuk ka nevojë të ndërtohet një pemë e plotë vendimi, pasi tashmë në fazën fillestare është e mundur të përcaktohet rregullsia e shfaqjes së degëve të reja në çdo nivel tjetër, siç u bë, për shembull, në problemin 18. .

Në përgjithësi, problemet për gjetjen e zgjidhjeve të një sistemi ekuacionesh logjike janë ushtrime të mira matematikore.

Nëse problemi është i vështirë për t'u zgjidhur me dorë, atëherë mund t'ia besoni zgjidhjen e problemit kompjuterit duke shkruar një program të përshtatshëm për zgjidhjen e ekuacioneve dhe sistemeve të ekuacioneve.

Është e lehtë të shkruash një program të tillë. Një program i tillë do të përballojë lehtësisht të gjitha detyrat e ofruara në provim.

Mjaft e çuditshme, por detyra për të gjetur zgjidhje për sistemet e ekuacioneve logjike është gjithashtu e vështirë për një kompjuter, rezulton se një kompjuter ka kufijtë e tij. Kompjuteri mund të përballojë lehtësisht detyrat ku numri i variablave është 20-30, por do të fillojë të mendojë për një kohë të gjatë për detyra më të mëdha. Çështja është se funksioni 2 n që specifikon numrin e grupeve është një eksponent që rritet me shpejtësi me n. Aq i shpejtë sa një kompjuter personal normal nuk mund të përballojë një detyrë me 40 variabla në ditë.

Programi C# për zgjidhjen e ekuacioneve logjike

Është e dobishme të shkruani një program për zgjidhjen e ekuacioneve logjike për shumë arsye, qoftë edhe vetëm sepse mund të përdoret për të kontrolluar korrektësinë e zgjidhjes suaj për problemet e testit USE. Një arsye tjetër është se një program i tillë është një shembull i shkëlqyer i një problemi programimi që plotëson kërkesat për problemet e kategorisë C në USE.

Ideja e ndërtimit të një programi është e thjeshtë - bazohet në një numërim të plotë të të gjitha grupeve të mundshme të vlerave të ndryshueshme. Meqenëse numri i ndryshoreve n është i njohur për një ekuacion logjik të caktuar ose sistem ekuacionesh, dihet edhe numri i grupeve - 2 n, të cilat duhet të zgjidhen. Duke përdorur funksionet bazë të gjuhës C# - mohimi, shkëputja, lidhja dhe identiteti, është e lehtë të shkruhet një program që, për një grup të caktuar variablash, llogarit vlerën e një funksioni logjik që korrespondon me një ekuacion logjik ose një sistem ekuacionesh.

Në një program të tillë, ju duhet të ndërtoni një cikël me numrin e grupeve, në trupin e ciklit, me numrin e grupit, të formoni vetë grupin, të llogarisni vlerën e funksionit në këtë grup dhe nëse kjo vlerë është e barabartë në 1, atëherë grupi i jep një zgjidhje ekuacionit.

Vështirësia e vetme që lind në zbatimin e programit lidhet me detyrën e formimit të vetë grupit të vlerave të variablave nga numri i caktuar. E bukura e kësaj detyre është se kjo detyrë në dukje e vështirë, në fakt, zbret në një detyrë të thjeshtë që tashmë është ngritur vazhdimisht. Në të vërtetë, mjafton të kuptohet se grupi i vlerave të ndryshoreve që korrespondojnë me numrin i, i përbërë nga zero dhe njëshe, përfaqëson paraqitjen binar të numrit i. Kështu që detyrë e vështirë marrja e një grupi vlerash të ndryshoreve me numrin e grupit reduktohet në problemin e njohur të shndërrimit të një numri në një sistem binar.

Kështu duket funksioni C# që zgjidh problemin tonë:

///

/// program për numërimin e numrit të zgjidhjeve

/// ekuacioni logjik (sistemi i ekuacioneve)

///

///

/// funksioni logjik - metoda,

/// nënshkrimi i të cilit vendoset nga delegati i DF

///

/// numri i variablave

/// numri i zgjidhjeve

Static int SolveEquations (DF fun, int n)

bool set = bool i ri[n];

int m = (int)Math.Pow(2, n); //numri i grupeve

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

//Numërimi i plotë sipas numrit të grupeve

për (int i = 0; i< m; i++)

//Formimi i grupit të ardhshëm - grup,

//e dhënë nga paraqitja binar e numrit i

për (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Llogaritni vlerën e funksionit në grup

Për të kuptuar programin, shpresoj që të mjaftojnë shpjegimet e idesë së programit dhe komentet në tekstin e tij. Do të ndalem vetëm në shpjegimin e titullit të funksionit të mësipërm. Funksioni SolveEquations ka dy parametra hyrës. Parametri fun specifikon një funksion logjik që korrespondon me ekuacionin ose sistemin e ekuacioneve që zgjidhen. Parametri n specifikon numrin e variablave në funksionin argëtues. Si rezultat, funksioni SolveEquations kthen numrin e zgjidhjeve të funksionit logjik, domethënë numrin e grupeve në të cilat funksioni vlerësohet në të vërtetë.

Për nxënësit e shkollës, është e zakonshme kur për ndonjë funksion F(x) parametri hyrës x është një variabël i tipit aritmetik, varg ose boolean. Në rastin tonë, përdoret një dizajn më i fuqishëm. Funksioni SolveEquations i referohet funksioneve të rendit më të lartë - funksione të tipit F(f), parametrat e të cilëve mund të jenë jo vetëm variabla të thjeshtë, por edhe funksione.

Klasa e funksioneve që mund të kalohet si parametër në funksionin SolveEquations përcaktohet si më poshtë:

delegoj bool DF(bool vars);

Kjo klasë përfshin të gjitha funksionet që kalohen si parametër një grup vlerash të variablave boolean të specifikuara nga vargu vars. Rezultati është një vlerë Boolean që përfaqëson vlerën e funksionit në këtë grup.

Si përfundim, do të jap një program në të cilin funksioni SolveEquations përdoret për të zgjidhur disa sisteme ekuacionesh logjike. Funksioni SolveEquations është pjesë e klasës së mëposhtme ProgramCommon:

klasë Programi i përbashkët

delegoj bool DF(bool vars);

zbrazëti statike kryesore (argët e vargut)

Console.WriteLine("Funksioni dhe zgjidhjet - " +

ZgjidheEkuacione (FunDhe, 2));

Console.WriteLine("Funksioni ka 51 zgjidhje - " +

ZgjidheEkuacione (Fun51, 5));

Console.WriteLine("Funksioni ka 53 zgjidhje - " +

ZgjidheEkuacione (Fun53, 10));

bool statike FunAnd (bool vars)

kthim vars && vars;

static bool Fun51 (bool vars)

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

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

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

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

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

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

Ja si duken rezultatet e zgjidhjes për këtë program:

10 detyra për punë të pavarur

  1. Cili nga tre funksionet është ekuivalent:
    1. (X → Y) ˅ ¬Y
    2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
    3. ¬X ˄ Y
  2. Jepet një fragment i tabelës së së vërtetës:
x1 x2 x3 x4 F
1 0 0 1 1
0 1 1 1 1
1 0 1 0 0

Cili nga tre funksionet i korrespondon këtij fragmenti:

  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. Juria përbëhet nga tre persona. Vendimi merret nëse për të voton kryetari i jurisë, i mbështetur nga të paktën një prej anëtarëve të jurisë. Në të kundërt nuk merret asnjë vendim. Ndërtoni një funksion logjik që zyrtarizon procesin e vendimmarrjes.
  5. X fiton mbi Y nëse katër hedhje monedhash vijnë tre herë lart. Përcaktoni një funksion boolean që përshkruan fitimin X.
  6. Fjalët në një fjali numërohen duke filluar nga një. Një fjali konsiderohet e mirëformuar nëse plotësohen rregullat e mëposhtme:
    1. Nëse një fjalë e numëruar çift përfundon me një zanore, atëherë fjala tjetër, nëse ekziston, duhet të fillojë me një zanore.
    2. Nëse një fjalë me numër tek përfundon me një bashkëtingëllore, atëherë fjala tjetër, nëse ekziston, duhet të fillojë me një bashkëtingëllore dhe të përfundojë me një zanore.
      Cilat nga fjalitë e mëposhtme janë të sakta:
    3. Mami e lau Mashën me sapun.
    4. Lideri është gjithmonë një model.
    5. E vërteta është e mirë, por lumturia është më e mirë.
  7. Sa zgjidhje ka ekuacioni:
    (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
  8. Listoni të gjitha zgjidhjet e ekuacionit:
    (a → b) → c = 0
  9. Sa zgjidhje ka sistemi i mëposhtëm i ekuacioneve:
    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. Sa zgjidhje ka ekuacioni:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Përgjigjet për detyrat:

  1. Funksionet b dhe c janë ekuivalente.
  2. Fragmenti i përgjigjet funksionit b.
  3. Lëreni variablin boolean P të marrë vlerën 1 kur kryetari i jurisë voton "pro" vendimin. Variablat M 1 dhe M 2 përfaqësojnë opinionin e anëtarëve të jurisë. Funksioni logjik që specifikon miratimin e një vendimi pozitiv mund të shkruhet si më poshtë:
    P ˄ (M 1 ˅ M 2)
  4. Lëreni variablin boolean P i të marrë vlerën 1 kur i-të hedhin monedha del lart. Funksioni logjik që përcakton fitimin X mund të shkruhet si më poshtë:
    ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
    (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
    (¬P 3 ˄ ¬P 4))
  5. Oferta b.
  6. Ekuacioni ka 3 zgjidhje: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a=0; b=1; c=0)

Ky material përmban një prezantim që paraqet metodat e zgjidhjes së ekuacioneve logjike dhe sistemet e ekuacioneve logjike në detyrën B15 (Nr. 23, 2015) të Provimit të Unifikuar të Shtetit në Informatikë. Dihet se kjo detyrë është një nga më të vështirat ndër detyrat e provimit. Prezantimi mund të jetë i dobishëm gjatë zhvillimit të mësimeve me temën "Logjika" në klasa të specializuara, si dhe në përgatitjen për dhënien e provimit.

Shkarko:

Pamja paraprake:

Për të përdorur pamjen paraprake të prezantimeve, krijoni një llogari (llogari) Google dhe regjistrohuni: https://accounts.google.com


Titrat e rrëshqitjeve:

Zgjidhja e detyrës B15 (sistemi i ekuacioneve logjike) Vishnevskaya M.P., MAOU "Gjimnazi nr. 3" 18 nëntor 2013, Saratov

Detyra B15 është një nga më të vështirat në provimin në shkenca kompjuterike !!! Kontrollohen aftësitë: të transformohen shprehjet që përmbajnë variabla logjike; të përshkruajë në gjuhën natyrore grupin e vlerave të ndryshoreve logjike për të cilat një grup i caktuar variablash logjikë është i vërtetë; numëroni numrin e grupeve binare që plotësojnë kushtet e dhëna. Më e vështira, sepse nuk ka rregulla formale se si ta bëni këtë, kërkohet hamendje.

Çfarë nuk duhet të bëni pa!

Çfarë nuk duhet të bëni pa!

Lidhja e konventave: A /\ B , A  B , AB , A &B, A dhe B ndarja: A \ / B , A + B , A | B , A ose B mohim:  A , A, jo ekuivalent A: A  B, A  B, A  B XOR: A  B , A xor B

Metoda e zëvendësimit të variablave Sa grupe të ndryshme vlerash të variablave boolean x1, x2, ..., x9, x10 ekzistojnë që plotësojnë të gjitha kushtet e mëposhtme: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\  (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ ​​· (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\  (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Përgjigja nuk ka nevojë të renditë të gjitha grupet e ndryshme x1, x2, …, x9, x10 nën të cilat sistemi i caktuar i barazive është i kënaqur. Si përgjigje, duhet të tregoni numrin e grupeve të tilla (versioni demo 2012)

Zgjidhja Hapi 1. Thjeshtoni duke ndryshuar variablat t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Pas thjeshtimit: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Shqyrtoni një nga ekuacionet: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Natyrisht, është =1 vetëm nëse njëra nga variablat është 0 dhe tjetra është 1 Ne përdorim formulën për të shprehur veprimin XOR në termat e lidhjes dhe ndarjes: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Hapi 2. Analiza e sistemit .të. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), atëherë çdo vlerë tk korrespondon me dy çifte vlerash x2k-1 dhe x2k, për shembull: tk =0 korrespondon me dy çifte - (0, 1) dhe (1, 0) , dhe tk =1 janë çiftet (0,0) dhe (1,1).

Hapi 3. Numërimi i numrit të zgjidhjeve. Çdo t ka 2 zgjidhje, numri i t është 5. Kështu për variablat t ka 2 5 = 32 zgjidhje. Por çdo t i korrespondon një çifti zgjidhjesh x, d.m.th. sistemi origjinal ka 2*32 = 64 zgjidhje. Përgjigje: 64

Metoda e eliminimit të zgjidhjes së pjesshme Sa grupe të ndryshme vlerash të ndryshoreve logjike x1, x2, …, x5, y1, y2,…, y5 ekzistojnë që plotësojnë të gjitha kushtet e mëposhtme: (x1→ x2)∧(x2→ x3)∧ (x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. Përgjigja nuk ka nevojë të renditë të gjitha grupet e ndryshme x1, x2, ..., x5, y 1, y2, ..., y5, sipas të cilave plotësohet ky sistem barazish. Si përgjigje, duhet të tregoni numrin e grupeve të tilla.

Vendimi. Hapi 1. Vendim konsistent ekuacionet x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 secila prej nënkuptimeve është e vërtetë. Implikimi është i rremë vetëm në një rast, kur 1  0, në të gjitha rastet e tjera (0  0, 0  1, 1  1) operacioni kthen 1. Le ta shkruajmë këtë në formën e një tabele:

Hapi 1. Zgjidhja sekuenciale e ekuacioneve Т.о. Janë marrë 6 grupe zgjidhjesh për х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Duke argumentuar në mënyrë të ngjashme, arrijmë në përfundimin se për y1, y2, y3, y4, y5 ekziston i njëjti grup zgjidhjesh. Sepse këto ekuacione janë të pavarura, d.m.th. nuk ka ndryshore të zakonshme në to, atëherë zgjidhja e këtij sistemi ekuacionesh (pa marrë parasysh ekuacionin e tretë) do të jetë 6 * 6 = 36 palë "xes" dhe "po". Merrni parasysh ekuacionin e tretë: y5→ x5 =1 Çiftet janë zgjidhja: 0 0 0 1 1 1 Çifti nuk është zgjidhje: 1 0

Të krahasojmë zgjidhjet e marra.Ku nuk përshtaten y5 =1, x5=0. janë 5 çifte të tilla.Numri i zgjidhjeve të sistemit: 36-5= 31. Përgjigje: 31 U desh kombinatorika!!!

Metoda e programimit dinamik Sa zgjidhje të ndryshme ka ekuacioni logjik x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, ku x 1, x 2, ..., x 6 janë ndryshore logjike? Përgjigja nuk ka nevojë të listojë të gjitha grupet e ndryshme të vlerave të ndryshueshme për të cilat vlen kjo barazi. Si përgjigje, duhet të tregoni numrin e grupeve të tilla.

Zgjidhja Hapi 1. Analiza e gjendjes Në anën e majtë të ekuacionit, veprimet e nënkuptimit shkruhen në mënyrë sekuenciale, përparësia është e njëjtë. Rishkruaj: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Çdo variabël tjetër nuk varet nga ajo e mëparshme, por nga rezultati i implikimit të mëparshëm!

Hapi 2. Zbulimi i modelit Merrni parasysh nënkuptimin e parë, X 1 → X 2. Tabela e së vërtetës: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Nga një 0 morëm 2 njësi, dhe nga 1 ne mori një 0 dhe një 1. Vetëm një 0 dhe tre 1, ky është rezultati i operacionit të parë.

Hapi 2. Duke zbuluar një model Duke lidhur x 3 me rezultatin e veprimit të parë, marrim: 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 1 0 0 1 1 1 1 0 0 1 1 1 Nga dy 0 - dy 1, nga secila 1 (janë 3) një secila 0 dhe 1 (3 + 3)

Hapi 3. Nxjerrja e formulës ju mund të bëni formula për llogaritjen e numrit të zerove N i dhe numrit të njësheve E i për një ekuacion me variabla i: ,

Hapi 4. Plotësimi i tabelës Le të plotësojmë tabelën për i = 6 nga e majta në të djathtë, duke llogaritur numrin e zeros dhe njëshit duke përdorur formulat e mësipërme; Tabela tregon se si është ndërtuar kolona pasardhëse sipas asaj të mëparshme: : numri i ndryshoreve 1 2 3 4 5 6 Numri i zerove N i 1 1 3 5 11 21 Numri i njësheve E i 1 2*1+1= 3 2 *1+3= 5 11 21 43 Përgjigje: 43

Metoda duke përdorur thjeshtimet e shprehjeve logjike Sa zgjidhje të ndryshme ka ekuacioni ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 ku J , K, L, M, N janë variabla logjike? Përgjigja nuk ka nevojë të renditë të gjitha grupet e ndryshme të vlerave J, K, L, M dhe N për të cilat vlen kjo barazi. Si përgjigje, duhet të tregoni numrin e grupeve të tilla.

Zgjidhje Vini re se J → K = ¬ J  K Prezantojmë një ndryshim të ndryshoreve: J → K=A, M  N  L =B E rishkruajmë ekuacionin duke marrë parasysh ndryshimin: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Natyrisht, A  B për të njëjtat vlera të A dhe B 6. Konsideroni implikimin e fundit M → J =1 Kjo është e mundur nëse: M= J=0 M=0, J=1 M=J=1

Zgjidhje A  B , atëherë me M=J=0 marrim 1 + K=0. Nuk ka zgjidhje. Me M=0, J=1 marrim 0 + K=0, K=0, dhe N dhe L - çdo, 4 zgjidhje: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 nje

Zgjidhja 10. Me M=J=1 marrim 0+K=1 *N * L , ose K=N*L, 4 zgjidhje: 11. Gjithsej ka 4+4=8 zgjidhje Përgjigje: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Burimet e informacionit: O.B. Bogomolova, D.Yu. Usenkov. B15: detyra të reja dhe zgjidhje të reja // Informatikë, Nr. 6, 2012, f. 35 – 39. K.Yu. Polyakov. Ekuacionet logjike // Informatika, Nr. 14, 2011, f. 30-35. http://ege-go.ru/zadania/grb/b15/, [Burimi elektronik]. http://kpolyakov.narod.ru/school/ege.htm, [Burimi elektronik].


Le të jetë një funksion logjik i n variablave. Ekuacioni logjik është:

Konstanta C ka vlerën 1 ose 0.

Një ekuacion logjik mund të ketë nga 0 në zgjidhje të ndryshme. Nëse C është e barabartë me 1, atëherë zgjidhjet janë të gjitha ato grupe variablash nga tabela e së vërtetës në të cilat funksioni F merr vlerën true (1). Grupet e mbetura janë zgjidhje të ekuacionit për C të barabartë me zero. Ne gjithmonë mund të marrim parasysh vetëm ekuacionet e formës:

Në të vërtetë, le të jepet ekuacioni:

Në këtë rast, mund të shkoni në ekuacionin ekuivalent:

Konsideroni një sistem k ekuacionesh logjike:

Zgjidhja e sistemit është një grup variablash në të cilat plotësohen të gjitha ekuacionet e sistemit. Për sa i përket funksioneve logjike, për të marrë një zgjidhje për sistemin e ekuacioneve logjike, duhet gjetur një grup në të cilin funksioni logjik Ф është i vërtetë, që përfaqëson lidhjen e funksioneve origjinale:

Nëse numri i variablave është i vogël, për shembull, më pak se 5, atëherë nuk është e vështirë të ndërtoni një tabelë të vërtetësisë për funksionin, e cila ju lejon të thoni sa zgjidhje ka sistemi dhe cilat janë grupet që japin zgjidhje.

Në disa detyra të Provimit të Unifikuar të Shtetit për gjetjen e zgjidhjeve për një sistem ekuacionesh logjike, numri i variablave arrin vlerën 10. Më pas, ndërtimi i një tabele të së vërtetës bëhet një detyrë pothuajse e pazgjidhshme. Zgjidhja e problemit kërkon një qasje të ndryshme. Për një sistem arbitrar ekuacionesh, nuk ka asnjë mënyrë të përgjithshme, përveç numërimit, që lejon zgjidhjen e problemeve të tilla.

Në problemet e propozuara në provim, zgjidhja zakonisht bazohet në marrjen parasysh të specifikave të sistemit të ekuacioneve. E përsëris, përveç numërimit të të gjitha varianteve të një grupi variablash, nuk ka asnjë mënyrë të përgjithshme për të zgjidhur problemin. Zgjidhja duhet të ndërtohet në bazë të specifikave të sistemit. Shpesh është e dobishme të kryhet një thjeshtësim paraprak i një sistemi ekuacionesh duke përdorur ligjet e njohura të logjikës. Një teknikë tjetër e dobishme për zgjidhjen e këtij problemi është si më poshtë. Ne nuk jemi të interesuar për të gjitha grupet, por vetëm ato në të cilat funksioni ka vlerën 1. Në vend që të ndërtojmë një tabelë të plotë të së vërtetës, ne do të ndërtojmë analogun e saj - një pemë binar vendimi. Çdo degë e kësaj peme i përgjigjet një zgjidhjeje dhe specifikon bashkësinë në të cilën funksioni ka vlerën 1. Numri i degëve në pemën e vendimit përkon me numrin e zgjidhjeve të sistemit të ekuacioneve.

Çfarë është një pemë e vendimeve binare dhe si është ndërtuar, unë do të shpjegoj me shembuj të disa detyrave.

Problemi 18

Sa grupe të ndryshme vlerash të variablave boolean x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ka që plotësojnë një sistem me dy ekuacione?

Përgjigje: Sistemi ka 36 zgjidhje të ndryshme.

Zgjidhje: Sistemi i ekuacioneve përfshin dy ekuacione. Le të gjejmë numrin e zgjidhjeve për ekuacionin e parë në varësi të 5 ndryshoreve - . Ekuacioni i parë mund të konsiderohet si një sistem prej 5 ekuacionesh. Siç është treguar, sistemi i ekuacioneve përfaqëson në të vërtetë një lidhje funksionesh logjike. Deklarata e kundërt është gjithashtu e vërtetë - lidhja e kushteve mund të konsiderohet si një sistem ekuacionesh.

Le të ndërtojmë një pemë vendimi për nënkuptimin () - termi i parë i lidhëzës, i cili mund të konsiderohet si ekuacioni i parë. Ja si duket imazhi grafik i kësaj peme


Pema përbëhet nga dy nivele sipas numrit të variablave në ekuacion. Niveli i parë përshkruan variablin e parë. Dy degë të këtij niveli pasqyrojnë vlerat e mundshme të kësaj ndryshore - 1 dhe 0. Në nivelin e dytë, degët e pemës pasqyrojnë vetëm ato vlera të mundshme të ndryshores për të cilat ekuacioni merr vlerën e vërtetë. Meqenëse ekuacioni përcakton një nënkuptim, dega në të cilën ka vlerën 1 kërkon që të ketë vlerën 1 në atë degë. Dega në të cilën ka një vlerë 0 gjeneron dy degë me vlera të barabarta me 0 dhe 1. Pema e ndërtuar përcakton tre zgjidhje, ku implikimi merr vlerën 1. Në secilën degë shkruhet grupi përkatës i vlerave të variablave, i cili i jep zgjidhje ekuacionit.

Këto grupe janë: ((1, 1), (0, 1), (0, 0))

Le të vazhdojmë ndërtimin e pemës së vendimit duke shtuar ekuacionin e mëposhtëm, nënkuptimin e mëposhtëm. Specifikimi i sistemit tonë të ekuacioneve është se çdo ekuacion i ri i sistemit përdor një ndryshore nga ekuacioni i mëparshëm, duke shtuar një ndryshore të re. Meqenëse ndryshorja ka tashmë vlera në pemë, atëherë në të gjitha degët ku ndryshorja ka vlerën 1, ndryshorja do të ketë gjithashtu vlerën 1. Për degë të tilla, ndërtimi i pemës vazhdon në nivelin tjetër, por nuk shfaqen degë të reja. E vetmja degë ku ndryshorja ka vlerën 0 do të japë një degëzim në dy degë, ku ndryshorja do të marrë vlerat 0 dhe 1. Kështu, çdo shtim i një ekuacioni të ri, duke pasur parasysh specifikën e tij, shton një zgjidhje. Ekuacioni i parë origjinal:

ka 6 zgjidhje. Ja se si duket pema e plotë e vendimit për këtë ekuacion:


Ekuacioni i dytë i sistemit tonë është i ngjashëm me të parën:

I vetmi ndryshim është se ekuacioni përdor variabla Y. Ky ekuacion gjithashtu ka 6 zgjidhje. Meqenëse çdo zgjidhje variabël mund të kombinohet me secilën zgjidhje të ndryshueshme, numri i përgjithshëm i zgjidhjeve është 36.

Vini re se pema e ndërtuar e vendimeve jep jo vetëm numrin e zgjidhjeve (sipas numrit të degëve), por edhe vetë zgjidhjet, të shkruara në secilën degë të pemës.

Problemi 19

Sa grupe të ndryshme vlerash të variablave boolean x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ka që plotësojnë të gjitha kushtet e mëposhtme?

Kjo detyrë është një modifikim i detyrës së mëparshme. Dallimi është se shtohet një ekuacion tjetër që lidh variablat X dhe Y.

Nga ekuacioni del se kur ka vlerën 1 (ekziston një zgjidhje e tillë), atëherë ka vlerën 1. Kështu, ekziston një grup në të cilin dhe ka vlerat 1. Kur është e barabartë me 0, mund të ketë çdo vlerë, si 0 ashtu edhe 1. Prandaj, çdo grup është i barabartë me 0, dhe ka 5 grupe të tilla, korrespondon me të 6 grupet me ndryshore Y. Prandaj, numri i përgjithshëm i zgjidhjeve është 31.

Problemi 20

Zgjidhje: Duke kujtuar ekuivalencën bazë, e shkruajmë ekuacionin tonë si:

Zinxhiri ciklik i implikimeve do të thotë që variablat janë identikë, kështu që ekuacioni ynë është i barabartë me:

Ky ekuacion ka dy zgjidhje kur të gjitha janë ose 1 ose 0.

Problemi 21

Sa zgjidhje ka ekuacioni:

Zgjidhja: Ashtu si në problemin 20, kalojmë nga implikimet ciklike në identitete duke rishkruar ekuacionin në formën:

Le të ndërtojmë një pemë vendimi për këtë ekuacion:


Problemi 22

Sa zgjidhje ka sistemi i mëposhtëm i ekuacioneve?

Tema e mësimit: Zgjidhja e ekuacioneve logjike

arsimore - mësimi i zgjidhjes së ekuacioneve logjike, formimi i aftësive dhe aftësive për zgjidhjen e ekuacioneve logjike dhe ndërtimi i një shprehjeje logjike sipas tabelës së së vërtetës;

arsimore - krijojnë kushte për zhvillimin e interesit kognitiv të studentëve, promovojnë zhvillimin e kujtesës, vëmendjes, të menduarit logjik;

arsimore : kontribuojnë në edukimin e aftësisë për të dëgjuar mendimet e të tjerëve, edukimi i vullnetit dhe këmbënguljes për të arritur rezultatet përfundimtare.

Lloji i mësimit: mësim i kombinuar

Pajisjet: kompjuter, projektor multimedial, prezantim 6.

Gjatë orëve të mësimit

    Përsëritja dhe përditësimi i njohurive bazë. Ekzaminimi detyre shtepie(10 minuta)

Në mësimet e mëparshme, ne u njohëm me ligjet bazë të algjebrës së logjikës, mësuam se si t'i përdorim këto ligje për të thjeshtuar shprehjet logjike.

Le të kontrollojmë detyrat e shtëpisë për thjeshtimin e shprehjeve logjike:

1. Cila nga fjalët e mëposhtme plotëson kushtin logjik:

(bashkëtingëllore e parë → bashkëtingëllore e dytë)٨ (zanorja e shkronjës së fundit → zanorja e shkronjës së parafundit)? Nëse ka disa fjalë të tilla, tregoni më të voglën prej tyre.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Le të prezantojmë shënimin:

A është shkronja e parë e një bashkëtingëllore

B është shkronja e dytë e një bashkëtingëllore

S është zanorja e fundit

D - zanore e parafundit

Le të bëjmë një shprehje:

Le të bëjmë një tabelë:

2. Tregoni cila shprehje logjike është ekuivalente me shprehjen


Le të thjeshtojmë shkrimin e shprehjes origjinale dhe opsionet e propozuara:

3. Jepet një fragment i tabelës së vërtetës së shprehjes F:

Cila shprehje i përgjigjet F?


Le të përcaktojmë vlerat e këtyre shprehjeve për vlerat e specifikuara të argumenteve:

    Njohja me temën e mësimit, prezantimi i materialit të ri (30 minuta)

Ne vazhdojmë të studiojmë bazat e logjikës dhe temën e mësimit tonë të sotëm "Zgjidhja e ekuacioneve logjike". Pas studimit të kësaj teme, do të mësoni mënyrat themelore për zgjidhjen e ekuacioneve logjike, do të fitoni aftësitë për të zgjidhur këto ekuacione duke përdorur gjuhën e algjebrës logjike dhe aftësinë për të kompozuar një shprehje logjike në tabelën e së vërtetës.

1. Zgjidh ekuacionin logjik

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

Shkruani përgjigjen tuaj si një varg prej katër karakteresh: vlerat e variablave K, L, M dhe N (në atë renditje). Kështu, për shembull, rreshtit 1101 i përgjigjet K=1, L=1, M=0, N=1.

Vendimi:

Le të transformojmë shprehjen(¬K M) → (¬L M N)

Shprehja është e rreme kur të dy termat janë false. Termi i dytë është i barabartë me 0 nëse M=0, N=0, L=1. Në termin e parë, K = 0, pasi M = 0, dhe
.

Përgjigje: 0100

2. Sa zgjidhje ka ekuacioni (shënoni vetëm numrin në përgjigjen tuaj)?

Zgjidhje: transformoni shprehjen

(A+B)*(C+D)=1

A+B=1 dhe C+D=1

Metoda 2: përpilimi i një tabele të së vërtetës

3 mënyra: ndërtimi i SDNF - një formë normale e përsosur ndarëse për një funksion - një ndarje e lidhëzave të plota të rregullta elementare.

Le të transformojmë shprehjen origjinale, hapim kllapat për të marrë ndarjen e lidhëzave:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Le t'i plotësojmë lidhëzat me lidhëzat e plota (produkti i të gjitha argumenteve), hapni kllapat:

Konsideroni të njëjtat lidhje:

Si rezultat, marrim një SDNF që përmban 9 lidhje. Prandaj, tabela e së vërtetës për këtë funksion ka një vlerë 1 në 9 rreshta nga 2 4 = 16 grupe vlerash të ndryshueshme.

3. Sa zgjidhje ka ekuacioni (shënoni vetëm numrin në përgjigjen tuaj)?

Le të thjeshtojmë shprehjen:

,

3 mënyra: ndërtimi i SDNF

Konsideroni të njëjtat lidhje:

Si rezultat, marrim një SDNF që përmban 5 lidhje. Prandaj, tabela e së vërtetës për këtë funksion ka një vlerë 1 në 5 rreshta me 2 4 = 16 grupe vlerash të ndryshueshme.

Ndërtimi i një shprehjeje logjike sipas tabelës së së vërtetës:

për çdo rresht të tabelës së së vërtetës që përmban 1, ne përpilojmë produktin e argumenteve, dhe ndryshoret e barabarta me 0 përfshihen në produktin me mohim, dhe variablat e barabartë me 1 - pa mohim. Shprehja e dëshiruar F do të përbëhet nga shuma e produkteve të fituara. Pastaj, nëse është e mundur, kjo shprehje duhet të thjeshtohet.

Shembull: jepet tabela e së vërtetës së një shprehjeje. Ndërtoni një shprehje logjike.

Vendimi:

3. Detyrë shtëpie (5 minuta)

    Zgjidhe ekuacionin:

    Sa zgjidhje ka ekuacioni (përgjigjuni vetëm numrit)?

    Sipas tabelës së dhënë të së vërtetës, bëni një shprehje logjike dhe

thjeshtoje atë.

Postime të ngjashme