curs3.pdf logica propozitionala

8/3/2019 Curs3.PDF Logica Propozitionala
1/48
Fundamente de informatica
Logica propozitionala
Marius Minea
[email protected]
http://www.cs.upt.ro/~marius/curs/fi
21 octombrie 2011
http://www.cs.upt.ro/~marius/curs/fihttp://www.cs.upt.ro/~marius/curs/fihttp://www.cs.upt.ro/~marius/curs/fihttp://www.cs.upt.ro/~marius/curs/fi

2/48
De ce logica
E necesara n programare si dincolo de ean rationamente, argumente, etc.
Logica propozitionala e unul din cele mai simple limbaje
asa cum codificam numere, etc. n bitiputem exprima probleme prin formule n logica
Problema de azi: fiind data o formula, poate fi adevarata ?(realizabilitate, engl. satisfiability) SAT checking

3/48
Ce stim despre logica?
Stim deja: operatorii logici SI (), SAU (), NU ()
p pF T
T F
negatie NU
p
qp q F T
F F F
T F T
conjunctie SI
p
qp q F T
F F T
T T T
disjunctie SAU

4/48
Implicatia logica
p q
Semnificatie: daca p e adevarat, atunci q e adevarat (if-then)daca p nu e adevarat, nu stim nimic despre q (poate fi oricum)
Deci, p q e fals doar daca p e adevarat si q e fals(q ar trebui sa fie adevarat)
p
qp q F T
F T T
T F T
Atentie!fals
implica orice! un rationament cu o veriga falsa poate duce la orice concluzie
Implicatia nu nseamna cauzalitateun fapt adevarat implica orice fapt adevarat (fara legatura)
fals implica orice

5/48
Logica propozitionala, mai riguros
Limbajul logicii propozitionale: format din simboluripentru
propozitii: p, q, r, etc.operatori (conectori logici): , paranteze ( )
Formulele logicii propozitionale:
orice propozitie atomica este o formuladaca este o formula, atunci () este o formula.daca si sunt formule, atunci ( ) este o formula.
Operatorii cunoscuti pot fi definiti folosind si :
def= ( )
def=
def= ( ) ( )
(am renuntat la parantezele redundante)

6/48
Calculul n logica: functii de adevar
O functie de adevar v: atribuie la orice formula o valoare de adevar{T,F} astfel ncat:
v(p) e definita pentru fiecare propozitie atomica p.
v() =
T daca v() = FF daca v() = T
v( ) = F daca v() = T si v() = FT n caz contrar
O interpretare a unei formule = o evaluare pentru propozitiile ei
O intrepretare satisface o formula daca o evalueaza la T.(interpretarea e un model pentru formula respectiva).
O formula poate fi:valida (tautologie): adevarata n toate interpretarilerealizabila (satisfiable): adevarata n cel putin o interpretarenerealizabila (contradictie): falsa n orice interpretare

7/48
Implicatia logica (adevarul logic)
O multime de formule H = {1, . . . , n} implica o formula
H |=
daca orice functie de adevar care satisface H (formulele din H)
satisface
Pentru a stabili implicatia logica trebuie sa interpretam formulele(cu valori/functii de adevar)
lucram cu semantica (ntelesul) formulelor

8/48
Deductii logice
O varianta de a stabili adevarul unei formule n mod sintactic(folosind doar structura ei)
bazata pe o regula de deductie
1 1 22 modus ponens
(din 1 si 1 2 deducem 2)
si un set de axiome(formule care pot fi folosite ca premise/ipoteze)
A1: ( )A2: ( ( )) (( ) ( ))A3: ( ) ( )

9/48
Realizabilitatea unei formule propozitionale (satisfiability)
Se da o formula nlogica propozitionala
.Exista vreo atribuire de valori de adevar care o face adevarata ?= e realizabila (engl. satisfiable) formula ?
(a b d)
(a b) (a c d) (a b c)
Gasiti o atribuire care satisface formula?
Formula e n forma normala conjunctiva (conjunctive normal form)= conjunctie de disjunctii de literale (pozitive sau neg)
Fiecare conjunct (linie de mai sus) se numeste clauza

10/48
De ce e importanta?
Practic:
In probleme de decizie / constrangere:Putem gasi o solutie la . . . cu proprietatea . . . ?
conditiile se pot exprima ca formule n logica
n verificarea de circuite (ex. optimizam functia f n fopt)f(v1, ...,vn) = fopt(v1, ..., vn) e echivalent cuf(v1, ...,vn) fopt(v1, ..., vn) = 0 e corect daca f fopt NU poate fi adevarata
n verificarea de software (model checking), testare, depanare n biologie (determinari genetice), etc.

11/48
De ce e importanta?
Teoretic:E prima problema demonstrata a fi NP-completa.(probleme care se crede ca nu au solutii polinomiale)
O problema e NP-completa daca
o solutie poate fi verificata n timp polinomial (e n NP)(a verifica o solutie e mult mai usor decat a o gasi!)
daca se rezolva polinomial, atunci si orice alta problema din NP.
Cum demonstram ca o problema e NP-completa (grea) ?
reducem o problema cunoscuta la problema studiata daca s-ar putea rezolva polinomial problema noua,atunci s-ar putea rezolva si problema cunoscuta

12/48
Aplicatie: Planificarea
= un termen general pentru probleme de luare de decizie
Exemple:deplasarile unor roboti inteligenticomportamentul sistemelor autonome (sonde spatiale)rezolvarea de probleme (de tip puzzle, jocuri, etc.)
In general: ntr-un sistem descris prin stari si actiuni (tranzitii),
cum gasim o cale de la o stare initiala la o stare tinta (finala) ?

13/48
Exemplu: lumea blocurilor
3
2
1
5
4
1
2
3
4
5
Actiuni: mutarea unui bloc liber pe alt bloc.
Ce actiuni trebuie efectuate ? Care e numarul minim de actiuni ?
! Starile si tranzitiilesistemului se pot reprezenta ca formule logice

14/48
Reprezentarea unei stari
Putem folosi propozitii (variabile boolene):
2
1 3 p2on1 p1on0 p3on0 (2 e pe 1; 1 si 3 pe masa)
Avem nevoie de: n (n 1) propozitii pentru perechi de n obiecte,plus n propozitii care exprima daca un obiect e pe masa (nr. 0)
scriem si propozitiile neadevarate (din totalul de n2 propozitii)p1on2 p1on3 p2on0 p2on3 p3on1 p3on2
Sau: reprezentam pe ce se afla fiecare piesa:
base1 = 0 base2 = 1 base3 = 0ntregi, codificati n binar total n log n biti (propozitii)
Codificarea mai compacta nu duce neaparat la rezolvare eficienta.

15/48
Reprezentarea unei tranzitii
2
1 3 1
2
3
Efectul mutarii: p2on3 (notam cu
starea urmatoare)Constrangeri de executie (starea anterioara):

16/48
2
1 3 1
2
3
p1on2 p3on2 (piesa mutata e libera)

17/48
2
1 3 1
2
3
p1on2 p3on2 (piesa mutata e libera)p1on3 p2on3 (piesa tinta e libera)

18/48
2
1 3 1
2
3
Implicit: p2on0 p
2on1 (2 nu va fi pe altceva)
R i i ii

19/48
2
1 3 1
2
3
Implicit: p2on0 p
2on1 (2 nu va fi pe altceva) p
1on2 p
3on2 (nu va fi altceva pe 2) p
1on3 (nu va fi altceva pe 3)
R i i ii

20/48
2
1 3 1
2
3
Implicit: p2on0 p
2on1 (2 nu va fi pe altceva) p
1on2 p
3on2 (nu va fi altceva pe 2) p
1on3 (nu va fi altceva pe 3)
Valorile raman la fel pentru perechile neimplicate:p1on0 = p1on0 p
3on0 = p3on0 p
3on1 = p3on1
Conjunctia relatiilor descrie mutarea lui 2 pe 3, n toate cazurile
F tii i l tii

21/48
Functii si relatii
O functie F : A B de pe multimea A la multimea Basociaza fiecarui element din A un unic element din B.
O relatie R ntre multimile A si B e o submultime a produsuluicartezian A B: R A B

curs3.pdf logica propozitionala

Documents

Curs3 [Compatibility Mode]

Curs3-Notiuni Introductive MS Office 2007

I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

Curs3 - CATIA

ºiLo icã Arumentare g - PROFESOR Solomon Laura · PDF file 2020. 5. 9. · logica matematicã, logica sim bolicã, logica polivalentã, logica deonticã, logica întrebã rilor º.a

Curs3-Inginerie citotisulara

oftalmologie curs3-refractia oculara

curs3 fiziologie

Curs3 risc

curs3 cap1-12.pdf

snv-curs3 - farmaco

Anomalii Ale Hemostazei- Curs3

Porturi curs3

Curs3-Inginerie Citotisulara (1)

Vraciu - Logica 1 (Logica Propozitiilor).pdf

Structuri discrete - Curs3: Relații

limba engleza - curs3.pdf

Paradigme de Logicaogica cu predicate de ordinul 1 (FOL)cu predicate de ordinul 1 (FOL) • Extinde logica propozitionala (unde universul discursului e descris prin propozitii declarative,

An2 Programare-Orientata-obiect Curs3

Curs3 Amg Bpoc