1 logica propozitionala clasica

Download 1 Logica Propozitionala Clasica

Post on 02-Mar-2016

35 views

Category:

Documents

0 download

Embed Size (px)

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)