c2lmc6 logica

download c2lmc6 logica

of 41

  • date post

    06-Dec-2015
  • Category

    Documents

  • view

    224
  • download

    0

Embed Size (px)

description

c2lmc6 logicac2lmc6 logica

Transcript of c2lmc6 logica

  • Logica matematica si computationalaCursul II

    Claudia MURESANcmuresan11@yahoo.com

    Universitatea din BucurestiFacultatea de Matematica si Informatica

    Bucuresti

    2011-2012, semestrul I

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 1 / 41

  • 1 Multimi si functii

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 2 / 41

  • Multimi si functii

    Continuam recapitularea din sectiunea Multimi si functii.

    Amintim din primul curs si primul seminar faptul ca are sens sa ne referim laobiecte (elemente, multimi, clase) arbitrare, pentru care nu specificam undomeniu al valorilor.

    Amintim din primul seminar urmatoarea metoda de a demonstra ca douamultimi A si B satisfac incluziunea A B: A B ddaca, pentru oriceelement x , are loc implicatia x A x B.Amintim din primul seminar urmatoarea metoda de a demonstra ca douamultimi A si B sunt egale, provenita din faptul ca egalitatea de multimi esteechivalenta cu dubla incluziune ntre ele si din metoda descrisa imediat maisus pentru demonstrarea incluziunii ntre doua multimi: A = B ddaca, pentruorice element x , are loc echivalenta x A x B.

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 3 / 41

  • Multimi si functii

    Notatie

    Alaturarea de simboluri ! semnifica exista un unic, exista si este unic.

    Notatie

    Vom nota cu multimea vida, adica multimea fara elemente. Pastram notatiilecunoscute , si \ pentru reuniunea, intersectia si respectiv diferenta de multimi.De asemenea, pastram notatiile , (, si ) pentru incluziunile si incluziunilestricte dintre multimi n fiecare sens. Vom mai nota incluziunile stricte si cu sirespectiv , dar numai atunci cand precizarea ca este vorba de o incluziune strictasi nu poate avea loc egalitatea de multimi nu ne foloseste n cele prezentate.

    RemarcaEste evident faptul ca singura submultime a multimii vide este multimea vida.

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 4 / 41

  • Multimi si functii

    Notatie

    Pentru orice elemente a si b, notam cu (a, b) perechea ordonata formata din a sib.

    Definitie

    Pentru orice multimi A si B, se defineste produsul cartezian dintre A si B (numitsi produsul direct dintre A si B) ca fiind multimea {(a, b) | a A, b B}, notataA B.

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 5 / 41

  • Multimi si functii

    Remarca

    Se demonstreaza usor ca, pentru orice multime A, A = A = .De asemenea, se demonstreaza usor ca produsul cartezian este distributiv fata dereuniunea, intersectia si diferenta de multimi, adica, pentru orice multimi A, B siC , au loc egalitatile:

    A (B C ) = (A B) (A C ) si (B C ) A = (B A) (C A)A (B C ) = (A B) (A C ) si (B C ) A = (B A) (C A)A (B \ C ) = (A B) \ (A C ) si (B \ C ) A = (B A) \ (C A)

    Aveti ca tema pentru acasa demonstrarea tuturor acestor egalitati.

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 6 / 41

  • Multimi si functii

    Definitie

    Fie A si B multimi oarecare. Se numeste functie de la A la B un tripletf := (A,G ,B), unde G A B, a. ., pentru orice a A, exista un unic b B,cu proprietatea ca (a, b) G .Formal: (a A)(!b B)(a, b) G .Faptul ca f este o functie de la A la B se noteaza cu f : A B sau A f B.Multimea A se numeste domeniul functiei f , B se numeste codomeniul saudomeniul valorilor lui f , iar G se numeste graficul lui f .Pentru fiecare a A, unicul b B cu proprietatea ca (a, b) G se noteaza cuf (a) si se numeste valoarea functiei f n punctul a.

    Exemplu

    Care dintre urmatoarele corespondente este o functie de la A la B?f

    rrA

    rrrB

    ZZ~

    g

    rrA

    rrrB

    ZZ~XXz

    h

    rrA

    rrrB

    ZZ~XXz

    :

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 7 / 41

  • Multimi si functii

    Remarca

    Amintim din primul curs si primul seminar ca, oricare ar fi propozitiile (i. e.proprietatile, enunturile, afirmatiile) p si q:

    implicatia p q este echivalenta cu non p sau q, asadar:implicatia p q este adevarata ddaca p e falsa sau q e adevarataimplicatia p q este falsa ddaca p e adevarata si q e falsa

    Intr-adevar, echivalenta ntre p q si non p sau q se arata foarte usor:implicatia directa (p q implica non p sau q) se demonstreaza observandca, daca are loc p q, atunci, cand non p e falsa, adica p e adevarata,rezulta ca e adevarata si q, asadar, ori de cate ori p q este adevarata,rezulta ca si non p sau q este adevarata; implicatia inversa (non p sau qimplica p q) rezulta din faptul ca, daca non p sau q este adevarata,atunci, cand p este adevarata si deci non p este falsa, rezulta ca esteadevarata q, prin urmare implicatia p q este adevarata.

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 8 / 41

  • Multimi si functii

    Remarca

    Fie B o multime oarecare (poate fi vida si poate fi nevida). Atunci exista ounica functie f : B.Intr-adevar, o functie f : B trebuie sa fie un triplet f = (,G ,B), cuG B = , deci G = . Asadar, exista cel mult o functie f : B, anumef = (, ,B) este unica posibilitate. Sa aratam ca acest triplet satisface definitiafunctiei:

    (a )(!b B)(a, b) , i. e.:(a)[a (!b)(b B si (a, b) )].

    Pentru orice element a, proprietatea a este falsa, asadar, pentru orice elementa, implicatia [a . . .] este adevarata. Iar acest lucru nseamna exact faptulca ntreaga proprietate (a)[a . . .] este adevarata, deci f este functie. Prinurmare, exista o unica functie f : B, anume f = (, ,B).

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 9 / 41

  • Multimi si functii

    Remarca

    Fie A o multime nevida. Atunci nu exista nicio functie f : A .Intr-adevar, o functie f : A trebuie sa fie un triplet f = (A,G , ), cuG A = , deci G = . Asadar, daca ar exista o functie f : A , atunci amavea neaparat f = (A, , ). Sa vedem daca acest triplet verifica definitia functiei:

    (a A)(!b )(a, b) , i. e.:

    (a)[a A [[(b)(b si (a, b) )] si[(c)(d)((c si d si (a, c) si (a, d) ) c = d)]]].

    Oricare ar fi elementul b, proprietatea b este falsa, deci, oricare ar fielementele a si b, conjunctia (b si (a, b) ) este falsa, deci, oricare ar fielementul a, proprietatea (b)(b si (a, b) ) este falsa, asadar, oricare ar fielementul a, conjunctia care succede mai sus implicatiei avand ca antecedent pea A este falsa. In schimb, ntrucat A este nevida, rezulta ca proprietatea a Aeste adevarata pentru macar un element a. Prin urmare, implicatia [a A . . .]de mai sus este falsa pentru cel putin un element a, ceea ce nseamna ca ntreagaproprietate (a)[a A . . .] este falsa, si deci f nu este functie.

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 10 / 41

  • Multimi si functii

    Definitie

    Pentru orice multimi A si B, orice functie f : A B si orice submultimi X A siY B, se definesc:

    imaginea lui X prin f sau imaginea directa a lui X prin f , notata f (X ), estesubmultimea lui B: f (X ) = {f (x) | x X} Bf (A) = {f (a) | a A} B se mai noteaza cu Im(f ) si se numeste imaginealui f

    preimaginea lui Y prin f sau imaginea inversa a lui Y prin f , notata f 1(Y )(f (Y ) n unele carti, pentru a o deosebi de imaginea lui Y prin inversa f 1

    a lui f , care exista numai atunci cand f este inversabila, adica numai atuncicand f este bijectiva, pe cand preimaginea unei submultimi a codomeniuluipoate fi definita pentru orice functie), este submultimea lui A:f 1(Y ) = {x A | f (x) Y } A

    Remarca

    Evident, cu notatiile de mai sus, f 1(B) = A.

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 11 / 41

  • Functia caracteristica a unei submultimi a unei multimi

    Definitie

    Pentru orice multimi A si B, notam cu AB diferenta simetrica a lui A si B,anume: AB = (A \ B) (B \ A).

    Notatie

    Pentru orice multime T , vom nota cu P(T ) multimea partilor lui T , i. e.multimea submultimilor lui T : P(T ) = {X | X T}.

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012, semestrul I 12 / 41

  • Functia caracteristica a unei submultimi a unei multimi

    Tehnica de demonstratie pentru incluziunea sau egalitatea de multimi, amintita lanceputul acestui curs, poate fi adaptata la cazul particular al submultimilor uneimultimi date T , astfel:

    pentru stabilirea incluziunii ntre doua submultimi A si B ale lui T , n loc dea se demonstra ca, pentru orice element x , x A x B, este suficient sase demonstreze ca, pentru orice element x T , x A x B, ceea ce,conform metodei din cazul general, nseamna ca AT B T , dar, ntrucatA,B P(T ), avem ca A T = A si B T = B, si rezulta ca A B;pentru a stabili egalitatea a doua submultimi A si B ale lui T , n loc de a sedemonstra ca, pentru orice element x , x A x B, este suficient sa searate ca: pentru orice x T , x A x B, ceea ce, conform varianteidemonstratiei din cazul general, arata ca: A T = B T ; dar, ntrucatA,B P(T ), au loc: A T = A si B T = B, de unde rezulta ca A = B.

    Claudia MURESAN (Universitatea din Bucuresti) Curs II logica matematica si computationala 2011-2012