a) O disjuncție alternativă, deoarece se presupune o condiție a doi, dar nu ambele.
b) Disjuncția (deși dacă vorbitorul este "cinstit", atunci este posibilă o disjuncție alternativă).
c) Disjuncție alternativă.
Sunt declarații și formule la fel:
a) Dacă Pământul se ciocnește cu Soarele, atunci va ploua;
a) În mod identic, deoarece premisa este falsă și din minciună totul urmează.
b) Implicația este falsă în singurul caz în care adevărul rezultă dintr-o minciună. Dacă este adevărat, atunci P și Q iau valori de adevăr egale. Prin urmare, implicația este adevărată, iar implicația externă este aceeași. Dacă este falsă, atunci implicația externă este întotdeauna adevărată. Astfel, întreaga formulă este identică.
În alt mod, studiul poate fi realizat prin construirea unei tabele de adevăr pentru formula noastră. Constructul tabel de adevăr condensat (adică, pentru fiecare variabilă va aloca doar o singură coloană, în locul primei sale apariție în formulă, fiecare disjuncție - de asemenea, o coloană, folosind, astfel, a înregistrat formula ..):
Aici este o tabelă cu adevărat scurt pentru formula: în primul rând, sunt completate coloane de valori posibile ale lui P și Q. astfel de seturi vor fi; apoi coloanele pentru conectorii logici "interni" (echivalență și implicarea corectă) și, în final, coloana implicării externe (stânga), care dă valorile adevărului întregii formule. Cifrele de sub tabel arată ordinea umplerii coloanelor. Deoarece pe orice set de valori ale adevărului variabilelor, formula ia doar valoarea 1. atunci este identic adevărat.
c) Luați imediat în considerare tabelul de adevăr:
Deoarece formula poate lua ambele valori de adevăr (vedeți coloana selectată), nu este identică.
Pentru a crea tabele de adevăr pentru formule:
1.2. Simplificarea formulelor. Transformări identice.
Dovada echivalenței, identitatea
adevăr și falsitate de identitate
formule și funcții booleene
Rezumat al teoriei
Atunci când se folosește definiția formală a algebrei formulei logice, formularul de înregistrare conține adesea paranteze "extra", care pot fi neglijate fără a aduce atingere sensului, dacă aplicăm niște reguli general acceptate.
Mai întâi, în formule separate (sau dacă limitele formulei sunt clare din context), puteți omite parantezele exterioare.
În al doilea rând, cum ar fi aritmetica, ligamente și cuantificatorii pot fi sortate dupa „puterea“ lor, adică. E. aranjați într-o anumită ordine, cu excepția faptului că personajele sunt în această ordine sunt corecte, „se leagă mai puternic“, adică. E acestea ar trebui să fie efectuate în primul rând:
Astfel, disjuncția și conjuncția sunt mai puternice decât implicațiile, dar mai slabe decât negarea. Conjuncția este mai puternică decât disjuncția. Cea mai slabă relație este echivalența. Cuantificatorii sunt egali în raport cu legarea (acest lucru este discutat în detaliu în secțiunea 2), ele se leagă mai puternic decât orice conectivitate logică.
În comparație cu definiția generală a formulei formale a limbajului pentru formulele logicii propoziționale (în continuare simple formule), facem următoarele îmbunătățiri:
1) ca scrisori propoziționale (variabile individuale) vom lua în considerare doar simple declarații x, y. z ,. B. B = 1, 0>;
2) vom construi formule simple complexe numai cu ajutorul operațiunilor logice și parantezelor.
Prin această abordare, orice formulă va fi complet determinată de tabelul său de adevăr.
O funcție booleană (sau o funcție a algebrei logice, o funcție logică) este orice funcție a n variabilelor (n = 1. 2.) cu un domeniu de definiție al cărui set de valori este conținut în B.
Orice funcție booleană poate fi în mod evident specificată printr-un tabel de adevăr exact același tip cu tabelele care sunt mapate la formule. Dacă tabelul de adevăr specificând funcția booleană f. coincide cu tabelul de adevăr al unei anumite formule Φ. atunci se spune că formula Φ reprezintă (sau definește sau realizează) o funcție f.
Două formule Φ și se spune că sunt echivalente (care este notat cu Φ) dacă reprezintă aceeași funcție booleană.
Pentru oricare două formule, nu există nici o dificultate în a verifica dacă ele sunt echivalente: este suficient să comparăm tabelele lor de adevăr.
Funcțiile booleene (din orice număr de variabile) care iau valoarea 1 indiferent de valorile argumentelor sunt numite (ca și formulele de realizare) tautologii (sau identice adevărate).
Funcțiile booleene (și realizarea formulelor lor), luând întotdeauna valoarea 0. se numesc contradicții (sau identice false).
Puteți verifica identitatea sau identitatea unei anumite formule prin același tabel de adevăr (coloana rezultată a tabelului va conține numai constanta corespunzătoare).
O altă modalitate de a demonstra echivalența formulelor sau de a verifica adevărul sau falsitatea lor identică este să folosiți așa-numitele legi logice de bază (echivalențe de bază), justificarea cărora se poate face prin construirea tabelelor de adevăruri corespunzătoare. Următoarele relații se referă de obicei la legile logice de bază:
Rezultatele calculelor tabelelor de adevăr ale ambelor părți ale echivalentelor nu depind de modul în care valorile variabilelor incluse în aceste relații, t. E. Contează dacă aceste variabile sunt independente sau, la rândul său, obținut ca rezultat al oricăror calcule. Prin urmare, echivalențele de mai sus rămân valabile atunci când înlocuim orice variabilă cu orice funcție logică și, prin urmare, orice formule care reprezintă aceste funcții. Este important să se respecte următoarea regulă pentru înlocuirea unei formule pentru o variabilă. atunci când formula Φ este înlocuită cu variabila x, toate aparițiile variabilei x în raportul original trebuie înlocuite simultan cu formula Φ.
În fiecare algebră (inclusiv algebra booleană a funcțiilor) relația
ФФ înseamnă că formulele Ф și Φ descriu aceeași funcție booleană f. Prin urmare, dacă o formulă Φ conține Φβ ca subformula, atunci schimbarea Φη nu schimbă elementul algebricii booleene f. peste care operațiile sunt efectuate în formula Φ; Prin urmare Φ ', obținut din Φ printr-o astfel de substituție, este echivalent cu Φ. Această afirmație este o regulă pentru înlocuirea subformulelor. ceea ce face posibilă obținerea unor formule echivalente cu una dată, în conformitate cu echivalențele disponibile.
Observați diferența dintre regulile substituției și substituției. Atunci când este substituită, variabila este înlocuită cu formula; formula poate fi orice. dar este necesar să o înlocuiască pentru toate aparițiile variabilei. Înlocuind subformulele, orice subformula este înlocuită, dar nu de oricare alta, ci numai de echivalentul acesteia. În acest caz, înlocuirea tuturor aparițiilor subformulei originale nu este necesară.
Să presupunem că există o echivalență a ΦΦ, unde Φ și Φ conțin variabila x. Dacă în loc de toate aparițiile lui x în Φ, Φ substituiți o formulă arbitrară Φ. atunci obținem noi formule Φ 'și Φ', și nu neapărat ΦΦ 'și ΦΦ'; Cu toate acestea, noile formule sunt echivalente unul cu altul: Φ 'Φ'. Dacă înlocuim subformula cu o formulă echivalentă cu aceasta, obținem o nouă formulă Φ '. care este echivalent cu F.
Astfel de transformări, echivalență folosind formule (de stoc, care poate fi extins prin normele de substituție) și reguli de substituție, numite transformări identitare. transformări identice sunt dovezi puternice de echivalență formule identice și adevăr sau falsitate de formule identice sunt în general mai eficiente decât de calcul a acestora pe tuple de variabile (t. E. Desen decât tabele de adevăr).
Observăm că "tactica" dovezii echivalenței poate fi diferită: fie transformăm una din formule, dăm-o spre cealaltă formă, fie transformăm ambele formule, conducându-le la aceeași formulă.
Dovediți echivalența formulelor folosind tabelele lor de adevăr:
a) comparați tabelele de adevăr pentru părțile din dreapta și din stânga:
1.13. Construiți o formulă U astfel încât formula dată să fie identică:
1.14. Construiește o formulă din trei variabile care este adevărată dacă și numai dacă exact două variabile sunt false.
1.15. Construiți o formulă din trei variabile, care are același înțeles ca majoritatea (minoritatea) variabilelor.
1.3. Formule normale ale formulelor logice propoziționale
Rezumat al teoriei
O conjuncție elementară este o conjuncție a variabilelor sau negările lor, în care fiecare variabilă sau negarea ei nu are loc mai mult decât o dată.
Orice disjuncție a conjuncțiilor elementare este denumită formă normală disjunctivă (DNF).
Trebuie remarcat faptul că funcția DNF (sau formula) poate să nu fie singura.
Algoritmul de reducere la DNP poate fi descris cu ajutorul echivalențelor date mai sus sau a legilor logice de bază (vezi secțiunea 1.2). În primul rând, cu ajutorul legii (II.1) și a legilor lui de Morgan (II.2), (II.3), toate negările "coboară" la variabile. Apoi, consolele sunt dezvăluite prin legi logice (I.7), (I.8), (IV.7) și (IV.8) elimină excesul de conjuncție și variabilele recurență în conjuncții și prin legi logice (IV.1. ) - (IV.6) constantele sunt șterse.
Se spune că o conjuncție elementară este regulată. dacă fiecare variabilă intră nu mai mult de o dată (inclusiv aparițiile sale sub semnul negării).
Se spune că o conjuncție elementară regulată este completă cu privire la variabile dacă fiecare dintre aceste variabile intră într-o singură dată (probabil sub semnul negării).
Forma normală disjunctivă normală (DSNF) în ceea ce privește variabilele se numește DNF, în care nu există conjuncții elementare identice și toate conjuncțiile elementare sunt regulate și complete cu privire la variabile.
Datorită volumului mare, acest material este plasat pe mai multe pagini:
1 2 3
Trimiteți-le prietenilor: