Post on 26-Jan-2020
O evaluare booleana este o functie v al carei domeniu este
multimea tuturor formulelor din logica propozitiilor, iar
codomeniul este multimea de valori de adevar {A, F} a.i.
v(p) este definit pentru orice formula atomica p.
Pentru orice formula ,
▪ v() = A, daca v() = F
▪ v() = F, daca v() = A …
Dintr-o multime de formule spunem ca se deduce o formula
, (sau este consecinta logica pentru ), notat
, daca fiecare evaluare booleana v care satisface il
satisface si pe .
Fie formulele P1, P2, …, Pn. Formula P este consecinta logica a
multimii {P1, P2, …, Pn} daca si numai daca P1 P2 … Pn P
este nesatisfiabila.
Propozitiile compuse p si q se numesc echivalente logic daca si
numai daca p q este o tautologie. Notatie: p q.
(p q) p q
(p q) p q
Cand este nevoie sa construim tabele complete de adevar si cand
nu.
Ex1: Sa se arate ca (p q) (p q) este o tautologie.
(p q) (p q) ( (p q)) (p q) ( p q) (p q) ( p q) (p q) ( p p) ( q q) A A A
Ex2: Aratati ca p q si (p q) ( p q) sunt echivalente.
p q (p q) (q p)
( p q) ( q p)
// not ( p q) cu X, deci vom avea X ( q p)
// adica (X q) (X p)
(( p q) q) (( p q) p)
(( q p) ( q q)) ((p p) (p q))
//( q q) F, la fel (p p)
( q p) (p q)
Exc1: Sa se arate prin tabele de adevar ca urmatoarele formule
propozitionale sunt tautologii:
1. p (p q)
2. (p q) p
3. ( p (p q)) q
4. (p (p q)) q
5. ( p (p q)) q
Exc2: Sa se arate fara sa se foloseasca tabele de adevar ca
formulele de la exercitiul 6 sunt tautologii.
Exc3: Verificati prin tabele de adevar daca urmatoarele formule
sunt echivalente:
1. (p q) r, (p r) (q r)
2. (p q), p q
3. (p q), p q
4. p (q r), q (p r)
5. (p q) r, p ( q r)
Exc4: Verificati fara tabele de adevar daca formulele de la
exercitiul 3 sunt echivalente.
Pentru punctul 3 al exc 3 este necesara si cunoasterea echivalentei:
p q (p q) ( p q)
Ce s-ar intampla daca
din logica propozitiilor eliminam echivalenta () si o inlocuim cu
varianta ei echivalenta: A B (A B) (B A)?
s-ar obtine un limbaj echivalent logic cu logica propozitiilor.
Simplificarea poate merge si mai departe, a.i. orice
propozitie compusa poate fi scrisa folosind numai negatia, o
alta conectiva logica si paranteze.
Exc5: Utilizand numai negatia, implicatia si paranteze scrieti propozitii care sunt logic echivalente cu cele de mai jos:
1. p q
2. p q
3. p q
Exc6: Utilizand numai negatia, disjunctia si paranteze scrieti propozitii care sunt logic echivalente cu cele de mai jos:
1. p q
2. p q
3. p q
4. p q
p q
p
q
p = “Afara ploua” q = “Afara este insorit” Stim ca:
p q = “Afara ploua sau este insorit.”
p = “Afara nu ploua.”
Rezulta: q = “Afara este insorit.”
p q
p
q
p = “Ai o parola.” q = “Te poti loga la calculator.” Stim ca
p q = “Daca ai o parola, atunci te poti loga la calculator.”
p = “Ai o parola.”
Rezulta q = “Te poti loga la calculator.”
Forme precum silogismul disjunctiv sau modus ponens pot fi
combinate pentru a crea demonstratii mai complicate:
P (Q P)
P
Q
Din modus ponens, pornind de la ceea ce stim, obtinem Q P,
o concluzie intermediara.
Din Q P, si P, prin silogism disjunctiv se obtine Q.
D.p.d.v. formal, o demonstratie este o secventa de
propozitii.
Primele propozitii din secventa se numesc premise.
Fiecare propozitie ulterioara se deduce din cele anterioare
printr-o regula de demonstratie.
Ultima propozitie din secventa (cea de sub linie) reprezinta
concluzia.
Intr-un sistem de deductie naturala, avem 2 reguli pentru
fiecare operator logic:
O regula de introducere (notata cu I) care ne permite sa demonstram
o propozitie care are operatorul ca si conectiva principala.
O regula de eliminare (notata cu E) care ne permite sa demonstram
ceva cand se da o propozitie care are operatorul ca si conectiva
principala.
In plus, avem si regula de reiterare (notata cu R) .
Daca ceva a fost deja demonstrat , reiterarea permite reluarea acelei
reguli intr-o line noua.
Cand adaugam o linie la o demonstratie, specificam:
Ce regula (R, I sau E) justifica linia.
Numerele liniilor la care s-a aplicat regula.
R1 in exemplul de mai sus arata ca linia n este justificata prin
reiterare aplicata liniei m.
Reiterarea nu demonstreaza nimic nou, doar aminteste o
propozitie de mai sus (de obicei, mai multe linii mai sus).
m P
n P R m
De ce ar fi nevoie pentru a demonstra P Q?
Ar trebui sa demonstram separat ca P este adevarat, la fel, Q.
m P
n Q
P Q I m,n
I m,n inseamna ca introducerea conjunctiei se aplica pentru
liniile m si n.
Liniile pot fi orice linii existente intr-o demonstatie, nu neaparat
consecutive, lucru valabil pentru toate celelalte reguli.
Evident, P si Q pot fi propozitii complexe (din acest motiv le-am notat cu
litere mari).
Ce se poate deduce din o propozitie precum P Q? Se poate deduce P. La fel, se poate deduce Q.
m P Q
P E m
Q E m
Cand avem o conjunctie pe o linie, se poate utiliza E pentru
a deriva oricare din propozitiile implicate in conjunctie.
E necesita o singura propozitie, deci scriem un singur
numar de linie ca justificare pentru aplicarea acestei reguli.
Ex3: Aratati ca:
[(p q) (r s)] [(t u) (v w)]
[(t u) (v w)] [(p q) (r s)]
Incepem prin a scrie premisa pe prima linie si a trage o liniesub ea. Tot ce apare sub aceasta linie este justificat de o regula a
demonstratiei.
1 [(p q) (r s)] [(t u) (v w)]
Ex3 (cont): Aratati ca:
[(p q) (r s)] [(t u) (v w)]
[(t u) (v w)] [(p q) (r s)]
Din premisa, putem deduce oricare din cele doua propozitii
complexe, prin eliminarea conjunctiei.
1 [(p q) (r s)] [(t u) (v w)]
2 [(p q) (r s)] E 1
3 [(t u) (v w)] E 1
Ex3 (cont): Aratati ca:
[(p q) (r s)] [(t u) (v w)]
[(t u) (v w)] [(p q) (r s)]
I necesita ca fiecare din elementele care vor fi adaugate la
conjunctie sa fie disponibile in demonstratie.
Ele nu trebuie sa fie neaparat in ordine.
1 [(p q) (r s)] [(t u) (v w)]
2 [(p q) (r s)] E 1
3 [(t u) (v w)] E 1
Ex3 (cont): Aratati ca:
[(p q) (r s)] [(t u) (v w)]
[(t u) (v w)] [(p q) (r s)]
I necesita ca fiecare din elementele care vor fi adaugate la
conjunctie sa fie disponibile in demonstratie.
Ele nu trebuie sa fie neaparat in ordine.
1 [(p q) (r s)] [(t u) (v w)]
2 [(p q) (r s)] E 1
3 [(t u) (v w)] E 1
4 [(t u) (v w)] [(p q) (r s)] I 3,2
De observatordinea liniilor
Daca propozitia p este adevarata, atunci si p q este adevarata.
Deci, daca avem o propozitie P adevarata, putem introduce o disjunctie
in care sa apara si P.
m P
P Q I m
Q P I m
Q poate fi orice alta propozitie, simpla sau complexa.
Asadar, o demonstratie corecta este si cea de mai jos.
1 p
2 p [(r q) (r s)] I 1
Stiindu-se P adevarat, se poate introduce disjunctia cu Q.
Aceasta se poate interpreta ca: daca P este adevarat, atunci si P Q
este adevarat, indiferent ce valoarea de adevar a lui Q.
Deci concluzia nu poate fi falsa daca premisa este adevarata, deci
demonstratia este corecta.
Ce se poate concluziona daca se stie ca P Q este adevarata?
Nu se poate spune ca P este adevarata.
▪ Nu stim daca P face P Q adevarata sau Q o face adevarata.
Analog, nu se poate concluziona nimic despre Q.
Nu se poate trage nicio concluzie doar din premisa P Q.
Daca stim insa si ca P este falsa, atunci putem concluziona ca
este adevarata Q.
Am ajuns la silogismul disjunctiv.
m P Q
n P
Q E m, n
m P Q
n Q
P E m, n
Se observa ca cele doua sunt logic echivalente.
Scriem demonstratia incepand cu premisa, dupa care tragem
o linie orizontala.
P Q
P Q
1 P Q
Daca am fi stiut ca P este adevarat, am fi putut
concluziona Q prin E.
Dar nu stim acest fapt...
Putem incepe o subdemonstratie (subdem), adica odemonstratie in cadrul demonstratiei principale.
Se mai trage o linie verticala pentru a indica faptul ca nu ne
mai aflam in cadrul demonstratiei principale.
Apoi scriem in cadrul subdem o presupunere.
In cazul nostru, ar fi util sa presupunem P.
1 P Q
2 P
Este important sa mentionam ca nu pretindem ca P este demonstrat. Nu este nevoie insa sa demonstram nicio presupunere din subdem.
Poate fi interpretata ca: ce s-ar putea demonstra daca P ar fi adevarat?▪ Se poate demonstra Q.
1 P Q
2 P
3 Q E 1,2
Am demonstrat asadar ca daca avem premisa P, putem
demonstra Q.
Altfel spus, am demonstrat ca P Q.
Prin urmare, putem iesi din subdem cu concluzia P Q.
Notatia de la introducerea implicatiei cuprinde toate liniile
din subdem, care desigur pot fi mai multe de doua.
1 P Q
2 P
3 Q E 1,2
4 PQ I 2-3
Din faptul ca putem presupune absolut orice, poate parea ca
se merge spre haos.
Totusi, presupunerile se leaga de afirmatiile adevarate din afara
demonstratiei.
O subdem se incheie atunci cand se incheie linia verticala.
Pentru a se termina o demonstratie, trebuie incheiate toate
subdem.
Cand inchidem o subdem, nu ne mai putem referi inapoi la
afirmatii din liniile din subdem (care contin presupuneri).
Cand introducem o subdem, incepem cu ceea ce vrem sa deducem
in coloana.
Asadar, pentru a obtine o implicatie prin I, incepem presupunerea
cu antecedentul implicatiei pe care vrem sa o realizam.
Ultima linie a subdem va contine elementul din dreapta implicatiei.
m P
n Q
PQ I m-n
Nu obtinem nimic doar dintr-o implicatie PQ.
Daca am sti insa si P, am putea concluziona Q.
E se mai numeste si modus ponens.
m P Q
n P
Q E m, n
Ex4: Aratati ca:
Devreme ce concluzia contine o implicatie, va trebui sa se
utilizeze regula I.
Pentru aceasta, avem nevoie de o subdem care sa inceapa cu P.
PQ
Q R
P R
Presupunand P adevarat, avem posibilitatea sa utilizam E asupra primei premise. Aceasta ne permite sa-l determinam pe Q.
E aplicat premisei 2 ne conduce la R.
Din presupunerea lui P am ajuns sa demonstram R si aplicam I.
1 P Q
2 Q R
3 P
Presupunand P adevarat, avem posibilitatea sa utilizam E asupra primei premise. Aceasta ne permite sa-l determinam pe Q.
E aplicat premisei 2 ne conduce la R.
Din presupunerea lui P am ajuns sa demonstram R si aplicam I.
1 P Q
2 Q R
3 P
4 Q E 1, 3
5 R E 2, 4
6 P R I 3-5
Pentru a demonstra ca P Q, trebuie sa aratam ca
presupunand P obtinem Q si viceversa.
Deci trebuie sa aratam ca PQ si Q P.
Prin urmare, trebuie sa avem doua subdem, una in care presupunem P
si obtinem Q si una in care presupunem Q si obtinem P.
m P
n Q
… …
p Q
q P
PQ I m-n, p-q
Daca stim P Q si de asemenea stim P, atunci putem
concluziona Q.
Analog, stiind PQ si Q putem concluziona P.
m P Q
n P
Q E m, n
m P Q
n Q
P E m, n
Se face prin reducere la absurd.
Se face in cadrul unei subdem o presupunere si, daca se
ajunge la o contradictie, am demonstrat negatia
presupunerii initiale.
m P RA
n Q
n + 1 Q
n + 2 P I m-n + 1
Reducere la absurd.
De la m pana la n + 1.
Ultimele doua propozitii ale subdem trebuie sa fie o
contradictie clara, adica o propozitie urmata de negatia ei.
Ex5: Aratati ca (P P) este o tautologie.
Demonstratia se poate face incepand cu o subdem prin presupunerea
ca P P.
1 P P RA
2 P E 1
3 P E 1
4 (P P) I 1-3
Se presupune o afirmatie negata si daca se ajunge la o
contradictie, afirmatia fara negatie este considerata adevarata.
m P RA
n Q
n + 1 Q
n + 2 P E m-n + 1
Ex6: Demonstrati ca:
1 P Q
2 P R
3 Q R
4 R RA
5 P RA
6 R E 2, 5
7 R R 4
8 P I 5-7
9 Q RA
10 R E 3, 9
11 R R 4
12 Q I 9-11
13 Q E 1, 8
14 R
P Q
P R
Q R
R
Avem o serie de reguli care sunt permise in cadrul unorpropozitii complexe.
Comutativitatea (notata in cadrul demonstratiilor com)
P Q P Q
P Q Q P
PQ Q P
Dubla negatie (DN)
P P
Legile lui De Morgan (DeM)
(P Q) P Q
(P Q) P Q
Implicatia (Impl)
PQ P Q
P Q P Q
Echivalenta (Echiv)
P Q (PQ) (Q P)
Ex7: Aratati ca: (PQ)
P Q
1 (PQ)
2 ( P Q) Impl 1
3 P Q DeM 2
4 P Q DN 3
Exc7: Adaugati justificarile (regula aplicata si numerele de
linii) pentru fiecare linie a demonstratiilor urmatoare.
1 T Q
2 P T
3 Q (R S)
4 T
5 Q
6 R S
7 S
1 P Q
2 P Q
3 P
4 Q
5 P
6 P
7 P
Exc8: Demonstrati ca:
P Q
P Q
P (Q R)
(P Q) R
P (P P)
P
P P
P
P (Q R)
P R
Q
(P Q) R
R Q
PQ
P R
Q R
P Q
Q R
P R
P (Q P)
P Q
Exc9 tema: Demonstrati ca:
Exc10: Demonstrati ca urmatoarele propozitii sunt tautologii:
P P
P P
(P Q) (P Q)
(P Q) (P R)
(P S)
S T
T
Exc11: Aratati ca urmatoarele perechi de propozitii sunt
demonstrabil echivalente:
P, P
PQ, Q P
PQ, (PQ)
Exc12: Demonstrati ca:
P (Q P) (P Q) P
{P (Q R), ( P R)} { R }