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ď sú všetky veličiny zahrnuté v rovnici rovné 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)

X0

A	IN	S
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 previesť:

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

Koncom roka sa ukázalo, že len jeden z troch predpokladov bol pravdivý. Ktoré divízie dosiahli na konci roka zisk?

Riešenie. Predpoklady z problémových podmienok si zapíšme formou logických tvrdení: „Poberanie zisku delením B nie je nevyhnutnou podmienkou získania

zisk delením A“: F 1 (A, B, C) = A → B

„Získanie zisku z aspoň jednej divízie B a C nestačí na dosiahnutie zisku divíziou A“: F 2 (A, B, C) = (B + C) → A

„Divízie A a B nebudú dosahovať zisk súčasne“: F 3 (A, B, C) = A B

Z podmienky je známe, že iba jeden z troch predpokladov je pravdivý. To znamená, že musíme nájsť, ktorý z nasledujúcich troch logických výrazov nie je rovnako nepravdivý:

1) F 1 F 2 F 3

2) F 1 F 2 F 3

3) F 1 F 2 F 3

1) (A → B) ((B + C) → A) (A ↔ B) = A B (BC + A) (AB + A B) = 0

2) (A → B) ((B + C) → A) (A ↔ B) = (A + B) (A B + A C) (A B + A B) = A B C

3) (A → B) ((B + C) → A) (A B) = (A + B) (BC + A) (AB + A B) = 0

Následne sa na konci roka ukázal ako pravdivý druhý predpoklad a prvý a tretí nepravdivý.

									A = 0
	F1 F2 F3 = A B C = 1
									vtedy a len vtedy, ak B = 0.
									C = 1

Preto divízia C získa zisk, ale divízie A a B zisk nedostanú.

Riešenie logických rovníc

V textoch štátneho centralizovaného testovania je úloha (A8), ktorá žiada nájsť koreň logickej rovnice. Pozrime sa na spôsoby riešenia takýchto úloh pomocou príkladu.

Nájdite koreň logickej rovnice: (A + B) (X AB) = B + X → A.

Prvým riešením je zostaviť pravdivostnú tabuľku. Poďme zostaviť pravdivostné tabuľky pre pravú a ľavú stranu rovnice a uvidíme, pri akom X sa zhodujú hodnoty v posledných stĺpcoch týchto tabuliek.

F1 (A, B, X ) = (A + B) (X AB)

					A+B	(A + B) (X AB)	F 1 (A, B, X)

F2 (A, B, X) = B + X → A

			X → A							F 2 (A, B, X)
					X → A			X → A

Porovnajme výsledné pravdivostné tabuľky a vyberte tie riadky, v ktorých sa hodnoty F 1 (A, B, X) a F 2 (A, B, X) zhodujú.

			F 1 (A, B, X)	F 2 (A, B, X)

Prepíšme len vybrané riadky, ponechajme len stĺpce argumentov. Pozrime sa na premennú X ako funkciu A a B.

Je zrejmé, že X = B → A.

Druhým riešením je nahradiť znamienko rovnosti v rovnici znamienkom ekvivalentu a následne zjednodušiť výslednú logickú rovnicu.

Aby sme si uľahčili ďalšiu prácu, najprv zjednodušíme pravú a ľavú stranu logickej rovnice a nájdeme ich negácie:

F1 = (A + B) (X AB) = A + B + (X ↔ AB) = A B + X A B + X A + X B

F1 = (A + B) (X AB) = (A + B) (X A + X B + X A B) = X A B + X A B + X A B

F2 = B + X → A = B (X → A) = B (X + A) = X B + A B F2 = B + X → A = B + X + A = B + X A

Nahraďte znamienko rovnosti v našej logickej rovnici znamienkom ekvivalencie:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B + X A B + X A + X B) (X B + A B) +

+ (XAB + XAB + X A B) (B + X A) =

= (XAB + X B + X A B) + (X A B + X A B) =

Preusporiadame logické pojmy tohto výrazu, pričom faktory X a X vyjmeme zo zátvoriek.

X (AB) + X (B + AB) = X (AB) + X (B + A) =

Označme teda T = A B

X T + X T = X ↔ T .

Preto, aby logická rovnica mala riešenie: X = A B = B + A = B → A.

Logické prvky počítača. Konštrukcia funkčných schém

S rozvojom výpočtovej techniky sa ukázalo, že matematická logika úzko súvisí s otázkami návrhu a programovania výpočtovej techniky. Algebra logiky našla široké uplatnenie spočiatku vo vývoji reléový kontakt schém Prvý základný výskum, ktorý upriamil pozornosť inžinierov zapojených do počítačového dizajnu na možnosť analyzovať elektrické obvody pomocou Booleovej algebry, publikoval v decembri 1938 Američan Claude Shannon, „Symbolic Analysis of Ladder Circuits“. Po tomto článku sa počítačový dizajn nezaobišiel bez použitia booleovskej algebry.

Logický prvok je obvod, ktorý implementuje logické operácie disjunkcie, konjunkcie a inverzie. Uvažujme o implementácii logických prvkov prostredníctvom elektrických reléových kontaktných obvodov, ktoré sú vám známe zo školského kurzu fyziky.

Sériové pripojenie kontaktov

Paralelné pripojenie kontaktov

Zostavme si tabuľku závislostí stavu obvodov na všetkých možných stavoch kontaktov. Uveďme si nasledovné označenia: 1 – kontakt je zopnutý, v obvode je prúd; 0 – kontakt je otvorený, v obvode nie je prúd.

		Stav obvodu	Stav obvodu s paralelou
		sériové pripojenie	spojenie

Ako vidíte, obvod so sériovým pripojením zodpovedá logickej operácii spojenia, pretože prúd v obvode sa objaví iba vtedy, keď sú kontakty A a B súčasne zatvorené. Obvod s paralelným pripojením zodpovedá logickému fungovaniu disjunkcie, pretože v obvode nie je prúd iba v okamihu, keď sú oba kontakty otvorené.

Logická prevádzka inverzie sa realizuje prostredníctvom kontaktného obvodu elektromagnetického relé, ktorého princíp sa študuje v školskom kurze fyziky. Kontakt x je otvorený, keď je x zatvorený a naopak.

Použitie reléových kontaktných prvkov na konštrukciu logických obvodov počítačov sa neosvedčilo z dôvodu nízkej spoľahlivosti, veľkých rozmerov, vysokej spotreby energie a nízkeho výkonu. Nástup elektronických zariadení (vákuových a polovodičových) vytvoril možnosť konštrukcie logických prvkov s rýchlosťou 1 milión prepnutí za sekundu a vyššou. Polovodičové logické prvky pracujú v spínacom režime podobne ako elektromagnetické relé. Celá teória prezentovaná pre kontaktné obvody je prenesená na polovodičové prvky. Logické prvky na polovodičoch nie sú charakterizované stavom kontaktov, ale prítomnosťou signálov na vstupe a výstupe.

Zoberme si logické prvky, ktoré implementujú základné logické operácie:

Invertor - implementuje operáciu negácie alebo inverzie. U

menič má jeden vstup a jeden výstup. Zobrazí sa výstupný signál

keď na vstupe nie je žiadny a naopak.

Spojka -

X1 X 2 ... X n

implementuje operáciu spojenia.

U spojky

jeden východ a aspoň dva vchody. Signál zapnutý

sa objaví vo výstupe vtedy a len vtedy

všetky vstupy sú signalizované.

X 2 + ... X n

Disjunktor - implementuje operáciu disjunkcie. U

disjunktor má jeden východ a aspoň dva

Výstupný signál sa neobjaví vtedy a len vtedy

keď do všetkých vstupov neprichádzajú žiadne signály.

	Stavať	funkčné
F(X, Y, Z) = X (Y + Z)
			X + Z

diagram zodpovedajúci funkcii:

&F(X, Y, Z)

Riešenie problémov pomocou konjunktívneho normálu

A disjunktívny-normálny formulárov

IN Knihy logických problémov často obsahujú štandardné problémy, kde potrebujete napísať funkciu, ktorá ich implementuje rebríkový diagram, zjednodušte ho a zostrojte pravdivostnú tabuľku pre túto funkciu. Ako vyriešiť inverzný problém? Vzhľadom na ľubovoľnú pravdivostnú tabuľku musíte zostaviť funkčný alebo reléový diagram. Touto problematikou sa dnes budeme zaoberať.

Akákoľvek funkcia logickej algebry môže byť reprezentovaná kombináciou troch operácií: konjunkcie, disjunkcie a inverzie. Poďme zistiť, ako sa to robí. Aby sme to dosiahli, napíšme si niekoľko definícií.

Minterm je funkcia vytvorená spojením určitého počtu premenných alebo ich negácií. Minterm má hodnotu 1 pre jedinú zo všetkých možných množín

argumenty a hodnota je 0 pre všetky ostatné. Príklad: x 1 x 2 x 3 x 4 .

Maxterm je funkcia vytvorená disjunkciou určitého počtu premenných alebo ich negáciami. Maxterm má hodnotu 0 v jednej z možných množín a 1 vo všetkých ostatných.

Príklad: x 1 + x 2 + x 3.

Funkcia v disjunktívna normálna forma(DNF) je logický súčet mintermov.

Príklad: x 1 x 2 + x 1 x 2 + x 1 x 2 x 3.

Konjunktívna normálna forma(CNF) je logickým produktom elementárnych disjunkcií (maxterms).

Príklad: (x 1 + x 2 + x 3 ) (x 1 + x 2 ) .

Dokonalá disjunktívna normálna forma sa nazýva DNF, v každom minterme sú prítomné všetky premenné alebo ich negácie.

Príklad: x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3

Dokonalá konjunktívna normálna forma sa nazýva CNF, v každom maxterme, ktorého sú prítomné všetky premenné alebo ich negácie.

Príklad: (x 1 + x 2 + x 3 ) (x 1 + x 2 + x 3 )

Zápis logickej funkcie z tabuľky

Akákoľvek logická funkcia môže byť vyjadrená ako SDNF alebo SCNF. Ako príklad uvažujme funkciu f uvedenú v tabuľke.

			f(x1 , x2 , x3 )

Funkcie G0, G1, G4, G5, G7 sú mintermy (pozri definíciu). Každá z týchto funkcií je súčinom troch premenných alebo ich inverzných hodnôt a má hodnotu 1 iba v jednej situácii. Je vidieť, že na získanie 1 v hodnote funkcie f je potrebný jeden minterm. V dôsledku toho sa počet mintermov, ktoré tvoria SDNF tejto funkcie, rovná počtu jednotiek vo funkčnej hodnote: f= G0+G1+G4+G5+G7. SDNF má teda tvar:

f (x 1, x 2, x 3) = x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3.

Podobne môžete postaviť SKNF. Počet faktorov sa rovná počtu núl vo funkčných hodnotách:

f (x 1, x 2, x 3) = (x 1 + x 2 + x 3) (x 1 + x 2 + x 3) (x 1 + x 2 + x 3).

Každá logická funkcia zadaná vo forme tabuľky môže byť teda napísaná ako vzorec.

Algoritmus na konštrukciu SDNF pomocou pravdivostnej tabuľky

Je uvedená pravdivostná tabuľka nejakej funkcie. Ak chcete vytvoriť SDNF, musíte vykonať nasledujúcu postupnosť krokov:

1. Vyberte všetky riadky tabuľky, v ktorých má funkcia hodnotu 1.

2. Ku každému takémuto riadku priraďte spojenie všetkých argumentov alebo ich inverzie (minterm). V tomto prípade je argument s hodnotou 0 zahrnutý do minterm s negáciou a hodnota 1 je zahrnutá bez negácie.

3. Nakoniec vytvoríme disjunkciu všetkých získaných mintermov. Počet mintermov sa musí zhodovať s počtom jednotiek logickej funkcie.

Algoritmus na konštrukciu SCNF pomocou pravdivostnej tabuľky

Je uvedená pravdivostná tabuľka nejakej funkcie. Ak chcete zostaviť SKNF, musíte vykonať nasledujúcu postupnosť krokov:

1. Vyberte všetky riadky tabuľky, v ktorých má funkcia hodnotu 0.

2. Pre každý takýto riadok priraďte disjunkciu všetkých argumentov alebo ich inverzie (maxterm). V tomto prípade je argument s hodnotou 1 zahrnutý do maxterm s negáciou a hodnota 1 je zahrnutá bez negácie.

3. Nakoniec vytvoríme konjunkciu všetkých získaných maxtermov. Počet maxtermov sa musí zhodovať s počtom núl logickej funkcie.

Ak sa z dvoch foriem (SDNF alebo SKNF) dohodneme na uprednostnení tej, ktorá obsahuje menej písmen, potom je SDNF výhodnejšie, ak je medzi hodnotami funkcie pravdivostnej tabuľky, SKNF, menej jednotiek – ak je núl menej.

Príklad. Je uvedená pravdivostná tabuľka logickej funkcie troch premenných. Zostavte logický vzorec, ktorý implementuje túto funkciu.

			F(A, B, C)

Vyberme tie riadky v tejto pravdivostnej tabuľke, v ktorých je funkčná hodnota 0.

F(A, B, C) = (A + B + C) (A + B + C)

Skontrolujme odvodenú funkciu vytvorením pravdivostnej tabuľky.

Porovnaním počiatočných a konečných pravdivostných tabuliek môžeme konštatovať, že logická funkcia je skonštruovaná správne.

Riešenie problémov

1. Traja učitelia vyberajú úlohy na olympiádu. Na výber je viacero úloh. Ku každej úlohe každý učiteľ vyjadrí svoj názor: ľahká (0) alebo ťažká (1) úloha. Úloha je zaradená do úlohy olympiády, ak ju aspoň dvaja učitelia označia ako ťažkú, ale ak ju všetci traja učitelia považujú za ťažkú, potom takáto úloha nie je zaradená do úlohy olympiády ako príliš ťažká. Vytvorte logickú schému zariadenia, ktoré vydá 1, ak je úloha zahrnutá v úlohe olympiády, a 0, ak nie je zahrnutá.

Zostavme pravdivostnú tabuľku pre požadovanú funkciu. Máme tri vstupné premenné (traja učitelia). Preto bude požadovaná funkcia funkciou troch premenných.

Analýzou stavu problému získame nasledujúcu pravdivostnú tabuľku:

Budujeme SDNF. F(A, B, C) = ABC + ABC + ABC

Teraz vytvoríme logický diagram tejto funkcie.

B & 1 F(A,B,C)

2. Mestská olympiáda v základnom kurze informatiky, 2007.Zostavte schému elektrického obvodu pre vchod do trojposchodového domu tak, aby vypínač na ktoromkoľvek poschodí mohol zapínať alebo vypínať svetlá v celom dome.

Máme teda tri spínače, ktoré musíme použiť na zapnutie a vypnutie svetla. Každý prepínač má dva stavy: hore (0) a dole (1). Predpokladajme, že ak sú všetky tri spínače v polohe 0, svetlá vo vchode sú vypnuté. Potom, keď presuniete ktorýkoľvek z troch spínačov do polohy 1, malo by sa rozsvietiť svetlo vo vchode. Je zrejmé, že keď presuniete akýkoľvek iný spínač do polohy 1, svetlo vo vchode zhasne. Ak sa prepne tretí spínač do polohy 1, rozsvieti sa svetlo vo vchode. Vytvárame tabuľku pravdy.

Potom F(A, B, C) = ABC + ABC + ABC + ABC .

	3. Zmeňte stav			hodnoty logických funkcií			F(A, B, C) = C ->		A+B
	zmena argumentov B a C súčasne je:
		A → (B C)						(B C) → A
					A(B C)
	4) (BC) → A				A → (B C)

Poznámka. Ak chcete úspešne vyriešiť tento problém, zapamätajte si nasledujúce logické vzorce:

x → y = x + y x y = x y + x y

x ↔ y = x y + x y

Máme logickú funkciu troch premenných F 1 (A, B, C) = C → A + B = C + A B.

Zmeňme súčasne premenné B a C: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. Zostavme pravdivostné tabuľky pre tieto dve funkcie:

Poďme analyzovať výslednú tabuľku. Z ôsmich riadkov tabuľky iba v dvoch (2. a 3.) funkcia nemení svoju hodnotu. Všimnite si, že v týchto riadkoch premenná A neobráti svoju hodnotu, ale premenné B a C áno.

Funkcie SKNF vytvárame pomocou týchto riadkov:

F3 (A, B, C) = (A + B + C) (A + B C) = A + AB + AC + AB + BC + AC + B C =.

A + (B ↔ C) = A + B C = (BC) → A

Požadovaná odpoveď je teda 4.

4. Podmienka pre zmenu hodnoty logickej funkcie F (A, B, C) = C + AB pri súčasnej zmene argumentov A a B sa rovná:

1) C + (A B)

C+(A B)

TAXÍK)

4) C(A B)

C → (A B)

F1 (A, B, C) =

C+AB

F 2 (A, B, C) = F 1 (

C) = A

Vytvárame tabuľku pravdy.

Poďme analyzovať výslednú tabuľku. Z ôsmich riadkov tabuľky len v dvoch (1. a 7.) funkcia mení svoju hodnotu. Upozorňujeme, že v týchto riadkoch nemení svoju hodnotu premenná C, ale premenné A a B áno.

Funkcie SDNF vytvárame pomocou týchto riadkov:

F3 (A, B, C) = A B C + A B C = C (A B + A B) = C (A ↔ B) = C + (A B)

Požadovaná odpoveď je teda 2.

Referencie

1. Shapiro S.I. Riešenie logických a herných problémov(logické a psychologické štúdie). – M.: Rádio a spoje, 1984. – 152 s.

2. Šolomov L.A. Základy teórie diskrétnych logických a výpočtových zariadení. – M.: Veda. Ch. vyd. fyzické - mat. lit., 1980. - 400 s.

3. Pukhalsky G.I., Novoseltseva T.Ya. Návrh diskrétnych zariadení na integrovaných obvodoch: Príručka. – M.: Rádio a spoje, 1990.

Veľkosť: px

Začnite zobrazovať zo stránky:

Prepis

1 Riešenie logických rovníc a sústav logických rovníc Nech F(x, x2, xn) je logická funkcia n premenných. Logická rovnica má tvar: F(x, x2, xn) = C, kde konštanta C má hodnotu resp. Logická rovnica môže mať až 2 n rôznych riešení. Ak sa C rovná, riešeniami sú všetky tie množiny premenných z pravdivostnej tabuľky, na ktorých má funkcia F hodnotu true (). Zostávajúce množiny sú riešenia rovnice s C rovným nule. Vždy môžete uvažovať iba rovnice v tvare: F(x, x2, xn) = Vskutku, nech je rovnica daná: F(x, x2, xn) = V tomto prípade môžete prejsť na ekvivalentnú rovnicu: F( x, x2, xn) = Uvažujme sústavu k logických rovníc: F(x, x2, xn) = F2(x, x2, xn) = ( Fk(x, x2, xn) = Riešením sústavy je množina premenných, na ktorých sú splnené všetky rovnice systému V logických termínoch funkcií na získanie riešenia systému logických rovníc by sme mali nájsť množinu, na ktorej platí logická funkcia Ф, ktorá predstavuje spojenie pôvodných funkcií F: Ф = F F2 Fk Ak je počet premenných malý, napríklad menší ako 5, potom nie je ťažké zostrojiť pravdivostnú tabuľku pre funkciu Ф, ktorá umožňuje povedať, koľko riešení má systém a aké sú množiny ktoré dávajú riešenia V niektorých problémoch USE pri hľadaní riešení systému logických rovníc, počet premenných dosiahne hodnotu. Potom sa zostavenie pravdivostnej tabuľky stáva takmer nemožnou úlohou. Pre ľubovoľný systém rovníc neexistuje iná všeobecná metóda ako enumerácia, ktorá umožňuje riešenie takýchto problémov. V problémoch navrhnutých na skúške je riešenie zvyčajne založené na zohľadnení špecifík systému rovníc. Opakujem však, že okrem vyskúšania všetkých možností pre množinu premenných neexistuje všeobecný spôsob riešenia problému. Riešenie musí byť postavené na základe prezentovaného systému. Často je užitočné vykonať predbežné zjednodušenie systému rovníc pomocou známych logických zákonov. Ďalšia užitočná technika na riešenie tohto problému je nasledovná. Nezaujímajú nás všetky množiny, ale iba tie, na ktorých má hodnotu funkcia Φ. Namiesto zostavenia kompletnej pravdivostnej tabuľky vytvoríme jej analóg - binárny rozhodovací strom. Každá vetva tohto stromu zodpovedá

2 na jedno riešenie a určuje množinu, na ktorej má funkcia Ф hodnotu. Počet vetiev v rozhodovacom strome sa zhoduje s počtom riešení sústavy rovníc. Na príkladoch niekoľkých problémov vysvetlím, čo je binárny rozhodovací strom a ako sa vytvára. Problém Koľko rôznych množín hodnôt logických premenných x, x2, x3, x4, x5, y, y2, y3, y4, y5 spĺňa systém dvoch rovníc? (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = ( (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Odpoveď: Systém má 36 rôznych riešení Sústava rovníc obsahuje dve rovnice, nájdime počet riešení v závislosti od 5 premenných x, x2, x5 bolo znázornené, sústava rovníc vlastne predstavuje konjunkciu logických funkcií je pravdivé aj konjunkciu podmienok možno považovať za sústavu rovníc (x x2) - prvý člen konjunkcie, ktorú možno považovať za prvú rovnicu Takto vyzerá grafické znázornenie tohto stromu: X X2 Strom sa skladá z dvoch úrovní podľa počtu premenných v rovnici prvá premenná X. Dve vetvy tejto úrovne odrážajú možné hodnoty tejto premennej a na druhej úrovni vetvy stromu odrážajú iba tie možné hodnoty premennej X2, pre ktoré platí rovnica. Keďže rovnica špecifikuje implikáciu, vetva, na ktorej má X hodnotu, vyžaduje, aby X2 mala hodnotu na tejto vetve. Vetva, na ktorej má X hodnotu, vedie k dvom vetvám s hodnotami X2 rovnými a. Skonštruovaný strom špecifikuje tri riešenia, pri ktorých implikácia X X2 nadobúda hodnotu. Na každej vetve je zapísaná zodpovedajúca sada premenných hodnôt, ktorá poskytuje riešenie rovnice. Tieto množiny sú: ((,), (,), (,)) Pokračujme v zostavovaní rozhodovacieho stromu pridaním nasledujúcej rovnice, nasledujúcej implikácie X2 X3. Špecifikom nášho systému rovníc je, že každá nová rovnica systému používa jednu premennú z predchádzajúcej rovnice a pridáva jednu novú premennú. Keďže premenná X2 už má hodnoty v strome, potom na všetkých vetvách, kde má premenná X2 hodnotu, bude mať hodnotu aj premenná X3. Pre takéto vetvy pokračuje stavba stromu na ďalšiu úroveň, ale nové vetvy sa nezobrazujú. Jediná vetva, kde má premenná X2 hodnotu, sa rozvetví na dve vetvy, kde premenná X3 dostane hodnoty a. Každé pridanie novej rovnice, berúc do úvahy jej špecifiká, teda pridáva jedno riešenie.

3 Pôvodná prvá rovnica: (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = má 6 riešení. Takto vyzerá úplný strom riešenia pre túto rovnicu: X X2 X3 X4 X5 Druhá rovnica nášho systému je podobná prvej: (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Jediný rozdiel je v tom, že rovnica používa premenné Y. Táto rovnica má tiež 6 riešení. Keďže každé riešenie pre premenné Xi možno kombinovať s každým riešením pre premenné Yj, celkový počet riešení je 36. Všimnite si, že zostrojený rozhodovací strom udáva nielen počet riešení (podľa počtu vetiev), ale aj samotné riešenia napísané na každej vetve stromu. Úloha 2 Koľko rôznych množín hodnôt logických premenných x, x2, x3, x4, x5, y, y2, y3, y4, y5 spĺňa všetky nižšie uvedené podmienky? (x x2) ^ (x2 x3) ^ (x3 x4) ^ (x4 x5) = ((y y2) ^ (y2 y3) ^ (y3 y4) ^ (y4 y5) = (x y) = Odpoveď: 3 Tento problém je modifikáciou predchádzajúcej úlohy, rozdiel je v tom, že sa pridáva ďalšia rovnica, ktorá dáva do vzťahu premenné X a Y. Z rovnice X Y vyplýva, že keď X má hodnotu (existuje jedno takéto riešenie), potom má Y hodnotu , je jedna sada , na ktorej

4 X a Y majú význam. Keď sa X rovná, Y môže mať akúkoľvek hodnotu, a to ako aj. Preto každej množine, ktorej X sa rovná a takýchto množín je 5, zodpovedá všetkým 6 množinám s premennými Y. Celkový počet riešení je teda 3. Úloha 3 Koľko riešení má rovnica: (X X2) ( X2 X3) (X3 X4) (X4 X5) (X5 X) = Odpoveď: 2 Pripomínajúc si základné ekvivalencie, zapíšeme našu rovnicu v tvare: (X X2) (X2 X3) (X3 X4) (X4 X5) (X5 X) = Cyklický reťazec implikácií znamená identitu premenných, takže naša rovnica je ekvivalentná rovnici: X X2 X3 X4 X5 = Táto rovnica má dve riešenia, keď všetky Xi sú buď alebo. Úloha 4 Koľko riešení má rovnica: (X X2) (X2 X3) (X3 X4) (X4 X2) (X4 X5) = Odpoveď: 4 Rovnako ako v úlohe 2, prejdime od cyklických implikácií k identitám a prepíšme rovnica v tvare: (X X2) (X2 X3 X4) (X4 X5) = Zostavme rozhodovací strom pre túto rovnicu: X X2 X3 X4 X5

5 Úloha 4 Koľko riešení má nasledujúca sústava rovníc? Odpoveď: 64 ((X X2) (X3 X4)) ((X X2) (X3 X4)) = ((X3 X4) (X5 X6)) ((X3 X4) (X5 X6)) = ((X5 X6) (X7 X8)) ((X5 X6) (X7 X8)) = (((X7 X8) (X9 X)) ((X7 X8) (X9 X)) = Prejdime od premenných k 5 premenným zavedením nasledujúcej zmeny premenných: Y = (X X2) Y2 = (X3 X4 = (X7 X8); (Y Y2) = Prejdeme na tradičnú formu, systém zapíšeme po zjednodušeniach v tvare: (Y Y2) = (Y2 Y3) = ( (Y3 Y4) = (Y4 Y5) = Rozhodovací strom pre tento systém je jednoduché a pozostáva z dvoch vetiev so striedajúcimi sa hodnotami premenných: Y Y2 Y3 Y4 Y5 Vráťme sa k pôvodným premenným X, poznamenávame, že každá hodnota premennej Y zodpovedá 2 hodnotám premenných X, preto každé riešenie v premenných Y generuje 2 5 riešení v premenných X Dve vetvy generujú 2 * 2 5 riešení, takže celkový počet riešení je 64. Ako vidíte, každý problém riešenia sústavy rovníc si vyžaduje iný prístup. Bežnou technikou je vykonávanie ekvivalentných transformácií na zjednodušenie rovníc.

6 Bežnou technikou je konštrukcia rozhodovacích stromov. Použitý prístup čiastočne pripomína zostrojenie pravdivostnej tabuľky s tou zvláštnosťou, že nie sú zostrojené všetky množiny možných hodnôt premenných, ale len tie, na ktorých má funkcia hodnotu (true). V navrhovaných problémoch často nie je potrebné budovať úplný rozhodovací strom, pretože už v počiatočnom štádiu je možné vytvoriť vzor vzhľadu nových vetiev na každej nasledujúcej úrovni, ako sa to stalo napríklad v probléme. .

Putilov Viktor Vasilievich MAOU Stredná škola 46 Systémy logických rovníc. Obsah Poznámka o nahradení premenných.... Úlohy obsahujúce implikáciu alebo jej ekvivalentný zápis....2 Prítomnosť dodatočnej podmienky...6

Riešenie sústavy logických rovníc. Koľko riešení má rovnica A BB C C D = 0 Počet množín premenných je =. Môžete vytvoriť pravdivostnú tabuľku a skontrolovať, koľko množín zodpovedá

Konštrukcia a analýza pravdivostných tabuliek logických výrazov. Jednotná štátna skúška 2015 2 (základná úroveň, čas 3 minúty) Príklad P-13. Každý booleovský výraz A a B závisí od rovnakej množiny 5 premenných.

N B Rogov Ako sa naučiť riešiť úlohu B15 Jednotnej štátnej skúšky z informatiky (systémy logických rovníc) za 180+ minút Materiály pre hodiny Online sekcia: http://basicschoolru/?page=eam_info_b15 Teoretický úvod:

B4 Téma: Konverzia logických výrazov. O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované vo „serióznej“ matematickej logike (,), sú nepohodlné a nie sú intuitívne jasné.

Matematika a matematické modelovanie MDT 004.023 Semenov Sergey Maksimovič Vladivostok Štátna univerzita ekonomiky a služieb Rusko. Vladivostok O jednom spôsobe riešenia logických systémov

B4 (vysoká úroveň, čas 1 min) Téma: Prevod logických výrazov. O zápisoch Bohužiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované vo „serióznej“ matematickej logike (,),

B0 (vysoká úroveň, čas 0 min) Téma: Prevod logických výrazov. O zápisoch Bohužiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované vo „serióznej“ matematickej logike (,),

19022017 Bitové operácie v problematike KIM Jednotná štátna skúška z informatiky Časť II KYu Polyakov, doktor technických vied, učiteľ informatiky GBOU Stredná škola 163, Petrohrad Tento článok sa po prvýkrát zaoberá problémami nasledujúceho typu

Samostatná práca na tému „Metódy zadávania logických funkcií“ 1. Vypočítajte hodnotu funkcie F(x, y, z) = na množine premenných (1, 1, 0). 3. Určte ekvivalenciu funkcií F(x, y, z) = a G(x,

Logika je veda, ktorá študuje metódy stanovenia pravdivosti alebo nepravdivosti niektorých tvrdení na základe pravdivosti alebo nepravdivosti iných tvrdení. Výrok (rozsudok) je nejaká veta, ktorá

B vysoká úroveň, čas 0 min) K. Polyakov, 009-0 Téma: Transformácia logických výrazov. O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované v „serióznej“ matematickej

Úloha 1: Daný fragment pravdivostnej tabuľky výrazu F: Aký výraz môže byť F? X Y Z F 0 0 0 0 0 0 1 0 1 1 1 1 1) X /\ Y /\ Z 2) X \/ Y \/ Z 3) X \/ Y \/ Z 4) X /\ Y /\ Z Zvážte prvý výraz

FUNKCIE LOGICKEJ ALGEBRY (pokračovanie) Počet booleovských funkcií n premenných zistíme podľa vzorca: P2 (n) = 2 2n Logické funkcie dvoch premenných 6 Najčastejšie sa používajú tieto funkcie: f (x,

Riešenia úloh v dvojhodnotovej logike F.G. Korablev Úloha 1. Pre funkciu f(x, y, z) = ((x y) (x z)) (z x) nájdite podstatné a fiktívne premenné, vykonajte operáciu eliminácie fiktívnych premenných. Riešenie.

051216 Bitové operácie v problémoch KIM Jednotná štátna skúška z informatiky Časť II KYu Polyakov, doktor technických vied, učiteľ informatiky GBOU Stredná škola 163, Petrohrad Tento článok po prvýkrát rozoberá problémy nasledujúceho typu

Mironchik E.A., učiteľ informatiky, Novokuzneck Riešenie úlohy Unified State Exam-18 s bitovými operáciami Opísaná metóda demonštruje metódu riešenia založenú na identických prechodoch, t.j. = "funguje"

Téma: Základné pojmy matematickej logiky. Vzorové otázky O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, prijaté v „serióznej“ matematickej logike (,), sú nepohodlné a intuitívne

Časť 1 1. Uveďte, ktorý logický výraz je ekvivalentný výrazu A /\ (B \/ C). 1) A \/ B \/ C 2) A /\ B /\ C 3) A /\ B /\ C 4) A /\ B /\ C Riešenie: Použitie de Morganovho vzorca (B \/ C) = B /\ C a

Glinka N.V. Použitý zápis Negácia Násobenie (konjunkcia) Sčítanie (disjunkcia) Implikácia Ekvivalencia Príklady úloh pred školským rokom 2010 Koľko rôznych riešení má rovnica ((K

Bitové operácie v problémoch KIM v informatike Typy problémov Tento webinár sa zaoberá problémami nasledujúceho typu (tieto problémy sa prvýkrát objavili v KIM na Unified State Exam 2015): Zaviesť výraz M & K, označujúci

Praktická práca 6 Riešenie logických úloh s využitím zákonov logickej algebry Cieľ práce: posilnenie schopnosti transformovať logické výrazy pomocou zákonov logickej algebry, počítať

A10 (základná úroveň, čas 1 min) Téma: Transformácia logických výrazov. De Morganove vzorce. O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované v „serióznej“ matematickej

Gurskaya K.A., Ivin V.V., Semenov S.M. Riešenie problémov matematickej logiky v Jednotnej štátnej skúške z informatiky 1 MDT 004.9 Gurskaya K.A., Ivin V.V., Semenov S.M. Učebnica „Riešenie problémov matematickej logiky v jednotnej štátnej skúške“

OBSAH Predhovor................................... 3 Kapitola 1. Matematická logika...... ........ .... 4 1. Výroková algebra.................. 4 2. Booleovské algebry.......... ........ .... 12 3. Kalkul

PREDNÁŠKA 5 LOGICKÉ OPERÁCIE V INFORMAČNEJ VEDE 1. Matematická logika a informatika 2. Logické výrazy a logické operácie 3. Konštrukcia pravdivostných tabuliek a logických funkcií 4. Zákony logiky a pravidlá

B5 vysoká úroveň, čas 0 min) Téma: Transformácia logických výrazov. O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované vo „serióznej“ matematickej logike, sú nepohodlné,

Logická algebra Logická algebra je formálna logická teória, odvetvie matematickej logiky vyvinuté v 19. storočí anglickým matematikom Georgeom Boolom. Algebra logiky využíva algebraické metódy

2 (základná úroveň, min. čas) Téma: Konštrukcia a rozbor pravdivostných tabuliek logických výrazov. O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované v „serióznej“ matematickej

A8 (základná úroveň, čas 1 min) Téma: Transformácia logických výrazov. De Morganove vzorce. O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované v „serióznej“ matematickej

B15 Uveďte hodnoty premenných K, L, M, N, pre ktoré je logický výraz (K M) (L K) N nepravdivý. Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí).

Základy logiky. Logické operácie a pravdivostné tabuľky Základy logiky. Logické operácie a pravdivostné tabuľky Táto stránka bude diskutovať o 6 logických operáciách: konjunkcia, disjunkcia, inverzia,

Identity Booleovej algebry Hlavnou úlohou matematickej logiky je určiť význam zložitého tvrdenia na základe nepravdivosti alebo pravdivosti jednoduchých tvrdení. Logické operácie vo výrokovej algebre

Mestská rozpočtová vzdelávacia inštitúcia mesta Abakan „Stredná škola 11“ Metodický vývoj na tému Riešenie úloh typu 18 Jednotná štátna skúška z informatiky Atyushkina Marina Valerievna,

Téma 4. Logické základy POČÍTAČA 1. ZÁKLADNÉ INFORMÁCIE Z LOGICKEJ ALGEBRA... 1 2. ZÁKONY LOGICKEJ ALGEBRA... 4 3. KONCEPCIA MINIMALIZÁCIE LOGICKÝCH FUNKCIÍ... 6 4. TECHNICKÁ INTERPRETÁCIA LOGICKÝCH FUNKCIÍ...

Téma 9. Logické základy počítačov. 1. Logika. Informácie spracované v počítači sú reprezentované pomocou fyzikálnych veličín, ktoré môžu mať iba dva stabilné stavy a nazývajú sa „binárne premenné“.

Iracionálne nerovnosti Nerovnosti, v ktorých je premenná obsiahnutá pod koreňovým znakom, sa nazývajú iracionálne Hlavnou metódou riešenia iracionálnych nerovností je metóda zmenšenia originálu

26 transformácií, zostavte správny reťazec uvažovania a urobte aritmetickú chybu v poslednej akcii. Všimnite si, že pri riešení tejto úlohy dosiahne počet iba aritmetických operácií

Regionálna súťaž vzdelávacích, výskumných a dizajnérskych prác študentov „Aplikované otázky matematiky“ Algebra Algebra logiky Alena Sergeevna Semusheva, Mestské vzdelávacie zariadenie „Lyceum“ Perm, kl. Borková Olga Vladimirovna,

K. Polyakov, 009-0 B5 vysoká úroveň, čas 0 min) Téma: Transformácia logických výrazov. O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované v „serióznej“ matematickej

PRAKTICKÁ LEKCIA 1 Lineárne rovnice prvého rádu, Bernoulliho rovnica Rovnica v totálnych diferenciáloch Lineárna diferenciálna rovnica prvého rádu je rovnica + p(= q(If

Moskovská štátna technická univerzita pomenovaná po N.E. Bauman Fakulta základných vied Katedra matematického modelovania A.N. KAPITÁLOVÝ DASHMANN

A9 (základná úroveň, čas 2 min) Téma: Konštrukcia pravdivostných tabuliek logických výrazov. O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované v „serióznej“ matematickej

Mironchik E.A., MB NOU "Lyceum", Novokuznetsk Spôsob zobrazenia Zadanie. Koľko riešení má systém: Všetky rovnice zahrnuté v systéme sú rovnakého typu a každá rovnica obsahuje tri premenné. Vedieť

Federálna agentúra pre vzdelávanie Uralská štátna ekonomická univerzita Yu B. Melnikova Boolean a logické funkcie Sekcia elektronickej učebnice k prednáške e-mail: melnikov@k66.ru,

E.V.Prosolupov 42. Booleovská algebra. Funkcie logickej algebry 1 Booleovské funkcie Budeme uvažovať o boolovských funkciách - funkciách, ktorých argumenty a hodnoty nadobúdajú hodnoty true a false. Pravda a klamstvo budú

Federálna agentúra pre vzdelávanie Uralská štátna ekonomická univerzita Yu B. Melnikova Boolean a logické funkcie Sekcia elektronickej učebnice k prednáške Ed. 3., rev.

MINISTERSTVO ŠKOLSTVA A VEDY RF Federálna štátna autonómna vzdelávacia inštitúcia vyššieho odborného vzdelávania "NÁRODNÝ VÝSKUM TOMSKOVÁ POLYTECHNICKÁ UNIVERZITA"

Praktická práca 1 Logické operácie. Ekvivalencia vzorcov Cieľ práce: Naučiť sa zostavovať pravdivostné tabuľky logických výrokov a transformovať vzorce pomocou základných ekvivalencií Obsah

Hovorí sa, že keď Aristoteles prišiel s logikou, oslávil ju hostinou a nariadil zabiť 40 oviec. Odvtedy ovce nemajú radi logiku. Základné pojmy logickej algebry, ročník 10, akademický rok 2017-2018

Diferenciálne rovnice prvého rádu riešené vzhľadom na deriváciu Veta o existencii a jednoznačnosti riešenia Vo všeobecnom prípade má diferenciálna rovnica prvého rádu tvar F ()

Prednáška 2. Konjunktívne normálne formy. Implicenta, jednoduchá implicitná funkcia. Znížený CNF funkcií logickej algebry. Metódy konštrukcie skráteného CNF. Prednášajúca Svetlana Nikolaevna Selezneva selezn@cs.msu.ru

LOGIKA VÝROVNÍ Výrok Výrok je oznamovacia veta, ktorej obsah možno vyhodnotiť ako pravdivý alebo nepravdivý. Rozlišujte medzi: absolútne pravdivé tvrdenia, absolútne

Zdieľať P.G. Charkovská národná univerzita mechaniky a matematiky Fakulta diskrétnej matematiky. Poznámky k prednáške. Obsah 1. Výroková algebra a logika. 1.1 Príkazy a logické operácie...

Zákony logiky algebry To je zaujímavé! Matematika a De Morganov zákon Ako matematicky zapíšete, či bod x patrí úsečke? Dá sa to urobiť takto: 2 x 5. To znamená, že zároveň musíme

Matematická logika a teória algoritmov Pervukhin Michail Aleksandrovich Logický dôsledok v AB Hovoria, že vzorec ψ x 1, x n AB je logickým dôsledkom vzorcov φ 1 (x 1, x n), φ m x 1,

Moskovská štátna technická univerzita pomenovaná po N.E. Bauman Fakulta základných vied Katedra matematického modelovania A.N. KASIATOVIKOV

PREDNÁŠKA 21 POISSON BRACKETS. JACOBI-POISSONOVA VETA. KANONICKÉ TRANSFORMÁCIE 1. Poissonove zátvorky V poslednej prednáške bol predstavený koncept Lagrangeovej zátvorky. Tento výraz bol zložený z parciálnych derivátov

POUŽITE úlohu 8 („Znalosť základných pojmov a zákonov matematickej logiky“) ZÁKONY LOGICKEJ ALGEBRA X = X X /\ Y = Y /\ X X \/ Y = Y \/ X (X /\ Z) \/ (Y / \ Z )=(X \/ Y) /\ Z A\/ = A A/\ = A A/\ =. ZÁKONY ALGEBRA

KAPITOLA 6 Formalizmus Poissonových zátvoriek v klasickej mechanike 61 Poissonove zátvorky Poissonove zátvorky Nech sú dané dve dynamické veličiny, dve funkcie kanonických premenných a čas t: (a (Poissonova zátvorka

Laboratórne práce BERLEKAMP-MESSIE ALGORITHM NA HĽADANIE KOEFICIENTOV Spätnej väzby GENERÁTORA PSEUDONÁHODNÝCH SEKVENCIÍ Pozrime sa, ako môžeme obnoviť polynóm definujúci spätnú väzbu

K.Yu. Polyakov, M.A. Roitberg Systémy logických rovníc v úlohách jednotnej štátnej skúšky v informatike K.Yu. Polyakov, M.A. Roitberg, 0 http://kpolkov.sp.ru K.Yu. Polyakov, M.A. Roitberg, 0 http://kpolkov.sp.ru Výroba

Bitové operácie v problémoch jednotnej štátnej skúšky KIM v informatike K.Yu. Polyakov, doktor technických vied, učiteľ informatiky GBOU Stredná škola 163, Petrohrad Tento článok sa zaoberá nasledujúcim typom problémov (tieto problémy sa prvýkrát objavili

Ministerstvo školstva Ruskej federácie Don Štátna technická univerzita Katedra vyššej matematiky Problémy diskrétnej matematiky Rostov na Done 2001 MDT 517 Zostavil: Baranov

Chlapci, pokračujeme v štúdiu veľkej témy logaritmov, dnes sa pozrieme na to, ako vyriešiť rôzne rovnice, ktoré obsahujú logaritmy. Logaritmická rovnica je takáto rovnica

A3 (základná úroveň, čas 2 min) Téma: Konštrukcia pravdivostných tabuliek logických výrazov. O zápisoch, žiaľ, zápisy pre logické operácie AND, OR a NOT, akceptované v „serióznej“ matematickej

Doba chodu 4 hodiny. LABORATÓRNA PRÁCA 2 ALGEBRA LOGIKY Účel práce Preštudovať si základy algebry logiky. Ciele laboratórnej práce V dôsledku absolvovania vyučovacej hodiny musí študent: 1) poznať: definície

Nerovnice C C Príprava na Jednotnú štátnu skúšku 0 (materiál na prednášku pre učiteľov 8040) Prokofiev AA aaprokof@yanderu Základné metódy riešenia: Úlohy C Riešenie nerovností na intervaloch Zjednodušenie nerovností a redukcia

Príloha 1 SKUPINY, KRUHY, POLIA Pre kryptografiu je algebra jedným z hlavných nástrojov teoretického výskumu a praktickej konštrukcie kryptografických transformácií

Riešenie rovnice 1. Prejdite na predponový tvar zápisu rovnice, pričom symboly negácií nahraďte ¬ 2. Zostrojte názov pravdivostnej tabuľky špeciálneho typu 3. Vyplňte riadky pravdivostnej tabuľky pre všetky kombinácie A a B s dosadením 0 alebo 1 namiesto X. 4. Vytvorte pravdivostnú tabuľku pre X = F (A,B) 5. Pomocou pravdivostnej tabuľky určte typ funkcie X, ak je to potrebné, pomocou metód konštrukcie SCNF a SDNF, o ktorých sa bude diskutovať nižšie.

Zostrojenie pravdivostnej tabuľky špeciálneho tvaru ¬((A+B)·(X A·B))=¬(B+¬(X A))

Pravdivostná tabuľka X=F(A, B) ABX Zodpovedá negácii implikácie B v A ODPOVEĎ:

Kombinačné obvody logických prvkov Základné prvky (GOST): 1 A B Disjunkcia A B Ekvivalencia & A B Konjunkcia M2 A B XOR

Kombinačné obvody logických prvkov Základné prvky (GOST): 1 A B Implikácia & A B Schaefferov prvok & A B Koimplementácia 1 A B Webbov prvok

Príklad obvodu F 1 & 1 & & 1M2 B A

Riešenie obvodov 1 Možnosť - prevod obvodu do zložitého logického vyjadrenia a jeho následné zjednodušenie podľa zákonov logiky. Možnosť 2 – zostavenie pravdivostnej tabuľky a následne v prípade potreby konštrukcia cez SKNF alebo SDNF (pozri nižšie). Zvážme druhú možnosť, pretože je jednoduchšia a zrozumiteľnejšia.

Konštrukcia pravdivostnej tabuľky AB A + B + · B B · A + A B A + · ·

Pravdivostná tabuľka F(A, B) ABX Zodpovedá negácii implikácie B v A ODPOVEĎ:

SDNF a SKNF (definície) Elementárna konjunkcia je konjunkcia viacerých premenných, braných s negáciou alebo bez negácie, pričom medzi premennými môžu byť identické Elementárna disjunkcia sa nazýva disjunkcia viacerých premenných braných s negáciou alebo bez negácie a medzi premennými môžu byť identické Ľubovoľná disjunkcia elementárnych konjunkcií Nazvime to disjunktívna normálna forma (DNF) Nazvime ju ako konjunktívna normálna forma (DNF).

SDNF a SCNF (definície) Dokonalá disjunktívna normálna forma (PDNF) sa nazýva DNF, v ktorej neexistujú identické elementárne konjunkcie a všetky konjunkcie pozostávajú z rovnakej množiny premenných, v ktorých sa každá premenná vyskytuje iba raz (prípadne s negáciou). Dokonalá konjunktívna normálna forma (PCNF) je CNF, v ktorej neexistujú identické elementárne disjunkcie a všetky disjunkcie pozostávajú z rovnakej množiny premenných, v ktorých sa každá premenná vyskytuje iba raz (prípadne s negáciou).

Algoritmus na získanie SDNF z pravdivostnej tabuľky 1. Označte riadky pravdivostnej tabuľky, ktorých v poslednom stĺpci je 1. 2. Zapíšte ku každému označenému riadku konjunkciu všetkých premenných nasledovne: ak je hodnota premennej v daný riadok je 1, potom zahrňte túto premennú samotnú do spojky, ak sa rovná 0, potom jej negáciu. 3. Spojte všetky výsledné spojky do disjunkcie. Algoritmus na získanie SCNF z pravdivostnej tabuľky 1. Označte riadky pravdivostnej tabuľky, ktorých v poslednom stĺpci je 0. 2. Vypíšte ku každému označenému riadku disjunkciu všetkých premenných nasledovne: ak je hodnota premennej v daný riadok je 0, potom zahrňte túto premennú samotnú do spojky, ak sa rovná 1, potom jej negáciu. 3. Spojte všetky výsledné disjunkcie do konjunkcie.

Príklad konštrukcie SKNF XY F(X,Y) Označte nuly 2. Disjunkcie: X + Y 3. Spojka: (X + Y) · (X + Y)