Metódy riešenia sústav logických rovníc v informatike. Systémy logických rovníc v úlohách jednotnej štátnej skúšky z informatiky
Téma lekcie: Riešenie logických rovníc
Vzdelávacie – štúdium metód riešenia logických rovníc, rozvíjanie zručností v riešení logických rovníc a zostrojovanie logického výrazu pomocou pravdivostnej tabuľky;vývojové - vytvárať podmienky pre rozvoj kognitívneho záujmu žiakov, podporovať rozvoj pamäti, pozornosti a logického myslenia;
Vzdelávacie : podporovať schopnosť počúvať názory iných, pestovanie vôle a vytrvalosti dosiahnuť konečné výsledky.
Typ lekcie: kombinovaná lekcia
Vybavenie: počítač, multimediálny projektor, prezentácia 6.
Počas vyučovania
Opakovanie a aktualizácia základných vedomostí. Kontrola domácich úloh (10 minút)
V predchádzajúcich lekciách sme sa oboznámili so základnými zákonmi logickej algebry a naučili sme sa tieto zákony využívať na zjednodušenie logických výrazov.
Pozrime sa na našu domácu úlohu o zjednodušení logických výrazov:
1. Ktoré z nasledujúcich slov spĺňa logickú podmienku:
(prvopísmenová spoluhláska→druhá písmenová spoluhláska)٨ (posledná samohláska → predposledná samohláska)? Ak existuje niekoľko takýchto slov, uveďte najmenšie z nich.
1) ANNA 2) MARIA 3) OLEG 4) ŠTEPÁN
Predstavme si nasledujúci zápis:
A – spoluhláska prvého písmena
B – spoluhláska druhého písmena
S – samohláska posledného písmena
D – predposledné samohláskové písmeno
Urobme si výraz:
Urobme si tabuľku:
2. Uveďte, ktorý logický výraz je ekvivalentný výrazu
Zjednodušme nahrávanie pôvodného výrazu a navrhovaných možností:
3. Daný fragment pravdivostnej tabuľky výrazu F:
Ktorý výraz sa zhoduje s F?
Určme hodnoty týchto výrazov pre zadané hodnoty argumentov:
Úvod do témy lekcie, prezentácia nového materiálu (30 minút)
Pokračujeme v štúdiu základov logiky a témou našej dnešnej lekcie je „Riešenie logických rovníc“. Po preštudovaní tejto témy sa naučíte základné spôsoby riešenia logických rovníc, získate zručnosti na riešenie týchto rovníc pomocou jazyka logickej algebry a schopnosť zostaviť logický výraz pomocou pravdivostnej tabuľky.
1. Vyriešte logickú rovnicu
(¬K M) → (¬L M N) = 0
Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.
Riešenie:
Transformujme výraz(¬K M) → (¬L M N)
Výraz je nepravdivý, keď sú oba pojmy nepravdivé. Druhý člen sa rovná 0, ak M = 0, N = 0, L = 1. V prvom člene K = 0, keďže M = 0, a 
.
Odpoveď: 0100
2. Koľko riešení má rovnica (uveďte v odpovedi len číslo)?
Riešenie: transformujte výraz
(A + B)* (C + D) = 1
A + B = 1 a C + D = 1
Metóda 2: zostavenie pravdivostnej tabuľky
3 spôsob: konštrukcia SDNF - dokonalá disjunktívna normálna forma pre funkciu - disjunkcia úplných pravidelných elementárnych konjunkcií.Transformujme pôvodný výraz, otvorme zátvorky, aby sme získali disjunkciu spojok:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Doplňme spojky na úplné spojky (súčin všetkých argumentov), otvorme zátvorky:
Zoberme do úvahy rovnaké spojky:
Výsledkom je, že získame SDNF obsahujúci 9 konjunkcií. Pravdivostná tabuľka pre túto funkciu má teda hodnotu 1 v 9 riadkoch 2 4 =16 množín hodnôt premenných.
3. Koľko riešení má rovnica (uveďte v odpovedi len číslo)?
Zjednodušme výraz:
,
3 spôsob: výstavba SDNF
Zoberme do úvahy rovnaké spojky:
Výsledkom je, že získame SDNF obsahujúci 5 konjunkcií. Pravdivostná tabuľka pre túto funkciu má teda hodnotu 1 na 5 riadkoch 2 4 =16 množín hodnôt premenných.
Zostrojenie logického výrazu pomocou pravdivostnej tabuľky:
pre každý riadok pravdivostnej tabuľky obsahujúcej 1 zostavíme súčin argumentov a premenné rovné 0 sú zahrnuté v súčine s negáciou a premenné rovné 1 sú zahrnuté bez negácie. Požadovaný výraz F bude zložený zo súčtu výsledných produktov. Potom, ak je to možné, tento výraz by sa mal zjednodušiť.
Príklad: je uvedená pravdivostná tabuľka výrazu. Zostavte logický výraz.
Riešenie:3. domáca úloha (5 minút)
Vyriešte rovnicu:
Koľko riešení má rovnica (uveďte v odpovedi iba číslo)?
Pomocou danej pravdivostnej tabuľky zostrojte logický výraz a
zjednodušiť to.
Používanie rovníc je v našich životoch veľmi rozšírené. Používajú sa pri mnohých výpočtoch, stavbe konštrukcií a dokonca aj v športe. Človek používal rovnice v staroveku a odvtedy sa ich používanie len zvyšuje. V matematike existujú určité problémy, ktoré sa zaoberajú výrokovou logikou. Na vyriešenie tohto druhu rovnice je potrebné mať určité znalosti: znalosť zákonov výrokovej logiky, znalosť pravdivostných tabuliek logických funkcií 1 alebo 2 premenných, metódy na prevod logických výrazov. Okrem toho musíte poznať nasledujúce vlastnosti logických operácií: konjunkcia, disjunkcia, inverzia, implikácia a ekvivalencia.
Akákoľvek logická funkcia \premenných - \môže byť špecifikovaná pravdivostnou tabuľkou.
Poďme vyriešiť niekoľko logických rovníc:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\rightharpoondown X9\vee X10=1\]
Začnime riešenie s \[X1\] a určme, aké hodnoty môže mať táto premenná: 0 a 1. Ďalej zvážime každú z vyššie uvedených hodnôt a uvidíme, čo môže byť \[X2.\].
Ako vidno z tabuľky, naša logická rovnica má 11 riešení.
Kde môžem vyriešiť logickú rovnicu online?
Rovnicu môžete vyriešiť na našej webovej stránke https://site. Bezplatný online riešiteľ vám umožní vyriešiť online rovnice akejkoľvek zložitosti v priebehu niekoľkých sekúnd. Všetko, čo musíte urobiť, je jednoducho zadať svoje údaje do riešiteľa. Na našej stránke si môžete pozrieť aj video návod a naučiť sa riešiť rovnicu. A ak máte stále otázky, môžete sa ich opýtať v našej skupine VKontakte http://vk.com/pocketteacher. Pridajte sa do našej skupiny, vždy vám radi pomôžeme.
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, kde J, K, L, M, N sú logické premenné?
Riešenie.
Výraz (N ∨ ¬N) teda platí pre ľubovoľné N
J ∧ ¬K ∧ L ∧ ¬M = 0.
Aplikujme negáciu na obe strany logickej rovnice a použijeme De Morganov zákon ¬ (A ∧ B) = ¬ A ∨ ¬ B. Dostaneme ¬J ∨ K ∨ ¬L ∨ M = 1.
Logický súčet sa rovná 1, ak sa aspoň jeden z jeho základných výrokov rovná 1. Výsledná rovnica je teda splnená ľubovoľnou kombináciou logických premenných okrem prípadu, keď sa všetky veličiny zahrnuté v rovnici rovnajú 0. Každá z 4 premenné sa môžu rovnať buď 1 alebo 0, preto sú všetky možné kombinácie 2·2·2·2 = 16. Preto rovnica má 16 −1 = 15 riešení.
Zostáva poznamenať, že nájdených 15 riešení zodpovedá ktorejkoľvek z dvoch možných hodnôt logickej premennej N, takže pôvodná rovnica má 30 riešení.
odpoveď: 30
Koľko rôznych riešení má rovnica?
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (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.
Používame vzorce A → B = ¬A ∨ B a ¬(A ∨ B) = ¬A ∧ ¬B
Zoberme si prvý podvzorec:
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Zoberme si druhý podvzorec
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬
Zoberme si tretí podvzorec
1) M → J = 1 teda,
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Poďme kombinovať:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 teda 4 riešenia.
(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
Poďme kombinovať:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L teda 4 riešenia.
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.
Odpoveď: 4 + 4 = 8.
odpoveď: 8
Koľko rôznych riešení má rovnica?
((K ∨ L) → (L ∧ M ∧ N)) = 0
kde K, L, M, N sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Riešenie.
Prepíšme rovnicu pomocou jednoduchšieho zápisu operácií:
((K + L) -> (L M N)) = 0
1) z pravdivostnej tabuľky operácie „implikácia“ (pozri prvý problém) vyplýva, že táto rovnosť je pravdivá vtedy a len vtedy, ak súčasne
K + L = 1 a LMN = 0
2) z prvej rovnice vyplýva, že aspoň jedna z premenných, K alebo L, sa rovná 1 (alebo obe spolu); pozrime sa teda na tri prípady
3) ak K = 1 a L = 0, potom je druhá rovnosť splnená pre všetky M a N; keďže existujú 4 kombinácie dvoch booleovských premenných (00, 01, 10 a 11), máme 4 rôzne riešenia
4) ak K = 1 a L = 1, potom druhá rovnosť platí pre M · N = 0; sú 3 takéto kombinácie (00, 01 a 10), máme ešte 3 riešenia
5) ak K = 0, potom L = 1 (z prvej rovnice); v tomto prípade je splnená druhá rovnosť, keď M · N = 0; sú 3 takéto kombinácie (00, 01 a 10), máme ešte 3 riešenia
6) celkovo dostaneme 4 + 3 + 3 = 10 riešení.
odpoveď: 10
Koľko rôznych riešení má rovnica?
(K ∧ L) ∨ (M ∧ N) = 1
Riešenie.
Výraz je pravdivý v troch prípadoch, keď (K ∧ L) a (M ∧ N) sú rovné 01, 11, 10, v tomto poradí.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N sa rovnajú 1 a K a L sú čokoľvek okrem súčasnej 1. Preto existujú 3 riešenia.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 roztok.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 riešenia.
odpoveď: 7.
odpoveď: 7
Koľko rôznych riešení má rovnica?
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
kde X, Y, Z, P sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne súbory hodnôt, pre ktoré platí táto rovnosť. Ako odpoveď stačí uviesť počet takýchto sád.
Riešenie.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
Logické OR je nepravdivé iba v jednom prípade: keď sú oba výrazy nepravdivé.
teda
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Y = 1.
Preto existuje len jedno riešenie rovnice.
odpoveď: 1
Koľko rôznych riešení má rovnica?
(K ∨ L) ∧ (M ∨ N) = 1
kde K, L, M, N sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď stačí uviesť počet takýchto sád.
Riešenie.
Logické A je pravdivé iba v jednom prípade: keď sú všetky výrazy pravdivé.
K ∨ L = 1, M ∨ N = 1.
Každá rovnica dáva 3 riešenia.
Uvažujme rovnicu A ∧ B = 1, ak A aj B nadobúdajú pravdivé hodnoty v troch prípadoch, potom má rovnica celkovo 9 riešení.
Preto je odpoveď 9.
odpoveď: 9
Koľko rôznych riešení má rovnica?
((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
kde A, B, C, D sú logické premenné?
Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt A, B, C, D, pre ktoré platí táto rovnosť. Ako odpoveď musíte uviesť počet takýchto sád.
Riešenie.
Logické „ALEBO“ je pravdivé, ak je pravdivé aspoň jedno z tvrdení.
(D ∧ ¬D) = 0 pre ľubovoľné D.
teda
(A -> B) - C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, čo nám dáva 3 možné riešenia pre každé D.
(D ∧ ¬ D)= 0 pre ľubovoľné D, čo nám dáva dve riešenia (pre D = 1, D = 0).
Preto: celkové riešenia 2*3 = 6.
Celkom 6 riešení.
odpoveď: 6
Koľko rôznych riešení má rovnica?
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
kde K, L, M, N sú logické premenné? Odpoveď nemusí uvádzať všetky rôzne množiny hodnôt K, L, M a N, pre ktoré platí táto rovnosť. Ako odpoveď stačí uviesť počet takýchto sád.
Riešenie.
Aplikujme negáciu na obe strany rovnice:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Logické OR je pravdivé v troch prípadoch.
Možnosť 1.
K ∧ L ∧ M = 1, potom K, L, M = 1 a ¬L ∧ M ∧ N = 0. N je ľubovoľné, to znamená 2 riešenia.
Možnosť 2.
¬L ∧ M ∧ N = 1, potom N, M = 1; L = 0, K ľubovoľné, teda 2 riešenia.
Preto je odpoveď 4.
odpoveď: 4
A, B a C sú celé čísla, pre ktoré je výrok pravdivý
¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).
Čomu sa rovná B, ak A = 45 a C = 43?
Riešenie.
Upozorňujeme, že toto zložité vyhlásenie pozostáva z troch jednoduchých
1) ¬(A = B); (A > B) -> (B > C); (B > A) -> (C > B);
2) tieto jednoduché príkazy sú spojené operáciou ∧ (AND, spojka), to znamená, že musia byť vykonané súčasne;
3) z ¬(A = B)=1 okamžite vyplýva, že A B;
4) predpokladajme, že A > B, potom z druhej podmienky dostaneme 1→(B > C)=1; tento výraz môže byť pravdivý vtedy a len vtedy, ak B > C = 1;
5) teda máme A > B > C, tejto podmienke zodpovedá len číslo 44;
6) pre každý prípad zaškrtnime aj možnosť A 0 →(B > C)=1;
tento výraz platí pre akékoľvek B; Teraz sa pozrieme na tretiu podmienku a dostaneme
tento výraz môže byť pravdivý vtedy a len vtedy, ak C > B, a tu máme rozpor, pretože neexistuje také číslo B, pre ktoré by C > B > A.
odpoveď: 44.
odpoveď: 44
Zostrojte pravdivostnú tabuľku pre logickú funkciu
X = (A ↔ B) ∨ ¬ (A → (B ∨ C))
v ktorom stĺpec hodnôt argumentu A je binárne vyjadrenie čísla 27, stĺpec hodnôt argumentu B je číslo 77, stĺpec hodnôt argumentu C je číslo 120. Číslo v stĺpci sa píše zhora nadol od najvýznamnejšieho po najmenej významný (vrátane nulovej sady). Preveďte výslednú binárnu reprezentáciu hodnôt funkcie X do desiatkovej číselnej sústavy.
Riešenie.
Napíšme rovnicu pomocou jednoduchšieho zápisu operácií:
1) toto je výraz s tromi premennými, takže v pravdivostnej tabuľke budú riadky; preto binárne znázornenie čísel použitých na zostavenie stĺpcov tabuľky A, B a C musí pozostávať z 8 číslic
2) preveďte čísla 27, 77 a 120 do dvojkovej sústavy, pričom na začiatok čísel okamžite pridajte až 8 číslic núl
3) je nepravdepodobné, že budete môcť okamžite zapísať hodnoty funkcie X pre každú kombináciu, takže je vhodné pridať do tabuľky ďalšie stĺpce na výpočet medzivýsledkov (pozri tabuľku nižšie)
| A | IN | S | X|
| 0 | 0 | ||
| 0 | 1 | 1 | |
| 0 | 0 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
4) vyplňte stĺpce tabuľky:
| A | IN | S | X | ||||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
hodnota je 1 iba v tých riadkoch, kde A = B
hodnota je 1 v tých riadkoch, kde buď B alebo C = 1
hodnota je 0 len v tých riadkoch, kde A = 1 a B + C = 0
hodnota je inverzná k predchádzajúcemu stĺpcu (0 sa nahradí 1 a 1 sa nahradí 0)
výsledkom X (posledný stĺpec) je logický súčet dvoch stĺpcov a
5) Ak chcete získať odpoveď, napíšte bity zo stĺpca X zhora nadol:
6) preveďte toto číslo do desiatkovej sústavy:
odpoveď: 171
Aké je najväčšie celé číslo X, pre ktoré platí výrok (10 (X+1)·(X+2))?
Riešenie.
Rovnica je operácia implikácie medzi dvoma vzťahmi:
1) Samozrejme, tu môžete použiť rovnakú metódu ako v príklade 2208, ale budete musieť vyriešiť kvadratické rovnice (nechcem...);
2) Všimnite si, že podľa podmienky nás zaujímajú iba celé čísla, takže sa môžeme pokúsiť nejako transformovať pôvodný výraz a získať ekvivalentný výrok (presné hodnoty koreňov nás vôbec nezaujímajú!);
3) Zvážte nerovnosť: samozrejme, môže to byť kladné alebo záporné číslo;
4) Je ľahké skontrolovať, či v doméne platí tvrdenie pre všetky celé čísla a v doméne - pre všetky celé čísla (aby nedošlo k zámene, je vhodnejšie použiť neprísne nerovnosti a namiesto a );
5) Preto ho pre celé čísla možno nahradiť ekvivalentným výrazom
6) doménou pravdivosti výrazu je spojenie dvoch nekonečných intervalov;
7) Teraz zvážte druhú nerovnosť: je zrejmé, že to môže byť aj kladné alebo záporné číslo;
8) V oblasti platí výrok pre všetky celé čísla av oblasti - pre všetky celé čísla, preto ho pre celé čísla možno nahradiť ekvivalentným výrazom
9) doménou pravdivosti výrazu je uzavretý interval;
10) Daný výraz platí všade okrem oblastí, kde a ;
11) Upozorňujeme, že hodnota už nie je vhodná, pretože tam a , čiže implikácia dáva 0;
12) Pri dosadzovaní 2, (10 (2+1) · (2+2)), alebo 0 → 0, ktorá podmienku spĺňa.
Takže odpoveď je 2.
odpoveď: 2
Aké je najväčšie celé číslo X, pre ktoré je výrok pravdivý
(50 (X+1)·(X+1))?
Riešenie.
Aplikujme implikačnú transformáciu a transformujme výraz:
(50 (X+1)·(X+1)) ⇔ ¬(X2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Logické OR je pravdivé, keď je pravdivé aspoň jedno logické tvrdenie. Po vyriešení oboch nerovností a pri zohľadnení toho, že vidíme, že najväčšie celé číslo, pre ktoré je splnená aspoň jedna z nich, je 7 (na obrázku je kladné riešenie druhej nerovnosti znázornené žltou a prvé modrou farbou).
odpoveď: 7
Uveďte hodnoty premenných K, L, M, N, pri ktorých je logický výraz
(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
falošné. Napíšte odpoveď ako reťazec 4 znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.
Riešenie.
Duplikuje úlohu 3584.
Odpoveď: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Riešenie.
Aplikujme implikačnú transformáciu:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Aplikujme negáciu na obe strany rovnice:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Poďme sa transformovať:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Preto M = 0, N = 0, teraz zvážte (¬K ∧ L ∨ M ∧ L):
z toho, že M = 0, N = 0, vyplýva, že M ∧ L = 0, potom ¬K ∧ L = 1, teda K = 0, L = 1.
Odpoveď: 0100
Zadajte hodnoty premenných K, L, M, N, pri ktorých je logický výraz
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
falošné. Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.
Riešenie.
Napíšme rovnicu pomocou jednoduchšieho zápisu operácií (podmienka „výraz je nepravdivý“ znamená, že sa rovná logickej nule):
1) z formulácie podmienky vyplýva, že výraz musí byť nepravdivý len pre jednu množinu premenných
2) z pravdivostnej tabuľky operácie „implikácia“ vyplýva, že tento výraz je nepravdivý vtedy a len vtedy, ak súčasne
3) prvá rovnosť (logický súčin sa rovná 1) je splnená vtedy a len vtedy a ; z toho vyplýva (logický súčet sa rovná nule), čo sa môže stať len vtedy, keď ; Takto sme už definovali tri premenné
4) z druhej podmienky, , for a získame .
Duplikuje úlohu
Odpoveď: 1000
Zadajte hodnoty logických premenných P, Q, S, T, pri ktorých je logický výraz
(P ∨ ¬Q) ∨ (Q → (S ∨ T)) je nepravda.
Napíšte odpoveď ako reťazec štyroch znakov: hodnoty premenných P, Q, S, T (v tomto poradí).
Riešenie.
(1) (P ∨ ¬Q) = 0
(2) (Q → (S ∨ Т)) = 0
(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ Т)) = 0 Aplikujme implikačnú transformáciu:
¬Q ∨ S ∨ T = 0 => S = 0, T = 0.
Odpoveď: 0100
Zadajte hodnoty premenných K, L, M, N, pri ktorých je logický výraz
(K → M) ∨ (L ∧ K) ∨ ¬N
falošné. Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.
Riešenie.
Logické OR je nepravdivé vtedy a len vtedy, ak sú oba výroky nepravdivé.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Aplikujme implikačnú transformáciu na prvý výraz:
¬K ∨ M = 0 => K = 1, M = 0.
Zvážte druhý výraz:
(L ∧ K) ∨ ¬N = 0 (pozri výsledok prvého výrazu) => L ∨ ¬N = 0 => L = 0, N = 1.
Odpoveď: 1001.
Odpoveď: 1001
Zadajte hodnoty premenných K, L, M, N, pri ktorých je logický výraz
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
pravda. Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.
Riešenie.
Logické "AND" je pravdivé vtedy a len vtedy, ak sú pravdivé oba výroky.
1) (K → M) = 1 Použiť implikačnú transformáciu: ¬K ∨ M = 1
2) (K → ¬M) = 1 Použiť implikačnú transformáciu: ¬K ∨ ¬M = 1
Z toho vyplýva, že K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1 Aplikujme implikačnú transformáciu: K ∨ (M ∧ ¬L ∧ N) = 1 z toho, že dostaneme K = 0.
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:
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: 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):
(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 sa rovná m +1.
|
Strom |
Počet riešení |
|
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
|
… |
V prípade ťažkostí s uvažovaním výskumu a výstavbyriešení, s ktorými môžete hľadať riešenie použitím 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) |
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*cNa 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ý.
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.
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.