Condicionais na Lógica Proposicional

Prévia do material em texto

FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 1 - Condicionais
1
Lógica Proposicional-3
Condicional e Bicondicional
Provas informais e formais com condicionais
Referência: Language, Proof and Logic
Jon Barwise e John Etchemendy, 1999
Capítulos: 7-8
Lógica Proposicional-2
Condicional
„ Implicação ou condicional material: →
– P → Q P é antecedente e Q consequente
„ Linguagem natural
– se P então Q
Se a Ana está na sala então a Rita está na biblioteca
NaSala(ana) → NaBib(rita)
– P só se Q [condição necessária]
O Vasco é aprovado só se assistir a 75% das aulas
Aprovado(vasco) → Assiste75%(vasco)
– Q se P [condição suficiente]
O Luís é bom aluno se tiver média de 15
Media15(luis) → BomAluno(luis)
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 2 - Condicionais
Lógica Proposicional-3
Tradução
– Q sempre que P, Q quando P, Q dado P
Chove sempre que vou à praia
NaPraia(eu) → Chove
– P implica Q [valor de verdade, não causalidade]
A Otília andar à chuva implica que fica molhada
AndarChuva(otilia) → Molhada(otilia)
„ Combinado com negação: ¬P → Q
– Q a menos que P; a não ser que P, Q
A Clara vai à praia a menos que chova
¬Chove → ΝaPraia(clara) [se chover não se sabe...]
„ Em fórmulas quantificadas: expressões mais naturais
Todos os A’s são B´s
– Para todo o x (A(x) → B(x))
Lógica Proposicional-4
→: Semântica e Regra do jogo
„ P → Q verdadeiro se e só se P é falso ou Q verdadeiro
P Q P → Q
V V V
V F F
F V V
F F V
significado é ¬P∨ Q
„ Quando é falso: antecedente verdadeiro e consequente falso
„ Não aumenta a potência da linguagem mas torna-a mais 
natural e fácil de entender
„ Tarski´s World: P → Q é abreviatura de ¬P ∨ Q 
– no jogo: substitui e usa regra para ∨
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 3 - Condicionais
Lógica Proposicional-5
Verdade lógica e consequência lógica
„ Importância do condicional: reduzir consequência lógica a 
verdade lógica
„ Q é consequência das premissas P1, … Pn se e só se 
é impossível todas serem verdadeiras e Q falso
Então a fórmula
(P1 ∧ … ∧ Pn) → Q não pode ser falsa
é logicamente verdadeira
Lógica Proposicional-6
Bicondicional
„ Equivalência ou bicondicional material: ↔
„ [condição necessária e suficiente]
„ LN: se e só se… só no caso em que...
– n é par sse n2 é par
Par(n) ↔ Par(n2)
„ Propriedades: P e Q logicamente equivalentes se e só se o 
bicondicional P ↔ Q logicamente verdadeiro
P ⇔ Q sse; abreviatura; não é símbolo da FOL
P ↔ Q conectiva; logicamente verdadeiro; símbolo da FOL
„ Exemplo: lei de DeMorgan
¬ (P ∨ Q) ↔ (¬P ∧¬ Q) é logicamente verdadeira
P se Q P ← Q
P só se Q P → Q
sse
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 4 - Condicionais
Lógica Proposicional-7
↔: Semântica e Regra do jogo
„ P ↔ Q verdadeiro se e só P e Q têm o mesmo valor de verdade
P Q P ↔ Q
V V V
V F F
F V F
F F V
significado é (P∧Q) ∨ (¬ P∧¬Q)
„ Tarski´s World: 
– P ↔ Q é substituído por (P → Q) ∧ (Q → P) 
– no jogo: substitui e usa regra para →
Lógica Proposicional-8
LN: o que decorre de uma frase?
„ Ao traduzir LN para LPO:
– questão do que é ou não consequência da frase
A Rita está na sala quando o Rui não está na sala
? ¬NaSala(rui) → NaSala(rita)
? ¬NaSala(rui) ↔ NaSala(rita)
– Na frase em LN: decorre de alguma maneira que se o Rui estiver na 
sala, então a Rita não estará
„ Distinção a fazer:
– condições de verdade de uma afirmação
– outras coisas que decorrem da afirmação
„ H.P. Grice: introduz noção de decorrência conversacional
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 5 - Condicionais
Lógica Proposicional-9
Decorrência Conversacional
Frase F, e conclusão C
„ se C faz parte do significado de F: não pode ser cancelada 
por afirmações subsequentes
8 A Rita e o Rui estão na sala … mas o Rui não está na sala
O Rui está na sala é parte do significado: não pode ser cancelado
„ se C é mera decorrência de F: pode ser cancelada por 
afirmações subsequentes
9 A Rita está na sala quando o Rui não está na sala … mas quando 
o Rui está na sala não sei onde está a Rita
NaSala(Rita) → ¬NaSala(Rui) não faz parte do significado da 
afirmação: pode ser cancelado na afirmação seguinte sem 
contradição
Lógica Proposicional-10
Métodos de prova usando → e ↔ 
„ Estritamente: podem usar-se só as regras para ¬, ∧ e ∨
„ Provas mais naturais: usam regras próprias para → e ↔
„ Passos de prova:
„ Modus ponens ou eliminação do condicional
– tendo estabelecido P→Q e P pode inferir-se Q
„ Eliminação do bicondicional
– tendo estabelecido Q↔R ou R↔Q, tendo Q pode inferir-se R
„ Equivalências
P→Q ⇔ ¬Q →¬P
P→Q ⇔ ¬P ∨ Q
¬(P→Q) ⇔ P ∧ ¬Q
P↔Q ⇔ (P→Q) ∧ (Q→P)
P↔Q ⇔ (P ∧ Q) ∨ (¬P ∧ ¬Q)
contrapositiva
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 6 - Condicionais
Lógica Proposicional-11
Método de prova condicional
„ Para provar P → Q :
– Assumir P como premissa
– Provar Q
„ Exemplo: A → C é consequência de A → B e B → C 
– Assumindo A: de A→B, por modus ponens infere-se B
– De B e B→C , por modus ponens infere-se C
– Provou-se C tendo assumido A, provou-se A→C
„ Exemplo: Par(n2) → Par(n) 
– Assumindo Par(n2), e fazendo prova por contradição
„ n é ímpar, n= 2m + 1
„ n2 = (2m+1)2 = 4 m2 + 4m + 1 = 2 (2 m2 + 2m) +1 donde n2 é ímpar
„ Contradiz a premissa, logo n é par 
– Par(n2) → Par(n) infere-se por prova condicional
Lógica Proposicional-12
Provas com ↔
„ Prova condicional: para provar P ↔ Q
– Assumir P e provar Q
– Assumir Q e provar P
„ Para provar Q1, Q2, Q3 todos equivalentes:
Expressão em LPO:
Q1 ↔ Q2
Q2 ↔ Q3
Q1 ↔ Q3
Em vez de 6 provas condicionais: 
provar um ciclo
Q1 → Q2
Q2 → Q3
Q3 → Q1
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 7 - Condicionais
Lógica Proposicional-13
Exemplo
„ As condições seguintes nos números naturais são todas 
equivalentes:
(1) n é par
(2) n2 é par
(3) n2 é divisível por 4
„ Provando (3) → (2) → (1) → (3)
– Assumindo (3): se n2 é divisível por 4, é divisível por 2, logo (2)
– (2) → (1) por contrapositiva: se n é ímpar, pode escrever-se 
„ n= 2m + 1
„ n2 = (2m+1)2 = 4 m2 + 4m + 1 = 2 (2 m2 + 2m) +1 é ímpar
– (1) → (3) é evidente
Lógica Proposicional-14
Regras de inferência para →
Eliminação do condicional
(→ Elim)
P → Q
…
P
…
Q
Introdução do condicional
(→ Intro)
P
…
Q
P → Q
Prova condicionalModus ponens
> >
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 8 - Condicionais
Lógica Proposicional-15
→ nas provas formais
1. (A ∨ B) → C
2. A
3. A ∨ B ∨ Intro: 2
4. C → Elim: 1,3
5. A → C → Intro: 2-4
1. A 
2. ¬ A
3. ⊥ ⊥ Intro: 1,2
4. ¬¬A ¬ Intro: 2,3
5. A → ¬¬A → Intro: 1-4
Usar prova de ¬¬A a partir de A
para provar o condicional 
A → ¬¬A
(sem premissas)
Lógica Proposicional-16
Regras de inferência para ↔
Eliminação do bicondicional
(↔ Elim)
P ↔ Q (ou Q ↔ P )
…
P
…
Q
Introdução do bicondicional
(↔ Intro)
P
…
Q
Q
…
P
P ↔ Q
Dupla prova condicional
>
>
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 9 - Condicionais
Lógica Proposicional-17
↔ nas provas formais
1. ¬(P ∧ Q)
2. ¬P ∨ ¬Q Teor Prev(Teorema 2): 1
3. ¬P ∨ ¬Q
4. ¬(P ∧ Q) Teor Prev(Teorema 3): 3
5. ¬(P ∧ Q) ↔ (¬P ∨ ¬Q) ↔ Intro: 1-2, 3-4
Lógica Proposicional-18
Esquemas úteis
„ Modus ponens
– De A → B e Α
– Inferir Β
„ Modus tollens
– De A → B e ¬B
– Inferir ¬A
„ Cancelamento
– De A ∨ B e ¬B
– Inferir A
„ Reforço do antecedente
– De B → C
– Inferir (A ∧ B) → C
„ Enfraquecimento do consequente
– De A → B
– Inferir A → (B ∨ C)
„ Dilema construtivo
– De A ∨ B , A → C, B → D
– Inferir C ∨ D