Baixe o app para aproveitar ainda mais
Prévia do material em texto
0.0.1 Linguagem LP da Lógica Proposicional Clássica De nição 1 O alfabeto a ser utilizado consiste dos seguintes símbolos: a) Variáveis Proposicionais: p0; p1; p2; ::: .(uma lista in nita); b) Sinais de Pontuação: (e). c) Conectivos: :;^;_;�! e ! : símbolo nome leitura : negação não ^ conjunção e _ disjunção ou �! condicional se...então... ! bicondicional ...se e somente se ... De nição 2 Uma expressão lógica proposicional clássica é dita ser uma fór- mula1 se satisfazer ao menos uma das seguintes condições: a) Cada variável proposicional é uma fórmula; b) Se X é uma fórmula, então (:X) é uma fórmula; c) Se X e Y são fórmulas, então (X ^ Y ) ; (X _ Y ) ; (X �! Y ) e (X ! Y ) são fórmulas; d) Só é fórmula o que advém das condições acima. As seguintes expressões são exemplos de fórmulas da linguagem LP : � (p1 �! p2) � (: (: (:p1))) � (((p2 ^ p3) �! p5) _ (p1 �! (:p2))) � p5: 1Uma fórmula é uma expressão bem formada. 1 0.0.2 Parênteses De nição 3 Convenções para eliminação (e restauração) de parênteses. i) parênteses externos podem ser omitidos; ii) para partes de fórmulas com o mesmo conectivo adota-se o príncipio de associação à esquerda; iii) a seguinte ordem hierárquica de colocação de conectivos é adotada: ":"; "^ "; " _ "; " �! "; " ! ": As convenções de eliminação de parênteses são as mesmas con- venções utilizadas para restauração de parênteses. a) A fórmula ((p1 ^ p2) �! p3) torna-se p1 ^ p2 �! p3 após aplicação das convenções; b) A fórmula ((p1 �! p2) ^ p3) torna-se (p1 �! p2) ^ p3 após aplicação das convenções quanto a eliminação dos parênteses; c) :::p1advém de (: (: (:p1))) ; d) p1 �! p7 �! p9 ^p8 advém de ((p1 �! p7) �! (p9 ^ p8)) após aplicação das convenções quanto a eliminação dos parênteses. 0.1 Semântica 0.1.1 Valorações Proposicionais De nição 4 Seja F o conjunto de todas as fórmulas da linguagem L: Uma val- oração proposicional v é uma aplicação de F em fV; Fg que satisfaz as seguintes condições para quaisquer fórmulas X;Y de F : i) v (:X) = � V , se v (X) = F e F; caso contrário. ii) v (X _ Y ) = � F; se v (X) = v (Y ) = F e V; caso contrário. iii) v (X ^ Y ) = � V; se v (X) = v (Y ) = V e F; caso contrário. iv) v (X �! Y ) = � F; se v (X) = V e v (Y ) = F e V; caso contrário. v) v (X ! Y ) = � V; se v (X) = v (Y ) e F; caso contrário. 2 0.1.2 Tabela Verdade Uma tabela verdade é um procedimento efetivo (mecânico) utilizado para anal- isar os valores verdade de uma fórmula da linguagem LP : Sejam X e Y fórmulas quaisquer de F: X (:X) V F F V X Y (X ^ Y ) (X _ Y ) (X �! Y ) (X ! Y ) V V V V V V V F F V F F F V F V V F F F F F V V De um modo geral, para uma fórmula com n variáveis proposicionais difer- entes, a tabela terá 2n linhas. Exemplo 5 p0 p1 p2 (p0 �! p1) (p0 _ p2) (: (p0 _ p2)) ((p0 �! p1) ^ (: (p0 _ p2))) V V V V V F F V V F V V F F V F V F V F F V F F F V F F F V V V V F F F V F V F V V F F V V V F F F F F V F V V Tabela verdade da fórmula ((p0 �! p1) ^ (: (p0 _ p2))) : 0.1.3 Propriedades semânticas De nição 6 Uma fórmula X é dita ser uma tautologia se v (X) = V para toda a valoração proposicional v: Uma fórmula é dita ser uma contradição se e somente se v(X) = F para toda valoração proposicional. As fórmulas que não são contradições nem tautologias, são chamadas de contigentes. Símbolo Nome Leitura De nição > verum constante de verdade > =def (X _ :X) ? falsum constante de falsidade ? =def (X ^ :X) De nição 7 Um conjunto de fórmulas � é "satisfazível"se existir uma valo- ração proposicional v tal que v(X) = V para todo X 2 �: 3 Seja � = fA1; A2; :::; Ang um conjunto de fórmulas da lógica. Seja a tabela verdade de cada fórmula de � exposta abaixo. Li ! A1 A2 A3 . . . An ... ... ... ... ... V V V . . . V ... ... ... ... ... Se existir ao menos uma linha Li na tabela verdade acima, de tal forma que nessa linha Li se tem que v(X) = V para todo X 2 �; então � é satisfazível. Neste texto a palavramodelo será utilizada, quando não houver dúvidas no contexto, como sinônimo de satisfazível. O conjunto � tem modelo se e somente se existe uma valoração proposicional v; tal que v(Z) = V para toda fórmula Z 2 �: De nição 8 Seja � um conjunto de fórmulas. Diz-se que a fórmula X é con- sqüência lógica do conjunto de fórmulas � (em símbolos, � j= X) se para toda valoração proposicional v, se v(C) = V para todo C 2 � então v (X) = V: De nição 9 Diz-se que as fórmulas X e Y são logicamente eqüivalentes (em símbolos, X � Y ) se para toda valoração proposicional v; v (X) = v (Y ) : A fórmula : (p0 _ p1) é logicamente eqüivalente a fórmula (:p0 ^ :p1) ; pois ambas tem a mesma atribuição de valores verdade. p0 p1 (p0 _ p1) : (p0 _ p1) :p0 :p1 :p0 ^ :p1 V V V F F F F V F V F F V F F V V F V F F F F F V V V V 0.2 Forma Normal Conjuntiva De nição 10 Uma fórmula na forma normal conjuntiva é uma conjunção (X1 ^X2 ^ ::: ^Xn) onde para cada X1; com 1 � i � n : 1. ou Xi é uma variável proposicional, 2. ou Xi é uma disjunção (Y1 _ Y2 _ ::: _ Ym) onde: i) Para cada Yj (1 � j � m) ; ou Yj é uma variável proposicional ou é uma negação de uma variável proposicional, exclusivamente. 4 0.2.1 Algoritmo para obter fórmuas na FNC Para transformar uma fórmula X numa fórmula normal conjuntiva, procede-se segundo os seguintes passos: 1. Os conectivos "�!"e " !"que por ventura existam na fórmulaX, devem ser substituídos por :Y _Z e por (:Y _ Z)^: (Y _ Z) respectivamente. 2. Utilizar as leis de De Morgan. 3. Eliminar multiplas negações. 2. Caso necessário, aplicar a lei distributiva: Y _(Z ^W ) ou do tipo (Z ^W )_ Y; deve-se substituir por (Y _ Z) ^ (Y _W ) 0.3 Forma Normal Disjuntiva De nição 11 Uma fórmula na forma normal disjuntiva é uma disjunção (X1 _X2 _ ::: _Xn) onde para cada Xi;com 1 � i � n : 1. ou Xi é uma variável proposicional, 2. ou Xi é uma conjunção (Y1 ^ Y2 ^ ::: ^ Ym) onde: i) Para cada Yj (1 � j � m) ; ou Yj é uma variável proposicional ou é uma negação de uma variável proposicional, exclusivamente. 0.3.1 Algoritmo para obter fórmulas na FND A transformação de uma fórmula X qualquer para uma fórmula logicamente eqüivalente na FND é semelhante ao algoritmo elaborado para FNC a menos do último passo. O algoritmo é: 1. Os conectivos "�!"e " !"que por ventura existam na fórmulaX, devem ser substituídos por :Y _Z e por (:Y _ Z)^: (Y _ Z) respectivamente. 2. Utilizar as leis de De Morgan. 3. Eliminar multiplas negações. 2. Caso necessário, aplicar a lei distributiva: Y ^ (Z _W ) ou (Z _W ) ^ Y; deve-se substituir por (Y ^ Z) _ (Y ^W ) : 1 Tableaux Analítico Desenvolvimentos sobre o método tableaux podem ser encontrados em Beth (1959) e Hintikka (1955) ou Smullyan (1968). 5 1.1 Sistema formal baseado em Tableaux Analíticos Os tableaux são procedimentos de demonstração (procedimentos formais) elab- orados em forma de árvores binárias. Se se quer mostrar que X é um teorema através de tableaux, as únicas fórmulas envolvidas na demonstração (em forma de árvores) são as fórmulas que se constituem como partes de X. Desse modo, (para a lógica proposicional), se uma fórmula X não for um teorema, o tableau para X mostra todas as possibilidades que tornam X falso. Uma árvore binária contém nós, em cada nó ocorre uma fórmula de LP . A construção de um tableau inicia-se pela origem da árvore a qual é um nó único. Em um tableau para a fórmula X, tem-se que no nó de origem ocorre a fórmula (:X). Essa é a primeira regra de construção de tableaux. Sempre inicia-se por (:X) um tableau para a fórmula X. A partir do nó de origem estabelece-se regras que possibilitem a extensão da árvore, caracter- izando seus ramos e suas bifurcações. Após todas as possíveis aplicações de regras de extensão da árvore tem-se um tableaucompleto, ou seja, uma árvore que se estendeu o máximo possível através das aplicações de regras para todas as fórmulas que ocorrem na árvore. A partir dessa árvore completa, onde nos nós ocorrem fórmulas, é possível analisar e certi car-se se a fórmula X é um teorema ou se X não é um teorema (numa árvore para a fórmula X). Em cada nó ocorre uma fórmula de Lp (ØX) origem um ramo sucessor da esquerda sucessor da direita ponto simples ponto de junção ponto final 1.1.1 Fórmulas do tipo � e fórmulas do tipo � As fórmulas de � são fórmulas do tipo (�1^�2) e as fórmulas de � são fórmulas do tipo (�1 _ �2). 6 � - fórmulas �1 �2 (X _ Y ) X Y (X �! Y ) :X Y : (X ^ Y ) :X :Y � - fórmulas �1 �2 : (X _ Y ) :X :Y : (X �! Y ) X :Y (X ^ Y ) X Y ::X X :? 1.1.2 Extensões de ramos Extensões a partir de um nó p, para fórmulas do tipo-� e fórmulas do tipo-�; respectivamente. extensões de p produzindo bifurcaçãoextensões de p no mesmo ramo p p As regras de extensões de ramos são de dois tipos: � Regra �. Regra de extensão no mesmo ramo. � Regra �. Regra de extensão em ramos separados (bifurcação). 7 De nição 12 Uma fórmula X é um teorema (ou um teorema-tableau) se existir um tableau com contradições para X. Ou seja, um tableau que comece com \(1) (:X) � e de tal forma que cada ramo seja um ramo com contradições. Indica-se `t X para X é um teorematableaux. Seja � um conjunto de fórmulas e X uma fórmula qualquer. Diz-se que X é dedutível-tableaux a partir de � (em símbolos, � `t X) se existir um tableau com contradições que comece por \(1) (:X) � e de tal forma que qualquer fórmula de � puder ser adicionada em qualquer nó do tableau que começa por \(1) (:X) �: Se � `t X diz-se que o ocorreu uma dedução-tableau de X a partir de �. Se � = ? diz-se que X é um teorema-tableau. Se � = fX1; X2; :::; Xng então � ` X se o tableau começado por e estendido através das regras � e �, de modo que nenhuma fórmula que sem sofrer aplicação de alguma regra de extensão de ramos, for um tableau cujos ramos (todos) são ramos com contradições. Exemplo 13 Seja � = f(p1 �! p2);:p2g e X = :p1: 8 O tableau acima é uma dedução-tableau de X a partir de �. 2 Cálculo de Quanti cadores Seja 8 o símbolo que representa "para todo. Este é chamado de quanti cador universal. Seja 9 o símbolo que representa a palavra existe, chamado de quanti cador existencial. Seja P um símbolo de predicado. P (x) representa o predicado P com sujeito x. Por exemplo, Se o predicado P representar é um livro azul, então P (x) representa x é um livro azul. Sejam os símbolos a1, a2, a3, ...,an representando constantes individuais. Se- jam x; y e z representando variáveis sobre sujeitos. Assim (8x)P (x) representa um quanti cador universal e (9x)P (x) representa um quanti cador existencial. P (a1); P (a2), ..., representam proposições do cálculo proposicional, as quais são verdadeiras ou falsas. O comportamento de um quanti cador universal (8) pode ser entendido, de modo intuitivo, como uma conjunção iterada P (a1) ^ P (a2) ^ P (a3) ^ ::: ^ P (an) : O quanti cador existencial (9x)P (x) pode ser entendido, intuitivamente, como uma disjunção iterada. P (a1) _ P (a2) _ P (a3) _ ::: _ P (an) : Exemplo 14 Algumas equivalências entre quanti cadores. : (8x)P (x) � : (P (a1) ^ ::: ^ P (an)) � (:P (a1) _ ::: _ :P (an)) � (9x):P (x) : (9x)P (x) � : (P (a1) _ ::: _ P (an)) � (:P (a1) ^ ::: ^ :P (an)) � (8x):P (x) (8x)P (x) � (P (a1) ^ ::: ^ P (an)) � : (:P (a1) _ ::: _ :P (an)) � : (9x):P (x) (9x)P (x) � (P (a1) _ ::: _ P (an)) � : (:P (a1) ^ ::: ^ :P (an)) � : (8x):P (x) Alguns exemplos de predicados: � I(x; y): x é igual a y 9 � F (x; y): x é pai de y � O(x): x é um número ímpar � H(x; y; z): x é menor que y mais z � C(x; y): x é casado com y Todo A é B (8x) (A (x) �! B (x)) A rmativa Universal Todo A não é B (8x) (A (x) �! :B (x)) Negativa Universal Algum A é B (9x) (A (x) ^B (x)) A rmativa Particular Algum A não é B (9x) (A (x) ^ :B (x)) Negativa Particular Exemplo 15 Nenhum jóquei é alto. J(x) : "x é um jóquei" H(x) : "x é alto" (8x) (J (x) �! :H (x)) Exemplo 16 Todas as baleias são mamíferos. B(x) : "x é uma baleia" M(x) : "x é um mamífero" (8x) (B (x) �!M (x)) Exemplo 17 Nem todos cachorros são bravos. C(x) : "x é um cachorro" T (x) : "x é bravo" (9x) (C (x) ^ :B (x)) Exemplo 18 Todo solteiro é triste. H(x) : "x é um homemi" C(x; y) : "x é casado com y" (8x) ((H (x) ^ (8y) :C (x; y)) �! T (x)) Exemplo 19 O único número primo par é 2. P (x) : "x é um inteiro par" D(x) : "x é um inteiro primo" I(x; y) : "x é igual a y" a : 2. (8x) (P (x) ^D (x)) �! I (x; a) 2.1 Semântica de LQ Sejam as seguintes fórmulas: a) P 21 (x1; x2) ; b) (8x1) (9x2)P 21 (x1; x2) ; c) (9x2) (8x1)P 21 (x1; x2) : 10 2.1.1 Uma interpretação I1 � A letra de predicado P 21 representa a relação �; � P 21 (x1; x2) representa "x1 é menor ou igual que x2" � conjunto de constantes individuais (domínio) é N: A leitura das três fórmulas acima, sob essa interpretação, é: a) x1 � x2; P 21 (x1; x2) b) Para todo x1; existe x2 tal que x1 � x2; (8x1) (9x2)P 21 (x1; x2) c) Existe x2 tal que para todo x1; se tem que x1 � x2: (9x2) (8x1)P 21 (x1; x2) Os valores verdade das fórmulas sob a interpretação I1 são: Para a): Essa fórmula é verdadeira para todos os pares (a; b) números naturais tais que a � b:Por exemplo (3; 4); (1; 1); :::. Note que, a fórmula P 21 (5; 6) é verdadeira e a fórmula P 21 (32; 4) é falsa Como não se sabe a princípio quem são x1 e x2; a fórmula é verdadeira para alguns elementos do domínio e falsa para outros; Para b): Essa fórmula é verdadeira. Note que não tem variáveis livres (todas as variáveis estão sob o escôpo de algum quanti cador). De fato, esta representa a seguinte frase: para cada número natural existe um número maior ou igual. Para o primeiro número natural existe um número natural que é maior, para o segundo número natural existe um número natural que é maior, para o terceiro existe um que é maior, ... . Para o número 1 existe o número 2 que é maior, o número 3 que é maior, o número 4 que é maior, .... Para c): Essa fórmula é falsa em N; pois a rma que existe um número natural maior ou igual a todos os outros. Ou seja, para x1 = 0; x1 = 1; x1 = 2; ::: existe um x2 tal que x1 � x2: A fórmula caracteriza que existe um número natural que é maior ou igual que todos os outros, ou seja, que é maior ou igual ao primeiro, que é maior ou igual ao segundo, que é maior ou igual ao terceiro, etc. 2.1.2 Uma interpretação I2 � A letra de predicado P 21 representa a relação "... é lho de ..." � P 21 (x1; x2) representa "x1 é pai de x2" � conjunto de constantes individuais (domínio) é o conjunto das pessoas do mundo. A leitura das três fórmulas acima, sob a interpretação, é: 11 a) x1 é pai de x2; P 21 (x1; x2) b) Para todo x1; existe x2 tal que x1 é lho de x2; (8x1) (9x2)P 21 (x1; x2) c) Existe x2 tal que para todo x1; se tem que x1 é lho de x2: (9x2) (8x1)P 21 (x1; x2) Os valores verdade das fórmulas sob a interpretação I2 são: Para a): Representa que x1 é pai de x2. Esta é verdadeira por todo par (a; b) de pessoas tais que a seja lho de b. Para b): A fórmula pode ser representada pela frase: Todos tem um pai. Esta frase é verdadeira. Para c): A frase que representa a fórmula é: Todos tem um único pai. Nota-se que o valor verdade de uma fórmula em uma linguagem de primeira ordem depende da interpretação envolvida. 2.1.3 Interpretação de LQ De nição 20 Seja LQ uma linguagem. Uma interpretação I para LQ consiste de: 1) Um conjunto não vazio D, chamado de domínio de I; 2) Uma função V que associa a cada letra de predicado Pnk uma relação n��aria V (Pnk ) de elementos de D: Denomina-se essa função V de valoração de primeira ordemO domínio de uma interpretação consiste do conjunto de constantes individ- uais. A partir dos predicados da linguagem associa-se a cada letra n� �aria de predicado uma relação n� �aria constituída de elementos do domínio. Por exemplo, seja I4 a seguinte interpretação: � Domínio: N ; � P 21 (x1; x2) : "x1 � x2"; � P 11 (x1) : "x1 é par" Tem-se duas letras de predicados, cada uma determina uma relação. A letra de predicado P 21 determina uma relação binária, ou seja, determina um conjunto de elementos � (a; b) 2 N2 j a � b = f(0; 0) ; (0; 1) ; (1; 1) ; (1; 2) ; :::g : A função V associa a cada letra de predicado, neste caso à letra P 21 ; a relação binária V � P 21 � = f(0; 0) ; (0; 1) ; (1; 1) ; (1; 2) ; :::g : Já, a letra de predicado P 11 determina uma relação unária (1��aria), a qual é dada pelo conjunto f0; 2; 4; 6; 8; :::g cujos elementos satisfazem a relação 1 � �aria determinada por P 11 : A valoração de primeira ordem V (função V ) associa a letra de predicado P 11 a relação 1�ária V � P 11 � = f0; 2; 4; 6; 8; 10; :::g : 12 � (8x1) � P 11 (x1) �! P 12 (x1) � �! (P 11 (x1) �! (8x1)P 12 (x1)) De nição 21 Uma fórmula A de uma linguagem LQ é LQ-satisfatível se A é verdadeira em pelo menos uma interpretação. De nição 22 Seja I uma interpretação de uma linguagem LQ, e A uma fór- mula fechada de LQ. Então, A é uma fórmula válida (em símbolos, j= A) se para toda interpretação I, j=I A. De nição 23 Seja � um conjunto de fórmulas em uma linguagem LQ: Um modelo para � é uma interpretação na qual todas as fórmulas de � sejam ver- dadeiras. Um modelo para uma fórmula A é uma interpretação onde A é ver- dadeira. De nição 24 Seja � um conjunto de fórmulas e A uma fórmula em uma lin- guagem uma LQ: A fórmula A é conseqüência lógica do conjunto de fórmulas � (em símbolos, � j= A) se todo o modelo de � é modelo de A: 1) A fórmula (8x)P (x) �! P (y) é uma fórmula válida. 2) A fórmula (8x) (P (x) �! P (y)) não é uma fórmula válida. 3) A fórmula (8x) (P (x) �! Q (x)) �! (P (x) �! (8x)Q (x)) é uma fórmula válida. 4) A fórmula (8x) (9y) (P (x) �! P (y)) é uma fórmula válida. 5) A fórmula (9x) (9y) (P (x) �! P (y)) não é uma fórmula válida. Justi cativa: Seja uma interpretação I onde o domínio é o conjunto dos números naturais. P (x) representa x é um número primo. A leitura da fórmula acima é: Existem números naturais x e y, tais que se x é primo então y também é primo. Logo, existe um número natural igual a 3 e existe um número natural igual a 8, mas não se tem que se 3 é um número primo então 8 também é um número primo, ou seja a fórmula P (3) �! P (8) é falsa. Desse modo, I é uma interpretação onde a fórmula (9x) (9y) (P (x) �! P (y)) é falsa, portanto não é válida. 3 Tableaux analíticos para LQ 3.1 Regras Tableaux para LQ. Regra (k) onde k é qualquer constante Regra � 13 � �(k) onde k é uma nova constante A regra é de simples utilização. Se uma fórmula do tipo ocorre num nó de um tableau, então no nó seguinte (ou nas terminações a partir do nó corrente) é possível adicionar (k) para qualquer que seja a constante individual k. Regra : (8x)A A(x/k ) : (9x)A :A(x/k ) para qualquer constante individual k. Ao se utilizar a regra � deve-se ter algum cuidado. Se alguma fórmula do tipo � ocorre num nó de um tableau, então pode-se estendê-la adicionando � (k), desde que a constante individual k não tenha aparecido em fórmulas anteriores no tableau. Regra � : (9x)A A(x/k ) : (8x)A :A(x/k ) para alguma constante individual k que não tenha ocorrido em fórmulas anteriores no tableau. Exemplo de uma prova tableau em LQ para a fórmula (8x)P (x) �! (9x)P (x). (1) : ((8x)P (x) �! (9x)P (x)) (2) (8x)P (x) (3) : (9x)P (x) (4) P (k1) (5) :P (k1) � O tableau acima é completo e está fechado pois ocorreu uma contradição, P (k1) e :P (k1). A fórmula da linha (4) adveio da fórmula da linha (2) pela aplicação da regra . A fórmula da linha (5) adveio da fórmula da linha (3) pela aplicação da regra . Como a regra não tem restrições foi possível acrescentar a mesma constante individual k1 na duas aplicações da regra . O seguinte é um exemplo de um tableau completo e aberto para a fórmula (8x) (9y)P (x; y) �! (9x) (8y)P (x; y) (1) : ((8x) (9y)P (x; y) �! (9x) (8y)P (x; y)) (2) (8x) (9y)P (x; y) regra � aplicada em (1) (3) : (9x) (8y)P (x; y) regra � aplicada em (1) (4) (9y)P (k1; y) regra aplicada em (2) (5) : (8y)P (k1; y) regra aplicada em (3) (6) P (k1; k2) regra � aplicada em (4) 14 (7) :P (k1; k3) regra � aplicada em (5) O tableau não fechou pois não ocorreu contradição. Nota-se que nas linhas (6) e (7) a regra � foi utilizada e foi aplicado a restrição imposta nessa regra, qual seja, que a constante a ser introduzida não apareça em fórmulas anteriores no tableau. Exemplo de tableau para a fórmula (8x)P (x)! (9x)P (x) 15
Compartilhar