Metódy riešenia sústav logických rovníc. Metódy riešenia sústav logických rovníc

Metódy riešenia sústav logických rovníc

Systém logických rovníc môžete vyriešiť napríklad pomocou pravdivostnej tabuľky (ak počet premenných nie je príliš veľký) alebo pomocou rozhodovacieho stromu, pričom každú rovnicu najprv zjednodušíte.

1. Variabilná metóda výmeny.

Zavedenie nových premenných vám umožňuje zjednodušiť systém rovníc a znížiť počet neznámych.Nové premenné musia byť na sebe nezávislé. Po vyriešení zjednodušeného systému sa musíme vrátiť k pôvodným premenným.

Uvažujme o aplikácii tejto metódy na konkrétnom príklade.

Príklad.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Riešenie:

Zavedme nové premenné: A=(X1≡ X2); B = (X3 = X4); С=(X5 ≡ X6); D = (X7 = X8); E = (X9 = X10).

(Pozor! Každá z premenných x1, x2, ..., x10 musí byť zahrnutá len v jednej z nových premenných A, B, C, D, E, t.j. nové premenné sú od seba nezávislé).

Potom bude systém rovníc vyzerať takto:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Zostavme rozhodovací strom pre výsledný systém:

Uvažujme rovnicu A=0, t.j. (X1≡ X2) = 0. Má 2 korene:

		X1 ≡ X2

Z tej istej tabuľky je vidieť, že aj rovnica A=1 má 2 korene. Usporiadajme počet koreňov v rozhodovacom strome:

Ak chcete zistiť počet riešení jednej vetvy, musíte vynásobiť počet riešení na každej úrovni. Ľavá vetva má 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 32 roztokov; pravá vetva má tiež 32 riešení. Tie. celý systém má 32+32=64 riešení.

odpoveď: 64.

2. Spôsob uvažovania.

Náročnosť riešenia systémov logických rovníc spočíva v ťažkopádnosti úplného rozhodovacieho stromu. Metóda uvažovania vám umožňuje nepostaviť celý strom, ale pochopiť, koľko vetiev bude mať. Pozrime sa na túto metódu pomocou konkrétnych príkladov.

Príklad 1 Koľko rôznych množín hodnôt logických premenných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 spĺňa všetky nižšie uvedené podmienky?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

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

x1\/y1 = 1

Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt premenných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, pre ktoré je tento systém rovnosti splnený. Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie :

Prvá a druhá rovnica obsahujú nezávislé premenné, ktoré súvisia s treťou podmienkou. Zostavme strom riešenia pre prvú a druhú rovnicu.

Na reprezentáciu stromu riešenia pre systém prvej a druhej rovnice musí každá vetva prvého stromu pokračovať stromom pre premenné pri . Takto skonštruovaný strom bude obsahovať 36 konárov. Niektoré z týchto vetiev nespĺňajú tretiu rovnicu systému. Na prvom strome si označme počet vetiev stromu"y" , ktoré spĺňajú tretiu rovnicu:

Vysvetlime si: na splnenie tretej podmienky, keď x1=0 musí byť y1=1, t.j. všetky vetvy stromu"X" , kde x1=0 môže pokračovať len jednou vetvou zo stromu"y" . A to len na jednu vetvu stromu"X" (vpravo) pasujú všetky vetvy stromu"y". Kompletný strom celého systému teda obsahuje 11 vetiev. Každá vetva predstavuje jedno riešenie pôvodnej sústavy rovníc. To znamená, že celý systém má 11 riešení.

odpoveď: 11.

Príklad 2 Koľko rôznych riešení má sústava rovníc?

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

kde x1, x2, …, x10 sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne sady hodnôt premenných, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie : Zjednodušme systém. Zostavme pravdivostnú tabuľku pre časť prvej rovnice:

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

Venujte pozornosť poslednému stĺpcu, zhoduje sa s výsledkom akcie X1 ≡ X10.

X1 ≡ X10

Po zjednodušení dostaneme:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Zvážte poslednú rovnicu:(X1 ≡ X10) = 0, t.j. x1 by sa nemalo zhodovať s x10. Aby sa prvá rovnica rovnala 1, musí byť rovnosť pravdivá(X1 ≡ X2) = 1, t.j. x1 sa musí zhodovať s x2.

Zostavme strom riešenia pre prvú rovnicu:

Zvážte druhú rovnicu: pre x10=1 a pre x2=0 zátvorkumusí sa rovnať 1 (t. j. x2 sa zhoduje s x3); pre x10=0 a pre x2=1 zátvorku(X2 ≡ X10)=0, čo znamená zátvorku (X2 ≡ X3) by sa malo rovnať 1 (t. j. x2 sa zhoduje s x3):

Týmto spôsobom vytvoríme rozhodovací strom pre všetky rovnice:

Sústava rovníc má teda len 2 riešenia.

odpoveď: 2.

Príklad 3

Koľko rôznych množín hodnôt logických premenných x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 spĺňa všetky nižšie uvedené podmienky?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Riešenie:

Zostavme strom riešenia pre 1. rovnicu:

Zvážte druhú rovnicu:

Keď x1=0 : druhá a tretia zátvorka sa budú rovnať 0; aby sa prvá zátvorka rovnala 1, y1=1, z1=1 (t.j. v tomto prípade - 1 riešenie)
Keď x1=1 : prvá zátvorka sa bude rovnať 0; druhý alebo tretia zátvorka sa musí rovnať 1; druhá zátvorka sa bude rovnať 1, keď y1=0 a z1=1; tretia zátvorka sa bude rovnať 1, keď y1=1 a z1=0 (t.j. v tomto prípade - 2 riešenia).

Podobne pre zostávajúce rovnice. Všimnime si výsledný počet riešení pre každý uzol stromu:

Ak chcete zistiť počet riešení pre každú vetvu, vynásobte výsledné čísla samostatne pre každú vetvu (zľava doprava).

1 vetva: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 roztok

Vetva 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 riešenia

3. vetva: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 riešenia

4. vetva: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 riešení

5. vetva: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 riešení

Výsledné čísla zrátajme: spolu je 31 riešení.

odpoveď: 31.

3. Prirodzený nárast počtu koreňov

V niektorých systémoch závisí počet koreňov nasledujúcej rovnice od počtu koreňov predchádzajúcej rovnice.

Príklad 1 Koľko rôznych množín hodnôt logických premenných x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 spĺňa všetky nižšie uvedené podmienky?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Poďme si to zjednodušiť prvá rovnica:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Potom bude mať systém tvar:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

Atď.

Každá ďalšia rovnica má o 2 korene viac ako predchádzajúca.

4 rovnica má 12 koreňov;

Rovnica 5 má 14 koreňov

Rovnica 8 má 20 koreňov.

Odpoveď: 20 koreňov.

Niekedy počet koreňov rastie podľa Fibonacciho zákona.

Riešenie sústavy logických rovníc si vyžaduje kreatívny prístup.

Tento materiál obsahuje prezentáciu, ktorá prezentuje metódy riešenia logických rovníc a sústav logických rovníc v úlohe B15 (č. 23, 2015) Jednotnej štátnej skúšky z informatiky. Je známe, že táto úloha je jednou z najťažších úloh jednotnej štátnej skúšky. Prezentácia môže byť užitočná pri vyučovaní na tému „Logika“ v špecializovaných triedach, ako aj pri príprave na jednotnú štátnu skúšku.

Stiahnuť ▼:

Náhľad:

Ak chcete použiť ukážky prezentácií, vytvorte si účet Google a prihláste sa doň: https://accounts.google.com

Popisy snímok:

Riešenie úlohy B15 (systémy logických rovníc) Vishnevskaya M.P., MAOU “Gymnasium No. 3” 18. novembra 2013, Saratov

Úloha B15 je jednou z najťažších na Jednotnej štátnej skúške z informatiky!!! Testujú sa tieto zručnosti: konvertovať výrazy obsahujúce logické premenné; opísať v prirodzenom jazyku množinu hodnôt logických premenných, pre ktoré je daná množina logických premenných pravdivá; spočítajte počet binárnych množín, ktoré spĺňajú dané podmienky. Najťažšia vec je, pretože... neexistujú žiadne formálne pravidlá, ako to urobiť, vyžaduje si to dohady.

Bez čoho sa nezaobídeš!

Symboly spojenie: A /\ B , A  B , AB , A & B, A a B disjunkcia: A \ / B , A + B , A | B , A alebo B negácia:  A , A, nie A ekvivalencia: A  B, A  B, A  B bez „alebo“: A  B , A xor B

Metóda nahradenia premennej Koľko rôznych množín hodnôt logických premenných x1, x2, ..., x9, x10 existuje, ktoré spĺňajú všetky podmienky uvedené nižšie: ((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 Odpoveď nemusí uvádzať všetky rôzne množiny x1, x2, …, x9, x10, pre ktoré tento systém rovnosti platí. Ako odpoveď musíte uviesť počet takýchto sád (demo verzia 2012)

Riešenie Krok 1. Zjednodušte zmenou premenných t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Po zjednodušení: (t1 \/ t2) /\ (¬t1 \/\ t2) = 1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Uvažujme jednu z rovníc: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Je zrejmé, že je to =1 iba vtedy, ak jedna z premenných je 0 a druhá je 1 Použime vzorec na vyjadrenie operácie XOR pomocou konjunkcie a disjunkcie: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Krok 2. Systémová analýza ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 0 1 0 Т1 .Do. tk = x2k-1 ≡ x2k (t1 = x1  x2,….), potom každá hodnota tk zodpovedá dvom párom hodnôt x2k-1 a x2k, napríklad: tk =0 zodpovedá dvom párom - (0 ,1) a (1, 0) , a tk =1 – dvojice (0,0) a (1,1).

Krok 3. Počítanie počtu riešení. Každé t má 2 riešenia, počet ts je 5. Teda. pre premenné t je 2 5 = 32 riešení. Ale pre každé t zodpovedá dvojica riešení x, t.j. pôvodný systém má 2*32 = 64 riešení. odpoveď: 64

Spôsob eliminácie časti riešení Koľko rôznych množín hodnôt logických premenných x1, x2, ..., x5, y1,y2,..., y5 existuje, ktoré spĺňajú všetky nižšie uvedené podmienky: (x1→ x2 )∧(x2→x3)∧(x3→x4)∧(x4→x5) =1; (y1→ y2)∧(y2→y3)∧(y3→y4) ∧(y4→y5) =1; y5 → x5 = 1. Odpoveď nemusí uvádzať všetky rôzne množiny x1, x2, ..., x5, y 1 , y2, ... , y5, pre ktoré tento systém rovnosti platí. V odpovedi musí byť uvedený počet takýchto sád.

Riešenie. Krok 1. Postupné riešenie rovníc 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 Prvá rovnica je konjunkcia viacerých operácií implikácie, rovná 1, t.j. každá z implikácií je pravdivá. Implikácia je nepravdivá iba v jednom prípade, keď 1  0, vo všetkých ostatných prípadoch (0  0, 0  1, 1  1) vráti operácia 1. Zapíšme si to do tabuľky:

Krok 1. Sekvenčné riešenie rovníc T.o. Získalo sa 6 sád riešení pre x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Podobne dospejeme k záveru, že pre y1, y2, y3, y4, y5 existuje rovnaká množina riešení. Pretože tieto rovnice sú nezávislé, t.j. nemajú spoločné premenné, potom riešenie tohto systému rovníc (bez zohľadnenia tretej rovnice) bude 6 * 6 = 36 párov „X“ a „Y“. Uvažujme tretiu rovnicu: y5→ x5 =1 Riešením sú dvojice: 0 0 0 1 1 1 Dvojica nie je riešením: 1 0

Porovnajme získané riešenia Kde y5 =1, x5=0 nie je vhodné. takýchto dvojíc je 5. Počet riešení sústavy: 36-5= 31. Odpoveď: Bolo treba 31 kombinatoriky!!!

Metóda dynamického programovania Koľko rôznych riešení má logická rovnica x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, kde x 1, x 2, …, x 6 sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne sady hodnôt premenných, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť množstvo takýchto sád.

Riešenie Krok 1. Analýza podmienky Vľavo v rovnici sú operácie implikácie zapísané postupne, priorita je rovnaká. Prepíšme: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 Poznámka! Každá nasledujúca premenná nezávisí od predchádzajúcej, ale od výsledku predchádzajúcej implikácie!

Krok 2. Odhalenie vzoru Uvažujme prvú implikáciu, X 1 → X 2. Tabuľka pravdy: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Z jednej 0 sme dostali 2 jednotky a z 1 dostali sme jednu 0 a jednu 1. Existuje len jedna 0 a tri 1, toto je výsledok prvej operácie.

Krok 2. Odhalenie vzoru Spojením x 3 s výsledkom prvej operácie dostaneme: 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 Od dvoch 0 – dvoch 1, od každého 1 (sú 3) jedna 0 a jedna 1 (3+3)

Krok 3. Odvodenie vzorca T.o. môžete vytvoriť vzorce na výpočet počtu núl N i a počtu jednotiek E i pre rovnicu s premennými i: ,

Krok 4. Vyplnenie tabuľky Vyplňte tabuľku zľava doprava pre i = 6, pričom vypočítame počet núl a jednotiek pomocou vyššie uvedených vzorcov; tabuľka ukazuje, ako je nasledujúci stĺpec zostavený z predchádzajúceho: počet premenných 1 2 3 4 5 6 Počet núl N i 1 1 3 5 11 21 Počet jednotiek E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Odpoveď: 43

Metóda využívajúca zjednodušenia logických výrazov Koľko rôznych riešení má rovnica ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 kde J, K, L, M, N sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt J, K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.

Riešenie Všimnite si, že J → K = ¬ J  K Zavedme zmenu premenných: J → K=A, M  N  L =B Prepíšme rovnicu s prihliadnutím na zmenu: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Je zrejmé, že A  B pre rovnaké hodnoty A a B 6. Uvažujme poslednú implikáciu M → J = 1 Toto je možné, ak: M= J=0 M=0, J=1 M=J=1

Riešenie Pretože A  B, potom Keď M=J=0 dostaneme 1 + K=0. Žiadne riešenia. Keď M=0, J=1 dostaneme 0 + K=0, K=0 a N a L sú ľubovoľné, 4 riešenia: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Riešenie 10. Keď M=J=1 dostaneme 0+K=1 *N * L, alebo K=N*L, 4 riešenia: 11. Celkom má 4+4=8 riešení Odpoveď: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Zdroje informácií: O.B. Bogomolová, D.Yu. Usenkov. B15: nové úlohy a nové riešenia // Informatika, č. 6, 2012, s. 35 – 39. K.Yu. Polyakov. Logické rovnice // Informatika, č. 14, 2011, s. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektronický zdroj]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronický zdroj].

Účel služby. Online kalkulačka je určená pre zostavenie pravdivostnej tabuľky pre logický výraz.
Pravdivostná tabuľka – tabuľka obsahujúca všetky možné kombinácie vstupných premenných a im zodpovedajúce výstupné hodnoty.
Pravdivostná tabuľka obsahuje 2n riadkov, kde n je počet vstupných premenných a n+m sú stĺpce, kde m sú výstupné premenné.

Inštrukcie. Pri zadávaní z klávesnice používajte nasledujúce konvencie:

Napríklad logický výraz abc+ab~c+a~bc je potrebné zadať takto: a*b*c+a*b=c+a=b*c
Na zadávanie údajov vo forme logického diagramu použite túto službu.

Pravidlá pre zadávanie logickej funkcie

Namiesto symbolu v (disjunkcia, OR) použite znak +.
Nie je potrebné špecifikovať označenie funkcie pred logickou funkciou. Napríklad namiesto F(x,y)=(x|y)=(x^y) musíte jednoducho zadať (x|y)=(x^y) .
Maximálny počet premenných je 10.

Návrh a analýza počítačových logických obvodov sa vykonáva pomocou špeciálneho odvetvia matematiky - logickej algebry. V algebre logiky možno rozlíšiť tri hlavné logické funkcie: „NOT“ (negácia), „AND“ (konjunkcia), „ALEBO“ (disjunkcia).
Na vytvorenie akéhokoľvek logického zariadenia je potrebné určiť závislosť každej z výstupných premenných od existujúcich vstupných premenných; táto závislosť sa nazýva spínacia funkcia alebo funkcia logickej algebry.
Funkcia logickej algebry sa nazýva úplne definovaná, ak sú zadané všetky jej hodnoty 2n, kde n je počet výstupných premenných.
Ak nie sú definované všetky hodnoty, funkcia sa nazýva čiastočne definovaná.
Zariadenie sa nazýva logické, ak je jeho stav opísaný pomocou funkcie logickej algebry.
Na reprezentáciu funkcie logickej algebry sa používajú nasledujúce metódy:
V algebraickej forme môžete zostaviť obvod logického zariadenia pomocou logických prvkov.

Obrázok 1 - Schéma logického zariadenia

Všetky operácie algebry logiky sú definované pravdivostné tabuľky hodnoty. Pravdivostná tabuľka určuje výsledok operácie pre každý je možný x logické hodnoty pôvodných príkazov. Počet volieb odrážajúcich výsledok aplikovania operácií bude závisieť od počtu príkazov v logickom výraze. Ak je počet výrokov v logickom výraze N, potom pravdivostná tabuľka bude obsahovať 2 N riadkov, pretože existuje 2 N rôznych kombinácií možných hodnôt argumentov.

Operácia NOT - logická negácia (inverzia)

Logická operácia NIE JE aplikovaná na jeden argument, ktorým môže byť jednoduchý alebo zložitý logický výraz. Výsledok operácie NIE JE nasledujúci:

ak je pôvodný výraz pravdivý, potom výsledok jeho negácie bude nepravdivý;
ak je pôvodný výraz nepravdivý, potom výsledok jeho negácie bude pravdivý.

Nasledujúce konvencie nie sú akceptované pre operáciu negácie:
nie A, Ā, nie A, ¬A, !A
Výsledok operácie negácie NIE JE určený nasledujúcou pravdivostnou tabuľkou:

A	nie A
0	1
1	0

Výsledok operácie negácie je pravdivý, keď je pôvodný výrok nepravdivý, a naopak.

Operácia OR - logické sčítanie (rozdelenie, spojenie)

Logická operácia OR vykonáva funkciu spojenia dvoch príkazov, ktoré môžu byť jednoduchým alebo zložitým logickým výrazom. Príkazy, ktoré sú východiskovými bodmi pre logickú operáciu, sa nazývajú argumenty. Výsledkom operácie OR je výraz, ktorý bude pravdivý vtedy a len vtedy, ak bude pravdivý aspoň jeden z pôvodných výrazov.
Použité označenia: A alebo B, A V B, A alebo B, A||B.
Výsledok operácie OR určuje nasledujúca pravdivostná tabuľka:
Výsledok operácie OR je pravdivý, keď A je pravda, alebo B je pravda, alebo A aj B sú pravdivé, a nepravda, keď sú argumenty A a B nepravdivé.

Operácia AND - logické násobenie (konjunkcia)

Logická operácia AND plní funkciu prieniku dvoch tvrdení (argumentov), ktoré môžu byť jednoduchým alebo zložitým logickým výrazom. Výsledkom operácie AND je výraz, ktorý bude pravdivý vtedy a len vtedy, ak sú pravdivé oba pôvodné výrazy.
Použité označenia: A a B, A Λ B, A & B, A a B.
Výsledok operácie AND je určený nasledujúcou pravdivostnou tabuľkou:

A	B	A a B
0	0	0
0	1	0
1	0	0
1	1	1

Výsledok operácie AND je pravdivý vtedy a len vtedy, ak sú výroky A a B pravdivé a nepravdivé vo všetkých ostatných prípadoch.

Operácia „AK-POTOM“ - logický dôsledok (implicita)

Táto operácia spája dva jednoduché logické výrazy, z ktorých prvý je podmienkou a druhý je dôsledkom tejto podmienky.
Použité označenia:
ak A, potom B; A znamená B; ak A, potom B; A→B.
Tabuľka pravdy:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Výsledok operácie implikácie je nepravdivý iba vtedy, ak je premisa A pravdivá a záver B (dôsledok) nepravdivý.

Operácia „A vtedy a len vtedy, keď B“ (ekvivalencia, ekvivalencia)

Použité označenie: A ↔ B, A ~ B.
Tabuľka pravdy:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Operácia „Addition modulo 2“ (XOR, exkluzívna alebo striktná disjunkcia)

Použitý zápis: A XOR B, A ⊕ B.
Tabuľka pravdy:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Výsledok operácie ekvivalencie je pravdivý iba vtedy, ak A aj B sú pravdivé alebo nepravdivé súčasne.

Priorita logických operácií

Akcie v zátvorkách
Inverzia
Konjunkcia (&)
Disjunkcia (V), exkluzívne OR (XOR), súčet modulo 2
Implikácia (→)
Ekvivalencia (↔)

Dokonalá disjunktívna normálna forma

Dokonalá disjunktívna normálna forma vzorca(SDNF) je ekvivalentný vzorec, ktorý je disjunkciou elementárnych spojok a má nasledujúce vlastnosti:

Každý logický člen vzorca obsahuje všetky premenné obsiahnuté vo funkcii F(x 1,x 2,...x n).
Všetky logické pojmy vzorca sú odlišné.
Ani jeden logický člen neobsahuje premennú a jej negáciu.
Žiadny logický výraz vo vzorci neobsahuje tú istú premennú dvakrát.

SDNF možno získať buď pomocou pravdivostných tabuliek alebo pomocou ekvivalentných transformácií.
Pre každú funkciu sú SDNF a SCNF jednoznačne definované až do permutácie.

Dokonalá konjunktívna normálna forma

Dokonalá konjunktívna normálna forma vzorca (SCNF) Toto je ekvivalentný vzorec, ktorý je konjunkciou elementárnych disjunkcií a spĺňa vlastnosti:

Všetky elementárne disjunkcie obsahujú všetky premenné obsiahnuté vo funkcii F(x 1 ,x 2 ,...x n).
Všetky elementárne disjunkcie sú odlišné.
Každá elementárna disjunkcia obsahuje raz premennú.
Ani jedna elementárna disjunkcia neobsahuje premennú a jej negáciu.

Metódy riešenia sústav logických rovníc

Kirgizová E.V., Nemková A.E.

Pedagogický inštitút Lesosibirsk –

pobočka Sibírskej federálnej univerzity v Rusku

Schopnosť dôsledne myslieť, presvedčivo uvažovať, vytvárať hypotézy a vyvracať negatívne závery neprichádza sama od seba, túto zručnosť rozvíja veda o logike. Logika je veda, ktorá študuje metódy na zistenie pravdivosti alebo nepravdivosti niektorých tvrdení na základe pravdivosti alebo nepravdivosti iných tvrdení.

Zvládnutie základov tejto vedy je nemožné bez riešenia logických problémov. Testovanie rozvoja zručností na uplatnenie svojich vedomostí v novej situácii sa uskutočňuje prostredníctvom absolvovania. Ide najmä o schopnosť riešiť logické problémy. Úlohy B15 v jednotnej štátnej skúške sú úlohy so zvýšenou zložitosťou, pretože obsahujú systémy logických rovníc. Existujú rôzne spôsoby riešenia systémov logických rovníc. Ide o redukciu na jednu rovnicu, zostavenie pravdivostnej tabuľky, rozklad, sekvenčné riešenie rovníc atď.

Úloha:Vyriešte sústavu logických rovníc:

Uvažujme redukčná metóda na jednu rovnicu . Táto metóda zahŕňa transformáciu logických rovníc tak, aby sa ich pravá strana rovnala pravdivostnej hodnote (tj 1). Na tento účel použite operáciu logickej negácie. Potom, ak rovnice obsahujú zložité logické operácie, nahradíme ich základnými: „A“, „ALEBO“, „NIE“. Ďalším krokom je spojenie rovníc do jednej, ekvivalentnej systému, pomocou logickej operácie „AND“. Potom by ste mali transformovať výslednú rovnicu na základe zákonov logickej algebry a získať konkrétne riešenie systému.

Riešenie 1:Použite inverziu na obe strany prvej rovnice:

Predstavme si implikáciu prostredníctvom základných operácií „ALEBO“ a „NIE“:

Keďže ľavé strany rovníc sa rovnajú 1, môžeme ich spojiť pomocou operácie „AND“ do jednej rovnice, ktorá je ekvivalentná pôvodnému systému:

Otvoríme prvú zátvorku podľa De Morganovho zákona a transformujeme získaný výsledok:

Výsledná rovnica má jedno riešenie: A= 0, B = 0 a C = 1.

Ďalšia metóda je vytváranie pravdivostných tabuliek . Keďže logické veličiny majú len dve hodnoty, môžete jednoducho prejsť všetky možnosti a nájsť medzi nimi tie, pre ktoré daný systém rovníc vyhovuje. To znamená, že zostavíme jednu spoločnú pravdivostnú tabuľku pre všetky rovnice systému a nájdeme riadok s požadovanými hodnotami.

Riešenie 2:Vytvorme pravdivostnú tabuľku pre systém:








0	0	1	1	0	1

Riadok, pre ktorý sú splnené podmienky úlohy, je zvýraznený tučným písmom. Takže A = 0, B = 0 a C = 1.

spôsob rozklad . Cieľom je zafixovať hodnotu jednej z premenných (nastaviť ju na 0 alebo 1) a tým zjednodušiť rovnice. Potom môžete opraviť hodnotu druhej premennej atď.

Riešenie 3: Nechaj A = 0, potom:

Z prvej rovnice dostaneme B =0 a od druhého – C=1. Riešenie sústavy: A = 0, B = 0 a C = 1.

Môžete tiež použiť metódu sekvenčné riešenie rovníc v každom kroku pridanie jednej premennej do uvažovanej množiny. Na to je potrebné transformovať rovnice tak, aby sa premenné zadávali v abecednom poradí. Ďalej vytvoríme rozhodovací strom, do ktorého postupne pridávame premenné.

Prvá rovnica systému závisí iba od A a B a druhá rovnica od A a C. Premenná A môže mať 2 hodnoty 0 a 1:

Z prvej rovnice to vyplýva , takže keď A = 0 a dostaneme B = 0 a pre A = 1 máme B = 1. Prvá rovnica má teda dve riešenia vzhľadom na premenné A a B.

Ukážme si druhú rovnicu, z ktorej určíme hodnoty C pre každú možnosť. Keď A = 1, implikácia nemôže byť nepravdivá, to znamená, že druhá vetva stromu nemá riešenie. O A= 0 dostaneme jediné riešenie C= 1 :

Takto sme dostali riešenie sústavy: A = 0, B = 0 a C = 1.

Na Jednotnej štátnej skúške z informatiky je veľmi často potrebné určiť počet riešení sústavy logických rovníc bez toho, aby sa nachádzali samotné riešenia, existujú na to aj určité metódy. Hlavným spôsobom, ako nájsť počet riešení systému logických rovníc, je nahradenie premenných. Najprv musíte každú z rovníc čo najviac zjednodušiť na základe zákonov logickej algebry a potom nahradiť zložité časti rovníc novými premennými a určiť počet riešení nového systému. Potom sa vráťte k náhrade a určite počet riešení pre ňu.

Úloha:Koľko riešení má rovnica ( A → B) + (C → D ) = 1? Kde A, B, C, D sú logické premenné.

Riešenie:Predstavme si nové premenné: X = A → B a Y = C → D . S prihliadnutím na nové premenné bude rovnica napísaná takto: X + Y = 1.

Disjunkcia je pravdivá v troch prípadoch: (0;1), (1;0) a (1;1), zatiaľ čo X a Y je implikácia, to znamená, že v troch prípadoch je pravdivá a v jednom nepravdivá. Preto prípad (0;1) bude zodpovedať trom možným kombináciám parametrov. Prípad (1;1) – bude zodpovedať deviatim možným kombináciám parametrov pôvodnej rovnice. To znamená, že celkové možné riešenia tejto rovnice sú 3+9=15.

Ďalším spôsobom, ako určiť počet riešení systému logických rovníc, je binárny strom. Pozrime sa na túto metódu pomocou príkladu.

Úloha:Koľko rôznych riešení má systém logických rovníc:

Daný systém rovníc je ekvivalentný rovnici:

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

Predstierajme toX 1 – je pravda, potom to z prvej rovnice dostanemeX 2 tiež pravda, od druhého -X 3 =1 a tak ďalej až do x m= 1. Takže množina (1; 1; …; 1) z m jednotiek je riešením systému. Nechaj to terazX 1 =0, potom z prvej rovnice mámeX 2 =0 alebo X 2 =1.

Kedy X 2 true, získame, že zostávajúce premenné sú tiež pravdivé, to znamená, že množina (0; 1; ...; 1) je riešením systému. OX 2 =0 chápeme to X 3 =0 alebo X 3 = a tak ďalej. Pokračovaním k poslednej premennej zistíme, že riešením rovnice sú nasledujúce množiny premenných ( m +1 riešenie v každom riešení m premenné hodnoty):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Tento prístup je dobre ilustrovaný zostrojením binárneho stromu. Počet možných riešení je počet rôznych vetiev zostrojeného stromu. Je ľahké vidieť, že je to rovnaké m + 1.

Premenné	Strom	Počet riešení
x 1
x 2
x 3

V prípade ťažkostí pri uvažovaní a zostavovaní rozhodovacieho stromu môžete hľadať riešenie pomocou pravdivostné tabuľky, pre jednu alebo dve rovnice.

Prepíšme sústavu rovníc do tvaru:

A vytvorte pravdivostnú tabuľku samostatne pre jednu rovnicu:

x 1	x 2	(x 1 → x 2)

Vytvorme pravdivostnú tabuľku pre dve rovnice:

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

Ďalej môžete vidieť, že jedna rovnica platí v nasledujúcich troch prípadoch: (0; 0), (0; 1), (1; 1). Systém dvoch rovníc platí v štyroch prípadoch (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). V tomto prípade je hneď jasné, že existuje riešenie pozostávajúce len z núl a viac m riešenia, v ktorých sa pridáva jedna jednotka naraz, začínajúc od poslednej pozície, kým sa nezaplnia všetky možné miesta. Dá sa predpokladať, že všeobecné riešenie bude mať rovnakú formu, ale aby sa takýto prístup stal riešením, je potrebný dôkaz o správnosti predpokladu.

Aby som zhrnul všetky vyššie uvedené, rád by som upriamil vašu pozornosť na skutočnosť, že nie všetky diskutované metódy sú univerzálne. Pri riešení každého systému logických rovníc je potrebné vziať do úvahy jeho vlastnosti, na základe ktorých by sa mala zvoliť metóda riešenia.

Literatúra:

1. Logické problémy / O.B. Bogomolov – 2. vyd. – M.: BINOM. Laboratórium vedomostí, 2006. – 271 s.: ill.

2. Polyakov K.Yu. Sústavy logických rovníc / Náučné a metodické noviny pre učiteľov informatiky: Informatika č.14,2011.

Existujú rôzne spôsoby riešenia systémov logických rovníc. Ide o redukciu na jednu rovnicu, zostavenie pravdivostnej tabuľky a rozklad.

Úloha: Vyriešte sústavu logických rovníc:

Riešenie 1: Použite inverziu na obe strany prvej rovnice:

Predstavme si implikáciu prostredníctvom základných operácií „ALEBO“ a „NIE“:

Keďže ľavé strany rovníc sa rovnajú 1, môžeme ich spojiť pomocou operácie „AND“ do jednej rovnice, ktorá je ekvivalentná pôvodnému systému:

Otvoríme prvú zátvorku podľa De Morganovho zákona a transformujeme získaný výsledok:

Výsledná rovnica má jedno riešenie: A =0, B=0 a C=1.

Riešenie 2: Vytvorme pravdivostnú tabuľku pre systém:








0	0	1	1	0	1

Riadok, pre ktorý sú splnené podmienky úlohy, je zvýraznený tučným písmom. Takže A=0, B=0 a C=1.

spôsob rozklad . Cieľom je zafixovať hodnotu jednej z premenných (nastaviť ju na 0 alebo 1) a tým zjednodušiť rovnice. Potom môžete opraviť hodnotu druhej premennej atď.

Riešenie 3: Nech A = 0, potom:

Z prvej rovnice dostaneme B = 0 a z druhej - C = 1. Riešenie sústavy: A = 0, B = 0 a C = 1.

Na Jednotnej štátnej skúške z informatiky je veľmi často potrebné určiť počet riešení sústavy logických rovníc bez toho, aby sa nachádzali samotné riešenia, existujú na to aj určité metódy. Hlavným spôsobom, ako nájsť počet riešení systému logických rovníc, jenahradenie premenných. Najprv musíte každú z rovníc čo najviac zjednodušiť na základe zákonov logickej algebry a potom nahradiť zložité časti rovníc novými premennými a určiť počet riešení nového systému. Potom sa vráťte k náhrade a určite počet riešení pre ňu.

Úloha: Koľko riešení má rovnica (A →B) + (C →D) = 1? Kde A, B, C, D sú logické premenné.

Riešenie: Zavedme nové premenné: X = A →B a Y = C →D. Ak vezmeme do úvahy nové premenné, rovnica bude napísaná ako: X + Y = 1.

Disjunkcia je pravdivá v troch prípadoch: (0;1), (1;0) a (1;1), zatiaľ čo X a Y sú implikácie, to znamená, že je pravdivá v troch prípadoch a nepravdivá v jednom. Preto prípad (0;1) bude zodpovedať trom možným kombináciám parametrov. Prípad (1;1) – bude zodpovedať deviatim možným kombináciám parametrov pôvodnej rovnice. To znamená, že celkové možné riešenia tejto rovnice sú 3+9=15.

Ďalším spôsobom, ako určiť počet riešení systému logických rovníc, je binárny strom. Pozrime sa na túto metódu pomocou príkladu.

Úloha: Koľko rôznych riešení má systém logických rovníc:

Daný systém rovníc je ekvivalentný rovnici:

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

Predstierajme to X 1 – je pravda, potom to z prvej rovnice dostaneme X 2 tiež pravda, od druhého - X 3 =1 a tak ďalej až do x m= 1. To znamená, že množina (1; 1; …; 1) m jednotiek je riešením systému. Nechaj to teraz X 1 =0, potom z prvej rovnice máme X 2 =0 alebo X 2 =1.

Kedy X 2 true, získame, že zostávajúce premenné sú tiež pravdivé, to znamená, že množina (0; 1; ...; 1) je riešením systému. O X 2 =0 chápeme to X 3 =0 alebo X 3 = a tak ďalej. Pokračovaním k poslednej premennej zistíme, že riešenia rovnice sú nasledujúce množiny premenných (m + 1 riešenie, každé riešenie obsahuje m hodnôt premenných):