curs3.pdf logica propozitionala

Download Curs3.PDF Logica Propozitionala

Post on 07-Apr-2018

222 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • 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
  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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)

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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/3/2019 Curs3.PDF Logica Propozitionala

    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: ( ) ( )

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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.

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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) ?

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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.

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    15/48

    Reprezentarea unei tranzitii

    2

    1 3 1

    2

    3

    Efectul mutarii: p2on3 (notam cu

    starea urmatoare)Constrangeri de executie (starea anterioara):

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    16/48

    Reprezentarea unei tranzitii

    2

    1 3 1

    2

    3

    Efectul mutarii: p2on3 (notam cu

    starea urmatoare)Constrangeri de executie (starea anterioara):

    p1on2 p3on2 (piesa mutata e libera)

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    17/48

    Reprezentarea unei tranzitii

    2

    1 3 1

    2

    3

    Efectul mutarii: p2on3 (notam cu

    starea urmatoare)Constrangeri de executie (starea anterioara):

    p1on2 p3on2 (piesa mutata e libera)p1on3 p2on3 (piesa tinta e libera)

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    18/48

    Reprezentarea unei tranzitii

    2

    1 3 1

    2

    3

    Efectul mutarii: p2on3 (notam cu

    starea urmatoare)Constrangeri de executie (starea anterioara):

    p1on2 p3on2 (piesa mutata e libera)p1on3 p2on3 (piesa tinta e libera)

    Implicit: p2on0 p

    2on1 (2 nu va fi pe altceva)

    R i i ii

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    19/48

    Reprezentarea unei tranzitii

    2

    1 3 1

    2

    3

    Efectul mutarii: p2on3 (notam cu

    starea urmatoare)Constrangeri de executie (starea anterioara):

    p1on2 p3on2 (piesa mutata e libera)p1on3 p2on3 (piesa tinta e libera)

    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

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    20/48

    Reprezentarea unei tranzitii

    2

    1 3 1

    2

    3

    Efectul mutarii: p2on3 (notam cu

    starea urmatoare)Constrangeri de executie (starea anterioara):

    p1on2 p3on2 (piesa mutata e libera)p1on3 p2on3 (piesa tinta e libera)

    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

  • 8/3/2019 Curs3.PDF Logica Propozitionala

    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