lpo_reduzido

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Cálculo dos Predicados ou Lógica de Primeira Ordem
(Versão Reduzida)
Claudio e Rogério
(Lógica Matemática)
Autorização de Uso	
	Este conjunto de slides pertence ao Prof. José Augusto Baranauskas (http://dfm.ffclrp.usp.br/~augusto)
	Com sua autorização, alterei conforme interesses da disciplina de Lógica Matemática (LMA)
	Esta parte constitui-se de fundamentos (essenciais) de Prolog e da PLR
	Se algum erro for encontrado ... fui eu, pois alterei algumas fontes do ppt original, para odp
Apenas anotem o que não está escrito :
	Anotem o que for interessante e que não está escrito
	O material de hoje está em : http://www.joinville.udesc.br/coca → cursos → LMA
	Ou: http://www2.joinville.udesc.br/~coca/index.php/Main/MaterialCursos
Nota	
	O conteúdo é relativamente longo … tinhoso
	Para o curso de LMA … ficaremos com a 1a parte, onde quantificadores serão reduzidos a proposições, e regras de inferência (teoremas) serão aplicados (ver livro da Judith Gersting – Matemática para Computação)
	A 2a. parte fica para os interessados em entender profundamente, como o PROLOG funciona. 
	Variáveis
	Quantificadores
	Relações
Lógica Proposicional
	Proposições
	Regras Inferenciais
	Teoremas
Lógica dos Predicados
Onde estamos?
Introdução
	No Cálculo Proposicional, utilizamos proposições para representação de conceitos. Ex: O céu é azul.
	No Cálculo dos Predicados ou LPO utilizaremos:
	Objetos (pertencentes a um domínio D)
	Fatos sobre objetos
	Relações ou relacionamentos entre os objetos de domínios D = D1UD2UD3 ...
Onde queremos chegar ?
Seja o enunciado:
“Todo homem é mortal
Sócrates é um homem”
Demonstre que Sócrates é mortal.
Escrevendo em LPO
1. x ( homem(x)  mortal(x) )
2.	 homem(sócrates)
E como resolver isto?
Resolvendo com LPO+LP
1. x ( homem(x)  mortal(x) )
2.	 homem(sócrates)
-------------------------------------------------
3. homem(sócrates)  mortal(sócrates) 
..... Como? Particularização Universal (PU) em 1 com x/sócrates …..
4. mortal(sócrates) 
….. aplicando MP entre 2 e 3
CQD
Em Prolog (a lógica em prática)	
	mortal(X) :- homem(X). 
	homem(socrates).
	
	No compilador/interpretador a pergunta :
	
	?- mortal(X).
	X = socrates
	Yes
	?-
Logo	…....		
	Entender a lógica é saber faz programas de computador
	Uma destas linguagens é o Prolog
	Há muitos elementos … muito o que estudar
	Contudo, há respostas rápidas em se fazer programas
Os Elementos da LPO
Conjunto de símbolos lógicos = { ~, , , ,  }
Quantificadores = { ,  }
Conjunto de variáveis	= {x, y, z, w, ...}
Conjunto de Símbolos (ctes)	= {a, b, c, ..., “alba”, “bete”}
Conjunto de Símbolos de Escrita	= {(, ), ,, [, ], ... }
Functores ou Funções Lógicas	= {f, g, h, ...}
Domínios				= {V, F}
Outros Domínios	= {símbolos em gera, 1, 2, N, R …...}
Motivação
	Dado o domínio 
D={Angélica, Ana Laura, Cláudia}
	Para expressar que todas as mulheres são bonitas no Cálculo Proposicional, é necessário definir uma proposição para cada mulher do domínio D
	p: Angélica é bonita
	q: Ana Laura é bonita
	r: Cláudia é bonita
	…..... faltarão símbolos proposicionais
Motivação
	Suponha D = conjunto de todos brasileiros
	
	Expressar que todas as mulheres são bonitas torna-se inviável (para domínios com grande número de elementos)
	Por exemplo:
Angélica é bonita
Ana Laura é bonita
Cláudia é bonita
Wilma é bonita
Maria Alice é bonita
Ana Paula é bonita
Maria Helena é bonita
...
Solução
	Utilizar variáveis para representar elementos não específicos do domínio
	Por exemplo:
	Para todo XD, se X é mulher então X é bonita 
ou ainda,
		Para todo XD, mulher(X)  bonita(X)
ou ainda pode-se omitir D, já que é conhecido
		Para todo X, mulher(X)  bonita(X)
Predicados
	Para todo X, mulher(X)  bonita(X)
	Para todo X: é o quantificador da variável X
	X: é uma variável
	mulher, bonita: são predicados
	Predicado é uma relação com argumentos que possui valor-verdade associado v(erdade) ou f(also)
	Em resumo: Interpretação(Predicado(xis))={V,F}
	Int(cao(rin-tin-tin))=V ... se existir um ....
	Acompanhe as explicações...
Definições da LPO (uma linguagem formal precisa ter elementos para se demonstrar algo)
	Símbolos Constantes
	Símbolos Variáveis
	Símbolos Funcionais
	Símbolos Predicados
	Termos
	Átomos
	Símbolo de Igualdade 
	Conectivos
	Quantificadores
Símbolos Constantes
	Representam um objeto específico (ou elemento) do domínio do discurso (ou universo) D
	São representados por nomes que se iniciam com uma letra minúscula ou números inteiros ou reais
	Exemplos:
a, b, x, maria, 3, 10e+5
Símbolos Variáveis
	Representam um objeto não específico domínio do discurso D
	São representados por nomes que se iniciam com letras maiúsculas
	Assumem apenas valores do domínio D
	Exemplos:
	A, B, X, Y, Alguém
	se D = {júlia, mônica, carolina},
X não pode assumir o valor “fernando”
Símbolos Funcionais
	Representam funções f no domínio D
f: Dn D, n é a aridade (nº de argumentos)
	Usados para rotular objetos sem dar nomes a eles
	São representados por nomes que se iniciam com letras minúsculas
	Não possuem valor-verdade associado
	Exemplos:
	pé_direito(joão) => Int(pé_direito(joão)) = chute
	mãe_de(maria) => Int(mãe_de(maria)) = josie
	idade(joao) => Int(idade(joao)) = 23
Símbolos Predicados
	Representam relação ou propriedade p de um ou mais objetos no domínio D
p: Dn {v,f}, n é a aridade (nº de argumentos)
	São representados por nomes que se iniciam com letras minúsculas
	Possuem valor-verdade associado
	Exemplos:
	gosta(X,Y)
	empresta(Fulano,Objeto,Alguém)
Observações
	Símbolos variáveis assumem apenas valores no domínio D
	Símbolos funcionais sem argumentos (n=0) são símbolos constantes
	Símbolos funcionais não possuem valor-verdade associado. Ex: maior(3,(4+5)), onde (4+5) estará associado ao símbolo 9.
	Símbolos predicados possuem valor-verdade associado. Ex: Int(maior(3,(4+5)))=F
Termos
	Uma constante é um termo
	Uma variável é um termo
	f(t1, t2, ..., tn) é um termo, onde f é um símbolo funcional e t1, t2, ..., tn são termos
	(t1, t2, ..., tn) é uma tupla de termos
	Exemplos:
	a, baleia
	X, Alguém
	orelha(joão), orelha(mãe(joão))
	onde mãe(joão)=dona_tereza (um mapeamento)
Átomos (ou Fórmulas Atômicas)
	Átomo é um símbolo predicado aplicado a uma tupla de termos
	Um átomo assume a forma p(t1, t2, ..., tn)
onde p é um símbolo predicado e t1, t2, ..., tn são termos
	Exemplos:
	gosta(maria,ana)
	gosta(maria,X)
	gosta(maria,mãe(joão))
	empresta(maria,livro,joão)
	empresta(maria,livro,mãe(joão))
Símbolo de Igualdade
	O símbolo de igualdade é utilizado para fazer declarações que afirmam que dois termos se referem ao mesmo objeto
	Exemplo
	pai(joão) = henrique
	Indica que o objeto referido por “pai(joão)” e o objeto referido por “henrique” são iguais
Conectivos
Conectivos (onde X é variável, P é predicado):
	e						conjunção
	ou						disjunção
	não					negação
	condicional				condicional
	bicondicional				bicondicional
	para todo X, P	X P	quant. universal
	existe X, P		X P		quant. existencial
Conectivos
Os conectivos:
	e						conjunção
	ou						disjunção
	não					negação
	condicional				condicional
	bicondicional				bicondicional
	
possuem o mesmo significado que no CP
Mas não quanto os: X P e X P 
Quantificadores
	Permitem expressar propriedades ou relações de toda uma coleção de objetos
	Evitam enumeração
de cada objeto separadamente
	Atuam apenas sobre objetos do domínio
	Pode-se definir vários quantificadores, desde que cada um atue apenas sobre objetos
	Os dois mais comuns: quantificador universal e quantificador existencial
Quantificador Universal 
	Permite enumerar todos os objetos do domínio D
	Representado pelo símbolo 
	X P é lido como
	“para todo XD, P é verdade” ou
	“para todo XD, P” ou
	“para todo X, P”
	Exemplo
	X gosta(ana,X)
	é lido como “para todo X, Ana gosta deste X” ou “Ana gosta de todos”
Quantificador Universal 
Exemplo: “Fredegunda gosta de todos”
	D={frajola, tom, fredegunda}
	X gosta(fredegunda,X) é equivalente a:
	gosta(fredegunda,frajola)	 
gosta(fredegunda,tom)		
gosta(fredegunda,fredegunda)
	A interpretação acima de cada termo em “gosta” é V
	Fora dele é falso. Ex: Int(gosta(joe,jose)) = F.
	Ou seja, interpretação é a análise de sua consistência ou satisfatibilidade.
	Logo: se é para todos, então é um  entre os termos!
Quantificador Universal 
Exemplo: “Todos os gatos são mamíferos”
	D={fredegunda, frajola, tom}
	X(gato(X)  mamífero(X)) equivale a:
	(gato(frajola)		mamífero(frajola))	
(gato(tom)		mamífero(tom)) 	
(gato(fredegunda)		mamífero(fredegunda))	
	Note que existe uma conjunção entre cada sentença individual (sem o quantificador)
	Assim, é necessário que todas sejam v(erdade) para que X(gato(X)  mamífero(X)) seja v (verdade)
Exercício 01
Seja D = { joao , ana, paulo }
x (gosta(ana,X))
Interprete e avalie a validade da fórmula acima:
Φ(gosta(ana,ana)) = V % efetivamente ela se gosta
Φ(gosta(ana,joao)) = V  % namora o Joao e eh soh gosta um além dela :
Φ(gosta(ana, paulo)) = F
Quanto a interpretacao final?
Φ(Conjunção de todos as Φ nos Domínios ) =
Φ(gosta(ana,ana) AND gosta(ana,joao) AND gosta(ana, paulo) ) =
Φ(gosta( V AND V AND F ) = F
Então a fórmula é FALSA
Exercício 02
Idem ….
D = { joao , ana }
x (gosta(ana,X))
Interprete?
Φ(gosta(ana,ana)) = V %%% efetivamente ela se ama
Φ(gosta(ana,joao)) = V %%% namora o Joao e eh só gosta de um além dela
Quanto a interpretação final?
Φ(Conjunção de todos as Φ nos Domínios ) =
Φ(gosta(ana,ana) AND gosta(ana,joao) ) =
Φ(gosta( V AND V ) = V
Então a fórmula é VERDADEIRA
Quantificador Universal 
	X(gato(X)  mamífero(X)) equivale a:
((gato(frajola)		mamífero(frajola))	
(gato(tom)		mamífero(tom)) 	
(gato(fredegunda)		mamífero(fredegunda)))
	Sabendo que Frajola e Tom são gatos, tem-se:
(v		mamífero(tom))	
(v		mamífero(frajola))	
(f		mamífero(fredegunda))
	Obtém-se uma afirmativa sobre sobre o lado direito da implicação apenas para objetos que satisfazem o lado esquerdo
	 :: é o conectivo natural para uso com 
	Exercícios: pausa para exercícios
Exercício 03
Socrates é um homem e Zeus é um deus mitológico.
D = { socrates, zeus }
x (homem(X) ---> mortal(X) )
Interprete a fórmula acima. Esta éh verdadeira ou falsa?
Φ(homem(socrates)) = V 
Φ(mortal(socrates)) = V
Φ(homem(zeus)) = F
Φ(mortal(zeus)) = F
Compondo a interpretacao acima
Φ( (V → V) AND (F → F)) =
Φ( V AND V ) = V
Então a fórmula é VERDADEIRA
Exercício 04
Socrates é um homem e Zeus que é homem e é um deus mitológico.
D = { socrates, zeus }
x (homem(X) → mortal(X) )
Interprete a fórmula acima. Esta é verdadeira ou falsa?
Φ(homem(socrates)) = V 
Φ(mortal(socrates)) = V
Φ(homem(zeus)) = V %%% um homem 
Φ(mortal(zeus)) = F %%% que é imortal ...
Compondo a interpretacao acima
Φ( (V → V) AND (V → F)) =
Φ( V AND F ) = F
Então a fórmula é FALSA
Quantificador Existencial 
	Permite enumerar pelo menos um objeto do domínio D
	Representado pelo símbolo 
	X P é lido como
	“existe um XD tal que P é verdade” ou
	“existe um XD, P” ou
	“existe X, P”
	Exemplo: X gosta(ana,X) é lido como “existe X tal que Ana gosta deste X” ou “Ana gosta alguém”
Quantificador Existencial: 
Exemplo:
	D={frajola, tom, fredegunda}
	X gosta(fredegunda,X) é equivalente a:
gosta(fredegunda,frajola)		 
gosta(fredegunda,tom)		 
gosta(fredegunda,fredegunda)
	Note que existe uma disjunção entre cada sentença individual (sem quantificador) 
	Assim, é necessário que pelo menos uma seja v(erdade) para que X gosta(ana,X) seja 
 :: é o conectivo natural do  
Exercício 01
Seja D = { joao , ana, paulo }
x (gosta(ana,X))
Interprete e avalie a validade da fórmula acima:
Φ(gosta(ana,ana)) = V % efetivamente ela se gosta
Φ(gosta(ana,joao)) = V  % namora o Joao e eh soh gosta um além dela :
Φ(gosta(ana, paulo)) = F
Quanto a interpretacao final?
Φ(Disjunção de todos as Φ nos Domínios ) =
Φ(gosta(ana,ana) OR gosta(ana,joao) OR gosta(ana, paulo) ) =
Φ(gosta( V OR V OR F ) = V
Então a fórmula é Verdadeira
Exercício 02
Idem ….
D = { joao , ana }
x (gosta(ana,X))
Interprete?
Φ(gosta(ana,ana)) = V %% efetivamente ela se ama
Φ(gosta(ana,joao)) = V %% namora o Joao e eh só gosta dele além dela
Quanto a interpretação final?
Φ(Disjunção de todos as Φ nos Domínios ) =
Φ(gosta(ana,ana) OR gosta(ana,joao) ) =
Φ(gosta( V OR V ) = V
Entao a formula eh VERDADEIRA
Quantificador Existencial 
Exemplo: “Existe uma mulher bonita”
	D={frajola, tom, fredegunda}
	X (mulher(X)  bonita(X)) é equivalente a:
((mulher(frajola)  bonita(frajola))		 
(mulher(tom)  bonita(tom))			 
(mulher(fredegunda)  bonita(fredegunda)))
	Sabendo-se que Fredegunda é uma mulher bonita(!), a terceira disjunção é verdadeira, tornando a sentença original verdadeira 
	: é o conectivo natural para uso com 
Exercício 03
Sócrates é um homem e Zeus é um deus mitológico.
D = { socrates, zeus }
x (homem(X) → mortal(X) )
Interprete a fórmula acima. Esta fórmula é verdadeira ou falsa?
Φ(homem(socrates)) = V 
Φ(mortal(socrates)) = V
Φ(homem(zeus)) = F
Φ(mortal(zeus)) = F
Compondo a interpretação acima :
Φ( (V → V) OR (F → F)) =
Φ( V OR V ) = V
Logo, a fórmula acima é verdadeira
Exercício 04
Socrates é um homem e Zeus que é homem e é um deus mitológico.
D = { socrates, zeus }
x (homem(X) → mortal(X) )
Interprete a fórmula acima. Esta é verdadeira ou falsa?
Φ(homem(socrates)) = V 
Φ(mortal(socrates)) = V
Φ(homem(zeus)) = V %%% um homem 
Φ(mortal(zeus)) = F %%% que é imortal ...
Compondo a interpretacao acima
Φ( (V → V) OR (V → F)) =
Φ( V OR F ) = V
Logo, a fórmula acima é verdadeira
Observações	
	Constata-se a forte dependência do domínio na interpretação das fórmulas
	Contudo há fórmulas sempre falsas ora sempre verdadeiras.
	Exemplos : x (px OR ~px) = x (p(x) OR ~p(x)) 
	Exemplos : x (px AND ~px) = x (p(x) AND ~p(x))
	Igualmente para o quantificador dos exemplos acima : 
Propriedades do  e  :
	São definições simples
	Usa-se na prova de teorema como na LP
	Particularização Existencial (PE) e Universal (PU)
	Generalização Existencial (GE) e Universal (GU)
	Há regras de uso …. mas a proposta é instanciar há objetos no domínio (a particularização), ou do domínio generalizar uma fórmula com  e , desde que as variáveis não estejam relacionadas há outras já existentes. 
Propriedades Universal:
	Exemplo : PU: Se X(gato(X)), uma PU é dada por gato(frajola), dado que D={frajola}, pois frajola pertence a D
	Exemplo : GU: Se gato(frajola), temos u(gato(u)) onde u≠x onde x estava em alguma parte outra fórmula. O u é variável e não átomo.
Propriedades Existencial:
	PE: Se X(gato(X)), uma PE é dada por gato(frajola), dado que D={frajola}
	GE: Se gato(frajola), temos u(gato(u)) onde u≠x onde x estava em alguma outra fórmula. O u é variável e não átomo.
	Cuidado na PE e GE … veja algo inválido:
p(a) ├ xp(x) … isto é verdade
	Contudo: p(a,x) ├ xp(x,x) aqui o x já estava
ligado a fórmula, logo é falso este teorema.
	├ simbolo de teorema
Exemplos
	x y(ama(x,y)) = x y(ama(x,y))
	yx (ama(x,y)) = yx (ama(x,y))
Cuidados com GE, PE, GU e PU
	TEM QUE ATUALIZAR DO LIVRO DA JUDITH GERSTING
	Mover este conteudo para o final da parte 1
	Incluir exercicios completos
	Exercícios agora
Simbolização
	Assim, como na lógica proposicional é possível simbolizar sentenças em linguagem natural no Cálculo dos Predicados
	Normalmente, adotam-se nomes significativos para predicados, constantes e símbolos funcionais
	É comum também definir o significado de cada predicado ou símbolo funcional
	Ex: gosta(A,B): A gosta de B
Exercício
Dado o esquema abreviador
	e(X,Y): X estuda Y (para experts exy)
	gosta(X,Y): X gosta de Y (simplificada: gxy)
Simbolizar as seguintes frases
	Ana gosta do livro
	Ana estuda o livro
	Se Ana estuda o livro então ela gosta dele
	Ana gosta da mão de Pedro
	Ana gosta do livro
gosta(ana,livro)
	Ana estuda o livro
e(ana,livro)
	Se Ana estuda o livro então ela gosta dele
e(ana,livro)  gosta(ana,livro) 
	Ana gosta da mão de Pedro
gosta(ana , mão(pedro) ), aqui mão(pedro) é uma função lógica, que está mapeada. mão(pedro) = anel ( ex: passagem a Paris)
	e(X,Y): X estuda Y
	gosta(X,Y): X gosta de Y
Solução
Simbolização
	Embora nomes significativos para os seres humanos sejam adotados para predicados, constantes e símbolos funcionais, é importante lembrar que, para o mecanismo de inferência, eles são apenas símbolos
	O mecanismo de inferência utiliza os símbolos respeitando as regras da linguagem para derivar novas sentenças válidas
	Entretanto, somente os seres humanos é que dão valor semântico real ao significado dos símbolos associados, por exemplo gato(X) indica que X é um animal mamífero com pelos, etc
	Para o mecanismo de inferência é indiferente representar um gato como “gato(X)” ou “g(X)” ou “cat(X)” ou “c(X)” ou “a(X)” ou ...
Como diferenciar uma fórmula lógica de uma função?	
	Em LP: { f1, f2, … fn}... estes são predicados, sempre, com mapeamento em {V,F}
	Agregando uma função g, então f(g(X,Y...)), onde f é predicado e g é função!
	Ex: impar(s(0)).
Simbolização
	A simbolização permite transformar uma sentença ou fórmula em linguagem natural para a linguagem lógica (e vice-versa)
	Não existe uma única forma de simbolizar um determinado conhecimento
	Por exemplo: “A casa é amarela”
	amarela(casa1.3)
	cor(casa1,amarela)
	valor(cor,casa1,amarela)
	é(casa1,amarela)
	No slide seguinte (cuidado aqui...)
	X é uma variável (por estar sempre quantificada)
	m é uma propriedade ou relação (predicado)
	n é uma propriedade ou relação (predicado)
Simbolização
	X (m(X)  n(X))
	Todo m é n
	m são n
	Cada m é um n
	Qualquer m é um n
	Todos os objetos com a propriedade m são objetos que têm a propriedade n
	X (m(X)  ¬n(X))
	Nenhum m é n
	Ninguém que seja m é n
	Nada que seja m é n
	Nenhum dos m é n
	X (m(X)  n(X))
	Alguns m são n
	Existem m que são n
	Há m que são n
	Alguns m são n
	X (m(X)  ¬n(X))
	Alguns m são não n
	Alguns m não são n
	Certos m não são n
	Existem m que não são n
	Pelo menos um m não é n
Exemplos e Exercícios
	Todos os homens são mortais
	X (homem(X)  mortal(X))
	Alguns gatos são amarelos
	X (gato(X) amareloX))
	Nenhuma baleia é peixe
	X (baleia(X)  ¬peixe(X))
	Nem tudo que é reluz é ouro
	X (reluz(X)  ¬ouro (X))
	¬X (reluz(X)  ouro(X))
	Meninas e meninos gostam de brincar
	X (menina(X)  menino(X)  gosta(X,brincar))
	X (menino(X)  gosta(X,brincar)) Y (menina(Y)  gosta(Y,brincar))
	Leite e banana são nutritivos
	X (leite(X)  banana(X)  nutritivo(X))
Exemplos e Exercícios
	Há pintores que não são artistas mas artesãos
	X (pintor(X)  ¬artista(X) artesão(X))
	Não há crime sem lei que o define
	X (crime(X)  Y(lei(Y) define(Y,X))
	Jacó não foi o primeiro homem
	X (homem(X) nasceu(X,DataX) nasceu(jacó,D) DataX < D)
	Não há bom livro escrito por maus autores
	X ((livro(X) bom(X)  Y(autor(Y) bom(Y) escreveu(Y,X)))
	Todos os números pares são divisíveis por dois
	X (natural(X) par(X)  divisível(X,2))
	Todos os animais devem ser protegidos pelos homens
	X Y (homem(X)  animal(Y)  protege(X,Y) )
	Todos os homens foram gerados por alguma mulher
	X (homem(X)  Y (mulher(Y) mãe(Y,X))
	Há pelo menos dois senadores
	X Y (senador(X)  senador(Y)  XY)
	p(X) : X é uma pessoa
	e(X,Y) : X engana Y
	X((p(X)  Y(p(Y)  e(X,Y)))  e(X,X))
Traduzir para Linguagem Natural
Pessoas que enganam outras pessoas enganam a si mesmas
	e(X) : X é um erro
	h(X) : X é humano
	f(X,Y) : X faz Y
1) X(h(X)  Y(e(Y)  f(X,Y)))
2) X(Y(e(Y)  f(X,Y))  h(X))
Traduzir para Linguagem Natural
Todo ser humano erra
	Quem quer que não cometa erros não é humano
	Não é humano quem não erra
Fórmulas Bem Formadas (wff)
Well Formed Formula
1. um átomo é uma wff
2. se α e β são wff e X uma variável livre, então são também wff:
	
3. As únicas wff são definidas por (1) e (2)
existe X, α
X α
para todo X, α
X α
α se e somente se β
α  
se α então β
α  
α ou β
α  
α e β
α  
não α
¬α
lê-se
wff
Prioridade dos Conectivos
maior prioridade
menor prioridade 
 ou 




X, X
Prioridade dos Conectivos
	Exemplo
	X p(X)  Y q(X,Y)  p(Y) significa
X (p(X)  (Y (q(X,Y)  p(Y))))
	A precedência pode ser alterada pelo uso de parênteses
Semântica da LPO
	Para interpretar uma wff no CR é necessário definir o domínio D
	Se os valores-verdade das fórmulas  e  são calculados, então os valores-verdade das fórmulas:
	¬, (  ), (  ), (  ) e (  )
	são determinados usando tabelas-verdade dos conectivos, como definido na Lógica Proposicional
	X  é v se o valor-verdade de  for v para todo X no domínio D; caso contrário será f
	X  é v se o valor-verdade de  for v para pelo menos um X no domínio D; caso contrário será f
Semântica da LPO (interpretação: Φ)
	Uma fórmula  é satisfatível (consistente) se e somente se existe uma interpretação Φ tal que  é v em Φ
	Uma fórmula  é insatisfatível (inconsistente) se e somente se não existe uma interpretação Φ tal que  é v
	Uma fórmula  é válida ou verdadeira (tautologia) se e somente se toda interpretação Φ de  é v
Conseqüência Lógica (f1,f2 … → g) 
	Uma fórmula  é conseqüência lógica de 1, 2, ..., n se e somente se para toda interpretação Φ, se (1  2  ...  n) é v em Φ então  é v em Φ
	Notação
	1, 2, ..., n |= 
	 é equivalente a  () se e somente se
( |= )  ( |= )
	Os teoremas sobre conseqüência lógica vistos no LP também são válidos na LPO
Fórmulas Válidas
	X P(X)			 	 X P(X)
	(X P(X)  X Q(X))	 	 X (P(X)  Q(X))
	X (P(X)  Q(X))	 	 (X P(X)  X Q(X))
	X (P(X)  Q(X))	 	 (X P(X)  X Q(X))
	X (P(X)  c)		 	 (X P(X)  c)
	Como exercício demonstre que as mesmas são válidas. Como diga, use a especificação e a generalização, afim de reduzi-las a LP.
Equivalência entre  e 
	X P(X)		(¬X) (¬P(X))
	X (¬P(X))		(¬X) P(X)
	X (¬P(X)) 		(¬X) P(X)
	X P(X)			(¬X) (¬P(X))
	¬(X P(X))	 	(¬X) P(X)
	¬(X P(X))	 	(¬X) P(X)
2 e 3 são fundamentais !!!
Resumo das Transformaçoes
Judit-Gersting – Livro
x p(x)	 	p(a)				Particularização Universal
x p(x)  	p(a)				Particularização Existencial
p(x)		x p(x)			 Generalização Universal
p(x)		x p(x)			 Generalização Existencial
Fórmulas Relacionais Equivalentes (Ver GE a PU)
	P  X Q		 X (P  Q), se X não ocorre em P
	P  X Q		 X (P  Q), se X não ocorre em P
	P  X Q		 X (P  Q), se X não ocorre em P
	P  X Q		 X (P  Q), se X não ocorre em P
	(X P)  (X Q)	 X (P  Q)
	(X P)  (X Q)	 X (P  Q)
	(X P)  (X Q)	 X Y (P  Q)
	(X P)  (X Q)	 X Y (P  Q)
	P  (X Q)	 X (P  Q), se X não ocorre em P
	P  (X Q)	 X (P  Q), se X não ocorre em P
	X (P  Q)	 X (P  Q), se X não ocorre em Q
	X (P  Q)	 X (P  Q), se X não ocorre em Q
Aqui se encerra a PARTE 1	
	Falta inserir o conteudo do livro da Judith Gersting
	PU, PE, GU, GE …. ver livro da Judith
	Rogerio tenho vários exercicios etc …
	Aqui se encerra o curso.
	De bom tamanho
	Exercícios para todos :: interpretações e teoremas básicos ….. com regras da LP.
José Augusto Baranauskas
Departamento de Física e Matemática – FFCLRP-USP
Autorização de uso para Claudio Cesar de Sá – DCC-UDESC