Introdução à Lógica Matemática

Método Dedutivo no Cálculo de Predicados de 1ª Ordem

João Marques Salomão

Curso de Engenharia Elétrica

CEFET-ES

Introdução à Lógica Matemática - 2006/1 – p. 1/13

Eliminação e Inserção de Quantificadores

No CP as premissas são relações do tipo “Pxy”, “Qxyz”, etc. Portanto, não há nenhum processo sistemático para validar os argumentos.

As regras de inferência e de dedução, se aplicam também ao CP, mas os quantificadores, variáveis e predicados nos enunciados, complicam a validação dos argumentos.

Regras adicionais de inferência são definidas para a inserção e/ou eliminação dos quantificadores.

Neste caso:As Premissas do CP são transformadas em enunciados do Cálculo Proposicional, isto permite usar as eqüivalências e inferências conhecidas, em seguida, insere-se novamente os quantificadores e processa-se a validação.

O processo gera quatros regras e exige:1 - Eliminar os quantificadores das premissas.

2 - Deduzir a conclusão com eqüivalências e inferências do Cálculo Proposicional.

3 - Inserir (se for o caso) os quantificadores na conclusão.

As quatro regras geradas são chamadas de: Generalização Universal e Existencial;Instanciação Universal e Existencial;

Eliminação e Inserção de Quantificadores

Instanciação Universal (IU)

Pode ser enunciada da seguinte forma: “Se todos os objetos de um dado universo possuem uma dada propriedade, então um objeto particular desse universo também possui essa propriedade”. Isto é: u Onde uma regra de inferência (RI), ou implicação tautológica. Isto é, é uma fórmula que resulta de ao substituir cada ocorrência da variável livre u por um termo t.

A RI pode assumir muitas formas, dependendo de : Exemplos:

Se x Fx então Fx Se x Fx então FaSe y (FyGb) então Fx Gb Se y (FyGb) então FaGbSe x Gx então Gy Se x (Gx Hx) então Gz HzSe x (Fxx (GxHy)) então Fb x (GxHy)

Ver aplicação dessa regra na pagina 58.

Generalização Universal (GU)

“Se um objeto, arbitrariamente escolhido dentre um universo, tiver uma certa propriedade, todos os objetos desse universo terão essa propriedade”. Em termos simbólicos: u w ( w), onde é uma fórmula e w um objeto arbitrariamente escolhido, é uma regra de Inferência.

Podemos garantir que todos os elementos de um universo possuem dada propriedade ao utilizarmos a expressão arbitrariamente escolhido.

Alguns exemplos dessa regra de inferência:Se Fx então x FxSe Fx então y Fy

Ver aplicação da regra GU através do argumento da página 59.

Generalização Existencial (GE)

“O que é verdadeiro para um dado objeto, é verdadeiro para algum objeto”.

Em formulação simbólica, temos:: w u u,onde w é uma constante ou variável, u é variável, e w resulta de u pela substituição das ocorrências livres de u por w; - se w for uma variável, deve ocorrer livre em w nos locais em que u ocorrer livre em u.

Exemplos de aplicação desta regra de inferência:Se Fx então y Fy Se Fa então x FxSe Fa então y Fy Se FaGb então x (FxGb)Se Fa Gb então y (Fy Gb) Se Fx Gy então z (Fx Gz)Se Fx Gx então y (Fy Gy) Se Fx Gx então y (Fy Gy)

Um exemplo de utilização da regra GE é dado na dedução do argumento da página 60.

Instanciação Existencial (IE)

“O que é verdadeiro para algum objeto, é verdadeiro para um dado objeto, desde que esse objeto não tenha sido utilizado anteriormente na dedução”. Em notação simbólica: u u w, onde é uma fórmula, e desde que w seja variável livre nos locais em que u ocorria livre em u, e que w não tenha ocorrência livre anterior.

Dois exemplos da utilização dessa regra:Se x Fx então Fx Se x Fx então Fy.

Um exemplo de aplicação dessa regra,é dado na dedução do argumento da página 61.

Obs: A aplicação dessa RI exige certos cuidados. Deve-se certificar de que o termo não tenha sido utilizado anteriormente na dedução.

Observe o 2o argumento da página 61/62 e ver os cuidados no uso da GE- página 62.

Eqüivalências e Regras de Inferências.

As eqüivalências e inferências do Cálculo Proposicional podem ser utilizadas para obter suas correspondentes entre expressões com quantificadores e variáveis. Veja alguns conceitos novos:

Validade lógica (corresponde à tautologia no Cálc. Proposicional): “Uma sentença fechada é logicamente válida, se e somente se, qualquer instanciação da sentença em qualquer universo não vazio for uma sentença verdadeira (for satisfeita para todos os objetos)”.

Isto é, uma sentença fechada é dita válida quando sua veracidade não depender da instanciação das variáveis.

Eqüivalências e Regras de Inferências

A sentença x Px x Px, diz que:“se todos os elementos x possuírem o predicado P, então existe um x que possui o predicado P”. Pode ser instanciada para: “se todos estão alegres, então existe alguém alegre”,

“uma sentença aberta é válido quando seu conjunto verdade for o próprio universo”. Por exemplo:O aberto: Py x Px, afirma que:“se y possui a propriedade P, então existe um x que possui a propriedade P”, o que é satisfeito por todos os objetos de qualquer universo. Instanciações dessa sentença: “se y é sábio, então existe um x tal que x é sábio”; “se y é mortal, então existe um x tal que x é mortal”.

Sentenças x tautologias

É possível mostrar que se um esquema sentencial tiver a forma de um enunciado válido do Cálculo Proposicional (uma tautologia), então ele também será logicamente válido no CP . Isto é extremamente útil, pois permite construir um grande número de esquemas sentenciais abertos e fechados logicamente válidos.

Exemplos:sentenças válidas, por possuírem a forma de tautologias:

Sentenças Eqüivalentes no CP

Duas sentenças S1 e S2 são equivalentes, S1 S2, se e somente se, S1 S2 for um esquema logicamente válido.

“Uma sentença com a forma de uma equivalência do Cálculo Proposicional também será uma equivalência do CP ”. Exemplos:

Sentenças Eqüivalentes no CP

Como ocorre no Sistema Proposicional, se duas sentenças S1 e S2, do CP, diferirem por partes equivalentes, então elas são equivalentes.

Por exemplo: (Py x Qx) Rx é equivalente a Py x Qx Rx.

Em resumo: padrões sentenciais, cuja forma é a de padrões sentenciais equivalentes ou que diferenciam-se pela ocorrência de partes equivalentes, são equivalentes.

Eqüivalencias de esquemas sentenciais do CP

Há esquemas sentenciais do Cálculo de Predicados que são equivalentes, mas que não têm a forma de enunciados equivalentes.

Exemplos:

x Px x Px (De Morgan) [EQ01]

x Px x Px (De Morgan) [EQ02]

x (Px Qx ) x Px x Qx (Distrib) [EQ03]

x (Px Qx ) x Px x Qx (Distrib) [EQ04]

Eqüivalencias de sentenças do CP

Podemos também definir inferências no Cálculo de Predicados. Assim, dizemos que da sentença S1 inferimos S2, e escrevemos

S1 S2, se e somente se S1 S2 for logicamente válida. Mais uma vez as inferências do Cálculo Proposicional podem ser

utilizados como padrões para inferências no Cálculo de Predicados: Exemplos:

Inferências de sentenças do CP

O CP possui inferências, que não correspondem a padrões de inferência nos enunciados do cálculo proposicional. Exemplos:

x Px x Px [INF01]x (Px Qx) x Px x Qx [INF02]x Px x Qx x (Px Qx) [INF03]x (Px Qx) x Px x Qx [INF04]

Essas eqüivalências e inferências serão úteis na dedução de argumentos no CP.

As que possuem a forma de enunciados tautológicos têm, sua validade lógica assegurada. As demais, EQ01 a EQ04 e INF01 a INF04, necessitam de demonstração formal (Ver páginas 65 a 69).

Dedução no CP

Um argumento no CP é tal que, um dos esquemas sentenciais, chamado conclusão, decorre logicamente dos demais, chamados premissas;

Se essa decorrência se verificar, o argumento é dito válido, em caso contrário, é inválido.

Deduzir um argumento, é, obter uma seqüência de esquemas sentenciais 1, 2, ..., n, onde cada i ou é uma premissa ou resulta das anteriores após o uso de eqüivalências e inferências.

Para deduzir a validade de um argumento, usamos as regras de inferência GU, IU, GE e IE, e as de equivalência/inferências EQ01 a EQ04 e INF01 a INF04.

Dedução: Aspectos gerais

Procedimentos gerais usados na dedução (as premissas e conclusão devem estar na forma simbólica).

Utilizar as:1. eqüivalências e inferências do CP que correspondem às

eqüivalências e inferências do Cálculo Proposicional;2. eqüivalências e inferências EQ01 a EQ04 e INF01 a INF04;3. inferências IU e IE, visando eliminar os quantificadores;4. eqüivalências e inferências do Cálculo Proposicional, visando

chegar à conclusão;5. inferências GE e GU, visando reintroduzir os quantificadores

na conclusão, se for necessário.

Revisão: O Diagrama de Venn e o SC

Para a Proposição Universal Afirmativa (A) “Todo S é P”, x (Sx Px) temos o 1o diagrama;

Proposição Universal Negativa (E), “Nenhum S é P”, ou, simbolicamente, x (Sx ~Px), pelo 2o;

A Proposição Particular Afirmativa (I), “Algum S é P”, ou x (Sx Px), é representada pelo 3o diagrama abaixo;

Proposição Particular Negativa (O), “Algum S não é P”, cuja forma simbólica é x (Sx ~Px),

A I E O

Dedução no CP: Exemplo

Nenhum atleta é apegado aos livros.

Carlos é apegado aos livros.

Portanto, Carlos não é um atleta.

Sol: x (Ax Lx)

L (Carlos)

A (Carlos)

Dedução no CP: Exemplo

2. Ácidos ou bases são químicos.

O vinagre é um ácido.

Logo, o vinagre é um químico.

Sol: x(AxBx Qx) A (vinagre) Q (vinagre)

Exemplos de dedução

3. Todos os cidadãos que não são traidores estão presentes.

Todos os oficiais são cidadãos.

Alguns oficiais não estão presentes.

Logo, há traidores.Sol:

x (Cx TxPx)

x (Ox Cx)

x (Ox Px)

x Tx

Ver mais ex. na pp. 71.

Invalidade de argumentos no CP

O método do absurdo Proposicional, (premissas verdades e conclusão falsa), pode ser adaptado ao CP desde que exista pelo menos um indivíduo no universo.

Exemplo: Todos os mercenários são violentos. Nenhum guerrilheiro é mercenário. Logo, nenhum guerrilheiro é violento

Simbolicamente:x (Mx Vx) (A) x (Gx Mx) (E) x (Gx Vx)Se existir apenas um indivíduo a no universo, o argumento assume:Ma VaGa Ma Ga Va

(Mostre por SC)(Ver ex. pp 72 : exige pelo menos 2 indivíduos)

Validade e Subargumentos

Se o número de premissas e/ou de predicados em um argumento é grande, a dificuldade em deduzir a conclusão ou de provar a invalidade do argumento cresce significativamente.

Nestes casos, o uso de subargumentos é recomendável. Ele consiste em:

1. escolher uma ou mais premissas no argumento dado;

2. obter uma conclusão com essas premissas, construindo um subargumento válido;

3. incluir a conclusão obtida como mais uma premissa no

argumento original.Repetir o processo até se obter a conclusão do argumento original, ou ficar convencido de que isso não será possível.

Validade: uso de subargumentos

Exemplo: Alguns fotógrafos são habilidosos. Só artistas são fotógrafos. Os fotógrafos não são todos habilidosos. Todo biscateiro é habilidoso. Logo, alguns artistas não são biscateiros.

Sol: a 3a e 4a premissas escritas na forma típica:Todo biscateiro é habilidoso.Alguns fotógrafos não são habilidosos. Logo, alguns fotógrafos não são biscateiros. (silogismo categórico). Sol: Forma simbólicax (Bx Hx) (A), x (Fx Hx) (O); x (Fx Bx)

O diagrama de Venn ao lado valida o subargumento:

Validade: uso de subargumentos

Substituindo as premissas pela conclusão, e escrevendo a outra premissa na forma típica, temos o outro argumento como outro silogismo categórico:

Todos os fotógrafos são artistas.Alguns fotógrafos não são biscateiros.Logo, alguns artistas não são biscateiros.Sol: Forma simbólica:x (Fx Ax) (A), x (Fx Bx) (O); x (Ax Bx)

O diagrama de Venn ao lado valida o argumento:

(ver outro exemplo na pag 75) .

Invalidade: uso de subargumentos

Ver o exemplo das páginas 78, 79 e 80)

FIM