Lógica e Especificação Edward Hermann Haeusler Departamento de Informática TECMF PUC/RJ

Lógica e Especificação

Edward Hermann Haeusler

Departamento de Informática

TECMF

PUC/RJ

Edward Hermann Lógica e Computação 2

Qual a relação entre a Lógica e a Computação ?

- O que é a (Teoria da) Computação ?

- O que é Lógica ?

Tentativa de conceituação do Computável

Tentativa de conceituação do Razoável


Computável

Tudo aquilo que pode ser realizado por um ser burro com um mínimode conhecimento/capacidade.

burro = Incapaz de Aprender

conhecimento = ?


Razoável

Todo evento que é passível de uma explicação, na forma argumentativa,construída sobre fatos iniciais inquestionáveis.


Computável = Razoável ?

- Computável Razoável ?

- Razoável Computável ?


Como Definir tais Conceitos ?

Através de Linguagens para :

Expressar Procecimentos

Expressar Argumentos


Principais Componentes de uma Linguagem

- Sintaxe : Como se escreve ?

- Semântica : O que significa ?

- Pragmática : Como se usa ?


Em uma L.P.

- Como é um programa ?

- Como se executa ou, O que um programa faz ?

- Como se constroem programas visando a solução de problemas ?


Semântica

Significado

Mundo Sintático Mundo "Real"


Linguagem e Metalinguagem

À linguagem descritora chamamos de metalinguagem enquanto à descrita chamamos de linguagem objeto.

- Precisa-se de uma linguagem para descrever outra linguagem.

-


Paradoxos

1. Eu sou Mentiroso.

2. - O menor denominador comum entre 1/2 e 2/3 é 6. - 1/2 = 2/4 Então o menor denominador comum entre 2/4 e 2/ 3 é 6.


Princípio da Funcionalidade de Frege

A Semântica de uma expressão deve ser uma função da semântica das suas sub-expressões.

Objetos sintáticos são naturalmente Hierárquicos (estruturados).


SemânticasExtensional X

Intensional1. Planeta Vênus.2. Estrela Vespertina.3. Segundo Planeta do Sistema Solar.

- Em uma sem. extensional 1,2 e 3 têm o mesmo significado.

- Em uma sem. intensional 1, 2 e 3 têm diferentes significados. A forma é levada (sintaxe ?) em conta.


Princípio da Funcionalidade e

intensionalidade.

1. Necessariamente a estrela matutina é a estrela matutina.

2. Necessariamente a estrela matutina é a estrela vespertina.

Linguagem natural necessita de semântica intensional.

•


Expressões aritméticas :

*

+

1 2

5

(1 + 2) * 5

V( (1 + 2) * 5)

V( 1 + 2 ) * V( 5 )

V( 1 ) + V( 2 ) * 5

( 1 + 2 ) * 5 = 15

Sintaxe Semântica Ext.


A Linguagem da Lógica

A Lógica tem, tradicionalmente, por objetivo a definição do que seja uma argumentação correta.

Argumentação = Sequência de sentenças onde distingue-se premissas e conclusão

Sentença = Expressão linguística enunciadorade um pensamento completo.


Exemplos de Sentenças.

1. Salvador é a capital da Bahia.2. (2 + 3) = 5.3. Qual o melhor time de futebol do Brasil ?4. Compile o Programa !

O tipo de sentença de interesse em uma argumentação é a sentença declarativa.


Exemplos de Argumentos

Todo homem é mortal. FHC é homem. ------------------------------------- FHC é mortal.

Todo homem é animal Todo gato é animal ------------------------------------- Todo gato é homem


Há exatamente 136 caixas de bombas em um depósito.Cada caixa contém pelo menos 140 bombas.

---------------------------------------------------------------------------Nenhuma caixa tem mais de 156 bombas

Lula é o presidente do BrasilBrasília é a capital do Brasil---------------------------------------------A lua é um satélite da Terra


Lula é o presidente do Brasil-----------------------------------------------------Lula é humano e presidente do Brasil

Lula é o presidente do Brasil-----------------------------------------------------Lula é humano ou presidente do Brasil


Alguns paulistas são latinos.Alguns brasileiros são latinos-------------------------------------------Alguns brasileiros são paulistas

Tudo que é raro é caro. Uma casa boa e barata é rara.-------------------------------------------Uma casa boa e barata é cara.

Todo triângulo tem somente 3 ladosTodo quadrado é triângulo.----------------------------------------------------Todo quadrado tem somente 3 lados.


Argumentos e Solucao de Problemas

-Tenho 3 esferas visualmente identicas. Entretanto duas tem o mesmo peso, enquanto uma terceira tem peso diferente. Utilizando somente uma balanca de equilibrio, sem pesos marcados, como posso descobrir a esfera diferente e saber se e’ mais pesada ou mais leve ???

Prove que uma das 3 esferas e’ mais pesada ou mais leve


Especificacao, Prova e Solucao de Problemas

-Os sobrenomes de Ana, Beatriz e Carla são Arantes, Braga e Castro, não necessariamente nesta ordem. A de sobrenome Braga, que não ‘e Ana, ‘e mais velha que Carla e a sobrenome Castro e’ a mais velha das 3.

Qual a melhor ordem ? - Resolver, Especificar, Provar - Resolver, Provar, Especificar - Especificar, Resolver, Provar - Provar, Especificar, Resolver - Especificar, Provar, Resolver - Provar, Resolver, Especificar


Em Lógica Matemática

Prova

formada por

(Argumentação)

Regras de Inferência formada por

Premissas conclusão

•

(Argumento)

são

Sentenças

Átomosconectivos/ quantificadores

Sentenças Compostas

?


Como representar os elementos da linguagem

lógica tendo por princípio a universalidade ?Formalização da linguagem.

Somente conectivos/quantificadores podem possuir significado a priori.

Átomos são representados por Letras sentenciais (log. Sentencial).

Fórmulas (combinações de átomosvia conectivos) representam sentençasem geral.


O significado de cada conectivo pode ser determinado

pelas regras que ditam seu uso(Semântica Operacional)

Da praxis matemática tiramos :

Conjunção ( "e" lógico)

Disjunção ( "ou" lógico)

Implicação ( "se ____ então____")

~ = Negação ( "não lógico ")

Conectivos

•

O significado de cada conectivo pode ser determinadopelas condições de verdade estabelecidas por ele

(Semântica tradicional ou Tarskiana)


Fórmulas

Toda letra sentencial é uma fórmula

Se e são fórmulas, então também são fórmulas :

- ~

Obs : Parenteses são usados para auxiliar à análise sintática.


Semântica p/ Lógica Clássica

Extensional com Valores de "Verdade".

Atribuição arbitrária de valores para as letras sentenciais.

Fórmulas têm seus valores determinados pela interpretacão e pelas funções semân- ticas associadas a cada conectivo.

(Interpretação)


Funções na forma de Tabela.

V F

V

F

V F

V

F

V F

V

F

V F

F F

V V

V F

V F

V V

~ V F

F VF


V F

V

F

V F

V V

V F

V

F

V F

VF


Atribuição de Valores à fórmulas

Interpretação :

I : Letras {V,F}

Dada uma interpretação I pode-se definir a

denotação associada V:

V(I, L) = I ( L) se L é letra sentencial.

V( I, ) = V(I, ) V( I, )

V(I, ) = V(I, ) V(I, )

V(I, ) = V(I, ) F = ~ V(I, )


Def. Uma f interpretação que a torna verdadeira, i.e.

Existe I , tal que V(I, ) = V

Def. Diz-se que uma fórmula é válida, sse, ela é verdadeira sob toda interpretação.

órmula é dita satisfatível, sse, existe uma

Def. Um conjunto de f órmulas é satisfatível, sse, todasas suas fórmulas são satisfatíveis (para a mesma interpretação.


O conceito de conectivo principal.

É aquele conectivo que aparece em primeiro plano em uma análise sintá- tica.

Exemplos:

(A B) (C D)

~ (A B)

(A B) C


Def. Uma fórmula é dita ser consequência lógica de um conjunto de fórmulas ( ), sse :

- Toda interpretação que "torna" todas as fórmulas de verdadeiras “torna” verdadeira. Ex: - { ~~ A} A - {A, A B} B - {A B, A C, B C} C - {A B} ~B ~A

Def. é equivalente a sse e


Completude funcional da lógica clássica

- Pode-se expressar todas os conectivos em função de e ??




- Pode-se expressar todas as funções booleanas (arid. finita) por meio dos conectivos acima ??

- Pode-se expressar todas as funções booleanas (arid. finita) com um conectivo só (novo certamente) ??


Sistemas Dedutivos e Argumentação Formal

Def1. Um sistema dedutivo é um mecanismo que permite a construção de argumentos formais

Def2. Um sistema dedutivo é um mecanismo que permite estabelecer conclusões a partir de hipóteses.

Def3. Um sistema dedutivo é um conjunto de regras (as vezes axiomas) que permite “chegar” a conclusões (sentenças) a partir de hipóteses (sentenças).

Def4. Um sistema dedutivo é um conjunto de regras (as vezes axiomas) onde os axiomas são fórmulas válidas e as regras preservam a verdade.


Universalidade da noção de

correto

O conceito de argumento correto deve ser baseado na forma do mesmo e não em seu significado particular, ou

Um argumento é correto quando é invariante sob substituição, i.e., o que importa é o rela-cionamento entre premissas e conclusão e não estas propriamente ditas.


Os sistemas a la Frege/Hilbert

Esquemas de Axiomas:

(K) A(B A)

(S) A (B C) (A B) (A C)

(Cla) A A

Regra:

(Modus Ponens) A AB

B


Exemplos de Deduções

A ((A A) A) A ((A A) A) ( (A(AA)) (AA))

(A(AA)) (AA)A(AA)

AA

B (B A) B (B A) A B (B A)

A B (B A)


Discussão:

1- O método da “tabela verdade” é um sistema dedutivo ??

2- O que dizer do sistema dedutivo somente com a regra de modus ponens e como axiomas todas as fórmulas válidas (tautologias)

3- Como comparar sistemas dedutivos ??

4- O que a prova de um teorema deve nos dizer ??

5- O que prova de teoremas tem a ver com computação e programação ??


Programa do Curso

1. Linguagem Clássica de Primeira Ordem.

2. Lógica Intuicionista3. Algebras de Processo4. Logicas Temporais

Documents

Lógica e Especificação Edward Hermann Haeusler Departamento de Informática TECMF PUC/RJ