Lógica de predicados (introducao_a_logica_e_predicados.ppt)

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

*
*
Introdução a lógica
Jeneffer Ferreira Lázaro
email: jenefferferreira@gmail.com
*
*
O que é IA?
Patrick Winston diz que “IA é o estudo de conceitos que permitem aos computadores serem inteligentes”.
Marvin Minsky diz que “IA é a habilidade de resolver problemas difíceis”.
Elaine Rich e Kelvin Knitght dizem que “IA é o estudo de como fazer os computadores realizarem coisas que, no momento, as pessoas fazem melhor”.
Campo do conhecimento que tenta entender e construir agentes inteligentes.
*
*
Origem
Na Grécia Antiga, 342 a.C, o filósofo Aristóteles sistematizou o conhecimento existente em Lógica, elevando-o à categoria de ciência.
Aristóteles se preocupava com as formas de raciocínio que, a partir de conhecimentos considerados verdadeiros, permitiam obter novos conhecimentos.
A partir dos conhecimentos tidos como verdadeiros, caberia à Lógica a formulação de leis gerais de encadeamentos de conceitos e juízos que levariam à descoberta de novas verdades. Essa forma de encadeamento é chamada, em Lógica, de argumento.
*
*
Ilustrando
Através da lógica, conhecimentos tidos anteriormente produzem novos conhecimentos.
*
*
Argumentos
Argumento é uma seqüência de proposições (declarações/afirmações) na qual uma delas é a conclusão e as demais são premissas.
A conclusão de um argumento é aquela proposição que se afirma com base nas outras proposições do mesmo argumento
Premissas são enunciadas como prova ou razões para aceitar a conclusão. Ou seja, pretende-se que as premissas se justifiquem, garantem e deem evidências a conclusão. 
*
*
Premissas e Conclusões - exemplos
A água tem um calor latente superior ao do ar: mais calorias são necessárias para aquecer uma determinada quantidade de água do que para aquecer um igual montante de ar. Assim, a temperatura do mar determina, de um modo geral, a temperatura do ar acima dele. 
*
*
Sentenças, proposições e enunciados.
Sentenças são frases afirmativas, ou seja, declarativas. 
Abaixo segue duas frase que não são proposições.
Que horas são?
Feche a porta!
Frases interrogativas e imperativas não são proposições.
*
*
Exemplo 1
Toda baleia é um mamífero
Todo mamífero tem pulmões 
Logo, toda baleia tem pulmões 
É Válido ou não? Verdadeiro ou falso?
Argumento válido;
Conclusão e premissas são verdadeiras.
Verdadeiro
Verdadeiro
Verdadeiro
*
*
Exemplo 2
Toda aranha tem seis pernas 
Todo ser de seis pernas tem asas 
Logo, toda aranha tem asas
É Válido ou não? Verdadeiro ou falso?
Argumento válido;
Conclusão falsa
Falso
Falso
Falso
*
*
Validade e forma
Validação do argumento.
Argumento 1: Válido
P1: Todo gato é mamífero.
P2: Miau é um gato.
Logo, Miau é um mamífero.
Argumento 2: Inválido
Todo gato é mamífero
Lulu é um mamífero
Logo, Lulu é gato.
*
*
Proposições
*
*
Proposições
Todo o conjunto de palavras ou símbolos que exprimem um pensamento completo.
Uma proposição é uma frase que pode ser apenas verdadeira ou falsa, são os chamados valores lógicos de uma proposição. 
Ex.
Dez é menor que sete. (F)
A Lua é o satélite da Terra. (V)
Pedro Álvares Cabral descobriu o Brasil. (V)
Dante escreveu Os Lusíadas. (F)
*
*
Proposições
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 proposição ou é VERDADEIRA ou é FALSA, isto é, verifica-se sempre um destes casos e nunca um terceiro.
...EM RESUMO:
Toda proposição tem um, e somente um, dos valores V ou F.
*
*
Valores lógicos das proposições
Os valores lógicos verdadeiro e falso de uma proposição designam-se abreviamente pelas letras V e F.
Ex.
O mercúrio é mais pesado que a água. (V)
O Sol gira em torno da Terra. (F)
*
*
Tabela Verdade
O que é uma TABELA VERDADE?
Tabela verdade é a representação de todas as possibilidades de entrada e como é o comportamento após aplicar o conectivo (ou conjunto de conectivos)
*
*
CONECTIVOS
Conectivos são palavras usadas para formar uma proposição a partir das premissas.
Os principais conectivos são:
 “e”, “ou”, “não ”,“se... então”, “se e somente se”.
Ex.
P: O número 6 é par e o número 8 é cubo perfeito
Q: O triangulo ABC é retângulo ou é isósceles
R: Hoje não é feriado. 
S: Se Jorge é engenheiro, então sabe Matemática.
T: O triangulo ABC é eqüilátero se e somente se é eqüiângulo.
*
*
Operações Lógicas sobre Proposições
*
*
*
*
Negação (~)
Chama-se negação de uma premissa p é representa por "não p", cujo valor lógico é a verdade (V) quando p é falsa e a falsidade (F) quando p é verdadeira.
Assim, "não p" tem o valor lógico oposto daquele de p.
Simbolicamente, a negação de p indica-se com a notação "~p", que se lê: "não p".
O valor lógico da negação de uma premissa é, portanto, definido pela seguinte tabela-verdade muito simples:
ou seja, pelas igualdades:
~V = F , ~F = V
Ex:
 p: Isabel tem olhos azuis.
 ~ p: Isabel NÃO tem olhos azuis.
 q: dois é um número par
 ~ q: dois NÃO é um número par.
*
*
Negação (~)
Outra maneira de efetuar a negação consiste em antepor à proposição dada expressões tais como:
"não é verdade que“
 "é falso que“
“não é que todo”
Ex.
q: Carlos é mecânico
~q: Não é verdade que Carlos é mecânico
~q: É falso que Carlos é mecânico
Observa-se, entretanto a negação:
s: Todos os homens são elegantes
~s: Nem todos os homens são elegantes
~s: Nenhum homem é elegante
~s: Alguns homem é elegante.
~s: Não é que todos os homens são elegantes
*
*
Negação (~) - Exemplo
Premissa:
Todo homem é mortal
Negações da premissa acima:
Nem todo homem é mortal
É o mesmo que dizer:
 Existem homens que não são mortais
Outro exemplo
Existem pessoas inseguras
Não existem pessoas inseguras
*
*
Negação (~)
Exercícios do livro 
Introdução a Lógica para a Ciência da Computação. 
Jair Minoro Abe
Páginas 26 e 27
*
*
Conjunção “E” ( ^)
O valor lógico de uma conjunção será verdadeiro quando ambas premissas forem verdadeiras, e falso nos outros casos.
Notações: p  q (lê-se p e q)
A conjunção também pode ser expressa gramaticamente por palavras como: 'mas', 'todavia', 'embora‘, 'contudo', ...
Exemplo: “Chove mas faz calor”
*
*
Tabela-verdade da CONJUNÇÃO:
 
 
 
EXEMPLOS:
“Elefantes são grandes e bolas são redondas.”
 “A lua é quadrada e a neve é branca .”
*
*
Conjunção ^
Exercícios do livro 
Introdução a Lógica para a Ciência da Computação. 
Jair Minoro Abe
Páginas 28 e 29
*
*
Disjunção “OU” ( ˅)
O valor lógico de uma disjunção será verdadeiro quando pelo menos uma das proposições for verdadeira, e falso quando ambas forem falsas.
*
*
Tabelas Verdades “E” e “OU”
Pode-se perceber que, assim como no português, o “E” é muito mais restrito do que o “OU”
*
*
Disjunção v
Exercícios do livro 
Introdução a Lógica para a Ciência da Computação. 
Jair Minoro Abe
Páginas 30 e 31
*
*
Condicional “SE... ENTÃO” 
O valor lógico de uma condicional será falso quando “p” for verdadeira e “q” for falsa, e verdadeiro nos demais casos. 
*
*
Condicional “SE... ENTÃO” 
Enunciados do tipo se... então ... chamam-se condicionais ou implicações.
O enunciado subsequente ao 'se' chama-se o antecedente e o subsequente ao 'então‘ chama- se o consequente.
Forma do condicional:
Se antecedente então consequente
Exemplo: Se sinto frio então visto o casaco.
*
*
Condicional “SE... ENTÃO” 
Se antecedente então consequente
O antecedente é condição suficiente para ocorrência do consequente
O consequente é condição necessária para ocorrência do antecedente
Exemplo:
Se é Juiz então é formado em Direito
O fato de ser juiz é suficiente para saber que é formado em Direito
Para alguém ser juiz é necessário que seja formado em Direito
*
*
Condicional “SE... ENTÃO” – Formas de expressar
Exemplo: “O fogo é uma condição necessária para a fumaça” ou “Se houver fumaça haverá fogo”
Exemplo: “Se chover então molha a rua”
É suficiente chover para você deduzir que a rua fica molhada, porém o fato da rua ficar molhada não garante que choveu
Uma condicional também pode ser expressa na ordem inversa: 
“Visto o casaco se sentir frio” mantém a semântica de “Se sentir frio, visto o casaco” ou “Se sentir frio então visto o casaco”
*
*
Bicondicional “se e somente se” (↔)
O valor lógico de uma bicondicional será falso quando p e q tiverem valores (V ou F) diferentes , e verdadeiro nos demais casos.
*
*
Bicondicional “se e somente se” (↔)
Exemplo:
“T é um triângulo se e somente se T é um polígono de três lados”
Equivale:
T é um triângulo se T é um polígono de três lados; e T é um triângulo somente se T é um polígono de três lados.
*
*
Exercícios 
Iniciação à Lógica Matemática 
Edgard de Alencar Filho
Páginas 25 a 28
*
*
Lógica de predicados
*
*
SÍMBOLOS INDIVIDUAIS
Para caracterizar uma linguagem formal necessitamos, primeiro, especificar seu alfabeto ou conjunto de símbolos básicos.
O alfabeto é um conjunto de 65 caracteres:
*
*
SÍMBOLOS INDIVIDUAIS
O primeiro grupo de expressões básicas são chamadas de constantes individuais, que têm a função de designar indivíduos.
Usaremos as letras minúsculas a,...,t como constantes individuais.
Admite-se também o uso de subscritos para os números naturais positivos a1,a2 .....
A possibilidade do uso de subscritos nos garante que vamos ter um conjunto infinito, enumerável, de constantes individuais.
a,b,c,...,t , a1,b1,...,t1,a2,b2,....
Seguindo está ordem, a é a primeira constante, b é a segunda e, assim por diante.
*
*
Exemplos 
P1: Cleo é um peixe.
P2: Miau é um gato.
Cleo é um peixe e Miau é um gato.
Poderíamos usar a letra c para simbolizar ‘Cleo’, e a primeira premissa do argumento.
 c é um peixe.
*
*
Exemplos 
Constantes individuais funcionam como nomes.
João, Maria, Cleo, etc...
 Chamamos descrições definidas.
Por exemplo:
O autor de D. Quixote, embora não seja um nome próprio, designa univocamente um indivíduo.
O autor de D. Quixote é espanhol,
Poderia ser traduzida para:
 a é espanhol.
*
*
Atenção
Você não pode usar a mesma constante para dois indivíduos diferentes.
Por exemplo:
João e José não é permitido usar a letra j para ambos.
Usar j1 e j2
*
*
VARIÁVEIS INDIVIDUAIS
Usaremos letras minúsculas u, ...z, com ou sem subscritos para variáveis individuais.
u, v, w, x, y, z, u1, v1, w1, x1, y1, z1, ...
As variáveis individuais funcionam, gramaticalmente, como as constantes, isto é, como nomes.
Porém, obviamente, elas não são nomes de indivíduos específicos, mas têm associado a sim um domínio de variação.
Da mesma forma em que escrevemos c é um peixe para indicar que o indivíduo (determinado) cujo nome é c é um peixe, podemos também escrever, usando uma variável
 x é um peixe.
Afirma que, algum indivíduo não especificado ainda, ele é um peixe.
*
*
CÁLCULO DE PREDICADOS
símbolos de predicados: P , Q , R , S ,...
os símbolos de predicados (nome do predicado) representam propriedades ou relações entre os objetos do Universo
 Quantificadores:
∀(universal),
∃(existencial)
*
*
CÁLCULO DE PREDICADOS
Nas linguagens de programação conhecidas como Declarativas, os programas reúnem uma série de dados e regras e as usam para gerar conclusões.
As variáveis individuais têm a função de marcadores de lugar, isto indica, a posição dentro da expressão linguística.
Essas linguagens declarativas incluem 
predicados,quantificadores, conectivos lógicos e regras de inferência que fazem parte do Cálculo de Predicados.
*
*
CÁLCULO DE PREDICADOS
Representamos o predicado por sua inicial maiúscula, e o sujeito a seguir, entre parênteses; assim, “Sócrates é humano” fica representado por
H (Sócrates)
Exemplos
"Maria é inteligente":
I(m) ; onde “m" está identificando Maria e
 "I" a propriedade de "ser inteligente".
"Alguém gosta de Maria":
G(x,m) ; onde G representa a relação "gostar de" e "x" representa "alguém".
*
*
CÁLCULO DE PREDICADOS
Sentenças Abertas e Fechadas
O sujeito é uma constante
Ex.: “Sócrates é humano”, pode ser verdadeira ou falsa
Logo, o enunciado acima é uma sentença aberta.
O sujeito é uma variável
Ex.: “Ele foi presidente do Brasil”, ela não é verdadeira nem falsa, dependendo de nome que assuma o lugar do pronome. 
Uma frase como essa não é, portanto, um enunciado.
*
*
CÁLCULO DE PREDICADOS
Os enunciados são chamadas sentenças abertas, como:
“x foi presidente do Brasil”
“y escreveu Os Lusíadas”
“z viajou para os Estados Unidos”
As sentenças abertas não são verdadeiras nem falsas 
podemos dizer apenas que são satisfeitas para certos valores das variáveis, e não satisfeitas para outros.
A substituição das variáveis de uma sentença aberta por constantes chama-se instanciação ou especificação;
A instanciação transforma uma sentença aberta em um enunciado, e este sim, pode ser verdadeiro ou falso.
*
*
CÁLCULO DE PREDICADOS
OPERAÇÕES LÓGICAS
*
*
CÁLCULO DE PREDICADOS
Operações Lógicas
Negação
Conjunção
Disjunção
Condicional
Bicondicional
*
*
CÁLCULO DE PREDICADOS
Negação
 Universo: seres humanos
 Sentença:
 x é médico: M(x)
 
 x não é médico: ~ M(x)
*
*
CÁLCULO DE PREDICADOS
Conjunção
Universo: seres humanos
Sentenças:
 x é médico: M(x)
 x é professor: P(x)
 x é médico e professor:
 M(x) ^ P(x)
*
*
CÁLCULO DE PREDICADOS
Conjunção
A conjunção é expressa por:
e, mas, todavia, e etc.
Exemplo:
Pedro é inteligente e preguiçoso 
 ou
Pedro é inteligente, mas preguiçoso,
Estamos afirmando que Pedro é inteligente e também preguiçoso.
*
*
CÁLCULO DE PREDICADOS
Disjunção
 Universo: seres humanos
 Sentenças:
 x é médico: M(x)
 x é professor: P(x)
 x é médico ou professor: M(x) v P(x)
 Os valores de U que satisfazem M(x) v P(x) são todos os elementos que são médicos e todos os elementos que são professores:
 A disjunção poderá ser:
Ou...ou....
Ora...ora....
*
*
CÁLCULO DE PREDICADOS
Condicional
Universo: seres humanos
Sentença:
			x é médico: M(x)
			x cursou medicina: C(x)
		 Se x é médico, então x cursou medicina:
				M(x) → C(x)
*
*
CÁLCULO DE PREDICADOS
Bicondicional
Universo: seres humanos
Sentença:
			x é médico: M(x)
			x cursou medicina: C(x)
		 x é médico se e somente se x cursou medicina:
				M(x) ↔ C(x)
*
*
Cálculo de Predicados
Quantificadores
*
*
Calculo de predicado
Aristóteles é um filósofo.
Poderíamos representar por:
				F(a)
Estamos afirmando que alguém é um filósofo. 
Portanto:
 x é um filósofo.
Lembramos que x é uma variável individual
 b: Beatriz 
Se substituir b por x, temos 
				F (b)
Logo, alguém é um filósofo.
 
*
*
Cálculo de Predicados
Quantificadores
No primeiro caso (VP = U), dizemos que “para todo x em U, P(x) é verdadeiro”, ou, simbolicamente:
 (∀x  U) (Px)
ou ainda: ∀x P(x)
P(x) é uma sentença aberta, mas ∀x P x é um enunciado, podendo ser portanto verdadeiro ou falso.
*
*
Cálculo de Predicados
Quantificadores
Quantificador universal: ∀
Exemplos na linguagem natural:
Para todo x. 
Qualquer que seja x. 
Cada x.
Todos x
A expressão ∀x P(x) afirma que P(x) é verdadeiro para cada x  U
*
*
Cálculo de Predicados
Quantificadores
No segundo caso (VP ≠ 0), existe pelo menos um x para o qual P(x) é verdadeiro. 
Representamos tal fato por “existe um x em U tal que P(x) é verdadeiro”, ou, simbolicamente,
 (∃x  U) (Px)
ou ainda: ∃x P(x)
P(x) é uma sentença aberta, mas ∃x P(x) é um enunciado, podendo ser portanto verdadeiro ou falso.
*
*
Cálculo de Predicados
Quantificadores
Quantificador existencial: ∃
Exemplos na linguagem natural:
Existe um x. 
Existe pelo menos um x. 
Para algum x. 
Algum(ns) x
Alguém
A expressão ∃x P(x) afirma que P(x) é verdadeiro para pelo menos um x  U
*
*
Exemplo
L é a relação = x gosta de Miau
m: Miau
x gosta de Miau
Alguém gosta de Miau
 ∃x (L (x,m)) ou ∃x L (x,m)
Todos gostam de Miau
 ∀x L(x,m)
 
*
*
*
*
Negação – ninguém, nada, nem todos
*
*
*
*
EXERCÍCIOS
*
*
*
*
*
*
LINGUAGENS DE PRIMEIRA ORDEM
*
*
LINGUAGENS DE PRIMEIRA ORDEM
Um conjunto enumerável de constantes individuais;
Um conjunto enumerável de variáveis individuais;
Operadores;
Quantificadores;
Sinais de Pontuação.
Lógica de Primeira Ordem:
Uma linguagem de primeira ordem é qualquer subconjunto da linguagem geral do CQC que inclua todos os símbolos lógicos e pelo menos uma constante de predicado.
*
*
LINGUAGENS DE PRIMEIRA ORDEM
Exemplo:
Todos os peixes são azuis
Significa:
Para qualquer x, vale o seguinte:
Se ele for peixe, então é azul
ou seja,
para qualquer x, então é azul 
 ∀x (P(x) → A(x))
*
*
Proposição categórica
*
*
*
*
*
*
Porque usar a disjunção?
 Um individuo não pode ser um gato ou cachorro ao mesmo tempo.
*
*
*
*
*
*
*
*
Dado o predicado abaixo, passe para a língua portuguesa:
*
*
Dadas as frases abaixo, use quantificadores e predicados indicados:
*
*
Dadas as frases abaixo, use quantificadores e predicados indicados:
*
*
*
*
Árvore de composição de uma fórmula. 
*
*
Introdução
Daqui em diante, usamos também a seguinte terminologia: diz-se que uma fórmula
(A) é do tipo não.
(A  B) é do tipo e
(A  B) é do tipo ou
(A→B) é do tipo implica
(A↔B) é do tipo bi-implica.
*
*
Árvore de decomposição.
O método da arvore de decomposição determina a validade de uma fórmula a partir da estrutura de dados denominada arvore.
Uma arvore é um conjunto de nós ou vértices ligados por arestas.
A arvore de decomposição, permite a verificação cuidadosa da formação de fórmulas, como também permite analisar como uma fórmula foi obtida.
*
*
Vamos exibir um processo gráfico para determinar todas as subfórmulas (i.e., intuitivamente, todas as fórmulas que compõe a fórmula em questão) de uma dada fórmula.
Precisamente faremos uso somente de árvores binárias. 
*
*
Arvore binária 
*
*
*
*
Utilizaremos essa estrutura de árvore binária do seguinte modo:
*
*
Dada uma fórmula qualquer S esta será a raiz da árvore de subfórmulas de S.
2. Se S é uma fórmula do tipo não, então ela é composta por uma fórmula A, de tal modo que S = (A), logo teremos
*
*
3. Se S é uma fórmula do tipo e, então ela é composta por duas fórmulas A e B de tal modo que S = (A  B), logo teremos
4 . Se S é uma fórmula do tipo ou, então ela é composta por duas fórmulas A e B de tal modo que S = (A B), daí teremos
*
*
5. Se S é uma fórmula do tipo implica, então ela é composta por duas fórmulas A e B de tal modo que S é dado por (A→B), e teremos
6. Se S é uma fórmula do tipo bi-implica, então ela é composta por duas fórmulas A e B de tal modo que S é dado por (A↔B), e teremos
*
*
Cada nó representa uma fórmula, em particular, cada nó “gera” uma sub-árvore, isto é, cada nó pode ser considerada uma raiz de uma árvore “menor” que tem como nós os sucessores do respectivo nó raiz.
A construção de uma árvore de subfórmulas a partir de uma fórmula dada, termina quando todas as folhas contiverem somente letras proposicionais.
Por exemplo, podemos dizer qual conectivo foi aplicado inicialmente, o segundo, etc., até chegarmos ao último. 
Desse modo, é possível decompor uma fórmula exibindo todas as suas fórmulas que o compõe. 
*
*
Analisemos a fórmula:
 [A→ (B  C)]
Podemos verificar sem dificuldade que ela foi obtida das fórmulas A e (B  C) pela aplicação do conectivo →. 
Portanto, este → foi o último conectivo que foi aplicado à fórmula [A → (B  C)]. Esquematizamos isso assim:
*
*
*
*
A árvore de decomposição toma a forma:
*
*
{[(A→B) → A] → A}
*
*
{A  [C  (A  C)]}
*
*
{[( E→C)  (A  D)]  [(E↔C) ↔ (A  D)]}
*
*
Tabela-verdade de uma fórmula
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Referencias 
Abe , Jair Minoro Introdução a Lógica para a Ciência da Computação. 
Filho, Edgard de Alencar. Iniciação à Lógica Matemática 
MORTARI, Cesar A. Introdução a lógica. São Paulo. Editora UNESP:Imprensa Oficial do Estado. 2001.
COPI, Irving M. Introdução à lógica. 2 Edição. São Paulo. Editora Mestre Jou, 1978.
*
*
*