2.

1 Lógica Formal
Lógica
 Tem, por objeto de estudo, as leis gerais do
pensamento, e as formas de aplicar essas
leis corretamente na investigação da
verdade.
 Origem
 Aristóteles - filósofo grego - 342 a.C,
sistematizou os conhecimentos existentes em
Lógica, elevando-os à categoria de ciência.

 Em sua obra chamada Organum (“ferramenta

para o correto pensar”), estabeleceu princípios
tão gerais e tão sólidos que até hoje são
considerados válidos.
 Origem
 Aristóteles se preocupava com as formas de
raciocínio que, a partir de conhecimentos
considerados verdadeiros, permitiam obter novos
conhecimentos.

 A partir dos conhecimentos tidos como

verdadeiros, caberia à Lógica a formulação de leis
gerais de encadeamentos lógicos que levariam à
descoberta de novas verdades. Essa forma de
encadeamento é chamada, em Lógica, de
argumento.
 Argumento
 Um argumento é uma seqüência de proposições na qual uma
delas é a conclusão e as demais são premissas. As premissas
justificam a conclusão.
 Proposições: sentenças afirmativas que podem ser

verdadeiras ou falsas.
 Premissas: afirmações disponíveis

 Exemplo:
Todo aluno de Computação precisa estudar Lógica (premissa)
José é aluno de Computação. (premissa)
Logo, José precisa estudar Lógica. (conclusão)
Argumento
 O objetivo de um argumento é justificar uma afirmação
que se faz, ou dar as razões para uma certa conclusão
obtida.

Exemplo:

Você me traiu. Pois, disse que ia estudar e meu irmão

lhe viu na boate.

 Um argumento demonstra/prova como a partir dos

dados de um problema chegou-se a uma conclusão.
Argumento: Raciocínio e Inferência
 Exercício 1:

Um turista está andando pela terra dos honestos e

mentirosos. Lá, as pessoas são radicais, umas só falam
a verdade e outras só falam mentiras. Chegou a hora do
almoço e o turista encontra-se numa estrada com uma
bifurcação. O turista sabe que um dos caminhos é para
um restaurante e o outro para um abismo, mas não sabe
distingui-los. Nesta bifurcação ele encontra um homem
nativo. Naturalmente o turista não sabe se ele é honesto
ou mentiroso. Como o turista descobre o caminho para o
restaurante fazendo uma única pergunta a esse nativo?
Argumento: Raciocínio e Inferência
 Exercício 2:

Um rei resolveu dar a liberdade a um de seus três

prisioneiros. Mandou trazer três chapéus brancos e dois
vermelhos. Vendou os olhos dos prisioneiros, colocou um
chapéu em cada um e depois foi retirando a venda dos olhos
deles. Ganharia a liberdade aquele que soubesse dizer, de
forma convincente, a cor do seu próprio chapéu olhando
para os outros prisioneiros. Os dois primeiros não souberam
dizer. O terceiro, antes que o rei lhe tirasse a venda dos
olhos, afirmou com toda certeza a cor do seu chapéu.
Qual a cor do chapéu do terceiro prisioneiro? Justifique.
Argumento: Raciocínio e Inferência
 Para convencer que você sabe a resposta (que não é um
chute) você tem de expor as razões que o levaram a
conclusão (justificar).

Pontos de Partida

Caminhos Seguidos Raciocínio ou

Processo de Inferência

Conclusão

 Um argumento poderia ser considerado uma reconstrução

explícita do raciocínio efetuado
Argumento: Raciocínio e Inferência

 Inferência é a relação que permite passar

das premissas para a conclusão (um
“encadeamento lógico”)

 A palavra inferência vem do latim, Inferre,

e significa “conduzir para”
 Argumento

 O objeto de estudo da lógica é determinar

se a conclusão de um argumento é ou não
decorrente das premissas (uma inferência).
Validade de um Argumento
 Em um argumento válido, as premissas são
consideradas provas evidentes da verdade da
conclusão, caso contrário não é válido.

 Quando é válido, podemos dizer que a conclusão

é uma consequência lógica das premissas, ou
ainda que a conclusão é uma inferência
decorrente das premissas.
 Validade de um Argumento
 Exemplo 1: O argumento que segue é válido?

Se eu ganhar na Loteria, serei rico.

Eu ganhei na Loteria.
Logo, sou rico.
 É Válido
(a conclusão é uma decorrência
lógica das duas premissas.)
Validade de um Argumento
 Exemplo 2: O argumento que segue é válido?

Se eu ganhar na Loteria, serei rico

Eu não ganhei na Loteria
Logo, não sou rico

 Não é Válido
(a conclusão não é uma decorrência
lógica das duas premissas.)
Validade de um Argumento
 A lógica se preocupa com o relacionamento entre
as premissas e a conclusão, ou seja, com a
estrutura e a forma do raciocínio. A verdade do
conteúdo de cada premissa e da conclusão é
estudo das demais ciências.

 A validade do argumento está diretamente ligada

à forma pela qual ele se apresenta.
 Lógica Formal estuda a forma dos argumentos.
 Dedução e Indução
 A Lógica dispõe de duas ferramentas que podem
ser utilizadas pelo pensamento na busca de novos
conhecimentos: a dedução e a indução, que dão
origem a dois tipos de argumentos: Dedutivos e
Indutivos.
Argumentos Dedutivos
 Os Argumentos Dedutivos pretendem que suas
premissas forneçam uma prova conclusiva da
veracidade da conclusão.
Podem ser:
 Válidos: quando suas premissas, se

verdadeiras, fornecem provas convincentes

para a conclusão. Isto é, se as premissas forem
verdadeiras, é impossível que a conclusão seja
falsa;
 Inválidos: não se verifica a característica

anterior.
 Argumentos Dedutivos
 Exemplos de argumentos dedutivos:

Ela toca piano ou violão.

Argumento Inválido
Ela toca piano.
Logo, ela não toca violão.

Todo homem é mortal.

Sócrates é um homem. Argumento Válido

Logo, Sócrates é mortal.

Argumentos Indutivos
 Os Argumentos Indutivos não pretendem que suas
premissas forneçam provas cabais da veracidade da
conclusão, mas apenas que forneçam indicações
dessa veracidade. (possibilidade, probabilidade)

 Seguem do Raciocínio Indutivo, isto é, obtém

conclusões baseada em observações/experiências.
Enquanto que um Raciocínio Dedutivo exige uma
prova formal sobre a validade do argumento.

 Os termos válidos e inválidos não se aplicam para os

argumentos indutivos. Eles são avaliados de acordo
com a maior ou a menor probabilidade com que suas
conclusões sejam estabelecidas.
Argumentos Indutivos
 Exemplo1:
Joguei uma pedra no lago, e ela afundou;
Joguei outra pedra no lago e ela também afundou;
Joguei mais uma pedra no lago, e ela também afundou;
Logo, se eu jogar uma outra pedra no lago, ela vai afundar.
Argumentos Indutivos
 Exemplo2:
A vacina funcionou bem nos ratos.
A vacina funcionou bem nos macacos.
Logo, vai funcionar bem nos humanos.

 Exemplo3:
80% dos entrevistados vão votar no candidato X.
Logo, o candidato X vai vencer as eleições.
Argumentos Indutivos

 A Lógica Formal Clássica só estuda

Argumentos Dedutivos, verificando se são
ou não válidos.
Validade e Verdade
 Verdade e Falsidade: são propriedades das
proposições, nunca dos argumentos

 Validade ou Invalidade: são propriedades

dos argumentos dedutivos que dizem
respeito a inferência ser ou não válida
(raciocínio ser ou não correto)
Validade e Verdade
 Exemplo 1
Toda baleia é um mamífero (V)
Todo mamífero tem pulmões (V)
Logo, toda baleia tem pulmões (V)

 Argumento válido e a conclusão verdadeira.

 Validade e Verdade
 Exemplo 2
Toda aranha tem seis pernas (F)
Todo ser de seis pernas tem asas (F)
Logo, toda aranha tem asas (F)

 Argumento válido e a conclusão falsa

 Validade e Verdade
 Os conceitos de argumento válido ou inválido são
independentes da verdade ou falsidade de suas
premissas e conclusão.

 Qualquer combinação de valores verdade entre as

premissas e a conclusão é possível, exceto que
nenhum argumento dedutivo válido tenha as
premissas verdadeiras e a conclusão falsa.

 Um argumento dedutivo no qual todas as

premissas são verdadeiras é dito Argumento
Correto, evidentemente sua conclusão também é
verdadeira.
Lógica Clássica e Lógica Matemática
 Lógica Informal formula os argumentos em
linguagem natural, mas enfrenta problemas de
ambigüidade e de construções confusas.

 A Lógica Matemática utiliza símbolos de origem

matemática para formular os argumentos.
Trabalho iniciado pelo matemático inglês George Boole (1815 –
1864) – Algebra Booleana. e consolidado pelo filósofo e
matemático alemão Goottlob Frege (1848 – 1895) – Regras de
Demonstração Matemática.
Lógica Clássica e Lógica Matemática
 Uma vez que , a Lógica Matemática tem sua
própria linguagem técnica, é um instrumento
poderoso para a análise e a dedução dos
argumentos, especialmente com o uso do
computador (Prova Automática de Teoremas).

 Tradicionalmente a Lógica tem sido estudada para

orientações filosóficas e matemáticas. Na
computação, ela é utilizada para representar
problemas e para obter suas soluções.
 Lógica Matemática

 Lógica Formal
proposições em forma simbólica
 Lógica Proposicional
Cálculo proposicional
 Lógica de Predicados
Sistema Formal de Lógica
 Lógica Formal
 Proposição
Sentença passível de possuir um dos valores
lógicos: verdadeiro ou falso.
Hoje é quinta-feira
9 < 4
y +2 = 7
Como está voce?
Existe vida em outros planetas
 Proposições
 Princípios

Princípio da não contradição: nenhuma proposição é

verdadeira e falsa simultaneamente.

Princípio do terceiro excluído: toda proposição é

verdadeira ou é falsa.
 Proposições
 Classificação

Proposição Simples: não pode ser decomposta em

proposições menores.

Proposição Composta: pode ser dividida em duas ou

mais proposições.
 Proposições … exemplos

Classifique as seguintes proposições como simples ou

compostas:
1) Diógenes é carteiro.
R.: Simples.
2) Joãozinho não conta mentiras.
R.: Composta.
3) Se Cléber ganhar a eleição, então os impostos serão
reduzidos.
R.: Composta.
 Proposições … exemplos

Classifique as seguintes proposições como simples ou

compostas:
4) O processador é rápido mas a impressora é lenta.
R.: Composta.
5) Amanhã irei à praça ou ao supermercado.
R.: Composta.
6) Pagarei todas as minhas dívidas se e somente se meu
salário sair.
R.: Composta.
Formalizando Sentenças: Variáveis Proposicionais

Sejam as seguintes proposições compostas:

1) O dia está lindo, embora nublado
2) O dia está ensoladado e José está feliz.
Representaremos estas proposições compostas de maneira
mais compacta substituindo as proposições simples por
variáveis proposicionais.
 Formalizando Sentenças: Conectivos lógicos

Nossas proposições agora são:

1) A, embora B
2) C e D
Ambas as proposições são compostas por conjunções.
Visando tornar a notação uniforme, adotam-se os seguintes
símbolos para conectivos lógicos, em que A e B denotam
proposições quaisquer:

As sentenças anteriores são representadas pelas fórmulas A ∧ B e C ∧ D.B e C ∧ B e C ∧ D.D.

Formalizando Sentenças: Conectivos lógicos
 Formalizando Sentenças: exemplos

Escreva cada uma das proposições a seguir utilizando

notação simbólica.

1) Diógenes é carteiro.
R.: A

2) Joãozinho não conta mentiras.

R.: ¬A

3) Se Cléber ganhar a eleição, então os impostos serão reduzidos.

R.: A → B
 Formalizando Sentenças: exemplos
Escreva cada uma das proposições a seguir utilizando notação simbólica.

4) O processador é rápido mas a impressora é lenta.

R.: A ∧ B e C ∧ D. B

5) Amanhã irei à praça ou ao supermercado.

R.: A ∨ B B

6) Pagarei todas as minhas dívidas se e somente se meu salário sair.

R.: A ↔ B
 Formalizando Sentenças: exemplos
Escreva cada uma das proposições a seguir utilizando notação simbólica.

4) O processador é rápido mas a impressora é lenta.

R.: A ∧ B e C ∧ D. B

5) Amanhã irei à praça ou ao supermercado.

R.: A ∨ B B

6) Pagarei todas as minhas dívidas se e somente se meu salário sair.

R.: A ↔ B
Tabelas – verdade (sejam as variáveis p, q)

Negação
Conjunção

Disjunção
Tabelas – verdade (sejam as variáveis p, q)

Condicional

Bicondicional
Referências bibliográficas:
Judith L. GERSTING,
GERSTING Fundamentos matemáticos para a
Ciência da Computação: um tratamento moderno de
matemática discreta.
Kenneth H. ROSEN,
ROSEN Discrete mathematics and its
applications.

… → cálculo proposicional