Tabulka hodnot logických operací. Problém syntézy logických obvodů na booleovské bázi

Vyberte řádky kde
a vypište spojky všech proměnných, navíc pokud je proměnná v této množině rovna 1, tak ji zapíšeme a pokud proměnná = 0, tak její negaci.

Pro tento příklad

konjunkce těchto disjunkcí bude požadovaný vzorec:

Definice: Spojení volal základní, pokud se všechny proměnné v něm obsažené liší. Nazývá se počet písmen zahrnutých v elementární konjunkci nebo elementární disjunkci hodnost.

Číslo 1 je považováno za elementární konjunkci hodnosti 0. Proměnná je považována za elementární konjunkci nebo elementární disjunkci hodnosti 1. Číslo 0 je považováno za elementární disjunkci hodnosti 0. Jakákoli konjunkce proměnných, která není shodně nepravdivá, může být redukována na elementární formu a jakákoliv disjunkce písmen, která není identicky pravdivá , může být také redukována na elementární formu. K tomu je potřeba uplatnit vlastnosti komutativnosti, idempotence a asociativnosti konjunkce a disjunkce.

Je důsledně dokázáno, že jakýkoli vzorec Booleovy algebry lze vyjádřit pomocí operací , &, . Intuitivně je tato skutečnost zřejmá, připomeňme si algoritmus pro sestavení vzorce podle pravdivostní tabulky. V tomto případě používáme pouze tyto operace. Tato forma psaní se nazývá disjunktivní normální forma(DNF). Toto je druh mechanismu pro normalizaci vzorců algebry logiky.

Definice: DNF je disjunkce různých elementárních spojek (tj. každá spojka se skládá z elementárních výroků nebo jejich negací).

Podobně je definován CNF – konjunktivní normální forma.

Definice: Pokud v DNF mají všechny elementární konjunkce stejnou hodnost rovnou počtu proměnných, na kterých závisí DNF, pak se nazývá perfektní (SDNF).

Teorém. Pro jakoukoli funkci, která není identicky nepravdivá, existuje jedinečný SDNF.

Následek . Jakoukoli booleovskou funkci, která není shodně nepravdivá, lze reprezentovat jako superpozici &,, a negace se vztahuje pouze na proměnné.

Definice: Systém logických operací se nazývá funkčně úplný, pokud je možné pomocí těchto operací a konstant tohoto systému reprezentovat jakoukoli funkci Booleovy algebry.

Systémy (&,,); (,); (&,),(/) jsou funkčně kompletní

(&,) - funkčně neúplné.

Tyto skutečnosti přijmeme bez důkazu a při řešení úloh se pokusíme znázornit libovolný vzorec pomocí (&, , ). Později probereme podrobněji problematiku funkční úplnosti a neúplnosti systému operací.

Téma 1.7. Metody pro zjednodušení logických výrazů. Metody řešení logických úloh.

Zvažte příklad řešení logického problému.

Příklad :

Po projednání složení účastníků výpravy bylo rozhodnuto, že musí být splněny dvě podmínky.

Pokud půjde Arbuzov, měli by jít Bryukvin nebo Višněvskij

Pokud odejdou Arbuzov a Višněvskij, půjde Bryukvin

Sestavte v symbolické podobě logický vzorec pro rozhodování, zjednodušte výsledný vzorec a na jeho základě formulujte novou podmínku pro vznik expedice.

Zaveďme proměnné a jim odpovídající elementární výroky.

- Arbuzov půjde

- Bryukvin půjde

- Višnevskij půjde

Pak budou rozvinuté podmínky pro vytvoření expedice vypadat takto:

Udělejme obecný vzorec a zjednodušíme výraz

těch. půjde-li Arbuzov, půjde Brjukvin.

Příklad:

Pokud bude zítra pěkné počasí, půjdeme na pláž nebo do lesa. Udělejme vzorec našeho chování pro zítřek.

- dobré počasí

- půjdeme na pláž

- půjdeme do lesa

Nyní sestrojme negaci této fráze

Že. získat prohlášení „Zítra bude dobré počasí a nepůjdeme do lesa a na pláž.

Ti, kteří si přejí, mohou sestavit pravdivostní tabulku a zkontrolovat toto tvrzení.

Příklad :

Brown, John a Smith jsou zadrženi pro podezření z trestného činu. Jeden z nich je ve městě vážený stařec, druhý úředník a třetí známý podvodník. Při vyšetřování starý muž řekl pravdu, podvodník lhal a třetí zadržený v jednom případě řekl pravdu a v druhém lhal.

Zde je to, co řekli:

Brown: Udělal jsem to. John za to nemůže. (B&D)

John: Není to Brownova chyba. Zločinec Smith. (B&S)

Smith: Není to moje chyba. Blame Brown (C&B)

Popišme tato prohlášení formálně:

Brown spáchal zločin

John spáchal zločin

Smith spáchal zločin

Poté jsou jejich slova popsána následujícími výrazy:

Hnědý:

John:

Kovář:

Protože podle podmínek problému jsou dvě z těchto & nepravdivé a jedna je pravdivá

Udělejme pravdivostní tabulku

Zůstává pouze případ 2, tzn. zločincem je Smith a oba jeho výroky jsou nepravdivé.

proto - nepravdivé a - skutečný

= 1 - John si vážil starého muže

Zůstává, že Brown je úředníkem a od té doby - tedy falešné - skutečný.

Pomocí zákonů a identit Booleovy algebry můžete zjednodušit logické výrazy.

Příklad :

Cvičení:

Konstrukce pravdivostních tabulek a logických funkcí

Booleovská funkce je funkce, ve které proměnné nabývají pouze dvou hodnot: logické jedničky nebo logické nuly. Pravda nebo nepravda složitých výroků je funkcí pravdivosti nebo nepravdy jednoduchých. Tato funkce se nazývá booleovská soudová funkce f(a, b).

Libovolnou logickou funkci lze zadat pomocí pravdivostní tabulky, na jejíž levé straně je zapsána sada argumentů, a na pravé straně - odpovídající hodnoty logické funkce. Při konstrukci pravdivostní tabulky je nutné vzít v úvahu pořadí, v jakém se logické operace provádějí.

Pořadí provádění logických operací ve složitém booleovském výrazu:

1. inverze;

2. spojení;

3. disjunkce;

4. implikace;

5. rovnocennost.

Závorky se používají ke změně zadaného pořadí operací.

Algoritmus pro konstrukci pravdivostních tabulek pro složité výrazy :

počet řádků = 2 n + řádek pro záhlaví ,

n je počet jednoduchých příkazů.

počet sloupců = počet proměnných + počet booleanů ;

určit počet proměnných (jednoduché výrazy);

určit počet logických operací a pořadí jejich provádění.

3. Do sloupců vyplňte výsledky provádění logických operací v uvedeném pořadí s přihlédnutím k pravdivostním tabulkám hlavních logických operací.

Příklad: Vytvořte pravdivostní tabulku logického výrazu:

D= A & (BPROTIC)

Řešení:

1. Určete počet řádků:

na vstupu jsou tři jednoduchá tvrzení: A, B, C, tedy n = 3 a počet řádků = 23 + 1 = 9.

2. Určete počet sloupců:

jednoduché výrazy (proměnné): A, B, C;

mezivýsledky (logické operace):

A- inverze (označená E);

BPROTIC- operace disjunkce (označuje se F);

a také požadovanou konečnou hodnotu aritmetického výrazu:

D= A & (BPROTIC) . tj. D = E & F je konjunkční operace.

Vyplňte sloupce s přihlédnutím k pravdivostním tabulkám logických operací.

font-size:12.0pt">Sestavení logické funkce z její pravdivostní tabulky:

Pokusme se vyřešit obrácený problém. Nechť je dána pravdivostní tabulka pro nějakou logickou funkci Z (X ,Y ):

font-size:12.0pt">1 .

Protože existují dvě čáry, dostaneme disjunkci dvou prvků: () PROTI () .

Každý logický prvek v této disjunkci zapíšeme jako spojení argumentů funkce X a Y : ( X & Y) PROTI ( X & Y).

Algebra logiky

Algebra logiky

Algebra logiky(Angličtina) algebra logiky) je jednou z hlavních větví matematické logiky, ve které se při logických transformacích používají metody algebry.

Zakladatelem algebry logiky je anglický matematik a logik J. Boole (1815-1864), který založil svou logickou doktrínu na analogii mezi algebrou a logikou. Zapsal jakékoli tvrzení pomocí symbolů jazyka, který vyvinul, a obdržel „rovnice“, jejichž pravdivost nebo nepravdivost bylo možné dokázat na základě určitých logických zákonů, jako jsou zákony komutativnosti, distributivity, asociativnosti atd.

Moderní algebra logiky je obor matematické logiky a studuje logické operace s výroky z hlediska jejich pravdivosti (pravda, nepravda). Výroky mohou být pravdivé, nepravdivé nebo mohou obsahovat pravdu a nepravdu v různém poměru.

logické tvrzení je jakákoli oznamovací věta, o níž lze jednoznačně prohlásit, že její obsah je pravdivý nebo nepravdivý.

Například „3 krát 3 se rovná 9“, „Arkhangelsk severně od Vologdy“ jsou pravdivá tvrzení a „pět je méně než tři“, „Mars je hvězda“ jsou nepravdivé.

Je zřejmé, že ne každá věta může být logickým tvrzením, protože ne vždy má smysl mluvit o její nepravdivosti nebo pravdě. Například tvrzení „Informatika je zajímavý předmět“ je vágní a vyžaduje další informace a tvrzení „Pro studenta 10. třídy Ivanov A. A. informatika je zajímavý předmět“, v závislosti na zájmech Ivanova A. A., může mít hodnotu „true“ nebo „lež“.

Až na dvouhodnotová výroková algebra, ve kterém jsou akceptovány pouze dvě hodnoty - "true" a "false", existuje vícehodnotová výroková algebra. V takové algebře se kromě významů „pravda“ a „nepravda“ používají také pravdivostní hodnoty jako „pravděpodobně“, „možné“, „nemožné“ atd.

V algebře se logika liší jednoduchý(základní) prohlášení, označované latinskými písmeny (A, B, C, D, ...), a komplex(složené), složené z několika jednoduchých pomocí logických spojek, např „ne“, „a“, „nebo“, „když a jen tehdy“, „pokud ... pak“. Pravdivost nebo nepravdivost takto získaných složitých tvrzení je určena významem jednoduchých tvrzení.

Označte jako A výrok "Algebra logiky byla úspěšně aplikována v teorii elektrických obvodů", a přes V- "Algebra logiky se používá při syntéze reléových kontaktních obvodů."

Pak složený výrok „Algebra logiky je úspěšně aplikována v teorii elektrických obvodů a v syntéze relé-kontaktních obvodů“ lze stručně napsat jako A a B; zde "a" je logické spojení. Pochopitelně od základních návrhů A a B jsou pravdivé, pak je složený výrok také pravdivý A a B.

Každá logická spojka je považována za operaci s logickými příkazy a má svůj vlastní název a označení.

Existují pouze dvě logické hodnoty: skutečný A false (FALSE). To odpovídá digitální reprezentaci − 1 A 0 . Výsledky každé logické operace lze zaznamenat ve formě tabulky. Takové tabulky se nazývají pravdivostní tabulky.

Základní operace logické algebry

1. Logická negace, inverze(lat. inverze- obrácení) - logická operace, jejímž výsledkem je z daného příkazu získán nový příkaz (například A) ( ne A), který se nazývá negaci původního tvrzení, označované symbolicky překřížením ($A↖(-)$) nebo konvencemi jako např. ¬, "ne" a zní: „ne ​​A“, „A je nepravdivé“, „není pravda, že A“, „negace A“. Například „Mars je planeta sluneční soustavy“ (výrok A); „Mars není planeta ve sluneční soustavě“ ($A↖(-)$); výrok „10 je prvočíslo“ (výrok B) je nepravdivý; výrok „10 není prvočíslo“ (výrok B) je pravdivý.

Zavolá se operace použitá s ohledem na jednu veličinu unární. Tabulka hodnot pro tuto operaci má tvar

$A↖(-)$ je nepravda, když A je pravda, a pravda, když A je nepravda.

Geometricky lze negaci znázornit takto: je-li A určitá množina bodů, pak $A↖(-)$ je doplněk množiny A, tedy všechny body, které do množiny A nepatří.

2.Spojení(lat. konjunkce- připojení) - logické násobení, operace, která vyžaduje alespoň dvě logické hodnoty (operandy) a spojuje dva nebo více příkazů pomocí svazku "A"(Například, "A a B"), který je symbolicky označen znakem ∧ (A ∧ B) a zní: „A a B“. Následující znaky se také používají k označení spojení: A ∙ B; A a B, A a B a někdy se mezi příkazy nedává žádné znaménko: AB. Příklad logického násobení: "Tento trojúhelník je rovnoramenný a pravoúhlý." Tento výrok může být pravdivý pouze tehdy, jsou-li splněny obě podmínky, jinak je výrok nepravdivý.

prohlášení A ∧ V pravdivé pouze tehdy, jsou-li obě tvrzení A A V skutečný.

Geometricky lze spojku znázornit takto: jestliže A, B A ∧ V dochází k průniku množin A A V.

3. Disjunkce(lat. disjunkce- dělení) - logické sčítání, operace, která spojuje dva nebo více příkazů pomocí svazku "nebo"(Například, "A nebo B"), který je symbolicky označen znakem ∨ (A∨ V) a zní: "A nebo B". Následující znaky se také používají k označení disjunkce: A + B; A nebo B; A | B. Příklad logického sčítání: "Číslo x je dělitelné 3 nebo 5." Toto tvrzení platí, pokud jsou splněny obě podmínky nebo alespoň jedna z podmínek.

Pravdivostní tabulka operace má tvar

prohlášení A∨ V je nepravdivé pouze tehdy, když jsou oba výroky A A V Nepravdivé.

Geometricky lze logické sčítání znázornit následovně: jestliže A, B jsou tedy nějaké sady bodů A ∨ V je spojení množin A A V, tedy obrazec, který kombinuje čtverec i kruh.

4. Striktní disjunkce disjunkce, modulo dva sčítání- logická operace, která spojuje dva příkazy pomocí spojky "nebo", používaný ve výlučném smyslu, který je symbolicky označen znaky ∨ ∨ nebo ⊕ ( A ∨ ∨ B, A ⊕ V) a zní: "Buď a nebo b". Příkladem sčítání modulo dva je výrok "Tento trojúhelník je tupý nebo ostrý." Tvrzení je pravdivé, pokud je splněna některá z podmínek.

Pravdivostní tabulka operace má tvar

Tvrzení A ⊕ B je pravdivé pouze tehdy, mají-li výroky A a B různý význam.

5. implikace(lat. implicitně- Pevně ​​spojuji) - logická operace, která spojuje dva příkazy pomocí svazku "když...tak" do komplexního výroku, který je symbolicky označen znakem → ( A → V) a zní: "jestliže A, pak B", "A implikuje B", "z A následuje B", "A implikuje B". Znaménko ⊃ (A ⊃ B) se také používá k označení implikace. Příklad implikace: "Pokud je výsledný čtyřúhelník čtverec, lze kolem něj opsat kruh." Tato operace spojuje dva jednoduché logické výrazy, z nichž první je podmínkou a druhý důsledkem. Výsledek operace je nepravdivý, pouze pokud je premisa pravdivá a důsledek nepravdivý. Například, "Pokud 3 * 3 = 9 (A), pak je Slunce planetou (B)", výsledek implikace A → B je nepravdivý.

Pravdivostní tabulka operace má tvar

Pro fungování implikace platí tvrzení, že ze lži může vyplývat cokoli, ale z pravdy pouze pravda.

6. Ekvivalence, dvojí implikace, ekvivalence(lat. aequalis- rovné a valentis- valid) - logická operace, která umožňuje dva příkazy A A V získat nový výpis A ≡ B který zní: "A je ekvivalentní B". K označení ekvivalence se také používají následující znaky: ⇔, ∼. Tato operace může být vyjádřena spojovacími výrazy „pokud a jen tehdy“, „nezbytné a dostatečné“, „ekvivalentní“. Příkladem ekvivalence je tvrzení: "Trojúhelník bude pravoúhlý právě tehdy, když jeden z úhlů bude roven 90 stupňům."

Pravdivostní tabulka operace ekvivalence má tvar

Operace ekvivalence je opakem sčítání modulo 2 a vyhodnocuje se jako true tehdy a jen tehdy, když jsou hodnoty proměnných stejné.

Při znalosti významů jednoduchých výroků je možné na základě pravdivostních tabulek určit významy složitých výroků. Zároveň je důležité vědět, že k reprezentaci jakékoli funkce algebry logiky stačí tři operace: konjunkce, disjunkce a negace.

Priorita logických operací je následující: negace ( "Ne") má nejvyšší prioritu, potom spojka ( "A"), po spojení — disjunkce ( "nebo").

Pomocí logických proměnných a logických operací lze formalizovat jakýkoli logický výrok, tedy nahradit jej logickým vzorcem. Přitom elementární výroky, které tvoří složený výrok, mohou být významově absolutně nesouvisející, ale to nebrání určit pravdivost nebo nepravdivost složeného výroku. Například výrok „Pokud je pět větší než dva ( A), pak úterý vždy následuje po pondělí ( V)" - implikace A→ V, a výsledek operace je v tomto případě "pravda". V logických operacích se nebere v úvahu význam výroků, uvažuje se pouze o jejich pravdivosti či nepravdivosti.

Zvažte například konstrukci složeného příkazu z příkazů A A V, což by bylo nepravdivé tehdy a jen tehdy, když jsou oba výroky pravdivé. V pravdivostní tabulce pro operaci sčítání modulo dva najdeme: 1 ⊕ 1 = 0. A tvrzení může být například toto: „Tato koule je úplně červená nebo úplně modrá.“ Pokud tedy prohlášení A"Tato koule je úplně červená" je pravda a tvrzení V„Tato koule je úplně modrá“ je pravda, pak je složené tvrzení nepravdivé, protože koule nemůže být zároveň červená i modrá.

Příklady řešení problémů

Příklad 1 Určete pro uvedené hodnoty X hodnotu logického příkazu ((X > 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Řešení. Posloupnost operací je následující: nejprve se provedou srovnávací operace v závorkách, poté disjunkce a provede se poslední implikační operace. Operátor disjunkce ∨ ​​je nepravdivý právě tehdy, když jsou oba operandy nepravdivé. Pravdivostní tabulka pro implikaci je

Odtud dostáváme:

1) pro X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) pro X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) pro X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Příklad 2 Zadejte množinu celočíselných hodnot X, pro které platí výraz ¬((X > 2) → (X > 5)).

Řešení. Operace negace se aplikuje na celý výraz ((X > 2) → (X > 5)) , takže když je výraz ¬((X > 2) → (X > 5)) pravdivý, výraz ((X > 2) →(X > 5)) je nepravda. Proto je nutné určit, pro které hodnoty X je výraz ((X > 2) → (X > 5)) nepravdivý. Operátor implikace nabývá hodnotu „false“ pouze v jednom případě: když z pravdy vyplývá nepravda. A to platí pouze pro X = 3; X = 4; X = 5.

Příklad 3 Pro které z následujících slov je tvrzení ¬(první písmenná samohláska ∧ třetí písmenná samohláska) ⇔ řetězec 4 znaků nepravdivé? 1) eso; 2) cookie; 3) kukuřice; 4) chyba; 5) silák.

Řešení. Podívejme se postupně na každé z následujících slov:

1) pro slovo assa dostáváme: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — tvrzení je pravdivé;

2) pro slovo kuku dostáváme: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — tvrzení je pravdivé;

3) pro slovo kukuřice dostáváme: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - tvrzení je nepravdivé;

4) pro slovo chyba dostáváme: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — tvrzení je pravdivé;

5) pro slovo silák dostáváme: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - tvrzení je nepravdivé.

Booleovské výrazy a jejich převod

Pod booleovský výraz je třeba chápat takový záznam, který může mít logickou hodnotu „true“ nebo „false“. S touto definicí je mezi logickými výrazy nutné rozlišovat mezi:

• výrazy, které používají porovnávací operace („větší než“, „menší než“, „rovná se“, „není rovno“ atd.) a nabývají logických hodnot (například výraz a > b, kde a = 5 a b = 7, rovná se "nepravda");
• přímé logické výrazy spojené s logickými hodnotami a logickými operacemi (například A ∨ B ∧ C, kde A = pravda, B = nepravda a C = pravda).

Booleovské výrazy mohou zahrnovat funkce, algebraické operace, porovnávací operace a logické operace. V tomto případě je priorita provádění akcí následující:

1. výpočet existujících funkčních závislostí;
2. provádění algebraických operací (nejprve násobení a dělení, poté odčítání a sčítání);
3. provádění srovnávacích operací (v náhodném pořadí);
4. provádění logických operací (nejprve operace negace, poté operace logického násobení, logické sčítání, poslední operace jsou implikace a ekvivalence).

Booleovský výraz může používat závorky, které mění pořadí, ve kterém jsou operace prováděny.

Příklad. Najděte hodnotu výrazu:

$1 ≤ a ∨ A ∨ sin(π/a – π/b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$ pro a = 2, b = 3, A = pravda, B = nepravda.

Řešení. Pořadí počítání hodnot:

1) b a + a b > a + b, po substituci dostaneme: 3 2 + 2 3 > 2 + 3, tj. 17 > 2 + 3 = pravda;

2) A ∧ B = pravda ∧ nepravda = nepravda.

Proto výraz v závorkách je (b a + a b > a + b ∨ A ∧ B) = pravda ∨ nepravda = pravda;

3) 1≤ a = 1 ≤ 2 = pravda;

4) sin(π/a – π/b)< 1 = sin(π/2 - π/3) < 1 = истина.

Po těchto výpočtech nakonec dostaneme: true ∨ A ∧ true ∧ ¬B ∧ ¬true.

Nyní je třeba provést negační operace, pak logické násobení a sčítání:

5) ¬B = ¬false = pravda; ¬pravda = nepravda;

6) A ∧ pravda ∧ pravda ∧ nepravda = pravda ∧ pravda ∧ pravda ∧ nepravda = nepravda;

7) pravda ∨ nepravda = pravda.

Výsledek logického výrazu pro dané hodnoty je tedy „pravda“.

Poznámka. Vzhledem k tomu, že původní výraz je v konečném důsledku součtem dvou členů a hodnota jednoho z nich 1 ≤ a = 1 ≤ 2 = true, bez dalších výpočtů můžeme říci, že výsledek pro celý výraz je také „pravda“. “.

Identitní transformace logických výrazů

V algebře logiky jsou naplněny základní zákony, které umožňují shodné transformace logických výrazů.

Důkazy těchto tvrzení jsou vytvářeny na základě konstrukce pravdivostních tabulek pro odpovídající záznamy.

Ekvivalentní transformace logických vzorců mají stejný účel jako transformace vzorců v běžné algebře. Slouží ke zjednodušení vzorců nebo jejich uvedení do určité formy pomocí základních zákonů algebry logiky. Pod zjednodušení vzorce, která neobsahuje operace implikace a ekvivalence, je chápána jako ekvivalentní transformace vedoucí ke vzorci, který obsahuje buď menší počet operací oproti původnímu, nebo menší počet proměnných.

Některé transformace logických vzorců jsou podobné transformacím vzorců v běžné algebře (závorkování společného faktoru, použití komutativních a asociativních zákonů atd.), zatímco jiné transformace jsou založeny na vlastnostech, které běžné algebrické operace nemají (pomocí distributivního zákona pro konjunkci, zákony absorpce, lepení, de Morganovy atd.).

Podívejme se na příklady některých technik a metod používaných při zjednodušování logických vzorců:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

K transformaci zde můžete použít zákon idempotence, distribuční zákon; variabilní operace s inverzí a konstantní operace.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Zde se pro zjednodušení uplatňuje zákon absorpce.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

Při převodu se uplatňuje de Morganovo pravidlo, operace proměnné s její inverzí, operace s konstantou

Příklady řešení problémů

Příklad 1 Najděte logický výraz ekvivalentní výrazu A ∧ ¬(¬B ∨ C) .

Řešení. Aplikujeme de Morganovo pravidlo pro B a C: ¬(¬B ∨ C) = B ∧ ¬C .

Získáme výraz ekvivalentní původnímu: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Odpovědět: A ∧ B ∧ ¬C.

Příklad 2 Uveďte hodnotu logických proměnných A, B, C, pro které je hodnota logického výrazu (A ∨ B) → (B ∨ ¬C ∨ B) nepravdivá.

Řešení. Operace implikace je nepravdivá pouze v případě, že a je z pravdivého předpokladu nepravda. Pro daný výraz tedy musí mít premisa A ∨ B hodnotu „pravda“ a důsledek, tedy výraz B ∨ ¬C ∨ B , musí mít hodnotu „nepravda“.

1) A ∨ B - výsledek disjunkce je "pravda", pokud je alespoň jeden z operandů "pravdivý";

2) B ∨ ¬C ∨ B - výraz je nepravdivý, pokud všechny členy mají hodnotu "nepravda", tj. B - "nepravda"; ¬C je "false", a proto má proměnná C hodnotu "true";

3) pokud vezmeme v úvahu premisu a vezmeme v úvahu, že B je „nepravda“, pak dostaneme, že hodnota A je „pravda“.

Odpovědět: A je pravda, B je nepravda, C je pravda.

Příklad 3 Jaké je největší celé číslo X, pro které je příkaz (35

Řešení. Zapišme si pravdivostní tabulku pro operaci implikace:

Výraz X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Odpovědět: X = 5.

Použití booleovských výrazů k popisu geometrických oblastí

K popisu geometrických oblastí lze použít booleovské výrazy. V tomto případě je problém formulován následovně: napište pro danou geometrickou oblast takový logický výraz, který pro hodnoty x, y nabývá hodnotu „true“ tehdy a jen tehdy, když patří jakýkoli bod se souřadnicemi (x; y) do geometrické oblasti.

Uvažujme popis geometrické oblasti pomocí logického výrazu na příkladech.

Příklad 1 Obraz geometrické oblasti je nastaven. Napište logický výraz popisující množinu bodů, které k němu patří.

1) .

Řešení. Danou geometrickou oblast lze znázornit jako množinu následujících oblastí: první oblast — D1 — polorovina $(x)/(-1) +(y)/(1) ≤ 1$, druhá — D2 — kružnice se středem v počátku $x ^2 + y^2 ≤ 1$. Jejich průsečík D1 $∩$ D2 je požadovaný region.

Výsledek: booleovský výraz $(x)/(-1)+(y)/(1) ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

Tato oblast může být zapsána následovně: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

Poznámka. Při konstrukci logického výrazu se používají nestriktní nerovnosti, což znamená, že do stínované oblasti patří i hranice obrazců. Pokud použijete striktní nerovnosti, pak se hranice nebudou brát v úvahu. Hranice, které nepatří do oblasti, jsou obvykle zobrazeny jako tečkované čáry.

Můžete vyřešit inverzní problém, a to: nakreslete oblast pro daný logický výraz.

Příklad 2 Nakreslete a vystínujte oblast, jejíž body splňují logickou podmínku y ≥ x ∧ y + x ≥ 0 ∧ y< 2 .

Řešení. Požadovaná oblast je průsečík tří polorovin. Stavíme na rovině (x, y) přímky y = x; y=-x; y = 2. Toto jsou hranice regionu a poslední hranice y = 2 do regionu nepatří, proto ho nakreslíme tečkovanou čarou. Pro splnění nerovnosti y ≥ x je nutné, aby body byly nalevo od přímky y = x a pro body, které jsou napravo od přímky y = -x, byla splněna nerovnost y = -x. Podmínka y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Použití logických funkcí k popisu elektrických obvodů

Logické funkce jsou velmi vhodné pro popis činnosti elektrických obvodů. Takže pro obvod znázorněný na obrázku, kde hodnota proměnné X je stav spínače (pokud je zapnutý, hodnota X je "pravda" a pokud je vypnutý - "nepravda"), toto hodnota Y je stav žárovky (pokud svítí) - hodnota je "true" a pokud ne - "false"), logická funkce bude zapsána následovně: Y = X . Zavolá se funkce Y vodivostní funkce.

Pro obvod znázorněný na obrázku má logická funkce Y tvar: Y = X1 ∪ X2, protože k rozsvícení žárovky stačí jeden spínač. V obvodu na obr., aby žárovka hořela, musí být oba spínače zapnuty, proto má funkce vodivosti tvar: Y \u003d X1 ∧ X2.

U složitějšího obvodu bude funkce vodivosti vypadat takto: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

Obvod může také obsahovat zapínací kontakty. V tomto případě otevřený kontakt jako spínač zajišťuje, že se žárovka rozsvítí při uvolnění tlačítka, nikoli stisknutí. Pro takové obvody je odpojovací spínač popsán negací.

Dvě schémata se nazývají ekvivalent, jestliže proud prochází jedním z nich, když prochází druhým. Ze dvou ekvivalentních obvodů je za jednodušší považován obvod, jehož vodivostní funkce obsahuje menší počet prvků.Úkol najít nejjednodušší schémata mezi ekvivalentními je velmi důležitý.

Využití aparátu logické algebry při návrhu logických obvodů

Matematický aparát algebry logiky je velmi vhodný pro popis toho, jak funguje hardware počítače. Jakákoli informace při zpracování na počítači je reprezentována v binární podobě, to znamená, že je zakódována určitou sekvencí 0 a 1. Zpracování binárních signálů odpovídajících 0 a 1 je v počítači prováděno logickými prvky. Logická hradla, která provádějí základní logické operace A NEBO NE, jsou uvedeny na Obr.

Symboly pro logické prvky jsou standardní a používají se při sestavování logických obvodů počítače. Pomocí těchto obvodů můžete implementovat jakoukoli logickou funkci, která popisuje činnost počítače.

Technicky je logický prvek počítače realizován jako elektrický obvod, což je spojení různých částí: diody, tranzistory, rezistory, kondenzátory. Logický prvek, nazývaný také hradlo, přijímá elektrické signály vysoké a nízké úrovně napětí na vstupu a jeden výstupní signál je také buď vysoký nebo nízký na výstupu. Tyto úrovně odpovídají jednomu ze stavů binárního systému: 1 - 0; PRAVDA – NEPRAVDA. Každý logický prvek má svůj symbol, který vyjadřuje jeho logickou funkci, ale neudává, který elektronický obvod je v něm implementován. To usnadňuje psaní a pochopení složitých logických obvodů. Činnost logických obvodů je popsána pomocí pravdivostních tabulek. Symbol na diagramu OR je znak "1" - ze zastaralého zápisu disjunkce jako ">=1" (hodnota disjunkce je 1, pokud je součet dvou operandů větší nebo roven 1). Znak „&“ v diagramu AND je zkrácený zápis anglického slova and.

Logické prvky se používají ke skládání elektronických logických obvodů, které provádějí složitější logické operace. Sada logických prvků, skládající se z prvků NOT, OR, AND, se kterými můžete sestavit logickou strukturu libovolné složitosti, se nazývá funkčně kompletní.

Konstrukce pravdivostních tabulek logických výrazů

Pro logický vzorec můžete vždy psát pravdivostní tabulka, tj. prezentovat danou logickou funkci v tabulkové formě. V tomto případě by tabulka měla obsahovat všechny možné kombinace argumentů funkcí (vzorců) a odpovídajících hodnot funkcí (výsledky vzorců pro danou sadu hodnot).

Vhodnou formou zápisu při hledání funkčních hodnot je tabulka obsahující kromě hodnot proměnných a funkčních hodnot také hodnoty mezivýpočtů. Uvažujme příklad sestavení pravdivostní tabulky pro formuli $(X1)↖(-) ∧ X2 ∨ (X1 ∨ X2)↖(-) ∨ X1$.

Pokud se funkce vyhodnotí jako 1 pro všechny sady hodnot proměnných, je tomu tak stejně pravdivé; pokud pro všechny sady vstupních hodnot funkce nabývá hodnotu 0, je stejně falešné; pokud sada výstupních hodnot obsahuje 0 i 1, je funkce volána proveditelné. Výše uvedený příklad je příkladem identicky pravdivé funkce.

Znáte-li analytickou formu logické funkce, můžete vždy přejít na tabulkovou formu logických funkcí. Pomocí dané pravdivostní tabulky můžete vyřešit inverzní problém, konkrétně: pro danou tabulku sestavte analytický vzorec pro logickou funkci. Existují dvě formy konstrukce analytické závislosti logické funkce podle tabulkově dané funkce.

1. Disjunktivní normální forma (DNF) je součet produktů vytvořených z proměnných a jejich negací pro falešné hodnoty.

Algoritmus pro konstrukci DNF je následující:

1. v pravdivostní tabulce vybírají funkce sady argumentů, pro které jsou logické formy rovny 1 („pravda“);
2. všechny vybrané logické množiny jako logické součiny argumentů jsou zaznamenány jejich sekvenčním spojováním pomocí operace logického součtu (disjunkce);
3. pro argumenty, které jsou nepravdivé, je do vytvořeného zápisu uvedena operace negace.

Příklad. Sestavte funkci, která určí, že první číslo se rovná druhému, pomocí metody DNF. Pravdivostní tabulka funkce má tvar

Řešení. Vybíráme sady hodnot argumentů, ve kterých je funkce rovna 1. Jedná se o první a čtvrtý řádek tabulky (řádek záhlaví se při číslování nebere v úvahu).

Zapíšeme logické součiny argumentů těchto množin a spojíme je s logickým součtem: X1 ∧ X2 ∨ X1 ∧ X2 .

Zapíšeme negaci argumentů vybraných množin, které mají nepravdivou hodnotu (čtvrtý řádek tabulky; druhá množina ve vzorci; první a druhý prvek): X1 ∧ X2 ∨ $(X1)↖(- )$ ∧ $(X2)↖(-)$.

Odpovědět: F(X1, X2) = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

2. Konjunktivně normální forma (CNF) je součin součtů vytvořených z proměnných a jejich negací pro skutečné hodnoty.

Algoritmus pro konstrukci CNF je následující:

1. v pravdivostní tabulce jsou vybrány sady argumentů, pro které jsou logické formy 0 („false“);
2. všechny vybrané logické množiny jako logické součty argumentů se zapisují postupně a spojují je navzájem operací logického součinu (konjunkce);
3. pro argumenty, které jsou pravdivé, je operace negace uvedena v konstruovaném zápisu.

Příklady řešení problémů

Příklad 1 Zvažte předchozí příklad, tj. pomocí metody CNF sestavíme funkci, která určí, že první číslo se rovná druhému. Pro danou funkci má její pravdivostní tabulka tvar

Řešení. Vybíráme sady hodnot argumentů, ve kterých je funkce rovna 0. Jedná se o druhý a třetí řádek (řádek záhlaví se při číslování nebere v úvahu).

Zapíšeme logické součty argumentů těchto množin a spojíme je s logickým součinem: X1 ∨ X2 ∧ X1 ∨ X2 .

Zapíšeme negaci argumentů vybraných množin, které mají pravdivou hodnotu (druhý řádek tabulky, první množina vzorce, druhý prvek; pro třetí řádek, a to je druhá množina vzorce , první prvek): X1 ∨ $(X2)↖(-)$ ∧ $( X1)↖(-)$ ∨ X2.

Tak byl získán záznam logické funkce v CNF.

Odpovědět: X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2.

Hodnoty funkcí získané těmito dvěma metodami jsou ekvivalentní. K prokázání tohoto tvrzení použijeme logická pravidla: F(X1, X2) = X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2 = X1 ∧ $(X1)↖ (-)$ ∨ X1 ∧ X2 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ $(X2)↖(-)$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $(X2 )↖(- )$ ∧ $(X1)↖(-)$ ∨ 0 = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

Příklad 2. Sestavte logickou funkci pro danou pravdivostní tabulku:

Požadovaný vzorec: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 .

Lze to zjednodušit: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 = X2 ∧ (X1 ∨ $(X1)↖(-)$) = X2 ∧ 1 = X2.

Příklad 3 Pro danou pravdivostní tabulku sestrojte logickou funkci pomocí metody DNF.

Požadovaný vzorec: X1 ∧ X2 ∧ X ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∪ X1 ∧ $(X2)ↈ(-)$ (X3)↖(-)$.

Vzorec je poměrně těžkopádný a měl by být zjednodušen:

X1 ∧ X2 ∧ X3 ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∨ X1 ∧ $(X2)↖(-)X3) $ ↖(-)$ = X2 ∧ X3 ∧ (X1 ∨ $(X1)↖(-)$) ∨ X1 ∧ $(X3)↖(-)$ ∧ (X2 ∨ $(X2)↖(-)$) = X2 ∧ X3 ∨ X1 ∧ $(X3)↖(-)$.

Pravdivé tabulky pro řešení logických problémů

Sestavování pravdivostních tabulek je jedním ze způsobů řešení logických problémů. Při použití tohoto způsobu řešení jsou podmínky, které problém obsahuje, fixovány pomocí speciálně sestavených tabulek.

Příklady řešení problémů

Příklad 1 Vytvořte pravdivostní tabulku pro bezpečnostní zařízení, které používá tři senzory a spustí se, když se zavřou pouze dva z nich.

Řešení. Je zřejmé, že výsledkem řešení bude tabulka, ve které bude požadovaná funkce Y(X1, X2, X3) pravdivá, pokud jsou pravdivé libovolné dvě proměnné.

Příklad 2 Udělejte si rozvrh hodin na daný den, vzhledem k tomu, že hodina informatiky může být pouze první nebo druhá, hodina matematiky – první nebo třetí a hodina fyziky – druhá nebo třetí. Je možné vytvořit rozvrh, který splňuje všechny požadavky? Kolik možností rozvrhu existuje?

Řešení. Problém lze snadno vyřešit, pokud vytvoříte příslušnou tabulku:

Tabulka ukazuje, že pro požadovaný rozvrh existují dvě možnosti:

1. matematika, informatika, fyzika;
2. informatika, fyzika, matematika.

Příklad 3 Na sportovní soustředění přijeli tři kamarádi - Peter, Boris a Alexej. Každý z nich má rád dva sporty. Je známo, že takových sportů je šest: fotbal, hokej, lyžování, plavání, tenis, badminton. Je také známo, že:

1. Boris je nejstarší;
2. hrát fotbal je mladší než hrát hokej;
3. hraje fotbal a hokej a Peter bydlí ve stejném domě;
4. když dojde k hádce mezi lyžařem a tenistou, Boris je usmíří;
5. Petr neumí hrát tenis ani badminton.

Jaké sporty každého z kluků baví?

Řešení. Udělejme tabulku a zohledněme v ní podmínky problému a do odpovídajících buněk doplňte čísla 0 a 1 podle toho, zda je odpovídající tvrzení nepravdivé nebo pravdivé.

Protože existuje šest sportů, ukázalo se, že všichni chlapci mají rádi různé sporty.

Z podmínky 4 vyplývá, že Boris nemá rád lyžování ani tenis, a z podmínek 3 a 5, že Peter nemůže hrát fotbal, hokej, tenis a badminton. V důsledku toho jsou Petrovými oblíbenými sporty lyžování a plavání. Dáme to do tabulky a zbývající buňky ve sloupcích „Lyžování“ a „Plavání“ doplníme nulami.

Tabulka ukazuje, že tenis může hrát pouze Aleksey.

Podmínky 1 a 2 naznačují, že Boris není fotbalista. Alexej tedy hraje fotbal. Pokračujme ve vyplňování tabulky. Zadejme nuly do prázdných buněk řádku "Alexey".

Nakonec jsme zjistili, že Boris má rád hokej a badminton. Finálový stůl bude vypadat takto:

Odpovědět: Petr rád lyžuje a plave, Boris hraje hokej a badminton a Alexej hraje fotbal a tenis.

Definice 1

Booleovská funkce je funkce, jejíž proměnné nabývají jedné ze dvou hodnot: $1$ nebo $0$.

Libovolnou logickou funkci lze zadat pomocí pravdivostní tabulky: sada všech možných argumentů je zapsána na levé straně tabulky a odpovídající hodnoty logické funkce jsou na pravé straně.

Definice 2

pravdivostní tabulka- tabulka, která ukazuje, jaké hodnoty bude mít složený výraz pro všechny možné sady hodnot jednoduchých výrazů, které jsou v něm obsaženy.

Definice 3

Ekvivalent se nazývají logické výrazy, jejichž poslední sloupce pravdivostních tabulek se shodují. Ekvivalence je označena znakem $"="$.

Při sestavování pravdivostní tabulky je důležité zvážit následující pořadí provádění logických operací:

Obrázek 1.

Závorky mají přednost v pořadí provádění operací.

Algoritmus pro konstrukci pravdivostní tabulky logické funkce

Určete počet řádků: počet řádků= $2^n + 1 $ (pro titulní lištu), $n$ je počet jednoduchých výrazů. Například pro funkce dvou proměnných jsou $2^2 = 4$ kombinací množin hodnot proměnných, pro funkce tří proměnných jsou $2^3 = 8$ a tak dále.

Určete počet sloupců: počet sloupců = počet proměnných + počet logických operací. Při určování počtu logických operací se bere v úvahu i pořadí jejich provádění.

Vyplňte sloupce výsledky provádění logických operací v určité posloupnosti s přihlédnutím k pravdivostním tabulkám základních logických operací.

Obrázek 2

Příklad 1

Vytvořte pravdivostní tabulku logického výrazu $D=\bar(A) \vee (B \vee C)$.

Řešení:

Určíme počet řádků:

počet řádků = $ 2^3 + 1 = 9 $.

Počet proměnných je $3$.

1. invertovat ($\bar(A)$);
2. disjunkce, protože je v hranatých závorkách ($B \vee C$);

3. disjunkce ($\overline(A)\vee \left(B\vee C\right)$) je požadovaný logický výraz.

   Počet sloupců = $3 + 3=6$.

Vyplňme tabulku s přihlédnutím k pravdivostním tabulkám logických operací.

Obrázek 3

Příklad 2

Na základě daného logického výrazu sestrojte pravdivostní tabulku:

Řešení:

Určíme počet řádků:

Počet jednoduchých výrazů je $n=3$, takže

počet řádků = $2^3 + 1=9$.

Definujme počet sloupců:

Počet proměnných je $3$.

Počet logických operací a jejich posloupnost:

1. negace ($\bar(C)$);
2. disjunkce, protože je v hranatých závorkách ($A \vee B$);
3. spojení ($(A\vee B)\bigwedge \overline(C)$);
4. negace, kterou označíme $F_1$ ($\overline((A\vee B)\bigwedge \overline(C))$);
5. disjunkce ($A \vee C$);
6. spojení ($(A\vee C)\bigwedge B$);
7. negace, kterou označíme $F_2$ ($\overline((A\vee C)\bigwedge B)$);

8. disjunkce je požadovaná logická funkce ($\overline((A\vee B)\bigwedge \overline(C))\vee \overline((A\vee C)\bigwedge B)$).

Učíme se vytvářet logické výrazy z výroků, definujeme pojem „pravdivostní tabulka“, studujeme posloupnost akcí pro konstrukci pravdivostních tabulek, učíme se nacházet hodnotu logických výrazů sestavováním pravdivostních tabulek.

Cíle lekce:

1. Návody:
   1. Naučte se vytvářet logické výrazy z výroků
   2. Představte pojem „tabulka pravdy“
   3. Studovat posloupnost akcí pro konstrukci pravdivostních tabulek
   4. Naučte se najít hodnotu logických výrazů vytvářením pravdivostních tabulek
   5. Zavést pojem ekvivalence logických výrazů
   6. Naučte se dokazovat ekvivalenci logických výrazů pomocí pravdivostních tabulek
   7. Upevnit dovednosti hledání hodnot logických výrazů vytvářením pravdivostních tabulek
2. Rozvíjející se:
   1. Rozvíjejte logické myšlení
   2. Rozvíjejte pozornost
   3. Rozvíjejte paměť
   4. Rozvíjet řeč žáků
3. Vzdělávací:
   1. Pěstovat schopnost naslouchat učitelům a spolužákům
   2. Kultivujte přesnost vedení zápisníku
   3. Pěstujte disciplínu

Během vyučování

Organizace času

Ahoj hoši. Pokračujeme ve studiu základů logiky a tématu naší dnešní lekce „Skládání logických výrazů. Pravdivé tabulky. Po prostudování tohoto tématu se naučíte, jak se výroky skládají z logických forem, a určíte jejich pravdivost sestavením pravdivostních tabulek.

Kontrola domácích úkolů

Napište řešení domácích úkolů na tabuli
Všichni ostatní, otevřete sešity, já to projdu a zkontroluji, jak jste si udělali domácí úkol
Zopakujme si logické operace ještě jednou
V jakém případě v důsledku operace logického násobení bude složený výrok pravdivý?
Složený příkaz vytvořený jako výsledek operace logického násobení je pravdivý tehdy a pouze tehdy, když jsou pravdivé všechny jednoduché příkazy v něm obsažené.
V jakém případě bude v důsledku operace logického sčítání složený příkaz nepravdivý?
Složený příkaz vytvořený jako výsledek operace logického sčítání je nepravdivý, když všechny jednoduché příkazy v něm obsažené jsou nepravdivé.
Jak inverze ovlivňuje výpověď?
Inverze činí pravdivý výrok nepravdivým a naopak nepravdivým pravdivým.
Co můžete říci o implikaci?
Logický důsledek (implikace) je tvořen spojením dvou výroků do jednoho pomocí figury „když ... pak ...“.
Označeno A-> V
Složený výrok vytvořený pomocí operace logického důsledku (implikace) je nepravdivý právě tehdy, když z pravdivého předpokladu (první výrok) vyplývá nepravdivý závěr (druhý výrok).
Co můžete říci o operaci logické ekvivalence?
Logická rovnost (ekvivalence) vzniká spojením dvou výroků do jednoho pomocí figury „... tehdy a jen tehdy, když…“, „… tehdy a jen tehdy…“
Složený výrok vytvořený pomocí operace logické ekvivalence je pravdivý právě tehdy, když jsou oba výroky současně buď nepravdivé nebo pravdivé.

Vysvětlení nového materiálu

No, zopakovali jsme si probranou látku, přecházíme na nové téma.

V minulé lekci jsme našli hodnotu složeného příkazu nahrazením počátečních hodnot vstupních booleovských proměnných. A dnes se dozvíme, že je možné sestavit pravdivostní tabulku, která určuje pravdivost nebo nepravdivost logického výrazu pro všechny možné kombinace počátečních hodnot jednoduchých příkazů (logických proměnných) a že je možné určit hodnoty počátečních logických proměnných, vědět, jaký výsledek potřebujeme.

Zvažte znovu náš příklad z minulé lekce.

a sestavte pravdivostní tabulku pro tento složený výrok

Při konstrukci pravdivostních tabulek existuje určitá posloupnost akcí. Pojďme si zapsat

1. Je nutné určit počet řádků v pravdivostní tabulce.

• počet řádků = 2 n , kde n je počet booleovských proměnných

Zaznamenáno. Sestavení pravdivostní tabulky
co uděláme jako první?
Určete počet sloupců v tabulce
jak to uděláme?
Počítáme počet proměnných. V našem případě logická funkce obsahuje 2 proměnné
Který?
A a B
Kolik řádků tedy bude v tabulce?
Počet řádků v pravdivostní tabulce musí být 4.
Co když jsou 3 proměnné?
Počet řádků = 2³ = 8
Že jo. co budeme dělat dál?
Definujeme počet sloupců = počet booleovských proměnných plus počet booleovských operací.
Kolik to bude v našem případě?
V našem případě je počet proměnných dvě a počet logických operací pět, tedy počet sloupců v pravdivostní tabulce je sedm.
Pokuta. Dále?
Sestavíme tabulku se zadaným počtem řádků a sloupců, označíme sloupce a zadáme do tabulky možné sady hodnot počátečních logických proměnných a vyplníme pravdivostní tabulku po sloupcích.
Kterou operaci provedeme jako první? Dejte si pozor na závorky a přednost
Můžete nejprve provést logickou negaci nebo nejprve najít hodnotu v první závorce, poté inverzní a hodnotu v druhé závorce a poté hodnotu mezi těmito závorkami

Nyní můžeme určit hodnotu logické funkce pro jakoukoli sadu hodnot logických proměnných
Nyní zapíšeme položku „Ekvivalentní logické výrazy“.
Logické výrazy, jejichž poslední sloupce pravdivostních tabulek jsou stejné, se nazývají ekvivalent. K označení ekvivalentních logických výrazů se používá znak „=“,
Dokažme, že logické výrazy ┐ A& ┐B a AvB jsou ekvivalentní. Nejprve sestavíme pravdivostní tabulku logického výrazu

Kolik sloupců bude mít tabulka? 5
Kterou operaci provedeme jako první? Inverze A, inverze B

Nyní sestavme pravdivostní tabulku logického výrazu AvB
Kolik řádků bude v tabulce? 4
Kolik sloupců bude mít tabulka? 4

Všichni chápeme, že pokud potřebujete najít negaci pro celý výraz, pak přednost má v našem případě disjunkce. Proto nejprve provedeme disjunkci a poté inverzi. Navíc můžeme přepsat náš logický výraz AvB. Protože potřebujeme najít negaci celého výrazu a ne jednotlivých proměnných, pak lze inverzi vyjmout ze závorek ┐(AvB) a víme, že nejprve najdeme hodnotu v závorkách

Postavené stoly. Nyní porovnejme hodnoty v posledních sloupcích pravdivostních tabulek, protože výsledkem jsou poslední sloupce. Shodují se, proto jsou logické výrazy ekvivalentní a můžeme mezi ně vložit znak „=“.

Řešení problému

1.

Kolik proměnných obsahuje tento vzorec? 3
Kolik řádků a sloupců bude mít tabulka? 8 a 8
Jaká bude posloupnost operací v našem příkladu? (inverze, operace v závorkách, operace v závorkách)

2. Dokažte pomocí pravdivostních tabulek ekvivalenci následujících logických výrazů:

(A → B) A (Av┐B)

Co z toho vyvodíme? Tyto logické výrazy nejsou ekvivalentní

Domácí práce

Dokažte pomocí pravdivostních tabulek, že logické výrazy

┐A v ┐B a A&B jsou ekvivalentní

Vysvětlení nového materiálu (pokračování)

Pojem „tabulka pravdy“ používáme již několik lekcí za sebou a co je pravdivostní tabulka, Jak si myslíte, že?
Pravdivostní tabulka je tabulka, která stanoví shodu mezi možnými sadami hodnot logických proměnných a hodnotami funkcí.
Jak jste si udělal domácí úkol, jaký byl váš závěr?
Výrazy jsou ekvivalentní
Pamatujte, že v předchozí lekci jsme vytvořili vzorec ze složeného příkazu a nahradili jsme jednoduché příkazy 2 * 2 \u003d 4 a 2 * 2 \u003d 5 proměnnými A a B
Nyní se naučíme, jak z příkazů vytvářet logické výrazy

Zapište si úkol

Napište ve formě logického vzorce výroku:

1) Pokud je Ivanov zdravý a bohatý, pak je zdravý

Pojďme analyzovat prohlášení. Hledání jednoduchých vět

A - Ivanov je zdravý
B - Ivanov je bohatý

Dobře, jak by tedy vzorec vypadal? Jen nezapomeňte, aby se význam výroku neztratil, umístěte do vzorce závorky

2) Číslo je prvočíslo, pokud je dělitelné pouze 1 a sebou samým

Číslo je dělitelné pouze 1
B - číslo je dělitelné pouze samo sebou
C - číslo je prvočíslo

3) Je-li číslo dělitelné 4, je dělitelné 2

A je dělitelné 4
B je dělitelné 2

4) Libovolné číslo je buď dělitelné 2, nebo dělitelné 3

A je dělitelné 2
B je dělitelné 3

5) Sportovec je diskvalifikován, pokud se chová nesprávně k soupeři nebo rozhodčímu a pokud si vzal „doping“.

A - sportovec je diskvalifikován
B - chová se nekorektně ve vztahu k soupeři
C - chová se nekorektně k rozhodčímu
D - bral "doping".

Řešení problému

1. Sestavte pravdivostní tabulku pro vzorec

((p&q)→ (p→r)) v p

Vysvětlete, kolik řádků a sloupců bude v tabulce? (8 a 7) Jaká bude posloupnost operací a proč?

Podívali jsme se na poslední sloupec a došli jsme k závěru, že pro jakoukoli sadu vstupních parametrů nabývá vzorec skutečnou hodnotu, takový vzorec se nazývá tautologie. Napišme definici:

Vzorec se nazývá zákon logiky nebo tautologie, pokud má stejnou hodnotu „pravda“ pro jakoukoli sadu hodnot proměnných obsažených v tomto vzorci.
A pokud jsou všechny hodnoty nepravdivé, co si myslíte, že lze o takovém vzorci říci?
Můžeme říci, že vzorec je nemožný

2. Zapište formou logického vzorce výroku:

Úřad námořního přístavu vydal následující příkaz:

1. Pokud kapitán lodi dostane zvláštní pokyn, pak musí opustit přístav na své lodi
2. Pokud kapitán neobdrží zvláštní pokyn, nesmí opustit přístav, jinak mu bude odepřen vstup do tohoto přístavu.
3. Kapitánovi je buď odepřen přístup k tomuto portu, nebo neobdrží speciální pokyny

Identifikujeme jednoduchá tvrzení, skládáme vzorce

• A - kapitán obdrží speciální pokyn
• B - opouští přístav
• C - ztratí přístup k portu

1. ┐А→(┐В v С)
2. C v ┐A

3. Zapište složený výrok „(2*2=4 a 3*3 = 9) nebo (2*2≠4 a 3*3≠9)“ ve formě logického výrazu. Sestavte tabulku pravdy.

A=(2*2=4) B=(3*3=9)

(A&B) v (┐A&┐B)

Domácí práce

Vyberte složený výrok, který má stejnou pravdivostní tabulku jako ne (ne A a ne (B a C)).

1. A&B nebo C&A;
2. (A nebo B) a (A nebo C);
3. A a (B nebo C);
4. A nebo (ne B nebo C).