Lógica na Ciência da Computação

Prévia do material em texto

*Introdução
A lógica na Ciência da Computação
■ Aplicação de métodos matemáticos rigorosos para 
resolução de problemas
■ Importância dos métodos formais, fundamentados em 
lógica formal, dentro dos diversos ramos presentes na 
Ciência da Computação
Introdução
■ Origem
■ Definição
■ A lógica matemática e a computação
■ O que é lógica?
■ O que significa estudar lógica?
■ Qual sua definição?
A Lógica Formal
■ Definição
■ Tem por objeto de estudo as leis gerais do pensamento, e as 
formas de aplicar essas leis corretamente na investigação da 
verdade
■ Trabalhos anteriores, textos sobre lógica foram encontrados, 
mas é tradicionalmente aceito que a Lógica nasceu na Grécia 
e seu criador é Aristóteles
Um pouco de história
■ Aristóteles, na Grécia antiga (342 a.C.) ...
■ Estabeleceu os fundamentos da lógica sistemática, através de 
princípios tão gerais e sólidos que até hoje são considerados 
válidos.
■ George Boole
■ Propôs em 1847 uma linguagem formal que permite realizar 
inferências.
■ Gottlob Frege
■ Publicou em 1879 a primeira versão do que hoje é conhecido 
como Cálculo de Predicados.
Um pouco de história
■ Final do século XX
■ A lógica passou a ser utilizada como base formal para outros 
campos da matemática.
■ Estudiosos:
■ David Hilbert, Giuseppe Peano, Georg Cantor, Thoralf 
Skolem, entre outros.
Um pouco de história - Aristóteles
 A Lógica foi considerada na cultura clássica e 
medieval como um instrumento indispensável ao 
pensamento científico.
 Aristóteles se preocupava com as formas de 
raciocínio que, a partir de conhecimentos verdadeiros, 
permitiam obter novos conhecimentos 
Um pouco de história - Aristóteles
 Era necessário argumentar com clareza, mediante 
demonstrações rigorosas, respondendo as objeções 
dos adversários.
 Cabe à lógica a “formulação de leis gerais de 
encadeamentos de conceitos e juízos que levam à 
descoberta de novas verdades.” 
 Encadeamentos? 
Teoria dos argumentos de Aristóteles
■ Encadeamento – argumento
■ Afirmações envolvidas – proposições
■ Um argumento é um conjunto de proposições, tal que 
uma delas é a conclusão e as demais, as premissas. As 
premissas justificam a conclusão. 
■ Teoria dos argumentos de Aristóteles
■ Todos os homens são mortais
■ Sócrates é homem
■ Portanto, Sócrates é mortal
Euclides e o método axiomático
■ Com sua obra Elementos, o matemático Euclides (325 
a 265 a.C.) deu forma sistemática ao saber 
geométrico.
■ A partir de algumas noções comuns (axiomas), 
Euclides deduz novas proposições ou teoremas, as 
quais constituem todo o saber geométrico.
■ As deduções devem obedecer a um conjunto de 
regras fixas.
Leibniz, o Precursor da Lógica Moderna
■ A lógica moderna começou no século XVI, com o 
filósofo e matemático alemão Gottfried Wilhelm 
Leibniz (1646-1716).
■ O projeto de Leibniz tinha como base uma lógica 
simbólica e de caráter completamente algébrico, 
semelhante ao cálculo diferencial, inventado por ele e 
Newton.
■ Deduções lógicas deveriam ser feitas através de uma 
pura manipulação simbólica, sem referência ao 
significado “real” destes símbolos.
A Lógica Matemática no século XIX
■ A passagem do século XVIII para o século XIX é 
conhecida como a idade áurea da matemática.
■ Em especial, começam a ser delineados os 
fundamentos da ciência da computação.
■ A lógica matemática, a partir daqui, tem o objetivo 
principal de tornar explícitas as formas de inferência, 
deixando de lado o conteúdo das verdades que elas 
possam transmitir.
Fundamentos da Lógica Matemática e 
da Computação
■ O inglês George Boole (1815-1864) é considerado o 
pai da lógica simbólica.
■ Desenvolveu o primeiro sistema formal para raciocínio 
lógico (lógica booleana).
■ Foi o primeiro a enfatizar a possibilidade de aplicar o 
cálculo formal a diferentes situações.
■ Boole percebeu que uma álgebra de objetos (que não 
fossem números) poderia ser construída e ter várias 
aplicações: Circuitos Lógicos, Verdade ou Falsidade de 
Proposições, Aritmética sobre Números Binários
Fundamentos da Lógica
■ Gottlob Frege (1848-1925) foi o primeiro a formular com 
precisão a diferença entre constante e variável.
■ Introduziu a noção de função lógica de várias variáveis 
(predicados) e o conceito de quantificador.
■ O emprego de quantificadores para ligar variáveis, 
principal característica do simbolismo lógico moderno e 
que o torna superior em alguns aspectos à linguagem 
vulgar e ao simbolismo algébrico de Boole, está entre as 
maiores invenções intelectuais do século XIX
Kurt Gödel – Muito além da lógica
■ O trabalho notável de Gödel (1906-1978) pode ser 
resumido no seguinte teorema:
■ “Se S é um sistema formal suficientemente forte para conter 
a aritmética elementar, então S é incompleto ou 
inconsistente”.
■ Por exemplo, em uma teoria sobre números naturais, 
existem verdades que não podem ser provadas apenas na 
lógica (simbólica)!
Kurt Gödel – Muito além da lógica
■ Fim do sonho dos lógicos, visto que não se pode 
desenvolver toda a aritmética (e muito menos toda a 
matemática) num sistema lógico que seja (ao mesmo 
tempo) consistente e completo.
■ Fim do sonho formalista: existem enunciados 
matemáticos que são verdadeiros, mas não são 
suscetíveis de prova, isto é, existe um abismo entre 
verdade e demonstração
Alan Turing - O Berço da Computação
■ A revolução do computador/computação iniciou 
quando Alan Turing (1912-1954) tomou conhecimento 
do Problema de Decisão de David Hilbert.
■ Toda a comunidade da época estava interessada em 
encontrar uma solução precisa para o conceito 
informal de realizar uma computação.
Matemática, Lógica e Computação
Matemática (Semântica)
[Aritmética]
[Geometria]
[Análise]
(Verdades Matemáticas) Lógica (Sintaxe)
[Alfabeto (Símbolos)]
[Expressões]
[Axiomas e Regras de Inferência]
(Teoremas)
Computação
[Alfabeto (Símbolos)]
[Programas]
[Funções e Procedimentos]
[Algoritmos]
[Correção de Algoritmos]
Lógica - Definição
“Lógica: conhecimento das formas gerais e regras gerais 
do pensamento correto e verdadeiro, 
independentemente dos conteúdos pensados; regras 
para demonstração científica verdadeira; regras para 
pensamentos não-científicos; regras sobre o modo de 
expor o conhecimento; regras para verificação da 
verdade ou falsidade de um pensamento etc.”
Lógica e informática
 “As conexões entre a Lógica e a Informática crescem e 
se aprofundam rapidamente. Ao lado da demonstração 
automática, da programação em lógica, da 
especificação e verificação de programas, outros 
setores revelam uma fascinante interação mútua com 
a Lógica, como a teoria de tipos, a teoria do 
paralelismo, a inteligência artificial, a teoria da 
complexidade, as bases de dados, a semântica 
operacional e as técnicas de compilação” 
 (José Meseguer)
Ciência e Lógica
■ A busca pelo conhecimento acontece na maioria das 
atividades que envolvem o ser humano. Na religião, 
na política, no campo social, etc...
■ Mas a ciência ocupa um papel importante nesses 
campos.
■ O que é ciência? Como os cientistas realizam 
investigação?
■ O que busca um biólogo, por exemplo? 
Ciência e Lógica
■ Em princípio, podemos dizer que todo cientista está 
buscando compreender algum fenômeno, entender e 
explicar uma parte da nossa realidade.
■ Um pesquisador médico investiga o mecanismo de 
certas doenças. Um biólogo, estuda o comportamento 
de uma mosca, etc...
■ A investigação usa a razão. Mas, o que é razão?
■ Podemos dizer que a razão humana se materializa 
num contexto linguístico. Não há razão sem 
linguagem...
Ciência e Lógica
■ Qual linguagem um biólogo investiga seu objeto de 
estudo (a mosca)? Linguagemnatural...
■ Voltemos à lógica. Qual a porção da realidade que um 
lógico investiga? Através de qual linguagem?
■ Pode ser os números. Os números naturais são 
entidades lógicas!
■ O curioso é: um biólogo captura uma mosca e inicia a 
investigação. O médico seleciona os pacientes e 
investiga a doença. As moscas encontramos por aí. Os 
pacientes são seres vivos e também estão ao nosso 
alcance. Mas e se um lógico quiser estudar o número 2, 
onde ele está?
Ciência e Lógica
■ Isto parece irrelevante, mas o número 2 existe?
■ Um livro existe? Por que?
■ Porque vejo e toco. 
■ Mas os sentidos podem falhar?
■ “Penso, logo existo”
■ Conclusão: Existe pensamento. Mas, eu existo?
O que é lógica?
■ O estudo da Lógica é o estudo dos métodos e princípios 
usados para distinguir o raciocínio correto do incorreto 
(“Introdução à Lógica”, Irving M. Copi, Ed. Mestre Jou, São 
Paulo, 1968);
■ A Lógica formal é uma ciência que determina as formas 
corretas (ou válidas) de raciocínio (“Noções de Lógica Formal”, 
Joseph Dopp, Ed. Herder, São Paulo, 1970);
■ Lógica é o estudo de argumentos. Um argumento é uma 
seqüência de enunciados na qual um dos enunciados é a 
conclusão e os demais são premissas, as quais servem para 
provar, ou pelo menos fornecer alguma evidência para a 
conclusão (“Lógica”, John Nolt e Dennis Rohatyn, Makron 
Books, São Paulo, 1991).
Argumento
Exemplos
Se eu ganhar na loteria, serei rico.
Eu ganhei na loteria.
Logo, sou rico.
Todo aluno de computação precisa estudar Lógica.
José é aluno de Computação.
Logo, José precisa estudar Lógica.
“sou rico” – decorrência lógica das duas premissas
Argumento válido!
Conceitos - Argumento
■ Um argumento é uma seqüência de proposições 
(declarações/afirmações) na qual uma delas é a 
conclusão e as demais são premissas.
■ Uma proposição (ou declaração/afirmação) é uma 
sentença que pode ser verdadeira ou falsa 
■ O objeto de estudo da lógica é determinar se a 
conclusão de um argumento é ou não uma 
consequência lógica das premissas. 
Lógica
■ A Lógica se preocupa com:
■ Premissas e conclusão
■ Estrutura e forma de raciocínio
■ Para a Lógica não importa o conteúdo
■ A Lógica busca determinar se a conclusão é ou não 
uma consequência lógica das premissas
■ O objeto da Lógica é a forma pela qual o raciocínio 
está estruturado – Lógica Formal
Atenção!
Raciocínio e Inferência
Pontos de partida
Caminhos seguidos
 Conclusão
■ Argumento – reconstrução do raciocínio efetuado
■ Inferência – relação que permite passar das 
premissas para a conclusão (“encadeamento lógico”)
Raciocínio ou 
Processo de Inferência
Você sabe raciocinar?
Problemas de lógica...
“Se 5 máquinas levam 5 minutos para fazer 5 objetos, quanto 
levaria para 100 máquinas fazer 100 objetos? ”
“João está olhando para Ana, e Ana está olhando para 
Carlos; João é Casado, Carlos não é. Tem alguma pessoa 
casada olhando para uma pessoa solteira?”
“Um taco e uma bola custam R$1,10 no total. O taco custa 
um real a mais do que a bola. Quanto custa a bola?”
O que é lógica?
 O estudo da Lógica é o estudo dos métodos e princípios 
usados para distinguir o raciocínio correto do incorreto 
(“Introdução à Lógica”, Irving M. Copi, Ed. Mestre Jou, São 
Paulo, 1968);
 A Lógica formal é uma ciência que determina as formas 
corretas (ou válidas) de raciocínio (“Noções de Lógica Formal”, 
Joseph Dopp, Ed. Herder, São Paulo, 1970);
 Lógica é o estudo de argumentos. Um argumento é uma 
seqüência de enunciados na qual um dos enunciados é a 
conclusão e os demais são premissas, as quais servem para 
provar, ou pelo menos fornecer alguma evidência para a 
conclusão (“Lógica”, John Nolt e Dennis Rohatyn, Makron 
Books, São Paulo, 1991).
Argumento
 Exemplos
Se eu ganhar na loteria, serei rico.
Eu ganhei na loteria.
Logo, sou rico.
Todo aluno de computação precisa estudar Lógica.
José é aluno de Computação.
Logo, José precisa estudar Lógica.
“sou rico” – decorrência lógica das duas premissas
Argumento válido!
Argumento
 Exemplos
Se eu ganhar na loteria, serei rico.
Eu não ganhei na loteria.
Logo, não sou rico.
Argumento inválido!
“não sou rico” – não é decorrência lógica das duas premissas
Conceitos - Argumento
 Um argumento é uma seqüência de proposições 
(declarações/afirmações) na qual uma delas é a conclusão e as 
demais são premissas.
 Uma proposição (ou declaração/afirmação) é uma sentença 
que pode ser verdadeira ou falsa 
 O objeto de estudo da lógica é determinar se a conclusão de 
um argumento é ou não uma consequência lógica das 
premissas. 
Lógica
 A Lógica se preocupa com:
 Premissas e conclusão
 Estrutura e forma de raciocínio
 Para a Lógica não importa o conteúdo
 A Lógica busca determinar se a conclusão é ou não 
uma consequência lógica das premissas
 O objeto da Lógica é a forma pela qual o raciocínio 
está estruturado – Lógica Formal
Atenção!
Raciocínio e Inferência
Pontos de partida
Caminhos seguidos
 Conclusão
 Argumento – reconstrução do raciocínio efetuado
 Inferência – relação que permite passar das premissas para a 
conclusão (“encadeamento lógico”)
Raciocínio ou 
Processo de Inferência
Validade do argumento
 Se um argumento é válido, a conclusão é uma consequencia 
lógica das premissas, ou uma inferência decorrente das 
premissas
Todo aluno de computação precisa estudar Lógica.
José é aluno de Computação.
Logo, José precisa estudar Lógica.
Todo aluno de computação precisa estudar Lógica.
José não é aluno de Computação.
Logo, José não precisa estudar Lógica.
 No segundo argumento, a conclusão não se segue logicamente 
das premissas
Argumento válido!
Argumento inválido!
Avaliação de um argumento
 Como avaliar se um argumento é válido? (Ou seja, é 
possível demonstrar que a conclusão é verdadeira?)
 Critérios empregados para avaliar um argumento:
 Se todas as premissas são verdadeiras 
 Se dada a verdade das premissas, a conclusão é ao menos 
provável
 Se as premissas são relevantes para a conclusão
Dedução e Indução
 Ferramentas principais empregadas pelo pensamento 
na busca de novos conhecimentos
 Dedução
 Indução
 Dando origem aos argumentos 
 Dedutivos
 Indutivos
Argumento dedutivo
 Pretende que suas premissas forneçam uma prova 
conclusiva da veracidade da conclusão
 Válido: quando suas premissas, se verdadeiras, 
fornecem provas convincentes para a conclusão. 
Isto é, se as premissas são verdadeiras, é 
impossível que a conclusão seja falsa.
 Inválido: caso contrário.
Argumentos dedutivos
Laura toca piano ou violão.
Laura toca piano.
Logo, Laura não toca violão.
Todo homem é mortal.
Sócrates é um homem.
Logo, Sócrates é mortal.
Argumento inválido!
Argumento válido!
Argumento indutivo
 Não pretende que suas premissas forneçam provas cabais da 
veracidade da conclusão, mas apenas que forneçam 
indicações dessa veracidade (possibilidade, probabilidade…).
 Os termos válido e inválido não se aplicam para os argumentos 
indutivos. Estes são avaliados de acordo com a maior ou a 
menor probabilidade com que suas conclusões sejam 
estabelecidas.
Argumentos indutivos
Laura jogou uma pedra no lago e ela afundou.
Laura jogou outra pedra no lago e ela também afundou.
Laura jogou mais uma pedra no lago e ela também afundou
Logo, se Laura jogar uma outra pedra no lago, ela vai afundar.
A vacina funcionou bem nos ratos.
A vacina funcionou bem nos macacos.
Logo, vai funcionar bem nos humanos.
80% dos entrevistados vão votar no candidato X.
Logo, o candidato X vai vencer as eleições.
Dedução e Indução
 Raciocínio Indutivo
 Argumentos indutivos obtém conclusões baseadas em 
observação/experiências Argumentos indutivos partem do particular para o geral. Dadas 
observações particulares, busca-se por regras gerais 
 Raciocínio Dedutivo
 Exige uma prova formal sobre a validade do argumento
 Argumentos dedutivos partem de regras gerais para estabelecer a 
veracidade do acontecimentos particulares
 A Lógica Formal Clássica só estuda argumentos dedutivos, 
verificando se são válidos ou inválidos.
Validade e verdade
 Verdade e Falsidade 
■ Propriedades das proposições, não dos argumentos
 Validade ou Invalidade
■ Propriedade dos argumentos dedutivos 
■ Uma inferência é ou não válida (o raciocínio é ou não é 
correto)
Validade e verdade
 Exemplos
Toda baleia é um mamífero (V)
Todo mamífero tem pulmões (V)
Logo, toda baleia tem pulmões (V)
Toda aranha tem seis pernas (F)
Todo ser de seis pernas tem asas (F)
Logo, toda aranha tem asas (F)
Argumento válido e 
conclusão verdadeira
Argumento válido e 
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 tenhas 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 x Lógica Simbólica
■ Os argumentos formulados em linguagem natural são de 
difícil avaliação. Enfrenta problemas de ambiguidade e 
construções confusas.
■ Uso de símbolos para expressar os enunciados e 
raciocínio da Lógica 
■ Lógica Matemática ou Lógica Simbólica
■ Lógica baseada em linguagem natural
■ Lógica Clássica
Lógica Simbólica
 Com sua linguagem técnica vem se tornando um instrumento 
cada vez mais poderoso para a análise e a dedução dos 
argumentos. 
 Vantagens do uso de uma simbologia
 ajuda a expor as estuturas lógicas das proposições e dos argumentos
 possibilita utilização de recursos computacionais no tratamento de 
enunciados e argumentos
 os computadores manipulam bem os símbolos, enquanto encontram 
dificuldade na manipulação da linguagem natural
 Na computação a Lógica é utilizada para representar 
problemas e para obter suas soluções.
Proposições e Predicados
 Idéias envolvidas nos argumentos podem ser apresentadas 
através de proposições (enunciados ou sentenças) que se refere 
a um objeto
“Eu ganhei na loteria”
“José atirou uma pedra no lago”
“Sócrates é um homem” 
 Estas proposições são singulares.
Proposições e Predicados
 Outras proposições fazem referência a conjuntos de objetos
■ “Todos os homens são mortais”
■ “Alguns astronautas foram à Lua”
■ “Nem todos os gatos caçam ratos”
 Os termos “homens”, “astronautas” e “gatos” são conceitos. 
Não se referem a um homem ou astronauta em particular, mas 
ao conjunto de propriedades que faz com que um objeto esteja 
em uma categoria ou outra. Estamos nos referindo aos 
predicados.
Proposições e Predicados
 Proposições singulares e predicados dão origem ao Cálculo 
Proposicional e ao Cálculo de Predicados
 A lógica que trata apenas das proposições é mais simples
 O Cálculo de Predicados lida com dois conceitos
 variável: se refere ao objeto genérico de uma categoria
 quantificadores: expressões como “para todo” e “existe algum” que 
se referem à quantidade de objetos que partilham o mesmo 
predicado
Lógica Matemática
■ Lógica Proposicional
■ Lógica de Predicados
■ Programação Lógica
■ Outras Lógicas
Lógica Formal
 Introdução ao Cálculo Proposicional
Conceitos Iniciais
 Para descrever o mundo usamos sentenças declarativas
■ Toda mãe ama seus filhos
■ Maria é mãe e Paulo é filho de Maria
 Aplicando regras gerais de raciocínio, é possível concluir a partir 
das afirmações acima
■ Maria ama Paulo
Conceitos Iniciais
 O Cálculo Proposicional (ou Lógica Proposicional) é o estudo da 
linguagem proposicional
 Estuda basicamente cinco símbolos:
■ Negação: ¬ (ou ~)
■ Conjunção: ∧
■ Disjunção: ∨
■ Implicação: →
■ Bi-implicação: ↔
 Tais símbolos são os conectivos lógicos ou conetivos 
proposicionais
Conceitos Iniciais
 Proposições: construção (frase, sentença, pensamento) à qual se 
pode atribuir falso ou verdadeiro
 As sentenças abaixo são proposições?
■ Dez é menor que sete.
■ Como vai você?
■ Existe vida em outros planetas
■ Parabéns!
 Proposições compostas: duas ou mais sentenças agrupadas 
através dos conectivos lógicos
■ Vou comprar um sapato preto ou marrom.
■ Se chover hoje, então não haverá jogo.
■ Windows é um sistema operacional e Prolog é uma linguagem de 
programação.
Paradoxos - definição
paradoxo
(cs) [Do gr. parádoxon, pelo lat. paradoxon.]
Substantivo masculino 
1.Conceito que é ou parece contrário ao comum; contra-senso, absurdo, 
disparate: 
“Era um conversador admirável, adorável nos seus erros, .... nas suas opiniões 
revoltantes e belíssimas, nos seus paradoxos, nas suas blagues.” (Mário de Sá-
Carneiro, A Confissão de Lúcio, p. 21.) 
2.Contradição, pelo menos na aparência: 
A obsessão da velocidade e o congestionamento do trânsito são um dos paradoxos 
da vida moderna. 
3.Figura (15) em que uma afirmação aparentemente contraditória é, no 
entanto, verdadeira. 
4.Filos. Afirmação que vai de encontro a sistemas ou pressupostos que se 
impuseram, como incontestáveis ao pensamento. [Cf., nesta acepç., aporia e 
antinomia.] 
5.Lóg. Dupla implicação entre uma proposição e sua negação, que 
caracteriza uma contradição insolúvel. [V. paradoxos lógicos e paradoxos 
semânticos.] 
6.Lóg. Dificuldade na conclusão de um raciocínio, seja pela vaguidade dos 
termos das suas proposições, seja pela insuficiência dos instrumentos 
lógicos formais. [V. paradoxo do monte.] 
Paradoxos
 Definição
 Paradoxos lógicos e paradoxos semânticos
 Exemplos
Paradoxos
 Paradoxo do mentiroso
■ Paradoxo semântico
■ Toda sentença declarativa da língua portuguesa ou é 
verdadeira ou é falsa, nunca ambas simultaneamente.
■ Por exemplo, seja a seguinte frase:
■ É possível verificar que a sentença S1 é verdadeira, pois 
contém oito palavras
S1: “A sentença escrita neste quadro contém oito 
palavras”
Paradoxos
 Paradoxo do mentiroso
■ Seja a seguinte frase:
■ Trata-se de uma sentença falsa, pois S2 contém oito palavras e 
não onze.
■ Porém, considere S3:
■ S3 é verdadeira ou falsa?
S2: “A sentença escrita neste quadro contém onze 
palavras”
S3: “A sentença escrita neste quadro é 
falsa”
Paradoxos
 Paradoxo do mentiroso
■ S3 é verdadeira ou falsa?
■ Do ponto de vista gramatical está correta
■ Trata-se de uma sentença declarativa, porém 
 ou S3 é verdadeira, 
 ou S3 é falsa
 Se S3 for verdadeira – é verdadeiro que “A sentença escrita neste 
quadro é falsa” – e, portanto, conclui-se que S3 é falsa
 Se S3 é falsa - é falso que “A sentença escrita neste quadro é 
falsa” – logo, deduz-se que S3 é verdadeira.
S3: “A sentença escrita neste quadro é 
falsa”
Paradoxos
■ Assim:
 S3 é verdadeira se e somente se S3 é falsa!
S3: “A sentença escrita neste quadro é 
falsa”
Paradoxo do mentiroso
Paradoxos semânticos
 Paradoxo do cartão
■ Suponha que numa das faces de um cartão esteja escrita a 
frase:
■ Pergunta: a sentença escrita em um dos lados do cartão é 
verdadeira ou falsa?
A sentença escrita no 
verso deste cartão é 
verdadeira.
A sentença escrita no 
verso deste cartão é 
falsa.
Paradoxos semânticos
 Paradoxo de Grelling
■ Adjetivos autológicos são assim definidos se a propriedade 
que ele denota pode ser atribuída a ele mesmo.■ Adjetivos heterológicos denotam atributos que não são 
aplicáveis a si próprios.
Exemplos: “curto” e 
“proparoxítona”
Exemplos: “longo”, “oxítona” e 
“verde”
Paradoxos semânticos
 Paradoxo de Grelling
■ Seja o adjetivo “heterológico”
Se “heterológico” for heterológico, então ele é 
autológico.
Se “heterológico” não for heterológico, ou seja, 
autológico, então ele é heterológico.
Assim, o adjetivo “heterológico” é heterológico e 
autológico ao mesmo tempo...
Paradoxos semânticos
 Paradoxo do Barbeiro
■ É óbvio que:
 ou ele se barbeia, 
 ou ele não se babeia.
 Portanto, um barbeiro se barbeia se e somente se ele não se 
barbeia. Adotando-se a Lógica Clássica, tal barbeiro não existe.
Numa pequena cidade do interior vive um barbeiro, muito 
conhecido dos moradores da cidade, que barbeia todas (e 
somente aquelas) pessoas moradoras da cidade que não se 
barbeiam sozinhas. Ora, o babeiro é um morador da cidade. 
Pergunta: Quem faz a barba do babeiro?
Paradoxos
 Paradoxo de Russell
■ Paradoxo lógico
■ Existem dois tipos de conjuntos: 
 (i) os normais, que não contêm a si próprios como elementos, 
por exemplo, os números naturais, as cadeiras de uma sala, as 
bandeiras dos países do mundo, etc., 
 (ii) os não normais, que têm a si próprios como elementos, por 
exemplo, o conjunto de todos os conjuntos com mais de n 
elementos, o conjunto de todos os conjuntos, o conjunto de 
todas as entidades abstratas, o conjunto de todas as coisas 
pensáveis, etc. 
■ Seja N o conjunto de todos os conjuntos normais, N é normal 
ou não? 
Paradoxos
 Paradoxo de Russell
■ Verifica-se que se N é normal, então ele contém a si mesmo, pois 
por definição ele contém todos os conjuntos normais, mas se ele 
contém a si mesmo então ele é não normal. 
■ E por outro lado, se ele é não normal, então ele não contém a si 
mesmo, pois por definição ele contém apenas conjuntos normais, 
mas se ele não contém a si mesmo então ele é normal. 
■ Esse paradoxo, fruto da utilização ingênua do conceito de 
conjunto, alertou os matemáticos sobre o perigo de confiar em 
intuições para resolver o problema dos fundamentos, levando a 
uma radicalização maior ainda em direção à abstração. 
As linguagens da lógica
 A partir dos paradoxos é possível verificar que uma linguagem 
natural, como a língua portuguesa, não pode ser adequada ao 
tratamento rigoroso da lógica
 A linguagem formal
 A linguagem da teoria dos conjuntos é a linguagem universal da 
lógica
 A Lógica Proposicional
■ conectivos lógicos
■ tabelas-verdade
Exemplos
Hoje é sexta-feira ou terça-feira.
Hoje não é sexta-feira.
Hoje é terça-feira.
Ele é menor de 18 anos ou é irresponsável.
Ele não é menor de 18 anos.
Ele é um irresponsável.
 Os argumentos apresentados são da forma:
P ou Q
Não é o caso que é P
Q
Formas de argumentos
 Proposições: sentenças declarativas
■ A neve é branca. (verdadeiro)
■ 2+2=5. (falsa)
■ Há cinco milhões de grãos de areia na lua. (?)
 Exemplos
Quatro é maior do que cinco.
Ela é muito inteligente.
São Paulo é uma cidade grande.
Como vai você?
Como isso pode acontecer!
Bom dia!
Formas de argumentos
 Proposições compostas (argumentos): usam os 
conectivos lógicos
■ Negação – “Não é o caso que”
■ Conjunção – “E”
■ Disjunção – “Ou”
■ Implicação – “Se... Então”
■ Bi-implicação ou equivalência – “Se e somente se”
Negação
 A negação de uma sentença é constituída colocando a 
palavra não de forma apropriada ou prefixando-se a 
expressão “não é fato que” ou “não é o caso que”
■ Brasil não é um país livre
■ Não é fato que o Windows seja um software livre
■ Não é o caso que ele é fumante (negação da sentença “Ele é 
fumante”)
 Ele é não-fumante
 Ele não é fumante
 Ele não fuma
Negação
 Qual a negação da sentença?
− Pedro é alto e magro.
− Pedro é baixo e gordo.
− Pedro é baixo ou gordo.
− Pedro não é alto ou não é magro.
Conjunção
 Composição de duas sentenças ligadas por “e”
■ Chove e faz calor
 A conjunção pode ser expressa por palavras como: “mas”, 
“todavia”, “embora”, “contudo”, “além do mais”, “no entanto”, 
“apesar disso” ...
■ Chove mas faz calor
Disjunção
 Proposição composta consistindo de duas sentenças 
ligadas por “ou”
■ Chove ou faz calor
Implicação
 Enunciados do tipo se...então, chamados implicações ou 
condicionais
 O enunciado subsequente ao “se” é o antecedente e o 
subsequente ao “então” é o consequente.
 Forma
■ Se antecedente então consequente
■ Se sinto frio então visto o casaco.
■ Visto o casaco se sentir frio.
■ Se sentir frio, vista o casaco.
■ Se sentir frio então vista o casaco.
Implicação
 Variações gramaticais da implicação:
− Se P então Q
− P implica Q; P, logo Q
− P só se Q; P somente se Q
− P apenas se Q; P só quando Q
− Q se P; Q segue de P
Bi-implicação
 Enunciados formados com a expressão “se e somente se” 
são chamados bicondicionais ou equivalencias
■ T é um triângulo se e somente se T é um polígono de três 
lados.
 Uma bi-implicação pode ser considerada uma conjunção de 
duas implicações
■ P se e somente se Q
■ P se Q e P se e somente se Q
■ Se Q então P e P se e somente Q
■ Se Q então P e Se P então Q
■ Se P então Q e Se Q então P
Exemplo
A proposta de auxílio está no correio. Se os árbitros a receberem 
até sexta-feira, eles a analisarão. Portanto, eles a analisarão 
porque se a proposta estiver no correio, eles a receberão até 
sexta-feira. (C, S, A)
C: A proposta de auxílio está no correio.
S: Os árbitros recebem a proposta até Sexta-feira.
A: Os árbitros analisarão a proposta.
. C
. SA
. CS {C, SA, CS} |-- A
□ A
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30