Simboluri, formule, axiome ale calculului propozițional.
Reguli de inferență
Luați în considerare un sistem axiomatic formal, într-un sens adecvat algebrului pronunțărilor. Noi numim acest sistem calculul propozițiilor.
Pentru a construi calcul, este necesar să se determine calcularea alfabetului, conceptul de formula, formule, clasa, numite axiomele, regulile de inferență calculului.
Literele mari latine A, B, C. X, Y, Z. pe care le numim declarații variabile.
Simboluri ale operațiunilor de calcul Ù. Ú, ®, ¾ (semnul conjuncției, disjuncția, urmărirea și negarea).
Sistemul calculului propozițional nu conține alte simboluri.
O formulă în calculul propozițional este o secvență de simboluri. Dar nu fiecare succesiune de simboluri este o formulă. De exemplu, secvențele A → B (C →) și (A B) nu sunt formule. Definiția unei formule în calculul propozițional este dată de:
1. Fiecare instrucțiune variabilă este o formulă.
2. Dacă a, b sunt formule, atunci expresiile formei (aÙb) ,. . (unÚb), (a®b) sunt, de asemenea, formule.
În calculul propozițional dăm clasa formulelor-axiome originale adevărate.
Regulile inferenței permit să se deducă din acest sistem de axiome alte adevărate formule de calcul propozițional. Noi numim formula calculului propozițional fals dacă negația lui este adevărată. Vom denumi formulele reale prin litera R, false - F.
Regulile de bază ale inferenței includ două:
1) Regula de concluzie.
Dacă a și (a ® b) sunt formule adevărate, atunci b este de asemenea adevărat. Această teză poate fi scrisă în formular
2) regula de substituție
Să presupunem că o formulă a conține o propoziție variabilă A. Apoi, înlocuind instrucțiunea A peste tot, unde apare, prin orice formula b, obținem formula adevărată. Această teză este scrisă în formular.
Se spune că o formulă este deductibilă în calculul propozițional, dacă se poate obține prin aplicarea regulilor de deducere la axiomele calculului propozițional. Declarația că formula b este deductibilă este scrisă după cum urmează:
Procesul de obținere a formulelor din axiomele calculului propozițional se numește o derivare formală. Concluzia formală constă în indicarea regulilor, în ce ordine și formulelor folosite pentru a obține această formulă.
Să demonstrăm că A? A este derivabil, adică, A ®.
1. Scrie Axiom 2 din grupa I.
2. Aplicăm regula de substituție. și anume
3. Rețineți că a este o formulă adevărată, ca axiom din grupul I; avem formulele adevărate a și a ® b. Aplicăm regula de concluzii și obținem (A ® B) ® (A ® A).
4. Aplicăm regula de substituire a formulei rezultate, înlocuind declarația B cu:
5. Dar. este axiomul 2 din grupa IV. Aplicăm regula de concluzie formula formulată. și anume -A®A.
Se spune că formula b este deductibilă de la formulele a1. a2. o. dacă formula b poate fi dedusă prin regula de închisoare, luând ca formulele inițiale a1. a2. un și toate sunt adevărate în calculul propozițional al formulei. Derivabilitatea formulei b din formulele a1. a2. un este scris ca a1. a2. o. b.
Dacă formula b este deductibilă de la formulele a1. a2. o. atunci formula derivată este a1 ® (a2 ® (. (a ® b).)), adică,
Teorema deducției face posibilă stabilirea derivabilității diferitelor formule ale calculului propozițional într-un mod mai simplu decât derivarea directă a acestor formule din axiome folosind regulile de inferență. Cu ajutorul teoremei de deducere derivăm regulile de bază ale calculului propozițional:
1. Regula silogismului. Dacă formulele (a ® b) și (b ® g) sunt adevărate, atunci formula (a ® g), adică
2. Regula privind permutarea parcelelor. Dacă formula (a® (b®g)) este adevărată, atunci formula (b® (a®g)) este adevărată; ;
3. Regula de conectare a parcelelor. Dacă formula (a® (b®g)) este adevărată, atunci formula (aÙb®g), adică .
Problemele de coerență, de completitudine,
independența axiomilor calculului propozițional
Folosim algebra propozițională ca un anumit model al calculului propozițional. Formulele calculului propozițional vor fi tratate ca formule ale algebrei propoziționale. Pentru a face acest lucru, toate literele incluse în alfabetul calculului propozițional vor fi considerate declarații variabile într-un sens semnificativ, adică, variabile care iau valorile lui AND și L. Simbolurile alfabetului Ù. Ú, ®, ¾. - vor fi înțelese ca conexiuni logice ale algebricii propozițiilor.
Următoarea teoremă este adevărată.
Toate axiomele calculului propozițional sunt aceleași formule adevărate ale algebrei propoziționale. Toate formulele derivate din axiomele calculului propozițional sunt aceleași formule adevărate ale algebrei propoziționale.
O dovadă a primei părți a teoremei poate fi făcută printr-o verificare directă.
Valabilitatea a doua parte a teoremei poate fi văzut, arătând că, prin aplicarea regulii de inferență și regula de substituție la identic adevărată formulă de algebră propoziționale, obținem formula identic adevărat. Astfel, fiecare formulă dedusă în calculul propozițional este identitatea adevăratei formule a algebrei propositionale.
Atunci când se analizează orice sistem logic formal, inclusiv calculul afirmațiilor, există trei probleme: consecvența, completitudinea, independența sistemului axiomelor de calcul.
Un calcul logic este considerat consecvent dacă nu derivă nici două formule, dintre care una este negarea celuilalt.
Problema de consecvență este că trebuie clarificat faptul că acest calcul este consecvent.
Dacă în calcul putem obține o formulă a și negarea ei. atunci un astfel de calcul va fi contradictoriu. Dacă calculul logic este inconsistent, orice formulă va fi dedusă din ea. Un astfel de calcul nu are valoare, pentru că este incapabil să reflecte diferența dintre adevăr și falsitate.
Pentru a dovedi coerența unui calcul logic, este suficient să găsiți în el cel puțin o formulă nedeductibilă. În calculul propozițional, problema de consistență este rezolvată după cum urmează.
Teorema I. Calculul propozițiilor este consistent.
Validitatea acestei afirmații rezultă din teorema anterioară. De fapt, să fie o formulă deductibilă în calculul propozițional. În consecință, este identic adevărat dacă este considerată o formulă substanțială a algebrei propoziționale. Apoi - este identic fals, adică nu este deductibilă pentru toate valorile variabilelor care intră în ea. În consecință, a și nu pot fi deductibile împreună în calculul propozițional.
Astfel, orice formulă deductibilă în calculul propozițional este identică dacă această formulă a calculului propozițional este considerată ca o formulă de conținut a algebricii propoziționale. Problema inversă apare.
Orice formulă identică a algebrei propoziționale poate fi dedusă din axiomele calculului propozițional.
Această problemă este problema integrității calculului declarațiilor în sens larg.
Pentru fiecare completitudine definiție sistem logic, în cel mai larg sens poate fi formulată după cum urmează: calculul logic se numește complet dacă toate în adevăratul sens al formulei de conținut poate fi derivat în conformitate cu regulile axiomele de calcul.
Pentru calculul pronunțărilor, problema de completitudine este rezolvată pozitiv.
Teorema II. Sistemul calculului propozițional este complet.
La fel de importantă este definirea integrității unui sistem logic în sensul strict al cuvântului. Calculul logic se numește complet în sensul strict al cuvântului, în cazul în care adăugarea la sistemul de axiome underivable în această formulă de calcul face calcule contradictorii. Calculul propozițiilor este complet, de asemenea, în sens restrâns al cuvântului.
Pentru orice sistem logic apare problema independenței axiomelor acestui calcul. Ne întrebăm dacă este posibil să se deducă orice axiom al calculului de axiomele rămase folosind regulile de deducere a acestui sistem. Dacă acest lucru este posibil, atunci axioma derivată din alte axiome poate fi ștearsă din lista axiomelor acestui calcul. O axiomă care nu poate fi dedusă din axiomele rămase este numită independentă de aceste axiome. Un sistem de axiome în care nici o axiomă nu poate fi dedusă din restul se numește un sistem independent de axiome.
Această problemă pentru calcul este rezolvată pozitiv.
THEOREM III. Sistemul axiomelor calculului propozițional este independent.
Problema independenței sistemului de calcul axiomă logică este o problemă de matematică foarte importantă, uneori, ceea ce duce la problema înlocuirii oricăruia dintre axiomele sale de negare. Ca un exemplu, problema independenței lui Euclid postulat al cincilea sistemul de axiome de geometrie, problema independenței axiomele sistemului Zermelo de axiome ale teoriei multimilor. Aceste întrebări au avut o mare importanță în dezvoltarea matematicii.
Pentru a defini conceptul de predicat, luați în considerare următoarele exemple.
1. Fie N un set de numere naturale, iar P indică faptul că proprietatea unui număr natural este simplă. Dacă x este un element arbitrar al N, atunci expresia "număr natural x este simplă", care poate fi scrisă în forma P (x), nu mai este o declarație, deoarece Valoarea adevărului acestei instrucțiuni depinde de x. În esență, P (x) este variabilă (nedefinita) declarație care devine certă atunci când x este înlocuită cu un element particular al lui N. De exemplu, P (3) = 1, P (4) = 0. Cu alte cuvinte, P (x) este funcție definită pe setul de numere naturale și luând doar două valori: 0 și 1.
2. Fie Z setul de numere întregi și P proprietatea unei perechi de numere care au același semn. Apoi P (x, y) va însemna: "numerele întregi x și y au același semn". Această declarație vagă devine clară dacă x și y sunt înlocuite cu numere specifice. De exemplu, P (2,3) = 1, P (-1,5) = 0. Instrucțiunea indefinită P (x, y) este o funcție a două variabile.
3. Fie A și B setul de puncte, C setul de linii pe planul euclidian și P (a, b, c) denotă: "linia dreaptă c trece prin punctele a și b". În acest exemplu, avem de-a face cu o funcție a trei variabile, cu a și b luând valori dintr-un set de puncte și c luând valori din setul de linii ale planului euclidian.
Definiție 1. Un predicat este o funcție care cartografiază un set de natură arbitrară într-un set sau (fals, adevărat).
Acum ne referim la definiția predicatului în cazul general.
Definiție 2. Fie N = 1, N2, N3, ..., Nn o colecție finită de seturi. Fiecare funcție P (X1, ..., Xn) care se asociază cu fiecare set de n elemente 1, a2, ..., an), unde ai ÎNi. oricare dintre elementele unei algebre booleene se numește un predicat n-loc pe N. Un set Ni se numește un domeniu obiect pentru variabila xi. Variabilele x1, ..., xn se numesc variabile obiect. Unele seturi de Ni pot coincide.
Dacă imaginea setului (a1, a2, ... an) este o unitate în maparea P, atunci este scrisă.
și spunem că valoarea predicatului P pentru mulțimea (a1, ..., an) este adevărată. Dacă, totuși, imaginea (a1, ..., a) este zero, apoi scrieți
și spunem că predicatul P pentru set (a1, ..., an) este fals.
n - un predicat local cu n = 1 este numit un predicator unar,
n = 2 - binar și cu n = 3 ternar. Pentru generalitate, introducem conceptul de predicat local 0, și anume, un predicat local 0 este o afirmație adevărată sau falsă.
Deoarece predicatele iau valori de la (0,1), atunci toate operațiile logice pe care le considerăm în algebra propozițională (-, Ù. Ú, ®, n), păstrând aceleași definiții. Pe lângă operațiile de algebră propozițională, vom folosi încă două operații noi care sunt legate de singularitățile predicatelor și vor exprima afirmațiile universalității și existenței.
Fie P (x) un predicat unic definit pe un anumit set M. Daca variabila x denota orice element al setului M, atunci P (x) este o declaratie indefinita.
Operația "pune declarația" xP (x) în corespondență cu propoziția indefinită P (x), care citește: "P (x) este valabilă pentru orice x" și prin definiție este adevărat dacă și numai dacă P (x) orice element xÎM. Trecerea de la instrucțiunea indefinită P (x) la expresia "xP (x) se numește operația de atârnare a cuantificatorului de comunitate peste variabila obiect x.
Operația $ atribuie propoziția $ xP (x) la propoziția indefinită P (x), care citește: "există un x astfel încât P (x) să dețină și prin definiție este adevărat dacă și numai dacă P (x) adevărat pentru cel puțin un element xÎM. Trecerea de la instrucțiunea nedeterminată P (x) la propoziția $ xP (x) se numește operația de suspendare a cuantificatorului de existență peste variabila obiect x.
În primul caz, spunem că variabila obiectivă x este conectată în predicatul P (x) de către cuantificatorul universal, în cel de-al doilea caz - de cuantificatorul existenței.
Definim operațiile de suspendare a cuantificatorului pentru cazul general al unui predicat n local (P1, ..., xn). Operațiile de agățare a cuanti fi cătorilor "și $ în raport cu variabila x1 (în cazul general, în raport cu variabila xi, unde I =), caracterizează predicatul P (x1, ..., xn) (n-1)
Valorile adevărului acestor predicate sunt definite pentru seturile fixe de valori ale variabilelor obiective x2, ..., xn după cum urmează:
În cazul general, dacă k Luați în considerare predicatul D (x1, x2) - "numărul x1 este divizibil cu numărul x2" definit pe setul de numere naturale. Apoi, operația de cuantificare duce la următoarele afirmații: 1. "x1 D (x1, x2) -" pentru orice x1, avem D (x1, x2) ", adică fiecare x1 este divizibil de x2 Acest predicat presupune valoarea adevărului doar pentru x2 = 1. 2. $ x1 D (x1, x2) - "există x1 care este divizibil de x2". Acest predicat preia o valoare reală pentru orice valoare de x2. 3. "x1" x2 D (x1, x2) - "pentru fiecare x1 și pentru fiecare x2 are loc divizibilitatea lui x1-x2. Această afirmație este falsă. 4. $ x1 "x2 D (x1, x2) -" există x1 divizibil la fiecare x2 "- o declarație falsă.
Articole similare
Trimiteți-le prietenilor: