logica proposicional 2009

Lógica I

•

UNDB

1

0

1

0

Paulo Roberto

07.05.2016

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

*
Inteligência Artificial: Lógica Proposicional e Prolog 
Prof. Elaini Simoni Angelotti
elaini.angelotti@gmail.com
*
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
O valor de qualquer proposição composta depende unicamente dos valores lógicos das proposições simples componentes. Por exemplo: P = p ^ q 
*
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.
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)
*
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)
*
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)
*
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)
*
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)
*
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) 
*
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) 
*
Princípios
Uma proposição é INDETERMINADA quando não é uma tautologia e não é uma contradição.
 Ex: p  ~p
*
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 Idempotentes
		p  p  p
		p  p  p
(5) Leis complementares
		p  ~p   (tautologia) (V)
		p  ~p   (contradição) (F)
(6) Leis de Identidade
		p    p 	p    
		p     	p    p
*
Leis de Equivalência
(7) Leis Comutativas
		p  q  q  p 
		p  q  q  p
(8) Leis Associativas
		p  (q  r)  (p  q)  r
 		p  (q  r)  (p  q)  r
(9) Leis Distributivas
		p  (q  r)  (p  q)  (p  r)
		p  (q  r)  (p  q)  (p  r)
*
Leis de Equivalência
(10) Condicional
		p  q  ~(p  ~q)  ~p  q
		~ (p  q)  p  ~q
		p  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