Logic is a systematic way of thinking that allow us to parse the meanings of sentences and to deduce new information from old information. […] Logic is a process of deducing information correctly, not just deducing correct information.”
Página 34
Apresentação
A primeira parte desse projeto é um resumo (mais conciso e menos didático) do livro do professor Richard Hammack. O objetivo desse manual é servir como material de revisão e auxílio aos que quiserem seguir o caminho proposto no Projeto Matemática do nosso site. Quaisquer dúvidas podem ser enviadas nos comentários do projeto.
Todos os posts estão compilados em um pdf disponível no meu github. Link para download.
Proposições
O estudo da lógica começa com as proposições. Uma proposição é uma sentença ou expressão matemática que seja definitivamente verdadeira ou falsa. Em cima dessas proposições é que aplicamos a lógica para produção de novas proposições. Qualquer resultado ou teorema provado é, na verdade, uma proposição.
Aviso: Ao longo desse capítulo a palavra “proposição” vai ser repetida muitas vezes. Essa repetição é proposital. Eu quero que você internalize a importância desse conceito para a análise matemática.
Podemos usar letras para nomear proposições. Por exemplo, a proposição “se um número x é múltiplo de 6, então x é par” pode ser resumida em uma letra. Nesse caso diremos que “P” é a proposição acima. Dessa feita, sempre que dissermos P é falso ou P é verdadeiro, estamos nos referindo à proposição completa.
Quando uma proposição possuir variáveis, podemos escrevê-la de uma maneira similar às funções. No exemplo do parágrafo acima, podemos usar o símbolo P(x) para expressar que a proposição P possui uma variável x dentro dela.
Uma sentença aberta é uma proposição cuja validade depende da sua variável. Ou seja, dependendo do valor que você der para a variável, a proposição pode ser verdadeira ou falsa.
Esse livro do professor Hammack é justamente sobre o método de como se provar que uma proposição é verdade ou falsa. Existem estratégias de raciocínio que podem ser usadas para demonstrar proposições e, consequentemente, teoremas complexos. Nosso objetivo nesse curso é lhe ensinar essas técnicas.
Operadores: e, ou, não
Até agora foi dito que você pode usar proposições junto à lógica para se chegar a outras proposições. Então vamos aprender como trabalhar com mais de uma proposição por meio dos operadores lógicos.
O primeiro operador que vamos aprender é o “e“. Dadas as proposições P e Q. Podemos criar uma nova proposição através desse operador. Quando escrevemos R: P e Q, estamos criando uma nova proposição R que é composta das duas proposições P e Q. O símbolo usado para esse conectivo é o “\land“. Aqui em baixo vamos colocar a tabela-verdade desse operador (“V” significa Verdadeiro e “F” significa Falso).
Outro operador lógico clássico é o “ou”. O símbolo dele é o “\lor“. Eu sei, parece muito com o símbolo do “e” mas a gente não pode fazer nada a não ser decorar bem a distinção entre esses dois símbolos. A tabela-verdade do “ou” segue abaixo.
Atenção: o significado da palavra “ou” na linguagem do dia a dia é diferente do significado empregado no contexto da lógica. Quando usamos o conectivo “ou” na lógica, fica implícita a possibilidade de que ambas as proposições sejam verdadeiras ao mesmo tempo. Para as situações onde queremos que apenas uma proposição seja aceita mas não ambas, usamos um “ou exclusivo” (o símbolo desse é o “\oplus“) dos seguintes modos:
- ou P ou Q ;
- P ou Q , mas não ambos;
- Exatamente um de P ou Q .
O último operador que veremos é a negação. Ela inverte a condição da proposição onde é aplicada. Seu símbolo é o “\sim“. Existem outras representações desse operador: \lnot, \veebar, \dot\lor), ou seja, se uma proposição é verdadeira, ao aplicarmos a negação à ela, tornamos essa proposição falsa. A tabela-verdade desse operador é bem simples.
Proposições Condicionais
Podemos ainda combinar proposições de outra maneira. Sejam as proposições P e Q. Podemos dizer que “se P for verdadeiro, então Q também será verdadeiro”. O símbolo usado para esse conectivo se…então é o “\implies“. Uma proposição desse tipo é chamada de proposição condicional. Leia a página 43 do livro caso você esteja com dúvida sobre as últimas duas linhas da tabela-verdade. O autor dá a dica de você pensar nas proposições compostas como promessas feitas por alguém. Isso ajuda muito a entender como as tabelas-verdade são construídas.
Dica: nessa parte do livro o professor coloca bastante esforço em explicar esse conceito. Se você não conseguir entender essa tabela-verdade acima, recomendo dar uma lida na seção que começa na página 42.
Proposições Bicondicionais
Existem situações onde duas proposições são mutuamente condicionais, ou seja, P \implies Q e Q \implies P. Nesses casos usamos o conectivo “se e somente se” cujo símbolo é “\iff“. A tabela-verdade segue abaixo.
Desafio: na prática, a proposição bicondicional P \iff Q nada mais é do que a proposição composta (P \implies Q) \land (Q \implies P). Leia a seção 2.5 e volte aqui. Seu desafio é provar essa equivalência.
Tabelas-Verdade para Proposições
Agora que você sabe as tabelas-verdade de \land,\lor,\sim,\implies e \iff, você deve internalizá-las de modo a serem muito naturais ao avaliar a validade de uma proposição cuja construção utilize esses operadores.
Vamos trabalhar uma proposição composta que expressa a seguinte situação: dadas duas proposições P e Q, somente uma delas é verdadeira mas não ambas. Não existe um operador que nos permita construir uma proposição apenas com um único símbolo. Para podermos construir tal proposição temos que combinar nossos operadores do seguinte modo:
(P \lor Q) \land \sim (P \land Q)
Essa proposição pode assustar numa primeira olhada, contudo, ela expressa exatamente nossa intenção anteriormente explicitada. Podemos resumi-la como: “P ou Q ” são verdadeiras, mas não é o caso onde P e Q são verdadeiras.
A tabela-verdade dessa proposição é a seguinte:
Calma. É bem mais tranquilo do que parece. Vamos analisar essa tabela por partes. Nas primeiras duas colunas temos as proposições iniciais P e Q. Nas linhas estão as situações onde testamos o que acontece quando elas são verdadeiras ou falsas. Na segunda parte temos as proposições compostas por \lor e \land (que você já conhece a tabela-verdade). Na parte 3 temos apenas a negação da coluna (P \land Q). Se criarmos mais duas proposições do tipo Z : \ (P \lor Q) e W : \ \sim(P \land Q), podemos reduzir a última coluna como a tabela-verdade abaixo:
Que é exatamente igual à última coluna da tabela-verdade anterior. Portanto, nossa proposição é verdadeira exatamente quando P ou Q são verdadeiros mas não quando ambos são verdadeiros. Parabéns por ter entendido até aqui!
Comentário: eu peguei esse exemplo direto do livro. Contudo, eu pensei um pouco e uma equivalência a essa proposição composta (bem mais simples) seria \sim(P \iff Q)
Equivalência Lógica
Nesse meu comentário acima já vemos um exemplo de equivalência lógica. Quando temos tabelas-verdade iguais para proposições diferentes, podemos dizer que elas são logicamente equivalentes.
Esse conceito é importante porque podemos trabalhar o mesmo problema de diferentes abordagens e acabarmos chegando no mesmo resultado. Cada abordagem pode ter facilidades que queiramos explorar e que vão nos permitindo desenrolar o pensamento necessário para uma demonstração mais complexa.
Muitos teoremas matemáticos usam a forma P \implies Q. Mas, não raramente, precisamos usar a equivalência lógica e trabalhar com a proposição \sim (Q) \implies \sim (P). Para ver essa equivalência, basta construir as tabelas-verdade das duas proposições. Fica como dever de casa pra você.
Existem equivalências que são tão importantes que possuem um nome particular. As duas abaixo são chamadas de Lei de DeMorgan.
A tabela-verdade da primeira parte é:
A tabela-verdade da segunda parte é:
Nessa parte o professor elenca várias equivalências que podem ser verificadas por suas respectivas tabelas-verdade.
- P \implies Q = (\sim Q) \implies (\sim P) – Lei Contrapositiva
- \sim (P \land Q) = (\sim P) \lor (\sim Q) – Lei de DeMorgan 1
- \sim (P \lor Q) = (\sim P) \land (\sim Q) – Lei de DeMorgan 2
- P \land Q = Q \land P – Lei Comutativa 1
- P \lor Q = Q \lor P – Lei Comutativa 2
- P \land (Q \lor R) = (P \land Q) \lor (P \land R) – Lei Distributiva 1
- P \lor (Q \land R) = (P \lor Q) \land (P \lor R) – Lei Distributiva 2
- P \land (Q \land R) = (P \land Q) \land R – Lei Associativa 1
- P \lor (Q \lor R) = (P \lor Q) \lor R – Lei Associativa 2
Comentário: como são muitas equivalências, se eu colocar todas as tabelas-verdade aqui vai ficar uma poluição muito grande. Então cabe a você demonstrar todas essas equivalências por conta própria. Não confie só porque está escrito. Demonstre com seu próprio esforço todas elas.
Quantificadores
Até agora nós já vimos um punhado de símbolos que nos permitem construir proposições consideravelmente complexas, bem como achar as equivalências entre diferentes proposições. Mas ainda temos um problema para superar: o que fazer quando temos que lidar com infinitos elementos?
O professor usa o seguinte exemplo: imagine um conjunto infinito de números inteiros X = \{ x_1,x_2,x_3, \dots \}. Com os símbolos apresentados até agora, como faríamos para representar as seguintes proposições?
- Z_1: “Todos os elementos de X são ímpares”
- Z_2: “Pelo menos um elemento de X é ímpar”
Primeiro vamos definir a proposição P : “O número x é ímpar”. Para a primeira proposição (Z_1), teríamos algo parecido com
P(x_1) \land P(x_2) \land P(x_3) \land \dots
E para a segunda proposição (Z_2), algo como
P(x_1) \lor P(x_2) \lor P(x_3) \lor \dots
Ou seja, acabaríamos com proposições de tamanho infinito.
Para superar essa dificuldade, vamos introduzir os novos símbolos “\forall” e “\exists“. O símbolo \forall significa “para todo” e o símbolo \exists significa “existe algum”. Desse modo podemos reescrever as proposições anteriores como:
- Z_1: \forall x \in X, P(x)
- Z_2: \exists x \in X, P(x)
Nós chamamos esses novos símbolos de quantificadores (não sei você, mas pra mim esse daria um bom nome de banda). Esse nome é porque eles se referem a alguma propriedade da quantidade de algo. \forall é chamado de quantificador universal e \exists é chamado de quantificador existencial. Proposições que contenham esses símbolos são chamadas de proposições quantificadas.
Dica: leia o exemplo 2.5 do livro. O professor Hammack dá 4 exemplos em inglês e “traduz” esses exemplos para os símbolos que já aprendemos até agora.
Um pouco mais sobre Proposições Condicionais
Na seção 2.1 nós vimos que uma sentença aberta é uma proposição cuja validade depende do valor da variável. Contudo, uma característica que os quantificadores possuem é transformar sentenças abertas em proposições.
Dada a sentença aberta “x é par \implies x é múltiplo de 6″. A validade dessa afirmação depende totalmente do valor dado para a variável x. Agora, quando adicionamos um quantificador “\forall x \in \mathbb{Z}, x é par \implies x é múltiplo de 6″, ela se torna uma proposição, ou seja, podemos definir se ela é verdadeira ou falsa (nesse caso, falsa).
De maneira geral, dadas duas proposições Q(x) e P(x), a expressão \forall x \in \mathbb{Z}, P(x) \implies Q(x) é verdadeira ou falsa. Logo, ela é uma proposição e não uma sentença aberta.
Agora chegamos no ponto importante sobre esse assunto: sempre que você ver duas proposições a respeito de uma variável que seja elemento de algum conjunto (previamente definido), uma expressão da forma P(x) \implies Q(x) deve ser interpretada como sendo uma proposição do tipo \forall x \in Conjunto, P(x) \implies Q(x). Ou seja, se uma proposição condicional não estiver quantificada explicitamente, então existe um quantificador implícito atrelado a ela. O motivo desse quantificador não aparecer é que cansa ter que ficar escrevendo toda hora “\forall x \in Conjunto“.
Agora nós vamos definir de maneira mais geral (mas consistente com o que foi dito na seção 2.1) as proposições condicionais.
Definição (Proposição Condicional): se P e Q são proposições ou sentenças abertas, então “se P, então Q” será uma proposição. Essa proposição será verdadeira se for impossível que P seja verdadeira enquanto Q seja falsa. E será falsa se existir alguma situação onde P é verdadeira e Q é falsa.
Traduzindo Português para a Lógica Simbólica
Quando estamos lendo provas de teoremas, sempre devemos estar atentos para a estrutura lógica e o significado das sentenças. Não é raro ter que converter as expressões feitas de palavras para expressões feitas dos símbolos que estudamos até agora. Essa seção é uma prática para você exercitar essa competência.
Comentário: a partir desse ponto pode ser que você veja alguns conceitos que não foram previamente explicados no material. Não se assuste por causa disso. Foque apenas na lógica e no que você aprendeu até aqui.
Exemplo 1: O teorema do valor médio do Cálculo Infinitesimal.
Se f é contínua no intervalo [a,b] e diferenciável em (a,b), então existe um número c \in (a,b) onde f'(c) = \dfrac{f(b) - f(a)}{b - a}.
A tradução para a forma simbólica dessa afirmação é:
\left( (f cont. em [a,b]) \land (f dif. em (a,b)) \right) \implies \left(\exists c \in (a,b), f'(c) = \dfrac{f(b) - f(a)}{b - a} \right)
Eu sei, ficou meio poluído. Pra melhorar um pouco vamos definir novas proposições e limpar um pouco essa sujeira toda. P : “f é contínua no intervalo [a,b]“, Q : “f é diferenciável em (a,b)“.
\left( P \land Q \right) \implies \left(\exists c \in (a,b), f'(c) = \dfrac{f(b) - f(a)}{b - a} \right)
Exemplo 2: A conjectura de Goldbach.
Todo número inteiro par maior que 2 é a soma de dois primos.
A tradução para a forma simbólica dessa afirmação é:
\left( n \in X \right) \implies \left( \exists p,q \in P, n = p + q \right)
Ou então, podemos usar essa outra forma equivalente:
\forall n \in X, \exists p,q \in P, n = p + q
Sendo P = {x : x \ é \ primo } e X = { 4,6,8,10.\dots }.
Esse exemplo nos mostra uma relação interessante entre as proposições do tipo (n \in X) \implies Q(n) e as do tipo \forall n \in X, Q(x). Toda proposição universalmente quantificada (ou seja, com o uso do \forall) pode ser expressa como uma proposição condicional.
Fato (Equivalência de Proposições): suponha que X é um conjunto e Q(x) é uma proposição a respeito de cada x \in X. As proposições abaixo são equivalentes:
\forall x \in X, Q(x)
(x \in X) \implies Q(x)
Essas equivalências são importantes porque podemos trocar a maneira como um teorema se apresenta na hora de tentar provar ou desprovar uma proposição.
Aviso: na hora que você ler um teorema, evite ir direto para as palavras “ou”, “se”, “e” como se elas sempre significassem os seus respectivos valores lógicos. O contexto é quem diz o real significado das palavras. Sempre analise o enunciado inteiro antes de transcrever para a linguagem simbólica da lógica.
Negando Proposições
Não é raro que ao tentar demonstrar uma proposição complexa R, por exemplo, seja mais fácil trabalhar com a negação dessa proposição \sim R. Mas na frente do curso você verá que essa é uma das técnicas usadas para provar teoremas.
Também não é incomum termos que lidar com negações de proposições quantificadas. Considere a proposição \sim(\forall x \in \mathbb{N}, P(x)). Podemos ler como “não é o caso que P(x) é verdade para todos os x números naturais”. Ou seja, a negativa dessa proposição envolve outro quantificador (o de existência), de modo que podemos reescrever essa negação como \exists x \in \mathbb{N},\sim P(x).
Chegamos em um ponto importante aqui. Os quantificadores são usados para negar um ao outro. Observe as seguintes equivalências:
\sim (\forall x \in X, P(x)) = \exists x \in X, \sim P(x)
\sim (\exists x \in X, P(x)) = \forall x \in X, \sim P(x)
Comentário: se você leu com atenção até aqui, você deve ser capaz de compreender essas equivalências. Se elas não fazem sentido na sua cabeça, manda um comentário aqui em baixo explicando qual a sua dúvida. Eu posso melhorar o texto com o seu feedback.
Quando se está escrevendo demonstrações, às vezes é necessário negar proposições condicionais P \implies Q. Se você aprendeu a tabela-verdade desse tipo de operador, você sabe que a única maneira de ele ser falso é quando temos P verdadeiro e Q falso. Em termo da lógica dizemos que \sim (P \implies Q) = P \land \sim Q.
Dica: tente fazer o exercício 5 da seção 2.10. Tem a solução dele no final do livro.
Inferência Lógica
A inferência lógica é o processo de se tirar conclusões dadas as premissas e regras previamente estabelecidas. Existem algumas maneiras de se trabalhar esse processo de pensamento. O professor elenca 3 modos: modus ponens, modus tollens e eliminação.
Os diagramas acima são fáceis de se ler. Tudo que está em cima da linha é dado como verdadeiro. O que está abaixo é a consequência lógica do que está acima. É importante que você internalize esses métodos de pensamento. Você usará bastante ao longo da sua jornada pela matemática.
Nota Importante
Para finalizar, o professos elenca 3 grandes motivos para se estudar lógica: 1) As tabelas-verdade nos dizem exatamente os significados das palavras “e”, “ou”, “não”, “se…então”, etc; 2) As regras da inferência produzem um sistema onde podemos deduzir novas informações de afirmações anteriores; 3) Regras lógicas (como a lei de DeMorgan) nos ajudam a transformar proposições em formatos que sejam mais fáceis de se trabalhar e que são equivalentes.
Lógica é a linguagem-comum que toda a Matemática utiliza, então temos que ter uma boa base para poder escrever e entender a própria matemática. Durante o resto desse livro não usaremos com tanta frequência os símbolos que vimos (\land, \lor, \implies, \iff, \sim, \forall, \exists) mas sempre que ler uma passagem matemática, você deve usá-los, mentalmente ou em papel, para se certificar que você a compreendeu de uma maneira inequívoca e verdadeira.
.
Leia toda a série do Projeto Matemática aqui.
Deixe um comentário