Lgica
Clculo Proposicional
Introduo
2
Lgica - Definio
Formalizao de alguma linguagem Sintaxe
Especificao precisa das expresses legais
SemnticaSignificado das expresses
DeduoProv regras que preservam a semntica
3
Clculo Proposicional - CP
Clculo Proposicional Lgica Proposicional
Apenas enunciados declarativos so permitidos
Excludas sentenas exclamativas, imperativas e interrogativas
4
Termo
usado para designar objetos
Exemplos: Paula
Um filme de terror
Tringulo retngulo
5
Proposio
uma sentena declarativa que pode assumir os valores verdade (v) ou falso (f)
Exemplos: Todo homem mortal Meu carro um fusca Est chovendo
6
Proposio Atmica
Sentena que no contm conectivos(e, ou, se...ento, ...)
Todo homem mortal. Meu carro um fusca. Est chovendo.
7
Proposio Composta
Sentena que contm um ou mais conectivos (e, ou, se...ento, ...)
Se Maria estuda ento far bons exames. Ele come e dorme. Pedro dana ou canta.
8
Proposio - Cuidado!
A expresso:
A distncia entre Paraty e Ubatuba
no uma sentena pois no possui valorverdade verdadeiro (v) ou falso (f).
9
Conceitos Adicionais
Proposio atmica tomo Proposies atmicas so designadas por
letras latinas minsculas (p, q, r, ...) Literal um tomo ou a negao de um
tomo Conectivos ou Juntores: permitem a
construo de proposies compostas
10
Conectivos
Conectivos ou Juntores: e ou no condicional bicondicional
11
Conectivo: e () A partir de duas proposies, obtm-se uma
terceira denominada conjuno: Exemplo:(p) Maria estuda o problema.(q) Jos vai pescar.
Conjuno de (p) e (q): p qMaria estuda o problema e Jos vai pescar.
12
Conectivo: ou () A partir de duas proposies, obtm-se uma
terceira denominada disjuno: Exemplo:(p) Maria estuda o problema.(q) Jos vai pescar.
Disjuno de (p) e (q): p qMaria estuda o problema ou Jos vai pescar.
13
Conectivo: no ()
Nega o valor-verdade de uma proposio
Exemplo:(p) Maria estuda o problema.
Negao de (p): pno (Maria estuda o problema).
14
Conectivo: condicional () Conectivo condicional lido como se...ento A partir de duas proposies, obtm-se uma
terceira denominada condicional ou implicao
Proposio esquerda de denomina-se premissa ou antecedente
Proposio direita de denomina-se concluso ou conseqente
15
Conectivo: condicional () Exemplo:(p) Eu como muito.(q) Eu engordo.
Condicional de (p) e (q): p qSe eu como muito ento eu engordo.
16
Conectivo: bicondicional ()
Conectivo bicondicional lido como se e somente se
A partir de duas proposies, obtm-se uma terceira denominada bicondicional
17
Conectivo: bicondicional () Exemplo:(p) Um tringulo retngulo(q) Um tringulo tem um ngulo reto.
Bicondicional de (p) e (q): p qUm tringulo retngulo se e somente se tem
um ngulo reto.
18
Semntica dos Conectivos
p q pq pq p pq pqv 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
Frmulas Bem Formadas (wff)
Frmulas construdas atravs dacombinaao vlida de smbolos
Frmulas Bem Formadas = Well FormedFormula = wff
Para representar wff so usadasmetavariveis proposicionais representadas pelas letras , , , etc
Cada expresso envolvendo , , , etc chamada de forma sentencial
20
Definio wff1. um tomo uma wff2. se e so wff, ento so tambm wff:
wff l-se no e ou se ento se e somente se
3. As nicas wff so 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 precedncia pode ser alterada pelo uso de parnteses.
24
Variaes de Notao
Item Adotada Outras e pq p&q p.q p,q ou pq p|q p+q p;q no p ~p p condicional pq pq pq qp bicondicional pq pq pq
25
Semntica do CP
Consiste na interpretao de suas frmulas, ou seja, atribuio dos valores-verdade (v ou f) s formulas atmicas, por exemplo:
(p v q) (p q)
Como a frmula possui 2 componentes atmicos ela admite 22 interpretaes. Para uma frmula de n componentes tem-se 2ninterpretaes .
26
Validade e Inconsistncia (1 de 5)
Se uma frmula tem valor v numa interpretao I, ento verdadeira na interpretao I.
Ex: p q p qI1. v v vI2. v f fI3. f v fI4. f f f
(p q) verdadeira na interpretao I1
27
Validade e Inconsistncia (2 de 5)
Se uma frmula verdadeira segundo alguma interpretao, ento satisfatvel(ou consistente).
Ex: p q p qI1. v v vI2. v f fI3. f v fI4. f f f
(p q) satisfatvel
28
Validade e Inconsistncia (3 de 5)
Uma frmula vlida (tautologia) quando for verdadeira em todas suas interpretaes
Ex: p p
29
Validade e Inconsistncia (4 de 5) Se uma frmula tem valor f numa
interpretao I, ento falsa na interpretao I.
Ex: p q p qI1. v v vI2. v f fI3. f v fI4. f f f
(p q) falsa nas interpretaes I2, I3 e I4.
30
Validade e Inconsistncia (5 de 5)
Uma frmula insatisfatvel (ou inconsistente ou contradio) quando for falsa segundo qualquer interpretao I.
Ex: p p Uma frmula invlida quando for falsa
segundo alguma interpretao I.Ex: p q Frmulas que no so tautologias nem
contradies so chamadas contingentes.
31
Exerccios
Provar usando tabela verdade que:
1. (p p) inconsistente e portanto invlida.2. (p p) valida e portanto consistente.3. (p p) invlida, ainda que consistente.
32
Conseqncia Lgica (1 de 2)
Sejam , 1, 2, ..., n wff. Diz-se que conseqncia lgica de 1, 2, ..., n se, e somente se, para qualquer interpretao em que 1, 2, ..., n forem simultaneamente verdadeiras, tambm verdadeira.
Se conseqncia lgica de 1, 2, ... n,, diz-se que segue-se logicamente de 1, 2, ... n,.
Notao: 1, 2, ..., n
33
Conseqncia Lgica (2 de 2) Teorema 2.7.1: conseqncia lgica de
1, 2, ..., n se e somente se:
1 2 ... n uma tautologia
Teorema 2.7.2: conseqncia lgica de 1, 2, ..., n se e somente se:
1 2 ... n uma contradio
34
Equivalncia Lgica
Uma frmula logicamente equivalente () a uma frmula quando for conseqncia lgica de e for conseqncia lgica de :
se e somente se uma tautologia
35
Exerccio
Provar que (p q) equivalente a (p q) p q pq pq (pq)(pq)v v v v v
v f f f v
f v v v v
f f v v v
36
Argumento
Argumento uma sequncia 1, 2, ..., n(n 1) de proposies, onde:i (1 i n-1) so chamadas premissas en denomina-se concluso.
Notao:1, 2, ..., n-1 n.
37
Argumento Vlido (1 de 2)
Um argumento 1, 2, ..., n-1 n vlidose e somente se:1 2 ... n-1 n for uma tautologia
ou equivalentemente,
1 2 ... n-1 n
38
Argumento Vlido (2 de 2)
Um argumento vlido pode ser lido como:
1, 2, ..., n-1 acarretam n ou n decorre de 1, 2, ..., n-1 ou n conseqncia lgica de 1, 2, ..., n-1
Para n=1, o argumento valido se e somente se 1 for tautolgica
39
Princpio da Substituio (1 de 2)
Subfrmulas: dada a frmula
: (p q) r, entop q, p, q, r, so as subfrmulas de .
O princpio afirma que uma subfrmula de uma frmula , ou toda a frmula , pode ser substituda por uma frmula equivalente e que a frmula resultante equivalente a .
40
Princpio da Substituio (2 de 2)
Exemplo: pelo princpio da substituio, a frmula
: (p v q) (p v r)
equivalente a:
: (p q) (p r).
41
Propriedades (1 de 5)
Existem vrias propriedades da negao, conjuno e disjuno.
Estas propriedades podem ser verificadas como equivalncias lgicas.
Para demonstrar cada uma, basta utilizar as tabelas-verdade, constatando a tautologia.
42
Propriedades (2 de 5)
Propriedades da Conjuno
associativa ( ) ( ) comutativa idempotente propriedadede v(erdade)
v propriedadede f(also)
f f
43
Propriedades (3 de 5)
Propriedades da Disjuno
comutativa v v associativa v ( v ) ( v ) v idempotente v propriedadede v(erdade)
v v vpropriedadede f(also)
v f
44
Propriedades (4 de 5)
Distributivas ( ) ( ) ( ) ( ) ( ) ( )
Negao ()
Absoro ( ) ( )
45
Propriedades (5 de 5)
De Morgan ( ) ( )
Equivalncia da Implicao
46
Frmulas Proposicionais Equivalentes (1 de 2)
Nome da Regra Regramodus ponens , |= modus tollens , |=
silogismo hipottico(ou regra da cadeia)
, |= silogismo disjuntivo , |= dilema construtivo , , |= dilema destrutivo , , |=
simplificao |= conjuno , |=
adio |= contraposio |=
exportao ( ) |= ( ) importao ( ) |= ( )
47
Frmulas Proposicionais Equivalentes (2 de 2)
Exemplo da forma de leitura modus ponens:
,
caso seja verdadee seja verdade,obrigatoriamente ser verdade.
48
Verificao de Validade de Argumentos (1 de 2)
Sejam 1, 2, ..., n, frmulas do ClculoProposicional. Uma sequncia finita de proposies C1, C2, ..., C uma prova ou deduo de , a partir das premissas 1, 2, ..., n , se e somente se:
49
Verificao de Validade de Argumentos (2 de 2)
cada C uma premissa j (1 j n), ouC provm das frmulas precedentes, pelo uso
de um argumento vlido das regras de inferncia, ouC provm do uso do princpio de substituio
numa frmula anterior, ouC
Diz-se ento que dedutvel de 1, 2, ..., n ou que um teorema.
50
Exemplo (1 de 3)
Se as uvas caem, ento a raposa as come.
Se a raposa as come, ento esto maduras.
As uvas esto 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, ento a raposa as come. (C1)Se a raposa as come, ento esto maduras. (C2)
As uvas esto 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 qr: as uvas esto maduras C2: q r(r: as uvas esto 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 qC3: r p
Deduz-se que:
C4: r p (C3: equivalncia)C5: q p (C2 + C4: regra da cadeia)C6: p q q p (C1 + C5: conjuno)C7: p q (C6: equivalncia)
LgicaLgica - DefinioClculo Proposicional - CPTermoProposioProposio AtmicaProposio CompostaProposio - Cuidado!Conceitos AdicionaisConectivosConectivo: e (?)Conectivo: ou (?)Conectivo: no ()Conectivo: condicional (?)Conectivo: condicional (?)Conectivo: bicondicional (?)Conectivo: bicondicional (?)Semntica dos ConectivosFrmulas Bem Formadas (wff)Definio wffPrioridade dos Conectivos (1 de 2)Prioridade dos Conectivos (1 de 2)Prioridade dos Conectivos (2 de 2)Variaes de NotaoSemntica do CPValidade e Inconsistncia (1 de 5)Validade e Inconsistncia (2 de 5)Validade e Inconsistncia (3 de 5)Validade e Inconsistncia (4 de 5)Validade e Inconsistncia (5 de 5)ExercciosConseqncia Lgica (1 de 2)Conseqncia Lgica (2 de 2)Equivalncia LgicaExerccioArgumentoArgumento Vlido (1 de 2)Argumento Vlido (2 de 2)Princpio da Substituio (1 de 2)Princpio da Substituio (2 de 2)Propriedades (1 de 5)Propriedades (2 de 5)Propriedades (3 de 5)Propriedades (4 de 5)Propriedades (5 de 5)Frmulas Proposicionais Equivalentes (1 de 2)Frmulas Proposicionais Equivalentes (2 de 2)Verificao de Validade de Argumentos (1 de 2)Verificao de Validade de Argumentos (2 de 2)Exemplo (1 de 3)Exemplo (2 de 3)Exemplo (3 de 3)