Lógica
2014-1
Texto 18
Lógica para Ciência da Computação I
Lógica Matemática
Texto 18
Passos lógicos
Sumário
1 Limitações do Método das Tabelas
1.1 Observações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
4
2 Passos lógicos
4
2.1 Observações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Exercı́cios resolvidos . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Neste texto, iniciamos as aplicações dos conteúdos e técnicas já estudados, apresentando, em linhas gerais, uma descrição lógica da prática matemática.
Do ponto de vista da Linguagem e da Lógica Matemáticas, as atividades mais
importantes executadas pelos matemáticos são a definição (descrição) de conceitos
e a demonstração (justificativa) de resultados. Nosso objetivo principal é utilizar os
conceitos e técnicas já estudados como uma base para apresentar e discutir certas
nuances que as definições e as demonstrações possuem. Se você já estudou definições
ou demonstrações em outras disciplinas, certamente o estudo deste texto enriquecerá a visão que você tem sobre estas noções. Se você nunca estudou definições
ou demonstrações, o estudo deste texto pode ser considerado como uma porta de
entrada para estes dois aspectos fascinantes da atividade matemática.
Inicialmente, abordamos a noção de passo lógico. Depois de estudarmos este
texto, vamos ser capazes de:
– entender o que é um passo lógico;
– reconhecer passos lógicos.
1
Lógica
1
2014-1
Texto 18
Limitações do Método das Tabelas
Como vimos anteriormente, um argumento é uma sequência finita de enunciados,
em que um é considerado como conclusão e os demais são considerados como premissas — também chamadas de hipóteses — sendo que as hipóteses são consideradas
como justificativas para a conclusão:
hipótese 1
···
hipótese 2
$,
hipótese n
rz
Conclusão
Exemplo 1 São exemplos de argumentos:
Existem pessoas ricas.
Todas as pessoas ricas são felizes.
Logo, existem pessoas felizes.
Nem todas as pessoas são ricas.
Todas as pessoas ricas são felizes.
Logo, nem todas as pessoas são felizes.
(1)
(2)
Vimos também, que um argumento é válido se em qualquer contexto em que suas
premissas são simultaneamente verdadeiras, a sua conclusão também é verdadeira.
Um argumento é inválido se não é válido, isto é, se existe ao menos um contexto no
qual as suas premissas são simultaneamente verdadeiras e a sua conclusão é falsa.
Exemplo 2 O argumento (1) é válido, pois em qualquer contexto em que existem
pessoas ricas, digamos p1 , p2 , . . ., e todas as pessoas ricas são felizes, estas mesmas
pessoas p1 , p2 , . . . são felizes.
O argumento (2) é inválido, pois podemos imaginar um contexto formado por
duas pessoas, digamos p1 e p2 , de modo que: p1 não é rica; p2 é rica; p1 é feliz; e p2
é feliz.
Neste contexto, temos que nem todas as pessoas são ricas (p1 não é rica), todas
as pessoas ricas são felizes (p2 é a única pessoa rica e ela é feliz), mas todas as
pessoas são felizes (p1 e p2 são felizes).
Assim, neste contexto imaginado, as premissas de (2) são simultaneamente V e
a conclusão é F .
Se você teve dificuldades em acompanhar as explicações do Exemplo 2, não se
preocupe, pois:
Um dos principais objetivos da Lógica é elaborar métodos para, dado um
argumento, decidir se ele é válido ou não.
Melhor ainda! De uma maneira geral, buscamos elaborar métodos mecânicos
que funcionam como programas de computador, ou seja, que quando aplicados
decidem automaticamente a validade dos argumentos.
2
Lógica
2014-1
Texto 18
Já estudamos um dos métodos mecânicos mais simples para a decidir a validade
de argumentos: o Método das Tabelas para Validade. Mas, como podemos observar
a partir do contato com disciplinas matemáticas,
não é comum encontrarmos textos matemáticos nos quais a justificativa
de enunciados através de argumentos, se faz por meio de tabelas.
Isto se dá, principalmente, por dois motivos.
Tabelas são ineficientes
Embora seja um método simples que pode ser programado em um computador,
o Método das Tabelas é extremamente ineficiente. De fato, existem casos em que
para verificar a validade de argumentos relativamente pequenos, necessitamos de
tabelas muito grandes.
Exemplo 3 Consideremos o seguinte argumento:
p
p→q
q→r
r→s
s→t
t
Como este argumento possui ocorrências de 5 variáveis, para verificar a sua
validade utilizando o Método das Tabelas, devemos construir uma tabela com 32
linhas, uma para cada interpretação das variáveis. Além disso, como teremos que
calcular os valores de todos os enunciados simbolizados envolvidos na construção da
implicação
( p ∧ (p → q) ∧ (q → r) ∧ (r → s) ∧ (s → t) ) → t
associada ao argumento, esta tabela terá, no mı́nimo, 10 colunas.
4
Tabelas são insuficientes
Talvez, o motivo que mais determina a ausência de tabelas nos textos matemáticos, é que mesmo os argumentos mais simples que são utilizados na Matemática
possuem ocorrências dos quantificadores
para todo
,
existe ao menos um
(e até outras partı́culas mais complicadas).
A ocorrência de quantificadores pode nos levar imediatamente a argumentos envolvendo enunciados tão complexos que a determinação da sua validade pelo Método
das Tabelas não é uma tarefa que possa ser executada mecanicamente.
3
Lógica
2014-1
Texto 18
Exemplo 4 O Método das Tabelas não pode ser adaptado para determinar a validade de argumentos como
Zero é um número natural.
Todo número natural tem um sucessor.
O sucessor de um número natural também é um número natural.
Logo, existem infinitos números naturais.
Observe que, neste argumento, temos a ocorrência do quantificador
existe ao menos um
fazendo referência a uma quantidade infinita de elementos.
Na verdade, o Método das Tabelas para Validade não pode ser adaptado para o
tratamento de muitos argumentos importantes que possuem ocorrências de quantificadores.
1.1
Observações
Observação 1 Uma das maiores conquistas da Lógica no inı́cio do Século XX foi
um perfeito entendimento dos conectivos e quantificadores. Este trabalho foi iniciado por George Boole (1815-1864), Charles S. Peirce (1839-1914) e Gottlob Frege
(1848-1925), e apresentado sistematicamente por Bertrand Russell (1872-1970) e Alfred N. Whithead (1861-1947). Baseado nos trabalhos destes pioneiros, os lógicos
Alonso Church (1903-1995) e Alan Turing (1912-1954) provaram, de maneiras diferentes, que não existe um método simples, isto é, que pode ser programado em um
computador, para determinar se um argumento qualquer que possui ocorrências dos
conectivos e quantificadores é válido, ou não.
Observação 2 O resultado de Church e Turing só diz respeito a métodos gerais,
isto é, métodos que podem ser aplicados a quaisquer argumentos que possuem
ocorrências de conectivos e quantificadores. O mesmo resultado não impossibilita a
elaboração de métodos particulares, isto é, métodos que só decidem a validade de
argumentos de um certo tipo. Bom, a aplicabilidade do Método das Tabelas para
Validade a argumentos que só possuem ocorrências de conectivos já é uma garantia
de que métodos particulares existem.
2
Passos lógicos
Neste texto e nos dois textos que seguem, tratamos apenas de argumentos
formados por enunciados que não possuem ocorrências de quantificadores.
Uma alternativa para o Método das Tabelas para Validade surge com a tentativa
de classificar os argumentos de acordo com a dificuldade inerente na determinação
das suas validades (ou invalidades):
4
Lógica
2014-1
Texto 18
1. existem argumentos cujas validades (ou invalidades) são fáceis de determinar;
2. existem argumentos cujas validades (ou invalidades) não são tão fáceis de
determinar.
Vejamos alguns exemplos de argumentos que pertencem à primeira categoria.
Exemplo 5 (a) Consideremos o argumento
p∧q
p
Um pouco de pensamento nos leva a concluir que a validade deste argumento é
imediata.
De fato, se supomos que p ∧ q é V , ou seja, que p e q são ambos V , temos que
concluir que p é V .
Outra maneira de se convencer da validade imediata: se supomos p ∧ q : V , não
podemos ter p : F , pois se assim fosse, terı́amos p ∧ q : F , contradizendo a suposição
p∧q :V.
Como já sabemos, uma outra maneira, ainda, de justificar a validade deste argumento é construir a tabela da implicação associada ao argumento:
ϕ : (p ∧ q) → p
p
V
V
F
F
q p∧q
V
V
F
F
V
F
F
F
ϕ
V
V
V
V
Como ϕ é uma tautologia, o argumento é válido.
Esta última opção não é trabalhosa (embora um pouco maçante) pois esta tabela
tem apenas 4 linhas e 4 colunas.
(b) Consideremos o argumento
p∨q
p
Um pouco de pensamento nos leva a concluir que a invalidade deste argumento
é imediata.
De fato, se supomos que p ∨ q é V , ou seja, que ao menos um dos dois p ou q é V ,
não temos que concluir que p é V . Para ver isto, basta considerar a interpretação
em que p : F e q : V . Neste caso, temos p ∨ q : V (premissa V ) e p : F (conclusão
F ).
Também, podemos construir a tabela da implicação associada ao argumento:
ϕ : (p ∨ q) → p
5
Lógica
2014-1
p
V
V
F
F
q p∨q
V
V
F
V
V
V
F
F
Texto 18
ϕ
V
V
F
V
Como ϕ não é uma tautologia, o argumento é inválido. A tabela tem apenas 4 linhas
e 4 colunas.
(c) Consideremos o argumento
p
p→q
q
Um pouco de pensamento nos leva a concluir que a validade deste argumento é
imediata.
De fato, se supomos que p e p → q são ambos V , ou seja, que p é V e p → q não
é F , temos que concluir que q também é V .
Outra maneira de se convencer da validade imediata: se supomos p : V e p →
q : V , não podemos ter q : F , pois se assim fosse, terı́amos p → q : F , contradizendo
a suposição p → q : V .
Também, podemos construir a tabela da implicação associada ao argumento:
ϕ : (p ∧ (p → q)) → q
p
V
V
F
F
q p → q p ∧ (p → q)
V
V
V
F
F
F
V
V
F
F
V
F
ϕ
V
V
V
V
Como ϕ é uma tautologia, o argumento é válido. A tabela tem apenas 4 linhas e 5
colunas.
(d) Consideremos o argumento
p→q
q
p
Um pouco de pensamento nos leva a concluir que a invalidade deste argumento
é imediata.
De fato, se supomos que p → q e q são ambos V , não temos que concluir que p
é V . Para ver isto, basta considerar a interpretação em que p : F e q : V . Neste
caso, temos p → q : V , q : V (premissas simultaneamente V ) e p : F (conclusão F ).
Podemos construir a tabela da implicação associada ao argumento:
ϕ : ((p → q) ∧ q) → p
p
V
V
F
F
q p → q (p → q) ∧ q
V
V
V
F
F
F
V
V
V
F
V
F
6
ϕ
V
V
F
V
Lógica
2014-1
Texto 18
Como ϕ não é uma tautologia, o argumento é inválido. A tabela tem apenas 4 linhas
e 5 colunas.
(e) Consideremos o argumento
p∨q
¬q
p
Um pouco de pensamento nos leva a concluir que a validade deste argumento é
imediata.
De fato, se supomos que p ∨ q e ¬q são ambos V , ou seja, que p ∨ q é V e q é F .
Temos, então, duas alternativas, p ou q, e a segunda delas, q, não acontece. Assim,
temos que concluir que p é V .
Outra maneira de se convencer da validade imediata: se supomos p ∨ q : V
e ¬q : V , não podemos ter p : F , pois se assim fosse, terı́amos p : F e q : F ,
acarretando p ∨ q : F , contradizendo a suposição p ∨ q : V .
Podemos construir a tabela da implicação associada ao argumento:
ϕ : ((p ∨ q) ∧ (¬q)) → p
p
V
V
F
F
q p ∨ q ¬q (p ∨ q) ∧ (¬q)
V
V
F
F
F
V
V
V
V
V
F
F
F
F
V
F
ϕ
V
V
V
V
Como ϕ é uma tautologia, o argumento é válido. A tabela tem apenas 4 linhas e 6
colunas.
Os exemplos acima motivam um dos principais conceitos referentes à maneira
como os matemáticos justificam conclusões a partir de premissas: a noção de passo
lógico.
Um passo lógico é um argumento simbolizado que
1. é válido;
2. possui, no máximo, a ocorrência de três variáveis;
3. possui, no máximo, a ocorrência de três premissas e uma conclusão;
4. as suas premissas e conclusão não são enunciados muito grandes.
Ou seja, um passo lógico não é nada mais do que um argumento simbolizado
que é válido e não é muito grande. Dito ainda de outra forma: os passos lógicos são
argumentos válidos, cujas validades não dão trabalho de verificar.
7
Lógica
2014-1
Texto 18
De preferência, a validade de um passo lógico deve ser verificada por meio
de uma análise lógica das suas premissas e conclusão, como fizemos nos Exemplos 5(a), 5(c) e 5(e). Mas o ponto importante é que, no pior caso, a validade de
um passo lógico pode ser verificada por meio de uma tabela de avaliação que possui
um número relativamente pequeno de linhas e colunas.
É claro que as noções de grande e pequeno são relativas e podem variar de pessoa
para pessoa. Assim, para ter uma parâmetro preciso que determina quando estamos
diante de um passo lógico, vamos considerar que:
Uma tabela de avaliação é pequena quando possui, no máximo, 8 linhas e 16
colunas.
Assim, uma definição mais precisa de passo lógico é a seguinte:
Um passo lógico é um argumento simbolizado que
1. é válido;
2. possui, no máximo, a ocorrência de três variáveis;
3. possui, no máximo, a ocorrência de três premissas e uma conclusão;
4. a tabela de avaliação de sua implicação associada é pequena.
Vejamos alguns exemplos de passos lógicos.
Exemplo 6 Observamos que todos os argumentos abaixo possuem, no máximo, a
ocorrência de três variáveis e, no máximo, a ocorrência de três premissas e uma
conclusão.
(a) Alguns passos lógicos associados ao ¬:
¬¬p
p
,
¬(p ∧ q)
(¬p) ∨ (¬q)
,
¬(p ∨ q)
(¬p) ∧ (¬q)
O primeiro é um passo lógico, pois se supomos ¬¬p : V , temos ¬p : F e,
consequentemente, p : V .
O segundo é um passo lógico, pois se supomos ¬(p ∧ q) : V , temos p ∧ q : F e,
consequentemente, ao menos um dos dois p : F ou q : F . Daı́, ao menos um dos
dois ¬p : V ou ¬q : V . Logo, (¬p) ∨ (¬q) : V .
O terceiro é um passo lógico, pois se supomos ¬(p ∨ q) : V , temos p ∨ q : F e,
consequentemente, ambos p : F e q : F . Daı́, temos ambos ¬p : V e ¬q : V . Logo,
(¬p) ∧ (¬q) : V .
8
Lógica
2014-1
Texto 18
Observamos que estes três passos lógicos são, na verdade, equivalências.
(b) Alguns passos lógicos associados ao ∧:
p∧q
p
p∧q
q
,
,
p
q
p∧q
Já vimos o primeiro é um passo lógico, no Exemplo 5(a).
Para mostrarmos que o segundo é um passo lógico, podemos aplicar um raciocı́nio
análogo ao usado no Exemplo 5(a). De fato, se supomos p ∧ q : V , temos ambos
p : V e q : V e, consequentemente, q : V .
O terceiro é um passo lógico, pois se supomos ambos p : V e q : V , temos,
consequentemente, p ∧ q : V .
Observamos que nenhum destes três passos lógicos é uma equivalência.
(c) Alguns passos lógicos associados ao ∨:
p
p∨q
p∨q
q∨p
,
p∧q
p∨q
,
O primeiro é um passo lógico, pois se supomos p : V , temos, consequentemente,
p∨q :V.
O segundo é um passo lógico, pois se supomos p ∨ q : V , temos ao menos um dos
dois p : V ou q : V e, consequentemente, q ∨ p : V .
O terceiro é um passo lógico, pois se supomos p ∧ q : V , temos ambos p : V e
q : V , e consequentemente, p ∨ q : V .
Observamos que o segundo passo lógico é uma equivalência, mas nem o primeiro
nem o terceiro é uma equivalência.
(d) Alguns passos lógicos associados ao →:
p
p→q
q
p→q
q→r
p→r
,
,
p→q
¬q
¬p
Já vimos que o primeiro é um passo lógico, no Exemplo 5(c).
O segundo é um passo lógico, pois se supomos p → q : V e q → r : V , não
podemos ter p → r : F pois, se assim fosse, terı́amos p : V e r : F . Agora, p : V e
p → q : V nos daria q : V . Além disso, q : V e q → r : V nos daria r : V . Assim, ao
final, terı́amos p : V e r : V , o que nos daria p → r : V , contradizendo a suposição
p → r : F.
O terceiro é um passo lógico, pois se supomos p → q : V e ¬q : V , temos q : F .
Assim, temos que ter p : F , ou seja, ¬p : V .
Observamos que nenhum destes três passos lógicos é uma equivalência.
(e) Passos lógicos associados ao ↔:
p
p↔q
q
p↔q
p→q
,
9
,
p↔q
q→p
Lógica
2014-1
Texto 18
O primeiro é um passo lógico, pois se supomos p : V e p ↔ q : V , temos que p e
q têm o mesmo valor. Assim, temos que ter q : V .
O segundo é um passo lógico, pois se supomos p ↔ q : V , não podemos ter
p → q : F , pois se assim fosse, terı́amos p : V e q : F , contradizendo a suposição
p↔q :V.
Para mostrarmos que o terceiro é um passo lógico, podemos aplicar um raciocı́nio
análogo ao usado anteriormente. De fato, se supomos p ↔ q : V , não podemos ter
q → p : F , pois se assim fosse, terı́amos q : V e p : F , contradizendo a suposição
p↔q :V.
Observamos que nenhum destes três passos lógicos é uma equivalência.
2.1
Observações
Observação 3 A noção de passo lógico não é uma noção intuitiva mas, sim, uma
noção técnica. Isto é, dado um argumento simbolizado qualquer, sempre podemos
decidir se ele é um passo lógico ou não. Para isto, basta construir a tabela da sua
implicação associada e contar o número de linhas e colunas que ela possui.
Observação 4 A nossa escolha de classificar um argumento como passo lógico
quando a sua implicação associada tem, no pior caso, uma tabela com 8 linhas
e 16 colunas é inteiramente arbitrária. Poderı́amos ter, por exemplo, definido como
passos lógicos os argumentos válidos cujas implicações associadas têm tabelas com
16 linhas e 32 colunas. A nossa preferência por argumentos menores é guiada pela
prática, que mostra que seres humanos toleram razoavelmente bem a contrução de
tabelas com 8 linhas e 16 colunas, mas não mais do que isto.
Observação 5 Como já salientamos, nosso objetivo é classificar como passos lógicos
argumentos válidos que possuem tabelas pequenas, pois isto facilita a verificação de
que eles são, de fato, passos lógicos. Mas, na prática, muitas vezes é conveniente
considerarmos como passos lógicos, também, argumentos que possuem tabelas um
pouco maiores. Por exemplo, qualquer estudante de Lógica que observa que o argumento
p∧q
p
é um passo lógico, não vacila em considerar que o argumento
p∧q∧r∧s∧t
p
cuja tabela possui 32 linhas, também pode ser aceito como um passo lógico.
Nos próximos exercı́cios, vamos treinar o reconhecimento de passos lógicos. O
objetivo é justificar cada item fazendo uma análise lógica dos enunciados — baseada
na experiência e no conhecimento dos conectivos — com fizemos no Exemplo 6.
Nossa intenção não é aplicar o Método das Tabelas para Validade, embora, em se
tratando de passos lógicos, isto sempre possa ser feito.
10
Lógica
2.2
2014-1
Texto 18
Exercı́cios resolvidos
Exercı́cio 1 Mostre que os seguintes argumentos são passos lógicos.
(i)
(iv)
(vii)
¬(p → q)
p ∧ (¬q)
¬q
(p → r) ∨ (¬q)
p∧q
q∧p
(ii)
p→q
q→r
¬r
¬p
(v)
(iii)
(¬p)
q
p→q
(vi)
¬(p → (q → r))
¬r
p ∨ (q → p)
¬p
(¬q) ∨ p
Exercı́cio 2 Mostre que os seguintes argumentos não são passos lógicos.
(i)
¬(p ∧ q)
(¬p) ∧ (¬q)
(iv)
(vii)
p∨q
p∧q
(ii)
(v)
p ∨ (¬q)
p→q
p∨q
¬q
p→q
(iii)
(vi)
p→q
p∧q
p∨q
q∨r
p∨r
p
p → (¬q)
q∨r
r→s
p→s
Antes de ler a resolução, tente resolver o exercı́cio usando os conceitos estudados.
Resolução do Exercı́cio 1: (i) Suponhamos ¬(p → q) : V . Daı́, p → q : F . Daı́,
p : V e q : F . Daı́, ambos p : V e ¬q : V . Logo, p ∧ (¬q) : V . (ii) Suponhamos
p ∧ q : V . Daı́, ambos p : V e q : V . Logo, q ∧ p : V . (iii) Suponhamos ¬p : V e
q : V . Daı́, p : F . Logo, p → q : V . (iv) Suponhamos ¬q : V . Daı́, ao menos um
de p → r : V ou ¬q : V . Logo, (p → r) ∨ (¬q) : V . (v) Suponhamos p → q : V ,
q → r : V e ¬r : V . Daı́, q → r : V e r : F , e temos q : F . Daı́, p → q : V e
q : F , e temos p : F . Logo, ¬p : V . (vi) Suponhamos ¬(p → (q → r)) : V . Daı́,
p → (q → r) : F . Daı́, p : V e q → r : F . Daı́, q : V e r : F . Logo, ¬r : V . (vii)
Suponhamos p ∨ (q → p) : V e ¬p : V . Daı́, p ∨ (q → p) : V e p : F . Daı́, q → p : V .
Agora, como q → p é equivalente a (¬q) ∨ p, temos (¬q) ∨ p : V .
11
Lógica
2014-1
Texto 18
Resolução do Exercı́cio 2: (i) Considerando a interpretação dada por p : V e
q : F , temos p ∧ q : F , e assim, ¬(p ∧ q) : V (premissa V ). Mas como p : V , temos
¬p : F , e assim, (¬p) ∧ (¬q) : F (conclusão F ). (ii) Considerando a interpretação
dada por p : V e q : F , temos ¬q : V , e assim, p ∨ (¬q) : V (premissa V ). Mas
p → q : F (conclusão F ). (iii) Considerando a interpretação dada por p : F e q : V ,
temos p → q : V (premissa V ). Mas p ∧ q : F (conclusão F ). (iv) Considerando a
interpretação dada por p : V e q : F , temos p ∨ q : V (premissa V ). Mas p ∧ q : F
(conclusão F ). (v) Considerando a interpretação dada por p : V e q : F , temos
p ∨ q : V e ¬q : V (premissas simultaneamente V ). Mas p → q : F (conclusão F ).
(vi) Considerando a interpretação dada por p : F , q : V e r : F , temos p ∨ q : V e
q ∨ r : V (premissas simultaneamente V ). Mas p ∨ r : F (conclusão F ). (vii) Não
é um passo lógico, pois possui ocorrências de 4 variáveis. Lembre-se: passos lógicos
são argumentos pequenos!
c 2014 Márcia Cerioli, Renata de Freitas e Petrucio Viana
IM-UFRJ, IME-UFF
12