Material de Apoio - Lógica para Computação

Universidade de Caxias do SulCentro de Computação e Tecnologia da InformaçãoProf. Simone C. Mendes Paiva

LÓGICA PARA COMPUTAÇÃOMATERIAL DA DISCIPLINA

Sumário

1.1 CONECTIVOS LÓGICOS ......................................................................................................................................4

1.1.1 Conectivo E (conjunção)....................................................................................................................................4

1.1.2 Conectivo OU (disjunção).................................................................................................................................4

1.1.3 Implicação (condicional)....................................................................................................................................4

1.1.4 Equivalência ......................................................................................................................................................4

1.1.5 Negação..............................................................................................................................................................4

1.2 WFFS – FÓRMULAS BEM FORMADAS........................................................................................................................5

1.3 TABELAS-VERDADE....................................................................................................................................................8

1.3.1 Tabela-verdade da negação...............................................................................................................................8

1.3.2 Tabela-verdade da conjunção ...........................................................................................................................9

1.3.3 Tabela-verdade da disjunção ............................................................................................................................9

1.3.4 Tabela-verdade da implicação ..........................................................................................................................9

1.3.5 Tabela-verdade da equivalência ....................................................................................................................10

1.4 CLASSIFICAÇÃO DE WFFS USANDO TABELAS-VERDADE.........................................................................................11

1.5 APLICAÇÕES DE TABELAS-VERDADE E FORMALIZAÇÃO.......................................................................12

CÁLCULO DE PREDICADOS....................................................................................................................................17

10.1 QUANTIFICADORES E VARIÁVEIS................................................................................................................17

10.1.1 QUANTIFICADOR UNIVERSAL: ...............................................................................................................17

10.1.2 QUANTIFICADOR EXISTENCIAL ............................................................................................................17

10.2 PREDICADOS E NOMES PRÓPRIOS................................................................................................................19

10.3 FORMALIZAÇÃO: ABC.............................................................................................................................................19

10.4 FORMALIZAÇÃO: ACB.............................................................................................................................................19

10.5 FORMALIZAÇÃO: DCLB...........................................................................................................................................19

EXERCÍCIOS DE REVISÃO........................................................................................................................................23

10.6 REGRAS NÃO HIPOTÉTICAS DE INFERÊNCIA.............................................................................................25

10.6.1 MODUS PONENS (MP).................................................................................................................................25

10.6.2 ELIMINAÇÃO DA NEGAÇÃO: (E~) ............................................................................................................26

10.6.3 INTRODUÇÃO DA CONJUNÇÃO (I∧)........................................................................................................27

10.6.4 ELIMINAÇÃO DA CONJUNÇÃO (E∧).........................................................................................................27

10.6.5 INTRODUÇÃO DA DISJUNÇÃO ( I ∨)........................................................................................................28

10.6.6 ELIMINAÇÃO DA DISJUNÇÃO (E∨)...........................................................................................................29

10.6.7 Introdução do Bicondicional (I↔): ..............................................................................................................30

10.6.8 ELIMINAÇÃO DO BICONDICIONAL (E↔)..............................................................................................31

10.7 REGRAS HIPOTÉTICAS DE INFERÊNCIA......................................................................................................32

10.7.1 SUBPROVA....................................................................................................................................................33

Prof. Simone C. Mendes Paiva

Lógica para Computação

2

10.7.2 PROVA DO CONDICIONAL (PC)................................................................................................................35

10.7.3 REDUÇÃO AO ABSURDO (RAA) ................................................................................................................36

10.8 ESTRATÉGIAS PARA PROVA...........................................................................................................................40

10.9 REGRAS DERIVADAS E DE EQUIVALÊNCIA...............................................................................................41

10.10 REGRAS DE INFERÊNCIA PARA QUANTIFICADORES.............................................................................46

10.10.1 ELIMINAÇÃO UNIVERSAL (EU)...............................................................................................................46

10.10.2 INTRODUÇÃO DO UNIVERSAL (IU)........................................................................................................47

10.10.2.1 RESTRIÇÕES DE IU............................................................................................................................................47

10.10.3 INTRODUÇÃO EXISTENCIAL (IE)............................................................................................................48

10.10.4 ELIMINAÇÃO DO EXISTENCIAL (EE)......................................................................................................48

10.10.4.1 RESTRIÇÕES EE..................................................................................................................................................49

1.6 ÁRVORES DE REFUTAÇÃO................................................................................................................................50



3

CÁLCULO PROPOSICIONAL

1.1 CONECTIVOS LÓGICOS

1.1.1 Conectivo E (conjunção)

representação: ∧ , & leitura: e, mas, também

Considerando as sentenças abaixo:

(1) “Portas abrem.” (2) “Telhados cobrem.”

Podemos formalizar a sentença (1) como sendo A, e a sentença (2) como B. Se desejarmos representar a sentença “Portas abrem e telhados cobrem.” , teremos a fórmula abaixo. A versão “Portas abrem mas telhados cobrem.” possuiria a mesma representação.

1.1.2 Conectivo OU (disjunção)

representação: ∨leitura: ou

Podemos representar a sentença “Portas abrem ou telhados cobrem.” como

1.1.3 Implicação (condicional)

representação: →leitura: se...então, somente se

A sentença “Se portas abrem, então telhados cobrem.” é formalizada como

1.1.4 Equivalência

representação: ↔leitura: se e somente se

A sentença “Portas abrem se, e somente se, telhados cobrem.” é formalizada como A ↔ é a abreviatura para (A → B) ∧ (B → A).A e B têm o mesmo valor verdade.

1.1.5 Negação

representação: ~, ¬leitura: não, não é o caso que

A sentença “Portas não abrem.” ou “Não é o caso que portas abram.” é representada por A tabela abaixo resume os conectivos lógicos e suas representações:



4

~A

A↔ B

A → B

A ∨ B

A ∧ B

Operador Lógico SímboloNão é o caso que ~E ∧Ou ∨Se ... então →Se e somente se ↔

1.2 WFFs – Fórmulas Bem Formadas

Uma fórmula do cálculo proposicional é uma seqüência qualquer de elementos do vocabulário. Uma wff (well formed formula) ou fórmula-bem-formada é uma fórmula definida pelas seguintes regras:

1. qualquer letra sentencial é uma wff.2. se A é uma wff, então ~A também é.3. se A e B são wff, então (A ∧B), (A∨B), (A→B) e (A↔B) também são.

Qualquer outra coisa não estabelecida por uma das regras acima não é uma wff.

Exercícios:

1.Utilize as regras de formação para determinar quais das seguintes fórmulas são wffs e quais não são. Justifique sua resposta.

a) ~~~Rb) (~R)c) PQd) P → Qe) (P→Q)f) ~(P→Q)g) ((P∧Q) →R)h) (P∧Q) →Ri) ~(~P ∧ ~Q)j) ((P∧Q) ∨ (R∧S))

2. Interprete a letra sentencial “C” como 'Está chovendo', e “N” como 'Está nevando' e expresse a forma de cada sentença na notação do cálculo proposicional.

a) Está Chovendo

b) Não está chovendo

c) Está chovendo ou nevando

d) Está chovendo e nevando

e) Está chovendo mas não está nevando

f) Não é o caso que está chovendo e nevando

g) Se não está chovendo, então está nevando

h) Não é o caso que se está chovendo então está nevando

i) Não é o caso que se está nevando então está chovendo

j) Está chovendo se e somente se não está nevando

k) Não é o caso que está chovendo ou nevando



5

l) Se está nevando e chovendo, então está nevando

m) Se não está chovendo, então não é o caso que está nevando e chovendo

n) Ou está chovendo, ou está nevando e chovendo

o) Ou está chovendo e nevando, ou está nevando mas não está chovendo.

3.Formalize os seguintes enunciados, utilizando o vocabulário abaixo:

P – Paula vai.

Q – Quincas vai.

R – Richard vai.

S – Sara vai.

a) Paula não vai.

b) Paula vai, mas Quincas não.

c) Se Paula for, então Quincas também irá.

d) Paula irá, se Quincas for.

e) Paula irá, somente se Quincas for.

f) Paula irá, se e somente se Quincas for.

g) Nem Paula nem Quincas irão.

h) Paula e Quincas não irão.

i) Ou Paula vai, ou Quincas não vai.

j) Paula não irá se Quincas for.

k) Ou Paula irá, ou Richard e Quincas irão.

l) Se Paula for, então Richard e Quincas irão.

m) Paula não irá, mas Richard e Quincas irão.

n) Se Richard for, então se Paula não for, Quincas irá.

o) Se nem Richard nem Quincas forem, então Paula irá.

p) Richard irá somente se Paula e Quincas não forem.

q) Richard e Quincas vão, apesar de Paula e Sara não irem.

r) Se Richard ou Quincas for, então Paula irá e Sara não irá.

s) Richard e Quincas irão se e somente se Paula ou Sara for.

Se Sara for, então Richard ou Paula irão, e se Sara não for, então Paula e Quincas irão.

4. Formalize os seguintes argumentos usando as letras sentenciais indicadas. Utilize os indicadores de premissa (vírgulas) e conclusão (asserção --| ) para distinguir as premissas da conclusão.

a) Se Deus existe, então a vida tem significado. Deus existe. Portanto, a vida tem significado. (D, V)

b) Deus não existe. Pois, se Deus existisse, a vida teria significado. Mas a vida não tem significado. (D, V)

c) Se o avião não tivesse caído, nós teríamos feito contato pelo rádio. Não fizemos contato pelo rádio. Portanto, o avião caiu. (C, R)

d) Como hoje não é quinta-feira, deve ser sexta-feira. Hoje é quinta-feira ou sexta-feira. (Q, S)



6

e) Se hoje é quinta-feira, então amanhã será sexta-feira. Se amanhã for sexta-feira, então depois de amanhã será sábado. Conseqüentemente, se hoje for quinta-feira, então depois de amanhã será sábado. (Q, S1, S2)

f) Hoje é um fim de semana se e somente se é sábado ou domingo. Portanto, hoje é um final de semana, desde que hoje é sábado. (F, S, D)

g) Hoje é um fim de semana se hoje é sábado ou domingo. Mas, hoje não é um fim de semana. Portanto, hoje não é sábado e hoje não é domingo. (F, S, D)

h) Hoje é um fim de semana somente se hoje é sábado ou domingo. Hoje não é sábado. Hoje não é domingo. Portanto, hoje não é um fim de semana. (F, S, D)

i) A proposta de auxílio não está no correio. Se os árbitros a receberem até sexta-feira, eles a analisarão. Portanto, eles a analisarão porque se a proposta estiver no correio, eles a receberão até sexta-feira. (C, S, A)

j) Ela não está em casa ou não está atendendo ao telefone. Mas se ela não está em casa, então ela foi seqüestrada. E se ela não está atendendo ao telefone, ela está correndo algum outro perigo. Portanto, ou ela foi seqüestrada ou ela está correndo um outro perigo. (C, T, S, P)

5. Os seguintes argumentos são válidos. Formalize-os usando a interpretação indicada. Após conhecer as regras

básicas de derivação (conteúdo a ser trabalhado posteriormente!), prove a validade da forma resultante

utilizando somente as dez regras de introdução de eliminação.

C: A conclusão deste argumento é verdadeira

P: As premissas deste argumento são verdadeiras

S: Este argumento é correto

V: Este argumento é válido

a) Este argumento não é incorreto. Portanto, este argumento é correto.

b) Este argumento é correto. Portanto, este argumento não é incorreto.

c) Se este argumento for correto, então ele será válido. Ele não é válido. Portanto, ele não é correto.

d) Se este argumento for correto, então ele não será inválido. Ele é correto. Daí, ele é válido.

e) Se este argumento for correto, então ele não será inválido. Assim, se ele for inválido, então ele será incorreto.

f) Este argumento é correto e válido. Portanto, ele é correto ou ele é inválido.

g) Este argumento não é, ambos, correto e inválido. Ele é correto. Portanto, ele é válido.

h) Este argumento é correto se e somente se todas as suas premissas forem verdadeiras. Mas nem todas as suas

premissas são verdadeiras. Portanto, ele é incorreto.



7

i) Se a conclusão deste argumento for não-verdadeira, então este argumento é incorreto. Assim, não é caso que este

argumento é correto e sua conclusão não-verdadeira.

j) Se este argumento for incorreto e válido, então nem todas as suas premissas são verdadeiras. Todas as suas premissas

são verdadeiras. Ele é válido. Portanto, ele é correto.

k) Se este argumento for válido e todas as suas premissas forem verdadeiras, então ele será correto. Se ele for correto,

então a sua conclusão será verdadeira. Todas as suas premissas são verdadeiras. Portanto, se este argumento for válido,

então a sua conclusão será verdadeira.

l) Ou este argumento é incorreto ou, caso contrário, ele é válido e todas as suas premissas são verdadeiras. Donde, ele é

incorreto ou válido.

m) Este argumento é correto se e somente se ele for válido e todas as suas premissas forem verdadeiras. Nem todas as

suas premissas são verdadeiras. Daí, ele é incorreto.

n) Este argumento é correto se e somente se ele for válido e todas as suas premissas forem verdadeiras. Daí, se ele for

válido, ele será correto se todas as suas premissas forem verdadeiras.

o) Este argumento será incorreto se e somente se nem todas as suas premissas forem verdadeiras ou se ele for inválido.

Mas ele é válido e todas as suas premissas são verdadeiras. Portanto, ele é correto.

1.3 Tabelas-Verdade

O conceito central na semântica da lógica proposicional é o valor-verdade. Os enunciados verdadeiros possuem valor-verdade verdadeiro, e os enunciados falsos possuem valor-verdade falso. Todos enunciados possuem um único valor-verdade. A semântica para a lógica proposicional se baseia no princípio de bivalência, supondo que verdadeiro e falso são os únicos valores-verdade e que em toda situação possível cada enunciado assume um deles. Utiliza-se as abreviações V para verdadeiro e F para falso.

A tabela abaixo chama-se Tabela-Verdade. Abaixo de A são analisadas duas possibilidades: ou A é verdadeiro ou A é falso. ~A possui os valores-verdade para cada valor-verdade de A.

1.3.1 Tabela-verdade da negaçãoA negação de um enunciado A é verdadeira se A for falso, e é falsa se A for verdadeiro.

A ~AV FF V



8

1.3.2 Tabela-verdade da conjunção Uma conjunção é verdadeira se ambos os seus conjunctos forem verdadeiros, ou seja, se ambas as letras sentenciais que

participam da conjunção forem verdadeiras. Senão, ela é falsa.

A B A∧BV V VV F FF V FF F F

1.3.3 Tabela-verdade da disjunção Uma disjunção é verdadeira se, pelo menos, um dos disjunctos for verdadeiro, senão ela é falsa. Ou seja, A∨B será

verdadeiro sempre que , no mínimo, uma das letras sentenciais (A ou B) for verdadeira.

A B A∨BV V VV F VF V VF F F

1.3.4 Tabela-verdade da implicação A construção da tabela-verdade da implicação exige o conhecimento dos conceitos de antecedente e conseqüente.

Antecedente: é a letra sentencial ou wff que encontra-se antes do conectivo da implicação.Conseqüente: é a letra sentencial ou wff que encontra-se depois do conectivo da implicação.

Exemplo:Indique o antecedente e o conseqüente das frases abaixo:

a) A caneta escreve quando tem tinta e está com a tampa aberta. Antecedente: a caneta escreveConseqüente: ter tinta e estar com a tampa aberta

b) Se a fome continuar, então algumas pessoas morrerão. Antecedente: a fome continuarConseqüente: algumas pessoas morrerão

A tabela-verdade da implicação só será falsa no caso em que o antecedente da implicação é verdadeiro e o conseqüente é falso. Em todos os demais casos, ela é verdadeira.

A B A→BV V VV F FF V VF F V

Considere a seguinte afirmação:

“Se eu passar na prova, vou viajar.”



9

Podemos formalizá-la como A→B.

Agora vamos considerar todas as combinações entre verdadeiro e falso para as letras sentenciais A e B.

Caso 1: A é verdadeiro e B também o é. (linha 1 da tabela-verdade)

Situação: Passei na prova e viajei. Logo, a afirmação é verdadeira.

Caso 2: A é verdadeiro e B é falso. (linha 2 da tabela-verdade)

Situação: Passei na prova e não viajei. Logo, a afirmação é falsa, pois eu havia afirmado que, se passasse na prova, viajaria.

Caso 3: A é falso e B é verdadeiro. (linha 3 da tabela-verdade)

Situação: Não passei na prova e viajei. Logo, a afirmação é verdadeira, pois eu não afirmei que, se não passasse na prova, não iria viajar.

Caso 4: A é falso e B também o é. (linha 4 da tabela-verdade)

Situação: Não passei na prova e não viajei. Logo, a afirmação é verdadeira.

1.3.5 Tabela-verdade da equivalência A equivalência é a abreviatura para (A B) ∧ (B A). A equivalência A ↔B será verdadeira quando A e B

possuírem o mesmo valor-verdade, seja ele verdadeiro ou falso.

A B A→B B→A (A→B) ∧ (B→A)V V V V VV F F V FF V V F FF F V V V

Logo, a tabela-verdade para a equivalência é:

A B A↔BV V VV F FF V FF F V

Exercícios:



1

5. Construa a tabela-verdade para:

1. (A → Β) ↔ (Β → A)2. (A ∨ ~A) → (Β ⊥ ∼Β)3. (A → B) → B4. (~B → ~A) → B5. (A ∨ ~B) → ~(A ∨ B)6. ~(P → Q)7. (A ∧ ~A)

1.4 Classificação de Wffs Usando Tabelas-Verdade

Uma wff pode ser uma tautologia, contingência ou contradição. Tal classificação é definida de acordo com o resultado da tabela-verdade para a wff em questão.

Tautologia: a wff será uma tautologia quando todos os valores-verdade resultantes na tabela-verdade forem verdadeiros.

Contradição: a wff será uma contradição quando todos os valores-verdade resultantes na tabela-verdade forem falsos.

Contingência: a wff será uma contingência quando os valores-verdade resultantes na tabela-verdade variarem entre verdadeiro e falso.

Exercício: 6. Classifique as wffs do exercício anterior como tautologia, contradição ou contingência.

1.4 TABELAS-VERDADE PARA FORMAS DE ARGUMENTO

Uma forma de argumento é válida se, e somente se, todas as suas instâncias são válidas. Uma instância de uma forma é válida se é impossível que a sua conclusão seja falsa enquanto suas premissas são verdadeiras, ou seja, se não houver, na tabela-verdade, uma linha com conclusão falsa e todas premissas verdadeiras.

Se um argumento for válido, então sua conclusão poderá ser provada com a utilização das regras de dedução natural, que serão vistas nas páginas seguintes.

Exemplo 1:Seja a forma de argumento P∨Q, ~P |-- Q. Construa a tabela-verdade para essa forma de argumento e mostre se ela é válida ou inválida.

A tabela-verdade para essa forma será:

Col1 Col2 Col3 Col4 Col5P Q P ∨ Q ~P Q

Linha 3 V V V F VLinha 4 V F V F FLinha 5 F V V V VLinha 6 F F F V F

As colunas 3 e 4 da tabela-verdade contêm as premissas da forma de argumento, ou teorema. A coluna 5 contém a conclusão.



1

Nas linhas 3 e 5, as premissas são todas verdadeiras. São apenas nestas linhas que deve ser analisada a conclusão. Em ambas as linhas a conclusão também é verdadeira. Logo, a forma de argumento é válida.

Exemplo 2:Seja a forma de argumento P→Q, Q |-- P. Construa a tabela-verdade para essa forma de argumento e mostre se ela é válida ou inválida.

A tabela-verdade para essa forma será:

Col1 Col2 Col3 Col4 Col5P Q P → Q Q P

Linha 3 V V V V VLinha 4 V F F F VLinha 5 F V V V FLinha 6 F F V F F

As colunas 3 e 4 da tabela-verdade contêm as premissas da forma de argumento, ou teorema. A coluna 5 contém a conclusão.

Nas linhas 3 e 5, as premissas são todas verdadeiras. São apenas nestas linhas que deve ser analisada a conclusão. Na linha 3 a conclusão é verdadeira, porém, na linha 5, a conclusão é falsa. Como ocorreu um caso em que as premissas foram verdadeiras e a conclusão falsa (linha 5), a forma de argumento é inválida.

Exercício:

7. Formalize os enunciados abaixo e utilize a tabela verdade para afirmar se eles são válidos ou não.

a) Se eu passar na prova, irei viajar. Não passei na prova, logo, não viajei.

b) Vou passar de ano se, e somente se, eu estudar e não viajar. Não estudei. Viajei. Logo, passei na prova.

1.5 APLICAÇÕES DE TABELAS-VERDADE E FORMALIZAÇÃO

As tabelas-verdade podem auxiliar na resolução de problemas em que se deseja saber a verdade ou não. Os

exercícios abaixo mostram uma aplicação de tabelas-verdade e formalização.

Exercícios:

8. Três estudantes declararam o seguinte:

Paulo: Eu não fiz o teste, mas, se Rogério o fez, Sérgio também fez.

Rogério: Eu fiz o teste, mas um de meus colegas não fez.

Sérgio: Se Rogério fez o teste, eu também o fiz.

Formalize estas três declarações na linguagem lógica proposicional utilizando o vocabulário abaixo. A seguir, monte a tabela-verdade das proposições e utilize-a para responder as questões a, b e c:

P: Paulo fez o teste.

R: Rogério fez o teste.

S: Sérgio fez o teste.

a) Se todos estão dizendo a verdade, quem fez o teste?



1

b) Se todos estão mentindo, quem fez o teste?

c) Se todos fizeram o teste, quem está dizendo a verdade e quem está mentindo?

9.Três estudantes declararam o seguinte:

Pedro: Eu entreguei o trabalho, mas, se João não entregou, Maria também não entregou.

João: Se Pedro não entregou o trabalho, eu também não entreguei.

Maria: Eu não entreguei o trabalho, mas um de meus colegas entregou.

Formalize estas três declarações na linguagem lógica proposicional utilizando o vocabulário abaixo. A seguir, monte a tabela-verdade das proposições e utilize-a para responder as questões a, b e c:

P: Pedro entregou o trabalho.

J: João entregou o trabalho.

M: Maria entregou o trabalho.

d) Se todos estão dizendo a verdade, quem entregou o trabalho?

e) Se todos estão mentindo, quem entregou o trabalho?

f) Se todos entregaram o trabalho, quem está dizendo a verdade e quem está mentindo?



1

EXERCÍCIOS DE REVISÃO

1. Construa a tabela verdade das wff´s abaixo e classifique-as:

a) ~(P→ (A↔B))

b) (A∧(~B∨ (C↔~A))) → ~C

2. Considere os seguintes depoimentos:

Paulo: Eu não estudei lógica, mas se João estudou, então Maria não estudou.

João: Se um dos meus colegas não estudou lógica, então eu também não estudei.

Maria: Se Paulo e João estudaram lógica, então eu também estudei.

Formalize estas três declarações na linguagem lógica proposicional utilizando o vocabulário abaixo:

P: Pedro estudou lógica.

J: João estudou lógica.

Maria: Maria estudou lógica

Monte a tabela-verdade para responder e justificar as seguintes questões. Indique em que linha da tabela-verdade é

possível identificar as situações.

a) Se apenas Paulo estudou lógica, quem diz a verdade e quem está mentindo?

b) Se ninguém estudou lógica, quem está dizendo a verdade e quem está mentindo?

3. Três suspeitos declararam o seguinte:

Suspeito A: "Eu não participei do crime, mas um dos demais suspeitos participou. "

Suspeito B: "Se eu participei do crime, então o suspeito A participou e o suspeito B não participou. "

Suspeito C: "Eu participei do crime se, e somente se um dos outros dois suspeitos não participou. "

Formalize as declarações utilizando o vocabulário abaixo:

A = Suspeito A participou do crime.

B = Suspeito B participou do crime.

C = Suspeito C participou do crime

Construa a tabela verdade para as três declarações e utilize-a para responder as perguntas a seguir. Indique

qual(is) linha(s) da TV você utilizou para criar sua resposta.

a) Quem mente e quem diz a verdade se:



1

1. Todos participaram do crime?

2. Apenas o suspeito A participou do crime?

3. Apenas o suspeito B não participou do crime?

4. Ninguém participou do crime?

5. Apenas os suspeitos A e B participaram do crime?

b) Quem participou do crime e quem não participou se:

1. Todos dizem a verdade?

2. Todos mentem?

3. Apenas os suspeitos A e B dizem a verdade?

4. Apenas o suspeito B mente?

5. Apenas o suspeito A mente?

4. Formalize as formas de argumento abaixo:

a) Se está garoando ou nevando, então o céu não está claro. Não é o caso que o céu não está claro. Portanto, não é o

caso que está garoando ou nevando.

b) Se está chovendo, então há nuvens no céu. Não há nuvens no céu. Portanto, não está chovendo.

c) Se P é verdadeiro, então Q é verdadeiro. Portanto, se Q não é verdadeiro, então P também não deve ser.

d) Miau não é, ao mesmo tempo, um gato e um cachorro. Miau é um gato, logo, Miau não é um cachorro.

e) Se Miau é um gato e Cléo um peixinho, então Fido não é um cachorro. Ou Fido é um cachorro, ou Miau e Cléo

gostam de nadar. Miau é um gato se, e somente se, Cléo é um peixinho. Logo, se Miau é um gato, Miau gosta de

nadar.

f) Se Miau caça, ele apanha ratos. Se ele não dorme bastante, então ele caça. Se ele não apanha ratos, ele dorme

bastante. Logo, Miau apanha ratos.

g) Se Maria está doente, Pedro não vai à escola. Se Pedro está doente, Maria não vai à escola. Maria e Pedro vão à

escola. Logo, nem Maria nem Pedro estão doentes.

h) Se a lua gira em torno da terra e a terra gira em torno do sol, então Copérnico tinha razão. Se Copérnico tinha

razão, então Ptolomeu não tinha razão. A terra gira em torno do sol. Logo, se a lua gira em torno da terra, Ptolomeu

não tinha razão.

i) Se a lua gira em torno da terra, então a terra gira em torno do sol. Se a terra gira em torno do sol, então, se a lua gira

em torno da terra, ou Copérnico ou Ptolomeu tinham razão. Nem Copérnico nem Ptolomeu tinham razão. Logo, a

lua não gira em torno da terra.



1

j) Se meu cliente é culpado, então a faca estava na gaveta. Ou a faca não estava na gaveta ou Jason viu a faca. Se a

faca não estava lá no dia 10 de outubro, então segue que Jason não viu a faca. Além disso, se a faca estava lá em 10

de outubro, então a faca estava na gaveta e também o machado estava no celeiro. Mas todos nós sabemos que o

machado não estava no celeiro. Portanto, senhoras e senhores presentes no Júri, meu cliente é inocente.

k) Se eu percebo, então ou minha percepção é ilusória ou ela é verídica. Se a minha percepção é ilusória então eu

percebo alguma coisa e ainda assim eu não percebo um objeto material. Se eu percebo alguma coisa e ainda assim

eu não percebo um objeto material, então eu percebo uma sensação. Se a minha percepção é verídica então eu

percebo alguma coisa. Se a minha percepção é verídica e eu percebo um objeto material, então minha experiência

em percepção verídica sempre diferirá da minha experiência em percepção ilusória. Minha experiência em

percepção verídica nem sempre difere da minha experiência em percepção ilusória. Portanto, se eu percebo, então

eu percebo uma sensação e eu não percebo um objeto material.



1

CÁLCULO DE PREDICADOS

O cálculo de predicados combina conceitos do cálculo proposicional com conceitos de “todo” e “algum”.

10.1 QUANTIFICADORES E VARIÁVEIS

Quantificadores: indicam quantos objetos possuem uma propriedade. São frases como “para todo”, “para cada”, ou “para algum”, “existe um” , “para pelo menos um”.

Os quantificadores aparecem agora para suprir a necessidade de quantificar proposições.

10.1.1QUANTIFICADOR UNIVERSAL:

Representação: ∀Lê-se: “para todo”, “para cada”, “qualquer que seja”

Considere o enunciado: Todo S é P.

Usando a letra x para representar objetos individuais, podemos expressar o enunciado como “qualquer que seja x, se x é S, então x é P”.

O quantificador universal é o símbolo que representará o “qualquer que seja”. Assim, a representação do enunciado é:

Exemplo:

Todas as janelas são transparentes.Formalização: ∀x(Jx →Tx)

10.1.2QUANTIFICADOR EXISTENCIAL

Representação: ∃ Lê-se: “existe um”, “para pelo menos um”, “para algum”

Considere o enunciado: Algum S é P

Usando a letra x para representar objetos individuais, podemos expressar o enunciado como “para pelo menos um x, x é S e x é P”.

O quantificador existencial é o símbolo que representará o “para pelo menos um”. Assim, a representação do enunciado é:

Exemplo:Algumas as janelas são transparentes.Formalização: ∃x(Jx ∧Tx)

Exemplos:



1

∀x(Sx →Px)

∃x (Sx ∧ Px)

♠Dica! Normalmente, a implicação é o conectivo associado ao quantificador universal, e a

conjunção é o conectivo associado ao quantificador existencial!

Escreva wffs que expressem:

a) Todos os estudantes são inteligentes.∀x (Sx → Ix)Sx: x é estudanteIx: x é inteligente

b) Alguns estudantes inteligentes gostam de música.∃x (Sx ∧ Ix ∧ Mx ) )

c) Todos que gostam de música são estudantes cantores.∀x (Mx → (Sx ∧ Cx))M(x): x gosta de músicaS(x): x é estudanteC(x): x é cantor

Exercícios:11. Interpretando a letra “C” como a sentença “Está chovendo” e pelas letras “R”, “V”, “S” e “I” os predicados

“É uma rã”, “É verde”, “É saltitante”, “É iridescente”, formalize as seguintes sentenças:

a) Todas as rãs são verdes.

b) Nenhuma rã é verde.

c) Algumas rãs são verdes.

d) Algumas rãs não são verdes.

e) Toda coisa é uma rã.

f) Alguma coisa é uma rã.

g) Nem toda coisa é uma rã.

h) Nada é uma rã.

i) Existem rãs verdes.

j) Qualquer coisa ou é rã ou é iridescente.

k) Qualquer coisa é uma rã verde.

l) Está chovendo e algumas rãs estão saltitando.

m) Se está chovendo, então todas as rãs estão saltitando.

n) Algumas coisas são verdes e algumas não são.

o) Algumas coisas são verdes e iridescentes simultaneamente.

p) Ou qualquer coisa é uma rã ou nada é uma rã.

q) Qualquer coisa ou é uma rã ou não é uma rã.

r) Todas as rãs são rãs.

s) Somente rãs são verdes.

t) Não existem rãs iridescentes.

u) Todas as rãs verdes estão saltitando.

v) Todas as rãs verdes não estão saltitando.

w) Não é verdade que algumas rãs verdes estão saltitando.

x) Se nada é verde, então não existem rãs verdes.

y) Rãs verdes saltam se e somente se não está chovendo.



1

10.2 PREDICADOS E NOMES PRÓPRIOS

Nem todos enunciados contêm quantificadores. Os enunciados do tipo sujeito-predicado atribuem uma propriedade

a uma pessoa ou coisa.

As letras minúsculas (do início ao meio do alfabeto) podem ser interpretadas como nomes próprios para indivíduos,

enquanto as letras finais minúsculas do alfabeto representam variáveis (sempre associadas a quantificadores) e letras

maiúsculas do alfabeto representam letras nominais.

As wffs desse tipo são chamadas wffs predicativas, enquanto as demais são wffs proposicinais.

wff Proposicional: são as que contêm apenas símbolos proposicionais e conectivos lógicos (^, ∨, ~, →, ↔)

wff Predicativa: são as que contêm predicados e variáveis.

Uma wff proposicional sempre tem valor-verdade, enquanto uma predicativa pode não ter valor-verdade.

Wff Proposicional Wff PredicativaSeu valor-verdade depende dos valores-verdade atribuídos aos símbolos proposicionais

Seu valor-verdade (ou sua falta) depende da interpretação

Há apenas 2n linhas possíveis para wffs proposicionais Há um número infinito de interpretações possíveisUma tautologia é uma wff proposicional que é verdadeira em todas as linhas da tabela-verdade

O análogo à tautologia é a validade. Uma wff predicativa é válida se for verdadeira para qualquer interpretação possível. Pode-se provar que uma wff predicativa é inválida se encontrarmos uma única interpretação na qual a wff tenha valor-verdade falso ou não tenha valor-verdade.

Exemplos:

1. Bob ama Cátia

10.3 Formalização: Abc

2. Cátia ama Bob

10.4 Formalização: Acb

3. Cátia deu Lulu para Bob

10.5 Formalização: Dclb

EXERCÍCIOS:

12. Formalize as sentenças a seguir utilizando predicados e nomes próprios;

a) Cátia é mecânica.

b) Bob é mecânico.

c) Cátia e Bob são mecânicos.

d) Ou Cátia ou Bob são mecânicos.

e) Cátia é mecânica ou enfermeira.

f) Se Cátia é mecânica, então ela não é enfermeira.

g) Cátia é mais alta que Bob.



1

h) Bob ama Cátia.

i) Bob ama a si próprio.

j) Bob ama a qualquer pessoa.

k) Qualquer pessoa ama Bob.

l) Qualquer pessoa ama a si mesma.

m) Alguma pessoa ama a si mesma.

n) Existe alguém que Cátia não ama.

o) Existe alguém que tanto Bob quanto Cátia amam.

p) Existe alguém que Bob ama e alguém que Cátia ama.

q) Cátia deu alguma coisa para Bob.

r) Bob deu um anel para Cátia.

s) Todo mundo ama todo mundo.

t) Alguém ama alguém.

u) Existe alguém que ama todo mundo.

v) Todo mundo é amado por alguém.

w) Se Bob ama a si próprio, então ele ama alguma pessoa.

x) Se Bob não ama a si próprio, então ele ama alguém.

y) Para quaisquer três objetos, se o primeiro é mais alto que o segundo e o segundo é mais alto que o terceiro, então o

primeiro é mais alto que o terceiro.

13. Formalize as seguintes sentenças usando o vocabulário a seguir.

Nomes:

a – Al

b – Beth

f – fama

d – dinheiro

Predicados Unários:

F – é famoso

A – é ambicioso

H – é ser humano

Predicado binário:

G - ...gosta de...

Predicado ternário:

P - ...prefere...do que ...

a) Al e Beth gostam de dinheiro.

b) Nem Beth nem Al são famosos.

c) Al gosta de fama e de dinheiro.

d) Beth prefere fama do que dinheiro.



2

e) Al prefere Beth do que dinheiro e fama.

f) Beth prefere qualquer coisa do que Al.

g) Al prefere nada do que Beth.

h) Alguns humanos são ambiciosos e famosos.

i) Qualquer pessoa ambiciosa gosta de dinheiro.

j) Nem toda pessoa que gosta de dinheiro é ambiciosa.

k) Se Al e Beth são ambiciosos, então existe um ser humano ambicioso.

l) Beth gosta de qualquer ser humano.

m) Alguém não gosta de si mesmo.

n) Alguém não gosta de alguém.

o) Ninguém gosta de todo mundo.

p) Nenhum ser humano gosta de todo mundo.

q) Al gosta de todo ser humano que gosta dele.

r) Alguns famosos gostam de si próprios.

s) Todos famosos gostam de si próprios.

t) Nem todos gostam de todos que são famosos.

14. Formalize as seguintes sentenças, interpretando pela letra ‘C’ a sentença ‘está chovendo’ e pelas letras ‘U’,

‘B’, ‘F’ e ‘P’ os predicados ‘é urso’, ‘é branco’, ‘é feroz’ e ‘é polar’, respectivamente.

a) Todos os ursos são brancos.

b) Nenhum urso é branco.

c) Alguns ursos são brancos.

d) Alguns ursos não são brancos.

e) Toda coisa é um urso.

f) Alguma coisa é um urso.

g) Nem toda a coisa é um urso.

h) Nada é um urso.

i) Existem ursos brancos.

j) Qualquer coisa ou é urso ou é polar.

k) Qualquer coisa é um urso branco.

l) Está chovendo e alguns ursos estão ferozes.

m) Se está chovendo, então todos os ursos estão ferozes.

n) Algumas coisas são brancas e algumas não são.

o) Algumas coisas são brancas e polares simultaneamente.

p) Ou qualquer coisa é um urso ou nada é um urso.

q) Qualquer coisa é um urso ou não é um urso.

r) Todos os ursos são ursos.

s) Somente ursos são brancos.



2

t) Não existem ursos polares.

u) Todos os ursos estão ferozes.

v) Não é verdade que alguns ursos brancos estão ferozes.

w) Alguns ursos brancos não estão ferozes.

x) Se nada é branco, então não existem ursos brancos.

z) Ursos brancos são ferozes se e somente se não está chovendo.



2

EXERCÍCIOS DE REVISÃO

1. Formalize as sentenças a seguir na Lógica de Predicados utilizando o vocabulário indicado:

Cx = x é um Corvette

Px= x é um Porshe

Fx = x é uma Ferrari

Dxy = x é mais devagar que y

Ex = x é um romance de espionagem

Lx = x é longo

Mx = x é um romance policial

Bxy = x é melhor do que y

a) Nada é ao mesmo tempo um Corvette e uma Ferrari.

b) Alguns Porshes só andam mais devagar do que Ferraris.

c) Apenas Corvettes andam mais devagar que Porshes.

d) Todas as Ferraris andam mais devagar do que algum Corvette.

e) Alguns Porshes não andam mais devagar do que Corvette algum.

f) Se existe algum Corvette que anda mais devagar do que uma Ferrari, então todos os Corvetes andam mais devagar

que todas as Ferraris.

g) Todos os romances de espionagem são longos.

h) Nem todo romance policial é de espionagem.

i) Apenas romances policiais são longos.

j) Alguns romances de espionagem são policiais.

k) Romances de espionagem são melhores que romances policiais.

l) Alguns romances policiais são melhores do que todos os de espionagem.

m) Apenas romances de espionagem são melhores do que romances policiais.

2. Dê versões em português para as wff´s a seguir utilizando o vocabulário indicado:

Axy = x ama y

Bx = x é bonito

Vx = x é vistoso

Hx = x é um homem

Mx = x é uma mulher

j = João

c = Cátia

a) Vj ∧ Acj

b) ∀x (Mx→Vx)



2

c) ∃x( (Hx∧Vx) ∧ Acx)

d) ∀x(Mx ∧ (Bx→ Ajx) )

e) ∀x[Mx→ ∀y(Axy→ ( Hy ∧ Vy) ) ]

f) ∃x[ (Mx∧Bx) ∧ ∀y(Axy→ ( Vy ∧ Hy) ) ]

3. Formalize as sentenças a seguir no cálculo de predicados. Utilize o vocabulário abaixo:

D(x) -x é um dia J(x) - x é um juiz F(x) -x é um farmacêutico

S(x) -x está fazendo sol A(x) -x é um advogado M(x,y) - x admira y

C(x) -x está chovendo M(x) -x é uma mulher

a) Todos os dias está fazendo sol.

b) Alguns dias não está chovendo.

c) Todo dia que não está fazendo sol está chovendo.

d) Alguns dias está fazendo sol e chovendo.

e) Nenhum dia está fazendo sol e chovendo ao mesmo tempo.

f) É sempre um dia de sol apenas se for um dia chuvoso.

g) Nenhum dia faz sol.

h) Existem algumas mulheres advogadas que são farmacêuticas.

i) Nenhuma mulher é, ao mesmo tempo, advogada e farmacêutica.

j) Alguns advogados admiram apenas juízes.

k) Todos os juízes admiram apenas juízes.

l) Todas mulheres advogadas admiram algum juiz.

m) Algumas mulheres não admiram nenhum juiz.



2

SISTEMAS FORMAIS

O sistema formal que usa as wffs proposicionais é chamada de Lógica Proposicional, lógica de sentenças ou cálculo proposicional. O sistema formal que usa wffs predicativas é chamado lógica predicada ou cálculo predicado.

Certas wff's são aceitas como axiomas, os seja, são wff's que não precisam ser provados. Assim, um axioma deve ser uma wff cuja “verdade” seja evidente. Um axioma, então, deve ser uma tautologia, ou, se envolve predicados, uma wff válida.

Além dos axiomas, sistemas formais contêm regras de inferência, que são uma convenção que permite a uma nova wff ser inferida, ou deduzida, de uma ou duas outras wff's, ou seja, são regras capazes de gerar todas as formas de argumento válidas e que podem ser expressas na linguagem do cálculo proposicional.

Seqüência de Prova é uma seqüência de wff's na qual cada wff seja ou um axioma ou o resultado da aplicação de uma das regras de inferência às wff's anteriores. Um teorema é o último componente desta seqüência. A seqüência é a prova do teorema.

Em uma derivação ou prova, as regras de inferência geram as formas de argumento numa série de etapas simples e precisas de raciocínio, que é a derivação ou prova.

Seqüência de uma prova de teorema:

wff 1 (um axioma ou premissa)wff 2 (um axioma ou premissa)wff 3 (inferida da wff1 e da wff 2 por uma regra de inferência)wff 4 (um axioma ou premissa)wff 5 (inferida da wff 4 por uma regra de inferência)wff 6 (inferida da wff 3 e wff 5 por uma regra de inferência)

wff 6 é o teorema

10.6 REGRAS NÃO HIPOTÉTICAS DE INFERÊNCIA

Existem dez regras básicas de inferência: duas (uma de introdução e uma de eliminação) para cada um dos cinco operadores lógicos ( ^, ∨, →, ↔, e ~ ). A regra de eliminação para um operador é usada para inferir a partir de premissas nas quais ele é o operador principal. A regra de introdução para um operador é usada para derivar conclusões nas quais ele é o operador principal.

As regras não hipotéticas de derivação são as seguintes:

a. Modus Ponens (MP)b. Eliminação da Negação (E~)c. Introdução da Conjunção (I∧)d. Eliminação da Conjunção (E∧)e. Introdução da Disjunção (I∨)f. Eliminação da Disjunção (E∨)g. Introdução do Bicondicional (I↔)h. Eliminação do Bicondicional (E↔)

10.6.1 MODUS PONENS (MP)

É a regra de eliminação para o condicional (se, então, implica). É a regra usada para inferir de premissas que contêm o operador condicional. MP pode ser aplicada a condicionais cujos antecedente e conseqüente são wffs compostas.



2

Exemplos:

C, S → Α, C → S |-- A

1. C ----------------------------premissa2. S → A --------------------- premissa3. C → S --------------------- premissa4. S --------------------------- 1, 3 MP5. A --------------------------- 2, 4 MP

~P → (Q → R), ~P, Q |-- R

1. ~P → (Q → R) --------------------- premissa2. ~P ------------------------------------ premissa3. Q ------------------------------------- premissa4. (Q → R) --------------------------- 1, 2 MP5. R ------------------------------------- 3, 4 MP

10.6.2 ELIMINAÇÃO DA NEGAÇÃO: (E~)

Permite inferir premissas que são negações de negações.

Exemplo:

~P → ~~Q , ~~~P |−− Q



2

Regra: de um condicional e seu antecedente, podemos inferir seu conseqüente.

A → BA

MP B

Regra: De uma wff da forma ~~A podemos inferir A

~~A E~

A

A → B , A |-- B1. A → B ---------------------------- premissa2. A ---------------------------------- premissa3. B ---------------------------------- 1, 2 MP

~~ A |-- A

1.~~ A -------------------------- premissa

2. A ----------------------------- E~

1. ~P → ~~Q ---------------------------- premissa2. ~~~P ----------------------------------- premissa3. ~P -------------------------------------- 2 E~4. ~~Q ------------------------------------ 1, 3 MP5. Q --------------------------------------- 4 E~

10.6.3 INTRODUÇÃO DA CONJUNÇÃO (I∧)

10.6.4 ELIMINAÇÃO DA CONJUNÇÃO (E∧)

Exemplos:

P |-- P ∧ P



2

De quaisquer wffs A e B, podemos inferir a conjunção Α ∧ B.

A B

I∧ A ∧ B

A , B |-- A ∧ B

1. A ---------------------------- premissa

2. B ---------------------------- premissa

3. A ∧ B ---------------------- 1, 2 I∧

De uma conjunção podemos inferir qualquer um de seus conjuntos.

A∧B_______E∧A

A∧B______ E∧ B

A ∧ B |-- A

1. A∧ B ---------------------------- premissa

2. A --------------------------------- E∧

A ∧ B |-- A

1. A∧ B ---------------------------- premissa

2. B --------------------------------- E∧

1. P ----------------------------------------- premissa2. P ∧ P ----------------------------------- 1, 1 I ∧

P → (Q ∧ R), P |-- P ∧ Q

1. P → (Q ∧ R) ---------------------------- premissa2. P ------------------------------------------ premissa3. (Q ∧ R) ---------------------------------- 1, 2 MP4 Q ------------------------------------------ 4 E ∧5. P ∧ Q ------------------------------------ 2, 4 I ∧

P ∧ Q |-- Q ∧ P

1. P ∧ Q ------------------------------------ premissa2. P ----------------------------------------- 1 E ∧ 3. Q ----------------------------------------- 1 E ∧4. Q ∧ P ------------------------------------ 2, 3 I ∧

(P ∧ Q) → (R ∧ S), ~~P, Q |-- S

1. (P ∧ Q) → (R ∧ S) ---------------------- premissa2. ~~P ---------------------------------------- premissa3. Q ------------------------------------------ premissa4. P ------------------------------------------- 2 E~5. P ∧ Q ------------------------------------- 3, 4 I ∧6. (R ∧ S) ----------------------------------- 1, 5 MP7. S ------------------------------------------ 6 E ∧

10.6.5 INTRODUÇÃO DA DISJUNÇÃO ( I ∨)

Exemplos:

P |--- (P ∨ Q) ∧ (P ∨ R)



2

De uma wff A, podemos inferir a disjunção de A com qualquer wff (A pode ser o primeiro ou o segundo disjunto dessa disjunção)

A |-- A ∨ B

1. A ---------------------------- premissa

2. A ∨ B ----------------------- I ∨

A |-- B ∨ A

1. A ---------------------------- premissa

2. B ∨ A ----------------------- I ∨

A

_____ Ι∨A∨Β

A

_______ I∨B∨Α

A ∨ BA → CB → C---------- E∨ C

1. P ---------------------------------- premissa2. P ∨ Q ---------------------------- 1 I∨3. P ∨ R ---------------------------- 1 I∨4. (P ∨ Q) ∧ (P ∨ R) ------------- 2, 3 I ∧

P, ~~(P → Q) |--- Q ∨ ∼Q

1. P -------------------------------- premissa2. ~~(P → Q) -------------------- premissa3. P → Q ------------------------- 2 E ~~4. Q ------------------------------- 1, 3 MP5. Q ∨ ∼Q ------------------------ 4 I ∨

P, ~~(P → Q) |--- (R ∧ S) ∨ Q1. P -------------------------------- premissa2. ~~(P → Q) -------------------- premissa3. (P → Q) ----------------------- 2 E ~4. Q ------------------------------- 1, 3 MP5. (R ∧ S) ∨ Q ------------------ 4 I ∨

10.6.6 ELIMINAÇÃO DA DISJUNÇÃO (E∨)

Considere as seguintes afirmações:

Irei ao cinema ou ao teatro.Se eu for ao cinema, será divertido.Seu eu for ao teatro, será divertido.

Qual é a conclusão a que se pode chegar a partir das três afirmações acima?Que, independente do que eu faça, ir ao teatro ou ao cinema, será divertido.

Formalizando as sentenças, temos:

C ∨ T , C → D , T → D |-- D

que é a regra de eliminação da disjunção!Portanto, para que a disjunção possa ser eliminada, é necessário que existirem uma disjunção e duas implicações com conseqüentes idênticos. A conclusão sempre será o conseqüente presente nas duas implicações.

Exemplos:



2

De wffs da forma A∨B, A→C , B→C, podemos inferir a wff C.

A∨B, A→C, B→C |-- C

1. A ∨ B ----------------------- premissa

2. A → C ---------------------- premissa

3. B → C ---------------------- premissa

4. C ----------------------------- 1, 2, 3 E∨

S ∨ D, S → F, D → F |--- F

1. S ∨ D -------------------------------- premissa2. S → F ------------------------------- premissa3. D → F------------------------------- premissa4. F -------------------------------------1, 2, 3 E∨

(P ∨ Q) ∧ (P ∨ R), P → S, Q → S, P → Τ, R → Τ |--- S ∧ T

1. (P ∨ Q) ∧ (P ∨ R) --------------------------------- premissa2. P → S ------------------------------------------------ premissa3. Q → S ----------------------------------------------- premissa4. P → Τ ----------------------------------------------- premissa5. R → Τ ----------------------------------------------- premissa6. P ∨ R ------------------------------------------------ 1 E ∧7. T ---------------------------------------------------- 4, 5, 6 E ∨8. P ∨ Q ------------------------------------------------ 1 E ∨9. S ------------------------------------------------------ 2, 3, 8 E ∨10. S ∧ T ---------------------------------------------- 7, 9 I ∧

10.6.7 Introdução do Bicondicional (I↔):

Exemplo:

P → Q, (P→Q) → (Q→P) |-- P ↔ Q



3

De quaisquer wffs de formas (Α → Β) e (B → Α), podemos inferir Α ↔ Β

A → BB → A---------- I↔A ↔ B

A → BB → A---------- I↔B ↔ A

A→B, B→A |-- A ↔ B

1. A → B ---------------------- premissa

2. B → A ---------------------- premissa

3. A ↔ B ---------------------- 1, 2 I↔

A→B, B→A |-- B ↔ A

1. A → B ---------------------- premissa

2. B → A ---------------------- premissa

3. B ↔ A ---------------------- 1, 2 I↔

1. P → Q ------------------------- premissa2. (P→Q) → (Q→P) ----------- premissa3. Q→P -------------------------- 1, 2 MP4. P ↔ Q ------------------- 1, 3↔

10.6.8 ELIMINAÇÃO DO BICONDICIONAL (E↔)

Exemplos:

F ↔ (S ∨ D), S |--- F

1. F ↔ (S ∨ D) -------------------- premissa2. S ---------------------------------- premissa3. S ∨ D → F ---------------------- 1 E ↔4. S ∨ D ----------------------------- 2 I ∨5. F ---------------------------------- 3, 4 MP

P ↔ Q |--- Q ↔ P

1. P ↔ Q ---------------------------- premissa2. P → Q ---------------------------- 1 E ↔3. Q → P ---------------------------- 1 E ↔4. Q ↔ P ---------------------------- 2, 3 I ↔

EXERCÍCIOS

16. Utilizando as regras básicas de derivação, prove as seguintes formas de argumento:

1. P ↔Q , Q↔R , Q |-- (R∧P) ∨ (P↔R)

2. (P∨T) ↔ Q , (P∨T) ↔ S , Q∨ S |-- P∨T

3. P↔Q , R∧~~Q |-- P∧R



3

De quaisquer wffs da forma A ↔ Β, podemos inferir A → Β ou Β →Α .A ↔ B --------- E↔A → B

A ↔ B--------- E↔B → A

A ↔ B |-- A→B

1. A ↔ B -------------------- premissa

2. A → B ---------------------- 1 E↔

A ↔ B |-- B→A

1. A ↔ B -------------------- premissa

2. B → A ---------------------- 1 E↔

4. F↔ (S∨ D) , S |-- F∧ (S∨ D)

5. ~~(P → (S∧R) ) , S∨ P , S → (S∧R) |-- (R∨ P) ∧ (S∧R)

6. P → (Q → (~R∧Q) ) , P, S, S → (~R∧Q) |-- ~R∧S

7. S, (S∨T) → ~~~Q |-- (S∧~Q) ∨ (S∧Q)

8. (S∧T) ↔ (P∧R) , S, P∧T |-- R∧T

9. P↔(~T∨S) , R ↔ (~T∨S) , T ↔ (~T∧P) , T |-- ~T∨S

10. R → (R∧T) , R→ S , S→ (R∧T) , R , S→ (R∨T) |-- T

11. (Q∧S)→ (P∧ (Q∧R) ) , (R ∧ (Q∧S) )→P , R , Q∧ S |-- (P∧(Q∧R)) ∧ (P∧(Q∧S))

12. (P∧R)→ (Q ∧~~S) , ~~P , P→ (S∧R) |-- S∧(Q∧R)

13. P , S , S→ (~R∧Q) |-- ~R∧S

15. (S∧T)→ (P∧R) , S , P∧T |-- R∧T

16. P |-- ( (P∨ Q)∨ R) ∧ ( (Q∨P) ∨ S)

10.7 REGRAS HIPOTÉTICAS DE INFERÊNCIA



3

As regras apresentadas a seguir envolvem a utilização do raciocínio hipotético, que é baseado em hipóteses, ou seja, em uma suposição feita “em consideração ao argumento” com o objetivo de mostrar que uma conclusão particular segue daquela suposição.

10.7.1 SUBPROVA

Ao escrever uma hipótese, estamos iniciando uma subprova, que será uma prova menor dentro da prova principal. Para representar a subprova graficamente, usamos a tabulação mais à direita.

Depois de encerrada a subprova, não é permitido utilizar regras que estejam nela. Apenas podem ser usadas regras que estejam na mesma tabulação que a atual ou mais à esquerda dela.

É possível construir subprovas dentro de subprovas já iniciadas. Para encerrá-las, é necessário fazer na ordem inversa em que foram iniciadas. Uma prova não estará completa caso seja encerrada com alguma subprova ainda não encerrada. A linha vertical ao lado da subprova indica que ela está encerrada.

O esquema de uma subprova pode ser representado da seguinte maneira:

No esquema acima, as linhas 3, 4 e 5 não poderão ser utilizadas nas linhas 6 e 7, pois estão encerradas juntamente com a subprova. Dentro da subprova, ou seja, nas linhas 3, 4 e 5 é possível utilizar as linhas 1 e 2, que estão mais à esquerda.

Os esquemas a seguir representam outras situações de construção de subprovas.



3

XXX ----------------------------------------------- regra 1

XXX ---------------------------------------------- regra 2

YYY ------------------------- hipótese (p/ regra A)

XXX ----------------------------------------- regra 3

XXXX --------------------------------------- regra 4

ZZZZ --------------------------------------------- regra A

XXX ----------------------------------------------- regra 5

XXX ----------------------------------------- regra 1

XXX ----------------------------------------- regra 2

YYY ------------------------ hipótese (p/ regra A)

XXX ------------------------------------ regra 3

RRRR -------------- hipótese (p/ regra B)

XXXX ----------------------------- regra 4

SSSS ------------------------------- regra B

XXX ------------------------------------- regra 5

9. TTTT ------------------------------------------- regra A



3

Resumindo.. as condições para realização de uma subprova são as seguintes:

1. Cada hipótese introduz numa prova o início de uma nova linha vertical;

2. Nenhuma ocorrência de uma fórmula à direita de uma linha vertical pode ser citada em qualquer regra aplicada depois que terminar a linha vertical;

3. Se duas ou mais hipóteses são vigentes simultaneamente, então a ordem na qual elas são descartadas deve ser a ordem inversa na qual elas são introduzidas;

4. Uma prova não está completa até que as hipóteses sejam descartadas.

10.7.2 PROVA DO CONDICIONAL (PC)

Nesta regra, supomos algo como hipótese. A hipótese não necessita ser extraída de lugar algum, ela pode ser gerada de acordo com que se necessita no desenvolvimento da subprova.

Exemplos:



3

XXX --------------------------------------------- regra 1

XXX --------------------------------------------- regra 2

YYY ------------------------ hipótese (p/ regra A)

XXX ---------------------------------------- regra 3

XXX -------------------------------------------- regra A

RRRR ------------------ hipótese (p/ regra B)

XXXX ------------------------------------- regra 4

SSSS --------------------------------------- regra 5

9. TTTT --------------------------------------------- regra B

Dada uma derivação de uma wff B a partir de uma hipótese A, podemos descartar a hipótese e inferir Α → Β

A ∧ B |-- A → B

1. A ∧ B ------------------------------------- premissa

2. A ------------------------- hipótese (p/ PC)

3. B -------------------------------------- 1 E∧

4. A → B------------------------------------- 2 – 3 PC

I, (I ∧ C) → ~S, ~S → ~A |-- C → ~A

1. I ----------------------------------------- premissa2. (I ∧ C) → ~S -------------------------- premissa3. ~S → ~A ------------------------------- premissa

4. C ----------------------------- hipótese (p/ PC)5. I ∧ C ------------------------- 1, 4 I ∧6. ~S ----------------------------- 2, 5 MP7. ~A ---------------------------- 3, 6 MP

8. C → ~A -------------------------------- 4 – 7 PC

P ∨ Q |-- Q ∨ P

1. P ∨ Q --------------------------------------- premissa2. P ---------------------------------- hipótese (p/ PC) 3. Q ∨ P ----------------------------- 2 I ∨

4. P → (Q ∨ P) -------------------------------- 2 – 3 PC5. Q ---------------------------------- hipótese (p/ PC)6. Q ∨ P ----------------------------- 5 I ∨

6. Q → (Q ∨ P) -------------------------------- 5 – 6 PC7. Q ∨ P ---------------------------------------- 1, 4 , 6 E ∨

10.7.3 REDUÇÃO AO ABSURDO (RAA)

É a regra de introdução da negação.

Para provar uma conclusão negada por RAA, colocamos como hipótese a conclusão sem o sinal de negação e daí derivamos uma contradição. Isso mostra que a hipótese é falsa. De onde segue que a conclusão da negação é verdadeira.



3

Dada uma derivação de uma contradição a partir de uma hipótese A podemos descartar a hipótese e inferir ~A

~B, B |-- A

~B ------------------------------------- premissa

B --------------------------------------- premissa

A ------------------------- hipótese (p/ RAA)

B ∧ ~B ---------------------------- 1 E∧

~A --------------------------------------- 2 – 3 RAA

Exemplo:

P → Q, ~Q |-- ~P

1. P → Q ---------------------------- premissa2. ~Q -------------------------------- premissa

3. P ----------------------- hipótese (p/ RAA)4. Q ----------------------- 1, 3 MP5. Q ∧ ~Q ---------------- 2, 4 I ∧

6. ~P --------------------------------- 3 – 5 RAA

Exercícios Resolvidos

a) ~(~P ^ ~Q) , ~P |--- Q

1. ~(~P ^ Q) --------------------------------- premissa2. ~P ----------------------------------------- premissa

3. ~Q ------------------------------ hipótese (p/RAA)4. ~P ∧ ~Q ------------------------ 2, 3 I ∧5. (~P ∧ ~Q) ∧ ~(~P ∧ ~Q) ----- 1, 4 I ∧

6. ~~Q ---------------------------------------- 3 – 5 RAA7. Q ------------------------------------------- 6 E ~

b) P → Q |−− ∼P∨ Q1. P → Q ------------------------------------------ premissa

2. ~(~P ∨ Q)---------------------------- hipótese (p/RAA)3. P --------------------------- hipótese (p/RAA)4. Q ---------------------------1, 3 MP5. ~P ∨ Q -------------------- 4 I ∨6. (~P ∨ Q) ∧ ~(~P ∨ Q) --- 2, 5 I ∧

7. ~P ------------------------------------- 3 – 6 RAA8. ~P ∨ Q -------------------------------- 7 I ∨9. (~P ∨ Q) ∧ ~(~P ∨ Q) --------------- 2 , 8 I ∧

10. ~~(~P ∨ Q) ------------------------------------- 2 – 9 RAA11. ~P ∨ Q ------------------------------------------ 10 E ~

c) ~(P ∧ Q) |--- ~P ∨ ∼Q1. ~(P ∧ Q) ---------------------------------------------- premissa

2. ~(~P ∨ ~Q) -------------------------------- hipótese (p/RAA)3. ~ P ------------------------------- hipótese (p/RAA)4. ~P ∨ ~Q ------------------------- 3 I ∨5. (~P ∨ ~Q) ∧ ~(~P ∨ ~Q) ----- 2, 4 I∧

6. ~~P ----------------------------------------- 3 – 5 RAA7. P -------------------------------------------- 6 E ~

8. ~Q ------------------------------- hipótese (p/RAA)9. ~P ∨ ~Q ------------------------- 8 I ∨10. (~P ∨ ~Q) ∧ ~(~P ∨ ~Q) ---- 2, 9 I ∧

11. ~~Q --------------------------------------- 8 – 10 RAA12. Q ------------------------------------------ 11 E ~13. P ∧ Q ------------------------------------- 7, 12 I∧14. (P ∧ Q) ∧ ~(P ∧ Q) --------------------- 1, 13 I∧

15. ~~(~P ∨ ~Q) --------------------------------------- 2 – 14 RAA16. ~P ∨ ~Q --------------------------------------------- 15 E ~



3

d) |--- P → P

1. P ------------------------------ hipótese (p/PC)2. P → P ----------------------------------- 1 PC

e) |--- P → (Q → (P ∧ Q))

1.P ------------------------------- hipótese (p/PC) 2. Q ------------------------------ hipótese (p/PC)

3. P ∧ Q---------------- 1, 2 I ∧4. Q → (P∧ Q) ------------------ 2 – 3 PC

5. P → (Q → (P ∧ Q)) -------------------- 1 – 4 PC

f) (P ∧ Q) |--- P → Q

1. P ∧ Q ----------------------------------- premissa2. P ------------------------------ hipótese (p/PC)3 Q ------------------------------ 1 E ∧

4. P → Q ---------------------------------- 2 – 3 PC

g) (P ∧ Q) ∨ (P ∧ R) |--- P ∧ (Q ∨ R)

1. (P ∧ Q) ∨ (P ∧ R) ------------------------------------ premissa2. P ∧ Q --------------------------------------- hipótese (p/PC)3. P --------------------------------------------- 2 E ∧4. Q -------------------------------------------- 2 E ∧ 5. Q ∨ R -------------------------------------- 4 I ∨6 P∧ (Q ∨ R)--------------------------------- 3, 5 I∧

7. (P ∧ Q) → (P ∧ ( Q ∨ R))-------------------------- 2 – 6 PC8. P ∧ R --------------------------------------- hipótese (p/PC)9. P -------------------------------------------- 8 E ∧10. R------------------------------------------- 8 E ∧11. Q ∨ R ------------------------------------- 10 I ∨12. P ∧ (Q ∨ R) ----------------------------- 9, 11 I∧

13. (P ∧ R) → (P ∧ (Q ∨ R) ------------------------- 8 – 12 PC14. P ∧ (Q ∨ R) ---------------------------------------- 1, 7, 13 E ∨

17. Utilizando as regras básicas (hipotéticas ou não), prove as seguintes formas de argumento:

1. A ↔C , A |-- (A∧B) → (A∧C)

2. ~~(B→C), A |-- (A∧B) → (A∧C)

3. A ∧ C, B ∧ C |-- A↔C

4. ~~(A∧C) |-- C ∧ (B→ C)



3

5. A∧B |-- ~A → (B→ A)

6. A |-- (A→ B) → (B∨ C)

7. ~P → P |-– P

8. ~P∨ ~Q |-- ~(P∧Q)

9. A ∧ ~B |-- ~(A→ B)

10. ~B |-- ( A → ~(A∧B) ) ∧ ~B

11. ~C→ C, A→ C |-- A→ (~B∧ ~A)

12. |-- P→ ((P→ Q) → Q)

13. |-- P ∨ ~P

14. |-- (P→ Q) → ~(P ∧~Q)



3

10.8 ESTRATÉGIAS PARA PROVA

Se a condicional for um(a) Então faça

Fórmula Atômica Se nenhuma estratégia é imediata, coloca-se como hipótese a negação da conclusão para RAA. Se isso for bem sucedido, então a conclusão pode ser obtidadepois de RAA, por E ~

Fórmula Negada Coloca-se como hipótese a conclusão, sem o símbolo da negação, para RAA. Se resultar uma contradição, a

conclusão pode ser obtida por RAA

Conjunção Prove cada um dos conjuntos, separadamente, e então faça a conjunção deles com I ^

Disjunção Se uma premissa disjuntiva está presente, tenta-se provaros condicionais necessários para obter a conclusão porE∨. Χασο χοντρ⟨ριο, χολοχα−σε χοµο ηιπ⌠τεσε α νεγαοda conclusão e tenta-se RAA. Algumas vezes, uma conclusão disjuntiva pode ser provada diretamente,provando-se um de seus disjuntos e aplicando-se I ∨

Condicional Coloca-se como hipótese o seu antecedente e deriva-se oseu conseqüente por PC

Bicondicional Use PC, 2 vezes, para provar os dois condicionaisnecessários para obter a conclusão por I ↔



4

10.9 REGRAS DERIVADAS E DE EQUIVALÊNCIA

2.9.1 REGRAS DERIVADAS

As regras derivadas permitem outras soluções para demonstrações formais. São elas:

MODUS TOLLENS (MT)

De wffs de formas φ → ψ e ~ψ, infere-se ~φ.

Exemplo:

A→ B, ~B |-- ~A

1. A→ B----------------------- premissa2. ~B -------------------------- premissa3. ~A -------------------------- 1, 2 MT

SILOGISMO HIPOTÉTICO (SH)

De wffs de formas φ → ψ e ψ → χ, infere-se φ → χ.

Exemplo:

A→ B, B→ C |-- A→ C

1. A→ B ------------------------------- premissa2. B→ C ------------------------------- premissa3. A→ C ------------------------------- 1, 2 SH

ABSORÇÃO (ABS)

De uma wff da forma φ → ψ, infere-se φ → (φ ∧ ψ).

Exemplo:

A→ B |-- A→ (A ∧ B)

1. A→ B ---------------------------- premissa2. A→ (A ∧ B) --------------------- 1 ABS

DILEMA CONSTRUTIVO (DC)

De wffs de forma φ ∨ ψ, φ → χ e ψ → ω, infere-se χ ∨ ϖ.

Exemplo:



4

A∨ B , A→ C, B→ D |-- C∨ D

1. A∨ B --------------------------- premissa2. A→ C -------------------------- premissa3. B→ D -------------------------- premissa

4. C∨ D --------------------- 1, 2, 3 DC

REPETIÇÃO (RE)

De qualquer wff φ, infere-se φ.

Exemplo:

A∨ B |-- C→ (A∨ B)

1. A∨ B ----------------------------- premissa2. C ---------------------------- hipótese (p/ PC)3. A∨ B ----------------------- RE

4. C→ (A∨ B) -------------------- 2-3 PC

CONTRADIÇÃO (CONTRAD)

De wffs de formas φ e ~φ, infere-se qualquer wff.

Exemplo:

A, ~A |-- (A∨ B) → C

1. A ----------------------- premissa2. ~A --------------------- premissa3. (A∨ B) → C --------- 1, 2 CONTRAD

SILOGISMO DISJUNTIVO (SD)

De wffs de formas φ ∨ ψ e ∼φ , infere-se ψ.

Exemplo:

1. A∨ B -------------------- premissa2. ~A ----------------------- premissa3. B ------------------------- 1, 2 SD

INTRODUÇÃO DE TEOREMA (IT)

Qualquer instância substitutiva de um teorema pode ser introduzida em qualquer linha de uma prova.

INTRODUÇÃO DE EQUIVALÊNCIA



4

Se φ e ψ são interderiváveis e φ é uma subwff de alguma wff χ, de χ infere-se o resultado da substituição de uma ou mais ocorrências de φ em χ por ψ. (a abreviação usada depende da equivalência utilizada)

2.9.2 REGRAS DE EQUIVALÊNCIA

As regras de equivalência permitem que wff´s inteiras ou partes de wff´s sejam substituídas por formas equivalentes, definidas nas regras a seguir. Os exemplos representam parte de uma prova qualquer.

DE MORGAN (DM)

~(P ^ Q) ↔ (∼P ∨ ~Q)~(P ∨ Q) ↔ (~P ^ ~Q)

Exemplo:1.............2............3. A→ (~B ∧ ~C) --------------------- premissa4. A→ ~(B∨ C) ----------------------- 3 DM

COMUTAÇÃO (COM)

(P ∨ Q) ↔ (Q ∨ P) (P ^ Q) ↔ (Q ^ P)

Exemplo:1.............2............3. (~B ∧ ~C) ↔ D --------------------- premissa4. (~C ∧ ~B) ↔ D ----------------------- 3 COM

ASSOCIAÇÃO (ASSOC)

(P ∨ (Q ∨ R)) ↔ ((P ∨ Q) ∨ R) (P ^ (Q ^ R)) ∨ ((P ^ Q) ^ R)

Exemplo:1.............2............3. A ∧ (~B ∧ ~C) --------------------- premissa4. (A ∧ ~B) ∧ ~C ----------------------- 3 ASSOC

DISTRIBUIÇÃO (DIST)

(P ^ (Q ∨ R)) ↔ ((P ^ Q) ∨ (P ^ R)) (P ∨ (Q ^ R)) ↔ ((P ∨ Q) ^ (P ∨ R))

Exemplo:1.............2............3. A ∨ (~B ∧ ~C) --------------------- premissa4. (A ∨ ~B) ∧ (A ∨ ~C) ------------- 3 DIST

DUPLA NEGAÇÃO (DN)



4

P ↔ ~~P

Exemplos:1.............2............3. A→ (~~B ∧ C) -------------------- premissa4. A→ (B ∧ C) ----------------------- 3 DN

1.............2............3. A→ (B ∧ C) --------------------- premissa4. A→ ~~ (B∧ C) ------------------ 3 DN

TRANSPOSIÇÃO (TRANS)

(P → Q) ↔ (~Q → ~P)

Exemplo:1.............2............3. A→ (B ∧ C) --------------------- premissa4. ~(B ∧ C)→ ~A ------------------ 3 TRANS

IMPLICAÇÃO MATERIAL (IM)

(P → Q) ↔ (~P ∨ Q)

Exemplo:1.............2............3. A→ (~B ∧ ~C) --------------------- premissa4. A→ ~(B∨ C) ----------------------- 3 DM

EXPORTAÇÃO (EXP)

((P ^ Q) → R) ↔ (P → (Q → R))

Exemplo:1.............2............3. A → (~B → ~C) --------------------- premissa4. (A ∧ ~B) → ~C) ---------------------- 3 EXP

TAUTOLOGIA (TAUT)

P ↔ (P ^ P)P ↔ (P ∨ P)

Exemplo:1.............2............3. A→ C ----------------------- premissa4. A→ (C∨ C) ---------------- 3 TAUTEXERCÍCIOS



4

18. Prove as formas de argumento abaixo utilizando regras básicas, derivadas e/ou de equivalência do Cálculo

de Dedução Natural.

a) P ↔ Q, Q ↔ R |-- P ↔ R

b) P ↔ Q |-- ~P ↔ ~Q

c) ~P ∨ Q -- ~(P ∧ ~Q)

d) ~P ∧ (~Q ∧ ~R) |-- ~(Q ∨ P)

e) P ∨ (~Q ∧ R), ~P. R→Q |-- ~R

f) (P∧ Q) ↔ ~~(P∧ Q) |-- (P∧ Q) ↔ ~( P→ ~Q)

g) ~P→ Q, R→ S, ~P ∨ R, ~Q |-- S

h) P→ (Q→ ~R), R |-- ~P ∨ ~Q

i) ~P→ P |-- P

j) P ∨ Q, ~Q |-- P

k) (P∨ Q) ∧ (P∨ R) |-- ~P → (P∨ R)

l) (~P ∨ Q) ∨ R, (Q ∨ R) → S |-- P → S

m) P → (Q → ~R), R |-- ~P ∨ ~Q

n) (G ∨ N) → ~C |-- ~~C → ~(G ∨ N)

o) P |-- Q → P

p) P ∨ Q, ~P |-- Q

q) ~P → Q, (P∧ Q) → R, ~R |-- ~P

19. Formalize as sentenças abaixo e prove-as utilizando regras básicas e derivadas do Cálculo de

Dedução Natural.

a) Não entendemos psicologia ou, se a entendemos, então não é preciso estudar a história. Não é preciso estudar

história. Embora, assim, alguns pontos fiquem obscuros, ou entendemos psicologia. Não é o caso que não

precisemos estudar história se compreendemos psicologia. Acresce que, se não estudamos história, ignoramos

aspectos vitais da cultura e, além disso, voltamos aos filósofos do passado ou deixamos alguns pontos obscuros.

b) Se meu filho tirar boas notas, ele é esforçado, se trabalhou muitas horas. Se ele não for descuidado, ele não deixará

de usar suas capacidades, se aprender bastante. Meu filho aprenderá bastante apenas se obtiver boas notas e não for

descuidado. Eu sei que ele aprenderá bastante. Segue-se que ele é esforçado ou não deixará de usar suas

capacidades.

c) Condição necessária para que uma flor atraia insetos é que seja vistosa. Ser vistosa é condição suficiente para que

seja agradável aos olhos. A flor atrai insetos ou é feia (não ambos). Não se dá que uma flor seja feia e não

perfumada. Não sucede que seja perfumada e sem valor comercial. Segue-se que, se a flor não é agradável aos

olhos, tem valor comercial.



4

d) A menos que estudemos matemática e não no percamos em futilidades, não faremos o trabalho. Se formos ao baile

ou não fizermos o trabalho, então não se dará que tenhamos lucro e não vejamos o projeto concluído. Ou há lucro,

ou estudamos matemática (não ambos). Iremos ao baile se, e somente se, fizermos o trabalho. Mas não iremos ao

baile. Portanto, não se dá que nos percamos em futilidades e não vejamos o projeto concluído.

e) Esta planta não é hermafrodita. Se não o é, tem androceu ou gineceu. Logo, ou não tem gineceu ou não tem

androceu.

20. Considere a forma de argumento abaixo:

A → (B → C), D → (A ∧ E), (G ∧ E) → (B ∨ F), G ∧ D, F → H |-- H ∨ C

a) Construa um vocabulário e traduzia a forma de argumento para a Língua Portuguesa:

A = E =

B = F =

C = G =

D = H =

b) Prove a forma de argumento utilizando as regras básicas, derivadas e de equivalência do cálculo de

dedução natural.

10.10 REGRAS DE INFERÊNCIA PARA QUANTIFICADORES

10.10.1 ELIMINAÇÃO UNIVERSAL (EU)

Exemplos:

∀x (Hx → Mx), Hs |--- Ms

1. ∀x (Hx → Μx) ------------------------------ premissa2. Hs---------------------------------------------- premissa3. Hs → Ms------------------------------------- 1 EU4. Ms --------------------------------------------- 2, 3 MP

∀x (Px → Cx), ∀x (Cx → Vx) |--- ∀x (Px → Vx)



4

De uma wff quantificada universalmente, ∀βφ, podemos inferir uma wff, da forma φ α/β , a qual resulta substituindo-se cada ocorrência da variável β em φ por uma letra nominal α.

∀x Hx |--- Ha

1. ∀x Hx ------------------------------ premissa2. Ha----------------------------------- 1 EU

1. ∀x (Px → Cx) ----------------------------------- premissa2. ∀x (Cx → Vx) ----------------------------------- premissa3. Pa → Ca ----------------------------------------- 1 EU4. Ca → Va ----------------------------------------- 2 EU5. Pa → Va ----------------------------------------- 3, 4 SH6. ∀x (Px → Vx) ---------------------------------- 5 IU

10.10.2 INTRODUÇÃO DO UNIVERSAL (IU)

A regra de introdução do universal possui algumas restrições, descritas a seguir.

10.10.2.1 RESTRIÇÕES DE IU

Restrição 1: A letra nominal α não pode ocorrer em qualquer premissa. A seguinte derivação ignora essa restrição e consequentemente, é inválida:

1. Pa ----------------------------- premissa2. ∀x Px ------------------------ 1 IU (incorreto)

Restrição 2: A letra nominal α não deve ocorrer em qualquer hipótese vigente numa linha em que φ ocorre (uma hipótese é vigente numa linha se ela foi introduzida antes dessa linha e ainda não foi descartada naquela linha, em outras palavras, ela é vigente se a linha vertical começando com a hipótese estende-se para baixo até aquela linha). Isso impede o tipo de invalidade exibida acima.

1. ∀x (Px → Cx) ------------------------ premissa2. Pa → Ca ------------------------------ 1 EU

3. Pa -------------------------- hipótese (P/ PC)4. Ca -------------------------- 2, 3 MP5. ∀x Cx --------------------- 4 IU (incorreto)

6. Pa → ∀x Cx ------------------------- 3 – 5 PC

Restrição 3: φ β/α é o resultado de substituir todas as ocorrências de α em φ por uma variável β. A ênfase aqui, está na palavra “todas”. Esta cláusula previne o seguinte tipo de erro:

1. ∀x Lxx ------------------------------ premissa2. Laa ---------------------------------- 1 EU

3. ∀z Lza--------------------------------- 2 IU (incorreto)

Exemplos de derivações válidas



4

Para uma wff φ contendo uma letra nominal α que não ocorre em qualquer uma das premissas ou em

qualquer hipótese vigente na linha em que φ ocorre, podemos inferir uma wff da forma ∀ β φ β/α, onde

φ β/α é o resultado de se substituir todas as ocorrências de α em φ por uma variável β que não ocorra em φ.→ no exemplo anterior, na aplicação de IU na linha 6, a wff φ é 'Pa → Va', a letra nominal α

é 'a', a variável β é 'x' e a fórmula φ β/α é '(Px → Vx)'

∀x (Fx → (Gx ∨ Hx), ∀x ~Gx |--- ∀x Fx → ∀x Ηx

1. ∀x (Fx → (Gx ∨ Hx)------------------------------- premissa2. ∀x ~Gx ---------------------------------------------- premissa3. Fa → (Ga ∨ Ha) ----------------------------------- 1 EU4. ~Ga -------------------------------------------------- 2 EU

5. ∀x Fx ------------------------------------- hipótese (p/PC)6. Fa ----------------------------------------- 5 EU7. Ga → Ha -------------------------------- 3, 6 MP8. Ha ---------------------------------------- 4, 7 SD9. ∀x Hx ----------------------------------- 8 IU

10. ∀x Fx → ∀x Hx --------------------------------- 5 – 9 PC

10.10.3 INTRODUÇÃO EXISTENCIAL (IE)

Exemplo:

Dada a premissa “Fa ∧ Ga” (a suposição de que o indivíduo “a” tem a propriedade F e G, podemos inferir “∃x (Fx ^ Gx)”.

Prova:1. Fa ∧ Ga ------------------------ premissa2. ∃x (Fx ∧ Gx) ----------------- 1 IE

em que....α é 'a'β é 'x'

φ β/α é '(Fx ∧ Gx)

Em contraste com o casa para IU a variável β não precisa substituir todas as ocorrências de α em φ; é preciso substituir somente uma, ou mais. Assim, as duas demonstrações a seguir estarão corretas:

1. Fa ∧ Ga -------------------------------- premissa2. ∃x (Fx ∧ Ga) -------------------------- 1 IE

1. Fa ∧ Ga -------------------------------- premissa2. ∃x (Fx ∧ Gx) -------------------------- 1 IE

10.10.4 ELIMINAÇÃO DO EXISTENCIAL (EE)



4

∃x(Fx∧Gx) |--∃x Fx

1. ∃x (Fx ∧ Gx) ------------------------ premissa2. Fa ∧ Ga ------------------ hipótese (p/EE)3. Fa ------------------------ 2 E ∧

4. ∃x Fx ----------------------- 3 IE5. ∃x Fx ------------------------------- 1, 2 – 4 EE

Dada uma wff φ contendo uma letra nominal α, podemos inferir uma wff da forma ∃β φ β/α, onde φ β/α é o resultado de se substituir uma ou mais ocorrências de α em φ por uma variável β, que não ocorra em φ.

Dada uma wff quantificada existencialmente ∃ β φ e uma derivação de alguma conclusão ψ de uma hipótese da forma

φ α/β (o resultado de se substituir cada ocorrência da variável β em φ por uma letra nominal α que não ocorra em φ),

podemos descartar φ α/β e reafirmar ψ. Restrição: A letra nominal α não pode ocorrer em ψ, nem em qualquer premissa, nem em qualquer hipótese vigente na linha em que EE é aplicada.

A regra de eliminação do existencial, assim como a regra de introdução do universal, possui restrições.

10.10.4.1 RESTRIÇÕES EE

Restrição 1: A letra nominal α não pode ocorrer em φ.

1. ∀x ∃y F(y,x) --------------------------------premissa2. ∃y F(y,a) ----------------------------------- 1 EU não pode!

3. F(a,a) ---------------------------- hipótese (p/EE)4. ∃x F(x,x) ------------------------ 3 IE

5. ∃x F(x,x) ---------------------------------- 2, 3 – 4 EE (incorreto)

Restrição 2: A letra nominal α não deve ocorrer em ψ(a conclusão de uma derivação hipotética.

1. ∃x H(x,x) ------------------------------------ premissa2. H(a,a) ----------------------------- hipótese (p/EE) erro!3. ∃x H(a,x) ------------------------- 2 IE

4. ∃x H(a,x) ------------------------------------ 1, 2 – 3 EE (incorreto)

Restrição 3: α não pode ocorrer em qualquer premissa.

1. ∃x Gx ------------------------------------ premissa2. Fa ---------------------------------------- premissa erro!

3. Ga ---------------------------- hipótese (p/EE)4. Fa ∧ Ga --------------------- 2, 3 I ∧5. ∃x (Fx ∧ Gx) --------------- 4 IE

6. ∃x (Fx ∧ Gx) ---------------------------- 1, 3 – 5 EE (incorreto)

Restrição 4: α não pode ocorrer em qualquer hipótese vigente na linha em que EE é aplicada.

1. ∃x Gx --------------------------------------- premissa2. Fa -------------------------------- hipótese (p/PC)

3. Ga --------------------- hipótese (p/EE)4. Fa ∧ Ga --------------- 2, 3 I ∧ 5. ∃x (Fx ∧ Gx) --------- 4 IE

6. ∃x (Fx ∧ Gx) ------------------- 1, 3 – 5 EE (incorreto)7. Fa → ∃x (Fx ∧ Gx) --------------------- 2 – 6 PC



4

1.6 ÁRVORES DE REFUTAÇÃO

As Árvores de Refutação são utilizadas para provar a validade de uma forma de argumento. Dessa forma,

fechamos aqui o “ciclo” das lógicas Proposicional e de Predicados: formalizamos formas de argumento, verificamos a

sua validade usando árvores de refutação (isso significa verificar que os argumentos permitem que se chegue àquela

conclusão) e então, provamos as formas de argumento usando sistemas formais – Dedução Natural.

A seguir veremos como construir uma Árvore de Refutação.

– dada uma lista de wff´s, uma Árvore de Refutação é uma busca exaustiva de caminhos nos quais todas as wff´s da

lista podem ser vedadeiras

– constrói-se uma lista consistindo em suas premissas e na negação de sua conclusão

– a busca é executada desmembrando as wff´s da lista em letras sentenciais ou suas negações. Se encontrarmos

alguma atribuição de verdade e falsidade para letras sentenciais que torne verdadeiras todas as wff´s da lista, então

as premissas da forma são verdadeiras enquanto sua conclusão é falsa. Assim, refuta-se a forma de agumento, pois

ela é inválida. Se na busca não surgir atribuição de verdade e falsidade para letras sentenciais que torne verdadeiras

todas as wff´s da lista, então a refutação falha, pois a forma é válida.

Ramo Aberto: é um ramo que não termina com X

Ramo Fechado: é um ramo que termina com X

Exemplo 1 passo-a-passo:

Construir a árvore de refutação para mostrar que a forma P ∧ Q |-- ~~P

Passo 1. formar uma lista com as premissas e a negação da conclusão.

P ∧ Q

~~~P

Passo 2. a premissa é verdadeira se e somente se P e Q forem verdadeiros, portanto, pode-se substituir P ∧ Q

por essas duas letras sentencias

v P ∧ Q

~~~P

P

Q

Passo 3. ~~~P é V se e somente se ~P é V, logo, marca-se ~~~P e substitui-se ele por ~P

v P ∧ Q

v ~~~P

P

Q

~P



5

Passo 4. desmembramos a lista original de fómulas num lista de letras sentenciais ou negações de letras

sentenciais, os quais devem ser verdadeiras se todos os membros da lista original são verdadeiras. Mas, entre essas

letras sentenciais e suas negações, temos P e ~P, as quais não podem ser ambas V. Logo, é impossível que todas as

fórmulas desta últimal listagem sejam verdadeiras. Expressa-se isso escrevendo X no final da lista. (ou seja, quando

encontrarmos uma contradição, fechamos um ramo com um X)

v P ∧ Q

v ~~~P

P

Q

~P

X

Assim a árvore de refutação está completa. A busca de uma refutação de uma forma de argumento falhou, daí

essa forma é válida. Ou seja, a forma será válida quando todos os ramos da árvore forem “encerrados” com um X. Caso

contrário, a forma será inválida.


Construir uma árvore de refutação para mostrar que a forma P ∨ Q, ~P |-- Q é válida.

1. Lista de premissas e conclusão negada

P ∨ Q

~P

~Q

2. Como ~P e ~Q são negações de letras sentenciais, elas não podem ser analisadas além disso. Mas, P ∨ Q é

V se e somente se P ou Q for V. Para representar isso, bifurca-se a árvore

P ∨ Q

~P

~Q

P Q

3. As três fórmulas da lista inicial podem se verdadeiras se e somente se todas as fórmulas de um dos ramos

puderem ser V. Mas o primeiro ramo contém P e ~P, e o segundo ramo contém Q e ~Q. Como, dessa forma, nem todas

as fórmulas em qualquer um dos ramos podem ser V, termina-se os ramos com X.

P ∨ Q

~P

~Q

P Q

X X



5

A árvore de refutação falhou nos dois ramos (ou seja, os dois ramos foram encerrados com X), portanto o

argumento é válido. Se a árvore não falhar em todos os ramos (ou seja, se algum ramo não for encerrado com X), a

forma de agumento será inválida. Traduzindo: com as premissas da forma de argumento não permitem que seja possível

chegar àquela conclusão.

Para que seja possível desmembrar cada wff da árvore, é necessário utilizar regras que permitam que tal

desmembramento seja realizado. Tais regras são apresentadas a seguir e deverão ser indicadas na árvore quando

utilizadas, confome exemplos.

NEGAÇÃO (~) : se um ramo aberto contém uma wff não marcada da forma ~~ φ, marca-se ~~ φ e escreve-

se φ no final de cada ramo aberto que contém ~~ φ marcada

CONJUNÇÃO (∧): se um ramo aberto contém uma wff não marcada da forma φ ∧ ϕ , marca-se φ ∧ ϕ e

escreve-se φ e ϕ no final de cada ramo aberto que contém φ ∧ ϕ marcada

DISJUNÇÃO (∨): se um ramo aberto contém uma wff não marcada da forma φ ∨ ϕ , marca-se φ ∨ ϕ e

bifurca-se cada ramo aberto que contém φ ∨ ϕ marcado. No final do primeiro ramo escreve-se φ e no final do

segundo ramo escreve-se ϕ

CONDICIONAL (→): se um ramo aberto contém uma wff não marcada da forma φ → ϕ , marca-se φ → ϕ e

bifurca-se o final de cada ramo aberto que contém φ → ϕ marcado. No final do primeiro ramo escreve-se ~φ

e no final do segundo ramo escreve-se ϕ

BICONDICIONAL (↔): se um ramo aberto contém uma wff não marcada da forma φ ↔ ϕ , marca-se φ ↔ ϕ

e bifurca-se o final de cada ramo aberto que contém φ ↔ ϕ marcado. No final do primeiro ramo escreve-se φ

e ϕ , e no final do segundo ramo escreve-se ~φ e ~ϕ

CONJUNÇÃO NEGADA (~∧): se um ramo aberto contém uma wff não marcada da forma ~(φ ∧ ϕ) , marca-

se ~(φ ∧ ϕ) e bifurca-se o final de cada ramo aberto que contém ~(φ ∧ ϕ) marcado. No final do primeiro ramo

escreve-se ~φ, e no final do segundo ramo escreve-se ~ϕ

DISJUNÇÃO NEGADA (~∨): se um ramo aberto contém uma wff não marcada da forma ~(φ ∨ ϕ), marca-se

~(φ ∨ ϕ) e escreve-se ~φ e ~ϕ no final de cada ramo aberto que contém ~(φ ∨ ϕ)

CONDICIONAL NEGADO (~→): se um ramo aberto contém uma wff não marcada da forma ~(φ → ϕ),

marca-se ~(φ → ϕ) e escreve-se φ e ~ϕ no final de cada ramo aberto que contém ~(φ → ϕ) marcada.



5

BICONDICIONAL NEGADO (~↔): se um ramo aberto contém uma wff não marcada da forma ~(φ ↔ ϕ) ,

marca-se ~(φ ↔ ϕ) e bifurca-se o final de cada ramo aberto que contém ~(φ ↔ ϕ) marcado. No final do

primeiro ramo escreve-se φ e ∼ϕ, e no final do segundo ramo escreve-se ~φ e ϕ



5

ÁRVORES DE REFUTAÇÃO

As Árvores de Refutação são utilizadas para provar a validade de uma forma de argumento. Dessa

forma, fechamos aqui o “ciclo” das lógicas Proposicional e de Predicados: formalizamos formas de

argumento, verificamos a sua validade usando árvores de refutação (isso significa verificar que os

argumentos permitem que se chegue àquela conclusão) e então, provamos as formas de argumento usando

sistemas formais – Dedução Natural.

A seguir veremos como construir uma Árvore de Refutação.

– dada uma lista de wff´s, uma Árvore de Refutação é uma busca exaustiva de caminhos nos quais todas

as wff´s da lista podem ser vedadeiras

– constrói-se uma lista consistindo em suas premissas e na negação de sua conclusão

– a busca é executada desmembrando as wff´s da lista em letras sentenciais ou suas negações. Se

encontrarmos alguma atribuição de verdade e falsidade para letras sentenciais que torne verdadeiras

todas as wff´s da lista, então as premissas da forma são verdadeiras enquanto sua conclusão é falsa.

Assim, refuta-se a forma de agumento, pois ela é inválida. Se na busca não surgir atribuição de verdade

e falsidade para letras sentenciais que torne verdadeiras todas as wff´s da lista, então a refutação falha,

pois a forma é válida.

Ramo Aberto: é um ramo que não termina com X

Ramo Fechado: é um ramo que termina com X


Construir a árvore de refutação para mostrar que a forma P ∧ Q |-- ~~P

Passo 1. formar uma lista com as premissas e a negação da conclusão.

P ∧ Q

~~~P

Passo 2. a premissa é verdadeira se e somente se P e Q forem verdadeiros, portanto, pode-se

substituir P ∧ Q por essas duas letras sentencias

v P ∧ Q

~~~P

P

Q

Passo 3. ~~~P é V se e somente se ~P é V, logo, marca-se ~~~P e substitui-se ele por ~P

v P ∧ Q

v ~~~P

P



5

Q

~P

Passo 4. desmembramos a lista original de fómulas num lista de letras sentenciais ou negações de

letras sentenciais, os quais devem ser verdadeiras se todos os membros da lista original são verdadeiras.

Mas, entre essas letras sentenciais e suas negações, temos P e ~P, as quais não podem ser ambas V.

Logo, é impossível que todas as fórmulas desta últimal listagem sejam verdadeiras. Expressa-se isso

escrevendo X no final da lista. (ou seja, quando encontrarmos uma contradição, fechamos um ramo com um

X)

v P ∧ Q

v ~~~P

P

Q

~P

X

Assim a árvore de refutação está completa. A busca de uma refutação de uma forma de argumento

falhou, daí essa forma é válida. Ou seja, a forma será válida quando todos os ramos da árvore forem

“encerrados” com um X. Caso contrário, a forma será inválida.


Construir uma árvore de refutação para mostrar que a forma P ∨ Q, ~P |-- Q é válida.

1. Lista de premissas e conclusão negada

P ∨ Q

~P

~Q

2. Como ~P e ~Q são negações de letras sentenciais, elas não podem ser analisadas além disso.

Mas, P ∨ Q é V se e somente se P ou Q for V. Para representar isso, bifurca-se a árvore

P ∨ Q

~P

~Q

P Q



5

3. As três fórmulas da lista inicial podem se verdadeiras se e somente se todas as fórmulas de um

dos ramos puderem ser V. Mas o primeiro ramo contém P e ~P, e o segundo ramo contém Q e ~Q. Como,

dessa forma, nem todas as fórmulas em qualquer um dos ramos podem ser V, termina-se os ramos com X.

P ∨ Q

~P

~Q

P Q

X X

A árvore de refutação falhou nos dois ramos (ou seja, os dois ramos foram encerrados com X),

portanto o argumento é válido. Se a árvore não falhar em todos os ramos (ou seja, se algum ramo não for

encerrado com X), a forma de agumento será inválida. Traduzindo: com as premissas da forma de

argumento não permitem que seja possível chegar àquela conclusão.

Para que seja possível desmembrar cada wff da árvore, é necessário utilizar regras que permitam

que tal desmembramento seja realizado. Tais regras são apresentadas a seguir e deverão ser indicadas na

árvore quando utilizadas, confome exemplos.

NEGAÇÃO (~) : se um ramo aberto contém uma wff não marcada da forma ~~ φ, marca-se ~~ φ e escreve-

se φ no final de cada ramo aberto que contém ~~ φ marcada

CONJUNÇÃO (∧): se um ramo aberto contém uma wff não marcada da forma φ ∧ ϕ , marca-se φ ∧ ϕ e

escreve-se φ e ϕ no final de cada ramo aberto que contém φ ∧ ϕ marcada

DISJUNÇÃO (∨): se um ramo aberto contém uma wff não marcada da forma φ ∨ ϕ , marca-se φ ∨ ϕ e

bifurca-se cada ramo aberto que contém φ ∨ ϕ marcado. No final do primeiro ramo escreve-se φ e no final do

segundo ramo escreve-se ϕ

CONDICIONAL (→): se um ramo aberto contém uma wff não marcada da forma φ → ϕ , marca-se φ → ϕ e

bifurca-se o final de cada ramo aberto que contém φ → ϕ marcado. No final do primeiro ramo escreve-se ~φ

e no final do segundo ramo escreve-se ϕ

BICONDICIONAL (↔): se um ramo aberto contém uma wff não marcada da forma φ ↔ ϕ , marca-se φ ↔ ϕ

e bifurca-se o final de cada ramo aberto que contém φ ↔ ϕ marcado. No final do primeiro ramo escreve-se φ

e ϕ , e no final do segundo ramo escreve-se ~φ e ~ϕ

CONJUNÇÃO NEGADA (~∧): se um ramo aberto contém uma wff não marcada da forma ~(φ ∧ ϕ) , marca-

se ~(φ ∧ ϕ) e bifurca-se o final de cada ramo aberto que contém ~(φ ∧ ϕ) marcado. No final do primeiro ramo

escreve-se ~φ, e no final do segundo ramo escreve-se ~ϕ



5

DISJUNÇÃO NEGADA (~∨): se um ramo aberto contém uma wff não marcada da forma ~(φ ∨ ϕ), marca-se

~(φ ∨ ϕ) e escreve-se ~φ e ~ϕ no final de cada ramo aberto que contém ~(φ ∨ ϕ)

CONDICIONAL NEGADO (~→): se um ramo aberto contém uma wff não marcada da forma ~(φ → ϕ),

marca-se ~(φ → ϕ) e escreve-se φ e ~ϕ no final de cada ramo aberto que contém ~(φ → ϕ) marcada.

BICONDICIONAL NEGADO (~↔): se um ramo aberto contém uma wff não marcada da forma ~(φ ↔ ϕ) ,

marca-se ~(φ ↔ ϕ) e bifurca-se o final de cada ramo aberto que contém ~(φ ↔ ϕ) marcado. No final do

primeiro ramo escreve-se φ e ∼ϕ, e no final do segundo ramo escreve-se ~φ e ϕ

ÁRVORES DE REFUTAÇÃO PARA QUANTIFICADORES

Determinarão a validade ou invalidade de argumentos para o Cálculo de Predicados.

QUANTIFICAÇÃO UNIVERSAL (∀): se uma wff da forma ∀βφ aparece em um ramo aberto, e se α é uma

letra nominal que ocorre em uma wff desse ramo, então escrevemos φ α/β no final de cada ramo. Se

nenhuma wff contendo uma letra nominal aparece no ramo, então escolhemos uma letra nominal α e

escrevemos φ α/β no final do ramo. Em cada caso, não marcamos ∀βφ

QUANTIFICAÇÃO UNIVERSAL NEGADA (~∀): se uma wff não marcada da forma ~∀βφ aparece em um

ramo aberto, marca-se ela e escreve-se ∃β~φ no final de cada ramo aberto que contém a wff marcada

recentemente.

QUANTIFICAÇÃO EXISTENCIAL NEGADA (~∃): se uma wff não marcada da forma ~∃βφ aparece em um

ramo aberto, marca-se ela e escreve-se ∀β∼φ no final de cada ramo aberto que contém a wff marcada

recentemente.

QUANTIFICAÇÃO EXISTENCIAL (∃): se uma wff não marcada da forma ∃βφ aparece em um ramo aberto,

marca-se ela. Escolhe-se então uma letra nominal α que ainda não apareceu naquele ramo e escreve-se

φ α/β no final de cada ramo aberto contendo a wff recentemente marcada.

Exemplo:



5

∃x(Fx ∧ Gx) |−− ∃xFx ∧ ∃xGx

∃x(Fx ∧ Gx)

∼(∃xFx ∧ ∃xGx)

Fa ∧ Ga 1 ∃

Fa 3 ∧

Ga 3 ∧

∼ ∃xFx 2~∧ ~∃xGx 2~∧

∀x~Fx 6~∃ ∀x~Gx 6~∃

∼Fa 7∀ ∼Ga 7∀

X 4, 8 ~ X 5, 8 ~



5

ANEXO 1

REGRAS BÁSICAS

Redução ao absurdo (RAA) Exibida uma derivação de uma contradição a partir deuma hipótese φ, descarta-se a hipótese e infere-se ~φ.

Eliminação da negação (~E) De uma wff da forma ~~φ, infere-se φ.

Prova condicional (PC) Exibida uma derivação de uma wff ψ a partir de umahipótese φ, descarta-se a hipótese e infere-se ψ → φ .

Modus ponens (MP) De uma condicional e seu antecedente, infere-se o seuconseqüente.

Introdução da conjunção (I ∧) De quaisquer wffs φ e ψ, infere-se a conjunção φ ^ ψ.

Eliminação da conjunção (E ∧) De uma conjunção infere-se cada um de seusconjunctos.

Introdução da disjunção (I ∨) De uma wff φ, infere-se a disjunção de φ com qualquer wff.

Eliminação da disjunção (E ∨) De wffs de formas φ ∨ ψ, φ → χ e ψ → χ, infere-se χ.

Introdução do bicondicional (I ↔) De wffs de formas φ → ψ e ψ → φ, infere-se φ ↔ ψ.

Eliminação do bicondicional (E ↔) De wff da forma φ ↔ ψ, infere-se φ → ψ ou ψ → φ.

REGRAS DE EQUIVALÊNCIA

~(P ^ Q) ↔ (∼P ∨ ~Q) Lei de De Morgan (DM)~(P ∨ Q) ↔ (~P ^ ~Q) Lei de De Morgan (DM)(P ∨ Q) ↔ (Q ∨ P) Comutação (COM)(P ^ Q) ↔ (Q ^ P) Comutação (COM)(P ∨ (Q ∨ R)) ↔ ((P ∨ Q) ∨ R) Associação (ASSOC)(P ^ (Q ^ R)) ∨ ((P ^ Q) ^ R) Associação (ASSOC)(P ^ (Q ∨ R)) ↔ ((P ^ Q) ∨ (P ^ R)) Distribuição (DIST)(P ∨ (Q ^ R)) ↔ ((P ∨ Q) ^ (P ∨ R)) Distribuição (DIST)P ↔ ~~P Dupla Negação (DN)(P → Q) ↔ (~Q → ~P) Transposição (TRANS)(P → Q) ↔ (~P ∨ Q) Implicação Material (IM)((P ^ Q) → R) ↔ (P → (Q → R)) Exportação (EXP)P ↔ (P ^ P) Tautologia (TAUT)P ↔ (P ∨ P) Tautologia (TAUT)



5

REGRAS DERIVADAS

Modus tollens (MT) De wffs de formas φ → ψ e ~ψ, infere-se ~φ.

Silogismo hipotético (SH) De wffs de formas φ → ψ e ψ → χ, infere-se φ → χ.

Absorção (ABS) De uma wff da forma φ → ψ, infere-se φ → (φ ^ ψ).

Dilema construtivo (DC) De wffs de forma φ ∨ ψ, φ → χ e ψ → ω, infere-seχ ∨ ϖ.

Repetição (RE) De qualquer wff φ, infere-se φ.

Contradição (CONTRAD) De wffs de formas φ e ~φ, infere-se qualquer wff.

Silogismo disjuntivo (SD) De wffs de formas φ ∨ ψ e ∼φ , infere-se ψ.

Introdução de teorema (IT) Qualquer instância substitutiva de um teorema pode ser introduzida em qualquer linha de uma prova.

Introdução de Equivalência Se φ e ψ são interderiváveis e φ é uma subwff de (a abreviação usada depende alguma wff χ, de χ infere-se o resultado da substituição da equivalência utilizada) de uma ou mais ocorrências de φ em χ por ψ.



6

Documents

Material de Apoio - Lógica para Computação