Logické rovnice v informatice online. Řešení logických rovnic

Metody řešení soustav logických rovnic

Systém logických rovnic můžete řešit například pomocí pravdivostní tabulky (pokud počet proměnných není příliš velký) nebo pomocí rozhodovacího stromu, po zjednodušení každé rovnice.

1. Metoda změny proměnných.

Zavedení nových proměnných umožňuje zjednodušit soustavu rovnic snížením počtu neznámých.Nové proměnné musí být na sobě nezávislé. Po vyřešení zjednodušeného systému je nutné se opět vrátit k původním proměnným.

Zvažte použití této metody na konkrétním příkladu.

Pří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

Řešení:

Zavedeme nové proměnné: А=(X1≡X2); B = (X3 = X4); С=(X5 ≡ X6); D = (X7 = X8); E=(X9 = X10).

(Pozor! Každá jejich proměnná x1, x2, ..., x10 musí být zahrnuta pouze v jedné z nových proměnných A, B, C, D, E, tedy nové proměnné jsou na sobě nezávislé).

Pak bude soustava rovnic vypadat takto:

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

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

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

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

Vytvořme rozhodovací strom výsledného systému:

Uvažujme rovnici A=0, tzn. (X1≡ X2) = 0. Má 2 kořeny:

		X1 ≡ X2

Ze stejné tabulky je vidět, že rovnice A \u003d 1 má také 2 kořeny. Uspořádejme počet kořenů na rozhodovacím stromě:

Chcete-li zjistit počet řešení pro jednu větev, musíte vynásobit počet řešení na každé úrovni. Levá větev má 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 řešení; pravá větev má také 32 řešení. Tito. celý systém má 32+32=64 řešení.

Odpověď: 64.

2. Metoda uvažování.

Složitost řešení soustav logických rovnic spočívá v objemnosti celého rozhodovacího stromu. Metoda uvažování vám umožňuje nepostavit celý strom úplně, ale zároveň pochopit, kolik větví bude mít. Zvažme tuto metodu na konkrétních příkladech.

Příklad 1 Kolik různých sad hodnot booleovských proměnných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 existuje, které splňují všechny následující podmínky?

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

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

x1\/y1 = 1

V odpovědi není třeba vypisovat všechny různé množiny hodnot proměnných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, pod kterými je daný systém rovnosti splněn. Jako odpověď musíte uvést počet takových sad.

Řešení :

První a druhá rovnice obsahují nezávislé proměnné, které souvisí s třetí podmínkou. Vytvořme rozhodovací strom pro první a druhou rovnici.

Pro reprezentaci rozhodovacího stromu systému z první a druhé rovnice je nutné pokračovat v každé větvi prvního stromu stromem pro proměnné na . Takto zkonstruovaný strom bude obsahovat 36 větví. Některé z těchto větví nesplňují třetí rovnici systému. Poznamenejte si na prvním stromě počet větví stromu"na" , které splňují třetí rovnici:

Ujasněme si: pro splnění třetí podmínky v x1=0 musí být y1=1, tedy všechny větve stromu"X" , kde x1=0 lze pokračovat pouze jednou větví ze stromu"na" . A to jen na jednu větev stromu"X" (vpravo) hodí všechny větve stromu"na". Kompletní strom celého systému tedy obsahuje 11 větví. Každá větev představuje jedno řešení původní soustavy rovnic. Celý systém má tedy 11 řešení.

Odpověď: 11.

Příklad 2 Kolik různých řešení má soustava rovnic

(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 jsou booleovské proměnné? Odpověď nemusí uvádět všechny různé sady hodnot proměnných, pro které tato rovnost platí. Jako odpověď musíte uvést počet takových sad.

Řešení : Pojďme si systém zjednodušit. Sestavme pravdivostní tabulku části první rovnice:

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

Věnujte pozornost poslednímu sloupci, shoduje se s výsledkem akce 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

Zvažte poslední rovnici:(X1 ≡ X10) = 0, tj. x1 by nemělo být totéž jako x10. Aby se první rovnice rovnala 1, musí platit rovnost(X1 ≡ X2) = 1, tj. x1 se musí shodovat s x2.

Vytvořme rozhodovací strom pro první rovnici:

Uvažujme druhou rovnici: pro x10=1 a pro x2=0 závorkumusí být rovno 1 (tj. x2 je stejné jako x3); při x10=0 a při x2=1 závorka(X2 ≡ X10)=0 , takže závorka (X2 ≡ X3) musí být rovno 1 (tj. x2 je stejné jako x3):

Tímto způsobem zkonstruujeme rozhodovací strom pro všechny rovnice:

Soustava rovnic má tedy pouze 2 řešení.

Odpověď: 2.

Příklad 3

Kolik různých sad hodnot booleovských proměnných x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 existuje, které splňují všechny následující podmínky?

(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

Řešení:

Sestavme rozhodovací strom první rovnice:

Zvažte druhou rovnici:

• Když x1=0 : druhá a třetí závorka bude 0; aby se první závorka rovnala 1, musí y1=1 , z1=1 (tj. v tomto případě - 1 řešení)
• S x1=1 : první závorka bude 0; druhý nebo třetí závorka musí být rovna 1; druhá závorka bude rovna 1, když y1=0 a z1=1; třetí závorka bude rovna 1 pro y1=1 a z1=0 (tj. v tomto případě - 2 řešení).

Podobně pro zbytek rovnic. Poznamenejte si počet řešení získaných pro každý uzel stromu:

Pro zjištění počtu řešení pro každou větev získaná čísla vynásobíme zvlášť pro každou větev (zleva doprava).

1 větev: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 roztok

2 větve: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 řešení

3. větev: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 řešení

4 větve: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 řešení

5 větví: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 řešení

Sečteme získaná čísla: celkem 31 řešení.

Odpověď: 31.

3. Pravidelné zvyšování počtu kořenů

V některých systémech závisí počet kořenů následující rovnice na počtu kořenů rovnice předchozí.

Příklad 1 Kolik různých sad hodnot booleovských proměnných x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 existuje, které splňují všechny následující podmínky?

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

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

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

Zjednodušit první rovnice:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Poté bude mít systém podobu:

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

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

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

Atd.

Každá následující rovnice má o 2 kořeny více než předchozí.

4 rovnice má 12 kořenů;

Rovnice 5 má 14 kořenů

8 rovnice má 20 kořenů.

Odpověď: 20 kořenů.

Někdy počet kořenů roste podle zákona Fibonacciho čísel.

Řešení soustavy logických rovnic vyžaduje kreativní přístup.

Obecní rozpočtová vzdělávací instituce

"Střední škola č. 18"

městská část města Salavat v Republice Bashkortostan

Soustavy logických rovnic

v úlohách zkoušky z informatiky

Část "Základy algebry logiky" v úlohách zkoušky je považována za jednu z nejtěžších a špatně vyřešených. Průměrné procento dokončení úkolů na toto téma je nejnižší a je 43,2.

Sekce kurzu	Průměrné procento dokončení podle skupin úkolů
Kódování informací a měření jejich množství
informační modelování
Číselné soustavy
Základy algebry logiky
Algoritmizace a programování
Základy informačních a komunikačních technologií

Na základě specifikace KIM 2018 tento blok zahrnuje čtyři úlohy různé úrovně složitosti.

№ úkoly	Kontrolovány obsahové prvky	Úroveň obtížnosti úkolu
	Schopnost sestavit pravdivostní tabulky a logické obvody
	Schopnost vyhledávat informace na internetu
	Znalost základních pojmů a zákonitostí matematická logika
	Schopnost vytvářet a transformovat logické výrazy

Úkol 23 je velmi obtížný, proto má nejnižší procento dokončení. Mezi proškolenými absolventy (81-100 bodů) jej splnilo 49,8 %, průměrně připravení (61-80 bodů) zvládá 13,7 %, zbývající skupina studentů tento úkol neplní.

Úspěšnost řešení soustavy logických rovnic závisí na znalosti zákonů logiky a na přesné aplikaci metod řešení soustavy.

Uvažujme řešení soustavy logických rovnic metodou mapování.

(23.154 Polyakov K.Yu.) Kolik různých řešení má soustava rovnic?

((X1  y1 )  (X2  y2 ))  (X1  X2 )  (y1  y2 ) =1

((X2  y2 )  (X3  y3 ))  (X2  X3 )  (y2  y3 ) =1

((X7  y7 )  (X8  y8 ))  (X7  X8 )  (y7  y8 ) =1

kde X1 , X2 ,…, X8, na1 ,y2 ,…,y8 - Booleovské proměnné? Odpověď nemusí uvádět všechny různé sady hodnot proměnných, pro které tato rovnost platí. Jako odpověď musíte uvést počet takových sad.

Řešení. Všechny rovnice zahrnuté v systému jsou stejného typu a v každé rovnici jsou zahrnuty čtyři proměnné. Když známe x1 a y1, můžeme najít všechny možné hodnoty x2 a y2, které splňují první rovnici. Argumentujeme-li podobným způsobem, ze známých x2 a y2 můžeme najít x3, y3, které splňují druhou rovnici. To znamená, že když známe pár (x1 , y1) a určíme hodnotu páru (x2 , y2) , najdeme pár (x3 , y3 ), což zase povede k páru (x4 , y4 ) a tak na.

Pojďme najít všechna řešení první rovnice. Toho lze dosáhnout dvěma způsoby: sestavením pravdivostní tabulky prostřednictvím uvažování a uplatňování zákonů logiky.

Tabulka pravdy:

				x 1  y 1	x2  y2	(x 1  y1)  (x 2  y2)	(x 1  x2)	(y 1  y2)	(x 1  x2)  (y 1  y2)

Sestavení pravdivostní tabulky je pracné a časově neefektivní, proto používáme druhý způsob – logické uvažování. Součin je 1 právě tehdy, když je každý faktor 1.

(X1  y1 )  (X2  y2 ))=1

(X1  X2 ) =1

(y1  y2 ) =1

Zvažte první rovnici. Následující se rovná 1, když 0 0, 0 1, 1 1, pak (x1 y1)=0 v (01), (10), pak dvojice (X2  y2 ) může být libovolné (00), (01), (10), (11) a pro (x1 y1)=1, tj. (00) a (11) má dvojice (x2 y2)=1 stejné hodnoty (00) a (11). Z tohoto řešení vyloučíme ty dvojice, pro které jsou druhá a třetí rovnice nepravdivé, tedy x1=1, x2=0, y1=1, y2=0.

(X1 , y1 )	(X2 , y2 )

Celkový počet párů 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Kolik různých řešení má systém logických rovnic

(X 1  (X 2  y 2 ))  (y 1  y 2 ) = 1

(X 2  (X 3  y 3 ))  (y 2  y 3 ) = 1

...

( X 6  ( X 7  y 7 ))  ( y 6  y 7 ) = 1

X 7  y 7 = 1

Řešení. 1) Rovnice jsou stejného typu, takže metodou uvažování najdeme všechny možné dvojice (x1,y1), (x2,y2) první rovnice.

(X1  (X2  y2 ))=1

(y1  y2 ) = 1

Řešením druhé rovnice jsou dvojice (00), (01), (11).

Pojďme najít řešení první rovnice. Pokud x1=0, pak x2 , y2 - libovolný, pokud x1=1, pak x2 , y2 nabývá hodnoty (11).

Udělejme spojení mezi dvojicemi (x1 , y1) a (x2 , y2).

(X1 , y1 )	(X2 , y2 )

Udělejme tabulku pro výpočet počtu párů v každé fázi.

							0

Zohlednění řešení poslední rovnice X 7  y 7 = 1, vyřadíme dvojici (10). Najděte celkový počet řešení 1+7+0+34=42

3)(23.180) Kolik různých řešení má soustava logických rovnic

(X1  X2 )  (X3  X4 ) = 1

(X3  X4 )  (X5  X6 ) = 1

(X5  X6 )  (X7  X8 ) = 1

(X7  X8 )  (X9  X10 ) = 1

X1  X3  X5  X7  X9 = 1

Řešení. 1) Rovnice jsou stejného typu, tedy metodou uvažování najdeme všechny možné dvojice (x1,x2), (x3,x4) první rovnice.

(X1  X2 )  (X3  X4 ) = 1

Z řešení vyloučíme dvojice, které dále dávají 0 (1 0), jedná se o dvojice (01, 00, 11) a (10).

Vytvořte odkazy mezi dvojicemi (x1,x2), (x3,x4)

Přiřazení služby. Online kalkulačka je určena pro sestavení pravdivostní tabulky pro logický výraz.
Pravdivostní tabulka - tabulka obsahující všechny možné kombinace vstupních proměnných a jim odpovídajících výstupních hodnot.
Pravdivostní tabulka obsahuje 2n řádků, kde n je počet vstupních proměnných a n+m jsou sloupce, kde m jsou výstupní proměnné.

Návod. Při zadávání z klávesnice použijte následující konvence:

booleovský výraz:

Výstup mezilehlých tabulek pro pravdivostní tabulku
Budova SKNF
Konstrukce SDNF
Konstrukce Zhegalkinova polynomu
Konstrukce mapy Veitch-Carnot
Minimalizace booleovské funkce

Například logický výraz abc+ab~c+a~bc je třeba zadat takto: a*b*c+a*b=c+a=b*c
Pro zadávání dat ve formě logického diagramu použijte tuto službu.

Pravidla pro zadávání logických funkcí

1. Místo v (disjunkce, OR) použijte znaménko +.
2. Před logickou funkcí nemusíte zadávat označení funkce. Například místo F(x,y)=(x|y)=(x^y) byste jednoduše napsali (x|y)=(x^y) .
3. Maximální počet proměnných je 10 .

Návrh a analýza počítačových logických obvodů se provádí pomocí speciální části matematiky - algebry logiky. V algebře logiky lze rozlišit tři hlavní logické funkce: "NOT" (negace), "AND" (konjunkce), "OR" (disjunkce).
Pro vytvoření libovolného logického zařízení je nutné určit závislost každé z výstupních proměnných na aktuálních vstupních proměnných, taková závislost se nazývá spínací funkce nebo funkce logické algebry.
Funkce logické algebry se nazývá plně definovaná, pokud jsou zadány všechny 2 n jejích hodnot, kde n je počet výstupních proměnných.
Pokud nejsou definovány všechny hodnoty, funkce se nazývá částečně definovaná.
Zařízení se nazývá logické, pokud je jeho stav popsán pomocí funkce algebry logiky.
K reprezentaci funkce logické algebry se používají následující metody:
V algebraické formě je možné sestrojit diagram logického zařízení pomocí logických prvků.


Obrázek 1 - Schéma logického zařízení

Jsou definovány všechny operace algebry logiky pravdivostní tabulky hodnoty. Pravdivostní tabulka určuje výsledek provedení operace pro vše možné x logické hodnoty původních příkazů. Počet voleb, které odrážejí výsledek použití operací, bude záviset na počtu příkazů v logickém výrazu. Pokud je počet výroků v logickém výrazu N, pak pravdivostní tabulka bude obsahovat 2 N řádků, protože existuje 2 N různých kombinací možných hodnot argumentů.

Operace NOT - logická negace (inverze)

Logická operace NENÍ aplikována na jediný argument, kterým může být jednoduchý nebo složitý logický výraz. Výsledek operace NENÍ následující:

• pokud je původní výraz pravdivý, pak výsledek jeho negace bude nepravdivý;
• pokud je původní výraz nepravdivý, pak výsledek jeho negace bude pravdivý.

Pro operaci negace NEJSOU přijímány následující konvence:
ne A, Ā, ne A, ¬A, !A
Výsledek operace negace NENÍ určen následující pravdivostní tabulkou:

A	ne A
0	1
1	0

Výsledek operace negace je pravdivý, když je původní výrok nepravdivý, a naopak.

Operace OR - logické sčítání (disjunkce, sjednocení)

Logická operace OR plní funkci spojení dvou příkazů, které mohou být jednoduchým nebo složitým logickým výrazem. Příkazy, které jsou počáteční pro logickou operaci, se nazývají argumenty. Výsledkem operace OR je výraz, který bude pravdivý tehdy a pouze tehdy, když je pravdivý alespoň jeden z původních výrazů.
Používaná označení: A nebo B, A V B, A nebo B, A||B.
Výsledek operace OR je určen následující pravdivostní tabulkou:
Výsledek operace OR je pravdivý, když A je pravda, nebo B je pravda, nebo A i B jsou pravdivé, a nepravda, když A i B jsou nepravdivé.

Operace AND - logické násobení (konjunkce)

Logická operace AND plní funkci průniku dvou výroků (argumentů), což může být buď jednoduchý, nebo složitý logický výraz. Výsledkem operace AND je výraz, který je pravdivý tehdy a pouze tehdy, když jsou pravdivé oba původní výrazy.
Použité symboly: A a B, A Λ B, A & B, A a B.
Výsledek operace AND je určen následující pravdivostní tabulkou:

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

Výsledek operace AND je pravdivý tehdy a pouze tehdy, jsou-li výroky A a B pravdivé i nepravdivé ve všech ostatních případech.

Operace IF-THEN - logický důsledek (implikace)

Tato operace spojuje dva jednoduché logické výrazy, z nichž první je podmínkou a druhý je důsledkem této podmínky.
Použité označení:
jestliže A, pak B; A přitahuje B; jestliže A pak B; A → B.
Tabulka pravdy:

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

Výsledek operace následku (implikace) je nepravdivý pouze tehdy, když premisa A je pravdivá a závěr B (důsledek) je nepravdivý.

Operace "A tehdy a jen tehdy, když B" (ekvivalence, ekvivalence)

Použitelné označení: A ↔ B, A ~ B.
Tabulka pravdy:

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

Operace přidávání Modulo 2 (XOR, exkluzivní nebo striktní disjunkce)

Použitý zápis: A XOR B, A ⊕ B.
Tabulka pravdy:

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

Výsledek operace ekvivalence je pravdivý pouze tehdy, jsou-li obě A i B pravdivé nebo obě nepravdivé.

Přednost logických operací

• Akce v závorkách
• Inverze
• Konjunkce (&)
• Disjunkce (V), Exclusive OR (XOR), modulo 2 součet
• Implikace (→)
• Ekvivalence (↔)

Dokonalá disjunktivní normální forma

Dokonalý disjunktivní normální tvar vzorce(SDNF) je jemu ekvivalentní formule, která je disjunkcí elementárních spojek, která má následující vlastnosti:

1. Každý logický člen vzorce obsahuje všechny proměnné obsažené ve funkci F(x 1 ,x 2 ,...x n).
2. Všechny logické členy vzorce jsou různé.
3. Žádný logický člen neobsahuje proměnnou a její negaci.
4. Žádný logický výraz ve vzorci neobsahuje stejnou proměnnou dvakrát.

SDNF lze získat buď pomocí pravdivostních tabulek, nebo pomocí ekvivalentních transformací.
Pro každou funkci jsou SDNF a SKNF jednoznačně definovány až do permutace.

Dokonalá konjunktivní normální forma

Dokonalá konjunktivní normální forma vzorce (SKNF) je jí ekvivalentní formule, která je konjunkcí elementárních disjunkcí, která splňuje následující vlastnosti:

1. Všechny elementární disjunkce obsahují všechny proměnné obsažené ve funkci F(x 1 ,x 2 ,...x n).
2. Všechny elementární disjunkce jsou zřetelné.
3. Každá elementární disjunkce obsahuje jednou proměnnou.
4. Žádná elementární disjunkce neobsahuje proměnnou a její negaci.

Jak vyřešit některé problémy v oddílech A a B zkoušky z informatiky

Lekce číslo 3. Logika. Logické funkce. Řešení rovnic

Velké množství úloh USE je věnováno logice návrhů. K vyřešení většiny z nich stačí znát základní zákony výrokové logiky, znalost pravdivostních tabulek logických funkcí jedné a dvou proměnných. Uvedu základní zákony výrokové logiky.

1. Komutativnost disjunkce a konjunkce:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Distributivní zákon týkající se disjunkce a konjunkce:
   a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negativní zápor:
   ¬(¬a) ≡ a
4. Konzistence:
   a ^ ¬a ≡ nepravda
5. Exkluzivní třetí:
   a ˅ ¬a ≡ pravda
6. De Morganovy zákony:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Zjednodušení:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ pravda ≡ a
   a ˄ nepravda ≡ nepravda
8. Vstřebávání:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Nahrazení implikace
   a → b ≡ ¬a ˅ b
10. Změna identity
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Reprezentace logických funkcí

Libovolnou logickou funkci n proměnných - F(x 1 , x 2 , ... x n) lze definovat pravdivostní tabulkou. Taková tabulka obsahuje 2 n množin proměnných, pro každou z nich je uvedena hodnota funkce na této množině. Tato metoda je dobrá, když je počet proměnných relativně malý. I pro n > 5 se zobrazení stává špatně viditelným.

Dalším způsobem je definovat funkci nějakým vzorcem pomocí známých poměrně jednoduchých funkcí. Systém funkcí (f 1 , f 2 , … f k ) se nazývá úplný, pokud lze jakoukoli logickou funkci vyjádřit vzorcem obsahujícím pouze funkce f i .

Systém funkcí (¬, ˄, ˅) je kompletní. Zákony 9 a 10 jsou příklady toho, jak jsou implikace a identita vyjádřeny prostřednictvím negace, konjunkce a disjunkce.

Ve skutečnosti je kompletní i systém dvou funkcí – negace a konjunkce nebo negace a disjunkce. Reprezentace vyplývají z De Morganových zákonů, které umožňují vyjádřit konjunkci prostřednictvím negace a disjunkce a v souladu s tím vyjádřit disjunkci prostřednictvím negace a konjunkce:

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

Paradoxně je systém skládající se pouze z jedné funkce kompletní. Existují dvě binární funkce – antikonjunkce a antidisjunkce, nazývané Pierceův šíp a Schaefferův zdvih, představující dutý systém.

Mezi základní funkce programovacích jazyků obvykle patří identita, negace, konjunkce a disjunkce. V úlohách zkoušky spolu s těmito funkcemi často existuje implikace.

Podívejme se na několik jednoduchých úloh souvisejících s logickými funkcemi.

Úkol 15:

Je uveden fragment pravdivostní tabulky. Která ze tří uvedených funkcí odpovídá tomuto fragmentu?

x1	x2	x3	x4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Funkce číslo 3.

K vyřešení problému potřebujete znát pravdivostní tabulky základních funkcí a mít na paměti priority operací. Připomínám, že konjunkce (logické násobení) má vyšší prioritu a provádí se před disjunkcí (logickým sčítáním). Při výpočtu je dobře vidět, že funkce s čísly 1 a 2 na třetí množině mají hodnotu 1 a z tohoto důvodu neodpovídají fragmentu.

Úkol 16:

Které z následujících čísel splňuje podmínku:

(číslice začínající nejvýznamnější číslicí, jdou sestupně) → (číslo - sudé) ˄ (nejnižší číslice - sudé) ˄ (nejvyšší číslice - liché)

Pokud existuje několik takových čísel, uveďte největší.

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

Podmínku splňuje číslo 4.

První dvě čísla nesplňují podmínku z toho důvodu, že nejnižší číslice je lichá. Konjunkce podmínek je nepravdivá, pokud je jedna z podmínek konjunkce nepravdivá. U třetího čísla není splněna podmínka pro nejvyšší číslici. U čtvrtého čísla jsou splněny podmínky kladené na vedlejší a velké číslice čísla. První člen spojky je také pravdivý, protože implikace je pravdivá, pokud je její premisa nepravdivá, což je tento případ.

Problém 17: Dva svědci vypovídali takto:

První svědek: Pokud je A vinen, pak B je zcela jistě vinen a C je nevinný.

Druhý svědek: Dva jsou vinni. A jeden ze zbývajících je rozhodně vinen a vinen, ale nedokážu přesně říct kdo.

Jaké závěry o vině A, B a C lze z důkazů vyvodit?

Odpověď: Ze svědectví vyplývá, že A a B jsou vinni, ale C je nevinný.

Řešení: Odpověď lze samozřejmě dát na základě zdravého rozumu. Ale podívejme se, jak to lze provést přísně a formálně.

První věc, kterou musíte udělat, je formalizovat prohlášení. Uveďme tři booleovské proměnné, A, B a C, z nichž každá je pravdivá (1), pokud je příslušný podezřelý vinen. Pak je výpověď prvního svědka dána vzorcem:

A → (B ˄ ¬C)

Výpověď druhého svědka je dána vzorcem:

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

Předpokládá se, že výpovědi obou svědků jsou pravdivé a představují spojení odpovídajících vzorců.

Vytvořme pravdivostní tabulku pro tato čtení:

A	B	C	F1	F2	Ž 1 Ž 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Souhrnné důkazy jsou pravdivé pouze v jednom případě, což vede k jasné odpovědi - A a B jsou vinni a C je nevinný.

Z rozboru této tabulky také vyplývá, že výpověď druhého svědka je vypovídající. Z pravdivosti jeho svědectví vyplývají pouze dvě možné možnosti - A a B jsou vinni a C je nevinný, nebo A a C jsou vinni a B je nevinen. Výpověď prvního svědka je méně vypovídající – existuje 5 různých možností, které odpovídají jeho výpovědi. Společně výpovědi obou svědků dávají jednoznačnou odpověď o vině podezřelých.

Logické rovnice a soustavy rovnic

Nechť F(x 1 , x 2 , …x n) je logická funkce n proměnných. Logická rovnice je:

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

Konstanta C má hodnotu 1 nebo 0.

Logická rovnice může mít 0 až 2n různých řešení. Je-li C rovno 1, pak řešením jsou všechny ty množiny proměnných z pravdivostní tabulky, na kterých má funkce F hodnotu true (1). Zbývající množiny jsou řešení rovnice pro C rovné nule. Vždy můžeme uvažovat pouze rovnice ve tvaru:

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

Vskutku, budiž dána rovnice:

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

V tomto případě můžete přejít na ekvivalentní rovnici:

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

Uvažujme systém k logických rovnic:

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

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

Fk (x 1, x 2, ... x n) = 1

Řešením soustavy je množina proměnných, na které jsou splněny všechny rovnice soustavy. Pokud jde o logické funkce, abychom získali řešení systému logických rovnic, měli bychom najít množinu, na které platí logická funkce Ф, představující konjunkci původních funkcí F:

Ф = F 1 ˄ F 2 ˄ … F k

Je-li počet proměnných malý, například menší než 5, pak není obtížné sestrojit pravdivostní tabulku pro funkci Ф, která umožňuje říci, kolik řešení má systém a jaké jsou množiny, které řešení dávají.

V některých úlohách Jednotné státní zkoušky na hledání řešení soustavy logických rovnic dosahuje počet proměnných hodnoty 10. Pak se sestavení pravdivostní tabulky stává téměř neřešitelným úkolem. Řešení problému vyžaduje jiný přístup. Pro libovolný systém rovnic neexistuje žádný obecný způsob, jiný než výčet, který umožňuje řešení takových problémů.

U úloh navržených ve zkoušce je řešení obvykle založeno na zohlednění specifik soustavy rovnic. Opakuji, kromě výčtu všech variant množiny proměnných neexistuje obecný způsob, jak problém vyřešit. Řešení musí být postaveno na základě specifik systému. Často je užitečné provést předběžné zjednodušení systému rovnic pomocí známých logických zákonů. Další užitečná technika pro řešení tohoto problému je následující. Nezajímají nás všechny množiny, ale pouze ty, na kterých má funkce Ф hodnotu 1. Místo sestavování úplné pravdivostní tabulky postavíme její analog - binární rozhodovací strom. Každá větev tohoto stromu odpovídá jednomu řešení a určuje množinu, na které má funkce Ф hodnotu 1. Počet větví v rozhodovacím stromě se shoduje s počtem řešení soustavy rovnic.

Co je binární rozhodovací strom a jak se staví, vysvětlím na příkladech několika úloh.

Problém 18

Kolik různých sad hodnot booleovských proměnných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 existuje, které splňují systém dvou rovnic?

Odpověď: Systém má 36 různých řešení.

Řešení: Soustava rovnic obsahuje dvě rovnice. Najděte počet řešení první rovnice v závislosti na 5 proměnných – x 1 , x 2 , …x 5 . První rovnici lze zase považovat za soustavu 5 rovnic. Jak bylo ukázáno, soustava rovnic ve skutečnosti představuje konjunkci logických funkcí. Platí i obrácené tvrzení – konjunkci podmínek lze považovat za soustavu rovnic.

Sestavme rozhodovací strom pro implikaci (x1→ x2), první člen konjunkce, který lze považovat za první rovnici. Takto vypadá grafické znázornění tohoto stromu:

Strom se skládá ze dvou úrovní podle počtu proměnných v rovnici. První úroveň popisuje první proměnnou X 1 . Dvě větve této úrovně odrážejí možné hodnoty této proměnné - 1 a 0. Na druhé úrovni větve stromu odrážejí pouze ty možné hodnoty proměnné X 2, pro které rovnice nabývá hodnotu true. Protože rovnice definuje implikaci, větev, na které má X 1 hodnotu 1, vyžaduje, aby na této větvi měl X 2 hodnotu 1. Větev, na které má X 1 hodnotu 0, generuje dvě větve s hodnotami X 2 rovnými 0 a 1 Sestrojený strom definuje tři řešení, na kterých implikace X 1 → X 2 nabývá hodnoty 1. Na každé větvi je zapsána odpovídající množina hodnot proměnných, která dává řešení rovnice.

Tyto sady jsou: ((1, 1), (0, 1), (0, 0))

Pokračujme ve vytváření rozhodovacího stromu přidáním následující rovnice, následující implikace X 2 → X 3 . Specifikem našeho systému rovnic je, že každá nová rovnice systému používá jednu proměnnou z předchozí rovnice a přidává jednu novou proměnnou. Protože proměnná X 2 již má ve stromu hodnoty, pak na všech větvích, kde má proměnná X 2 hodnotu 1, bude mít proměnná X 3 také hodnotu 1. U takových větví pokračuje konstrukce stromu další úroveň, ale neobjeví se žádné nové větve. Jediná větev, kde má proměnná X 2 hodnotu 0, poskytne větvení na dvě větve, kde proměnná X 3 nabude hodnoty 0 a 1. Každé přidání nové rovnice tedy vzhledem ke své specifičnosti přidá jednu řešení. Původní první rovnice:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
má 6 řešení. Zde je, jak vypadá úplný rozhodovací strom pro tuto rovnici:

Druhá rovnice našeho systému je podobná první:

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

Jediný rozdíl je v tom, že rovnice používá proměnné Y. Tato rovnice má také 6 řešení. Protože každé proměnné řešení X i lze kombinovat s každým proměnným řešením Y j , je celkový počet řešení 36.

Všimněte si, že sestrojený rozhodovací strom udává nejen počet řešení (podle počtu větví), ale i samotná řešení, napsaná na každé větvi stromu.

Problém 19

Kolik různých sad hodnot booleovských proměnných x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 existuje, které splňují všechny následující podmínky?

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

Tento úkol je modifikací předchozího úkolu. Rozdíl je v tom, že je přidána další rovnice, která dává do souvislosti proměnné X a Y.

Z rovnice X 1 → Y 1 vyplývá, že když má X 1 hodnotu 1 (jedno takové řešení existuje), pak má Y 1 hodnotu 1. Existuje tedy jedna množina, na které mají X 1 a Y 1 hodnoty ​​1. Když se X 1 rovná 0, Y 1 může mít libovolnou hodnotu, 0 i 1. Proto každá množina s X 1 rovna 0 a existuje 5 takových množin, odpovídá všem 6 množinám s proměnnými Y. , celkový počet řešení je 31 .

Problém 20

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

Řešení: Pamatujeme si základní ekvivalenci, zapíšeme naši rovnici jako:

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

Cyklický řetězec implikací znamená, že proměnné jsou identické, takže naše rovnice je ekvivalentní:

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

Tato rovnice má dvě řešení, když všechna X i jsou buď 1 nebo 0.

Problém 21

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

Řešení: Stejně jako v problému 20 přejdeme od cyklických implikací k identitám přepsáním rovnice do tvaru:

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

Vytvořme rozhodovací strom pro tuto rovnici:

Problém 22

Kolik řešení má následující soustava rovnic?

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

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

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

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

Odpověď: 64

Řešení: Pojďme z 10 proměnných na 5 proměnných zavedením následující změny proměnných:

Yi = (Xi = X2); Y 2 \u003d (X 3 ≡ X 4); Y3 = (X5 = X6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);

Pak bude mít první rovnice tvar:

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

Rovnici lze zjednodušit tak, že ji napíšete jako:

(Yi = Y2) = 0

Po přechodu na tradiční formu zapíšeme systém po zjednodušení ve tvaru:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Rozhodovací strom pro tento systém je jednoduchý a skládá se ze dvou větví se střídavými hodnotami proměnných:

Vrátíme-li se k původním X proměnným, všimněte si, že každá hodnota proměnné Y odpovídá 2 hodnotám proměnných X, takže každé řešení v proměnných Y generuje 2 5 řešení v proměnných X. Dvě větve generují 2 * 2 5 řešení , takže celkový počet řešení je 64.

Jak vidíte, každá úloha pro řešení soustavy rovnic vyžaduje svůj vlastní přístup. Běžným trikem je provádět ekvivalentní transformace pro zjednodušení rovnic. Běžnou technikou je konstrukce rozhodovacích stromů. Použitý přístup částečně připomíná konstrukci pravdivostní tabulky s tou zvláštností, že nejsou konstruovány všechny množiny možných hodnot proměnných, ale pouze ty, na kterých funkce nabývá hodnoty 1 (true). V navrhovaných problémech často není potřeba budovat úplný rozhodovací strom, protože již v počáteční fázi je možné stanovit pravidelnost vzhledu nových větví na každé další úrovni, jak tomu bylo například v problému 18 .

Obecně platí, že úlohy na hledání řešení soustavy logických rovnic jsou dobrá matematická cvičení.

Je-li problém ručně řešitelný, můžete jeho řešení svěřit počítači napsáním vhodného programu pro řešení rovnic a soustav rovnic.

Napsat takový program je snadné. Takový program se snadno vyrovná se všemi úkoly nabízenými ve zkoušce.

Kupodivu, ale úkol najít řešení soustav logických rovnic je pro počítač také obtížný, ukazuje se, že počítač má své limity. Počítač si hravě poradí s úkoly, kde je počet proměnných 20-30, ale nad většími úkoly začne dlouze přemýšlet. Jde o to, že funkce 2 n, která udává počet množin, je exponent, který s n rychle roste. Tak rychle, že běžný osobní počítač nezvládne úlohu se 40 proměnnými za den.

C# program pro řešení logických rovnic

Napsat program pro řešení logických rovnic je užitečné z mnoha důvodů, už jen proto, že jej lze použít ke kontrole správnosti vlastního řešení úloh testu USE. Dalším důvodem je, že takový program je vynikajícím příkladem programátorského problému, který splňuje požadavky na problémy kategorie C v USE.

Myšlenka sestavení programu je jednoduchá – je založena na úplném výčtu všech možných sad hodnot proměnných. Protože pro danou logickou rovnici nebo soustavu rovnic je znám počet proměnných n, je znám i počet množin - 2 n , které je potřeba roztřídit. Pomocí základních funkcí jazyka C# - negace, disjunkce, konjunkce a identity je snadné napsat program, který pro danou množinu proměnných vypočítá hodnotu logické funkce odpovídající logické rovnici nebo soustavě rovnic.

V takovém programu musíte sestavit cyklus podle počtu množin, v těle cyklu podle počtu množin, vytvořit samotnou množinu, vypočítat hodnotu funkce na této množině, a pokud je tato hodnota rovna do 1, pak množina dává řešení rovnice.

Jediný problém, který vzniká při implementaci programu, souvisí s úkolem vytvořit sadu proměnných hodnot samotným nastaveným číslem. Krása tohoto úkolu spočívá v tom, že tento zdánlivě obtížný úkol ve skutečnosti spočívá v jednoduchém úkolu, který se již opakovaně objevil. Ve skutečnosti stačí pochopit, že množina hodnot proměnných odpovídajících číslu i, skládající se z nul a jedniček, představuje binární reprezentaci čísla i. Složitý úkol získat sadu hodnot proměnných nastaveným číslem je tedy redukován na známý problém převodu čísla do binárního systému.

Takto vypadá funkce C#, která řeší náš problém:

///

/// program pro počítání počtu řešení

/// logická rovnice (systém rovnic)

///

///

/// logická funkce - metoda,

/// jehož podpis nastavuje delegát DF

///

/// počet proměnných

/// počet řešení

static int SolveEquations(DF fun, int n)

sada bool = new bool[n];

int m = (int)Math.Pow(2, n); //počet sad

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

//Úplný výčet podle počtu sad

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

//Vytvoření další množiny — množiny,

//dán binární reprezentací čísla i

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

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

//Výpočet hodnoty funkce na sadě

K pochopení programu doufám, že postačí vysvětlení myšlenky programu a komentáře v jeho textu. Zdržím se pouze u vysvětlení nadpisu výše uvedené funkce. Funkce SolveEquations má dva vstupní parametry. Parametr fun určuje logickou funkci odpovídající řešené rovnici nebo soustavě rovnic. Parametr n udává počet proměnných ve funkci fun. Výsledkem je, že funkce SolveEquations vrací počet řešení logické funkce, tedy počet množin, na kterých se funkce vyhodnotí jako true.

Pro školáky je zvykem, že u některé funkce F(x) je vstupním parametrem x proměnná aritmetického, řetězcového nebo booleovského typu. V našem případě je použito výkonnější provedení. Funkce SolveEquations odkazuje na funkce vyššího řádu - funkce typu F(f), jejichž parametry mohou být nejen jednoduché proměnné, ale i funkce.

Třída funkcí, které lze předat jako parametr funkci SolveEquations, je definována takto:

delegovat bool DF(bool vars);

Tato třída zahrnuje všechny funkce, které jsou předány jako parametr sady hodnot booleovských proměnných specifikovaných polem vars. Výsledkem je booleovská hodnota představující hodnotu funkce na této množině.

Na závěr uvedu program, ve kterém se funkce SolveEquations používá k řešení několika soustav logických rovnic. Funkce SolveEquations je součástí následující třídy ProgramCommon:

třída ProgramCommon

delegovat bool DF(bool vars);

static void Main (string args)

Console.WriteLine("Funkce a řešení - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("Funkce má 51 řešení - " +

SolveEquations(Zábava51, 5));

Console.WriteLine("Funkce má 53 řešení - " +

SolveEquations(Zábava53, 10));

statický bool FunAnd(bool vars)

return vars && vars;

statický bool Fun51 (bool vars)

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

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

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

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

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

statický bool Fun53 ​​(bool vars)

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

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

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

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

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

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

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

Takto vypadají výsledky řešení pro tento program:

10 úkolů pro samostatnou práci

1. Které z těchto tří funkcí jsou ekvivalentní:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. Je uveden fragment pravdivostní tabulky:

x1	x2	x3	x4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Která z těchto tří funkcí odpovídá tomuto fragmentu:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Porota se skládá ze tří osob. Rozhodnutí je přijato, pokud pro něj hlasuje předseda poroty, který podporuje alespoň jeden z členů poroty. Jinak se nerozhodne. Sestavte logickou funkci, která formalizuje proces rozhodování.
5. X vyhraje nad Y, pokud čtyři házení mincí padnou hlavou třikrát. Definujte booleovskou funkci popisující výplatu X.
6. Slova ve větě jsou číslována od jedné. Věta je považována za správně vytvořenou, pokud jsou splněna následující pravidla:
   1. Pokud sudé slovo končí samohláskou, pak další slovo, pokud existuje, musí začínat samohláskou.
   2. Pokud slovo s lichým číslem končí na souhlásku, pak další slovo, pokud existuje, musí začínat souhláskou a končit samohláskou.
      Která z následujících vět je správná:
   3. Máma umyla Mášu mýdlem.
   4. Vedoucí je vždy model.
   5. Pravda je dobrá, ale štěstí je lepší.
7. Kolik řešení má rovnice:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Uveďte všechna řešení rovnice:
   (a → b) → c = 0
9. Kolik řešení má následující soustava rovnic:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Kolik řešení má rovnice:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Odpovědi na úkoly:

1. Funkce b a c jsou ekvivalentní.
2. Fragment odpovídá funkci b.
3. Nechť má booleovská proměnná P hodnotu 1, když předseda poroty hlasuje „pro“ rozhodnutí. Proměnné M 1 a M 2 představují názor členů poroty. Logická funkce, která určuje přijetí kladného rozhodnutí, může být zapsána takto:
   P ˄ (M 1 ˅ M 2)
4. Nechť booleovská proměnná P i nabude hodnoty 1, když přijde i-tý hod mincí. Logická funkce, která definuje výplatu X, může být zapsána následovně:
   ¬((¬P 1 ˄ (¬P 2˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Nabídka b.
6. Rovnice má 3 řešení: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a=0; b=1; c=0)

Způsoby řešení soustav logických rovnic

Kirgizová E.V., Němková A.E.

Pedagogický institut Lesosibirsk -

pobočka Sibiřské federální univerzity v Rusku

Schopnost důsledně myslet, přesvědčivě argumentovat, vytvářet hypotézy, vyvracet negativní závěry nepřichází sama od sebe, tuto dovednost rozvíjí věda o logice. Logika je věda, která studuje metody stanovení pravdivosti nebo nepravdivosti některých tvrzení na základě pravdivosti nebo nepravdivosti jiných tvrzení.

Zvládnutí základů této vědy je nemožné bez řešení logických problémů. Kontrola formování dovedností uplatnit své znalosti v nové situaci se provádí absolvováním. Zejména se jedná o schopnost řešit logické problémy. Úlohy B15 ve zkoušce jsou úkoly se zvýšenou složitostí, protože obsahují soustavy logických rovnic. Systémy logických rovnic lze řešit různými způsoby. Jedná se o redukci na jednu rovnici, konstrukci pravdivostní tabulky, rozklad, sekvenční řešení rovnic atd.

Úkol:Vyřešte soustavu logických rovnic:

Zvážit metoda redukce na jednu rovnici . Tato metoda zahrnuje transformaci logických rovnic tak, aby se jejich pravé strany rovnaly pravdivostní hodnotě (tj. 1). K tomu použijte operaci logické negace. Pokud jsou pak v rovnicích složité logické operace, nahradíme je základními: „A“, „NEBO“, „NE“. Dalším krokem je spojení rovnic do jedné, ekvivalentní systému, pomocí logické operace „AND“. Poté byste měli provést transformace výsledné rovnice na základě zákonů algebry logiky a získat konkrétní řešení systému.

Řešení 1:Použijte inverzi na obě strany první rovnice:

Představme si implikaci prostřednictvím základních operací „NEBO“, „NE“:

Protože se levé strany rovnic rovnají 1, můžete je spojit pomocí operace „AND“ do jedné rovnice, která je ekvivalentní původnímu systému:

Otevřeme první závorku podle de Morganova zákona a transformujeme výsledek:

Výsledná rovnice má jedno řešení: A= 0, B=0 a C=1.

Další způsob je konstrukce pravdivostních tabulek . Protože logické veličiny mají pouze dvě hodnoty, můžete jednoduše projít všechny možnosti a najít mezi nimi ty, pro které daný systém rovnic vyhovuje. To znamená, že vytvoříme jednu společnou pravdivostní tabulku pro všechny rovnice systému a najdeme řádek s požadovanými hodnotami.

Řešení 2:Udělejme pravdivostní tabulku pro systém:

0	0	1	1	0	1

Tučně je označena čára, pro kterou jsou splněny podmínky problému. Takže A = 0, B = 0 a C = 1.

Cesta rozklad . Cílem je zafixovat hodnotu jedné z proměnných (postavit ji na 0 nebo 1) a tím zjednodušit rovnice. Potom můžete opravit hodnotu druhé proměnné a tak dále.

Řešení 3: Nechat A = 0, pak:

Z první rovnice dostaneme B =0 a od druhého - С=1. Systémové řešení: A = 0 , B = 0 a C = 1 .

Můžete také použít metodu sekvenční řešení rovnic , přidáním jedné proměnné do uvažované sady v každém kroku. K tomu je nutné transformovat rovnice tak, aby se proměnné zadávaly v abecedním pořadí. Dále vytvoříme rozhodovací strom a postupně do něj přidáváme proměnné.

První rovnice systému závisí pouze na A a B a druhá rovnice na A a C. Proměnná A může nabývat 2 hodnot 0 a 1:

Z první rovnice vyplývá, že , takže když A = 0 dostaneme B = 0 a pro A = 1 máme B = 1 . Takže první rovnice má dvě řešení s ohledem na proměnné A a B .

Nakreslíme druhou rovnici, ze které určíme hodnoty C pro každou možnost. Pro A =1 nemůže být implikace nepravdivá, to znamená, že druhá větev stromu nemá řešení. Na A= 0 dostaneme jediné řešení C= 1 :

Tak jsme dostali řešení soustavy: A = 0 , B = 0 a C = 1 .

V USE v informatice je velmi často nutné určit počet řešení soustavy logických rovnic, aniž bychom nacházeli samotná řešení, existují na to i určité metody. Hlavní způsob, jak zjistit počet řešení soustavy logických rovnic, je změna proměnných. Nejprve je nutné každou z rovnic co nejvíce zjednodušit na základě zákonů algebry logiky a následně nahradit složité části rovnic novými proměnnými a určit počet řešení nové soustavy. Poté se vraťte k náhradě a určete pro ni počet řešení.

Úkol:Kolik řešení má rovnice ( A → B) + (C → D ) = 1? Kde A, B, C, D jsou booleovské proměnné.

Řešení:Pojďme si představit nové proměnné: X = A → B a Y = C → D . S přihlédnutím k novým proměnným lze rovnici zapsat jako: X + Y = 1.

Disjunkce je pravdivá ve třech případech: (0;1), (1;0) a (1;1), while X a Y je implikace, to znamená, že je pravdivá ve třech případech a nepravdivá v jednom. Proto bude případ (0;1) odpovídat třem možným kombinacím parametrů. Případ (1;1) - bude odpovídat devíti možným kombinacím parametrů původní rovnice. Existuje tedy 3+9=15 možných řešení této rovnice.

Následující způsob, jak určit počet řešení soustavy logických rovnic, je − binární strom. Zvažme tuto metodu na příkladu.

Úkol:Kolik různých řešení má systém logických rovnic:

Daný systém rovnic je ekvivalentní rovnici:

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

Předstírejme toX 1 je pravda, pak z první rovnice dostaneme, žeX 2 také pravda, od druhého -X 3 =1 a tak dále, dokud x m= 1. Proto množina (1; 1; …; 1) z m jednotek je řešením systému. Nechte teďX 1 =0, pak z první rovnice mámeX 2 =0 nebo X 2 =1.

Když X 2 true, získáme, že ostatní proměnné jsou také pravdivé, tedy množina (0; 1; ...; 1) je řešením systému. NaX 2 =0 rozumíme tomu X 3 =0 nebo X 3 =, a tak dále. Pokračujeme-li k poslední proměnné, zjistíme, že řešením rovnice jsou následující sady proměnných ( m +1 řešení v každém řešení m proměnné hodnoty):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Tento přístup je dobře ilustrován vytvořením binárního stromu. Počet možných řešení je počet různých větví konstruovaného stromu. Je snadné vidět, že ano m+1.

Proměnné	Strom	Počet rozhodnutí
x 1
x2
x 3

V případě potíží s uvažováním a budováním rozhodovacího stromu můžete hledat řešení pomocí pravdivostní tabulky, pro jednu nebo dvě rovnice.

Přepíšeme soustavu rovnic do tvaru:

A udělejme pravdivostní tabulku zvlášť pro jednu rovnici:

x 1	x2	(x 1 → x 2)

Udělejme pravdivostní tabulku pro dvě rovnice:

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

Dále můžete vidět, že jedna rovnice platí v následujících třech případech: (0; 0), (0; 1), (1; 1). Systém dvou rovnic platí ve čtyřech případech (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). V tomto případě je hned jasné, že existuje řešení skládající se pouze z nul a více mřešení, ve kterých se přidává jedna jednotka, počínaje od poslední pozice, dokud nejsou obsazena všechna možná místa. Lze předpokládat, že obecné řešení bude mít stejnou formu, ale aby se takový přístup stal řešením, je nutný důkaz pravdivosti předpokladu.

Shrneme-li vše výše uvedené, rád bych upozornil na skutečnost, že ne všechny uvažované metody jsou univerzální. Při řešení každé soustavy logických rovnic by měly být brány v úvahu její vlastnosti, na základě kterých by měla být zvolena metoda řešení.

Literatura:

1. Logické úkoly / O.B. Bogomolov - 2. vyd. – M.: BINOM. Vědomostní laboratoř, 2006. - 271 s.: ill.

2. Polyakov K.Yu. Soustavy logických rovnic / Vzdělávací a metodické noviny pro učitele informatiky: Informatika č. 14, 2011