Logo no início do estudo de qualquer linguagem de programação nos deparamos com a palavra “lógica”. Usualmente tal palavra é utilizada para se referir ou ao processo de elaboração de um algoritmo, ou a estruturas condicionais da linguagem, ou a operadores como E e OU. Nestes dois últimos contextos, estamos nos referindo à chamada lógica matemática. Neste artigo, abordo o básico de lógica matemática para estudantes de programação.
Tópicos
Introdução
Este artigo tem por objetivo ser um material resumido de introdução ao estudo de lógica matemática. Tentei colocar o que considero o mínimo de material de partida para quem desejar se aprofundar depois com outros materiais. É um artigo construído com base nas minhas próprias anotações quando estava estudando para entender melhor operadores lógicos quando estudava Python. Correções e sugestões são bem vindas. Aqueles que desejarem um estudo mais aprofundado, podem procurar o livro Filho, E. A. Iniciação à lógica matemática, Editora Nobel, 2002.
A lógica matemática (ou lógica simbólica ou, ainda, lógica proposicional), trata do estudo das sentenças declarativas também conhecidas como proposições. Chama-se proposição todo o conjunto de palavras ou símbolos que exprimem um pensamento de sentido completo. Por exemplo, “A Lua é um satélite da Terra” é uma proposição, assim como “\pi \gt \sqrt{5}“.
As proposições devem satisfazer aos dois princípios fundamentais seguintes:
- Princípio do terceiro excluído: uma proposição só pode ser verdadeira ou falsa, não havendo outra alternativa.
- Princípio da não contradição: uma proposição não pode ser ao mesmo tempo verdadeira e falsa.
Diz-se, então, que uma proposição verdadeira possui valor lógico V (verdade) e uma proposição falsa possui valor lógico F (falso). Os valores lógicos também costumam ser representados por 0 (zero) para proposições falsas e 1 (um) para proposições verdadeiras. Em inglês, True (T) ou False (F).
As duas proposições usadas de exemplo anteriormente são verdadeiras, mas a proposição “O número π é racional” é falsa.
Aqui alguns já irão reconhecer alguns aspectos que surgem quando começamos o estudo de alguma linguagem de programação. Boa parte das linguagens possuem um tipo de dados chamado booleano, nome derivado do matemático George Boole, que é justamente um tipo que assume apenas dois valores possíveis.
Apenas para ilustrar, vejamos alguns exemplos simples em Python:
3 > 2True
2 > 3False
a = 2
b = 2
a == bTrue
Veja que nas comparações acima temos como resultado True ou False. Podemos associar tais valores à uma variavél:
t = True
type(t)bool
Veja que o tipo é bool que vem de booleano.
Uma aplicação imediata de retornos booleanos é o controle de fluxo de estruturas condicionais. Veja o simples exemplo:
pessoas = {'João': 17,
'Maria': 20,
'Tibúrcio': 18}
idade_adulta = 18
for pessoa, idade in pessoas.items():
if idade >= idade_adulta:
print(f'{pessoa} pode consumir bebidas alcoólicas.')
else:
print(f'{pessoa} NÃO pode consumir bebidas alcoólicas.')João NÃO pode consumir bebidas alcoólicas. Maria pode consumir bebidas alcoólicas. Tibúrcio pode consumir bebidas alcoólicas.
Veja que criamos um dicionário com nomes de pessoas e suas idades e verificamos se cada pessoa possui ao menos 18 anos. Se possuir, tal pessoa pode consumir bebidas alcoólicas. Veja que há uma checagem idade >= idade_adulta. A saída de tal checagem é um booleano, só pode ser True ou False. O resultado determina o fluxo que o programa vai seguir, entrando no bloco if ou no bloco else. Vejamos o resultado da checagem para cada entrada no dicionário:
for pessoa, idade in pessoas.items():
print(idade >= idade_adulta)False True True
Alguns símbolos utilizados na lógica matemática
Já vimos que há relação do assunto com programação. Vamos nos aprofundar um pouco mais. Independentemente da linguagem que tiver contato, haverá o conceito de operadores lógicos sendo os mais conhecidos os operadores E e OU. O símbolo referente a cada operador varia de linguagem para linguagem. Em Python, por exemplo, E e OU são representados pelas palavras em inglês and e or, respectivamente. No estudo de lógica, são chamados de conjunção e disjunção.
Os operadores formam novas proposições a partir de outras. Em livros e materiais de lógica os seguintes símbolos são utilizados para os principais operadores lógicos:
| Símbolo | Significado |
|---|---|
| ~ ou \neg | negação |
| \land | conjunção |
| \lor | disjunção |
| \rightarrow | condicional |
| \leftrightarrow | bicondicional |
| \vert | tal que |
| NOR ou \downarrow | NOR |
| XOR ou \underline{\vee} | disjunção exclusiva |
| NAND ou \uparrow | NAND |
Considere a proposição “O número 6 é par e o número 8 é cubo perfeito”. Vemos em negrito uma conjunção de duas proposições: “O número 6 é par”, “O número 8 é cubo perfeito”. É comum representarmos proposições simples por letras minúsculas. Assim, poderíamos expressar a proposição composta deste exemplo como p ^ q. Mas como determinar o valor lógico de uma dada proposição composta?
Tabelas verdades
Com os operadores acima citados, proposições compostas podem ser criadas. Consequentemente, é de interesse verificar a validade lógica de uma dada proposição composta. Para isso servem as chamadas tabelas verdades.
Há diversos materiais online e livros sobre lógica matemática para quem deseja uma apresentação mais formal do assunto. Aqui neste artigo quero mostrar de uma forma mais prática, que o leitor possa replicar facilmente e até mesmo possa verificar o resultado de exercícios simples de lógica. Assim, vou utilizar um pequeno pacote Python, o ttg – truth-table-generator que, como o nome mostra, permite construir tabelas verdades.
A instalação é bem simples: pip install truth-table-generator
Para usar o ttg, os seguintes termos são utilizados como símbolos. Estão entre aspas simples para deixar explícito que o programa os recebe como strings. São apresentados os nomes em português e em ingês.
| Português | Inglês | Termo |
|---|---|---|
| negação | negation | 'not', '-', '~' |
| disjunção | logical disjunction | 'or' |
| nor | logical nor | 'nor' |
| disjunção exclusiva | exclusive disjunction | 'xor', '!=' |
| conjunção | logical conjunction | 'and' |
| nand | logical NAND | 'nand' |
| condicional | material implication | '=>', 'implies' |
| bicondicional | logical biconditional | '=' |
Precisamos importar o construtor de tabelas do pacote, denominado de Truths:
from ttg import TruthsSuponha que você gostaria de construir uma tabela verdade manualmente. Se uma proposição composta é formada por n proposições simples, a sua tabela verdade possuirá 2^n linhas. Na primeira coluna, supondo que esta possui x linhas, coloque nas \frac{x}{2} primeiras linhas V (ou qualquer referência ao valor de verdadeiro) e nas demais F (ou qualquer referência ao valor de falso). Na segunda coluna, coloque nas \frac{x}{4} primeiras linhas V nas próximas \frac{x}{4}, F e alterne assim até o fim das linhas. A linha de raciocínio prossegue para as próximas colunas. Pratique, por exemplo, com 4 proposições simples.
Verifique sua resposta com a tabela a seguir gerada pelo ttg para 4 proposições simples p, q, r e s:
print(Truths(['p', 'q', 'r', 's']))+-----+-----+-----+-----+ | p | q | r | s | |-----+-----+-----+-----| | 1 | 1 | 1 | 1 | | 1 | 1 | 1 | 0 | | 1 | 1 | 0 | 1 | | 1 | 1 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 0 | 1 | 0 | | 1 | 0 | 0 | 1 | | 1 | 0 | 0 | 0 | | 0 | 1 | 1 | 1 | | 0 | 1 | 1 | 0 | | 0 | 1 | 0 | 1 | | 0 | 1 | 0 | 0 | | 0 | 0 | 1 | 1 | | 0 | 0 | 1 | 0 | | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 0 | +-----+-----+-----+-----+
Repare que o padrão do ttg é colocar 1 como símbolo para verdadeiro e 0 para falso. Passando um parâmetro denominado ints (significando números inteiros – 0 e 1) como False a tabela passa a apresentar as palavras em inglês True e False:
print(Truths(['p', 'q', 'r', 's'], ints=False))+-------+-------+-------+-------+ | p | q | r | s | |-------+-------+-------+-------| | True | True | True | True | | True | True | True | False | | True | True | False | True | | True | True | False | False | | True | False | True | True | | True | False | True | False | | True | False | False | True | | True | False | False | False | | False | True | True | True | | False | True | True | False | | False | True | False | True | | False | True | False | False | | False | False | True | True | | False | False | True | False | | False | False | False | True | | False | False | False | False | +-------+-------+-------+-------+
Essa última forma de representação será a adotada no restante do artigo.
Operações lógicas
O ttg permite apresentar as tabelas de forma mais agradável visualmente nos Jupyter Notebooks, pois utiliza o Pandas internamente. Abaixo apresento uma função para melhorar a apresentação. Você pode alterar a função para apresentar cores ou outros efeitos. Fica o convite para fazer alterações e as compartilhar.
def df_style(logic):
"""Applies style to logical expression (logic) pandas truth table.
Text: center. Table: no index column."""
d = logic.as_pandas().style.set_table_styles(
[{'selector':'th',
'props': [('font-size', '12pt')]}]).set_properties(
**{'text-align': 'center', 'font-size': '115%'}).hide_index()
return dVamos verificar a tabela verdade para cada operador binário presente no ttg.
df_style(Truths(['p', 'q'],
['p and q', 'p or q', 'p => q', 'p = q', 'p xor q',
'p nand q', 'p nor q'],
ints=False))| p | q | p and q | p or q | p => q | p = q | p xor q | p nand q | p nor q |
|---|---|---|---|---|---|---|---|---|
| True | True | True | True | True | True | False | False | False |
| True | False | False | True | False | False | True | True | False |
| False | True | False | True | True | False | True | True | False |
| False | False | False | False | True | True | False | True | True |
São essas pequenas tabelas que costumam ser apresentadas em materiais de lógica de operadores para programação. Já vimos neste artigo que o comportamento de curto circuito de operadores pode ser compreendido a partir dessas tabelas verdades. Da mesma forma, são essenciais para o entendimento de circuitos digitais e das chamadas operações bitwise.
Vamos ver mais um exemplo de lógica. Considere que você quer construir uma tabela verdade para a proposição (p \land q) \rightarrow (p \lor q). Para praticar, construa manualmente a tabela antes de continuar.
Utilizando a forma já vista anteriormente, mas declarando uma variável para ficar mais fácil de reproduzir a tabela:
proposicao01 = Truths(['p', 'q'], ['(p and q) => (p or q)'], ints=False)
df_style(proposicao01)| p | q | (p and q) => (p or q) |
|---|---|---|
| True | True | True |
| True | False | True |
| False | True | True |
| False | False | True |
Exercício resolvido
Vamos resolver um exercício onde as formas de visualização anteriores irão se mostrar úteis. Para praticar, faça os exercícios manualmente e compare com o resultado apresentado pelo ttg a seguir.
Sendo p uma proposição verdadeira e q uma proposição falsa, qual o valor lógico
da proposição composta (p \land \neg q) \rightarrow q?
Resolução: Vamos começar declarando uma variável e apresentar uma tabela simples com print:
exercicio01 = Truths(['p', 'q'], ['(p and (~q)) => q'], ints = False)Atenção: Repare no cuidado com os parênteses, especialmente com o operador negação.
df_style(exercicio01)| p | q | (p and (~q)) => q |
|---|---|---|
| True | True | True |
| True | False | False |
| False | True | True |
| False | False | True |
O enunciado atribuiu valores lógicos específicos para as proposições simples. Podemos ver que a linha que corresponde ao contexto do enunciado é a linha 2. Logo, o valor lógico da proposição composta no contexto apresentado é Falso.
Tautologias, contradições e contingências
Tautologia é toda proposição composta cujo valor lógico é sempre verdade quaisquer que sejam os valores lógicos das proposições simples componentes. Ou seja, em qualquer contexto.
Contradição é toda proposição composta cujo valor lógico é sempre falso quaisquer que sejam os valores lógicos das proposições simples componentes. Ou seja, em qualquer contexto.
Contingência é toda proposição composta que não é tautologia nem contradição.
O ttg possui o método valuation que, por padrão, analisa a última coluna de uma tabela-verdade e avalia se é uma tautologia, contradição ou contingência. É possível passar parâmetros para valuation em tabelas com várias colunas, veja a documentação para detalhes se for de interesse.
df_style(proposicao01)| p | q | (p and q) => (p or q) |
|---|---|---|
| True | True | True |
| True | False | True |
| False | True | True |
| False | False | True |
proposicao01.valuation()'Tautology'
proposicao02 = Truths(['p'], ['p and (~p)'], ints=False)
df_style(proposicao02)| p | p and (~p) |
|---|---|
| True | False |
| False | False |
proposicao02.valuation()'Contradiction'
proposicao03 = Truths(['p', 'q', 'r'], ['(p and q) or r'], ints=False)
df_style(proposicao03)| p | q | r | (p and q) or r |
|---|---|---|---|
| True | True | True | True |
| True | True | False | True |
| True | False | True | True |
| True | False | False | False |
| False | True | True | True |
| False | True | False | False |
| False | False | True | True |
| False | False | False | False |
proposicao03.valuation()'Contingency'
Exercício resolvido
Demonstre que são tautologias as seguintes proposições compostas.
a. (p \land q) \rightarrow p
b. p \rightarrow (p \lor q)
c. [p \land (p \rightarrow q)] \rightarrow q (conhecido como modus ponens)
d. [(p \rightarrow q) \land (\neg q)] \rightarrow (\neg p) (conhecido como modus tollens)
Obs.: Essas tautologias são conhecidas como regras de inferência.
exercicio02 = Truths(
['p', 'q'],
['(p and q) => p', 'p => (p or q)',
'(p and (p => q)) => q', '((p => q) and (~q)) => (~p)'],
ints=False)df_style(exercicio02)| p | q | (p and q) => p | p => (p or q) | (p and (p => q)) => q | ((p => q) and (~q)) => (~p) |
|---|---|---|---|---|---|
| True | True | True | True | True | True |
| True | False | True | True | True | True |
| False | True | True | True | True | True |
| False | False | True | True | True | True |
Vemos que são todas tautologias. Podemos passar cada coluna para o método valuation e verificar usando o ttg também:
print(exercicio02.valuation(3))
print(exercicio02.valuation(4))
print(exercicio02.valuation(5))
print(exercicio02.valuation(6))Tautology Tautology Tautology Tautology
Equivalência lógica
Sejam p, q e r três proposições simples quaisquer. A seguir, o símbolo \Leftrightarrow é utilizado no sentido de equivalência entre a proposição anterior e a posterior ao símbolo. Duas proposições são equivalentes se possuem tabelas verdades idênticas. Assim, o leitor pode praticar construindo tabelas para as proposições antes e depois do símbolo de equivalência em cada caso a seguir e verificando que são iguais.
- Leis idempotentes
- p \land p \Leftrightarrow p
- p \lor p \Leftrightarrow p
- Leis comutativas
- p \land q \Leftrightarrow q \land p
- p \lor q \Leftrightarrow q \lor p
- Leis de identidade
- p \land V \Leftrightarrow p
- p \land F \Leftrightarrow F
- p \lor V \Leftrightarrow V
- p \lor F \Leftrightarrow p
- Leis complementares
- \neg (\neg p) \Leftrightarrow p
- p \land \neg p \Leftrightarrow F
- p \lor \neg p \Leftrightarrow V
- \neg V \Leftrightarrow F
- \neg F \Leftrightarrow V
- Leis associativas
- (p \land q) \land r \Leftrightarrow p \land (q \land r)
- (p \lor q) \lor r \Leftrightarrow p \lor (q \lor r)
- Leis distributivas
- p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)
- p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)
- Leis de absorção
- p \land (p \lor q) \Leftrightarrow p
- p \lor (p \land q) \Leftrightarrow p
- Leis de Augustus de Morgan
- \neg (p \land q) \Leftrightarrow \neg p \lor \neg q
- \neg (p \lor q) \Leftrightarrow \neg p \land \neg q
- \neg (p \land q \land r) \Leftrightarrow \neg p \lor \neg q \lor \neg r
- \neg (p \lor q \lor r) \Leftrightarrow \neg p \land \neg q \land \neg r
- Negação da condicional
- \neg (p \rightarrow q) \Leftrightarrow p \land \neg q
- Negação da bicondicional
-
\neg (p \leftrightarrow q) \Leftrightarrow (p \land \neg q) \lor (\neg p \land q)
Além disso, os seguintes termos são utilizados no estudo de condicionais:
-
\neg (p \leftrightarrow q) \Leftrightarrow (p \land \neg q) \lor (\neg p \land q)
| Proposição | Termo |
|---|---|
| p \rightarrow q | condicional |
| q \rightarrow p | recíproca |
| \neg p \rightarrow \neg q | inversa |
| \neg q \rightarrow \neg p | contrapositiva |
A condicional e a contrapositiva são equivalentes: (p \rightarrow q) \Leftrightarrow (\neg q \rightarrow \neg p)
Vamos verificar as duas primeiras leis de Morgan apresentadas e a negação da condicional com o ttg.
lei_morgan01 = Truths(['p','q'], ['~(p and q)', '(~p) or (~q)'])
lei_morgan02 = Truths(['p','q'], ['~(p or q)', '(~p) and (~q)'])
negacao_condicional = Truths(['p','q'], ['~(p => q)', 'p and (~q)'])df_style(lei_morgan01)| p | q | ~(p and q) | (~p) or (~q) |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 |
df_style(lei_morgan02)| p | q | ~(p or q) | (~p) and (~q) |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 |
df_style(negacao_condicional)| p | q | ~(p => q) | p and (~q) |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 |
Repare que as duas colunas para cada um dos três últimos exemplos são iguais, demonstrando as equivalências apresentadas.
Exercícios complementares
A seguir são sugeridos alguns exercícios. O gabarito se encontra em um notebook neste repositório. No arquivo de gabarito algumas considerações e discussões também são feitas durante as resoluções. Sugiro que resolva os exercícios manualmente em papel, para praticar e ter certeza que compreendeu o conteúdo, e depois utilize o ttg para conferir suas respostas.
Exercício 1: Construa a tabela verdade para as proposições e as classifique como tautologia, contradição ou contingência.
a. \neg p \lor \neg q
b. [ (p \land \neg q) \lor \neg r] \land [ (\neg p \lor q) \land r ]
c. (p \land q) \rightarrow (p \lor q)
d. (p \land q) \lor r
e. (p \land q) \rightarrow p
f. p \rightarrow (p \lor q)
g. [ p \land (p \rightarrow q) ] \rightarrow q
h. [ (p \rightarrow q) \land \neg q ] \rightarrow \neg q
i. (p \land q) \land \neg p
j. [ (p \lor \neg q) \land r ] \land [ (p \land q) \lor \neg r ]
k. [ (p \leftrightarrow q) \rightarrow r ] \leftrightarrow [ \neg (p \land r) \rightarrow q ]
Exercício 2: Sendo p uma proposição de valor lógico verdadeiro e q uma proposição de valor lógico falso, qual o valor lógico da proposição composta R: (p \land \neg q) \rightarrow q?
Exercício 3: Atribua valor lógico verdadeiro ou falso a cada uma das afirmações a seguir:
a. Se Marte é um planeta então 3 = 7 - 4.
b. A soma de dois números pares é um número par e 7^2 = 49.
c. 3=5 se e somente se o urso é um animal invertebrado.
d. Se 10^2 = 100 então todo número inteiro é natural.
e. 2 = 3^2 - 7 ou a Terra é plana.
f. 3 > 1 e 4 > 2
g. 3 > 1 ou 3 = 1
Exercício 4: Sejam:
- p: Londres é a capital da Inglaterra.
- q: A Torre Eiffel situa-se em Londres.
- r: O meridiano de Greenwich passa por Londres.
Traduza para a linguagem natural cada uma das proposições compostas abaixo e determine o respectivo valor lógico.
a. \neg q \land \neg p
b. \neg q \lor \neg p
c. \neg (p \land q)
d. \neg p \lor r
Exercício 5: Prove que uma condicional é equivalente a \neg (p \land q)
Exercício 6: Comprove que \neg (p \rightarrow q) é equivalente a p \land \neg q
Exercício 7: Mostre simbolicamente que são logicamente equivalentes: “Se um aluno estuda, então ele é aprovado” e “Não é verdade que um aluno estuda e não é aprovado”.
Exercício 8: Mostre simbolicamente que a negação de “Se um aluno estuda, então ele é aprovado” é “Há alunos que estudam e não são aprovados”.
Exercício 9: Considere a proposição: “Se o Edson se candidatar a presidente, então ele se elegerá”. Em qual dos casos abaixo essa proposição condicional deve ser considerada falsa?
a. O Edson se candidatou a presidente e se elegeu.
b. O Edson se candidatou a presidente e não se elegeu.
c. O Edson não se candidatou a presidente.
Exercício 10: Considere a condicional: “Se o seu dente está cariado, você precisa de um dentista”.
a. Suponha que “o seu dente não está cariado e você precisa de um dentista”. Isto significa uma negação da anterior?
b. Escreva uma proposição que não seja condicional e que corresponde à negação da proposição acima.
Exercício 11: Escreva na linguagem simbólica e verifique se são logicamente equivalentes as proposições “Se eu me chamo João, então eu passo no vestibular”, e “Eu passo no vestibular ou não me chamo João”.
Exercício 12: Sendo a proposição p \rightarrow (r \lor s) falsa e a proposição (q \land \neg s) \rightarrow p verdadeira, classifique em verdadeira ou falsa as afirmações p, q, r e s.
Exercício 13: Sabendo que as proposições p e q são verdadeiras e que a proposição r é falsa, determine o valor lógico da seguinte proposição: (\neg p \downarrow q) \land (q \uparrow \neg r)
Conclusão
Neste artigo vimos o básico de lógica matemática para programadores com o auxílio do pacote Python ttg – truth-table-generator. É um assunto vasto e com o básico demonstrado aqui quem precisar pode pesquisar mais. O notebook deste artigo e o com as respostas dos exercícios propostos se encontram neste repositório.
Até a próxima.
