LPLbook_-_Captulo_05_-_Mtodos_de_Prova_para_a_Lgica_Booleana (1)

Prévia do material em texto

Caṕıtulo 5
Métodos de Prova para Lógica
Booleana
Tabelas verdade nos dão técnicas poderosas para investigar a lógica dos opera-
dores booleanos. Mas elas não são de forma alguma o fim da história. Tabelas
verdade são razoavelmente boas para mostrar a validade de argumentos sim-
ples que dependem somente dos conectivos verofuncionais, mas o método tem
duas limitações muito significativas.
Primeiro, tabelas verdade ficam extremamente grandes quando o número
de sentenças atômicas aumenta. Um argumento envolvendo sete sentençaslimitações dos métodos
da tabela verdade atômicas é dificilmente incomum, mas testar a sua validade exigiria uma
tabela verdade com 27 = 128 linhas. Testar um argumento com 14 sentenças
atômicas, apenas duas vezes maior, exigiria uma tabela contendo mais de 16
mil linhas. Você provavelmente poderia obter um doutorado em lógica por
construir uma tabela verdade deste tamanho. Este crescimento exponencial
limita severamente o valor prático do método da tabela verdade.
A segunda limitação é, surpreendentemente, ainda mais significativa. Méto-
dos de tabela verdade não podem ser facilmente estendidos para racioćınios
cuja validade dependem mais do que apenas conectivos verofuncionais. Como
você pode imaginar a partir da artificialidade dos argumentos analisados em
caṕıtulos anteriores, isto exclui a maioria dos tipos de racioćınio que encon-
tramos na vida cotidiana. O racioćınio ordinário depende muito da lógica dos
conectivos booleanos, não se enganem sobre isso. Mas conta também com a
lógica de outros tipos de expressões. Uma vez que o método da tabela ver-
dade detecta apenas consequência tautológica, precisamos de um método de
aplicação de lógica booleana que pode trabalhar junto com outro prinćıpios
válidos de racioćınio.
Métodos de prova, tanto formal como informal, dá-nos a capacidade de ex-
tensão requerida. Neste caṕıtulo, discutiremos padrões leǵıtimos de inferência
que surgem quando nós introduzimos os conectivos booleanos em uma lin-
guagem, e mostramos como aplicar os padrões em provas informais. No Caṕıtu-
lo 6, vamos estender o nosso sistema formal com regras correspondentes. A
principal vantagem dos métodos de prova sobre tabelas verdade é que nós va-
mos ser capazes de usá-los, mesmo quando a validade da nossa prova depender
de mais do que apenas os operadores booleanos.
Os conectivos booleanos dão origem a muitos padrões de inferência válidos.
138
Passos de inferência válidos / 139
Alguns deles são extremamente simples, como a implicação da sentença de
P ∧ Q a P. Vamos nos referir a isto como passos de inferência válidos, e discu-
tiremos sobre isso brevemente na primeira seção. Muito mais interessante são
dois novos métodos de prova que são permitidos pelas novas expressões: prova
por casos e prova por contradição. Iremos discutir sobre eles mais tarde, um
de cada vez.
Seção 5.1
Passos de inferência válidos
Aqui está uma regra de ouro importante: Em uma prova informal, é sempre
leǵıtimo se deslocar de uma sentença P para outra sentença Q, se você e
seu “público” (a pessoa ou as pessoas que você está tentando convencer) já regra de ouro
importantesabe que Q é uma consequência lógica de P. A principal exceção a esta regra
é quando você dá provas informais para o seu instrutor de lógica: presumi-
velmente, seu instrutor sabe que o argumento atribúıdo é válido, portanto,
nessas circunstâncias, você tem que fingir que você está apresentando a prova
para alguém que ainda não sabe disso. O que você está realmente fazendo é
convencendo o seu instrutor que você vê que o argumento é válido e que você
poderia provar a alguém que não viu.
A razão pela qual nós começamos com esta regra de ouro é que você já
aprendeu várias equivalências lógicas bem conhecidas que você deve sentir-se
livre para usar ao dar provas informais. Por exemplo, você pode livremente
usar dupla negação ou idempotência se surgir a necessidade em uma prova.
Assim, uma cadeia de equivalências do tipo que demos na página 131 é um
componente leǵıtimo de uma prova informal. Claro, se for solicitado a provar
uma das equivalências nomeadas, digamos uma das leis de distribuição ou leis
de DeMorgan, então você não deve as pressupor em sua prova. Você vai ter
que descobrir uma maneira de prová-la a alguém que ainda não sabe que ela
é válida.
Um caso especial desta regra é o seguinte: Se você já sabe que uma sentença
Q é uma verdade lógica, então você pode afirmar Q em qualquer ponto de sua
prova. Já vimos esse prinćıpio sendo usado no Caṕıtulo 2, quando discutimos a
reflexividade da identidade, o prinćıpio que nos permitiu afirmar uma sentença
da forma a = a em qualquer ponto em uma prova. Isto também nos permite
afirmar outras verdades lógicas simples, como o terceiro exclúıdo (P ∨ ¬P), em
qualquer ponto de uma prova. Claro, as verdades lógicas têm que ser simples
o suficiente para que você possa ter certeza que seu público irá reconhecê-las.
Há três passos simples de inferência que mencionaremos aqui que não
Seção 5.1
140 / Métodos de Prova para Lógica Booleana
envolvem equivalências lógicas ou verdades lógicas, mas que são claramente
apoiados pelos significados de ∧ e ∨. Primeiro, suponha que conseguimos
provar uma conjunção, digamos P ∧ Q, durante a nossa prova. As sentenças
individuais P e Q são claramente consequências dessa sentença, porque não há
nenhuma maneira de a conjunção ser verdadeira, sem que cada sentença seja
verdadeira. Assim, estamos justificados em afirmar qualquer uma. De modo
mais geral, nós estamos justificados em inferir, a partir de uma conjunção de
qualquer número de sentenças, qualquer uma de suas sentenças. Este padrãoeliminação
da conjunção
(simplificação)
de inferência é às vezes chamado de eliminação da conjunção ou simplificação,
quando é apresentado no contexto de um sistema formal de dedução. Quando é
utilizado em provas informais, no entanto, geralmente passa sem comentários,
uma vez que é tão óbvio.
Apenas um pouco mais interessante é o inverso. Dado o significado de
∧, é claro que P ∧ Q é uma consequência lógica do par de sentenças P e Q:
não há como as últimas serem verdadeiras, sem que a primeira também seja
verdadeira. Assim, se conseguimos provar P e provar Q a partir das mesmas
premissas, então temos o direito de inferir a conjunção P ∧ Q. De modo mais
geral, se queremos provar uma conjunção de um monte de sentenças, podemosintrodução da
conjunção fazê-lo provando cada uma separadamente. Em um sistema formal de dedução,
medidas desse tipo são chamadas às vezes de introdução da conjunção ou
apenas conjunção. Mais uma vez, no racioćınio da vida real, esses passos
são muito simples para justificar a menção. Nas nossas provas informais, nós
raramente iremos apontá-los explicitamente.
Finalmente, olhemos para um padrão de inferência válido envolvendo ∨.
É um passo simples, mas que parece estranho para os alunos. Suponha que
você provou Cube(b). Então, você pode concluir Cube(a) ∨ Cube(b) ∨ Cube(c),introdução
da disjunção se você quiser, por alguma razão, uma vez que esta é uma consequência da
primeira. De modo mais geral, se você provou alguma sentença P, então você
pode inferir qualquer disjunção que tenha P como um de seus componentes.
Afinal, se P é verdadeira, então qualquer disjunção deste tipo também é.
O que impressiona os recém-chegados à lógica sobre esse passo é que usá-
lo equivale a jogar fora informações. Por que você iria querer concluir P ∨ Q
quando você já sabe da proposição mais informativa P? Mas, como veremos,
este passo é bastante útil quando combinado com alguns dos métodos de prova
a serem discutidos mais tarde. Ainda assim, em provas matemáticas,geral-
mente passam despercebidas. Em sistemas formais, é apelidado de introdução
da disjunção, ou (e infelizmente) soma.
Caṕıtulo 5
Passos de inferência válidos / 141
Questões de estilo
Provas informais servem a dois propósitos. Por um lado, eles são um método
de descoberta, pois eles permitem-nos extrair novas informações a partir de
informações já obtidas. Por outro lado, eles são um método de comunicação,
pois eles nos permitem transmitir nossas descobertas para os outros. Tal como
acontece com todas as formas de comunicação, isso pode ser bem feito ou mal
feito.
Quando aprendemos a escrever, aprendemos algumas regras básicas de
pontuação, uso de letras maiúsculas, estrutura de parágrafo e assim por diante.
Mas, além das regras básicas, há também questões de estilo. Autores diferentes
têm estilos diferentes. E isso é uma coisa boa, uma vez que iŕıamos ficar muito
cansados de ler se todo mundo escrevesse com o mesmo estilo. Assim também
acontece com as provas. Se você continuar a estudar matemática, você vai ler
muitas provas, e você vai achar que todo escritor tem o seu próprio estilo.
Você ainda vai desenvolver um estilo próprio.
Cada passo em uma “boa” prova, além de ser correto, deve ter duas pro-
priedades. Deve ser facilmente compreendida e significativa. por “facilmente
compreendida” queremos dizer que as outras pessoas devem ser capazes de
acompanhar o passo sem dificuldade indevida: elas devem ser capazes de ver
que o passo é válido, sem ter que se envolver sozinhos em um pedaço de
racioćınio complexo. Por “significativo” queremos dizer que o passo deve ser
informativo, e não um desperd́ıcio do tempo do leitor.
Estes dois critérios vão em direções opostas. Normalmente, quanto mais
significativo o passo, mais dif́ıcil de entender ele é. Um bom estilo requer um
equiĺıbrio razoável entre os dois. E isso, por sua vez requer alguma noção de conhecer o seu público
quem é seu público. Por exemplo, se você e seu público têm trabalhado com
lógica há algum tempo, você vai reconhecer uma série de equivalências que
você vai querer usar, sem mais uma prova. Mas se você ou o seu público são
iniciantes, a mesma inferência pode necessitar de vários passos.
Seção 5.1
142 / Métodos de Prova para Lógica Booleana
Lembre-se
1. Ao dar uma prova informal a partir de algumas premissas, se Q já é
reconhecida como uma consequência lógica das sentenças P1, . . . ,Pn e
cada uma de P1, . . . ,Pn foi provada a partir das premissas, então você
pode afirmar Q em sua prova.
2. Cada passo em uma prova informal deve ser significativo, mas facil-
mente compreendido.
3. Se um passo é significativo ou facilmente entendido depende do público
a quem se dirige.
4. A seguir apresentamos padrões válidos de inferência que, geralmente,
não serão mencionados nas provas informais:
◦ De P ∧ Q, inferir P.
◦ De P e Q, inferir P ∧ Q.
◦ De P, inferir P ∨ Q.
Exerćıcios
Nos exerćıcios a seguir, listamos uma série de padrões de inferência, dos quais apenas alguns são válidos.
Para cada padrão, determine se ele é válido. Se for, explique por que é válido, recorrendo às tabelas
verdade dos conectivos envolvidos. Se não for, dê um exemplo concreto de como o passo poderia ser
usado para obter, a partir de premissas verdadeiras, uma conclusão falsa.
5.1
�
De P ∨ Q e ¬P, inferir Q. 5.2
�
De P ∨ Q e Q, inferir ¬P.
5.3
�
De ¬(P ∨ Q), inferir ¬P. 5.4
�
De ¬(P ∧ Q) e P, inferir ¬Q.
5.5
�
De ¬(P ∧ Q), inferir ¬P. 5.6
��
De P ∧ Q e ¬P, inferir R.
Caṕıtulo 5
Prova por casos / 143
Seção 5.2
Prova por casos
As formas simples de inferência discutidas na última seção são todas instâncias
do prinćıpio de que você pode usar casos já estabelecidos de consequência
lógica em provas informais. Mas os conectivos booleanos também dão origem
a dois métodos de prova inteiramente novos, métodos que são explicitamente
aplicados em todos os tipos de racioćınio rigoroso. O primeiro destes é o
método de prova por casos. No nosso sistema formal F , este método será
chamado de eliminação da disjunção, mas não se deixe enganar pelo nome soar
comum: é muito mais significativo do que, digamos, introdução da disjunção
ou eliminação da conjunção.
Começamos ilustrando a prova por casos com um pedaço bem conhecido do
racioćınio matemático. O racioćınio mostra que existem números irracionais
b e c tais que bc é racional. Primeiro, vamos rever o que isso significa. Um
número é dito ser racional se pode ser expresso como uma fração n/m, para
inteiros n e m. Se não puder ser expresso como tal, então é irracional. Assim
2 é racional (2 = 2/1), mas
√
2 é irracional. (Vamos provar este último fato
na próxima seção, para ilustrar prova por contradição; por enquanto, apenas
aceite como uma verdade bem conhecida) Agora, aqui está a nossa prova:
Prova: Para mostrar que não existem números irracionais b e c tais
que bc é racional, vamos considerar o número
√
2
√
2
. Notamos que
esse número ou é racional ou irracional.
Se
√
2
√
2
é racional, então nós encontramos os nossos b e c, ou seja,
nós tomamos b = c =
√
2.
Suponhamos, por outro lado, que
√
2
√
2
é irracional. Então tomamos
b =
√
2
√
2
e c =
√
2 e calculamos bc:
bc = (
√
2
√
2
)
√
2
=
√
2
(
√
2·√2)
=
√
2
2
= 2
Assim, vemos que, neste caso, bc é racional também.
Consequentemente, se
√
2
√
2
é racional ou irracional, sabemos que
existem números irracionais b e c tais que bc é racional.
Seção 5.2
144 / Métodos de Prova para Lógica Booleana
O que nos interessa aqui não é o resultado em si, mas a estrutura geral do
argumento. Começamos com um objetivo desejado que nós queremos provar,
digamos S, e uma disjunção que já sabemos, digamos P ∨ Q. Em seguida,prova por casos
mostramos duas coisas: que S é verdadeira se presumirmos que P é o caso,
e que S é verdadeira se assumimos que Q é o caso. Como sabemos que uma
delas deve ser verdadeira, nós então conclúımos que S tem que ser verdadeira.
Este é o padrão de racioćınio conhecido como prova por casos.
Na prova por casos, não estamos limitados a dividir em apenas dois casos,
como fizemos no exemplo. Se em qualquer estágio de uma prova de que temos
um disjunção contendo n sentenças, digamos P1∨ . . . ∨ Pn, então podemos
quebrar em n casos. No primeiro assumimos P1, no seguinte P2, e assim por
diante para cada sentença. Se somos capazes de provar o nosso resultado
desejado S em cada um desses casos, estamos justificados em concluir que S
é verdadeira.
Vejamos um exemplo ainda mais simples de prova por casos. Suponha que
queremos provar que Small(c) é uma consequência lógica de
(Cube(c) ∧ Small(c)) ∨ (Tet(c) ∧ Small(c))
Isso é bastante óbvio, mas a prova envolve a quebra em casos, como você vai
notar se você pensar cuidadosamente sobre como você reconhece isso. Para
que conste, aqui é como nós iŕıamos escrever a prova.
Prova: Nos foi dado
(Cube(c) ∧ Small(c)) ∨ (Tet(c) ∧ Small(c))
como premissa. Nós vamos quebrar em dois casos, correspondendo
às duas sentenças da disjunção. Em primeiro lugar, suponhamos
que Cube(c) ∧ Small(c) é verdadeira. Mas então (por eliminação da
conjunção, que realmente não deveŕıamos sequer mencionar), temos
Small(c). Mas da mesma forma, se presumirmos Tet(c) ∧ Small(c),
então advém que Small(c). Assim, em qualquer caso, temos Small(c),
como desejado.
Nosso próximo exemplo mostra como o passo estranho de introdução da
disjunção (a partir de P inferir P ∨ Q) pode ser usado proveitosamente com a
prova por casos. Suponha que sabemos que ou Max está em casa e Carl está
feliz, ou Claire está em casa e Scruffy está feliz, ou seja,
(Casa(max) ∧ Feliz(carl)) ∨ (Casa(claire) ∧ Feliz(scruffy))
Queremos provar que, ou Carl ou Scruffy está feliz, isto é,
Feliz(carl) ∨ Feliz(scruffy)
Caṕıtulo 5
Provapor casos / 145
Uma prova passo-a-passo, um tanto pedante, ficaria assim:
Prova: Suponha a disjunção:
(Casa(max) ∧ Feliz(carl)) ∨ (Casa(claire) ∧ Feliz(scruffy))
Então ou
Casa(max) ∧ Feliz(carl)
ou:
Casa(claire) ∧ Feliz(scruffy).
Se a primeira alternativa for verdadeira, então Feliz(Carl), e por isso
temos
Feliz(carl) ∨ Feliz(scruffy)
pela introdução da disjunção. Do mesmo modo, se a segunda alter-
nativa for verdadeira, temos Feliz(scruffy), e assim
Feliz(carl) ∨ Feliz(scruffy).
Portanto, em ambos os casos, temos a nossa conclusão desejada.
Assim, nossa conclusão advém através de uma prova por casos.
Argumentar por casos é extremamente útil no racioćınio cotidiano. Por
exemplo, um dos autores (vamos chamá-lo de J) e sua esposa recentemente
lembraram-se que o parqúımetro deles tinha expirado várias horas antes. J
argumentou da seguinte maneira que não havia sentido em apressar-se de
volta para o automóvel (lógicos argumentam desta forma, não se case com
um):
Prova: A esta altura, ou nós já fomos multados ou não fomos. Se
já fomos multados, não seremos multados novamente no tempo que
nos leva para chegar ao carro, então correr não teria qualquer utili-
dade. Se nós não fomos multados nas últimas horas, é extremamente
improvável que sejamos multados nos poucos minutos seguintes, de
modo que, novamente, correr seria inútil. Em ambos os casos, não
há necessidade de apressar-se.
A esposa de J respondeu com o seguinte contra-argumento (mostrando
que muitos anos de casamento com um lógico tem um impacto):
Prova: Ou vamos ser multados nos próximos poucos minutos ou
não vamos ser multados. Se formos ser multados, então correr pode
impedir isso, o que seria uma coisa boa. Se não formos ser multados,
Seção 5.2
146 / Métodos de Prova para Lógica Booleana
então ainda assim será um bom exerćıcio e também vai mostrar o
nosso respeito pela lei, sendo que ambas são coisas boas. Assim, em
ambos os casos, correr de volta para o carro é uma coisa boa a se
fazer.
A esposa de J ganhou a discussão.
A validade da prova por casos não pode ser demonstrada pelo método
simples da tabela verdade introduzido no caṕıtulo 4. A razão é que pode-
mos inferir a conclusão S do fato de que S é comprovável a partir de cada
uma das sentenças P e Q. Ele se baseia no prinćıpio de que se S é uma con-
sequência lógica de P, e também uma consequência lógica de Q, então é uma
consequência lógica de P ∨ Q. Isto é porque qualquer circunstância que faz
P ∨ Q verdadeira deve fazer pelo menos uma de P ou Q verdadeira, e por
conseguinte, S também, pelo fato de S ser uma consequência das duas.
Lembre-se
Prova por casos: Para provar S a partir de P1 ∨ . . . ∨ Pn usando este
método, prove S a partir de cada um de P1, . . . , Pn.
Exerćıcios
Os próximos dois exerćıcios apresentam argumentos válidos. Entregue provas informais da validade dos
argumentos. Suas provas devem ser redigidas em sentenças em Português, bem formadas e completas,
fazendo uso de sentenças de primeira ordem de acordo com a sua conveniência, de acordo com o estilo
que usamos acima. Sempre que você usar a prova por casos, digamos assim. Você não tem que ser
expĺıcito sobre o uso de passos simples de prova como eliminação da conjunção. Por sinal, normalmente
há mais de uma maneira de provar um determinado resultado.
5.7
�
Casa(max) ∨ Casa(claire)
¬Casa(max) ∨ Feliz(carl)
¬Casa(claire) ∨ Feliz(carl)
Feliz(carl)
5.8
�
LeftOf(a, b) ∨ RightOf(a, b)
BackOf(a, b) ∨ ¬LeftOf(a, b)
FrontOf(b, a) ∨ ¬RightOf(a, b)
SameCol(c, a) ∧ SameRow(c, b)
BackOf(a, b)
5.9
�|�
Suponha que as mesmas quatro premissas do Exerćıcio 5.8. LeftOf(b, c) é uma consequência
lógica dessas premissas? Se assim for, entregue uma prova informal da validade do argumento.
Se não, submeta um mundo contraexemplo.
Caṕıtulo 5
Prova indireta: prova por contradição / 147
5.10
�
Suponha que o time de basquete favorito de Max é o Chicago Bulls e o time de futebol ameri-
cano favorito é o Denver Broncos. O pai de Max, John, está voltando de Indianápolis para São
Francisco na United Airlines, e prometeu comprar no caminho uma lembrança para Max de um
de seus times favoritos. Explique o racioćınio de John, recorrendo ao fato irritante que todos os
vôos da United entre Indianápolis e São Francisco param ou em Denver ou em Chicago. Torne
expĺıcito o papel que a prova por casos desempenha neste racioćınio.
5.11
�
Suponha que a poĺıcia está investigando um assalto e descobre os seguintes fatos. Todas as
portas da casa estavam fechadas por dentro e não mostram nenhum sinal de arrombamento.
De fato, as únicas maneiras de entrar e sair da casa eram por uma janela pequena do banheiro
no primeiro andar que foi deixada aberta e uma janela destrancada do quarto no segundo
andar. Com base nisto, os detetives descartaram uma ladrão conhecido, Julius, que pesa 114
quilos e tem artrite. Explique o racioćınio deles.
5.12
�
Em nossa prova de que existem números irracionais b e c onde bc é racional, um dos nossos
passos foi afirmar que
√
2
√
2
ou é racional ou irracional. O que justifica a introdução desta
afirmação à nossa prova?
5.13
�
Descreva um exemplo comum de racioćınio por casos que você tenha feito nos últimos dias.
5.14
��
Dê uma prova informal de que se S é uma consequência tautológica de P e uma consequência
tautológica de Q, então S é uma consequência tautológica de P ∨ Q. Lembre-se de que a tabela
verdade conjunta de P ∨ Q e S pode ter mais linhas ou do que a tabela verdade conjunta de
P e S, ou do que a tabela verdade conjunta de Q e S. [Dica: Suponha que você está olhando
para uma única linha da tabela verdade conjunta de P ∨ Q e S, em que P ∨ Q é verdadeira.
Comece com casos baseados em se P é verdadeira ou Q é verdadeira e prove que S tem que ser
verdadeira em ambos os casos.]
Seção 5.3
Prova indireta: prova por contradição
Um dos métodos mais importantes da prova é conhecido como prova por
contradição. É também chamado de prova indireta ou reductio ad absurdum.
Sua correspondente em F é chamada de introdução da negação.
A ideia básica é esta. Suponha que você queira provar uma sentença ne-
gativa, digamos ¬S, a partir de algumas premissas, digamos P1, . . . ,Pn. Uma prova indireta ou prova
por contradiçãomaneira de fazer isso é assumir temporariamente S e demonstrar que uma con-
tradição é resultado desta suposição. Se você pode demonstrar isso, então você
Seção 5.3
148 / Métodos de Prova para Lógica Booleana
tem direito de concluir que ¬S é uma consequência lógica das premissas origi-
nais. Por quê? Porque a sua prova da contradição mostra que S, P1, . . . ,Pn não
podem ser todas verdadeiras simultaneamente. (Se assim fosse, a contradição
teria de ser verdadeira, e ela não pode ser.) Dáı se P1, . . . ,Pn são verdadeiras
em qualquer conjunto de circunstâncias, então S tem que ser falsa nessas cir-
cunstâncias. O que significa dizer que, se P1, . . . ,Pn são todas verdadeiras,
então ¬S tem que ser verdadeira também.
Vejamos uma prova indireta simples. Suponha que Cube(c) ∨ Dodec(c) and
Tet(b). Vamos provar que ¬(b = c).
Prova: Para provar ¬(b = c), presumimos b = c e tentamos obter
uma contradição. De nossa primeira premissa, sabemos que ou Cube(c)
ou Dodec(c). Se a primeira for o caso, então podemos concluir Cube(b)
pela indiscernibilidade dos idênticos, o que contradiz Tet(b). Mas da
mesma forma, se a segunda for o caso, obtemos Dodec(b) que con-
tradiz Tet(b). Assim, nenhum dos casos é posśıvel, e nós temos uma
contradição. Desta forma, a nossa suposição inicial de que b = c deve
estar errada. Assim, a prova por contradição nos dá a nossa con-
clusão desejada, ¬(b = c). (Note-se que este argumento também usa
o método de prova por casos.)
Vamos agora dar um exemplo mais interessante e famoso deste métodode prova. Os gregos ficaram chocados ao descobrir que a raiz quadrada de
2 não poderia ser expressa como uma fração, ou, como diria, é irracional. A
prova deste fato procede por contradição. Antes de passar pela prova, vamos
rever alguns fatos numéricos simples que eram bem conhecidos dos gregos. O
primeiro é que qualquer número racional pode ser expresso como uma fração
p/q, onde pelo menos um de p e q é ı́mpar. (Se não, divida repetidamente
o numerador e o denominador por 2 até que um deles seja ı́mpar.) O outro
fato decorre da observação de que quando elevamos um número ı́mpar ao
quadrado, nós sempre teremos um número ı́mpar como resultado. Assim, se
n2 é um número par, então n também é par. E, a partir disso, vemos que, se
n2 é par, ele deve ser diviśıvel por 4.
Agora estamos prontos para a prova de que
√
2 é irracional.
Prova: Visando a obtenção de uma contradição, vamos supor que√
2 é racional. Assim, nesta hipótese,
√
2 pode ser expressa na forma
p/q, onde pelo menos um de p e q é ı́mpar. Como p/q =
√
2 podemos
elevar ambos os lados ao quadrado para obter:
p2
q2
= 2
Caṕıtulo 5
Prova indireta: prova por contradição / 149
Multiplicando ambos os lados por q2, temos p2 = 2q2. Mas isto
demonstra que p2 é um número par. Como observamos antes, isto
permite-nos concluir que p é par e que p2 é diviśıvel por 4. Olhando
novamente para a equação p2 = 2q2, vemos que se p2 é diviśıvel por
4, então 2q2 é diviśıvel por 4 e, portanto, q2 deve ser diviśıvel por 2.
Em ambos os casos, q também é par. Assim, ambos p e q são pares,
contradizendo o fato de que pelo menos um deles é ı́mpar. Assim, a
nossa hipótese de que
√
2 é racional nos levou a uma contradição, e
por isso concluimos que ele é irracional.
Em ambos os exemplos, foi utilizado o método de prova indireta para
provar uma sentença que começa com uma negação. (Lembre-se, “irracional”
significa simplesmente não racional.) Você também pode usar este método
para provar uma sentença de S que não comece com um negação. Neste caso,
você poderia começar presumindo ¬S, obter uma contradição, e então concluir
que ¬¬S é o caso, o que, claro, é equivalente a S.
A fim de aplicar o método de prova por contradição, é importante que você
entenda o que é uma contradição, que é o que você precisa provar a partir de
sua suposição temporária. Intuitivamente, a contradição é qualquer alegação contradição
que não pode ser verdadeira, ou qualquer conjunto de proposições que não
podem ser todas verdadeiras simultaneamente. Exemplos são uma sentença
Q e sua negação ¬Q, um par de proposições inconsistentes como Cube(c) e
Tet(c) ou x < y e y < x, ou uma única sentença da forma a �= a. Podemos
tomar a noção de contraditório ou conjunto de sentenças inconsistente para
ser qualquer conjunto de sentenças que não possam ser todas verdadeiras em
qualquer situação.
O śımbolo ⊥ é muitas vezes usado como uma forma abreviada de dizer que śımbolo de
contradição (⊥)uma contradição foi obtida. Diferentes pessoas lêem ⊥ como “contradição”, “o
absurdo,” e “falso”, mas o que isso significa é que uma conclusão foi alcançada,
que é logicamente imposśıvel, ou que várias conclusões foram derivadas as
quais, em conjunto, são imposśıveis.
Observe que a sentença S é uma impossibilidade lógica se, e somente se, sua
negação ¬S é logicamente necessária. Isso significa que qualquer método que
tivermos para demonstrar que uma sentença é logicamente necessária também
demonstra que a negação lógica é imposśıvel, isto é, uma contradição. Por
exemplo, se uma tabela verdade demonstra que ¬S é uma tautologia, então
sabemos que S é uma contradição.
Similarmente, o método da tabela verdade nos dá uma maneira de demon-
strar que uma coleção de sentenças são mutuamente contraditórias. Con-
strua uma tabela verdade conjunta para P1, . . . ,Pn. Estas sentenças são tt-
contraditórias se cada linha tem um F atribúıdo a pelo menos uma das sen- tt-contraditórias
Seção 5.3
150 / Métodos de Prova para Lógica Booleana
tenças. Se as sentenças são tt-contraditórias, sabemos que elas não podem ser
todas verdadeiras de uma vez, simplesmente em virtude dos significados dos
conectivos verofuncionais dos quais elas são constrúıdas. Nós já mencionamos
um exemplo: qualquer par de sentenças, em que uma seja a negação da outra.
O método da prova por contradição, como prova por casos, é muitas vezes
encontrado no racioćınio cotidiano, embora a contradição derivada seja al-
gumas vezes deixada impĺıcita. As pessoas, muitas vezes, presumem uma
proposição de causa do argumento e, em seguida, demonstram que a suposição
leva a algo que se sabe ser falso. Elas então concluem a negação da proposição
original. Esse tipo de racioćınio é, de fato, uma prova indireta: a incoerência
torna-se expĺıcita se acrescentarmos o fato conhecido ao nosso conjunto de
premissas.
Vejamos um exemplo desse tipo de racioćınio. Imagine um advogado de
defesa apresentando o seguinte resumo para o júri:
A promotoria afirma que meu cliente matou o proprietário do clube
KitKat. Suponha que eles estão corretos. Você já ouviu os próprios
especialistas deles testemunharem que o assassinato ocorreu às 5:15
da tarde. Nós também sabemos que o réu ainda estava no trabalho
na Câmara Municipal às 4:45, de acordo com o testemunho de cinco
colegas de trabalho. Segue-se que o meu cliente teve que se deslo-
car da Câmara Municipal para o clube KitKat, em 30 minutos ou
menos. Porém, fazer essa viagem leva 35 minutos, sob a melhor das
circunstâncias, e registros policiais mostram que houve um enorme
engarrafamento no dia do assassinato. Proponho que o meu cliente
é inocente.
Claramente, esse tipo de racioćınio é usado o tempo todo: sempre que
presumimos alguma coisa e, em seguida, eliminamos a hipótese, com base em
suas consequências. Às vezes, essas consequências não são contradições, ou
até mesmo coisas que sabemos ser falsas, mas sim consequências futuras que
consideramos inaceitáveis. Você pode, por exemplo, supor que você vai para
o Haváı para as férias de primavera, calcular o impacto sobre as suas finanças
e capacidade para terminar os trabalhos finais que faltam, e relutantemente
concluir que você não pode fazer a viagem. Quando você raciocinar desta
forma, você está usando o método da prova indireta.
Lembre-se
Prova por contradição: Para provar que ¬S usando este método, assuma
S e prove uma contradição ⊥.
Caṕıtulo 5
Prova indireta: prova por contradição / 151
Exerćıcios
Nos exerćıcios a seguir, decida se o argumento exibido é válido. Se for, entregue uma prova infor-
mal, redigidas em sentenças em Português, bem formadas e completas, fazendo uso de sentenças de
primeira ordem de acordo com a sua conveniência. Sempre que você usar a prova por casos ou prova
por contradição, diga isso. Você não tem que ser expĺıcito sobre o uso de passos de provas simples como
eliminação da conjunção. Se o argumento for inválido, construa um mundo contraexemplo em Tarski’s
World. (Argumento 5.16 é válido, e por isso não será necessário um contraexemplo.)
5.15
�|�
b é um tetraedro.
c é um cubo.
Ou c é maior que b ou então eles são idênticos.
b é menor que c.
5.16
�
Max ou Claire estão em casa mas ou Scruffy ou Carl está
infeliz.
Ou Max não está em casa ou Carl está feliz.
Ou Claire não está em casa ou Scruffy está infeliz.
Scruffy está infeliz.
5.17
�|�
Cube(a) ∨ Tet(a) ∨ Large(a)
¬Cube(a) ∨ a = b ∨ Large(a)
¬Large(a) ∨ a = c
¬(c = c ∧ Tet(a))
a = b ∨ a = c
5.18
�|�
Cube(a) ∨ Tet(a) ∨ Large(a)
¬Cube(a) ∨ a = b ∨ Large(a)
¬Large(a) ∨ a = c
¬(c = c ∧ Tet(a))
¬(Large(a) ∨ Tet(a))
5.19
�
Considere as seguintes sentenças
1. Folly era o animal de estimação de Claire às 2 pm ouàs 2:05 pm.
2. Folly era o animal de estimação de Max às 2 pm.
3. Folly era o animal de estimação de Claire às 2:05 pm.
Será que (3) é resultado de (1) e (2)? Será que (2) é resultado de (1) e (3)? Será que (1) é resul-
tado de (2) e (3)? Em cada caso, ou dê uma prova de consequência, ou descreva uma situação
que faz com que as premissas sejam verdadeiras e a conclusão seja falsa. Você pode presumir
que Folly só pode ser animal de estimação de uma pessoa em um determinado momento.
Seção 5.3
152 / Métodos de Prova para Lógica Booleana
5.20
�
Suponha que é sexta-feira à noite e você está saindo com seu namorado. Ele quer ver uma
comédia romântica, enquanto você quer ver o último filme de terror de Wes Craven. Ele ressalta
que, se ele vir o filme de terror de Wes Craven, não será capaz de dormir, porque não suporta ver
sangue, e terá de fazer o teste de admissão da faculdade de medicina amanhã. Se ele não fizer
bem este teste, não vai entrar na faculdade de medicina. Analise o argumento de seu namorado,
apontando onde a prova indireta está sendo usada. Como você refutaria o argumento dele?
5.21
�
Descreva um exemplo comum de uma prova indireta que você tenha usado nos últimos dias.
5.22
��
Prove que prova indireta é um método tautologicamente válido de prova. Isto é, mostre que se
P1, . . . ,Pn, S é tt-contraditória, então ¬S é consequência tautológica de P1, . . . ,Pn.
Nos próximos três exerćıcios pedimos que você prove fatos simples sobre os números naturais. Nós não
esperamos que você fraseie as provas em fol. Você vai ter que recorrer a fatos básicos da aritmética,
além das definições de números pares e ı́mpares. Isto está OK, mas torne o uso desses recursos expĺıcito.
Também torne expĺıcito qualquer uso de prova por contradição.
5.23
��
Suponha que n2 é
ı́mpar. Prove que n
é ı́mpar.
5.24
��
Suponha que n+m
é ı́mpar. Prove que
n×m é par.
5.25
��
Suponha que n2 é
diviśıvel por 3.
Prove que n2 é
diviśıvel por 9.
5.26
���
Uma boa maneira de ter certeza de que você entende uma prova é tentar generalizá-la. Prove
que
√
3 é irracional. [Dica: Você precisa descobrir alguns fatos sobre divisibilidade por 3, que
são paralelos aos fatos que usamos sobre pares e ı́mpares, por exemplo, o fato expresso no
Exerćıcio 5.25.] Você pode generalizar esses dois resultados?
Seção 5.4
Argumentos com premissas inconsistentes
O que é resultado de um conjunto inconsistente de premissas? Se você olhar
atrás para a nossa definição de consequência lógica, você vai ver que cada
sentença é consequência de um conjunto deste tipo. Afinal de contas, se as
premissas são contraditórias, então não há nenhuma circunstância em que
todas sejam verdadeiras. Assim, não há circunstâncias nas quais as premissas
sejam verdadeiras e a conclusão seja falsa. O que significa dizer, em qualquer
situação em que as premissas são todas verdadeiras (não há nenhuma destas!),
a conclusão será verdadeira também. Por isso, qualquer argumento com umsempre válido
conjunto inconsistente de premissas é trivialmente válido. Em particular, se
Caṕıtulo 5
Argumentos com premissas inconsistentes / 153
alguém pode estabelecer uma contradição ⊥ baseado nas premissas, então
temos o direito de afirmar qualquer sentença.
Isso muitas vezes atinge os alunos como um método muito estranho de
racioćınio, e por razão muito boa. Recordemos a distinção entre um argu-
mento válido e um argumento correto. Um argumento correto é um argumento
válido com as premissas verdadeiras. Mesmo que qualquer argumento com um
conjunto inconsistente de premissas seja válido, nenhum argumento deste tipo
é correto, uma vez que não há nenhuma maneira das premissas do argumento
serem todas verdadeiras. Por esta razão, um argumento com um conjunto in-
consistente de premissas não vale muito por conta própria. Afinal de contas,
a razão de estarmos interessados em consequência lógica é por causa de sua nunca correto
relação com a verdade. Se as premissas não podem ser verdadeiras, então,
mesmo que saibamos que o argumento é válido não temos nenhuma pista so-
bre a verdade ou falsidade da conclusão. Um argumento incorreto não dá mais
apoio à sua conclusão do que um argumento inválido.
Em geral, os métodos de prova não nos permitem mostrar que um argu-
mento é incorreto. Afinal de contas, a verdade ou falsidade das premissas não
é uma questão de lógica, mas de como o mundo é. Mas no caso de argumentos
com premissas inconsistentes, nossos métodos de prova nos dão uma maneira
de demonstrar que, pelo menos, uma das premissas é falsa (embora talvez
não saiba qual), e, portanto, que o argumento é incorreto. Para fazer isso, nós
provamos que as premissas são inconsistentes por levar a uma contradição.
Suponha, por exemplo, que você tem uma prova de que o seguinte argu-
mento é válido:
Casa(max) ∨ Casa(claire)
¬Casa(max)
¬Casa(claire)
Casa(max) ∧ Feliz(carl)
Embora seja verdade que esta conclusão é uma consequência das premissas,
sua reação não deve ser a de acreditar na conclusão. De fato, usando a prova
por casos, podemos demonstrar que as premissas são inconsistentes, e, por-
tanto, que o argumento é incorreto. Não há razão de estar convencido da
conclusão de um argumento incorreto.
Seção 5.4
154 / Métodos de Prova para Lógica Booleana
Lembre-se
A prova de uma contradição ⊥ a partir de premissas P1, . . . ,Pn (sem
suposições adicionais) demonstra que as premissas são inconsistentes. Um
argumento com premissas inconsistentes é sempre válido, mas o mais
importante, sempre incorreto.
Exerćıcios
5.27
�
Dê duas provas diferentes de que as premissas do argumento acima são inconsistentes. Sua
primeira prova deve usar a prova por casos, mas não a Lei de DeMorgan, enquanto que a
segunda prova pode usar DeMorgan, mas não prova por casos.
Caṕıtulo 5