Formula de algebra propozitional

1. Definiție și exemple de formule

Cu ajutorul operațiilor logice discutate în secțiunea anterioară, putem, pe baza unei declarații simplu, pentru a construi un nou mai complex,. De exemplu, pe baza declarațiilor de R. „Pușkin - poet român“, Q. „Gauss - matematicianul german“, R. „“, puteți construi o nouă declarație :. „Dacă Pușkin - poet român și Gauss - matematician german,“ Această nouă declarație are forma

Expresia (1), în afară de sensul specific declarațiilor Q. R. R. poate fi privit ca un sistem care permite, pornind de la orice declarații R. Q. R. construi noi enunț. Că astfel de sisteme și va fi interesat de noi astăzi. Ele se numesc algebra propozitional. Desigur, suntem obișnuiți cu puțin diferită de interpretare a termenului „formula“; Formula pentru noi - este egalitatea de tip (formula suprafața unui cerc), (formula care exprimă teorema lui Pitagora), etc. Cu toate acestea, expresia poate fi văzută ca un fel de formula - .. formula pentru construirea unui compozit de afirmații simple.

Înainte de a da o formulă definiție generală a algebră propozițiilor, suntem de acord după cum urmează. variabile propozitiilor noi numim aceste variabile, care pot lua ca valoare orice declarații specifice. Vom nota aceste litere majuscule variabile X, Y, Z, U, V .. sau prin aceleași litere cu indicii: vom introduce, în plus, două variabile și mai specifice și propozițiilor A; în loc de prima, puteți înlocui orice declarație adevărată, în loc de un al doilea - orice fals.

Descrierea completa a formulelor de concept dau următoarele acorduri:

1 °. Fiecare variabilă propozițională individuală este o formulă.

2 °. Dacă - două formule, expresia. Ele sunt, de asemenea, formule.

3 °. El nu există alte formule, altele decât cele care sunt obținute prin aplicarea unui număr finit de ori revendicărilor 1 ° și 2 °.

De exemplu, formula este următoarele expresii: etc.

Pentru o mai mare claritate menționăm exemple de expresii care nu sunt formule.

Faptul că noi nu recunoaștem formula din ultimele expresii scrise, poate provoca la început enigmatic. Cu toate acestea, dacă urmați definiția de mai sus, expresia - nu este o formulă; pentru a deveni o formulă, îi lipsește bretele, deoarece, în conformitate cu n. ° 2, formula trebuie sa fie o expresie. în schimb. Diferența dintre expresiile și devine semnificativă în special dacă includem expresia ca parte componentă a unei formule mai complexe: compara, de exemplu, expresia. Este o formulă cu (nu formula); nu este clar modul de interpretare a doua expresie (operație care urmează o: după sau după).

Astfel, înregistrarea eclise exterioare în formula va fi considerată facultativă, cu excepția cazului această formulă nu include o componentă a unei formule mai complexe.

2. tabele de adevăr pentru formulele

Luați în considerare orice formulă de algebră propoziționale, de exemplu. Notăm această formulă de reducere F (X, Y, Z). Valoarea de adevăr a formulei F (X, Y, Z) este complet determinată de valorile de adevăr ale variabilelor X, Y, Z. Această circumstanță permite să elaboreze un tabel care furnizează valoarea de adevăr pentru F (X, Y, Z), în funcție de valorile de adevăr pentru X, Y, Z. Acesta este compus din patru coloane: trei - pentru variabilele X, Y, Z, și unul - pentru formula în sine. Deoarece fiecare dintre variabilele X, Y, Z poate presupune două valori (1 sau 0), apoi se triplează X, Y, Z obținut diferite caracteristici. Acest lucru înseamnă că ar trebui să aibă masa de 8 rânduri. Pentru a umple ultima coloană a valorilor tabel substitutive X, Y și Z în formula F (X, Y, Z). De exemplu, dacă X = 1, Y = 1, Z = 1, avem

când X = 1, Y = 1, Z = 0 descoperim

.. Etc Ca rezultat, de umplere se obține următorul tabel:

În general, pentru fiecare formulă de algebră propoziționale, puteți crea un tabel care dă valoarea de adevăr a formulei, în funcție de adevăr valorile variabilelor. Un astfel de tabel este numit un tabel

formula de adevăr

Proceduri pentru tabelul de adevăr poate fi simplificată prin utilizarea unor trucuri. Să ilustrăm acest lucru cu următorul exemplu.

Exemplu. Crearea unui tabel de adevăr pentru formula

(În virtutea suporturilor externe privind acordul în formula omisă).

Primul pas este de a stabili o secvență de operații. Pentru a face acest lucru pe semnul fiecare operațiune logică care apare în numărul formula stabilită, indicând secvența acestei operațiuni. În acest caz, este posibil, de exemplu, o astfel de numerotare:

Primul rând (antet) al tabelului scriem X, Y, și această formulă. Sub variabilele X și Y, vom scrie tot felul de seturi de valori logice. Apoi, vom obține o masă

Numărul de coloană 5 (preparat ultima) dă valoare de adevăr a formulei.

Definiție 1. Formula de algebră propozițiilor se numește în mod identic adevărat (sau tautologie) în cazul în care valoarea sa de adevăr este egal cu 1 pentru orice valoare a adevărului pentru.

Rolul tautologii este în primul rând faptul că acestea dau circuitele de declarații adevărate, indiferent de conținutul și veridicitatea componentelor declarații.

De exemplu, formula este tautologie

( «X sau X»). Într-adevăr, oricare ar fi un anumit enunț poate fi înlocuită cu X, o afirmație este adevărată, deoarece

Cu toate acestea tautologii semnificația constă nu numai în faptul că, cu ajutorul lor construit declarații adevărate; nu mai puțin important este faptul că o tautologie da metodele corecte de inferență. Ilustrăm acest lucru pentru exemplul formulei

Această formulă este tautologie; care este ușor de a verifica dacă scrie (o unitate va fi în valorile coloanelor pentru întreaga formule) la masa de adevăr. Schema de deducții logice, a exprimat această tautologie; utilizate în mod obișnuit în matematică: această schemă se numește „o dovadă de contradicție“. Și anume, să fie obligată să dovedească o X. afirmație Susținem ca aceasta: să spunem că X este falsă (și anume, că este adevărat ..). Apoi, cu ajutorul unor argumente (în cadrul teoriei, care este studiată) argumentăm că rezultă dintr-o utverzhdenieY. și - că ar trebui să fie opusul afirmării. Deoarece valabilitatea simultană a afirmațiilor și Y nu este posibilă, din considerațiile de mai sus, concluzionăm asupra validității (adevăr) X.

Să subliniem câteva tautologie foarte importante.

1. Legile comutativitatea conjuncției și disjuncție:

2. Legile asociativitate conjuncție și disjuncție:

3. distributivitate:

4. Legile De Morgan :.

5. Legea mijloc exclus :.

6. contrapunere :.

7. Articolul închisoare Lanțul (legea silogism):

8. Articolul "modus ponens". .

9. Schema de probă „contrare“ :.

Dovada că fiecare dintre formulele menționate este o tautologie, deține propria lor într-un exercițiu.

4. echivalențele

Definiție 2. Două formule și algebra propozitionale sunt numite echivalente. dacă oricare dintre valorile logice ale variabilelor logica propozițională valorile F și H sunt aceleași. Echivalența formulele F și H este scrisă ca :.

Există o relație strânsă între noțiunea de echivalență cu formula și conceptul tautologiei. Acesta este după cum urmează: Formula F și H sunt echivalente dacă și numai dacă formula este o tautologie.

Această afirmație rezultă direct din definițiile propriu-zise

echivalențele și tautologie.

1. Dovedește echivalența formulelor și.

Pentru fiecare dintre aceste formule formează tabelul de adevăr:

Comparând tabele, vom vedea că aceste formule sunt echivalente.

2. Demonstrarea echivalenței formulelor și.

Desigur, puteți compara tabelul de adevăr aceste formule! Cu toate acestea, putem argumenta astfel: formulă este falsă numai dacă X = 1, Y = 0. formula și - numai în cazul în care X = O, Y = 0. adică atunci când X = 1, Y = 0. Astfel, atât .. formulă falsă sau adevărată simultan.

Un equipollences număr poate fi obținut pornind de la un anumit n. 3 tautologie. De exemplu, formulele sunt echivalente, deoarece formula este tautologie (vezi. Tautologie 4 °).

Trebuie remarcat faptul că expresia nu este o formulă. Este pur și simplu o înregistrare a faptului că între formulele F și H are un anumit tip de relație (și anume, că F este echivalent cu H).