1 logica propozitionala clasica

Upload: lucian-eu

Post on 02-Mar-2016

57 views

Category:

Documents


1 download

TRANSCRIPT

  • 1 Logica propoziional clasic

    Prof. univ. dr. Dumitru GHEORGHIU

  • Sintaxa LPCLimbajul LPC:n atomi propoziionali: p, q, r, s, p1, p2, , q1, q2, n operatori propoziionali: (negaie), & (conjuncie),

    (disjuncie), (condiional), (bicondiional)n semne tehnice: (, ), [, ]

    Atomii sunt variabile ale LPC: unui atom i se pot atribui valorile logice adevrat (1) sau fals (0).Operatorii sunt constante ale LPC, citite, respectiv, nu (nu este cazul c, nu este adevrat c, non-), i, sau, dac , atunci , dac i numai dac.

    2

  • Sintaxa LPC

    n Operatorii i & sunt primitivi.n Se numete formul a LPC orice ir de simboluri

    construit conform urmtoarelor reguli:(R1) Orice atom propoziional este formul (atomic)(R2) Dac A este o formul, atunci (A) este o

    formul (non-atomic)(R3) Dac A i B sunt formule, atunci (A & B) este

    formul (non-atomic)

    3

  • Sintaxa LPC

    n ((((p & q)) & (r))) este o formul, ((p &) q (rnu este o formul.

    n Dac A este o formul sau (A) este o formul, atunci A este aceeai formul cu (A). Astfel, formula de mai sus devine ((p & q) & r).

    n n absena parantezelor, are prioritate asupra &. De exemplu, formula (p & q) nseamn nu deopotriv p i q, n timp ce formula p & qnseamn deopotriv non-p i q.

    4

  • Sintaxa LPC

    n Urmtoarele clauze definesc subformulele unei formule:n Orice formul este propria sa subformuln Orice subformul a lui A este subformul a An Orice subformul a lui A sau B este subformul a

    lui A & Bn Fie A = (p & q). Subformulele lui A sunt p, q,

    p, q, p & q i (p & q). Ordinea de prezentare a acestora corespunde ordinii n care A a fost construit conform (R1)-(R3).

    5

  • Semantica LPCn n LPC exist doar dou valori logice: adevrat, notat cu 1, i

    fals, notat cu 0.n Definiiile semantice ale & i sunt date de urmtoarele tabele

    de adevr:Tabelul 2.1 Tabelul 2.2

    p q p & q p p1 1 1 1 01 0 0 0 10 1 00 0 0

    6

  • Semantica LPC

    n Operatorii , , . Pentru oricare dou formule A i B,n A B prescurteaz (A & B)n A B prescurteaz (A B)n A B prescurteaz ((A B) & (B A))

    n n absena parantezelor, are prioritate asupra &, , i .

    n Pe lng indicarea ordinii operaiilor, parantezele elimin ambiguitile. E.g., nu vom scrie p & q r, ci p & (q r) sau (p & q) r.

    7

  • Semantica LPCn Folosind tabelele 2.1 i 2.2, putem construi tabele de adevr

    pentru orice formul.

    Tabelul 2.3 Tabel de adevr pentru p q

    p q p q p & q (p & q) p q1 1 0 0 0 1 11 0 0 1 0 1 10 1 1 0 0 1 10 0 1 1 1 0 0

    8

  • Semantica LPC

    Tabelul 2.4 Tabel de adevr pentru p q

    p q p p q p q

    1 1 0 1 11 0 0 0 00 1 1 1 10 0 1 1 1

    9

  • Semantica LPC

    Tabelul 2.5 Tabel de adevr pentru p q

    p q p q q p (p q) & (q p) p q

    1 1 1 1 1 11 0 0 1 0 00 1 1 0 0 00 0 1 1 1 1

    10

  • Semantica LPC

    n Pentru oricare trei formule A, B, i C,n (A & B) & C este aceeai formul cu A & B & Cn (A B) C este aceeai formul cu A B C

    n ntruct formulele (A & B) & C i A & B & C au acelai tabel de adevr, parantezele pot fi eliminate, acelai fiind cazul cu formulele (A B) C .

    n Prin contrast, A & (B C) sau (A & B) C nu au acelai tabel de adevr, deci parantezele nu pot fi eliminate.

    11

  • Semantica LPC

    12

    n O interpretare este o funcie v care atribuie fiecrui atom una i numai una dintre valorile 1 i 0. Dac v atribuie unui atom pvaloarea 1, scriem v(p) = 1, iar dac v atribuie unui atom pvaloarea 0, scriem v(p) = 0.

    n Pentru o mulime de n atomi propoziionali exist 2n interpretri distincte.

    n Dat fiind o interpretare v, aceasta se extinde la o funcie, numit funcie de adevr i notat tot cu v, care atribuie fiecrei formule propoziionale o valoare logic (unic determinat).

    n Fie formula A = (p q) & r. n interpretarea n care v(p) = v(q) = 0 i v(r) = 1, v(A) = 1, iar n interpretarea n care v(p) = v(r) = 1 i v(q) = 0, v(A) = 0.

  • Semantica LPCn Fie A o formul i v o interpretare a formulei A. v este un model

    al formulei A, dac v(A) = 1. v este un contra-model al formulei A, dac v(A) = 0.

    n O formul A este valid, dac orice interpretare a formulei Aeste un model al formulei A. O formul este nevalid, dac exist cel puin un contra-model al formulei A.

    n O formul A este nerealizabil, dac orice interpretare a formulei A este un contra-model al formulei A. O formul A este realizabil, dac cel puin o interpretare a formulei A este un model al formulei A.

    13

    Formule realizabile i

    valide

    Formule realizabile i nevalide

    Formule nerealizabile

  • Semantica LPCn p (p & q) este realizabil, deoarece ia valoarea 1 n orice

    interpretare n care v(p) = 0, dar este nevalid, deoarece ia valoarea 0 n interpretarea n care v(p) = 1 i v(q) = 0.

    n p & p este nerealizabil. (p & p) i p p sunt valide.n Formulele valide se mai numesc tautologii sau legi logice.

    Formulele nerealizabile se mai numesc formule inconsistente. Formulele realizabile i nevalide se mai numesc formule contingente.

    n Pentru orice formul A, A este valid ddac A este nerealizabil i A este valid ddac A este nerealizabil.

    14

  • Semantica LPCn O interpretare v a unei mulimi de formule

    propoziionale G este un model al mulimii G, dac v(A) = 1 pentru orice formul A G.

    n O mulime de formule este realizabil, dac are cel puin un model i este nerealizabil, dac nu are nici un model.

    n {p, p q, p q} este realizabil, avnd modelul v(p) = 0, v (q) = 1.

    n {p, q, p q} este nerealizabil, deoarece pentru v(p) = v(q) = 1, avem v(p q) = 0.

    15

  • Semantica LPC

    n O formul B este consecin logic a formulei A, n simboluri A B, dac orice model al formulei A este model al formulei B.

    n Vom scrie A B, dac nu este cazul c A B.n Dac A B, atunci se mai spune c A implic logic B.n Fie A i B, dou formule oarecare:

    A & B A, A & B B, A A B, B A B.

    16

  • Semantica LPC

    n A B ddac A & B este nerealizabil.n Dac o formul A & B este realizabil, atunci A B.

    n acest caz spunem c orice model al formulei A &B este un contra-model al preteniei c A B.

    n ntruct interpretarea v(p) = 1, v(q) = 0 este model al formulei (p q) & q, aceast interpretare este un contra-model al preteniei c p q q.

    17

  • Semantica LPCn O formul B este consecin logic a unei mulimi de formule G,

    n simboluri G B, dac orice model al mulimii G este model al formulei B.

    n Fie A i B, dou formule oarecare:{A, B} A B, {A, A B} B, {A, A B } B.

    n G B ddac mulimea G {B} este nerealizabil.n Dac G {B} este realizabil, atunci G B. n acest caz,

    spunem c orice model al mulimii G {B} este contra-modelal preteniei c B este consecin logic din G.

    n ntruct interpretarea v(p) = 1, v(q) = v(r) = 0 este model almulimii {p q, q, r p, r}, aceast interpretare estecontra-model al preteniei c {p q, q, r p} r.

    18

  • Semantica LPCn Se spune c dou formule A, B sunt echivalente logic, n

    simboluri A B, dac orice model al formulei A este model al formulei B i reciproc. Prin definiie, A B ddac A B i B A.

    n Fie A i B, dou formule oarecare:A B B A, A B B A, A A.

    n Fie CA o formul care conine una sau mai multe apariii aleformulei A i CB o formul obinut din CA prin nlocuirea a celpuin unei apariii a formulei A cu formula B. Dac A B,atunci CA CB (Teorema nlocuirii).

    n Fie formula (p q) & q. ntruct p q q p, avem(p q) & q (q p) & q

    19

  • Metoda tabelelor de adevrn Este (p & (p q)) q realizabil?

    p q p q p & (p q) (p & (p q)) q1 1 1 1 1

    1 0 0 0 1

    0 1 1 0 1

    0 0 1 0 1

    20

  • Metoda tabelelor de adevrn Este ((p q) p) & p realizabil?

    p q p q (p q) p p ((p q) p) & p1 1 1 1 0 01 0 0 1 0 00 1 1 0 1 00 0 1 0 1 0

    21

  • Metoda tabelelor de adevrn Tabelele de adevr pot fi folosite i pentru a decide dac o

    formul este consecin logic a unei mulimi de formule.n Este p este consecin logic din {p q, q}?n {p q, q} p ddac mulimea de formule {p q, q, p}

    este nerealizabil.

    22

    p q p q q p1 1 1 0 11 0 0 1 10 1 1 0 00 0 1 1 0

  • Unele reguli semantice ale LPCn Urmtoarele dou echivalene exprim idempotena & i :

    (1) A & A A(2) A A A

    n Urmtoarele dou echivalene exprim regulile distributivitiipentru & i :

    (3) (A & (B C)) ((A & B) (A & C))(4) (A (B & C)) ((A B) & (A C))

    n Urmtoarele dou echivalene exprim regulile lui De Morgan:(5) (A & B) (A B)(6) (A B) (A & B)

    23

  • Metoda formelor normalen Un literal este un atom sau negaia unui atom. Atomii fr

    negaie se numesc literali pozitivi, iar atomii cu negaie se numesc literali negativi .

    n O clauz disjunctiv este o disjuncie de literali L1 Ln, n 1, iar o clauz conjunctiv este o conjuncie de literali L1 & &Ln, n 1.

    n O formul n form normal conjunctiv (FNC) este o conjuncie de clauze disjunctive C1 & & Cm, m 1.

    n O formul n form normal disjunctiv (FND) este o disjuncie de clauze conjunctive C1 Cm, m 1.

    24

  • Metoda formelor normale

    n FNC i FND se identific atunci cnd formula este un literal i atunci cnd formula este o conjuncie sau o disjuncie de literali.

    n (p q) & (r s) & (p q r) este n FNC.

    n (p & q) r (q & r) este n FND.

    n p q este att n FNC, ct i n FND.n (p q) & ((p & r) (q & s)) nu este nici n FNC, nici

    n FND.

    25

  • Metoda formelor normaleAlgoritmul de normalizare

    1. B C (B C) & (C B)2. B C B C3. B B regula dublei negaii4. (B & C) B C regula lui De Morgan pentru &5. (B C) B & C regula lui De Morgan pentru 6. B & (C D) (B & C) (B & D) distributivitatea & fa de 7. B (C & D) (B C) & (B D) distributivitatea fa de &8. B & B B idempotena &9. B B B idempotena 10. B & (C C ) B simplificare11. B (C & C ) B simplificare

    26

  • Metoda formelor normaleAlgoritmul de normalizare

    n nlocuiete orice sub-formul de forma B C cu (B C ) & (C B) i orice sub-formul de forma B C cu B C

    n nlocuiete orice sub-formul de forma B cu B, orice sub-formul de forma (B & C) cu B C i orice sub-formul de forma (B C) cu B & C.

    n Pentru a obine o formul n FNC, nlocuiete orice sub-formul de forma B (C & D) sau (C & D) B cu (B C) & (B D).

    n Pentru a obine o formul n FND, nlocuiete orice sub-formul de forma B & (C D) sau (C D) & B cu (B & C) (B & D).

    n Orice formul propoziional este echivalent logic cu o formul n FNC i cu o formul n FND.

    27

  • Metoda formelor normalen S se normalizeze (p q) (q & p)1. Eliminm :

    (p q) (q & p)2. De Morgan pentru :

    (p & q) (q & p) FND3. Distributivitatea fa de &:

    [(p & q) q] & [(p & q) p]4. Distributivitatea fa de &:

    (p q) & (q q) & (p p) & (q p) FNC5. Idempotena i simplificarea:

    (p q) & q & (q p) FNC

    28

  • Metoda formelor normale

    n O clauz disjunctiv C este valid ddac exist cel puin un atom x astfel nct x C i x C

    n O formul n FNC este valid ddac toate clauzele sale sunt valide

    n O clauz conjunctiv, C, este nerealizabil ddac exist cel puin un atom x astfel nct x C i x C

    n O formul n FND este nerealizabil ddac toate clauzele sale sunt nerealizabile

    29

  • Metoda formelor normaleAlgoritmul de decizie prin forme normale

    1. Se aduce A la FNC:n Dac FNC este valid, atunci A este validn Dac nu acesta este cazul, se aduce A la FND; dac FND

    este nerealizabil, atunci A este nerealizabiln Dac nici acesta nu este cazul, atunci A este contingent

    2. Se aduce A la FND:n Dac FND este nerealizabil, atunci A este nerealizabiln Dac nu acesta este cazul, se aduce A la FND; dac FND

    astfel obinut este nerealizabil, atunci A este validn Dac nici acesta nu este cazul, atunci A este contingent

    30

  • Metoda formelor normalen S se decid dac [(p q) p] p este valid1. Eliminm :

    [(p q) p] p[(p q) p] p[(p q) p] p

    2. De Morgan pentru i eliminarea dublei negaii:[(p q) & p] p[(p q) & p] p

    3. Distributivitatea fa de &:(p p q) & (p p) FNC

    ntruct FNC este valid, formula iniial este valid.

    31

  • Metoda formelor normale

    n Fie G = {A1, , An}. G B ddac formula A1 & & An & B este nerealizabil

    n Pentru a decide dac {A1, , An} B:n formm conjuncia A1 & & An & Bn aducem aceast conjuncie la FND in aplicm algoritmul de decizie prin forme

    normale.

    32

  • Metoda formelor normalen S se decid dac p & q, (p & r) r1. p & q & (p & r) & r2. De Morgan pentru & i eliminarea dublei negaii:

    p & q & (p r) & r3. Distributivitatea & fa de :

    p & q & [(r & p) (r & r)]4. Distributivitatea & fa de :

    (p & q & r & p) (p & q & r & r) FND

    n ntruct FND este nerealizabil, p & q, (p & r) r

    33

  • Metoda rezoluiein Pentru concizie, n loc de clauz disjunctiv

    vom scrie clauzn Clauzele sunt considerate mulimi de literali;

    formulele in FNC sunt considerate mulimi de clauze

    n (p q r) & (r s) & p & (q s) devine

    {{p, q, r}, {r, s}, {p}, {q, s}}

    34

  • Metoda rezoluiein Dou clauze, C1 i C2, se numesc x-rezolubile dac exist cel

    puin un atom x astfel nct x C1 i x C2.n {p, q, r} i {q, s} sunt q-rezolubile, {p, q, r} i {r, s} sunt

    r-rezolubile.n Fie C1 i C2 clauze x-rezolubile. Se numete rezolventul clauzelor

    C1 i C2 n raport cu x, rezx(C1, C2), clauza obinut prin reuniunea clauzei C1 din care am eliminat atomul x cu clauza C2din care am eliminat pe x:

    rezx(C1, C2) = {C1 - {x} C2 - {x}}n Rez(C1, C2) denot mulimea tuturor rezolvenilor clauzelor C1 i

    C2.

    35

  • Metoda rezoluiein C1 = {p, q, r} i C2 = {q, r, s}.

    n rezq(C1, C2) = {p, r, r, s}n rezr(C1, C2) = {p, q, q, s}n Rez(C1, C2) = {{p, r, r, s}, {p, q, q, s}}.

    n Fie C1 i C2 clauze x-rezolubile. Rezolventul n raport cu x al clauzelor C1 i C2 este consecin logic a mulimii {C1, C2}:

    {C1, C2} rezx(C1, C2).n Fie o mulime de clauze, S, i o clauz C. O derivare prin

    rezoluie a clauzei C din S este un ir finit de clauze C1, , Cn, astfel nct Cn = C i pentru orice Ci, 1 i n, sau Ci S, sau Ci Rez(Cj, Ck), unde j, k < i.

    n Dac exist o derivare prin rezoluie a clauzei C din S, atunci scriem S Rez C.

    36

  • Metoda rezoluiein C1 = {p, q, s}, C2 = {p, q, r, s}, C3 = {q, r}, C4 = {p}, C =

    {r}n Urmtorul ir de clauze arat c {C1, C2, C3, C4} Rez C:

    1. {p, q, s} C12. {p, q, r, s} C23. {p, q, r} din 1, 2, rezs4. {q, r} C35. {p, r} din 3, 4, rezq6. {p} C47. {r} din 5, 6, rezp

    n Dac S Rez C, atunci S C.

    37

  • Metoda rezoluiein Se numete clauza vid, , mulimea vid de literali.

    Pentru orice atom x, poate fi obinut numai ca rezolvent al clauzelor {x} i {x}.

    n ntruct nu are membri care s ia valoarea 1, este nerealizabil.

    n Dac S Rez C i clauza C este nerealizabil, atunci Seste nerealizabil.

    n n particular, dac S Rez , atunci S este nerealizabil.n ncercarea de a deriva prin rezoluie clauza vid dintr-o

    mulime de clauze este esena metodei rezoluiei.

    38

  • Metoda rezoluiein (p q r) & p & (p q r) & (p q)n C1 = {p, q, r}, C2 = {p}, C3 = {p, q, r}, C4 = {p, q}

    n C5 = rezr(C1, C3) = {p, q}n C6 = rezq(C4, C5) = {p}n C7 = rezp(C2, C6) =

    n Putem continua obinerea de rezolveni:n C8 = rezp(C1, C2) = {q, r}n C9 = rezp(C2, C5) = {q}n ........................................

    39

  • Metoda rezoluiein Pentru a decide prin rezoluie dac o formul A este sau nu

    valid, lucrm cu formula A, pe care o aducem la FNC.n S se decid dac (p & (p q)) q este valid1. [(p & (p q)) q]2. p & (p q) & q FNC3. C1 = {p}, C2 = {p, q}, C3 = {q}

    n C4 = rezp(C1, C2) = {q}n C5 = rezq(C3, C4) =

    n [(p & (p q)) q] este nerealizabil, deci (p & (p q)) qeste valid.

    40

  • Metoda rezoluiein Pentru a decide dac {A1, , An} B:

    n formm conjuncia A1 & & An & Bn aducem aceast conjuncie la FNC in aplicm metoda rezoluiei

    n S se decid dac {p, q} p & q1. p & q & (p & q)2. p & q & (p q) FNC3. {{p}, {q}, {p}, {q}}

    n ntruct aceast mulime este nerealizabil, {p, q} p & q

    41