Resumo - Lógica para Computação

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

1 
 
LÓGICA PARA COMPUTAÇÃO 
LÓGICA 
 Lógica é o estudo dos métodos e princípios usados para distinguir o raciocínio correto do incorreto. Lógica se preocupa 
com premissas e conclusão e estrutura e forma de raciocínio. Para a Lógica não importa o conteúdo. 
 Argumento é uma sequência de proposições (declarações/afirmações) na qual uma delas é a conclusão e as demais 
são premissas. As premissas justificam a conclusão. É uma sequência de enunciados na qual um dos enunciados é a 
conclusão e os demais são premissas, as quais servem para provar, ou pelo menos fornecer alguma evidência para a 
conclusão. 
o Argumento Válido: as premissas são consideradas provas evidentes da verdade da conclusão. A conclusão é 
uma decorrência lógica das duas premissas. Se as premissas são verdadeiras, é impossível que a conclusão 
seja falsa. 
o Argumento Inválido: as premissas são consideradas provas evidentes da mentira da conclusão. A conclusão 
não é uma decorrência lógica das duas premissas. Se as premissas são falsas, é impossível que a conclusão 
seja verdadeira. 
o Argumento Dedutivo as premissas, se verdadeiras, a conclusão é também verdadeira. O raciocínio dedutivo 
obtém conclusões baseadas em uma prova formal sobre a validade do argumento. Um argumento dedutivo 
no qual todas as premissas são verdadeiras é dito argumento correto, evidentemente sua conclusão também 
é verdadeira. 
o Argumento Indutivo, a verdade das premissas não basta para assegurar a verdade da conclusão. Argumentos 
deste tipo não pretendem que suas premissas forneçam provas cabais da veracidade da conclusão, mas 
apenas que forneçam indicações dessa veracidade (possibilidade, probabilidade). O raciocínio Indutivo 
obtém conclusões baseadas em observações/experiências. 
 Raciocínio (ou processo de inferência): relação que permite passar das premissas para a conclusão (“encadeamento 
lógico”). 
 Validade ou Invalidade são propriedades dos argumentos dedutivos que dizem respeito a inferência ser ou não válida 
(raciocínio ser ou não correto). 
LÓGICA FORMAL 
 Lógica Formal é uma ciência que determina as formas corretas (ou válidas) de raciocínio. O objeto da Lógica é a forma 
pela qual o raciocínio está estruturado. Lógica Formal só estuda argumentos dedutivos, verificando se são válidos ou 
inválidos. 
 História 
o Aristóteles, na Grécia antiga (342 a.C.): estabeleceu os fundamentos da lógica sistemática, através de 
princípios tão gerais e sólidos que até hoje são considerados válidos. A Lógica foi considerada na cultura 
clássica e medieval como um instrumento indispensável ao pensamento científico. Aristóteles se preocupava 
com as formas de raciocínio que, a partir de conhecimentos verdadeiros, permitiam obter novos 
conhecimentos. Encadeamento – argumento. Afirmações envolvidas – proposições. 
o George Boole, propôs em 1847 uma linguagem formal que permite realizar inferências. 
o Gottlob Frege, publicou em 1879 a primeira versão do que hoje é conhecido como Cálculo de Predicados. 
o Final do século XX, a lógica passou a ser utilizada como base formal para outros campos da matemática. 
Estudiosos: David Hilbert, Giuseppe Peano, Georg Cantor, Thoralf Skolem, entre outros. 
LÓGICA MATEMÁTICA 
 No século XIX começam a ser delineados os fundamentos da ciência da computação. A lógica matemática, a partir 
daqui, tem o objetivo principal de tornar explícitas as formas de inferência, deixando de lado o conteúdo das verdades 
que elas possam transmitir. 
LÓGICA SIMBÓLICA 
 Com sua linguagem técnica vem se tornando um instrumento cada vez mais poderoso para a análise e a dedução dos 
argumentos. 
o Vantagens do uso de uma simbologia, ajuda a expor as estruturas lógicas das proposições e dos argumentos, 
possibilita utilização de recursos computacionais no tratamento de enunciados e argumentos e os 
computadores manipulam bem os símbolos, enquanto encontram dificuldade na manipulação da linguagem 
natural. Na computação a Lógica é utilizada para representar problemas e para obter suas soluções. 
2 
 
 Predicados são outras proposições que fazem referência a conjuntos de objetos, mas não se referem a um objeto em 
particular, mas ao conjunto de propriedades que faz com que um objeto esteja em uma categoria ou outra. Estamos 
nos referindo aos predicados. 
LÓGICA PROPOSICIONAL 
 Lógica Proposicional (ou cálculo proposicional) é o estudo da linguagem proposicional. 
 Proposição (ou enunciados ou sentenças): é uma sentença declarativa, é uma sentença que pode ser verdadeira ou 
falsa. E a construção (frase, sentença, pensamento) à qual se pode atribuir falso ou verdadeiro. 
o Proposição Singular são ideias envolvidas nos argumentos que podem ser apresentadas através de 
proposições que se refere a um objeto. 
o Proposição Composta (argumentos): duas ou mais sentenças agrupadas através dos conectivos lógicos. 
 Sintáticos são símbolos do alfabeto e fórmulas. 
 Semântico é significado dos símbolos e fórmulas. A semântica da lógica proposicional associa a cada objeto sintático 
um significado. 
 Paradoxo é o conceito que é ou parecer contrário ao comum; contrassenso, absurdo, disparate; contradição, pelo 
menos na aparência; em que uma afirmação aparentemente contraditória é, no entanto, verdadeira; afirmação que 
vai de encontro a sistemas ou pressupostos que se impuseram, como incontestáveis ao pensamento; dupla implicação 
entre uma proposição e sua negação, que caracteriza uma contradição insolúvel; dificuldade na conclusão de um 
raciocínio, seja pela vacuidade dos termos das suas proposições, seja pela insuficiência dos instrumentos lógicos 
formais. 
o Paradoxo do Mentiroso; Paradoxo do Barbeiro; Paradoxo do Cartão. 
o Paradoxo de Grelling. 
 Adjetivos Autológicos são assim definidos se a propriedade que ele denota pode ser atribuída a ele 
mesmo. 
 Adjetivos Heterológicos denotam atributos que não são aplicáveis a si próprios. 
 Alfabeto contém símbolos que formam as palavras da linguagem. Palavras (Fórmulas) são formadas pela 
concatenação de símbolos do alfabeto. 
o Símbolos de pontuação:), ( 
o Símbolos de verdade: true, false (fórmula da Lógica Proposicional) 
o Símbolos proposicionais: P, Q, R, S, P1, Q1, P2, Q2... 
 Fórmulas é todo símbolo de verdade ou proposicional é uma fórmula da Lógica Proposicional. 
 Subfórmula é quando há uma fórmula sob outra. 
o Conectivos proposicionais: ¬, ∨, ∧, →, ↔ 
 Ordem de precedência (Segundo (**)) 
 Maior precedência: ¬ 
 Precedência intermediária: →, ↔ 
 Menor precedência: ∨, ∧ 
TABELA-VERDADE 
 Negação (not) ¬ 
 Conjunção (and) ∧ 
 Disjunção (or) ∨ 
 Implicação (se A então B / if {}) → 
 Equivalência (A se e somente se B) ↔ 
 
3 
 
 Interpretação das Fórmulas é feita a partir de um conjunto de regras semânticas. Tais regras são obtidas a partir dos 
significados semânticos dos símbolos proposicionais, dos símbolos de verdade e dos conectivos proposicionais 
o I é função interpretação que associa a cada fórmula da lógica proposicional um valor de verdade “verdadeiro” 
ou “falso” (T ou F). 
 Lógica Bivalente possui apenas 2 estados semânticos, verdadeiro e falso. Função Binária só possui em sua imagem 2 
elementos. 
 Uma Interpretação I, em Lógica Proposicional, é uma função binária tal que: 
o O domínio de I é o conjunto de fórmulas proposicionais. 
o A imagem (contradomínio) é o conjunto {T,F}. 
o O valor da interpretação I, tendo como argumentos os símbolos de verdade true e false, é dado por I[true]=T 
e I[false]=F. 
o Dado um símbolo proposicional P, I[P] ∈ {T,F}. 
VALIDAÇÃO 
 Validação 
o Uma fórmula H é uma tautologia (ou é válida) se e somente se para toda interpretação I, I[H]=T. Se alguma 
coluna ou fórmula contém apenas o símbolo T. 
o Uma fórmula H é factível ou satisfazível se e somente se existe pelo menos uma interpretação
I, tal que 
I[H]=T. Se a coluna ou fórmula contém pelo menos um símbolo T. 
o Uma fórmula H é contraditória se e somente se para toda interpretação I, I[H]=F. Se a coluna ou fórmula 
contém apenas o símbolo F. 
ÁRVORE SEMÂNTICA 
 Árvore Semântica é a estrutura de dados. Árvore = conjunto de nós (vértices) ligados por arestas. 
o Lei da Contraposição: Para o caso em que todas as folhas da árvore são rotuladas com F, tem-se fórmula 
contraditória. Se pelo menos uma folha estiver rotulada com T, então fórmula satisfazível. 
MÉTODO DA NEGAÇÃO (ABSURDO) 
 Lei da Transitividade: Método geral de demonstração empregado aqui para demonstrar a validade de fórmulas. Ponto 
de partida, é a negação daquilo que se quer demonstrar. Se o objetivo é demonstrar que a fórmula H é uma tautologia, 
então supõe-se que H não é uma tautologia. Resultado = absurdo, logo a suposição inicial é falsa. Se uma asserção é 
negada, mas o absurdo não aparece, nada se pode concluir sobre a veracidade da asserção. 
SISTEMA DE DEDUÇÃO 
 Sistema de Dedução são sistemas formais que estabelecem estruturas que permitem a representação e dedução 
formal do conhecimento. Os sistemas axiomático e natural definem métodos que produzem ou verificam fórmulas ou 
argumentos válidos. 
SISTEMA DE AXIOMÁTICO 
 Sistema Axiomático é um sistema que utiliza axiomas, para se deduzir um novo conhecimento, a partir deles. É 
definido pela composição dos quatro elementos, e como se deduz um novo conhecimento a partir de um outro dado 
a priori. Os quatro elementos do sistema axiomático 
o O alfabeto da lógica proposicional. 
o O conjunto das fórmulas da lógica proposicional. 
o Um subconjunto das fórmulas – axiomas (conhecimento a priori). 
o Um conjunto de regras de dedução. 
 Axiomas do Sistema são fórmulas da lógica proposicional determinadas pelos esquemas a seguir, onde E, G e H são 
fórmulas. Os axiomas representam o conhecimento a priori. Neste sistema os axiomas são tautologias. 
 
4 
 
 
 Modus Ponens é a regra de inferência do sistema axiomático. Define um procedimento sintático de dedução de 
conhecimento Empregado em linguagens de programação como o Prolog. A partir de 2 argumentos H e (H→G) 
conclui-se G. Mp = (H,(H→G))/G 
 Consequências lógicas representam o conhecimento provado a partir de axiomas mais fórmulas extras denominadas 
hipóteses (conjunto de hipóteses β= {G1, ..., G9}), e a aplicação das regras de inferência aos axiomas e às hipóteses 
=> argumentos denominados consequências lógica. 
 Teorema é uma fórmula que representa um conhecimento derivável no sistema axiomático, a partir de seus axiomas. 
É uma fórmula H derivável a partir de um conjunto vazio de hipóteses. Uma fórmula H é um teorema no sistema 
axiomático se existe uma prova de H que utiliza apenas axiomas. Neste caso o conjunto de hipóteses é vazia. 
o Conjunto de hipóteses β= {H1, H2, ..., Hn}. 
o Se H é consequência lógica de βentão β├ H ou {H1, H2, ..., Hn} ├ H. 
o Se βé vazio então a notação empregada é├ H. 
o Teorema da Correção deve ser uma tautologia os argumentos deduzidos a partir dos axiomas, utilizando as 
regras de inferência, devem ser válidos. 
o Teorema da Completude deve ser um teorema se o sistema é completo, então a tautologia é um teorema 
toda tautologia pode ser derivada no sistema axiomático. 
o Consistência, um sistema axiomático é consistente, se e somente se, dada uma fórmula H, não se pode ter 
├ H e ├ ¬H. Isto é, H e ¬H não podem ser teoremas ao mesmo tempo. O sistema axiomático é consistente. 
TABLEAUX SEMÂNTICO 
 Tableaux Semântico é uma sequência de fórmulas construída de acordo com regras e apresentada na forma de uma 
árvore. Mesma estrutura do sistema de dedução natural. As regras de dedução do tableau semântico definem o 
mecanismo de inferência. Elementos básicos 
o alfabeto da Lógica Proposicional. 
o conjunto de fórmulas da Lógica Proposicional. 
o conjunto de regras de dedução. 
 Emprego do método da negação ou absurdo (Sistema de refutação), onde para provar A é considerada inicialmente 
sua negação ¬A. A aplicação das regras de dedução decompõe a fórmula ¬A em subfórmulas. 
o A aplicação das regras é feita considerando qualquer uma das fórmulas presentes na árvore. Uma boa 
heurística na construção de um tableau semântico é aplicar inicialmente as regras que não bifurcam a árvore, 
ou seja, postergar a bifurcação. Heurística: aplique preferencialmente as regras: R1, R5, R7e R8, que não 
bifurcam o tableau. 
 
5 
 
 Tableau Semântico é construído como se segue. Seja {A1, ..., An} um conjunto de fórmulas. A árvore a seguir, com 
apenas um ramo é um tableau associado a {A1, ..., An}. 
 Tipos de Ramo 
o Ramo Fechado de um tableau é se ele contém uma fórmula A e sua negação ¬A ou contém o símbolo de 
verdade false. 
o Ramo Aberto é quando não é fechado. 
 Tipos de Tableau 
o Tableau Fechado é quando todos os seus ramos são fechados. 
o Tableau Aberto é quando não é fechado. 
 Prova, seja H uma fórmula. Uma prova de H utilizando tableaux semânticos é um tableau fechado associado a ¬H. 
Neste caso, H é um teorema do sistema de tableaux semânticos. 
 Consequência lógica, dada uma fórmula H e um conjunto de hipóteses β= {A1, ..., An}, então H é uma consequência 
lógica de β, nos tableaux semânticos, se existe uma prova de (A1∧... ∧An) →H utilizando tableaux semânticos. A 
notação empregada é a mesma dos outros sistemas de dedução β├ H. 
o Deve-se provar se H é ou não uma tautologia. Se a prova de ¬H é um absurdo, ou seja, produz um tableau 
fechado, então a consequência lógica ocorre. 
RESOLUÇÃO 
 Resolução é o método de prova desenvolvido nos anos 60. Base da linguagem de programação Prolog. Pode ser 
considerada como dual dos tableaux semânticos. Elementos básicos da resolução 
o Alfabeto da Lógica Proposicional. 
o Conjunto de cláusulas da Lógica Proposicional. 
o Regra de resolução. 
 Nos tableaux semânticos é empregada a heurística: Aplique preferencialmente as regras R1, R5, R7e R8, que não 
bifurcam o tableau. Isso significa que o tableau é construído de forma eficiente para fórmulas que são conjunções de 
disjunções de literais. 
 A resolução se aplica a fórmulas que são conjunções de disjunções de literais, representadas na forma de conjunto de 
cláusulas. 
o Seja a fórmula H=(P∨¬Q∨R) ∧(P∨¬Q) ∧(P∨P). Esta fórmula é representada na forma de conjuntos como H={{P, 
¬Q,R}, {P, ¬Q}, {P}} H é um conjunto de conjunto de literais, onde as vírgulas mais internas representam “∨” 
e as mais externas “∧” A disjunção (P∨¬Q∨R) é representada por {P, ¬Q,R} e (P∨P) por {P} pois {P, P} = {P} 
(Não se representa duplicidade). 
 Regra de resolução C1={A1, ...,An} e C2={B1, ...,Bn}. A regra aplicada a C1 e C2 é definida pelo procedimento: tendo 
C1 e C2 deduza res(C1,C2). 
 Expansão é obtida por três aplicações da regra de resolução. Neste caso, não é possível obter a cláusula vazia A 
expansão por resolução resultante não contém a cláusula vazia, propriedade importante, análogo à obtenção de um 
tableau fechado. Uma expansão por resolução é fechada se ela contém a cláusula vazia. 
 Cláusula é uma disjunção de literais. Utilizando a notação de conjuntos, uma cláusula é um conjunto finito de literais. 
Exemplos: C1= {P, ¬Q,R}, C2={P, ¬Q}, C3={P} 
o Dois literais são complementares, se um é a negação do outro. Resolvente de duas cláusulas 
o Forma Clausal, dada uma fórmula H, a forma clausal associada a H é uma fórmula Hc tal que Hc é uma 
conjunção de cláusulas e Hc é equivalente a H. 
 Prova por resolução, seja H uma fórmula e ¬Hc a forma clausal associada a ¬H. Uma prova de H por resolução é uma 
expansão por resolução fechada sobre ¬Hc. Neste caso, H é um teorema do sistema de resolução. 
LÓGICA DE PREDICADOS 
 Lógica de Predicados é a extensão da lógica proposicional. Inferências que não possuem
representação adequada na 
lógica proposicional podem ser representadas na lógica de predicados 
 Alfabeto 
o Símbolos de pontuação: ( , ). 
o Símbolo de verdade: true, false. 
o Conjunto de símbolos para variáveis: x, y, z, w, x1, y1, z1, w1, x2, ... 
o Conjunto de símbolos para funções: f, g, h, f1, g1, h1, f2, g2, ... 
o Conjunto de símbolos para predicados: p, q, r, p1, q1, r1, p2, ... 
o Conectivos: ¬, ∧, ∨,→, ↔, ∀, ∃ 
o Conectivos quantificadores aumentam poder de representação 
 Aridade é o número inteiro não-negativo associado a cada símbolo para função ou predicado. 
6 
 
 Variáveis não ocorrem na Lógica Proposicional. Em programação lógica são utilizadas na determinação das respostas 
dos programas. 
 Funções e predicados são de maior poder de representação. 
 Constantes e símbolos proposicionais. 
o Se aridade=0, a função ou predicado tem zero argumento. Funções com aridade nula são constantes. 
Predicados com zero argumento são os símbolos proposicionais. 
 Termos são sentenças que representam os objetos. 
o Variáveis são termos (a interpretação é um objeto). 
o Função de termos é um termo (resultado da aplicação de uma função a um conjunto de termos é um termo). 
 Átomos são expressões cuja interpretação é um valor verdade. 
o Símbolos de verdade são átomos. Predicado de termos é um átomo. 
 Fórmula é a concatenação de átomos e conectivos. São construídas a partir destas regras. 
o Todo átomo é uma fórmula da Lógica de Predicados. 
 Expressão = termo ou fórmula. 
 Subtermo. 
o Se E=x, então a variável x é subtermo de E. Se E = f(t1,t2,...,tn) então ti e f(t1,t2,...,tn) são subtermos de E. Se 
t1 é subtermo de t2 e t2 de E, então t1 também é subtermo de E. 
 Subfórmula. 
o Se H=(¬G), então G é subfórmula de H. Se H é do tipo (E∨G), (E∧G), (E→G) ou (E↔G), então E e G são 
subfórmulas de H. Se x é uma variável e Q um quantificador, H=((Qx)G) então G e ((Qx)G) são subfórmulas 
de H. Se G é subfórmula de H, então toda subfórmula de G também é subfórmula de H. 
 Elementos básicos da linguagem 
o Todo subtermo ou subfórmula é uma subexpressão. 
o Literal em lógica de predicados é um átomo ou sua negação. Uma fórmula está na forma normal disjuntiva 
(fnd ou DNF, em inglês) se é uma disjunção de conjunções de literais. Uma fórmula está na forma normal 
conjuntiva (fnc ou CNF, em inglês) se é uma conjunção de disjunções de literais. 
 Escopo do quantificador é abrangência de seu uso nas subfórmulas. 
o Se E é uma fórmula na Lógica de Predicados. Se ((∀x)H) é subfórmula de E. O escopo de (∀x) é H. Se ((∃x)H) 
é subfórmula de E. O escopo de (∃x) é H. 
 Ocorrência livre e ligada 
o Ligada, se x está no escopo de um quantificador (∀x) ou (∃x) em E.G=(∀x)(∃y)((∀z)p(x,y,w,z) → 
(∀y)q(z,y,x,z1)). Exemplo: x,y,p(z). 
o Livre, se não for ligada. G=(∀x)(∃y)((∀z)p(x,y,w,z) → (∀y)q(z,y,x,z1)). Exemplo: w,z1,q(z). 
 Variável livre e ligada 
o Ligada em E, se existir uma ou mais ocorrências ligadas de x em E. G=(∀x)(∃y)((∀z)p(x,y,w,z) → 
(∀y)q(z,y,x,z1)). Exemplo: x,y,p(z). 
o Livre em E, se existir uma ou mais ocorrências livres de x em E. G=(∀x)(∃y)((∀z)p(x,y,w,z) → (∀y)q(z,y,x,z1)). 
Exemplo: w,q(z,z1). 
 Símbolos livres são suas variáveis livres, símbolos de função e de predicado. Tudo menos os conectivos, variáveis dos 
quantificadores, símbolos de verdade e de pontuação 
o G=(∀x)(∃y)((∀z)p(x,y,w,z)→ (∀y)q(z,y,x,z1)). Conjunto de símbolos livres é {w,z,z1,p,q}. 
 Fórmulas fechadas não possuem variáveis livres. 
o G1=(∀w)(∀z)(∀z1)(∀x)(∃y)((∀z)p(x,y,w,z)→(∀y)q(z,y,x,z1)). 
 Fecho de uma fórmula 
o Fecho Universal. G=(∀x)(∃y)((∀z)p(x,y,w,z)→ (∀y)q(z,y,x,z1)). G1=(∀w)(∀z)(∀z1)(∀x)(∃y) 
((∀z)p(x,y,w,z)→(∀y)q(z,y,x,z1)). 
o Fecho Existencial. G=(∀x)(∃y)((∀z)p(x,y,w,z)→ (∀y)q(z,y,x,z1)). G2=(∃w)(∃z)(∃z1)(∀x)(∃y) 
((∀z)p(x,y,w,z)→(∀y)q(z,y,x,z1)). 
 O conjunto de propriedades semânticas da Lógica de predicados é análogo ao conjunto de propriedades apresentado 
para Lógica Proposicional, mas as técnicas utilizadas nas demonstrações são diferentes. 
 Satisfabilidade de Fórmulas 
o Uma fórmula H é satisfazível quando existe pelo menos uma interpretação I, tal que I[H]=T. 
 Validade de Fórmulas 
o Fórmula valida é quando a formula é tautologia. 
 Implicação de Fórmulas H→G 
 Equivalência de Fórmulas H↔G 
 
 
7 
 
TABLEAUX SEMÂNTICO 
 Sequência de fórmulas que se apresenta sob a forma de uma árvore, construída de forma análoga aos tableaux da 
Lógica Proposicional. 
 Elementos básicos 
o Alfabeto da Lógica de Predicados. 
o Conjunto de fórmulas da Lógica de Predicados. 
o Conjunto de regras de dedução (ou regras de inferência). 
 Utiliza a linguagem da Lógica de Predicados. Extensão do tableau da Lógica Proposicional. Construção e conceitos de 
tableau fechado são os mesmos apresentados na lógica proposicional. 
 
RESOLUÇÃO 
 Cláusulas são obtidas skolemizando fórmulas na forma prenex. Algoritmo de unificação é empregado para definir o 
resolvente de duas cláusulas. 
 Resolução 
o Alfabeto da Lógica de Predicados. 
o Conjunto de cláusulas da Lógica de Predicados. 
o A regra de resolução da Lógica de Predicados. 
 Cláusula em lógica de predicados é uma disjunção de literais. Dois literais são complementares quando um é a negação 
do outro. 
 Forma Prenex .Uma fórmula está na forma Prenex quando os quantificadores estão na frente da fórmula, ou seja, são 
identificados primeiramente os quantificadores, seguidos de uma fórmula aberta. Fórmula aberta em lógica de 
predicados – não contém quantificadores. (∀x)(∀y)(r(x,y) ∧ p(y)) 
 Skolemização. O método de resolução na lógica de predicados é definido a partir de fórmulas que estão na forma 
prenex e que não contém quantificadores existenciais. Método de eliminação dos quantificadores existenciais – 
método de skolem. 
 Unificação . 2 fórmulas são unificáveis se e somente se existir uma substituição que, se aplicada ambas, torna-as 
iguais.