Pravdivé tabuľky logických operácií, ako ich vyriešiť. Identické prevody logických výrazov

Dnes budeme hovoriť o predmete s názvom počítačová veda. Tabuľka pravdy, typy funkcií, poradie ich vykonávania - to sú naše hlavné otázky, na ktoré sa pokúsime nájsť odpovede v článku.

Tento kurz sa zvyčajne vyučuje na strednej škole, ale veľký počet študentov je dôvodom nepochopenia niektorých funkcií. A ak sa tomu chystáte zasvätiť svoj život, potom sa bez absolvovania jednotnej štátnej skúšky z informatiky jednoducho nezaobídete. Tabuľka pravdy, transformácia zložitých výrazov, riešenie logických problémov - to všetko nájdete v lístku. Teraz sa na túto tému pozrieme bližšie a pomôžeme vám získať viac bodov za skúšku.

Predmet logiky

Čo je to za predmet - informatika? Tabuľka pravdy - ako ju zostaviť? Prečo je potrebná veda o logike? Teraz odpovieme na všetky tieto otázky.

Počítačová veda je veľmi fascinujúci predmet. V modernej spoločnosti to nemôže spôsobiť ťažkosti, pretože všetko, čo nás nejakým spôsobom obklopuje, sa týka počítača.

Základy vedy o logike učia stredoškolskí učitelia na hodinách informatiky. Tabuľky pravdy, funkcie, zjednodušenie výrazov - to všetko by mal vysvetliť učiteľ informatiky. Táto veda je v našom živote jednoducho potrebná. Pozrite sa bližšie, všetko dodržiava niektoré zákony. Hodili ste loptu, tá letela hore, ale potom padla späť na zem, bolo to kvôli prítomnosti fyzikálnych zákonov a gravitačnej sily. Mama robí polievku a pridáva soľ. Prečo nezískame zrná, keď ich jeme? Je to jednoduché, soľ sa rozpúšťa vo vode a dodržiava zákony chémie.

Teraz dávajte pozor na to, ako hovoríte.

• „Ak vezmem svoju mačku na veterinárnu kliniku, bude očkovaná.“
• „Dnes bol veľmi ťažký deň, pretože prišla kontrola.“
• "Nechcem ísť na univerzitu, pretože dnes bude kolokvium," a tak ďalej.

Všetko, čo hovoríte, sa musí riadiť zákonmi logiky. Platí to pre obchodnú aj priateľskú konverzáciu. Z tohto dôvodu je potrebné porozumieť logickým zákonom, aby sme nekonali náhodne, ale aby sme si boli istí výsledkom udalostí.

Funkcie

Aby ste mohli zostaviť tabuľku pravdy pre problém, ktorý vám bol navrhnutý, musíte poznať logické funkcie. Čo to je? Logická funkcia má niektoré premenné, ktoré sú príkazmi (pravdivé alebo nepravdivé), a hodnota samotnej funkcie by nám mala dať odpoveď na otázku: „Je výraz pravdivý alebo nepravdivý?“

Všetky výrazy majú nasledujúce hodnoty:

• Pravda alebo lož.
• A alebo L.
• 1 alebo 0.
• Plus alebo mínus.

Tu dajte prednosť metóde, ktorá je pre vás pohodlnejšia. Aby sme mohli zostaviť tabuľku pravdy, musíme uviesť zoznam všetkých kombinácií premenných. Ich počet sa vypočíta podľa vzorca: 2 na mocninu n. Výsledkom výpočtu je počet možných kombinácií, premenná n v tomto vzorci označuje počet premenných v podmienke. Ak má výraz veľa premenných, môžete použiť kalkulačku alebo si vytvoriť malú tabuľku zvýšením dvoch na mocninu.

V logike spájajúcej výrazy sa rozlišuje sedem funkcií alebo spojení:

• Násobenie (spojka).
• Sčítanie (disjunkcia).
• Dôsledok (implikácia).
• Ekvivalencia.
• Inverzia.
• Schaefferova mŕtvica.
• Piercov šíp.

Prvá operácia v zozname sa nazýva „logické násobenie“. Môže byť označený graficky obráteným začiarknutím, & alebo *. Druhá operácia v našom zozname je logické sčítanie, graficky označené ako začiarkavacie políčko, +. Implikácia sa nazýva logický dôsledok, označuje sa ako šípka smerujúca od podmienky k následku. Rovnocennosť je označená dvojitou šípkou, funkcia má skutočnú hodnotu iba vtedy, ak obe hodnoty majú hodnotu „1“ alebo „0“. Inverzia sa nazýva logická negácia. Schaefferov zdvih sa nazýva funkcia, ktorá neguje spojenie, a Peirceov šíp sa nazýva funkcia, ktorá neguje disjunkciu.

Základné binárne funkcie

Tabuľka logickej pravdy pomáha nájsť odpoveď na problém, ale na to si musíte pamätať tabuľky binárnych funkcií. Budú uvedené v tejto sekcii.

Spojenie (násobenie). Ak sú dvaja, potom v dôsledku toho dostaneme pravdu, vo všetkých ostatných prípadoch dostaneme lož.

Výsledok je falošný s logickým sčítaním, máme iba v prípade dvoch falošných vstupov.

Logický dôsledok má falošný výsledok, iba ak je podmienka pravdivá a účinok je nepravdivý. Tu môžete uviesť príklad zo života: „Chcel som kúpiť cukor, ale obchod bol zatvorený,“ preto sa cukor nikdy nekúpil.

Ekvivalencia platí iba v prípadoch, keď sú hodnoty vstupných údajov rovnaké. To znamená, že s pármi: „0; 0“ alebo „1; 1“.

V prípade inverzie je všetko elementárne, ak je na vstupe pravdivý výraz, potom sa prevedie na nepravdu a naopak. Obrázok ukazuje, ako je to graficky znázornené.

Schifferov zdvih poskytne falošný výsledok iba vtedy, ak existujú dva pravdivé výrazy.

V prípade Piercovho šípu bude funkcia pravdivá, iba ak ako vstup použijeme iba falošné výrazy.

V akom poradí vykonávať logické operácie

Upozorňujeme, že vytváranie pravdivých tabuliek a zjednodušovanie výrazov je možné iba vtedy, ak je poradie operácií správne. Pamätajte si, v akom poradí je potrebné ich vykonať, je to veľmi dôležité pre získanie správneho výsledku.

• logická negácia;
• násobenie;
• dodatok;
• dôsledok;
• rovnocennosť;
• negácia násobenia (Schaefferova mŕtvica);
• negácia sčítania (Pierceova šípka).

Príklad č. 1

Teraz navrhujeme zvážiť príklad konštrukcie tabuľky pravdy pre 4 premenné. Je potrebné zistiť, v ktorých prípadoch F = 0 pre rovnicu: nieA + B + C * D

Odpoveď na túto úlohu bude vyčísliť nasledujúce kombinácie: „1; 0; 0; 0", "1; 0; 0; 1" a "1; 0; 1; 0". Ako vidíte, zostavenie tabuľky pravdy je veľmi jednoduché. Ešte raz by som vás chcel upozorniť na poradie vykonávania akcií. V konkrétnom prípade to bolo nasledovne:

1. Inverzia prvého jednoduchého výrazu.
2. Spojenie tretieho a štvrtého výrazu.
3. Disjunkcia druhého výrazu s výsledkami predchádzajúcich výpočtov.

Príklad č. 2

Teraz zvážime ďalšiu úlohu, ktorá si vyžaduje zostavenie tabuľky pravdy. Počítačová veda (príklady boli prevzaté zo školského kurzu) môže mať aj za úlohu. Poďme sa rýchlo pozrieť na jedného z nich. Je Vanya vinný z krádeže lopty, ak je známy nasledujúci prípad:

• Ak Vanya nekradol alebo Petya ukradol, potom sa Seryozha zúčastnil krádeže.
• Ak nie je vinný Vanya, potom Seryozha neukradol ani loptu.

Predstavme označenia: I - Vanya ukradol loptu; P - Petya ukradol; S - Seryozha kradol.

Podľa tejto podmienky môžeme zostaviť rovnicu: F = ((nie И + П) implikácia С) * (nie a implikácia notС). Potrebujeme tie možnosti, kde funkcia nadobúda skutočnú hodnotu. Ďalej musíte vytvoriť tabuľku, pretože táto funkcia má až 7 akcií, vynecháme ich. Zadáme iba vstupné údaje a výsledok.

Všimnite si toho, že v tomto probléme sme namiesto znamienok „0“ a „1“ použili plus a mínus. To je tiež prijateľné. Máme záujem o kombinácie, kde F = +. Po ich analýze môžeme vyvodiť nasledujúci záver: Vanya sa zúčastnila krádeže lopty, pretože vo všetkých prípadoch, kde F má hodnotu +, A má kladnú hodnotu.

Príklad č. 3

Teraz navrhujeme nájsť počet kombinácií, keď F = 1. Rovnica má nasledujúci tvar: F = notA + B * A + notB. Zostavujeme tabuľku pravdy:

Odpoveď: 4 kombinácie.

Základné logické operácie

Negácia (inverzia) z latinského inverzie - obrátiť:

Zodpovedá častici NIE, fráza JE NESPRÁVNE ČO;

Označenie: nie A, A, -A;

tabuľka pravdy:

Inverzia boolovskej premennej je pravdivá, ak je samotná premenná nepravdivá, a naopak, inverzná hodnota je nepravdivá, ak je premenná pravdivá.

Príklad: A = (Vonku sneží).

A = (Nie je pravda, že vonku sneží)

A = (Vonku nesneží);

Logické sčítanie (disjunkcia) z latinského disjunctio - rozlišujem:

Zhoda zhody ALEBO;

Označenie: +, alebo, alebo, V;

Pravdivá tabuľka:

Disjunkcia je nepravdivá vtedy a len vtedy, ak sú obe tvrdenia nepravdivé.

Príklad: F = (Vonku svieti slnko alebo fúka silný vietor);

Logické násobenie (spojka), z latinského conjunctio - spájam:

Zhoda zväzkov AND

(v prirodzenom jazyku: A aj B, A aj B, A spolu s B, A, napriek B, A, pričom B);

Označenie: Ч ,, &, a, ^, a;

Pravdivá tabuľka:

Spojka je pravdivá vtedy a len vtedy, ak sú pravdivé obe tvrdenia.

Príklad: F = (Vonku svieti slnko a fúka silný vietor);

Akékoľvek zložité tvrdenie je možné napísať pomocou základných logických operácií AND, OR, NOT Pomocou logických obvodov AND, OR NIE JE možné implementovať logickú funkciu, ktorá popisuje činnosť rôznych počítačových zariadení.

2) Pravdivá tabuľka je tabuľka popisujúca logickú funkciu.

V tomto prípade „logická funkcia“ znamená funkciu, v ktorej hodnoty premenných (parametre funkcie) a hodnota samotnej funkcie vyjadrujú logickú pravdu. Napríklad v logike s dvoma hodnotami môžu nadobúdať hodnoty „true“ alebo „false“ (buď, alebo).

Tabuľková definícia funkcií sa nachádza nielen v logike, ale tabuľky sa ukázali byť obzvlášť vhodné pre logické funkcie a od začiatku 20. storočia im bol priradený tento špeciálny názov. Tabuľky pravdy sa obzvlášť často používajú v booleovskej algebre a v podobných viachodnotových logických systémoch.

Spojka je logická operácia, ktorá sa vo svojej aplikácii čo najviac približuje spojke „a“. Logické násobenie, niekedy len „A“.

Disjunkcia je logická operácia, ktorá sa vo svojej aplikácii čo najviac blíži spojke „alebo“ v zmysle „buď toto, alebo toto, alebo oboje naraz“. logické sčítanie, niekedy len „ALEBO“.

Implikácia je binárne logické spojivo, pri aplikácii blízke spojkám „ak ... potom ...“. Implikácia je napísaná ako predpoklad následku; Používajú sa aj šípky iného tvaru a nasmerované iným smerom (bod vždy naznačuje účinok).

Ekvivalencia (alebo ekvivalencia) je dvojmiestna logická operácia. Obvykle je označený symbolom ≡ alebo ↔.

7. Logické výrazy, pravdivostné tabuľky logických výrazov.

Logickým výrazom je záznam alebo slovné tvrdenie, ktoré spolu s konštantami nevyhnutne zahŕňa premenné veličiny (objekty). V závislosti od hodnôt týchto premenných môže logický výraz nadobúdať jednu z dvoch možných hodnôt: TRUE (logická 1) alebo FALSE (logická 0)

Zložitý logický výraz je logický výraz zložený z jedného alebo viacerých jednoduchých (alebo zložitých) logických výrazov spojených s logickými operáciami.

Logické operácie a pravdivostné tabuľky

Logické násobenie KONJUNKCIA - tento nový komplexný výraz bude pravdivý iba vtedy, ak sú pravdivé oba pôvodné jednoduché výrazy. Konjunkcia definuje spojenie dvoch logických výrazov pomocou spojenia I.

Logické sčítanie - DISJUNCTION - tento nový komplexný výraz bude pravdivý vtedy a len vtedy, ak je pravdivý aspoň jeden z pôvodných (jednoduchých) výrazov. Disjunkcia definuje spojenie dvoch logických výrazov pomocou spojky OR

Logická negácia: INVERZIA - ak je pôvodný výraz pravdivý, potom bude výsledok negácie nepravdivý a naopak, ak je pôvodný výraz nepravdivý, bude výsledok negácie pravdivý / Táto operácia znamená, že častica NIE alebo k pôvodnému logickému výrazu sa pridáva slovo ZLE, ČO

Logický záver: IMPLIKÁCIA - spája dva jednoduché logické výrazy, z ktorých prvý je podmienkou (A) a druhý (B) je dôsledkom tejto podmienky. Výsledok IMPLIKÁCIE je NEPRAVDIVÝ, iba ak je podmienka A pravdivá a dôsledok B je nepravdivý. Označuje sa symbolom „preto“ a vyjadruje sa slovami IF ..., THEN ...

Logická ekvivalencia: EQUIVALENCE - určuje výsledok porovnania dvoch jednoduchých logických výrazov A a B. Výsledkom EQUIVALENCE je nový logický výraz, ktorý bude pravdivý vtedy a len vtedy, ak sú oba pôvodné výrazy súčasne pravdivé alebo nepravdivé. Označené symbolom „ekvivalencia“

Poradie vykonávania logických operácií v komplexnom logickom výraze:

1. inverzia

2. konjunkcia

3. rozpojenie

4.implikácia

5. ekvivalencia

Zátvorky sa používajú na zmenu zadaného poradia operácií.

Zostavovanie pravdivostných tabuliek pre zložité výrazy:

Počet riadkov = 2n + dva riadky pre názov (n je počet jednoduchých príkazov)

Počet stĺpcov = počet premenných + počet logických operácií

Pri konštrukcii tabuľky je potrebné vziať do úvahy všetky možné kombinácie logických hodnôt 0 a 1 pôvodných výrazov. Potom - určte poradie akcií a zostavte tabuľku, pričom vezmite do úvahy tabuľky pravdivosti hlavných logických operácií.

PRÍKLAD: zostavte pravdivostnú tabuľku komplexného logického výrazu D = notA & (B + C)

A, B, C - tri jednoduché tvrdenia, preto:

počet riadkov = 23 +2 = 10 (n = 3, pretože na vstupe sú tri prvky A, B, C)

počet stĺpcov: 1) A

4) nie A je inverzná hodnota k A (označená E)

5) B + C je disjunkčná operácia (označte F)

6) D = notA & (B + C), t.j. D = E & F je operácia spojenia

A B C E = nie A (nie 1) F = B + C (2 + 3) D = E&F (4 * 5)

Algebra logiky

Algebra logiky

Algebra logiky(angl. logická algebra) - jedna z hlavných sekcií matematickej logiky, v ktorej sa pri logických transformáciách používajú metódy algebry.

Zakladateľom algebry logiky je anglický matematik a logik J. Boole (1815-1864), ktorý svoje logické učenie založil na analógii medzi algebrou a logikou. Akékoľvek tvrdenie zapísal pomocou symbolov jazyka, ktorý vyvinul, a dostal „rovnice“, ktorých pravdivosť alebo nepravdivosť bolo možné dokázať na základe určitých logických zákonov, ako sú zákony komutativity, distribučnosti, asociativity atď.

Moderné logická algebra je odvetvím matematickej logiky a študuje logické operácie s tvrdeniami z pohľadu ich pravdivostnej hodnoty (pravda, nepravda). Vyhlásenia môžu byť pravdivé, nepravdivé alebo môžu obsahovať pravdivé a nepravdivé údaje v rôznych pomeroch.

Logické vyhlásenie Je nejaká deklaratívna veta, pri ktorej je možné jednoznačne tvrdiť, že jej obsah je pravdivý alebo nepravdivý.

Napríklad „3 krát 3 sa rovná 9“, „Archangelsk severne od Vologdy“ sú pravdivé tvrdenia a „päť je menej ako tri“, „Mars je hviezda“ sú nepravdivé.

Je zrejmé, že nie každá veta môže byť logickým tvrdením, pretože nie vždy má zmysel hovoriť o jej nepravde alebo pravde. Napríklad tvrdenie „Počítačová veda je zaujímavý predmet“ je vágne a vyžaduje si ďalšie informácie a tvrdenie „Pre 10-ročného študenta AA Ivanov je informatika zaujímavým predmetom“ v závislosti od záujmov AA Ivanov môže trvať o význame „pravdy“ alebo „klamstva“.

okrem dvojhodnotová výroková algebra, v ktorom sú akceptované iba dve hodnoty - „pravda“ a „nepravda“, existuje propozičná algebra s viacerými hodnotami. V takejto algebre sa okrem významov „pravda“ a „nepravda“ používajú také pravdivostné hodnoty ako „pravdepodobne“, „možné“, „nemožné“ atď.

V algebre sa logika líši jednoduché(elementárne) výroky, označené latinskými písmenami (A, B, C, D, ...), a komplexné(kompozitný), zložený z niekoľkých jednoduchých pomocou logických spojok, napríklad ako napr „Nie“, „a“, „alebo“, „vtedy a iba vtedy“, „ak ... potom“... Pravdivosť alebo nepravdivosť takto získaných zložitých tvrdení je určená významom jednoduchých tvrdení.

Označme ako A tvrdenie „Algebra logiky sa úspešne používa v teórii elektrických obvodov“ a prostredníctvom V.- "Algebra logiky sa používa pri syntéze obvodov reléových kontaktov."

Potom zložené tvrdenie „Algebra logiky sa úspešne používa v teórii elektrických obvodov a pri syntéze obvodov reléových kontaktov“ možno stručne napísať ako A a B.; tu „a“ je logickým spojivom. Očividne od elementárnych vyhlásení A a B. sú pravdivé, potom zložené tvrdenie A a B..

Každý logický spojovací prvok je považovaný za operáciu logických príkazov a má svoj vlastný názov a označenie.

Existujú iba dve logické hodnoty: pravda) a false (FALSE)... To zodpovedá digitálnej reprezentácii - 1 a 0 ... Výsledky každej logickej operácie je možné zaznamenať vo forme tabuľky. Takéto tabuľky sa nazývajú pravdivostné.

Základné operácie booleovskej algebry

1. Logická negácia, inverzia(lat. inverzia- inverzia) - logická operácia, v dôsledku ktorej sa z daného príkazu získa nový príkaz (napríklad A) ( nie A.), ktorá sa volá negácia pôvodného tvrdenia, symbolicky označený stĺpcom vyššie ($ A↖ (-) $) alebo takýmito konvenciami ako ¬, „nie“, a znie: „Nie A“, „A je falošné“, „nie je pravda, že A“, „negácia A“... Napríklad „Mars je planéta slnečnej sústavy“ (hovorí A); „Mars nie je planétou slnečnej sústavy“ ($ A↖ (-) $); tvrdenie „10 je prvočíslo“ (výrok B) je nepravdivé; tvrdenie „10 nie je prvočíslo“ (tvrdenie B) je pravdivé.

Operácia použitá s ohľadom na jednu veličinu sa nazýva unárny... Tabuľka hodnôt tejto operácie má tvar

Tvrdenie $ A↖ (-) $ je nepravdivé, ak A je pravdivé, a pravdivé, ak A je nepravdivé.

Geometricky možno negáciu znázorniť nasledovne: ak A je nejaká množina bodov, potom $ A↖ (-) $ je doplnkom množiny A, to znamená, že všetky body, ktoré nepatria do množiny A.

2.Spojenie(lat. spojivka- spojenie) - logické násobenie, operácia, ktorá vyžaduje aspoň dve logické hodnoty (operandy) a spája dva alebo viac príkazov pomocou odkazu "a"(napríklad, "A a B"), ktorý je symbolicky označený znakom ∧ (A ∧ B) a znie: „A a B“. Nasledujúce znaky sa používajú aj na označenie spojky: A ∙ B; A & B, A a B., a niekedy nie je medzi vyhláseniami vložené žiadne znamienko: AB. Príklad logického násobenia: „Tento trojuholník je rovnoramenný a pravouhlý.“ Dané tvrdenie môže byť pravdivé iba vtedy, ak sú splnené obe podmienky, inak je tvrdenie nepravdivé.

A	B	A ∧ B
1	0	0
0	1	0
0	0	0
1	1	1

Výpoveď A ∧ V. je pravda, iba ak obidva tvrdenia - A a V. sú pravdivé

Geometricky môže byť spojka reprezentovaná nasledovne: ak A, B. A ∧ V. existuje priesečník množín A a V..

3. Rozpojenie(lat. disjunkcia- oddelenie) - logické sčítanie, operácia, ktorá spája dva alebo viac príkazov pomocou zväzku "alebo"(napríklad, "A alebo B"), ktorý je symbolicky označený znakom ∨ (A.∨ V) a znie: "A alebo B"... Nasledujúce znaky sa používajú aj na označenie disjunkcie: A + B; A alebo B; A | B... Príklad logického sčítania: „Číslo x je deliteľné 3 alebo 5“. Toto tvrdenie bude pravdivé, ak sú splnené obe podmienky alebo aspoň jedna z nich.

Pravdivá tabuľka operácie má formu

A	B	A ∨ B
1	0	1
0	1	1
0	0	0
1	1	1

Výpoveď A∨ V. nepravdivé, iba ak obe tvrdenia - A a V. sú falošné.

Geometricky logické sčítanie môže byť reprezentované nasledovne: ak A, B. Existuje teda niekoľko súborov bodov A ∨ V. Je spojenie množín A a V., to znamená postava spájajúca štvorec aj kruh.

4. Prísne oddeľujúca disjunkcia, modul navyše dva- logická operácia, ktorá spája dva príkazy pomocou odkazu "alebo", používaný vo výhradnom zmysle, ktorý je symbolicky označený znakmi ∨ ∨ alebo ⊕ ( A ∨ ∨ B, A. ⊕ V.) a znie: „Buď A alebo B“... Príkladom sčítania modulo dva je príslovie „Tento trojuholník je tupý alebo s ostrým uhlom“. Vyhlásenie je pravdivé, ak je splnená ktorákoľvek z podmienok.

Pravdivá tabuľka operácie má formu

A	V.	A⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

Výrok A ⊕ B je pravdivý iba vtedy, ak majú výroky A a B odlišný význam.

5. Dôsledok(lat. implisito- úzko súvisí) - logická operácia, ktorá spája dva príkazy pomocou zväzku "Ak potom" do komplexného výroku, ktorý je symbolicky označený znamienkom → ( A → V.) a znie: „Ak A, potom B“, „A znamená B“, „B vyplýva z A“, „A znamená B“... Znak ⊃ (A ⊃ B) sa používa aj na označenie implikácie. Príklad implikácie: „Ak je výsledný štvoruholník štvorec, dá sa okolo neho popísať kruh.“ Táto operácia spája dva jednoduché logické výrazy, pričom prvý je podmienkou a druhý dôsledkom. Výsledok operácie je falošný, iba ak je premisa pravdivá a efekt je nepravdivý. Napríklad „Ak 3 * 3 = 9 (A), potom je Slnko planéta (B)“, výsledok implikácie A → B je falošný.

Pravdivá tabuľka operácie má formu

A	V.	A→V.
1	0	0
0	1	1
0	0	1
1	1	1

Pokiaľ ide o implikáciu, je pravda, že z lži môže vyplývať čokoľvek a iba pravda môže vyplývať z pravdy.

6. Ekvivalencia, dvojitá implikácia, ekvivalencia(lat. aequalis- rovný a valentis- platné) - logická operácia, ktorá umožňuje dva príkazy A a V. získať nové vyhlásenie A ≡ B ktorý znie: „A je ekvivalentom B“... Nasledujúce symboly sa používajú aj na označenie ekvivalencie: ⇔, ∼. Táto operácia môže byť vyjadrená väzmi „Vtedy a iba vtedy“, „potrebné a dostatočné“, „ekvivalentné“... Príkladom ekvivalencie je tvrdenie: „Trojuholník bude obdĺžnikový vtedy a len vtedy, ak má jeden z uhlov 90 stupňov.“

Pravdivostná tabuľka operácie ekvivalencie má tvar

A	V.	A∼ V.
1	0	0
0	1	0
0	0	1
1	1	1

Operácia ekvivalencie je opakom sčítania modulo dva a má výsledok „pravdivý“ vtedy, ak sa hodnoty premenných zhodujú.

Keď poznáme významy jednoduchých tvrdení, je možné určiť významy komplexných tvrdení na základe pravdivostných tabuliek. Je dôležité vedieť, že tri operácie sú dostatočné na to, aby predstavovali akúkoľvek funkciu algebry logiky: spojku, disjunkciu a negáciu.

Priorita vykonávania logických operácií je nasledovná: negácia ( "nie") má najvyššiu prioritu, potom spojka ( "a"), po spojke - disjunkcii ( "alebo").

S pomocou logických premenných a logických operácií môže byť akékoľvek logické tvrdenie formalizované, to znamená nahradené logickým vzorcom. Elementárne tvrdenia, ktoré tvoria zložené tvrdenie, môžu zároveň významovo úplne nesúvisieť, ale to nezasahuje do určovania pravdivosti alebo nepravdivosti zloženého tvrdenia. Napríklad tvrdenie „Ak je päť viac ako dva (( A), potom utorok vždy príde po pondelku ( V.) “- implikácia A→ V., a výsledok operácie je v tomto prípade „pravdivý“. Pri logických operáciách sa neberie do úvahy význam výrokov, zvažuje sa iba ich pravdivosť alebo nepravdivosť.

Uvažujme napríklad o konštrukcii zloženého príkazu z príkazov A a V.čo by bolo nepravdivé, ak a iba vtedy, ak sú obe tvrdenia pravdivé. V tabuľke pravdy pre činnosť sčítacieho modulu dva nájdeme: 1 ⊕ 1 = 0. A tvrdenie môže byť napríklad toto: „Táto guľa je úplne červená alebo úplne modrá.“ Preto ak vyhlásenie A„Táto guľa je úplne červená“ je pravda a vyhlásenie V.„Táto guľa je úplne modrá“ je pravda, potom je zložené tvrdenie lož, pretože loptička nemôže byť súčasne červená aj modrá.

Príklady riešenia problémov

Príklad 1. Určte pre uvedené hodnoty X hodnotu logického príkazu ((X> 3) ∨ (X< 3)) → (X < 4) :

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

Riešenie. Postupnosť operácií je nasledovná: najskôr sa vykonajú porovnávacie operácie v zátvorkách, potom disjunkcia a posledná je implikačná operácia. Operácia disjunkcie ∨ je nepravdivá vtedy a len vtedy, ak sú oba operandy nepravdivé. Pravdivá tabuľka implikácie je

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

Odtiaľto dostávame:

1) pre X = 1:

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

2) pre X = 12:

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

3) pre X = 3:

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

Príklad 2. Zadajte množinu celočíselných hodnôt X, pre ktoré platí výraz ¬ ((X> 2) → (X> 5)).

Riešenie. Operácia negácie sa použije na celý výraz ((X> 2) → (X> 5)), preto keď je výraz ¬ ((X> 2) → (X> 5)) pravdivý, výraz ((X > 2) → (X> 5)) je nepravdivé. Preto je potrebné určiť, pre ktoré hodnoty X je výraz ((X> 2) → (X> 5)) nepravdivý. Implicitná operácia nadobúda hodnotu „false“ iba v jednom prípade: keď z pravdy vyplýva nepravda. A to sa robí iba pre X = 3; X = 4; X = 5.

Príklad 3. Pre ktoré z uvedených slov je tvrdenie ¬ (prvé písmeno samohlásky ∧ tretie písmeno samohlásky) ⇔ reťazec 4 znakov nepravdivý? 1) assa; 2) kuku; 3) kukurica; 4) chyba; 5) silný muž.

Riešenie. Zoberme si všetky navrhované slová v poradí:

1) pre slovo zadok dostaneme: ¬ (1 ∧ 0) ⇔ 1, 1 ⇔ 1 - tvrdenie je pravdivé;

2) pre slovo kuku dostaneme: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - tvrdenie je pravdivé;

3) pre slovo kukurica dostaneme: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - tvrdenie je nepravdivé;

4) pre slovo chyba dostaneme: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - tvrdenie je pravdivé;

5) pre slovo strongman dostaneme: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - tvrdenie je nepravdivé.

Booleovské výrazy a ich transformácia

Pod logický výraz mali by ste porozumieť takému záznamu, ktorý môže mať logickú hodnotu „true“ alebo „false“. Pri tejto definícii je potrebné rozlišovať medzi logickými výrazmi:

• výrazy, ktoré používajú porovnávacie operácie („väčšie ako“, „menšie ako“, „rovnaké“, „nerovnaké“ atď.) a majú logické hodnoty (napríklad výraz a> b, kde a = 5 a b = 7, sa rovná hodnote „false“);
• priame logické výrazy spojené s logickými hodnotami a logickými operáciami (napríklad A ∨ B ∧ C, kde A = true, B = false a C = true).

Booleovské výrazy môžu zahŕňať funkcie, algebraické operácie, porovnávacie operácie a logické operácie. V tomto prípade je priorita vykonávania akcií nasledovná:

1. výpočet existujúcich funkčných závislostí;
2. vykonávanie algebraických operácií (prvé násobenie a delenie, potom odčítanie a sčítanie);
3. vykonávanie porovnávacích operácií (v žiadnom konkrétnom poradí);
4. vykonávanie logických operácií (na začiatku sa vykonávajú operácie negácie, potom sa vykonávajú operácie logického násobenia, logického sčítania, posledné operácie implikácie a ekvivalencie).

Booleovské výrazy môžu používať zátvorky, ktoré menia poradie vykonávania operácií.

Príklad. Nájdite hodnotu výrazu:

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

Riešenie. Poradie počítania hodnôt:

1) b a + a b> a + b, po substitúcii dostaneme: 3 2 + 2 3> 2 + 3, t.j. 17> 2 + 3 = pravda;

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

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

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

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

Po týchto výpočtoch konečne dostaneme: pravda ∨ А ∧ pravda ∧ ¬В ∧ ¬ pravda.

Teraz by sa mali vykonať negačné operácie, po ktorých by malo nasledovať logické násobenie a sčítanie:

5) ¬В = ¬ nepravda = pravda; ¬true = nepravda;

6) A ∧ true ∧ true ∧ false = true ∧ true ∧ true ∧ false = false;

7) pravda ∨ nepravda = pravda.

Výsledok daných hodnôt booleovského výrazu je teda „pravdivý“.

Poznámka. Vzhľadom na to, že pôvodný výraz je nakoniec súčtom dvoch výrazov a hodnota jedného z nich je 1 ≤ a = 1 ≤ 2 = pravda, bez ďalších výpočtov môžeme povedať, že výsledok pre celý výraz je tiež „pravda“.

Identické prevody logických výrazov

V algebre logiky sú splnené základné zákony, ktoré umožňujú vykonávať identické transformácie logických výrazov.

Zákon	Za ∨	Za ∧
Pohon	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Kombinované	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
Križovatka	A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
De Morganove pravidlá	$ (A ∨ B) ↖ (-) $ = $ A↖ (-) ∧ B↖ (-) $	$ (A ∧ B) ↖ (-) $ = $ A↖ (-) ∨ B↖ (-) $
Idempotencie	A ∨ A = A	A ∧ A = A
Absorpcia	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
Lepenie	(A ∧ B) ∨ (A↖ (-) ∧ B) = B	(A ∨ B) ∧ (A↖ (-) ∨ B) = B
Variabilná prevádzka s jej inverziou	$ A ∨ A↖ (-) $ = 1	$ A ∧ A↖ (-) $ = 0
Prevádzka s konštantami	A ∨ 0 = A A ∨ 1 = 1	A ∧ 1 = A A ∧ 0 = 0
Dvojitá negácia	$ A↖ (=) $ = A

Dôkazy o týchto tvrdeniach sa robia na základe zostavenia pravdivostných tabuliek pre zodpovedajúce záznamy.

Ekvivalentné transformácie logických vzorcov majú rovnaký účel ako transformácie vzorcov v bežnej algebre. Slúžia na zjednodušenie vzorcov alebo ich uvedenie do určitej podoby pomocou základných zákonov algebry logiky. Pod zjednodušenie vzorca, ktorý neobsahuje operácie implikácie a ekvivalencie, sa chápe ako ekvivalentná transformácia, ktorá vedie k vzorcu, ktorý obsahuje buď menej ako pôvodný počet operácií, alebo menej premenných.

Niektoré transformácie logických vzorcov sú podobné transformáciám vzorcov v bežnej algebre (pričom sa vezme spoločný faktor mimo zátvoriek, pomocou zákonov o posunutí a kombinácii atď.), Zatiaľ čo iné transformácie sú založené na vlastnostiach, ktoré operácie bežnej algebry nemajú (použitie distribučného zákona pre spojky, zákony absorpcie, lepenia, de Morgan, atď.).

Pozrime sa na príklady niektorých techník a metód používaných na zjednodušenie logických vzorcov:

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

Na transformáciu tu môžete použiť zákon idempotencie, distribučný zákon; inverzná variabilná operácia a konštantná operácia.

2) X1 × X1 × X2 = X1 × (1 × 1 × X2) = X1 × (1 × X2) = X1.

Tu sa pre jednoduchosť uplatňuje absorpčný zákon.

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

Pri prevode sa použije de Morganovo pravidlo, operácia premennej s jej inverziou, operácia s konštantou

Príklady riešenia problémov

Príklad 1. Nájdite booleovský výraz ekvivalentný A ∧ ¬ (¬B ∨ C).

Riešenie. Na B a C uplatňujeme de Morganovo pravidlo: ¬ (¬B ∨ C) = B ∧ ¬C.

Získame výraz ekvivalentný pôvodnému: A ∧ ¬ (¬B ∨ C) = A ∧ B ∧ ¬C.

Odpoveď: A ∧ B ∧ ¬C.

Príklad 2. Uveďte hodnotu logických premenných A, B, C, pre ktoré je hodnota logického výrazu (A ∨ B) → (B ∨ ¬C ∨ B) nepravdivá.

Riešenie. Pôsobenie implikácie je falošné iba v prípade, ak nepravda vyplýva zo skutočného predpokladu. Preto pre daný výraz musí premisa A ∨ B nadobudnúť hodnotu „pravda“ a dôsledok, to znamená, že výraz B ∨ ¬C ∨ B, musí byť „nepravda“.

1) A ∨ B - výsledok disjunkcie je „pravdivý“, ak je aspoň jeden z operandov „pravdivý“;

2) B ∨ ¬C ∨ B - výraz je nepravdivý, ak všetky výrazy majú hodnotu „false“, to znamená B - „nepravda“; ¬C - „nepravda“, a preto má premenná C hodnotu „true“;

3) ak vezmeme do úvahy premisu a vezmeme do úvahy, že B je „falošné“, potom dostaneme, že hodnota A je „pravdivá“.

Odpoveď: A je pravda, B je nepravda, C je pravda.

Príklad 3. Aké je najväčšie celé číslo X, pre ktoré je príkaz (35

Riešenie. Napíšte tabuľku pravdy pre implikačnú operáciu:

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

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

Odpoveď: X = 5.

Použitie boolovských výrazov na opis geometrických oblastí

Na opis geometrických oblastí je možné použiť booleovské výrazy. V tomto prípade je problém formulovaný nasledovne: pre danú geometrickú oblasť napíšte logický výraz, ktorý pre hodnoty x, y vezme hodnotu „true“, ak a len ak má nejaký bod súradnice (x; y) patrí do geometrickej oblasti.

Uvažujme popis geometrickej oblasti pomocou logického výrazu pomocou príkladov.

Príklad 1. Je zadaný obrázok geometrickej oblasti. Napíšte booleovský výraz opisujúci množinu bodov, ktoré k nemu patria.

1) .

Riešenie. Danú geometrickú oblasť možno reprezentovať ako množinu nasledujúcich oblastí: prvá oblasť - D1 - polorovina $ (x) / ( - 1) + (y) / (1) ≤ 1 $, druhá - D2 - kruh so stredom na začiatku $ x ^ 2 + y ^ 2 ≤ 1 $. Ich priesečník D1 $ ∩ $ D2 je požadovaná doména.

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

2)

Túto oblasť je možné napísať takto: | x | ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1.

Poznámka. Pri konštrukcii logického výrazu sa používajú slabé nerovnosti, čo znamená, že hranice tieňov patria aj do tieňovanej oblasti. Ak sa použijú prísne nerovnosti, hranice sa nebudú brať do úvahy. Hranice, ktoré nepatria do regiónu, sú zvyčajne zobrazené bodkovanou čiarou.

Môžete vyriešiť inverzný problém, a to: nakreslite oblasť pre daný logický výraz.

Príklad 2. Nakreslite a zatiente oblasť, pre ktorú body je logická podmienka splnená y ≥ x ∧ y + x ≥ 0 ∧ y< 2 .

Riešenie. Požadovaná oblasť je priesečníkom troch polorovín. Staviame na rovinu (x, y) priamky y = x; y = -x; y = 2. Toto sú hranice oblasti a posledná hranica y = 2 do oblasti nepatrí, preto ju nakreslíme bodkovanou čiarou. Na splnenie nerovnosti y ≥ x je potrebné, aby body boli vľavo od čiary y = x a nerovnosť y = -x bola splnená pre body, ktoré sú napravo od čiary y = -x. Podmienka r< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Použitie logických funkcií na opis elektrických obvodov

Logické funkcie sú veľmi užitočné na opis činnosti elektrických obvodov. Takže pre obvod zobrazený na obr., Kde hodnota premennej X je stav prepínača (ak je zapnutý, hodnota X je „true“ a ak je vypnutý, je „falošný“) , táto hodnota Y je stav žiarovky (ak je zapnutá - hodnota je „true“, a ak nie - „false“), logická funkcia bude zapísaná nasledovne: Y = X. Volá sa funkcia Y funkcia vodivosti.

Pre obvod zobrazený na obr. Má logická funkcia Y tvar: Y = X1 × X2, pretože na zapálenie svetla stačí jeden zapnutý spínač. Na diagrame na obr. Aby svetlo mohlo horieť, musia byť zapnuté oba spínače, preto má vodivostná funkcia tvar: Y = X1 ∧ X2.

V prípade zložitejšieho obvodu bude vodivostná funkcia: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

Obvod môže tiež obsahovať uzatváracie kontakty. V tomto prípade otvorený kontakt ako spínač zaisťuje, aby sa svetlo rozsvietilo pri uvoľnení tlačidla a nie pri stlačení. Pre takéto obvody je odpínač opísaný negáciou.

Tieto dve schémy sa nazývajú rovnať sa ak prúd prechádza jedným z nich, keď prechádza aj druhým. Z dvoch ekvivalentných obvodov je jednoduchší obvod, ktorého vodivá funkcia obsahuje menej prvkov.Úloha nájsť najjednoduchšie schémy medzi ekvivalentmi je veľmi dôležitá.

Použitie aparátu logickej algebry pri návrhu logických obvodov

Algebra logickej matematiky je veľmi užitočná na opis fungovania počítačového hardvéru. Pri spracovaní na počítači sú všetky informácie reprezentované v binárnej forme, to znamená, že sú kódované nejakou sekvenciou 0 a 1. Spracovanie binárnych signálov zodpovedajúcich 0 a 1 sa v počítači vykonáva logickými prvkami. Logické brány, ktoré vykonávajú základné logické operácie A, ALEBO, NIE, sú znázornené na obr.

Symboly logických prvkov sú štandardné a používajú sa pri navrhovaní logických obvodov počítača. Pomocou týchto obvodov môžete implementovať akúkoľvek logickú funkciu, ktorá popisuje činnosť počítača.

Technicky je počítačový logický prvok implementovaný vo forme elektrického obvodu, ktorý je spojením rôznych častí: diódy, tranzistory, odpory, kondenzátory. Vstup logického prvku, ktorý sa nazýva aj brána, prijíma elektrické signály vysokého a nízkeho napätia a na výstupe je tiež daný jeden výstupný signál, buď vysoký alebo nízky. Tieto úrovne zodpovedajú jednému zo stavov binárnej sústavy: 1 - 0; PRAVDA je NEPRAVDA. Každý logický prvok má svoj vlastný symbol, ktorý vyjadruje jeho logickú funkciu, ale neuvádza, aký druh elektronického obvodu je v ňom implementovaný. To uľahčuje zápis a porozumenie zložitým logickým obvodom. Činnosť logických obvodov je popísaná pomocou pravdivostných tabuliek. Konvenčné označenie na obvode OR, znak „1“ - zo zastaraného označenia disjunkcie ako „> = 1“ (hodnota disjunkcie je 1, ak je súčet dvoch operandov väčší alebo rovný 1). Znak „&“ v diagrame AND je skratkou pre anglické slovo a.

Elektronické logické obvody sú zložené z logických prvkov, ktoré vykonávajú zložitejšie logické operácie. Sada logických prvkov pozostávajúca z prvkov NOT, OR, AND, pomocou ktorých môžete vybudovať logickú štruktúru akejkoľvek zložitosti, sa nazýva funkčne kompletný.

Budovanie tabuliek pravdy s booleovským výrazom

Pre logický vzorec môžete vždy písať tabuľka pravdy, to znamená reprezentovať danú logickú funkciu v tabuľkovej forme. V tomto prípade by tabuľka mala obsahovať všetky možné kombinácie funkčných argumentov (vzorcov) a zodpovedajúcich funkčných hodnôt (vzorec vychádza z danej sady hodnôt).

Vhodnou formou zápisu na nájdenie hodnôt funkcie je tabuľka obsahujúca okrem hodnôt premenných a funkčných hodnôt aj hodnoty medziproduktov. Uvažujme príklad zostrojenia tabuľky pravdy pre vzorec $ (X1) ↖ (-) ∧ X2 ∨ (X1 ∨ X2) ↖ (-) ∨ X1 $.

X1	X2	$ (X1) ↖ (-) $	$ (X1) ↖ (-) $ \ X2	X1, X2	$ (X1 ∨ X2) ↖ (-) $	$ (X1) ↖ (-) $ ∧ X2 ∨ $ (X1 ∨ X2) ↖ (-) $	$ (X1) ↖ (-) $ ∧ X2 ∨ $ (X1 ∨ X2) ↖ (-) $ ∨ X1
1	1	0	0	1	0	0	1
1	0	0	0	1	0	0	1
0	1	1	1	1	0	1	1
0	0	1	0	0	1	1	1

Ak funkcia pre všetky sady hodnôt premenných nadobúda hodnotu 1, je to tak rovnako pravdivé; ak pre všetky sady vstupných hodnôt funkcia nadobúda hodnotu 0, je rovnako falošné; ak sada výstupných hodnôt obsahuje 0 aj 1, funkcia sa zavolá uskutočniteľné... Vyššie uvedený príklad je príkladom identicky pravdivej funkcie.

Ak poznáte analytickú formu logickej funkcie, môžete kedykoľvek prejsť na tabuľkovú formu logických funkcií. Pomocou danej tabuľky pravdy je možné vyriešiť inverzný problém, a to: pre danú tabuľku zostrojte analytický vzorec pre logickú funkciu. Existujú dve formy konštrukcie analytickej závislosti logickej funkcie podľa danej tabuľkovej funkcie.

1. Disjunktívna normálna forma (DNF)- súčet produktov vytvorených z premenných a ich negácií pre falošné hodnoty.

Algoritmus na konštrukciu DNF je nasledujúci:

1. v tabuľke pravdy funkcie sú vybraté množiny argumentov, pre ktoré sú logické tvary rovné 1 („true“);
2. všetky vybrané logické sady sú zapísané ako logické produkty argumentov a postupne ich navzájom spájajú pôsobením logického súčtu (disjunkcia);
3. pre argumenty, ktoré sú nepravdivé, sa na vytvorený záznam použije operácia negácie.

Príklad. Pomocou metódy DNF zostrojte funkciu, ktorá určí, že prvé číslo sa rovná druhému. Pravdivostná tabuľka funkcie má tvar

X1	X2	F (X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Riešenie. Vyberieme množiny hodnôt argumentov, v ktorých je funkcia rovná 1. Ide o prvý a štvrtý riadok tabuľky (riadok hlavičky sa pri číslovaní neberie do úvahy).

Zapíšeme logické produkty argumentov týchto množín a spojíme ich s logickým súčtom: X1 ∧ X2 ∨ X1 ∧ X2.

Negáciu píšeme s ohľadom na argumenty vybraných množín, ktoré majú falošnú hodnotu (štvrtý riadok tabuľky; druhá množina vo vzorci; prvý a druhý prvok): X1 ∧ X2 ∨ $ (X1) ↖ ( -) $ ∧ $ (X2) ↖ (-) $.

Odpoveď: F (X1, X2) = X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ $ (X2) ↖ (-) $.

2. Normálna konjunktíva (CNF)- súčin súčtov vytvorených z premenných a ich negácií pre skutočné hodnoty.

Algoritmus na stavbu CNF je nasledujúci:

1. v tabuľke pravdy sú vybraté množiny argumentov, pre ktoré sú logické tvary rovné 0 („nepravda“);
2. všetky vybrané logické množiny ako logické súčty argumentov sú zapísané postupne, pričom ich spájajú operáciou logického produktu (spojka);
3. pre argumenty, ktoré sú pravdivé, je operácia negácie zapísaná do vytvoreného záznamu.

Príklady riešenia problémov

Príklad 1. Uvažujme o predchádzajúcom príklade, to znamená, že pomocou metódy CNF zostrojíme funkciu, ktorá určí, že prvé číslo sa rovná druhému. Pre danú funkciu má jej tabuľka pravdy formu

X1	X2	F (X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Riešenie. Vyberáme množiny hodnôt argumentov, v ktorých je funkcia rovná 0. Ide o druhý a tretí riadok (pri číslovaní sa nadpisový riadok neberie do úvahy).

Zapíšeme logické súčty argumentov týchto množín a spojíme ich s logickým súčinom: X1 ∨ X2 ∧ X1 ∨ X2.

Negáciu píšeme s ohľadom na argumenty vybraných množín, ktoré majú skutočnú hodnotu (druhý riadok tabuľky, prvá množina vzorca, druhý prvok; pre tretí riadok je to druhá množina vzorca , prvý prvok): X1 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ X2.

Bol teda získaný záznam o logickej funkcii v CNF.

Odpoveď: X1 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ X2.

Funkčné hodnoty získané týmito dvoma metódami sú ekvivalentné. Na potvrdenie tohto tvrdenia používame pravidlá logiky: 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) ↖ (-) $.

Príklad 2... Zostavte booleovskú funkciu pre danú tabuľku pravdy:

Hľadaný vzorec: X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ X2.

Dá sa to zjednodušiť: X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ X2 = X2 ∧ (X1 ∨ $ (X1) ↖ (-) $) = X2 ∧ 1 = X2.

Príklad 3. Pre danú tabuľku pravdy zostrojte logickú funkciu pomocou metódy DNF.

X1	X2	X3	F (X1, X2, X3)
1	1	1	1		X1, X2, X3
1	0	1	0
0	1	1	1		$ (X1) ↖ (-) $ ∧ X2 ∧ X3
0	0	1	0
1	1	0	1		X1 ∧ X2 ∧ $ (X3) ↖ (-) $
1	0	0	1		X1 ∧ $ (X2) ↖ (-) $ ∧ $ (X3) ↖ (-) $
0	1	0	0
0	0	0	0

Hľadaný vzorec: X1 ∧ X2 ∧ X ∨ $ (X1) ↖ (-) $ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $ (X3) ↖ (-) $ ∪ X1 ∧ $ (X2) ↖ (-) $ ∧ $ (X3) ↖ (-) $.

Vzorec je dosť ťažkopádny a mal by byť 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) ↖ (-) $.

Tabuľky pravdy na riešenie logických problémov

Zostavenie tabuliek pravdy je jedným zo spôsobov riešenia logických problémov. Pri použití tohto riešenia sú podmienky, ktoré problém obsahuje, opravené pomocou špeciálne zostavených tabuliek.

Príklady riešenia problémov

Príklad 1. Vytvorte tabuľku pravdy pre bezpečnostné zariadenie, ktoré používa tri senzory a spustí sa, keď sú zatvorené iba dva z nich.

Riešenie. Výsledkom riešenia bude zrejme tabuľka, v ktorej požadovaná funkcia Y (X1, X2, X3) bude mať hodnotu „true“, ak akékoľvek dve premenné majú hodnotu „true“.

X1	X2	X3	Y (X1, X2, X3)
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	0
0	0	0	0

Príklad 2. Vytvorte rozvrh hodín na deň, pričom vezmite do úvahy, že hodina informatiky môže byť iba prvá alebo druhá, hodina matematiky - prvá alebo tretia a fyzika - druhá alebo tretia. Je možné vytvoriť rozvrh, ktorý spĺňa všetky požiadavky? Koľko možností plánovania existuje?

Riešenie. Problém je ľahko vyriešený, ak zostavíte príslušnú tabuľku:

	1. lekcia	2. lekcia	3. lekcia
Počítačová veda	1	1	0
Matematika	1	0	1
Fyzika	0	1	1

Tabuľka ukazuje, že pre požadovaný rozvrh existujú dve možnosti:

1. matematika, počítačová veda, fyzika;
2. informatika, fyzika, matematika.

Príklad 3. Do športového tábora prišli traja priatelia - Peter, Boris a Alexey. Každý z nich má rád dva športy. Je známe, že existuje šesť takýchto športov: futbal, hokej, lyžovanie, plávanie, tenis, bedminton. Je tiež známe, že:

1. Boris je najstarší;
2. ten, kto hrá futbal, je mladší ako ten, kto hrá hokej;
3. hrá futbal a hokej a Peter žije v jednom dome;
4. keď dôjde k hádke medzi lyžiarom a tenistom, Boris ich zmieri;
5. Peter nemôže hrať tenis ani bedminton.

Aké športy majú každý z chlapcov?

Riešenie. Zostavme tabuľku a odrazme v nej podmienky problému. Do príslušných buniek zadajte čísla 0 a 1 v závislosti od toho, či je príslušný údaj nepravdivý alebo pravdivý.

Keďže existuje šesť druhov športov, ukazuje sa, že všetci chlapci majú radi rôzne športy.

Z podmienky 4 vyplýva, že Boris nemá rád lyžovanie alebo tenis, ale z podmienok 3 a 5, že Peter nevie hrať futbal, hokej, tenis a bedminton. Preto sú Peterovými obľúbenými športmi lyžovanie a plávanie. Vložíme to do tabuľky a vyplníme zvyšné bunky stĺpcov „Lyže“ a „Plávanie“ nulami.

Tabuľka ukazuje, že tenis môže hrať iba Alexej.

Z podmienok 1 a 2 vyplýva, že Boris nie je futbalista. Alexey preto hrá futbal. Pokračujme vo vypĺňaní tabuľky. Zadajte prázdne bunky do prázdnych buniek v riadku „Alexey“.

Nakoniec sme zistili, že Boris má rád hokej a bedminton. Výsledná tabuľka bude vyzerať takto:

Odpoveď: Peter miluje lyžovanie a plávanie, Boris hokej a bedminton a Alexey futbal a tenis.

Úloha 1 # 10050

\ ((x \ klin y) \ vee (x \ klin \ prekrytie y) \ vee (y \ klin z) \ vee (z \ klin x) \)

Urobte jej tabuľku pravdy. Pre svoju odpoveď zadajte počet množín \ ((x, \) \ (y, \) \ (z), \), pre ktoré je funkcia 1.

1. Zjednodušiť \ ((x \ klin y) \ vee (x \ klin \ prekrytie y). \)

Podľa zákona o distribúcii \ ((y \ klin x) \ vee (x \ klin \ prekrytie y) \) = \ (x \ klin (y \ vee \ nadčiarknuť y). \)\ (y \ vee \ overline y = 1 \) (ak \ (y = 0, \) potom \ (\ overline y \ vee y = 1 \ vee 0 = 1, \) ak \ (y = 1, \) potom \ (\ overline y \ vee y = 0 \ vee 1 = 1). \) Potom \ (x \ klin (y \ vee \ nadčiarknutý y) = x \ klin 1 = x. \)

2. Zjednodušiť \ ((y \ klin z) \ vee (z \ klin x). \) Podľa zákona o distribúcii \ ((y \ klin z) \ vee (z \ klin x) = z \ klin (y \ vee x). \)

3. Získame: \ ((x \ wedge y) \ vee (x \ wedge \ overline y) \ vee (y \ wedge z) \ vee (z \ wedge x) = x \ vee z \ klin (y \ vee x). \)

4. Pravdivá tabuľka obsahuje 8 riadkov (riadky sú vždy \ (2 ^ n, \) kde \ (n \) je počet premenných). V našom prípade existujú 3 premenné.

5. Vyplňte tabuľku pravdy.

\ [\ begin (pole) (| c | c | c | c | c | c | c |) | hline x & y & z & y \ vee x & z \ klin (y \ vee x) & F = x \ vee z \ klin (y \ vee x) \\ \ hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \ hline 0 & 0 & 1 & 0 & 0 & 0 \\ \ hline 0 & 1 & 0 & 1 & 0 & 0 \\ \ hline 0 & 1 & 1 & 1 & 1 & 1 \\ \ hline 1 & 0 & 0 & 1 & 0 & 1 \\ \ hline 1 & 0 & 1 & 1 & 1 & 1 \\ \ hline 1 & 1 & 0 & 1 & 0 & 1 \\ \ hline 1 & 1 & 1 & 1 & 1 & 1 \\ \ hline \ end (pole) \]

Od rozpojenia \ (x \ vee z \ klin (y \ vee x) \) je pravda, ak je pravdivý aspoň jeden z tvrdení, ktoré sú v ňom uvedené, potom pre \ (x = 1 \) \ (F = 1 \) pre akékoľvek \ (y \) a \ (z \) (riadky 5-8 v tabuľka pravdy).

Uvažujme prípad, keď \ (x = 0. \) Potom bude hodnota funkcie závisieť od hodnoty \ (z \ klin (y \ vee x). \) If \ (z \ klin (y \ vee x) \ ) je pravda, potom a \ (F \) je pravda, ak je nepravdivé, potom \ (F \) je nepravdivé. Uvažujme prípad, keď \ (F = 1. \) Spojka \ ((z \ wedge (y \ vee x)) \) je pravdivá, ak sú všetky tvrdenia v ňom uvedené pravdivé, to znamená \ (y \ vee x = 1 \) a \ (z = 1. \) \ (x = 0, \) znamená \ (y \ vee x = 1, \) keď \ (y = 1 \) (riadok 4).

Ak je jedno z tvrdení zahrnutých v spojke nepravdivé, potom je celá spojka nepravdivá. Ak \ (x = 0 \) a \ (y = 0, \) potom \ (y \ vee x = 0. \) Potom \ (z \ klin (x \ vee y) = 0 \) pre akékoľvek \ (z \) (riadky 1-2). Pretože \ (x = 0, \) a druhé tvrdenie v disjunkcii \ ((z \ wedge (x \ vee y)), \) je tiež nepravdivé, potom je nepravdivá celá funkcia. Ak \ (x = 0 \) a \ (y = 1, \) potom \ (y \ vee x = 1. \) Ak \ (z = 0, \) \ (z \ klin (y \ vee x) = 0. \) Potom \ (F = 0 \) (riadok 3). V predchádzajúcom odseku sa uvažoval prípad, keď \ (z = 1, \) \ (y = 1, \) \ (x = 0, \).

Zostavili sme tabuľku pravdy. Vidíme, že je v ňom 5 sád, pre ktoré \ (F = 1. \) Preto je odpoveď 5.

Odpoveď: 5

Úloha 2 # 10051

Logická funkcia \ (F \) je daná výrazom:

\ ((x \ klin \ nadčiarknutý y \ klin z) \ vee (x \ vpravo šípka y) \)

Urobte jej tabuľku pravdy. Pre svoju odpoveď zadajte počet množín \ ((x, \) \ (y, \) \ (z), \), pre ktoré je funkcia 0.

\ [\ begin (pole) (| c | c | c | c | c | c | c | c | c | c |) | hline x & y & z & \ overline y & x \ wedge \ overline y & x \ wedge \ overline y \ wedge z & \ overline x & \ overline x \ vee y & x \ wedge \ overline y \ wedge z \ vee \ overline x \ vee y \\ \ hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ \ hline 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \ hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \ hline 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ \ hline 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ \ hline 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ \ hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \ hline 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 a 1 \\ \ hline \ end (pole) \]

1. \ (x \ rightarrow y \) = \ (\ overline x \ vee y. \)

2. Všimnite si, že pre \ (y = 1 \) \ (F = 1, \), pretože disjunkcia je pravdivá, ak je pravdivý aspoň jeden výraz v nej zahrnutý (riadky 3-4, 7-8 v tabuľke pravdy). Podobne pre \ (\ overline x = 1, \) to znamená pre \ (x = 0, \) \ (F = 1 \) (riadky 1-4).

3. Pre \ (x = 1 \) a \ (y = 0 \) \ (\ overline x \ vee y = 0, \) \ (x \ wedge \ overline y = 1. \) For \ (z = 1 \) \ (x \ klin \ prekrytie y \ klin z = 1 \) a \ (F = 1, \), pretože jeden z výrazov (riadok 6) je pravdivý, a pre \ (z = 0 \) \ (x \ klin \ prekrytie y \ klin z = 0 \) a \ (F = 0, \), pretože oba výrazy zahrnuté v disjunkcii sú nepravdivé (riadok 5).

Podľa zostrojenej tabuľky pravdy vidíme, že pre jednu množinu \ ((x, \) \ (y, \) \ (z) \) \ (F = 0. \)

Odpoveď: 1

Úloha 3 # 10052

Logická funkcia \ (F \) je daná výrazom:

\ ((\ overline (z \ vee \ overline y)) \ vee (w \ wedge (z \ equiv y)) \)

Urobte jej tabuľku pravdy. Ako odpoveď zadajte súčet hodnôt \ (z, \) \ (y \) a \ (w, \), pre ktoré \ (F = 1. \)

\ [\ begin (pole) (| c | c | c | c | c | c | c | c | c | c | c |) \ hline w & y & z & \ overline y & z \ vee \ overline y & \ overline ( z \ vee \ overline y) & z \ equiv y & w \ wedge (z \ equiv y) & \ overline z \ vee \ overline y \ vee w \ wedge (z \ equiv y) \\ \ hline 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ \ hline 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \ hline 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \ hline 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ \ hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ \ hline 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \ hline 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \ hline 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \ hline \ end (pole) \]

1. \ ((\ overline (z \ vee \ overline y)) = \ overline z \ wedge y \)

2. Pravdivá tabuľka bude mať \ (2 ^ 3 = 8 \) riadkov.

3. Ak \ (z = 1 \) a \ (y = 1, \) \ (potom (z \ ekviv y) = 1 \) (pretože ekvivalencia je pravdivá vtedy a len vtedy, ak sú obe tvrdenia súčasne nepravdivé alebo pravdivé) ... \ (\ overline z \ wedge y = 0 \) \ ((0 \ wedge 1 = 0). \) If \ (w = 1, \) \ (w \ wedge (z \ equiv y) = 1 \) \ ((1 \ wedge 1 = 1) \) a \ (F = 1, \), pretože disjunkcia je pravdivá, ak je pravdivé aspoň jedno z tvrdení, ktoré je v nej uvedené (riadok 8 v tabuľke pravdy). Ak \ (w = 0, \) \ (w \ wedge (z \ equiv y) = 0 \) \ ((0 \ wedge 1 = 0) \) a \ (F = 0, \) pretože oba príkazy sú zahrnuté v disjunkcii sú nepravdivé (riadok 4).

4. Podobne pre \ (z = 0, y = 0. \) \ ((z \ ekvivalent y) = 1, \) \ (\ overline z \ klin y = 0 \) \ ((1 \ klin 0 = 0 ). \) Potom opäť bude hodnota funkcie závisieť od \ (w. \) Pre \ (w = 1 \) \ (w \ klin (z \ ekviv. y) = 1, \)\ (F = 1, \), pretože jedno z tvrdení zahrnutých v disjunkcii je pravdivé (riadok 5) a pre \ (w = 0 \) \ (w \ klin (z \ ekviv. y) = 0, \)\ (F = 0, \), pretože všetky tvrdenia sú nepravdivé (riadok 1).

5. Ak \ (z = 0 \) a \ (y = 1, \) potom \ (\ overline z \ klin y = 1 \) \ ((1 \ klin 1 = 1). \) Pretože \ ((z \ equiv y) = 0 \) (koniec koncov, hodnoty \ (z \) a \ (y \) sú rôzne), bude nepravdivé pre akékoľvek \ (w. \) Potom, pretože hodnota premennej \ (w \) nebude mať vplyv na hodnotu funkcie, pretože \ (z = 0 \) a \ (y = 1 \) \ (w \) môže byť buď 0 alebo 1. \ (F = 1, \ ) pretože jedno z tvrdení zahrnutých v disjunkcii je pravdivé (riadky 3, 7).

6. Ak \ (z = 1 \) a \ (y = 0, \) potom \ (\ overline z \ klin y = 0 \ klin 0 = 0. \) Pretože \ ((z \ ekviv. Y) = 0, \) \ (w \ wedge (z \ ekviv. y) = w \ klin 0 \) bude nepravdivé pre akékoľvek \ (w \) (t.j. \ (w \) môže byť 0 a 1). Preto pre \ (z = 1 \) a \ (y = 0 \) \ (F \) bude vždy nepravdivé (pretože oba príkazy zahrnuté v disjunkcii sú nepravdivé, riadky 2, 5).

7. \ (F = 1 \) pre nasledujúce množiny \ (z, \) \ (y, \) \ (w: \) (0, 0, 1), (0, 1, 1), (1, 1, 1), (0, 1, 0). Ak spočítame hodnoty, dostaneme 7.

Odpoveď: 7

Úloha 4 # 10053

Logická funkcia \ (F \) je daná výrazom:

\ (a \ wedge ((\ overline (b \ wedge c)) \ vee (a \ wedge \ overline b) \ vee (\ overline c \ wedge a)) \)

Urobte jej tabuľku pravdy. Ako odpoveď zadajte súčet hodnôt \ (a, \) \ (b \) a \ (c, \), pre ktoré \ (F = 1. \)

\ [\ begin (pole) (| c | c | c | c | c | c |) \ hline a & b & c & F \\\ hline 0 & 0 & 0 & 0 \\ \ hline 0 & 0 & 1 & 0 \ \ \ hline 0 & 1 & 0 & 0 \\ \ hline 0 & 1 & 1 & 0 \\ \ hline 1 & 0 & 0 & 1 \\ \ hline 1 & 0 & 1 & 1 \\ \ hline 1 & 1 & 0 & 1 \\ \ hline 1 & 1 & 1 & 0 \\ \ hline \ end (pole) \]

1. V tabuľkách pravdy \ (2 ^ 3 = 8 \) riadkov.

2. Pre \ (a = 0 \) \ (F = 0 \) pre akékoľvek hodnoty \ (b \) a \ (c, \), pretože spojka je pravdivá vtedy a len vtedy, ak sú pravdivé všetky tvrdenia v nej zahrnuté (riadky 1-4 v tabuľke pravdy).

3. Zvážte prípady, keď \ (a = 1. \) Ak \ (\ overline ((b \ wedge c)) \ vee (a \ wedge \ overline b) \ vee (\ overline c \ wedge a) = 1, \) potom \ (F = 1 \) (pretože oba tvrdenia budú pravdivé), inak \ (F = 0 \) (pretože jedno tvrdenie bude nepravdivé). De Morganov zákon \ (\ overline (b \ wedge c) = \ overline b \ vee \ overline c. \) Potom, berúc do úvahy, že \ (a = 1, \) \ (\ overline ((b \ wedge c)) \ vee (a \ wedge \ overline b) \ vee (\ overline c \ wedge a) = \ overline b \ vee \ overline c \ vee \ overline b \ vee \ overline c = \ overline b \ vee \ overline c. \)

4. Ak \ (\ overline b = 0 \) a \ (\ overline c = 0 \) (súčasne, tj pre \ (b = 1 \) a \ (c = 1), \) potom \ (\ overline b \ vee \ overline c = 0 \) a \ (F = 0 \) (riadok 8). V iných prípadoch \ (\ overline b \ vee \ overline c = 1 \) a \ (F = 1 \) (riadky 5-7).

5. Množiny \ ((x, \) \ (y, \) \ (z), \), pre ktoré \ (F = 1: \) (1, 0, 0), (1, 1, 0), (1, 0, 1). Súčet hodnôt je 5.

Odpoveď: 5

Úloha 5 # 10054

Logická funkcia \ (F \) je daná výrazom:

\ (((a \ wedge b) \ vee (b \ wedge c)) \ equiv ((d \ rightarrow a) \ vee (b \ wedge \ overline c)) \)

Vytvorte tabuľku pravdy. Ako odpoveď zadajte súčet hodnôt \ (a, \), pri ktorých \ (F = 0, \)

\ [\ begin (pole) (| c | c | c | c | c | c | c |) \ hline a & b & c & d & F \\\ hline 0 & 0 & 0 & 0 & 0 \\ \ hline 0 & 0 & 0 & 1 & 1 \\ \ hline 0 & 0 & 1 & 1 & 1 \\ \ hline 0 & 1 & 1 & 1 & 0 \\ \ hline 1 & 0 & 0 & 0 & 0 \\ \ hline 1 & 1 & 0 & 0 & 1 \\ \ hline 1 & 1 & 1 & 0 & 1 \\ \ hline 1 & 1 & 1 & 1 & 1 \\ \ hline 0 & 1 & 0 & 0 & 0 \\ \ hline 0 & 0 & 1 & 0 & 0 \\ \ hline 1 & 1 & 0 & 1 & 1 \\ \ hline 1 & 0 & 1 & 0 & 0 \\ \ hline 1 & 0 & 0 & 1 & 0 \\ \ hline 0 & 1 & 1 & 0 & 1 \\ \ hline 1 & 0 & 1 & 1 & 0 \\ \ hline 0 & 1 & 0 & 1 & 0 \\ \ hline \ end (pole) \]

1. Podľa zákona o distribúcii \ ((a \ klin b) \ vee (b \ klin c) = b \ klin (a \ vee c). \)

2. \ (d \ rightarrow a = \ overline d \ vee a. \)

3. \ (((a \ wedge b) \ vee (b \ wedge c)) \ equiv ((d \ rightarrow a) \ vee (b \ wedge \ overline c)) = b \ klin (a \ vee c) \ equiv (\ overline d \ vee a \ vee (b \ wedge \ overline c)). \)

4. Ak \ (b = 0, \), potom sa ľavá strana funkcie rovná 0 \ ((0 \ klin (a \ vee c) = 0). \) \ (b \ klin \ prekrytie c = 0 \ klin \ prekrytie c = 0. \) To znamená, že pre \ (b = 0 \) \ (c \) môže byť čokoľvek, pretože to neovplyvňuje hodnotu funkcie. \ (F = 1, \) if \ (\ overline d \ vee a = 0 \) (potom jeden z výrazov zahrnutých v disjunkcii bude pravdivý). To sa robí s \ (\ overline d = 0 \) \ ((d = 1) \) a \ (a = 0 \) (riadky 2, 3). Pre ostatné \ (d \) a \ (a \) \ (\ overline d \ vee a = 0, \) to znamená \ (F = 0, \), pretože operácia ekvivalencie je pravdivá vtedy a len vtedy, ak sú oba príkazy súčasne pravdivé alebo nepravdivé (riadky 1, 10 v tabuľke pravdy).

5. Ak \ (b = 1, \) potom \ (b \ klin (a \ vee c) = 1 \ klin (a \ vee c) = a \ vee c. \) \ (b \ klin \ pretiahnutie c = 1 \ klin \ prekrytie c = \ pretiahnutie c. \) Potom to máme \ (a \ vee c \ equiv \ overline d \ vee a \ vee \ overline c. \) Ak \ (a = 1, \) potom \ (a \ vee c = 1 \) a \ (\ overline d \ vee a \ vee \ overline c = 1, \) pretože disjunkcia je pravdivá, ak je aspoň jeden z výrazov pravdivý (a obe disjunkcie obsahujú \ (a = 1). \) Potom, ak \ (b = 1 \) a \ (a = 1, \) \ (F = 1 \) pre ľubovoľné \ (c \) a \ (d \) (riadky 5, 7, 8, 11).

Ak \ (a = 0, \) potom \ (a \ vee c = 0 \ vee c = c, \) a \ (\ overline d \ vee a \ vee \ overline c = \ overline d \ vee \ overline c. \) Máme: \ (c \ equiv (\ overline d \ vee \ overline c). \) Pre \ (c = 1 \) \ (1 \ equiv \ overline d. \) Pre \ (d = 1 \) \ (F = 0, \) pretože príkazy sú odlišné (riadok 4), pre \ (d = 0 \) \ (F = 1, \), pretože oba tvrdenia sú pravdivé (riadok 14). Pre \ (c = 0 \) \ (0 \ equiv (\ overline d \ vee 1). \) Pretože \ (\ overline d \ vee 1 \) je disjunkcia, v ktorej je jedno z tvrdení pravdivé, je celá disjunkcia pravdivá. Potom \ (0 \ ekviv. 1, \) čo nie je pravda, čo znamená \ (F = 0 \) pre akékoľvek \ (d \) (riadky 9, 16).

Podľa zostrojenej tabuľky vidíme, že \ (F = 0 \) pre \ (a = 0 \) (riadky 1, 4, 9, 10, 16) a pre \ (a = 1 \) (riadky 6, 12 , 13, 15). Potom je súčet hodnôt 0 * 5 + 1 * 4 = 4.

Odpoveď: 4

Úloha 6 # 10055

Logická funkcia \ (F \) je daná výrazom:

\ ((a \ equiv (b \ vee \ overline c)) \ rightarrow (c \ wedge (b \ vee a)) \)

Vytvorte tabuľku pravdy. Ako odpoveď zadajte súčet hodnôt \ (c, \), pre ktoré \ (F = 1. \)

\ [\ begin (pole) (| c | c | c | c | c | c |) \ hline a & b & c & F \\\ hline 0 & 0 & 0 & 1 \\ \ hline 0 & 0 & 1 & 0 \ \ \ hline 0 & 1 & 1 & 1 \\ \ hline 0 & 1 & 0 & 1 \\ \ hline 1 & 0 & 0 & 0 \\ \ hline 1 & 1 & 0 & 0 \\ \ hline 1 & 1 & 1 & 1 \\ \ hline 1 & 0 & 1 & 1 \\ \ hline \ end (pole) \]

Tabuľka obsahuje \ (2 ^ 3 = 8 \) riadkov.

1. implikácia je nepravdivá vtedy a len vtedy, ak z pravdivého tvrdenia vyplýva, že je nepravdivá. Preto \ (F = 0, \) ak a \ (c \ klin (b \ vee a) = 0. \) V ostatných prípadoch \ (F = 1. \) Zvážte, pre aké hodnoty \ (a, \ ) \ (b \) a \ (c \) \ (a \ equiv (b \ vee \ overline c) = 1 \)(ak \ (a \ equiv (b \ vee \ overline c) = 0, \) potom \ (F = 1 \) pre akúkoľvek hodnotu \ (c \ klin (b \ vee a) = 0). \)

Ak \ (a = 0, \) potom na spustenie \ (a \ equiv (b \ vee \ overline c) = 1, \) nevyhnutné \ (b \ vee \ overline c = 0 \) (operácia ekvivalencie je koniec koncov pravdivá vtedy a len vtedy, ak sú obidva tvrdenia pravdivé alebo sú obe nepravdivé). Aby bola disjunkcia \ ((b \ vee \ overline c) \) nepravdivá, musia byť v nej zahrnuté obidva tvrdenia, tj \ (b = 0 \) a \ (\ overline c = 0 \) \ ( (c = 1). \) Pre tieto hodnoty \ (c \ klin (b \ vee a) = 1 \ klin (0 \ vee 0) = 0. \) Potom \ ((a \ equiv (b \ vee \ overline c)) \ rightarrow (c \ wedge (b \ vee a)) = 1 \ rightarrow 0 = 0, \)\ (F = 0. \) To zodpovedá riadku 2 z tabuľky pravdy.

Ak \ (a = 1, \) potom spustite \ (a \ equiv (b \ vee \ overline c) = 1, \)\ (b \ vee \ overline c = 1. \) To sa deje vo viacerých prípadoch. Ak \ (b = 1, \) potom \ (c \) sa môže rovnať nule aj jedničke, pretože jeden z tvrdení zahrnutých v disjunkcii je už pravdivý. Pre \ (c = 1 \) \ (c \ klin (b \ vee a) = 1 \ klin 1 = 1, \) potom \ (F = 1 \) (pretože \ (1 \ rightarrow 1 = 1, \) riadok 7). Pre \ (c = 0 \) \ (c \ klin (b \ vee a) = 0 \ klin 1 = 0, \) teda \ (F = 0 \) \ ((1 \ pravá šípka 0 = 0, \) riadok 6). Ak \ (b = 0, \) potom \ (\ overline c = 1 \) \ ((c = 0, \), potom jedno z tvrdení zahrnutých v disjunkcii bude pravdivé). V tomto prípade \ (c \ klin (b \ vee a) = 0 \ klin (0 \ vee 1) = 0. \)\ (F = 0, \) pretože \ (1 \ pravá šípka 0 = 0 \) (riadok 5).

2. Pre ostatné hodnoty \ (a, \) \ (b \) a \ (c \) \ (F = 1, \) pretože \ (a \ equiv (b \ vee \ overline c) = 0 \)(riadky 1, 3, 7, 8).

3. Zo zostavenej tabuľky pravdy vidíme, že \ (F = 1 \) pre \ (c = 0 \) (riadky 1, 4) a pre \ (c = 1 \) (riadky 3, 7, 8). Súčet hodnôt je 0 * 2 + 1 * 3 = 3. \ (2 ^ 4 = 16 \) riadkov.

1. Pretože spojka je nepravdivá, ak je aspoň jeden z tvrdení nepravdivý, potom pre \ (d = 0 \) \ (F = 0 \) pre akékoľvek \ (a, \) \ (b \) a \ ( c \) (riadky 1, 6-10, 12, 14 v tabuľke pravdy).

2. Uvažujme prípad, keď \ (d = 1. \) Potom \ ((a \ rightarrow b) \ wedge (b \ equiv c) \ wedge d = (a \ rightarrow b) \ klin (b \ equiv c) \ klin 1 = (a \ rightarrow b) \ klin (b \ equiv c). \) Pre \ (b = 1 \) \ (a \ rightarrow b = a \ rightarrow 1 = 1 \) pre akékoľvek \ (a, \), pretože implikácia je nepravdivá vtedy a len vtedy, ak z pravdivého tvrdenia vyplýva, že je nepravdivé. Ak \ (c = 1, \) potom \ (b \ equiv c = 1, \), pretože operácia ekvivalencie je pravdivá, ak sú oba výrazy pravdivé alebo sú obidva nepravdivé, a \ (F = 1 \) (pretože všetky zahrnuté výrazy sú v spojení sú pravdivé). To zodpovedá riadkom 4 a 5. Ak \ (c = 0, \) potom \ (b \ equiv c = 0, \) \ (F = 0, \), pretože jeden z výrazov zahrnutých v spojke je nepravdivý (riadky 11 a 16).

Pre \ (b = 0: \) ak \ (a = 1, \) potom \ (a \ rightarrow b = 1 \ rightarrow 0 = 0, \) potom je jeden z výrazov zahrnutých v spojke nepravdivý a \ (F = 0 \) pre akékoľvek \ (c \) (riadky 13 a 15). Ak \ (a = 0, \) potom \ (a \ rightarrow b = 0 \ rightarrow 0 = 1. \) Ak \ (c = 0, \) potom \ (b \ ekviv c = 0 \ ekviv 0 = 1, \)\ (F = 1, \), pretože oba výrazy zahrnuté v spojke sú pravdivé (riadok 2). Ak \ (c = 1, \) potom \ (b \ ekviv c = 0 \ ekviv 1 = 0, \)\ (F = 0, \), pretože jeden z výrazov zahrnutých v spojke je nepravdivý (riadok 3).

Teda \ (F = 1 \) pre \ (d = 1 \) (riadky 2, 4, 5). Súčet hodnôt \ (d \) je 1 * 3 = 3.

Konštrukcia pravdivostných tabuliek pre komplexné tvrdenia.

Booleovská priorita

1) inverzia 2) spojka 3) disjunkcia 4) implikácia a ekvivalencia

Ako vytvoriť tabuľku pravdy?

Pravdivostná tabuľka logického vzorca podľa definície vyjadruje korešpondenciu medzi rôznymi množinami hodnôt premenných a hodnotami vzorca.

Pre vzorec, ktorý obsahuje dve premenné, existujú iba štyri takéto sady hodnôt premenných:

(0, 0), (0, 1), (1, 0), (1, 1).

Ak vzorec obsahuje tri premenné, potom existuje osem možných množín hodnôt premenných (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1) , ((1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Počet množín pre vzorec so štyrmi premennými je šestnásť a podobne.

Vhodnou formou zápisu na nájdenie hodnôt vzorca je tabuľka obsahujúca okrem hodnôt premenných a hodnôt vzorcov aj hodnoty medziproduktov.

Príklady.

1. Vytvorme tabuľku pravdy pre vzorec 96% "style =" width: 96,0% ">

Tabuľka to ukazuje pre všetky sady hodnôt premenných xay vzorec nadobúda hodnotu 1, to je, je rovnako pravdivé.

2. Tabuľka pravdy pre vzorec 96% "style =" width: 96,0% ">

Tabuľka to ukazuje pre všetky množiny hodnôt premenných x a y vzorec nadobúda hodnotu 0, to je, je rovnako falošné .

3. Tabuľka pravdy pre vzorec 96% "style =" width: 96,0% ">

Tabuľka to ukazuje vzorec 0 "style =" border-collapse: collapse; border: none ">

Záver: v poslednom stĺpci sme dostali všetky jednotky. To znamená, že význam komplexného tvrdenia platí pre všetky hodnoty jednoduchých tvrdení K a C. Učiteľ preto logicky uvažoval správne.