Fundamentos de Matemática: Lógica e Conectivos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Universidade Federal de Santa Catarina
Notas de Aula
Fundamentos de Matemática
Autores: Rafael Aleixo e Luiz-Rafael Santos
Blumenau, SC
21 de agosto de 2017
ii
Sumário
Prefácio v
1 Lógica 1
1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Conectivos e, ou, não e tabelas verdade . . . . . . . . . . . . . . . . . . . . . 1
1.3 Implicação e a bicondicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Tautologias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Argumentos e o princípio da demonstração . . . . . . . . . . . . . . . . . . . 17
1.6 Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.7 Mais quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.8 Métodos de demonstração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2 Conjuntos, Relações e Funções 41
2.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 Conjuntos Verdade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.3 Relações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.4 Mais relações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.5 Relações de Equivalência e Partições . . . . . . . . . . . . . . . . . . . . . . . 77
2.6 Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.7 Mais Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3 Indução Matemática 101
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.2 Princípio da Indução Matemática . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.3 Formas Equivalentes do Princípio da Indução Matemática . . . . . . . . . . . 106
Exercícios Resolvidos 113
Referências Bibliográficas 169
Índice Remissivo 171
iii
iv
Prefácio
Os fundamentos de matemática são essenciais para o entendimento e construção de ma-
teática. Os objetos de estudo (lógica, conjuntos, relações, funções e indução matemática)
darão ao leitor as ferramentas básicas para entender a linguagem e formalismo matemático.
Esse passo rumo à maturidade matemática é por um lado muito interessante pois nos faz
enxergar a matemática de um ponto de vista mais lógico-formal, por outro lado pode “dar
um nó” em nossa cabeça pois exige muito raciocínio e uma forma de pensar que muitos dos
leitores ainda não estão acostumados.
v
vi
Capítulo 1
Lógica
1.1 Introdução
Um amigo meu recentemente me disse que quando ele estudou lógica ele ficava com sono.
Eu respondi que ele parecia com sono e ele disse, “Sim, estou como sono”. Então ele adicionou,
“Portanto, você pode concluir que eu estava estudando lógica.” “Certamente, não!” eu respndi.
“Este é um bom exemplo de um argumento inválido”. De fato, se você estivesse estudando
lógica é óbvio que você não teria aprendido muito.
Este pequeno excerto de uma situação da vida real foi criado para ilustrar o fato que
usamos lógica em todos os dias de nossas vidas, embora nem sempre a usamos corretamente.
A lógica fornece o significado pelo qual obtemos conclusões e estabelecemos argumentos. A
lógica também fornece regras pelas quais raciocinamos em matemática. Para ser bem sucedido
em matemática teremos que entender precisamente as regras da lógica. Claramente, podemos
também aplicar estas regras a outras áreas da vida além de matemática e surpreender (ou
desanimar) nossos amigos com nossa lógica, mentes bem treinadas.
Neste capítulo descreveremos os vários conectivos usados em lógica, desenvolver a notação
simbólica, descobrir algumas regras úteis de inferência, discutir quantificação e exibir alguma
formas típicas de demonstração. Embora nossa dicussão sobre conectivos e tabelas verdade
no começo seja bastante mecânica e não requereira muita reflexão, ao final do capítulo esta-
remos analisando demonstrações e escrevendo algumas por nós mesmos, um processo menos
mecânico e bem profundo.
1.2 Conectivos e, ou, não e tabelas verdade
Os blocos básicos da lógica são as proposições. Por proposições entendemos como uma
sentença declarativa a qual é verdadeira ou falsa, mas não ambas. Por exemplo, “2 é maior que
3” e “todo triângulo equilátero tem os três ângulos congruentes” são proposições, enquanto
“x ≤ 3” e “esta sentença é falsa” não o são (a primeira é uma sentença declarativa mas não
podemos dizer se é verdade até definirmos o valor de x, tente determinar se a segunda é
verdade). Denotaremos proposições por letras minúsculas, p, q, r, s, etc. Em uma discussão
letras diferentes podem ou não representar proposições diferentes, mas uma letra aparecendo
mais de uma vez em uma dada discussão sempre será representada pela mesma proposição.
Uma proposição verdadeira dará um valor verdade de V (de verdadeiro) e uma proposição
1
2
falsa dará um valor verdade de F (de falso). Por exemplo, “2 + 3 < 7” tem valor verdade de
V enquanto “2 + 3 = 7” tem valor verdade de F.
Estamos interessados em combinar simples proposições (às vezes chamadas subproposi-
ções) para gerar proposições mais complicadas (ou compostas). Combinamos proposições com
conectivos, entre os quais são “e”,“ou”, e “implica”. Se p, q são duas proposições então “p e
q” é também uma proposição, chamada de conjunção de p e q, e denotadas por
p ∧ q.
O valor verdade de p∧q depende dos valores verdade das proposições p e q : p∧q é verdade
quando ambos p e q são verdade, caso contrário é falso. Note que, esse é o significado usual
de “e” que utilizamos em Português. A palavra “mas” tem o mesmo sentido lógico que “e”
mesmo que no Português corrente tenha uma conotação ligeiramente diferente. Uma maneira
conveniente para representar este fato é utilizando a tabela verdade. Quando cada uma de
duas proposições p e q tem dois possíveis valores verdade, juntos eles têm 2× 2 = 4 possíveis
valores verdade, a tabela abaixo lista todas as possibilidades:
p q p ∧ q
V V V
V F F
F V F
F F F
Então, por exemplo, quando p é V e q é F (linha 2 da tabela verdade), p∧ q é F. De fato,
a tabela verdade pode ser tomada como a definição do conectivo ∧.
Deve-se comentar aqui que a tabela verdade acima não tem nada a ver com p e q, já que é
apenas utilizada para definir p∧q. A tabela verdade pode ser vista como o x em f(x) = 3x+8.
O que a tabela verdade nos diz, por exemplo, é que quando a primeira proposição é F e a
segunda é V (terceira linha da tabela) a conjunção das duas proposições é F. Você pode
verificar sua compreensão disso fazendo o exercício 5 desta seção.
Outro conectivo comum é o “ou”, às vezes chamado de disjunção. A disjunção de p e q,
denotada por
p ∨ q,
é verdade quando pelo menos um de p, q é verdade. Isso é chamado de o “ou inclusivo”,
e corresponde ao “e/ou” que às vezes encontramos em documentos. Note que, em nossas
conversas do dia a dia utilizamos o “ou” de maneira exclusiva, isto é, tem valor verdade V
somente quando exatamente uma das subproposições é verdade. Por exemplo, a verdade de
“Quando você me ligou eu devo ter ido tomar banho ou ter passeado com o cachorro” não é
esperada quando se inclui ambas as possibilidades. Em matemática nós sempre usamos “ou”
no sentido inclusivo como definido acima e a tabela verdade é dada abaixo:
p q p ∨ q
V V V
V F V
F V V
F F F
3
Dada uma proposição p, podemos formar uma nova proposição com o opostos do valor
verdade, chamada de negação de p, também denotada por
¬p,
e é normalmente lida como “não p”.
A tabela verdade da negação é:
p ¬ p
V F
F V
Podemos formar a negação de uma proposição, sem o entendimento do significado da
mesma, com “ é falso que” ou “não é o caso que”, mas a proposição resultante é estranha
e não passa a real natureza da negação. Uma consideração
mais precisa do siginificado da
proposição em questão geralmente indicará uma melhor maneira de expressar a negação. Mais
adiante veremos métodos para negar proposições compostas.
Considere os seguintes exemplos abaixo:
a) 3 + 5 > 7
b) Não é o caso que 3 + 5 > 7
c) 3 + 5 ≤ 7
d) x2 − 3x+ 2 = 0 não é uma equação quadrática
e) Não é verdade que x2 − 3x+ 2 = 0 não seja um equação quadrática
f) x2 − 3x+ 2 = 0 é uma equação quadrática
Note que, b) e c) são negações de a); e) e f) são negações de d), mas c) e f) são mais adequadas
que b) e e) respectivamente.
Usaremos a mesma convenção para ¬ da que se usa em álgebra elementar; com efeito, a
negação é aplicada somente ao próximo símbolo, o qual, neste caso, representa uma propo-
sição. Então, ¬p ∨ q significará (¬p) ∨ q ao invés de ¬(p ∨ q), assim como −3 + 4 representa
1 e não −7. Com esta convenção evitamos ambiguidade quando negamos uma composta de
proposições em Português. Por exemplo, como distinguimos entre ¬p ∨ q e ¬(p ∨ q) em Por-
tuguês? Suponha que, p representa “2 + 2 = 4” e q representa “3 + 2 < 4”. A proposição
“Não é o caso que 2 + 2 = 4 ou 3 + 2 < 4” deve significar ¬(p ∨ q) ou ¬p ∨ q? Se usamos a
mesma convenção que utilizamos para nosso símbolos, devemos ter ¬p∨ q. Mas, se tomarmos
esse significado, como diremos ¬(p ∨ q)? O problema parece ser o mesmo do equivalente ao
parênteses que usamos para agrupamento. Vamos adotar a convenção que “não é o caso que”
(ou uma negação similar) aplica-se a tudo que segue até algum tipo grupamento claramente
estabelecido. Então “Não é o caso que 2 + 2 = 4 ou 3 + 2 < 4” significaria ¬(p∨ q), enquanto
que “Não é o caso que 2+2 = 4, ou 3+2 < 4” significaria ¬p∨q. Claramente, quando falamos,
devemos ser muito cuidadosos usando pausas para, assim, indicar o significado correto.
Tabelas verdade podem ser utilizadas para expressar os possíveis valores verdade de pro-
posições compostas construindo colunas de uma maneira metódica. Por exemplo, desejamos
4
construir uma tabela verdade para ¬(p ∨ ¬q). Começamos uma tabela verdade de quatro
linhas (existem quatro possibilidades) da seguinte forma:
p q ¬ ( p ∨ ¬ q )
V V
V F
F V
F F
Os valores verdade são preenchidos passo por passo:
p q ¬ ( p ∨ ¬ q )
V V V V
V F V F
F V F V
F F F F
preenchemos as colunas p e q
p q ¬ ( p ∨ ¬ q )
V V V F V
V F V V F
F V F F V
F F F V F
preenchemos a coluna ¬ q
p q ¬ ( p ∨ ¬ q )
V V V V F V
V F V V V F
F V F F F V
F F F V V F
preenchemos a coluna p ∨¬ q
p q ¬ ( p ∨ ¬ q )
V V F V V F V
V F F V V V F
F V V F F F V
F F F F V V F
preenchemos a coluna ¬ (p ∨¬ q)
Depois que alguma experiência é obtida, muitos dos passos escritos acima podem ser
eliminados. Note, também, que se a proposição composta envolve n subproposições então sua
tabela verdade requerirá 2n linhas. Portanto, por exemplo, a proposição composta de quatro
subproposições necessitará de 24 = 16 linhas.
5
Exercícios 1.2
1. Determine os valores verdade das seguintes proposições
a) 3 ≤ 7 e 4 é um inteiro ímpar.
b) 3 ≤ 7 ou 4 é um inteiro ímpar.
c) 2 + 1 = 3 mas 4 < 4.
d) 5 é ímpar ou divisível por 4.
e) Não é verdade que 2 + 2 = 5 e 5 > 7.
f) Não é verdade que 2 + 2 = 5 ou 5 > 7.
g) 3 ≥ 3.
2. Suponha que representamos “7 é um número par” por p e “3+1 = 4” por q e “24 é diísivel
por 8” por r.
a) Escreva na forma símbólica e determine os valores verdade para:
i) 3 + 1 6= 4 e 24 é divísivel por 8.
ii) Não é verdade que 7 é ímpar ou 3 + 1 = 4.
iii) 3 + 1 = 4 mas 24 não é divísivel por 8.
b) Escreva o que vem a seguir em palavras e determine os valores verdade para:
i) p ∨ ¬ q.
ii) ¬ (r ∧ q).
iii) ¬ r ∨ ¬ q.
3. Construa a tabela verdade para:
a) ¬ p ∨ q.
b) ¬ p ∧ q.
c) (¬ p ∨ q) ∧ r.
d) ¬ (p ∧ q).
e) ¬ p ∧ ¬ q.
f) ¬ p ∨ ¬ q.
g) p ∨ ¬ p.
h) ¬ (¬ p).
4. Construa negações úteis para:
a) 3− 4 < 7.
b) 3 + 1 = 5 e 2 ≤ 4.
c) 8 é divisível por 3 mas 4 não é.
5. Suponha que definimos o conectivo ? dizendo que p ? q é verdade somente quando q é
verdade e p é falso, e é falso caso contrário.
a) Escreva a tabela verdade de p ? q.
b) Escreva a tabela verdade de q ? p.
c) Escreva a tabela verdade de (p ? p) ? q.
6
6. Vamos denotar o “ou exclusivo” às vezes utilizado nas conversas do dia a dia por ⊕.
Portanto, p ⊕ q será verdade exatamente quando uma condição de p, q é verdade e falso
caso contrário.
a) Escreva a tabela verdade de p⊕ q.
b) Escreva a tabela verdade de p⊕ p e (p⊕ q)⊕ q.
c) Mostre que “e/ou” realmente significa “e ou ou”, isto é, a tabela verdade para (p∧q)⊕
(p⊕ q) é a mesma tabela verdade que (p ∨ q).
d) Mostre que não faz diferença se tomamos o “ou” em “e/ou” como sendo inclusivo (∨)
ou exclusivo (⊕).
7. Explique a seguinte piada: Ansioso, o pai pergunta ao obstetra: “Doutor, é menino ou
menina?” O médico responde: “Sim.”
1.3 Implicação e a bicondicional
Se tivéssemos que escrever a tabela verdade de ¬ (p ∧ q) e ¬ p ∨ ¬ q (como, de fato,
já fizemos nos exercícios 3d e 3f acima) e compará-las então, notaríamos que essas duas
proposições tem os mesmos valores verdade e, portanto, em algum sentido são iguais. Esse
conceito é importante (importante suficiente para ter um nome), então a seguir fazemos a
seguinte definição:
Suponha que as duas proposições p, q tem a mesma tabela verdade. Então p e q são ditos
logicamente equivalentes, e denotaremos por
p ⇐⇒ q.
Basicamente, quando duas proposições são logicamente equivalentes elas têm a mesma forma,
e assim podemos utilizar uma ou a outra em outra proposição ou teorema. É importante
enfatizar que é a forma e não o valor verdade da proposição que determina se é (ou não)
equivalente a uma outra proposição. Por exemplo, “2 + 2 = 4” e “7 − 5 = 2” são ambas
proposições verdadeiras, mas não são logicamente equivalentes pois elas têm tabelas verdade
diferentes (se representamos a primeira proposição por p então a outra necessita um outro
símbolo, digamos q, e sabemos que elas não têm as mesmas tabelas verdade). Por outro lado,
“2+3 = 5 ou3−4 = 2” e “3−4 = 2 ou 2+3 = 5” são logicamente equivalentes. Para ver isso,
tome p representando “3− 4 = 2” e q representando “2 + 3 = 5”. A primeira proposição tem
a forma q ∨ p enquanto a segunda tem a forma p ∨ q. Uma rápida inspeção das duas tabelas
verdade nos mostra que estas duas proposições têm, de fato, a mesma tabela verdade.
Usando a ideia da equivalência lógica podemos formular certas relações entre negação,
disjunção e conjunção, também chamadas de Leis de DeMorgan:
Sejam p, q proposições quaisquer. Então
¬(p ∨ q) ⇐⇒ ¬p ∧ ¬q.
¬(p ∧ q) ⇐⇒ ¬p ∨ ¬q.
Já verificamos a segunda destas relações no exercícios 3d e 3f da seção 1.2. O leitor pode
verificar a outra simplesmente comparando as tabelas verdade. Em outras palavras, as lei de
7
DeMorgan dizem que, a negação de uma conjunção é logicamente equivalente a disjunção das
negações; e a negação de uma disjunção é logicamente equivalente a conjunção das negações.
Um erro comum é tratar ¬ em lógica como − em álgebra e pensar que ¬ distribui sobre ∨ e
∧ assim como − distribui sobre +. Isto é, desde que −(a+ b) = −a+ (−b), alguém poderia
pensar que ¬(p ∨ q) ⇐⇒ ¬p ∨ ¬q. Usando tabelas verdade pode-se ver que isso não está
correto. Então, enquanto nossa notação lógica parece de alguma forma “tipo-álgebra” (e, de
fato, é um certo tipo de álgebra), suas regras diferem daquelas da ágebra dos números reais
e não devemos fazer o mesmo erro de assumir que certas operações lógicas se comportam de
maneira análoga aos nosso amigos algébricos +, × e −.
Umas das formas proposicionais mais importantes em matemática é a da implicação ,
também chamada de condicional. De fato, todos os teoremas matemáticos são de alguma
forma uma implicação: Se “hipótese” então “conclusão”. A forma geral de implicação é “se p
então q”, onde p, q são proposições; vamos denotar este fato por:
p→ q.
Na condicional p→ q, p é chamada
de premissa (ou hipótese ou antecedente) e q é chamada
de conclusão (ou consequência ou tese ou consequente). A tabela verdade para p→ q é
p q p → q
V V V
V F F
F V V
F F V
Se pensarmos da maneira usual como damos significado ao implica, devemos concordar
que as duas primeiras linhas da tabela verdade acima correspondem ao uso comum que
fazemos, mas as duas últimas linhas podem não ser tão claras. É claro que, somos livres
para definir os valores verdade dos vários conectivos da maneira que quisermos e podemos
ter a posição que é essa a maneira que queremos definir implica (o que é de fato o caso) mas
vale a pena ver que a definição acima também está de acordo como usamos de forma diária.
Para este fim, vamos considerar o que será chamada “A parábola do cliente não satisfeito”.
Imagine que compramos um produto, digamos um sabão em pó chamado Limpão, depois
de ouvir o comercial que dizia, “Se você usar Limpão então sua roupa ficará branca!” Sob
quais circunstâncias podemos reclamar com o fabricante? Uma rápida reflexão revela que
certamente não podemos reclamar se não usamos Limpão (o comercial não dizia nada sobre
o que aconteceria se usassemos Omu, por exemplo), e não poderíamos reclamar se usassemos
Limpão e nossa roupa ficasse branca; portanto poderíamos reclamar somente no caso que
tivessemos usado Limpão e nossa roupa não ficasse branca (como prometido). Entretanto, a
promessa do comercial é falsa somente quando “Usamos Limpão e obtemos uma roupa que
não é branca” é verdade. Vamos utilizar nossa notação lógica para examinar essa situação
de forma precisa. Sejam, p representando “Usamos Limpão,” e q representando “Nossa roupa
está branca.” Então a promessa do comercial é
p→ q
8
e podemos reclamar (isto é, a promessa é falsa) somente no caso quando
p ∧ ¬q
é verdadeira. Portanto, p ∧ ¬q deve ser logicamente equivalente a ¬(p → q), chamada a
negação de p→ q. Escrevendo a tabela verdade para p ∧ ¬q, obtemos (convidamos o leitor a
verificar isso):
p q p ∧ ¬ q
V V F
V F V
F V F
F F F
Como esta proposição é logicamente equivalente à negação de p→ q, a tabela verdade de
p→ q deve ser a negação da tabela verdade acima (o qual é, veja o que foi feito anteriormente
para verificar isso) e a nossa definição lógica da implicação realmente concorda com o senso
comum.
Note que, somente o caso no qual p → q é falso é quando p é verdade e q é falso, isto é,
quando a hipótese é verdadeira e a conclusão é falsa. Portanto as seguintes implicações são
todas verdadeiras:
a) Se 2 + 2 = 4 então 1 + 1 = 2.
b) Se 2 + 3 = 4 então 1 + 1 = 5.
c) Se verde é vermelho então a lua é feita de queijo.
d) Se verde é vermelho então a lua não é feita de queijo.
e) 7 < 2 se 2 < 1.
Deve-se também notar que se uma implicação é verdade então sua conclusão pode ser
verdadeira ou falsa (veja os itens a) e b) acima), mas se a implicação é verdade e a hipótese
é verdade então a conclusão necessariamente é verdade. Isso, claramente, é a forma básica
de um teorema matemático: se sabemos que o teorema (uma implicação) é correto (verdade)
e a hipótese do teorema é verdade, podemos tomar a conclusão desse teorema como sendo
verdade.
Existem diversas maneiras de exprimir a condicional em Português e todas a seguir são
consideradas logicamente consistentes:
a) Se p então q.
b) p implica q.
c) p é mais forte que q.
d) q é mais fraca que p.
e) p somente se q.
9
f) q se p.
g) p é suficiente para q.
h) q é necessária para p.
i) Uma condição necessária para p é q.
j) Uma condição suficiente para q é p.
Na maior parte do tempo iremos utilizar as duas primeiras, mas é importante se familiari-
zar com o resto. Lembrando da definição de p → q nos ajudará a lembrar algumas dessas
maneiras. Por exemplo, quando dizemos que “r é suficiente para s”, significa que a verdade
de r é suficiente para garantir a verdade de s, isto é, queremos dizer que r → s. De forma
similar, quando dizemos que “r é necessária para s”, significa que quando s é verdade, r deve
necessariamente ser verdade também, isto é, queremos dizer que s→ r.
Quando observamos a tabela verdade para p → q notamos que não é simétrica com
respeito a p e q, isto é, a tabela verdade para p→ q não é a mesma tabela verdade para q → p.
Em outras palavras, estas duas proposições não são logicamente equivalentes e portanto não
podem ser substituídas uma pela outra. Por causa desta falta de simetria é conveniente fazer
a seguinte definição.
Dada a implicação p→ q:
i) q → p é chamada sua recíproca.
ii) ¬q → ¬p é chamada sua contrapositiva.
iii) ¬p→ ¬q é chamada sua inversa.
Mesmo que o leitor já tenha percebido isso, vale a pena dizer que a inversa de uma implicação
é a contrapositiva de sua recíproca (é também a recíproca da contrapositiva).
Talvez o erro lógico mais comum é aquele de confundir uma implicação com sua recíproca
(ou inversa). De fato, este erro parece estar na base de muitas propagandas. Por exemplo, se
nos dizem que “Se você usar Limpão então sua roupa ficará branca!” (que pode ser verdade),
espera-se que aparentemente acreditemos que se não usarmos Limpão então nossa roupa
não ficará branca. Mas isso é a inversa, a qual é logicamente equivalente a recíproca da
reivindicação original. Portanto, vemos que podemos acreditar na fala da Limpão e, ainda,
usar Omu com a consciência limpa e usar roupas brancas. Entretanto, uma implicação e sua
contrapositiva são logicamente equivalentes (veja nos exercícios a seguir) e, portanto, podem
ser usadas da mesma forma. Neste caso, isso significa que se nossas roupas não são brancas
então não usamos Limpão.
O conectivo final que vamos considerar é o bicondicional. Se p, q são duas proposições
então “p se e somente se q”, denotado por
p↔ q,
é chamado de bicondicional (não confundir com a equivalência lógica “ ⇐⇒ ”, embora haja
uma relação entre eles que será mostrada na próxima seção). Dizemos que p ↔ q é verdade
quando p, q têm o mesmo valor verdade e falso quando eles têm valor verdade distintos. Então
a tabela verdade para a bicondicional é
Outras maneiras de expressar p↔ q são:
10
p q p↔ q
V V V
V F F
F V F
F F V
i) p é necessária e suficiente para q.
ii) p é equivalente a q.
Como os nomes (bicondicional, se e somente se) e a notação sugerem, existe uma estreita
conecção entre a condicional e a bicondicional. De fato, p ↔ q é logicamente equivalente a
(p→ q) ∧ (q → p).
Exercícios 1.3
1. Escreva as senteças a seguir usando os símbolos da lógica matemática:
a) Se eu sou feliz, você é infeliz e se você é infeliz, eu não sou feliz.
b) José virá a festa e Maria não gostará ou José não virá a festa e Maria gostará da festa.
c) A novela será exibida, a menos que seja exibido programa político.
d) Se chover irei para casa, caso contrário, ficarei no escritório.
e) Se Maria é bonita, inteligente e sensível, e se Rodrigo ama Maria, então ele é feliz.
f) Se Sr. Oscar é feliz, Sra. Oscar é infeliz e se Sra. Grotta é feliz, Sr. Grotta é infeliz.
g) Maurício virá à festa e Kátia não virá, ou Maurício não virá festa e Kátia ficará Infeliz.
h) Irei ao teatro hoje somente se for uma peça de comédia.
i) Se minha namorada vier, irei ao teatro somente se for uma peça de drama.
2. Seja as proposições “p: Rafael joga futebol” e “q: Rafael joga basquete”. Escreva na lin-
guagem usual as seguintes proposições:
a) p ∨ q
b) p ∧ q
c) p ∧ ¬q
d) ¬p ∧ ¬q
e) ¬(¬p)
f) ¬(¬p ∧ ¬q)
3. Quais das seguintes proposições são logicamente equivalentes?
a) p ∧ ¬q.
b) p→ q.
c) ¬(¬p ∨ q).
d) q → ¬p.
e) ¬p ∨ q.
f) ¬(p→ q).
g) p→ ¬q.
h) ¬p→ ¬q.
4. Mostre que os seguintes pares são logicamente equivalentes:
11
a) p ∧ (q ∨ r); (p ∧ q) ∨ (p ∧ r) .
b) p ∨ (q ∧ r); (p ∨ q) ∧ (p ∨ r).
c) p↔ q; (p→ q) ∧ (q → p).
d) p→ q; ¬q → ¬p.
5. Mostre que os seguintes pares não são logicamente equivalentes:
a) ¬(p ∧ q); ¬p ∧ ¬q.
b) ¬(p ∨ q); ¬p ∨ ¬q
c) p→ q; q → p.
d) ¬(p→ q); ¬p→ ¬q.
6. Determine:
a) a contrapositiva de ¬p→ q.
b) a recíproca de ¬q → p.
c) a inversa da recíproca de q → ¬p.
d) a negação de p→ ¬q.
e) a recíproca de ¬p ∧ q.
7. Indique quais das proposições a seguir são verdadeiras:
a) Se 2 + 1 = 4 então 3 + 2 = 5.
b) Vermelho é branco se, e somente se, verde é azul.
c) 2 + 1 = 3 e 3 + 1 = 5 implicam que 4 é ímpar.
d) Se 4 é ímpar então 5 é ímpar.
e) Se 4 é ímpar então 5 é par.
f) Se 5 é ímpar então 4 é ímpar.
8. Conforme o caso, dê exemplos de, ou então, explique porque não pode existir:
a) Uma implicação verdadeira com uma conclusão falsa.
b) Uma implicação verdadeira com uma conclusão verdadeira.
c) Uma implicação falsa com uma conclusão verdadeira.
d) Uma implicação falsa com uma conclusão falsa.
e) Uma implicação falsa com uma hipótese falsa.
f) Uma implicação falsa com uma hipótese verdadeira.
g) Uma implicação verdadeira com uma hipótese verdadeira.
h) Uma implicação verdadeira com uma hipótese falsa.
9. Traduza em símbolos:
a) p sempre que q.
b) p a menos que q.
10. Dê a negação para p↔ q na forma que não envolva uma bicondicional.
11. Suponha que p, ¬q e r são verdade. Quais a seguir são proposições verdadeiras?
12
a) p→ q
b) q → p
c) p→ (q ∧ r)
d) p↔ q
e) p↔ r
f) (p ∧ q)→ p
g) (p ∨ q)→ q
12. Note que temos cinco “conectivos” lógicos: ∧, ∨, →, ↔ e ¬, cada qual corresponde a
uma construção da linguagem comum. Acontece que do ponto de vista lógico isto é, de
alguma forma, um deperdício já que podemos expressar todos estes conectivos em termos
de, apenas, ¬ e ∧. Ainda mais, se definirmos p | q para ser falsa quando ambos p e q
são verdadeiros, e verdadeiro caso contrário, podemos expressar todas as cinco formas em
termos deste único conectivo (| é conhecido como Conectivo de Sheffer ou Conectivo Nou).
Verifique parcialmente que os argumentos dados acima por
a) Encontrando a proposição a qual equivale a p ∨ q usando apenas ∧ e ¬.
b) Escrevendo a tabela verdade para p | q.
c) Mostrando que p | p é logicamente equivalente a ¬p.
d) Mostrando que (p | q) | (q | p) é logicamente equivalente a p ∧ q.
13. Escreva a recíproca, a negação e a contrapositiva das seguintes afirmações:
a) Cão que ladra não morde.
b) Nem tudo que reluz é ouro.
c) O que não mata engorda.
d) Quem não tem cão caça com gato.
e) Em boca fechada não entra mosca.
f) Onde há fumaça, há fogo.
1.4 Tautologias
Uma importante classe de proposições são aquelas que apresentam tabelas verdade con-
tendo apenas V’s na coluna final, isto é, proposições que são sempre verdadeiras e o fato de
serem smpre verdadeiras depende da sua forma e não a qualquer significado que pode ser
dado a elas (por exemplo o exercício 3g da seção 1.2: p∨¬p). Tais proposições são chamadas
tautologias. É importante fazermos uma distinção entre proposições verdadeiras e tautologias.
Por exemplo, “2+2=4” é uma proposição verdadeira mas não é uma tautologia pois sua forma
é p a qual não é sempre verdadeira. Por outro lado, “5 é a raíz primitiva de 17 ou 5 não é
uma raíz primitiva de 17” é uma tautologia não importanto o significado de raíz primitiva.
É uma tautologia em virtude de sua forma p ∨ ¬p apenas.
A negação de uma tautologia, isto é, a proposição que sempre é falsa, é chamada de
contradição . Devemos, também, fazer uma distinção entre contradições e proposições falsas
da mesma forma que distinguimos tautologias de proposições verdadeiras. Uma proposição é
uma contradição baseada apenas em sua forma. Como exemplos, considere as tabelas verdade:
Observe que, p→ (p ∨ q) é uma tautologia e (p→ q) ∧ (p ∧ ¬q) é uma contradição.
13
p q p → (p ∨ q)
V V V V V V V
V F V V V V F
F V F V F V F
F F F V F F V
p q (p → q) ∧ (p ∧ ¬ q)
V V V V V F V F F
V F V F F F V V V
F V F V V F F F F
F F F V F F F F V
Usando a ideia de tautologia, talvez podemos deixar claro a distinção entre “equivalente”
e “logicamente equivalente”. Duas proposições p, q são logicamente equivalentes se e somente
se p↔ q é uma tautologia. De fato, p↔ q e p ⇐⇒ q são proposições em dois níveis diferen-
tes. Se pensarmos que “p é equivalente a q” como uma proposição, então “ p é logicamente
equivalente a q” é uma proposição sobre essa proposição , chamada (meta)-proposição “p é
equivalente a q é verdade.” Por exemplo, (p→ q)↔ (¬q → ¬p) é uma implicação lógica en-
quanto p→ (p∧q) não é, esta implicação é “apenas” uma implicação que pode ser verdadeira
ou não.
Usamos a ideia de tautologia para definir o seguinte: dizemos que p→ q é uma implicação
lógica (também “p implica logicamente q ou q é uma consequencia lógica de p”) se p → q é
uma tautologia. p implica logicamente q é denotado por
p⇒ q.
Se p implica logicamente q, e p é verdade, então q tem que ser verdade também. Por exemplo,
p→ (p ∨ q) e (p ∧ q)→ p são implicações lógicas enquanto p→ (p ∧ q) não é (quando p é V
e q é F então a última implicação é F e portanto não é uma tautologia).
Tautologias são as regras pelas quais nós raciocinamos. Para referência futura uma lista,
com as mais comuns e com alguns de seus nomes, é dada abaixo. Para isso, p, q, r representam
proposições, c representa uma contradição e t representa uma tautologia.
14
Lista de tautologias
1. p ∨ ¬p
2. ¬(p ∧ ¬p)
3. p→ p
4. a) p↔ (p ∨ p) Leis idempotentes
b) p↔ (p ∧ p)
5. ¬¬p↔ p Dupla negação
6. a) (p ∨ q)↔ (q ∨ p) Comutatividade
b) (p ∧ q)↔ (q ∧ p)
c) (p↔ q)↔ (q ↔ p)
7. a) (p ∨ (q ∨ r))↔ ((p ∨ q) ∨ r) Associatividade
b) (p ∧ (q ∧ r))↔ ((p ∧ q) ∧ r)
8. a) (p ∧ (q ∨ r))↔ ((p ∧ q) ∨ (p ∧ r)) Distributividade
b) (p ∨ (q ∧ r))↔ ((p ∨ q) ∧ (p ∨ r))
9. a) (p ∨ c)↔ p Identidades
b) (p ∧ c)↔ c
c) (p ∨ t)↔ t
d) (p ∧ t)↔ p
10. a) ¬(p ∧ q)↔ (¬p ∨ ¬q) Leis de DeMorgan
b) ¬(p ∨ q)↔ (¬p ∧ ¬q)
11. a) (p↔ q)↔ ((p→ q) ∧ (q → p)) Equivalência
b) (p↔ q)↔ ((p ∧ q) ∨ (¬p ∧ ¬q))
c) (p↔ q)↔ (¬p↔ ¬q)
12. a) (p→ q)↔ (¬p ∨ q) Implicação
b) ¬(p→ q)↔ (p ∧ ¬q)
13. (p→ q)↔ (¬q → ¬p) Contrapositiva
14. (p→ q)↔ ((p ∧ ¬q)→ c) Reductio ad absurdum
15. a) ((p→ r) ∧ (q → r))↔ ((p ∨ q)→ r)
b) ((p→ q) ∧ (p→ r))↔ ((p→ (q ∧ r))
16. ((p ∧ q)→ r)↔ (p→ (q → r)) Lei de exportação
17. p→ (p ∨ q) Adição
18. (p ∧ q)→ p Simplicação
19. (p ∧ (p→ q))→ q Modus ponens
20. ((p→ q) ∧ ¬q)→ ¬p Modus tollens
21. ((p→ q) ∧ (q → r))→ (p→ r) Silogismo hipotético
22. ((p ∨ q) ∧ ¬p)→ q Silogismo disjuntivo
23. (p→ c)→ ¬p Absurdo
24. ((p→ q) ∧ (r → s))→ ((p ∨ r)→ (q ∨ s))
25. (p→ q)→ ((p ∨ r)→ (q ∨ r))
15
Observe na lista acima que, 4-16 são equivalências lógicas enquanto 17-25 são implicações
lógicas.
Uma das primeiras perguntas que os estudantes fazem quando vêm uma lista como a
acima é “Tenho que memorizar esta tabela?” A resposta é “Não, memorização não é sufici-
ente, você tem que saber todas elas! Elas têm que estar na sua forma de pensar.” Em um
primeiro momento, isto parece uma tarefa difícil, e talvez o seja. Mas algumas destas já es-
tão incorporadas na forma como pensamos. Por exemplo, se alguém diz: “vendemos garrafas
de água é com gás ou sem gás. Está não é com gás,” o que concluímos sobre a garrafa de
água? Concluímos que é uma garrafa de água sem gás e fazendo isso estaremos usando o
silogismo disjuntivo (item 22 da tabela de tautologias). De forma similar, alguém poderia
dizer “se eu leio o livro de fundamentos de matemática antes da aula então eu gosto da aula.
Eu li o livro de fundamentos de matemática hoje antes da aula.” Concluímos que a pessoa
que disse isso, gostou da aula de hoje. Esta é uma aplicação do modus ponens (item 19 da
tabela de tautologias), uma das mais básicas e importantes equivalências lógicas e formas de
racioncínio.
Não é importante que aprendamos os nomes das várias equivalências e implicações, mas é
importante que aprendamos suas formas para reconhecermos quando estamos utilizando-as.
É importante também reconhecer quando elas não parecem ou soam corretas, isto é, quando
utilizamos
alguma coisa que não é uma implição lógica.
Exercícios 1.4
1. Verifique que 7 a), 9 b), 13 e 14 da lista acima são tautologias.
2. Determine quais das seguintes proposições têm alguma forma presente na lista de tauto-
logias (por exemplo, (¬q ∧ p)→ ¬q tem a forma 18 da lista) e nestes casos, indique qual
forma:
a) ¬q → (¬q ∨ ¬p).
b) q → (q ∧ ¬p).
c) (r → ¬p)↔ (¬r ∨ ¬p).
d) (p→ ¬q)↔ ¬(¬p→ q).
e) (¬r → q)↔ (¬q → r).
f) (p→ (¬r ∨ q))↔ ((r ∧ ¬q)→ ¬p).
g) r → ¬(q ∧ ¬r).
h) (¬q ∨ p) ∧ q)→ p.
3. Dê exemplos ou diga porque as proposições a seguir não existem:
a) Uma implicação lógica com uma falsa conclusão.
b) Uma implicação lógica com uma conclusão verdadeira.
c) Uma implicação lógica com uma hipótese verdadeira e uma conclusão falsa.
4. Quais das seguintes são corretas?
a) (p→ (q ∨ r))⇒ (p→ q).
16
b) ((p ∨ q)→ r)⇒ (p→ r).
c) (p ∨ (p ∧ q)) ⇐⇒ p.
d) ((p→ q) ∧ ¬p)⇒ ¬q.
5. Quais das seguintes são tautologias, contradições ou nenhuma das duas?
a) (p ∧ ¬q)→ (q ∨ ¬p).
b) ¬p→ p.
c) ¬p↔ p.
d) (p ∧ ¬p)→ p.
e) (p ∧ ¬p)→ q.
f) (p ∧ ¬q)↔ (p→ q).
g) [(p→ q)↔ r]↔ [p→ (q ↔ r)].
6. Quais dos seguintes são corretos?
a) (p↔ q)⇒ (p→ q).
b) (p→ q)⇒ (p↔ q).
c) (p→ q)⇒ q.
7. → é associoativa? Isto é ((p→ q)→ r) ⇐⇒ ((p→ (q → r)).
8. ↔ é associoativa? Isto é ((p↔ q)↔ r) ⇐⇒ ((p↔ (q ↔ r)).
9. Quais das seguintes proposições verdadeiras são tautologias?
a) Se 2 + 2 = 4 então 5 é ímpar.
b) 3 + 1 = 4 e 5 + 3 = 8 implica 3 + 1 = 4.
c) 3 + 1 = 4 e 5 + 3 = 8 implica 3 + 2 = 5.
d) Vermelho é amarelo ou vermelho não é amarelo.
e) Vermelho é amarelo e vermelho é vermelho.
f) 4 é ímpar ou 2 é par e 2 é ímpar implica que 4 é ímpar.
g) 4 é ímpar ou 2 é par e 2 é ímpar implica que 4 é par.
10. Quais das seguintes são consequências lógicas do conjunto de proposições p ∨ q, r → ¬q,
¬p?
a) q.
b) r.
c) ¬p ∨ s.
d) ¬r.
e) ¬(¬q ∧ r).
f) q → r.
17
1.5 Argumentos e o princípio da demonstração
Quando ganhamos uma discussão? Claramente, tirando intimidação, coerção ou ameaças.
Estamos dizendo, convencer alguém da exatidão lógica de sua posição. Poderíamos começar
dizendo, “Você aceita p,q e r verdade?” Se a resposta é, “Sim, qualquer pateta pode ver isso!”
então você diz “Bem, então segue que t deve ser verdade.” Para ganhar essa discussão, deve
ser o caso (e isso é o que podemos argumentar) que (p∧q∧r)→ t é uma tautologia, isto é, não
existe de forma alguma que suas premissas (p, q, r que seu amigo já aceitou) sejam verdade
e sua conclusão, t, seja falsa. É assim a prova (demonstração) de um teorema matemático.
Na demonstração devemos mostrar que sempre que as premissas do teorema são verdade,
então a conclusão é verdade também. Agora, tentaremos colocar esta ideia de uma maneira
mais formal e então discutir algumas técnicas para demonstrar que um teorema está correto.
Começaremos com algumas definições.
Um argumento (ou teorema) é uma proposição da forma
(p1 ∧ p2 ∧ . . . ∧ pn)→ q.
Diremos que p1, p2, . . . , pn são premissas (ou hipótese) e q é a conclusão. Um argumento é
válido (ou um teorema é verdade) se é uma tautologia. Neste caso, dizemos que q (a conclusão)
é uma consequência lógica de p1, p2, . . . , pn (as premissas).
Observe que um argumento válido é uma implicação lógica. Pensando em tabelas verdade
para a implicação vemos que isto significa que sempre que p1, p2, . . . , pn são verdade então q
também é verdade. Vista por esta perspectiva, a definição de argumento válido dada acima
parecer concordar com o significado que usualmente damos. Se as premissas são todas verdade
e o argumento é válido então a conclusão é necessariamente verdade. Note que, se o argumento
é válido, a conclusão pode ser verdade ou falsa, tudo que está afirmado é que se as premissas
são todas verdade então a conclusão necessariamente é verdade. Por exemplo, considere o
seguinte argumento:
(¬q ∧ (p→ q))→ ¬p.
Uma maneira comum de exibir os argumentos é listar as premissas, traçar uma linha
horizontal e então escrever a conclusão. Assim, o argumento acima seria exibido como:
¬q
p→ q
¬p.
(1.1)
Para testar a validade deste argumento, podemos utilizar a tabela verdade:
p q (¬q ∧ p→ q) → ¬p
V V F F V V F
V F V F F V F
F V F F V V V
F F V V V V V
Como o argumento é uma tautologia, isto é, um argumento válido. Note que, isto significa
que sempre que as premissas são todas verdades (neste caso linha 4), a conclusão também é
verdade.
18
Agora, considere o argumento:
¬p
p→ q
¬q.
(1.2)
Novamente, escrevamos a tabela verdade:
p q (¬p ∧ p→ q) → ¬q
V V F F V V F
V F F F F V V
F V V V V F F
F F V V V V V
Este argumento não é uma tautologia (na linha 3 vemos que as premissas são verdade
mas a conclusão é falsa), não é válido.
Para deixar estes exemplos um pouco mais concretos, sejam p “2 + 2 = 4” e q “3 + 5 = 7”.
Então, o primeiro argumento 1.1 se torna
3 + 5 6= 7
Se 2 + 2 = 4, então 3 + 5 = 7
2 + 2 6= 4.
O segundo é argumento 1.2 é
2 + 2 6= 4
Se 2 + 2 = 4, então 3 + 5 = 7
3 + 5 6= 7.
No primeiro caso (um argumento válido) vemos que a conclusão é falsa, enquanto no
segundo caso (um argumento inválido) a conclusão é verdade! O que está acontencendo aqui?
A resposta é que a validade (ou falta dela) de um argumento é somente baseada na forma do
argumento e não tem nada a ver com a falsidade ou verdade das proposições envolvidas (se
esse não fosse o caso, não haveria maneira de representar de forma simbólica). Também, é
importante lembrar que a validade de um argumento garante a verdade da conclusão somente
quando todas as premissas são verdades. No primeiro argumento 1.1 vemos que a segunda
premissa, “Se 2 + 2 = 4, então 3 + 5 = 7”, é falsa.
Embora o procedimento acima de usar tabelas verdade para verificar a validade do argu-
mento seja simples, não é muito conveniente quando o número de proposições é grande. Por
exemplo, se existem oito proposições, então a tabela verdade requeriria 28 = 256 linhas.
Outro método de demonstrar (provar) a validade de um argumento é chamada de princípio
de demonstração :
A demonstração de que o argumento (p1 ∧ p2 ∧ . . .∧ pn)→ q é válido é uma sequência de
proposições s1, s2, . . . , sk de forma que sk (a última proposição na sequência) é q e cada si,
1 ≤ i ≤ k, na sequência satisfaz um ou mais dos seguintes requerimentos:
a) si é uma das hipóteses.
b) si é uma tautologia.
19
c) si é uma consequência lógica das proposições anteriores da sequência.
Então vemos que sob esta suposição de que as premissas são verdade, cada proposição na
demonstração também será verdade e como a última proposição da sequência é a conclusão
do argumento, a demonstração mostra (demonstra) que se todas as premissas são verdade
então a conclusão deve, necessariamente, ser verdade, isto é, o argumento é válido.
Como exemplo disso, vamos considerar o exemplo acima o qual verificamos usando a
tabela verdade:
¬q
p→ q
¬p.
Quando se escreve uma demonstração é útil que o leitor inclua a justificativa para cada
proposição da sequência. Geralmente, não incluímos os nomes e números das tautologias que
usamos, mas como ajuda aos iniciantes, as justificativas estão incluidas aqui.
Proposição Razão
1. ¬q hipótese
2. p→ q hipótese
3. ¬q → ¬p contrapositiva de 2. (13 da lista de tautologias)
4. ¬p consequência lógica de 1. e 3. (19 da lista de tautologias, modus ponens)
Existem outras maneiras de fazer a demonstração corretamente e mesmo neste caso po-
demos proceder um pouco diferente:
Proposição Razão
1. ¬q hipótese
2. p→ q hipótese
3. ¬p consequência lógica de 1. e 2. (20 da lista de tautologias, modus tollens)
Considere o exemplo um pouco mais complicado:
p ∨ q
q → ¬p
p→ q
q.
(1.3)
Proposição Razão
1. q → ¬p hipótese
2. p→ q hipótese
3. ¬q → ¬p contrapositiva de 2.
4. (q ∨ ¬q)→ ¬p consequência lógica de 1. e 3. (15a da lista de tautologias)
5. q ∨ ¬q tautologia
6. ¬p consequência lógica
de 4. e 5. (19 da lista de tautologias, modus ponens)
7. p ∨ q hipótese
8. q consequência lógica de 6. e 7. (22 da lista de tautologias, silogismo disjuntivo)
20
Outra demonstração para o mesmo argumento (você poderia tentar encontrar outras
demonstrações):
Proposição Razão
1. q → ¬p hipótese
2. p→ q hipótese
3. p→ ¬q contrapositiva de 1.
4. p→ (q ∧ ¬q) consequência lógica de 2. e 3. (15b da lista de tautologias)
5. ¬p consequência lógica de 4. (23 da lista de tautologias, absurdo)
6. p ∨ q hipótese
7. q consequência lógica de 5. e 6. (22 da lista de tautologias, silogismo disjuntivo)
Uma extensão do princípio de demonstração, chamado de método de demonstração indi-
reta (ou demonstração por contradição) é baseada na equivalência lógica reductio ad absur-
dum (item 14 da lista de tautologias). Aplicando esta forma para nosso argumento temos:
((p1 ∧ p2 ∧ . . . ∧ pn)→ q)↔ ((p1 ∧ p2 ∧ . . . ∧ pn ∧ ¬q)→ c).
Como esta é uma equivalência lógica podemos substituir o lado esquerdo pelo lado direito.
Isto significa que em nossa demonstração temos uma hipótese adicional, ¬q (a negação da
conclusão). Nossa demonstração estará completa assim que obtermos uma contradição.
Como um exemplo deste método, considere o argumento (1.3) usado no exemplo anterior:
Proposição Razão
1. ¬q hipótese (negação da conclusão na prova indireta)
2. p ∨ q hipótese
3. p consequência lógica de 1. e 2. (22 da lista de tautologias, silogismo disjuntivo)
4. p→ q hipótese
5. q consequência lógica de 3. e 4. (19 da lista de tautologias, modus ponens)
6. q ∧ ¬q consequência lógica de 1. e 5. (essa é a contradição que procurávamos)
7. q consequência lógica de 6. (prova indireta)
É interessante notar que a hipótese q → ¬p não foi usada nesta prova, embora estivesse nas
duas provas anteriores. Você poderia tentar encontrar uma demonstração direta da validade
do argumento sem usar esta hipótese.
O princípio de demonstração fornece um bom método de estabelecer a validade de um
arguento mas tem a desvantegem de não mostrar que um argumento é inválido. O fato
que de não podermos dar uma demonstração de um argumento particular não é suficiente
para mostrar que um argumento é inválido. Entretanto, existe uma outra forma, sem usar
tabelas verdade, de mostrar que um argumento é inválido. Se recordarmos o que significa
um argumento válido, lembraremos que uma conclusão deve ser verdade sempre que todas as
premissas são verdade, portanto se encontrarmos uma maneira de encontrar um caso onde as
premissas são verdade e a conclusão é falsa, então mostramos que o argumento é inválido. Às
vezes, fracassar em obter a demonstração, nos leva ao caso geralmente, chamado de contra
21
exemplo de um arguento. Por exemplo, considere o seguinte argumento:
p→ q
¬p ∨ q
q → p.
Sem muito esforço podemos ver que se q é V e p é falso então a conclusão é F enquanto ambas
a premissas são V, portanto, o argumento é inválido.
Exercícios 1.5
1. Determine a validade dos seguintes argumentos usando tabelas verdade:
a)
p→ q
¬p ∨ q
q → p. b)
p ∨ q
r → q
q
¬r.
c)
p ∨ ¬q
¬p
¬q.
2. Dê exemplos nos itens a seguir sempre que possível. Se não for possível, diga porque:
a) Um argumento inválido com conclusão falsa.
b) Um argumento válido com uma conclusão verdadeira.
c) Um argumento inválido com uma conclusão verdadeira.
d) Um argumento válido com uma conclusão falsa.
e) Um argumento válido com hipóteses verdeiras e uma conclusão falsa.
f) Um argumento inválido com hipóteses verdeiras e uma conclusão falsa.
g) Um argumento válido com hipóteses falsas e uma conclusão verdadeira.
3. Determine a validade dos seguintes argumentos usando o princípios de demonstração ou
mostre por contra exemplo que é inválido:
a)
¬p ∨ q
p
q.
b)
p→ q
r → ¬q
p→ ¬r.
c)
¬p ∨ q
¬r → ¬q
p→ ¬r.
d)
q ∨ ¬p
¬q
p.
e) ¬p
p→ q.
f)
(p ∧ q)→ (r ∧ s)
¬r
¬p ∨ ¬q.
g)
p→ q
¬q → ¬r
s→ (p ∨ r)
s
q.
h)
p ∨ q
q → ¬r
¬r → ¬p
¬(p ∧ q).
i)
p→ q
¬r → ¬q
r → ¬p
¬p.
j) p→ ¬p¬p.
k)
p ∨ q
p→ r
¬r
q.
22
l)
p
q → ¬p
¬q → (r ∨ ¬s)
¬r
¬s.
m)
p→ (q ∨ s)
q → r
p→ (r ∨ s).
n)
p→ ¬q
q → p
r → p
¬q.
o)
p→ q
r → s
¬(p→ s)
q ∧ ¬r.
1.6 Quantificadores
Quando iniciamos nossa discussão sobre proposições notamos que “x < 3” não era uma
proposição porque não sabíamos o que x representava, portanto não pudemos definir um valor
verdade. Neste caso, chamamos x uma variável (um símbolo que pode tomar vários valores)
e “x < 3” uma função proposicional. De fato, isto é um pequeno abuso de linguagem pois
“x < 3” é realmente função de valor proposicional, isto é para cada (devidamente escolhido)
valor de x temos uma proposição. Esta é similar as funções de valores reais que estudamos
nos cursos de pré cálculo. Por exemplo, se f é uma função dada por f(x) = 2x−3, então para
cada valor de x no domínio de f (o qual tomaremos como o conjunto dos números reais),
f retorna um valor real, isto é f(x) é um número real. Portanto, f(−1) = −5, f(5) = 7.
Se adotarmos uma notação funcional para “x < 3,” digamos p(x) e seja o domínio de p
o conjunto dos números reais, então para cada escolha de x no domínio de p, p(x) é uma
proposição. Por exemplo, quando x = 2, obtemos p(2) que significa “2 < 3” e quando x = 8,
obtemos p(8) ou “8 < 3.” note que p(2) é uma proposição verdadeira enquanto p(8) é uma
proposição falsa.
Assim, diremos que se r é uma sentença declarativa contendo uma ou mais variáveis e r
se torna uma proposição quando valores particulares (às vezes chamados interpretações) são
dados para as variáveis, então r é uma função proposicional. Como é no caso com funções
que tomam valores reais do pré cálculo, o conjunto dos possíveis valores para a variável é
chamado domínio da função proposicional. Às vezes o domínio será explicitamente definido,
às vezes o domínio será inferido do contexto. Denotaremos as funções proposicionais por p, q,
etc., e (como no caso das funções reais) usamos p(x), q(x, y) (para ser lidos como “p de x”,
“q de x, y”) para indicar “fórmulas” para estas funções. Portanto, se p(x) é “x < 3” então
p(1), p(−7), p(0) são verdadeiras, enquanto p(3), p(12), p(pi) são falsas, se q(x, y) é “x < y”,
então q(1, 2), q(−2, 14), q(0, 5) são verdadeiras, enquanto q(0, 0), q(2, 1), q(pi, 3) são falsas.
Suponha que D é o domínio da função proposicional p. Sabemos que podemos transformar
p em uma proposição substituindo vários membros de D em p, entretanto esta não é a única
forma na qual p pode ser transformada em uma proposição. O outro método é chamado
quantificação e existem duas formas de quantificarmos funções proposicionais. Na primeira,
procedemos a função proposicional com “para todo x em D” (ou “para cada x em D”), na
segunda procedemos a função proposicional com “existe um x em D tal que” (or “algum x
em D tem a propriedade que”). A notação que usaremos para isso é
Para todo x em D, p(x) é denotada por ∀x em D, p(x).
Existe um x em D, tal que p(x) é denotada por ∃x em D 3 p(x).
23
∀ é chamado o quantificador universal e é lido como “para todo”, ∃ é chamado quan-
tificador existencial e é lido como “existe” e 3 é o símbolo para “tal que”. Determinamos
valores verdade para estas proposições de acordo com o significado usual que damos para
“para todos” e “existe”:
∀x em D, p(x)
será dado valor verdade de V se p(x) for verdade para cada interpretação de x em D, caso
contrário, o valor verdade é F.
∃x em D 3 p(x)
será dado valor verdade de V se p(x) é verdade para pelo menos uma interpretação de x em
D, caso contrário será dado o valor verdade de F. Portanto, vemos que se D é finito, digamos
com elementos x1, x2, . . . , xn, então
∀x em D, p(x)
é equivalente a uma conjunção, isto é,
p(x1) ∧ p(x2) ∧ . . . ∧ p(xn),
enquanto
∃x em D 3 p(x)
é equivalente a uma disjunção, isto é
p(x1) ∨ p(x2) ∨ . . . ∨ p(xn).
Por exemplo, se D = {1,
2, 3, 4}, S = {−1, 0, 1, 2} e p é a função proposicional dada por p(x)
é “x < 3” então
∀x em D, p(x)
é falsa (pois p(3) é falsa), enquanto
∀x em S, p(x); ∃x em D 3 p(x); ∃x em S 3 p(x)
são verdade. Note que o valor verdade da função proposicional quantificada depende do
domínio usado. Com p e S como acima, vamos dar uma olhada de outra forma.
∀x em S, p(x)
é equivalente a
p(−1) ∧ p(0) ∧ p(1) ∧ p(2),
enquanto,
∃x em S 3 p(x)
é equivalente a
p(−1) ∨ p(0) ∨ p(1) ∨ p(2).
Portanto, se você fosse uma programa de computador (digamos) checando os valores verdade
para ∀x em S, p(x), você teria que tomar cada elemento x em S e verificar o valor verdade
24
para p(x). Assim que você encontrasse uma valor falso você retornaria o valor falso para
∀x em S, p(x), caso contrário retornaria o valor verdade depois de verificar cada elemento
de S. De forma similar, para determinar o valor verdade de ∃x em S 3 p(x), você tomaria
cada elemento x de S e verificaria o valor verdade de p(x). Assim que você encontrasse um
verdade, você retornaria verdade para o valor verdade de ∃x em S 3 p(x), caso contrário,
você retornaria falso depois de verificar todos os elementos de S.
Com o vimos acima, em mente devemos ser capazes de considerar o caso especial (dege-
nerado) quando o domínio em questão é vazio (contém nenhum elemento). Por exemplo, qual
valor verdade deve ser atribuído as proposições “Todos matemáticos com altura superior a 3
metros gostam de chocolate” e “ Existe um matemático com mais de 3 metros de altura que
gosta de chocolate”? Se D é o conjunto dos matemáticos com mais de 3 metros de altura (um
exemplo de conjunto vazio) e seja p(x) “x gosta de chocolate” as proposições enunciadas se
tornam
∀x em D, p(x) e ∃x em D 3 p(x).
Para o primeiro ser falso devemos encontrar matemático alto que não gosta de chocolate.
Como não há (suficientes) matemáticos altos, certamente não podemos encontrar um que
não goste de chocolate, assim, a primeira proposição deve ser verdade. De forma similar, para
a segunda ser verdade devemos encontrar um matemático alto que goste de chocolate. Não
podemos, logo a segunda proposição é falsa. Para resumir, se D é vazio então não importando
o que seja p(x) temos,
∀x em D, p(x) verdade e ∃x em D 3 p(x) falso.
O leitor pode não gostar disso, mas é assim que é.
Um pouco de reflexão revelará como formar negações de funções proposicionais quanti-
ficadas. Considere, ∀x em D, p(x). Se esta proposição é falsa então p(x) não é verdade para
todas as interpretações de x em D, isto é, existe pelo menos um valor de x tal que p(x) é
falso. Assim, vemos que:
¬(∀x em D, p(x))↔ ∃x em D 3 ¬p(x).
Usando raciocínio similar, obtemos
¬(∃x em D 3 p(x))↔ ∀x em D,¬p(x).
Se D, é finito, estas são apenas extensões das leis de DeMorgan, tente criar um exemplo para
ver isso.
Para ilustrar a negação de uma função proposicional quantificada, considere
∀x em D, [p(x)→ q(x)].
Usando as ideias acima, obtemos como negação
∃x em D 3 [p(x) ∧ ¬q(x)].
Uma das principais dificuldades para lidar com as funções proposicionais quantificadas
dadas em nossa língua (neste caso Português) é determinar a correta forma lógica das de-
25
clarações quantificadas. É claro que, se nos é dado algo como “Existe um inteiro tal que seu
quadrado é 9,” é fácil ver que que sua forma é
∃x em Z 3 p(x),
onde Z é o conjunto dos inteiros e p(x) é “x2 = 9.” Infelizmente, na maior parte dos casos
a representação em Português não é tão simples e uma tradução correta em símbolos (que
mostra claramente a forma lógica) requer um entendimento do significado da sentença. A
tradução não pode ser feita de uma maneira determinada e fácil, ou de acordo a um simples
algoritmo. Às vezes, a própria quantificação não é mencionada explicitamente, mas enten-
dida ou inferida. Isto, também, é verdade para o domínio, mesmo que o quantificador estiver
presente. Por exemplo, a maioria das definições e teoremas matemáticos envolvem quanti-
ficadores, entretanto, muito frequentemente não estão aparentes para os leitor descuidado
(claro que nenhum de nosos leitores estuda matemática de forma descuidada). Assim, “Se
f é diferenciável então é contínua” realmente significa “Para todas as funções f (em algum
conjunto de funções), se f é diferenciável, então f é contínua.” É geralmente uma aposta
segura assumir que todo teorema tem um quantificador universal escondido em algum lugar,
expressado ou implícito.
Além de encontrar os quantificadores, outro problema que pode surgir é a determinação
da forma correta para a função proposicional quantificada. Por exemplo, “Todos estudantes
de lógica entendem quantificadores” claramente envolve o quantificador universal, mas qual
é a sua forma correta? Se deixamos o domínio D ser o conjunto dos estudantes, p(x) será
“x é um estudante de lógica” e q(x) será “x entende quantificadores” então a possibilidade
parece ser ∀x em D, p(x)∧ q(x). Mas isto significa “Todo estudante é um estudante de lógica
e entende quantificadores”, que não é a mensagem da proposição original. A correta inter-
pretação é: “∀x em D, p(x)→ q(x),” que significa “Para todo estudante, se o estudante é um
estudante de lógica então aquele estudante entende quantificadores.” De forma similar, pode-
mos ficar tentados a representar “Alguns estudantes de lógica entendem quantificadores” por
∃x em D 3 p(x)→ q(x). Entretanto, isto não está correto, pode não existir estudantes de ló-
gica em nosso conjunto de estudantes, fazendo ∃x em D 3 p(x)→ q(x) ser verdade enquanto
a verdadeira proposição será verdade somente se existir pelo menos um estudante de lógica o
qual entende de quantificadores. A proposição dada pode ser corretamente interpretada por
∃x em D 3 p(x)∧ q(x), que significa que existe pelo menos um estudante que é estudante de
lógica e que entende de quantificadores. Devemos perceber que estas formas são de alguma
meneira dependentes do domínio pois se simplificamos coisas ou restringimos nosso domínio
para apenas o conjunto de estudante de lógica (digamos D′), então a primeira proposição se
torna ∀x em D′, q(x) e a segunda se torna ∃x em D′ 3 q(x). Para resumir:
todo p é um q
pode ser representado por
∀x em D, p(x)→ q(x)
enquanto para
algum p é um q
é dado por
∃x em D 3 p(x) ∧ q(x),
26
(D sendo o domínio em questão).
Uma forma de determinar se você entende a versão em linguagem de uma função proposici-
onal quantificada é tentar negá-la. Existem várias maneiras de abordar este tipo de problema.
Aquela que requer a menor experiência é traduzir a sentença para a forma simbólica, usar as
já bem conhecidas regras para a negação de proposição e funções proposicionais quantificadas
e então traduzir o resultado de volta para o Português. Depois de alguma prática você deve
ser capaz de negar algumas sentenças diretamente, mas mesmo com considerável experiência
é útil usar as representações simbólicas para clarificar a estrutura.
Como exemplo do fato descrito acima, suponha que desejamos negar “Todos estudantes
de lógica entendem quantificadores.” Com D, p e q como antes, a representação simbólica é
∀x em D, p(x)→ q(x).
Procedendo com a negação passo a passo, temos
¬[∀x em D, p(x)→ q(x)]
↔ ∃x em D 3 ¬[p(x)→ q(x)]
↔ ∃x em D 3 p(x) ∧ ¬q(x).
Assim, a negação de “Todos estudantes de lógica entendem quantificadores.” é “Existe um
estudante que é estudante de lógica e que não entende quantificadores,” ou, ainda mais, no
estilo da proposição original “Alguns estudante de lógica não entendem quantificadores.” Para
um entendimento mais profundo você poderia se perguntar “O que faria ‘Todos os estudante
de lógica entende quantificadores’ ser falsa?” Depois de um pouco de reflexão, responderíamos,
“Tem que existir um estudante de lógica que não entende quantificadores,” que, claramente,
será verdade quando nossa negação “Algum estudante de lógica não entende quantificadores”
é verdade.
Exercícios 1.6
1. Traduza as seguintes sentenças para a forma simbólica, indicando as escolhas apropriadas
para domínios:
a) Existe um inteiro x tal que 4 = x+ 2.
b) Para todos inteiros x, 4 = x+ 2.
c) Todo triângulo equilátero é equiângulo.
d) Todos estudantes gostam de lógica.
e) Alguns estudantes não gostam de lógica.
f) Nenhum homem é uma ilha.
g) Todo mundo que entende lógica gosta dela.
h) Cada pessoa tem uma mãe.
i) Entre todos os inteiros existem uns que são primos.
j) Alguns inteiros são pares e divisíveis por 3.
k) Alguns inteiros são pares ou divisíveis por 3.
l) Todos grupos cíclicos são abelianos.
m) Pelo menos uma das letras de banana é uma vogal.
27
n) Um dia no próximo mês é uma sexta-feira.
o) x2 − 4 = 0 tem uma solução positiva.
p) Cada solução de x2 − 4 = 0 é positiva.
q) Nenhuma solução de x2 − 4 = 0 é positiva.
r) Um candidato será o vencedor.
s) Cada elemento do conjunto A é um elemento do conjunto B.
2. Encontre a negação para cada uma das proposições no exercício acima.
3. Sejam D o conjunto dos números naturais (isto é, D = {1, 2, 3, 4, 5, . . .}), p(x) “x é par”,
q(x) “x é divisível por 3” e r(x) “x é divísivel por 4.” Para cada uma das proposições abaixo,
expresse em Português, determine seu valor verdade e dê uma negação em Português.
a) ∀x em D, p(x).
b) ∀x em D, p(x) ∨ q(x).
c) ∀x em D, p(x)→ q(x).
d) ∀x em D, p(x) ∨ r(x).
e) ∀x em D, p(x) ∧ q(x).
f) ∃x em D 3 r(x).
g) ∃x em D 3 p(x) ∧ q(x).
h) ∃x em D 3 p(x)→ q(x).
i) ∃x em D 3 q(x)→ q(x+ 1).
j) ∃x em D 3 p(x)↔ q(x+ 1).
k) ∀x em D, r(x)→ p(x).
l) ∀x em D, p(x)→ ¬q(x).
m) ∀x em D, p(x)→ p(x+ 2).
n) ∀x em D, r(x)→ r(x+ 4).
o) ∀x em D, q(x)→ q(x+ 1).
4. Para cada uma das proposições do exercício acima (se possível) dê um exemplo de um
domínio D′ tal que as proposições tenham o valor verdade oposto daquele que tinha em
D, o conjunto dos números naturais.
5. As seguintes proposições são sempre, às vezes ou nunca verdade? Dê exemplos de domínios
D e a função proposicional p ou razões para justificar suas respostas.
a) [∀x em D, p(x)]→ [∃x em D 3 p(x)].
b) [∃x em D 3 p(x)]→ [∀x em D, p(x)].
c) [∀x em D,¬p(x)]→ ¬[∀x em D, p(x)].
d) [∃x em D 3 ¬p(x)]→ ¬[∃x em D 3 p(x)].
e) ¬[∀x em D, p(x)]→ [∀x em D,¬p(x)].
f) ¬[∃x em D 3 p(x)]→ [∃x em D 3 ¬p(x)].
28
1.7 Mais quantificadores
Muitas sentenças matemáticas envolvem mais de um quantificador. Alguns exemplos des-
tas sentenças são:
• “Para cada número inteiro n existe um inteiro k tal que n = 2k”,
• “Para cada linha ` e para cada ponto p não pertencente a `, existe uma linha `′ que
passa por p e é paralela a `”,
• “Para todo y em B existe um x em A tal que f(x) = y”,
• “Para todo x no domínio de f e para cada � > 0 existe um δ > 0 tal que |x − c| < δ
implica |f(x)− L| < �”,
• “Para cada x em G existe um x′ em G tal que xx′ = e”.
Como pode ser esperado, as dificuldades que se apresentavam quando consideramos um
quantificador persiste quando temos mais de um quantificador e, adicionalmente, novas di-
ficuldades surgem, portanto teremos que ser especialmente cuidadosos nas análises destas
quantificações de nível superior.
Vamos dar uma olhada na estrutura de uma proposição envolvendo dois quantificadores
diferentes, digamos
∀x em S, ∃y em T 3 p(x, y).
Como lemos isto? Como sempre, lemos da direita para a esquerda, a proposição acima significa
∀x em S, [∃y em T 3 p(x, y)].
Assim, se S = {1, 2} e T = {3, 4} então teremos (aplicando o quantificador universal primeiro,
como requerido):
[∃y em T 3 p(1, y)] ∧ [∃y em T 3 p(2, y)].
Agora, aplicando o quantificador existencial
[p(1, 3) ∨ p(1, 4)] ∧ [p(2, 3) ∨ p(2, 4)]. (1.4)
Em contraste, considere a mesma função proposicional com a ordem dos quantificadores
invertida, isto é
∃y em T 3 ∀x em S, p(x, y).
Procedendo da mesma forma, obtemos
[∀x em S, p(x, 3)] ∨ [∀x em S, p(x, 4)].
e consequentemente,
[p(1, 3) ∧ p(1, 4)] ∨ [p(2, 3) ∧ p(2, 4)]. (1.5)
Note que as duas funções proposicionais apresentadas não são equivalentes, por exemplo, se
p(1, 3) e p(2, 4) são ambas verdade enquanto p(2, 3) e p(1, 4) são ambas falsas então (1.4) é
verdade mas (1.5) é falsa.
29
Um exemplo um pouco mais concreto disso é: sejam S = {1, 2} e p(x, y) “x = y.” Então
(o leitor deverá fornecer os detalhes)
∀x em S, ∃y em S 3 p(x, y)
se torna
[∃y em S 3 1 = y] ∧ [∃y em S 3 2 = y]
que é,
[1 = 1 ∨ 1 = 2] ∧ [2 = 1 ∨ 2 = 2],
uma proposição verdadeira, enquanto
∃y em S 3 ∀x em S, p(x, y)
é
[∀x em S, x = 1] ∨ [∀x em S, x = 2]
ou
[1 = 1 ∧ 1 = 2] ∨ [2 = 1 ∧ 2 = 2],
uma proposição falsa.
Note que se a proposição da forma
∀x em S, ∃y em T 3 p(x, y)
é verdadeira, então para cada x em S deve necessariamente existir algum y em T tal que
p(x, y) seja verdade, entretanto a escolha de y pode depender da escolha de x. Por outro lado,
para que
∃y em T 3 ∀x em S, p(x, y)
seja verdade deve existir algum y em T , digamos y0, tal que, para este particular y0, p(x, y0)
seja verdade para cada escolha de x em S.
Seria útil se tivéssemos uma forma gráfica para olhar para isto. Suponha que S =
{1, 2, 3, 4} e T = {1, 2, 3}. Podemos representar todas as doze possívies escolhas em uma
tabela retangular como abaixo, com ◦ indicando as possibilidades.
3 ◦ ◦ ◦ ◦
T 2 ◦ ◦ ◦ ◦
1 ◦ ◦ ◦ ◦
1 2 3 4
S
Como sempre, vamos representar o primeiro conjunto (S) ao longo do eixo horizontal
e o segundo conjunto (T ) ao longo do eixo vertical. Para entender como as coordenas são
representadas, os valores são mostrados abaixo:
30
3 (1, 3) (2, 3) (3, 3) (4, 3)
T 2 (1, 2) (2, 2) (3, 2) (4, 2)
1 (1, 1) (2, 1) (3, 1) (4, 1)
1 2 3 4
S
Agora, suponha que p(1, 1), p(2, 3), p(3, 2) e p(4, 1) são verdade e para todos os outros
valores de x e y, p(x, y) é falsa (os valores verdadeiros são representados por retângulos na
figura abaixo):
3 ◦ ◦ ◦ ◦
T 2 ◦ ◦ ◦ ◦
1 ◦ ◦ ◦ ◦
1 2 3 4
S
Baseada na figura acima vemos que para
∀x em S, ∃y em T 3 p(x, y) (1.6)
ser verdade deve existir pelo menos um retângulo em cada coluna vertical, enquanto para
∃y em T 3 ∀x em S, p(x, y) (1.7)
ser verdade deve existir uma linha horizontal inteira de retângulos. Assim, para o exemplo
dado, (1.6) é verdade enquanto (1.7) é falsa. Deve estar claro que sempre que (1.7) for verdade
(uma linha inteira de retângulos), (1.6) deve também ser verdade (pelo menos um retângulo
em cada coluna).
Para um exemplo mais “caseiro” disso, sejam S o conjunto de todas as pessoas e p(x, y)
representando “y é mãe de x.” Então ∀x em S, ∃y em T 3 p(x, y) significa todo mundo tem
uma mãe enquanto ∃y em T 3 ∀x em S, p(x, y) significa que existe uma pessoa que é mãe de
todo mundo, claramente duas sentenças diferentes.
Vamos tentar entender outro exemplo caseiro: “Para cada cachorro no sofá existe uma
pulga no carpete com a propriedade que se o cachorro é preto então a pulga mordeu o ca-
chorro.” Algumas questões que devemos ser capazes de responder (se entendemos o significado
da sentença) são:
• “Qual é a negação desta sentença?”
• “O que podemos dizer de seus valores verdade se
a) não há nenhum cachorro preto no sofá?
b) uma pulga em particular mordeu todos os cachorros?
c) existe um cachorro preto não mordido?
d) não há pulgas no carpete?”
Como responderíamos estas questões? Se não podemos respondê-las imediatamente, uma boa
maneira para começar é traduzir a proposição para a forma simbólica. Sejam S o conjunto
31
dos cachorros, C o conjunto das pulgas no carpete, p(x) “x é preto”, e q(x, y) “y mordeu x.”
Então a proposição é
∀x em S,∃y em C 3 p(x)→ q(x, y).
A negação pode ser tratada de uma maneira simples passo a passo:
¬[∀x em S, ∃y em C 3 p(x)→ q(x, y)]
↔ ∃x em S 3 ¬[∃y em C 3 p(x)→ q(x, y)]
↔ ∃x em S 3 ∀y em C,¬[p(x)→ q(x, y)]
↔ ∃x em S 3 ∀y em C, p(x) ∧ ¬q(x, y).
Assim a negação, em Português, é “Existe um cachorro no sofá tal que, para cada pulga
no carpete, o cachorro é preto e a pulga não mordeu o cachorro,” ou de forma mais fluida,
“Tem um cachorro preto no sofá que não foi mordido.” Agora devemos ser capazes de res-
ponder as outras questões que foram formuladas anteriormente. Na situação a) a proposição
é verdade pois deve existir um cachorro preto não mordido para esta ser falsa; a situação b)
é verdade pois q(x, y) será verdade para todos os cachorros x; a situção c) é falsa pois sua
negação é verdade. O valor verdade na situação na situação d) não pode ser decidido sem
mais informações. Se existe um cachorro preto no sofá então a proposição é falsa, se não há
cachorros pretos então é verdade. Isto nos dá um exemplo de uma variedade de questões que
podemos ser capazes de responder se entendermos so significado de tal função proposicional
quantificada.
Com dois quantificadores e dois domínios existem oito ordens possíveis nas quais os quan-
tificadores podem ocorrer. Já notamos que quando os quantificadores são mistos (isto é, um
universal e um existencial), a ordem é importante:
∀x em S, ∃y em T 3 p(x, y)
não é necessariamente o mesmo que
∃y em T 3 ∀x em S, p(x, y)
Se ambos os quantificadores são os mesmos, temos equivalência (isto se deve ao fato que os
conectivos são todos os mesmos, ∨ para ∃ e ∧ para ∀; apenas a ordem é diferente e sabemos
que ambos ∨ e ∧ comutam), assim:
[∃x em S 3 ∃y em T 3 p(x, y)]↔ [∃y em T 3 ∃x em S 3 p(x, y)]
e
[∀x em S,∀y em T, p(x, y)]↔ [∀y em T, ∀x em S, p(x, y)]
Se o domínio é o mesmo para ambos os quantificadores, geralmente encurtamos as equiva-
lências acima escrevendo-as como:
∀x, y em S, p(x, y) para ∀x em S, ∀y em T, p(x, y) e
∃x, y em S 3 p(x, y) para ∃x em S 3 ∃y em T 3 p(x, y).
32
Enquanto as forma mistas não são equivalentes, podemos dizer que
[∃y em T 3 ∀x em S, p(x, y)]⇒ [∀x em S,∃y em T 3 p(x, y)].
Isto se deve ao fato, como observamos acima, que se o lado esquerdo é verdadeiro então existe
pelo menos um elemento de T , digamos y0, que faz p(x, y0) ser verdade para todos os x em
S, portanto este y0 pode ser usado para cada x no lado direito.
Há outro conjunto de dificuldades que podem surgir, e que é distinguir, por exemplo
“Todo inteiro é par ou ímpar,”
e
“Todo inteiro é par ou todo inteiro é ímpar.”
É fácil ver (esperamos), que estas proposicões não são equivalentes, pois a primeira é
verdade enquanto a segunda é falsa. Para ajudar a analisar esta situação, vamos pôr estas
proposições na forma simbólica. Sejam D o conjunto dos inteiros, p(x) “x é par,” e q(x) “x
é ímpar,” então a primeira proposição é
∀x em D, [p(x) ∨ q(x)],
enquanto que a segunda é
[∀x em D, p(x)] ∨ [∀x em D, q(x)].
A razão para estas duas proposicões não serem equivalentes é essencialmente a mesma razão
para não termos equivalência para quantificadores mistos; o ∀ envolve “e’s” e tomado em
conjunção com o “ou,” a ordem na qual as interpretções ocorrem muda de sentido. Usando o
mesmo raciocínio poderíamos suspeitar que
∃x em D 3 [p(x) ∧ q(x)],
e
[∃x em D 3 p(x)] ∧ [∃x em D 3 q(x)],
não sejam equivalentes. Também, como p → q é equivalente a uma disjunção (¬p ∨ q),
esperaríamos que
∀x em D, [p(x)→ q(x)]
e
[∀x em D, p(x)]→ [∀x em D, q(x)].
não sejam equivalentes. Nossas supeitas são bem fundamentadas como nenhum destes pares
é equivalente. Entretanto, em cada par existe uma que implica a outra, portanto temos as
seguintes implicações lógicas:
{[∀x em D, p(x)] ∨ [∀x em D, q(x)]} ⇒ ∀x em D, [p(x) ∨ q(x)],
∃x em D 3 [p(x) ∧ q(x)]⇒ {[∃x em D 3 p(x)] ∧ [∃x em D 3 q(x)]},
∀x em D, [p(x)→ q(x)]⇒ {[∀x em D, p(x)]→ [∀x em D, q(x)]}.
33
Devemos, também, suspeitar que a ordem de “∀” e “∧” ou “∃” e “∨” não muda o significado
e, novamente, estaria correto que
{[∀x em D, p(x)] ∧ [∀x em D, q(x)]} ⇔ ∀x em D, [p(x) ∧ q(x)],
e
∃x em D 3 [p(x) ∨ q(x)]⇔ {[∃x em D 3 p(x)] ∨ [∃x em D 3 q(x)]}.
As ideias e métodos de análise que usamos para sentenças envolvendo dois quantificadores
podem ser extendidas para três (ou mais) quantificadores. Alguns destes exemplos foram
incluídos nos exercícios.
Exercícios 1.7
1. Traduza as seguintes sentenças para a forma simbólica, indicando as escolhas apropriadas
para domínios:
a) Para cada inteiro par n existe um inteiro k tal que n = 2k.
b) Para cada reta l e cada ponto p que não está em l existe uma reta l′ que passa por p
que é paralela a l.
c) Para cada y em B existe um x em A tal que f(x) = y.
d) Para cada x no domínio de f e para cada � > 0 existe δ > 0 tal que |x− c| < δ implica
|f(x)− L| < �.
e) Para cada x em G existe um x′ em G tais que xx′ = e.
f) Se todo inteiro é ímpar então todo inteiro é par.
g) Alguém ama alguém em algum momento.
h) Entre todas as pulgas do carpete existe uma para a qual existe em todos os cachorros
no sofá uma mordida que aquela pulga fez.
i) Para cada inteiro n existe outro inteiro maior que 2n.
j) A soma de quaisquer dois inteiros pares é par.
k) Todo subconjunto fechado e limitado de R é compacto.
2. Encontre a negação para cada uma das proposições no exercício acima.
3. Sejam p(x, y) representando “x + 2 > y” e D o conjunto dos números naturais (D =
{1, 2, 3, . . .}, também denotado por N). Escreva em palavras e determine o valor verdade
de
a) ∀x em D,∃y em D 3 p(x, y).
b) ∃x em D 3 ∀y em D, p(x, y).
c) ∀x em D,∀y em, p(x, y).
d) ∃x em D 3 ∃y em D 3 p(x, y).
e) ∀y em D,∃x em D 3 p(x, y).
f) ∃y em D 3 ∀x em D, p(x, y).
34
4. Sejam D = {1, 2}, p(x) “x é par” e q(x) “x é ímpar.” Escreva em detalhes as seguintes
quantificações como conjunções e disjunções das interpretações (como feito no começo
desta seção):
a) ∀x em D, [p(x) ∧ q(x)].
b) [∀x em D, p(x)] ∧ [∀x em D, q(x)].
c) ∀x em D, [p(x) ∨ q(x)].
d) [∀x em D, p(x)] ∨ [∀x em D, q(x)].
e) ∃x em D 3 [p(x) ∧ q(x)].
f) [∃x em D 3 p(x)] ∧ [∃x em D 3 q(x)].
g) ∃x em D 3 [p(x) ∨ q(x)].
h) [∃x em D 3 p(x)] ∨ [∃x em D 3 q(x)].
i) ∃x em D 3 [p(x)→ q(x)].
j) [∃x em D 3 p(x)]→ [∃x em D 3 q(x)].
5. Dê alguns exemplos para mostrar que as seguintes implicações lógicas não são equivalências
lógicas:
a) {[∀x em D, p(x)] ∨ [∀x em D, q(x)]} ⇒ ∀x em D, [p(x) ∨ q(x)].
b) ∃x em D 3 [p(x) ∧ q(x)]⇒ {[∃x em D 3 p(x)] ∧ [∃x em D 3 q(x)]}.
c) ∃x em D 3 [p(x)→ q(x)]⇒ {[∃x em D 3 p(x)]→ [∃x em D 3 q(x)]}.
6. Determine a relação (se existir uma) entre
∃x em D 3 [p(x)→ q(x)]
e
[∃x em D 3 p(x)]→ [∃x em D 3 q(x)].
7. Mostre que a segunda equivalência lógica em cada uma dos pares pode ser obtida da
primeira por negação:
a)
[∃x em S 3 ∃y em T 3 p(x, y)]⇔ [∃y em T 3 ∃x em S 3 p(x, y)]
e
[∀x em S, ∀y em T, p(x, y)]⇔ [∀y em T, ∀x em S, p(x, y)]
b)
{[∀x em D, p(x)] ∧ [∀x em D, q(x)]} ⇔ ∀x em D, [p(x) ∧ q(x)]
e
∃x em D 3 [p(x) ∨ q(x)]⇔ {[∃x em D 3 p(x)] ∨ [∃x em D 3 q(x)]}.
8. Considere as seguinte proposicão: “Para toda galinha na gaiola e para toda cadeira na
cozinha existe uma frigideira no armário tal que se o ovo da galinha está na frigideira
então a galinha está a menos de dois metros da cadeira.”
35
a) Traduza esta proposicão para a forma simbólica.
b) Expresse a negação em símbolos e em Português.
c) Dê dois exemplos de ciscunstâncias nas quais a proposição seria verdade.
d) Dê dois exemplos de ciscunstâncias nas quais a proposição seria falsa.
1.8 Métodos de demonstração
Agora que aprendemos o básico de lógica, precisamos colocar em prática nossas ideias
para demonstração de teoremas. Claramente que, como já observamos lendo livros texto de
matemática, as demonstrações são escritas de uma maneira informal em vez do estilo bas-
tante formal em nossas demonstrações na seção 1.5. Mas, apesar desta óbvia diferença de
estilo, a estrutura lógica é a mesma em cada caso: assumindo que as hipóteses são verdade,
escrevemos uma sequência de proposições que são consequências lógicas do que escrevemos
anteriormente, encerrando com a conclusão do teorema. Por exemplo, considere o seguinte
teorema
e prova:
Teorema: Se m e n são inteiros pares então m + n é um inteiro par. (Lembre-se que um
inteiro n é par se, e somente se, existe um inteiro k tal que n = 2k; n é ímpar se, e somente
se, existe um inteiro k tal que n = 2k = 1.)
Demonstração: Sejam m e n inteiros pares. Então existem j e k inteiros tais que m = 2j e
n = 2k. Então m+ n = 2j + 2k = 2(j + k). Portanto, m+ n é par.
�
Aqui apresentamos o que é conhecido por demonstração direta: começamos assumindo a
hipótese (m e n são inteiros pares) e desenvolvemos uma sequência de consequências lógicas,
encerrando com a conclusão (m+n é par). Note que há alguns quantificadores escondidos que
precisam ser examinados. Uma sentença completa do teorema seria “∀m,∀n (m é um inteiro
par e n é um inteiro par) → (m+ n é um inteiro par).” Como foi que provamos este teorema
considerando apenas dois inteiros (m e n) quando queríamos demonstrar que a conclusão vale
para todos os inteiros? Seria diferente se tivessemos observado que 2 e 4 são pares e que sua
soma, 6, é par? Sim, muito diferente! A demonstração acima contém um exemplo do uso de
variáveis “fixas mas arbitrárias.” Observando que 2 + 4 = 6 e que 6 é par somente mostra qie
o teorema é verdade para estes dois números. Entretanto, se escolhemos dois inteiros pares e
não assumimos nada mais sobre eles então o mesmo raciocínio pode ser usado para qualquer
par de inteiros pares, então a prova é geral e vale para todos os inteiros pares. Assim, o termo
“fixo mas arbitrário”: m e n são fixos (e podemos fazer cálculos com eles), mas são arbitrários
(não têm nenhuma propriedade que não são compartilhas por todos os inteiros pares).
Existem dois outros métodos de demonstração usados usualmente, ambos baseados nas
familiares equivalências lógicas: as equivalências contrapositiva e reductio ad absurdum. Para
conveniência listamos as duas equivalências aqui novamente (lembre que c representa uma
contradição, a proposição que é sempre falsa):
(p→ q)⇔ (¬q → ¬p) contrapositiva
(p→ q)⇔ ((p ∧ ¬q)→ c) reductio ad absurdum.
36
Vejamos o que elas nos dizem para demonstrar um teorema. Suponha que estamos interessa-
dos em provar um teorema, digamos p→ q. A lei contrapositiva nos diz que isso é equivalente
a sua contrapositiva, ¬q → ¬p. Assim, poderíamos provar o teorema assumindo ¬q e encer-
rando com ¬p; isto é começamos com a negação da conclusão do teorema e encerramos com
a negação da hipótese. Chamaremos esta demonstração de demonstração por contrapositiva.
Por exemplo, considere a demonstração por contrapositiva do teorema acima, onde nosso
ponto de partida será que m+ n não é par (a negação da conclusão):
Demonstração: Suponha que m,n sejam inteiros e que m + n não é par, isto é m + n
é ímpar. Então existe um inteiro k tal que m+ n = 2k + 1. Agora, m é par ou ímpar. Se m
for ímpar, a demonstração estará finalizada, portanto assuma que m é par. Então existe um
inteiro j tal que m = 2j. Portanto,
n = (m+ n)−m = 2k + 1− 2j = 2(k − j) + 1,
portanto n é ímpar e a demonstração está completa.
�
Existem vários pontos neste demonstração por contrapositiva que devem ser analisados.
Para ajudar a ver isso, vamos analisar a forma do teorema negligenciando os quantificadores.
Sejam p “m é um inteiro par,” q “n é um inteiro par” e r “m+ n é um inteiro par.” Então o
teorema é
(p ∧ q)→ r.
Assim a contrapositiva é
¬r → ¬(p ∧ q).
Podemos usar a lei de DeMorgan para obter a forma logicamente equivalente:
¬r → (¬p ∨ ¬q),
e essa é a forma usada na demonstração acima. Uma tradução disto em palavras seria “Se
m+n é ímpar então m é ímpar ou n é ímpar.” Assim a forma contrapositiva do teorema tem
uma disjunção como conclusão. Relembre que uma disjunção é verdade quando pelo menos
uma das subproposições é verdade, então para mostrar que a conclusão é verdade precisamos
mostrar que m é ímpar ou n é ímpar. A demonstração acima fez isso dizendo que se m é
ímpar ou par (lembre-se que p∨¬p é uma tautologia) e então analisando ambos os casos (um
exemplo de análise exaustiva): se m é ímpar então “m é ímpar ou n é ímpar” é verdade e o
teorema está demonstrado; se m é par então n é ímpar (um pouco de trabalho foi requerido
aqui) então “m é ímpar ou n é ímpar” é ainda verdade, o que completa a demonstração. Essa
é a técnica comum para mostrar que uma disjunção é verdade, isto é se uma subproposição é
verdade, estamos prontos, portanto assumimos que uma subproposição é falsa e mostramos
que a outra subproposição deve necessariamente ser verdade.
O método de demonstração baseado na equivalência reductio ad absurdum é chamado de
demonstração indireta ou demonstração por contradição foi discutido na seção 1.5. Lembre-se
que isso envolve começar com uma hipótese adicional, a negação da conclusão, e a demonstra-
ção estará completa quando uma contradição é obtida. Como um exemplo, a demonstração
indireta ou por contradição do teorema enunciado acima:
37
Demonstração: Suponha que m,n sejam inteiros pares e que m + n seja ímpar. Então
existem inteiros j, k tais que m = 2j e m+ n = 2k + 1. Assim
n = (m+ n)−m = 2k + 1− 2j = 2(k − j) + 1.
Portanto, n é ímpar e par, uma contradição, que completa a demonstração.
�
Antes de analisar esta demonstração, estejamos certos que entendemos a equivalência
reductio ad absurdum. Lembre-se que p ∧ ¬q é a negação de p → q portanto a equivalência
reductio ad absurdum é equivalente a
(p→ q)⇔ (¬(p→ q)→ c).
Se a proposição implica uma contradição (relembre que c representa uma contradição) então
a proposição deve ser necessariamente falsa (absurdo, número 23 da lista de tautologias na
seção 1.4). Assim, se ¬(p → q) → c é verdade, ¬(p → q) deve necessariamente ser falso,
isto é, p → q é verdade. O que isso nos diz sobre a demonstração indireta é que ao invés
de demonstrar p → q, podemos mostrar (p ∧ ¬q) → c, isto é mostrar que a conjunção da
hipótese original, p, e a negação da conclusão, ¬q, nos leva a uma contradição.
Traduzindo isso para o teorema enunciado acima, a forma da demonstração indireta é
(usando p, q, r como antes):
(p ∧ q ∧ ¬r)→ c,
ou, em palavras, “m é um inteiro par e n é um inteiro par e m + n é um inteiro ímpar
implica em uma contradição.” A particular contradição que obtemos em nosso caso foi “n é
par e n é ímpar (não par),” embora qualquer contradição tenha servido também. Uma das
vantagens da demonstração indireta é que ela nos dá uma hipótese adicional para trabalhar
e é particularmente útil para provar a não existência de objetos matemáticos.
Vamos, agora, resumir os três métodos de demonstração:
a) Demonstração direta: Assuma as hipóteses, desenvolva a demonstração (corpo da de-
monstração) e chegue a conclusão.
b) Demonstração por contrapositiva: Assuma a negação da conclusão, desenvolva a
demonstração (corpo da demonstração) e chegue na negação das hipóteses.
c) Demonstração indireta ou por contradição: Assuma as hipóteses e a negação da
conclusão, desenvolva a demonstração (corpo da demonstração) e chegue a uma contra-
dição.
Em cada uma destas formas, “corpo da demonstração” representa as consequências lógicas
que seguem das premissas e nos levam a uma “conclusão,” que pode ser a conclusão original,
a negação das hipóteses ou uma contradição.
Se um teorema a ser demonstrado tem a forma p ↔ q, então a demonstração deve ser
quebrada em duas partes, uma para mostrar que p → q e a outra para mostrar a recíproca,
q → p.
38
Como foi no caso dos princípios de demonstração, não usamos nossas técnicas de demons-
tração para mostar que uma conjectura é falsa. Naturalmente, nossa incapacidade de produzir
uma demonstração para a verdade da conjectura não é suficiente para garantir sua falsidade,
logo devemos utilizar contra-exemplos. Se tivessemos a seguinte conjectura:
“Se x é um inteiro ímpar e y é um inteiro par então x+ y é par”
podemos mostrar que ela é falsa produzindo um contra-exemplo x = 3 e y = 2 e observar