condicionais
9 pág.

condicionais


DisciplinaMatemática Básica5.111 materiais56.622 seguidores
Pré-visualização1 página
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: \u2192
\u2013 P \u2192 Q P é antecedente e Q consequente
„ Linguagem natural
\u2013 se P então Q
Se a Ana está na sala então a Rita está na biblioteca
NaSala(ana) \u2192 NaBib(rita)
\u2013 P só se Q [condição necessária]
O Vasco é aprovado só se assistir a 75% das aulas
Aprovado(vasco) \u2192 Assiste75%(vasco)
\u2013 Q se P [condição suficiente]
O Luís é bom aluno se tiver média de 15
Media15(luis) \u2192 BomAluno(luis)
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 2 - Condicionais
Lógica Proposicional-3
Tradução
\u2013 Q sempre que P, Q quando P, Q dado P
Chove sempre que vou à praia
NaPraia(eu) \u2192 Chove
\u2013 P implica Q [valor de verdade, não causalidade]
A Otília andar à chuva implica que fica molhada
AndarChuva(otilia) \u2192 Molhada(otilia)
„ Combinado com negação: ¬P \u2192 Q
\u2013 Q a menos que P; a não ser que P, Q
A Clara vai à praia a menos que chova
¬Chove \u2192 \u39daPraia(clara) [se chover não se sabe...]
„ Em fórmulas quantificadas: expressões mais naturais
Todos os A\u2019s são B´s
\u2013 Para todo o x (A(x) \u2192 B(x))
Lógica Proposicional-4
\u2192: Semântica e Regra do jogo
„ P \u2192 Q verdadeiro se e só se P é falso ou Q verdadeiro
P Q P \u2192 Q
V V V
V F F
F V V
F F V
significado é ¬P\u2228 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 \u2192 Q é abreviatura de ¬P \u2228 Q 
\u2013 no jogo: substitui e usa regra para \u2228
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, \u2026 Pn se e só se 
é impossível todas serem verdadeiras e Q falso
Então a fórmula
(P1 \u2227 \u2026 \u2227 Pn) \u2192 Q não pode ser falsa
é logicamente verdadeira
Lógica Proposicional-6
Bicondicional
„ Equivalência ou bicondicional material: \u2194
„ [condição necessária e suficiente]
„ LN: se e só se\u2026 só no caso em que...
\u2013 n é par sse n2 é par
Par(n) \u2194 Par(n2)
„ Propriedades: P e Q logicamente equivalentes se e só se o 
bicondicional P \u2194 Q logicamente verdadeiro
P \u21d4 Q sse; abreviatura; não é símbolo da FOL
P \u2194 Q conectiva; logicamente verdadeiro; símbolo da FOL
„ Exemplo: lei de DeMorgan
¬ (P \u2228 Q) \u2194 (¬P \u2227¬ Q) é logicamente verdadeira
P se Q P \u2190 Q
P só se Q P \u2192 Q
sse
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 4 - Condicionais
Lógica Proposicional-7
\u2194: Semântica e Regra do jogo
„ P \u2194 Q verdadeiro se e só P e Q têm o mesmo valor de verdade
P Q P \u2194 Q
V V V
V F F
F V F
F F V
significado é (P\u2227Q) \u2228 (¬ P\u2227¬Q)
„ Tarski´s World: 
\u2013 P \u2194 Q é substituído por (P \u2192 Q) \u2227 (Q \u2192 P) 
\u2013 no jogo: substitui e usa regra para \u2192
Lógica Proposicional-8
LN: o que decorre de uma frase?
„ Ao traduzir LN para LPO:
\u2013 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) \u2192 NaSala(rita)
? ¬NaSala(rui) \u2194 NaSala(rita)
\u2013 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:
\u2013 condições de verdade de uma afirmação
\u2013 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 \u2026 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 \u2026 mas quando 
o Rui está na sala não sei onde está a Rita
NaSala(Rita) \u2192 ¬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 \u2192 e \u2194 
„ Estritamente: podem usar-se só as regras para ¬, \u2227 e \u2228
„ Provas mais naturais: usam regras próprias para \u2192 e \u2194
„ Passos de prova:
„ Modus ponens ou eliminação do condicional
\u2013 tendo estabelecido P\u2192Q e P pode inferir-se Q
„ Eliminação do bicondicional
\u2013 tendo estabelecido Q\u2194R ou R\u2194Q, tendo Q pode inferir-se R
„ Equivalências
P\u2192Q \u21d4 ¬Q \u2192¬P
P\u2192Q \u21d4 ¬P \u2228 Q
¬(P\u2192Q) \u21d4 P \u2227 ¬Q
P\u2194Q \u21d4 (P\u2192Q) \u2227 (Q\u2192P)
P\u2194Q \u21d4 (P \u2227 Q) \u2228 (¬P \u2227 ¬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 \u2192 Q :
\u2013 Assumir P como premissa
\u2013 Provar Q
„ Exemplo: A \u2192 C é consequência de A \u2192 B e B \u2192 C 
\u2013 Assumindo A: de A\u2192B, por modus ponens infere-se B
\u2013 De B e B\u2192C , por modus ponens infere-se C
\u2013 Provou-se C tendo assumido A, provou-se A\u2192C
„ Exemplo: Par(n2) \u2192 Par(n) 
\u2013 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 
\u2013 Par(n2) \u2192 Par(n) infere-se por prova condicional
Lógica Proposicional-12
Provas com \u2194
„ Prova condicional: para provar P \u2194 Q
\u2013 Assumir P e provar Q
\u2013 Assumir Q e provar P
„ Para provar Q1, Q2, Q3 todos equivalentes:
Expressão em LPO:
Q1 \u2194 Q2
Q2 \u2194 Q3
Q1 \u2194 Q3
Em vez de 6 provas condicionais: 
provar um ciclo
Q1 \u2192 Q2
Q2 \u2192 Q3
Q3 \u2192 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) \u2192 (2) \u2192 (1) \u2192 (3)
\u2013 Assumindo (3): se n2 é divisível por 4, é divisível por 2, logo (2)
\u2013 (2) \u2192 (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
\u2013 (1) \u2192 (3) é evidente
Lógica Proposicional-14
Regras de inferência para \u2192
Eliminação do condicional
(\u2192 Elim)
P \u2192 Q
\u2026
P
\u2026
Q
Introdução do condicional
(\u2192 Intro)
P
\u2026
Q
P \u2192 Q
Prova condicionalModus ponens
> >
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 8 - Condicionais
Lógica Proposicional-15
\u2192 nas provas formais
1. (A \u2228 B) \u2192 C
2. A
3. A \u2228 B \u2228 Intro: 2
4. C \u2192 Elim: 1,3
5. A \u2192 C \u2192 Intro: 2-4
1. A 
2. ¬ A
3. \u22a5 \u22a5 Intro: 1,2
4. ¬¬A ¬ Intro: 2,3
5. A \u2192 ¬¬A \u2192 Intro: 1-4
Usar prova de ¬¬A a partir de A
para provar o condicional 
A \u2192 ¬¬A
(sem premissas)
Lógica Proposicional-16
Regras de inferência para \u2194
Eliminação do bicondicional
(\u2194 Elim)
P \u2194 Q (ou Q \u2194 P )
\u2026
P
\u2026
Q
Introdução do bicondicional
(\u2194 Intro)
P
\u2026
Q
Q
\u2026
P
P \u2194 Q
Dupla prova condicional
>
>
FEUP/LEIC Teoria da Computação II 2001/2002
Cristina Ribeiro/Gabriel David 9 - Condicionais
Lógica Proposicional-17
\u2194 nas provas formais
1. ¬(P \u2227 Q)
2. ¬P \u2228 ¬Q Teor Prev(Teorema 2): 1
3. ¬P \u2228 ¬Q
4. ¬(P \u2227 Q) Teor Prev(Teorema 3): 3
5. ¬(P \u2227 Q) \u2194 (¬P \u2228 ¬Q) \u2194 Intro: 1-2, 3-4
Lógica Proposicional-18
Esquemas úteis
„ Modus ponens
\u2013 De A \u2192 B e \u391
\u2013 Inferir \u392
„ Modus tollens
\u2013 De A \u2192 B e ¬B
\u2013 Inferir ¬A
„ Cancelamento
\u2013 De A \u2228 B e ¬B
\u2013 Inferir A
„ Reforço do antecedente
\u2013 De B \u2192 C
\u2013 Inferir (A \u2227 B) \u2192 C
„ Enfraquecimento do consequente
\u2013 De A \u2192 B
\u2013 Inferir A \u2192 (B \u2228 C)
„ Dilema construtivo
\u2013 De A \u2228 B , A \u2192 C, B \u2192 D
\u2013 Inferir C \u2228 D