Apostila Lógica I Geral para cursos de TI

Prévia do material em texto

�
Lógica Proposicional e da Lógica de Predicados�
SUMÁRIO
Apresentação
Capítulo 1 – Lógica Proposicional
Capítulo 2 – Dedução na Lógica Proposicional Capítulo 3 – Sentenças Abertas
Capítulo 4 – Quantificadores
Capítulo 5 – A Lógica de Predicados
Apêndices
Referências
Sobre os autores
Inform ações técnicas
�
APRESENTAÇÃO
Este liv ro-texto foi escrito para possibilitar aos alunos dos cursos de graduação na área de Com putação (Ciência da Com putação, Sistem as de Inform ação, Análise de Desenv olv im ento de Sistem as, Engenharia da Com putação, dentre outros) o aprendizado dos conceitos da Lógica Proposicional e da Lógica de Predicados.
Os tópicos do liv ro foram definidos para serem abordados em um a disciplina oferecida em um sem estre. Essa lim itação é im portante, pois existe na literatura um a gam a enorm e de outras lógicas. As duas lógicas abordadas neste texto serv em com o base para v árias outras disciplinas da Com putação.
Para reforçar os conceitos apresentados em cada capítulo, o liv ro contém no final um a seção com questões com entadas em diferentes nív eis de aprendizado.
im portante salientar que div ersos liv ros cobrem os tópicos abordados neste texto. Dentre eles, dev em os destacar os liv ros de Nolt
	(1 991 ),
	Gersting (2002),
	Mortari (2001 ), Hein (2004) e Alencar
	(1 999)
	que serv iram de
	base para o desenv olv im ento do texto
	apresentado neste m aterial.
	
O autor
�
CAPÍTULO 1
LÓGICA PROPOSICIONAL
N este capítu l o são apresentadas definições precisas sobre o qu e são proposiçõe s, fórm u l as e tau tol ogias qu e nos perm itirão definir u m a l ingu agem form al para a l ógica das proposições, ou seja, nos perm itirão criar u m a Lógica Proposicional.
1.1 Proposições e operadores lógicos
Proposição lógica
Intuitiv am ente, um a proposição lógica (ou apenas um a proposição) é um a frase ou sentença da Língua Portuguesa (ou de qualquer outro idiom a) que pode assum ir apenas um de dois v alores-v erdade: ou a frase é verdadeira (ela diz um a v erdade) ou ela é falsa (diz um a falsidade).
Observações:
Proposições são bastante com uns na linguagem natural, porque, por exem plo, todas as afirm ações são naturalm ente proposições.
Existem , entretanto, v ários exem plos de frases que não se encaixam na definição de proposição: com andos e solicitações, por exem plo, não são exatam ente proposições - quando um a ordem é dada (“feche a porta!”) ou um a solicitação feita (“por fav or, m e passe o prato”), não há necessariam ente um v alor - v erdade por trás destas frases.
A linguagem natural tam bém perm ite escrev er sentenças cujo significado não pode ser logicam ente determ inado (são os fam osos paradoxos). Por exem plo, a sentença, aparentem ente inocente, “Esta sentença é falsa” não é (nem pode ser) nem v erdadeira nem falsa (pense um pouco).
As proposições são usualm ente sim bolizadas (representadas) por letras m aiúsculas do início do alfabeto: A, B, C, … Os v alores lógicos das proposições são representados de form a resum ida usando V para
�
v erdadeiro e F para falso.
As proposições podem ser sim ples ou com postas. As proposições com postas são form adas de proposições sim ples conectadas atrav és de operadores (ou conetivos) lógicos. Estes operadores ou conetiv os representam as seguintes operações lógicas, que serão descritas m ais adiante:
Conjunção
Disjunção
Negação
Im plicação (ou condicional)
Bi-im plicação (ou bicondicional)
Conjunção de proposições
conetiv o “ e” é a form a m ais utilizada de se form arem proposições com postas atrav és da conjunção lógica de proposições.
Este conetiv o é usado, por exem plo, em sentenças com o “gatos são m am íferos e canários são av es”, “3 < 5 e 2 + 3 = 5” etc. A conjunção tam bém pode ser representada por preposições com o “m as”, “tam bém ” e sim ilares.
O sím bolo ∧ é usado para representar form alm ente a conjunção lógica. Caso A e B sejam proposições, então a fórm ula A ∧ B representa a conjunção lógica das proposições A e B. Essa fórm ula é lida sim plesm ente com o "A e B".
Exercício 1.1
Agora responda as seguintes questões:
Se A é v erdadeira e B v erdadeira, que v alor v ocê atribuiria a A
B?
Se A é v erdadeira e B falsa, que v alor v ocê atribuiria a A ∧ B?
Se A é falsa e B v erdadeira, que v alor v ocê atribuiria a A ∧ B?
Se A e B são falsas, que v alor v ocê atribuiria a A ∧ B?
Construa um a tabela resum indo o resultado das questões (a) até (d). Use V para v erdadeiro e F para falso. Mostre em cada linha da tabela a com binação de v alores de A, B e de A ∧ B.
�
tabela referente às questões acim a, representada a seguir, é cham ada de tabela-verdade do conetiv o (ou operador) lógico da conjunção (∧).
	A
	B
	A ∧ B
	V
	V
	V
	V
	F
	F
	F
	V
	F
	F
	F
	F
Dica: Um a conjunção som ente é verdadeira quando todas as proposições que a com põem são verdadeiras, e é falsa em todos os outros casos.
Disjunção de proposições
O sím bolo ∨ será em pregado para representar um dos significados usuais do conetiv o “ou” em frases da linguagem natural. O significado assum ido por este sím bolo é o do “ou inclusiv o” que som ente será falso se am bas as sentenças sendo conectadas por ele forem falsas, isto é, A ∨ B será falso som ente se A e B forem falsos. Diz-se que o sím bolo ∨ representa a disjunção lógica das proposições A e B. A fórm ula A ∨ B é lida com o "A ou B".
Exercício 1.1.2
Construa a tabela-v erdade do operador ∨.
Dica: Um a disjunção som ente é falsa quando todas as proposições que a com põem são falsas, e é v erdadeira em todos os outros casos.
�
Negação de uma proposição
Os sím bolos ¬ ou ~ serão usados para representar a negação de um a proposição. Neste caso, se A é um a proposição v erdadeira, então ¬A ou ~A será um a proposição falsa e v ice-v ersa. Ou seja ¬A é a negação lógica de A (as v ezes o sím bolo ‘ (apóstrofo) tam bém é usado para sim bolizar a negação). A fórm ula ¬A é lida sim plesm ente com o "Não A" ou "Não é v erdade que A".
Exercício 1.1.3
Construa a tabela da negação lógica.
1.2 Implicação e bi-implicação
Implicação
O sím bolo → será usado para representar sentenças com o “se chov er, então a rua ficará m olhada”, ou então “não estudar im plica tirar notas baixas” ou tam bém “não fui ao cinem a porque o carro estragou” e sentenças sim ilares. Geralm ente, essas sentenças podem ser reescritas no form ato “Se sentença A, então sentença B”, que sim bolicam ente fica apenas: A → B.
A noção que esse operador lógico pretende capturar é a de existência de im plicação ou de consequência entre as sentenças. Dessa form a, a sentença B não poderia ser falsa se a sentença A fosse v erdadeira, isto é, v oltando aos exem plos, não faria sentido afirm ar “se chov er, então a rua ficará m olhada” se (A) realm ente chov eu e (B) a rua não ficou m olhada (!?). Isso significa que se considera que a sentença sim bolizada por A→B seria falsa som ente no caso em que A é v erdadeira e B falsa. Nos outros casos a expressão A→B seria v erdadeira.
sím bolo → é o operador de implicação (tam bém denom inado
d e condicional). Quando há chance de conflito com a relação de
im plicação lógica, esse operador tam bém pode ser denom inado implicação material.
fórm ula A → B é lida com o "A im plica em B" ou "se A então B". Neste caso a proposição A é denom inada condição (ou antecedente) da im plicação e a proposição B é denom inada conclusão (ou
�
consequente) dessa im plicação.
Nota: quando a sentença A na fórm ula A → B é falsa, então o resultado de toda a fórm ula A → B é v erdadeiro independente de B. Isso sim plesm ente indica que, se assum im os falsidades com o v erdades, então qualquer coisa é possível.
Com base na discussão acim a, a construção da tabela-v erdade de A→B é representada a seguir .
	A
	B
	A → B
	V
	V
	V
	V
	F
	F
	F
	V
	V
	F
	F
	V
Dica: Um a implicação material A→B som ente é falsa quando a condição A for verdadeira e a conclusão B for falsa. Ela é v erdadeira em todos os outros casos.
Bi-implicação ou equivalência
operação de bi-implicação ou de equivalência (tam bém denom inada bicondicional) é representada pelo sím bolo ↔ e v erifica se duas proposições têm o m esm o v alor lógico.
O uso de bi-im plicações não é com um na linguagem natural, m as existe um a form a tradicional de se traduzir (transliterar) o operador ↔ para a linguagem natural, atrav és da expressão “ se e somente se” , assim a fórm ula A↔B pode ser lida com o "A bi-im plica em B" ou "A se e som ente se B".
operação A↔B pode ser considerada um a abrev iação da seguinte fórm ula (A→B) ∧ (B→A), afinal ela é um a "bi-im plicação", ou seja, um a im plicação dupla. Com essa inform ação a construção da tabela-v erdade de A↔B está representada na sequência.
�
A	B	A ↔ B
�
	V
	
	V
	
	V
	V
	
	F
	
	F
	F
	
	V
	
	F
	F
	
	F
	
	V
	
	
	
	Dica: Um a
	bi-im plicação m aterial
	A↔B é v erdadeira
quando A = B e falsa caso A ≠ B.
1.3 Fórmulas e precedência
Um a fórm ula é construída pela com posição de sím bolos de sentenças sim ples (A, B, …) e de conetiv os lógicos binários ( ∧ , ∨ , → e
) e unários (¬, ~). Tam bém podem ser usados parênteses. A precedência usual é:
1 . Fórm ulas dentro de parênteses (os m ais internos prim eiro)
2 . ¬, ~ (a negação)
3 . ∧ (conjunção)
4 . ∨ (disjunção)
5. → (im plicação m aterial)
6 . ↔ (bi-im plicação ou equiv alência lógica)
7 . Da esquerda para a direita: ∧ , ∨
8. Da direita para a esquerda: → , ↔
Um a fórm ula que não tenha erro de sintaxe em sua escrita (por exem plo, não tenha excesso nem falta de parênteses, operadores ou sím bolos estranhos etc.) é cham ada de "fórm ula bem -form ada" (ou fbf). Na literatura tam bém é m uito usado o term o em inglês "well-formed formula" (wff).
Neste liv ro, entretanto, quando nos referirm os a um a fórmula, estarem os assum indo que ela é bem -form ada. Exceções são indicadas no texto.
Em term os de sintaxe, fórm ula é um a estrutura que dev e ser m ontada pelas seguintes regras de form ação:
�
1 . Qualquer	sentença	sim ples P, Q, R, ..., P1, P2,	...	é um a
fórm ula.
2 . Se P é um a fórm ula, então ¬ P tam bém é.
3 . Se P e Q são fórm ulas, então P ∧ Q, P ∨ Q, P → Q e P ↔ Q tam bém são fórm ulas.
Qualquer coisa que não possa ser m ontada pelas regras acim a não é considerada um a fórm ula. Essas regras m ostram com o fórm ulas compostas ou complexas são construídas a partir das fórm ulas sim ples, por aplicações repetidas das regras de form ação. As fórm ulas que entram na com posição de um a fórm ula com plexa são sub-fórm ulas desta fórm ula.
Exemplos:
¬ (A ∧ B)
Pela regra 1 v em os que A e B são fórm ulas sim ples. Vam os cham ar a sentença sim ples A de fórm ula P e a sentença sim ples B de fórm ula Q. Seguindo pela regra 3 v em os que P ∧ Q é um a fórm ula e, portanto A ∧ B tam bém é um a fórm ula. Para finalizar, basta cham ar esta fórm ula A ∧ B récem form ada de P, então, pela regra 2, ¬ P é um a fórm ula e consequentem ente ¬ (A ∧ B) é um a fórm ula corretam ente m ontada (form ada) pelas regras de form ação.
¬ B ∧ (C → D)
Tam bém podem os utilizar as regras de form ação para "desm ontar" um a fórm ula, v erificando enquanto isso se a fórm ula foi corretam ente form ada. Se div idirm os a fórm ula acim a em duas partes, denom inando ¬ B de P e C → D de Q, então podem os v er que a fórm ula acim a foi form ada pela regra 3 : P ∧ Q. Agora falta v erificar se as partes P e Q são realm ente fórm ulas bem -form adas. No caso de P que é igual a
B é fácil de v er que ela pode ser corretam ente m ontada pela regra 1 para tanto basta considerar a sentença B com o a fórm ula P dessa regra, resultando em ¬P e portanto em ¬B. O caso da parte Q que é igual a C → D é sim ilar . Basta usar a regra 3 de nov o, m as desta v ez cham ando a sentença C de fórm ula P e a sentença D de fórm ula Q, resultando em P → Q e então em C → D. Não há m ais o que "desm ontar", portanto a
�
fórm ula ¬ B ∧ (C → D) foi inteiram ente desm ontada pelas regras de form ação, m ostrando que ela é um a fórm ula bem -form ada.
Supondo que A, B e C são proposições lógicas, então as seguintes expressões são fórm ulas:
1 . (A → B) ↔ (B → A)
2 . (A ∨ ¬A) → (B ∧ ¬B)
3 . (A ∧ ¬B) → ¬C
4 . (A → B) ↔ B → A
((A ∧ B ∧ C) ∨ ¬(¬B v A) v (A ∧ ¬C)) → (C v ¬A) 6 . ¬¬(A ∧ C)
Contraexemplos (erros mais comuns):
As seguintes fórm ulas apresentam alguns erros bastante com uns de escrita (sintaxe) que podem ocorrer nas fórm ulas (do lado é indicado o tipo de erro):
	1 . ( A → B ↔ (B → A)
	falta um fecha parênteses
	2
	. ( A ∨ ¬) → (B ∧ ¬B)
	a prim eira negação não está seguida
	
	de um a proposição
	
	
	3
	. ¬((A ¬B) → ¬C
	falta um operador lógico binário
	
	entre A e ¬B
	
	
	4
	. (v ¬A) → (B ∧ ¬B)
	falta um a proposição no lado
	
	esquerdo do operador v
	
	
	5. ((A B ∧ C) ∨ ¬(¬v A) v (C v ¬A)
	falta um operador
	
	lógico binário entre A e B e tam bém falta um a proposição
	
	depois do operador de negação antes do operador v
1.4 Construção de tabelas-verdade para fórmulas
Um a tabela-v erdade m ostra, em suas colunas m ais à esquerda, todas as com binações de v alores lógicos que as proposições de um a determ inada fórm ula podem assum ir . A partir desses v alores de entrada pode-se “calcular” os v alores que essa fórm ula irá ter para cada um a dessas com binações de v alores. Esse cálculo é feito passo a passo,
�
criando-se colunas interm ediárias que ficam posicionadas à direita das colunas de entrada e que contêm os v alores das subfórm ulas que com põem a fórm ula principal. Na últim a coluna m ais à direita se coloca a coluna que contém os v alores finais dessa fórm ula. Resum indo, para se construir a tabela-v erdade de um a fórm ula lógica pode-se seguir os passos:
nas colunas à esquerda coloque os sím bolos sentenciais sim ples (A, B, …), depois,
se houv er sentenças sim ples negadas (¬A, ¬B, …), coloque-as nas próxim as colunas e, por fim ,
seguindo a precedência, crie um a coluna para cada fórm ula com posta (não é necessário repetir as sentenças sim ples negadas).
A últim a coluna à direita dev e ser a expressão ou fórm ula final. As sentenças ou sím bolos proposicionais sim ples pertencentes a
um a fórm ula definem o núm ero de linhas da tabela-v erdade para esta fórm ula atrav és de um a regra sim ples:
1 sím bolo:A	2 linhas (2 1 com binações: V e F)
2 sím bolos: A	4 linhas (2 2 com binações: VV, VF, FV, FF)
e B
3 sím bolos: A,	8 linhas (2 3 com binações: VVV, VVF, VFV,
B e C	VFF, FVV, FVF, FFV, FFF)
4 sím bolos: A,	1 6 linhas (2 4 com binações)
B, C e D
n sím bolos: A,	2 n linhas (2 n com binações)
B, …
A últim a linha da tabela acim a define a regra: para n sím bolos
proposicionais	sim ples	dev em	existir	2 n	linhas	na	tabela	para
representar as 2 n com binações de v alores-v erdade possív eis.
�
Exemplo:
�
O operador de disjunção ∨ é aplicado sobre duas proposições A ∨ B. A tabela-v erdade desse operador, usando V para indicar v erdadeiro e F para indicar falso (que dev eria ter sido construída no exercício 1 .1 .), é igual a:
	A
	B
	A ∨ B
	V
	V
	V
	V
	F
	V
	F
	V
	V
	F
	F
	F
Outra form a de representar v erdadeiro/falso é atrav és de v alores num éricos, 0 significa falso e 1 significa v erdadeiro (esta é a form a m ais com um usada em álgebra booleana e em circuitos lógicos). Usandoessa notação, a tabela acim a ficaria:
	A
	
	B
	
	A ∨ B
	0
	
	0
	
	0
	0
	
	1
	
	1
	1
	
	0
	
	1
	1
	
	1
	
	1
	Note que,
	quando se usa 0 e 1 , a
	disposição dos v alores
v erdadeiros e falsos m uda. No caso de se usar V e F, geralm ente se com eça com a linha superior toda em V e as dem ais linhas v ão aos poucos sendo preenchidas com F até que na linha inferior todos os v alores são F. No caso de se usar 0 e 1 a disposição é exatam ente contrária. O reflexo dessas diferentes disposições aparece claram ente na últim a coluna.
Neste texto som ente será usada a prim eira representação, com V para v erdadeiro e F para falso, que é a form a usual da lógica proposicional.
�
Exercício 1.4.1
�
Agora construa tabelas-v erdade para as seguintes fórm ulas:
1 . (A → B) ↔ (B → A)
2 . (A ∨ ¬A) → (B ∧ ¬B)
3 . ¬((A ∧ ¬B) → ¬C)
4 . (A → B) ↔ (¬B → ¬A)
5. ((A ∧ B ∧ C) ∨ ¬¬(¬B v A) v (A ∧ ¬C)) → (C v ¬A)
1.5 Tautologias e contradições
Um a tautologia é um a fórm ula que assum e apenas o v alor V, ou seja, que é sem pre v erdadeira. Um a tautologia é “intrinsecam ente v erdadeira” pela sua própria estrutura; ela é v erdadeira independente de qualquer v alor lógico atribuído às suas letras de proposição.
Um a contradição é o oposto de um a tautologia, ou seja, é um a fórm ula que assum e apenas o v alor F independente de qualquer com binação de v alores-v erdade atribuída às proposições lógicas sim ples que entram em sua com posição.
No caso da lógica proposicional, para dem onstrar que um a fórm ula é um a tautologia ou um a contradição basta construir sua tabela-v erdade.
A questão (A → B) ↔ (¬B → ¬A) apresentada acim a é um exem plo de tautologia (basta conferir sua tabela-v erdade).
Exercício 1.5.1
Descobrir quais das seguintes fórm ulas são tautologias, contradições ou fórm ulas contingentes (fórm ulas “sim ples” que não são tautologias ou contradições).
1 . (A ∨ B) ↔ (B ∨ A)
2 . ((A ∨ B) ∨ C) ↔ (A ∨ (B ∨ C))
3 . ¬(A ∧ B) ↔ (¬A ∧ ¬B)
4 . (A → B) ↔ (¬B → ¬A)
((A ∧ B) ∧ B) → ¬(¬B v A) ∧ ¬A) 6 . ¬(¬A ↔ ¬B) → (B ∧ (C v ¬A))
�
1.6 Equivalências tautológicas e Leis de DeMorgan
Equivalências tautológicas
Considere que P e Q sejam duas fórm ulas lógicas quaisquer e que P↔Q seja um a tautologia, então pela própria definição do conetiv o ↔, sem pre que P for V em um a linha da tabela-v erdade de P↔Q, a fórm ula Q tam bém dev erá ser V nesta linha. O m esm o acontece para quando P tem v alor F. Neste caso se diz que P e Q são fórmulas equivalentes.
Essa propriedade é denotada pelo operador ⇔ de equiv alência tautológica entre as fórm ulas P e Q, sim bolicam ente fica P ⇔ Q.
Na tabela a seguir são apresentadas algum as equiv alências tautológicas que definem propriedades im portantes da disjunção e conjunção:
Tabela 1 – Equiv alências da disjunção ( ∨ ) e da conjunção ( ∧ )
Fonte: el aborada pel os au tores.
Na tabela a seguir são apresentadas algum as equiv alências tautológicas que perm item reescrev er ou redefinir os outros operadores:
Tabela 2 – Equiv alências dos outros operadores
Fonte: el aborada pel os au tores.
�
Exercício 1.6.1
�
Dem onstrar, pelo uso da tabela-v erdade, as equiv alências tautológicas acim a (não é necessário repetir as dem onstrações para a equiv alência com utativ a, associativ a e contraposição).
Leis de De Morgan
As equiv alências v istas anteriorm ente perm item efetuar v ários tipos de m anipulações ou alterações em um a fórm ula sem que ela altere seu significado. Além dessas fórm ulas, entretanto, seria interessante que houv esse m aneiras de se conv erter proposições conectadas pelo operador ∨ em proposições conectadas por ∧. Essas equiv alências são denom inadas Leis de DeMorgan em hom enagem ao m atem ático inglês do século XIX Augustus DeMorgan, que foi o prim eiro a enunciá-las.
1.7 Simbolização de proposições
seguir são apresentados alguns exem plos tanto de passagem de um a fórm ula para texto quanto de texto para fórm ula.
Supondo que A = “hoje está chov endo”, B = “hoje faz frio” e C = “hoje v am os para a praia”, então a fórm ula:
A ∧ B ∧ ¬C
Poderia ser v ersada para o português de diferentes m aneiras:
Hoje está chovendo, hoje faz frio e não é verdade que hoje vamos para a praia.
Hoje está chovendo, faz frio e não vamos para a praia.
Hoje está chovendo e faz frio, todavia não vamos para a praia.
Hoje está chovendo e faz frio, mas não vamos para a praia hoje.
A frase (a) que é um a transliteração direta da fórm ula A ∧ B ∧ ¬C, em bora correta do ponto de v ista gram atical, sim plesm ente não é usada pelo excessiv o form alism o. As dem ais form as são m ais usuais (e existem m uitas outras equiv alentes). Note que a negação quase nunca
�
colocada no início da proposição. Note tam bém que são usadas v árias form as de conjunções além do conetiv o “e”: é usada a v írgula no caso
(b) e as conjunções adv ersativ as “todav ia” e “m as” nos casos (c) e (d). Usando os m esm os significados para os sím bolos A, B e C, a
fórm ula:
(A ∧ B) ∨ C
Poderia ser v ersada para o português das seguintes form as:
Hoje está chovendo e faz frio, ou hoje vamos para a praia.
Ou hoje está chovendo e faz frio, ou hoje vamos para a praia.
Ou hoje está chovendo e faz frio, ou então hoje vamos para a praia.
A fórm ula:
¬(Α ∧ B)
um pouco m ais com plexa de ser v ersada, por conta da negação de um a subfórm ula em parênteses, algo sim plesm ente não usado na linguagem natural. A fórm ula poderia ser transliterada no texto:
Não é verdade que hoje está chovendo e fazendo frio.
Mas este texto é am bíguo, podendo representar a fórm ula ¬Α ∧
Um a representação m ais razoáv el da fórm ula ¬(Α ∧ B) exigiria a retirada dos parênteses, algo que som ente pode ser feito pelo uso das Leis de DeMorgan. Neste caso a fórm ula se torna:
¬Α ∨ ¬B
facilm ente v ersada para:
Hoje não está chovendo ou hoje não está fazendo frio.
A seguir são apresentados exem plos de texto, com sua sim bolização equiv alente:
Se hoje está chovendo, então ou vamos para a praia, ou está fazendo frio.
�
A→(C ∨ B)
Hoje não está chovendo, nem fazendo frio, portanto vamos para a praia.
(¬A ∧ ¬B) → C
Hoje não vamos para a praia, porque está chovendo e fazendo frio.
(A ∧ B) → ¬C
1.8 Expressões em português e operadores lógicos
Dev ido à riqueza da língua portuguesa, palav ras com significados sem elhantes são representadas pelo m esm o operador lógico. A tabela a seguir m ostra expressões com uns em português associadas a div ersos operadores lógicos.
Tabela 3 – Expressões em português
	Expressão em português
	Operador lógico
	Expressão lógica
	E; m as; tam bém
	Conjunção
	A ∧ B
	Ou
	Disjunção
	A ∨ B
	Se A, então B
	Im plicação/
	A → B
	A im plica B
	Condicional
	
	A, logo B
	
	
	A som ente se B
	
	
	A se e som ente se B
	Bi-im plicação/
	A ↔ B
	
	Bicondicional
	
	Não A
	Negação
	¬ A
	É falso que A…
	
	
	Não é v erdade que A…
	
	
Fonte: el aborada pel os au tores.
�
1.9 Questões comentadas
�
Nas questões a seguir, é possív el v erificar a construção da tabela-v erdade para três fórm ulas. É im portante lem brar dos passos para construção da tabela:
colocar nas colunas à esquerda as proposições sim ples;
se houv er proposições sim ples negadas, colocar nas colunas seguintes e
seguindo a precedência, crie um a coluna para cada fórm ula
com posta.
Questão 1. (A → B) ↔ (B → A)
Neste exem plo, não tem os o passo (ii).
	A
	B
	A → B
	B → A
	(A → B) ↔ (B → A)
	V
	V
	V
	V
	V
	V
	F
	F
	V
	F
	F
	V
	V
	F
	F
	F
	F
	V
	V
	V
Questão 2. ¬((A ∧ ¬B) → ¬C)Neste exem plo, é im portante observ ar a precedência dos operadores para construir as colunas do passo (iii).
	A
	B
	C
	¬B
	¬C
	A ∧
	(A ∧ ¬B) →
	¬((A ∧ ¬B) →
	
	
	
	
	
	¬B
	¬C
	¬C)
	V
	V
	V
	F
	F
	F
	V
	F
	V
	V
	F
	F
	V
	F
	V
	F
	V
	F
	V
	V
	F
	V
	F
	V
	V
	F
	F
	V
	V
	V
	V
	F
	F
	V
	V
	F
	F
	F
	V
	F
	
	
	
	
	
	
	
	
�
	F
	V
	F
	F
	V
	F
	V
	F
	F
	F
	V
	V
	F
	F
	V
	F
	F
	F
	F
	V
	V
	F
	V
	F
Questão 3. ((A ∧ B ∧ C) ∨ ¬¬(¬B v A) v (A ∧ ¬C)) → (C v ¬A)
Com o a construção da tabela-v erdade dessa fórm ula tem v árias colunas, considerando que cada coluna tem um a fórm ula com m uitas proposições e operadores, então para auxiliar na representação da fórm ula é utilizado um a legenda com o segue, o núm ero da coluna representa a fórm ula abaixo:
1 . (A ∧ B) ∧ C
2 . (A ∧ B ∧ C) ∨ ¬¬(¬B v A)
3 . (A ∧ B ∧ C) ∨ ¬¬(¬B v A) v (A ∧ ¬C)
4 . ((A ∧ B ∧ C) ∨ ¬¬(¬B v A) v (A ∧ ¬C)) → (C v ¬A)
	A
	B
	C
	¬A
	¬B
	¬C
	A
	1.
	A
	¬B
	¬(¬B
	¬¬(¬B
	C
	2.
	3.
	4.
	
	
	
	
	
	
	∧
	
	∧
	v
	v A)
	v A)
	v
	
	
	
	
	
	
	
	
	
	B
	
	¬C
	A
	
	
	¬A
	
	
	
	V
	V
	V
	F
	F
	F
	V
	V
	F
	V
	F
	V
	V
	V
	V
	V
	V
	V
	F
	F
	F
	V
	V
	F
	V
	V
	F
	V
	F
	F
	V
	F
	V
	F
	V
	F
	V
	F
	F
	F
	F
	V
	F
	V
	V
	V
	V
	V
	V
	F
	F
	F
	V
	V
	F
	F
	V
	V
	F
	V
	F
	F
	V
	F
	F
	V
	V
	V
	F
	F
	F
	F
	F
	F
	V
	F
	V
	V
	V
	V
	F
	V
	F
	V
	F
	V
	F
	F
	F
	F
	V
	F
	V
	V
	V
	V
	F
	F
	V
	V
	V
	F
	F
	F
	F
	V
	F
	V
	V
	V
	V
	V
	F
	F
	F
	V
	V
	V
	F
	F
	F
	V
	F
	V
	V
	V
	V
	V
�
CAPÍTULO 2
DEDUÇÃO NA LÓGICA PROPOSICIONAL
A s definições vistas até agora nos perm itiram criar u m a l ingu agem form al para a Lógica Proposicional . Essas definições tam bém nos perm itiram ver com o se pode descobrir o val or -verdade de expressões nessas l ingu agens através de tabel as-verdade. Porém isso não é tu do qu e u m a l ingu agem l ógica pode nos fornecer . A inda é necessário definir com o são feitos raciocínios ou argu m entações nessa l ingu agem . A l ógica form al l ida com u m tipo particu l ar de argu m ento, denom inado argume nto de dutivo, qu e nos perm ite dedu zir u m a concl u são Q, com base em u m conju nto de proposições P 1 a P n , onde Q e P 1 a P n representam fórm u l as inteiras bem -form adas da Lógica Proposicional (e não apenas proposições sim pl es).
2.1 Argumentos
Quando afirm am os que um a proposição lógica é v erdadeira em razão de (ou em consequência) de outras proposições lógicas tam bém serem v erdadeiras, estam os, na v erdade, expressando um argum ento lógico, ou sim plesm ente, um argumento.
Um argum ento pode ser sem pre v erdadeiro, quando a proposição que é a conclusão do argum ento sem pre for v erdadeira e quando as dem ais proposições que com põem o argum ento (cham adas de
hipóteses ou premissas) forem v erdadeiras. Neste caso, tem os um a r g u m en t o válido que poderá ser utilizado para fazer raciocínios
lógicos corretos. Por outro lado, nem sem pre argum entos são v álidos. Neste capítulo v am os estudar m étodos para garantir ou v erificar que um argum ento é v álido.
Um argum ento pode ser representado de form a sim bólica pela seguinte fórm ula da Lógica Proposicional:
P1 ∧ P2 ∧ P3 ∧ … ∧ Pn → Q
As	proposições	P1	a	Pn	são	as	hipóteses	ou	prem issas	do
argum ento. A proposição Q é a conclusão do argum ento. Em term os da
Linguagem Natural esse tipo de sim bolism o pode ser lido com o:
“P1, P2, … Pn acarretam Q” ou
“Q decorre de P1, P2, … Pn ” ou
“Q se deduz de P1, P2, … Pn ” ou ainda
�
“Q se infere de P1, P2, … Pn ”
Um a interpretação ingênua do argum ento acim a poderia pressupor que se houv er um a situação que as prem issas são v erdadeiras e a conclusão tam bém é v erdadeira, isso seria suficiente para considerar o argum ento com o correto ou apropriado. Porém isso não é suficiente: a conclusão Q som ente poderá ser considerada um a conclusão lógica das hipóteses P1, P2, … Pn se e som ente se a v erdade das
proposições P1, P2, … Pn im plicar na v erdade Q, ou seja, apenas quando a fórm ula.
P1 ∧ P2 ∧ P3 ∧ … ∧ Pn → Q
for sem pre v erdadeira (for um a tautologia).
O problem a com a interpretação ingênua é que ela poderia assum ir com o v álido um argum ento com o:
A ∧ B → C
onde A representa “um dia tem 24 horas”, B representa “bananas são frutas” e C representa “hoje é depois de ontem ” . Em bora as três sentenças sejam v erdadeiras e portanto, neste caso, A ∧ B → C seja v erdadeiro, não existe um a relação form al (ou real) entre elas e portanto não se pode dizer que um argum ento na form a tão genérica
quanto	A	∧	B	→	C	seja	sem pre	v álido,	ou	seja,	v erdadeiro
independentem ente do v alor v erdade das hipóteses ou da conclusão,
m as em função apenas da sua form a.
Assim	podem os	definir	que	um argumento	válido é	um
argum ento onde a fórm ula:
P1 ∧ P2 ∧ P3 ∧ … ∧ Pn → Q
é um a tautologia.
O fato do argum ento P1 ∧ P2 ∧ P3 ∧ … ∧ Pn → Q ser v álido é sim bolizado pela seguinte expressão:
P1, P2, P3, …, Pn ⊢ Q
Esta expressão afirm a que a fórm ula Q é logicam ente im plicada pelas hipóteses P1, P2, P3, …, Pn , ou seja, há um a relação de
�
consequência lógica entre as hipóteses e a conclusão do argum ento. Em um argum ento v álido não interessam os v alores-v erdade das
hipóteses nem da conclusão, porque som ente a form a do argum ento é capaz de garantir sua v alidade. Por isso ele é denom inado argumento formal e esta é a razão por trás do poder de dedução da lógica form al, que pode v erificar a v alidade ou correção de um argum ento sem se ater às proposições que o com põem , isto é, sem se im portar com seu significado.
Nota: às v ezes pode-se encontrar na literatura o sím bolo ⊢ em v ez d e ⊨ para representar a conclusão do argum ento. Este sím bolo, que será apresentado m ais adiante, serv e para indicar que existe um a prova ou demonstração do argum ento.
2.2 Tabela-verdade para argumentos
Um argum ento é v álido se e som ente se todas as suas instâncias são v álidas. Um a instância é v álida se todas as prem issas forem v erdadeiras e a conclusão tam bém for v erdadeira. A v alidade de um argum ento da Lógica Proposicional pode ser testada atrav és de um a v ersão sim plificada da tabela-v erdade, onde são colocadas em colunas separadas todas as prem issas do argum ento e na coluna final é colocada
conclusão do argum em to. Agora, cada um a das linhas dessa tabela m ostra um a das instâncias possív eis do argum ento. Assim , o argum ento será v álido se e som ente se nas linhas onde todas as prem issas são v erdadeiras, então a conclusão tam bém é v erdadeira. Caso contrário, existirá nessa tabela-v erdade pelo m enos um a instância em que as prem issas são v erdadeiras e a conclusão é falsa, m ostrando, então, que o argum ento é inv álido. Essa situação cham a-se contra-
exemplo.	A	existência	de	um	contra-exem plo	na	tabela-v erdade
m ostra que a form a do argum ento é inv álida.
Podem os	nos	basear	na	construção	de	tabelas-v erdade	para
análise sintática (gram atical) para v erificarm os se um argum ento é
	v álido. Buscam os exam inar a sintaxe do
	cálculo
	proposicional
	m ostrando com o as form as de v árias sentenças podem
	ser expressas
	com o fórm ulas (sim bolização das sentenças).
	
	
	Para determ inar se a form a de um argum ento da lógica
	proposicional é v álida, v am os construir um a
	tabela-v erdade para a
	expressão: P ∨ Q, ¬P ⊢ Q.
	
	
�
Tabela 4 – Tabela-v erdade do argum ento : P ∨ Q, ¬P ⊢ Q
	
	P
	Q
	¬P
	P ∨ Q
	Q
	1
	V
	V
	F
	V
	V
	2
	V
	F
	F
	V
	F
	3
	F
	V
	V
	VV
	4
	F
	F
	V
	F
	F
Fonte: el aborada pel os au tores.
Esta tabela-v erdade serv e para testar a v alidade do argum ento, sendo apenas um a v ersão sim plificada da tabela-v erdade da fórm ula ((P ∨ Q) ∧ ¬P) → Q. Nela podem os v erificar que a form a do argum ento é v álida, pois onde as prem issas são v erdadeiras a conclusão tam bém é v erdadeira (destacado na linha 3 ). Assim , não há situação possív el onde as prem issas são v erdadeiras e a conclusão é falsa, não im porta qual a com binação de V e F atribuída a cada hipótese.
Outro exem plo de argum ento onde v am os construir a tabela-v erdade para v erificarm os se sua form a é v álida: P ∨ Q, Q → ¬P ⊢ Q ∧ P.
Tabela 5 – Tabela-v erdade do argum ento: P ∨ Q, Q → ¬P ⊢ Q ∧ P
	
	P
	Q
	¬P
	P ∨ Q
	Q → ¬P
	Q ∧ P
	1
	V
	V
	F
	V
	F
	V
	2
	V
	F
	F
	V
	V
	F
	3
	F
	V
	V
	V
	V
	F
	4
	F
	F
	V
	F
	V
	F
Fonte: el aborada pel os au tores.
Neste caso v erificam os que nas linhas 2 e 3 as hipóteses são v erdadeiras e a conclusão é falsa. Portanto, o argum ento é inv álido.
Se na construção da tabela-v erdade v erificarm os m ais de um a instância com todas as prem issas v erdadeiras, então terem os que av aliar todas elas.
No argum ento P → ¬Q, ¬Q ⊢ P tem os as linhas 2 e 4 em destaque para v erificar . Na linha 2, as hipóteses e a conclusão são v erdadeiras.
�
Com esse resultado, o argum ento seria v álido, entretanto, é necessário av aliar a linha 4 tam bém . Na linha 4 tem os o m esm o caso do exem plo anterior, as hipóteses são v erdadeiras e a conclusão é falsa. Portanto, o argum ento é inv álido.
Tabela 6 – Tabela-v erdade do argum ento: P → ¬Q, ¬Q ⊢ P
	
	P
	Q
	¬Q
	P → ¬Q
	P
	1
	V
	V
	F
	F
	V
	2
	V
	F
	V
	V
	V
	3
	F
	V
	F
	V
	F
	4
	F
	F
	V
	V
	F
Fonte: el aborada pel os au tores.
2.3 Demonstrações formais
Conform e v isto anteriorm ente, para testar se o argum ento P1 ∧ P2 ∧ P3 ∧ … ∧ Pn → Q é v álido, poderíam os sim plesm ente construir a
tabela-v erdade correspondente ao argum ento. Há, entretanto, um outro m étodo para testar a v alidade de um argum ento que é totalm ente independente das tabelas-v erdade. Este m étodo é baseado na aplicação d e regras de dedução (ou regras de inferência) que m odificam fórm ulas de m odo a preserv ar seu v alor lógico.
ideia básica desse m étodo é com eçar com as hipóteses H1, H2, … Hn (supostam ente v erdadeiras) e tentar aplicar regras de dedução até
term inar com a conclusão Q. Essa conclusão teria que ser, então, v erdadeira um a v ez que o v alor lógico v erdadeiro é sem pre preserv ado sob as regras de inferência.
Dessa form a, um a prova ou demonstração form al da lógica proposicional seria form ada por um a série de linhas num eradas den om in a da s passos da prov a, onde cada passo tem a seguinte estrutura:
�
1 .	H1	Hipótese 1
�
	2 .
	H2
	Hipótese 2
	…
	
	
	n.
	Hn
	Hipótese n
	n+1 .
	F1
	Fórm ula obtida aplicando um a regra sobre
	
	
	fórm ulas dos passos anteriores
	n+2 .
	F2
	Fórm ula obtida aplicando um a regra sobre
	
	
	fórm ulas dos passos anteriores
	…
	
	
	n+m .
	Fm
	Fórm ula obtida aplicando um a regra sobre
	
	
	fórm ulas dos passos anteriores
	
	Q
	Fórm ula obtida aplicando um a regra sobre
	
	
	fórm ulas dos passos anteriores
Nesta dem onstração, a conclusão Q é sim plesm ente a fórm ula contida no últim o passo, que foi obtida atrav és da aplicação de um a regra de dedução (tam bém cham ada de regra de inferência) sobre fórm ulas contidas em passos anteriores. A própria form a da regra indica com o ela pode ser utilizada e quais passos poderiam ser úteis. Os passos que foram efetiv am ente usados na aplicação da regra dev em ser referenciados no fim do passo, para que se possa v erificar se a regra foi utilizada corretam ente.
A sequência de passos obtida por este processo é denom inada sequência de demonstração da conclusão em função de suas hipóteses. Essa sequência é a prova (ou demonstração) que a conclusão Q se deduz das hipóteses H1, H2, …, H n . Nesse caso, prov ar um
argum ento H1 ∧ H2 ∧ H3 ∧ … ∧ Hn → Q é sim bolizado atrav és da seguinte expressão:
H1, H2, H3, …, Hn ⊢ Q
Esta expressão afirm a que a conclusão Q pode ser deduzida das hipóteses H1, H2, H3, …, H n , ou seja, que existe um a relação de dedução entre as hipóteses e a conclusão do argum ento.
Nota: Em bora pareça m uito m ais sim ples aplicar o m étodo de construção da tabela-v erdade para v erificar a v alidade de um argum ento, o m étodo da dem onstração form al se justifica por duas razões:
�
Quando o núm ero de proposições sim ples é m uito grande, por exem plo, com apenas 40 proposições sim ples seria necessária um a tabela-v erdade com aproxim adam ente 1 trilhão de linhas.
No caso das lógicas m ais expressiv as com o a lógica de predicados, sim plesm ente não é possív el aplicar o m étodo da tabela-v erdade, ou seja, som ente nos resta aplicar o m étodo da dem onstração form al.
Na v erdade, na Lógica Proposicional é possív el prov ar que qualquer um dos dois m étodos, tabela-v erdade ou dem onstração form al, pode ser usado para com prov ar a v alidade de um argum ento, ou seja, sem pre que a tabela-v erdade m ostrar que o argum ento é v álido, então hav erá um a dem onstração form al deste argum ento e se houv er um a dem onstração form al de um argum ento, então sua tabela-v erdade irá m ostrar que este argum ento é v álido.
2.4 Regras de dedução natural
m étodo de dedução utilizado neste liv ro é denom inado Dedução Natural, por ser considerado um m étodo que se aproxim a da form a com o deduções lógicas são feitas naturalm ente. Esse m étodo foi desenv olv ido na década de 1 93 0 por Gentzen para ajudar nas prov as de consistência da Teoria dos Núm eros (NOLT, 1 991 ). O m étodo de dedução em pregado neste liv ro é m uito sim ilar aos m étodos de dedução form al apresentados em (NOLT, 1 991 ) e (BARONETT, 2005).
Todas as regras de dedução se baseiam em argum entos sim ples que já se tenha dem onstrado por tabela-v erdade serem v álidos. A Tabela 7 apresenta as regras básicas de inferência da lógica proposicional.
Tabela 7 – Regras básicas de inferência
�
Fonte: el aborada pel os au tores.
�
Tabela 8 – Regras de inferência deriv adas
�
Fonte: el aborada pel os au tores.
Exemplos de aplicação do método
Excetuando-se as regras de redução ao absurdo (RAA) e prov a condicional (PC), todas as dem ais regras de inferência e de equiv alência apresentadas nas Tabelas 7 , 8 e 9 são de aplicação direta. Nesta seção serão m ostrados exem plos de uso dessas regras de aplicação direta.
Supondo que A→ (B ∧ C) e A são duas hipóteses de um argum ento, então a seguinte dem onstração é v álida:
	1 .
	A → (B ∧ C)
	hip
	2 .
	A
	hip
	3 .
	B ∧ C
	1 ,2, m p
As fórm ulas das 2 prim eiras linhas são inseridas por conta das hipóteses, enquanto a fórm ula da linha 3 é deriv ada das fórm ulas das linhas 1 e 2 pela regra modus ponens.
Usando a lógica proposicional, prov a-se o seguinte argum ento:
A, B → C, (A ∧ B) → (C → D), B ⊢ D
�
Prim eiro as hipóteses do argum ento:
	1 .
	A
	hip
	2 .
	B → C
	hip
	3 .
	(A ∧ B) → (C → D)
	hip
	4 .
	B
	hip
Alguns passos óbv ios (que poderão ser úteis ou não):
	5.
	C
	2, 4, m p
	6 .
	A ∧ B
	1 , 4, cj
	7 .
	C → D
	3 , 6, m p
	E agora, portanto:
	8.
	D 5, 7 , m p
De acordo com o m étodo, para prov ar que o argum ento é v álido, inicialm ente enum era-se as hipóteses. O argum ento para prov ar é:
P ∧ Q, P → R, (R ∧ S) → ¬T, Q → S ⊢ ¬T
	1 .
	P ∧ Q
	hip
	2 .
	P → R
	hip
	3 .
	(R ∧ S) → ¬T
	hip
	4 .
	Q → S
	hip
partir disso, com o sugestão v erifica-seonde está a conclusão ou parte dela nas hipóteses. Assim é possív el aplicar as regras gerando fórm ulas até que a fóm ula gerada seja a conclusão. A conclusão do argum ento é ¬T, então é possív el identificar ¬T na linha 3 .
�
3 .	(R ∧ S) → ¬T	hip
Tam bém é im portante salientar que para aplicar um a regra na linha 3 , tem os que identificar o principal operador lógico da fórm ula, nesse caso, a im plicação. A regra que elim ina a im plicação (→) é a Modus Ponens (m p).
Para aplicar a regra, precisa-se de duas fórm ulas conform e indica a estrutura apresentada, isto é, um a fórm ula é P e a outra é P → Q. Com o as fórm ulas estão acim a da linha horizontal, então já dev em existir na dem onstração e o que está abaixo é a fórm ula que será gerada a partir da aplicação da regra m p. Com isso, v oltando à dem onstração do argum ento, para aplicar a regra m p na linha 3 , tem os que encontrar a outra fórm ula P. Nesse caso, P dev e ser exatam ente igual ao antecedente da fórm ula da linha 3 , então dev em os gerar R ∧ S.
Da m esm a form a que foi discutido anteriorm ente para a fórm ula da linha 3 , onde a im plicação é o operador principal e dev e ser aplicada a regra m p, agora a linha 2 precisa-se liberar R e o operador principal é um a im plicação.
	1 .
	P ∧ Q
	hip
	2 .
	P → R
	hip
	3 .
	(R ∧ S) → ¬T
	hip
	4 .
	Q → S
	hip
	5.
	P
	1, sp
Aplicar a regra m p é possív el, pois tem os duas fórm ulas conform e m ostra a im agem , então a fórm ula R na linha 6 é gerada a partir da aplicação da regra m p na linha 2 e na linha 5.
�
	1 .
	P ∧ Q
	hip
	2 .
	P → R
	hip
	3 .
	(R ∧ S) → ¬T
	hip
	4 .
	Q → S
	hip
	5.
	P
	1 , sp
	6.
	R
	2,5, mp
Com esse raciocínio, é possív el gerar a fórm ulas da linha 7 e da linha 8.
	1 .
	P ∧ Q
	hip
	2 .
	P → R
	hip
	3 .
	(R ∧ S) → ¬T
	hip
	4 .
	Q → S
	hip
	5.
	P
	1 , sp
	6 .
	R
	2,5, m p
	7 .
	Q
	1, sp
	8.
	S
	4,7, mp
Pela ideia inicial de aplicar a regra m p na linha 3 , foi necessário aplicar outras regras parar gerar fórm ulas até gerar a fórm ula da linha 9 .
	1 .
	P ∧ Q
	hip
	2 .
	P → R
	hip
	3 .
	(R ∧ S) → ¬T
	hip
	4 .
	Q → S
	hip
	5.
	P
	1 , sp
	6 .
	R
	2,5, m p
	7 .
	Q
	1 , sp
	8.
	S
	4,7 , m p
	9.
	R ∧ S
	6,8, cj
�
Por fim , aplica-se m p na linha 3 e na linha 9 para gerar a fórm ula ¬T, que v em a ser a conclusão do argum ento.
	1 .
	P ∧ Q
	hip
	2 .
	P → R
	hip
	3 .
	(R ∧ S) → ¬T
	hip
	4 .
	Q → S
	hip
	5.
	P
	1 , sp
	6 .
	R
	7 .
	Q
	1 , sp
	8.
	S
	4,7 , m p
	9 .
	R ∧ S
	6,8, cj
	10.
	¬T
	3, 9, mp
2.5 Uso das regras hipotéticas
As seis regras básicas de inferência para a Lógica Proposicional que tratam da inclusão e exclusão dos operadores ∧, ∨, ¬, → e ↔ , além da regras de exclusão da im plicação (Modus Ponens - m p) e da negação (Dupla Negação - dn) são de aplicação direta, não sendo necessário um raciocínio hipotético para funcionar .
Por outro lado, as duas regras de inclusão da im plicação (Prov a Condicional - pc) e da negação (Redução Ao Absurdo - raa) exigem raciocínios hipotéticos para serem aplicadas. Esses raciocínios são incorporados na prov a na form a de dem onstrações auxiliares ou hipotéticas, que têm um caráter “tem porário” e que dev erão ser descartadas quando a conclusão da dem onstração auxiliar for atingida.
form a com o os resultados obtidos com a dem onstração auxiliar serão usados na prov a principal depende da regra de inferência usada.
No caso da redução ao absurdo (raa), a dem onstração auxiliar é usada para m ostrar que a partir de um a fórm ula P, usada com o hipótese inicial na dem onstração auxiliar, é possív el dem onstrar um a contradição lógica, isto é, um a fórm ula do tipo Q ∧ ¬Q. Neste caso a nov a fórm ula que se pode adicionar na prov a principal é ¬P, que pode ser assum ida com o v álida, porque caso contrário se chega a um a
�
contradição lógica.
Já no caso da prov a condicional (pc), a dem onstração auxiliar m ostra que, caso se assum a a fórm ula P com o hipótese inicial da dem onstração auxiliar, então é possív el se deduzir um a fórm ula Q. Se conseguirm os deduzir, a partir de P e das outras hipóteses, um a outra fórm ula Q, então a fórm ula P → Q pode ser adicionada na sequência norm al de dem onstração. Neste caso, a fórm ula P → Q adicionada à prov a principal resum e o fato (prov ado) que de P se pode deduzir Q.
Quando as regras que utilizam raciocínio hipotético são concluídas, então todas as fórm ulas que constituem a dem onstração auxiliar têm que ser “descartadas” e não m ais utilizadas na sequência norm al de dem onstração. Som ente a fórm ula que foi dem onstrada atrav és do artifício do raciocínio hipotético pode ser usada na
dem onstração norm al.
Quando	as	regras	hipotéticas	são	utilizadas	em	um a
dem onstração, algum as considerações dev em ser esclarecidas:
Tabela 9 – Restrições sobre o uso de regras hipotéticas
1 )	Cada hipótese de um a regra hipotética introduz em um a prov a o início de um a nov a linha v ertical. Essa linha continua até a hipótese ser descartada pela finalização da regra hipotética, seja ela PC ou RAA.
Nenhum a ocorrência de um a fórm ula à direita de um a linha v ertical pode ser citada em qualquer regra aplicada depois de term inar a linha v ertical. Isso é para garantir que a fórm ula deriv ada da hipótese não seja usada indev idam ente depois que a hipótese foi descartada.
3 ) Se duas ou m ais hipóteses de regras hipotéticas são v igentes sim ultaneam ente, então a ordem na qual elas são descartadas dev e ser a ordem inv ersa na qual elas são introduzidas.
Um a dem onstração não está com pleta até que todas as hipóteses de regras hipotéticas seja descartadas (ou seja que todas as regras hipotéticas sejam finalizadas). As hipóteses que não são descartadas são prem issas adicionais introduzidas ilicitam ente na dem onstração.
�
Fonte: adaptado de N OLT, 1991, p.121.
Exemplos:
Prov e o seguinte argum ento, que equiv ale à regra do silogism o hipotético:
P → Q, Q → R ⊢ P → R
A dem onstração é a seguinte e usa a regra de prov a condicional:
1	P→Q	hip
Q→R hip
3	| P	hip-pc
| Q1 ,3 , m p
| R2,4, m p
6 P→R 3 -5, pc
Observ e que a hipótese da prov a condicional (hip-pc) e as fórm ulas obtidas a partir dela e das hipóteses norm ais foram escritas ao lado da barra v ertical | , m ais à esquerda que as fórm ulas pertencentes
sequência norm al de dem onstração. Isso é para deixar claro o caráter tem porário destas fórm ulas.
Um outro exem plo de uso de prov a condicional é usado na dem onstração do argum ento:
P ⊢ (P → Q) → Q
A dem onstração é:
	1
	P
	hip
	2
	| P→Q
	hip-pc
	3
	| Q
	1 ,2, m p
	4
	(P→Q)→Q 2 -3 , pc
�
regra da prov a condicional tam bém é útil para prov ar o seguinte argum ento:
A → (A → B) ⊢ A → B
Usando essa regras a dem onstração fica:
	1
	A → (A → B)
	hip
	2
	| A
	hip-pc
	3
	| A → B
	1 , 2, m p
	4
	| B
	2, 3 , m p
	5
	A → B
	2 -4, pc
A regra de redução ao absurdo pode ser usada para prov ar o seguinte argum ento (que é equiv alente à regra deModus Tollens):
P → Q, ¬Q ⊢ ¬P
A dem onstração fica:
	1
	P→Q
	hip
	2
	¬Q
	hip
	3
	| P
	hip-raa
	4
	| Q
	1 ,3 , m p
	5
	| Q ∧ ¬Q
	2,4, cj
	6
	¬P
	3 -5, raa
Regras hipotéticas podem ser “aninhadas” um a dentro da outra, se isso for necessário. Isso ocorre, por exem plo, na prov a de:
(P ∧ Q) → R ⊢ P → (Q → R)
Cuja dem onstração é a seguinte:
�
1	(P ∧ Q)→R	hip
�
	2
	| P
	hip-pc
	3
	| | Q
	hip-pc
	4
	| | P ∧ Q
	2,3 , cj
	5
	| | R
	1 ,4, m p
	6
	| Q→R
	3
	-5, pc
	7
	P → (Q→R)
	2
	-6, pc
Importante:
Sem pre que as regras hipotéticasRAA e PC forem usadas em um a dem onstração elas dev em ser finalizadas antes de se deduzir a conclusão do argum ento.
Dicas de dedução para construção das provas
1 . A regra de Modus Ponens é prov av elm ente a regra de inferência m ais intuitiv a. Tente usá-la m uitas v ezes.
2 . Fórm ulas na form a ¬(P ∨ Q) ou ¬(P ∧ Q) dificilm ente são úteis em um a sequência de dem onstração. Tente usar as Leis de DeMorgan para conv ertê-las, respectiv am ente, em ¬P ∧ ¬Q ou ¬P ∨ ¬Q, separando os com ponentes indiv iduais de cada fórm ula.
3 . Fórm ulas na form a P ∨ Q dificilm ente são úteis em um a sequência de dem onstração, já que não im plicam P nem Q. Tente usar a dupla negação para conv erter P ∨ Q em ¬(¬P) ∨ Q e depois usar a regra do condicional para obter ¬P → Q.
4 . Não há m aneira correta de se construir um a prov a. Se um a form a pode ser prov ada, ele pode ser prov ada por diferentes trocas de regras. Entretanto, as prov as m ais curtas, m ais sim ples e m ais fáceis são obtidas por um a estratégia baseada na estrutura da conclusão. As sugestões da Tabela 1 0 são guias úteis para o planejam ento de tais estratégias. Geralm ente, elas lev am
prov as razoav elm ente eficientes, em bora alguns problem as requeiram habilidade e engenhosidade.
�
	
	Tabela 1 0 – Estratégias para prov a
	
	
	Formato
	Estratégia de Prova
	da
	
	Conclusão
	
	Fórm ula
	Se nenhum a estratégia é im ediata, coloca-se com o
	atôm ica
	hipótese a negação da conclusão para raa (redução
	
	ao absurdo). Se isso for bem -sucedido, então a
	
	conclusão pode ser obtida depois de raa, pela
	
	aplicação da regra dupla negação (dn –
	
	elim inação da ¬).
	Fórm ula
	Coloca-se com o hipótese a conclusão sem a negação
	negada
	para raa. Se resultar um a contradição, a conclusão
	
	pode ser obtida por raa.
	Conjunção
	Prov e cada um a das sentenças separadam ente e
	
	então faça a conjunção delas com a regra
	
	conjunção (cj – introdução do ∧).
	Disjunção
	Se um a prem issa com um a disjunção faz parte do
	
	argum ento, então tenta-se prov ar os condicionais
	
	necessários para obter a conclusão pela regra de
	
	eliminação da disjunção (E∨). Caso contrário,
	
	coloca-se com o hipótese a negação da conclusão e
	
	tenta-se raa. Em algum as situações, é possív el
	
	prov arm os a conclusão diretam ente, encontrando
	
	um a das prem issas e aplicando a regra adição (ad
	
	– introdução do ∨).
	Im plicação
	Coloca-se com o hipótese o seu antecedente e deriv a-
	
	se o seu consequente, aplicando a regra prova
	
	condicional (pc - introdução da →).
	Bi-
	Use a regra prova condicional (pc – introdução do
	im plicação
	condicional) – duas v ezes para prov ar os dois
	
	condicionais necessários para obter a conclusão pela
	
	regra introdução da bi-implicação (↔Eq)
Fonte: elaborada pelos autores.
�
2.6 Regras de equivalência
�
Além das regras de inferência (básicas e deriv adas) v istas anteriom ente, tam bém é possív el utilizar na dedução natural as regras baseadas em equiv alências tautológicas apresentadas na Seção 1 .6 . Essas regras são denom inadas regras de equivalência. A Tabela 1 1 , apresentada a seguir, contém as principais regras de equiv alência:
Tabela 1 1 – Regras de equiv alência
Fonte: el aborada pel os au tores.
Importante:
Note que as propriedades de equiv alência apresentadas na Seção 1 .6 são “rev ersív eis”, isto é, pode-se passar da fórm ula à esquerda do operador de equiv alência ⇔ para a fórm ula à direita deste operador e v ice-v ersa. A Tabela 1 0 já inclui todas as possibilidades de "rev ersão" das equiv alências, incluindo os dois "sentidos" possív eis de uso de cada regra de equiv alência.
Isso im plica que, diferente das regras de inferência, um a regra de equiv alência pode ser aplicada na m odificação de partes de um a fórm ula. Assim , as fórm ulas de um a regra de equiv alência são intercam biáv eis: pode-se substituir um a
�
subfórm ula de um a fórm ula por outra equiv alente sem alterar sua v alidade lógica.
Porém as regras de inferência não são reversíveis e não podem ser aplicadas a partes de uma fórmula, som ente pode-se passar da situação prev ista no esquem a de aplicação da regra, definido acim a da barra horizontal, que dev e ser "encaixado" em um a fórm ula inteira de um passo da dem onstração, para a fórm ula situada abaixo desta barra. O oposto, pela própria natureza da regra, não é perm itido.
Exemplos:
Prov ar o seguinte argum ento:
¬A ∨ B, B → C ⊢ A → C
Sem o uso das regras de equiv alência, a prov a da v alidade deste argum ento é relativ am ente com plexa:
	1
	¬A ∨ B
	hip
	2
	B → C
	hip
	3
	| A
	hip-pc
	4
	| | B
	hip-pc
	5
	| B → B
	4 -4, pc
	6
	| | ¬A
	hip-pc
	7
	| | B
	3 ,6, inc
	8
	| ¬A → B
	6 - 7 , pc
	9
	| B
	1 ,5,8, Ev
	1 0
	| C
	2,9, m p
	1 1
	A → C
	3 -1 0, pc
Por outro lado, se considerarm os a regra de equiv alência do condicional (cond), então a fórm ula da linha 1 ¬A ∨ B pode ser transform ada em A → B, tornando m uito m ais fácil a prov a do argum ento:
�
	1
	¬A ∨ B
	hip
	2
	B → C
	hip
	3
	A → B
	1 , cond
	4
	| A
	hip-pc
	5
	| B
	3 , 4, m p
	6
	| C
	2, 5, m p
	7
	A → C
	4 -6, pc
Em bora não pareça, esse argum ento é m uito sim ilar ao argum ento que prov a a v alidade do silogism o hipotético (SH), que afirm a que de P → Q e de Q → R, pode-se inferir P → R. Usando essa regra a prov a desse argum ento se torna ainda m ais sim ples:
	1
	¬A ∨ B
	hip
	2
	B → C
	hip
	3
	A → B
	1 , cond
	4
	A → C
	2, 3 , sh
Adaptado de: NOLT, 1 991 , p. 1 29 .
Outro argum ento para prov ar:
¬P ∨ ¬Q, ¬¬Q, R → P ⊢ ¬R
	Sem
	o uso das
	regras deriv adas e de equiv alência, a
	dem onstração pode ser elaborada conform e a estratégia a seguir .
	1
	¬P ∨ ¬Q
	hip
	2
	¬¬Q
	hip
	3
	R → P
	hip
	4
	| R
	hip-raa
	5
	| P
	3 , 4, m p
	6
	| Q
	2, dn
	�
7
	| P ∧ Q
	
	5, 6, cj
	8
	| ¬(P ∧ Q)
	1 , dem or
	9
	| (P ∧ Q) ∧ ¬(P ∧ Q)
	7 , 8, cj
	1 0
	¬R
	
	4 - 9, pc
	Aplicando o
	conjunto de
	regras básicas, deriv adas e de
	equiv alência, a dem onstração pode ser m ais sim ples.
	1
	¬P ∨ ¬Q
	hip
	
	2
	¬¬Q
	hip
	
	3
	R → P
	hip
	
	4
	¬Q ∨ ¬P
	1 , com
	
	5
	¬P
	2, 4, sd
	
	6
	¬R
	3 , 5, m t
	
Por fim , um a solução usando as regras hipotéticas, as regras deriv adas e de equiv alência.
	1
	¬P ∨ ¬Q
	hip
	2
	¬¬Q
	hip
	3
	R → P
	hip
	4
	| P
	hip-raa
	5
	| ¬¬P
	4, dn
	6
	| ¬Q
	1 , 5, sd
	7
	| ¬Q ∧ ¬¬Q
	2, 6, cj
	8
	¬P
	4
	-7 , pc
	9
	¬R
	3
	, 8, m t
2.7 Prova de teoremas
�
Um teorem a é sim plesm ente um argum ento que não precisa de
�
hipótese (ou prem issa) para ser v álido (ou seja, para ser sem pre v erdadeiro). Por exem plo, o seguinte argum ento é um teorem a:
P → (P ∨ Q)
prov a de um argum ento sem pre parte de um a regra hipotética (ou redução ao absurdo – RAA – ou prov a condicional – PC).
Exemplos:
No caso do teorem a a prov a pode ser feita pela regra da prov a condicional:
	1
	| P
	hip-pc
	2
	| P ∨ Q
	1
	, ad
	3
	P → (P ∨ Q)
	1
	-2, pc
Note que não há hipótese ou prem issa para esse argum ento, a linha 1 já com eça pela regra de dedução da prov a condicional.
Outro exem plo de teorem a:
A → (B→A)
Este teorem a pode ser prov ado da seguinte form a:
	1
	| A
	hip-pc
	2
	| | B
	hip-pc
	3
	| | | ¬A
	hip-raa
	4
	| | | A ∧¬A 1 ,3 , cj
	5
	| | ¬¬A
	3 -4, raa
	6
	| | A
	5, dn
	7
	| B→A
	2 -6, pc
	8
	A → (B→A) 1 -7 , pc
�
2.8 Prova de equivalências
Um a equiv alência é um teorem a sobre um abi-im plicação lógica P ↔ Q. Neste caso, para prov ar que a bi-im plicação é v álida é necessário prov ar am bos os lados da im plicação, ou seja, que de P pode-se deduzir Q e que de Q pode-se deduzir P. Neste caso P e Q são interderiv áv eis. Para prov ar a equiv alência, seguim os a m esm a estratégia usada para prov ar bi-im plicações, criando-se prov as separadas para cada lado da regra de introdução da equiv alência (↔I).
Exemplo:
(P ∨ Q) ↔ (¬P → Q)
1	| P ∨ Q	hip-pc
| ¬¬P ∨ Q 1 , dn (aplica-se a regra dn dev ido à exceção da regra indicada na Tabela 1 0.)
	3
	| ¬P → Q
	2, cond
	4
	(P ∨ Q) →
	1 -3 , pc
	
	(¬P → Q)
	
	5
	| ¬P → Q
	hip-pc
	6
	| ¬¬P ∨ Q
	5, cond
	7
	| P ∨ Q
	6, dn
	8
	(¬P → Q)
	5-7 , pc
	
	→ (P ∨ Q)
	
	9
	(P ∨ Q) ↔
	4,8, ↔I
	
	(¬P → Q)
	
2.9 Simbolização de argumentos verbais
�
Considere o argum ento:
�
“ Se as taxas de juros caírem, o mercado vai melhorar. Ou os impostos federais vão cair, ou o mercado não vai melhorar. As taxas de juros vão cair. Portanto, os impostos vão cair.”
Supondo que as proposições sim ples usadas no argum ento acim a são representadas pelos seguintes sím bolos:
M = “O m ercado v ai m elhorar”
J = “A taxa de juros v ai cair”
I = “Os im postos federais v ão cair”
Então o argum ento v erbal acim a seria equiv alente à seguinte fórm ula da lógica proposicional:
(J → M) ∧ (I ∨ ¬M) ∧ J ⊢ I
Que pode ser transform ado no seguinte argum ento form al:
J → M, I ∨ ¬M, J ⊢ I
Um a dem onstração possív el da v alidade deste argum ento form al é apresentada a seguir:
	1 .
	J → M
	hip
	2 .
	I ∨ ¬M
	hip
	3 .
	J
	hip
	4 .
	¬M ∨ I
	2, com
	5.
	M → I
	4, cond
	6 .
	J → I
	1 , 5, sh
	7 .
	I
	3 , 6, m p
Em outro exem plo, considere o argum ento:
“ Se Linus Torvalds é o criador do Linux, então ele é um ídolo. Se Linus Torvalds é o criador do Linux, então o Bill Gates não pode superá-lo. Portanto, se Linus Torvalds é o criador do Linux, ele é um ídolo e Bill Gates não pode superá-lo.”
�
As proposições usadas para representar o argum ento são:
L = “Linus Torv alds é o criador do Linux”
I = “Linus Torv alds é um ídolo”
B = “Bill Gates não pode superá-lo”
argum ento v erbal acim a seria equiv alente ao seguinte argum ento form al:
L → I, L → B ⊢ L → (I ∧ B)
Um a dem onstração possív el da v alidade deste argum ento form al é apresentada a seguir:
	1
	L → I
	hip
	2
	L → B
	hip
	3
	| L
	hip-pc
	4
	| I
	1 ,3 , m p
	5
	| B
	2,3 , m p
	6
	| I ∧ B
	4,5, cj
	7
	L → (I ∧ B)
	3 -6, pc
2.10 Questões comentadas
Nas questões apresentadas a seguir, tem os o argum ento e um a sequência de dem onstração. Em algum as questões, apresentam os m ais de um a dem onstração, pois em determ inadas estratégias utiliza-se o conjunto de regras de inferência (básicas e deriv adas) e o conjunto de regras de equiv alência.
De form a geral, com o dica para com eçarm os a elaboração da estratégia de dem onstração, dev em os listar as hipóteses e observ ar qual a fórm ula da conclusão. A partir disso, procuram os nas hipóteses onde encontram os a fórm ula da conclusão ou parte dela para considerarm os que regras aplicarem os a partir da identificação do operador principal da hipótese. Assim que identificam os o operador principal da hipótese, já selecionam os algum as regras possív eis de serem aplicadas na
�
dem onstração, bem com o já percebem os a fórm ula que será gerada. É im portante relem brar que, pelo m étodo, aplicam os um a regra por linha, além de identificarm os quais as linhas são utilizadas junto com a regra.
Com essa ideia em m ente, acom panhe as estratégias elaboradas para cada dem onstração.
Questão 1. ¬(P ∧ Q) → (R → S), R ∧ ¬S, Q → T ⊢ T
	1
	¬(P ∧ Q) → (R → S)
	hip
	2
	R ∧ ¬S
	hip
	3
	Q → T
	hip
	4
	| ¬(P ∧ Q)
	hip-raa
	5
	| R → S
	1
	, 4, m p
	6
	| R
	2, sp
	7
	| S
	5, 6, m p
	8
	| ¬S
	2, sp
	9
	| S ∧ ¬S
	7 , 8, cj
	1 0
	¬¬ (P ∧ Q)
	4 - 9, raa
	1 1
	P ∧ Q
	1
	0, dn
	1 2
	Q
	1
	1 , sp
	1 3
	T
	3 , 1 2, m p
conclusão desse argum ento é a fórm ula T. Identificam os T na hipótese da linha 3 e constatam os que operador principal é um a im plicação (→). Para inferir T aplicando a regra mp (m odus pones), tem os que encontrar outra fórm ula igual ao antecedente da hipótese da linha 3 , isto é, a fórm ula Q. Consequentem ente, identificam os Q na
hipótese da linha 1 onde o operador principal tam bém é um a im plicação. Entretanto, Q faz parte do antecedente da hipótese, então a r egr a mp talv ez não seja um a boa opção. Um a estratégia possív el é a r egr a mt (m odus tollens), que aplicada na linha 1 , gera um a fórm ula que é a negação do antecedente (¬¬(P ∧ Q)), basta term os tam bém a
fór m u l a ¬(R → S). Outra estratégia nesse caso será gerar a fór m u la ¬¬(P ∧ Q) a partir da regra r a a (redução ao absurdo),
�
contem plada na dem onstração da linha 4 até a linha 1 0. A partir disso, precisam os apenas liberar a fórm ula Q para gerarm os a fórm ula da conclusão T.
Questão 2. P ∨ (¬Q → R), ¬(P ∨ S) ∧ ¬R ⊢ Q
	1
	P ∨ (¬Q → R)
	hip
	2
	¬(P ∨ S) ∧ ¬R
	hip
	3
	¬(P ∨ S)
	2, sp
	4
	¬P ∧ ¬S
	3 , dem or
	5
	¬P
	4, sp
	6
	¬Q → R
	1 , 5, sd
	7
	¬R
	2, sp
	8
	¬¬Q
	6, 7 , m t
	9
	Q
	8, dn
A estratégia elaborada e desenv olv ida na questão 2 é sim ples. A partir da identificação da fórm ula da conclusão Q na linha 1 e do operador principal ser um a disjunção (∨), pensam os em aplicar a regra sd (silogism o disjuntiv o). Para isso, é necessário gerarm os a fórm ula ¬P, etapa apresentada da linha 3 até a linha 5. O próxim o passo segue a ideia geral, com o liberar Q da linha 6, sendo que o operador principal é um a im plicação(→). Para aplicar a regra mt (m odus tollens) na linha 6, tem os que gerar a fórm ula ¬R. Assim , geram os a fórm ula da conclusão na linha 9 .
Questão 3. (¬P ∨ ¬Q) → R, R → S ⊢ ¬S → P
	1
	(¬P ∨ ¬Q) → R
	hip
	2
	R → S
	hip
	3
	| ¬S
	hip-pc
	4
	| ¬R
	2, 3 , m t
	
	
	
�
	
	5
	| ¬(¬P ∨ ¬Q)
	1 , 4, m t
	
	
	6
	| ¬¬P ∧ ¬¬Q
	5, dem or
	
	
	7
	| ¬¬P
	6, sp
	
	
	8
	| P
	7 , dn
	
	
	9
	¬S → P
	3 - 8, pc
	
	Essa dem onstração baseia-se na dica de dedução sugerida na
	Tabela 1 0 para
	fórm ulas da
	conclusão que têm a im plicação com o
operador principal. A sugestão para elaborar a estratégia é aplicar a r e g r a pc (prov a condicional), então colocam os com o hipótese o antecedente (¬S) e deriv am os até o consequente (P).
Questão 4. (¬B → ¬A) ↔ (C ∨ D), D, ¬B, A ∨ (T ∨ ¬¬Q)
(T ∨ ¬¬Q) ∨ R
	1
	(¬B → ¬A) ↔ (C ∨ D)
	hip
	2
	D
	hip
	3
	¬B
	hip
	4
	A ∨ (T ∨ ¬¬Q)
	hip
	5
	(C ∨ D) → (¬B → ¬A)
	1 , E↔
	6
	C ∨ D
	2, ad
	7
	¬B → ¬A
	5, 6, m p
	8
	¬A
	3 , 7 , m p
	9
	T ∨ ¬¬Q
	4, 8, sd
	1 0
	(T ∨ ¬¬Q) ∨ R
	9, ad
Essa dem onstração tam bém se baseia na dica sugerida na Tabela 1 0. Com o o operador principal da fórm ula da conclusão é um a disjunção (∨), então podem os encontrar um a das fórm ulas e aplicar a regra ad (adição) para gerar a outra. Com o a hipótese da linha 4 tem parte da conclusão (T ∨ ¬¬Q), a estratégia elaborada foi liberar essa fórm ula. Para isso, foi necessário gerar a fórm ula ¬A para aplicar a regra sd (silogism o disjuntiv o), conform e m ostram as linhas da dem onstração.
�
Questão 5. (¬B ∧ ¬C) → (D → C), ¬B, C → B ⊢ ¬D
	1
	(¬B ∧ ¬C) → (D → C)
	hip
	2
	¬B
	hip
	3
	C → B
	hip
	4
	¬C
	2, 3 , m t
	5
	¬B ∧ ¬C
	2, 4, cj
	6
	D → C
	1 , 5, m p
	7
	¬D
	4, 6, m t
Solução 2 para (¬B ∧ ¬C) → (D → C), ¬B, C → B ⊢
¬D
	1
	(¬B ∧ ¬C) → (D → C)
	hip
	2
	¬B
	hip
	3
	C → B
	hip
	4
	¬B → ¬C
	3, cont
	5
	¬C
	2, 4, m p
	6
	¬B ∧ ¬C
	2, 5, cj
	7
	D → C
	1 , 6, m p
	8
	D → B
	3 , 7 , sh
	9
	¬B → ¬D
	8, cont
	1 0
	¬D
	2, 9, m p
Solução 3 para (¬B ∧ ¬C) → (D → C), ¬B, C → B ⊢
¬D
	1
	(¬B ∧ ¬C) → (D → C)
	hip
	2
	¬B
	hip
	3
	C → B
	hip
	4
	| D
	hip-raa
	
	
	
�
	5
	| ¬C
	∧ ¬C
	2, 3 , m t
	6
	| ¬B
	
	2, 5, cj
	7
	| D → C
	1 , 6, m p
	8
	| C
	
	4, 7 , m p
	9
	| C ∧ ¬C
	5, 8, cj
	1 0
	¬D
	
	4 - 9, raa
Nessa questão apresentam os 3 dem onstrações, sendo que a últim a faz uso da regra hipotética raa (redução ao absurdo). De acordo com a Tabela 1 0, a dica nesse caso é abrir a prov a tem porária colocando com o hipótese a fórm ula da conclusão sem a negação, pois se encontrarm os um a contradição, fecham os a prov a e introduzim os a negação na fórm ula da hipótese. Esses passos estão descritos na linha 4
(| D) quando abrim os a prov a, na linha 9 (| C ∧ ¬C) quando conseguim os obter um a contradição e, por fim , na linha 1 0 (¬D) que nos perm ite fechar a prov a tem porária descartando a hipótese e inferindo a fórm ula negada.
Questão 6. ¬P ∨ ¬Q, (R ∨ S) → P, Q ∨ ¬S, ¬R ⊢ ¬(R ∨ S)
	1
	¬P ∨ ¬Q
	hip
	2
	(R ∨ S) → P
	hip
	3
	Q ∨ ¬S
	hip
	4
	¬R
	hip
	5
	¬P → ¬(R ∨ S)
	2, cont
	6
	| ¬Q
	hip-pc
	7
	| ¬S
	3 , 6, sd
	8
	| ¬R ∧ ¬S
	4, 7 , cj
	9
	|¬(R ∨ S)
	8, dem or
	1 0
	¬Q → ¬(R ∨ S)
	6 - 9, pc
	1 1
	¬(R ∨ S)
	1 , 5, 1 0, E∨
�
A	estratégia	para	resolv erm os essa	questão poderia	seguir	a
�
adotada na questão 5, pois a conclusão do argum ento tam bém é um a fórm ula negada (¬(R ∨ S)). Entretanto, para apresentarm os outra estratégia e aplicarm os outro conjunto de regras, essa dem onstração tem com o base a regra E∨ (elim inação da disjunção). Pela dica de dedução da Tabela 1 0, se tem os um a fórm ula com um a disjunção, então tentam os prov ar os condicionais.
Questão 7 . (P ∨ Q) → R, S → (¬R ∧ ¬Q), S ∨ U ⊢ P → U
	1
	(P ∨ Q) → R
	hip
	2
	S → (¬R ∧ ¬Q)
	hip
	3
	S ∨ U
	hip
	4
	| P
	hip-pc
	5
	| P ∨ Q
	4, ad
	6
	| R
	1 , 5, m p
	7
	| | S
	hip-raa
	8
	| | ¬R ∧ ¬Q
	2, 7 , m p
	9
	| | ¬R
	8, sp
	1 0
	| | R ∧ ¬R
	6, 9, cj
	1 1
	| ¬S
	7 - 1 0, raa
	1 2
	| U
	3 , 1 1 , sd
	1 3
	P → U
	4 - 1 2, pc
A estratégia elaborada nessa dem onstração usa regras hipotéticas aninhadas. Com o a fórm ula da conclusão é um condicional, toam os com o base um a das dicas de construção de prov a que é iniciar a dem onstração aplicando a regra pc (prov a condicional). Partim os da hipótese P, que é o antecedente da fórm ula da conclusão.
Questão 8. P ∨ (Q ∧ R), ¬R ∨ S, S → ¬T ⊢ T → P
�
1	P ∨ (Q ∧ R)	hip
�
	2
	¬R ∨ S
	hip
	3
	S → ¬T
	hip
	4
	| T
	hip-pc
	5
	| ¬¬T
	4, dn
	6
	| ¬S
	3 , 5, m t
	7
	| R → S
	2, cond
	8
	| ¬R
	6, 7 , m t
	9
	| ¬Q ∨ ¬R
	8, ad
	1 0
	| ¬(Q ∧ R)
	9, dem or
	1 1
	| (Q ∧ R) ∨ P
	1 , com
	1 2
	| P
	1 0, 1 1 , sd
	1 3
	T → P
	4 - 1 2, pc
A estratégia elaborada nessa dem onstração usa a regra hipotética pc (prov a condicional), pois pelas dicas de construção de prov a da Tabela 1 0, quando a conclusão é um a fórm ula com a im plicação, a sugestão é abrir um a prov a tem porária colocando com o hipótese o antecedente e deriv a-se o consequente. Nessa dem onstração partim os da fórm ula T, então agora a estratégia é gerar a fórm ula P. Para isso, identificam os P com o parte da fórm ula na linha 1 e seu operador principal é a disjunção (∨). A regra utilizada para gerar P nessa solução é a regra sd (silogism o disjuntiv o).
Questão 9. P → Q, ¬Q, P ∨ R ⊢ R
	1
	P → Q
	hip
	2
	¬Q
	hip
	3
	P ∨ R
	hip
	4
	¬P
	1 , 2, m t
	5
	R
	3 , 4, sd
�
Solução 2 para P → Q, ¬Q, P ∨ R ⊢ R
�
	1
	P → Q
	hip
	2
	¬Q
	3
	P ∨ R
	hip
	4
	| ¬R
	hip-raa
	5
	| R ∨ P
	3 , com
	6
	| P
	4, 5, sd
	7
	| Q
	1 , 6, m p
	8
	| Q ∧ ¬Q
	2, 7 , cj
	9
	¬¬R
	4 - 8, raa
	1 0
	R
	9, dn
Solução 3 para P → Q, ¬Q, P ∨ R ⊢ R
	1
	P → Q
	hip
	2
	¬Q
	hip
	3
	P ∨ R
	hip
	4
	¬P ∨ Q
	1 , cond
	5
	Q ∨ ¬P
	4, com
	6
	¬P
	2, 5, sd
	7
	R
	3 , 6, sd
Apresentam os 3 soluções para essa questão. Vale ressaltar a solução 2 que usa a regra hipotética raa. Nesse caso, partim os de um a fórm ula negada (¬R) e na sequência das deriv ações encontram os a contradição (| Q ∧ ¬Q). A dedução da contradição na linha 8 no perm ite descartar a hipótese e inferir a fórm ula negada, o resultado é ¬¬R.
Questão 10. P ∨ ¬Q, R → ¬P, R ⊢ ¬Q
	1
	P ∨ ¬Q
	hip
	2
	R → ¬P
	hip
�
	3
	R
	hip
	
	4
	¬P
	2,3 , m p
	
	5
	¬Q
	1 , 4, sd
	
	Solução 2 para P ∨ ¬Q, R → ¬P, R ⊢ ¬Q
	
	
	
	
	1
	P ∨ ¬Q
	
	hip
	2
	R → ¬P
	
	hip
	3
	R
	
	hip
	4
	| Q
	
	hip-raa
	5
	| ¬¬Q
	
	4, dn
	6
	| ¬P
	
	2, 3 , m p
	7
	| ¬P ∧ ¬¬Q
	5, 6, cj
	8
	| ¬(P ∨ ¬Q)
	7 , dem or
	9
	| (P ∨ ¬Q) ∧ ¬(P ∨ ¬Q)
	1 , 8, cj
	1 0
	¬Q
	
	4 - 9, raa
	Solução 3 para P ∨ ¬Q, R → ¬P, R ⊢ ¬Q
	1
	P ∨ ¬Q
	hip
	
	2
	R → ¬P
	hip
	
	3
	R
	hip
	
	4
	| Q
	hip-raa
	
	5
	| ¬P
	2, 3 , m p
	
	6
	| ¬Q
	1 , 5, sd
	
	7
	| Q ∧ ¬Q
	4, 6, cj
	
¬Q4 - 7 , raa
Nov am ente apresentam os 3 dem onstrações possív eis para o argum ento. Nesse m om ento, acreditam os que v ocê já sabe o que dev e considerar para elaborar a estratégia de prov a. Então, fica com o exercício v ocê propor a resposta das 3 soluções.
�
Questão 11. ¬P ∨ Q, ¬S → ¬R, P ∨ (R ∧ T) ⊢ Q ∨ S
	1
	¬P ∨ Q
	hip
	2
	¬S → ¬R
	hip
	3
	P ∨ (R ∧ T)
	hip
	4
	P → Q
	1
	, cond
	5
	| P
	hip-pc
	6
	| Q
	4, 5, m p
	7
	| Q ∨ S
	6, ad
	8
	P → (Q ∨ S)
	5 - 7 , pc
	9
	| R ∧ T
	hip-pc
	1 0
	| R
	9, sp
	1 1
	| ¬¬R
	1
	0, dn
	1 2
	| ¬¬S
	2, 1 1 , m t
	1 3
	| S
	1
	2, dn
	1 4
	| Q ∨ S
	1
	3 , ad
	1 5
	(R ∧ T) → (Q ∨ S)
	9 - 1 4, pc
	1 6
	Q ∨ S
	3 , 8, 1 5, E∨
A estratégia elaborada tem com o base a aplicação da regra Ev (elim inação da disjunção). Com o precisam os gerar os condicionais, a ideia é que o consequente de cada fórm ula seja a conclusão (Q ∨ S). Com isso, tem os a fórm ula P ∨ (R ∧ T) da linha 3 e terem os que gerar
fórm ula P → (Q ∨ S) e a fórm ula (R ∧ T) → (Q ∨ S). Nov am ente, para aplicarm os a regra pc (prov a condicional) colocam os com o hipótese o antecedente da fórm ula e deriv am os até o consequente. Assim , a linha 1 6 é a aplicação da regra Ev nas linhas 3 , 8 e 1 5.
Questão 12. ¬P ∧ Q, R → P ⊢ ¬P ∧ ¬R
	1
	¬P ∧ Q
	hip
	2
	R → P
	hip
	
	
	
�
	3
	¬P
	1 , sp
	4
	¬R
	2,3 , m t
	5
	¬P ∧ ¬R
	3 , 4, cj
Solução 2 para ¬P ∧ Q, R → P ⊢ ¬P ∧ ¬R
	1
	¬P ∧ Q
	hip
	2
	R → P
	hip
	3
	¬P
	1 , sp
	4
	| R
	hip-raa
	5
	| P
	2, 4, m p
	6
	| P ∧ ¬P
	3 , 5, cj
	7
	¬R
	4 - 6, raa
	8
	¬P ∧ ¬R
	3 , 7 , cj
A estratégia aplicada nas duas soluções é ev idente, encontram os cada parte da fórm ula separadam ente e aplicam os a regra cj (conjunçao). Na solução 2 usam os a regra hipotética raa para gerar a fórm ula ¬R.
Questão 13. A ↔ Q, F ↔ R, A ∧ R ⊢ F ∧ Q
	1
	A ↔ Q
	hip
	2
	F ↔ R
	hip
	3
	A ∧ R
	hip
	4
	A → Q
	1 , E↔
	5
	R → F
	2, E↔
	6
	A
	3 , sp
	7
	R
	3 , sp
	8
	Q
	4, 6, m p
	9
	F
	5, 7 , m p
	
	
	
�
1 0	F ∧ Q	8, 9, cj
estratégia elaborada é sim ples, encontram os cada parte da fórm ula separadam ente e aplicam os a regra cj (conjunção).
Questão 14. P ∧ Q, P → R, (R ∧ S) → ¬T, Q → S ⊢ ¬T
	1
	P ∧ Q
	hip
	2
	P → R
	hip
	3
	(R ∧ S) → ¬T
	hip
	4
	Q → S
	hip
	5
	P
	1 , sp
	6
	Q
	1 , sp
	7
	R
	2, 5, m p
	8
	S
	4, 6, m p
	9
	R ∧ S
	7 , 8, cj
	10
	¬T
	3 , 9, m p
Pela orientação geral, listam os as hipóteses, identificam os a conclu são ¬ T com o parte da hipótese da linha 3 e constatam os que o operador principal é um a im plicação (→). Para inferir ¬T aplicando a r egr a mp (m odus pones), é necessário encontrar outra fórm ula com o antecedente da hipótese da linha 3 , isto é, a fórm ula R ∧ S. A estratégia para gerar R ∧ S, é inferir separadam ente a fórm ula R e a fór m u la S para aplicar a regra cj (conjunção) e inferir a fórm ula esperada R ∧ S. Para finalizar a dem onstração, aplicam os a regra mp (m odus ponens) nas linhas 3 e 9 para inferir a conclusão.
Questão 15. R → (P ∧ Q), ¬P ∨ ¬Q, R ∨ S ⊢ S
	1
	R → (P ∧ Q)
	hip
	2
	¬P ∨ ¬Q
	hip
	
	
	
�
	3
	R ∨ S
	hip
	4
	| R
	hip-raa
	5
	| P ∧ Q
	1 , 4, m p
	6
	| ¬(P ∧ Q)
	2, dem or
	7
	| (P ∧ Q) ∧ ¬(P ∧ Q)
	5, 6, cj
	8
	¬R
	4 - 7 ,raa
	9
	S
	3 , 8, sd
Apresentam os a dem onstração, agora esperam os que v ocê com ente a estratégia elaborada e quem sabe nos indica outra solução? ;-)
	Questão 16.
	(P ∧ Q) ↔ ¬R, ¬R → ¬P, ¬Q → ¬R ⊢ Q
	
	
	
	1
	(P ∧ Q) ↔ ¬R
	hip
	2
	¬R → ¬P
	hip
	3
	¬Q → ¬R
	hip
	4
	| ¬R
	hip-raa
	5
	| ¬P
	2, 4, m p
	6
	| ¬P ∨ ¬Q
	5, ad
	7
	| ¬(P ∧ Q)
	6, dem or
	8
	| ¬R → (P ∧ Q)
	1 , E↔
	9
	| ¬¬R
	7 , 8, m t
	1 0
	| R
	9, dn
	1 1
	| R ∧ ¬R
	4, 1 0, cj
	1 2
	¬¬R
	4 - 1 1 , raa
	1 3
	¬¬Q
	3 , 1 2, m t
	1 4
	Q
	1 3 , dn
Apresentam os a dem onstração, agora esperam os que v ocê com ente a estratégia elaborada e quem sabe nos indica outra solução? ;-)
�
Questão 17 . ¬(P ∧ Q) → ¬T, T ∨ (¬¬A ∧ ¬C), A → ¬E, ¬(P ∧ Q) ⊢ (A → ¬E) ∧ ¬E
	1
	¬(P ∧ Q) → ¬T
	hip
	2
	T ∨ (¬¬A ∧ ¬C)
	hip
	3
	A → ¬E
	hip
	4
	¬(P ∧ Q)
	hip
	5
	¬T
	1 , 4, m p
	6
	¬¬A ∧ ¬C
	2, 5, sd
	7
	¬¬A
	6, sp
	8
	A
	7 , dn
	9
	¬E
	3 , 8, m p
	1 0
	(A → ¬E) ∧ ¬E
	3 , 9, cj
Apresentam os a dem onstração, agora esperam os que v ocê com ente a estratégia elaborada e quem sabe nos indica outra solução? ;-)
�
CAPÍTULO 3
SENTENÇAS ABERTAS
N este capítu l o, serão apresentadas noções de sentenças abertas, apl icação dos operadores l ógicos em sentenças abertas e sentenças abertas com n variáveis. Tais conceitos estão baseados na Teoria dos Conju ntos e são apresentados ao l eitor para facil itar a com preensão da Lógica de Predicados, qu e será introdu zida nos próxim os capítu l os.
3.1 Sentenças abertas com uma variável
Intuitiv am ente, um a sentença aberta pode ser considerada um a frase que possui “espaços em brancos” que dev em ser preenchidos com "coisas" retiradas de algum conjunto predeterm inado.
Quando algum elem ento é retirado desse conjunto e “encaixado” na sentença aberta, então esta sentença deixa de ser aberta e passa a se com portar com o um a proposição sim ples, tendo um v alor lógico possív el: ou ela é um a sentença que afirm a algo v erdadeiro (proposição v erdadeira) ou um a sentença que afirm a algo falso (um a proposição falsa). Diz-se que a sentença é fechada quando isso ocorre.
Construir sentenças abertas é sim ilar a jogar um jogo de m ontar frases, em que as frases são form adas a partir de trechos sugeridos pelos participantes. Nesse tipo de jogo, por exem plo, um participante diz o início, um segundo diz o m eio e um terceiro tem que sugerir um final engraçado para a frase (m as que tam bém seja consistente com o que já foi dito). No nosso caso, podem os com eçar com algum as sentenças fechadas e depois identificar seus espaços em branco:
(a.1) “A m esa é branca.”
(b.1) “Este com putador está funcionando.”
(c.1) “O cachorro com eu sua ração.”
Estas poderiam se transform ar nas seguintes sentenças abertas:
(a.2) “ _ _ _ _ é branca.”
(b.2) “ _ _ _ _ está funcionando.”
(c.2) “ _ _ _ _ com eu sua ração.”
�
Um problem a com as frases acim a é que cada espaço em branco é igual aos outros espaços em branco. Quando existe só um a sentença (só um a frase), então geralm ente não há problem a. Porém , quando v árias sentenças são usadas em conjunto, então é necessário indicar claram ente quem pode aparecer nos espaços em branco. Por exem plo, nas frases acim a, em bora a sentença que afirm a que algo é branco ("_ _
_ é branca") pode ser usada tanto para cachorros quanto com putadores, não faz m uito sentido im aginar um cachorro "funcionando" ou um com putador que "com eu sua ração". A solução é dar “nom e” aos espaços em branco, que deixam de ser espaços e passam a ser v ariáv eis:
(a.3) “ x é branca.”
(b.3) “ y está funcionando.”
(c.3) “ z com eu sua ração.”
Usar v ariáv eis ajuda m as não resolv e o caso, porque ainda é necessário escolher tam bém de onde serão retirados os elem entos que se encaixarão na frase aberta, ou seja, que poderão ser v alores das v ariáv eis. Isso ocorre tam bém nos jogos de m ontar frases ou palav ras, que recorrem os às pessoas, coisas, objetos etc. conhecidos ou em que nos obrigam os a som ente usar as palav ras presentes em um dicionário. Não faz sentido ou, sim plesm ente não é engraçado falarm os sobre pessoas ou coisas que não conhecem os ou entendem os.
Para tanto é necessário definir o domínio das v áriav eis utilizadas nas sentenças abertas. Esse dom ínio é apenas um conjunto
	que não pode ser v azio, que define
	de
	onde
	dev em ser retirados os
	v alores de um a
	v ariáv el. No exem plo,
	v am os supor
	que x pode ser
	retirada de
	um
	conjunto que
	contém
	m óv eis, com o
	por
	exem plo:
	estantes, m esas, cadeiras etc. Os v alores da v ariáv el y , por
	sua v ez,
	pertencem
	a
	um conjunto
	que
	contém
	equipam entos com o:
com putadores, calculadoras, telefones etc. Por fim , o dom ínio de z será um conjunto de anim ais dom ésticos.
Agora, para com pletar o processo de sim bolização são atribuídos sím bolos para as afirm ações abertas e é definido a partir do dom ínio das v ariáv eis:
(a.4) P(x) para x ∈ A, onde P(x)= “ x é branco” e A é um conjunto de m óv eis.
(b.4) Q(y) para x ∈ B, onde Q(y)= “ y funciona” e B é um
�
conjunto de equipam entos.
(c.4) R(z) para x ∈ C, onde R(z)= “ z com eu a ração” e C é um conjunto de anim ais dom ésticos.
Lem bre-se que a gram ática da Língua Portuguesa (e das dem ais Linguagens naturais) div ide as frases em sujeito e predicado: o sujeito é a pessoa, objeto ou "coisa" a qual se refere o predicado da frase, enquanto o predicado diz qual ação este sujeito fez (ou sofreu). O espaço em branco das sentenças abertas (ou a v ariáv el correspondente) ocupa o lugar onde v ai o sujeito da frase.
As sentenças ou orações sim ples da Língua Portuguesa serv em para afirm ar algum a propriedade (o predicado) sobre algum a pessoa, objeto ou coisa (o sujeito). Por essa razão sentenças abertas tam bém são denom inadas predicados.
Já as sentenças abertas formais são construídas considerando-se que o sujeito da frase é substituído por um a v ariáv el. Tam bém é definido um dom ínio para essa v ariáv el, dizendo quem são os objetos, pessoas, entidades, coisas etc. que podem ser representados pela v ariáv el. O predicado restante passa a ser então a afirm ação que está sendo feita sobre algum sujeito do dom ínio.
Em term os form ais, um a sentença aberta com uma variável em um domínio D ou sim plesm ente um a sentença aberta em D é um a expressão P(x) tal que P(a) é v erdadeira (V) ou falsa (F) para todo elem en to a pertencente ao dom ínio D, ou seja, para todo a ∈ D. O dom ínio D é um conjunto não v azio que define os v alores possív eis da v ariáv el x, ou seja, ele é o dom ínio da v ariáv el x.
Sentenças abertas podem ser aplicadas a qualquer tipo de dom ínio conhecido, porém é com um que essas sentenças sejam exem plificadas e caracterizadas atrav és de proposições m atem áticas, principalm ente