Dedução Natural e Sistemarosalvo.oliveira/Disciplinas/... · Univasf –Engenharia de...

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.

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

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

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.

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

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

Argumentos Dedutivos

X

Argumentos Indutivos

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

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

Argumento

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

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

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

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.

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

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

Exemplo de Argumento Dedutivo

A porta do apartamento 1 deste edifício é branca

A porta do apartamento 2 deste edifício é branca

A porta do apartamento 3 deste edifício é branca

A porta do apartamento 4 deste edifício é branca

Este edifício tem apenas 4 apartamentos

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

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

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

Exemplo de Argumento Indutivo

A porta do apartamento 1 deste edifício é branca

A porta do apartamento 2 deste edifício é branca

A porta do apartamento 3 deste edifício é branca

A porta do apartamento 4 deste edifício é branca

Este edifício tem 6 apartamentos

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

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

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

Argumento válido

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

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

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

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

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

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

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.

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

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

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.

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

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

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).

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

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

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.

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

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

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

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

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

Introdução da CONJUNÇÃO

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

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

Introdução da DISJUNÇÃO

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

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

Introdução da IMPLICAÇÃO

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

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

Introdução da NEGAÇÃO

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

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

Eliminação da CONJUNÇÃO

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

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

Eliminação da DISJUNÇÃO

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

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

Eliminação da IMPLICAÇÃO

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

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

Eliminação da NEGAÇÃO

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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)).

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

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

Definição 6.2 (axiomas do sistema Pa)

Axl =(H ∨ H) → H,

Ax2 = H → (G ∨ H),

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

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

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

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).

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

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

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.

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

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

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.

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

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

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 β.

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

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

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.

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

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

Prove utilizando o Sistema de Dedução Natural

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

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

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

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

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

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

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

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

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

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

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