Metoda řešení soustav logických rovnic. Systémy logických rovnic v jednotné státní zkoušce problémy v informatice Řešení logických rovnic v informatice online

Řešení rovnice 1. Přejděte na předponový tvar zápisu rovnice a nahraďte symboly negací ¬ 2. Sestrojte název pravdivostní tabulky speciálního typu 3. Vyplňte řádky pravdivostní tabulky pro všechny kombinace A a B s dosazením 0 nebo 1 místo X. 4. Vygenerujte pravdivostní tabulku pro X = F (A,B) 5. Pomocí pravdivostní tabulky určete typ funkce X, případně pomocí metod konstrukce SCNF a SDNF, které budou diskutovány níže.

Konstrukce pravdivostní tabulky speciálního tvaru ¬((A+B)·(X A·B))=¬(B+¬(X A))

Pravdivostní tabulka X=F(A, B) ABX Odpovídá negaci implikace B v A ODPOVĚĎ:

Kombinační obvody logických prvků Základní prvky (GOST): 1 A B Disjunkce A B Ekvivalence & A B Konjunkce M2 A B XOR

Kombinační obvody logických prvků Základní prvky (GOST): 1 A B Implikace & A B Schaefferův prvek & A B Koimplicitní 1 A B Webbův prvek

Příklad obvodu F 1 & 1 & & 1M2 B A

Řešení obvodů 1 Možnost - převod obvodu do složitého logického vyjádření a jeho následné zjednodušení podle zákonů logiky. Varianta 2 – konstrukce pravdivostní tabulky a následně v případě potřeby konstrukce prostřednictvím SKNF nebo SDNF (viz níže). Zvažme druhou možnost, protože je jednodušší a srozumitelnější.

Konstrukce pravdivostní tabulky AB A + B + · B B · A + A B A + · ·

Pravdivostní tabulka F(A, B) ABX Odpovídá negaci implikace B v A ODPOVĚĎ:

SDNF a SKNF (definice) Elementární konjunkce je konjunkce několika proměnných, braných s negací nebo bez negace, přičemž mezi proměnnými mohou být i identické Elementární disjunkce se nazývá disjunkce více proměnných, braná s negací nebo bez negace a mezi proměnnými mohou být shodné Libovolná disjunkce elementárních konjunkcí Říkejme tomu disjunktivní normální forma (DNF) Libovolnou konjunkci elementárních disjunkcí označme konjunktivní normální forma (DNF)

SDNF a SCNF (definice) Dokonalá disjunktivní normální forma (PDNF) se nazývá DNF, ve které neexistují identické elementární konjunkce a všechny konjunkce se skládají ze stejné množiny proměnných, ve kterých se každá proměnná vyskytuje pouze jednou (případně s negací). Dokonalá konjunktivní normální forma (PCNF) je CNF, ve které neexistují identické elementární disjunkce a všechny disjunkce se skládají ze stejné množiny proměnných, ve kterých se každá proměnná vyskytuje pouze jednou (případně s negací).

Algoritmus pro získání SDNF z pravdivostní tabulky 1. Označte řádky pravdivostní tabulky, v jejichž posledním sloupci je 1. 2. Zapište pro každý označený řádek konjunkci všech proměnných následovně: pokud je hodnota proměnné v daný řádek je 1, pak zahrňte tuto proměnnou samotnou do konjunkce, pokud se rovná 0, pak její negaci. 3. Spojte všechny výsledné spojky do disjunkce. Algoritmus pro získání SCNF z pravdivostní tabulky 1. Označte řádky pravdivostní tabulky, v jejichž posledním sloupci je 0. 2. Vypište pro každý označený řádek disjunkci všech proměnných následovně: je-li hodnota proměnné v daný řádek je 0, pak zahrňte tuto proměnnou samotnou do konjunkce, pokud se rovná 1, pak její negaci. 3. Spojte všechny výsledné disjunkce do konjunkce.

Příklad konstrukce SKNF XY F(X,Y) Označte nuly 2. Disjunkce: X + Y 3. Konjunkce: (X + Y) · (X + Y)

Velikost: px

Začněte zobrazovat ze stránky:

Přepis

1 Řešení logických rovnic a soustav logických rovnic Nechť F(x, x2, xn) je logická funkce n proměnných. Logická rovnice má tvar: F(x, x2, xn) = C, kde konstanta C má hodnotu nebo. Logická rovnice může mít až 2 n různých řešení. Je-li C rovno, pak řešením jsou všechny ty množiny proměnných z pravdivostní tabulky, na kterých funkce F nabývá hodnoty true (). Zbývající množiny jsou řešením rovnice s C rovným nule. Vždy můžete uvažovat pouze rovnice ve tvaru: F(x, x2, xn) = Opravdu, budiž rovnice dána: F(x, x2, xn) = V tomto případě můžete přejít na ekvivalentní rovnici: F( x, x2, xn) = Uvažujme soustavu k logických rovnic: F(x, x2, xn) = F2(x, x2, xn) = ( Fk(x, x2, xn) = Řešením soustavy je množina proměnných, na kterých jsou splněny všechny rovnice systému. V logických termínech funkce pro získání řešení systému logických rovnic bychom měli najít množinu, na které platí logická funkce Ф, představující konjunkci původních funkcí F: Ф = F F2 Fk 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é poskytnout řešení. V některých USE problémech hledání řešení systému logických rovnic dosáhne počet proměnných hodnoty. Pak se sestavení pravdivostní tabulky stává prakticky neřešitelným úkolem. K vyřešení problému je zapotřebí jiný přístup. Pro libovolný systém rovnic neexistuje žádná jiná obecná metoda než výčet, která umožňuje řešení takových problémů. U úloh navržených na zkoušce je řešení obvykle založeno na zohlednění specifik soustavy rovnic. Opakuji však, že kromě vyzkoušení všech možností pro sadu proměnných neexistuje obecný způsob, jak problém vyřešit. Řešení musí být postaveno na základě předloženého systému. Často je užitečné provést předběžné zjednodušení soustavy 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. Místo sestavování kompletní pravdivostní tabulky sestavíme její analog – binární rozhodovací strom. Každá větev tohoto stromu odpovídá

2 na jedno řešení a určuje množinu, na které má funkce Ф hodnotu. Počet větví v rozhodovacím stromě se shoduje s počtem řešení soustavy rovnic. Na příkladech několika problémů vysvětlím, co je binární rozhodovací strom a jak se staví. Problém Kolik různých sad hodnot logických proměnných x, x2, x3, x4, x5, y, y2, y3, y4, y5 existuje, které splňují systém dvou rovnic? (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Odpověď: Systém má 36 různých řešení. Soustava rovnic obsahuje dvě rovnice. Najděte počet řešení první rovnice v závislosti na 5 proměnných x, x2, x5. První rovnici lze zase považovat za soustavu 5 rovnic. znázorně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 (x x2) - první člen konjunkce, kterou lze považovat za první rovnici Zde je, jak vypadá grafické znázornění tohoto stromu: X X2 Strom se skládá ze dvou úrovní podle počtu proměnných v rovnici První úroveň popisuje první proměnnou X Dvě větve této úrovně odrážejí možné hodnoty této proměnné a. Na druhé úrovni větve stromu odrážejí pouze ty možné hodnoty proměnné X2, pro které platí rovnice. Protože rovnice určuje implikaci, větev, na které má X hodnotu, vyžaduje, aby X2 měla hodnotu na této větvi. Větev, na které má X hodnotu, vede ke dvěma větvím s hodnotami X2 rovnými a. Vytvořený strom specifikuje tři řešení, ve kterých implikace X X2 nabývá hodnoty. Na každé větvi je zapsána odpovídající sada proměnných hodnot, která dává řešení rovnice. Tyto množiny jsou: ((,), (,), (,)) Pokračujme ve vytváření rozhodovacího stromu přidáním následující rovnice, následující implikace X2 X3. 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á X2 již má hodnoty ve stromu, pak na všech větvích, kde má proměnná X2 hodnotu, bude mít hodnotu i proměnná X3. U takových větví pokračuje stavba stromu na další úroveň, ale nové větve se neobjevují. Jediná větev, kde má proměnná X2 hodnotu, se rozvětví na dvě větve, kde proměnná X3 obdrží hodnoty a. Každé přidání nové rovnice s přihlédnutím k jejím specifikům tedy přidává jedno řešení.

3 Původní první rovnice: (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = má 6 řešení. Zde je, jak vypadá úplný strom řešení pro tuto rovnici: X X2 X3 X4 X5 Druhá rovnice našeho systému je podobná první: (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Jediný rozdíl je v tom, že rovnice používá proměnné Y. Tato rovnice má také 6 řešení. Protože každé řešení pro proměnné Xi lze kombinovat s každým řešením pro proměnné Yj, 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 také samotná řešení napsaná na každé větvi stromu. Úloha 2 Kolik různých sad hodnot logických proměnných x, x2, x3, x4, x5, y, y2, y3, y4, y5 existuje, které splňují všechny níže uvedené podmínky? (x x2) ^ (x2 x3) ^ (x3 x4) ^ (x4 x5) = ((y y2) ^ (y2 y3) ^ (y3 y4) ^ (y4 y5) = (x y) = Odpověď: 3 Tento problém je modifikací předchozí úlohy. Rozdíl je v tom, že je přidána další rovnice týkající se proměnných X a Y. Z rovnice X Y vyplývá, že když X má hodnotu (existuje jedno takové řešení), pak má hodnotu Y. Tedy, existuje jedna sada , na které

4 X a Y mají význam. Když se X rovná, Y může mít libovolnou hodnotu, obojí a. Každá množina s X rovným, a takových množin je 5, tedy odpovídá všem 6 množinám s proměnnými Y. Celkový počet řešení je tedy 3. Úloha 3 Kolik řešení má rovnice: (X X2) ( X2 X3) (X3 X4) (X4 X5) (X5 X) = Odpověď: 2 Při vzpomínce na základní ekvivalence zapíšeme naši rovnici ve tvaru: (X X2) (X2 X3) (X3 X4) (X4 X5) (X5 X) = Cyklický řetězec implikací znamená identitu proměnných, takže naše rovnice je ekvivalentní rovnici: X X2 X3 X4 X5 = Tato rovnice má dvě řešení, když všechna Xi jsou buď nebo. Úloha 4 Kolik řešení má rovnice: (X X2) (X2 X3) (X3 X4) (X4 X2) (X4 X5) = Odpověď: 4 Stejně jako v úloze 2 přejděme od cyklických implikací k identitám a přepišme rovnice ve tvaru: (X X2) (X2 X3 X4) (X4 X5) = Postavme rozhodovací strom pro tuto rovnici: X X2 X3 X4 X5

5 Úloha 4 Kolik řešení má následující soustava rovnic? Odpověď: 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)) = Přejděme od proměnných k 5 proměnným zavedením následující změny proměnných: Y = (X X2); Y2 = (X3 X4); Y3 = (X5 X6); Y4 = (X7 X8); Y5 = (X9 X); Pak bude mít první rovnice tvar: (Y Y2 ) (Y Y2) = Rovnici lze zjednodušit tak, že ji napíšeme ve tvaru: (Y Y2) = Přejdeme k tradičnímu tvaru, systém po zjednodušeních zapíšeme ve tvaru: (Y Y2) = (Y2 Y3) = ( (Y3 Y4) = (Y4 Y5) = Rozhodovací strom pro tento systém je jednoduchý a skládá se ze dvou větví se střídajícími se hodnotami proměnných: Y Y2 Y3 Y4 Y5 Vrátíme-li se k původním proměnným X, poznamenáme, že každá hodnota proměnné Y odpovídají 2 hodnotám proměnných X, proto každé řešení v proměnných Y generuje 2 5 řešení v proměnných X. Dvě větve vytvářejí 2 * 2 5 řešení, takže celkový počet řešení je 64. Jak vidíte, každý problém řešení soustavy rovnic vyžaduje jiný přístup. Běžnou technikou je provádění ekvivalentních transformací pro zjednodušení rovnic.

6 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 (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 vzor vzhledu nových větví na každé následující úrovni, jak tomu bylo například v problému .

Putilov Viktor Vasilievich MAOU střední škola 46 Soustavy logických rovnic. Obsah Poznámka k nahrazení proměnných.... Problémy obsahující implikaci nebo její ekvivalentní zápis....2 Přítomnost dodatečné podmínky...6

Řešení soustavy logických rovnic. Kolik řešení má rovnice A BB C C D = 0 Počet množin proměnných je =. Můžete vytvořit pravdivostní tabulku a zkontrolovat, kolik sad odpovídá

Konstrukce a analýza pravdivostních tabulek logických výrazů. Jednotná státní zkouška 2015 2 (základní úroveň, čas 3 minuty) Příklad P-13. Každý booleovský výraz A a B závisí na stejné sadě 5 proměnných.

N B Rogov Jak se naučit řešit úlohu B15 jednotné státní zkoušky z informatiky (systémy logických rovnic) za 180+ minut Materiály pro hodiny Online sekce: http://basicschoolru/?page=eam_info_b15 Teoretický úvod:

B4 Téma: Převod logických výrazů. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT, akceptované ve „seriózní“ matematické logice (,), jsou nepohodlné a nejsou intuitivně jasné.

Matematika a matematické modelování MDT 004.023 Semenov Sergey Maksimovič Vladivostok Státní univerzita ekonomiky a služeb Rusko. Vladivostok O jednom způsobu řešení logických systémů

B4 (vysoká úroveň, čas 1 min) Téma: Převod logických výrazů. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT, akceptované ve „vážné“ matematické logice (,),

B0 (vysoká úroveň, čas 0 min) Téma: Převod logických výrazů. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT, akceptované ve „vážné“ matematické logice (,),

19022017 Bitové operace v problematice jednotné státní zkoušky KIM z informatiky Část II KYu Polyakov, dt.

Samostatná práce na téma „Metody zadávání logických funkcí“ 1. Vypočítejte hodnotu funkce F(x, y, z) = na množině proměnných (1, 1, 0). 3. Určete ekvivalenci funkcí F(x, y, z) = a G(x,

Logika je věda, která studuje metody stanovení pravdivosti nebo nepravdivosti některých tvrzení na základě pravdivosti nebo nepravdivosti jiných tvrzení. Výrok (rozsudek) je nějaká věta, která

B vysoká úroveň, čas 0 min) K. Polyakov, 009-0 Téma: Transformace logických výrazů. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT jsou akceptovány ve „seriózních“ matematických

Úloha 1: Je dán fragment pravdivostní tabulky výrazu F: Jaký výraz může být 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 Zvažte první výraz

FUNKCE LOGICKÉ ALGEBRA (pokračování) Počet booleovských funkcí n proměnných zjistíme vzorcem: P2 (n) = 2 2n Logické funkce dvou proměnných 6 Nejčastěji se používají tyto funkce: f (x,

Řešení úloh ve dvouhodnotové logice F.G. Korablev Úloha 1. Pro funkci f(x, y, z) = ((x y) (x z)) (z x) najděte podstatné a fiktivní proměnné, proveďte operaci eliminace fiktivních proměnných. Řešení.

051216 Bitové operace v problematice KIM Jednotná státní zkouška z informatiky Část II KYu Polyakov, doktor technických věd, učitel informatiky GBOU Střední škola 163, St. Petersburg Tento článek poprvé pojednává o problémech následujícího typu

Mironchik E.A., učitel informatiky, Novokuzněck Řešení úlohy Unified State Exam-18 s bitovými operacemi Popsaná metoda demonstruje metodu řešení založenou na identických přechodech, tzn. = "funguje"

Téma: Základní pojmy matematické logiky. Ukázkové otázky O zápisech Bohužel zápisy pro logické operace AND, OR a NOT používané ve „seriózní“ matematické logice (,) jsou nepohodlné a intuitivní.

Část 1 1. Uveďte, který 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 Řešení: Použití de Morganova vzorce (B \/ C) = B /\ C a

Glinka N.V. Použitý zápis Negace Násobení (konjunkce) Sčítání (disjunkce) Implikace Ekvivalence Příklady úloh před školním rokem 2010 Kolik různých řešení má rovnice ((K

Bitové operace v problémech KIM v informatice Typy problémů Tento webinář pojednává o problémech následujícího typu (tyto problémy se poprvé objevily v KIM na Unified State Exam 2015): Zaveďte výraz M & K, označující

Praktická práce 6 Řešení logických úloh pomocí zákonů logické algebry Cíl práce: posílení schopnosti transformovat logické výrazy pomocí zákonů logické algebry, počítat

A10 (základní úroveň, čas 1 min) Téma: Transformace logických výrazů. De Morganovy vzorce. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT jsou akceptovány ve „seriózních“ matematických

Gurskaya K.A., Ivin V.V., Semenov S.M. Řešení problémů matematické logiky v Jednotné státní zkoušce z informatiky 1 MDT 004.9 Gurskaya K.A., Ivin V.V., Semenov S.M. Učebnice „Řešení problémů matematické logiky v jednotné státní zkoušce“

OBSAH Předmluva................................... 3 Kapitola 1. Matematická logika...... ........ .... 4 1. Výroková algebra.................. 4 2. Booleovské algebry.......... ........ .... 12 3. Počet

PŘEDNÁŠKA 5 LOGICKÉ OPERACE V INFORMAČNÍ VĚDĚ 1. Matematická logika a informatika 2. Logické výrazy a logické operace 3. Konstrukce pravdivostních tabulek a logických funkcí 4. Logické zákony a pravidla

B5 vysoká úroveň, čas 0 min) Téma: Transformace logických výrazů. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT, akceptované ve „seriózní“ matematické logice, jsou nepohodlné,

Logická algebra Logická algebra je formální logická teorie, odvětví matematické logiky vyvinuté v 19. století anglickým matematikem Georgem Booleem. Algebra logiky používá algebraické metody

2 (základní úroveň, čas min) Téma: Konstrukce a rozbor pravdivostních tabulek logických výrazů. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT jsou akceptovány ve „seriózních“ matematických

A8 (základní úroveň, čas 1 min) Téma: Transformace logických výrazů. De Morganovy vzorce. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT jsou akceptovány ve „seriózních“ matematických

B15 Uveďte hodnoty proměnných K, L, M, N, pro které je logický výraz (K M) (L K) N nepravdivý. Napište svou odpověď jako řetězec čtyř znaků: hodnoty proměnných K, L, M a N (v tomto pořadí).

Základy logiky. Logické operace a pravdivostní tabulky Základy logiky. Logické operace a pravdivostní tabulky Tato stránka probere 6 logických operací: konjunkce, disjunkce, inverze,

Identity Booleovy algebry Hlavním úkolem matematické logiky je určit význam složitého tvrzení na základě nepravdivosti nebo pravdivosti jednoduchých tvrzení. Logické operace ve výrokové algebře

Městská rozpočtová vzdělávací instituce města Abakan „Střední škola 11“ Metodický vývoj k tématu Řešení úkolů typu 18 Jednotná státní zkouška z informatiky Atyushkina Marina Valerievna,

Téma 4. Logické základy POČÍTAČE 1. ZÁKLADNÍ INFORMACE Z LOGICKÉ ALGEBRA... 1 2. ZÁKONY LOGICKÉ ALGEBRA... 4 3. KONCEPCE MINIMALIZACE LOGICKÝCH FUNKCÍ... 6 4. TECHNICKÁ INTERPRETACE LOGICKÝCH FUNKCÍ...

Téma 9. Logické základy počítačů. 1. Logika. Informace zpracovávané v počítači jsou reprezentovány pomocí fyzikálních veličin, které mohou nabývat pouze dvou stabilních stavů a ​​nazývají se „binární proměnné“.

Iracionální nerovnosti Nerovnosti, ve kterých je proměnná obsažena pod kořenovým znakem, se nazývají iracionální Hlavní metodou řešení iracionálních nerovností je metoda redukce původní

26 transformací, sestavte správný řetězec uvažování a udělejte v poslední akci aritmetickou chybu. Všimněte si, že při řešení této úlohy dosáhne počtu pouze aritmetických operací

Regionální soutěž výukových, výzkumných a designových prací studentů „Aplikované otázky matematiky“ Algebra Algebra logiky Alena Sergeevna Semusheva, Městský vzdělávací ústav „Lyceum“ Perm, tř. Borková Olga Vladimirovna,

K. Polyakov, 009-0 B5 vysoká úroveň, čas 0 min) Téma: Transformace logických výrazů. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT jsou akceptovány ve „seriózních“ matematických

PRAKTICKÁ LEKCE 1 Lineární rovnice prvního řádu, Bernoulliho rovnice Rovnice v totálních diferenciálech Lineární diferenciální rovnice prvního řádu je rovnice + p(= q(Pokud

Moskevská státní technická univerzita pojmenovaná po N.E. Bauman Fakulta základních věd Katedra matematického modelování A.N. KAPITÁLNÍ DASHMANN

A9 (základní úroveň, čas 2 min) Téma: Konstrukce pravdivostních tabulek logických výrazů. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT jsou akceptovány ve „seriózních“ matematických

Mironchik E.A., MB NOU "Lyceum", Novokuzněck Způsob zobrazení Zadání. Kolik řešení má systém: Všechny rovnice zahrnuté v systému jsou stejného typu a každá rovnice obsahuje tři proměnné. Vědět

Federální agentura pro vzdělávání Uralská státní ekonomická univerzita Yu B. Melnikov Booleovské a logické funkce Část elektronické učebnice k přednášce e-mail: [e-mail chráněný],

E.V.Prosolupov 42. Booleovská algebra. Funkce logické algebry 1 Booleovské funkce Budeme uvažovat booleovské funkce - funkce, jejichž argumenty a hodnoty nabývají hodnot true a false. Pravda a lež budou

Federální agentura pro vzdělávání Uralská státní ekonomická univerzita Yu B. Melnikov Booleovské a logické funkce Část elektronické učebnice k přednášce Ed. 3., rev.

MINISTERSTVO ŠKOLSTVÍ A VĚDY RF Federální státní autonomní vzdělávací instituce vyššího odborného vzdělávání "NÁRODNÍ VÝZKUM TOMSK POLYTECHNIC UNIVERSITY"

Praktická práce 1 Logické operace. Ekvivalence vzorců Cíl práce: Naučit se sestavovat pravdivostní tabulky logických tvrzení a transformovat vzorce pomocí základních ekvivalencí Obsah

Říká se, že když Aristoteles přišel s logikou, oslavil to hostinou a nařídil porazit 40 ovcí. Od té doby ovce nemají rády logiku. Základní pojmy logické algebry, ročník 10, akademický rok 2017-2018

Diferenciální rovnice prvního řádu řešené s ohledem na derivaci Věta o existenci a jednoznačnosti řešení V obecném případě má diferenciální rovnice prvního řádu tvar F ()

Přednáška 2. Konjunktivní normální formy. Implicenta, prostá implicenta funkce. Snížená CNF funkcí logické algebry. Metody konstrukce zkráceného CNF. Přednáší Světlana Nikolaevna Selezneva [e-mail chráněný]

LOGIKA VÝROKŮ Výrok Výrok je deklarativní věta, jejíž obsah lze vyhodnotit buď jako pravdivý, nebo nepravdivý. Rozlišujte mezi: absolutně pravdivá tvrzení, absolutně

Sdílet P.G. Charkovská národní univerzita mechaniky a matematiky Fakulta diskrétní matematiky. Poznámky k výuce. Obsah 1. Výroková algebra a logika. 1.1 Příkazy a logické operace...

Zákony logiky algebry To je zajímavé! Matematika a De Morganův zákon Jak matematicky zapíšete, zda bod x patří úsečce? To lze provést takto: 2 x 5. To znamená, že zároveň musíme

Matematická logika a teorie algoritmů Pervukhin Michail Aleksandrovich Logický důsledek v AB Říkají, že formule ψ x 1, x n AB je logickým důsledkem formulí φ 1 (x 1, x n), φ m x 1,

Moskevská státní technická univerzita pojmenovaná po N.E. Bauman Fakulta základních věd Katedra matematického modelování A.N. KASIATOVIKOV

PŘEDNÁŠKA 21 POISSON BRACKETS. JACOBI-POISSONOVA VĚTA. KANONICKÉ TRANSFORMACE 1. Poissonovy závorky V minulé přednášce byl představen pojem Lagrangeova závorka. Tento výraz byl složen z parciálních derivací

POUŽÍVEJTE úkol 8 („Znalost základních pojmů a zákonů matematické logiky“) ZÁKONY LOGICKÉ 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 Formalismus Poissonových závorek v klasické mechanice 61 Poissonovy závorky Poissonovy závorky Nechť jsou dány dvě dynamické veličiny, dvě funkce kanonických proměnných a čas t: (a (Poissonova závorka

Laboratorní práce BERLEKAMP-MESSIE ALGORITHM PRO HLEDÁNÍ KOEFICIENTŮ ZPĚTNÉ VAZBY GENERÁTORU PSEUDONÁHODNÝCH SEKVENCÍ Uvažujme, jak můžeme obnovit polynom definující zpětnou vazbu

K.Yu Polyakov, M.A. Roitberg Systémy logických rovnic v úlohách jednotné státní zkoušky v informatice 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é operace v problémech KIM Unified State Examination in computer science K.Yu. Polyakov, doktor technických věd, učitel informatiky GBOU Střední škola 163, Petrohrad Tento článek pojednává o následujícím typu problémů (tyto problémy se objevily poprvé

Ministerstvo školství Ruské federace Don státní technická univerzita Katedra vyšší matematiky Problémy diskrétní matematiky Rostov na Donu 2001 MDT 517 Sestavil: Baranov

Chlapi, pokračujeme ve studiu velkého tématu logaritmů, dnes se podíváme na to, jak řešit různé rovnice, které obsahují logaritmy. Logaritmická rovnice je taková rovnice

A3 (základní úroveň, čas 2 min) Téma: Konstrukce pravdivostních tabulek logických výrazů. O zápisech Bohužel zápisy pro logické operace AND, OR a NOT jsou akceptovány ve „seriózních“ matematických

Doba provozu 4 hodiny. LABORATORNÍ PRÁCE 2 ALGEBRA LOGIKY Účel práce Prostudovat základy algebry logiky. Cíle laboratorní práce V důsledku absolvování lekce musí student: 1) znát: definice

Nerovnice C C Příprava na Jednotnou státní zkoušku 0 (materiál na přednášku pro učitele 8040) Prokofiev AA aaprokof@yanderu Základní metody řešení: Úlohy C Řešení nerovnic na intervalech Zjednodušování nerovností a redukce

Příloha 1 SKUPINY, KROUŽKY, POLE Pro kryptografii je algebra jedním z hlavních nástrojů teoretického výzkumu a praktické konstrukce kryptografických transformací.

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 problematice jednotné státní zkoušky v informatice

Část „Základy algebry logiky“ v úkolech jednotné státní zkoušky je považována za jednu z nejobtížnějších a nejobtížněji řešitelných. Průměrné procento splněných ú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 logické algebry
Algoritmizace a programování
Základy informačních a komunikačních technologií

Na základě specifikace KIM z roku 2018 tento blok obsahuje čtyři úkoly různých úrovní obtížnosti.

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

Úkol 23 má vysokou úroveň obtížnosti, proto má nejnižší procento dokončení. Mezi připravenými absolventy (81-100 bodů) splnilo úkol 49,8 %, středně připravení (61-80 bodů) 13,7 %, zbývající skupina studentů tento úkol nesplnila.

Ú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 pomocí metody 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 - logické 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 každá rovnice obsahuje č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. Uvažování 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), který zase povede k páru (x4, y4) a tak dále.

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

Tabulka pravdy:

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

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

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

(X1  X2 ) =1

(y1  y2 ) =1

Podívejme se na první rovnici. Důsledek je roven 1, když 0 0, 0 1, 1 1, což znamená (x1 y1)=0 pro (01), (10), pak dvojice (X2  y2 ) může být libovolný (00), (01), (10), (11), a když (x1 y1) = 1, to znamená (00) a (11), pár (x2 y2) = 1 má stejné hodnoty (00) a (11). Vynechme z tohoto řešení ty dvojice, pro které platí druhá a třetí rovnice, 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 pomocí 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í pro první rovnici. Pokud x1=0, pak x2, y2 - libovolný, pokud x1=1, pak x2, y2 nabývá hodnotu (11).

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

(X1 , y1 )	(X2 , y2 )

Vytvořme 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, vylučme pár (10). Najděte celkový počet řešení 1+7+0+34=42

3)(23.180) Kolik různých řešení má systém 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, takže pomocí uvažování najdeme všechny možné dvojice (x1,x2), (x3,x4) první rovnice.

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

Vynechme z řešení dvojice, které v posloupnosti dávají 0 (1 0), jedná se o dvojice (01, 00, 11) a (10).

Udělejme spojení mezi páry (x1,x2), (x3,x4)

Účel 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é.

Instrukce. Při zadávání z klávesnice používejte následující zápisy: Například logický výraz abc+ab~c+a~bc je třeba zadat takto: a*b*c+a*b=c+a=b*c
Chcete-li zadat data ve formě logického diagramu, použijte tuto službu.

Pravidla pro zadávání logické funkce

1. Místo symbolu v (disjunkce, OR) použijte znaménko +.
2. Není potřeba specifikovat označení funkce před logickou funkcí. Například místo F(x,y)=(x|y)=(x^y) stačí zadat (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ího oboru matematiky - logické algebry. 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 existujících vstupních proměnných, tato závislost se nazývá spínací funkce nebo funkce logické algebry.
Funkce logické algebry se nazývá zcela definovaná, pokud jsou dány všechny 2n 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 logické algebry.
K reprezentaci funkce logické algebry se používají následující metody:
V algebraické formě můžete sestavit obvod 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 operace pro každý je možný x logické hodnoty původních příkazů. Počet voleb odrážejících výsledek použití operací bude záviset na počtu příkazů v logickém výrazu. Pokud je počet příkazů 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 výchozími body 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ž je A pravdivé, B je pravdivé, nebo A i B jsou pravdivé, a nepravdivé, pokud jsou argumenty A a B 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ý bude pravdivý tehdy a pouze tehdy, když jsou pravdivé oba původní výrazy.
Používaná označení: 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, když jsou výroky A a B pravdivé a ve všech ostatních případech nepravdivé.

Operace „KDYŽ-PAK“ - logický důsledek (implicita)

Tato operace spojuje dva jednoduché logické výrazy, z nichž první je podmínkou a druhý je důsledkem této podmínky.
Používaná označení:
jestliže A, pak B; A znamená 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 implikace je nepravdivý pouze tehdy, je-li premisa A pravdivá a závěr B (důsledek) nepravdivý.

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

Použité 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 „Addition 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 v případě, že A a B jsou pravdivé nebo nepravdivé současně.

Priorita logických operací

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

Dokonalá disjunktivní normální forma

Dokonalá disjunktivní normální forma vzorce(SDNF) je ekvivalentní formule, která je disjunkcí elementárních spojek a 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. Ani jeden 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 SCNF jednoznačně definovány až do permutace.

Dokonalá konjunktivní normální forma

Dokonalá konjunktivní normální forma vzorce (SCNF) Toto je ekvivalentní vzorec, který je konjunkcí elementárních disjunkcí a splňuje 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 různé.
3. Každá elementární disjunkce obsahuje jednou proměnnou.
4. Ani jedna elementární disjunkce neobsahuje proměnnou a její negaci.

Tento materiál obsahuje prezentaci, která představuje metody řešení logických rovnic a soustav logických rovnic v úloze B15 (č. 23, 2015) Jednotné státní zkoušky z informatiky. Je známo, že tento úkol je jedním z nejobtížnějších mezi úkoly jednotné státní zkoušky. Prezentace může být užitečná při výuce na téma „Logika“ ve specializovaných hodinách a také při přípravě na Jednotnou státní zkoušku.

Stažení:

Náhled:

Chcete-li používat náhledy prezentací, vytvořte si účet Google a přihlaste se k němu: https://accounts.google.com

Popisky snímků:

Řešení úlohy B15 (systémy logických rovnic) Vishnevskaya M.P., MAOU “Gymnasium No. 3” 18. listopadu 2013, Saratov

Úloha B15 je jedním z nejtěžších v Jednotné státní zkoušce z informatiky!!! Testují se následující dovednosti: převádět výrazy obsahující logické proměnné; popsat přirozeným jazykem množinu hodnot logických proměnných, pro které je daná množina logických proměnných pravdivá; spočítat počet binárních množin, které splňují dané podmínky. Nejtěžší je, protože... neexistují žádná formální pravidla, jak to udělat, vyžaduje to dohady.

Bez čeho se neobejdete!

Bez čeho se neobejdete!

Symboly spojení: A /\ B , A  B , AB , A & B, A a B disjunkce: A \ / B , A + B , A | B , A nebo B negace:  A , A, nikoli A ekvivalence: A  B, A  B, A  B bez „nebo“: A  B , A xor B

Metoda nahrazování proměnných Kolik různých sad hodnot logických proměnných x1, x2, ..., x9, x10 existuje, které splňují všechny níže uvedené podmínky: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ ​​(¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ ​​​​(¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ ​​​​(¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ ​​​​(¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Odpověď nemusí uvádět všechny různé množiny x1, x2, …, x9, x10, pro které tento systém rovnosti platí. Jako odpověď musíte uvést počet takových sad (demo verze 2012)

Řešení Krok 1. Zjednodušte změnou proměnných t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Po zjednodušení: (t1 \/ t2) /\ (¬t1 \/ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Uvažujme jednu z rovnic: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Je zřejmé, že je to =1 pouze v případě, že jedna z proměnných je 0 a druhá 1 Použijme vzorec k vyjádření operace XOR pomocí konjunkce a disjunkce: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Krok 2. Systémová analýza ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 0 1 0 Т1 .Na. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), pak každá hodnota tk odpovídá dvěma párům hodnot ​​x2k-1 a x2k, například: tk =0 odpovídá dvěma párům - (0 ,1) a (1, 0) , a tk =1 – dvojice (0,0) a (1,1).

Krok 3. Počítání počtu řešení. Každé t má 2 řešení, počet ts je 5. Tedy. pro proměnné t existuje 2 5 = 32 řešení. Ale pro každé t odpovídá dvojice řešení x, tzn. původní systém má 2*32 = 64 řešení. Odpověď: 64

Metoda eliminace části řešení Kolik různých sad hodnot logických proměnných x1, x2, ..., x5, y1,y2,..., y5 existuje, které splňují všechny níže uvedené podmínky: (x1→ x2 )∧(x2→ x3)∧(x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5 → x5 =1. Odpověď nemusí vyjmenovávat všechny různé množiny x1, x2, ..., x5, y 1 , y2, ... , y5, pro které tento systém rovnosti platí. V odpovědi musí být uveden počet takových sad.

Řešení. Krok 1. Sekvenční řešení rovnic x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 První rovnicí je konjunkce více operací implikace, rovných 1, tzn. každá z implikací je pravdivá. Implikace je nepravdivá pouze v jednom případě, kdy 1  0, ve všech ostatních případech (0  0, 0  1, 1  1) operace vrací 1. Zapišme to do tabulky:

Krok 1. Sekvenční řešení rovnic T.o. Bylo získáno 6 sad řešení pro x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Obdobným uvažováním dojdeme k závěru, že pro y1, y2, y3, y4, y5 existuje stejná množina řešení. Protože tyto rovnice jsou nezávislé, tzn. nemají společné proměnné, pak řešení tohoto systému rovnic (bez zohlednění třetí rovnice) bude 6 * 6 = 36 párů „X“ a „Y“. Uvažujme třetí rovnici: y5→ x5 =1 Řešením jsou dvojice: 0 0 0 1 1 1 Dvojice není řešení: 1 0

Porovnejme získaná řešení Kde y5 =1, x5=0 není vhodné. takových dvojic je 5. Počet řešení soustavy: 36-5= 31. Odpověď: Bylo potřeba 31 kombinatoriky!!!

Metoda dynamického programování Kolik různých řešení má logická rovnice x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, kde x 1, x 2, …, x 6 jsou logické 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 množství takových sad.

Řešení Krok 1. Analýza podmínky Vlevo v rovnici jsou operace implikace zapsány sekvenčně, priorita je stejná. Přepišme: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 Pozn. Každá následující proměnná nezávisí na předchozí, ale na výsledku předchozí implikace!

Krok 2. Odhalení vzoru Uvažujme první implikaci, X 1 → X 2. Tabulka pravdy: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Z jedné 0 jsme dostali 2 jednotky a z 1 dostali jsme jednu 0 a jednu 1. Existuje pouze jedna 0 a tři jedničky, to je výsledek první operace.

Krok 2. Odhalení vzoru Spojením x 3 s výsledkem první operace dostaneme: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Od dvou 0 – dva 1, od každého 1 (jsou 3) jedna 0 a jedna 1 (3+3)

Krok 3. Odvození vzorce T.o. můžete vytvořit vzorce pro výpočet počtu nul N i a počtu jedniček E i pro rovnici s i proměnnými: ,

Krok 4. Vyplnění tabulky Vyplňme tabulku zleva doprava pro i = 6, přičemž pomocí výše uvedených vzorců vypočítáme počet nul a jedniček; tabulka ukazuje, jak je z předchozího sestaven další sloupec: počet proměnných 1 2 3 4 5 6 Počet nul N i 1 1 3 5 11 21 Počet jedniček E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Odpověď: 43

Metoda využívající zjednodušení logických výrazů Kolik různých řešení má rovnice ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 kde J, K, L, M, N jsou logické proměnné? Odpověď nemusí uvádět všechny různé sady hodnot J, K, L, M a N, pro které tato rovnost platí. Jako odpověď musíte uvést počet takových sad.

Řešení Všimněte si, že J → K = ¬ J  K Zaveďme změnu proměnných: J → K=A, M  N  L =B Přepišme rovnici s přihlédnutím ke změně: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Je zřejmé, že A  B pro stejné hodnoty A a B 6. Uvažujme poslední implikaci M → J =1 To je možné, pokud: M= J=0 M=0, J=1 M=J=1

Řešení Protože A  B, pak Když M=J=0 dostaneme 1 + K=0. Žádná řešení. Když M=0, J=1 dostaneme 0 + K=0, K=0 a N a L jsou libovolné, 4 řešení: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 11

Řešení 10. Když M=J=1 dostaneme 0+K=1 *N * L, nebo K=N*L, 4 řešení: 11. Celkem má 4+4=8 řešení Odpověď: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Zdroje informací: O.B. Bogomolová, D.Yu. Useňkov. B15: nové úkoly a nová řešení // Informatika, č. 6, 2012, str. 35 – 39. K.Yu. Polyakov. Logické rovnice // Informatika, č. 14, 2011, str. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektronický zdroj]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronický zdroj].