Dedução Natural e Sistemarosalvo.oliveira/Disciplinas/... · Univasf –Engenharia de Computação - LÓGICA APLICADA A COMPUTAÇÃO - Prof.: Rosalvo Neto 04 Definições Dedução

Dedução Natural e Sistema Axiomático Pa(Capítulo 6)

LÓGICA APLICADA A COMPUTAÇÃO

Professor: Rosalvo Ferreira de Oliveira Neto

Estrutura

1. Definições

2. Dedução Natural

3. Sistemas axiomático Pa

4. Lista

Univasf – Engenharia de Computação - LÓGICA APLICADA A COMPUTAÇÃO - Prof.: Rosalvo Neto

04Univasf – Engenharia de Computação - LÓGICA APLICADA A COMPUTAÇÃO - Prof.: Rosalvo Neto

Definições Dedução Natural Sistemas axiomático Pa Lista

Um dos objetivos principais da lógica é o estudo de estruturas quepossam ser utilizadas na representação e dedução doconhecimento.

Se, por um lado, a Lógica estabelece uma linguagem útil, elatambém analisa como o conhecimento é deduzido, formalmente, apartir do conhecimento dado a priori.



Esse conhecimento, fornecido de antemão, é representado por umconjunto de fórmulas denominados axiomas. Os axiomas são,portanto, fórmulas às quais atribuímos um status especial deverdade básica ou a priori.



Argumentos Dedutivos

X

Argumentos Indutivos



Argumento

Seqüência de premissas seguida por uma conclusão.



Os argumentos são divididos em dois grupos:

Argumentos Dedutivos

•O argumento será dedutivo quando suas premissas fornecerem umaprova conclusiva da veracidade da conclusão.

•O argumento é dedutivo quando a conclusão é completamentederivada das premissas.

Argumentos Indutivos

•O argumento será indutivo quando suas premissas não forneceremo apoio completo para ratificar as conclusões.



Exemplo de Argumento Dedutivo

A porta do apartamento 1 deste edifício é branca




Este edifício tem apenas 4 apartamentos

Logo, todas as portas de apartamento deste edifício sãobrancas.



Exemplo de Argumento Indutivo





Este edifício tem 6 apartamentos

Logo, todas as portas de apartamento deste edifícios são brancas.



Argumento válido

Um argumento é válido quando sua conclusão é uma conseqüêncialógica de suas premissas



Conseqüência lógica

Definição informal:

Uma fórmula é uma conseqüência lógica de um conjunto de fórmulas se sempre que estas forem verdadeiras aquela também seja verdadeira.

Definição formal:

Dada uma fórmula H e um conjunto de hipóteses b, H é conseqüência lógica de b num sistema de dedução, se existir uma prova de H a partir de b



Sistema Axiomático

Seja S0 um conjunto de objetos sintáticos. Um sistema axiomático sobreSO é um par K = (A,R), onde

A é um conjunto finito de esquemas de axiomas, que são conjuntosdecidíveis de SO. Os elementos de um esquema de axioma sãochamados de axiomas.

Na lógica tradicional, um axioma ou postulado é uma sentença ouproposição que não é provada ou demonstrada e é considerada comoóbvia

R é um conjunto finito de regras de inferência, que são subconjuntosdecidíveis de SO.



Prova Sintática

Sejam:

H uma fórmula e

β um conjunto de fórmulas denominadas por hipóteses.

Uma prova sintática de H a partir de β, é uma seqüência defórmulas

H1,H2,...,Hn,

onde temos:

H = Hn.



Sistemas Dedutivos

Um sistema dedutivo é um conjunto de regras (as vezes axiomas)que permite obter (deduzir) conclusões (sentenças) a partir dehipóteses (sentenças).



Sistemas Dedução Natural

Dedução natural é um dos sistemas dedutivos utilizados paraconstruir demonstrações formais na Lógica, tais demonstraçõessão realizadas através de uma árvore de dedução utilizando regrasde introdução e eliminação.



Regras

Regras de Introdução

Introdução da CONJUNÇÃOIntrodução da DISJUNÇÃOIntrodução da IMPLICAÇÃOIntrodução da NEGAÇÃO

Regras de Eliminação

Eliminação da CONJUNÇÃOEliminação da DISJUNÇÃOEliminação da IMPLICAÇÃOEliminação da NEGAÇÃO



Introdução da CONJUNÇÃO



Introdução da DISJUNÇÃO



Introdução da IMPLICAÇÃO



Introdução da NEGAÇÃO



Eliminação da CONJUNÇÃO



Eliminação da DISJUNÇÃO



Eliminação da IMPLICAÇÃO



Eliminação da NEGAÇÃO



Exemplos de prova de conseqüência lógica por dedução natural











Algumas das principais regras da lógica proposicional clássica são as seguintes:









Definição 6.1 (sistema axiomático Pa) O sistema formal axiomático Pa da Lógica Proposicional é definidopela composição dos quatro elementos:

•o alfabeto da Lógica Proposicional, na forma simplificada, Definição 5.4, sem o símbolo de verdade false;

•o conjunto das fórmulas da Lógica Proposicional;

•um subconjunto das fórmulas, que são denominadas axiomas;

•um conjunto de regras de dedução.



Definição 6.2 (axiomas do sistema Pa) Os axiomas1 do sistema Pa

são fórmulas da Lógica Proposicional determinadas pelosesquemas indicados a seguir. Nesses esquemas E, G e H sãofórmulas quaisquer da Lógica Proposicional.

Ax1 = ¬(H ∨ H) ∨ H,

Ax2 = ¬H ∨ (G ∨ H),

Ax3 = ¬(¬H ∨ G) ∨ (¬(E ∨ H) ∨ (G ∨ E)).



Definição 6.2 (axiomas do sistema Pa)

Axl =(H ∨ H) → H,

Ax2 = H → (G ∨ H),

Ax3 =(H → G) → ((E ∨ H) → (G ∨ E)).



Notação. No sistema Pa são consideradas as correspondências aseguir, que definem os conectivos, e .

H G denota ( H ∨ G).

(H G) denota (H G) ∧ (G H).

(H ∧ G) denota ( H ∨ G).



Definição 6.3 (regra de inferência do sistema Pa, modus ponens)

Dadas as fórmulas H e G, a regra de inferência do sistema Pa,denominada modus ponens (MP ), é definida peloprocedimento:

tendo H e (¬H ∨ G) deduza G.



Notação. Para representar o esquema de regra de inferênciamodus ponens, a notação a seguir é considerada

Nessa notação, o "numerador" da equação é o antecedente.

O "denominador" é o conseqüente.



Definição 6.5 (conseqüência lógica sintática no sistema Pa)

Dada uma fórmula H e um conjunto de hipóteses β,

então

H é uma conseqüência lógica sintática de β em Pa,

se

existe uma prova de H a partir de β.



Definição 6.6 (teorema no sistema Pa)

Uma fórmula H é um teorema em Pa,

se

existe uma prova de H, em Pa, que utiliza apenas os axiomas.

Nesse caso, o conjunto de hipóteses é vazio.



Prove utilizando o Sistema de Dedução Natural

1- A Λ (B Λ C) (A Λ B) Λ C

2- A D V ((B V A) V C)



1- A Λ (B Λ C) (A Λ B) Λ C



2- A D V ((B V A) V C)



Nestes exercícios, além de MP e MT, lembre-se de usar DeduçãoNatural.

Documents

Dedução Natural e Sistemarosalvo.oliveira/Disciplinas/... · Univasf –Engenharia de Computação - LÓGICA APLICADA A COMPUTAÇÃO - Prof.: Rosalvo Neto 04 Definições Dedução