logica matematica

Prévia do material em texto

Matema´tica para controle:
Introduc¸a˜o a` Lo´gica
Amit Bhaya,
Programa de Engenharia Ele´trica
COPPE/UFRJ
Universidade Federal do Rio de Janeiro
amit@nacad.ufrj.br
http://www.nacad.ufrj.br/˜ amit
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Introduc¸a˜o a (notac¸a˜o) lo´gica
Lo´gica matema´tica:
• Disciplina fundamental sobre a qual se fundamenta
matema´tica.
• Uma linguagem formal.
• Um ramo de matema´tica com caracter´ısticas
pro´prias.
1
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Paradoxos
A ide´ia de consisteˆncia: papel fundamental em
sistema lo´gico. Desde a Gre´cia cla´ssica surgem
paradoxos.
1. Paradoxo do mentiroso (Creta): Considere a
sentenc¸a (frase)
(A) Eu estou mentindo.
A sentenc¸a (A) e´ verdadeira (V) ou falsa (F).
Se V, a pessoa esta´ mentindo, portanto (A) e´ F!
Se F, a pessoa esta´ dizendo a verdade, portanto (A) e´ V!
2. Paradoxo do carta˜o (Jourdain)
Um lado do carta˜o tem a frase (A): A sentenc¸a do outro lado do carta˜o e´ verdadeira; o
outro lado do carta˜o a frase (B): A sentenc¸a do outro lado do carta˜o e´ falsa.
(A) e´ V implica (B) e´ V, portanto, (A) e´ F
(A) e´ F implica (B) e´ F, portanto, (A) e´ V!
Sentenc¸as (A), (B) sa˜o, ao mesmo tempo, V e F.
Problema: auto-refereˆncia
Conclusa˜o: Linguagem coloquial na˜o apropriada,
necessidade de linguagens formais.
2
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Proposic¸o˜es
Chama-se proposic¸a˜o todo o conjunto de palavras
que exprimem um pensamento de sentido completo.
Proposic¸o˜es transmitem pensamentos; afirmam
fatos.
Exemplos:
1. eiπ = cosπ + i sen π = −1 (Euler).
2. xn + yn = zn na˜o possui soluc¸o˜es inteiras (x, y, z)
para n ≥ 3. (Fermat-Wiles).
3. A velocidade da luz e´ constante independente da
velocidade da fonte e/ou da referencial. (Einstein)
3
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Regras fundamentais de lo´gica
matema´tica
1. Princ´ıpio de na˜o-contradic¸a˜o: Uma proposic¸a˜o
na˜o pode ser verdadeira e falsa ao mesmo tempo.
2. Princ´ıpio do terceiro exclu´ıdo: Toda a proposic¸a˜o
ou e´ verdadeira ou e´ falsa. Isto e´, verifica-se sempre
um destes casos e nunca um terceiro.
Consequeˆncia destes princ´ıpios: Toda a proposic¸a˜o
assume valor lo´gico verdadeiro (V) ou falso (F).
4. π e´ um nu´mero racional.
5. Camo˜es escreveu A Divina Come´dia.
Frases 1 a 3 (na pa´gina anterior) possuem valor lo´gico
V, frases 4 e 5 possuem v.l. F.
4
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Tipos de proposic¸o˜es
Proposic¸a˜o simples: Aquela que na˜o conte´m
nenhuma outra proposic¸a˜o como parte.
Notac¸a˜o: Letra minu´scula romana do final do
alfabeto; p. ex. p, q, r etc.
Proposic¸a˜o composta: Formada pela combinac¸a˜o
de duas ou mais proposic¸o˜es simples.
Notac¸a˜o: Letra maiu´scula romana do final do
alfabeto; p. ex. P,Q,R etc.
Exemplo: P (p, r): O nu´mero 625 e´ quadrado
perfeito e um hexa´gono tem 9 diagonais.
Valor lo´gico de P (p, r) e´ V, pois 625 = 25× 25, e(
6
2
)
− 6 = 15− 6 = 9.
5
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Conectivos
Conectivos sa˜o palavras que se usam para formar
novas proposic¸o˜es a partir de outras.
Sa˜o eles: e, ou, na˜o, ‘se . . . enta˜o’, ‘se e somente
se’.
Conectivos em negrito
P (p, q): O nu´mero 6 e´ par (p) e o nu´mero 8 e´ cubo
perfeito (q).
Q(r, s): O sistema e´ linear (r) ou e´ na˜o-linear (s).
R: Na˜o esta´ chovendo.
S: Se Jorge e´ engenheiro (p), enta˜o sabe matema´tica
(q).
T : A matriz A e´ invers´ıvel se e somente se detA 6= 0.
6
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Conectivos: notac¸a˜o
S´ımbolo Significado Exemplo
¬ na˜o . . . ¬p
∧ . . . e . . . p ∧ q
∨ . . . ou . . . r ∨ s
→ se . . . enta˜o . . . p→ q
↔ . . . se e somente se . . . p↔ q
7
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Tabela verdade de conectivo
Forma tabular de apresentar os valores lo´gicos de
sentenc¸as envolvendo conectivos.
p ¬p
V F
F V
p q p ∧ q
V V V
V F F
F V F
F F F
p q p ∨ q
V V V
V F V
F V V
F F F
p q p→ q
V V V
V F F
F V V
F F V
p q p↔ q
V V V
V F F
F V F
F F V
8
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Mais sobre tabela verdade de →
Problema: Na linguagem coloquial a construc¸a˜o ‘se
. . . enta˜o’ exige uma ligac¸a˜o causal (= causa-efeito).
Na lo´gica matema´tica, na˜o se exige relac¸a˜o lingu¨istica
entre os membros de uma sentenc¸a composta.
Exemplo: Eu colei na prova (p) e eu vou levar meu
guarda chuva (q).
Considere a lei de f´ısica: Todo metal e´ malea´vel.
Enquanto lei, a sentenc¸a e´ sempre verdadeira (V).
se x e´ metal, enta˜o x e´ malea´vel (⋆)
Uma vez que acreditamos na lei universal de f´ısica, vale substituir
x por qualquer coisa, obtendo uma implicac¸a˜o verdadeira
p q p→ q Valor de x
V V V ferro
V F F
F V V barro
F F V madeira
Para a sentenc¸a/lei (⋆), jamais chegamos a conclusa˜o de que
o antecedente (p) e´ V e o consequente (q) e´ F.
9
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Mais sobre tabela verdade de →
Compare as tabelas abaixo:
p q p→ q
V V V
V F F
F V V
F F V
p q ¬p ¬p ∨ q
V V F V
V F F F
F V V V
F F V V
Vemos, atrave´s das tabelas, que
a sentenc¸a p → q EQUIVALE a sentenc¸a ¬p ∨ q
(equivale significa t.v.s coincidem, Notac¸a˜o: p → q
⇔ ¬p ∨ q)
Outras locuc¸o˜es para p→ q:
1. q e´ uma condic¸a˜o necessa´ria para p.
2. p acarreta q; (ou p implica q).
3. p e´ uma condic¸a˜o suficiente para q.
Exemplo: Triaˆngulo A e triaˆngulo B possuem a mesma base
e a mesma altitude (p) → Area △A = Area △B (q). Pore´m
q 6→ p!
10
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Deduc¸a˜o e Tabelas-verdade
Considere as frases
S´ımbolo Sentenc¸a
p Ha´ prec¸os altos
s Ha´ sala´rios altos
c Ha´ congelamento
i Ha´ inflac¸a˜o
e as premissas (sentenc¸as que tem valor lo´gico V)
1. p→ s, 2. p ∨ c, 3. c→ ¬i.
Fato: Ha´ inflac¸a˜o. Pergunta: E´ va´lido concluir (a
partir das premissas) que ha´ sala´rios altos?
Isto e´: (Sentenc¸a i e´ V) acarreta (sentenc¸a s e´ V)?
Racioc´ınio:
[i (V) (dado)] ∧ [c→ ¬i (V)(prem.)] → [c (F)] (pela t.v. de→)
[p ∨ c (V) (prem.)] ∧ [c (F)] → [p (V)] (pela t.v. de ∨)
[p (V)] ∧ [p→ s (prem.)] → [s (V)]
11
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Func¸a˜o verdade
Func¸a˜o verdade (f.v.) f : {V, F}n → {V, F}
Ha´ 22
n
f.v.s de n varia´veis
Para n = 2, das 16 f.v.s poss´ıveis, apenas 4 sa˜o
destacadas (∧,∨,→,↔).
Para n = 1, das 4 f.v.s poss´ıveis, apenas uma e´
destacada (¬).
Podemos definir um conjunto T de f.v.s
recursivamente:
1. ¬p, p ∧ q, p ∨ q, p→ q, p↔ q pertencem a T .
2. f ∈ T implica que a func¸a˜o obtida pela substituic¸a˜o
de qualquer varia´vel de f por outra em T tambe´m
pertence a T .
p. ex. [(¬p) ∨ q] ∈ T → [(¬p) ∨ (t ∨ (r ∧ s))] ∈ T
Ou seja, sentenc¸as compostas podem ser geradas a partir de
sentenc¸as simples recursivamente.
Tautologia: Sentenc¸a cujo valor lo´gico e´ sempre
V (para qualquer escolha de valores para componentes
primos).
Exemplos: p→ p, p ∧ (p→ q) → q.
12
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Deduc¸a˜o e gerac¸a˜o de tautologias
A definic¸a˜o e´ muito ineficiente para testar
tautologias. Na˜o ajuda a descobrir tautologias.
Incentivou a derivac¸a˜o de regras para gerar
tautologias a partir de outras.
Exemplos: (¬¬p) ⇔ (p), (p → q) ⇔ (¬q → ¬p),
¬(p ∨ q) ⇔ (¬p ∧ ¬q).
Resumo: Lei de De Morgan para negac¸a˜o de
sentenc¸as: Para obter a negac¸a˜o de uma sentenc¸a
(s), substitui-se todo ∧ por um ∨ e vice-versa, e toda
sentenc¸a simples p em s por ¬p.
Voltaremos ao assunto das leis de De Morgan mais
adiante.
13
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gicaContradic¸a˜o, Inconsisteˆncia
Contradic¸a˜o: Sentenc¸a cujo valor e´ sempre F.
P. ex. p ∧ ¬p.
Prova por contradic¸a˜o: {p1, . . . , pm} |= q se uma
contradic¸a˜o e´ consequeˆncia va´lida de {p1, . . . , pm} ∧
¬q. (Notac¸a˜o: |= significa acarreta).
Inconsisteˆncia: {p1, . . . , pm} e´ um conjunto
inconsistente se tem contradic¸a˜o como consequeˆncia
va´lida.
Em outras palavras, a prova por contradic¸a˜o
consiste em acrescentar a negac¸a˜o da conclusa˜o ao
conjunto das premissas e mostrar, atrave´s das regras
de infereˆncia, que o conjunto gerado desta maneira e´
inconsistente.
14
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Func¸a˜o proposicional
p : A → {V, F} onde p(x) e´ sentenc¸a com a
propriedade de que p(a) e´ V ou F para cada a ∈ A.
Em outras palavras, p(x) se torna uma proposic¸a˜o
sempre que x for substitu´ıdo por a ∈ A.
Exemplos:
p(x) : x+2 > 7 e´ uma f.p. se A = N, na˜o e´ se A = C.
p(x) : x2 = x e´ uma f.p. se A = R.
Vp ⊂ A conjunto verdade de p(x) := {x|x ∈ A, p(x)}
Exemplo: p(x) = x + 5 < 3, A = N, Vp = {x|x ∈
N, x+ 5 < 3} = ∅
15
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Quantificadores: ∀, ∃
Outra maneira de lidar com func¸o˜es proposicionais,
observando que p(x) pode ser V para todo x ∈ A,
para algum x0 ∈ A ou para nenhum x ∈ A.
Notac¸a˜o: ∀ = para todo (quantificador universal)
∃ = existe (quantificador existencial)
(∀x ∈ A)p(x) ou ∀x, p(x) e´ uma proposic¸a˜o que se leˆ
para todo x ∈ A, p(x) e´ V (ou seja, Vp = A). Outra
locuc¸a˜o: Qualquer que seja . . .
(∃x ∈ A)p(x) ou ∃x, p(x) e´ uma proposic¸a˜o que se leˆ
existe x ∈ A, p(x) e´ V (ou seja, Vp 6= ∅). Outras
locuc¸o˜es: para algum . . . , para ao menos um . . . .
Exemplos:⋂
i∈I Ai := {x|∀i ∈ I, x ∈ Ai}⋃
i∈I Ai := {x|∃i ∈ I, x ∈ Ai}
16
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Negac¸a˜o: proposic¸o˜es com
quantificadores
Todos os homens sa˜o mortais
na˜o (e´ verdade que todos os homens sa˜o mortais)
existe ao menos um homem que na˜o e´ mortal
¬(∀x ∈ H) (x e´ mortal) equivale a (∃x ∈ H)(x na˜o e´
mortal)
Teorema (de Morgan)
¬(∀x ∈ A)p(x) ⇔ (∃x ∈ A)¬p(x)
¬(∃x ∈ A)p(x) ⇔ (∀x ∈ A)¬p(x)
Exemplo: ¬(p(x) ∧ q(x)) ⇔ ¬p(x) ∨ ¬q(x)
Dado que ¬(∀x, p(x)) ⇔ (∃x¬p(x)), para mostrar que
∀x, p(x) e´ falso, basta que ∃x0, p(x0) e´ F. Tal x0 e´
denominado contraexemplo.
17
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Ordem da quantificac¸a˜o
Em geral, dada uma func¸a˜o proposicional
multivaria´vel, e´ necessa´rio que ela seja precedida por
quantificadores para cada varia´vel (para que se torne
uma proposic¸a˜o).
Atenc¸a˜o: Na˜o se pode trocar a ordem da quantificac¸a˜o
sem trocar o sentido da sentenc¸a (em geral)!
Exemplos: Sejam x, y inteiros.
(∀x)(∃y)(x < y) e´ V, PORE´M (∃x)(∀y)(x < y) e´ F!
18
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Exemplos de quantificac¸a˜o
n e´ um nu´mero natural primo.
∀m ∈ N, {∃k : n = mk → (m = 1 ∨m = n}
Todo nu´mero racional e´ real. ∀x,Q(x) → R(x)
Alguns reais sa˜o racionais. ∃x : R(x) ∧Q(x)
Para f : R → R, definic¸a˜o de continuidade em um
ponto: a func¸a˜o f e´ cont´ınua no ponto a se e somente
se, para todo ǫ > 0, existe δ > 0 tal que, para todo x,
se |x− a| < δ, enta˜o |f(x)− f(a)| < ǫ.
(∀ǫ > 0)(∃δ > 0)(∀x)(|x− a| < δ) → |f(x)− f(a)| <
ǫ.
E´ do tipo (∀ǫ)(∃δ)(∀x)(p→ q)
equivalentemente: (∀ǫ)(∃δ)(∀x)(¬p ∨ q).
Portanto, negac¸a˜o e´:
(∃ǫ)(∀δ)(∃x)(|x− a| < δ ∧ |f(x)− f(a)| ≥ ǫ)
19
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Quantificadores e xadrez
Sequeˆncia {xn} converge a x
∗ ∈ C
Quantificadores e varia´veis x∗, n, ǫ f.p. P (x∗, n, ǫ)︷ ︸︸ ︷
(∃x∗ ∈ C)(∀ǫ > 0)(∃M ∈ N)(∀n > M)
︷ ︸︸ ︷
(|xn − x
∗| < ǫ)
Jogo entre no´s e o adversa´rio:
No´s Adversa´rio No´s Adversa´rio No´s
x∗ ǫ(x∗) M(x∗, ǫ) n > M oˆnus de provar
para tornar P falso |xn − x
∗| < ǫ para ganhar
Analogia com xeque mate em duas jogadas (J =
jogada, B = branco, P = preto)
(∃ JB)(∀ JP)(∃ JB)(∀ JP)(B × Rei P)
x∗
x1
x2
x3
x4
x5 x6
x7
x8
x9
Re
Im
Todo c´ırculo com centro x∗
inclui todos os pontos xn
menos um nu´mero finito
20
COE745, PEE/COPPE 2006, c©Amit Bhaya Aula 1: Lo´gica
Quantificadores: leitura
(∃M ∈ N)(∀n > M) leˆ-se Para todos os inteiros
n menos um nu´mero finito ou ainda para todo n
suficientemente grande
Negac¸a˜o da definic¸a˜o de convergeˆncia:
(∀x∗)(∃ǫ > 0)(∀M ∈ N)(∃n > M)(|xn − x
∗| ≥ ǫ)
Qualquer que seja o ponto x∗ escolhido (como poss´ıvel
ponto limite da sequeˆncia), existe uma ǫ-vizinhanc¸a
de x∗ tal que existe um nu´mero infinito de pontos da
sequeˆncia fora dela.
21