Lógica de 1a Ordem
Introdução
„
Exemplo: Representar na Lógica Proposicional
Lógica Formal
Todo homem é mortal
Sócrates é um homem
Logo, Sócrates é mortal
Lógica de 1a Ordem
Se representarmos por:
P: Todo homem é mortal
Q: Sócrates é um homem
R: Sócrates é mortal
{P, Q} |≠ R
UNIVERSIDADE FEDERAL DE ALAGOAS
Lógica, Informática e Comunicação
Prof. Rômulo Nunes de Oliveira
Lógica de 1a Ordem
Introdução
„
Isso acontece porque os atributos (predicados ou
características) de P, Q e R não são considerados
Lógica de 1a Ordem
Introdução
„
„
„
„
Na Lógica Proposicional (LP) um átomo (P, Q,
R,...) representa uma sentença declarativa que
pode ser V ou F, mas não ambos.
„
Um átomo é tratado como uma entidade única.
Seus atributos e componentes são desprezados
Muitas idéias não podem ser tratadas de
maneira tão simples
„
Para provar que esse argumento é válido, é
necessário identificar indivíduos tais como
Sócrates, e seus predicados.
Predicados descrevem características ou
relacionamentos entre indivíduos (objetos)
A Lógica dos Predicados apresenta mais três
conceitos lógicos:
„
„
„
termos,
predicados e
quantificadores.
1
Enunciados Categóricos
Todo S é P
Qualquer que seja x, se x é S, então x é P.
Enunciados Categóricos
Exemplo Formalizar:
Todo homem é mortal
Sócrates é um homem
Logo, Sócrates é mortal
∀x (S(x) → P(x))
Considerando
Predicados
M(x): x é mortal
H(x): x é um homem
Um individuo: Sócrates
Nenhum S é P
Qualquer que seja x, se x é S, então x não é P.
∀x (S(x) → ~P(x))
„
Enunciados Categóricos
Exemplos:
Algum S é P
„
Para pelo menos um x, x é S e x é P.
∃x (S(x) ^ P(x))
„
Algum S não é P
Para pelo menos um x, x é S e x não é P.
∃x (S(x) ^ ~P(x))
∀x (H(x) → M(x))
H(sócrates)
M(sócrates)
Para formalizar os argumentos que
seguem, Interprete as letras C, R, V e
S como:
C ≡ está chovendo;
R ≡ é uma rã;
V ≡ é verde;
S ≡ é saltitante;
a – Todas as rãs são verdes.
∀x (R(x) → V(x))
2
Exemplos:
„
„
„
„
b – Nenhuma rã é verde.
∀x (R(x) → ~V(x))
c – Algumas rãs são verdes.
∃x (R(x) ^ V(x))
d – Toda coisa é uma rã.
∀x (R(x))
e – Nada é uma rã.
∀x (~R(x)) ou ~∃x (R(x))
Exemplos:
„
f – Qualquer coisa é uma rã verde.
∀x (R(x) ^ V(x))
„
g – Está chovendo e algumas rãs estão
saltitando.
C ^ ∃x (R(x) ^ S(x))
„
h – Somente rãs são verdes.
∀x (V(x) → R (x))
Exemplos:
„
i – Algumas rãs verdes não estão saltitando.
∃x ((R(x) ^ V(x)) ^ ~S(x))
„
j – Rãs verdes saltitam se, e somente se ,
está chovendo.
∀x ((R(x) ^ V(x)) → (S(x) ↔ C))
Exercício:
„
Para formalizar os argumentos que seguem considere
a interpretação:
Indivíduos:
Carlos, João e Maria
Predicados:
Mecânico(x) ≡ x é mecânico
Enfermeiro(x) ≡ x é enfermeiro
Ama(x, y) ≡ x ama y
3
Exercício:
1) Carlos é mecânico
Mecânico(Carlos)
2) Carlos e João são mecânicos
Mecânico(Carlos) ^ Mecânico(João)
3) Carlos é mecânico ou enfermeiro
Mecânico(Carlos) v Enfermeiro(Carlos)
Exercício:
4) Se Carlos é mecânico então Carlos não é
enfermeiro
Mecânico(Carlos) → ~Enfermeiro(Carlos)
5) João ama Maria
Ama(João, Maria)
6) João ama a si próprio
Ama(João, João)
Exercício:
7) Todo mundo ama João
∀x(Ama(x, João))
8) Existe alguém que Maria não ama
∃x(~Ama(Maria, x))
9) Todo mundo é amado por alguém
∀x∃y(Ama(y, x))
Exercício:
10) Alguém é amado por todos
∃x∀y(Ama(y,x))
11) Existe alguém que ama todo
mundo
∃x∀y(Ama(x,y))
12) Alguém ama alguém
∃x∃y(Ama(x,y))
4
Exercício 2: EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
um quantificador e predicados monádicos
„
Não existem marcianos (M(x) − x é marciano)
(não existe x tal que x seja um marciano)
¬ ∃x M(x)
( ou
para todo x, x não é um marciano)
Exercício 2: EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
um quantificador e predicados monádicos
„
Os morcegos são mamíferos (C(x) − x é
morcego; M(x) − x é um mamífero)
(para todo x, se x é um morcego, x é
um mamífero)
∀x (¬ M(x))
Exercício 2:
„
∀x (C(x) → M(x))
Exercício 2:
EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
um quantificador e predicados monádicos
EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
um quantificador e predicados monádicos
Nem todos são sábios (S(x) − x é sábio)
„
(para nem todo x, x é sábio )
¬ ∀x S(x)
(ou existe um x tal que x não é sábio)
∃x (¬ S(x))
Os cavalheiros não são sempre ricos
(para nem todo x, se x é um cavalheiro então
x é rico)
¬ ∀x (C(x) → R(x))
(ou, existe um x tal que x é um cavalheiro e x
não é rico)
∃x (C(x) ∧ ¬ R(x))
5
Exercício 2: EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
um quantificador e predicados monádicos
„
Somente os médicos podem cobrar por
tratamento clínico
Exercício 2: EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
mais de um quantificador e predicados
monádicos
„
(existe x tal que x é esperto, e existe y
tal que y não é esperto)
(para todo x, se x pode cobrar por
tratamento clínico, então x é médico)
∃x E(x) ∧ ∃y (¬ E(y))
∀x (C(x) → M(x))
Exercício 2:
EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
um quantificador e predicados monádicos
„
Nenhum carro é seguro, a menos que tenha
bons freios
~Ex ( C(x) ^ S(x) ) ↔ ~F(x)
Ou...
(para todo x, se x é um carro, então x é
seguro se e somente se tiver bons freios)
∀x [ C(x) → (S(x) ↔ F(x)) ]
Alguns são espertos, outros não
Exercício 2: EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
mais de um quantificador e predicados
monádicos
„
Existem políticos honestos e desonestos
(existe x tal que x é político e x é
honesto, e existe y tal que y é político e
y não é honesto)
∃x (P(x) ∧ H(x)) ∧ ∃y (P(y) ∧ ¬ H(y))
6
Exercício 2: EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
Relações
„
Todos têm pai
Exercício 2: EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
Relações estabelecendo regras de parentesco
(F(x,y) : x é pai de y)
„
(para todo x existe y tal que y é pai de x)
Genro
se x é casado com a filha de y, então x é
genro de y;
∀x ∃y F(y,x)
„
ou, mais precisamente: se existir z tal que x
seja casado com z, e z seja filha de y, então x
é genro de y
Todas as pessoas têm pai
(para todo x, se x é uma pessoa, existe y tal que y
é pai de x)
∀x ∀y [ ∃z (C(x,z) ∧ F(z,y)) → G(x,y) ]
∀x (P(x) → ∃y F(x,y))
Exercício 2:
Exercício 2:
EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
Relações
„
Existe um ancestral comum a todas as
pessoas
(existe um x tal que para todo y, se y é uma
pessoa, x é ancestral de y)
∃x ∀y (P(y) → A(x,y))
(ou, para todo y, se y é uma pessoa, existe
um x tal que x é ancestral de y)
EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
Relações estabelecendo regras de parentesco
„
Avô
se x é pai do pai de y, então x é avô de y
∀x ∀y [ ∃z (P(x,z) ∧ P(z,y)) → A(x,y) ]
∀y (P(y) → ∃x A(x,y))
7
Exercício 2: EXPRESSÕES TEXTUAIS
MOSTRANDO FORMAS LÓGICA E SIMBÓLICA:
Relações estabelecendo regras de parentesco
„
Cuidados na Formalização:
2) O nome de variáveis não faz diferença
para o significado.
Irmão
se o pai de x for também pai de y, x é
irmão de y
∀x ∀y [ ∃z (P(z,x) ∧ P(z,y)) → I(x,y) ]
Cuidados na Formalização:
1) Variáveis diferentes não classificam
necessariamente objetos diferentes.
Ex.: ∀x∀y ama(x, y)
Afirma não somente que qualquer
pessoa ama uma outra pessoa, como
também que qualquer pessoa ama a si
própria.
Ex.: ∀x∃y ama(y, x) equivale a
∀y∃x ama(x, y) equivale a
∀z∃w ama(w,z)
Cuidados na Formalização:
3) Quando dois ou mais quantificadores
justapõem-se numa mesma parte da
fórmula, uma variável diferente deve ser
usada para cada quantificador.
Ex.: ∀x∃x ama(x, x) não é correto
∀x∃y ama(y, x) é correto
8
Cuidados na Formalização:
„
4) A mesma variável usada em vários
quantificadores, não designa
necessariamente o mesmo objeto em
cada caso.
Ex.: ∃x ama(josé, x) ^ ∃x ama(carlos, x)
Cuidados na Formalização:
„
5) A ordem dos quantificadores consecutivos
afeta o significado somente quando os
quantificadores são diferentes.
Ex.:
∃x∀y ama(x,y) e
∀y∃x ama(x,y)
tem significados distintos
∃x∃y ama(x,y)
e
∃y∃x ama(x,y)
significam a mesma coisa
9