Complementos de Matemáticaa_Mauro_1

Prévia do material em texto

2012
ME-100
Fundamentos de Matemática
Mauro S. de F. Marques
– p. 1/83
CAPÍTULO 1
Noções básicas de lógica matemática
msdfm
– p. 2/83
1.1 Introdução
LÓGICA:
Parte da filosofia que trata das formas do pensamento
em geral (dedução, indução, hipótese, inferência,
etc...) e das operações intelectuais que visam à
determinação do que é verdadeiro ou não.
Produz conclusões e estabelece argumentos.
Etimologia gr. logikê (tékhnê) ’a ciência do raciocínio, a lógica’, f. fem. de logikós,ê,ón, pelo lat.
logìca,ae ou logìce,es ’id.’; ver log(o)-; f.hist. sXIV logica, sXIV lisica
msdfm
– p. 3/83
Grandes contribuic¸o˜es
• ARISTÓTELES (384 - 322a.C.). Criou a ciência da lógica.
• GEORGE BOOLE (1815-1864). Fundamentos da álgebra da lógica.
• AUGUSTUS DE MORGAN (1806-1871). Fundamentos da álgebra da lógica.
• GOTLOB FREGE (1848-1925). Desenvolvimento da lógica.
• GIUSEPPE PEANO (1858-1932). Simbologia da matemática.
• ALFRED NORTH WHITEHEAD (1861-1947). Lógica moderna.
• BERTRAND RUSSELL (1872-1970). Lógica moderna (PRINCIPIA MATHEMATICA).
msdfm
– p. 4/83
Informalmente a matemática pode usar uma
linguagem corrente para se exprimir mas como
ciência se faz necessário um rigor maior na linguagem
utilizada.
Isso nos leva ao estudo da chamada Lógica
Matemática.
msdfm
– p. 5/83
Cálculo proposicional
Proposic¸a˜o:
• Coisa que se propõe; proposta, sugestão.
• Na lógica tradicional de matriz aristotélica, expressão
lingüística de uma operação mental (o juízo), composta de
sujeito, verbo (sempre redutível ao verbo ser) e atributo, e
passível de ser verdadeira ou falsa; enunciado.
• Na lógica moderna, enunciado traduzível em símbolos
matemáticos, passível de múltiplos valores de verdade
(verdadeiro ou falso) e redutível a dois elementos básicos
(o sujeito e o predicado).
msdfm
– p. 6/83
Organizando:
• Os blocos básicos da lógica são as proposições.
• Uma proposição é um enunciado que pode ser verdadeiro
ou falso mas não ambos.
• Dada uma proposição a lógica matemática assume:
• Princípio da Identidade: “Todo objeto e´ ideˆntico a si mesmo”.
• Princípio da Contradição: “Dadas duas proposic¸o˜es contradito´rias (uma e´ negac¸a˜o
da outra), uma delas e´ falsa. ”.
• Princípio do Terceiro Excluído: “Dadas duas proposic¸o˜es contradito´rias, uma
delas e´ verdadeira ”.
msdfm
– p. 7/83
• Proposições serão denotadas por p, q, ..., p1, p2, ..., etc...
• A cada proposição podemos associar de maneira única o
seu valor-verdade:
• V (verdade) para uma proposição verdadeira.
• F (falso) para uma proposição falsa.
• A proposição “2 e´ um nu´mero par” tem valor-verdade V .
• A proposição “2 e´ um nu´mero impar” tem valor-verdade F .
• A proposição “2 e´ um nu´mero primo” tem valor-verdade V .
• A proposição “2 somado com 2 e´ igual a 0” tem valor-verdade F .
• A proposição “o sol gira em torno da terra” tem valor-verdade F .
• A proposição “o sol na˜o gira em torno da terra” tem valor-verdade V .
• “x > 0"não é uma proposição!
• “Essa proposic¸a˜o na˜o e´ verdadeira”
não é uma proposição!
msdfm– p. 8/83
1.2 Conectivos lógicos: e, ou e na˜o
Proposições podem ser combinadas resultando em uma
proposição composta.
EXEMPLOS:
• “2 e´ um nu´mero par e primo”. (V )
• “2 e´ um nu´mero maior que 3 ou impar”. (F )
• “2 na˜o e´ um nu´mero impar”. (V )
NOTAC¸ ˜AO:
• ∧ (e)
• ∨ (ou)
• ¬ (não)
msdfm
– p. 9/83
Sejam p e q duas proposições.
• A conjunc¸a˜o de p e q, isto é, a proposição “p e q”, é
denotada por
p ∧ q.
• A disjunc¸a˜o de p e q, isto é, a proposição “p ou q”, é
denotada por
p ∨ q.
• A negac¸a˜o de p, isto é, “a negação de p é verdadeira (falsa)
se e somente se p é falsa (verdadeira)”, é denotada por
¬p.
msdfm
– p. 10/83
Observac¸o˜es:
• Parênteses, ( ), são usados para indicar a abrangência dos
conectivos.
• O conectivo ¬ se aplica somente ao próximo símbolo.
Assim,
¬p ∨ q significa (¬p) ∨ q;
que é diferente de
¬(p ∨ q).
msdfm
– p. 11/83
1.3 Tabelas-verdade
Para determinar o valor-verdade de proposições compostas,
conhecidos os valores das proposições (simples) que as
compõem, tabelas-verdade podem (devem) ser utilizadas. Por
exemplo:
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 ¬p
V F
F V
msdfm
– p. 12/83
Tabelas-verdade podem ser usadas para determinar os possíveis
valores verdade de proposições mais elaboradas. Por exemplo,
para a proposição
¬(p ∨ ¬q)
temos:
p q ¬q p ∨ ¬q ¬(p ∨ ¬q)
V V F V F
V F V V F
F V F F V
F F V V F
msdfm
– p. 13/83
Exercı´cio
1.Assinale o valor-verdade para as seguintes
proposições:
(i) 3 ≤ 7 e 4 é um número impar.
(ii) 3 ≤ 7 ou 4 é um número impar.
(iii) 5 é impar ou divisível por 4.
(iv) 3 ≤ 3.
(v) Não é verdade que 2+2=5.
msdfm
– p. 14/83
2. Considere as seguintes proposições:
p : “7 e´ um nu´mero par”, q : “3 + 1 = 4”, e r : “24 e´ divis´ivel por 8”.
Escreva simbolicamente (em termos de p, q, r,∧,∨ e ¬) e
encontre o valor-verdade das proposições
(i) “3 + 1 6= 4 e 24 e´ divis´ivel por 8”.
(ii) “Na˜o e´ verdade que 7 e´ um nu´mero par ou 3 + 1 = 4”.
Expresse em palavras e encontre o valor-verdade das proposições
(i) p ∨ ¬q.
(ii) ¬(r ∧ q).
(iii) ¬r ∨ ¬q.
msdfm
– p. 15/83
3. Construa tabelas-verdade para:
(i) ¬p ∨ q
(ii) ¬p ∨ p
(iii) ¬p ∨ ¬q
(iv) ¬(p ∧ q)
(v) ¬(p ∨ q)
(vi) ¬p ∧ ¬q
(vii) p ∨ ¬p
(viii) ¬(¬p)
(ix) ¬¬p
msdfm
– p. 16/83
1.4 Equivalências e implicações
Note que as tabelas-verdade para as proposições
¬(p ∨ q) e ¬p ∧ ¬q
têm os mesmos valores-verdade.
Definic¸a˜o: Dizemos que duas proposições, p e q, são
logicamente equivalentes se elas têm a mesma tabela-verdade.
Nesse caso escrevemos
p ⇔ q.
Se p e q são logicamente equivalentes elas podem ser
intercambiadas em qualquer situação sem prejuizo.
msdfm
– p. 17/83
Exemplos simples de equivaleˆncia:
(i) p ⇔ p
(ii) p ∨ q ⇔ q ∨ p
(iii) p ∧ q ⇔ q ∧ p
(iv) (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)
(v) (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)
(vi) ¬(¬p) ⇔ p
msdfm
– p. 18/83
Leis de De Morgan:
(i) ¬(p ∨ q) ⇔ (¬p ∧ ¬q).
(ii) ¬(p ∧ q) ⇔ (¬p ∨ ¬q).
As relações entre negação, disjunção e conjunção acima são
chamadas “Leis de De Morgan”. Le-se:
A negac¸a˜o de uma disjunc¸a˜o e´ logicamente equivalente a
conjunc¸a˜o das negac¸o˜es.
A negac¸a˜o de uma conjunc¸a˜o e´ logicamente equivalente a
disjunc¸a˜o das negac¸o˜es.
msdfm
– p. 19/83
Implicac¸o˜es (condicionais) são as formas proposicionais mais
importantes em matemática. De fato,
• “Se ... então ...”
• “Hipótese” então “conclusão”
• “Hipótese” então “tese”
• “A” implica “B”
• “A” é suficiente para “B”
• etc...
msdfm
– p. 20/83
Em forma geral, para duas proposições p e q,
“Se p enta˜o q”
é uma proposição. Escrevemos
p→ q (p implica q).
p é chamada premissa (ou hipo´tese ou antecedente)
e
q conclusa˜o (ou consequencia ou consequente ou
tese).
msdfm
– p. 21/83
Para a proposição p→ q, obtemos a seguinte tabelas-verdade:
p q p → q
V V V
V F F
F V V
F F V
A implicac¸a˜o e´ falsa se, e somente se, o antecedente e´ verdadeiro
e o consequ¨ente e´ falso.
Note que o conectivo→ não é simétrico em p e q.
msdfm
– p. 22/83
Sa˜o equivalentes a p→ q:
(i) Se p enta˜o q
(ii) p implica q
(iii) p e´ mais forte que q
(iv) q e´ mais fraco que p
(v) p somente se q
(vi) q se p
(vii) p e´ suficiente para q
(viii) q e´ necessa´rio para p
(ix) Uma condic¸a˜o necessa´ria para p e´ q
(x) Uma condic¸a˜o suficiente para q e´ p msdfm
– p. 23/83
O conectivo Bicondicional
A proposição “p se e somente se q”, denotada por p↔ q, é
chamada bicondicionalidade. Ela é verdadeira se e somente se
seus componentes são ou ambos verdadeirosou ambos falsos.
Em outros termos, para a proposição p↔ q, temos a seguinte
tabelas-verdade:
p q p ↔ q
V V V
V F F
F V F
F F V
msdfm
– p. 24/83
Observac¸o˜es:
• Não confundir equivaleˆncia lo´gica (⇔) com
bicondicionalidade (↔).
• (p↔ q) ⇔ (p→ q) ∧ (q → p).
• Para p↔ q dizemos que p e´ necesssa´rio e suficiente para
q ou que p e q sa˜o equivalentes.
msdfm
– p. 25/83
Exercı´cio:
4. Use uma tabela-verdade para mostrar:
(i) (p ↔ q) ⇔
(
(p → q) ∧ (q → p)
)
.
(ii) (p → q) ⇔ (¬q → ¬p).
(iii) p ∧ (q ∨ r) ⇔
(
(p ∧ q) ∨ (p ∧ r)
)
.
(iv) p ∨ (q ∧ r) ⇔
(
(p ∨ q) ∧ (p ∨ r)
)
.
msdfm
– p. 26/83
Exercı´cio
5. Use uma tabela-verdade para mostrar que os pares
de proposições abaixo na˜o sa˜o logicamente
equivalentes (notação 6⇔).
(i) ¬(p ∧ q) 6⇔ (¬p ∧ ¬q).
(ii) ¬(p ∨ q) 6⇔ (¬p ∨ ¬q).
(iii) (p → q) 6⇔ (q → p).
(iv) ¬(p → q) 6⇔ (¬q → ¬p).
msdfm
– p. 27/83
Exercı´cio
6. Sem usar o conectivo↔ escreva uma negação de
p↔ q.
7. Supondo p, ¬q e r verdadeiros o que pode ser dito sobre:
(i) p → q.
(ii) q → p.
(iii) p → (q ∧ r).
(iv) p ↔ q.
(v) p ↔ r.
(vi) (p ∨ q) → p.
(vii) (p ∧ q) → q.
msdfm
– p. 28/83
Um pouco mais de “logiqueˆs”
Dado p → q dizemos:
• (q → p) é chamada de recı´proca de (p→ q).
• (¬q → ¬p) é chamada de contrapositivo de
(p→ q).
• (¬p→ ¬q) é chamada de inverso de (p→ q).
msdfm
– p. 29/83
Exercı´cio
8. Encontre:
(i) O contrapositivo de ¬p → q.
(ii) A recíproca de ¬q → p.
(iii) O inverso da recíproca de q → ¬p.
(iv) A negação de p → ¬q.
(v) A recíproca de ¬p ∧ q.
msdfm
– p. 30/83
1.5 Tautologias
Tautologia:
• Uso de palavras diferentes para expressar uma mesma
idéia; redundância, pleonasmo.
• Proposição analítica que permanece sempre verdadeira,
uma vez que o atributo é uma repetição do sujeito.
• Expressão que repete o mesmo conceito já emitido, ou que
só desenvolve uma idéia citada, sem aclarar ou aprofundar
sua compreensão.
Etimologia gr. tautología,as ’repetição (de forma ou significado), o que diz a mesma coisa já
dita’; ver taut(o)- e -logia
msdfm
– p. 31/83
Tautologias:
“Proposic¸o˜es cuja tabela-verdade conte´m somente V na
u´ltima coluna”.
Exemplos:
• p ∨ ¬p;
p ¬p p ∨ ¬p
V F V
F V V
• p→ (p ∨ q);
p q p ∨ q p→ (p ∨ q)
V V V V
V F V V
F V V V
F F F V
msdfm
– p. 32/83
Contradic¸a˜o:
“Proposic¸a˜o que sempre e´ falsa; negac¸a˜o de uma tautologia”.
Exemplo:
• (p ∧ ¬q) ∧ (p→ q);
p q ¬q p ∧ ¬q (p→ q) (p ∧ ¬q) ∧ (p→ q)
V V F F V F
V F V V F F
F V F F V F
F F V F V F
msdfm
– p. 33/83
Observac¸o˜es:
• Como distinguir equivaleˆncia lo´gica (⇔) de
bicondicionalidade (↔)?
(p⇔ q) se e somente se (p↔ q) e´ uma tautologia.
Definic¸a˜o: Dizemos que p implica logicamente q (ou q e´ uma
implicac¸a˜o lo´gica de p), escrevemos
p⇒ q,
se p→ q é uma tautologia.
msdfm
– p. 34/83
Exemplos
(i) p→ (p ∨ q) é uma implicação lógica, isto é, p⇒ (p ∨ q).
(ii) (p ∧ q)→ p é uma implicação lógica, isto é, (p ∧ q)⇒ p.
(iii) p→ (p ∧ q) na˜o é uma implicação lógica (verifique!).
msdfm
– p. 35/83
”Tautologias produzem as regras com as quais
raciocinamos”.
Principais tautologias: Sejam p, q, r e s proposições quaisquer ,
c uma contradição e t uma tautologia.
1. p ∨ ¬p
2. ¬(p ∧ ¬p)
3. p→ p
4. Leis idempotentes
4.1. p↔ (p ∨ p)
4.2. p↔ (p ∧ p)
5. Negação dupla
¬¬p↔ p
msdfm
– p. 36/83
6. Leis comutativas
6.1. (p ∧ q)↔ (q ∧ p)
6.2. (p ∨ q)↔ (q ∨ p)
6.3. (p↔ q)↔ (q ↔ p)
7. Leis associativas
7.1. (p ∧ (q ∧ r))↔ ((p ∧ q) ∧ r)
7.2. (p ∨ (q ∨ r))↔ ((p ∨ q) ∨ r)
8. Leis distributivas
8.1. (p ∧ (q ∨ r))↔ ((p ∧ q) ∨ (p ∧ r))
8.1. (p ∨ (q ∧ r))↔ ((p ∨ q) ∧ (p ∨ r))
9. Leis de identidade
9.1. (p ∨ c)↔ p
9.2. (p ∧ c)↔ c
9.3. (p ∨ t)↔ t
9.4. (p ∧ t)↔ p
msdfm
– p. 37/83
10. Leis de De Morgan
10.1. ¬(p ∧ q)↔ (¬p ∨ ¬q)
10.1. ¬(p ∨ q)↔ (¬p ∧ ¬q)
11. Equivalência
11.1. (p↔ q)↔ ((p→ q) ∧ (q → p))
11.1. (p↔ q)↔ ((p ∧ q) ∨ (¬p ∧ ¬q))
11.1. (p↔ q)↔ (¬p↔ ¬q))
12. Implicações
12.1. (p→ q)↔ (¬p ∨ q)
12.2. ¬(p→ q)↔ (p ∧ ¬q)
13. Contra-positivo
(p→ q)↔ (¬q → ¬p)
14. Redução ao absurdo
(p→ q)↔ ((p ∧ ¬q)→ c)
msdfm
– p. 38/83
15. Implicações
15.1. (p→ r) ∧ (q → r)↔ ((p ∨ q)→ r)
15.2. (p→ q) ∧ (p→ r)↔ (p→ (q ∧ r))
16. Lei de exportação
((p ∧ q)→ r)⇔ (p→ (q → r))
17. Adição
p→ (p ∨ q)
18. Simplificação
(p ∧ q)→ p
19. Modus ponens
(p ∧ (p→ q))→ q (Se p então q. p portanto q)
20. Modus tollens
((p→ q) ∧ ¬q)→ ¬p (Se p, então q. q é falso. Então, p é falso.)
msdfm
– p. 39/83
21. ((p→ q) ∧ (q → r))→ (p→ r)
22. ((p ∨ q) ∧ ¬p)→ q
23. Absurdo
((p→ c)→ ¬p
24. ((p→ q) ∧ (r → s))→ ((p ∨ r)→ (r ∨ s))
25. ((p→ q)→ (p ∨ r)→ (q ∨ r))
Como são tautologias, 4-16 acima também são equivalências
lógicas (⇔) e 17-25 implicações lógicas (⇒).
msdfm
– p. 40/83
Exercı´cio
9. Verifique entenda e memorize o máximo que puder das
tautologias 1-25 listadas.
10. Procure traduzir algumas das tautologias 1-25 listadas em
linguagem usual. Por exemplo,
22. ((p ∨ q) ∧ ¬p)→ q :
“A bola escolhida é preta ou amarela. Ela não é preta. Concluimos que ela é amarela".
11. Quais das seguintes são corretas?
(i) (p→ (q ∨ r)) ⇒ (p→ q)
(ii) ((p ∨ q)→ r) ⇒ (p→ r)
(iii) (p ∨ (p ∧ q)) ⇔ p
(iv) ((p→ q) ∧ ¬p) ⇒ ¬q
msdfm
– p. 41/83
12. Quais das seguintes são tautologias, contradições ou
nenhuma delas?
(i) (p ∧ ¬q)→ (q∨ 6= p)
(ii) ¬p→ p
(iii) ¬p↔ p
(iv) (p ∧ ¬p)→ p
(v) (p ∧ ¬p)→ q
(vi) (p ∧ ¬q)↔ (p→ q)
(vii) ((p→ q)↔ r))↔ ((p→ (q ↔ r))
msdfm
– p. 42/83
1.6 Argumentos e princípios de demonstração
• Por um argumento (ou teorema) entendemos uma
proposição da forma
(p1 ∧ p2 ∧ · · · ∧ pn)→ q.
• p1, p2, . . . , pn são chamadas de premissas ou hipo´teses e q
deconclusa˜o.
• Um argumento e´ va´lido (ou o teorema e´ verdadeiro) se
ele é uma tautologia
• Se o argumento é válido dizemos que q é a consequeˆncia
lo´gica de p1, p2, . . . , pn
msdfm
– p. 43/83
• Note que um argumento válido é uma implicação lógica
(⇒)
• Se um argumento é válido, a conclusão pode ser verdadeira
ou falsa. Um argumento válido significa que se todas as
premissas são verdadeiras então a conclusão é
obrigatoriamente verdadeira
msdfm
– p. 44/83
• Exemplo:
(
¬q ∧ (p→ q)
)
→ ¬p.
Premissa Premissa Conclusão Argumento
p q ¬q p→ q ¬q ∧ (p→ q) ¬p
(
¬q ∧ (p→ q)
)
→ ¬p
V V F V F F V
V F V F F F V
F V F V F V V
F F V V V V V
• Observa-se na última coluna da tabela-verdade que o argumento é uma tautologia.
• A conclusão (¬p) pode ser falsa ou verdadeira (penúltima coluna).
• Se as premissas são verdadeiras, então a conclusão é verdadeira!
msdfm
– p. 45/83
• Considere agora o argumento(
¬p ∧ (p→ q)
)
→ ¬q.
Premissa Premissa Conclusão Argumento
p q ¬p p→ q ¬q ∧ (p→ q) ¬q
(
¬q ∧ (p→ q)
)
→ ¬p
V V F V F F V
V F F F F V V
F V V V V F F
F F V V V V V
Claramente esse argumento não é uma tautologia, na terceira
linha as premissas são verdadeiras mas a conclusão é falsa,
portanto o argumento na˜o e´ va´lido.
msdfm
– p. 46/83
É usual apresentar argumentos na vertical. Inicialmente
listando-se as premissas, depois uma linha horizontal e por
último a conclusão. Assim, os argumentos
(
¬q ∧ (p→ q)
)
→ ¬p e
(
¬p ∧ (p→ q)
)
→ ¬q
são escritos na forma
¬q
p→ q
¬p
e
¬p
p→ q
¬q
msdfm
– p. 47/83
Como exemplo dos casos acima,
((
¬q ∧ (p→ q)
)
→ ¬p
)
e
((
¬p ∧ (p→ q)
)
→ ¬q
)
,
considere “p : 2 + 2 = 4” e “q : 3 + 5 = 7”. Assim,
“3 + 5 6= 7”
“Se 2 + 2 = 4 enta˜o 3 + 5 = 7”
“2 + 2 6= 4”
e
“2 + 2 6= 4”
“Se 2 + 2 = 4” enta˜o 3 + 5 = 7”
“3 + 5 6=7”
• No primeiro caso, um argumento válido, a conclusão é falsa.
• No segundo, um argumento inválido, a conclusão é verdadeira.
• !?!?!?!?!?!?!?!?!?!?!?
• A validade (ou não) de um argumento é baseada somente na sua forma e não na verdade
ou falsidadade das proposições envolvidas.
• Em um argumento válido, podemos garantir que a conclusão é verdadeira somente
quando todas as premissas são verdadeiras.
•
“Se 2 + 2 = 4” enta˜o 3 + 5 = 7"é falsa!
msdfm
– p. 48/83
O uso de tabelas-verdade para verificar a validade de
um argumento pode ser proibitivo quando o número
de premissas é grande.
Um método alternativo é o chamado
Princı´pios de demonstrac¸a˜o.
msdfm
– p. 49/83
Princı´pios de demonstrac¸a˜o: A demonstração de um
argumento
(p1 ∧ p2 ∧ · · · ∧ pn)→ q
é uma sequeˆncia de proposic¸o˜es, s1, s2, . . . , sk, onde
(1) sk é q
(2) Cada si, i = 1, 2, . . . , k, na sequência satisfaz um ou mais
dos seguintes requerimentos:
(a) si é uma das hipóteses (premissas).
(b) si é uma tautologia.
(c) si é uma consequência lógica (⇒) das proposições anteriores na sequência.
Se as premissas são verdadeiras, cada proposição si será
verdadeira, em particular a conclusão.
msdfm
– p. 50/83
Exemplos
1.
(
¬p ∧ (q → p)
)
→ ¬q.
Proposição Razão
s1 : ¬p Hipótese
s2 : q → p Hipótese
s3 : ¬p→ ¬q Contra-positivo de s2(Tautologia: (q → p)→ (¬p→ ¬q))
s4 : ¬q Consequência lógica de s1 e s3
((
(¬p→ ¬q) ∧ ¬p
)
→ ¬q
)
Ou diretamente pela tautologia 20 na lista.
msdfm
– p. 51/83
2.
(
(p ∨ q) ∧ ((q → ¬p) ∧ (p→ q)
)
→ q.
Proposição Razão
s1 : q → ¬p Hipótese
s2 : p→ q Hipótese
s3 : ¬q → ¬p Contra-positivo de s2
s4 : (q ∨ ¬q)→ ¬p Consequência lógica de s1 e s3 (15.1)
s5 : q ∨ ¬q Tautologia
s6 : ¬p Consequência lógica de s4 e s5 (19)
s7 : p ∨ q Hipótese
s8 : q Consequência lógica de s6 e s7 (22)
msdfm
– p. 52/83
Alternativamente,
(
(p ∨ q) ∧ ((q → ¬p) ∧ (p→ q)
)
→ q.
Proposição Razão
s1 : q → ¬p Hipótese
s2 : p→ q Hipótese
s3 : p→ ¬q Contra-positivo de s1
s4 : p→ (q ∧ ¬q) Consequência lógica de s2 e s3 (15.2)
s5 : ¬p Consequência lógica de s4, Absurdo (23)
s6 : p ∨ q Hipótese
s7 : q Consequência lógica de s5 e s6 (22)
msdfm
– p. 53/83
Me´dodo de demosntrac¸a˜o por contradic¸a˜o
(ou indireta)
Esta alternativa de demonstração é baseada na
tautologia de redução ao absurdo
(p→ q)↔ (p ∧ ¬q)→ c (14),
onde c é uma contradição.
Aplicando esta tautologia ao argumento de interesse
temos
(
(p1 ∧ p2 ∧ · · · ∧ pn)→ q
)
↔
(
(p1 ∧ p2 ∧ · · · ∧ pn ∧ ¬q)→ c
)
.
Como temos uma equivalência lógica, podemos substituir o lado
direito pelo lado esquerdo sem nenhum prejuizo.
msdfm
– p. 54/83
Exemplo:
(
(p ∨ q) ∧ ((q → ¬p) ∧ (p→ q)
)
→ q
Proposição Razão
s1 : ¬q Hipótese (negação da conclusão)
s2 : p ∨ q Hipótese
s3 : p Consequência lógica de s1 e s2
s4 : p→ q Hipótese
s5 : q Consequência lógica de s3e s4
s6 : q ∧ ¬q Consequência lógica de s1e s5 (CONTRADIC¸ ˜AO!)
s7 : q Consequência lógica de s6
Note que a hipótese (q → ¬p) não foi usada nesse método de
prova.
Pergunta:
(
(p ∨ q) ∧ (p→ q)
)
→ q é válido?
msdfm
– p. 55/83
• O princípio de demonstração é usado somente para mostrar
a validade de um argumento.
• O princípio de demonstração não serve para mostrar que
um argumento é invalido.
• Nossa incapacidade em mostrar a validade de um dado
argumento não quer dizer que ele não seja válido.
• Em um argumento válido a conclusão é obrigatoriamente
verdadeira se todas as premissas são verdadeiras.
• Se pudermos encontrar apenas um único caso onde as
premissas são verdadeiras mas a conclusão é falsa (um
contra-exemplo), então teremos demonstrado que o
argumento não é válido. msdfm
– p. 56/83
Exercı´cio
13. De um contra-exemplo para mostrar que o argumento
((p→ q) ∧ (¬p ∨ q))→ (q → p)
não é válido.
14. Verifique usando tabelas verdade os seguintes argumentos:
(i)
p→ q
¬p ∨ q
q → p
(ii)
p ∨ q
r → q
q
¬r
(iii)
p ∨ ¬q
¬p
¬q
msdfm
– p. 57/83
15. Estabeleça a validade dos argumentos abaixo usando o princípio de demonstração ou de um
contra-exemplo no caso de invalidade.
(i)
¬p ∨ q
p
q
(ii)
p→ q
r → ¬q
p→ ¬r
(iii)
¬p ∨ q
¬r → ¬q
p→ ¬r
(iv)
q → ¬p
¬q
p
(v)
¬p
p→ q
(vi)
(p ∧ q)→ (r ∧ s)
¬r
¬p ∨ ¬q
(vii)
p→ q
¬p→ ¬r
s→ (p ∨ r)
s
q
(viii)
p ∨ q
q → ¬r
¬r → ¬p
¬(p ∧ q)
(ix)
p→ q
¬r → ¬q
r →6= p
¬p
msdfm
– p. 58/83
(x)
p→ ¬p
¬p
(xi)
p ∨ q
p→ r
¬r
q
(xii)
p
q → ¬p
¬q → (r ∨ ¬s)
¬r
¬s
(xiii)
p→ (q ∨ s)
q → r
p→ (e ∨ s)
(xiv)
p→ ¬q
q → p
r → p
¬q
(xv)
p→ q
r → s
¬(p→ s)
q ∧ ¬r
msdfm
– p. 59/83
Quantificadores
x > 0
não é uma proposição pois como o valor de x não é
conhecido não podemos assinalar um valor-verdade.
Neste caso, x é chamado uma varia´vel, isto é, um
símbolo que pode asssumir diferentes valores
(também é chamados de interpretac¸o˜es).
Para cada possível valor de x, teremos uma
proposição. Assim, chamamos “x > 0” de uma
func¸a˜o proposicional, na verdade uma “função” de x
que assume como valor uma proposição.
msdfm
– p. 60/83
Fazendo
p(x) = “x > 0”;
• p(1) é a proposição “1 > 0” cujo valor-verdade é V .
• p(−1) é a proposição “− 1 > 0” cujo valor-verdade é F .
• p(0) é a proposição “0 > 0” cujo valor-verdade é F .
msdfm
– p. 61/83
Defnic¸a˜o:
Uma sentença contendo uma ou mais variáveis é
chamada uma sentenc¸a declarativa se quando
assinalamos valores particulares para as variáveis
envolvidas temos uma proposição.
Sentenças declarativas serão denotadas por
p(x), q(x, y), r(x, y, z), etc...
msdfm
– p. 62/83
Exemplos:
• p(x) = “x > 0”.
• p(x, y) = “x > y”;
• p(1, 0) tem valor-verdade V .
• p(0, 1) tem valor-verdade F .
• p(1, 1) tem valor-verdade F .
msdfm
– p. 63/83
Seja D o “conjunto” de todos os possíveis valores da variável x,
ou seja, o “domínio” da função proposicional p(x).
Um outro método de fazer com que p(x) se torne uma
proposição é referido como quantificac¸a˜o. Exite duas maneiras
com as quais quantificamos uma função proposicional p com
domínio D: Prefaciando a função proposicional p com:
1. “para todo x emD” ou “para qualquer x emD”, denotado por
“∀x em D”.
2. “existe x emD tal que” ou “para algum x emD tem-se a propriedade que” denotado por
“∃x em D ∋ ”.
msdfm
– p. 64/83
∀, ∃ e ∋ são chamados quantificadores;
• ∀ é chamado quantificador universal, lê-se
“para todo”,
• ∃ é chamado quantificador existencial, lê-se
“existe”, e
• ∋ é o simbolo para “tal que”.
msdfm
– p. 65/83
Assim:
∀x em D, p(x)
resultará em um valor-verdade V se p(x) é verdadeira
para todo valor de x em D e F caso contrário.
∃x em D ∋ p(x)
resultará em um valor-verdade V se p(x) é verdadeira
para pelo menos um valor de x em D e F caso
contrário.
msdfm
– p. 66/83
Se existe somente um número finito de possíveis
interpretações para x, isto é, um número finito de
possíveis valores de x, digamos x1, x2, . . . , xn, em
outras palavras, se D é finito, então
(
∀x em D, p(x)
)
↔
(
p(x1)∧ p(x2)∧ · · · ∧ p(xn)
)
e
(
∃x emD ∋ p(x)
)
↔
(
p(x1)∨p(x2)∨· · ·∨p(xn)
)
msdfm
– p. 67/83
No caso degenerado onde não existem interpretações,
isto é, “D é vazio” , não importando o que seja p(x),
tem-se:
• ∀x em D, p(x)
é sempre verdadeira pois não podemos produzir
um valor de x para o qual p(x) seja falsa.
• ∃x em D ∋ p(x)
é sempre falsa pois não podemos produzir um
único valor de x para o qual p(x) seja verdadeira.
msdfm
– p. 68/83
Negac¸o˜es:
É fácil ver (exercício) que:¬
(
∀x em D, p(x)
)
↔
(
∃x em D ∋ ¬p(x)
)
¬
(
∃x em D ∋ p(x)
)
↔
(
∀x em D,¬p(x)
)
Se D é finito, isto é apenas uma extensão da Lei de De Morgan.
Exemplo:
¬
(
∀x em D, (p(x)→ q(x))
)
→
∃x em D ∋ ¬(p(x)→ q(x))→
∃x em D ∋ (p(x) ∧ ¬q(x)).
msdfm
– p. 69/83
Exercı´cio
16. Verifique as negações acima.
17. Represente usando quantificadores:
(i) “Todo p(x) é um q(x)”.
(ii) “Algum p(x) é um q(x)”.
18 Escreva na forma simbólica, indicando escolhas apropriadas
de interpretações (domínio).
(i) Existe um número inteiro x tal que x+ 2 = 4.
(ii) x2 − 4 = 0 tem uma solução positiva.
(iii) Toda solução de x2 − 4 = 0 é positiva.
msdfm
– p. 70/83
19. Discuta as seguintes proposições;
(i) (∀x em D, p(x))→ (∃x em D ∋ p(x)).
(ii) (∃x em D ∋ p(x))→ (∀x em D, p(x)).
(iii) (∀x em D,¬p(x))→ ¬(∀x em D, p(x)).
(iv) ¬(∀x em D, p(x))→ (∀x em D,¬p(x)).
(v) ¬(∃x em D ∋ p(x))→ (∃x em D ∋ ¬p(x)).
msdfm
– p. 71/83
Mais sobre quantificadores
Algumas situações exigem mais do que um quantificador. Por
exemplo,
•
“Para todo nu´mero par n existe um nu´mero inteiro k tal que n = 2k”.
•
“Para toda reta l e para todo ponto a, fora de l, existe uma reta l’ que passa por a e e´
paralela a l”
Seja f uma “função” com “domínio” em D e “contra-domínio”
em B”:
•
“Para todo y em B, existe x emD tal que f(x) = y”.
• Para todo x no domı´nio de f e para todo nu´mero ǫ > 0, existe um nu´mero δ > 0 tal que
|x− c| < δ implica |f(x)− L| < ǫ”.
msdfm
– p. 72/83
Considere a proposição:
∀x em S, ∃y em T ∋ p(x, y)
A leitura deve ser feita sempre da esquerda para a direita. Ou
seja,
∀x em S,
(
∃y em T ∋ p(x, y)
)
Note a diferença para a proposição
∃y em T ∋ ∀x em S, p(x, y)
msdfm
– p. 73/83
É importante observar que:
• Em uma proposição do tipo
∀x em S, ∃y em T ∋ p(x, y),
(em outros termos, para cada x em S, vai existir um y em
T tal que p(x, y) e´ verdadeira) o valor de y pode depender
da escolha do valor de x
• Por outro lado, para
∃y em T ∋ ∀x em S, p(x, y)
ser verdadeira, deve existir ao menos um valor de y,
digamos y0, tal que p(x, y0) é verdadeira para toda escolha
de x.
msdfm
– p. 74/83
Exercı´cios:
20. Se os possíveis valores da variável x em S são s1 e s2 e os
possíveis valores da variável y em T são t1 e t2, verifique que:
∀x em S, ∃y em T ∋ p(x, y)↔
((
p(s1, t1) ∨ p(s1, t2)
)
∧
(
p(s2, t1) ∨ p(s2, t2)
))
e
∃y em T ∋ ∀x em S, p(x, y)↔
((
p(s1, t1) ∧ p(s2, t1)
)
∨
(
p(s1, t2) ∧ p(s2, t2)
))
.
21. O que acontece no Exercício 20 quando S e T são identicos e
p(x, y) = “x = y”?
22. Escreva a negação de
∀x em S, ∃y em T ∋ p(x)→ q(x, y).
msdfm
– p. 75/83
22. Os pares de proposições abaixo são equivalentes? Justifique!
(i) “Todo nu´mero inteiro e´ par ou impar” e “Todo nu´mero inteiro e´ par ou todo nu´mero
inteiro impar”.
(ii) (∀x em D, (p(x) ∨ q(x))) e ((∀x em D, p(x)) ∨ (∀x em D, q(x))).
(iii) (∀x em D, (p(x)→ q(x))) e ((∀x em D, p(x))→ (∀x em D, q(x))).
(iv) (∀x em D, (p(x) ∧ q(x))) e ((∀x em D, p(x)) ∧ (∀x em D, q(x))).
(v) (∃x em D ∋ (p(x) ∨ q(x))) e ((∃x em D ∋ p(x)) ∨ (∃x em D ∋ q(x))).
23. Escreva de forma simbólica
(i) “Para todo y em B existe x emD tal que f(x) = y”
(ii) “Para todo x no domı´nio de f e para todo nu´mero ǫ > 0 existe um nu´mero δ > 0 tal
que |x− c| < δ implica |f(x)− L| < ǫ”.
(iii) “A soma de dois nu´meros pares quaisquer e´ um nu´mero par”
(iv) “Para toda reta l e para todo ponto a fora de l existe uma reta l’ que passa por a e e´
paralela a l”
msdfm
– p. 76/83
Métodos de demonstração.
Três métodos de demonstração a serem considerados são:
• Demonstrac¸a˜o direta
(
p(x)→ q(x)
)
1. Assume a hipótese
2. Dedução lógica (corpo da demosntração)
3. Chega-se à conclusão
• Demonstrac¸a˜o do contrapositivo
(
¬q(x)→ ¬p(x)
)
1. Assume a negação da conclusão
2. Dedução lógica (corpo da demosntração)
3. Chega-se à negação da hipótese
• Demonstrac¸a˜o indireta ou por contradic¸a˜o(
(p(x) ∧ ¬q(x))→ c
)
1. Assume a hipótese e a negação da conclusão
2. Dedução lógica (corpo da demosntração)
3. Chega-se a uma contradição
msdfm
– p. 77/83
Mesmo nos livros de matemática avançados muitas
das demonstrações são apresentadas de maneira
informal, usando um mínimo da simbologia lógica.
No entanto, a estrutura lo´gica,
• hipo´tese,
• sequeˆncia de proposic¸o˜es que sa˜o
consequeˆncias lo´gicas de proposic¸o˜es pre´vias e
• conclusa˜o,
estara´ sempre presente.
msdfm
– p. 78/83
Exemplo: Assumindo que um número inteiro n é par se e
somente se existe um inteiro k tal que n = 2k, considere o
seguinte teorema:
Teorema: Se n em são números pares, então n+m é par.
Demonstrac¸a˜o: Sejam n em são números pares. Então existem
j e k inteiros tais que
n = 2k e m = 2j.
Então
m+ n = 2k + 2j = 2(k + j).
Portanto n+m é par. c.q.d
msdfm
– p. 79/83
Compare com:
Teorema: Seja P o “conjunto” dos números pares.
∀n em P, ∀m em P → (m+ n em P ).
Demonstrac¸a˜o:
∀n em P, ∀m em P, ∃j,∃k ∋ (n = 2k ∧m = 2j).
(n = 2k ∧m = 2j)→ m+ n = 2k + 2j = 2(k + j).
m+ n = 2(k + j)→ (m+ n em P ).
c.q.d
Note que a demostração do teorema foi dada na forma direta.
msdfm
– p. 80/83
Exercicio:
24. Demostre o teorema;
∀n em P, ∀m em P → (m+ n em P ),
onde P o “conjunto” dos números pares,
(i) Usando método contrapositivo.
(ii) Usando método indireto (contradição).
Observação: Sabemos que um número n é impar se e somente se
existe k tal que n = 2k + 1.
msdfm
– p. 81/83
25. Determine quais das seguintes “demonstrações” são corretas
e quais são incorretas. No caso de uma demonstração correta,
indique o tipo de método usado e no caso incorreto indique o
erro.
Teorema: Se x e y são números pares, então n−m é par.
(Prova 1) Suponha que x e y são números impares. Então existe números inteiros j e k tal que
x = 2j + 1 e y = 2k + 1. Logo
x− y = (2j + 1)− (2k + 1) = 2(j − k).
Portanto x− y é par.
(Prova 2) Suponha que x− y seja par e y seja impar. Então existem números inteiros j e k tal
que x− y = 2j e y = 2k + 1. Logo
y = y − x+ x = −2j + (2k + 1) = 2(k − j) + 1.
Portanto y é impar o que é uma contradição.
msdfm
– p. 82/83
(Prova 3) Suponha que x− y seja impar. Então existe um número j tal que x− y = 2j + 1. Se
y é par, a demonstração esta completa, suponhamos então que y é impar, isto é, y = 2k + 1 para
algum número k. Logo
x = (x− y) + y = (2j + 1) + (2k + 1) = 2(j + k) + 2 = 2
(
(j + k) + 1
)
.
Portanto x é par o que demonstra o teorema.
(Prova 4) Suponha que x e y são números pares e (x-y) é impar. Então existem números inteiros
j e k tal que x = 2j e y = 2k. Logo
x− y = 2j − 2k = 2(j − k)
portanto x− y é par. Mas isso contradiz a suposição que x− y é impar, completando a
demonstração.
(Prova 5) Suponha que x e y são números pares. Então existem números inteiros j e k tal que
x = 2j. Logo
x− y = 2j − 2k = 2(j − k).
Portanto x− y é par.
msdfm
– p. 83/83
	1.1 Introduc c~ao
	C'alculo proposicional
	small 1.2 Conectivos l'ogicos: {nullf e, ou e n~ao}
	small 1.3 Tabelas-verdade
	small 1.4 Equival^encias e implicac c~oes
	small 1.5 Tautologias
	small 1.6 Argumentos e princ'{i }pios de demonstrac c~ao
	small Quantificadores
	small M'etodos de demonstrac c~ao.