Reguli de deductie

[Cristi Popa]

Sa se justifice urmatoarele reguli de deductie:
1) Regula modus ponens (sau regula concluziei): Daca enunturile \( P \) si \( P \rightarrow Q \) sunt adevarate, atunci si enuntul \( Q \) este adevarat.
Pentru urmatoarele doua reguli de deductie consideram un predicat oarecare \( P\equiv P(x) \) ce contine variabila \( x \) (si eventual alte variabile) si un enunt oarecare \( Q \) (propozitie sau predicat) care nu contine variabila \( x \).
2) Regula introducerii cuantificarii existentiale (\( \exist\Rightarrow \)): Daca enuntul \( P \rightarrow Q \) este adevarat, atunci enuntul \( (\exist xP)\rightarrow Q \) este adevarat.
3) Regula introducerii cuantificarii universale (\( \Rightarrow\forall \)): Daca enuntul \( Q \rightarrow P \) este adevarat, atunci enuntul \( Q\rightarrow (\forall xP) \) este adevarat.

Observatie:
Exista un numar nelimitat de reguli de deductie, dar toate sunt consecinte a trei reguli fundamentale: regula modus ponens si regulile \( (\exist\Rightarrow),\ (\Rightarrow\forall) \). De fapt, se poate arata ca pentru nevoile oricarei teorii deductive sunt suficiente doar regula modus ponens si una dintre celelalte doua \( \left((\exist\Rightarrow),\ (\Rightarrow\forall)\right) \), deoarece fiecare dintre aceste reguli de introducere a cuantificarii, poate fi obtinuta din modus ponens si din cealalta regula de introducere a cuantificarii.

[Liviu Paunescu]

Spun cum vad eu lucrurile, doar asta pot sa fac la astfel de intrebari. Altii poate gandesc altfel.

La modus ponens nu prea avem ce comenta, este insasi notiunea de implicatie. Despre ultimile doua, pe mine unul ma enerveaza propozitiie in care apar variabile libere. Or fi utile in alte scopuri, dar nu sa stam sa le vedem valoarea de adevar. Din punctul meu de vedere cand spui \( A(x) \) cu \( x \) variabila libera, vrei sa spui de fapt \( \forall xA(x) \), dar ai uitat sa zici oricare ar fi x.
Pentru a treia regula, avem deci \( \forall x(Q\rightarrow P(x)) \) si cred ca e clar acum de ce \( Q\rightarrow(\forall xP(x)) \).

Putin mai tricky este a doua. Avem \( \forall(P(x)\rightarrow Q) \). Am sa scriu in cuvinte:) "Pentru orice \( x \) daca \( P(x) \) atunci \( Q \)". Sper ca e clar acum ca e suficient ca \( P(x) \) sa aibe loc pentru un singur \( x \) pentru ca propozitia \( Q \) sa fie adevarata. Deci \( (\exists xP(x))\rightarrow Q \).

[gefest]

...Daca enuntul \( Q \rightarrow P \) este adevarat ...

Ce înseamnă este adevărat? De exemplu pentru enunţul \( 1=1\to x^2-1=0. \)

La MP e mai clar: Dacă \( A \) şi \( A\to B \) sunt tautologii, atunci \( B \) este tautologie. Totodată \( B \) este o consecinţă a lui \( A \) şi \( A\to B \). Dar în cazul cuantificatorilor

[Liviu Paunescu]

La MP e mai clar fiindca e logica de ordinul zero. Cuantificatorii tin de logica de ordinul intai.

Cand faci cuantificari ai nevoie implicit de un univers. In enuntul tau variabila \( x \) este libera. Asta inseamna ca o sa ii pun un oricare in fata cum spuneam si in mesajul precedent. Totusi cuantificarea trebuie sa aibe loc dupa o multime. Oricare \( x \) numar natural sau real sau mai stiu eu ce.

Sa zicem ca universul tau pentru acel enunt ar fi multimea numerelor reale. Avem acum enuntul \( 1=1\to\forall x\in\mathbb{R}(x^2-1=0) \). E o implicatie in care ipoteza este adevarata (\( 1=1 \)) si concluzia este falsa. Deci enuntul dat de tine ca exemplu este fals.

[gefest]

...Sa zicem ca universul tau pentru acel enunt ar fi multimea numerelor reale. Avem acum enuntul \( 1=1\to\forall x\in\mathbb{R}(x^2-1=0) \). E o implicatie in care ipoteza este adevarata (\( 1=1 \)) si concluzia este falsa. Deci enuntul dat de tine ca exemplu este fals...

\( \forall x(Q\to P(x))\to(Q\to\forall xP(x)) \) este adevărat. Dar \( (Q\to P(x))\to(Q\to\forall xP(x)) \) poate fi fals. Prin urmare din falsitatea lui \( Q\to\forall xP(x) \) nu rezultă falsitatea lui \( Q\to P(x) \), ci mai degrabă că \( Q\to P(x) \) poate fi adevărat sau fals . Tot aşa cum în logica de ordinul zero implicaţia formulelor elementare \( p\to q \) are în tabel trei de T şi un F.

[Liviu Paunescu]

\( (Q\to P(x))\to(Q\to\forall xP(x)) \) este fals. Totusi nu cred ca acest lucru afecteaza argumentatia mea asupra faptului ca propozitia \( 1=1\to x^2-1=0 \) este falsa. Nu pot decat sa revin la ceea ce am zis initial despre enunturi cu variabile libere: ca nu trebuie neaparat sa le stabilim valoarea de adevar.

[gefest]

Alte reguli se numesc reguli de introducere si eliminare a simbolurilor logice. Vreo 14 sunt in total. Una este
Daca \( \Gamma\vdash A(x) \), atunci \( \Gamma\vdash\forall x A(x) \) (lista de formule (posibil vida) \( \Gamma \) nu contine variabila libera \( x \))

Regulile de introduce si eliminare se pot deduce din lista de postulate sau invers, pornind de la aceste reguli sa demonstram formulele din lista de mai sus.

In alte sisteme de axiome se folosesc nu scheme, dar formule elementare si atunci pe linga regulile MP, \( \forall \), \( \exists \) se introduce regula substitutiei (Novikov, Church).