Lógica

Cálculo Proposicional

Introdução

2

�� �� �Lógica - Definição

Formalização de alguma linguagem� Sintaxe

Especificação precisa das expressões legais

� SemânticaSignificado das expressões

� DeduçãoProvê regras que preservam a semântica

3

�� �� �Cálculo Proposicional - CP

� Cálculo Proposicional ≡ Lógica Proposicional

� Apenas enunciados declarativos são permitidos

� Excluídas sentenças exclamativas, imperativas e interrogativas

4

�� �� �Termo

É usado para designar objetos

Exemplos:� Paula

� Um filme de terror

� Triângulo retângulo

5

�� �� �Proposição

É uma sentença declarativa que pode assumir os valores verdade (v) ou falso (f)

Exemplos:� Todo homem é mortal� Meu carro é um fusca� Está chovendo

6

�� �� �Proposição Atômica

Sentença que não contém conectivos(e, ou, se...então, ...)

� Todo homem é mortal.� Meu carro é um fusca.� Está chovendo.

7

�� �� �Proposição Composta

Sentença que contém um ou mais conectivos (e, ou, se...então, ...)

� Se Maria estuda então fará bons exames.� Ele come e dorme.� Pedro dança ou canta.

8

�� �� �Proposição - Cuidado!

� A expressão:

A distância entre Paraty e Ubatuba

não é uma sentença pois não possui valorverdade verdadeiro (v) ou falso (f).

9

�� �� �Conceitos Adicionais

� Proposição atômica ≡ átomo� Proposições atômicas são designadas por

letras latinas minúsculas (p, q, r, ...)� Literal é um átomo ou a negação de um

átomo� Conectivos ou Juntores: permitem a

construção de proposições compostas

10

�� �� �Conectivos

Conectivos ou Juntores:� e ∧� ou ∨� não ¬� condicional →� bicondicional ⇔

11

�� �� �Conectivo: e (∧)

� A partir de duas proposições, obtém-se uma terceira denominada conjunção:

� Exemplo:(p) Maria estuda o problema.(q) José vai pescar.

Conjunção de (p) e (q): p ∧ qMaria estuda o problema e José vai pescar.

12

�� �� �Conectivo: ou (∨)

� A partir de duas proposições, obtém-se uma terceira denominada disjunção:

� Exemplo:(p) Maria estuda o problema.(q) José vai pescar.

Disjunção de (p) e (q): p ∨ qMaria estuda o problema ou José vai pescar.

13

�� �� �Conectivo: não (¬)

� Nega o valor-verdade de uma proposição

� Exemplo:(p) Maria estuda o problema.

Negação de (p): ¬pnão (Maria estuda o problema).

14

�� �� �Conectivo: condicional (→)

� Conectivo condicional lido como se...então� A partir de duas proposições, obtém-se uma

terceira denominada condicional ou implicação

� Proposição à esquerda de → denomina-se premissa ou antecedente

� Proposição à direita de → denomina-se conclusão ou conseqüente

15

�� �� �Conectivo: condicional (→)

� Exemplo:(p) Eu como muito.(q) Eu engordo.

Condicional de (p) e (q): p → qSe eu como muito então eu engordo.

16

�� �� �Conectivo: bicondicional (⇔)

� Conectivo bicondicional lido como se e somente se

� A partir de duas proposições, obtém-se uma terceira denominada bicondicional

17

�� �� �Conectivo: bicondicional (⇔)

� Exemplo:(p) Um triângulo é retângulo(q) Um triângulo tem um ângulo reto.

Bicondicional de (p) e (q): p ⇔ qUm triângulo é retângulo se e somente se tem

um ângulo reto.

18

�� �� �Semântica dos Conectivos

p q p∧q p∨q ¬p p→q p⇔q

v v v v f v v

v f f v f f f

f v f v v v f

f f f f v v v

19

�� �� �Fórmulas Bem Formadas (wff)

� Fórmulas construídas através dacombinaçao válida de símbolos

� Fórmulas Bem Formadas = Well FormedFormula = wff

� Para representar wff são usadasmetavariáveis proposicionais representadas pelas letras α, β, γ, etc

� Cada expressão envolvendo α, β, γ, etc échamada de forma sentencial

20

�� �� �Definição wff

1. um átomo é uma wff2. se α e β são wff, então são também wff:

wff lê-se¬α não αα ∧ β α e βα ∨ β α ou βα → β se α então βα ⇔ β α se e somente se β

3. As únicas wff são definidas por (1) e (2).

21

�� �� �Prioridade dos Conectivos (1 de 2)

¬∧∨→⇔

22

�� �� �Prioridade dos Conectivos (1 de 2)

¬∧∨→⇔

maior prioridade

menor prioridade

23

�� �� �Prioridade dos Conectivos (2 de 2)

� Exemplos:α → β ∨ γ significa α → (β ∨ γ)α ∨ β ∧ γ significa α ∨ (β ∧ γ)α → β ∧ ¬γ ∨ δ significa α → ((β ∧ (¬γ)) ∨ δ)

� A precedência pode ser alterada pelo uso de parênteses.

24

�� �� �Variações de Notação

Item Adotada Outras� e p∧q p&q p.q p,q � ou p∨q p|q p+q p;q� não ¬p ~p p� condicional p→q p⇒q p⊃q q←p� bicondicional p⇔q p↔q p≡q

25

�� �� �Semântica do CP

� Consiste na interpretação de suas fórmulas, ou seja, atribuição dos valores-verdade (v ou f) às formulas atômicas, por exemplo:

(p v q) → (p ∧ q)

� Como a fórmula possui 2 componentes atômicos ela admite 22 interpretações. Para uma fórmula de n componentes tem-se 2n

interpretações .

26

�� �� �Validade e Inconsistência (1 de 5)

� Se uma fórmula β tem valor v numa interpretação I, então β é verdadeira na interpretação I.

Ex: p q p ∧ qI1. v v vI2. v f fI3. f v fI4. f f f

(p ∧ q) é verdadeira na interpretação I1

27

�� �� �Validade e Inconsistência (2 de 5)

� Se uma fórmula β é verdadeira segundo alguma interpretação, então β é satisfatível(ou consistente).

Ex: p q p ∧ qI1. v v vI2. v f fI3. f v fI4. f f f

(p ∧ q) é satisfatível

28

�� �� �Validade e Inconsistência (3 de 5)

� Uma fórmula β é válida (tautologia) quando for verdadeira em todas suas interpretações

Ex: p ∨ ¬p

29

�� �� �Validade e Inconsistência (4 de 5)

� Se uma fórmula β tem valor f numa interpretação I, então β é falsa na interpretação I.

Ex: p q p ∧ qI1. v v vI2. v f fI3. f v fI4. f f f

(p ∧ q) é falsa nas interpretações I2, I3 e I4.

30

�� �� �Validade e Inconsistência (5 de 5)

� Uma fórmula β é insatisfatível (ou inconsistente ou contradição) quando for falsa segundo qualquer interpretação I.

Ex: p ∧ ¬p� Uma fórmula β é inválida quando for falsa

segundo alguma interpretação I.Ex: p ∧ q� Fórmulas que não são tautologias nem

contradições são chamadas contingentes.

31

�� �� �Exercícios

� Provar usando tabela verdade que:

1. (p ∧ ¬p) é inconsistente e portanto inválida.2. (p ∨ ¬p)é valida e portanto consistente.3. (p → ¬p)é inválida, ainda que consistente.

32

�� �� �Conseqüência Lógica (1 de 2)

� Sejam α, β1, β2, ..., βn wff. Diz-se que α éconseqüência lógica de β1, β2, ..., βn se, e somente se, para qualquer interpretação em que β1, β2, ..., βn forem simultaneamente verdadeiras, α é também verdadeira.

� Se α é conseqüência lógica de β1, β2, ... βn,, diz-se que α segue-se logicamente de β1, β2, ... βn,.

Notação: β1, β2, ..., βn � α

33

�� �� �Conseqüência Lógica (2 de 2)

� Teorema 2.7.1: α é conseqüência lógica de β1, β2, ..., βn se e somente se:

β1 ∧ β2 ∧ ... ∧ βn → α é uma tautologia

� Teorema 2.7.2: α é conseqüência lógica de β1, β2, ..., βn se e somente se:

β1 ∧ β2 ∧ ... ∧ βn ∧ ¬α é uma contradição

34

�� �� �Equivalência Lógica

� Uma fórmula α é logicamente equivalente (≡) a uma fórmula β quando α for conseqüência lógica de β e β for conseqüência lógica de α:

α≡β se e somente se α⇔β é uma tautologia

35

�� �� �Exercício

� Provar que (p → q) é equivalente a (¬p ∨ q) p q p→q ¬p∨q (p→q)⇔(¬p∨q)

v v v v v

v f f f v

f v v v v

f f v v v

36

�� �� �Argumento

� Argumento é uma sequência α1, α2, ..., αn(n ≥1) de proposições, onde:αi (1 ≤ i ≤ n-1) são chamadas premissas eαn denomina-se conclusão.

� Notação:α1, α2, ..., αn-1 � αn.

37

�� �� �Argumento Válido (1 de 2)

� Um argumento α1, α2, ..., αn-1 � αn é válidose e somente se:α1 ∧ α2 ∧ ... ∧ αn-1 → αn for uma tautologia

ou equivalentemente,

α1 ∧ α2 ∧ ... ∧ αn-1 � αn

38

�� �� �Argumento Válido (2 de 2)

Um argumento válido pode ser lido como:

� α1, α2, ..., αn-1 acarretam αn ou� αn decorre de α1, α2, ..., αn-1 ou� αn é conseqüência lógica de α1, α2, ..., αn-1

� Para n=1, o argumento é valido se e somente se α1 for tautológica

39

�� �� �Princípio da Substituição (1 de 2)

� Subfórmulas: dada a fórmula

α: (p → q) ⇔ r, entãop → q, p, q, r, são as subfórmulas de α.

� O princípio afirma que uma subfórmula de uma fórmula α, ou toda a fórmula α, pode ser substituída por uma fórmula equivalente e que a fórmula resultante é equivalente a α.

40

�� �� �Princípio da Substituição (2 de 2)

� Exemplo: pelo princípio da substituição, a fórmula

α: (p v q) ∧ (p v r)

é equivalente a:

ϒ: (¬p → q) ∧ (¬p → r).

41

�� �� �Propriedades (1 de 5)

� Existem várias propriedades da negação, conjunção e disjunção.

� Estas propriedades podem ser verificadas como equivalências lógicas.

� Para demonstrar cada uma, basta utilizar as tabelas-verdade, constatando a tautologia.

42

�� �� �Propriedades (2 de 5)

� Propriedades da Conjunção

associativa α ∧ (β ∧ϒ) ≡ (α ∧ β) ∧ ϒcomutativa α ∧ β ≡ β ∧ αidempotente α ∧ α ≡ αpropriedadede v(erdade)

α ∧ v ≡ α

propriedadede f(also)

α ∧ f ≡ f

43

�� �� �Propriedades (3 de 5)

� Propriedades da Disjunção

comutativa α v β ≡ β v α associativa α v (β v ϒ) ≡ (α v β) v ϒidempotente α v α ≡ αpropriedadede v(erdade)

α v v ≡ v

propriedadede f(also)

α v f ≡ α

44

�� �� �Propriedades (4 de 5)

� Distributivasα ∧ (β ∨ ϒ) ≡ (α ∧ β) ∨ (α ∧ ϒ)α ∨ (β ∧ ϒ) ≡ (α ∨ β) ∧ (α ∨ ϒ)

� Negação¬ (¬α) ≡ α

� Absorçãoα ∨ (α ∧ β) ≡ αα ∧ (α ∨ β) ≡ α

45

�� �� �Propriedades (5 de 5)

� De Morgan¬ (α ∧ β) ≡ ¬α ∨ ¬β¬ (α ∨ β) ≡ ¬α ∧ ¬β

� Equivalência da Implicaçãoα → β ≡ ¬α ∨ β

46

�� �� �

Fórmulas Proposicionais Equivalentes (1 de 2)

Nome da Regra Regramodus ponens α, α → β |= βmodus tollens α → β, ¬β |= ¬α

silogismo hipotético(ou regra da cadeia)

α → β, β → γ |= α → γ

silogismo disjuntivo α ∨ β, ¬α |= βdilema construtivo α → β, γ → δ, α ∨ γ |= β ∨ δdilema destrutivo α → β, γ → δ, ¬β ∨ ¬γ |= ¬α ∨ ¬γ

simplificação α ∧ β |= αconjunção α, β |= α ∧ β

adição α |= α ∨ βcontraposição α → β |= ¬β → ¬α

exportação α → (β → γ) |= (α ∧ β) → γimportação (α ∧ β) → γ |= α → (β → γ)

47

�� �� �

Fórmulas Proposicionais Equivalentes (2 de 2)

� Exemplo da forma de leitura modus ponens:

α, α→ β � β

caso α seja verdadee α→ β seja verdade,obrigatoriamente β será verdade.

48

�� �� �

Verificação de Validade de Argumentos (1 de 2)

� Sejam α1, α2, ..., αn, β fórmulas do CálculoProposicional. Uma sequência finita de proposições C1, C2, ..., Cκ é uma prova ou dedução de β, a partir das premissas α1, α2, ..., αn , se e somente se:

49

�� �� �

Verificação de Validade de Argumentos (2 de 2)

cada Cι é uma premissa αj (1 ≥ j ≥ n), ouCι provém das fórmulas precedentes, pelo uso de um argumento válido das regras de inferência, ouCι provém do uso do princípio de substituição numa fórmula anterior, ouCκ é β

� Diz-se então que β é dedutível de α1, α2, ..., αn ou que β é um teorema.

50

�� �� �Exemplo (1 de 3)

Se as uvas caem, então a raposa as come.

Se a raposa as come, então estão maduras.

As uvas estão verdes ou caem.

Logo,

A raposa come as uvas se e só se as uvas caem.

51

�� �� �Exemplo (2 de 3)

Se as uvas caem, então a raposa as come. (C1)

Se a raposa as come, então estão maduras. (C2)

As uvas estão verdes ou caem. (C3)

Logo,

A raposa come as uvas se e só se as uvas caem.

p: as uvas caem Premissas:

q: a raposa come as uvas C1: p → q

r: as uvas estão maduras C2: q → r

(¬r: as uvas estão verdes) C3: ¬r ∨ p

52

�� �� �Exemplo (3 de 3)

Premissas:

C1: p → q Provar que:

C2: q → r p → q, q → r, ¬r ∨ p |= p ↔ q

C3: ¬r ∨ p

Deduz-se que:

C4: r → p (C3: equivalência)

C5: q → p (C2 + C4: regra da cadeia)

C6: p → q ∧ q → p (C1 + C5: conjunção)

C7: p ↔ q (C6: equivalência)