cunoștințe teoretice generale
Conceptele de bază ale algebrei logicii
O bază logică pentru calculator este algebra logicii, care consideră operațiile logice pe propuneri.
logica algebra - o ramură a matematicii care studiază enunțului, văzută din partea valoare logică (adevărat sau fals) și operații logice pe ele.
Declarație logică - este orice propoziție declarativă pentru care se poate spune dacă este adevărat sau fals.
Exemplu. „3 - număr prim“ este o propunere, pentru că este adevărat.
Nu fiecare propoziție este o afirmație logică.
Exemplu. propoziția „Să mergem la film“ nu este o declarație. Exemple interogativ și imperative nu sunt declarații.
forma propozitionala - o propoziție declarativă, care este fie direct, fie indirect, conține cel puțin o variabilă și devine o declarație atunci când toate variabilele sunt înlocuite cu valorile lor.
Exemplu. «X + 2> 5" - formă propozițională care pentru x> 3 este adevărat, altfel false.
algebra logicii luând în considerare orice declarație cu un singur punct de vedere - dacă este adevărat sau fals. Cuvintele și expresiile „nu“, „și“, „sau“ „în cazul în care. apoi „“ dacă și numai dacă „și alții lasă în declarații deja dat pentru a construi o nouă expresie. Aceste cuvinte și expresii sunt numite conector logic.
Enunțuri formate din alte declarații conector logic, numit compozit (complex). Declarațiile care nu sunt componente numite elementare (simplu).
Exemplu. spunând că „Numărul 6 este împărțit în 2“ - o simplă declarație. A spune „Numărul 6 este divizibil cu 2 și 6 împărțit la numărul de 3„- compozit enunț format din două corzi simple, prin logică“și".
Adevărul sau falsitatea enunțuri compozit depinde de adevărul sau falsitatea declarațiilor elementare din care sunt compuse.
Pentru a avea acces la declarațiile logice, acestea sunt atribuite nume.
Exemplu. Notăm cu o simplă declarație „numărul 6 este divizibil cu 2“, iar prin simpla declarație în „numărul 6 împărțit la 3“. Apoi declarația compus „Numărul 6 este divizibil cu 2, iar numărul 6 este împărțit în 3“ poate fi scris ca „A și B“. Aici, „i“ - conectiv logic, A, B - variabilă logică, care poate presupune doar două valori - „true“ sau „false“, desemnate respectiv „1“ și „0“.
Fiecare pachet este văzut ca o operațiune logică pe declarațiile logice și are numele său propriu și denumirea (tabelul. 1).
Tabelul 1. operații booleene
NU operațiune este exprimat prin cuvântul „nu“ este numit negare și notat printr-o bară peste declarația (sau semnul). O afirmație este adevărată, atunci când A este fals, și fals atunci când A este adevărat.
Exemplu. Fie A = „Astăzi este tulbure“, atunci A = „Astăzi nu este acoperit de nori.“
Și Operațiunea, și-a exprimat buchet „și“ numit conjuncție (lat conjunctio -. Compus) sau multiplicare logică, și este notat punctul «•» (poate, de asemenea, semne să fie menționate sau ). • Propoziția A este adevărată dacă și numai dacă ambele propuneri A și B sunt adevărate.
Exemplu. Spunând „Numărul 6 este divizibil cu 2 și 6 împărțit la numărul de 3„- adevărat sau declarația“Numărul 6 este împărțit în două, iar numărul este mai mare de 10 6' - fals.
Sau operațiuni, și-a exprimat ciorchine „sau“ (într-un sens neexclusiv al cuvântului), se numește disjuncție (disjunctio Latină -. Divizia) sau o completare logică și notată cu simbolul
(Sau plus). Propoziția A este falsă dacă și numai dacă ambele propuneri A și B sunt false.
Exemplu: Declarația „Numărul 6 este divizibil cu 2 sau mai mult de 10 numărul 6„- adevărat sau mențiunea“numărul 6, împărțit la numărul 5 sau 6 mai mult de 10" - fals.
DACĂ ... ATUNCI operație, și-a exprimat mănunchiuri „dacă ... atunci“, „ar trebui să fie de ...““. atrage după sine ... „numit implicația (implico latină -. sunt strâns legate), și notată cu simbolul →. Spunând A → B este falsă dacă și numai dacă A este adevărat și B este fals.
Exemplu. Spunând „în cazul în care studentul a trecut toate examenele ca fiind“ excelent „el va primi o bursă.“ Evident, implicația ar trebui să fie recunoscută ca fiind falsă numai în cazul în care studentul a trecut la „excelent“ toate examenele, dar nu au primit bursa. În alte cazuri, atunci când nu toate examenele puse pe „excelent“ și este primit bursa (de exemplu, datorită faptului că studentul trăiește în familiile cu venituri mici) sau în cazul în care examenele nu pun și bursa se poate pune problema, implicația pot fi considerate adevărate.
Operațiunea este echivalentă, exprimată mănunchiuri „dacă și numai dacă“, „necesare și suficiente“.“ echivalent ...“, numită echivalență sau dublă implicație și notată cu simbolul ↔ sau
A↔V propoziția este adevărată dacă și numai dacă valorile A și B coincid.
Exemplu: Declarația „este un număr, chiar dacă și numai dacă este divizibil cu 2“ este adevărată, iar afirmația „este un număr impar, dacă și numai dacă este divizibil cu 2“ - fals.
Sau ... sau operație, și-a exprimat corduri „fie ... sau“ se numește SAU exclusiv sau modulo 2 și este desemnat sau XOR. Propoziția A este adevărată dacă și numai dacă valoarea A și B nu coincid.
Exemplu. Spunând „Numărul 6 sau impar sau divizibil cu 2“ este adevărat, și declarația „fie numărul 6 sau chiar numărul 6 împărțit la 3“ - este fals la fel de adevărat atât declarațiilor incluse în ea.
Notă. Implicația poate fi exprimată în termeni de disjuncție și negație:
.
Echivalența poate fi exprimată în termeni de negație, conjuncție și disjuncție:
.
XOR poate fi exprimată în termeni de negație, conjuncție și disjuncție:
.
Concluzie. Operațiuni negație, conjuncție și disjuncție este suficient pentru a descrie și declarații logice de proces.
Procedura pentru efectuarea operațiunilor logice indicate în paranteze. Dar, pentru a reduce numărul de paranteze au fost de acord să-și asume faptul că prima operațiune este realizată negație ( „nu“), atunci conjunctia ( „și“), după coroborat - disjuncția ( „sau“), și XOR, iar ultimul lucru - implicarea și echivalența.
Utilizarea variabilelor logice și simboluri operații logice orice propoziție poate fi formalizată, adică pentru a înlocui formula logică (expresie logică).
Formula logică - este o exprimare notație simbolică, constând în valori logice (constante sau variabile), operațiile logice combinate (fascicule).
Funcția logică - o funcție de variabile logice care pot lua doar două valori: 0 sau 1. La rândul său, ea însăși o boolean (funcția argument logic), poate lua, de asemenea, doar două valori: 0 sau 1.
Exemplu. - funcția logică a două variabile A și B.
Funcții Boolean pentru diferite combinații ale variabilelor de intrare - sau cum este numit altfel, set de variabile de intrare - stabilit în mod normal, o masă specială. Un astfel de tabel este numit un tabel de adevăr.
Aici tabelul de adevăr de bază al operațiilor logice (tabelul. 2)
Bazat pe masa de adevăr poate fi adevăr date tabelul de operații logice de bază pentru formule mai complexe.
Un algoritm pentru construirea tabelelor de adevăr pentru expresii complexe:
1. Se determină numărul de rânduri:
• numărul de rânduri n + 2 = string la header,
• n - numărul de propoziții simple.
2. Se determină numărul de coloane:
• numărul de coloane = numărul de variabile + număr de operații logice;
• Se determină numărul de variabile (expresie simplă);
• operații logice pentru a determina numărul și secvența de execuție a acestora.
Exemplul 1. Crearea unui tabel de adevăr pentru formula NAND, care poate fi scris.
1. Se determină numărul de rânduri:
Două exprimare simplă de intrare A și B, prin urmare, n = 2 și numărul de linii = 2 2 + 1 = 5.
2. Se determină numărul de coloane:
Expresia este format din două expresii simple (A și B) și două operații logice (1 inversia conjunction 1), adică numărul de coloane din tabelul de adevăr = 4.
3. Se umple coloanele cu tabelele de adevăr ale operațiilor logice (Tabel. 3).
Tabelul 3. Tabelul de adevăr pentru operație logică
Notă: NAND este, de asemenea, numit „accident vascular cerebral Sheffer“ (notat |) sau „antikonyunktsiya“; Și nici nu este, de asemenea, numit „logic, nici“ (↓ notate) sau „antidizyunktsiya“.
Exemplul 2: Crearea unui tabel al expresiei logice este adevărată.
1. Se determină numărul de rânduri:
Două exprimare simplă de intrare A și B, prin urmare, n = 2 și numărul de linii = 2 2 + 1 = 5.
2. Se determină numărul de coloane:
Expresia este format din două expresii simple (A și B) și cinci operații logice (2 inversiuni 2 conjuncție, disjuncție 1), adică numărul de coloane din tabelul de adevăr = 7.
În primul rând, se realizează operația de inversare, apoi conjuncțiilor puțin funcționare disjuncție.
3. Se umple coloanele cu tabelele de adevăr ale operațiilor logice (Tabel. 5).
Tabelul 5. Tabelul de adevăr pentru operație logică
Formulele logice pot fi, de asemenea, prin intermediul limbajului logic.
Există trei elemente logice de bază, care implementează trei operații logice de bază:
• poarta "și" - multiplicare logică - conjunctor;
• Element logic "sau" - plus logică - disjunctors;
• Element logic „NU“ - inversiune - invertorul.
Deoarece orice operație logică poate fi reprezentat ca o combinație de trei, orice dispozitiv de calculator principal sau stocarea prelucrarea de generare a informației pot fi colectate din elementele logice de bază, atât „cărămizi“.
Elementele logice ale calculatorului operează cu semnale care reprezintă impulsuri electrice. Există puls - semnal de sens logic - 1, nu are puls - 0. Intrările de poarta NAND recepționează semnale valori argument, rezultatul este o funcție de valoare a semnalului.
semnal de poarta de conversie este dată de tabelul de stat, care este de fapt un tabel de adevăr corespunzătoare funcției logica este reprezentată numai sub formă de circuite logice. Într-o astfel de formă, care să reprezinte un lanț de operații logice și calcule pentru a le produce.