Conceitos Básicos
Lógica para Programação
1
Lógica
 A lógica é usada em Informática para desenvolver
linguagens que modelam situações e que fornecem
mecanismos para raciocinar sobre essas situações de
modo a que se possa garantir que os resultados obtidos
estão correctos.
 Definição de lógica no contexto desta cadeira: ramo do
conhecimento que aborda a analise de argumentos, ou a
analise dos métodos para distinguir argumentos validos
de argumentos inválidos.
Lógica para Programação
2
Proposições
 Frases declarativas que fazem afirmações sobre algo
 Exemplos
 Sócrates é homem.
 Todas as aves têm penas.
 Todos os homens são mortais.
 2 e 3 são divisores de 6.
 Contra-exemplos
 O que é um dinossauro?
 Diga qual é o seu nome.
 Could you please pass me the salt?
Lógica para Programação
3
Premissas e conclusões
 Objectivo da lógica: geração de raciocínio correcto.
 Input = premissas: conjunto de frases declarativas que se
assume serem verdadeiras.
 Output = conclusões: conjunto de outras frases, geradas a
partir das premissas, que são verdadeiras nessa situação.
 Argumento - é um par (premissas,conclusão) também
representado por (,).
 Inferência - é o processo de geração de conclusões a partir de
premissas.
Lógica para Programação
4
Argumentos
 Representação de um argumento:
 Em linguagem corrente as premissas e a conclusão são relacionadas
com palavras como
então
portanto
logo
 Em lógica podem ser usadas duas representações alterativas:
({todos os Homens são mortais, Sócrates é um homem}, Sócrates
é mortal)
todos os Homens são mortais
Sócrates é um homem
 Sócrates é mortal
Lógica para Programação
5
Argumentos válidos e inválidos
 Diz-se que
 Um argumento (,) é valido
ou que
 implica logicamente 
ou, ainda, que
 é uma consequência lógica de 
sse
for logicamente impossível ter todas as premissas verdadeiras e a
conclusão falsa.
 Caso contrario o argumento é inválido.
Lógica para Programação
6
Validade/Invalidade vs Verdade/Falsidade
 Validade/Invalidade são atributos de argumentos
 Verdade/Falsidade são atributos de proposições
 Validade/Invalidade de um argumento é independente dos
conteúdos das proposições
 Validade/Invalidade de um argumento depende apenas da
existência de uma relação entre os valores lógicos (verdadeiros ou
falsos) das premissas e da conclusão
Lógica para Programação
7
Validade/Invalidade vs Verdade/Falsidade (cont.)
Valores lógicos (,)
Argumento válido
(Verdadeiro,Verdadeiro)
todos os homens são mortais
Sócrates é um homem
 Sócrates é mortal
(Verdadeiro,Falso)
todas as aves são humanos
(Falso,Verdadeiro)
todos os humanos têm penas
 todas as aves têm penas
todos os cães são felinos
(Falso,Falso)
todos os felinos têm penas
 todos os cães têm penas
Lógica para Programação
Argumento inválido
todos as pessoas são humanos
 todos os homens são pessoas
todos os cães são animais
 todos os animais são cães
todos os animais são cães
 todos os cães são animais
todos os gatos são cães
 todos os cães são gatos
8
Princípio da irrelevância do valor lógico
Princípio da irrelevância do valor lógico:
Excepto no caso em que as premissas são todas verdadeiras e a
conclusão e falsa, a verdade/falsidade das proposicões que
constituem um argumento não é relevante para determinar a
validade/invalidade do argumento.
Lógica para Programação
9
Forma dos argumentos
A forma de um argumento é estudada independentemente do domínio:
as partes das proposicões são substituídas por símbolos associados à
categoria gramatical (nome proprio, substantivo, adjectivo).
Por exemplo o argumento:
Bobi é um animal
todos os cães são animais
Bobi não é cão
 nem todos os animais são cães
tem a forma:
A é um B
todo o C é B
A não é C
 nem todos os B são C
em que A é um nome próprio e B e C são substantivos
Lógica para Programação
10
Forma dos argumentos (cont.)
Por exemplo os dois argumentos:
Piupiu é uma ave
TESTE é um nome em Java
nenhuma ave tem barbatanas
 Piupiu não tem barbatanas
nenhum nome em Java contém o caracter %
 TESTE não contém o caracter %
têm a mesma forma:
A é um B
nenhum B tem C
 A não tem C
em que A e um nome próprio e B e C são substantivos
Princípio da forma: se dois argumentos têm a mesma forma então são ambos
válidos ou ambos inválidos.
Lógica para Programação
11
Sistema Formal
 A lógica é um sistema formal porque estuda argumentos do ponto
de vista da forma.
 A lógica utiliza símbolos para descrever em termos lógicos os
objectos que são comuns a formas de argumentos.
 Por exemplo a forma:
A é um B
nenhum B tem C
 A não tem C
 pode ser apresentada de um modo mais compacto como:
B(A)
x [B(x) C(x)]
 C(A)
em que todos é representado por , implica por  e não por 
Lógica para Programação
12
Metodologia para determinar validade/invalidade
Lógica para Programação
13
Metodologia para determinar validade/invalidade (cont.)
 Embora um argumento seja sempre válido ou inválido, a sua
validade ou invalidade pode ser desconhecida.
Por exemplo o último teorema de Fermat foi formulado no sec.
XVII mas só foi provado em 1993.
({axiomas da aritmética},
para n > 2, não existem inteiros x,
y e z tais que zn = xn + yn)
Lógica para Programação
14
Componentes de uma lógica
 A linguagem de uma lógica é definida através de um conjunto de
regras de formação que especificam as frases possíveis da lógica,
denominadas formulas bem formadas (fbfs).
 Seja L a linguagem que corresponde às fbfs. Logo, um argumento
é um par (,) no qual   L e  L.
 Podemos manipular as frases da linguagem a dois níveis
diferentes:
 A nível simbólico - sistema dedutivo: realização de operações
de manipulação de símbolos que dão origem a sequências de
frases que começam pelas premissas e tentam obter uma
conclusão.
 A nível do significado - sistema semântico: atribuição de
significado/valor lógico às proposições de um argumento com o
objectivo de avaliar validade/invalidade de um argumento.
Lógica para Programação
15
Sistema dedutivo
 Composto por um conjunto de regras para a manipulação de
símbolos chamadas regras de inferência. Estas regras especificam
como formar novas fbfs a partir das fbfs existentes.
 Prova de um argumento (,): sequência finita de fbfs geradas a
partir de  de modo a obter , tal que cada fbf ou é uma premissa
ou é o resultado da aplicação de uma regra de inferência a uma ou
mais fbfs anteriores da prova.
 Axioma: fbf que é aceite sem demonstração.
Lógica para Programação
16
Derivação, demonstração e teoremas
 Dado um argumento (,),  é derivável a partir de , ou seja,
  sse existir uma sequência de regras de inferência que
aplicadas às fbfs de  (e às fbfs geradas a partir de ) produz
. Por outras palavras,  é derivável a partir de  se existe uma
prova de  a partir de .
 Se 
 então o argumento (,) e demonstrável.
 O conjunto de todas as fbfs deriváveis a partir de   L
corresponde à teoria gerada a partir de , ou seja, aos
teoremas de  (Th()).
Lógica para Programação
17
Sistema semântico
 Especifica as condições sob as quais as proposições são
verdadeiras ou falsas
 Uma interpretação permite determinar os valores lógicos das
proposições
 Dado um argumento (,), se não existe nenhuma interpretação
que torna todas as proposições em  verdadeiras e  falso, então
diz-se que  implica logicamente  ou que  é uma implicação lógica
de  , ou seja,  .
 Se 
 então o argumento (,) é válido.
Lógica para Programação
18
Sistema dedutivo e sistema semântico
 Solidez (ou coerência) de uma lógica: qualquer argumento demonstrável
(pelo sistema dedutivo) é válido (de acordo com a semântica).
 Completude de uma lógica: qualquer argumento válido (de acordo com a
semântica) e demonstrável (pelo sistema dedutivo).
Os conceitos de solidez e completude estabelecem uma relação entre o
sistema dedutivo e a semântica.
Numa lógica sólida e completa os conceitos de derivabilidade e validade são
equivalentes.
Lógica para Programação
19