Lógica Clássica
16 pág.

Lógica Clássica


DisciplinaMatemática68.298 materiais1.119.018 seguidores
Pré-visualização3 páginas
ser considerada para quantificadores existenciais.
1.1.2 Conectivos Lo´gicos
Nesta sec¸a\u2dco, consideraremos algumas formas de combinarmos sentenc¸as.
Dado duas sentenc¸as, estas podem ser unidas pela conjunc¸a\u2dco alternativa ou. Contudo,
em linguagem coloquial ou pode ser utilizada com sentido exclusivo ou inclusivo, vejamos
dois exemplos.
Dependendo do tempo, trabalharei de te\u2c6nis ou sanda´lia;
Se o produto a · b = 0, onde a e b sa\u2dco reais, enta\u2dco a = 0 ou b = 0.
No primeiro caso, ou e´ utilizado com sentido exclusivo. Contudo no segundo, podemos
ter a = 0 e b 6= 0, b = 0 e a 6= 0 e tambe´m a = b = 0, isto e´ ou foi utilizado no sentido
inclusivo. Neste caso, frequentemente em linquagem coloquial utiliza-se e/ou.
Definic¸a\u2dco 1.1. A disjunc¸a\u2dco de duas sentenc¸as P e Q e´ a sentenc¸a
P ou Q,
denotada P \u2228 Q, a qual deve ser entendida como verdade quando pelo menos uma das
duas sentenc¸as for verdadeira, e falsa quando ambas forem falsas. Isto e´, estamos uti-
lizando o conectivo ou no sentido inclusivo.
Duas sentenc¸as podem ser tambe´m unidas pela conjunc¸a\u2dco correlativa e. Aqui, vamos
utilizar A e B no sentido de ambos os dois, isto e´ A e tambe´m B. E´ neste sentido que a
conjunc¸a\u2dco coordenativa aditiva e sera´ utilizada.
8 CAPI´TULO 1. LO´GICA MATEMA´TICA - PROVAS WLADIMIR NEVES
Definic¸a\u2dco 1.2. A conjunc¸a\u2dco de duas sentenc¸as P e Q e´ a sentenc¸a
tanto P quanto Q,
denotada P \u2227 Q, a qual e´ entendida como verdadeira se tanto P quanto Q forem ver-
dadeiras, e falsa se pelo menos uma das duas sentenc¸as na\u2dco for verdadeira.
Por exemplo, sejam P e Q as seguintes declarac¸o\u2dces
2 e´ um nu´mero primo,
4 e´ um nu´mero primo.
Enta\u2dco, P \u2227Q e´ a afirmac¸a\u2dco composta
2 e´ um nu´mero primo, e 4 e´ um nu´mero primo.
Logo, conforme definic¸a\u2dco anterior, P \u2227Q e´ uma proposic¸a\u2dco falsa.
Ainda, podemos negar uma sentenc¸a dada.
Definic¸a\u2dco 1.3. A negac¸a\u2dco de uma sentenc¸a P e´ a sentenc¸a, na\u2dco P , denotada por
¬P,
a qual e´ entendida como verdade se P for falsa, e falsa se P for verdadeira.
Por exemplo, se P for a proposic¸a\u2dco
2 na\u2dco e´ um nu´mero primo,
enta\u2dco ¬P e´ a proposic¸a\u2dco
2 e´ um nu´mero primo.
As definic¸o\u2dces anteriores para os conectivos lo´gicos \u2228, \u2227 e ¬ podem ser resumidas pela
tabela verdade abaixo
P Q P \u2228Q P \u2227Q ¬P
V V V V F
V F V F F
F V V F V
F F F F V
1.1. LO´GICA MATEMA´TICA CLA´SSICA 9
Agora, consideramos o conectivo lo´gico \u21d2, que significa
se . . . enta\u2dco.
Para entendermos o significado de \u21d2, consideremos a declarac¸a\u2dco
Se eu ganhar na loteria hoje,
enta\u2dco comprarei um carro para meu filho.
Claramente esta declarac¸a\u2dco e´ falsa se eu ganhar e na\u2dco comprar um carro para meu
filho. Pore´m, e se eu na\u2dco ganhar? Bem, neste caso na\u2dco tenho compromisso de comprar
carro algum. Logo se na\u2dco tiver sorte de ganhar na loteria na\u2dco terei quebrado nenhuma
promessa na\u2dco comprando um carro. De fato, em argumentos matema´ticos estamos mais
interessados quando a hipo´tese for verdadeira, e na\u2dco muito interessados quando esta for
falsa. Usualmente, consideramos que a sentenc¸a P \u21d2 Q e´ falsa somente quando P for
verdadeira e Q for falsa, nos demais casos P \u21d2 Q e´ verdade. Consequentemente, se P e´
falso, consideraremos que a sentenc¸a P \u21d2 Q e´ verdadeira mesmo que Q seja verdadeiro
ou falso. Contudo deve-se estar atento, pois podemos provar qualquer coisa partindo-se
de uma premissa falsa!
Definic¸a\u2dco 1.4. Se P e Q sa\u2dco declarac¸o\u2dces, denotaremos por
P \u21d2 Q,
a afirmac¸a\u2dco condicional
se P enta\u2dco Q ou P implica Q.
Sendo a tabela verdade fornecida abaixo
P Q P \u21d2 Q
V V V
V F F
F V V
F F V
10 CAPI´TULO 1. LO´GICA MATEMA´TICA - PROVAS WLADIMIR NEVES
Definic¸a\u2dco 1.5. Se P e Q forem declarac¸o\u2dces, denotaremos por
P \u21d4 Q,
a afirmac¸a\u2dco bi-condicional
P se, e somente se, Q ou P e´ logicamente equivalente a Q.
Sendo a tabela verdade fornecida abaixo
P Q P \u21d4 Q
V V V
V F F
F V F
F F V
Utilizando conectivos lo´gicos, podemos formar expresso\u2dces mais sofisticadas como
[(P \u2228 ¬Q)\u21d2 R]\u21d4 (¬S \u21d2 ¬P ).
Expresso\u2dces como a anterior, usualmente sa\u2dco denominadas formas declarativas, algu-
mas sa\u2dco de interesse especial.
Definic¸a\u2dco 1.6. Uma tautologia e´ uma forma declarativa consistindo de letras rela-
cionadas por conectivos lo´gicos que e´ verdade quaisquer que sejam as proposic¸o\u2dces sub-
stituidas pelas letras existentes. Por outro lado, uma forma declarativa que seja sempre
falsa e´ denominada uma contradic¸a\u2dco.
Um dos exemplos mais simples de uma tautologia e´ uma expressa\u2dco da forma
P \u2228 ¬P,
e analogamente uma das mais simples contradic¸o\u2dces e´ da forma
P \u2227 ¬P.
1.1. LO´GICA MATEMA´TICA CLA´SSICA 11
No primeiro caso, qualquer que seja a proposic¸a\u2dco substitu´\u131da para P , o resultado sera´
verdadeiro, contudo para o segundo sera´ sempre falsa. Um segundo exemplo de uma
tautologia e´ a forma declarativa
[(P \u21d2 Q) \u2227 (Q\u21d2 R)]\u21d2 (P \u21d2 R),
a qual deve ser lida como
Se P implica Q e Q implica R, enta\u2dco P implica R.
Definic¸a\u2dco 1.7. Duas formas declarativas \u3b1 e \u3b2 sa\u2dco logicamente equivalentes se, e
somente se, a forma declarativa
\u3b1\u21d4 \u3b2
e´ uma tautologia.
Exemplo 1.1.4. A forma P \u21d2 Q e´ equivalente a ¬P \u2228 Q. Um exemplo simples e´
seguinte declarac¸a\u2dco
Se este carro na\u2dco funcionar, enta\u2dco chamarei um ta´xi.
Este carro funciona ou chamarei um ta´xi.
A equivale\u2c6ncia lo´gica e´ mostrada a seguir atrave´s da tabela verdade
P Q ¬P P \u21d2 Q ¬P \u2228Q
V V F V V
V F F F F
F V V V V
F F V V V
12 CAPI´TULO 1. LO´GICA MATEMA´TICA - PROVAS WLADIMIR NEVES
Exemplo 1.1.5. A forma ¬(P \u21d2 Q) e´ logicamente equivalente a P \u2227 ¬Q. Conforme
mostra a tabela verdade abaixo
P Q ¬Q ¬(P \u21d2 Q) P \u2227 ¬Q
V V F F F
V F V V V
F V F F F
F F V F F
Exemplo 1.1.6. A forma P \u21d2 Q e´ logicamente equivalente a ¬Q \u21d2 ¬P . Conforme
mostra a tabela verdade abaixo
P ¬P Q ¬Q P \u21d2 Q ¬Q\u21d2 ¬P
V F V F V V
V F F V F F
F V V F V V
F V F V V V
A forma ¬Q\u21d2 ¬P e´ chamada contraposic¸a\u2dco da forma declarativa P \u21d2 Q. O fato
destas duas formas declarativas serem equivalentes fornece a base de um tipo de prova
matema´tica indireta, a qual veremos mais adiante.
Exemplo 1.1.7. A forma P \u21d4 Q e´ logicamente equivalente a
(P \u21d2 Q) \u2227 (Q\u21d2 P ).
Por conseguinte, uma afirmac¸a\u2dco da forma P \u21d4 Q nada mais e´ do que duas implicac¸o\u2dces,
uma em que P \u21d2 Q e a rec´\u131proca, i.e., que Q\u21d2 P .
Agora, vejamos a negac¸a\u2dco de algumas declarac¸o\u2dces quantificadoras. Onde, iniciamos
observando a equivale\u2c6ncia nas seguintes declarac¸o\u2dces:
¬(\u2200x)(x+ 1 = 0),
(\u2203x)(x+ 1 6= 0) ou (\u2203x)[¬((x+ 1 = 0)].
1.2. PROVAS MATEMA´TICAS 13
Em geral, ¬(\u2200x), possui o mesmo significado que (\u2203x)¬. Em outras palavras, dizer que
uma declarac¸a\u2dco na\u2dco e´ sempre verdade e´ equivalente a dizer que algumas vezes e´ falsa.
Similarmente, ¬(\u2203x) possui o mesmo significado que (\u2200x)¬, como podemos observar
pelas seguintes declarac¸o\u2dces equivalentes
¬(\u2203x \u2208 IR)(x2 + 1 = 0),
(\u2200x \u2208 IR)(x2 + 1 6= 0).
Agora, apliquemos as obsevac¸o\u2dces anteriores de modo a negar a seguinte declarac¸a\u2dco
(\u2203x) (\u2200y) (\u2203z) P (x, y, z).
Temos que
¬(\u2203x) (\u2200y) (\u2203z) P (x, y, z)
\u21d4 (\u2200x) ¬(\u2200y) (\u2203z) P (x, y, z)
\u21d4 (\u2200x) (\u2203y) ¬(\u2203z) P (x, y, z)
\u21d4 (\u2200x) (\u2203y) (\u2200z) ¬P (x, y, z).
Note que, podemos obter a u´ltima expressa\u2dco a partir da original trocando os s´\u131mbolos \u2203
por \u2200, vice-versa e colocando a negac¸a\u2dco apo´s os quantificadores. Isto ilustra uma regra
u´til e fa´cil para negar declarac¸o\u2dces quantificadoras.
Observac¸a\u2dco 1.1. De modo a negar uma declarac¸a\u2dco quantificadora iniciada por uma
seque\u2c6ncia de quantificadores, permutamos os s´\u131mbolos \u2203 e \u2200 e colocamos o s´\u131mbolo de
negac¸a\u2dco ao final dos quantificadores.
1.2 Provas Matema´ticas
Sejam P e Q duas declarac¸o\u2dces. Gostar´\u131amos de mostrar que
P \u21d2 Q,
isto e´, a acertiva de que quando a hipo´tese P for verdadeira, enta\u2dco a conclusa\u2dco (ou
tese) Q seja verdade. Vejamos dois modos de realizarmos tal objetivo, primeiramente
as chamadas provas diretas, e posteriormente as denominadas provas indiretas.
14 CAPI´TULO 1. LO´GICA MATEMA´TICA - PROVAS WLADIMIR NEVES
1.2.1 Provas Diretas
A construc¸a\u2dco de uma prova direta de