Introdução à Lógica Matemática

Prévia do material em texto

Introdução à 
Lógica Matemática 
 
Introdução 
 A lógica é a ciência do pensamento correto1. Esta declaração não implica 
contudo em afirmar que ela seja a ciência da verdade. Mesmo que tudo o que se 
permita afirmar dentro da lógica seja supostamente verdadeiro em determinado 
contexto, as mesmas afirmações podem resultar falsas se aplicadas ao mundo 
real. Os filósofos da lógica afirmam que, "para entender o que realmente acontece 
no mundo, precisamos entender o que não acontece", isto é, as propriedades 
invariantes das entidades ou objetos que o compõem. Com essa idéia em mente, 
podemos considerar lógicos os conjuntos de declarações que possuem a 
propriedade de ser verdadeiros ou falsos independentemente do tempo ou lugar 
que ocupam no universo considerado. Este insigth inicial costuma ser de grande 
valia para entender como a lógica pode ser empregada na programação de 
computadores com grande vantagem sobre as linguagens convencionais. O 
cálculo proposicional, que é o subconjunto da lógica matemática mais diretamente 
envolvido nesse processo, formaliza a estrutura lógica mais elementar do discurso 
definindo precisamente o significado dos conetivos e, ou, não, se...então e outros. 
 
 
1 Na realidade, de uma certa classe de pensamento correto. 
História da Lógica 
 
A história da lógica começa com os trabalhos do filósofo grego Aristóteles (384-
322 a.C.) de Estagira (hoje Estavro), na Macedônia, não se conhecendo 
precursores de sua obra, no mundo antigo. 
Mais tarde, foram reunidos os trabalhos na obra denominada Organon, onde 
encontramos no capítulo Analytica Priora a parte essencial da Lógica. 
Para Aristóteles, o raciocínio (dedutivo) reduz-se essencialmente ao tipo 
determinado que se denomina silogismo. 
Os componentes do silogismo aristotélico são sentenças universais ou 
particulares, afirmativas ou negativas, isto é , dos tipos seguintes: 
A : Todos os animais são mortais – universal afirmativa 
E : Nenhum animal é imortal – universal negativa 
I : Alguns homens são sábios – particular afirmativa 
O: Alguns homens não são sábios – particular negativa 
Os silogismo aristotélicos constam de duas premissas e uma conclusão: 
Num premissa "todo X é Y", X e Y são termos. 
Ainda na antiguidade grega, temos a Lógica da escola dos estóicos e megáricos 
(Euclides de Megara – 400 A.C.). Esta lógica apresenta-se de modo diferente da 
aristotélica, pois, esta se liga ao Cálculo dos Predicados, ao passo que aquela se 
refere ao Cálculo Proposicional. Desenvolve aspectos não encontrados em 
Aristóteles. Pertence a essa escola, Zenão (336-204 A . C. ) que fundou o 
estoicismo. Crisipo foi o lógico mais fértil dessa época. Filo, também, dessa 
escola, ensinou que um condicional verdadeiro é a que não tem antecedente 
verdadeiro e consequente falso, denominada, também, implicação material. Nesta 
escola, foram ainda dadas as diferenças entre "ou" inclusivo e o "ou" exclusivo e 
que "se..então.." se define em função de "não" e do "ou". 
A Lógica moderna iniciou-se com a obra Investigation of the Laws of Thougt, de 
George Boole (1815 – 1864). Com isto deu novos rumos à Álgebra da Lógica. 
Paralelamente, Augustus De Morgan (1806-1871) desenvolveu, também, a 
Álgebra da Lógica. 
As idéias de Boole e De Morgan foram objetos de publicações importantes de 
Chales Sanders Peirce (1839-1914), nos Estados Unidos. 
Surge, então, Gottlob Frege (1848-1925), "o maior lógico dos tempos modernos", 
segundo Alonzo Church, com sua obra Begriffsschrift, onde pela primeira vez é 
desenvolvido axiomaticamente o Cálculo Sentencial, usando negação e 
implicação com conceitos primitivos, seis axiomas e regras de modus ponens e de 
substituição. 
Muitas idéias de Frege tratadas de maneira menos sistemática encontram-se em 
Peirce. 
A seguir vem Bertrand Russel a A.N. Witehead (1861-1947), com uma das mais 
importantes obras deste século Principia Matemática, em três volumes. 
Entre o grande número de lógicos atuais, mencionamos, Kurt Godel e Alfred 
Tarski. A Godel deve-se a primeira demonstração de completividade da Lógica 
elementar e da incompletividade de sistemas mais complexos, como a 
impossibilidade da existência de um sistema axiomático completo e consistente 
para a Aritmética usual. 
A Tarski deve-se muito no que respeita ao progresso dos estudos lógicos. Dentre 
as suas contribuições, destaca-se, a definição semântica de verdade, que tem 
aplicações em numerosos campos da Matemática, com repercussões na Filosofia. 
É difícil dar hoje uma idéia da ampliação do campo de estudos da lógica, quanto 
às pesquisas e possibilidades, mas o que é certo é que um conhecimento 
preliminar ainda que intuitivo é necessário em quase todos os ramos de 
conhecimento. 
Sabe-se que a lógica teve sua maior desenvoltura na Filosofia, caminhando pela 
Lingüística, Matemática e Ciência da Computação. 
 
 
A Lógica na Ciência da Computação 
 
Segundo John Nolt (et al., 1991), "A lógica pode ser estudada de dois pontos de 
vista: a formal e a informal. Lógica formal é o estudo das formas de argumento, 
modelos abstratos comuns a muitos argumentos distintos. Lógica informal é o 
estudo de argumentos particulares em linguagem natural e do contexto no qual 
eles ocorrem." Cabe aqui ressaltar que os dois pontos de vista não são opostos, 
mas se complementam. 
Do ponto de vista da ciência da computação, que se trabalha com o sentido 
semântico dos operadores lógicos (princípio de bivalência - verdade, falso) a 
lógica formal predomina. 
Esta disciplina nos introduzirá no mundo da lógica computacional (Ciência da 
Computação). Assim, veremos alguns conceitos e teremos a idéia da abrangência 
do mesmo. 
Segundo o dicionário Aurélio, lógica significa "coerência de raciocínio, de idéias. 
Modo de raciocinar peculiar a alguém, ou a um grupo. Seqüência coerente, regular 
e necessária de acontecimentos, de coisas." 
Um outro conceito seria: a ciência das leis ideais do pensamento e a arte de 
aplicá-los corretamente no processo de investigação e demonstração da verdade. 
No nosso dia a dia nos deparamos com vários problemas, nos quais, usamos a 
"lógica" de forma "consciente" para resolvê-los, isto é, um raciocínio detalhista, 
minucioso, com bastante clareza, ou, raciocinamos de forma lógica sem tomarmos 
conhecimento, intuitivamente. Para que fique claro, criemos uma situação !!! 
Você está viajando e fura um pneu de seu carro. Encosta-o e para. Será que você 
é capaz de descrever todos os passos desde a parada do carro até o pneu 
trocado? 
Dê um tempo! Tente ... pegue uma folha e descreva passo a passo ... depois 
prossiga a leitura. 
Se você tentou, agora responda algumas perguntas: 
Você desligou o carro? 
Você ligou o alerta? 
Você tirou o cinto de segurança? 
Você abriu a porta do carro? 
Você puxou o freio de mão? 
Você levou a chave para abrir o porta-malas? 
Você verificou se o estepe estava cheio? 
Teríamos N detalhes que muitas vezes fizemos intuitivamente e não nos 
preocupamos com isso, no entanto, quando os descrevemos chegamos a 
esquecer muitos deles. A lógica seria a seqüência detalhada e clara do fato. 
Quando alguém pergunta qual é a soma de 20 + 30, o resultado multiplicado por 4 
e este resultado dividido por dois, você faz os cálculos "de cabeça", no entanto 
você geralmente segue um raciocínio, uma lógica, como: 
- Primeiro, obter o resultado da soma (20+30=50) que chamaremos 
de resultado 1. 
- Segundo, pegar o resultado 1 que é 50 e multiplica por 4 
(50*4=200) assim, chamaremos este de resultado 2. 
- Terceiro, pegar o resultado 2 que é 200 e dividir por 2 (200/2=100) 
que chamaremos de resultado 3. 
- Quarto, responder o resultado 3 para quem o perguntou, que neste 
caso é 100. 
 
 
Raciocínio Lógico 
 
 
Veja a seguinte charada !!! 
 
 
Existe um rio a ser atravessado por três pessoas que pesam 
50, 50 e 100 Kg. Para atravessar este rio, as três pessoas 
dispõe de uma canoa que leva no máximo 100 Kg por 
viagem. Estacanoa tem que ser conduzida, isto é, ela não 
anda sozinha. Eis a questão, como estas pessoas chegam no 
outro lado da margem? É um problema com resolução 
simples. 
Depois de resolver este problema ou alguém lhe mostrar a 
solução, você é capaz de resolver problemas semelhante a 
este ou outros do gênero e até mais complexos. 
Esta é uma forma de "despertar" o Raciocínio Lógico. É 
impossível alguém lhe ensinar a lógica, pois ela já está em 
você, o máximo que se pode fazer é torná-la consciente. 
 
UNIDADE I - Proposições e conectivos 
Proposição - é todo o conjunto de palavras ou símbolos que exprimem um 
pensamento de sentido completo, isto é, afirmam fatos ou exprimem juízos que 
formamos a respeito de determinados entes. 
Exemplo: 
a) a lua é um satélite da Terra; 
b) O sol é amarelo; 
c) Brasília é a capital do Brasil. 
 
Princípios Adotados como Regras Fundamentais do Pensamento, na 
Lógica Matemática 
 
Princípio da não contradição - uma proposição não pode ser verdadeira e falsa ao 
mesmo tempo. 
Princípio do terceiro excluído - toda proposição ou é verdadeira ou é falsa, esto é, 
verifica-se sempre um destes casos e nunca um terceiro. 
 
Valores Lógicos das Proposições 
Chama-se valor lógico de uma proposição a verdade se a proposição é verdadeira 
e a falsidade se a proposição é falsa. 
Valor Lógico Símbolo de Designação 
Verdade V 
Falsidade F 
Toda proposição tem um e um só dos valores V , F ( de acordo os dois princípios 
supracitados). 
Exemplo: 
a) o mercúrio é mais pesado que a água; valor lógico da proposição : verdade (V) 
b) o sol gira em torno da Terra; valor lógico da proposição : falsidade (F) 
Tipos de Proposição 
 
Simples ou Atômicas - é a proposição que não contém nenhuma outra proposição 
como parte integrante de si mesma. As proposições simples são geralmente 
designadas por letras minúsculas p, q, r, s ..., chamadas letras proposicionais. 
Observação: Pode ser usada qualquer letra do alfabeto minúsculo para 
representar uma proposição simples. 
Exemplo: 
p : Oscar é prudente; 
q : Mário é engenheiro; 
r : Maria é morena. 
 
Composta ou Molecular - é a proposição formada pela combinação de duas ou 
mais proposições. São habitualmente designadas por letras maiúsculas P, Q, R, S 
..., também denominadas letras proposicionais. 
Exemplo: 
P : Walter é engenheiro E Pedro é estudante; 
Q : Mauro é dedicado OU Pedro é trabalhador; 
R : SE Flávio é estudioso ENTÃO será aprovado. 
Observação: As proposições compostas são também denominadas fórmulas 
proposicionais ou apenas fórmulas. Quando interessa destacar que uma 
proposição composta P é formada pela combinação de proposições simples, 
escreve-se: P ( p, q, r ...); 
Conectivos - são palavras que se usam para formar novas proposições a partir de 
outras. 
Exemplo: 
P : 6 é par E 8 é cubo perfeito; 
Q : NÃO vai chover; 
R : SE Mauro é médico, ENTÃO sabe biologia; 
S : o triângulo ABC é isósceles OU equilátero; 
T : o triângulo ABC é equilátero SE E SOMENTE SE é equilátero. 
São conectivos usuais em lógica Matemática as palavras que estão grifadas, isto é 
"e", "ou", "não", "se ... então", "... se e somente se ..." 
 
Tabela Verdade 
 
Proposição simples - Segundo o princípio do terceiro excluído, toda proposição 
simples p,é verdade ou falsa, isto é, tem o valor lógico verdade (V) ou o valor 
lógico falso (F). 
p 
V 
F 
Proposição composta - O valor lógico de qualquer proposição composta depende 
unicamente dos valores lógicos das proposições simples componentes, ficando 
por eles univocamente determinados. 
 
Tabela-Verdade 
É um dispositivo prático muito usado para a determinação do valor lógico de uma 
proposição composta. Neste dispositivo figuram todos os possíveis valores lógicos 
da proposição composta, correspondentes a todas as possíveis atribuições de 
valores lógicos às proposições simples componentes. 
 
Proposição Composta - 02 proposições simples 
Assim, por exemplo, no caso de uma proposição composta cujas proposições 
simples componentes são p e q, as únicas possíveis atribuições de valores lógicos 
a p e a q são: 
p q 
V V 
V F 
F V 
F F 
Observe-se que os valores lógicos V e F se alternam de dois em dois para a 
primeira proposição p e de um em um para a segunda proposição q, e que, além 
disso, VV, VF, FV e FF são os arranjos binários com repetição dos dois elementos 
V e F. 
 
 
Proposição Composta - 03 proposições simples 
No caso de uma proposição composta cujas proposições simples componentes 
são p, q e r as únicas possíveis atribuições de valores lógicos a p, a q e a r são: 
p q r 
V V V 
V V F 
V F V 
V F F 
F V V 
F V F 
F F V 
F F F 
Analogamente, observe-se que os valores lógicos V e F se alternam de quatro em 
quatro para a primeira proposição p, de dois em dois para a segunda proposição q 
e de um em um para a terceira proposição r, e que, além disso, VVV, VVF, VFV, 
VFF, FVV, FVF, FFV e FFF sãos os arranjos ternários com repetição dos dois 
elementos V e F. 
 
Notação 
O valor lógico de uma proposição simples p indica-se por V(p). Assim, exprime-se 
que p é verdadeira (V), escrevendo: V(p) = V. 
Analogamente, exprime-se que p é falsa (F), escrevendo: V(p) = F. 
Exemplos: 
p : o sol é verde; 
q : um hexágono tem nove diagonais; 
r : 2 é raiz da equação x² + 3x - 4 = 0 
V(p) = F 
V(q) = V 
V(r) = F 
 
UNIDADE II - Operações lógicas sobre proposições 
Operações Lógicas Fundamentais 
Quando pensamos, efetuamos muitas vezes certas operações sobre proposições, 
chamadas operações lógicas. As operações lógicas obedecem regras de um 
cálculo, denominado cálculo proposicional, semelhante ao da aritmética sobre 
números 
Negação 
Chama-se negação de uma proposição p a proposição representada por "não p", 
cujo valor lógico é verdade (V) quando p é falso e falsidade quando p é 
verdadeiro. 
Assim, "não p" tem valor lógico oposto daquele de p. 
Simbolicamente, a negação de p é indicada com notação "~ p", que se lê "não p". 
O valor lógico da negação de uma proposição é, portanto, definido pela seguinte 
tabela-verdade: 
p ~ p 
V F 
F V 
ou seja, pelas igualdades 
~ V = F e ~ F = V 
V (~ p) = ~ V(p) 
O valor lógico da negação de p é igual à negação do valor lógico de p. 
Em linguagem comum a negação efetua-se nos casos mais simples, antepondo o 
advérbio "não" ao verbo da proposição dada. 
Exemplo: 
p : o sol é uma estrela 
~p : o sol não é uma estrela 
Outra maneira de efetuar a negação consiste em antepor à proposição dada 
expressões tais como "não é verdade que", "é falso que". 
Exemplo: 
q : Carlos é engenheiro 
~q : é falso que Carlos é engenheiro; 
~q : não é verdade que Carlos é engenheiro. 
~q : não acontece que Carlos é engenheiro. 
Conjunção 
Chama-se conjunção de duas proposições p e q a proposição representada por "p 
e q", cujo valor lógico é a verdade (V) quando as proposições p e q são 
verdadeiras e a falsidade (F) nos demais casos. 
p q p  q 
V V V 
V F F 
F V F 
F F F 
Disjunção 
Chama-se disjunção de duas proposições p e q a proposição representada por p 
ou q, cujo o valor lógico é a verdade (V) quando ao menos uma das proposições p 
e q é verdadeira e a falsidade (F) quando as proposições p e q são ambas falsas. 
p q p  q 
V V V 
V F V 
F V V 
F F F 
Disjunção Exclusiva 
Chama-se disjunção exclusiva de duas proposições p e q a proposição 
representada simbolicamente por p V q, que se lê: "ou p ou q" ou "p ou q, mas não 
ambos", cujo valor lógico é a verdade (V) somente quando p é verdadeira ou q é 
verdadeira, mas não quando p e q são ambas verdadeiras, e a falsidade (F) 
quando p e q são ambas verdadeiras ou falsas. 
p q p  q 
V V F 
V F V 
F V V 
F F F 
Condicional 
Chama-se proposição condicional ou apenas condicional uma proposição 
representada por "se p então q", cujo valor lógico é a falsidade (F) no caso em que 
p é verdadeira e q é falsa e a verdade (V) nos demais casos. 
p q p  q 
V V V 
V F F 
F V V 
F F V 
Bicondicional 
Chama-se proposição bicondicional ou apenas bicondicional umaproposição 
representada por "p se e somente q", cujo valor lógico é a verdade(V) quando p e 
q são ambas verdadeiras ou ambas falsas, e a falsidade (F) nos demais casos. 
p q p  q 
V V V 
V F F 
F V F 
F F V 
 
UNIDADE III - Tabelas-verdade: Tautologia, 
Contradição e Contingência 
 
 
Construção de Tabelas - Verdade 
Dada várias proposições simples p, q, r , ..., podemos combiná-las pelos 
conectivos lógicos: 
 
Negação ~ 
Conjunção  
Disjunção  
Condicional  
Bicondicional  
 
 
e construir proposições compostas, tais como: 
P(p,q) = ~ p  (p  q) 
Q(p,q) = (p  ~ q)  q 
R(p,q,r) = (p ~ q  r )  ~ (q  (p  ~ r)) 
 
 
Tabela Verdade de uma Proposição Composta 
Então, com o emprego das tabelas verdade das operações lógicas fundamentais é 
possível construir a tabela verdade esta que mostrará exatamente os casos em 
que a proposição composta será verdadeira (V) ou falsa (F), admitindo-se, como é 
sabido, que o seu valor lógico só depende dos valores lógicos das proposições 
simples componentes. 
 
Números de Linhas de uma Tabela Verdade 
O número de linhas da tabela verdade de uma proposição composta depende do 
número de proposições simples que a integram, sendo dado pelo seguinte 
teorema: 
A tabela-verdade de uma proposição composta, com n proposições simples 
componentes, contém 2 elevado a n linhas. 
Para se construir a tabela-verdade de uma proposição composta dada, procede-se 
da seguinte maneira: 
a. determina-se o número de linhas da tabela- verdade que se quer construir; 
b. observa-se a precedência entre os conectivos, isto é, determina-se a forma das 
proposições que ocorrem no problema; 
c. aplicam-se as definições das operações lógicas que o problema exigir. 
Exemplo 
Construir a tabela-verdade da proposição: P(p,q) = ~ (p  ~ q) 
p q ~ q p  ~ q ~ (p  ~ q) 
V V F F V 
V F V V F 
F V F F V 
F F V F V 
 
 
 
O uso de parênteses 
É óbvia a necessidade de usar parêntesis na simbolização das proposições, que 
devem ser colocados para evitar qualquer tipo de ambigüidade. Assim, por 
exemplo, a expressão p  q  r dá lugar, colocando parêntesis, às duas seguintes 
proposições: 
(i) (p  q)  r 
(ii) p  ( q  r) 
que não têm o mesmo significado lógico, pois na (i) o conectivo principal é " ", e 
na (ii), o conectivo principal é " ". 
Por outro lado, em muitos casos, parêntesis podem ser suprimidos, a fim de 
simplificar as proposições simbolizadas, desde que, naturalmente, ambigüidade 
alguma venha a aparecer. 
A supressão de parêntesis nas proposições simbolizadas se faz mediante 
algumas convenções, das quais são particularmente importante as duas 
seguintes: 
A "ordem de precedência" para os conectivos é: 
(1º) ~ ; (2º)  e  ; (3º)  ; (4º)  
Portanto o conectivo mais "fraco" é "~" e o conectivo mais "forte" é " ". 
Assim, por exemplo, a proposição: 
p q  s  r 
é uma bicondicional e nunca uma condicional ou uma conjunção. Para convertê-la 
numa condicional há que usar parêntesis: p (q  s  r) 
e para convertê-la em uma conjunção: (p q  s)  r 
Quando um mesmo conectivo aparece sucessivamente repetido, suprimem-se os 
parêntesis, fazendo-se a associação a partir da esquerda. 
Exemplo: 
((~ (~ (p  q)))  (~ p) fica como ~ ~ (p  q )  ~ p 
Tautologias, Contradições e Contingências 
Tautologia - Chama-se tautologia toda a proposição composta cuja última coluna 
de sua tabela-verdade encerra somente a letra V (verdadeira). Em outros termos, 
Tautologia é toda proposição composta P(p, q, r, ...) cujo valor lógico é sempre (V) 
verdade, quaisquer que sejam os valores lógicos das proposições simples 
componentes. 
Exemplos: 
a) A proposição "~ (p  ~ p)" (Princípio da não contradição) é tautológica, 
conforme se vê pela sua tabela-verdade: 
p ~ p p  ~ p 
~ (p  ~ 
q) 
V F F V 
F V F V 
 
b) A proposição "p  ~ p" (Princípio do terceiro excluído) é uma tautologia. 
p ~ p p  ~ p 
V F V 
F V V 
 
Contradição - Chama-se contradição toda a proposição composta cuja última 
coluna da sua tabela-verdade encerra somente a letra F (falsidade). 
Em outros termos, contradição é toda proposição composta P(p, q, r,...) cujo valor 
lógico é sempre F (falsidade), quaisquer que sejam os valores lógicos das 
proposições simples componentes p, q, r, ... 
Como uma tautologia é sempre verdadeira (V), a negação de uma tautologia é 
sempre falsa (F), ou seja, é uma contradição, e vice-versa. 
p ~ p p  ~ p 
V F F 
F V F 
p ~ p p  ~ p 
V F F 
F V F 
Contingência - Chama-se contingência toda a proposição composta em cuja última 
coluna de sua tabela-verdade figuram as letras V e F cada uma pelo menos uma 
vez. 
Em outros termos, contingência é toda proposição composta que não é tautologia 
nem contradição. 
As contingências são também denominadas proposições contingentes ou 
proposições indeterminadas. 
p ~ p p  ~ p 
V F F 
F V V