Logică matematică

Calculul predicatelor: axiomele si regulile de deductie.

Form din calc pred se construiesc la fel ca si form din calc prop, insa aici in afara de mici simboluri mai apar si simb de pred: P(x), Q(x)..., simboluri de cuantificatori:"x,$x.

P/u a construi form in log pred e/e nevoie sa se satisfaca urm conditii:

1. Fie U o from ce contine variabila x libera, at "xU(x) si $xU(x) aceste expresii sint la fel formule, x- variabila de legatura.

2. Fie form U si V astfel de formule ce nu contin asa fel de variabile incit intr-o formula ele sa fie libere, iar in cealalta sa fie variabila de legatura, at expresiile: UÙV, UÚV, U®V si U tot sunt formule.

Lema A. In orice form variabilele de legatura si libere sunt notate cu diferite litere.

Lema B. D/a un cuant se afla in domeniul de activitate al altui cuant at var de legatura a ac cuant sunt notate cu diferite litere.

In calc pred avem 5 grupe de axiome> primele 4 grupe coincid cu cele din alg prop, pe cind a 5 e formata din a 2 numai legata cu cuant.: 1. "xF(x)®F(y) 2. F(y)®$xF(x).

Regulile de deductie din calc pred.:

1. MP Modus Pones( regula generalizarii) G,G®H

2. S- substitutia in afirmatii si pred e/e analogica cu substitutia din calc prop., insa acolo d/a form ce se subst era arbitrara, at aici treb sa se satisfaca citeva conditii adaugatoare SAVU(A)=U(V)

1. var de leg din V sunt notate cu diferit elitere fata de var din U(V) si invers. 2. D/a subformula A in form U se afla sub actiunea unui cuant "(x), at var x nu treb sa intre in form U.

Reguli de leg cu cuant.

IRlc – D/a in in calc pred poate fi dedusa form F¢V-V(x), ÎV at poate fi dedusa si form F¢V®"xU(x)

IIRlc D/a in calc pred poate fi dedusa regula U(x)®V,xÎV, at poate fi dedusa si $xUx®V. cunat " apare la ipoteza, consecinta. Calculul prop. Notiune de formula, simbolurile calcului pro, axiomele si regulile de deuctie.

In calc prop nu se introduc operatii si nu se alc tabele, dar se introduc formule. Form ce se introduc adevarate se num axiome, iar celelalte se obtin din acestea in baz unor anumite reguli ce permit a capata noi formule. Aceste reguli poata denumirea de deductie. In calc prop avem 3 categorii de simboluri:

1. A,B,C,...,A1;B3....

2. simboluri legaturilor logice: &,Ú,®, .

3. parantezele: ( ; )

Alte categorii nu $.

Def completa de formula are un caracter recursiv, ad se introduc la inceput citeva form initiale si in baza acetor formule se arata regule de formare din elel a noi formule.

Def.

1. literele latine mari le vom socoti form elementare.

2. daca A si B sint form at form sint si urm expresii: A&b,AÚB,A®B,A.

3. partile componente ale form le vom numi subformule.

Reguli de deductie:

1. Reg substitutiei: fie ca form A contine ca subform: A(A1,A2,...,An). Fie ca form B – form oarecare. Daca A(A1,A2,...,An) e/e adev at subst.

SA1B A(A1,A2,...,An)= A(B,A2,...,An).

2. Modus Pones MP

daca A-a si A®B-a at B-a

Axiomele calc prop.