Inteligência Artificial: Lógica Proposicional e Prolog
Prof. Elaini Simoni Angelotti
Lógica Proposicional
Um dos objetivos da lógica é estabelecer uma linguagem formal, onde se pode expressar com clareza, precisão e emitir juízo de verdadeiro ou falso para determinadas frases.
PROPOSIÇÃO é uma frase declarativa (com sujeito e predicado) a qual pode ser atribuído um dos valores verdadeiro (V) ou falso (F).
Lógica Proposicional
Exemplos de proposições: O Japão fica na África 3 + 4 = 7
Exemplos de fases que não são proposições: 3 + 4 Onde você vai?
Lógica Proposicional
proposições
Proposição simples (atômica): não contém nenhuma outra proposição como como parte integrante de si mesma. São designadas por letras minúsculas. Ex: Carlos é careca = q.
Proposição compostas (molecular): formada pela combinação de duas ou mais preposições. Designadas por letras maiúsculas. Ex: Carlos é careca e Pedro é estudante = Q.
Princípios Fundamentais da Lógica
PRINCÍPIO DA NÃO CONTRADIÇÃO: Uma proposição não pode ser verdadeira e falsa ao mesmo tempo
PRINCÍPIO DO TERCEIRO EXCLUÍDO: Toda a proposição ou é verdadeira ou é falsa, nunca ocorrendo um terceiro caso.
O valor lógico de uma proposição simples p, é indicado por V(p). Assim:
p: O sol é verde. V(p) = F
Princípios Fundamentais da Lógica
Os conectivos lógicos são usados para formar novas proposições a partir de outras proposições: ~ (não); (e); (ou exclusivo) (ou); (se então); (se e somente se);
Princípios Fundamentais da Lógica
TABELAS VERDADE para uma proposição simples p o valor será V ou F
p
V
F
O valor de qualquer proposição composta depende unicamente dos valores lógicos das proposições
simples componentes. Por exemplo: P = p ^ q p
V
V
q
V
F
F
F
V
F
Operações Lógicas sobre Proposições
NEGAÇÃO Se p é uma proposição, a negação da proposição p é
denotada por ~p (p) A negação apresenta valor lógico oposto ao da proposição
dada.
p
V
F
~p
F
V
Exemplos: r : Nenhum homem é elegante ~r : Algum homem é elegante
Operações Lógicas sobre Proposições
CONJUNÇÃO () Chama-se conjunção de duas proposições p e q a
proposição representada por “p q ”cujo o valor lógico é V quando ambas as proposições são verdadeira e F nos demais casos.
V(p q) = V(p) V(q)
p
V
V
q
V
F
F
F
V
F
p q
V
F
F
F
Operações Lógicas sobre Proposições
DISJUNÇÃO () Chama-se disjunção de duas proposições p e q a
proposição representada por “p q ”cujo o valor lógico é V quando ao menos uma das proposições é verdadeira e F quando ambas as proposições são falsas.
V(p q) = V(p) V(q)
p
V
V
q
V
F
F
F
V
F
p q
V
V
V
F
Operações Lógicas sobre Proposições
DISJUNÇÃO EXCLUSIVA ( ) Chama-se disjunção exclusiva de duas proposições p e q
a proposição representada por “p q ”cujo o valor lógico é V quando uma das proposições é verdadeira e a outra e falsa e F quando ambas as proposições são falsas ou ambas são verdadeiras.
V(p q) = V(p) V(q)
p
V
V
q
V
F
F
F
V
F
p q
F
V
V
F
Operações Lógicas sobre Proposições
CONDICIONAL () Chama-se proposição condicional uma proposição
representada por “p q” cujo o valor lógico é F quando p é verdadeira e q é falsa e V nos demais casos.
V(p q) = V(p) V(q)
p
V
V
q
V
F
F
F
V
F
p q
V
F
V
V
Operações Lógicas sobre Proposições
BICONDICIONAL () Chama-se proposição bicondicional uma proposição
representada por “p q” cujo o valor lógico é V quando p e q são ambos verdadeiros ou falsos e F nos demais casos.
V(p q) = V(p) V(q)
p
V
V
q
V
F
F
F
V
F
p q
V
F
F
V
Princípios
TAUTOLOGIA é toda a proposição composta cujo o valor lógico é sempre verdade (V) quaisquer que sejam os valores lógicos das proposições simples componentes.
Ex: ~(p ~p)
p
V
F
~p
F
V
p ~p
F
F
~(p ~p)
V
V
Princípios
CONTRADIÇÃO é toda a proposição composta cujo o valor lógico é sempre falso (F) quaisquer que sejam os valores lógicos das proposições simples componentes.
Ex: (p ~p)
p
V
F
~p
F
V
p ~p
F
F
Princípios
Uma proposição é INDETERMINADA quando não é uma tautologia e não é uma contradição.
Ex: p ~p
p
V
F
~p
F
V
p ~p
F
V
Leis de Equivalência
Dadas as proposições compostas P e Q, diz-se que ocorreu uma equivalência entre P e Q quando suas tabelas-verdade forem idênticas. (P Q)
É possível simplificar as proposições, utilizando as seguintes leis de equivalência:(1) Negação da negação
~ (~ p) p
(2) Negação da Conjunção~ (p q) ~p ~q
(3) Negação da Disjunção
~ (p q) ~p ~q
Leis de Morgan
Leis de Equivalência
(4) Leis Idempotentesp p pp p p
(5) Leis complementaresp ~p (tautologia) (V)p ~p (contradição) (F)
(6) Leis de Identidadep p p p p p
Leis de Equivalência
(7) Leis Comutativasp q q p p q q p
(8) Leis Associativasp (q r) (p q) r
p (q r) (p q) r
(9) Leis Distributivasp (q r) (p q) (p r)p (q r) (p q) (p r)
Leis de Equivalência
(10) Condicionalp q ~(p ~q) ~p q~ (p q) p ~qp q ~q ~p
Dada a proposição p q:* a recíproca da condicional é q p* a contrapositiva é ~q ~p* a inversa é ~p ~q
A condicional não satisfaz as leis:* idempotente: p p p* comutativa: p q q p* associativa: (p q) r p (q r)
Leis de Equivalência
(11) Bicondicional
p q (p q) (q p)
~ (p q) p ~q ~p q
p q (p q) (~p ~q)
~ (p q) (p ~q) (~p q)
Regras de Inferência
A lógica tem como um dos seus objetivos o uso de técnicas (regras) de inferência que permitem verificar se uma conclusão é válida a partir de fatos básicos.
Chama-se argumento toda a afirmação de que uma dada sequência finita P1, P2, ..., Pn de proposições tem como conseqüência uma proposição final Q.
Um argumento P1, P2, .., Pn | Q diz-se válido se e somente se Q é verdadeiro (V) todas as vezes que P1, P2, ..., Pn são verdadeiras (V).
A verdade das premissas é incompatível com a falsidade da conclusão.
Regras de Inferência
(1) Regras de Adição (AD)
(i) p | p q
(ii) p | q p(2) Regras de Simplificação (SIMP)
(i) p q | p
(ii) p q | q
(3) Regras da Conjunção (CONJ)
(i) p, q | p q
(ii) p, q | q p
Regras de Inferência
(4) Regra da Absorção (ABS)
p q | p (p q)
(5) Regra do Modus Ponens (MP)p q, p | q
(6) Regra do Modus Tollens (MT)
p q, ~q | ~ p
(7) Regra do Silogismo Disjuntivo (SD)
(i) p q, ~p | q
(ii) p q, ~q | p
Regras de Inferência
(8) Regra do Silogismo Hipotético (SH)
p q, q r | p r
(9) Regra do Dilema Construtivo
p q, r s, p r | q s
(10) Regra do Dilema Destrutivo
p q, r s, ~q ~s | ~p ~r