Ekvivalentné, TI a TL vzorce algebry logiky. Základné ekvivalencie. (Zákony logických operácií). Zákon duality. Booleovský zákon algebry jednotlivých prvkov

Logika- veda, ktorá študuje zákonitosti a formy myslenia; doktrína metód uvažovania a dôkazov.

Zákony sveta, podstatu predmetov, to, čo je v nich bežné, sa učíme prostredníctvom abstraktného myslenia. Hlavnými formami abstraktného myslenia sú pojmy, úsudky a závery.

koncepcie- forma myslenia, ktorá odráža podstatné znaky jednotlivého predmetu alebo triedy homogénnych predmetov. Pojmy v jazyku sú vyjadrené slovami.

Rozsah koncepcie- súbor predmetov, z ktorých každý má atribúty tvoriace obsah pojmu. Rozlišujú sa pojmy všeobecný a jednotný.

Podľa objemu sa rozlišujú tieto vzťahy pojmov:

identity alebo koincidencia objemov, čo znamená, že objem jedného konceptu sa rovná objemu iného konceptu;
podriadenosti alebo zahrnutie zväzkov: objem jedného z konceptov je plne zahrnutý do objemu druhého;
výnimkou zväzky - prípad, v ktorom nie je jediný znak, ktorý by bol v dvoch zväzkoch;
križovatka alebo čiastočná zhoda objemov;
podriadenosti zväzky - prípad, keď sú zväzky dvoch konceptov, ktoré sa navzájom vylučujú, zahrnuté do zväzku tretieho.

Rozsudok- je to forma myslenia, v ktorej sa niečo potvrdzuje alebo popiera o predmetoch, znakoch alebo ich vzťahoch.

záver- forma myslenia, prostredníctvom ktorej z jedného alebo viacerých úsudkov, nazývaných premisy, získavame podľa určitých pravidiel vyvodzovania úsudok-záver.

Algebra v širšom zmysle slova náuka o všeobecných operáciách podobných sčítaniu a násobeniu, ktoré možno vykonávať nielen s číslami, ale aj s inými matematickými objektmi.

Príklady algebier: algebra prirodzených čísel, algebra racionálnych čísel, algebra polynómov, algebra vektorov, algebra matíc, algebra množín atď. Objektmi algebry logiky alebo Booleovej algebry sú výroky.

vyhlásenie- ide o akúkoľvek vetu akéhokoľvek jazyka (výrok), ktorej obsah možno určiť ako pravdivý alebo nepravdivý.

Každý návrh je buď pravdivý alebo nepravdivý; nemôže to byť oboje súčasne.

V prirodzenom jazyku sú výpovede vyjadrené oznamovacími vetami. Zvolacie a opytovacie vety nie sú výroky.

Výroky môžu byť vyjadrené pomocou matematických, fyzikálnych, chemických a iných znakov. Z dvoch číselných výrazov možno urobiť výroky spojením so znamienkami rovnosti alebo nerovnosti.

Výpis je tzv jednoduché(elementárna), ak žiadna jej časť sama osebe nie je vyhlásením.

Výrok zložený z jednoduchých výrokov sa nazýva tzv zložený(ťažké).

Jednoduché výroky v algebre logiky sa označujú veľkými latinskými písmenami:
ALE= (Aristoteles je zakladateľ logiky),
AT= (Na jabloniach rastú banány).

O odôvodnení pravdivosti alebo nepravdivosti jednoduchých tvrdení sa rozhoduje mimo algebry logiky. Napríklad pravdivosť alebo nepravdivosť výroku: "Súčet uhlov trojuholníka je 180 stupňov" je stanovená geometriou a - v Euklidovej geometrii je toto tvrdenie pravdivé a v Lobačevského nepravdivé.

Pravdivému tvrdeniu je priradená 1, nepravdivému 0. ALE = 1, AT = 0.

Algebra logiky je abstrahovaná od sémantického obsahu výrokov. Zaujíma ju len jedna skutočnosť - daný výrok je pravdivý alebo nepravdivý, čo umožňuje určiť pravdivosť alebo nepravdivosť zložených výrokov algebraickými metódami.

Základné operácie výrokovej algebry.

Logická operácia CONJUNCTION(lat. conjunctio - viažem):

v prirodzenom jazyku zodpovedá spojka a;
označenie: & ;
v programovacích jazykoch je zápis: a;
iné meno: logické násobenie.

Spojka je logická operácia, ktorá spája každé dva jednoduché výroky so zloženým výrokom, ktorý je pravdivý vtedy a len vtedy, ak sú pravdivé oba pôvodné výroky.

Tabuľka pravdivosti spojok:

ALE	AT	ALE&AT
0	0	0
0	1	0
1	0	0
1	1	1

Logická operácia DISJUNCTION(lat. disjunctio - rozlišujem):

Disjunkcia je logická operácia, ktorá spája každé dva jednoduché výroky so zloženým výrokom, ktorý je nepravdivý vtedy a len vtedy, ak sú oba pôvodné výroky nepravdivé a pravdivé, keď je pravdivý aspoň jeden z dvoch výrokov, ktoré ho tvoria.

Tabuľka pravdy o disjunkcii:

ALE	AT	ALEAT
0	0	0
0	1	1
1	0	1
1	1	1

Logická operácia INVERZNÁ(lat. inversio - obrat):

Negácia je logická operácia, ktorá spája každý jednoduchý výrok so zloženým výrokom, ktorý spočíva v tom, že pôvodný výrok je negovaný.

Tabuľka negatívnej pravdy:

ALE	nie A
0	1
1	0

Funkcia logického sčítania OR (LogValue1;LogValue2;…) sa vyhodnotí ako TRUE (True) iba vtedy, keď je aspoň jeden booleovský argument TRUE (1).

Funkcia logickej negácie NOT(LogValue) sa vyhodnotí ako TRUE (True), keď je logický argument NEPRAVDA (0), a naopak ako hodnota FALSE (False), keď je logický argument TRUE (1).

Logická operácia DÔSLEDOK(lat. implicatio - úzko spájam):

Implikácia je logická operácia, ktorá spája každé dva jednoduché výroky so zloženým výrokom, ktorý je nepravdivý vtedy a len vtedy, ak je podmienka (prvý výrok) pravdivá a dôsledok (druhý výrok) je nepravdivý.

Tabuľka pravdy implikácie:

ALE	AT	ALEAT
0	0	1
0	1	1
1	0	0
1	1	1

Logická operácia EKVIVALENCIA(lat. aequivalens - ekvivalent):

v prirodzenom jazyku zodpovedá obratom reči vtedy a len vtedy a ak a len vtedy;
označenie: ~ ;
iné meno: rovnocennosť.

Ekvivalencia je logická operácia, ktorá priraďuje ku každému dvom jednoduchým výrokom zložený výrok, ktorý je pravdivý vtedy a len vtedy, ak sú oba pôvodné výroky pravdivé alebo oba nepravdivé.

Pravdivostná tabuľka ekvivalencie:

ALE	AT	ALE~AT
0	0	1
0	1	0
1	0	0
1	1	1

Logické operácie majú nasledujúcu prednosť: akcie v zátvorkách, inverzia, &, , ~.

Nazýva sa tabuľka zobrazujúca, aké hodnoty má zložený príkaz pre všetky kombinácie (množiny) hodnôt jeho jednoduchých príkazov pravdivostná tabuľka zložená výpoveď.

Zložené výroky v algebre logiky sa píšu pomocou logických výrazov. Pre každý logický výraz stačí jednoducho zostaviť pravdivostnú tabuľku.

Algoritmus na zostavenie pravdivostnej tabuľky:

spočítať počet premenných n v logickom vyjadrení;
určiť počet riadkov v tabuľke m = 2 n ;
spočítať počet logických operácií vo vzorci;
stanoviť postupnosť vykonávania logických operácií, berúc do úvahy zátvorky a priority;
určiť počet stĺpcov v tabuľke: počet premenných plus počet operácií;
zapisovať množiny vstupných premenných, berúc do úvahy skutočnosť, že ide o prirodzený rad n-bitových binárnych čísel od 0 do 2 n -1;
vyplňte pravdivostnú tabuľku po stĺpcoch a vykonajte logické operácie v súlade so sekvenciou stanovenou v odseku 4.

Aby sa predišlo chybám, odporúča sa, aby sa sady vstupných premenných uvádzali takto:
a) určiť počet súborov vstupných premenných;
b) rozdeľte stĺpec hodnôt prvej premennej na polovicu a vyplňte hornú časť stĺpca 0 a spodnú časť -1;
c) rozdeliť stĺpec hodnôt druhej premennej na štyri časti a vyplniť každú štvrtinu striedajúcimi sa skupinami 0 alebo 1, počnúc skupinou 0;
d) pokračujte v delení stĺpcov hodnôt nasledujúcich premenných 8, 16 atď. časti a ich vyplnenie skupinami 0 alebo 1, kým skupiny 0 a 1 nebudú pozostávať z jedného znaku.

Príklad. Pre vzorec A&(B C) zostavte pravdivostnú tabuľku algebraicky a pomocou tabuliek.

Počet booleovských premenných je 3, preto by počet riadkov v pravdivostnej tabuľke mal byť 2 3 = 8.

Počet logických operácií vo vzorci je 5, preto by počet stĺpcov v pravdivostnej tabuľke mal byť 3 + 5 = 8.

ALE	AT	C	ATC	ALE & (ATC)
0	0	0	1	0
0	0	1	0	0
0	1	0	1	0
0	1	1	1	0
1	0	0	1	1
1	0	1	0	0
1	1	0	1	1
1	1	1	1	1

Booleovská funkcia zavolajte funkciu F(X 1, X 2, ..., X n), ktorého argumenty X 1, X 2, ..., X n(nezávislé premenné) a samotná funkcia (závislá premenná) nadobúdajú hodnoty 0 alebo 1.

Tabuľka zobrazujúca, aké hodnoty má logická funkcia pre všetky kombinácie hodnôt jej argumentov, sa nazýva pravdivostná tabuľka logickej funkcie. Pravdivostná tabuľka logických funkcií n argumenty obsahuje 2 n linky, n stĺpce hodnoty argumentu a 1 stĺpec hodnoty funkcie.

Logické funkcie môžu byť špecifikované tabuľkovým spôsobom alebo analyticky - vo forme vhodných vzorcov.

Ak je logická funkcia reprezentovaná pomocou disjunkcií, konjunkcií a inverzií, potom sa táto forma reprezentácie nazýva normálne.

Existuje 16 rôznych logických funkcií z dvoch premenných.

Booleovské výrazy volal ekvivalent, ak sa ich pravdivé hodnoty zhodujú s akýmikoľvek hodnotami logických premenných, ktoré sú v nich zahrnuté.

V algebre logiky existuje množstvo zákonov, ktoré umožňujú ekvivalentné transformácie logických výrazov. Uveďme vzťahy odrážajúce tieto zákony.

Zákon dvojitej negácie:
nie (nie A) = A.
Dvojitá negácia vylučuje negáciu.
Komutatívny (komutatívny) zákon:
- pre logické doplnenie:
A B = B A;

A&B=B&A.
Výsledok operácie s výpismi nezávisí od poradia, v akom sa tieto výpisy zoberú.
Asociačný (asociačný) zákon:
- pre logické doplnenie:
(AB) C = A (BC);
Pre logické násobenie:
(A & B) & C = A & (B & C).
S rovnakými znakmi môžu byť zátvorky umiestnené ľubovoľne alebo dokonca vynechané.
Distribučné (distribučné) právo:
- pre logické doplnenie:
(AB) & C = (A & C) (B & C);
Pre logické násobenie:
(A & B) C = (AC) & (BC).
Definuje pravidlo pre uzatváranie všeobecných výrokov.
Zákon všeobecnej inverzie (de Morganove zákony):
- pre logické doplnenie:
;
Pre logické násobenie:
.
Zákon idempotencie (z latinských slov idem - rovnaký a potens - silný; doslova - ekvivalent):
- pre logické doplnenie:
A A = A;
Pre logické násobenie:
A&A=A.
Zákon znamená žiadne exponenty.
Zákony neustáleho vylúčenia:
- pre logické doplnenie:
Ai = 1, A° = A;
Pre logické násobenie:
A&1 = A, A&0 = 0.
Zákon rozporu:
A & (nie A) = 0.
Je nemožné, aby protichodné tvrdenia boli zároveň pravdivé.
Zákon o vylúčení tretieho:
A (nie A) = 1.
Z dvoch protichodných tvrdení o tej istej téme je jedno vždy pravdivé a druhé nepravdivé, tretie nie je dané.
Absorpčný zákon:
- pre logické doplnenie:
A(A&B)=A;
Pre logické násobenie:
A & (A B) = A.
Zákon vylúčenia (lepenie):
- pre logické doplnenie:
(A & B) (& B) = B;
Pre logické násobenie:
(A B) & (B) = B.
Zákon protikladu (pravidlo obrátenia):
(AB) = (BA).
Platnosť vyššie uvedených zákonov je možné dokázať tabuľkovým spôsobom: zapíšte všetky množiny hodnôt A a B, vypočítajte hodnoty ľavej a pravej časti výrazu, ktorý sa na nich dokazuje, a uistite sa, že výsledné stĺpce sa zhodujú.

Príklad. Zjednodušte boolovský výraz:

Efimova O., Morozov V., Ugrinovič N. Kurz výpočtovej techniky so základmi informatiky. Učebnica pre seniorské triedy. - M.: LLC "Vydavateľstvo AST"; ABF, 2000
Zošit-workshop z informatiky. V 2 zväzkoch / Ed. I. Semakina, E. Khenner. - M.: Laboratórium základných znalostí, 2001
Ugrinovič N. Informatika a informačné technológie. Ročník 10-11 - M .: Laboratórium základných znalostí, JSC "Moskva učebnice", 2001

Úlohy a testy na tému "Základy formálnej logiky"

Prístup k logike DBMS - Logické a matematické modely 10. ročník
Lekcie: 5 Úlohy: 9 Kvízy: 1
Riešenie logických úloh pomocou matematickej logiky
Lekcie: 4 Zadania: 6 Testy: 1

Milý študent!

Práca 1 predstavuje tri témy, ktoré tvoria základ predmetu "Informačné technológie". Dúfame, že už máte minimálne skúsenosti s počítačom a zoznámili ste sa s jeho zariadením na strednej škole.

Téma "Počítačová komunikácia. Internet" je v poslednej dobe veľmi zaujímavá, veľa mladých ľudí trávi takmer všetok svoj voľný čas v globálnej sieti. Chcel by som vám pripomenúť, že ovládanie internetu znamená nielen schopnosť „surfovať“ po sieti a občas navštíviť zaujímavé „chaty“, ale aj pochopiť princípy organizácie informácií v globálnej sieti, pochopiť jej štruktúru, protokoly, vedieť konfigurovať prehliadač a e-mailové programy, poznať a dodržiavať etiku práce na internete a samozrejme využívať sieť na jej najdôležitejší účel – rozširovať si obzory.

V tomto kurze sme sa nezaoberali technológiou vytvárania webových stránok, pretože sme verili, že minimálne znalosti na vytvorenie webovej domovskej stránky možno získať z ďalšej literatúry. Vytváranie stránok na profesionálnej úrovni si vyžaduje určité školenie, ktoré je založené na zručnostiach práce s textom a grafikou, ako aj na schopnosti programovať.

Téma „Logika“ zvyčajne spôsobuje medzi študentmi určitý zmätok, nie každý chápe dôležitosť štúdia tejto témy. Chcel by som poznamenať, že znalosť logiky je dôležitá nielen ako základ pre ďalšie štúdium programovacích jazykov a princípov práce s databázami, ale aj ako „simulátor“ pre rozvoj špeciálneho typu myslenia. Osoba, ktorá vyniká v štúdiu logiky, má obrovské výhody v komunikácii. Je veľmi lichotivé počuť na vašu adresu: „Je to logické“, „vo vašej úvahe je logika“.

Vyučovacia hodina informatiky je určená pre žiakov 10. ročníka všeobecnovzdelávacej školy, ktorej učebný plán obsahuje časť „Algebra logiky“. Táto téma je pre žiakov veľmi náročná, preto som ich ako pedagóg chcel zaujať štúdiom logických zákonov, zjednodušovaním logických výrazov a so záujmom pristupovať k riešeniu logických úloh. V bežnej forme je vyučovanie na túto tému únavné a problematické a niektoré definície nie sú deťom vždy jasné. V súvislosti s poskytovaním informačného priestoru som mal možnosť uverejňovať svoje lekcie v „learning“ shell. Študenti, ktorí sa doň zapíšu, môžu tento kurz navštevovať vo svojom voľnom čase a znovu si prečítať to, čo im na hodine nebolo jasné. Niektorí žiaci, ktorí majú vymeškané hodiny pre chorobu, si vymeškanú tému dopĺňajú doma alebo v škole a sú vždy pripravení na ďalšiu hodinu. Táto forma vyučovania mnohým deťom veľmi vyhovovala a tie zákony, ktoré boli pre ne nepochopiteľné, sa dnes učia počítačovou formou oveľa jednoduchšie a rýchlejšie. Ponúkam jednu z týchto hodín informatiky, ktorá prebieha integrovane s IKT.

Plán lekcie

Vysvetlenie nového materiálu, so zapojením počítača - 25 minút.
Základné pojmy a definície uvedené v "učení" - 10 minút.
Materiál pre zvedavcov - 5 minút.
Domáca úloha - 5 minút.

1. Vysvetlenie nového materiálu

Zákony formálnej logiky

Najjednoduchšie a najnutnejšie skutočné súvislosti medzi myšlienkami sú vyjadrené v základných zákonoch formálnej logiky. Sú to zákony identity, neprotirečenia, vylúčeného stredného, dostatočného dôvodu.

Tieto zákony sú zásadné, pretože v logike zohrávajú obzvlášť dôležitú úlohu, sú najvšeobecnejšie. Umožňujú vám zjednodušiť logické výrazy a vytvárať závery a dôkazy. Prvé tri z vyššie uvedených zákonov identifikoval a sformuloval Aristoteles a zákon dostatočného rozumu - G. Leibniz.

Zákon identity: v procese určitého uvažovania musí byť každý pojem a úsudok identický sám so sebou.

Zákon neprotirečenia: nie je možné, aby jedno a to isté oko súčasne bolo a nebolo inherentné tej istej veci v rovnakom ohľade. To znamená, že nie je možné súčasne niečo potvrdiť a poprieť.

Zákon vylúčeného stredu: z dvoch protichodných výrokov je jeden pravdivý, druhý nepravdivý a tretí nie je daný.

Zákon dostatočného dôvodu: Každá skutočná myšlienka musí byť dostatočne odôvodnená.

Posledný zákon hovorí, že dôkaz niečoho predpokladá opodstatnenie práve a len pravdivých myšlienok. Falošné myšlienky sa nedajú dokázať. Jedno dobré latinské príslovie hovorí: „Mýliť sa je spoločné pre každého človeka, ale len hlupák môže trvať na omyle.“ Pre tento zákon neexistuje žiadny vzorec, keďže má len vecný charakter. Ako argumenty na potvrdenie pravdivej myšlienky možno použiť pravdivé úsudky, faktický materiál, štatistické údaje, vedecké zákony, axiómy, overené vety.

Zákony výrokovej algebry

Algebra výrokov (algebra logiky) je časť matematickej logiky, ktorá študuje logické operácie s výrokmi a pravidlá pre transformáciu zložitých výrokov.

Pri riešení mnohých logických problémov je často potrebné zjednodušiť vzorce získané formalizáciou ich podmienok. Zjednodušenie vzorcov v algebre výrokov sa uskutočňuje na základe ekvivalentných transformácií založených na základných logických zákonoch.

Zákony algebry výrokov (algebra logiky) sú tautológie.

Niekedy sa tieto zákony nazývajú teorémy.

Vo výrokovej algebre sú logické zákony vyjadrené ako rovnosť ekvivalentných vzorcov. Medzi zákonmi sa rozlišujú najmä tie, ktoré obsahujú jednu premennú.

Prvé štyri z nasledujúcich zákonov sú základnými zákonmi výrokovej algebry.

Zákon o identite:

Každý pojem a úsudok je identický sám so sebou.

Zákon identity znamená, že v procese uvažovania nemožno nahradiť jednu myšlienku druhou, jeden pojem druhým. Ak dôjde k porušeniu tohto zákona, sú možné logické chyby.

Napríklad diskusia Správne hovoria, že jazyk ťa privedie do Kyjeva, ale včera som si kúpil údený jazyk, čo znamená, že teraz môžem bezpečne ísť do Kyjeva nesprávne, pretože prvé a druhé slovo „jazyk“ označujú rôzne pojmy.

V diskusii: Pohyb je večný. Chodiť do školy je pohyb. Chodenie do školy je preto navždy slovo "pohyb" sa používa v dvoch rôznych významoch (prvý - vo filozofickom zmysle - ako atribút hmoty, druhý - v bežnom zmysle - ako pohyb v priestore), čo vedie k nesprávnemu záveru.

Zákon neprotirečenia:

Výrok a jeho negácia nemôžu byť pravdivé súčasne. To znamená, že ak vyhlásenie ALE je pravda, potom jej negácia nie A musí byť nepravdivé (a naopak). Potom bude ich produkt vždy falošný.

Práve táto rovnosť sa často používa pri zjednodušovaní zložitých logických výrazov.

Niekedy je tento zákon formulovaný takto: dve tvrdenia, ktoré si odporujú, nemôžu byť súčasne pravdivé. Príklady nedodržania zákona o neprotirečení:

1. Na Marse je život a na Marse nie je život.

2. Olya vyštudovala strednú školu a je v 10. ročníku.

Zákon vylúčeného stredu:

Zároveň môže byť výrok pravdivý alebo nepravdivý, neexistuje žiadne tretie. Pravda buď ALE, alebo nie A. Príklady implementácie zákona vylúčeného stredu:

1. Číslo 12345 je buď párne alebo nepárne, žiadne tretie neexistuje.

2. Spoločnosť hospodári so stratou alebo ziskom.

3. Táto kvapalina môže alebo nemusí byť kyselina.

Zákon vylúčeného stredu nie je zákonom uznávaným všetkými logikmi ako univerzálny zákon logiky. Tento zákon sa uplatňuje tam, kde sa znalosti zaoberajú rigidnou situáciou: "buď - alebo", "pravda-nepravda". Tam, kde existuje neistota (napríklad v uvažovaní o budúcnosti), sa často nedá uplatniť právo vylúčeného stredu.

Zvážte nasledujúce vyhlásenie: Tento návrh je nepravdivý. Nemôže to byť pravda, pretože tvrdí, že je nepravdivá. Ale ani to nemôže byť nepravdivé, lebo potom by to bola pravda. Toto tvrdenie nie je pravdivé ani nepravdivé, a preto je porušený zákon vylúčeného stredu.

Paradox(grécky paradoxos - neočakávaný, zvláštny) v tomto príklade vyplýva zo skutočnosti, že veta odkazuje na seba. Ďalším známym paradoxom je kadernícky problém: V jednom meste kaderník ostrihá vlasy všetkých obyvateľov, okrem tých, ktorí si strihajú vlasy sami. Kto strihá holičovi vlasy? V logike nie je možné pre svoju formálnosť získať formu takéhoto odkazujúceho vyhlásenia. To opäť potvrdzuje myšlienku, že pomocou algebry logiky nie je možné vyjadriť všetky možné myšlienky a argumenty. Ukážme si, ako možno na základe definície výrokovej ekvivalencie získať zvyšok zákonov výrokovej algebry.

Napríklad definujme, čo je ekvivalentné (ekvivalentné) ALE(dvakrát nie ALE, teda negácia negácie ALE). Aby sme to dosiahli, vytvoríme pravdivú tabuľku:

Podľa definície ekvivalencie musíme nájsť stĺpec, ktorého hodnoty sa zhodujú s hodnotami stĺpca ALE. Toto bude stĺpec ALE.

Môžeme teda formulovať dvojité právonegácie:

Ak niektoré tvrdenie negujeme dvakrát, výsledkom je pôvodný výrok. Napríklad vyhlásenie ALE= Matroskin- kat je ekvivalentné povedať A = Nie je pravda, že Matroskin nie je mačka.

Podobne možno odvodiť a overiť nasledujúce zákony:

Konštantné vlastnosti:

Zákony idempotencie:

Bez ohľadu na to, koľkokrát opakujeme: TV zapnutá alebo TV zapnutá alebo TV zapnutá... význam vety sa nezmení. Rovnako z opakovania Vonku je teplo, vonku je teplo... nie o jeden stupeň teplejšie.

Zákony komutácie:

A v B = B v A

A a B = B a A

operandy ALE a AT v operáciách disjunkcie a konjunkcie možno zameniť.

Zákony asociatívnosti:

Av(BvC) = (AvB) vC;

A & (B & C) = (A & B) & C.

Ak výraz používa iba operáciu disjunkcie alebo iba operáciu spojenia, potom môžete zátvorky zanedbať alebo ich usporiadať ľubovoľne.

Zákony distribúcie:

A v (B & C) = (A v B) & (A v C)

(distributívna disjunkcia
ohľadom konjunkcie)

A & (B v C) = (A & B) v (A & C)

(distributívnosť konjunkcie
ohľadom disjunkcie)

Distributívny zákon konjunkcie vzhľadom na disjunkciu je podobný distributívnemu zákonu v algebre, ale zákon distributívnej disjunkcie vzhľadom na konjunkciu nemá analógiu, platí len v logike. Preto to treba dokázať. Dôkaz sa najlepšie vykoná pomocou pravdivostnej tabuľky:

Absorpčné zákony:

Av (A & B) = A

A & (A v B) = A

Vykonajte dôkaz o absorpčných zákonoch sami.

De Morganove zákony:

Slovné formulácie de Morganových zákonov:

Mnemotechnické pravidlo: na ľavej strane identity stojí nad celým výrokom operácia negácie. Na pravej strane sa zdá, že je rozbitá a nad každým z jednoduchých výrokov stojí negácia, no zároveň sa mení operácia: disjunkcia na konjunkciu a naopak.

Príklady implementácie de Morganovho zákona:

1) Vyhlásenie Nie je pravda, že viem arabsky alebo čínsky je totožné s výrokom Neviem po arabsky a neviem po čínsky.

2) Vyhlásenie Nie je pravda, že som sa poučil a dostal z toho D je totožné s výrokom Buď som sa nenaučil lekciu, alebo som z toho nedostal A.

Nahradenie operácií implikácie a ekvivalencie

Operácie implikácie a ekvivalencie niekedy nepatria medzi logické operácie konkrétneho počítača alebo kompilátora z programovacieho jazyka. Tieto operácie sú však potrebné na riešenie mnohých problémov. Existujú pravidlá na nahradenie týchto operácií postupnosťami operácií negácie, disjunkcie a konjunkcie.

Takže vymeňte prevádzku dôsledky možné podľa nasledujúceho pravidla:

Ak chcete nahradiť operáciu rovnocennosť existujú dve pravidlá:

Je ľahké overiť platnosť týchto vzorcov zostrojením pravdivostných tabuliek pre pravú a ľavú stranu oboch identít.

Znalosť pravidiel nahrádzania operácií implikácie a ekvivalencie pomáha napríklad správne zostrojiť negáciu implikácie.

Zvážte nasledujúci príklad.

Nech je uvedené vyhlásenie:

E = Nie je pravda, že ak vyhrám súťaž, dostanem cenu.

Nechaj ALE= Vyhrám súťaž

B = dostanem cenu.

Preto E = vyhrám súťaž, ale nedostanem cenu.

Nasledujúce pravidlá sú tiež zaujímavé:

Ich platnosť môžete dokázať aj pomocou pravdivostných tabuliek.

Zaujímavý je ich prejav v prirodzenom jazyku.

Napríklad fráza

Ak Macko Pú jedol med, je sýty

je totožné s frázou

Ak Macko Pú nie je sýty, potom nejedol med.

Cvičenie: premýšľajte o frázach-príkladoch o týchto pravidlách.

2. Základné pojmy a definície v prílohe 1

3. Materiál pre zvedavcov v prílohe 2

4. Domáce úlohy

1) Naučte sa zákony logiky pomocou kurzu Algebra logiky, ktorý sa nachádza v informačnom priestore (www.learning.9151394.ru).

2) Skontrolujte dôkaz De Morganových zákonov na PC vytvorením pravdivostnej tabuľky.

Aplikácie

Základné pojmy a definície (

§štyri. Ekvivalentné, TI a TL vzorce algebry logiky. Základné ekvivalencie. (Zákony logických operácií). Zákon duality.

Definícia.

Dva vzorce algebry logiky A a B sa nazývajú EKVIVALENTNÉ, ak majú rovnaké logické hodnoty na ľubovoľnom súbore základných výrokov zahrnutých vo vzorcoch. Ekvivalenciu vzorcov označíme znamienkom º a označenie A ºB znamená, že vzorce A a B sú ekvivalentné.

Vzorec A sa nazýva IDENTICKY PRAVDIVÝ (alebo TAUTOLOGICKÝ), ak má hodnotu 1 pre všetky hodnoty premenných, ktoré sú v ňom obsiahnuté.

Vzorec sa nazýva IDENTICKY NEPRAVDIVÝ (alebo ROZPOR), ak má hodnotu 0 pre všetky hodnoty premenných, ktoré obsahuje.

Medzi pojmami ekvivalencie a ekvivalencie existuje nasledujúca súvislosť: ak sú formuly A a B ekvivalentné, potom vzorec A“B je tautológia a naopak, ak je vzorec A“B tautológia, potom formule A a B sú ekvivalentné.

Najdôležitejšie ekvivalencie algebry logiky možno rozdeliť do troch skupín.

1. Základné ekvivalencie.

Zákony idempotencie.

Zákon protirečenia

Zákon vylúčeného stredu

dvojitý negatívny zákon

absorpčné zákony

2. Ekvivalencie vyjadrujúce niektoré logické operácie z hľadiska iných.

Tu sú 3, 4, 5, 6 Morganove zákony.

Je jasné, že ekvivalencie 5 a 6 získame z ekvivalencie 3 a 4, ak vezmeme negácie z oboch častí druhej a použijeme zákon o odstránení dvojitých negácií.

Prvé štyri ekvivalencie teda potrebujú dôkaz. Dokážme jeden z nich: ten prvý.

Keďže pre rovnaké logické hodnoty x a y sú vzorce pravdivé https://pandia.ru/text/78/396/images/image018.gif" width="124" height="21">. Preto v v tomto prípade majú obe časti ekvivalencie rovnakú skutočnú hodnotu.

Nech majú teraz x a y rôzne logické hodnoty. Potom ekvivalencia a jedna z dvoch implikácií alebo budú nepravdivé. Ale zároveň bude spojenie aj nepravdivé. .

V tomto prípade teda majú obe časti ekvivalencie rovnaký logický význam.

Ekvivalencie 2 a 4 sú dokázané podobne.

Z ekvivalencií tejto skupiny vyplýva, že každý vzorec algebry logiky môže byť nahradený formulou jemu ekvivalentnou, obsahujúcou iba dve logické operácie: konjunkciu a negáciu alebo disjunkciu a negáciu.

Ďalšie vylúčenie logických operácií nie je možné. Ak teda použijeme iba spojku, potom taký vzorec ako negáciu nemožno vyjadriť pomocou operácie spojky.

Existujú však operácie, ktorými možno vyjadriť ktorúkoľvek z piatich logických operácií, ktoré používame. Takouto operáciou je napríklad operácia „Schaefferova mŕtvica“. Táto operácia je označená symbolom ½ left " style="border-collapse:collapse;border:none;margin-left:6.75pt;margin-right: 6.75pt">

Moderné počítače založené na "starodávnych" elektronických počítačoch sú založené na určitých postulátoch ako základných princípoch fungovania. Nazývajú sa zákony algebry logiky. Prvýkrát takúto disciplínu opísal (samozrejme nie tak podrobne ako v jej modernej podobe) starogrécky vedec Aristoteles.

Algebra logiky, ktorá predstavuje samostatnú oblasť matematiky, v rámci ktorej sa študuje výrokový počet, má množstvo dobre definovaných záverov a záverov.

Aby sme lepšie porozumeli téme, analyzujeme pojmy, ktoré v budúcnosti pomôžu naučiť sa zákony algebry logiky.

Možno je hlavným pojmom v skúmanej disciplíne vyhlásenie. Toto je tvrdenie, ktoré nemôže byť zároveň nepravdivé aj pravdivé. Vždy má len jednu z týchto vlastností. Zároveň je konvenčne akceptované dávať hodnotu 1 pravde, 0 nepravdivosti a nazývať samotný výrok nejakým druhom A, B, C. Inými slovami, vzorec A=1 znamená, že výrok A je pravda. S výrazmi sa dá narábať rôznymi spôsobmi. Stručne zvážime akcie, ktoré s nimi možno vykonať. Všimnite si tiež, že zákony algebry logiky nemožno zvládnuť bez znalosti týchto pravidiel.

1. Disjunkcia dva výroky – výsledok operácie „alebo“. Môže byť buď nepravdivý alebo pravdivý. Používa sa znak „v“.

2. Konjunkcia. Výsledok takejto akcie vykonanej s dvoma výrokmi bude nový iba vtedy, ak sú pravdivé oba pôvodné výroky. Používa sa operácia "and", symbol "^".

3. Implikácia. Operácia „ak A, tak B“. Výsledkom je tvrdenie, ktoré je nepravdivé iba vtedy, ak je pravda A a nepravda B. Používa sa symbol „->“.

4. Ekvivalencia. Operácia „A vtedy a len vtedy, keď B keď“. Toto tvrdenie je pravdivé, ak majú obe premenné rovnakú hodnotu. symbol "<->».

Existuje aj množstvo operácií, ktoré sa približujú implikácii, ale v tomto článku sa nimi nebudeme zaoberať.

Teraz sa pozrime bližšie na základné zákony algebry logiky:

1. Komutatívny alebo komutatívny uvádza, že zmena miesta logických pojmov v operáciách spojky alebo disjunkcie neovplyvní výsledok.

2. Asociatívne alebo asociatívne. Podľa tohto zákona možno premenné v operáciách konjunkcie alebo disjunkcie spájať do skupín.

3. Distribúcia alebo distribúcia. Podstatou zákona je, že rovnaké premenné v rovniciach môžu byť vyňaté zo zátvoriek bez zmeny logiky.

4. De Morganov zákon (inverzia alebo negácia). Negácia operácie konjunkcie je ekvivalentná disjunkcii negácie pôvodných premenných. Negácia disjunkcie sa zasa rovná konjunkcii negácie tých istých premenných.

5. Dvojitá negácia. Negácia určitého tvrdenia dvakrát vedie k pôvodnému tvrdeniu, trikrát - jeho negácia.

6. Zákon idempotencie vyzerá pre logické sčítanie takto: x v x v x v x = x; pre násobenie: x^x^x^=x.

7. Zákon o neprotirečení hovorí: dva výroky, ak si protirečia, nemôžu byť súčasne pravdivé.

8. Zákon o vylúčení tretieho. Spomedzi dvoch protichodných tvrdení je jedno vždy pravdivé, druhé nepravdivé, tretie nie je dané.

9. Zákon absorpcie možno pre logické sčítanie zapísať takto: x v (x ^ y) = x, pre násobenie: x ^ (x v y) = x.

10. Zákon lepenia. Dve susedné konjunkcie sa môžu zlepiť a vytvoriť konjunkciu nižšej úrovne. V tomto prípade zaniká premenná, ktorou boli zlepené pôvodné spojky. Príklad logického sčítania:

(x^y) v (-x^y)=y.

Uvažovali sme len o najpoužívanejších zákonoch algebry logiky, ktorých môže byť v skutočnosti oveľa viac, pretože logické rovnice často nadobúdajú dlhú a ozdobnú formu, ktorá sa dá zredukovať použitím množstva podobných zákonov.

Na uľahčenie počítania a identifikácie výsledkov sa spravidla používajú špeciálne tabuľky. Všetky existujúce zákony algebry logiky, ktorých tabuľka má všeobecnú štruktúru mriežkového obdĺžnika, sú namaľované, pričom každá premenná je rozdelená do samostatnej bunky. Čím väčšia je rovnica, tým ľahšie sa s ňou pracuje pomocou tabuliek.

Zákony výrokovej algebry

Algebra výrokov (algebra logiky) je časť matematickej logiky, ktorá študuje logické operácie s výrokmi a pravidlá pre transformáciu zložitých výrokov.

Zákony výrokovej algebry (algebra logiky) sú tautológie.

Niekedy sa tieto zákony nazývajú teorémy.

Vo výrokovej algebre sú logické zákony vyjadrené ako rovnosť ekvivalentných vzorcov. Medzi zákonmi sa rozlišujú najmä tie, ktoré obsahujú jednu premennú.

Prvé štyri z nasledujúcich zákonov sú základnými zákonmi výrokovej algebry.

Zákon o identite:

A = A

Každý pojem a úsudok je identický sám so sebou.

Zákon identity znamená, že v procese uvažovania nemožno nahradiť jednu myšlienku druhou, jeden pojem druhým. Ak dôjde k porušeniu tohto zákona, sú možné logické chyby.

Napríklad uvažovanie Správne hovorí, že jazyk vás privedie do Kyjeva, ale včera som si kúpil fajčiarsky jazyk, čo znamená, že teraz môžem bezpečne ísť do Kyjeva nesprávne, pretože prvé a druhé slovo „jazyk“ označuje rôzne pojmy.

V uvažovaní: Pohyb je večný. Chodiť do školy je pohyb. Preto sa slovo „pohyb“ používa navždy v dvoch rôznych významoch (prvý - vo filozofickom zmysle - ako atribút hmoty, druhý - v bežnom zmysle - ako pohyb v priestore), ktorý vedie k nesprávnemu záveru.

Zákon neprotirečenia :

Zároveň môže byť výrok pravdivý alebo nepravdivý, neexistuje žiadne tretie. Buď A je pravdivé alebo nie A. Príklady implementácie zákona vylúčeného stredu:

1. Číslo 12345 je buď párne alebo nepárne, tretie sa neuvádza.

2. Spoločnosť hospodári so stratou alebo rentabilitou.

3. Táto kvapalina môže alebo nemusí byť kyselina.

Zákon vylúčeného stredu nie je zákonom uznávaným všetkými logikmi ako univerzálny zákon logiky. Tento zákon platí tam, kde sa poznanie zaoberá rigidnou situáciou: „buď-alebo“, „pravda-nepravda“. Tam, kde existuje neistota (napríklad v uvažovaní o budúcnosti), sa často nedá uplatniť právo vylúčeného stredu.

Zvážte nasledujúce tvrdenie: Táto veta je nepravdivá. Nemôže to byť pravda, pretože tvrdí, že je nepravdivá. Ale ani to nemôže byť nepravdivé, lebo potom by to bola pravda. Toto tvrdenie nie je pravdivé ani nepravdivé, a preto je porušený zákon vylúčeného stredu.

Paradox (grécky paradoxos - neočakávaný, zvláštny) v tomto príklade vyplýva zo skutočnosti, že veta odkazuje na seba. Ďalším známym paradoxom je holičský problém: V jednom meste holič ostrihá vlasy všetkých obyvateľov, okrem tých, ktorí si strihajú vlasy sami. Kto strihá holičovi vlasy? V logike nie je možné pre svoju formálnosť získať formu takéhoto odkazujúceho vyhlásenia. To opäť potvrdzuje myšlienku, že pomocou algebry logiky nie je možné vyjadriť všetky možné myšlienky a argumenty. Ukážme si, ako možno na základe definície výrokovej ekvivalencie získať zvyšok zákonov výrokovej algebry.

Napríklad určme, čo je ekvivalent (ekvivalent) A (dvojitá negácia A, t. j. negácia negácie A). Aby sme to urobili, zostavíme pravdivostnú tabuľku:

Podľa definície ekvivalencie musíme nájsť stĺpec, ktorého hodnoty sa zhodujú s hodnotami stĺpca A. Toto bude stĺpec A.

Môžeme teda formulovať zákon dvojitej negácie:

Ak niektoré tvrdenie negujeme dvakrát, výsledkom je pôvodný výrok. Napríklad vyhlásenie A = Matroskin - kat je ekvivalentné A = Nie je pravda, že Matroskin nie je mačka.

Podobne možno odvodiť a overiť nasledujúce zákony:

Konštantné vlastnosti:

Zákony idempotencie:

Bez ohľadu na to, koľkokrát opakujeme: televízor je zapnutý alebo televízor je zapnutý alebo televízor je zapnutý... význam výroku sa nezmení. Podobne z opakovania je vonku teplo, vonku je teplo, ... o stupeň teplejšie nebude.

Zákony komutácie:

A v B = B v A

A a B = B a A

Operandy A a B v operáciách disjunkcie a konjunkcie možno zameniť.

Zákony asociatívnosti:

Av(BvC) = (AvB) vC;

A & (B & C) = (A & B) & C.

Ak výraz používa iba operáciu disjunkcie alebo iba operáciu spojenia, potom môžete zátvorky zanedbať alebo ich usporiadať ľubovoľne.

Zákony distribúcie:

A v (B & C) = (A v B) & (A v C)

(distributívna disjunkcia
ohľadom konjunkcie)

A & (B v C) = (A & B) v (A & C)

(distributívnosť konjunkcie
ohľadom disjunkcie)

Absorpčné zákony:

Av (A & B) = A

A & (A v B) = A

Vykonajte dôkaz o absorpčných zákonoch sami.

De Morganove zákony:

Slovné formulácie de Morganových zákonov:

Mnemotechnické pravidlo: na ľavej strane identity je operácia negácie nad celým vyhlásením. Na pravej strane sa zdá, že je rozbitá a nad každým z jednoduchých výrokov stojí negácia, no zároveň sa mení operácia: disjunkcia na konjunkciu a naopak.

Príklady implementácie de Morganovho zákona:

1) Výrok Nie je pravda, že viem po arabsky alebo po čínsky je totožný s výrokom neviem po arabsky a neviem po čínsky.

2) Výrok Nie je pravda, že som sa naučil lekciu a dostal som za to dvojku, je zhodný s výrokom Buď som sa lekciu nenaučil, alebo som za to nedostal dvojku.

Nahradenie operácií implikácie a ekvivalencie

Operáciu implikácie teda môžete nahradiť v súlade s nasledujúcim pravidlom:

Existujú dve pravidlá nahradenia operácie ekvivalencie:

Je ľahké overiť platnosť týchto vzorcov zostrojením pravdivostných tabuliek pre pravú a ľavú stranu oboch identít.

Znalosť pravidiel nahrádzania operácií implikácie a ekvivalencie pomáha napríklad správne zostrojiť negáciu implikácie.

Zvážte nasledujúci príklad.

Nech je uvedené vyhlásenie:

E = Nie je pravda, že ak vyhrám súťaž, dostanem cenu.

Nechaj A = Vyhrám súťaž,

B = dostanem cenu.

Potom

Odtiaľ, E = Vyhrám súťaž, ale nedostanem cenu.