Logic A
Logic A
Logic A
DEPARTAMENTO DE MATEMTICA.
DISCIPLINA: TEORIA DE CONJUNTOS
TEMA I: INTRODUO LGICA MATEMTICA (V3-2008.1)
PROF. DR. ALBERTO M. MARTNEZ CASTAEDA
SUMRIO:
Item CONTEDO Pg.
01 Introduo Lgica 02
02 Proposies. 03
03 Sentenas abertas e fechadas. 04
04 Noes de lgebra Proposicional. Conectivos Lgicos. 04
05 Equivalncia Lgica. 08
06 Tautologia, Contradio e Contingncia. 09
07 Ordem de precedncia das operaes. 10
08 Leis da lgebra Proposicional. 12
09 Principio de Dualidade. 13
10 Implicao Lgica. 13
11 Deduo no Clculo Proposicional. 14
11.1
Argumentos. 14
11.2
Critrio de validade de um argumento. 16
11.3
Argumentos Dedutivos e Indutivos. 18
12 Regras de Inferncia. 19
13 Validade e Invalidade de um Argumento. 27
14 Clculo de Predicados. 30
15 Operaes Lgicas com Sentenas Abertas. 34
16 Quantificadores. 36
17 Teoremas. 40
18 Definies. 45
19 Como se apresenta uma teoria matemtica? 46
20 Provas. Mtodos de demonstrao de teoremas. 49
20.1
Provas. 50
20.2
Mtodos de Demonstrao de Teoremas. 50
20.3
Demonstrao Direta.
20.4
Demonstrao pelo Contrapositivo. 51
20.5
Demonstrao pelo Absurdo. 52
20.6
Demonstrao por Induo Matemtica. 54
20.7
Prova por Construo. 56
20.8
Prova por contra-exemplo. 57
21 Corolrios e Lemas 57
Perguntas para o estudo da teoria. 59
Exerccios 61
Referncias Bibliogrficas. 69
Anexos 70
2
1. INTRODUO LGICA
O termo lgica deriva-se do vocbulo grego logos, que significa idia,
palavra, razo ou regularidade. A Lgica como cincia estuda o conjunto de
regras que regem o processo de pensar e raciocinar. A Lgica uma cincia de ndole
matemtica e fortemente ligada Filosofia. Assim, podemos dizer que a lgica o ramo
da filosofia que cuida das regras do bem pensar, ou do pensar correto, sendo, portanto,
um instrumento do pensar. A aprendizagem da lgica no constitui um fim em si. Ela s
tem sentido enquanto meio de garantir que nosso pensamento proceda corretamente a
fim de chegar a conhecimentos verdadeiros. Podemos, ento, dizer que a lgica trata dos
argumentos, isto , das concluses a que chegamos atravs da apresentao de
evidncias que a sustentam.
Os argumentos formulados em uma linguagem natural, como o espanhol ou portugus,
so, muitas vezes, de difcil avaliao, principalmente por causa da ambigidade inerente s
linguagens naturais, e das construes s vezes vagas ou confusas dos termos. Em virtude
desses fatos, a partir dos trabalhos de George Boole, em meados do sculo XIX, foram sendo
utilizados cada vez mais smbolos de origem matemtica para expressar os enunciados e
raciocnios da Lgica. A Lgica apresentada dessa forma chamada Lgica Matemtica ou
Lgica Simblica, enquanto a Lgica baseada em linguagem natural chamada Lgica
Clssica. Na nossa disciplina no abordaremos a Lgica desde um ponto de vista geral,
vinculado Filosofia, mas a denominada Lgica Matemtica. O principal organizador
da lgica clssica foi o filsofo grego Aristteles (384 322 a.C.) em sua obra chamada
Organon que, em traduo livre, significa ferramenta, instrumento.
medida que a Lgica Simblica desenvolve sua prpria linguagem tcnica, vem se
tornando um instrumento cada vez mais poderoso para a anlise e a deduo dos argumentos. A
utilizao de uma simbologia matemtica ajuda a expor, com maior clareza, as estruturas
lgicas das proposies e dos argumentos, que podem no ficar suficientemente claras se
expressadas na linguagem natural.
Uma outra vantagem da utilizao de uma linguagem simblica para a Lgica a
possibilidade de utilizao de recursos computacionais no tratamento de enunciados e
argumentos; os computadores digitais se mostram bastante adequados manipulao de
smbolos, enquanto apresentam extrema dificuldade no tratamento de linguagem natural. Em
1965, um pesquisador chamado Robinson desenvolveu um procedimento computacional para a
deduo, chamado Resoluo, evidenciando as vantagens da utilizao de uma linguagem
simblica para a Lgica.
Pode o homem pensar corretamente sem conhecer as regras e leis exatas da
lgica? Tal vez alguns consigam, como certos msicos que tocam algum instrumento
sem conhecer a teoria musical, mas sua criao restringida. O estudo formal da Lgica
modela o pensamento desenvolvendo a preciso, exatido e ponderao na colocao
dos argumentos. Um matemtico profissional h de ter, sem dvidas, conhecimentos
bsicos de lgica. O pensamento lgico no congnito, pode e deve ser desenvolvido.
O estudo sistemtico da lgica uma das vias mais eficientes de desenvolvimento do
pensamento abstrato. A soluo de problemas lgicos um modo interessante de
conseguir este desenvolvimento.
A verdade e a Lgica so interdependentes. A Lgica ajuda a demonstrar os
juzos verdadeiros e refutar os falsos, ensina a pensar clara, concisa e corretamente. A
Lgica imprescindvel a todos os mais diversos profissionais. Os professores no
podero desenvolver de modo eficiente a mentalidade dos alunos sem dominar a
Lgica. Os juristas elaboram a acusao e defesa, e os mdicos diagnosticam uma
doena, segundo a Lgica. A Lgica ajuda os estudantes a assimilar a informao e ser
autodidatas, separando o fundamental do secundrio; a perceber de modo crtico os
conceitos tomados dos textos; a serem criativos.
3
Resulta totalmente desnecessrio enfatizar a importncia da Lgica para os
profissionais da Matemtica.
2. PROPOSIES
Introduziremos o importante conceito de proposio, pedra angular na
construo da Lgica Matemtica. Observe as oraes a seguir.
1. Duas retas perpendiculares a um plano so paralelas.
2. Duas retas contidas num mesmo plano so paralelas.
3. Voc me empresta cinco reais?
4. Oxal que o professor no ministre aulas durante quinze dias.
5. A virtude verde.
6. Que dia lindo!
7. O nmero natural a divisor do nmero natural b.
8. Agamenon engenheiro.
9. Saia da minha frente!
Destas oraes podemos dizer:
1. verdadeira.
2. falsa.
3. uma pergunta. No podemos atribuir-lhe valor de verdade: falsa ou
verdadeira.
4. Exprime um desejo de algum. Tambm no possvel atribuir-lhe valor de
verdade.
5. Carece de sentido e, portanto, no cabe se perguntar se verdadeira ou falsa.
6. Depende das circunstancias, da sensibilidade, do humor. No possvel
classific-la como verdadeira ou falsa.
7. Tem um sentido bem determinado, mas ser verdadeira ou falsa depende dos
valores de a e b.
8. Pode ser verdadeira ou falsa.
9. Exprime uma ordem. No faz sentido classific-la como verdadeira ou falsa.
Na linguagem natural (portugus, espanhol, etc.) as oraes ou sentenas
costumam-se classificar em declarativas, interrogativas, exclamativas e imperativas.
Nos exemplos acima temos que as oraes (1), (2), (4), (5), (7) e (8) so declarativas. A
nmero (3) interrogativa, a (6) exclamativa e a (9) imperativa.
Em Lgica Matemtica estudam-se as propriedades das oraes declarativas s
quais possvel atribuir um, e somente um, dos valores lgicos verdadeiro ou falso.
Tais oraes so chamadas de proposies. Das nove oraes apresentadas podemos
afirmar que so proposies as correspondentes aos nmeros (1), (2), (7) e (8). A
notao VL[p]=V (VL[p]=F) indica que o valor lgico da proposio p V (F).
A Lgica Matemtica se ocupa do estudo das formas de modificar ou combinar duas
ou mais proposies para obter novas proposies e das regras para elucidar se uma
proposio verdadeira ou falsa a partir do valor de verdade das proposies iniciais.
No compete Lgica Matemtica determinar se uma proposio em particular
verdadeira ou falsa. A tarefa prpria de algum sistema dedutivo particular, por
exemplo, a Geometria Euclidiana se ocupa das proposies (1) e (2); a Aritmtica da
4
nmero (7) e a nmero (8) podemos deixar para algum que conhea bem o Agamenon
(depois de definir sem ambigidades de qual Agamenon estamos falando).
A Lgica Matemtica adota dois axiomas ou regras bsicas:
1- Principio da no Contradio: Uma proposio no pode ser verdadeira e falsa
ao mesmo tempo
2- Princpio do Terceiro Excludo (Tertium non datur): Toda proposio ou
verdadeira ou falsa. No existe uma terceira possibilidade.
Ambos os princpios equivalem ao enunciado: dada uma proposio quaisquer, a
ela atribudo sempre um, e somente um, dos valores lgicos: verdadeiro (V) ou falso
(F).
Na Lgica Matemtica costuma-se representar as proposies por letras para indicar
a independncia do sentido intrnseco de cada proposio. Por exemplo, prprio da
Lgica este resultado: se p uma proposio verdadeira ento sua negao (no p)
uma proposio falsa e, reciprocamente, se p falsa ento (no p) uma proposio
verdadeira. Ou este outro: Se p verdadeira e p implica q, ento q verdadeira.
3. SENTENAS ABERTAS E FECHADAS
Uma frase na qual o sujeito uma constante, como Scrates humano, pode ser
verdadeira ou falsa, portanto uma proposio. Mas se o sujeito for uma varivel, como em ele
foi presidente do Brasil, ela no verdadeira nem falsa, dependendo de nome que assuma o
lugar do pronome. Uma frase como essa no , portanto, um enunciado.
Os enunciados so chamados sentenas fechadas, ou simplesmente, fechados, enquanto
que frases como x foi presidente do Brasil, y escreveu Os Lusadas e z viajou para os
Estados Unidos so chamadas sentenas abertas, ou, simplesmente, abertos.
Os abertos no so verdadeiros nem falsos; podemos dizer apenas que so satisfeitos para
certos valores das variveis, e no satisfeitos para outros. A substituio das variveis de um
aberto por constantes chama-se instanciao ou especificao; a instanciao transforma um
aberto em um enunciado, que, este sim, pode ser verdadeiro ou falso. As variveis que aparecem
numa sentena aberta so chamadas de variveis proposicionais.
So exemplos de sentenas abertas: 1) x mltiplo de y, 2) x+3>10, 3) Se x
sobrinho de y e z filho de y, ento, x e z so primos.
4. NOES DE LGEBRA PROPOSICIONAL. CONECTIVOS LGICOS.
O Clculo Proposicional, ou lgebra das Proposies, constitui a parte mais
elementar da Lgica Matemtica. Em geral, o Clculo Proposicional forma parte de
outros clculos e teorias lgicas, aos que serve de base. Sua simplicidade permite
estudar e simplificar muitos problemas da teoria lgica que posteriormente so
estendidos a outras partes de maior complexidade. O objeto do Clculo Proposicional
fundamentalmente o estudo das relaes que tm lugar entre as proposies num dado
discurso. A seguir apresentamos os denominados conectivos lgicos, uma das questes
bsicas do Clculo Proposicional.
Chamamos de conectivos a certas palavras ou frases que em Lgica so utilizadas
para criar proposies compostas a partir de outras proposies. Os conectivos usuais
so:
5
- A negao no, cujo smbolo ~.
- A conjuno e, cujo smbolo ..
- A disjuno ou cujo smbolo v.
- A disjuno excludente ou cujo smbolo v.
- O condicional se...,ento, cujo smbolo . Tambm pode ser .
- O bicondicional ...se, e somente se..., cujo smbolo , ou .
Na literatura so tambm utilizados outros smbolos, alm dos escritos acima, para
representar os conectivos lgicos: para a negao; - e & para a conjuno e
(ferradura) para a condicional.
Uma proposio simples quando no utiliza nenhum dos conectivos ., v, v,
,. Exemplos:
1. O nmero 5 impar.
2. O nmero 6 perfeito
1
.
3. t um nmero irracional.
4. O homem mortal.
5. O icosgono um polgono de 30 lados.
6. O galo pe ovos.
Denominam-se proposies compostas s proposies formadas (ou conectadas) por
duas ou mais proposies simples. Utilizamos os conectivos estudados para formar
proposies compostas. Exemplos:
1. Tales de Mileto foi um sbio e Barrabs um bandido.
2. Um nmero inteiro divisvel por 5 se, e somente se termina em zero ou cinco.
3. Todo inteiro par ou impar.
4. Se um quadriltero tem os lados paralelos dois a dois, ento um paralelogramo.
A seguir definimos os conectivos lgicos mediante as denominadas tabelas-verdade.
Negao
Dada qualquer proposio sempre podemos formar a sua negao. Por exemplo,
a negao de chove agora no chove agora. A maior parte das vezes, a correta
negao na lngua portuguesa exige o advrbio no, mas a negao pode tambm se
escrever usando algum adjetivo ou preposio. Por exemplo, a proposio alguma
reta corta o plano o pode ser negada nenhuma reta corta o plano o e apreende
com dificuldade pode ser negado como apreende sem dificuldade.
A definio da negao pode ser resumida na seguinte tabela-verdade:
p ~p
V F
F V
Conjuno
Eis um exemplo da conjuno de duas proposies:
p: O numero 2 primo; q: O nmero 2 par. A conjuno das proposies p e q,
denotada p.q : O nmero 2 primo e par. Neste exemplo p e q so verdadeiras e p.q
1
Um nmero inteiro perfeito quando igual soma de seus divisores prprios. Os divisores prprios de
6 so 1, 2 e 3. Como 6=1+2+3 ento, 6 perfeito.
6
tambm verdadeira. Se considerarmos a proposio w: O nmero 2 impar, a
conjuno p.w falsa.
Tem-se: A conjuno p.q de duas proposies p e q verdadeira unicamente
nos casos em que ambas as proposies p e q sejam verdadeiras. Se uma das
proposies p ou q (ou ambas) for falsa, ento a proposio composta p.q falsa. Na
tabela-verdade a seguir definimos a operao de conjuno de proposies:
p q p.q
V V V
V F F
F V F
F F F
Disjuno
Na linguagem natural a palavra ou tem dois sentidos. Exemplifiquemos:
Sejam as duas seguintes proposies compostas:
p: Edilberto policial militar ou matemtico
q: Rosa mineira ou goiana.
A proposio p est indicando que ao menos uma das proposies Edilberto
policial militar, Edilberto matemtico, podendo ser ambas verdadeiras: Edilberto
policial militar ou matemtico. Mas, a proposio Rosa mineira ou goiana est
afirmando que somente uma das proposies Rosa mineira e Rosa goiana
verdadeira, pois no possvel ocorrer que Rosa seja simultaneamente mineira e goiana.
Na proposio p diz-se que o ou inclusivo, j na proposio q, o ou
exclusivo. Logo, a proposio p a disjuno inclusiva ou simplesmente disjuno das
proposies simples Edilberto policial militar, Edilberto matemtico. Enquanto
que a proposio q a disjuno exclusiva das proposies simples Rosa mineira,
Rosa goiana. Tem-se:
A disjuno inclusiva (ou disjuno dbil) de duas proposies p e q a
proposio composta pvq, que se l: p ou q, e que falsa quando o valor lgico das
proposies p e q forem ambos falsos, e verdadeira nos demais casos, ou seja, quando
ao menos uma das proposies simples verdadeira. Quando dizemos simplesmente
disjuno entendemos a disjuno inclusiva.
A seguir a tabela-verdade da disjuno inclusiva:
p q pvq
V V V
V F V
F V V
F F F
A disjuno exclusiva (ou disjuno forte) de duas proposies p e q a
proposio composta pvq, que se l: ou p ou q ou p ou q, mas no ambos, que
falsa quando o valor lgico das proposies p e q forem ambos falsos ou ambos
verdadeiros, e verdadeira quando p e q tm valores lgicos diferentes. Em portugus
no existe uma palavra especfica para representar a disjuno exclusiva. Em latim, por
7
exemplo, vel significa ou inclusivo, e aut, ou exclusivo. A tabela-verdade que define a
disjuno exclusiva :
p q pvq
V V F
V F V
F V V
F F F
Condicional (se...,ento...).
Consideremos as proposies:
p: a mltiplo de 6.
q: a mltiplo de 3.
A proposio composta Se a mltiplo de 6, ento a mltiplo de 3 do tipo
chamado condicional. Na literatura matemtica, nos enunciados dos teoremas, aparece
freqentemente este tipo de sentena composta. A forma geral deste conetivo : Se p,
ento, q. Tambm se costuma escrever pq, ou pq. Esta ltima notao usada em
alguns livros para diferenciar o conectivo condicional da implicao lgica, presente
nos teoremas matemticos. Entre ambos existe uma relao estreita, mas so
conceitualmente diferentes.
Na proposio condicional se p, ento, q, a proposio p chamada de
antecedente ou implicante e a proposio q chamada de conseqente ou implicado.
A proposio pq pode ser lida ou expressada de qualquer uma das seguintes
formas:
p implica em q p, logo q p s se q q se p
se p ento q p condio suficiente para q p apenas se q q segue de p
p somente se q q condio necessria para p p s quando q
Na seguinte tabela-verdade definimos o conectivo condicional:
p q pq
V V V
V F F
F V V
F F V
fcil verificar numa tabela-verdade que as proposies pq e ~(p.~q) so
equivalentes, ou seja, ambas tm a mesma funo de verdade. Observando as duas
ltimas colunas da tabela a seguir comprovamos o fato.
p q ~q p.~q pq ~(p.~q)
V V F F V V
V F V V F F
F V F F V V
F F V F V V
8
Este conceito de implicao em Lgica diferente do sentido que tem a
implicao nos teoremas matemticos. Voltaremos sobre este assunto, mas deixamos
claro desde j que uma proposio composta condicional pq no afirma que o
conseqente q se deduz, ou se infere, do antecedente p. Unicamente permite, a partir de
duas proposies quaisquer p e q construir uma nova proposio denotada pq,
definida pela tabela-verdade mostrada.
Equivalncia (bicondicional; se, e somente se; ou )
A conjuno das sentenas pq e qp resulta na sentena pq. Assim,
(pq).(qp) equivale a pq. Prove esta afirmao numa tabela-verdade. A sentena
composta pq chamada de bicondicional e pode ser lida de qualquer uma das
seguintes maneiras:
p se, e somente se q;
p equivalente a q;
p condio necessria e suficiente para q;
Eis a tabela-verdade que define a proposio bicondicional:
p q pq
V V V
V F F
F V F
F F V
5. EQUIVALNCIA LGICA
Definio: Duas proposies P(p,q,...) e Q(p,q,...) so logicamente equivalentes (ou
apenas equivalentes), denotado P(p,q,...) Q(p,q,...), se e somente se suas tabelas-
verdade so idnticas. Em alguns livros se utiliza a notao P(p,q,...) Q(p,q,...) para
indicar a equivalncia.
Exemplo: As proposies ~pp e p so equivalentes.
Construmos a tabela-verdade de ambas as proposies:
p ~p ~pq
V F V
F V F
Observe que a primeira e terceira colunas so idnticas, logo ~pp p.
Exemplo: As proposies pq e a disjuno (p.q)v(~p.~q) so equivalentes.
p q ~p ~q pq p.q ~p.~q (p.q)v(~p.~q)
V V F F V V F V
V F F V F F F F
F V V F F F F F
F F V V V F V V
9
Teorema: A relao de equivalncia entre proposies uma relao de
equivalncia. Ou seja, tem-se que:
(i) Propriedade Reflexiva: Para toda proposio P(p,q,...), P(p,q,...) P(p,q,...).
(ii) Propriedade Simtrica: Se P(p,q,...) Q(p,q,...), ento Q(p,q,...) P(p,q,...).
(iii) Propriedade Transitiva: Se P(p,q,...) Q(p,q,...) e Q(p,q,...) R(p,q,...), ento
P(p,q,...)R(p,q,...).
A demonstrao deste teorema, que mostra que o uso da palavra equivalncia foi
apropriado, imediata.
6. TAUTOLOGIA, CONTRADIO E CONTINGNCIA
Denomina-se tautologia (proposio tautolgica ou proposio logicamente
verdadeira) proposio composta que sempre verdadeira. Na tabela-verdade de uma
proposio tautolgica, a ltima coluna ( direita) contm unicamente Vs (verdadeiros).
Exemplos de tautologias: 1) pv~p.
p ~p pv~p
V F V
F V V
2) pv~(p.q).
p q p.q ~(p.q) pv~(p.q)
V V V F V
V F F V V
F V F V V
F F F V V
Denomina-se contradio (proposio contravlida ou proposio logicamente
falsa) proposio composta que sempre falsa. Na tabela-verdade de uma contradio,
a ltima coluna ( direita) contm unicamente Fs (falsos).
Exemplos de contradies:
1) p.~p.
p ~p p.~p
V F F
F V F
2) p~p.
p ~p p~p
V F F
F V F
Denomina-se contingncia (proposio contingente ou proposio
indeterminada) a proposio composta que pode ser verdadeira ou falsa. Na tabela-
10
verdade de uma contingncia, a ltima coluna ( direita) contm Vs (verdadeiros) e Fs
(falsos).
Exemplos de contingncias:
1) p~p
p ~p p~p
V F F
F V V
2) pv(p.~q).
p q ~q p.~q pv( p.~q)
V V F F V
V F V V V
F V F F F
F F V F F
Tm-se os seguintes teoremas:
Teorema: P(p,q,...)Q(p,q,...) se e somente se a proposio P(p,q,...)Q(p,q,...)
uma tautologia.
Teorema: Se P(p,q,...) e Q(p,q,...) so ambas tautologias ou ambas contradies,
ento P(p,q,...)Q(p,q,...).
Corolrio: Se P(p,q,...)Q(p,q,...), ento P(p
1
,q
1
,...)Q(p
1
,q
1
,...) para quaisquer
proposies p
1
,q
1
,...
Nota: O corolrio estabelece que se em proposies equivalentes substituem-se as
variveis proposicionais por proposies, as proposies obtidas tambm so
equivalentes.
7. ORDEM DE PRECEDNCIA DAS OPERAES
Sabemos que com o auxlio dos conectivos podemos construir proposies compostas
mais elaboradas. Por exemplo, considere a seguinte proposio: Se o dficit persistir e a
arrecadao no aumentar, ento ou aumentamos os impostos ou haver inflao.
Simbolicamente podemos representar esta proposio p . ~ q r v s, onde: p= o dficit
persistir, q= a arrecadao aumentar, r= aumentamos os impostos e s= haver inflao.
A construo de expresses simblicas mais complexas pode apresentar alguns
problemas de interpretao duvidosa. Por exemplo, considere a expresso Se Mrio foi ao
cinema e Joo foi ao teatro, ento Marcelo ficou em casa. Sua transcrio em smbolos do
alfabeto da linguagem p.q r, onde: p= Mrio foi ao cinema, q= Joo foi ao teatro e r=
Marcelo ficou em casa. A proposio p.q r poderia indicar duas proposies distintas:
(a) Se Mrio foi ao cinema e Joo foi ao teatro, ento Marcelo ficou em casa, ou,
(b) Mrio foi ao cinema, e, se Joo foi ao teatro, ento Marcelo ficou em casa.
Para decidir qual proposio est sendo indicada, necessrio saber qual o conectivo que
atua primeiro, se o conectivo da conjuno ou da condicional. Por esse motivo necessrio
estabelecer uma hierarquia de operao dos conectivos. Tal hierarquia (ou ordem de
precedncia) a seguinte:
11
1. ~
2. . , v
3.
4.
Essa ordem de precedncia indica que a operao de negao a primeira a ser executada;
em seguida, as operaes de conjuno e disjuno na ordem em que estiverem dispostas;
depois deve ser executada a operao de condicionamento, e, por fim, a de bicondicionamento.
Em certas ocasies, essa ordenao no nica; por exemplo, p v q r v s, tanto podemos
executar primeiro a operao p v q e, em seguida a operao r v s, como ao contrrio; o
resultado seria o mesmo. Mas, para tornar o processo mais determinado, com uma nica
ordenao, podemos convencionar o seguinte algoritmo, para obter a ordem de execuo das
operaes:
Algoritmo Ordem de Precedncia
Passo 1. Percorra a expresso da esquerda para a direita, executando as operaes de
negao, na ordem em que aparecerem.
Passo 2. Percorra novamente a expresso, da esquerda para a direita, executando as operaes
de conjuno e disjuno, na ordem em que aparecerem.
Passo 3. Percorra outra vez a expresso, da esquerda para a direita, executando desta vez as
operaes de condicionamento, na ordem em que aparecerem.
Passo 4. Percorra uma ltima vez a expresso, da esquerda para a direita, executando as
operaes de bicondicionamento, na ordem em que aparecerem.
Dessa forma, as operaes da expresso p . ~ q r v s sero executadas na seguinte
ordem:
p . ~ q r v s
2 1 4 3
Um caso especial a utilizao de negaes consecutivas; por exemplo, a proposio
falso que eu no tenha sado pode ser simbolizada por ~ ~ p (onde p representa eu tenha
sado); nesse caso, a segunda negao deve ser executada antes.
Quando for necessrio modificar a ordem de precedncia, podemos utilizar os sinais
auxiliares (parnteses, colchetes e chaves). Assim, no exemplo dado, a expresso p . q r
significa se Mrio foi ao cinema e Joo foi ao teatro, ento Marcelo ficou em casa, e a
expresso p . (q r) significa Mrio foi ao cinema, e, se Joo foi ao teatro, ento Marcelo
ficou em casa.
A utilizao dos conectivos . e v pode causar ambigidade at mesmo em linguagem
natural; por exemplo, a expresso Mrio foi ao cinema e Marcelo ficou em casa ou Maria foi
praia representada por p . q v s, no deixa claro seu significado; tanto pode significar Mrio
foi ao cinema e Marcelo ficou em casa, ou ento Maria foi praia, representada por (p . q) v
s, como pode significar Mrio foi ao cinema e, ou Marcelo ficou em casa ou Maria foi praia,
representada por p . (q v s), que so claramente afirmaes distintas. Segundo a ordem de
precedncia definida, a expresso dada corresponde primeira forma apresentada, mas, para
evitar qualquer mal-entendido, aconselhamos a utilizar parnteses, nesses casos.
Utilizando parnteses e conectivos, as expresses simblicas podem assumir aspectos
ainda mais complexos, como, por exemplo,
(p q v (~ r s)) . ~ t
12
Para determinar a ordem de execuo das operaes no caso em que a expresso possui
parnteses, podemos utilizar o algoritmo abaixo:
Algoritmo Ordem de Precedncia com Parnteses
Passo 1. Percorra a expresso de esquerda a direita at encontrar o primeiro ).
Passo 2. Volte at encontrar o ( correspondente, delimitando assim um trecho da expresso
sem parnteses.
Passo 3. Execute o Algoritmo Ordem de Precedncia sobre a expresso delimitada.
Passo 4. Elimine o par de parnteses encontrado.
Passo 5. Volte ao Passo 1.
De acordo com esse algoritmo, as operaes da expresso anterior seriam executadas na ordem:
(p q v (~ r s)) . ~ t
4 3 1 2 6 5
8. LEIS DA LGEBRA PROPOSICIONAL
As principais leis da lgebra Proposicional so enunciadas no teorema a seguir.
Teorema: Se A, B e C so proposies, tem-se as seguintes propriedades:
1) ~ ~ A A (Lei da Dupla Negao).
2) A . B B . A (Lei da Comutatividade da Conjuno)
3) A v B B v A (Lei da Comutatividade da Disjuno)
4) (A . B) . C A . (B . C) (Lei da Associatividade da Conjuno)
5) (A v B) v C A v (B v C) (Lei da Associatividade da Disjuno)
6) A . (B v C) (A . B) v (A . C) (Primeira Lei de Distributividade)
7) A v (B . C) (A v B) . (A v C) (Segunda Lei de Distributividade)
8) ~ (A . B) ~A v ~B (Primeira Lei de De Morgan)
9) ~ (A v B) ~A . ~B (Segunda Lei de De Morgan)
10) A . A A (Lei da Idempotncia da Conjuno)
11) A v A A (Lei da Idempotncia da Disjuno)
Outras propriedades importantes so:
12) Lei da Condicional: A B ~ A v B
13) Lei da Bicondicional:
A B (A B) . (B A)
A B (A . B) v (~ A . ~ B)
14) Lei da Contraposio: A B ~ B ~ A
15) Lei da Absoro: A A . B A B
16) Lei de Clavius: ~ A A A
17) Lei da Refutao por Absurdo: (A B) . (A ~ B) ~ A
18) Lei do Dilema: (A B) . (~A B) B
19) Lei da Demonstrao por Absurdo (onde F uma contradio):
A . ~ B F A B
20) Lei de Exportao Importao: A (B C) A . B C
21) Lei da no Contradio: ~(A.~A) V
22) Lei do Tero Excluso: Av~A V
13
23) Lei da Identidade para a implicao: AA V
24) Lei da Identidade da Equivalncia: AA V
Embora evidentes, tambm registramos as propriedades:
(25) AvV V; (26) A. V A; (27) AvF A; (28) A.~A F.
Todas as propriedades podem ser demonstradas utilizando as tabelas-verdade.
Deixamos esta tarefa ao aluno.
9. PRINCIPIO DE DUALIDADE
Definio: Seja P uma proposio que s contem os conectivos ~, . e v. Chama-se
dual de P proposio obtida de P trocando cada smbolo v por ., e cada smbolo . por
v.
Exemplo: A dual de ~((p.q)v~r) ~((pvq).~r). Observe que cada uma dual
da outra.
Teorema: Se P e Q so proposies equivalentes que s contm conectivos ~, . e
v, ento as suas duais respectivas P e Q so tambm equivalentes.
Por exemplo, p.(pvq) p, a dual de p.(pvq) pv(p.q), a dual de p p, logo
pv(p.q) p.
10. IMPLICAO LGICA.
DEFINIO DE IMPLICAO LGICA (OU INFERNCIA LGICA)
Definio: Uma proposio P implica logicamente (ou apenas implica) uma
proposio Q, se Q verdadeira (V) todas as vezes que P verdadeira (V). A proposio
P chamada antecedente, e Q, conseqente da implicao.
A notao P Q indica que P implica Q.
Da definio decorre imediatamente que P Q, se e somente se, o conseqente Q
assumir o valor lgico V, sempre que o antecedente P assumir esse valor.
Se P Q, tambm se costuma dizer que a proposio Q se infere
2
da
proposio P. Os termos implicao lgica e inferncia lgica so sinnimos.
Uma definio equivalente de implicao ou inferncia lgica a seguinte:
P Q se e somente se P Q uma tautologia. Isto significa que na tabela-verdade de P
Q no acontece que numa mesma linha P V e Q F, ou seja, nunca ocorre que
simultaneamente P verdadeira e Q falsa.
2
Segundo o Dicionrio Houaiss, inferncia termo da lgica que significa operao intelectual por meio
da qual se afirma a verdade de uma proposio em decorrncia de sua ligao com outras j
reconhecidas como verdadeiras.
14
As regras de inferncia so, na verdade, formas vlidas de raciocnio, isto , so formas
que nos permitem concluir o conseqente, uma vez que consideremos o antecedente verdadeiro;
em termos textuais, costumamos utilizar o termo logo (ou seus sinnimos: portanto, em
conseqncia, etc.) para caracterizar as Regras de Inferncia; a expresso P Q pode ento ser
lida: P; logo, Q.
Exemplo: Consideremos as proposies p.q, pvq, pq. Suas tabelas-verdade
so:
p q p.q pvq pq
V V V V V
V F F V F
F V F V F
F F F F V
A proposio p.q verdadeira s na primeira linha e, nesta linha, as proposies
pvq e pq tambm so verdadeiras. Portanto, temos as implicaes ou regras de
inferncia lgica: p.q pvq, p.q pq.
11. DEDUO NO CLCULO PROPOSICIONAL
11.1 ARGUMENTOS
Definio: Chama-se argumento toda a afirmao de que uma dada seqncia
finita P
1
, P
2
,..., P
n
(n>1) de proposies tem como conseqncia, ou acarreta, uma
proposio final Q.
As proposies P
1
, P
2
,..., P
n
dizem-se as premissas do argumento e a proposio
final Q diz-se a concluso do argumento.
Um argumento de premissas P
1
, P
2
,..., P
n
e de concluso Q denota-se por:
P
1
, P
2
,..., P
n
Q
e se l de uma das seguintes maneiras:
- P
1
, P
2
,..., P
n
acarretam Q
- Q decorre de P
1
, P
2
,..., P
n
- Q se deduz de P
1
, P
2
,..., P
n
- Q se infere de P
1
, P
2
,..., P
n
O smbolo (em alguns textos se utiliza o smbolo ,) chamado de trao de
assero. O argumento tambm pode ser indicado (forma padronizada) por:
P
1
P
2
.
.
.
P
n
_____
Q
15
Tambm se utiliza o smbolo de implicao lgica para denotar os argumentos:
P
1
. P
2
..... P
n
Q
Definio: Um argumento que consiste em duas premissas e uma concluso chama-
se silogismo.
Exemplo (1) de argumento (Trata-se de um silogismo):
Hoje sbado ou domingo. Hoje no sbado. Logo hoje domingo.
O mesmo argumento na forma padronizada:
Hoje sbado ou domingo
Hoje no sbado_______
Hoje domingo
Simbolicamente: Sejam as proposies p: Hoje sbado; q: Hoje domingo. O
argumento fica representado assim:
p v q
~p
q
Definio: Um argumento P
1
, P
2
,..., P
n
Q diz-se vlido se e somente se a
concluso Q verdadeira todas as vezes que as premissas P
1
, P
2
,..., P
n
so verdadeiras.
Um argumento no vlido diz-se um sofisma.
Todo argumento vlido goza da seguinte propriedade caracterstica: A verdade
das premissas incompatvel com a falsidade da concluso.
A todo argumento vlido (correto, legtimo) podemos atribuir o valor V e a todo
sofisma atribumos o valor F.
Em termos lgicos, se um argumento vlido, ento a condicional que o
representa sempre verdadeira, independentemente dos valores lgicos das proposies
componentes. Em outras palavras, se um argumento vlido, a condicional que o
representa uma tautologia.
A lgica se preocupa com a validade dos argumentos e no com o fato de serem
verdadeiras ou falsas as premissas e as concluses. A validade de um argumento
depende exclusivamente da relao existente entre as premissas e a concluso. Portanto,
afirmar que um dado argumento vlido significa afirmar que as premissas esto de tal
modo relacionadas com a concluso que impossvel ter a concluso falsa se as
premissas so verdadeiras.
11.2 CRITERIO DE VALIDADE DE UM ARGUMENTO
Teorema: Um argumento P
1
, P
2
,..., P
n
Q vlido se e somente se a
condicional P
1
. P
2
. ... . P
n
Q uma tautologia.
Demonstrao: Por definio, o argumento P
1
, P
2
,..., P
n
Q vlido se e
somente se Q verdadeira todas as vezes que as premissas P
1
, P
2
,..., P
n
so verdadeiras.
As premissas P
1
, P
2
,..., P
n
so todas verdadeiras se e somente se a proposio P
1
. P
2
.
16
... . P
n
verdadeira. Logo, P
1
, P
2
,..., P
n
Q vlido se e somente se Q verdadeira
quando P
1
. P
2
. ... . P
n
verdadeira. Mas, Q verdadeira quando P
1
. P
2
. ... . P
n
verdadeira, equivale a que P
1
. P
2
. ... . P
n
implica logicamente a Q. Isto significa que
o argumento P
1
, P
2
,..., P
n
Q vlido se e somente se P
1
, P
2
,..., P
n
Q, ou seja, se e
somente se P
1
, P
2
,..., P
n
Q tautolgica.
Em virtude do teorema acima, podemos associar a um argumento qualquer P
1
,
P
2
,..., P
n
Q a implicao lgica P
1
. P
2
. ... . P
n
Q (ou a condicional P
1
. P
2
. ... .
P
n
Q). Reciprocamente, a toda implicao lgica P
1
. P
2
. ... . P
n
Q corresponde
o argumento P
1
, P
2
,..., P
n
Q. Costuma-se dizer que P
1
. P
2
. ... . P
n
Q a
condicional associada ao argumento dado.
Observao: Se o argumento P
1
(p, q, r,...), P
2
(p, q, r,...),..., P
n
(p, q, r,...) Q(p, q, r,...)
vlido, ento o argumento da mesma forma P
1
(P, Q, R,...), P
2
(P, Q, R,...),..., P
n
(P, Q,
R,...) Q(P, Q, R,...) tambm vlido, quaisquer sejam as proposies R, S, T,...
Por exemplo, do argumento vlido p p v q (1) segue-se a validade dos
argumentos: (~p.r) (~p.r) v (~sr) e (p r v s) (p r v s) v (~r. s), pois,
ambos tm a mesma forma de (1).
Portanto, a validade ou no-validade de um argumento depende apenas da sua
forma e no de seu contedo ou da verdade ou falsidade das proposies que o
integram. Argumentos diversos podem ter a mesma forma, e como a forma que
determina a validade, lcito falar da validade de determinada forma ao invs de falar
da validade de determinado argumento. E afirmar que uma determinada forma vlida
equivale a asseverar que no existe argumento algum dessa forma com premissas
verdadeiras e uma concluso falsa, isto , todo argumento de forma vlida um
argumento vlido. Vice-versa, dizer que um argumento vlido equivale a dizer que
tem forma vlida.
Quais mtodos podem se utilizar para provar que um argumento vlido?
A Tabela Verdade o mtodo mais imediato para verificar se uma forma
simblica ou no uma tautologia, e pode ser utilizado para determinar a validade ou
invalidade de um argumento. Vejamos dois exemplos:
Exemplo 2: Consideremos o argumento se eu tiver dinheiro, vou ao cinema ou
ao teatro; mas eu no tenho dinheiro. Logo, ou no vou ao cinema ou no vou ao
teatro.
Sejam as proposies: p: eu tiver dinheiro; q: vou ao cinema; r: vou ao teatro.
O argumento, representado simbolicamente, :
p q v r, ~ p ~ q v ~ r
Construmos a tabela-verdade:
1 2 3 4 5 6 7 8 9
17
p q r q v r pq v r ~p ~q ~r ~q v ~r
1 V V V V V F F F F
2 V V F V V F F V V
3 V F V V V F V F V
4 V F F F F F V V V
5 F V V V V V F F F
6 F V F V V V F V V
7 F F V V V V V F V
8 F F F F V V V V V
As colunas (5) e (6) correspondem s premissas do argumento e a coluna (9)
concluso. Nas linhas (5), (6), (7) e (8) todas as premissas do argumento so
verdadeiras. Para que o argumento fosse vlido preciso que nessas linhas o valor de
verdade de Q fosse V, para, assim, a condicional ser uma tautologia. Mas acontece que
na linha (5) F. Portanto, a expresso no uma tautologia, e, consequentemente, o
argumento no vlido.
Exemplo 3: O argumento se eu estudar, fico cansado; se eu ficar cansado, durmo.
Logo, se eu estudar, durmo, por sua vez pode ser representado por:
(p q) , (q r) (p r)
onde: p: eu estudar; q: eu ficar cansado; r: eu dormir.
Construmos a tabela-verdade:
1 2 3 4 5 6
p q r p q q r p r
1 V V V V V V
2 V V F V F F
3 V F V F V V
4 V F F F V F
5 F V V V V V
6 F V F V F V
7 F F V V V V
8 F F F V V V
As colunas das premissas so as correspondentes aos nmeros (4) e (5) e a da
concluso a nmero (6). Observemos que toda vez que todas as premissas so
verdadeiras, tem-se que a concluso tambm verdadeira. Logo, a condicional uma
tautologia, e, portanto, o argumento vlido.
A tabela-verdade acima prova, com toda generalidade, o argumento da
transitividade da condicional: (p q) . (q r) (p r), que doravante
utilizaremos como um argumento vlido.
11.3 ARGUMENTOS DEDUTIVOS E INDUTIVOS
Existem, em Lgica, dois tipos de argumentos, dedutivos e indutivos. Ambos
constituem as duas ferramentas principais que podem ser utilizadas pelo pensamento na
busca de novos conhecimentos: a deduo e a induo, que do origem a dois tipos de
argumentos, dedutivos e indutivos. Os argumentos apresentados nos exemplos (1) e (3)
18
so exemplos de argumentos dedutivos vlidos. O argumento do exemplo (2) um
argumento dedutivo invlido. A matemtica utiliza na estruturao das teorias os
argumentos dedutivos, pois eles asseguram a certeza, nos teoremas, da relao de
inferncia Hiptese Tese. Da que o mtodo cientfico da matemtica chamado
mtodo hipottico-dedutivo.
Os argumentos indutivos, por outro lado, no pretendem que suas premissas
forneam provas cabais da veracidade da concluso, mas apenas que forneam
indicaes dessa veracidade. Veja um exemplo de argumento indutivo:
Joguei uma pedra no lago, e a pedra afundou;
Joguei outra pedra no lago e ela tambm afundou;
Joguei mais uma pedra no lago, e tambm esta afundou;
Logo, se eu jogar uma outra pedra no lago, ela vai afundar.
Os termos vlidos e invlidos no se aplicam aos argumentos indutivos; eles
costumam ser avaliados de acordo com a maior ou menor possibilidade com que suas
concluses sejam estabelecidas.
Costuma-se dizer que os argumentos indutivos partem do particular para o geral,
isto , a partir de observaes particulares, procura estabelecer regras gerais, que, no
caso das cincias naturais, devem ser provadas por outros meios; os argumentos
dedutivos, por seu lado, partem de regras gerais para estabelecer a veracidade de
acontecimentos particulares. O desenvolvimento da cincia tem dependido, em grande
parte, da habilidade em combinar os dois tipos de raciocnio. Em matemtica um
razoamento indutivo permite gerar uma conjetura, ou seja, permite suspeitar que um
enunciado possa ser efetivamente um teorema, mas at que no exista uma prova
dedutiva do enunciado no pode ser admitido como tal. Um exemplo recente foi a prova
do denominado ltimo Teorema de Fermat.
Exemplos de aplicao do Mtodo Dedutivo
At agora temos utilizado o mtodo das tabelas-verdade para demonstrar
implicaes e equivalncias. Existe um mtodo mais eficiente, denominado Mtodo
Dedutivo, para realizar esta tarefa. Exemplificamos o mtodo nos seguintes exemplos:
Exemplo 1: Demonstrar que p.qp (Regra de Simplificao).
Demonstrao: p.qp ~(p.q) v p (~p v~q) v q ~p v (~q v q) ~p v T T
Observao: T representa uma tautologia. Poderamos escrever, com o mesmo sentido,
~p v (~q v q) ~p v V V.
Exemplo 2: Demonstrar que p pvq (Adio)
Demonstrao: p pvq ~p v (pvq) (~p v p) vq Tvq T.
Exemplo 3: Provar que (pq) . (p~q) ~p
Demonstrao: (pq) . (p~q) ~ p (~pvq) . (~pv~q) ~p v (q . ~q) ~pv F
~p..
12. REGRAS DE INFERNCIA
19
A seguir enunciamos um conjunto de argumentos vlidos bsicos que so usados
para fazer inferncias, isto , executar os passos de uma deduo ou demonstrao.
Alguns j so conhecidos, mas oferecemos a lista a modo de resumo das ferramentas
bsicas disponveis para as demonstraes. Cada uma delas pode ser provada, bastando
para isso construir a tabela-verdade da condicional correspondente; se a condicional for
tautolgica, ser uma inferncia. Em cada uma das regras mostramos as trs notaes
usuais para apresent-la e um exemplo.
1. Regra da Adio: (1) p p v q; (2) p , p v q; (3) p __ ;
p v q
Exemplo: Vou ao cinema; logo vou ao cinema ou ao teatro.
2. Regra da Simplificao: (1) p . q p; (2) p . q , p; (3) p . q ;
p
Exemplo: Fui ao cinema e ao teatro; logo fui ao cinema.
3. Regra da Conjuno: (1) p, q p . q; (2) p,q , p . q; (3) p
q___
p . q
Exemplo: Fui ao cinema, fui ao teatro; logo fui ao cinema e ao teatro.
4. Regra da Absoro: (1) p q p (p . q); (2) p q , p (p . q);
(3) p q____
p (p . q)
Exemplo: Se trabalho, ganho dinheiro; logo, se trabalho, trabalho e ganho dinheiro
5. Regra do Modus Ponens: (1) (p q) . p q; (2) (p q) , p , q; (3) p q
p____
q
Exemplo: Se ganhar na Loteria, fico rico; ganhei na Loteria; logo, fiquei rico.
6. Regra do Modus Tollens: (1) (p q) . ~ q ~ p; (2) (p q) , ~ q , ~ p;
(3) p q
~q___
~p
Exemplo: Se ganhar na Loteria, fico rico; no fiquei rico; logo no ganhei na Loteria
7. Regra do Silogismo Disjuntivo (ou Alternativo): (1) (p v q) . ~ p q;
(2) (p v q) , ~ p , q; (3) p v q
~p___
q
Exemplo: Ou trabalho ou estudo; no trabalho; logo, estudo
20
8. Regra do Silogismo Hipottico (ou Condicional): (1) (p q) . (q r) p r;
(2) (p q) , (q r) , p r; (3) p q
q r
p r
Exemplo: Se trabalho, ganho dinheiro, e, se ganho dinheiro, vou viajar; logo, se
trabalho, vou viajar.
9. Regra do Dilema Construtivo: (1) (p q) . (r s) . (p v r) q v s;
(2) (p q) , (r s) , (p v r) , q v s; (3) p q
r s
p v r__
q v s
Exemplo: Se vou festa, fico cansado; se vejo televiso, durmo; ou vou festa ou fico
vendo televiso; logo, ou fico cansado ou durmo.
10. Regra do Dilema Destrutivo: (1) (p q) . (r s) . (~ q v ~ s) ~ p v ~ r;
(2) (p q) , (r s) , (~ q v ~ s) , ~ p v ~ r;
(3) p q
r s
~ q v ~ s_
~ p v ~ r
Exemplo: Se vou festa, fico cansado; se vejo televiso, durmo; ou no fico cansado
ou no vou dormir; logo, ou no vou festa ou no vejo televiso
11. Regra da Simplificao Disjuntiva: (1) (p v q) . (p v ~ q) p; (p v q) , (p v ~ q)
, p;
(3) p v q
p v ~q
p
Exemplo: Ou estudo ou trabalho; ou estudo ou no trabalho; logo, estudo
12. Regra do Silogismo Conjuntivo (ou Incompatibilidade): (1) ~ (p . q) . q ~ p;
(2) ~ (p . q) , q , ~ p; (3) ~ (p . q)
_q_____
~p
Exemplo: falso que eu estudo e trabalho; eu trabalho; logo, no estudo
13. Regra da Atenuao: (1) p q p q v r; (2) p q , p q v r;
(3) p q___
p q v r;
Exemplo: Se eu ganhar na Loteria, fico rico; logo, se eu ganhar na Loteria, fico rico ou
tomo um sorvete.
Com auxilio destas regras pode-se demonstrar a validade de um grande nmero
de argumentos mais complexos. Como j indicamos, estas regras de inferncia podem
21
ser provadas utilizando as tabelas-verdade. Vamos exemplificar com a demonstrao da
regra de inferncia conhecida por Modus Ponens: (p q) . p q
1 2 3 4 5
p q p q (p q) . p (p q) . p q
1 V V V V V
2 V F F F V
3 F V V F V
4 F F V F V
As premissas so P
1
: (p q) e P
2
: p. A concluso Q: q. Observemos que as
premissas esto nas colunas (1) e (3) e a concluso na coluna (2). A linha (1) a nica
da tabela onde ambas as premissas so verdadeiras. A concluso tambm verdadeira
nessa linha, logo est provado o argumento.
Deixamos como exerccio a prova das restantes regras de inferncia.
Voltando resposta da pergunta: Quais mtodos podem se utilizar para
provar que um argumento vlido? Como vimos, ento, o mtodo das tabelas-
verdade pode ser utilizado para mostrar que um argumento vlido ou invlido. No
entanto, esse mtodo apresenta dois srios inconvenientes; em primeiro lugar, o nmero
de linhas cresce muito rapidamente, medida que aumenta o nmero de proposies
simples envolvidas no argumento; com 10 proposies a tabela necessita de 1024
linhas, e com 11, o numero de linhas vai a 2048. Com mais umas poucas proposies,
sua construo se torna impraticvel.
A segunda restrio ainda pior; no Clculo de Predicados, que veremos a
seguir, muitas vezes no existe um procedimento que permita estabelecer o valor lgico
de uma dada afirmao, o que torna impossvel a construo da tabela-verdade.
Para provar os argumentos tambm podemos utilizar o mtodo dedutivo, que j
foi apresentado. Mostramos, a seguir, um primeiro exemplo de aplicao desta tcnica.
Exemplo: Considere o argumento (Apostila Pinho):
Se Jos pegou as jias ou a Sra. Krasov mentiu, ento ocorreu um crime; se
ocorreu um crime ento o Sr. Krasov estava na cidade. Mas o Sr. Krasov no estava na
cidade; portanto, ou Jos no pegou as jias ou a Sra. Krasov no mentiu.
a) Enuncie as proposies que aparecem no argumento e escreva-o simbolicamente nas
trs formas possveis:
b) Analise se um argumento vlido.
Soluo:
Sejam as proposies:
p: Jos pegou as jias; q: a Sra. Krasov mentiu; r: ocorreu um crime; s: o Sr. Krasov
estava na cidade.
Em forma simblica o argumento se escreve:
p v q r, r s, ~s , ~ p v ~ q (ou p v q r, r s, ~s ~ p v ~ q)
Provemos, dedutivamente, que o argumento vlido:
r s, ~s , ~r (Modus Tollens)
p v q r, ~r , ~ (p v q) (Modus Tollens)
~ (p v q) ~p . ~q ( Lei de De Morgan)
~p . ~q ~p v ~q (P . Q P v Q uma tautologia)
22
Logo, p v q r, r s, ~s , ~ p v ~ q.
Tomando o exemplo acima como introdutrio, vamos a explicitar com maior
detalhe como proceder para provar dedutivamente um dado argumento.
Dado um argumento P
1
. P
2
. ... . P
n
Q chama-se demonstrao ou
deduo de Q a partir das premissas P
1
,..., P
n
, a seqncia finita de proposies X
1
,
X
2
,... X
k
, tal que cada X
i
ou uma premissa ou decorre logicamente de proposies
anteriores da seqncia, e de tal modo que a ltima proposio X
k
seja a concluso Q do
argumento dado.
Cada proposio X
i
que inclumos na seqncia deve decorrer logicamente das
anteriores; isso significa que deve ser obtida atravs da atuao de equivalncias ou
inferncias sobre uma proposio ou uma conjuno de proposies anteriores.
Se for possvel obter a concluso Q atravs do procedimento de deduo, o
argumento vlido; caso contrrio, no vlido.
O processo de deduo consiste basicamente dos seguintes passos:
Dado um argumento P
1
. P
2
. ... . P
n
Q fazemos:
- Definimos o conjunto P constitudo pelas premissas {P
1
, P
2
, ..., P
n
};
- Sobre um ou mais elementos do conjunto fazemos atuar equivalncias e inferncias
conhecidas, obtendo novas proposies, e incluindo-as no conjunto P;
- Repetimos o passo acima at que a proposio includa seja o conseqente Q.
Vamos exemplificar o processo provando o argumento (p q) . p q, a
conhecida regra de inferncia Modus Ponens, que j provamos aplicando o mtodo da
tabela-verdade.
Enumerando as proposies do conjunto P (premissas), temos:
(1) p q
(2) p
Como sabemos que p q equivalente a ~p v q (Lei da Condicional), inclumos em P
a proposio:
(3) ~p v q
A conjuno das expresses (2) e (3) produz a expresso
(4) p . (~p v q)
tambm includa em P. Utilizando a Lei de Distributividade nesta expresso obtemos
(5) ( p . ~ p ) v ( p . q )
Mas p .~p equivalente a F, uma contradio, e F v (p . q ) equivalente a p . q;
logo, podemos incluir em P a expresso
(6) p . q
Finalmente, pela Regra da Simplificao, p . q q, o que nos permite incluir em P a
expresso
(7) q
o que completa a demonstrao.
23
Por uma questo de organizao, podemos adotar uma forma de apresentao para as
dedues. Essa forma est exemplificada na tabela abaixo, na qual repetimos a deduo
de Modus Ponens, que acabamos de apresentar:
Passo Como a proposio foi obtida Proposio
1 Premissa p q
2 Premissa p
3 Lei da Condicional sobre (1) ~ p v q
4 Conjuno de (2) e (3) p . (~p v q)
5 Lei da Distributividade sobre (4) ( p . ~p ) v ( p . q )
6 Definio de contradio em (5) F v (p . q)
7 Definio de disjuno em (6) p . q
8 Regra da Simplificao sobre (7) q
Observe que a deduo apresentada sob forma de tabela, com trs colunas, da seguinte
forma:
coluna 1 - Os passos dados na deduo; a cada passo obtemos uma proposio,
referenciada no restante da deduo por esse nmero; os primeiros passos
so, naturalmente, o estabelecimento das premissas;
coluna 2 - Indicao de como foi obtida a proposio naquele passo; normalmente
as proposies so obtidas fazendose atuar equivalncias, regras de
inferncia ou outras propriedades sobre premissas j obtidas em passos
anteriores;
coluna 3 - A proposio obtida naquele passo; a ltima deve ser a concluso do
argumento.
Podemos ver, ento, que os mtodos dedutivos operam de forma distinta do
mtodo da Tabela Verdade; para demonstrar a regra de inferncia Modus Ponens
tivemos que utilizar vrias equivalncias e regras de inferncia sobre proposies
obtidas em passos anteriores; por esse motivo, a utilizao do mtodo direto de
deduo, exige que saibamos, de forma bem clara, quais as equivalncias e implicaes
lgicas que podem ser utilizadas.
Formalmente, o mtodo de deduo que apresentamos suficiente para obter a
concluso de qualquer argumento vlido; no entanto, muitas vezes, quando a concluso
uma proposio composta, envolvendo uma ou mais operaes lgicas, a deduo
torna-se mais difcil. Nesses casos, costuma-se simplificar a concluso, de forma a
facilitar a deduo. Damos, a seguir, algumas orientaes e exemplos para ilustrar esta
idia. Separamos os casos em funo da forma da concluso.
CONCLUSO DA FORMA p . q
Quando a concluso uma conjuno, devemos obter, independentemente, as parcelas p
e q, e a seguir, obter p . q. Nos baseamos no argumento p, q p . q [CPNJ].
Exemplo:
Se a procura do produto aumentar, seu preo subir; se o preo subir, o produto no ser
exportado; se no houver importao ou se o produto for exportado, o produto
24
escassear. A procura do produto aumentou e no haver importao. Logo, o produto
no ser exportado e escassear.
Fazendo: p: a procura aumentar
q: o preo subir
r: o produto ser exportado
s: haver importao
t: o produto escassear,
escrevemos o argumento na forma simblica:
p q, q ~ r, ~ sv r t, p . ~s , ~r . t
Procedemos demonstrao por deduo utilizando a tabela:
1 premissa 1 p q
2 premissa 2 q ~ r
3 premissa 3 ~ s v r t
4 premissa 4 p . ~s
5 4, SIMP p
6 1, 2, SH p ~ r
7 5, 6, MP ~ r
8 4, SIMP ~ s
9 8, AD ~ s v r
10 3, 9, MP t
11 7, 10, CONJ ~r . t
CONCLUSO DA FORMA q r
Suponha que o argumento tenha a forma P (q r), onde P a conjuno de
premissas. Ora, sabemos que, por EI,
p . q r p (q r)
o que permite escrever o argumento dado na forma
P . q r
Portanto, para deduzirmos um argumento cuja concluso da forma q r, inclumos q
no conjunto de premissas, e procuramos deduzir r. Este artifcio conhecido como
Deduo da Condicional.
Exemplo:
Se a casa ficar vazia ou eu conseguir o emprstimo ento pago a dvida e me mudo. Se
eu me mudar ou Pedro ficar em So Paulo ento volto a estudar. Logo, se a casa ficar
vazia, volto a estudar.
Fazendo p: a casa ficar vazia
q: eu conseguir o emprstimo
r: eu pagar a dvida
25
s: me mudar
t: Pedro ficar em So Paulo
u: voltar a estudar
temos o argumento p v q r . s, s v t u , p u
Utilizando Deduo da Condicional, incluo p nas premissas e a concluso se reduz a
u:
p v q r . s, s v t u, p , u
1 premissa 1 p v q r . s
2 premissa 2 s v t u
3 premissa 3 p
4 3, AD p v q
5 4, 1, MP r . s
6 5, SIMP s
7 6, AD s v t
8 7, 2, MP u
CONCLUSO DA FORMA p v q
Sabemos, por COND, que p v q ~ p q. Portanto, se a concluso do argumento tem
a forma pvq, podemos substitu-la por ~p q, e, utilizando Deduo da Condicional,
incluir ~p nas premissas e deduzir q.
Exemplo:
Ou pagamos a dvida ou o dficit aumenta; se as exportaes crescerem, o dficit no
aumenta. Logo, ou pagamos a dvida ou as exportaes no crescem.
Fazendo p: pagar a dvida
q: o dficit aumentar
r: as exportaes crescerem
temos o argumento p v q, r ~q , p v ~r
Como a concluso pv~ r equivalente a ~p r; ento, pela Deduo da Condicional, o
argumento assume a forma abaixo, com a deduo a seguir: p v q, r ~ q, ~ p , ~ r
1 premissa 1 p v q
2 premissa 2 r ~ q
3 premissa 3 ~ p
4 1, 3, SD q
5 2, 4, MT ~ r
Uma outra forma de deduzir uma disjuno obter um dos disjuntos, e, por adio,
incluir o outro.
26
Exemplo:
Considere o argumento, j na forma simblica:
(~ p v q) . ( r s), ~ q, , ~ p v s
Como a concluso ~ p v s, podemos deduzir ~ p, e, por adio, ~p v s, ou deduzir s, e,
por adio, ~ p v s.
1 premissa 1 (~p v q) . ( r s)
2 premissa 2 ~q
3 1, SIMP ~ p v q
4 2, 3, SD ~ p
5 4, AD ~ p v s
CONCLUSO DA FORMA p q
Sabemos, por BICOND, que p q (p q) . (q p). Ento, se a concluso
tem a forma p q, podemos substitu-la por (p q) . (q p), o que indica que temos
que deduzir, independentemente, p q e q p. Utilizando Deduo da Condicional,
podemos, na deduo de p q, incluir ~ p nas premissas e deduzir q, e, na deduo de
q p, incluir ~ q nas premissas e deduzir p.
Exemplo: Considere o argumento: p . q r, r v q ~ p v s, s q, p , r s
Temos ento que fazer duas dedues, uma para r s, para a qual inclumos r
nas premissas e deduzimos s, e outra para s r, na qual inclumos s nas premissas e
deduzimos r. As duas dedues devem ser realizadas em separado, pois os resultados
intermedirios de uma no podem ser utilizados na outra.
1 premissa 1 p . q r
2 premissa 2 r v q ~ p v s
3 premissa 3 s q
4 premissa 4 p
5 premissa 5 r
6 5, AD r v q
7 2, 6, MP ~ p v s
8 4, 7, SD s
Alternativamente, poderamos, na deduo da bicondicional, utilizar a outra
equivalncia BICOND,
p q (p . q) v (~ p . ~ q)
Nesse caso, bastaria deduzir p . q, ou deduzir ~ p . ~ q, e incluir o outro disjunto por
Adio.
Exemplo: p . q , p [q (s . t)] , s t
1 premissa 1 p . q r
2 premissa 2 r v q ~ p v s
3 premissa 3 s q
4 premissa 4 p
5 premissa 5 s
6 3, 5, MP q
7 4, 6, CONJ p . q
8 1, 7, MP r
27
1 premissa 1 p . q
2 premissa 2 p [q (s . t)]
3 2, EI p . q s . t
4 1, 3. MP s . t
5 4, AD (s . t) v (~s . ~ t)
6 5, BICOND s t
13. VALIDADE E INVALIDADE DE UM ARGUMENTO
Os mtodos de deduo que examinamos so capazes de mostrar a validade de
um argumento, atravs de uma seqncia de equivalncias e inferncias, que, a partir
das premissas, produz uma srie de concluses parciais, at chegar concluso final do
argumento.
Esse processo, no entanto, no serve para provar a invalidade de um argumento;
de fato, se, durante o processo de deduo, no conseguirmos chegar concluso, no
podemos inferir que no possvel obter tal concluso; talvez apenas no saibamos
como chegar a ela.
Portanto, para mostrar a invalidade de um argumento, necessitamos de um outro
mtodo. Conhecemos o teorema que estabelece que Um argumento P
1
, P
2
,..., P
n
Q
vlido se e somente se a condicional P
1
. P
2
. ... . P
n
Q uma tautologia. Portanto,
se P
1
. P
2
. ... . P
n
Q no uma tautologia tem-se que o argumento P
1
, P
2
,..., P
n
Q
no vlido.
P
1
. P
2
. ... . P
n
Q no uma tautologia se existir pelo menos uma
combinao de valores lgicos das proposies que torne a condicional falsa. Em que
condies uma condicional falsa? S existe uma possibilidade: quando o antecedente
verdadeiro e o conseqente falso. O antecedente, P
1
. P
2
. ... . P
n
verdadeiro se e
somente se todas as premissas P
1
, P
2
,..., P
n
so verdadeiras. Ento, para mostrar que um
argumento invlido, suficiente encontrar uma combinao de valores lgicos para as
proposies simples envolvidas, de forma que torne cada premissa verdadeira e a
concluso falsa.
Exemplo: Considere o seguinte argumento:
Se Jos comprar aes e o mercado baixar, ele perder seu dinheiro. O mercado no vai
baixar. Logo, ou Jos compra aes ou perder seu dinheiro.
Simbolicamente, o argumento fica representado por: p . q r, ~ q , p v r
onde: p: Jos comprar aes
q: o mercado baixar
r: Jos perder dinheiro
Para mostrar sua invalidade devemos encontrar valores lgicos (V ou F) para as
proposies simples p, q e r que faam as premissas verdadeiras e a concluso falsa; isto
: (a) VL[p . q r] = V; (b) VL[~ q] = V; (c) VL[p v r] = F. A partir destas trs
igualdades encontraremos os valores lgicos para p, q e r que as satisfaam.
De (b) vem (d) VL[q] = F; substituindo em (a), temos (e) VL[p . F r ] = V.
28
VL [p . F] = F qualquer que seja p, logo de (e) obtemos VL[F r] = V. Desta ltima
igualdade derivamos duas alternativas: VL[r]=V ou VL[r]=F, j que FVV e
FFV. Tomamos (f) VL[r]=F.
Substituindo (f) em (c) temos VL[p v F] = F. Daqui resulta (g) VL[p]=F.
Temos ento que, para o conjunto de valores lgicos
VL[p] = F, VL[q] = F, VL[r] = F
a condicional falsa, o que significa que o argumento invlido.
Um outro exemplo:
Considere o argumento: Ou estudo ou trabalho ou vou praia; se estudo sou aprovado;
no trabalho. Logo, sou aprovado.
Se fizermos: p: estudo
q: trabalho
r: vou praia
s: sou aprovado
o argumento fica representado simbolicamente por: p v q v r, p s, ~ q , s
Para que o argumento seja invlido necessrio:
a) VL[p v q v r] = V
b) VL[p s ] = V
c) VL[~ q] = V
d) VL[s] = F
De (c) e (d) vem, imediatamente, VL[q] = F e VL[s] = F; substituindo em (a) e (b), vem
e) VL[ p v F v r ] = V
f) VL[ p F ] = V
De (f), vem VL[ p ] = F; substituindo em (e), vem VL[ r ] = V.
Encontramos uma combinao de valores que satisfazem a condio de invalidade. O
argumento , portanto, invlido.
Se no for possvel atribuir valores verdade aos enunciados simples dos componentes de
argumento, de modo que suas premissas se tornem verdadeiras e sua concluso falsa,
ento o argumento vlido. Embora isso decorra da prpria definio de validade, tem
conseqncias curiosas. Observe o seguinte argumento:
Se eu for aprovado, vou para os Estados Unidos; se no, vou ficar aqui. No fui para os
Estados Unidos nem fiquei aqui. Logo, fui para a Argentina.
Simbolicamente: p q, ~ p r, ~q . ~r , s
onde: p: ser aprovado
q: ir para os Estados Unidos
r: ficar aqui
s: ir para a Argentina
29
Temos ento:
a) VL [ p q ] = V
b) VL [ ~p r ] = V
c) VL [ ~ q . ~ r ] = V
d) VL [ s ] = F
De (c), vem VL [ q ] = F e VL [ r ] = F; substituindo em (a) e (b), vem:
e) VL [ p F ] = V
f) VL [ ~ p F ] = V
De (e) vem VL [ p ] = F, e de ( f ), vem VL [ p ] = V, o que caracteriza uma contradio.
O que est ocorrendo?
Ora, no possvel fazer as premissas verdadeiras, independentemente da concluso,
porque as premissas so incoerentes entre si, o que torna sua conjuno contraditria.
Portanto, o argumento considerado vlido, pois no h possibilidade de atribuirmos o
valor F condicional que o representa.
Embora o argumento seja vlido, no possvel (nem necessrio) deduzir sua concluso
a partir das premissas, porque a concluso nada tem a ver com as premissas. Podemos
chamar esse tipo de validade de Validade por Contradio de Premissas.
Mas esse no o nico caso estranho. Observe o argumento:
Se eu for a festa, no chego cedo no trabalho. Se eu for ao cinema, no vou festa.
No vou ao cinema. Logo, ou eu chego cedo ao trabalho ou no chego cedo ao
trabalho.
Fazendo: p: vou festa
q: chego cedo ao trabalho
r: vou ao cinema
temos a seguinte forma para o argumento: p ~ q, r ~p, ~ r , q v ~ q
Observe que a concluso tem a forma q v ~q, que uma tautologia. Ento, no
possvel fazer a concluso falsa, e o argumento vlido. Tambm nesse caso, no
possvel deduzir a concluso a partir das premissas (a menos que a conjuno de
premissas tambm forme uma tautologia). Podemos chamar esse caso de validade de
Validade por Tautologia da Concluso.
Resumindo, temos as seguintes situaes na deduo de um argumento:
Um argumento vlido quando:
- o conjunto de premissas contraditrio.
- a concluso uma tautologia.
- a concluso pode ser deduzida das premissas.
Um argumento invlido quando:
30
- existe pelo menos um conjunto de valores para as proposies simples que
tornam as premissas verdadeiras e a concluso falsa.
Portanto, dado um argumento, para provar a sua validade ou invalidade,
devemos chegar a uma das concluses acima.
14. CLCULO DE PREDICADOS
PREDICADOS E VARIVEIS
Nos captulos anteriores examinamos uma parte da Lgica chamada Lgica das
Proposies, ou Clculo Proposicional, na qual aprendemos tcnicas que nos
permitiram verificar se um determinado tipo de argumento vlido ou invlido. Nos
argumentos estudados, os enunciados simples eram combinados atravs dos conectivos,
formando enunciados compostos, e a validade desses argumentos dependia,
essencialmente, da forma pela qual os enunciados compostos se apresentavam.
No difcil, no entanto, encontrar argumentos de um tipo distinto; por exemplo, o
argumento:
Todos os humanos so mortais
Scrates um humano
Logo, Scrates mortal
claramente vlido, mas sua validade no depende da forma pela qual os enunciados
simples se compem, uma vez que, neste argumento, no h enunciados compostos.
Pode-se perceber que sua validade depende, na verdade, da estrutura interna dos
enunciados que constituem o argumento. A construo de mtodos para analisar
argumentos como esse vai, portanto, exigir a criao de tcnicas para descrever e
simbolizar a estrutura interna dos enunciados.
Considere a premissa Scrates humano. Esse enunciado uma declarao de que
determinado indivduo (Scrates) possui uma propriedade especfica ( humano). Na
linguagem natural, o indivduo que possui a propriedade chamado sujeito, enquanto a
propriedade descrita chamada predicado.
O predicado, na verdade, explicita certas qualidades que o sujeito possui e que permite
inclu-lo em uma categoria; por exemplo, quando dizemos Scrates humano
queremos dizer que o objeto chamado Scrates possui certas caractersticas que
permitem inclu-lo no conceito que fazemos daquilo que chamamos humano.
Em Lgica Simblica, representamos o predicado por sua inicial maiscula, e o sujeito
a seguir, entre parnteses; assim, Scrates humano fica representado por
H (Scrates)
A linguagem natural permite ainda a construo de um outro tipo de sentena, como
ele foi presidente do Brasil na qual o sujeito no um substantivo, mas um pronome,
isto , um termo que fica no lugar do nome.
31
Em Lgica Simblica, tambm existem termos que ocupam o lugar dos nomes; so
chamados variveis, e costumam ser representados, como na Matemtica, pelas ltimas
letras do alfabeto, em minsculas: x, y, w, z, etc. Utilizando a varivel x no lugar de
ele, a sentena assume a forma
x foi presidente do Brasil
Em Lgica Simblica, representando o predicado foi presidente do Brasil por P, e
levando em conta que x sujeito, teramos a representao
P (x)
Para simplificar a notao alguns autores denotam P(x) por Px, ou seja, prescindem dos
parnteses para as variveis.
Em Lgica, portanto, um enunciado singular fica simbolizado pelo predicado,
representado por uma nica letra maiscula, seguido pelo sujeito, uma constante ou
uma varivel entre parnteses.
Uma frase na qual o sujeito uma constante, como Scrates humano, pode ser
verdadeira ou falsa; mas se o sujeito for uma varivel, como em ele foi presidente do
Brasil, ela no verdadeira nem falsa, dependendo de nome que assuma o lugar do
pronome. Uma frase como essa no , portanto, um enunciado.
Os enunciados so chamados sentenas fechadas, enquanto que frases como x foi
presidente do Brasil, y escreveu Os Lusadas e z viajou para os Estados Unidos so
chamadas sentenas abertas.
As sentenas abertas no so verdadeiras nem falsas; podemos dizer apenas que so
satisfeitas para certos valores das variveis, e no satisfeitas para outros. A substituio
das variveis de uma sentena aberta por constantes chama-se instanciao ou
especificao; a instanciao transforma uma sentena aberta em um enunciado, que,
este sim, pode ser verdadeiro ou falso.
Exemplos de sentenas abertas:
(1) 2x+3=7, xe
Poderamos interpretar esta sentena como a pergunta: Qual o nmero natural cujo
duplo somado com 3 da 7? Ou como a ordem: Determine o nmero natural cujo duplo
somado com 3 da 7. No podemos, evidentemente, atribuir o valor V ou F a esta
sentena, pois depende do valor que tome a varivel x. Uma vez substituda a varivel x
por um valor (especificao), por exemplo x=2 (2e ), a sentena 2 x 2+3=7
verdadeira. Se for x=5, 2 x 5+3=7 falsa.
(2) x+ys1 em
2
Esta sentena aberta pode ser interpretada como a pergunta: Quais os nmeros reais
cuja soma menor ou igual a 1? Ou como a ordem: determine os pares de nmeros
reais cuja soma menor ou igual a 1. Tambm no podemos atribuir o valor V ou F a
esta sentena, pois depende dos valores que tomem as variveis x e y.
32
A seguir escrevemos as definies para dar maior rigor aos conceitos.
Definio: Chama-se sentena aberta com uma varivel em um conjunto U, ou apenas
sentena aberta em U, a uma expresso P(x) tal que P(a) falsa (F) ou verdadeira (V)
para todo aeU. P denominado predicado e x a varivel da sentena aberta P(x).
A definio pode ser estendida a uma sentena aberta P(x
1
, x
2
,..., x
n
), com n variveis
x
1
, x
2
,..., x
n
, sendo x
1
eU
1
, x
2
eU
2
,..., x
n
eU
n
.
Definio: Chama-se conjunto-universo ou apenas universo de uma varivel ao
conjunto U de valores que ela pode assumir.
O universo U da varivel tambm costuma-se denominar domnio ou universo do
discurso.
Definio: Chamas-se conjunto de verdade de uma sentena aberta P(x) em um
universo U ao subconjunto de U formado pelos elementos aeU tais que P(a) uma
proposio verdadeira (V). Denotaremos o conjunto de verdade da sentena aberta P(x)
por V
P
. Ento, simbolicamente, V
P
={x | xeU . P(x) V} ou { aeU | VL[ P(a) ] = V }.
Para uma sentena em n variveis V
P
={ (x
1
, x
2
,..., x
n
) e U
1
U
2
... U
n
| P(x
1
, x
2
,...,
x
n
) V}.
Observaes:
1. Se aeU tal que VL[ P(a) ] = V, diz-se que a satisfaz ou verifica P(x).
2. Uma sentena aberta P(x) no universo U tambm se considera uma funo
proposicional em U, ou ainda, uma condio em U.
3. Em outros termos, P(x) uma sentena aberta em U se e somente se P(x) torna-se
uma proposio todas as vezes que se substitui x por qualquer elemento a do conjunto
U.
4. Na linguagem corrente, o Universo no , muitas vezes, explicitado; intuitivamente,
inclumos os objetos que podem substituir o pronome e descartamos aqueles objetos que
sabemos que no podem; por exemplo, na frase isto est verde sabemos que isto
pode ser uma fruta, ou uma parede, ou o mar, mas que dificilmente ser um ser humano.
5. Em Lgica, o Universo do Discurso, quando no for explicitado, definido pelo
prprio contexto. Muitas vezes, a definio do Universo pode afetar a satisfatoriedade
da sentena aberta; por exemplo, a sentena aberta x feroz pode ser satisfazvel se o
universo for o conjunto de animais, e no satisfazvel se o universo for o conjunto de
disciplinas de um curso.
Exemplos:
1. O universo da sentena aberta 2x+3=7, xe o conjuntodos nmeros naturais,
porque assim foi explicitado no seu enunciado. O conjunto de verdade {2}.
2. O universo da sentena aberta x+ys1 em
2
2
. O conjunto de verdade o
semiplano inferior determinado pela reta x+y = 1, mostrado na figura abaixo:
33
3. O conjunto verdade da sentena aberta x+3>5 no universo V=]2,+[.
4. O conjunto verdade da sentena aberta x+6<3 em o conjunto vazio V=C.
5. O conjunto verdade da sentena aberta x
2
>0 em o prprio .
6. Seja U = { 1, 2, 3, 4, 5, 6, 7 } e a expresso x primo representada por P(x). Temos
ento V
P
= { 2, 3, 5, 7 }.
Importante: Em Matemtica as equaes (f(x)=g(x)) e inequaes (f(x)<g(x) ou
f(x)> g(x)) so exemplos de sentenas abertas que exprimem, respectivamente, uma
relao de igualdade e desigualdade. Uma inequao em sentido amplo (f(x)sg(x) ou
f(x)>g(x)) exprime a disjuno entre uma relao de igualdade e outra de desigualdade.
Assim, assumindo como universo:
V
f(x)=g(x)
={xe | f(x)=g(x)}; V
f(x)<g(x)
={xe | f(x) < g(x)};
V
f(x)>g(x)
={xe | f(x) > g(x)}; V
f(x)sg(x)
={xe | [f(x)
<
g(x)] v [f(x)
=
g(x)] };
V
f(x)sg(x)
={xe | [f(x)
<
g(x)] v [f(x)
=
g(x)] }.
Resolver uma equao ou inequao, num dado conjunto universo, achar seu
conjunto de verdade. Duas equaes ou inequaes, ou dois sistemas de equaes so
equivalentes num certo conjunto-universo se possuem o mesmo conjunto-verdade. Por
exemplo, as equaes x4 =0 e x
2
8x+16=0 so equivalentes em , pois o conjunto de
verdade de ambas {4} neste conjunto universo.
O conceito de sentena aberta muito mais amplo que o de equao e
inequao, por exemplo, x divide a y, x mltiplo y, so sentenas abertas sem
serem equaes ou inequaes. Estes predicados com mais de um termo so chamados
de relaes por muitos autores, que reservam o nome predicado para os que possuem
somente uma varivel. Eis alguns exemplos de relaes e uma alternativa para denot-
las simbolicamente:
x gosta de y Gxy
Joo casado com Maria C (Joo, Maria)
x est entre y e z Exyz
34
Cames o autor de Os Lusadas A (Cames, Os Lusadas)
Nas relaes, a ordem das variveis importante; no exemplo dado, Gxy significa x
gosta de y, mas no significa y gosta de x. Esse fato deve ser levado em conta
mesmo em predicados que sabemos ser comutativos; no exemplo, C (Joo, Maria)
significa Joo casado com Maria, mas no significa Maria casada com Joo. O
motivo para isso que a Lgica Formal leva em conta apenas a forma das expresses, e
no seu significado.
Na instanciao, variveis iguais devem ser substitudas por nomes iguais; variveis
distintas, no entanto, podem ser substitudas por nomes iguais ou distintos. Por
exemplo, a sentena aberta x maior ou igual a y permite tanto a instanciao 7
maior ou igual a 3 como a instanciao 7 maior ou igual a 7.
Em relaes com duas variveis, o conjunto universo constitudo pelo produto
cartesiano dos Universos das variveis; o conjunto-verdade constitudo pelos pares
ordenados dos valores que satisfazem a relao. Por exemplo, considere a sentena
aberta Mxy representando x metade de y, onde U
x
= {1, 2, 3} e U
y
= { 4, 5 , 6 }.
Ento U
M
=U
x
U
y
= {(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)} e V
M
= {(2, 4 ),
(3, 6 )}.
15. OPERAES LGICAS COM SENTENAS ABERTAS
Tambm no Clculo de Predicados podemos definir as operaes de conjuno,
disjuno, negao, condicional e bicondicional, sobre enunciados e/ou sentenas
abertas.
Conjuno:
Considere, por exemplo, sentenas abertas x mdico, representado por M(x),
e x professor, representado por P(x), ambas com o mesmo universo. Podemos ento
representar x mdico e professor por M(x) . P(x). Se U o conjunto universo de x,
os valores de U que satisfazem simultaneamente M(x) e P(x) constituem o conjunto de
verdade da sentenas abertas M(x) . P(x) devem satisfazer; consequentemente,
V
M.P
= {xeU | M(x) . P(x)}= {xeU | M(x)} {xeU | P(x)}= V
M
V
P
Disjuno:
Da mesma forma, podemos representar x mdico ou professor por M(x) v
P(x). Esta sentena aberta satisfeita por todos os elementos que so mdicos ou por
todos que so professores; portanto,
V
MvP
= {xeU | M(x) v P(x)}={xeU | M(x)} {xeU | P(x)}= V
M
V
P
Negao:
Na operao de negao, podemos representar x no mdico por ~ M(x), e
seu conjunto-verdade ser constitudo por todos os elementos do Universo que no
satisfazem M(x), isto , o complemento de V
M
:
35
V
~M
= { xeU | ~M(x) }= U V
M
Uma notao de uso generalizado para o complemento de V
M
(V
M
)
ou (V
M
)
C
.
Exemplo: Sejam as sentenas abertas em , P(x): x
2
+ x 6=0; Q(x): x
2
9=0.
Tem-se que V
P
={xe| x
2
+ x 6=0}={3,2} e V
Q
={xe| x
2
9=0}={3,3}. Portanto:
V
PvQ
= V
P
V
Q
={3,2}{3,3}= {3,2,3} e V
P.Q
=V
P
V
Q
={3,2}{3,3}={3}.
Dado um sistema de equaes ou inequaes, se consideramos cada equao ou
inequao como uma sentena aberta, tem-se que o conjunto soluo do sistema o
conjunto-verdade da conjuno dos conjuntos-verdade (ou seja, do conjuntos solues)
das equaes ou inequaes do sistema.
Condicional:
Ligando as sentenas abertas P(x) e Q(x) pelo conectivo condicional ,
obtemos a nova sentena aberta P(x)Q(x). Lembrando que (PQ) (~PvQ), temos
para as sentenas condicionais que P(x)Q(x) ~P(x)vQ(x) em U. Logo, o conjunto-
verdade de P(x)Q(x) coincide com o conjunto-verdade de ~P(x)vQ(x) em U.
Simbolicamente: V
PQ
= V
~P
V
Q
= {xeU | ~P(x)} {xeU | Q(x)}.
Exemplo: Sejam as sentenas abertas em A={1,2,3,4,6,8,9,10,15,18,20,25,30}
P(x): x divisor de 18; Q(x): x divisor de 30.
Temos: V
P
={1,2,3,6,9,18}, V
~P
={4,8,10,15,20,25,30}, V
Q
={1,2,3,6,10,15,30}, logo,
V
PQ
= V
~P
V
Q
= {4,8,10,15,20,25,30}{1,2,3,5,6,10,15,30}=
= {1,2,3,4,6,8,10,15,20,25,30}.
Bicondicional:
Ligando as sentenas abertas P(x) e Q(x) pelo conectivo condicional ,
obtemos a nova sentena aberta P(x)Q(x). Lembrando que (pq)(pq) . (qp),
temos para as sentenas condicionais que P(x)Q(x) [P(x) Q(x)] . [Q(x) P(x)]
em U. Logo, o conjunto-verdade de P(x)Q(x) coincide com a interseo dos
conjuntos-verdade de P(x)Q(x) e Q(x) P(x). Simbolicamente:
V
PQ
= V
PQ
V
QP
= ( V
~P
V
Q
) ( V
~Q
V
P
).
Exemplo: Sejam a s sentenas abertas em A={0,1,2,3,4,5,6}, P(x): x
2
4x=0; Q(x):
x
2
2x=0. Temos: V
P
={0,4}, V
~P
={1,2,3,5,6}, V
Q
={0,2}, V
~Q
={1,3,4,5,6} e, portanto,
V
PQ
=( V
~P
V
Q
) ( V
~Q
V
P
)={0,1,2,3,5,6}{0,1,3,4,5,6}={0,1,3,5,6}.
16. QUANTIFICADORES
Consideremos, por exemplo, o conjunto A={5,7,8,9,11,13}. Podemos afirmar:
36
- Qualquer que seja o elemento de A, ele um nmero natural.
- Existe ao menos um elemento de A que nmero mpar.
- Existe um nico elemento de A que par.
- No existe elemento de A que mltiplo de 6.
Existem smbolos prprios, chamados quantificadores, para representar expresses
do tipo das quatro que acima dissemos. H fundamentalmente dois tipos de
quantificadores: universal e existencial.
Quantificador universal: Smbolo: . L-se: para todo, qualquer que seja.
Quantificador existencial: Smbolo: -. L-se: existe.
Observao: Quando dizemos existe um x tal que... no estamos dizendo que esse
x nico. Por exemplo, a sentena existe um nmero real x tal que x>2 verdadeira
embora existam infinitos nmeros reais maiores que 2.
Se P(x) uma sentena aberta num conjunto A, ento:
(xeA) P(x) ou
x
P(x) ou x,P(x)
um enunciado que l-se Para todo elemento x de A, P(x) um enunciado
verdadeiro, ou simplesmente, para todo x, P(x).
(-xeA) P(x) ou -
x
P(x) ou -x, P(x)
um enunciado que l-se Existe um xeA tal que P(x) um enunciado verdadeiro, ou
simplesmente, para algum x, P(x).
Para negar que existe, usa-se o smbolo - (l-se no existe). Por exemplo:
- xe| n
2
<0. Alguns autores representam a sentena Existe um nico x tal que...
pelo smbolo -!.
Observaes:
- A frase tal que, que aparece com freqncia em enunciados com o quantificador
existencial -, pode ser representada pelos smbolos: | ou:. Por exemplo, existe
um nmero natural n tal que n
2
<100 pode ser representada assim:
-ne
3
| n
2
<100.
- Quando no h perigo de dvida o quantificador universal pode ser escrito depois
e no antes da sentena aberta quantificada. Por exemplo, descrevendo a propriedade
associativa num grupo (G,*) podemos escrever: a*(b*c)=a*(b*c), a,b,ceG.
- Os quantificadores existenciais (-, -!, - ) nunca devem ser escritos aps a
sentena aberta quantificada.
Chama-se escopo de um quantificador a parte da frase sobre a qual ele atua;
em geral o escopo de um quantificador indicado pelos parnteses que o seguem. Se
3
Consideramos ={1,2,3,}, ou seja, no incluimos o zero em .
37
no houver parnteses, o escopo do quantificador limitado ao predicado que o segue.
Veja os exemplos abaixo:
-x ( P(x) v Q(x) ) escopo de -x: P(x) v Q(x)
-x P(x) v Q(x) escopo de -x: P(x)
-y ( P(x,y) . x Q(x) ) escopo de -y: P(x,y) . x Q(x) escopo de x: Q(x)
Voltando s quatro oraes do comeo do pargrafo relativas ao conjunto
A={5,7,8,9,11,13}, fazendo uso dos quantificadores podemos dizer:
- xeA, x natural.
- -xeA | x mpar.
- -! xeA | x par.
- - xeA | x mltiplo de 6.
Os quantificadores so usados para transformar sentenas abertas em
proposies. Seja P(x) uma sentena aberta num conjunto A, no vazio. Sendo P(x) uma
sentena aberta, evidentemente carece de valor lgico V ou F. Contudo, a sentena
aberta P(x) com qualquer quantificador antes dela, torna-se uma proposio e, portanto,
tem valor lgico V ou F.
Para o quantificador universal (), a proposio (xeA) P(x)
4
:
- Verdadeira se V
p
=A. Ou seja, verdadeira quando o conjunto de verdade de P(x)
o universo.
- Falsa se V
p
=A. Ou seja, falsa quando o conjunto de verdade de P(x) diferente do
universo.
Para o caso do quantificador existencial (-), a proposio (-xeA) p(x)
5
:
- Verdadeira se V
p
=C.
- Falsa se V
p
=C.
Negao de proposies que contm quantificadores.
Consideremos que a expresso x P(x) verdadeira no universo U={u
1
,u
2
,...,
u
n
}. Isto significa que P(u
1
)V, P(u
2
) V,... , P(u
n
) V. Logo, x P(x) [P(u
1
) . P(u
2
)
. ... . P(u
n
)]. Negando:
~[x P(x)] ~[P(u
1
).P(u
2
). ... .P(u
n
)] ~ P(u
1
)v ~ P(u
2
)v ... v ~ P(u
n
) -x ~ P(x)
Da Mesma forma, -x P(x) verdadeira no universo U={u
1
,u
2
,..., u
n
} significa
que P(u
1
)V ou P(u
2
) V ou ... ou P(u
n
) V. Ou seja: -x P(x) [P(u
1
) v P(u
2
) v ... v
P(u
n
)]. Negando:
~[-x P(x)] ~[P(u
1
)vP(u
2
) v ... vP(u
n
)] ~ P(u
1
) . ~ P(u
2
) . ... . ~ P(u
n
) x ~ P(x)
Portanto, ~[x P(x)] -x ~ P(x) e ~[-x P(x)] x ~ P(x),
ou, indicando o universo da varivel:
4
Tambm poderia se escrever (xeA) (p(x)).
5
Pode ser escrita (-xeA) (p(x)).
38
~(xeM) (P(x)) (-xeM) (~P(x)) e ~(-xeM)(P(x)) (xeM)(~P(x))
Dessas equivalncias decorre que para mostrar que uma expresso do tipo
x P(x) falsa, basta mostrar que sua negao -x ~P(x) verdadeira, ou seja, exibir um
elemento k tal que P(k) seja falsa. Para mostrar que -x P(x) falsa precisa-se provar
que x ~P(x) verdadeira.
Exemplos:
1. A negao da proposio todo homem mortal no verdade que todo homem
mortal, ou seja, existe ao menos um homem que no mortal. Simbolicamente, se M
denota o conjunto dos homens, ento as proposies anteriores podem se escrever
~(xeM)(x mortal) (-xeM)(x no mortal)
Melhor ainda, se P(x) significa que x mortal, podemos escrever:
~(xeM)(P(x)) (-xeM)(~P(x)) (1)
2. Consideremos a proposio: Existe um nmero real cujo quadrado negativo. A
negao falso que existe um nmero real cujo quadrado negativo, ou seja,
Todo nmero real tem quadrado no negativo. Simbolicamente, se Q(x), com xe,
significa que x
2
<0, temos:
~(-xe)(Q(x)) (xe)(~Q(x)), ou,
~(-xe)(x
2
<0) (xe)(x
2
>0)
3. A negao de Para todo nmero natural n, n+2>8, que podemos escrever tambm
(ne )(n+2>8), : Existe um nmero natural n tal que n+2 < 8, ou, Existe um
nmero natural n tal que n+2>8. Simbolicamente:
(-ne) (n+2>8), ou, -ne | n+2>8.
Observe que:
- a negao de s >
- a negao de > <
- a negao de < >
- a negao de > s
QUANTIFICAO DE SENTENAS ABERTAS COM MAIS DE UMA
VARIVEL
QUANTIFICAO PARCIAL
Consideremos, por exemplo, a expresso (-xeA) (2x+y<7) sendo A={1,2,3,4,5}
o universo das variveis x e y. Esta expresso, que se pode ler: Existe pelo menos um
xeA para o qual se tem 2x+y<7, no uma proposio, visto que seu valor lgico,
embora no dependa de x (varivel aparente), depende de y (varivel livre). Portanto,
uma sentena aberta em y, cujo conjunto-verdade {1,2,3,4}, pois, somente para y=5
no existe xeA tal que 2x+y<7.
39
Analogamente, a expresso (yeA) (2x+y<10) sendo A={1,2,3,4,5} o universo
das variveis x e y, que se pode ler: Para todo yeA se tem 2x+y<10, tambm no
uma proposio, mas uma sentena aberta em x (varivel livre), cujo conjunto de
verdade {1,2}, pois, somente para x=1 ou x=2 se tem 2x+y<10 para todo yeA.
De um modo geral, dada uma sentena aberta com mais de uma varivel, a
aplicao de um quantificador referido a uma das variveis, transforma a sentena
aberta dada numa outra sentena aberta com menos uma varivel livre.
QUANTIFICAO MLTIPLA
Toda sentena aberta precedida de quantificadores, um para cada varivel, isto ,
com todas as variveis quantificadas, uma proposio, pois, assume um dos valores
lgicos V ou F. Assim, so exemplos de proposies:
1. (xeA) (yeB) ( P(x,y) )
2. (xeA) (-yeB) ( P(x,y) )
3. (-xeA) (yeB) (zeC) ( P(x,y,z) )
Exemplos:
1) Considere os conjuntos H = { Carlos, Pedro, Mrio } e M = { Claudia, Llian } e
o predicado I(x,y) = x irmo de y, onde H o universo de x, e M o universo de y.
Suponha que Carlos e Pedro sejam irmos de Claudia, e que Mrio seja irmo de Llian.
Examine a validade dos seguintes enunciados:
a) (x e H) (-y e M) ( I(x,y) )
b) (-x e H) (y e M) ( I(x,y) )
c) (x e H) (y e M) ( I(x,y) )
d) (-x e H) (-y e M) ( I(x,y) )
fcil perceber que o primeiro e o ltimo so verdadeiros, e os demais, falsos.
Observe que mudando a ordem dos quantificadores obtemos proposies
diferentes. Por exemplo, mudando a ordem em (a) obtemos:
(e): (-y e M) (x e H) ( I(x,y) ) que falsa, ao invs de (a) que verdadeira.
2) A proposio (x e ) (ye ) ( (x+y)
2
> x
2
+y
2
) obviamente verdadeira. Esta
proposio tambm se pode escrever (x,ye) ( (x+y)
2
> x
2
+y
2
) ou (x+y)
2
> x
2
+y
2
,
x,ye.
A proposio (x+y)
2
> x
2
+y
2
, x,ye falsa, o que fcilmente se comprova tomando,
por ejemplo, x=4 e y= -5. Quando no existe dvida pode-se omitir o domnio das
variveis, por ejemplo, num contexto onde est claro que o universo de todas as
variveis podemos escrever (x+y)
2
= x
2
+2xy+y
2
, x,y no lugar de (x+y)
2
=
x
2
+2xy+y
2
, x,ye.
40
3) Consideremos os conjuntos A={1,2,3,4} e B={0,2,4,6,8} e a sentena aberta
em AB: 2x+y=8.
A proposio (xeA) (-yeB) (2x+y=8) verdadeira, pois, para x=1,2,3,4
temos y=6,4,2,0eB, respectivamente.
A proposio (yeB) (-xeA) (2x+y=8) falsa, pois, para x=8 temos x=0eA.
A proposio (-yeB) (xeA) (2x+y=8) tambm falsa, pois, no exite um
yeB tal que para todo xeA seja 2x+y=8.
Anlogamente, tambm falsa a proposio (-xeA) (yeB) (2x+y=8).
COMUTATIVIDADE DOS QUANTIFICADORES
1. Quantificadores da mesma especie podem ser comutados:
(xeA) (yeB) P(x,y) (yeB) (xeA) P(x,y)
(-xeA) (-yeB) P(x,y) (-yeB) (-xeA) P(x,y)
2. Quantificadores de especies diferentes em geral no podem ser comutados:
(xe) (-ye) (x > y) verdadeira, mas (-ye) (xe) (x > y) falsa.
NEGAO DE PROPOSIES COM MAIS DE UM QUANTIFICADOR
A negao de proposies com mais de um quantificador se obtn mediante a
aplicao sucesiva das leis de De Morgan, utilizando as regras para negao de
proposies com um nico quantificador. Por ejemplo:
~[x y P(x,y)] -x ~ [y P(x,y)] -x [-y ~ P(x,y)] -x -y ~ P(x,y)
~[-x -y P(x,y)] x ~ [-y P(x,y)] x [y ~ P(x,y)] x y ~ P(x,y)
~[x -y P(x,y)] -x ~ [-y P(x,y)] -x [y ~ P(x,y)] -x y ~ P(x,y)
~[-x y P(x,y)] x ~ [y P(x,y)] x [-y ~ P(x,y)] x -y ~ P(x,y)
Ou, sem escrever os parnteses nos passos intermedirios:
~x y P(x,y) -x ~ y P(x,y) -x -y ~ P(x,y)
~ -x -y P(x,y) x ~ -y P(x,y) x y ~ P(x,y)
~ x -y P(x,y) -x ~ -y P(x,y) -x y ~ P(x,y)
~ -x y P(x,y) x ~ y P(x,y) x -y ~ P(x,y)
Exemplo com trs quantificadores:
~(-x) (-y) (z) ( P(x,y,z) ) (x) [ ~(-y) (z) ( P(x,y,z) ) ] (x) (y) [ ~(z) ( P(x,y,z) ) ]
(x) (y) (-z) ~ P(x,y,z).
17. TEOREMAS
Um teorema em Matemtica uma relao condicional do tipo Se H, ento,
T, ou simbolicamente HT, com o sentido de que da veracidade da proposio H se
infere a veracidade da proposio T. Portanto, um teorema uma inferncia ou
implicao lgica. H constitui a hiptese do Teorema e T, a tese do Teorema. s vezes
se fala em hipteses do teorema, em plural, porque geralmente H uma proposio
composta.
41
O sentido de um teorema est na relao de implicao que se afirma existir
entre a hiptese e a tese, nesta ordem: A tese decorre da hiptese. Mas muito
importante saber que todo teorema tem que ser demonstrado. A demonstrao consiste
em provar que a tese uma proposio verdadeira, a partir da suposio de que a
hiptese uma proposio verdadeira. Uma vez provado o teorema podemos aplic-lo
em toda ocasio apropriada, isto , se numa situao concreta verificamos que a
hiptese do teorema verdadeira podemos, sem dvida, afirmar que a tese tambm
uma proposio verdadeira.
Uma diferena importante entre o significado da implicao no teorema (HT)
e a implicao no conetivo lgico condicional (HT), radica em que no segundo no
est estabelecida a veracidade de T como decorrente da veracidade de H; mas no
teorema ocorre a decorrncia. Por exemplo, consideremos as proposies: W t
irracional e R 7 primo. Ambas so proposies verdadeiras, logo a condicional W
R verdadeira. Mas WR no um teorema, porque o fato de ser 7 um nmero
primo no decorre, no conseqncia, no se infere, do fato de ser t um nmero
irracional.
Sabemos que muitos textos de lgica, para evitar confuses, denotam o conetivo
lgico se P ento Q por PQ, e o teorema se P ento Q por PQ. Reiteramos,
neste contexto, que os smbolos e representam questes diferentes. O indica
uma operao lgica, que a todo par de proposies P e Q associa uma nova
proposio, PQ. Ou seja, cria uma nova proposio a partir de duas proposies
quaisquer. Por outra parte, o smbolo estabelece uma relao entre as proposies P
e Q, que consiste em que se P VERDADEIRA, ento Q tambm VERDADEIRA.
Quando na literatura matemtica se fala em teorema, entende-se que nos
referimos a um teorema verdadeiro. Isto significa que foi rigorosamente provado,
aplicando as leis da lgica e o conhecimento da rea concreta, que se a hiptese
verdadeira, tem-se que a tese tambm verdadeira. Esta prova garante que, se
verificamos num dado modelo que o valor lgico da hiptese verdadeiro, ento est
garantido, sem dvida alguma, que o valor lgico da tese verdadeiro. Por exemplo,
temos o teorema: Se a soma dos algarismos de um nmero inteiro mltiplo de trs,
ento o nmero divisvel por trs. A Hiptese, H, a soma dos algarismos do
nmero mltiplo de trs e a tese o nmero divisvel por trs. Mediante uma
srie de passos o teorema provado, na Teoria dos Nmeros, com absoluto rigor e
generalidade. Se tomarmos o nmero 3249345699e e conferimos que
3+2+4+9+3+4+5+6+9+9=54=318, aplicando o teorema, temos certeza que
3249345699 divisvel por 3.
Os teoremas geram o conhecimento na Matemtica. Na construo de uma teoria
matemtica estamos interessados em achar proposies condicionais do tipo
verdadeiroverdadeiro, ou seja, estamos interessados em descobrir (ou inventar?)
teoremas. John B. Fraleigh, no seu excelente livro A First Course in Abstract Algebra,
diz: The main business of mathematics is proving theorems, que podemos livremente
traduzir como: O trabalho principal da matemtica es provar teoremas, ou, O
negocio principal da matemtica provar teoremas.
Em um teorema no devem existir hipteses redundantes, ou seja, no devem ser
colocadas hipteses desnecessrias ou sobrando. Portanto, na demonstrao de um
42
teorema sem hipteses redundantes, cada hiptese utilizada ao menos num lugar da
demonstrao.
Para enunciar um teorema podemos utilizar diversas locues como: por
conseguinte, se deduz, se infere, suficiente que..., para que..., logo..., e
outras similares para expressar que toda vez que se cumpra o asseverado na hiptese se
cumprir o que se afirma na tese. Por exemplo, os seguintes enunciados exprimem um
nico teorema:
- Se um nmero mltiplo de 6, ento, mltiplo de 3.
- De ser um nmero mltiplo de 6 se deduz que o nmero mltiplo de 3.
- suficiente que um nmero seja mltiplo de 6 para que seja mltiplo de 3.
- a mltiplo de 6 a mltiplo de 3
- Se um nmero mltiplo de 6 se infere que esse nmero mltiplo de 3.
- Para que um nmero seja mltiplo de 3 basta que seja mltiplo de 6.
- Ser mltiplo de 3 condio necessria para que um nmero seja mltiplo de 6.
- Um nmero mltiplo de 6 somente se mltiplo de 3.
Eis outros exemplos de teoremas:
1. A soma de dois nmeros inteiros pares um nmero inteiro par.
2. A soma de um nmero inteiro par e um nmero inteiro impar um nmero
impar.
3. Se uma funo real derivvel num ponto, ento, contnua nesse ponto.
4. Em todo tringulo retngulo, o quadrado da hipotenusa igual soma dos
quadrados dos catetos.
5. A soma dos n primeiros nmeros naturais igual a
( 1)
2
n n +
.
Para ter a certeza de que as proposies anteriores so teoremas teramos que
fazer suas demonstraes. Oportunamente estudaremos os tipos de demonstraes que
existem em Matemtica.
Quando lemos um enunciado que pretende ser um teorema devemos ser muito
cuidadosos e interpretar o que est estritamente escrito, porque a linguagem matemtica
rigorosa e no da espao para ambigidades. Por exemplo, a proposio: O quadrado
de todo nmero real um nmero positivo pode parecer primeira vista um teorema,
mas no . Observemos que 0 um nmero real e 0
2
=0 no um nmero positivo. O
enunciado correto : O quadrado de todo nmero real um nmero no negativo.
Para provar que um teorema falso basta encontrar um contra-exemplo, ou seja, um
caso concreto onde as hipteses so verdadeiras, mas a tese falsa. No exemplo, 0
2
=0
um contra-exemplo para o suposto teorema enunciado.
A relao de equivalncia entre a hiptese e a tese aparece com freqncia nos
enunciados de teoremas. Por exemplo, consideremos os teoremas:
1. Se um tringulo tem dois lados iguais, ento, os ngulos opostos a esses lados
tambm so iguais.
2. Se um tringulo tem dois ngulos iguais, ento, os lados opostos a esses ngulos
tambm so iguais.
43
Podemos incluir os dois teoremas anteriores em um nico enunciado. Para
compreender melhor separemos a hiptese e tese de cada um. Sejam:
pUm tringulo tem dois lados iguais.
q Um tringulo tem dois ngulos iguais.
O teorema (1) pq, e o teorema (2) qp. Podemos englobar os dois teoremas
em um nico enunciado, que tambm um teorema: pq. Na linguagem natural este
teorema poderia ser escrito de diferentes formas equivalentes, por exemplo:
- Um tringulo tem dois lados iguais se, e somente se, os ngulos opostos a
esses lados so iguais.
- condio necessria e suficiente para que um tringulo tenha dois lados iguais
que os ngulos opostos a esses lados sejam iguais.
- Em todo tringulo a existncia de dois lados iguais equivale existncia de dois
ngulos iguais.
Para compreender satisfatoriamente a literatura matemtica importante saber que
se HT um teorema, relacionam-se com ele os seguintes teoremas:
- O Teorema recproco do teorema HT o teorema TH.
Convencionalmente H T chamado de teorema direto e TH, de teorema
recproco, mas cada um o recproco do outro. s vezes o chamado de direto
recebe essa denominao por ser o mais aplicado ou conhecido. Observe que
para formar o recproco trocamos a hiptese pela tese, e a tese pela hiptese.
- O Teorema inverso ou contrrio do teorema H T o teorema ~H ~T.
Ou seja, a hiptese do teorema inverso a negao da hiptese do direto, e sua
tese a negao da tese do direto.
- O Teorema contrapositivo ou contra-recproco do teorema H T o
teorema ~T ~H. Observe que o teorema contra-recproco o contrrio do
recproco do teorema original.
Exemplos:
Consideremos o conhecido teorema (3): Se uma funo real derivvel num
ponto, ento, contnua nesse ponto. Separemos a hiptese (H) e a tese (T) deste
teorema, que consideraremos como o teorema direto:
H: A funo real f derivvel em x=a.
T: A funo real f contnua em x=a.
claro que o teorema (3) HT.
1. O recproco do teorema (3) seria TH, que na linguagem natural podemos
escrever: Se uma funo real contnua num ponto, ento, derivvel nesse ponto.
Do curso de Anlise sabemos que esta implicao falsa. O contra-exemplo
clssico a funo y=|x| em x=0. Logo, o recproco falso, ou seja, no propriamente
um teorema.
2. Tomemos o Teorema de Pitgoras: Em todo tringulo retngulo o quadrado da
hipotenusa igual soma dos quadrados dos catetos. Separemos hiptese e tese:
H: Um tringulo retngulo.
T: O quadrado da hipotenusa igual soma dos quadrados dos catetos.
44
O Teorema de Pitgoras HT. Lembremos que o nome hipotenusa designa o
lado maior do tringulo retngulo e o nome cateto dado a cada um dos lados menores.
O recproco : TH. Na linguagem natural podemos escrever: Se num
tringulo o quadrado do lado maior igual soma dos quadrados dos outros dois lados,
ento, o tringulo retngulo. Este teorema verdadeiro e sua demonstrao pode ser
achada em algum bom livro de Geometria.
Em fim, tem-se a equivalncia HT, ou seja, verdadeiro o teorema: A
condio necessria e suficiente para que um tringulo seja retngulo que o quadrado
do lado maior seja igual soma dos quadrados dos outros dois lados.
Quando temos uma equivalncia PQ, costuma-se dizer que Q uma
caracterizao de P (ou. P uma caracterizao de Q). Assim, o tringulo retngulo
esta caracterizado pela propriedade de que o quadrado do seu lado maior igual soma
dos quadrados dos outros dois lados.
Se HT e seu recproco TH so ambos teoremas verdadeiros, como no caso
do Teorema de Pitgoras, sabemos que tem-se a equivalncia: HT. Lembre que
quando lemos na literatura matemtica P se, e somente se Q, ou P equivalente a
Q, ou, P condio necessria e suficiente para Q, estamos perante a equivalncia
HT, consistente na conjuno dos dois teoremas: HT e TH.
Analisando os dois exemplos anteriores podemos afirmar que da validade de um
teorema no se infere a validade do seu recproco.
Observe tambm que o recproco do recproco o direto, logo, considerar um
teorema como direto e o outro como recproco convencional.
3. O teorema inverso do teorema (3): Se uma funo real derivvel num
ponto, ento, contnua nesse ponto seria: ~p~q: Se uma funo real no
derivvel num ponto, ento, no contnua nesse ponto. Obviamente falso, pois a
funo valor absoluto, y=|x| em x=0 no derivvel mas contnua.
O inverso do Teorema de Pitgoras : Se um tringulo no retngulo, ento,
o quadrado do lado maior no igual soma dos quadrados dos lados menores, que
verdadeiro. Portanto, conclumos que o inverso de um teorema pode ser ou no ser
um teorema.
4. O teorema contra-recproco do teorema (3) Se uma funo real no
contnua num ponto, ento, no derivvel nesse ponto. O teorema contra-recproco
do Teorema de Pitgoras : Se num tringulo o quadrado do lado maior no igual
soma dos quadrados dos lados menores, ento, o tringulo no retngulo."
Tem-se o importante resultado: Todo teorema HT equivalente a seu
contra-recproco ~T ~H. Portanto, para provar um deles basta provar o outro.
Vejamos a demonstrao: [ HT ] ~HvT Tv~H ~(~T) v~H [~T ~H].
Quando lemos o enunciado de um teorema frequentemente encontramos
conceitos que devem ser perfeitamente compreendidos para entender o contedo do
teorema em questo. Por exemplo, em lgebra Linear temos o teorema: Sejam E e F
dois espaos vetoriais de dimenso finita sobre o mesmo corpo K; f: EF uma
aplicao linear; Ker(f) e Im(f) o ncleo e a imagem, respectivamente, da aplicao f.
Ento dim
K
E = dim
K
Ker(f) + dim Im
K
(f). Para entender este teorema precisa saber o
que significa: Espao vetorial sobre um corpo; dimenso de um espao vetorial; espao
45
vetorial de dimenso finita; aplicao linear; ncleo de uma aplicao linear e imagem
de uma aplicao linear. Cada um desses conceitos definido na teoria na lgebra
linear. A seguir vemos o que uma definio em matemtica.
18. DEFINIES
Muitos alunos no valorizam adequadamente a importncia das definies na
Matemtica. A importncia das definies parte da necessidade de comunicao dos
matemticos com as pessoas que se interessam nos seus trabalhos. Se dois indivduos
esto tentando se comunicar sobre algum determinado objeto, eles devem ter o mesmo
entendimento sobre o objeto.
As definies permitem uma conceituao, organizao e estruturao das idias
e conceitos matemticos, sem as quais seria praticamente impossvel entender a teoria e,
muito menos, desenvolv-la. Por exemplo, a noo de continuidade para funes reais
conceituada mediante as definies de continuidade em um ponto e continuidade num
conjunto. Imagine se cada vez que vai tratar nos teoremas e problemas com funes
contnuas tivesse que listar todas suas caractersticas. Mediante as definies
caracterizamos novos objetos matemticos a partir de outros anteriores, assim,
mostramos a relao e articulao entre diversos conceitos que no apareceriam to
evidentes. Por exemplo, o tringulo pode ser definido em termos dos conceitos de reta e
ponto.
Toda definio deve ser entendida como uma equivalncia (se, e somente se),
embora se costume escrever unicamente a palavra se. Por exemplo, a definio um
tringulo issceles se tem dois lados iguais deve ser interpretada como um tringulo
issceles se, e somente se tem dois lados iguais. Isto , o conceito de tringulo
issceles est caracterizado, equivalente, ao fato de ter dois ngulos iguais.
As definies normalmente usadas em matemtica so consideradas do tipo
nominal. Includas neste tipo esto as definies simplesmente convencionais, que
equivalem a usar uma palavra ou smbolo em lugar de outros. Por exemplo, na lgebra
dos nmeros reais definimos o smbolo a
-1
para representar o b tal que ab = 1. Ou
um autor de um livro de lgebra define a palavra grupo como um conjunto G no qual
est definida uma operao * que satisfaz: i) a*(b*c)=(a*b)*c a,b,ceG. ii) $eeG|
a*e=e*a=a aeG. iii) aeG $ a
-1
eG | a a
-1
= a
-1
a=e.
Tambm esto includas nas definies nominais as definies que so propostas
como formalizaes ou reconstrues racionais de noes imprecisas ou
intuitivamente vagas.
Definies nominais so usadas por uma questo de convenincia, por exemplo,
quando uma longa sucesso de smbolos substituda por um nico smbolo, ou so
uma forma de chamar ateno para um objeto ou conceito particular considerado
relevante, ou uma tentativa de substituir uma noo intuitiva vaga por uma formal
precisa. As definies so julgadas pela sua utilidade, adequao e relevncia.
Outra questo importante, relativa ao ensino-aprendizado da matemtica, a
interpretao das definies. Ningum pode agregar ou suprimir proposies de uma
46
definio estabelecida. Por exemplo, quando definimos tringulo issceles no
escrevemos que o terceiro lado tem que ser diferente dos outros dois que so iguais,
portanto, um tringulo eqiltero (aquele com os trs lados iguais) tambm issceles.
A mesma coisa acontece com os conceitos de quadrado e retngulo, todo quadrado
tambm um retngulo.
Quando elaboramos ou interpretamos uma definio devemos pensar na sua
consistncia, analisando se no existe alguma ambigidade ou at contradio entre os
atributos dados ao objeto definido ou algum choque com outras definies existentes
na teoria. Por exemplo, quando definimos os coeficientes de Fourier, a
n
e b
n
,
de uma
funo f definida no intervalo [t,t] como as integrais
1
( ) cos( )
n
a f x nx dx
t
t
t
=
}
e
1
( ) ( )
n
b f x sen nx dx
t
t
t
=
}
, devemos pensar que para que a definio seja consistente tem
que estar garantida a existncia das integrais. Para isto suficiente que f seja contnua
em [t,t], logo, ao redigir a definio deve ser escrito que f contnua em [t,t].
Quando estudamos alguma teoria matemtica temos que memorizar as
definies (tambm os teoremas), mas a memorizao tem que ser feita com raciocnio
e interpretao, no como um papagaio que fala sem saber o que est falando. Voc
tem que ser capaz de reproduzir a definio com suas prprias palavras, no precisa ser
copia idntica colocada pelo professor ou lida no livro, mas no pode faltar nenhum
elemento importante. s vezes, as definies no aparecem explicitamente rotuladas
como tal nos livros e o leitor tem que interpretar como tal, por exemplo, lendo o texto:
Se v
1
, v
2
, ... , v
n
so vetores de um espao vetorial real V, e o
1
, o
2
, ... , o
n
so escalares,
um vetor da forma o
1
v
1
+ o
2
v
2
+... + o
n
v
n
uma combinao linear dos vetores v
1
, v
2
,
... , v
n
, devemos interpretar que esto definindo o conceito de combinao linear de
vetores.
19. COMO SE APRESENTA UMA TEORIA MATEMTICA?
Para ter uma idia de como apresentada, estruturada ou construda uma teoria
matemtica podemos pensar na Geometria. Existe um grande nmero de teoremas que
demonstram verdades geomtricas. Um dado teorema demonstrado se baseando em
alguns outros teoremas j demonstrados previamente; estes, pela sua vez, so provados
a partir de outros anteriores e assim sucessivamente. Mas se continuamos descendo a
escada at o principio, veremos que existem certas proposies primarias, primitivas,
que no podem ser demonstradas em termos de outras mais simples e, portanto, so
aceitas como verdadeiras sem demonstrao. Estas proposies que ficam no alicerce
do edifcio da teoria so os chamados axiomas. O mais famoso de todos os axiomas da
Matemtica , tal vez, o quinto postulado de Euclides: Por todo ponto exterior a uma
reta num plano sempre passa uma nica paralela dita reta.
Se pensarmos nos objetos geomtricos acontece algo parecido, definimos novos
objetos a partir de objetos anteriores. Por exemplo, o tringulo definido a partir dos
conceitos de reta e ponto. Mas, se tentamos definir ponto ou reta em termos de objetos
mais simples, ser impossvel. Ponto e reta so considerados elementos primitivos,
admitimos sua existncia sem t-los definido. Tambm existem propriedades e relaes
entre os elementos primitivos da teoria que no podem ser demonstrados e so aceitos
como axiomas. Por exemplo, so axiomas: dado dois pontos deferentes do plano existe
47
uma nica reta que os contm, existem trs pontos que no pertencem a uma nica
reta.
Por tanto, nos fundamentos de uma teoria matemtica esto os elementos
primitivos e os axiomas. So conceituados novos elementos ou objetos mediante as
definies e so provados os teoremas que estabelecem proposies verdadeiras
supondo a veracidade dos axiomas. Toda teoria matemtica apresentada como uma
seqncia de enunciados: axiomas, definies e teoremas, ordenados logicamente. Na
figura (1) mostramos esquematicamente a estruturao axiomtica de uma teoria
matemtica, conforme explicado.
Uma teoria dedutiva o conjunto dos elementos primitivos, axiomas, definies
e proposies. A Lgica Matemtica fornece as regras de inferncia e a linguagem
formal para, sem esquecer a linguagem natural, formar os novos conceitos nas
definies e obter os teoremas. Na figura 1 mostramos esquematicamente, a grosso
modo, a estruturao axiomtica de uma teoria. Voltaremos ao assunto para especificar
detalhes relativos s principais correntes filosficas atuais nos fundamentos da
Matemtica.
ALICERCE
Assumimos sua existncia Proposies assumidas como verdadeiras sem
sem dar uma definio. demonstrao. Caracterizam os elementos
primitivos e suas inter-relaes.
L I N G U A G E M
REGRAS DE INFERNCIA
Conceituam novos objetos matemticos a partir
dos elementos primitivos ou outros objetos
definidos previamente. Consistncia com
os Axiomas e Teoremas.
Proposies do tipo HT (ou HT) que
so demonstradas.
Figura 1: Estruturao axiomtica de uma teoria matemtica
Podemos distinguir neste contexto trs nveis de apresentao das teorias
matemticas: apresentao intuitiva, apresentao axiomtico-informal e apresentao
axiomtico-formal. Brevemente daremos uma descrio de cada uma de elas.
Apresentao intuitiva das teorias matemticas
Uma primeira forma de apresentar as teorias matemticas, estreitamente
vinculada com o surgimento histrico da matemtica e com a criatividade matemtica,
a apresentao intuitiva das teorias. A palavra intuio significa a faculdade de
perceber, discernir ou pressentir coisas, independentemente de raciocnio ou de anlise.
O conhecimento intuitivo direto, claro e imediato.
ELEMENTOS
PRIMITIVOS
AXIOMAS
DEFINIES
TEOREMAS
48
Um exemplo de apresentao intuitiva de teorias matemticas o temos na teoria
de conjuntos, como usualmente ministrada no ensino de segundo grau ou em cursos
elementares na universidade. No nvel intuitivo, uma teoria no outra coisa alm de
um conjunto de enunciados acerca de certos elementos, suas relaes e as operaes
factveis entre eles descritas pelos algoritmos correspondentes.
Apresentao axiomtico-informal das teorias matemticas
Uma segunda forma de apresentao das teorias matemticas a apresentao
axiomtico-informal, como por exemplo, a geometria euclidiana no segundo grau (numa
boa escola) ou em cursos introdutrios no terceiro grau. Esta forma de apresentao est
historicamente associada a um processo de reflexo com o objetivo de organizar e
sistematizar os conhecimentos acumulados em certa disciplina matemtica.
No nvel axiomtico informal, como no nvel intuitivo, uma teoria tambm um
conjunto de enunciados acerca de certos elementos, suas relaes, e as operaes e as
operaes factveis entre eles descritas pelos algoritmos correspondentes. A
caracterstica distintiva fundamental numa axiomtica informal a dependncia
dedutiva entre os enunciados e as proposies da teoria.
A dependncia dedutiva entre os enunciados ou proposies consiste em
considerar um conjunto A de enunciados, chamados axiomas, dos quais se extrai, por
meio de um sistema lgico no explicitado, um conjunto C(A) de conseqncias
lgicas de A; isto , um conjunto de enunciados chamados teoremas, que se estabelecem
estruturando demonstraes a partir dos axiomas e mediante o uso de certas regras de
deduo no esclarecidas.
Considera-se que os teoremas so dedutveis a partir dos axiomas e que os
conceitos definidos atravs dos conceitos primitivos possuem uma clareza intuitiva, j
que se apiam na evidncia intuitiva dos axiomas e dos conceitos primitivos.
Apresentao axiomtico-formal das teorias matemticas
Esta forma de apresentao das teorias matemticas resultado de uma anlise
crtica da linguagem utilizada para expressar ditas teorias (capacidade expressiva) e da
lgica utilizada na argumentao e a apresentao das provas dos teoremas (capacidade
de inferncia). Uma apresentao axiomtica que inclua uma explicitao exaustiva das
bases expressivas e lgicas de uma teoria uma apresentao axiomtico-formal. Trata-
se de um tratamento desenvolvido por lgicos e matemticos fundamentalistas.
Modernamente a axiomatizao formal tem-se desenvolvido num ramo especial da
lgica matemtica denominado teoria dos sistemas formais.
A forma axiomtico-formal das teorias matemticas se desenvolveu
fundamentalmente no fim do sculo XIX e durante as primeiras dcadas do sculo XX,
quando a revoluo operada no desenvolvimento da lgica, devida sobre todo a
Bertrand Russel, chamou a ateno para a lgica utilizada na argumentao e
apresentao de teoremas em matemtica. Esta situao culminou com a monumental
obra de Bertrand Russel, Principia Mathematica, escrita em colaborao com A.N.
Whitehead, e com os trabalhos de um dos mais destacados matemticos do sculo XX,
David Hilbert, cujas teses fundamentais foram recolhidas em seus Grundlagem des
Mathematik (Fundamentos da Matemtica) escrita em colaborao com Paul Bernais.
Como resultado desta anlise surge esta terceira forma de apresentao das teorias
matemticas, que conforme dito, distingue-se das anteriores ao incluir uma explanao
das bases expressivas e lgicas das teorias matemticas.
49
A forma de apresentao das teorias matemticas est estreitamente vinculada
com as conceies filosficas a respeito do objeto e do mtodo da matemtica e da
relao entre matemtica e realidade. A partir da segunda metade do sculo XIX
podemos caracterizar trs grandes correntes nos fundamentos da matemtica:
LOGICISMO, FORMALISMO e INTUICIONISMO. Esta classificao simplifica e
resume uma variedade maior de idias do pensamento matemtico, mas permite
compreender as questes bsicas que norteiam a construo do conhecimento, a
pesquisa e o ensino na matemtica. A seguir damos uma breve descrio destas trs
correntes.
20. PROVAS. MTODOS DE DEMONSTRAO DE TEOREMAS
20.1. PROVAS.
Segundo o dicionrio Houaiss, prova aquilo que demonstra que uma afirmao
ou um fato so verdadeiros; evidncia, comprovao e demonstrao qualquer
recurso capaz de atestar a veracidade ou a autenticidade de alguma coisa; prova;
raciocnio que torna evidente o carter verdico de uma proposio, idia ou teoria.
Como vemos, na lngua portuguesa, prova e demonstrao so sinnimos.
O conceito de prova envolve aspectos de natureza filosfica e lgica. Poderamos
nos perguntar: O que uma prova? Como reconhecer que uma proposio matemtica
foi provada ou demonstrada? De que maneira uma prova ou demonstrao matemtica
difere de uma prova em uma outra rea do conhecimento, por exemplo, de uma prova
em um tribunal de justia?
A maior parte dos matemticos no se preocupa em clarificar precisamente tais
noes, porque no julgam necessrio. Eles sabem intuitivamente o que uma prova
correta e o que no . Mas de onde vem esta intuio? um resultado da intuio e da
correo durante o aprendizado da matemtica, cada gerao passando prxima um
modo de se expressar matematicamente, uma cultura matemtica. As culturas mudam,
entretanto, e os padres utilizados em provas so agora muito diferentes dos usados no
tempo de Euclides ou no sculo XVII, quando o Clculo foi desenvolvido por Newton e
Leibniz. A maioria dos matemticos acredita que o padro mais alto agora, que
fazemos matemtica melhor que qualquer gerao anterior.
Uma prova em matemtica diferente de uma prova num tribunal de justia, no
pela virtude de apelar para termos especializados ou para formas de comunicao
rgidas, porque a lei tambm o faz, mas sim pelas formas particulares de prova que so
consideradas aceitveis. Consideraremos como sinnimos os conceitos de prova e
demonstrao, embora alguns autores prefiram considerar uma demonstrao como uma
verso informal de uma prova, que comunica as idias gerais a partir das quais a prova
pode ser reconstruda.
Apresentaremos as formas de prova que so fundamentais em matemtica,
esclarecendo que todas elas so casos particulares de uma definio formal de prova,
que escapa do escopo de uma disciplina introdutria como esta.
20.2. MTODOS DE DEMONSTRAO DE TEOREMAS.
50
Sabemos que um teorema uma relao de inferncia entre um conjunto de
premissas que constituem a hiptese, H, do teorema e uma proposio T, que a tese do
teorema. Simbolicamente, o teorema representado como HT. H e T so
frequentemente proposies compostas, pelo que, s vezes, se diz as hipteses do
teorema ou as teses do teorema.
A notao HT utilizada, como sabemos, para indicar uma implicao ou
inferncia lgica, mas existe uma diferena entre um teorema matemtico e uma
inferncia em lgica pura. Em lgica no interessa se as proposies que aparecem em
H ou T so intrinsecamente verdadeiras ou falsas, unicamente importa que se H
verdadeira ento isso implica que T verdadeira; ou seja, para a lgica o importante a
relao de inferncia entre H e T. Num teorema matemtico, alm da importante relao
de inferncia entre H e T, importa a natureza particular das proposies que formam H e
T e seu sentido no contexto da teoria matemtica onde o teorema est inserido.
Lembremos que um teorema uma clula de conhecimento matemtico. Na
demonstrao dos teoremas podemos aplicar todos os recursos da lgica, em particular
as conhecidas equivalncias e as regras de inferncia da lgica.
Uma boa demonstrao deve ser clara, rigorosa e o mais concisa possvel. Alm
das qualidades puramente tcnicas a demonstrao de um teorema tem muito de arte.
Beleza e elegncia so tambm atributos de uma demonstrao. Os que gostamos da
Matemtica curtimos certas demonstraes com emoes similares s de um apreciador
de uma pintura ou de uma sinfonia. Da mesma forma que os pintores em formao
estudam as diferentes tcnicas para pintar uma tela, por exemplo, aquarela ou leo, nos
devemos estudar os diferentes mtodos e tcnicas para demonstrar um teorema.
Os principais mtodos ou tipos de demonstrao em matemtica so:
- A demonstrao direta.
- Demonstrao pelo Contra-positivo.
- A demonstrao por reduo ao absurdo.
- A demonstrao por induo completa ou por recorrncia.
Explicaremos, a seguir, cada um destes mtodos.
20.3. DEMONSTRAO DIRETA
Na demonstrao direta estabelecemos uma seqncia finita de inferncias, a
partir da hiptese, at chegar tese. Podemos representar a idia da demonstrao direta
assim:
HP
1
P
2
...P
n
T
Ou seja, de H infere-se P
1
, de P
1
infere P
2
, assim sucessivamente, de P
n
infere-se T.
A seguir apresentamos um exemplo de demonstrao direta de um teorema.
Teorema: Se a e b so nmeros reais tais que a=0 e ab=0, ento, b=0.
A primeira questo distinguir as hipteses e a tese do teorema. As hipteses
deste teorema reduzem-se a quatro proposies simples:
51
1. p: a um nmero real.
2. q: b um nmero real.
3. r: a=0.
4. s: ab=0.
Formalmente, a hiptese H a proposio composta p.q.r.s. A tese a proposio
simples w: b=0. O teorema a implicao lgica: p.q.r.s w.
Estudando as hipteses vemos que (1) e (2) nos dizem qual o conjunto de
elementos com os que estamos tratando, neste caso, o corpo comutativo dos nmeros
reais. Devemos pensar que temos a nosso dispor as propriedades conhecidas das
operaes desta estrutura, particularmente as relativas ao produto, que a operao
sobre a que trata o teorema. No crebro sero ativados os conhecimentos associados,
como abrir uma gaveta de ferramentas e dar uma olhada para decidir quais sero
utilizadas.
Evidentemente, o primeiro que vem mente que o conjunto dos nmeros reais
sem o zero um grupo abeliano para a operao de multiplicao, isto , a
multiplicao possui as propriedades: associatividade, comutatividade, existncia de
elemento neutro (o nmero 1), e todo nmero diferente de zero tem inverso.
A hiptese (3) nos sugere que existe o inverso de a, a
-1
, tal que aa
-1
=1. A
hiptese (4) uma igualdade cujo lado direito zero e cujo lado esquerdo contm o
nmero b como fator, isto sugere trabalhar a igualdade para tentar chegar a b=0. Uma
idia seria multiplicar ambos os lados da igualdade ab=0 pelo a
-1
. Como o fator a est
esquerda multiplicamos por a
-1
esquerda para procurar o produto aa
-1
=1, vejamos:
[ae. a=0 ][-a
-1
e| aa
-1
=1], Justificativa: todo nmero real diferente de
zero tem inverso multiplicativo.
(ab=0).(-a
-1
e) a
-1
(ab)= a
-1.
0, Justificativa: vlida a propriedade: Se p,
q, re, p=q, ento, pr=qr, neste caso multiplicamos ambos os lados de ab=0 por a
-1
.
a
-1
(ab)=a
-1.
0 (a
-1
a)b=0, Justificativa: Associatividade da multiplicao de
nmeros reais e a propriedade de que todo nmero vezes zero igual a zero.
(a
-1
a)b=0 1.b=0 , Justificativa: sabemos que aa
-1
=1.
1. b=0 b=0, Justificativa: 1 o elemento neutro da multiplicao.
Como chegamos tese, o teorema est provado. No necessrio escrever a
demonstrao com tanto simbolismo, poderamos escrever numa linguagem mais
coloquial. Eis uma variante neste molde:
Demonstrao:
Por ser a=0, existe seu inverso a
-1
. Multiplicando ambos os lados de ab=0 por a
-1
temos a
-1
(ab) = a
-1.
0. Pela associatividade da multiplicao e por ser a
-1.
0 = 0, tem-
se
(a
-1
a)b=0, de onde 1b=0, e, b=0 conforme queramos provar.
20.4. DEMONSTRAO PELO CONTRA-POSITIVO
Sabemos que todo teorema HT equivalente ao seu teorema contrapositivo
~T ~H. O mtodo consiste em demonstrar o contrapositivo. Como uma conseqncia
lgica tem-se a validade do teorema direto. A prova pelo contrapositivo recomendada
quando resulta mais fcil que provar diretamente o teorema original.
52
Exemplo: Se a
2
um inteiro par, ento a um inteiro par.
Hiptese do teorema: ae; a
2
par.
Tese do teorema: a par.
O teorema contrapositivo : Se a um inteiro impar ento a
2
impar.
Demonstrao do teorema contrapositivo:
ae, a impar -ke | a = 2k+1.
a = 2k+1 a
2
= (2k+1)
2
= 4k
2
+4k+1= 2(2k
2
+2k)+1.
Como 2k
2
+2ke resulta que a
2
impar.
Portanto, o teorema direto verdadeiro.
20.5. DEMONSTRAO POR REDUO AO ABSURDO
Suponhamos que queremos provar uma sentena P. O mtodo de demonstrao
indireta, chamado tambm de mtodo por reduo ao absurdo (reductio ad
absurdum) ou de prova por contradio, consiste em supor a negao de P, ~P, e
deduzir uma contradio C. A contradio C geralmente do tipo R.~R, onde R
qualquer proposio que inclua a P, um dado axioma da teoria ou algum teorema j
demonstrado.
Formalmente, o mtodo se fundamenta na tautologia ~P . (R.~R) P, que
recomendamos provar.
Intuitivamente, P pode ser verdadeira ou falsa, mas no ambas. Se assumimos
sua negao ~P como verdadeira e isto conduz a uma proposio simultaneamente
verdadeira e falsa (R), ento somente pode ocorrer que P verdadeira.
Exemplo: Demonstrao ao absurdo da proposio P: 2 no um nmero
racional.
Suponhamos que a negao de P verdadeira, ou seja, suponhamos que 2
um nmero racional. Ento 2 pode ser representado por uma frao irredutvel, isto ,
existem inteiros no nulos p e q tais que 2
p
q
= e nenhum nmero diferente de 1 divide
a p e q. Temos 2 p q = , p
2
=2q
2
. Logo, p
2
par e p , portanto, par tambm. Por ser
irredutvel a frao
p
q
tem-se que q impar.
Por ser p par, existe re tal que p = 2r. Substituindo em p
2
=2q
2
resulta 4r
2
=2q
2
,
de onde q
2
=2r
2
. Esta ltima igualdade significa que q
2
par, portanto, q par.
Contradio: q par e impar! Portanto, q no racional. O teorema est
provado.
Nota: Observe que a proposio R q impar e ~R q par. De P obtemos
R . ~R, que uma contradio.
Se P um teorema HT temos que HT ~H v T.
53
Ento, ~(HT) ~(~Hv T) ~(~H) . ~T H . ~T.
Por conseguinte, para provar HT pelo absurdo supomos a hiptese, H, e a
negao da tese, ~T. A partir de H . ~T devemos chegar a uma contradio C. A
contradio C pode ser a negao de uma das premissas do teorema. Assim, se H
P
1
.....P
m
e chegarmos a ~P
k
, com 1 s k s m, temos a contradio P
k
. ~P
k
. Tambm pode
ser a contradio com um dado axioma da teoria ou algum teorema j demonstrado.
Resumindo, a prova pelo absurdo do teorema HT consiste em:
(1) Assumirmos a negao da tese ~T.
(2) Considerarmos a conjuno entre a hiptese do teorema e a negao da sua
tese, ~T . H, e inferirmos uma contradio C. Ou seja, ~T . H Contradio,
logo ~T . H F.
(4) Se ~T . H falsa, sua negao verdadeira. Isto ,
~(~T . H) V. Aplicando a lei de De Morgan ~(~T . H) T v ~H V.
Mas, T v ~H ~(~T) v ~H ~T ~H, logo, ~T ~H um teorema
verdadeiro.
(5) Como ~T ~H o teorema contrapositivo de H T, resulta que est
demonstrado o teorema.
Na prtica, para demonstrar um teorema pelo absurdo basta negar a tese e
deduzir uma contradio a partir da conjuno da hiptese com a negao da tese.
Observemos que existe uma estreita relao entre provar um teorema pelo
contrapositivo ou pelo absurdo. Em muitos livros existe certa confuso, sem maiores
conseqncias, entre ambos os mtodos, que so equivalentes para uma proposio
do tipo HT. Na prova pelo contrapositivo se demonstra pelo mtodo direto que
~T~H. Na prova pelo absurdo se assume ~T . H e se obtm uma contradio.
A prova pelo absurdo tem um alcance maior, pois permite provar proposies
que no tm a forma HT, como a do exemplo sobre a irracionalidade de 2 .
Exemplo: Demonstrao pelo absurdo do teorema: Se a e b so nmeros reais tais que
a=0 e ab=0, ento, b=0.
Hipteses: (1) a,be; (2) ab=0; (3) a=0. Tese: (4) b=0.
Negao da Tese: (5) b=0.
Demonstrao:
Assumimos H . ~T: (1) . (2) . (3) . (5).
Por ser b=0, existe seu inverso b
1
.
Multiplicando ambos os lados de (2) por b
1
: (ab)b
1
= 0 . b
1
.
Como 0 . b
1
= 0, resulta (ab)b
1
= 0.
Pela propriedade associativa (ab)b
1
= a(bb
1
) = a(1) = a. Logo a=0.
Chegamos contradio a=0 . a=0.
Portanto, o teorema est demonstrado.
A demonstrao indireta comumente utilizada quando resulta mais clara
simples e curta que a direta. Caso contrrio prefervel a demonstrao direta.
54
20.6. DEMONSTRAO POR INDUO MATEMTICA
Este mtodo de demonstrao exclusivo da matemtica e utilizado em
proposies que envolvem alguma propriedade relativa a um nmero natural, por
exemplo, o seguinte teorema: A soma dos n primeiros nmeros naturais igual a
( 1)
2
n n +
.
No devemos confundir a induo matemtica com a induo que poderamos
chamar de induo ordinria para evitar confuses. A induo ordinria, ou
simplesmente induo, foi apresentada no pargrafo intitulado Deduo e Induo
com o exemplo: Joguei uma pedra no lago, e a pedra afundou; Joguei outra pedra no
lago e ela tambm afundou; joguei mais uma pedra no lago, e tambm esta afundou;
Logo, se eu jogar uma outra pedra no lago, ela vai afundar. Um argumento indutivo
no fornece uma prova, simplesmente, oferece uma concluso razovel, mas precria,
que pode ser falsa. A induo ordinria no prova nenhum teorema matemtico, apenas
pode sugerir uma conjectura. um erro comum que alguns alunos considerem a
apresentao de exemplos que satisfazem um dado teorema como uma prova.
Pelo contrrio, a induo matemtica constitui uma prova dedutiva rigorosa.
Em que consiste o mtodo de induo matemtica?
Na aritmtica se faz uma fundamentao axiomtica dos nmeros naturais. Um
dos axiomas o chamado Axioma de Induo, que pode ser enunciado assim:
Axioma de Induo: Seja S um subconjunto de tal que: i) 1eS; ii) n, neSn+1 eS.
Ento, S=.
Do Axioma de Induo segue-se o seguinte teorema:
Teorema (Principio de Induo Matemtica): Sejam ae e P(n) uma
sentena aberta em ne. Suponha que: (i) P(a) uma proposio verdadeira. (ii) n >
a, P(n) P(n + 1). Ento, P(n) verdadeira para todo n > a.
O mtodo de induo matemtica, fundamentado no teorema acima, para
provar que a proposio P(n) vlida para todo n>k, ke; consiste em:
1. Provar que P(k) verdadeira.
2. Provar a inferncia P(n)P(n+1). Isto , se a proposio verdadeira para n,
ento, verdadeira par n+1.
Como exemplo, provemos por induo completa o teorema A soma dos n
primeiros nmeros naturais igual a
( 1)
2
n n +
. Ou seja, provemos a validade da
frmula 1 + 2 + . + n =
( 1)
2
n n +
, para todo ne .
55
Passo 1 da induo:
Para n=1: 1=
1(1 1)
2
+
=1. Logo, a propriedade certa para n=1.
Passo 2 da induo:
Provemos que P(n) P(n+1), isto , provemos que:
1+2+.+n=
( 1)
2
n n +
1+2+.+n+(n+1)=
( 1)( 2)
2
n n + +
Prova: 1+2+.+n=
( 1)
2
n n +
1+2+.+n+(n+1)=
( 1)
2
n n +
+(n+1) (somando n+1 a
ambos os lados de 1+2+.+n=
( 1)
2
n n +
).
Efetuando a soma indicada:
( 1)
2
n n +
+(n+1)=
2
n(n+1)+2(n+1) 2 2
2 2
n n n + + +
= =
=
2
3 2
2
n n + +
=
(n+1)(n+2)
2
. Portanto, provamos que P(n+1) certa e est
provado o teorema.
Como aplicao, calculemos a soma dos primeiros mil nmeros naturais,
1+2+.... +1000. Substituindo n=1000 na frmula, temos que:
1+2+....+1000=
1000(1000 1)
2
+
=5005.
O Principio da Induo Matemtica no somente oferece um mtodo de
demonstrao de propriedades concernentes aos nmeros naturais, mas tambm, um
procedimento de definio de novos conceitos referentes a este conjunto numrico,
denominado definio por recorrncia. A definio por recorrncia de um objeto E(n),
com ne, consiste em comear a definio por um primeiro nmero ae, ou seja, se
diz quem E(a), e a seguir se da um procedimento para obter o n-simo elemento, E(n),
a partir do anterior, E(n-1).
Exemplo 1: Definamos uma progresso geomtrica (x
n
) por: x
1
= qe, x
n
=x
n
-
1
. q.
Tambm, pode-se definir uma expresso E(n) por recorrncia atravs de uma
dada funo avaliada em vrios termos anteriores, E(n-1), E(n-2), ... , E(n-r), desde
que se conheam as expresses E(1), E(2), ... , E(r). Observe o exemplo a seguir.
Exemplo 2: A seqncia u
n
dos nmeros de Fibonacci definida por u
1
=1, u
2
=1,
u
n
=u
n
-
1
+u
n
-
2
. Os nmeros desta seqncia possuem propriedades aritmticas notveis
que ainda hoje so objeto de pesquisa.
Os trs mtodos de demonstrao descritos constituem as trs formas de prova
que so fundamentais em matemtica e devem ser conhecidas e aplicadas com
habilidade por qualquer um que aspire a ser um matemtico profissional.
Lamentavelmente, no ensino pr-universitrio negligenciada a demonstrao dos
teoremas, e a matemtica despojada da beleza de seu mtodo hipottico-dedutivo,
sendo apresentada mais como uma coleo de receitas de procedimentos mecnicos.
56
A seguir mostramos algumas classificaes de provas de teoremas, que no
constituem propriamente novos mtodos de demonstrao, mas apresentam certas
caractersticas particulares que podem ser destacadas.
20.7. PROVA POR CONSTRUO
Em matemtica h teoremas que estabelecem a existncia de determinado objeto
ou entidade matemtica. Para provar que alguma coisa existe pode-se constru-la. Uma
prova por construo uma prova onde construdo o objeto cuja existncia queira-se
provar.
Exemplo 3: Provar que a equao x
3
+ 1990y
3
= z
4
tem infinitas solues inteiras
com x>0, y>0 e z>0.
Demonstrao:
Consideremos x=y. Ento x
3
+ 1990y
3
= z
4
1991x
3
=z
4
Seja x=1991
t
, ento 1991x
3
=z
4
(1991)( 1991
t
)
3
= z
4
1991
3t+1
= z
4
Para ser z inteiro basta que 3t +1 seja mltiplo de 4. De fato, existem infinitos
valores inteiros positivos t tais que 3t +1 mltiplo de 4. Tomemos t = 4m+1, com
me{1,2,3,...}=, ento 3t +1= 3(4m+1) = 12m + 4 = 4(3m+1) que mltiplo 4.
Portanto, x = y = 1991
4m+1
, z = 19913
m+1
, com m=1,2,3,..., so infinitas
solues inteiras positivas da equao x
3
+ 1990y
3
= z
4
. O teorema est provado.
Observao: Provamos a existncia, mas no que as solues construdas sejam
as nicas solues da equao.
Na prova de alguns teoremas podemos construir determinado ente matemtico
que no aparece no seu enunciado, mas que facilita a demonstrao. Isso
relativamente freqente, mas no exclusivo, em alguns teoremas de geometria. Tais
construes so, s vezes, chamadas de construo auxiliar. Por exemplo, provemos o:
Teorema: Em todo tringulo a soma dos ngulos interiores igual a dois
ngulos retos.
Demonstrao:
Seja um tringulo ABC qualquer. Devemos provar que ZCAB + ZACB +
ZBCN = 2R.
Construo auxiliar: Tracemos pelo vrtice C uma reta MN paralela ao lado
AB.
M C N
A B
57
Tem-se (1): ZMCA + ZACB + ZBCN = 2R, por serem ngulos adjacentes.
ZMCA=ZCAB e ZBCN=ZABC, por serem alternos internos entre paralelas.
Substituindo em (1): ZCAB + ZACB + ZBCN = 2R.
20.8. PROVA POR CONTRA-EXEMPLO
A prova por contra-exemplo relacionada prova por construo. Para provar
que uma dada proposio sobre uma classe de objetos no verdadeira, basta apenas
exibir um elemento da classe para o qual falhe a propriedade.
Exemplo: Prove que a aplicao f :, f(x) = x
4
+ 1 no injetora.
Temos que 1, -1e, f (1)=2 e f(-1)=2; logo f no injetora.
21. COROLRIOS E LEMAS
Na literatura matemtica aparece frequentemente os termos corolrio e lema. Os
lemas e os corolrios so teoremas. A seguir esclarecemos em que consiste cada um
deles.
Um corolrio um teorema que uma conseqncia de um outro teorema
precedente considerado como principal. O corolrio se desprende do teorema principal,
sua demonstrao simples, ou at praticamente evidente, assumindo o teorema
principal. O dicionrio Houaiss das como acepes da palavra corolrio: (1) verdade
que decorre de outra, que sua conseqncia necessria ou continuao natural; (2)
proposio que deriva, em um encadeamento dedutivo, de uma assero precedente,
produzindo um acrscimo de conhecimento por meio da explicitao de aspectos que,
no enunciado anterior, se mantinham latentes ou obscuros.
Exemplo: Consideremos o seguinte
Teorema: Se uma reta ao cortar a dois lados de um tringulo os divide em segmentos
proporcionais, ento paralela ao terceiro lado.
Assumiremos que este teorema, que verdadeiro, est demonstrado. Ilustremos
com uma figura seu enunciado e separemos a hiptese e a tese:
Hiptese: ABC tringulo qualquer; MeAB; NeAC;
AM AN
MB NC
= .
Tese: MN || BC.
Corolrio: O segmento que une os pontos meios de dois lados de um tringulo
paralelo ao terceiro lado.
58
Demonstrao (utilizando a mesma figura): No tringulo ABC, seja M o ponto meio de
AB, ento
AM
MB
=1. Seja N o ponto meio de AC, logo
AN
NC
=1. Portanto,
AM AN
MB NC
= .
Pelo teorema anterior tem-se MN || BC.
Um lema um teorema cuja importncia principal estabelecer uma proposio
a ser usada na demonstrao de outro teorema posterior, considerado, tal vez, mais
importante. Os lemas facilitam a escrita e a compreenso do teorema principal, servem
para encurtar a prova de um teorema.
Exemplo (tomado de Anlise Real, Volume 2, de Elon Lages, pgina 66):
Lema 1: Sejam Xc
m
um conjunto arbitrrio e Kc
n
compacto. Fixemos x
0
eX.
Se f : XK
p
contnua ento, para todo c > 0 dado, pode-se obter o > 0 tal que xeX
e |x- x
0
| < o implicam |f(x,t) -f(x
0
,t) < c, seja qual for te K.
Este lema utilizado para demonstrar o teorema seguinte:
Teorema 3 (Derivao sob o sinal de integral): Dado Uc
n
aberto, seja
f:U[a,b] contnua, tal que a i-sima derivada parcial ( , )
i
f
x t
x
c
c
existe para todo
ponto (x,t) e U[a,b] e a funo
i
f
x
c
c
: U[a,b] , assim definida, contnua. Ento
a funo : U , dada por (x) = ( , )
b
a
f x t dt
}
, possui a i-sima derivada parcial em
cada ponto xeU, sendo ( ) ( , )
b
i i a
f
x x t dt
x x
c c
=
c c
}
.
Tambm pode ser chamado de lema um teorema que ser muito usado para
provar outros diversos teoremas. Por exemplo, o conhecido Lema de Cauchy-Schwarz:
Para quaisquer nmeros reais a
k
e b
k
, k = 1, 2, 3,..., n, tem-se a desigualdade
2 2
1 1 1
n n n
i i i i
i i i
a b a b
= = =
s
.
Segundo o dicionrio Houaiss, lema significa: (1) proposio preliminar cuja
demonstrao prvia necessria para demonstrar a tese principal que se pretende
estabelecer; (2) em sentido figurado, significa norma ou sentena, geralmente curta, que
resume um ideal, objetivo etc.
PERGUNTAS PARA O ESTUDO DA TEORIA
Estas perguntas tm o objetivo de orientar o estudo da teoria e a elaborao de
um resumo das principais questes tericas, de conhecimento necessrio para resolver
59
os exerccios. Para estudar a teoria voc deve ler a apostila na ntegra e depois responder
as perguntas. Lembre que necessrio memorizar as definies, teoremas e algoritmos
para ter xito na resoluo dos exerccios. Prtica sem teoria no funciona na
Matemtica desde a poca dos antigos sbios matemticos gregos (Tales, Pitgoras,
Euclides, etc.). Ainda uma recomendao: muito conveniente consultar as fontes
bibliogrficas indicadas, para aprofundar no conhecimento dos temas tratados, e no se
limitar aos apontes dado pelo professor. Este conjunto de perguntas no esgota a teoria
apresentada nas aulas, nem constitui a nica forma de perguntar a teoria nas avaliaes.
1. Explique brevemente de que trata a Lgica.
2. Qual a diferena entre a Lgica Clssica e a Lgica Matemtica?
3. O que uma proposio?
4. Enuncie os Princpios da no Contradio e do Tero Excludo.
5. Qual a problemtica abordada no clculo proposicional?
6. Descreva o conceito de conectivo lgico na lgebra de proposies. Defina, mediante
tabelas-verdade, os cinco conectivos.
7. O que uma proposio composta?
8. Explique os conceitos de tautologia, contradio e contingncia.
9. Defina o conceito de proposies lgicas equivalentes.
10. Enuncie principais leis da lgebra Proposicional. Como podem ser demonstradas?
11. Explique os algoritmos dados para definir a precedncia das operaes no clculo
proposicional.
12. Defina o conceito de proposies duais. Explique em que consiste o principio de
dualidade.
13. Defina os conceitos de argumento, silogismo e sofisma.
14. Explique os conceitos de argumento dedutivo e argumento indutivo. Qual destes
dois tipos de argumentos utilizado na construo do conhecimento matemtico?
15. Relate quais os mtodos para provar que um argumento vlido ou no-vlido
(invlido)?
16. Escreva uma relao das principais regras de inferncia utilizadas na demonstrao
dos argumentos.
17. Em que consiste o mtodo de demonstrao por reduo ao absurdo, tambm
chamado de mtodo indireto?
60
18. Explique como facilitar a demonstrao de um argumento quando a concluso tem
a forma pvq, p.q, pq, pq.
19. Defina os conceitos de sentena aberta, predicado, varivel, conjunto universo e
conjunto verdade de uma sentena aberta, em uma e em vrias variveis.
20. Qual o conjunto verdade das sentenas abertas ~P(x), P(x).Q(x), P(x)vQ(x),
P(x)Q(x), P(x)Q(x), em funo do conjunto-verdade das sentenas abertas P(x) e
Q(x)?
21. O que representam os smbolos , $ e $!? Que nome recebem?
22. Suponha que P(x) uma sentena aberta com xeU={u
1
,...,u
m
}. O que significa que
as sentenas abertas xeU, P(x) e $xeU| P(x) so verdadeiras, em termo dos valores
lgicos das proposies P(u
1
), .... , P(u
m
)?
23. Qual a negao de xeU, P(x) e $xeU| P(x)?
24. Quando podemos e quando no podemos comutar quantificadores numa sentena
aberta?
25. Como negar sentenas com mais de um quantificador?
26. O que uma implicao lgica?
27. O que um teorema em Matemtica?
28. Qual a diferena entre PQ (conetivo condicional) e PQ (teorema)?
29. O que uma definio em Matemtica? Qual a sua utilidade?
30. O que um axioma?
31. Dado um teorema, HT, o que entendemos por seu: teorema recproco, teorema
contrrio e teorema contrapositivo (contra-recproco)?
32. O que significam, em termos de implicaes lgicas, as oraes: (1) H suficiente
para T; (2) H necessria para T; (3) H necessria e suficiente para T; (4) H equivale
a T; (5) H se e somente se T; (6) Se H ento T.
33. Qual a relao lgica entre um teorema e seu teorema contrapositivo?
34. A partir da validade de um teorema, podemos inferir a validade de seu teorema
recproco? Exemplifique.
35. A partir da validade de um teorema, podemos inferir a validade de seu teorema
contrrio? Exemplifique.
61
36. Quais mtodos de demonstrao de teoremas voc conhece?
37. Em que consiste o mtodo de demonstrao direta de um teorema?
38. Em que consiste o mtodo de demonstrao indireta, ou por reduo ao absurdo, de
um teorema?
39. Em que consiste o mtodo de demonstrao por Induo Matemtica de um
teorema? A que tipo de proposies aplicvel este mtodo de demonstrao?
40. O que um prova por construo?
41. O que uma prova por contra-exemplo?
42. Quais as trs formas estudadas de apresentar uma teoria matemtica? Descreva cada
uma delas.
EXERCCIOS
1. Determinar o valor lgico (V ou F) de cada uma das seguintes proposies:
(a) O nmero 17 primo. (b) (3+5)
2
=3
2
+5
2
. (c) O valor archimediano de t
22
7
. (d) As
diagonais de um paralelogramo so iguais. (e) 0,13131313... uma dzima peridica
simples. (f) O hexaedro regular tem 8 arestas. (g) As razes da equao x
3
1=0 so todas
reais. (h) A expresso n
2
n+41 (ne) s produz nmeros primos. (i) Todo nmero
divisvel por 5 termina em 5.
2. Sejam as proposies p: Est frio e q: Est chovendo. Traduzir para a linguagem
natural as seguintes proposies:
(a) ~p. (b) p.q. (c) pvq. (d) qp. (e) p~q. (f) pv~q. (g) ~p.~q. (h) p~q.
(i) p.~qp.
3. Sejam as proposies p: Suely rica e q: Suely feliz. Assuma que a negao de ser
rica ser pobre e a de ser feliz ser infeliz. Traduzir para a linguagem simblica as
seguintes proposies:
(a) Suely pobre, mas feliz. (b) Suely rica ou infeliz. (c) Suely pobre e infeliz. (d)
Suely pobre ou rica, mas infeliz.
4. Sejam as proposies: p: O rato entrou no buraco; q: O gato seguiu o rato. Forme
sentenas, na linguagem natural, que correspondam s proposies seguintes:
a) ~p; b) ~q; c) q.p; d) qvp; e) q.~p; f) pv~q; g) ~(p.q); h) ~(pvq); i) ~p.~q;
j) ~pv~q; k) ~(~p); l) ~(~q).
5. Considere as sentenas: p: Tales filho de Wilson; q: Tales neto de Jos.
Escreva na forma simblica cada uma das sentenas seguintes:
a) Tales no filho de Wilson. b) Tales no neto de Jos. c) No verdade que Tales
no filho de Wilson. d) No verdade que Tales neto de Jos. e) Tales filho de
62
Wilson e neto de Jos. f) Tales filho de Wilson ou neto de Jos. g) Tales no filho
de Wilson e neto de Jos. h) Tales filho de Wilson e no neto de Jos. i) Tales no
filho de Wilson ou no neto de Jos. j) No verdade que Tales filho de Wilson
ou no neto de Jos. k) No verdade que Tales filho de Wilson ou neto de Jos. l)
No verdade que Tales no filho de Wilson ou no neto de Jos. m) Tales no
filho de Wilson nem neto de Jos.
6. Considere as seguintes proposies: p: Hipcia bonita. q: Humberto simptico. r:
Tain inteligente.
Simbolize as seguintes sentenas:
a) Se Humberto simptico, ento, Hipcia bonita.
b) Tain inteligente se Humberto simptico.
c) Hipcia bonita implica Humberto simptico.
d) Tain inteligente se, e somente se, Hipcia bonita.
e) Hipcia bonita condio suficiente para que Humberto seja simptico.
f) Hipcia bonita condio necessria para que Humberto seja simptico.
g) Hipcia bonita condio necessria e suficiente para que Humberto seja
simptico.
7. Traduzir para a linguagem simblica as seguintes proposies matemticas:
(a) x=0 ou x>0. (b) x=0 e y=0. (c) x>1 ou x+y=0. (d) x
2
=x.x e x
0
=1.
(e) (x+y=0 e x>0) ou z=0. (f) x=0 e (y+z>x ou z=0). (g) (x=y e z=t) ou (x<y e z=0).
(h) Se x+y=2 ento z>0. (i) Se x=1 ou z=2 ento y>1. (j) Se x<2 ento x=1 ou x=0.
(k) y=4 e se x<y ento x<5.
8. Simbolizar as seguintes proposies matemticas.
(a) x maior que 5 e menor que 7 ou x no igual a 6.
(b) Se x menor que 5 e maior que 3, ento x igual a 4.
(c) x maior que 1 ou x menor que 1 e maior que 0.
9. Determinar o valor lgico (V ou F) de cada uma das seguintes proposies:
(a) 0>1 . 3 irracional. (b) sen(t)=0 v cos(t)=0. (c)
( )
2
1 1 = . t irracional.
(d) 4 2 1 = v 13 um nmero primo. (e) 3=3 v 5=5. (f) Se 0<1 ento 2
irracional. (g) Se |1|=0 ento
1
6 2
sen
t | |
=
|
\ .
. (h)
0
3 2 2 2 > = . (i)
1 1 25 5 = = . (j) t>43> 5 . (k) 3+4=7 se e somente se 5
3
=125. (l) 1>2
t
2
< 20.
10. Determinar o valor de verdade de cada uma das seguintes proposies:
(a). No verdade que 12 um nmero impar. (b) No verdade que Belm a capital
do Par. (c) falso que 2+3=5 e 1+1=3. (d) falso que 3+3=6 ou 1 0 = .
(e) ~(1+1=2 3+4=5). (f) ~(1+1=5 3+3=1). (g) 2+2=4(3+3=71+1=4). (h)
~(2+2=4 e 3+5=8). (i) 3
4
=81~(2+1=3 . 50=0). (j) 4
3
=64~(3+3=71+1=2)
11. Se p, q e r so proposies verdadeiras e p
1
, q
1
e r
1
so proposies
falsas, quais so as verdadeiras e quais as falsas dentre as proposies seguintes?
a) (rvr
1
).(q
1
vq); b) ~(qvp
1
).~(q
1
vr
1
); c) (~q.r)v~(p.q
1
); d) ~[(~p
1
vp)v(~pvp
1
)];
63
e) ~[(~rvq
1
)v(~q
1
vr)]; f) [p.(qvr)].~[(p.q).(pvr)]; g) p (q
1
r
1
); h) [(qr
1
) q]
r
1
.
12. Determinar o valor lgico V(p) em cada um dos seguintes casos, sabendo que:
(a) V(q)=F e V(p.q)=F. (b) V(q)=F e V(pvq)=F. (c) V(q)=F e V(pq)=F. (d) V(q)=F e
V(qp)=V. (e) V(q)=V e V(pq)=F. (f) V(q)=F e V(pq)=V.
13. Determinar V(p) e V(q) em cada um dos seguintes casos, sabendo que:
(a) V(pq)=V e V(p.q)=F. (b) V(pq)=V e V(pvq)=F. (c) V(pq)=V e V(p.q)=V.
(d) V(pq)=V e V(pvq)=V. (e) V(pq)=F e V(~pvq)=V.
14. Determinar P(VFV) se P(p,q,r)=(pv(qr)) . (~pv r~q).
15. Construir as tabelas-verdade das seguintes proposies:
(a) ~(p.~q); (b) (pq) p.q; (c) (p~q) qp; (d) ~p.rqv~r;
(e) (p.qr) v(~pqv~r). (f) ~(pvq).~(qp); (g) [p(~q.r)].[q.(p~r)];
(h) [(p.q)r]v[~p(q.~r)].
16. Determinar quais das proposies so tautologias, contradies ou contingncias:
a) [pv(p.q)]p; b) (~pv~q)v(pq); c) (pv~q) (p~q); d) p [p (q.~p)]
17. Demonstrar, mediante tabelas-verdade, as seguintes propriedades da lgebra
Proposicional:
a) Lei da negao da negao: ~(~p)p
b) Lei da comutatividade da conjuno: p.qq.p
c) Lei da comutatividade da disjuno: pvqqvp
d) Lei da associatividade da conjuno: p.(q.r)(p.q).r
e) Lei da associatividade da disjuno: pv(qvr)(pvq)vr
f) Primeira lei distributiva: p.(qvr)(p.q)v(p.r)
g) Segunda lei distributiva: pv(q.r)(pvq).(pvr)
h) Primeira lei de De Morgan: ~(p.q)~pv~q
i) Segunda lei de De Morgan: ~(pvq)~p.~q
j) Lei de idempotncia para a conjuno: p.pp
k) Lei de idempotncia para a disjuno: pvpp
18. Determinar quais das seguintes proposies so tautologias, contradies ou
contingentes.
(a). p(~pq); (b) ~p vq (pq); (c) p (q(qp)); (d) ((pq) q) p;
(e). p v ~q (p ~q); (f) ~p v ~q ( p q); (g) p ( p v q) v r;
(h) p . q ( p q v r). (i) (p . q) . ~(p v q)
19. Demonstrar que o conectivo v (ou exclusivo) exprime-se em funo dos trs
conectivos ~, . e v do seguinte modo: pvq (pvq) . ~(p.q). (Alencar, pg. 64).
20. Achar o dual das frmulas bem formadas: (Bueno-Garcia, pg. 120).
(a) ~(pvq); (b) ~~( pq); (c) p~q; (d) ~~(pq); (e) (p~q) . ~(~q.q).
21. Demonstrar aplicando o mtodo dedutivo: (Alencar, pg. 79 e seguintes).
64
(a) (pq) . ~q ~p (Modus Tollens); (b) (pvq) .~p q (Silogismo disjuntivo);
(c) p.q pvq; (d) p qp; (e) p ~pq; (f) pq p . rq;
(g) p.q r p(qr); (h) (pq) v (pr) p q v r.
22. Sejam as sentenas abertas em A={1,2,3,4,5,6,7,8,9}: p(x): x
2
eA e q(x): x
par. Determine o conjunto-verdade das sentenas abertas:
a) p(x) . q(x); b) p(x)vq(x); c) p(x) q(x); d) q(x) p(x); e) p(x)q(x).
23. Dados os conjuntos A={2,3,7} e B={3,6,8,9,13}, determinar o conjunto-verdade da
sentena aberta x divide y em AxB.
24. Determinar o conjunto-verdade em das sentenas abertas:
a) 24x
2
2x 15=0 v 12x
2
+ x 6 =0 ; b) 3x 4s0 . x + 2 > 0.
25. Defina o conceito de nmero inteiro par e impar e prove que: (a) a soma de dois
inteiros pares um inteiro par; (b) o produto de dois inteiros pares um inteiro par.
Qual mtodo de demonstrao voc utilizou?
26. Seja x uma varivel real no sentido conhecido em clculo. Seja P(x) uma
propriedade de x. Considere as sentenas a seguir:
1. P(x) vlido para alguns x.
2. P(x) vlido para um x.
3. P(x) vlido para todo x.
4. Existe algum x tal que P(x) vlido.
5. P(x) vlido para ao menos um x.
6. Existe um nico x tal que P(x) vlido.
7. P(x) vlido para mais de um x.
8. No existe x tal que P(x) vlido.
9. P(x) falso para todo x, exceto um.
10. P(x) falso para todo x, exceto dois.
11. P(x) falso para todo x.
Algumas das sentenas acima so logicamente equivalentes. Separe as sentenas em
grupos, de forma que todas as que pertencem ao mesmo grupo sejam equivalentes.
27. Julgar as seguintes proposies:
1) (xe)(x+7>5); 2) (xe)(x+2>6); 3) (xe)(x
2
>0); 4) (-xe)(x+3<7);
5) (-xe)(x+6<4); 6) (-xe)( x
2
<0); 7) (xe)(5x7=0); 8) (-xe)(3x2=0);
9) (xe)( |x|=x ); 10) (-xe)( x
2
=x );
28. Negar as sentenas (no se preocupe em julgar se so V ou F):
1) (xe)(x+7>5); 2) (xe)(x+2<6); 3) (xe()(x
2
>0); 4) (-xe)(x+3s7).
5) (-xeA)(x+3=10); 6) (xe)( |x|=x ); 7) (-xe)(x
2
=x);
8) (-xe)(x+3<9 . x4= 2); 9) (-xe)(x+3>9 v x4s 2);
65
10. (xe)(x+4>5 v x
2
<10); 11) AcB (Lembre a definio: AcB [xeAxeB]);
12) p(x)q(x) (Utilize o smbolo que indica a negao da implicao);
13) A aplicao f:AB contnua em A (Lembre a definio: A aplicao f:AB
contnua em A se contnua em todo ponto de A).
29. Dados os seguintes teoremas, indique as proposies simples que a integram, e
reescreva o enunciado em forma simblica, utilizando o smbolo separando hiptese
e tese. [Observao: Assumimos a notao onde as letras maisculas representam
pontos e as letras minsculas representam retas do plano.]
Proposio 1: Quaisquer que sejam os pontos A e B do plano, se A distinto de B,
ento existe uma reta a que contm ambos os pontos A e B.
Proposio 2: Quaisquer que sejam os pontos A e B e as retas a e b, se A distinto de
B e A e B pertencem a a e a b, ento, a=b.
Proposio 3: Se trs vetores so coplanares, um deles combinao linear dos outros
dois.
Proposio 4: Se desde um ponto exterior a uma reta se traam uma perpendicular e
uma oblqua, o segmento de perpendicular compreendido entre o ponto e a interseo
com a reta menor que o segmento da oblqua compreendido entre o ponto e a reta.
Proposio 5: Os ngulos adjacentes so suplementares, isto , sua soma igual a dois
ngulos retos.
Proposio 6: Se uma reta perpendicular a outra, tambm perpendicular s suas
paralelas.
30. Considere o teorema: O centro de um grupo um subgrupo normal do grupo. Para
entender este teorema voc precisaria conhecer quais definies? Procure-as num livro
de lgebra. Separe hiptese e tese do teorema.
31. Considere o teorema: Suponhamos que a funo f est definida, cresce (ou
decresce) estritamente e contnua no intervalo [a,b], ento, existe a funo inversa f
1
sobre o intervalo de extremidades f(a) e f(b) e cresce (ou decresce) estritamente e
contnua sobre este intervalo. Para entender este teorema voc precisaria conhecer
quais definies? Procure-as num livro de Analise. Separe hiptese e tese do teorema.
32. Dados os teoremas seguintes, a) enuncie os teoremas recproco, contrrio e
contrapositivo, b) caso o recproco seja um teorema verdadeiro, enuncie o teorema que
inclui ambos os teoremas, direto e recproco.
Teorema 1: Se num crculo tem-se ngulos centrais iguais, ento, as cordas que estes
interceptam tambm so iguais.
Teorema 2: Se num tringulo dois lados so desiguais, ao maior lado se ope o maior
ngulo.
Teorema 3: Se as funes f:AB e g:BC so bijetoras, ento a funo composta gof:
AC tambm bijetora.
66
33. Considere as 17 sentenas a seguir e decida se so ou no teoremas. Re-escreva as
sentenas utilizando quantificadores. Separe hiptese e tese. Caso seja um teorema,
prove-o. Caso no seja um teorema, de um contra-exemplo. Qual mtodo de
demonstrao utilizou?
1. Todo nmero inteiro par que quadrado perfeito, um mltiplo de 4.
2. Se n um inteiro positivo, ento (n+3)
2
>9.
3. Existe um nico inteiro n tal que n
2
+2=3.
4. Existe um inteiro n tal que n
2
+4=8.
5. Existe um inteiro n tal que n
2
+5=14.
6. Existe exatamente um inteiro n tal que n
2
+5=14.
7. n
2
>n para todo inteiro n.
8. n
2
>n para cada inteiro negativo n.
9. x
2
<x para algum nmero real x.
10. n
2
>n para algum inteiro n.
11. n
2
=n para um nico inteiro n.
12. O quadrado de todo inteiro impar excede em uma unidade a algum mltiplo de
4.
13. Se n uma unidade a mais que um mltiplo de 3, ento n
2
tambm uma
unidade a mais que um mltiplo de 3.
14. Existe um nmero inteiro n tal que n
3
< n.
15. Sejam m e n inteiros tais que n < m e m = 0. Ento
2
1
n
m
| |
<
|
\ .
.
16. Sejam m e n inteiros tais que n < m e m = 0. Ento
2
n n
m m
| |
<
|
\ .
.
17. Sejam m e n inteiros tais que n < m e m = 0. Ento
3 2
n n
m m
| | | |
<
| |
\ . \ .
.
34. A argumentao a seguir incorreta e voc deve achar o erro: Em uma relao de
equivalncia R definida num conjunto A, a propriedade reflexiva redundante, pois
uma conseqncia das propriedades simtrica e transitiva: de aRb, pela simetria, resulta
bRa e aplicando a transitividade temos aRa.
35. (a) Defina o conceito de divisibilidade no conjunto dos nmeros naturais.
Observaes: a notao a|b indica que a divide a b; em um nico enunciado na
linguagem natural pode estar includo mais de uma implicao HT.
(b) Dados os seguintes teoremas, separe hiptese e tese. Indique as proposies simples
que aparecem nos enunciados.
T1) Sejam a,be* e ce. Tem-se que: i) 1|c, a|a, e a|0, ii) se a|b e b|c, ento a|c,
T2) Se a,b,c,de, com a=0 e c=0, ento a|b e c|d a.c|b.d.
T3) Sejam a,b,ce, com a=0, tais que a|(b+c). Ento a|b se e somente se a|c.
T4) Sejam a,b,ce, com a=0 e b>c, tais que a|(b-c). Ento a|b condio necessria e
suficiente para que a|c.
67
T5) Se a,b,ce, com a=0 e x,ye so tais que a|b e a|c, ento a|(xb+yc); e se xb>yc,
ento a|(xb - yc).
36. (a) Associe cada enunciado da coluna da esquerda com a implicao simblica da
coluna da direita que tm esse significado.
Coluna A Coluna B
(1) P condio suficiente para Q (1) P Q
(2) P condio necessria para Q (2) Q P
(3) Q condio suficiente para P (3) P Q
(4) Q condio necessria para P
(5) P equivale a Q
(6) Q uma caracterizao de P
(7) P condio necessria e suficiente para Q
(8) P necessrio para Q
(9) Q necessrio para P
(10) P acarreta Q
(11) Q acarreta P
(12) Q se infere de P
(13) P se infere de Q
(14) Se P ento Q
(15) Se Q ento P
(16) P se e somente se Q
(17) De P se infere Q
(18) De Q se infere P
(19) P somente se Q
(20) Q somente se P
(21) Para P basta Q
(22) Para Q basta P
37. Leia os textos a seguir e formalize-os, separando explicitamente definies e
teoremas.
(a) Um tringulo a regio do plano limitada por trs linhas retas que se
interceptam duas a duas. Os elementos fundamentais de um tringulo so os vrtices,
os lados e os ngulos. Os vrtices so os pontos de interseo das retas que
determinam o tringulo. Os lados so os segmentos das retas determinados pelos
vrtices, e os ngulos so os formados pelos lados. Quando os trs lados so iguais o
tringulo eqiltero. Se tiver dois lados iguais isscele, mas se os trs lados so
diferentes, o tringulo escaleno. Em todos os tringulos acontece que o lado maior
menor que a soma dos outros dois lados, e para que trs segmentos dados formem um
tringulo preciso que o maior dos trs seja menor que a soma dos outros dois lados.
Se dois lados de um tringulo so iguais, os ngulos que a eles se opem tambm so
iguais.
(b) Um nmero natural mltiplo de outro se podermos achar algum natural
que multiplicado pelo primeiro da o segundo. Por exemplo, 10 mltiplo de 5 porque
10=2.5. Se um nmero simultaneamente mltiplo de outros dois nmeros, ento
dizemos que ele um mltiplo comum desses dois nmeros. Por exemplo, 10 um
68
mltiplo comum de 2 e 5. O mnimo mltiplo comum de dois nmeros a e b, um
nmero m tal que: m um mltiplo comum de a e b, e, se c um mltiplo comum de a e
b, ento m divide a c. O mnimo mltiplo comum de a e b denotado por [a,b].
Dados dois nmeros naturais a e b sempre existe seu mnimo mltiplo comum e
tem-se [a,b](a,b)=ab, onde (a,b) denta o mximo divisor comum de a e b. Se a e b so
primos entre si, [a,b]=ab.
X1. Escreva os seguintes argumentos na forma de implicao lgica e na forma de
coluna.
(a) ~p, ~q p , q (b) p q , ~ (p. ~q) (c) p, p q, ~ q v (r . s) , r . s
(d) x=y x=5, x=5 x<z , x=y x<z
X2. Escreva os argumentos utilizando a notao com o trao de assero (,).
(a) p . (q.v ~p) q (b) (p q) . (p . ~q) s (c) ~(x<0 . y=x) x<
/
0 v y=x
X3. Indicar a regra de inferncia que justifica a validade dos seguintes argumentos:
(a) p q , (p q) v ~r
(b) ~p . (p q) , ~p
(c) p q, q ~r , p ~r
(d) p (q r), p , q r
(e) q v r ~p, q , ~q . ~r
(f) p q, r ~s , (p q) . ( r ~s)
(g) (p.q) v (~p.t), pv ~t , p.q
(h) p qvr , p p . (qvr)
(i) x+y = w y+z = r, x+y = w , y+z = r
(j) (xeA . yeA) (x + y)eA, (x+y)eA , xeA v yeA
(k) x=0, x=1 , x=0 . x=1
38. Demonstrar a no validade dos seguintes argumentos atribuindo convenientemente
valores s variveis proposicionais. Utilize a deduo, no a tabela-verdade completa.
(a) pq, rs, pvs , qvr; (b) ~(p.q), ~p.~qr.s, sr , r;
(c) pqvr, qpvr, rpvq, ~q , qvr; (d) pqvr; sr, ~pvq , ~p.q;
(e) (pq)r; r~sv~t; (st)u; u , pq;
(f) p(qr), s(tv), qs.t, ~(q.v) , pr.
39. Demonstrar dedutivamente, aplicando as equivalncias e regras de inferncia
estudadas, a veracidade dos seguintes argumentos:
(a) p.q, pvrs , p.s; (b) p(qr), pq, p , r; (c) pq, p.qr, ~( p.r) , ~p;
(d) pq, (pq) svq, p.qr, ~s , q;
(e) pq, pv(~~r.~~q), s~r, ~(p.q) , ~sv~q; (f) pv( q.r), pvqs , pvs;
(g) pq, qr, rp, p~r , ~p.~r;
40. Demonstrar os seguintes argumentos utilizando o mtodo de demonstrao indireta
ou pelo absurdo. Lembrete: Para provar a validade do argumento P
1
, P
2
,..., P
n
Q por
este mtodo assumimos ~Q como verdadeira e chegamos a uma contradio, ou seja,
provamos que P
1
, P
2
,..., P
n
,~Q C, onde C uma contradio qualquer, por exemplo,
do tipo A.~A.
(a) p~q, rq ~(p.r);
69
(b) ~(y=1) v z=-1), (x<y . x>z) . z = -1 x=0, ~(y=1 v x=0) v (x<y . x>z) x=0;
41. Prove as seguintes proposies pelo mtodo de induo matemtica:
(1) (ne) (2
n
> n); (2) (ne) (
2
1
( 1)(2 1)
6
n
j
n n n
j
=
+ +
=
);
(3) (ne)
1
1
( 1) 1
n
j
n
j j n
=
=
+ +
; (4)
2 1
2 2 2 2 2
n n+
+ + + = ;
42. Demonstrar dedutivamente, aplicando as equivalncias e regras de inferncia
estudadas, a veracidade dos seguintes argumentos:
(a) p.q, pvrs , p.s; (b) p(qr), pq, p , r; (c) pq, p.qr, ~( p.r) , ~p;
(d) pq, (pq) svq, p.qr, ~s , q;
(e) pq, pv(~~r.~~q), s~r, ~(p.q) , ~sv~q; (f) pv( q.r), pvqs , pvs;
(g) pq, qr, rp, p~r , ~p.~s;
43. Demonstrar os seguintes argumentos utilizando o mtodo de demonstrao indireta
ou pelo absurdo. Lembrete: Para provar a validade do argumento P
1
, P
2
,..., P
n
Q por
este mtodo assumimos ~Q como verdadeira e chegamos a uma contradio, ou seja,
provamos que P
1
, P
2
,..., P
n
,~Q C, onde C uma contradio qualquer, por exemplo,
do tipo A.~A.
(a) p~q, rq ~(p.r);
(b) ~(y=1) v z=-1), (x<y . x>z) . z = -1 x=0, ~(y=1 v x=0) v (x<y . x>z) x=0;
REFERNCIAS BIBLIOGRFICAS:
(1) Alencar, Edgar. Iniciao Lgica Matemtica. Nobel. So Paulo. 1975.
(2) Bittinger, Marvin L. Logic and Proof. Addison-Wesley Publishing Company,
Inc. USA. 1970.
(3) Bueno, Eramis. Garca, Luciano. Introduo Lgica Matemtica. Pueblo y
Educacin. La Habana. 1984. Em espanhol.
(4) Carnielli, Waltger. Epstein, Richard. Computabilidade. Funes Computveis.
Lgica e os Fundamentos da Matemtica. UNESP. 2005.
(5) Daghlian, Jacob. Lgica e lgebra de Boole. Atlas. So Paulo. 1995.
(6) Ershov, Yu. Paliutin, E. Lgica Matemtica. Editorial Mir. Mosc. 1990. Em
espanhol.
(7) Gutmanova, Alexandra. Lgica. Editorial Progreso. 1989. Em espaol.
(8) Pinho, Jos A. Introduo Lgica Matemtica. Apostila. Rio de Janeiro. 1999.
(9) Srates, Jonofon. Raciocnio Lgico. Volume I. 8 Edio. Editora JONOFON
Ltda., 1998.
70
ANEXO 1: RESUMO DAS EQUIVALENCIAS E INFERENCIAS BSICAS PARA
APLICAO NO MTODO DEDUTIVO.
I) Equivalncias:
1. Idempotncia [ID]: p p . p; p p v p
2. Comutatividade [COM]: p . q q . p; p v q q v p
3. Associatividade [ASSOC]: p . ( q . r ) ( p . q ) . r; p v ( q v r ) ( p v q ) v r
4. Distributividade [DIST]: p . ( q v r ) ( p . q ) v ( p . r ); p v ( q . r ) ( p v q ) . ( p v r )
5. Dupla Negao [DN]: p ~ (~ p )
6. Leis de De Morgan [DM]: ~ (p . q) ~ p v ~ q; ~ (p v q) ~ p . ~ q
7. Condicional [COND]: p q ~ p v q
8. Bicondicional [BICOND]: p q ( p q ) . ( q p ); p q ( p . q ) v (~p . ~q )
9. Contraposio [CP]: p q ~ q ~ p
10. Exportao Importao [EI]: p . q r p ( q r )
Alem dessas equivalncias, sero teis tambm as equivalncias que tratam com tautologias e
contradies:
11. Equivalncias com tautologias [ET]: p v ~ p V; p . V p
12. Equivalncias com contradies [EC]: p . ~ p F; p v F p
13. Conjuno [CPNJ]: p, q p . q
II) Regras de Inferncia:
1. Adio [AD]: p p v q
2. Simplificao [SIMP]: p . q p
3. Simplificao Disjuntiva [SIMPD]: ( p v q ) . ( p v ~ q ) p
4. Absoro [ABS]: p q p p . q
5. Modus Ponens [MP]: p . ( p q ) q
6. Modus Tollens [MT]: ( p q ) . ~ q ~ p
7. Silogismo disjuntivo [SD]: ( p v q) . ~ p q
8. Silogismo Hipottico [SH]: ( p q ) . ( q r ) p r
9. Dilema Construtivo [DC]: ( p q ) . ( r s ) . ( p v r ) q v s
10. Dilema Destrutivo [DD]: ( p q ) . ( r s ) . ( ~ q v ~ s ) ~ p v ~ r
11. p r . q r (p v q) r