INTRODUÇÃO À LÓGICA E PROGRAMAÇÃO

Material de suporte para curso optativo* – Curso EM técnico integrado

IFES – campus Montanha

Guilherme Messias Pereira Lima

2023
*Proibida a utilização do material sem devida autorização do autor
 INTRODUÇÃO À LÓGICA E PROGRAMAÇÃO

CONTEÚDOS

PARTE 1 – LÓGICA MATEMÁTICA

1. Lógica formal e sistemas dedutivos............................................................................1

2. Lógica proposicional e tabelas-verdade....................................................................12

3. Teorema da completude para a lógica proposicional................................................23

4. Lógica clássica..........................................................................................................33

5. Teorias de primeira ordem e modelos.......................................................................42

6. Álgebra de Boole e Circuitos lógicos.........................................................................49

7. Sistema binário de numeração..................................................................................54

8. Funções recursivas e computabilidade.....................................................................64

9. Números ordinais finitos e a Aritmética standard......................................................68

10. Noções de Aritmética transfinita: O hotel de Hilbert e a sequência de Goodstein..82

11. Teoremas de Incompletude de Gödel e os limites para teorias formais.................95

PARTE 2 – INTRODUÇÃO À PROGRAMAÇÃO

12. Algoritmos, fluxogramas e teste de mesa

13. Máquina de Turing e computabilidade

14. Linguagens de programação

15. Iniciando e finalizando um programa em C++

16. Variáveis em C++

17. Entrada e saída de dados

18. Laços de repetição

20. Algumas funções pré-programadas em C++

21. Introdução ao estudo de métodos numéricos via programação

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 1 – Lógica Formal e Sistemas Dedutivos

O que é Lógica? O prof. Dr. Cezar Mortari nos dá uma definição sobre o que é Lógica,
no sentido mais geral, que iremos indicar agora:

Lógica é a ciência que estuda princípios e métodos de inferência, tendo o objetivo

principal de determinar em que condições certas coisas se seguem (são consequência),
ou não, de outras. (MORTARI, C. A. Introdução à Lógica. Editora UNESP, 2001. p. 02)

Os gregos dividiam a coleção de “conhecimentos” humanos em duas grandes

categorias: doxa e epistéme. No campo da doxa estavam as crenças e impressões
que os indivíduos sustentavam para si (senso comum). No campo da epistéme
estavam aqueles enunciados, que chamamos hoje em dia propriamente de
conhecimento, que foram racionalmente justificados e validados como verdadeiros.
Esta distinção era importante, pois conseguia separar o que poderia ser ilusório ou
subjetivo às experiências de um sujeito, da “realidade” última do mundo, verificada
coletivamente pela racionalidade: logos (que pode ser traduzido como RAZÃO, mas
também como LINGUAGEM)

Portanto, o homem é racional por ser capaz de se comunicar, expressar pensamentos

que, organizados de tal forma, podem ser coletivamente entendidos e validados, de
alguma forma. A área da filosofia que trata como adquirimos conhecimento é
chamada de epistemologia – o estudo de como obtém-se a epistéme.

Se usualmente considera-se CONHECIMENTO apenas aquelas crenças que foram

RACIONALMENTE validadas como verdadeiras, a lógica é a ciência que nos auxilia a
como entender de que forma devemos organizar nosso discurso para fazermos
inferências ou concluirmos coisas, a partir de certas pressuposições ou hipóteses, de
maneira RACIONALMENTE adequada.

Iremos ver mais adiante que nos últimos dois séculos, investigações no escopo da
moralidade, da teoria do direito e da política, reflexões filosóficas e em razão do
avanço da ciência, nos obrigaram a questionar a ideia de que existiria por detrás da
racionalidade UMA única lógica. Hoje em dia sabemos que existem INFINTAS
lógicas, que têm aplicações em diversas áreas das ciências humanas, assim como
nas ciências naturais e na teoria da computação (a Inteligência Artificial depende de
uma lógica chamada de probabilística, por exemplo) – o que se costuma indicar por
pluralismo lógico.

Neste nosso curso iremos estudar a lógica que por milênios foi considerada como A
única e exclusiva forma correta de raciocínio: a lógica construída sobre os princípios
aristotélicos. A partir do século XVIII, esta lógica passou por uma reformulação, mas
mantendo seus princípios; é o que chamamos de primórdios da teoria da lógica
simbólica. A lógica que Aristóteles criou, séculos antes de Cristo, preocupada

Introdução à Lógica e Programação Página 1

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

sobretudo com o estudo das formas de inferências ou raciocínios (silogismos),

recebeu um tratamento matemático, podendo ser então simbolizada.

Mas o que é um raciocínio?

Os raciocínios estão ligados à capacidade humano-cognitiva de utilizar do logos

(razão/linguagem/intelecto) para sistematicamente obter certas conclusões a partir de
determinadas premissas. Estes raciocínios determinam o método para racionalmente
JUSTIFICARMOS a veracidade destas conclusões.

Portanto, chamamos de ARGUMENTO um tipo estruturado de raciocínio, que permite

deixar claro e evidente a relação lógica entre as premissas e a conclusão que elas
sustentam, ou seja, o argumento é a formalização em uma LINGUAGEM de um
raciocínio realizado.

Lógica Aristotélica

Aristóteles (século IV A.C.) foi um discípulo de Platão, o autor dos chamados diálogos
socráticos que narram como seu mestre, Sócrates, utilizava-se de diálogos
(maiêutica) para demonstrar o erro nas crenças (doxa) de seus interlocutores,
desvelando a verdade (alethéia) através da interação racional dos diálogos
(argumentos) que buscavam alcançar o conhecimento (epistéme).

Por ser discípulo de Platão, Aristóteles sabia da importância da construção adequada

dos argumentos para garantir que eles não fossem FALACIOSOS, ou seja,
argumentos que têm aparência racional, mas que na verdade não são logicamente
adequados para justificar suas conclusões. Por isso, Aristóteles estudou de forma
sistemática a construção correta de um argumento em diversas de suas obras,
tornando mais rigorosa a abordagem ao estudo desta ciência argumentativa – a
lógica. Por isso, ele é considerado o “pai” da teoria da lógica.

Nesta época, a lógica ainda não era simbólica, como atualmente, mas era descritiva;
uma das principais contribuições de Aristóteles foi estudar as formas válidas de um
argumento ou SILOGISMO, assim como determinar as formas inválidas ou falácias, e
estabelecer os princípios lógicos (aristotélicos) ou princípios da razão, que
permaneceram inquestionáveis por mais de milênios.

SILOGISMO: E um tipo de raciocínio DEDUTIVO formado por três proposições, duas

premissas ou hipóteses e uma conclusão. É um raciocínio dedutivo, pois deduzimos
ou inferimos a conclusão a partir das premissas.

Introdução à Lógica e Programação Página 2

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Exemplo silogismo 1:

P1: Todo homem é mortal.

P2: Sócrates é um homem.

Conclusão: Sócrates é mortal.

Veja que temos um raciocínio: Se soubermos que toda coisa que for homem tem uma
determinada propriedade, a mortalidade, e se soubermos que Sócrates é um homem,
então é óbvio que Sócrates também possui a propriedade de ser mortal, ou seja, do
conhecimento das duas premissas, inferimos uma conclusão, a de que Sócrates pode
morrer.

Mas antes de continuarmos nosso estudo dos silogismos, precisamos garantir que
conseguimos diferenciar algumas coisas.

Como comentado, a lógica estuda a forma como construímos argumentos e para isso
utilizamos uma linguagem. Se pensarmos na linguagem escrita, sentenças são a
representação gráfica de certos conteúdos linguísticos ou enunciados. Por exemplo,
se uma pessoa FALA “O livro está sobre a mesa” (I), ela EXPRESSA um enunciado,
que afirma o lugar onde determinado objeto está, por meio de uma SENTENÇA na
língua portuguesa. Este mesmo enunciado pode ser expresso por outra sentença,
“The book is on the table” (II), que agora é uma sentença em inglês. As sentenças (I)
e (II) expressam o mesmo enunciado ou fato sobre o mundo, mas são sentenças
diferentes, têm grafias diferentes e também estão em linguagens diferentes.

As sentenças “Cale a boca!”, “Está chovendo”, “Você está com fome?” expressam
enunciados sobre os quais não podemos afirmar, sem nenhuma informação ou
contextualização adicional, se são VERDADEIRAS ou FALSAS. Estas sentenças não
são de interesse da lógica, como ciência. A lógica se interessa apenas pelas
sentenças que chamamos de DECLARATIVAS, que enunciam um fato sobre o mundo
sobre o qual podemos dizer ser ele verdadeiro (ser o caso) ou falso (não ser o caso).

Chamaremos então de PROPOSIÇÃO àquelas sentenças que expressam um fato

sobre o mundo (enunciado) que possui um valor de verdade, podendo ser falso ou
verdadeiro.

A lógica aristotélica está interessada somente no estudo dos silogismos que envolvem
PROPOSIÇÕES.

Agora podemos retornar ao estudo dos silogismos!

Voltemos ao exemplo do silogismo 1. Usando diagrama de Venn e conjuntos,

podemos representar este silogismo da seguinte forma:
Introdução à Lógica e Programação Página 3
 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

M é a representação do conjunto de todos os mortais, H do conjunto de homens e

Sócrates um indivíduo.

De acordo com as premissas 1 e 2 temos o diagrama representado acima. Logo,

segue da FORMA entre os componentes destas duas proposições que o indivíduo
Sócrates também pertence ao conjunto de todos os mortais, de onde concluímos que:

SE as duas premissas forem verdadeiras, ENTÃO a conclusão também será

verdadeira.

Em função desta característica de análise, costumamos também chamar a ciência

lógica de LÓGICA FORMAL – o formato adequado dos argumentos justifica a
veracidade da conclusão em função da veracidade das premissas.

Argumento válido: Um argumento é dito válido se toda a vez que as premissas

forem verdadeiras, a conclusão também o será. Esta veracidade segue-se da forma,
da relação entre os componentes das premissas e como eles estão organizados na
conclusão.

Silogismo 2:

P1: Todo gato é um mamífero.

P2: Félix é um mamífero.

Portanto, Félix é um gato.

Introdução à Lógica e Programação Página 4

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Veja que ao representarmos o conjunto dos mamíferos e dos gatos, assim como o
indivíduo Félix, de acordo com as premissas, em um diagrama, não somos capazes
de determinar se Félix está em G ou em (M – G).

Logo, a conclusão de que Félix é um gato não segue das premissas, mesmo que
ambas sejam verdadeiras – isto é, elas não justificam formalmente a veracidade da
conclusão.

Por isso, o silogismo 2 é um argumento INVÁLIDO.

Silogismo 3.

P1: Todas as criaturas de 4 pernas têm asas.

P2: Uma espécie de aranha tem 4 pernas.

Portanto, Existe uma espécie de aranhas com asas.

Se P for o conjunto das criaturas com 4 pernas, A o conjunto das criaturas com asas e
E uma espécie de aranhas, temos:

Veja que o formato das proposições nos garante que seria verdadeira a conclusão
caso as premissas fossem verdadeiras, pois o silogismo é válido.

Sabemos, contudo, que a conclusão é falsa, e isto ocorre porque a premissa 1 é

obviamente uma proposição FALSA.

Mesmo em um argumento válido, a conclusão pode ser falsa, basta que uma das
premissas seja falsa – isso decorre pelo fato de que a FORMA do argumento só
garante que a veracidade da conclusão é necessária SE as premissas forem
verdadeiras.

Introdução à Lógica e Programação Página 5

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Argumento correto: Um argumento é dito correto se ele for válido e, além disso, as
premissas forem verdadeiras. Neste caso, toda conclusão de um argumento correto é
verdadeira.

Nos nossos exemplos, os silogismos 1 e 3 são válidos, e o silogismo 2 inválido.

Todavia, somente o silogismo 1 é correto.

A lógica aristotélica estuda em detalhes todas as formas de silogismo – aqui

analisamos apenas um dos formatos possíveis. Esta teoria, a teoria dos silogismos,
foi estudada por séculos durante a Idade Média, fazia parte do estudo da lógica no
Trivium, curso que precedia o Quadrivium, ambos pré-requisitos para ingresso nos
cursos universitários da época.

Aristóteles também estudou outras formas de raciocínio, além do raciocínio silogístico

ou dedutivo. Os raciocínios por INDUÇÃO e os raciocínios por ABDUÇÃO.

Os raciocínios indutivos são muito importantes na matemática, em especial para a

teoria dos números, pois o princípio de indução é uma característica definidora dos
números ordinais. Os números ordinais finitos são os números que usualmente
chamamos de números naturais.

Sistemas Dedutivos

Aristóteles considerava a dedução o método por excelência para obtenção de

conhecimento. Até hoje, as ciências dedutivas, como a Matemática, têm status
privilegiado em relação à situação epistêmica de proposições, que independem da
experiência ou de questões subjetivas ao sujeito cognoscente.

Nas suas obras lógicas, o filósofo delineou qual deveria ser o modelo por excelência
de uma ciência dedutiva:

Partir de conceitos básicos ou definições elementares. Assumir certas verdades

básicas necessárias e a priori, auto evidentes, sobre estes conceitos básicos,
chamadas de axiomas e/ou postulados. Por fim, por meio destas definições e do uso
reiterado de silogismos válidos, obter as consequências lógicas destes conceitos e
postulados – que são chamados de TEOREMAS.

A este tipo de estrutura costumamos chamar de SISTEMA DEDUTIVO, ou sistema

formal, já que todo o conhecimento que obtemos é uma consequência dedutiva
(formal) dos conceitos iniciais adotados e dos axiomas assumidos.

Introdução à Lógica e Programação Página 6

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Euclides foi um matemático grego que viveu em torno do ano 300 A.C. Sua maior
obra, Os Elementos, consiste em uma coleção de 13 livros que sistematizou todo o
conhecimento em geometria que a cultura grega possuía até então. Mas além de
compilar este conhecimento, Euclides realizou algo a mais. Ele adotou o modelo de
ciência dedutiva, proposto por Aristóteles, para sistematizar a geometria grega. Por
isso, por ele ser o responsável por dar um tratamento formal a esta teoria, usualmente
chamamos tal geometria de Geometria Euclidiana.

Partindo de conceitos básicos como ponto, reta e plano, e de alguns axiomas e

postulados considerados como evidentes e que não precisariam ser PROVADOS ou
DEMONSTRADOS, como o postulado que afirma que “Dados dois pontos distintos,
existe uma e somente uma única reta passando entre eles”, Euclides conseguiu
deduzir, aplicando regras de inferência (regras dedutivas) todos os resultados
conhecidos sobre a geometria até aquele momento, obtendo assim os Teoremas de
sua obra, por exemplo, o teorema que afirma que “dado um triângulo retângulo, a
medida da hipotenusa ao quadrado é igual à soma dos quadrados das medidas dos
catetos” (Teorema de Pitágoras).

Esta obra permaneceu, por mais de 2000 anos, como paradigma não só do espírito
de investigação matemática – uma ciência dedutiva sobre verdades necessárias -,
mas também sobre a única possibilidade de se desenvolver uma ciência geométrica –
e, portanto, física.

Porém, no séculos XVII e XVIII, questionamentos sobre seus alicerces, em especial

sobre o quinto postulado, que afirmava “que duas retas paralelas não possuem
pontos em comum”, revolucionaram não só a ciência da geometria, como os
fundamentos da matemática e das ciências naturais, com o surgimento e a
consolidação das Geometrias não-euclidianas – que permitiram uma análise sobre os
fundamentos da matemática, dos princípios lógicos e também abriram caminho para
teorias sobre o universo como a Teoria de Relatividade (que precisa de uma
geometria não-euclidiana para explicar os fenômenos físicos).

Por fim, o que é um sistema dedutivo?

Além da definição dada no início do capítulo, uma definição mais geral, no sentido
aristotélico, atualmente usamos o termo lógica como sinônimo para sistema dedutivo,
isto é:

1. Uma linguagem, na qual escrevemos nossos argumentos;

2. Um conjunto de definições iniciais e axiomas, verdades elementares que são

aceitas, sem necessitar de demonstração;

Introdução à Lógica e Programação Página 7

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

3. Um conjunto de regras de inferência, formas de argumentos válidos neste sistema

dedutivo, que permitem obtermos certas conclusões a partir de determinadas
premissas (processo válido de inferência).

Com isso, conseguimos demonstrar, provar dedutivamente, resultados, teoremas de

nosso sistema dedutivo, cuja verdade depende exclusivamente da verdade das
premissas de nossos argumentos.

Iremos formalizar a ideia de sistema dedutivo posteriormente, dando alguns

exemplos. Mas a Matemática nos dá o exemplo primordial de um sistema dedutivo: i.
temos uma linguagem, no qual podemos escrever sentenças; ii. temos algumas
verdades básicas “evidentes” ou que assumimos serem verdadeiras, considerando
nossas necessidades e iii. com algumas regras de inferência (como o modus ponens
ou a redução ao absurdo, por exemplo), podemos demonstrar, provar ou deduzir
(todas estas palavras são sinônimas) outras verdades matemáticas – naquela teoria.
Estes resultados são chamados de teoremas ou proposições (em geral, proposições
são teoremas mais “simples”), assim como lemas (proposições mais simples que
ajudam a demonstrar um teorema) ou os corolários (consequência direta da aplicação
de um teorema). Logo, um livro de matemática sempre começa com definições,
alguns axiomas e depois uma sucessão de resultados, os famosos teoremas, que
podemos provar aplicando as regras lógicas de dedução.

O Sistema-MIU

Consideremos que temos uma linguagem formada somente pelas letras M, I e U, ou

seja, só podemos formar “palavras” com estas três letras.

No Português, se escrevermos a “palavra” AEIBRA não estamos comunicando nada,

pois AEIBRA é só uma sequência de letras que não possui sentido. Da mesma forma,
em um sistema dedutivo, quando temos uma linguagem, precisamos deixar claro
quais são as regras que garantem se uma sequência de símbolos tem ou não
significado dentro do sistema formal estudado.

No sistema-MIU, quaisquer concatenações das letras formam uma palavra “com

sentido”, desde que seja observado a ordem das letras. Por exemplo, MUUI e IMUU
são duas palavras distintas de nossa linguagem.

Os teoremas de nosso sistema dedutivo serão todas as palavras obtidas de forma

legítima, isto é, ou é uma palavra legítima dada (um axioma do sistema), ou uma
palavra legítima obtida a partir de outras palavras legítimas, pela aplicação de certas
regras (regras de inferência).

Introdução à Lógica e Programação Página 8

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

A única palavra legítima dada é a palavra MI, ou seja:

AXIOMA do sistema-MIU: MI é uma palavra legítima.

As nossas regras de inferência serão quatro, isto é, a única forma de obter outras
palavras legítimas será pela aplicação destas regras em outras palavras legítimas.

• REGRA I. Se a sua palavra termina com a letra “I”, você pode obter outra
acrescentando “U” no final da sua palavra.

Exemplo: A partir de MI podemos obter a palavra MIU.

• REGRA II. Se sua palavra é da forma M𝑥, com 𝑥 representando uma

sequência qualquer de letras, você pode obter outra palavra duplicando a
sequência 𝑥, isto é, você obtém a nova palavra M𝑥𝑥.

Exemplo: A partir de MIU podemos obter a palavra MIUIU.

• REGRA III. Se a sequência de letras “III” aparecer em sua palavra, você pode
substituí-la pela letra “U”.

Exemplo: A partir de MIUIII podemos obter a palavra MIUU.

Note que esta regra vale só em um sentido, de MIUU NÃO podemos obter a palavra
MIUIII.

REGRA IV: Se q sequência “UU” ocorrer internamente em uma de suas palavras,

você pode obter uma nova palavra apagando esta sequência.

Exemplo: A partir de MUUUII você pode obter MUII.

Aqui acabam as explicações sobre o sistema-MIU. A partir da única palavra legítima

inicial MI, todas as outras palavras legítimas (teoremas) deste sistema dedutivo só
podem ser obtidas se aplicarmos as regras de inferência em outras palavras
legítimas.

EXEMPLO: Mostrar que a palavra MUIIU é uma palavra legítima.

Para isso, precisamos mostrar que esta palavra é um TEOREMA do nosso sistema
dedutivo, ou seja, precisamos encontrar uma dedução desta palavra, ou inferência ou
derivação, usando somente o axioma (a palavra MI) e a aplicação de uma das quatro
regras de inferência.

Introdução à Lógica e Programação Página 9

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

(1) MI AXIOMA

(2) MII Aplicação da regra II na linha (1)

(3) MIIII Aplicação da regra II na linha (2)

(4) MIIIIU Aplicação da regra I na linha (3)

(5) MUIU Aplicação da regra III na linha (4)

(6) MUIUUIU Aplicação da regra II na linha (5)

(7) MUIIU Aplicação da regra IV na linha (6)

Enigma: Será que a palavra MU é uma palavra legítima do sistema-MIU, i.e., será
que podemos obter uma derivação desta palavra usando as regras de inferência?

Em capítulos posteriores iremos retornar a este problema, mas que tal pensar um
pouco sobre ele?

EXERCÍCIOS

1. Avalie se os argumentos a seguir são válidos ou inválidos. Em caso de serem

válidos, diga se são corretos.

a. Alguns vendedores não são corteses.

Todos os verdadeiros cavalheiros são corteses.

Portanto, alguns vendedores não são verdadeiros cavalheiros.

b. Nenhum quadrado é um trapézio.

Todo trapézio é um paralelogramo.

Portanto, nenhum quadrado é um paralelogramo.

c. Todos os homens são capazes de sorrir.

Todos os homens são mortais.

Portanto, todos os seres capazes de sorrir são mortais.

Introdução à Lógica e Programação Página 10

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

d. Alguns times de futebol não são bons perdedores.

Nenhum time de basquetebol é um time de futebol.

Portanto, alguns bons perdedores não são times de basquetebol.

2. A partir do axioma MI, aplique a regra II três vezes. Por fim, aplique a regra I.
Agora, aplique a regra IV. Qual teorema do sistema-MIU você demonstrou?

3. Aplicando a regra I no axioma MI, qual teorema do sistema-MIU conseguimos

demonstrar?

4. Avaliando o que você fez nos exercícios 2 e 3, responda: É possível

demonstrarmos um mesmo teorema em um sistema dedutivo de mais de uma
maneira?

Introdução à Lógica e Programação Página 11

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 2 - Lógica proposicional e tabelas-verdade

Podemos formalizar a teoria aristotélica dos silogismos em um sistema formal

denominado “Lógica proposicional”. Esta lógica analisa o que podemos inferir usando
os princípios lógicos aristotélicos, considerando como base da linguagem apenas
aquilo que podemos representar por meio de proposições.

Mas quais são os princípios lógicos aristotélicos, ou princípios da lógica clássica?

Princípio da identidade: Princípio primeiramente exposto por Parmênides, o eleata,

este princípio afirma que “todo objeto é idêntico a si mesmo”. Este princípio não pode
ser formalizado na lógica proposicional, é preciso uma lógica quantificada para sua
formalização.

Princípio da não-contradição: No mundo não podem existir dois fatos contraditórios,

isto é, se p representar uma proposição, nunca será possível ser verdadeiro que p e
não-p ocorram ao mesmo tempo.

Princípio do terceiro excluído: Dado uma proposição p, existem somente duas

possibilidades, ou esta proposição é verdadeira, ou ela é falsa. Não há um terceiro
“valor de verdade”.

A física quântica ou modernas teorias psicológicas contrariam o princípio da

identidade; o princípio da incerteza de Eisenberg ou a dualidade onda-partícula da
luz, na teoria contemporânea da física, contrariam o princípio da não-contradição; a
computação quântica, por exemplo, contraria o princípio do terceiro excluído.

Todos estes campos de pesquisa operam em um contexto racional diferente do

contexto clássico, e é por isso que existem outras lógicas formalizadas, lógicas rivais
à lógica clássica, com suas leis e princípios próprios. Estas lógicas dão suporte
racional para estes campos de pesquisa em que os princípios racionais clássicos não
são válidos. Dizemos que estas lógicas são “lógicas não-clássicas”.

Porém, nos restringiremos a estudar a lógica clássica, em que estes três princípios
são válidos, e neste capítulo, em especial, estudaremos a lógica proposicional (no
contexto da lógica clássica, que também é chamada de “Cálculo sentencial”).

Introdução à Lógica e Programação Página 12

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Lógica Proposicional

1. Seja L a linguagem da lógica proposicional, um sistema dedutivo. Esta linguagem

tem alguns símbolos:

Símbolos não-lógicos: chamamos os símbolos que representam proposições como

variáveis proposicionais, denotam noções atômicas da linguagem, por exemplo:

p pode representar a proposição “Está chovendo agora” e q pode representar a

proposição “A rua está molhada”.

Símbolos lógicos: chamamos de símbolos lógicos os conectivos da linguagem,

utilizados para construção de proposições complexas a partir da composição de
símbolos atômicos ou variáveis proposicionais.

Conectivo negação: ¬

Exemplo: ¬𝑝 representaria, em nosso exemplo, a proposição “Não está chovendo

agora”.

Conectivo conjunção: ∧

Exemplo: 𝑝 ∧ 𝑞 representaria, em nosso exemplo, a proposição “Está chovendo agora

e a rua está molhada”.

Conectivo disjunção: ∨

Exemplo: 𝑝 ∨ 𝑞 representaria, em nosso exemplo, a proposição “Está chovendo agora

ou a rua está molhada”.

Conectivo implicação material: →

Exemplo: 𝑝 → 𝑞 representaria, em nosso exemplo, a proposição “Se está chovendo

agora então a rua está molhada”.

Símbolos de pontuação: Usamos os parênteses “(“ e “)” para distinguir algumas

fórmulas, por exemplo, ¬𝑝 ∧ 𝑞 é fórmula diferente de ¬(𝑝 ∧ 𝑞).

Além dos símbolos da linguagem, precisamos de algumas regras para garantir qual
concatenação de símbolos tem sentido nesta linguagem, o que chamamos
usualmente de fórmulas bem formadas.

O método para definir o que são fórmulas bem formadas é chamado de método por
indução no comprimento ou complexidade das fórmulas. Este método é muito
utilizado na Matemática, pois parte de uma definição básica, (complexidade 0) e induz
a definição para elementos mais complexos, partindo da noção de indução, que
afirma: Certa classe tem uma propriedade indutiva P quando, se P vale para uma
classe de complexidade n, então ela também vale para a classe de
complexidade n + 1.

Introdução à Lógica e Programação Página 13

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Regra 1 (base da indução): Variáveis proposicionais são fórmulas bem formadas.

Regra 2 (Passo indutivo sobre os conectivos): Se 𝛼 e 𝛽 forem fórmulas bem

formadas, então

a. ¬𝛼 é fórmula bem formada.

b. 𝛼 ∧ 𝛽 é fórmula bem formada.

c. 𝛼 ∨ 𝛽 é fórmula bem formada.

d. 𝛼 → 𝛽 é fórmula bem formada.

e. (𝛼) é fórmula bem formada.

Nada mais é fórmula bem formada.

2. Vários conjuntos de axiomas podem ser adotados para a lógica proposicional, por
isso dizemos que esta lógica pode ser axiomatizada de várias formas diferentes.
Porém, demonstra-se que todas estas coleções de axiomas são equivalentes entre si,
ou seja, no final, elas demonstram exatamente os MESMOS teoremas, resultando,
portanto, na mesma lógica ou sistema dedutivo.

Segue uma possível axiomatização para a lógica proposicional:

(Esquema de) Axioma 1. (𝐴 ∧ 𝐵) → 𝐵

(Esquema de) Axioma 2. 𝐴 → (𝐴 ∨ 𝐵)

(Esquema de) Axioma 3. (𝐴 ∨ 𝐵) → (𝐵 ∨ 𝐴)

(Esquema de) Axioma 4. (𝐴 → 𝐵) → ((𝐶 ∨ 𝐴) → (𝐶 ∨ 𝐵))

3. Regras de inferência

Para a lógica proposicional, costuma-se adotar somente uma única regra de

inferência (primitiva), a regra Modus Ponens.

Das fórmulas 𝐴 → 𝐵 e 𝐴 podemos inferir a fórmula 𝐵

Quando uma fórmula é deduzida a partir de um conjunto de outras fórmulas,

representamos tal relação pode meio do símbolo ⊢

Por exemplo, a regra Modus Ponens pode ser descrita da seguinte forma:

{𝐴 → 𝐵, 𝐴} ⊢ 𝐵

Introdução à Lógica e Programação Página 14

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Esta notação nos diz que a fórmula B é deduzida, ou inferida, das fórmulas 𝐴 → 𝐵 e 𝐴,
que são as hipóteses que sustentam a conclusão 𝐵.

Estas três estruturas, linguagem, axiomas e regras de inferência, caracterizam o

sistema dedutivo chamado de lógica proposicional. Esta é uma estrutura SINTÁTICA,
pois diz respeito, somente, a uma abordagem puramente formal à noção de inferência
lógica. Note que não falamos nada sobre o SIGNIFICADO dos símbolos da linguagem
e nem mencionamos nada sobre noções semânticas como verdade ou falsidade.

Quando uma fórmula pode ser deduzida SEM nenhuma hipótese, usando somente os
axiomas da lógica proposicional, dizemos que esta fórmula é um TEOREMA.

Se 𝛼 for teorema denotamos por ⊢ 𝛼, i.e., a fórmula 𝛼 é deduzida sem qualquer

hipótese (conjunto vazio).

Exemplo: A fórmula (𝑝 ∨ (((𝛼 ∧ 𝛽) → 𝛽) ∧ 𝛾)) → (𝑝 ∨ 𝛾) é um teorema da lógica

proposicional, para 𝑝 variável proposicional, 𝛼, 𝛽 e 𝛾 fórmulas bem formadas
quaisquer.

Para demonstrar este resultado, precisaríamos encontrar uma PROVA ou DEDUÇÃO

dela, usando somente os axiomas e a regra de inferência Modus Ponens.

(1) (((𝛼 ∧ 𝛽) → 𝛽) ∧ 𝛾) → 𝛾 Axioma 1

(2) ((((𝛼 ∧ 𝛽) → 𝛽) ∧ 𝛾) → 𝛾) → ((𝑝 ∨ (((𝛼 ∧ 𝛽) → 𝛽) ∧ 𝛾)) → (𝑝 ∨ 𝛾)) Axioma 4

(3) (𝑝 ∨ (((𝛼 ∧ 𝛽) → 𝛽) ∧ 𝛾)) → (𝑝 ∨ 𝛾) MP (1) + (2)

Portanto ⊢ (𝑝 ∨ (((𝛼 ∧ 𝛽) → 𝛽) ∧ 𝛾)) → (𝑝 ∨ 𝛾)

Veja que esta dedução foi bem curta. Mas a grande maioria dos teoremas pode dar
um certo “trabalho” para que encontremos quais axiomas e qual a ordem de inferência
a ser utilizadas para obtermos sua dedução (lembre-se do sistema-MIU). Será que
podemos “simplificar” o encontro dos teoremas da lógica proposicional?

Introdução à Lógica e Programação Página 15

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Abordagem semântica e Tabelas-verdade

Há uma outra abordagem para sistemas lógicos, envolvendo não mais noções
sintáticas, mas noções semânticas, sentido, verdade e falsidade. Quando analisamos
a semântica dos conectivos da linguagem, compreendemos melhor sua aplicação.

A semântica mais utilizada para a lógica proposicional é aquela proposta pelo filósofo
Ludwig Wittgenstein, em contraposição a semânticas mais antigas, porém mais
abstratas, como a álgebra de Boole. Tal semântica é chamada de tabelas-verdade.

Suponhamos que uma variável proposicional represente um fato atômico, simples,

sobre o mundo. Dizemos que este fato é verdadeiro se constatarmos que ele ocorre
no mundo. Considerando o princípio do terceiro excluído, cada variável proposicional
pode ter somente dois valores de verdade, ou ela é verdadeira (o fato que representa
obtém) ou ela é falsa (o fato não obtém); se p for uma variável que represente a
proposição “Carlos está atrasado”, então p é verdadeira se Carlos estiver atrasado, ou
p é falsa se Carlos não estiver atrasado. Determinar como constatamos se p é
verdadeira ou falsa não é uma tarefa exclusiva da lógica, mas depende da
epistemologia, da linguística, da psicologia etc.

Portanto, podemos construir as tabelas de verdade para todos os conectivos da lógica

proposicional.

NEGAÇÃO: Como o conectivo é aplicado em apenas uma fórmula, esta tabela de

verdade tem somente DUAS linhas:

𝑝 ¬𝑝
V F
F V

Quando 𝑝 representa uma proposição verdadeira, ou seja, um fato real sobre o

mundo, então não-p é uma proposição falsa sobre o mundo, pois a lógica
proposicional é BIVALORADA.

CONJUNÇÃO: Como o conectivo é aplicado em duas fórmulas, esta tabela de

verdade tem 2 x 2 = 4 linhas:

𝑝 𝑞 𝑝∧𝑞
V V V
V F F
F V F
F F F

Quando 𝑝 e 𝑞 representam duas proposições, a conjunção delas é verdadeira, ou

seja, 𝑝 E 𝑞 é uma proposição verdadeira somente se ambas as proposições forem
verdadeiras.

Introdução à Lógica e Programação Página 16

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

DISJUNÇÃO: Como o conectivo é aplicado em duas fórmulas, esta tabela de verdade

tem 2 x 2 = 4 linhas:

𝑝 𝑞 𝑝∨𝑞
V V V
V F V
F V V
F F F

Quando 𝑝 e 𝑞 representam duas proposições, para que a disjunção delas seja

verdadeira, ou seja, 𝑝 OU 𝑞 ser uma proposição verdadeira, basta que uma delas o
seja.

Observação: Existe outro tipo de disjunção na linguagem usual chamada de disjunção

exclusiva, que pode ser representada na lógica pelo símbolo . Este símbolo
significa que ou p é verdadeira, ou q é verdadeira, e SOMENTE uma delas, o que
exclui a possibilidade das duas serem verdadeiras ao mesmo tempo.

IMPLICAÇÃO MATERIAL: Como o conectivo é aplicado em duas fórmulas, esta

tabela de verdade tem 2 x 2 = 4 linhas:

𝑝 𝑞 𝑝→𝑞
V V V
V F F
F V V
F F V

Quando 𝑝 e 𝑞 representam duas proposições; para que a implicação material seja

verdadeira, ou seja, Se 𝑝 ENTÃO 𝑞 ser uma proposição verdadeira, basta que 𝑝 seja
falsa ou que 𝑞 seja verdadeira. Veja alguns exemplos para entender melhor este
conectivo:

Sejam 𝑝 a proposição “Choveu com dia ensolarado” e 𝑞 a proposição “Apareceu o

arco-íris no céu”.

A proposição 𝑝 → 𝑞 representa a proposição “Se choveu com dia ensolarado então

apareceu o arco-íris no céu”.

Quando é que esta proposição seria falsa? Somente se tivéssemos um CONTRA-

EXEMPLO para ela, ou seja, um momento em que, mesmo chovendo com o dia
ensolarado, ainda assim o arco-íris não tenha aparecido no céu, ou seja, quando a
proposição 𝑝 é verdadeira e a proposição 𝑞 é falsa. Em todos os outros casos, a
implicação material é, portanto, verdadeira, de acordo com o princípio do terceiro
excluído.

Introdução à Lógica e Programação Página 17

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Observação: Veja que a implicação material é verdadeira, mesmo se a proposição 𝑝,

chamada de antecedente da implicação, for falsa. Além disso, se a proposição 𝑝
significar “O leite ferveu” e 𝑞, o consequente, a proposição “Deus existe”, então a
proposição 𝑝 → 𝑞 representa a proposição “SE o leite ferveu ENTÃO Deus existe”, e
ela é verdadeira toda a vez que o leite não ferveu OU quando Deus existir, o que
parece ser um contrassenso, pois qual seria a relação entre estas duas proposições,
a fervura do leite com a existência de Deus?

Este fato representa o que chamamos de PARADOXO da implicação material, pois o

valor de verdade dessa implicação independe da conexão semântica entre o
antecedente e o consequente da implicação. É por isso que ela é chamada de
IMPLICAÇÃO MATERIAL, pois seu valor de verdade depende só da sua forma lógica.

Há outras lógicas que tentam resolver este problema, por exemplo, a lógica
relevante, ou mesmo a definição, dentro de uma lógica modal, de uma outra
implicação, a implicação restrita. Portanto, quando precisamos formalizar uma
implicação em que este paradoxo seja minimizado, precisamos de um contexto
distinto da lógica proposicional.

Façamos alguns exemplos de cálculo de tabelas de verdade.

Exemplo 1: A fórmula (𝑝 ∧ 𝑞) → 𝑞 é axioma.

𝑝 𝑞 𝑝∧𝑞 (𝑝 ∧ 𝑞) → 𝑞
V V V V
V F F V
F V F V
F F F V

Exemplo 2: A fórmula (𝑝 ∨ 𝑞) → 𝑞

𝑝 𝑞 𝑝∨𝑞 (𝑝 ∨ 𝑞) → 𝑞
V V V V
V F V F
F V V V
F F F V

Veja que o valor de verdade de uma fórmula bem formada da linguagem depende do
valor de verdade das variáveis proposicionais que compõem esta fórmula. Por isso, a
lógica proposicional é dita ser uma lógica VEROFUNCIONAL. Há outras lógicas que
NÃO são verofuncionais, como as lógicas modais anteriormente citadas.

Introdução à Lógica e Programação Página 18

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Uma fórmula bem formada da linguagem proposicional que é SEMPRE verdadeira é

chamada de tautologia. Numa fórmula tautológica, independentemente dos valores
de verdade das variáveis proposicionais, o seu valor de verdade é verdadeiro. Como
esperado, os axiomas, “verdades evidentes” são fórmulas tautológicas.

Uma fórmula bem formada da linguagem que é SEMPRE falsa é chamada de

contradição. Levando em conta o princípio da não-contradição, espera-se que a
fórmula 𝑝 ∧ (¬𝑝) seja contraditória. De fato:

𝑝 ¬𝑝 𝑝 ∧ ( ¬ 𝑝)
V F F
F V F

As fórmulas que não são nem tautológicas, nem contraditórias, são ditas
CONTINGENTES, ou seja, elas podem ser verdadeiras ou não, dependendo dos
fatos atômicos do mundo (valores de verdade das variáveis proposicionais).

EXERCÍCIOS

1. Construa as tabelas de verdade das fórmulas a seguir, determinando quais são

tautológicas, quais são contraditórias e quais são contingentes.

a. 𝑝 → (𝑞 → (𝑝 ∧ 𝑞))

b. ((𝑝 → 𝑞) ∧ (𝑞 ∧ 𝑟)) → (𝑝 → 𝑟)

c. (𝑝 → 𝑞) → (𝑞 → 𝑝)

d. (𝑝 ∧ 𝑞) ∨ 𝑟

e. 𝑝 ∧ (𝑞 ∨ 𝑟)

f. (𝑝 ∨ ¬𝑞) → 𝑟

g. (𝑝 → 𝑞) → ¬(¬𝑝 ∨ 𝑞)

2. Utilize os símbolos da lógica clássica para escrever, em linguagem simbólica, as

seguintes proposições.

a. Se eu prestar vestibular, prestarei Medicina.

b. Se eu fizer faculdade, vou cursar Matemática ou Física.

c. Eu só comprarei um carro novo se for promovido no trabalho.

d. Se chover ou se fizer frio, eu vou ficar em casa ou vou para o cinema.

e. Se fizer sol e não houver trovoadas, eu vou para o parque ou para a praia.

Introdução à Lógica e Programação Página 19

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

f. Se eu estudar Física, eu não vou estudar História, a menos que eu também estude
Português.

g. Eu não ouço Beethoven quando leio Kafka, a menos que esteja chovendo e eu
esteja deprimido.

h. Eu sempre ouço Mozart ou Bach quando leio Agatha Christie, exceto quando estou
cansado.

3. (Concurso para cargo de Administrador – SC) Diga se é verdadeira ou falsa a

proposição:

“Se o número 1 for primo então a terra é plana”.

4. (Concurso para Analista de Planejamento e Orçamento – RR) Considerando os

conectivos lógicos usuais, que as letras maiúsculas representam proposições e ~
representa a negação lógica, diga se é verdadeiro ou falso:

A expressão (𝐴 ∨ 𝐵) → 𝐶 é equivalente à expressão (~𝐴 ∧ ~𝐵) ∨ 𝐶.

5. (Concurso para Médico da prefeitura de Borborema – PB) Classifique cada

afirmação como verdadeira ou falsa.

( ) Toda proposição tem somente um valor lógico.

( ) Se a negação da proposição p for tautológica, então p é uma contingência.

( ) O valor lógico de qualquer proposição composta depende unicamente dos valores

lógicos das proposições simples que a compõem.

( ) A bicondicional 𝑝 ↔ 𝑞 e a conjunção (𝑝 → 𝑞) ∧ (𝑞 → 𝑝) nem sempre são

equivalentes.

Qual a sequência correta de V e F?

6. (FUVEST) Cada um dos cartões a seguir tem de um lado um número e do outro

lado uma letra.
A B 2 3

Alguém afirmou que todos os cartões que têm uma vogal numa face têm um número
para na outra. Para verificar se tal afirmação é verdadeira:

Introdução à Lógica e Programação Página 20

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

a) é necessário virar todos os cartões.

b) é suficiente virar os dois primeiros cartões.

c) é suficiente virar os dois últimos cartões.

d) é suficiente virar os dois cartões do meio.

e) é suficiente virar o primeiro e o último cartão.

7. (UFOP) Sabendo que todos os matemáticos são cientistas, que alguns

matemáticos são professores e que nem todo professor é cientista, pode-se afirmar
que, se João

a) é professor ou cientista, então é matemático.

b) não é matemático, mas é cientista, então é professor.

c) é matemático e professor, então é cientista.

d) não é cientista, mas é professor, então é matemático.

8. (FEI) Dadas as proposições.

1. Toda mulher é boa motorista.

2. Nenhum homem é bom motorista.

3. Todos os homens são maus motoristas.

4. Pelo menos um homem é mau motorista.

5. Todos os homens são bons motoristas.

A negação da proposição 5 é:

a) 1 b) 2 c) 3 d) 4 e) 5

9. (INSPER) Numa roleta, estão marcados todos os números inteiros de 0 a 36, num
total de 37 números. Cada vez que a roleta é acionada, um desses números é
escolhido aleatoriamente, tendo todos eles a mesma probabilidade de serem
escolhidos.

Um grupo de cinco amigos utiliza essa roleta para decidir quem inicia cada rodada de
um jogo. A cada rodada, a roleta é acionada e o número escolhido é dividido por 5,

Introdução à Lógica e Programação Página 21

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

tomando-se o resto dessa divisão. Então, o jogador que inicia a rodada é definido de
acordo com essa tabela a seguir:

Resto da divisão Jogador que inicia a rodada

0 Bruno
1 Felipe
2 Júlia
3 Luana
4 Rafael
Numa determinada rodada, o número escolhido na roleta foi tal que todas as
afirmações feitas a seguir são verdadeiras.

• Se o número escolhido é par, então ele é um quadrado perfeito.

• Se o número escolhido é maior do que 20, então a soma de seus algarismos é
maior ou igual a 7.
• Se o número escolhido é menor do que 15, então ele não é par.
• Se o número escolhido é ímpar, então ele é divisível por 11.

Assim, qual foi o jogador que iniciou aquela rodada?

10. Suponha que o valor de verdade “verdadeiro” possa ser representado pelo
número 1, e o valor de verdade “falso” possa ser representado pelo número 0.
Podemos dar uma semântica para a lógica proposicional, definindo uma função
𝑣: 𝑉𝑎𝑟(𝐿) → {0,1}, que atribui a cada variável proposicional em Var(L) um valor de
verdade 0 ou 1.

A partir desta valoração básica, estendemos a uma valoração para as outras fórmulas
da linguagem, de acordo com uma função 𝑉: 𝐹𝑜𝑟(𝐿) → {0,1}, de forma indutiva sobre
a complexidade das fórmulas em For(L), de acordo com o seguinte critério:

𝑉(𝑝) = 𝑣(𝑝)

𝑉(¬𝛼) = 1 − 𝑉(𝛼)

𝑉(𝛼 ∧ 𝛽) = min {𝑉(𝛼), 𝑉(𝛽)}

𝑉(𝛼 ∨ 𝛽) = max {𝑉(𝛼), 𝑉(𝛽)}

𝑉(𝛼 → 𝛽) = max {𝑉(¬𝛼), 𝑉(𝛽)}

Em que min {𝑥, 𝑦} retorna o menor valor entre 𝑥 e 𝑦 e max {𝑥, 𝑦} retorna o maior valor
entre 𝑥 e 𝑦.

Construa “tabelas de verdade” para estas fórmulas, a partir dos valores da função 𝑉 e
mostre que esta semântica “numérica”, assim definida, é equivalente à semântica
usual das tabelas-verdade, mostrando que esta valoração 𝑉 é uma semântica
alternativa para a lógica proposicional.

Introdução à Lógica e Programação Página 22

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 3 – Teorema da Completude para a Lógica proposicional

Você deve ter notado que o intuito principal de uma lógica ou sistema de dedutivo é
determinar duas coisas:

1. Os teoremas da lógica, ou seja, as consequências dedutivas (racionais) que podem

ser inferidas a partir de seus axiomas e regras de inferências – e usamos a notação ⊢
𝛼 caso 𝛼 seja teorema.

2. As consequências dedutivas de um conjunto de hipóteses ou premissas Γ – e

usamos a notação Γ ⊢ 𝛼. Ou seja, usando somente axiomas e outras fórmulas
hipoteticamente supostas, indicadas no conjunto Γ, conseguimos inferir
dedutivamente a fórmula 𝛼.

Vamos determinar formalmente o que significa este símbolo ⊢.

Definição: Seja L uma linguagem ENUMERÁVEL para a lógica proposicional. Uma

PROVA ou DEDUÇÃO para 𝛼 é uma sequência finita de fórmulas, cuja última fórmula
é 𝛼, que satisfaz:

1. uma das fórmulas é um axioma da lógica, ou;

2. uma das fórmulas é uma hipótese levantada, ou;

3. uma das fórmulas é inferida por uma regra de inferência a partir de fórmulas
anteriores da sequência.

Veja o exemplo de uma dedução na lógica proposicional.

Seja Γ = {¬(𝑝 ∧ 𝑞) → ¬𝑟, 𝑟 ∨ (¬¬𝑠 ∧ ¬𝑢), 𝑠 → ¬𝑣, ¬(𝑝 ∧ 𝑞)}

Podemos deduzir a fórmula (𝑠 → ¬𝑣) ∧ ¬𝑣 como consequência de das hipóteses Γ.

(1) ¬(𝑝 ∧ 𝑞) → ¬𝑟 Premissa

(2) 𝑟 ∨ (¬¬𝑠 ∧ ¬𝑢) Premissa

(3) 𝑠 → ¬𝑣 Premissa

Introdução à Lógica e Programação Página 23

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

(4) ¬(𝑝 ∧ 𝑞) Premissa

(5) ¬𝑟 MP (1) + (4)

(6) ¬¬𝑠 ∧ ¬𝑢 Disjunção (2) + (5)

(7) (¬𝑢 ∧ ¬¬𝑠) → ¬¬𝑠 Axioma

(8) ¬¬𝑠 MP (7) + (6)

(9) 𝑠 Dupla negação (8)

(10) ¬𝑣 MP (3) + (9)

(11) (𝑠 → ¬𝑣) ∧ ¬𝑣 Conjunção (3) + (10)

Veja que fizemos esta dedução usando as hipóteses, quatro primeiras linhas, e um
dos axiomas da lógica proposicional. Usamos também a regra de inferência Modus
Ponens.

Obtemos, portanto, uma sequência de 11 linhas, cada linha contém uma das
hipóteses de Γ, ou um axioma, ou uma fórmula deduzida por fórmulas anteriores pela
aplicação de regras de inferência, e por fim a fórmula a ser provada ou demonstrada.
Podemos então escrever Γ ⊢ 𝛼.

Na linha 6 justificamos a passagem (inferência) com a regra de dedução

DISJUNÇÃO, na linha 9 usamos a regra DUPLA NEGAÇÃO, e na linha 11 usamos a
regra CONJUNÇÃO. Estas três regras chamamos de regras de inferências derivadas.
Podemos provar, dentro da lógica, que estas regras são válidas, usando somente os
axiomas e a regra de inferência primitiva modus ponens. Mas mostrando que estas
regras são válidas, encurtamos as demonstrações dentro da lógica, ao deixar de
repetir estes mesmos procedimentos (a justificativa que ela é válida) em TODAS as
demonstrações que fizermos.

Observação: O que fizemos foi provar que SE Γ for um conjunto de hipóteses

assumidas, SÓ ENTÃO podemos dizer que (𝑠 → ¬𝑣) ∧ ¬𝑣 é uma consequência
dedutiva ou formal deste conjunto de premissas. Veja que (𝑠 → ¬𝑣) ∧ ¬𝑣 NÃO é um
teorema da lógica proposicional, pois ela não foi demonstrada usando somente os
axiomas.

Com este exemplo podemos apresentar uma característica de sistemas lógicos: Eles
possuem linguagem limitadas; no nosso exemplo, falamos que a linguagem L possui
uma quantidade enumerável, ou contável, de símbolos para variáveis proposicionais,
ou seja, temos um estoque infinito, mas contável, de variáveis para símbolos
proposicionais. Além disso, vimos que podemos provar regras de inferências a partir

Introdução à Lógica e Programação Página 24

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

do uso da única regra primitiva, o modus ponens, e utilizamos estas regras em nossas
demonstrações.

Similarmente, podemos definir OUTROS símbolos lógicos, a partir dos símbolos

lógicos PRIMITIVOS de nossa linguagem, que foram indicados no capítulo anterior: ¬,
∧, ∨, →

Vamos definir o BICONDICIONAL ↔, que será um conectivo definido “fora” da

linguagem, portanto não será um conectivo primitivo, mas um símbolo para simplificar
a notação da fórmula (𝐴 → 𝐵) ∧ (𝐵 → 𝐴), para 𝐴 e 𝐵 fórmulas.

Condição Necessária e Suficiente: O bicondicional representa uma expressão

lógica muito importante na matemática, a noção de condição necessária e suficiente.

Se 𝑝 → 𝑞 significa que toda vez que 𝑝 ocorre, então 𝑞 também ocorre, dizemos então
que 𝑝 é uma condição SUFICIENTE para 𝑞 (é suficiente dizer p para inferimos q)

Porém, não é NECESSÁRIO que todo q seja p. Por outro lado; Se 𝑞 → 𝑝 significa que
toda vez que 𝑞 ocorre, então 𝑝 também ocorre, temos:

Logo, definimos o bicondicional:

𝑝 ↔ 𝑞 ≔ (𝑝 → 𝑞) ∧ (𝑞 → 𝑝)

Temos a seguinte representação em diagrama de Venn.

Introdução à Lógica e Programação Página 25

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Ou seja, 𝑝 e 𝑞 são formas “diferentes” de dizer a mesma coisa, elas são proposições
EQUIVALENTES, logo uma é condição NECESSÁRIA e SUFICIENTE para a outra.

Exemplo: Um triângulo de lados medindo 𝑎, 𝑏 e 𝑐, em ordem decrescente, é um

triângulo retângulo SE E SOMENTE SE 𝑎2 = 𝑏 2 + 𝑐 2 .

Esta proposição nos fala DUAS coisas distintas:

(1) SE o triângulo tem lados medindo 𝑎, 𝑏 e 𝑐, em ordem decrescente, for um triângulo

retângulo ENTÃO é válida a relação numérica 𝑎2 = 𝑏 2 + 𝑐 2 (TEOREMA DE
PITÁGORAS).

(2) SE para um triângulo com lados medindo 𝑎, 𝑏 e 𝑐, em ordem decrescente, for

válida a relação numérica 𝑎2 = 𝑏 2 + 𝑐 2 , ENTÃO ele é um triângulo retângulo.

Portanto, o triângulo ser retângulo ou ser válida a relação numérica são coisas
equivalentes. Por isso, lemos o bicondicional ↔ desta forma: “Se e somente se”, pois
ele “esconde” duas implicações materiais em sentidos opostos.

Abordagem Sintática versus Semântica

Você deve ter percebido que encontrar uma prova de um teorema ou de uma
consequência dedutiva de um conjunto de premissas não é algo muito trivial. Existe
toda uma área de estudo e pesquisa em lógica chamada de TEORIA DA PROVA, que
procura desenvolver ferramentas, técnicas para encontro sintático dos teoremas ou
consequências de uma lógica. Ex: Inferência do sistema; sistemas de dedução
natural, cálculo de sequentes etc.

Por outro lado, parece ser mais “natural” lidarmos com as tabelas de verdade ou com
noções semânticas. Por isso, existem também estratégias semânticas para
determinar as tautologias da lógica proposicional. Em outras lógicas, o conceito
análogo ao de tautologia é o conceito de fórmulas válidas, ou seja, fórmulas sempre
“verdadeiras”. Também determinamos fórmulas que são sempre verdadeiras SE
assumirmos um conjunto de hipóteses ou premissas, o que chamamos de
CONSEQUÊNCIA LÓGICA. Ex: Métodos dos Tableaux, métodos mistos (teoria da
prova + noções semânticas), métodos algébricos ou métodos topológicos – a
depender da lógica analisada etc.

Vamos analisar uma abordagem semântica para o exemplo de prova que demos nas
páginas anteriores, por meio de tabelas de verdade.

Observação: Como temos 6 variáveis proposicionais envolviddas, esta tabela teria

26 = 64 linhas. Vamos omitir as linhas em que as premissas são falsas, e verificar o
que ocorre com o valor de verdade da conclusão nos casos em que TODAS as
premissas forem verdadeiras.

Introdução à Lógica e Programação Página 26

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

𝑝 𝑞 𝑟 𝑠 𝑢 𝑣 ¬(𝑝 ∧ 𝑞) → ¬𝑟 𝑟 ∨ (¬¬𝑠 ∧ ¬𝑢) 𝑠 → ¬𝑣 ¬(𝑝 ∧ 𝑞) (𝑠 → ¬𝑣) ∧ ¬𝑣

V F F V F F V V V V V
F V F V F F V V V V V
F F F V F F V V V V V

Note que a distribuição de valores de verdade para as variáveis proposicionais que

fazem com que as 4 premissas sejam verdadeiras, TAMBÉM fazem com que a
conclusão seja verdadeira. Dizemos neste caso que a conclusão (𝑠 → ¬𝑣) ∧ ¬𝑣 é
uma CONSEQUÊNCIA LÓGICA de nossas hipóteses Γ; note que consequência lógica
é uma noção semântica. Denotamos isso desta forma: Γ ⊨ (𝑠 → ¬𝑣) ∧ ¬𝑣. Ou seja,
sempre que as premissas forem verdadeiras, a conclusão também o será – noção
que reflete a ideia de argumento válido, como os silogismos aristotélicos.

Se 𝛼 for uma fórmula válida, tautologia na lógica proposicional, então denotamos ⊨ 𝛼.

Temos então duas noções “irmãs”:

a – Teoremas (sintático) e Fórmulas válidas ou tautologias na lógica proposicional

(semântico), representadas por ⊢ 𝛼 (noção sintática) e ⊨ 𝛼 (noção semântica)

b – Consequências dedutivas (sintático) e Consequências lógicas (semântico),

representadas por Γ ⊢ 𝛼 (noção sintática) e Γ ⊨ 𝛼 (noção semântica)

Um dos principais resultados no estudo das lógicas é encontrar a relação entre as

noções sintáticas e semânticas. Veja que para isso, precisamos fazer estudos
racionais SOBRE um sistema lógico. Lembre-se que uma lógica seria o sistema
dedutivo que nos PERMITE fazer inferências lógicas, portanto, temos que garantir de
não cairmos em um tipo de círculo vicioso, em que usamos o tipo de raciocínio que
queremos demonstrar ser válido para provar que ele é válido.

Quando estudamos as propriedades de um sistema lógico, devemos estar cientes que

estamos fazendo argumentos baseados em um tipo de estrutura racional. As
propriedades assim demonstradas sobre estes sistemas não são teoremas DO
sistema, mas SOBRE ele. Por isso, a forma correta de nos referirmos a eles é como
METATEOREMAS. Porém, ficando claro a distinção entre estes conceitos (um
TEOREMA é um resultado provado por um sistema lógico, e um METATEOREMA é
uma propriedade deste sistema lógico que conseguimos demonstrar que ele possui)
podemos simplificar a linguagem e nos referirmos, somente, como teorema a todas
proposições (dentro ou fora de um sistema) demonstradas logicamente por meio dos
princípios válidos para cada situação de inferência.

Introdução à Lógica e Programação Página 27

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Quando uma noção sintática implica uma noção semântica, dizemos que a lógica é
correta em relação àquela semântica estudada.

Por exemplo, a lógica proposicional é correta em relação à semântica dada pelas

tabelas de verdade.

Quando uma noção semântica implica uma noção sintática, dizemos que a lógica é
completa em relação àquela semântica estudada.

Por exemplo, a lógica proposicional é completa em relação à semântica dada pelas

tabelas de verdade.

Metateorema sobre a lógica proposicional: [Teorema da Completude]

A lógica proposicional é correta e completa em relação à semântica dada pelas

tabelas de verdade.

Veja que usamos a palavra Completude, com “C” maiúsculo, para representar as
noções de correção + completude; Completude, com “C” maiúsculo, também pode ser
definido com o conceito de ADEQUAÇÃO, para não ficar tão confusa a ideia de dois
conceitos com a “mesma” palavra, representando coisas distintas.

Quando uma lógica possui a propriedade de Completude (adequação) para

determinada semântica, isso significa que para encontrar seus teoremas ou
consequências dedutivas, podemos tanto usar as noções sintáticas, como as noções
semânticas, pois no final, elas são equivalentes. É um resultado extremamente forte,
pois no geral, é mais fácil usarmos ferramentas semânticas ao invés de ferramentas
da teoria da prova.

Portanto, dado o teorema da Completude para a lógica proposicional, por exemplo,

para determinarmos se uma fórmula é ou não um teorema, não precisamos
necessariamente encontrar uma dedução, basta fazermos uma tabela verdade para
esta fórmula, pois o teorema garante que com isso, somos capazes de determinar
TODOS os teoremas da lógica – a fórmulas que são tautológicas.

Mas como o Teorema da Completude para a lógica proposicional é demonstrado?

Introdução à Lógica e Programação Página 28

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Como este (meta)teorema mostra uma equivalência entre as duas abordagens, ele
deve ser provado usando a técnica usual para estes casos, demonstrando os dois
lados da implicação.

Parte 1: sintático implica semântico

Em geral a correção é o lado mais fácil de ser provado.

No caso da lógica proposicional, mostra-se que os esquemas de axiomas são

tautologias – no nosso caso, basta fazermos as quatro tabelas de verdade, e por fim
mostra-se que a regra de inferência primitiva modus ponens preserva a validade das
fórmulas, isto é, se as duas premissas forem verdadeiras, a conclusão também o
será.

Nota-se assim que uma boa estratégia ao definirmos uma lógica é adotarmos a menor
axiomatização e a menor quantidade possível de regras de inferências primitivas, pois
isso diminui o trabalho na hora da demonstração das propriedades desta lógica.

Parte 2: semântico implica sintático

Em geral, a completude é o lado mais complexo para ser provado.

No caso da lógica proposicional, usualmente realizam-se demonstrações para provar

o que chamamos de “completude forte”, isto é, se Γ ⊨ 𝛼 então Γ ⊢ 𝛼, resultando o
caso particular da completude (fraca) tomando Γ = ∅.

Tais demonstrações dependem de alguns conceitos:

Satisfação: dizemos que uma fórmula é satisfatível se existir alguma atribuição de

valores de verdade para as suas variáveis proposicionais que torna tal fórmula
verdadeira, logo ela é não pode ser uma contradição.

Consistência: Dizemos que um conjunto de fórmulas é consistente se existir alguma

atribuição de valores de verdade para as variáveis proposicionais que aparecem nas
fórmulas deste conjunto, de forma que TODAS as fórmulas do conjunto sejam
verdadeiras simultaneamente.

Como nosso curso é introdutório, não iremos realizar a demonstração deste teorema
aqui. Caso tenha interesse, consulte as obras na bibliografia.

Vale a pena observar que outra forma de demonstrar a Completude para a lógica
proposicional é considerá-la como um pedaço da lógica de primeira ordem, o cálculo
sentencial, demonstrar a Completude para a lógica de primeira ordem e deduzir a
Completude proposicional como um corolário deste teorema.

Introdução à Lógica e Programação Página 29

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

EXERCÍCIOS

1. Mostre como reescrever os conectivos a seguir.

Exemplo: Escrever ∨ em função de ¬ e ∧:

Faça as tabelas-verdade para verificar que 𝑝 ∨ 𝑞 ≔ ¬(¬𝑝 ∧ ¬𝑞). (o símbolo ≔

significa definição na linguagem).

a. Escrever ∧ em função de ¬ e ∨:

b. Escrever → em função de ¬ e ∨:

c. Escrever → em função de ¬ e ∧:

2. Justifique, usando o exercício anterior, que poderíamos considerar a linguagem L

da lógica proposicional com somente os conectivos primitivos ¬ e ∧.

3. Prove que usando somente o conectivo ¬ não podemos definir os outros

conectivos da linguagem.

4. Considere um conectivo binário ∘ para a lógica proposicional, que obedece a

seguinte tabela de verdade:

𝑝 𝑞 𝑝∘𝑞
V V F
V F F
F V F
F F V
a. Defina ∘ a partir dos conectivos usuais.

b. Mostre que é possível definir quaisquer conectivos da lógica proposicional

utilizando somente ∘.

5. Faça um diagrama de Venn representando as ações dos seguintes conectivos,

indicando qual operação conjuntista eles representam.

a. ¬𝑝

b. 𝑝 ∧ 𝑞

c. 𝑝 ∨ 𝑞

Introdução à Lógica e Programação Página 30

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

6. A barra de Sheffer ↑ é um conectivo binário da lógica proposicional que só é falso

quando os dois valores de verdade envolvidos forem verdadeiros, obedecendo a
seguinte tabela de verdade:

𝑝 𝑞 𝑝↑𝑞
V V F
V F V
F V V
F F V
a. Faça um diagrama de Venn representando a ação deste conectivo.

b. Mostre que podemos definir toda a linguagem proposicional usando somente a

barra de sheffer como conectivo primitivo. Esta propriedade faz este operador ser
muito importante na arquitetura de processadores para computador, por facilitar o
desenho da estrutura eletrônica digital de circuitos.

7. Utilize o teorema da Completude para verificar se os argumentos a seguir são

válidos ou não, ou seja, se a conclusão é de fato verdadeira, considerando as
premissas.

a. Ouvir rock me dá dor de cabeça. Quando estou com dor de cabeça não estudo.
Hoje não estudei. Portanto, ouvi rock.

b. Ouvir rock me deixa alegre. Eu só estudo quando estou alegre. Hoje eu ouvi rock.
Portanto, vou estudar.

c. Eu só fico tranquilo quando ouço música clássica. Eu nunca estudo quando não
estou tranquilo. Hoje eu estudei. Logo, eu ouvi música clássica.

8. Afirme se a dedução a seguir está correta:

Nenhum gato fantasiado de garça é antissocial.

Nenhum gato sem rabo brinca com gorilas.

Gatos com bigodes sempre se fantasiam de garça.

Nenhum gato sociável tem garras rombudas.

Nenhum gato tem rabo, a menos que tenha bigodes.

Portanto:

Nenhum gato com garras rombudas brinca com gorilas.

Introdução à Lógica e Programação Página 31

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

9. (Concurso para Técnico em Informática CODEN) Considere as afirmações I, II e III

como verdadeiras.

I. Se Francisco é mecânico, então Geraldo é encanador.

II. Se Heitor é vendedor, então Geraldo não é encanador.

III. Se Heitor não é vendedor, então José é pedreiro.

Considere falsidade a seguinte afirmação:

IV. Se Lucas é eletricista, então José é pedreiro.

A partir destas informações, é correto afirmar que:

a) Lucas não é eletricista.

b) Geraldo é encanador.

c) Francisco não é mecânico.

d) Jose é pedreiro.

e) Heitor não é vendedor.

10. (Concurso para Analista de Desenvolvimento – prefeitura de Vila Velha ES) Qual
a proposição incorreta?

a) São Paulo faz fronteira com o Amazonas ou São Paulo faz fronteira com o Rio de
Janeiro.

b) Rio de Janeiro faz fronteira com Minas Gerais e sua capital é Rio de Janeiro.

c) Belém é capital do Pará e fica na região Nordeste.

d) O clube do remo fica em Belém do Pará ou em Manaus.

e) A capital do Espírito Santo é Vitória ou Colatina.

11. (Concurso para Analista Administrativo da Procuradoria do estado de PE)

“A lógica bivalente não obedece ao princípio da não contradição, segundo o qual uma
proposição não assume simultaneamente valores lógicos distintos”. Esta sentença é
verdadeira ou falsa?

Introdução à Lógica e Programação Página 32

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 4 – Lógica Clássica

Chamamos de Lógica Clássica à lógica que admite os três princípios da lógica

aristotélica: princípio da identidade, do terceiro excluído e da não contradição, além
disso, ela é uma lógica enriquecida, em relação à Lógica Proposicional, pois tem
novos símbolos na linguagem para podermos formalizarmos sentenças que envolvem
objetos ou indivíduos.

Exemplo: Seja a sentença “Romeu ama Julieta”.

Se formos usar a linguagem proposicional, esta sentença poderia ser traduzida por
uma variável proposicional, pois não podemos simplificar, dividir, esta sentença
“Romeu ama Julieta” em outras mais simples – ela é uma sentença atômica.

Na lógica clássica, também chamada de lógica quantificada de primeira ordem, ou

lógica de predicados de primeira ordem, temos uma linguagem mais rica, no qual
podemos denotar os indivíduos Romeu, Julieta, e indicar a relação entre eles – a
relação de amor, por meio de um símbolo de predicado binário. Veja:

Sejam 𝑟 e 𝑗 dois símbolos, constantes, que denotam os indivíduos Romeu e Julieta, e

𝑃 um símbolo de predicado binário, que podemos denotar 𝑃(𝑥, 𝑦) ou 𝑥𝑃𝑦 para
representar que 𝑥 ama 𝑦. Assim, nesta linguagem, a sentença “Romeu ama Julieta”
pode ser formalizada por 𝑃(𝑟, 𝑗). Veja que “amar” é uma relação direcional, 𝑃(𝑥, 𝑦)
indica que x ama y, mas não podemos afirmar que y ama x, ou seja, esta relação não
é, necessariamente, SIMÉTRICA.

Note que a linguagem da lógica de primeira ordem é muito mais rica do que a
linguagem proposicional, pois podemos formalizar nesta linguagem expressões muito
mais detalhadas. De fato, a lógica clássica é essencial para escrevermos expressões
sobre a matemática.

Formalização da Linguagem para a Lógica Clássica

Seja ℒ a linguagem da Lógica de Predicados de Primeira Ordem. Ela é uma expansão

da linguagem L da lógica proposicional, com o acréscimo dos seguintes símbolos:

Variáveis individuais: representam objetos indeterminados. Utilizamos as letras 𝑥 e

𝑦, por exemplo, para representarmos variáveis individuais.

Constantes: representam objetos determinados, são como nomes. Utilizamos as

letras 𝑎 e 𝑏, por exemplo, para representar constantes.

Introdução à Lógica e Programação Página 33

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Símbolos funcionais: representam objetos ou coisas determinados a partir de

outros. Para cada 𝑛 ≥ 1, existe um estoque infinito e enumerável de símbolos
funcionais 𝑓 𝑛 – dizemos que 𝑛 é a aridade do símbolo funcional. Se 𝑔 é símbolo
funcional de aridade 3, então 𝑔(𝑥, 𝑦, 𝑐) é um objeto determinado em função dos
objetos representados pelas variáveis 𝑥 e 𝑦 e pelo objeto cujo nome é 𝑐 (constante).

Termos: Damos ao nome de termo uma expressão da linguagem que denota um

objeto. Veja alguns exemplos:

𝑥 é um termo (como é uma variável, este símbolo não denota nenhum objeto
específico)

𝑐 é um termo (como é uma constante, este símbolo denota o objeto “nomeado” por 𝑐)

𝑓(𝑥) é um termo (este símbolo não denota nenhum objeto específico, pois depende
do valor de 𝑥 para ser “calculado”)

𝑔(𝑥, 𝑐) é um termo (este símbolo não denota nenhum objeto específico, pois depende
do valor de 𝑥 para ser “calculado”)

ℎ(𝑎, 𝑏, 𝑐) é um termo (este símbolo denota o objeto “calculado”, pela função ℎ, para os
objetos denotados por 𝑎, 𝑏 e 𝑐)

Se 𝑓(𝑥) for a função “ser pai de”, então 𝑓(í𝑐𝑎𝑟𝑜) = 𝑑é𝑑𝑎𝑙𝑜𝑠, por exemplo. Veja que
Ícaro e Dédalos são nomes, podemos os considerar como constantes.

Após incluirmos na linguagem símbolos para representar os objetos (por isso dizemos
lógica “quantificada”, pois podemos quantificar sobre uma coleção ou conjunto-
universo), vamos ampliar o poder representativo da linguagem proposicional, por meio
de símbolos relacionais ou de predicados, que indicam propriedades ou relações
entre objetos.

Símbolos de predicado: Para cada número natural 𝑛 ≥ 1, existe uma coleção

enumerável de símbolos de predicado 𝑃𝑛 , em que 𝑛 é a aridade do símbolo de
predicado; todo símbolo de predicado 𝑃 com esta aridade deve ser seguido de 𝑛
temos. Veja alguns exemplos:

𝑃 símbolo de predicado de aridade 2: 𝑃(𝑥, 𝑦) ou 𝑃(𝑎, 𝑏) ou 𝑃(𝑥, 𝑓(𝑥, 𝑦, 𝑧)), em que 𝑓 é

um símbolo funcional de aridade 3.

Se 𝑃 for um predicado utilizado para representar que 𝑃(𝑥, 𝑦) significa “𝑥 está à

esquerda de 𝑦”, então interpretamos 𝑃(𝑎, 𝑏) como 𝑎 está à esquerda de 𝑏, assim
como interpretamos 𝑃(𝑥, 𝑓(𝑥, 𝑦, 𝑧)) como 𝑥 está à esquerda do objeto denotado por
𝑓(𝑥, 𝑦, 𝑧).

Introdução à Lógica e Programação Página 34

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Por fim, após inserirmos na linguagem as representações para os objetos, assim

como para as representações de propriedades ou relações (por isso o nome de
“Lógica de Predicados”), inserimos também os símbolos de quantificação (por isso o
nome de “Lógica Quantificada”).

Quantificador existencial: Suponha que 𝑃 represente um símbolo de predicado 1-

ário, por exemplo a propriedade 𝑥 é par: 𝑃(𝑥). Utilizamos o quantificador existencial
para dizer que EXISTE (dependendo do universo considerado) alguma coisa que
satisfaz esta propriedade, ao escrevermos ∃𝑥𝑃(𝑥).

Quantificador universal: Supondo o mesmo exemplo, utilizamos o quantificador

universal para dizer que TODAS as coisas que “existem” satisfazem esta propriedade,
ao escrevermos ∀𝑥𝑃(𝑥).

Regras de formação: As regras de formação de fórmulas bem formadas (da

linguagem proposicional) para os conectivos lógicos e símbolos de pontuação
continuam válidas para as fórmulas da lógica clássica. Basta darmos as regras de
formação para os novos símbolos.

1. Todo termo é fórmula bem formada;

2. Se 𝑃 for símbolo de predicado 𝑛 −ário e 𝑡1 , … 𝑡𝑛 forem termos, então 𝑃(𝑡1 , … , 𝑡𝑛 ) é

fórmula bem formada;

3. Se 𝛼 for fórmula bem formada, então ∃𝑥𝛼 e ∀𝑥𝛼 são fórmulas bem formadas, para
𝑥 variável individual.

Vimos que na lógica proposicional trabalhávamos apenas com as fórmulas que

representavam proposições, ou seja, elas poderiam ser ditas sempre serem
verdadeiras ou falsas.

Se você reparou, agora na linguagem da lógica clássica, ou lógica (quantificada ou de

predicados) de primeira ordem, as expressões ou sentenças nem sempre podem ser
ditas verdadeiras ou falsas, pois podemos ter a fórmula 𝑎, que denota um objeto, ou a
fórmula 𝑥 < 5, que representa um predicado binário (menor do que), que para ser
verdadeiro ou não, depende do valor que atribuímos para a variável 𝑥 (veja que 5 é
uma constante que denota um número específico).

Escopo de atuação de um quantificador: É a região de atuação de um

quantificador. Veja:

∃𝑥𝑃(𝑥) ∧ 𝑄(𝑥, 𝑦) e ∃𝑥(𝑃(𝑥) ∧ 𝑄(𝑥, 𝑦)) são fórmulas DISTINTAS da lógica clássica.

Introdução à Lógica e Programação Página 35

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

∃𝑥𝑃(𝑥) ∧ 𝑄(𝑥, 𝑦) nos afirma que existe alguma coisa que satisfaz a propriedade P E
que a relação Q é expressa para duas outras coisas quaisquer (mas não há a
afirmação de que estas duas coisas “existam”). Neste caso, o escopo de atuação do
quantificador é somente o predicado P.

∃𝑥(𝑃(𝑥) ∧ 𝑄(𝑥, 𝑦)) nos afirma que existe alguma coisa que além de satisfazer a
propriedade P, também está em relação com algo por meio da relação Q – note a
presença dos parênteses. Neste caso, o escopo de atuação do quantificador para x é
tanto a propriedade P, quanto para a relação Q.

Ocorrências ligadas de uma variável: Dizemos que a(s) ocorrência(s) de uma

variável individual em uma fórmula é ligada se ela(s) ocorre(m) no escopo de um
quantificador.

Na fórmula ∀𝑥(𝑃(𝑥, 𝑦, 𝑧) → ∃𝑧(𝑃(𝑥, 𝑧, 𝑧))) a variável x ocorre ligada pelo quantificador

universal, a variável y não ocorre ligada, e a variável z ocorre tanto ligada pelo
quantificador existencial no consequente da implicação, quanto ocorre não-ligada no
antecedente da implicação.

Quando uma variável tem uma ocorrência não-ligada numa fórmula, dizemos que esta
ocorrência da variável é LIVRE.

Fórmula fechada: É uma fórmula em que não ocorrem variáveis livres.

Fórmula aberta: É uma fórmula em que ocorrem variáveis livres.

As fórmulas abertas não podem receber um “valor de verdade”, pois elas não
representam proposições. As fórmulas abertas representam sentenças da linguagem
que podem receber um valor de verdade, ou seja, representam proposições.

Suponhamos que estamos no contexto da matemática, e no universo dos números

naturais.

A fórmula (𝑥 < 5) ∧ 𝑃(𝑥), para P(x) a propriedade x é primo, ela não tem um valor de
verdade, pois depende do que substituirmos no lugar da variável x.

A solução desta fórmula são todos os números naturais (universo) menores do que 5
e que são primos, ou seja, os números 2 e 3.

Já a fórmula ∃𝑥((𝑥 < 5) ∧ 𝑃(𝑥)) tem um valor de verdade, que depende de se a

sentença “Existe algum número natural que é menor do que 5 e primo” for verdadeira
ou não. Como vimos, existem dois números que satisfazem esta propriedade,
portanto a sentença seria verdadeira.

Introdução à Lógica e Programação Página 36

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Portanto, na lógica clássica, uma fórmula aberta tem um conjunto-solução, e uma

fórmula fechada é uma proposição e somente tem um valor de verdade, no caso, ou
ela é falsa, ou verdadeira.

Lógica Clássica

Para definirmos a Lógica Clássica, ou Lógica Quantificada de primeira ordem, ou

Lógica de Predicados de primeira ordem, precisamos da sua axiomática e das suas
regras de inferência.

Axiomatização:

1. Todas as fórmulas tautológicas da lógica proposicional são axiomas da lógica

clássica.

2. Se A e B forem fórmulas em que x é uma variável que NÃO ocorre livre em A,

então é axioma a fórmula (∀𝑥(𝐴 → 𝐵)) → (𝐴 → ∀𝑥𝐵).

3. Se A for fórmula, t for um termo e nenhuma ocorrência livre de x em A contém o

termo t, então é axioma ∀𝑥𝐴 → 𝐴[𝑥/𝑡] é axioma, em que 𝐴[𝑥/𝑡] significa que
substituímos todas as ocorrências de x em A pelo termo t.

4. 𝑥 = 𝑥 é um axioma, para qualquer variável 𝑥.

5. Suponhamos que A e B são fórmulas, e B é a fórmula obtida ao substituirmos uma

ou mais ocorrências livres de x em A pela variável y, então é axioma (𝑥 = 𝑦) →
(𝐴 → 𝐵).

Regras de inferência:

Além do Modus Ponens, temos a regra para quantificador.

Generalização: Se x for variável, da fórmula 𝐴 infere-se a fórmula ∀𝑥𝐴.

Se 𝛼 for fórmula da linguagem ℒ, do qual temos uma PROVA (usando somente os

axiomas e regras de inferência da Lógica de primeira ordem), dizemos que 𝛼 é um
TEOREMA da Lógica Clássica, e denotamos ⊢ 𝛼.

Se conseguirmos uma prova para 𝛼 usando, além de axiomas e das regras de

inferência, hipóteses adicionais que estão no conjunto Γ, denotamos Γ ⊢ 𝛼, ou seja, a
fórmula 𝛼 é consequência (sintática) de Γ.

Introdução à Lógica e Programação Página 37

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

EXERCÍCIOS

1. Seja N a linguagem de primeira ordem em que temos os símbolos primitivos:

Dois símbolos funcionais binários: +(𝑥, 𝑦) que representa 𝑥 + 𝑦; ⋅ (𝑥, 𝑦) que

representa 𝑥 ⋅ 𝑦;

Dois símbolos relacional binário: ≤ (𝑥, 𝑦) que representa 𝑥 ≤ 𝑦; = (𝑥, 𝑦) para

representar 𝑥 = 𝑦.

Duas constantes: 0 e 1.

Além disso, os predicados 𝐸(𝑥) para 𝑥 é par, 𝑃(𝑥) para 𝑥 é primo e 𝐷(𝑥, 𝑦) para 𝑥
divide 𝑦.

Traduza as sentenças a seguir usando esta linguagem, além dos símbolos lógicos.

a. Todo número par maior do que 2 pode ser escrito como soma de dois números
primos.

b. 𝑥 possui exatamente três divisores.

c. Todo número positivo admite raiz quadrada.

d. 𝑥 e 𝑦 são primos entre si.

e. 𝑧 é o maior divisor comum de 𝑥 e 𝑦.

2. Seja P a linguagem de primeira ordem em que temos as funções unárias 𝑀Ã𝐸(𝑥)

para representar a mãe de 𝑥, 𝑃𝐴𝐼(𝑥) para representa o pai de 𝑥.

Além disso, temos o símbolo relacional = (𝑥, 𝑦) para representar 𝑥 = 𝑦 e os

predicados 𝑀(𝑥) para indicar que 𝑥 é do sexo masculino e 𝐹(𝑥) para representar 𝑥 é
do sexo feminino.

Traduza as sentenças a seguir usando esta linguagem, além dos símbolos lógicos, se
precisar acrescente constante para representar os nomes. Você pode considerar os
nomes como constantes da linguagem.

a. Ele é primo de Maria.

b. João é filho único.

c. Maria possui um único irmão e nenhuma irmã.

d. João é meio-irmão de Maria.

e. Maria possui uma avó que tem três filhos(as).

Introdução à Lógica e Programação Página 38

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

3. Considerando a linguagem do exercício anterior, traduza para a linguagem

corrente, Português, preferencialmente, as sentenças em primeira ordem:

a. ∃𝑥(((𝑃𝐴𝐼(𝑗𝑜ã𝑜) = 𝑃𝐴𝐼(𝑥)) ∧ ((𝑥 = 𝑃𝐴𝐼(𝑚𝑎𝑟𝑖𝑎)) ∨ (𝑥 = 𝑀Ã𝐸(𝑚𝑎𝑟𝑖𝑎)))) ∨

((𝑀Ã𝐸(𝑗𝑜ã𝑜) = 𝑀Ã𝐸(𝑥)) ∧ ((𝑥 = 𝑃𝐴𝐼(𝑚𝑎𝑟𝑖𝑎)) ∨ (𝑥 = 𝑀Ã𝐸(𝑚𝑎𝑟𝑖𝑎)))))

b. ∃𝑥∃𝑦 ((¬(𝑥 = 𝑦)) ∧ (𝑗𝑜ã𝑜 = 𝑃𝐴𝐼(𝑥)) ∧ (𝑗𝑜ã𝑜 = 𝑃𝐴𝐼(𝑦)) ∧ ∀𝑧 ((𝑗𝑜ã𝑜 = 𝑃𝐴𝐼(𝑧)) →

((𝑧 = 𝑥) ∨ (𝑧 = 𝑦))))

4. Mostre que poderíamos usar somente um dos quantificadores como símbolo

primitivo da linguagem da lógica clássica. Para isso, escreva o quantificador
existencial em função do quantificador universal, assim como o quantificador universal
em função do quantificador existencial.

5. Identifique em cada fórmula a seguir quais são as variáveis de ocorrência livre, e

quais são as variáveis de ocorrência ligada, considerando a linguagem N do exercício
1.

a. (∃𝑥((1 + 𝑦) = 𝑥)) ∨ ∀𝑦(𝑦 < 𝑥)

b. ∀𝑦∀𝑧 ((𝑦 ⋅ 𝑧 = 𝑥) → ((𝑦 ≠ 𝑧) ∧ ((𝑦 = 1) ∨ (𝑧 = 1))))

c. (∃𝑥(𝑥 ⋅ 𝑥 = 2)) → (𝑥 + 1 = 0)

d. ∀𝑥∃𝑦(𝑧 < 1)

e. ∀𝑥((𝑥 = 0) ∨ (0 < 𝑥)) ∧ ∃𝑦(𝑦 ⋅ (1 + 1) = 𝑥)

f. ∀𝑥(𝑥 > (1 + 1) → 𝑦 < (𝑥 + 𝑥))

6. Identifique, no exercício anterior, quais fórmulas são fechadas e quais fórmulas são
abertas.

Considerando o universo do conjunto dos números naturais, fale, neste contexto, se

as fórmulas fechadas são verdadeiras ou falsas.

No mesmo contexto dos números naturais, indique qual o conjunto solução das
fórmulas abertas.

Introdução à Lógica e Programação Página 39

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

7. Lembra-se do sistema dedutivo MIU? Havíamos deixado um Enigma: Será que a

palavra MU é uma palavra legítima do sistema-MIU, i.e., será que podemos obter uma
derivação desta palavra usando as regras de inferência?

Tente demonstrar que NÃO, MU não é uma palavra legítima deste sistema (teorema).
Para isso, basta notar alguns teoremas que demonstramos: MIU ou MIUIU.

Dica:

1. Mostre que no axioma, o número de I’s na palavra não é um múltiplo de 3 (base da

indução).

2. Mostre que nenhuma das regras de inferências altera a contagem de I’s na palavra
obtida para um número múltiplo de 3, a não ser que você inicie a regra de inferência
com um número de I’s múltiplo de 3.

Com isso, justifique que MU não pode ser um teorema de sistema-MIU.

8. (Concurso para Analista de Sistemas do Tribunal de Justiça de SP) Todo PLATZ

que não é PLUTZ é também PLETZ. Alguns PLATZ que são PLETZ também são
PLITZ.

A partir destas afirmações, pode-se concluir que:

a) alguns PLITZ são PLETZ e PLATZ.

b) existe PLATZ que não é PLUTZ nem é PLETZ.

c) não existe PLUTZ que é apenas PLUTZ.

d) todo PLITZ é PLETZ.

e) existe PLITZ que é apenas PLITZ.

9. (Concurso para Analista de Sistemas e Engenheiro de Software da Petrobrás)

Associe corretamente as sentenças da lógica de primeira ordem com suas
respectivas propriedades.

I. ∀𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) → (∀𝑥𝑃(𝑥) ∨ ∀𝑥𝑄(𝑥))

II. ∀𝑥(¬𝑃(𝑥) → 𝑃(𝑥))

R – a sentença é uma tautologia.

S – é satisfatível, mas não uma tautologia.

T – é insatisfatível.

Introdução à Lógica e Programação Página 40

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

10. (IBMEC) Em cada um dos cinco quartos A, B, C, D e E de um hotel há um e

apenas um hóspede. Os tamanhos e disposição dos quartos estão indicados na
imagem a seguir.

B
D
C
A
E
Sabe-se que:

• um hóspede assassinou um dos outros quatro;

• se o assassino e a vítima se hospedaram em quartos que possuem o mesmo
número de quartos contíguos, então o hóspede do quarto C é o assassino;
• se o assassino e a vítima estavam em quartos de tamanhos diferentes, então o
criminoso estava no quarto A ou D.

Com base nessas informações, conclui-se que a vítima era o hóspede do quarto:

a) A

b) B

c) C

d) D

e) E

Introdução à Lógica e Programação Página 41

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 5 – Teorias de Primeira Ordem e Modelos

Vamos chamar de Teorias de Primeira Ordem a uma axiomatização para um

sistema dedutivo de primeira ordem que acrescenta, aos axiomas lógicos, alguns
axiomas não-lógicos. Nesse caso, uma teoria de primeira ordem é um sistema
dedutivo que contém a lógica clássica.

Alguns autores também consideram Teoria de Primeira Ordem à coleção de TODOS

os teoremas obtidos a partir destes axiomas não-lógicos. Nesse caso, uma teoria de
primeira ordem é uma coleção “consistente e maximal” de fórmulas de primeira
ordem. Não vamos usar esta definição aqui, para não termos de abordar estes
conceitos de consistência e maximalidade.

A assinatura de uma teoria de primeira ordem é a coleção de símbolos da linguagem

de primeira ordem específicos para a teoria. Vamos ver um exemplo:

Aritmética 𝑁

A assinatura desta teoria é o conjunto ℒ𝑁 = {0, 𝑠 , + , ⋅ , <}. 0 é uma constante, 𝑠 um

símbolo funcional 1-ário, + e ⋅ símbolos funcionais 2-ários, e < um símbolo de
predicado ou de relação binário.

O comportamento destes símbolos não lógicos, na teoria 𝑁, é determinado pelos

axiomas não lógicos desta teoria. Estes axiomas são chamados de axiomas de
Peano, pois ele foi o responsável em formalizar estas ideias em uma linguagem
formal de primeira ordem, embora o grande responsável por apresentar estas ideias,
pela primeira vez – mas não nesta linguagem formal – tenha sido o matemático
Dedekind, que aprimorou um trabalho anterior de Frege. Frege, por sua vez, foi um
dos principais responsáveis por apresentar uma noção organizada e sistemática para
a lógica de primeira ordem.

Axiomas para 𝑵

Considere 𝑥 ≠ 𝑦 uma abreviação para a fórmula ¬(𝑥 = 𝑦)

N1. ∀𝑥(𝑠(𝑥) ≠ 𝑥)

N2. ∀𝑥∀𝑦(𝑠(𝑥) = 𝑠(𝑦) → 𝑥 = 𝑦)

N3. ∀𝑥(𝑥 + 0 = 𝑥)

N4. ∀𝑥∀𝑦(𝑥 + 𝑠(𝑦) = 𝑠(𝑥 + 𝑦))

N5.∀𝑥(𝑥 ⋅ 0 = 0)

N6. ∀𝑥 ∀𝑦 (𝑥 ⋅ 𝑠(𝑦) = (𝑥 ⋅ 𝑦) + 𝑥

Introdução à Lógica e Programação Página 42

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

N7. ∀𝑥¬(𝑥 < 0)

N8. ∀𝑥∀𝑦(𝑥 < 𝑠(𝑦) ↔ (𝑥 < 𝑦 ∨ 𝑥 = 𝑦))

N9. ∀𝑥∀𝑦(𝑥 < 𝑦 ∨ 𝑥 = 𝑦 ∨ 𝑦 < 𝑥)

Qualquer fórmula 𝛼 da lógica clássica, com estes símbolos da assinatura da teoria 𝑁,

que for deduzida a partir dos axiomas Γ = {𝑁1, 𝑁2, … , 𝑁9}, é uma PROVA ou
DEDUÇÃO de Γ, ou seja, é um TEOREMA da teoria 𝑁, e denotamos por Γ ⊢ 𝛼.

Modelo para 𝑁

Note que até agora tratamos somente dos aspectos sintáticos da lógica clássica,
assim como da teoria que acabamos de dar como exemplo, a teoria 𝑁. Vamos usar a
teoria 𝑁 para explicar a abordagem semântica para a lógica clássica, a noção de
MODELO. Um MODELO (para uma teoria de primeira ordem) é uma estrutura que
INTERPRETA as constantes, símbolos funcionais e de predicado da teoria.

Consideremos o número zero, denotado pelo numeral 0, constante de nossa teoria

𝑁.

Consideremos o conjunto de números naturais ℕ = {0,1,2,3, … } o UNIVERSO para

nossa teoria. As variáveis individuais são símbolos da linguagem para representar
objetos de nosso domínio ou universo.

A função 𝑠 ∶ ℕ → ℕ será chamada de função sucessor.

A função + ∶ ℕ × ℕ → ℕ será chamada de função soma.

A função ⋅ ∶ ℕ × ℕ → ℕ será chamada de função produto.

A relação < ⊂ ℕ × ℕ será chamada de relação menor do que.

Os nove axiomas da teoria 𝑁 regulam a definição e comportamento dos símbolos da

teoria. Você irá perceber que os números naturais satisfazem estes axiomas, pois o
que estes axiomas determinam é a “estrutura” que existe nos números naturais. Veja:

Axioma N1: Afirma que para todo número do domínio, este número é diferente do seu
sucessor. De fato, os números naturais satisfazem esta propriedade, pois todo
número é distinto do seu sucessor.

Axioma N2: Afirma que se dois números têm os mesmos sucessores, então os dois
números são idênticos.

Axioma N3: Afirma que todo número somado com zero resulta nele mesmo.

Introdução à Lógica e Programação Página 43

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Axioma N4: Afirma que somar um número 𝑥 com o sucessor de 𝑦 é igual ao obter o
sucessor de 𝑥 + 𝑦. Veja que este axioma DEFINE a função de soma a partir da
função básica de sucessor.

Veja que podemos denotar 𝑠(0) = 1, então 0 + 1 = 0 + 𝑠(0) = 𝑠(0 + 0) = 𝑠(0) = 1;

usamos aqui a ideia da função sucessor, os axiomas N3 e N4.

Podemos agora denotar 𝑠(1) = 2 e 𝑠(2) = 3. Então:

1 + 1 = 1 + 𝑠(0) = 𝑠(1 + 0) = 𝑠(1) = 2

1 + 2 = 1 + 𝑠(1) = 𝑠(1 + 1) = 𝑠(2) = 3

E assim vamos “formalizando” os nomes e os valores da função sucessor para todos

os elementos de ℕ.

Axioma N5: Afirma que o produto de todo número por zero é igual a zero.

Axioma N6: Define a função produto. Veja:

1 ⋅ 1 = 1 ⋅ 𝑠(0) = 1 ⋅ 0 + 1 = 0 + 1 = 0 + 𝑠(0) = 𝑠(0 + 0) = 𝑠(0) = 1

1 ⋅ 2 = 1 ⋅ 𝑠(1) = 1 ⋅ 1 + 1 = 1 + 𝑠(0) = 𝑠(1 + 0) = 𝑠(1) = 2

1 ⋅ 3 = 1 ⋅ 𝑠(2) = 1 ⋅ 2 + 1 = 2 + 𝑠(0) = 𝑠(2 + 0) = 𝑠(2) = 3

Axioma N7: Afirma que nenhum número é menor do que 0.

Axioma N8: Afirma que se um número 𝑥 é menor do que o sucessor de 𝑦, então ou 𝑥

também é menor do que 𝑦, ou 𝑥 é exatamente igual a 𝑦.

Axioma N9: Afirma que para quaisquer dois números, ou deles é menor do que o
outro, ou eles são iguais.

Quando “interpretamos” os símbolos da teoria 𝑁 por este modelo, que estamos

chamando aqui de ℕ, dizemos que as fórmulas que são válidas nesta teoria são
consequências lógicas desta teoria, ou seja, uma consequência semântica da teoria,
pois toda estrutura ou modelo que satisfaz estes axiomas satisfazem os teoremas
desta teoria.

Logo, Γ ⊢ 𝛼, para Γ a axiomatização da teoria 𝑁, se e somente se ℕ ⊨ 𝛼, e isso

ocorre porque o TEOREMA DA COMPLETUDE também é válido para a Lógica
Clássica, isto é, as noções sintáticas e semânticas são equivalentes na lógica
clássica. Veja que ℕ é um MODELO para a teoria axiomatizada por Γ.

Introdução à Lógica e Programação Página 44

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Mais Alguns Exemplos

Não estamos sendo muito formais na forma como apresentamos os conceitos de

teoria de primeira ordem e de modelos. Há uma rica história sobre a evolução dessas
definições e reflexões sobre elas. De fato, existe toda uma área no campo da lógica
orientada para o estudo destes conceitos: a TEORIA DE MODELOS.

Por exemplo, ℕ é o modelo mais simples para a teoria 𝑁, mas existem muitas outras
estruturas que também são modelos para ela, ou seja, os “objetos” destas outras
estruturas funcionam “como se fossem” números naturais. E esta é a beleza da
Lógica e sua relação com a Matemática, ela mostra que o que importa, logicamente, é
a relação entre os objetos, e não os objetos em si. Qualquer “coisa” (estrutura) que
satisfaz os axiomas de Peano pode ser nomeada de número natural.

De fato, existem certos modelos para a teoria 𝑁 que não são ISOMORFOS ou
CATEGÒRICOS à estrutura ℕ; há modelos para a aritmética que são muito diferentes
do conjunto dos números naturais, como por exemplo, o da aritmética standard,
definido dentro da TEORIA DOS CONJUNTOS, em que é um modelo que tem
infinitas cadeias infinitas de números ordinais, a primeira cadeia infinita é composta
pelos números ordinais finitos, que são os “números naturais”, e outras infinitas
cadeias formadas, cada uma delas, por números ordinais infinitos, que usualmente
chamamos de ordinais transfinitos.

Porém, podemos axiomatizar a teoria dos números naturais em uma linguagem

quantificada de SEGUNDA ORDEM; e nesta axiomatização, prova-se, como
metateorema desta outra lógica, a LÓGICA QUANTIFICADA DE SEGUNDA ORDEM,
que todos os modelos da aritmética são isomorfos, ao contrário do que ocorre com os
modelos para a aritmética axiomatizados em primeira ordem

Grupos

Um grupo é uma estrutura matemática muito comum e importantíssima, tanto na área

da Álgebra quanto na área de Geometria. Qualquer estrutura que satisfaz os axiomas
da teoria de Grupos é um “GRUPO”.

A assinatura desta teoria é o conjunto ℒ𝐺 = {𝑒, −1 , ∗}. 𝑒 é uma constante, −1

um
símbolo funcional 1-ário e ∗ símbolo funcional 2-ário.

O comportamento destes símbolos não lógicos, na teoria 𝐺, é determinado pelos

axiomas não lógicos desta teoria.

Axiomas

G1. ∀𝑥∀𝑦∃𝑧(𝑥 ∗ 𝑦 = 𝑧) FECHO

G2. ∀𝑥∀𝑦∀𝑧((𝑥 ∗ 𝑦) ∗ 𝑧 = 𝑥 ∗ (𝑦 ∗ 𝑧)) ASSOCIATIVIDADE

Introdução à Lógica e Programação Página 45

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

G3. ∀𝑥(𝑥 ∗ 𝑒 = 𝑒 ∗ 𝑥 = 𝑥) ELEMENTO NEUTRO

G4. ∀𝑥∃𝑦(𝑦 = 𝑥 −1 ∧ (𝑥 ∗ 𝑥 −1 = 𝑥 −1 ∗ 𝑥 = 𝑒)) ELEMENTO INVERSO

Modelos

Grupo de Klein

Seja o conjunto {𝑒, 𝑎, 𝑏, 𝑐} e a operação ∗ definida sobre ele, dada pela tabela:

* 𝑒 𝑎 𝑏 𝑐
𝑒 𝑒 𝑎 𝑏 𝑐
𝑎 𝑎 𝑒 𝑐 𝑏
𝑏 𝑏 𝑐 𝑒 𝑎
𝑐 𝑐 𝑏 𝑎 𝑒
O elemento 𝑒 obviamente é o elemento inverso desta estrutura, vemos isso pelo
comportamento da operação ∗ na primeira linha e na primeira coluna.

Você pode verificar, fazendo os cálculos, que esta operação é associativa, e que
todos os elementos têm um inverso (eles mesmos), basta verificar a diagonal da
tabela da operação ∗.

Grupo ℤ módulo 𝑛

Seja 𝑛 um número natural maior do que 1. Definamos o conjunto

ℤ𝑛 = {0̅, 1̅, … , ̅̅̅̅̅̅̅
𝑛 − 1}. Cada elemento de ℤ𝑛 é o que chamamos de “classe de
equivalência”, em nosso caso, a classe de equivalência da divisão módulo 𝒏. Mas o
que é isso?

Para todo número natural 𝑥, podemos considerar a divisão inteira de 𝑥 por 𝑛. Quando
fazemos esta divisão, temos um quociente 𝑞 e um resto 𝑟, tal que 0 ≤ 𝑟 ≤ 𝑛 − 1. Se
dois números naturais divididos por 𝑛 têm o mesmo resto, dizemos que eles são
congruentes módulo 𝒏, e escrevemos 𝑥 ≡ 𝑦(𝑚𝑜𝑑(𝑛)); neste caso, dizemos que 𝑥 e
𝑦 estão na mesma classe de equivalência.

Se considerarmos 𝑒 a constante que denota a classe 0̅ e definirmos uma soma 𝑎̅ +

𝑏̅ = 𝑚
̅ , para 𝑚 ≡ ((𝑎 + 𝑏)𝑚𝑜𝑑(𝑛)) e 𝑚 < 5, como a operação ∗, então esta estrutura
construída é um grupo. Vamos dar um exemplo palpável.

Consideremos 𝑛 = 5. ℤ5 = {0̅, 1̅, 2̅, 3̅, 4̅}

Cada elemento deste conjunto é outro conjunto que contém infinitos números
naturais:

0̅ = {0, 5, 10, 15, 20, 25, … }

Introdução à Lógica e Programação Página 46

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

1̅ = {1, 6, 11, 16, 21, 26, … }

2̅ = {2, 7, 12, 17, 22, 27, … }

3̅ = {3, 8, 13, 18, 23, 28, … }

4̅ = {4, 9, 14, 19, 24, 29, … }

Note que quando dividimos todos os números em 3̅ por 5, obtemos o mesmo resto, o
número 3. Ou seja, todos esses números são “similares” em relação à congruência
módulo 5, o quão “distantes” eles estão dos múltiplos de 5.

Note também que temos esta tabela da operação +:

+ 0̅ 1̅ 2̅ 3̅ 4̅
0̅ 0̅ 1̅ 2̅ 3̅ 4̅
̅1 ̅1 ̅2 ̅3 ̅4 0̅
2̅ 2̅ 3̅ 4̅ 0̅ 1̅
3̅ 3̅ 4̅ 0̅ 1̅ 2̅
4̅ 4̅ 0̅ 1̅ 2̅ 3̅
Por cálculos você pode perceber que esta operação é associativa, e também todos os
2 + 3 = 5̅ = 0̅
elementos de ℤ5 têm inverso, por exemplo: 2̅ + 3̅ = ̅̅̅̅̅̅̅

Grupo de simetrias do quadrado

Podemos fazer 8 operações “geométricas” sobre um quadrado e ele permanece

visualmente “o mesmo”. Veja.

O conjunto de todas estas operações é denominado de 𝐷4 .

Introdução à Lógica e Programação Página 47

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Você pode verificar que considerando id a operação neutra, denotada na teoria de

grupos pela constante 𝑒, este conjunto 𝐷4 mais a operação ∗ de composição de
movimentos (fazer um após o outro) formam um grupo: o grupo das simetrias do
quadrado.

EXERCÍCIOS

1. Explique com suas palavras o significado dos 4 axiomas da teoria de grupos, assim
como foi feito no texto para a teoria da aritmética.

2. Seja Γ = {𝛼}, para 𝛼 = ∀𝑥∃𝑦∃𝑧(¬(𝑦 = 𝑧) ∧ ((𝑥 = 𝑦) ∨ (𝑥 = 𝑧)).

O que a teoria axiomatizada por Γ diz sobre seus modelos?

3. Quem são os elementos inversos do grupo ℤ7 ? Dica: construa a tabela para a

operação + neste grupo.

4. Considere no grupo ℤ24 , com operação +, a operação 𝑎̅ ⋅ 𝑏̅ = ̅̅̅̅̅̅

𝑎 ⋅ 𝑏 de produto.
Resolva a equação 6̅ ⋅ 𝑥 = 0̅.

5. Considere a estrutura organizada a partir do conjunto 𝐷4 no texto, com a operação

de composição ∗ definida. Por exemplo:

𝑟1 ∗ 𝑓𝑣 = 𝑓𝑑

Ou seja, se rotacionarmos o quadrado 90⁰ à direita e depois o refletirmos

verticalmente, temos como resultado a mesma figura que obteríamos se
simplesmente fizéssemos a reflexão diagonal deste quadrado na posição inicial.

Monte a tabela desta operação ∗, que possui 8 linhas e 8 colunas. Com esta tabela,
mostre que esta operação em 𝐷4 faz dele, de fato, um modelo para a teoria dos
conjuntos.

Depois, verifique quais são as operações inversas de cada um dos 8 elementos de

𝐷4 , responda também, analisando a tabela, se ∗ é uma operação comutativa.

Introdução à Lógica e Programação Página 48

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 6 – Álgebra de Boole e Circuitos lógicos

Uma álgebra de Boole é uma teoria de primeira ordem, cuja assinatura é ℒ𝐵 =

{0, 1, −, + ,⋅ }, no qual 0 e 1 são constantes, − uma operação ou símbolo funcional
unária, + e ⋅ duas operações ou funções binárias, que satisfazem estes axiomas,
dado um conjunto pressuposto como domínio com, no mínimo, dois elementos.

B1a. ∀𝑥∀𝑦∀𝑧(𝑥 + (𝑦 + 𝑧)) = ((𝑥 + 𝑦) + 𝑧) ASSOCIATIVIDADE

B1b. ∀𝑥∀𝑦∀𝑧(𝑥 ⋅ (𝑦 ⋅ 𝑧)) = ((𝑥 ⋅ 𝑦) ⋅ 𝑧)

B2a. ∀𝑥∀𝑦(𝑥 + 𝑦 = 𝑦 + 𝑥) COMUTATIVIDADE

B2b. ∀𝑥∀𝑦(𝑥 ⋅ 𝑦 = 𝑦 ⋅ 𝑥)

B3a. ∀𝑥∀𝑦(𝑥 + (𝑥 ⋅ 𝑦) = 𝑥) ABSORÇÃO

B3b. ∀𝑥∀𝑦(𝑥 ⋅ (𝑥 + 𝑦) = 𝑥)

B4a. ∀𝑥∀𝑦∀𝑧(𝑥 ⋅ (𝑦 + 𝑧)) = ((𝑥 ⋅ 𝑦) + (𝑥 ⋅ 𝑧)) DISTRIBUTIVIDADE

B4b. ∀𝑥∀𝑦∀𝑧(𝑥 + (𝑦 ⋅ 𝑧)) = ((𝑥 + 𝑦) ⋅ (𝑥 + 𝑧))

B5a. ∀𝑥(𝑥 + (−𝑥)) = 1 COMPLEMENTAÇÃO

B5b. ∀𝑥(𝑥 ⋅ (−𝑥)) = 0

Logo, uma algebra de Boole é qualquer estrutura que satisfaça os axiomas acima.
Exemplos:

1. O conjunto 𝑉 = {0,1}, com as operações −0 = 1 e −1 = 0, 0 ⋅ 0 = 0 ⋅ 1 = 0 e 1 ⋅ 1 =

1, 0 + 0 = 0 e 1 + 0 = 1 + 1 = 1 é uma álgebra de Boole.

2. Seja 𝐴 um conjunto não-vazio e consideremos o conjunto com no mínimo dois

elementos, ℘(𝐴), que contém, pelo menos, ∅ = 0 e 𝐴 = 1.

Definimos sobre ℘(𝐴) as operações −𝑎 = 𝑎𝐶 (operação do conjunto complementar),

𝑎 + 𝑏 = 𝑎⋃𝑏 a união de conjuntos e 𝑎 ⋅ 𝑏 = 𝑎 ∩ 𝑏 a intersecção de conjuntos. O
conjunto ℘(𝐴) com as operações definidas formam uma álgebra de Boole.

Introdução à Lógica e Programação Página 49

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

3. Seja 𝑉𝑎𝑟(𝐿) o conjunto de variáveis proposicionais e 𝑣: 𝑉𝑎𝑟(𝐿) → {𝑉, 𝐹} uma função

qualquer. Podemos estender a função 𝑣 sobre todas as fórmulas de L, 𝐹𝑜𝑟(𝐿),
definindo:

𝑉(𝑝) = 𝑣(𝑝)

𝑉(¬𝛼) = ¬𝑉(𝛼)

𝑉(𝛼 ∨ 𝛽) = 𝑉(𝛼) ∨ 𝑉(𝛽)

Definimos assim uma nova função 𝑉: 𝐹𝑜𝑟(𝐿) → {𝑉, 𝐹} que é uma valoração booleana
para as fórmulas da linguagem proposicional.

Sejam:

0 = {𝛼 ∈ 𝐹𝑜𝑟(𝐿) | 𝑉(𝛼) = 𝐹 𝑝𝑎𝑟𝑎 𝑞𝑢𝑎𝑖𝑠𝑞𝑢𝑒𝑟 𝑓𝑢𝑛çõ𝑒𝑠 𝑉} - formulas contraditórias

1 = {𝛼 ∈ 𝐹𝑜𝑟(𝐿) | 𝑉(𝛼) = 𝑉 𝑝𝑎𝑟𝑎 𝑞𝑢𝑎𝑖𝑠𝑞𝑢𝑒𝑟 𝑓𝑢𝑛çõ𝑒𝑠 𝑉}.- fórmulas tautológicas

Também definimos a seguinte relação (relação de equivalência) entre as fórmulas de

𝐿:

Duas fórmulas 𝛼 e 𝛽 de L são equivalentes se for tautológica a fórmula 𝛼 ↔ 𝛽, isso

significa que o valor de verdade da fórmula 𝛼 será o mesmo valor de verdade para a
fórmula 𝛽, independentemente da valoração booleana 𝑉.

Definimos o conjunto [𝛼] = { 𝛽 ∈ 𝐹𝑜𝑟(𝐿) | 𝛼 ↔ 𝛽} que chamamos de CLASSE DE

EQUIVALÊNCIA da fórmula 𝛼. Esta classe contém todas as fórmulas equivalentes à
𝛼. Logo, 0 e 1 são duas destas classes, a classe de equivalência de todas as
contradições e a classe de equivalência de todas as tautologias, respectivamente.

Podemos definir o conjunto [𝐿] = { [𝛼] | 𝛼 ∈ 𝐿} de todas as classes de equivalência

de nossa linguagem da lógica proposicional. Obviamente 0 ∈ [𝐿] e 1 ∈ [𝐿].

Definiremos as operações da assinatura da álgebra de Boole da seguinte forma:

−[𝛼] = [¬𝛼]

[𝛼] + [𝛽] = [𝛼 ∨ 𝛽]

[𝛼] ⋅ [𝛽] = [𝛼 ∧ 𝛽]

O conjunto [𝐿] é uma álgebra de Boole; de fato, uma álgebra de Boole muito especial,
chamada de Álgebra de Lindenbaum. Uma forma alternativa de demonstrar o
(meta)Teorema da Completude para a lógica proposicional é utilizando uma álgebra
de Lindenbaum como semântica para essa lógica.

Introdução à Lógica e Programação Página 50

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Circuitos Lógicos

Um circuito lógico é um dispositivo que utiliza os conceitos de uma álgebra de Boole

para dar uma representação do funcionamento de um circuito digital. Para isso,
precisamos ter alguns conceitos esclarecidos:

Circuito lógico ou circuito digital: são circuitos eletroeletrônicos que utilizam a

corrente, em dois tipos de tensão (presença de corrente ou não) para representar
informações.

Sistema binário: qualquer sistema de representação que contenha somente dois

símbolos.

As máquinas eletrônicas mais simples possíveis são aquelas que possuem somente
duas alternativas para cada ponto de um de seus circuitos: há corrente elétrica
passando neste ponto ou não? Por isso, elas trabalham com dois níveis de
informação:

Nível lógico 0 Nível lógico 1

Falso Verdadeiro
Desligado Ligado
Baixo Alto
Não Sim
Chave aberta Chave fechada

Portas de um circuito lógico

Porta AND

É a porta que considera a operação lógica de conjunção:

Note que em um circuito de porta AND, o resultado x após a entrada no circuito

depende da situação no circuito nos pontos de entrada, no caso A e B.

Para descobrir o “valor” de x no circuito (se há ou não corrente em x) depois de uma

porta do tipo AND, basta considerarmos a tabela de verdade do operador lógico
conjunção (E).

Veja que em uma porta AND, a operação é sinalizada com a operação de produto de
uma álgebra de Boole.

Introdução à Lógica e Programação Página 51

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Porta OR

É a porta que considera a operação lógica de disjunção:

Note que em um circuito de porta OR, o resultado x após a entrada no circuito

depende da situação no circuito nos pontos de entrada, no caso A e B.

Para descobrir o “valor” de x no circuito (se há ou não corrente em x) depois de uma

porta do tipo OR, basta considerarmos a tabela de verdade do operador lógico
disjunção (OU). Nesta porta, a operação é representada pela soma de uma álgebra
de Boole.

Porta NOT

É a porta que considera a operação lógica de negação:

Note que em um circuito de porta NOT, o resultado x após a entrada no circuito

depende da situação no circuito no ponto de entrada A, que é único.

Para descobrir o “valor” de x no circuito (se há ou não corrente em x) depois de uma

porta do tipo NOT, basta considerarmos a tabela de verdade do operador lógico
negação (NÃO). Nesta porta, a operação é sinalizada pelo complementar ̅ .

Qual a expressão lógica que representa o circuito a seguir?

Introdução à Lógica e Programação Página 52

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

No circuito anterior, se A e B forem falsos e C verdadeiro, qual a condição de corrente

no último ponto do circuito?

EXERCÍCIOS

1. Mostre que o conjunto das partes de um conjunto unitário qualquer, com as

operações de união, intersecção e complementar, forma uma álgebra de Boole.

2. Mostre que uma álgebra de Lindenbaum satisfaz os axiomas de uma álgebra de

Boole, sendo portanto um modelo para esta teoria.

3. Desenhe as portas lógicas que resolvem os seguintes problemas.

a) Uma lâmpada deverá ser acesa se 1. o sensor de movimento detectar movimento e

2. o sensor de luz detectar que a lâmpada não está acesa.

b) Em um avião com três banheiros, se uma das portas estiver fechada por dentro seu
sensor tem valor lógico 1. Uma lâmpada de sinalização fica acesa se pelo menos um
dos banheiros estiver disponível.

4. Desenhe o circuito que representa a seguinte expressão lógica

𝑆 = 𝐴 ⋅ 𝐵 ⋅ 𝐶 + (𝐴 + 𝐵) ⋅ 𝐶

5. Expresse a fórmula lógica representada pelo circuito lógico a seguir.

Introdução à Lógica e Programação Página 53

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 7 – Sistema Binário de Numeração

Sistema decimal de numeração

Nós utilizamos um sistema decimal para representarmos quantidades (números). Este

sistema é uma linguagem, que possui 10 símbolos, por isso sistema decimal, que
chamamos de algarismos: 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9. Ao concatenarmos estes
símbolos formamos “palavras”, os numerais. Estas palavras são signos, símbolos,
cujo significante, o seu sentido, são quantidades numéricas, ou números. É
importante diferenciarmos todos estes conceitos. Por exemplo:

a) 1 é um algarismo e um numeral, que representa o número 1 (UM).

b) 12 é um numeral que representa o número DOZE, sendo formado por dois

algarismos: 1 e 2

Veja que tanto nos números um e doze, representados no sistema decimal de

numeração, o algarismo 1 aparece. Porém, a quantidade que este algarismo
representa em cada um destes numerais é diferente, pois depende da posição em
que este algarismo aparece. Por isso, nosso sistema de numeração é chamado de
sistema de numeração posicional, pois o sentido de cada “letra” (algarismo) depende
da posição em que ela aparece na “palavra” (numeral).

No sistema decimal de numeração, cada posição representa uma ORDEM.

Ordem da unidade: 100 = 1

Ordem da dezena: 101 = 10

Ordem da centena: 102 = 100

Ordem da unidade de milhar: 103 = 1000

etc

Precisamos das “ordens”, pois nosso “alfabeto” tem somente 10 símbolos. Quando
esgotamos o uso de 10 símbolos, precisamos “ressignificar” o sentido do símbolo
para representar quantidades maiores do que dez (0 é a primeira quantidade, a
quantidade “vazia” ou nula).

Costumamos denotar esta representação na base 10 da seguinte forma para indicar o

número que cada numeral representa:

(12)10 = 10 + 2 = 1 ⋅ 101 + 2 ⋅ 100

Introdução à Lógica e Programação Página 54

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Veja outros exemplos:

(325)10 = 300 + 20 + 5 = 3 ⋅ 102 + 2 ⋅ 101 + 5 ⋅ 100

(45019)10 = 4 ⋅ 104 + 5 ⋅ 103 + 0 ⋅ 102 + 1 ⋅ 101 + 9 ⋅ 100

Note que o lado esquerdo é uma “palavra” no sistema decimal de numeração, a

sequência XXX que representamos por (𝑋𝑋𝑋)10, e o lado direito é uma quantidade, a
quantidade representada pelo numeral.

EXERCÍCIOS

1. (ITA) adicionando-se 100 a um número natural 𝑛 obtemos um quadrado perfeito;

adicionando-se 168 a 𝑛, obtemos outro quadrado perfeito. Qual é o número 𝑛?

2. (FUVEST) Um número inteiro positivo 𝑛 de quatro algarismos decimais satisfaz as

seguintes condições:

I. A soma dos quadrados dos 1° e 4° algarismos é 58.

II. A soma dos quadrados dos 2° e 3° algarismos é 52.

III. Se deste número 𝑛 subtrairmos o número 3816, obteremos um número formado

pelos mesmos algarismos do número 𝑛, mas na ordem contrária.

Qual é esse número?

3. (UNICAMP) Um determinado ano da última década do século XX é representado,

na base 10, pelo número abba e um outro, da primeira década do século XXI, é
representado, também na base 10, pelo número cddc.

a) Escreva esses dois números.

b) A que século pertencerá o ano representado pela soma abba + cddc?

4. (PUC) Para a orientação dos maquinistas, ao longo de uma ferrovia existem placas
com a indicação da quilometragem. Um trem percorre essa ferrovia em velocidade
constante e, num dado instante, seu maquinista observa uma placa em que o número
indicador da quilometragem tinha 2 algarismos. Após 30 minutos, ele passa por uma
outra em que, curiosamente, os algarismos assinalados eram os mesmos da primeira,
só que escritos na ordem inversa. Decorridos 30 minutos de sua passagem pela
segunda placa, ele passa por uma terceira em que o número marcado tinha os
mesmos algarismos das anteriores, mas na mesma ordem dos da primeira e com um
zero intercalado entre eles. Nessas condições, qual a velocidade desse trem, em
quilômetros por hora?

Introdução à Lógica e Programação Página 55

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Sistema binário de numeração

Caso tenhamos uma linguagem com somente dois símbolos para representar
quantidades numéricas dizemos que temos um sistema binário de numeração.

O sistema binário de numeração é muito importante para a área da eletrônica, pois

como vimos na análise dos circuitos lógicos, é a forma elementar de funcionamento
de qualquer circuito e, portanto, de máquinas e computadores. Temos sempre duas
situações: aberto/fechado; funcionando/não-funcionado; corrente elétrica/não corrente
elétrica.

Em função desta interpretação, a linguagem utilizada no sistema binário de

numeração é formada pelos símbolos 0 e 1. Portanto, no sistema binário de
numeração, todas as quantidades ou números são escritos usando estes dois
símbolos.

Escrevendo números no sistema binário

Os números zero e um são fáceis de serem escritos, pois temos símbolos para os
dois:

zero = “0” e um = “1”

Ou seja:

(0)2 = 0 = 0 ⋅ 20

(1)2 = 1 = 1 ⋅ 20

Veja que podemos usar a mesma lógica para representar números na base 10, com
cada ordem “valendo” potências de dez, e reproduzir esta lógica na representação de
quantidades numérica em uma base binária, usando potências de 2.

Como 2 = 21 este número pode ser escrito em numeração binária desta forma:

2 = 1 ⋅ 21 + 0 ⋅ 20 = (10)2

Ou seja, para escrevermos números no sistema binário de numeração, precisamos

escrever as quantidades usando potências de base dois.

3 = 2 + 1 = 1 ⋅ 21 + 1 ⋅ 20 = (11)2

4 = 4 = 1 ⋅ 22 + 0 ⋅ 21 + 0 ⋅ 20 = (100)2

5 = 4 + 1 = 1 ⋅ 22 + 0 ⋅ 21 + 1 ⋅ 20 = (101)2

6 = 4 + 2 = 1 ⋅ 22 + 1 ⋅ 21 + 0 ⋅ 20 = (110)2

7 = 4 + 2 + 1 = 1 ⋅ 22 + 1 ⋅ 21 + 1 ⋅ 20 = (111)2
Introdução à Lógica e Programação Página 56
 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

EXERCÍCIOS

1. Escreva os seguintes números no sistema binário de numeração.

8, 9, 10, 11, 12, 13, 14, 15, 16

2. Escreva os seguintes números como soma de potências de base 2:

a) 48

b) 64

c) 89

d) 100

3. Usando o exercício anterior, escreva os números a seguir no sistema binário de

numeração.

a) 48

b) 64

c) 89

d) 100

4. Converta para o sistema decimal os números a seguir:

a) (11011110)2

b) (1100001011)2

c) (10101010110)2

d) (100001111001)2

5. Se um número no sistema binário termina com o algarismo “0”, o que podemos

falar sobre este número? E se ele termina com o algarismo “1”?

Introdução à Lógica e Programação Página 57

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Representação de números decimais no sistema binário

Como podemos representar quantidades não inteiras no sistema binário de

numeração?

Assim como representamos as quantidades inteiras utilizando a decomposição do

número como soma de potências de dois, também representamos as quantidades
fracionárias ou decimais utilizando potências de dois. Como estas quantidades são
menores do que um, então estas potências de dois terão expoente negativo. Veja:

2−1 = 0,5

2−2 = 0,25

2−3 = 0,125

2−4 = 0,0625

etc

Exemplo:

0,625 = 0,50 + 0,125

Portanto 0,625 = 0 + 1 ⋅ 2−1 + 0 ⋅ 2−2 + 1 ⋅ 2−3 = (0,101)2

É possível escrever QUALQUER número decimal na base 2? Sim, basta escrever

como a soma (decimal) das potências de base dois com expoente negativo,
decompondo estes valores.

Exemplo:

0,8 = 0,5 + 0,25 + 0,03125 + 0,015625 + ...

Neste caso, a representação decimal do número é finita, MAS a representação binária

é uma dízima (periódica):

0,8 = (0,110011001100 … )2

Método prático

Para representar números decimais, podemos utilizar este mecanismo prático:

1. Multiplicamos a parte decimal por dois.

Introdução à Lógica e Programação Página 58

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

a. se o número for maior do que um, colocamos “1” naquela posição do sistema
binário.

b. se o número for menor do que um, colocamos “0” naquela posição do sistema
binário.

2. Descartamos a parte “inteira” do cálculo anterior.

3. Para preencher a nova posição no sistema binário, repetimos o passo 1 com a

nova parte fracionária.

4. O processo finaliza quando a parte decimal for igual a zero ou teremos uma
representação infinita (dízima).

Exemplo:

A) Representação no sistema binário de 0,625.

1. 0,625 × 2 = 1,25

1.a 0,625 = (0,1 … )2

2. 0,25

1. 0,25 × 2 = 0,5 (processo repete)

1.b 0,625 = (0,10 … )2

2. 0,5

1. 0,5 × 2 = 1,0 (processo finaliza)

1.a 0,625 = (0,101)2

B) Representação no sistema binário do número 0,8.

1. 0,8 × 2 = 1,6

1.a 0,8 = (0,1 … )2

2. 0,6

1. 0,6 × 2 = 1,2 (processo repete)

1.a 0,8 = (0,11 … )2

2. 0,2

Introdução à Lógica e Programação Página 59

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

1. 0,2 × 2 = 0,4 (processo repete)

1.b 0,4 = (0,110 … )2

2. 0,4

1. 0,4 × 2 = 0,8 (processo repete)

1.b 0,4 = (0,1100 … )2

Veja que retornamos ao passo de transformação de 0,8, portanto temos uma dízima
na representação deste número no sistema binário de numeração.

C) Representação no sistema binário do número 12,345.

12 = 8 + 4

logo 12 = 1100

Representemos agora a parte decimal 0,345.

1. 0,345 × 2 = 0,69

1.b 0,345 = (0,0 … )2

2. 0,69

1. 0,69 × 2 = 1,38

1.a 0,345 = (0,01 … )2

2. 0,38

1. 0,38 × 2 = 0,76

1.b 0,345 = (0,010 … )2

2. 0,76

1. 0,76 × 2 = 1,52

1.a 0,345 = (0,010𝟏 … )2

2. 0,52

1. 0,52 × 2 = 1,04

1.a 0,345 = (0,010𝟏1 … )2

2. 0,04

Introdução à Lógica e Programação Página 60

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

1. 0,04 × 2 = 0,08

1.b 0,345 = (0,010𝟏10 … )2

2. 0,08

1. 0,08 × 2 = 0,16

1.b 0,345 = (0,010𝟏100 … )2

2. 0,16

1. 0,16 × 2 = 0,32

1.b 0,345 = (0,010𝟏1000 … )2

2. 0,32

1. 0,32 × 2 = 0,64

1.b 0,345 = (0,010𝟏10000 … )2

2. 0,64

1. 0,64 × 2 = 1,28

1.a 0,345 = (0,010𝟏100001 … )2

2. 0,28

1. 0,28 × 2 = 0,56

1.b 0,345 = (0,010𝟏1000010 … )2

2. 0,56

1. 0,56 × 2 = 1,12

1.a 0,345 = (0,010𝟏10000101 … )2

2. 0,12

1. 0,12 × 2 = 0,24

1.b 0,345 = (0,010𝟏100001010 … )2

2. 0,24

1. 0,24 × 2 = 0,48

1.b 0,345 = (0,010𝟏1000010100 … )2

2. 0,48

Introdução à Lógica e Programação Página 61

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

1. 0,48 × 2 = 0,96

1.b 0,345 = (0,010𝟏10000101000 … )2

2. 0,96

1. 0,96 × 2 = 1,92

1.a 0,345 = (0,010𝟏100001010001 … )2

2. 0,92

1. 0,92 × 2 = 1,84

1.a 0,345 = (0,010𝟏1000010100011 … )2

2. 0,84

1. 0,84 × 2 = 1,68

1.a 0,345 = (0,010𝟏10000101000111 … )2

2. 0,68

1. 0,68 × 2 = 1,36

1.a 0,345 = (0,010𝟏100001010001111 … )2

2. 0,36

1. 0,36 × 2 = 0,72

1.b 0,345 = (0,010𝟏1000010100011110 … )2

2. 0,72

1. 0,72 × 2 = 1,44

1.a 0,345 = (0,010𝟏10000101000111101 … )2

2. 0,44

1. 0,44 × 2 = 0,88

1.b 0,345 = (0,010𝟏100001010001111010 … )2

2. 0,88

1. 0,88 × 2 = 1,76

1.a 0,345 = (0,010𝟏1000010100011110101 … )2

2. 0,76

Introdução à Lógica e Programação Página 62

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Veja que retornamos a um ponto em que há havíamos passado, mostrando que

temos uma dízima.

̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅)2
12,345 = (1100,01011000010100011110101

EXERCÍCIOS

1. Converta os números a seguir para representação na base binária.

a) 17,75 b) 8,1 c) 8,3125 d) 35,71875

Introdução à Lógica e Programação Página 63

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 8 – Funções recursivas e computabilidade

Sabemos que para calcular o fatorial de um número natural 𝑛, podemos estabelecer o

seguinte procedimento:

𝑛! = 𝑛 ⋅ (𝑛 − 1)!

Ou seja, se soubermos o fatorial de seu antecessor, 𝑛 − 1, para calcularmos o fatorial

de 𝑛 basta multiplicarmos o fatorial de seu sucessor por 𝑛.

Este processo explicita o funcionamento de uma função recursiva. A partir de um ou

mais valores iniciais (número finito) para valores de uma destas funções, dadas
algumas descrições objetivas de passos finitos, podemos calcular outros valores
destas funções.

Vamos lembrar!

Uma função (matemática) é uma relação entre dois conjuntos, A e B, dada por uma
“regra” ou “fórmula” 𝑓, a partir do qual, para cada 𝑥 ∈ 𝐴 existe um único 𝑦 ∈ 𝐵 tal que
𝑓(𝑥) = 𝑦, ou seja, aplicando a regra 𝑓 no número 𝑥 obtemos o número 𝑦.

O “tamanho” do conjunto A nos dá a aridade da função. Por exemplo, supomos que o

domínio da função 𝑓: 𝐴 → 𝐵, o conjunto A, seja um produto cartesiano, digamos 𝐴 =
ℝ × ℝ × ℕ, então esta função é sempre aplicada em uma TRIPLA ORDENADA da
forma (𝑥, 𝑦, 𝑧), no qual 𝑥 e 𝑦 são variáveis para números reais e 𝑧 um número natural.

O valor desta função 𝑓(𝑥, 𝑦, 𝑧) ∈ 𝐵, o conjunto contradomínio. Este valor também

depende da natureza do conjunto 𝐵, digamos neste caso que 𝐵 = ℕ × ℝ. Então a
fórmula desta função poderia ser algo deste tipo:

𝑓(𝑥, 𝑦, 𝑧) = (𝑧, 𝑧𝑦 − 𝑧𝑥)

Definindo a função fatorial

No caso da função fatorial, podemos considerar esta definição:

𝐹𝑎𝑡: ℕ → ℕ

𝐹𝑎𝑡(0) = 1
{
𝐹𝑎𝑡(𝑛) = 𝑛 ⋅ 𝐹𝑎𝑡(𝑛 − 1) 𝑝𝑎𝑟𝑎 𝑛 > 0

Veja que temos uma lista de duas instruções: Se o argumento inicial da função for 0,
o valor da função será 1. Se o argumento da função for maior do que zero, então o
valor da função é seu argumento vezes o valor da função no argumento anterior.

Isto caracteriza a noção de recursividade da função. Veja que um fato importante,

neste caso, é que estamos calculando a função no conjunto dos números naturais,
onde é possível apontarmos um antecessor para qualquer número. Se o domínio
Introdução à Lógica e Programação Página 64
 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

fosse o conjunto dos números racionais ou dos reais, isso se torna impossível (não há
um anterior ou posterior de qualquer número racional ou real, pois estes conjuntos
são DENSOS).

Note que esta propriedade de recursividade nos garante que uma “máquina” poderia
ser capaz de calcular o valor desta função, pois ela “sabe” o valor inicial da função e,
a partir dele, reproduzindo um mesmo passo, calcular todos os outros valores. Veja:

𝐹𝑎𝑡(0) = 1

𝐹𝑎𝑡(1) = 1 ⋅ 𝐹𝑎𝑡(0) = 1

𝐹𝑎𝑡(2) = 2 ⋅ 𝐹𝑎𝑡(1) = 2

𝐹𝑎𝑡(3) = 3 ⋅ 𝐹𝑎𝑡(2) = 6

𝐹𝑎𝑡(4) = 4 ⋅ 𝐹𝑎𝑡(3) = 24

𝐹𝑎𝑡(5) = 5 ⋅ 𝐹𝑎𝑡(4) = 120

etc

Construção de funções recursivas

Como notado, as funções recursivas são funções computáveis, ou seja, todas as

funções recursivas podem ser programadas por uma maquina ou um computador.
Veja que ainda NÃO afirmamos que todas as funções computáveis são recursivas
(condição necessária e suficiente); para falarmos sobre este assunto, precisaremos
avaliar mais algumas considerações.

Podemos demonstrar que TODAS as funções recursivas podem ser obtidas a partir
de um conjunto de funções básicas, a partir da repetição de três processos para
formar funções a partir de outras.

Funções básicas

• Função constante zero

Seja A um conjunto numérico qualquer e B um conjunto numérico com o número zero.

A função 𝑧: 𝐴 → 𝐵 cuja regra é 𝑧(𝑥) = 0 para todo 𝑥.

Digite a equação aqui.

Introdução à Lógica e Programação Página 65

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

• Função sucessor

Seja A um conjunto numérico enumerável e B um conjunto numérico que contenha A.

A função 𝑠: 𝐴 → 𝐵 cuja regra é 𝑠(𝑥) = sucessor de 𝑥 para todo 𝑥.

• Funções projeção

Seja A um conjunto qualquer e B um conjunto que é um dos fatores de A.

Se A for um conjunto formado por um produto cartesiano de 𝑛 conjuntos,

𝑛
𝐴 = 𝐴1 × … × 𝐴𝑛 . A função 𝑖𝑑𝑚 : 𝐴1 × … × 𝐴𝑛 → 𝐴𝑚 , para 0 ≤ 𝑚 ≤ 𝑛.
𝑛 (𝑥
𝑖𝑑𝑚 1 , … , 𝑥𝑛 ) = 𝑥𝑚

Esta função projeta uma das entradas do elemento de seu domínio.

Exemplos

1) 𝑖𝑑11 : 𝐴 → 𝐴 𝑖𝑑11 (𝑥) = 𝑥 (por isso esta função também é chamada de

identidade)

2) 𝑖𝑑23 : 𝐴1 × 𝐴2 × 𝐴3 → 𝐴2 𝑖𝑑23 (𝑥, 𝑦, 𝑧) = 𝑦

Processos para obtenção de funções recursivas

Há três processos para obtenção de funções recursivas.

I. Composição

Sejam 𝑓, função de aridade 𝑚, e 𝑔1 , … , 𝑔𝑚 funções de aridade 𝑛. Podemos “compor”

ou “substitui” estas funções para obter uma nova função ℎ de aridade 𝑛.

ℎ(𝑥1 , … , 𝑥𝑛 ) = 𝑓(𝑔1 (𝑥1 , … , 𝑥𝑛 ), … , 𝑔𝑚 (𝑥1 , … , 𝑥𝑛 ))

Exemplo: Funções constantes (naturais)

A primeira função constante é a função zero 𝑧.

A segunda função constante é a função 𝑐𝑜𝑛𝑠𝑡1 (𝑥) = 𝑠(𝑧(𝑥)) que é a composição das
funções zero e sucessor.

A terceira função constante é a função 𝑐𝑜𝑛𝑠𝑡2 (𝑥) = 𝑠(𝑐𝑜𝑛𝑠𝑡1 (𝑥)) que é a composição
das funções sucessor e 𝑐𝑜𝑛𝑠𝑡1 .

Introdução à Lógica e Programação Página 66

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

II. Recursão primitiva

Sejam 𝑓 e 𝑔 funções de aridade 1 e 3, respectivamente. Dizemos que estas funções

definem uma função recursiva ℎ por recursão primitiva, se a função ℎ satisfizer:

ℎ(𝑥, 0) = 𝑓(𝑥) e ℎ(𝑥, 𝑠(𝑦)) = 𝑔(𝑥, 𝑦, ℎ(𝑥, 𝑦))

Exemplo: Função soma (naturais)

Considere as funções 𝑠𝑜𝑚𝑎(𝑥, 0) = 𝑖𝑑(𝑥) e 𝑖𝑑33 (𝑥, 𝑦, 𝑠𝑜𝑚𝑎(𝑥, 𝑦))

Então podemos calcular o valor da função soma para todo par de números naturais,
considerando que 𝑠𝑜𝑚𝑎(𝑥, 𝑠(𝑦)) = 𝑠 (𝑖𝑑33 (𝑥, 𝑦, 𝑠𝑜𝑚𝑎(𝑥, 𝑦)))

Veja que usamos, além da recursão primitiva, a composição com a função sucessor.

Um segundo exemplo para uso do processo de recursão primitiva é usar uma função
auxiliar para construir a função fatorial, utilizando as definições dadas. Como este
exemplo extrapola a complexidade deste material, vamos só mencionar que aquela
função fatorial do início do capítulo pode ser escrita usando somente a função 𝑐𝑜𝑛𝑠𝑡1 ,
as funções identidade e 𝑖𝑑33 e 𝑖𝑑23 , assim como a função sucessor, combinando-as por
meio de composição e recursão primitiva. Isso prova, de maneira formal, que a função
fatorial, como intuitivamente constatamos, é de fato uma função recursiva.

III. Minimização

Suponhamos que 𝑓 seja uma função recursiva de aridade 𝑛 + 1. Então podemos

definir uma nova função recursiva ℎ, de aridade 𝑛, da seguinte forma:

𝑜 𝑚𝑒𝑛𝑜𝑟 𝑦 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑓(𝑥1 , … , 𝑥𝑛 , 𝑦) = 0, 𝑠𝑒 𝑒𝑙𝑒 𝑒𝑥𝑖𝑠𝑡𝑒

ℎ(𝑥1 , … , 𝑥𝑛 ) = {
𝑖𝑛𝑑𝑒𝑓𝑖𝑛𝑖𝑑𝑎, 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜

EXERCÍCIO

1. Considere o fato de que para todos os números naturais x e y:

𝑥⋅0=0 e 𝑥 ⋅ 𝑠(𝑦) = 𝑥 ⋅ 𝑦 + 𝑥

Mostre que a função produto é recursiva.

Introdução à Lógica e Programação Página 67

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 9 - Números ordinais finitos e a Aritmética standard

Anteriormente mostramos como axiomatizar um sistema dedutivo cuja semântica, seu
modelo, se comporte como esperamos que se comportem os números naturais, por
meio dos axiomas de Peano, que caracterizam uma teoria de primeira ordem.

Todavia, esta abordagem para os números naturais é um pouco “forçada”, já que

comentamos que “qualquer” coisa que satisfaça esses axiomas pode ser considerada
um “número natural”, e os axiomas não explicitam a regra, lei ou a fórmula da função
sucessor, a partir do qual construímos as outras operações matemáticas envolvendo
números naturais.

Teoria Ingênua dos Conjuntos e Teoria dos Conjuntos

Sabe todas aquelas operações com conjuntos que podemos representar usando os
diagramas de Venn? A forma de abordagem para o conceito matemático de conjunto
e suas operações na escola é o que chamamos atualmente de Teoria Ingênua dos
Conjuntos. Por um longo tempo, essa era a única abordagem possível para estes
conceitos, porém, no final do século XIX, uma tentativa de dar uma fundamentação
rigorosa para TODA a matemática, e não somente para o cálculo diferencial e
integral, levou a alguns pesquisadores a utilizar conceitos formais da lógica para
fundamentar todos estes conceitos muito utilizados em matemática, como o conceito
de função, indo além da fundamentação que já ocorrera no campo da Análise
Matemática (uma das áreas da Matemática). O grande responsável por dar o
tratamento contemporâneo para o que chamamos hoje de Teoria dos Conjuntos foi
George Cantor, e toda a abordagem anterior para estes conceitos, menos rigorosa,
passou a ser chamado de teoria ingênua dos conjuntos. Antes de delinearmos esta
teoria, vamos recompor sua trajetória histórica.

Primeiramente, Gotlob Frege formulou, em linguagem de primeira ordem, uma teoria

para os números naturais, utilizando os axiomas de Peano – cujas ideias remontam
para outros matemáticos até o final do século XVII. Todavia, esta teoria lógica não
fundamentava “O QUE” era um número natural, apenas dava indícios de como se
deveria comportar qualquer coisa que chamássemos de número natural.

Cantor foi capaz de ir além, ao invés de dar o comportamento dos números naturais
por meio de uma axiomática, ele propôs uma teoria lógica mais elementar que
determina o comportamento de um objeto ao qual chamamos de CONJUNTO e, nesta
teoria, ele pode CONSTRUIR praticamente todos os objetos matemáticos existentes
até então, por meio destes blocos básicos, os conjuntos – ou seja, os conjuntos
seriam os átomos para a matemática: Tudo é feito de conjuntos. Com isso, pode-se
dar uma definição rigorosa e formal do que seria um NÚMERO, pelo menos no que
concerne ao interesse do matemático, sem se preocupar com a “natureza” daquilo
que usualmente é chamado como número no cotidiano (números “existem” ou são

Introdução à Lógica e Programação Página 68

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

objetos fictícios? Se eles existem, existem como entes abstratos ou como entes
concretos? – essas perguntas são restritas ao trabalho de quem faz Filosofia da
Matemática, o matemático profissional, por sua vez, enquanto FAZ matemática, não
precisa ter essas respostas (se é que elas existem), mas precisa ter conceitos
logicamente corretos para embasar seu trabalho, e isto foi feita pela Teoria dos
Conjuntos).

Vamos adotar neste material uma abordagem mais direta e menos formal do que
aquela da Teoria dos Conjuntos contemporânea, sem entrarmos nesses detalhes
lógicos extremamente técnicos. Basta que você saiba que todas essas construções
podem ser feitas em uma linguagem de primeira ordem, dentro de uma teoria que
possui 8 ou 9 axiomas não-lógicos (de acordo com a axiomatização adotada), o que
chamamos de Teoria dos Conjuntos. Nesta teoria, consegue-se provar, por dedução
na lógica clássica, todas as operações conjuntistas.

Cantor (1845 – 1918) era ainda um matemático sem uma cadeira definitiva em uma
universidade quando publicou seus trabalhos revolucionários. Ao publicá-los, além de
dar uma fundamentação rigorosa para toda a matemática, ele também mostrou que
muito do que se acreditava à época estará incorreto, por exemplo, ele demonstrou a
ideia de que pudessem existir “diferentes” infinitos e que existiriam infinitos em ato, e
não somente a ideia aristotélica, defendida até então, de que o conceito de infinito era
uma entidade somente em potencial, e nunca em ato (esta crença era dos
matemáticos ocidentais. A cultura indiana, por seu turno, já possuía séculos antes de
Cristo a ideia de infinitos em ato e distintos entre si, tanto que eles possuíam 16
palavras com significados diferentes para representar conceitos distintos para coisas
infinitas).

Essa foi uma das principais razões que fizeram com que muitos matemáticos
contemporâneos a Cantor não dessem atenção à sua pesquisa, ou mesmo atuassem
para combatê-la, entre eles, o matemático Kronecker, a quem atribuiu-se ser o
principal responsável por Cantor nunca ter conseguido obter emprego estável como
professor; as dificuldades financeiras pelas quais Cantor passou, junto de outros
problemas familiares e de saúde, fizeram com que ele terminasse seus dias em uma
instituição de saúde com problemas mentais. Porém, poucos anos após a publicação
de seus trabalhos, novos matemáticos que tiveram contato com sua obra continuaram
suas pesquisas e foram responsáveis por colocarem Cantor no seu devido lugar,
assim como REVOLUCIONAR o campo de pesquisa em matemática. A matemática
contemporânea não seria a mesma sem o trabalho genial de Cantor, que sofreu
consequências em sua vida por essa mentalidade à frente de seu tempo.

O filósofo e matemático Bertrand Russell, junto de Alfred Whitehead, utilizaram-se da

obra de Cantor para, a partir de 1918, com a publicação dos 3 volumes da obra
Principia Matematica, em homenagem ao trabalho de Newton que inaugura o Cálculo
das fluxões (Cálculo Diferencial e Integral), darem demonstrações extremamente
rigorosas e completas sobre resultados básicos de matemático, utilizando para isso a

Introdução à Lógica e Programação Página 69

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

linguagem lógica de primeira ordem e uma axiomática para a Teoria dos Conjuntos –
ou seja, demonstraram estes resultados como TEOREMAS dentro de um sistema
formal, conforme esboçamos anteriormente.

Para você ter uma ideia, é depois de quase 300 páginas do primeiro volume do
“Principia” que os autores conseguem demonstrar o seguinte teorema (da Teoria dos
Conjuntos): ⊢”1 + 1 = 2”. É importante notar que esta axiomatização utilizada por
Russell e Whitehead bebe da teoria de Cantor, mas foi desenvolvida precisamente
por outros matemáticos, Zermelo e Fraenkel, e por isso esta teoria dos conjuntos,
com essa axiomática, é chamada de ZF. Existem outras axiomáticas para a Teoria
dos conjuntos, mas a maioria dos matemáticos atualmente trabalha no que
chamamos de “Ambiente ZFC”, que é a teoria ZF acrescida do axioma da escolha.

Estamos neste capítulo mais interessados em analisar o axioma do infinito. Com

exceção deste e do axioma da escolha, conseguimos com os outros axiomas
demonstrar muitos resultados da Teoria dos Conjuntos. O primeiro deles é a
existência de um objeto particular, o conjunto vazio denotado por ∅. É a partir deste
conjunto que demonstramos a existência, e das operações de conjuntos, que
construímos TODOS os outros conjuntos que existem na matemática e, portanto,
todos os seus objetos.

Todavia, SEM o axioma do infinito, somos capazes de criar, apenas, outros conjuntos
finitos. Isto acontece porque usamos uma linguagem de primeira ordem finitária, cujas
fórmulas são sempre finitas. Existem linguagens infinitárias para a lógica de primeira
ordem (cuja lógica resultante NÃO é a Lógica Clássica, mas uma lógica de primeira
ordem infinitária) e com ela poderíamos construir conjuntos infinitos com fórmulas
infinitas. Porém, a matemática usual é feita nos limites da Lógica Clássica (embora há
Matemáticas não standards que podem ser investigadas por matemáticos que
desejam utilizar um ambiente lógico diferente do ambiente clássico).

Construção dos números naturais em ZFC

O axioma do infinito é essencial para que, a partir dele, possamos assegurar a

existência de um conjunto infinito. Criamos assim uma coleção de objetos chamados
de números ordinais.

Por ora, neste capítulo, vamos nos preocupar somente com os objetos FINITOS que
iremos construir, os ordinais finitos, chamados de números naturais.

Veja quais são os passos para a construção dos conjuntos que caracterizam os
números ordinais.

Passo 1. Prova-se a existência de um conjunto sem elementos, chamado de conjunto

vazio e que é denotado pelo símbolo ∅ (este símbolo NÃO é uma constante da

Introdução à Lógica e Programação Página 70

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

linguagem formal, estamos atuando em um nível acima do nível sintático para

simplificar as demonstrações.

Passo 2. Construímos, de forma explícita, a existência de uma função 𝑠 chamada de

função sucessor. Ela faz o papel da função sucessor na teoria axiomática de Peano,
mas aqui ela é definida explicitamente, sabemos qual a regra para calcular esta
função:

Suponhamos que 𝑥 é um conjunto (que são os objetos existentes no domínio da

Teoria dos Conjuntos).

𝑠(𝑥) = 𝑥 ∪ {𝑥}

Passo 3. A partir da função sucessor colocamos constantes na linguagem para

nomear os conjuntos resultantes da aplicação desta função, criando assim os
números ordinais, usando a noção de número proposta pelo matemático Von-
Neumann.

0 será a constante da linguagem para denotar o objeto ∅

1 denotará o objeto 𝑠(∅)

2 denotará o objeto 𝑠(𝑠(∅))

3 denotará o objeto 𝑠 (𝑠(𝑠(∅)))

etc

Veja que para a construção dos números ordinais finitos (naturais) usamos somente a
função sucessor (operação de união) e a composição de funções. Como esperado,
construímos estes objetos por meio de uma recursão.

O que esta constantes (os numerais) denotam? Conjuntos. E como temos as regras
de cálculo desses conjuntos, conseguimos agora exibi-los.

0 denota o conjunto ∅

1 denota o conjunto 𝑠(∅) = ∅ ∪ {∅} = {∅}

2 denota o conjuntos 𝑠(𝑠(∅)) = {∅} ∪ {{∅}} = {∅, {∅}}

3 denota o conjunto 𝑠 (𝑠(𝑠(∅))) = {∅, {∅}} ∪ {{∅, {∅}}} = {∅, {∅}, {∅, {∅}}}

4 denota o conjunto 𝑠 (𝑠 (𝑠(𝑠(∅)))) = {∅, {∅}, {∅, {∅}}} ∪ {{∅, {∅}, {∅, {∅}}}} =

= {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}}

Introdução à Lógica e Programação Página 71

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

etc

Se usarmos um abuso de notação na linguagem, já que constante NÃO é um

conjunto, podemos fazer o seguinte esquema 0 ⊂ 1 ⊂ 2 ⊂ 3 ⊂ 4 ⊂ ⋯

Ou seja, abusando um pouco mais da linguagem:

1 = 0 ∪ {0}

2 = 1 ∪ {1}

3 = 2 ∪ {2}

4 = 3 ∪ {3}

etc

Veja que com essa estratégia de construção, começamos com um conjunto vazio,
depois um conjunto com um elemento, outro com dois elementos e assim por diante,
acrescentando um elemento em cada estágio. Portanto, se sempre “acrescentarmos”
sempre um elemento no conjunto anterior, finito, sempre continuamos com um
conjunto finito.

DEFINIÇÃO: Define-se como conjunto indutivo aquele conjunto 𝐼 que satisfaz:

a) ∅ ∈ 𝐼

b) se 𝑥 ∈ 𝐼 então 𝑠(𝑥) ∈ 𝐼

Definimos ℕ o conjunto formado por todos os conjuntos 𝑥 que pertencem a TODOS

os conjuntos indutivos. Logo, o conjunto dos números naturais é o menor dos
conjuntos indutivos. Mas como podemos garantir que EXISTE um conjunto indutivo?

Não podemos! Por isso é necessário o axioma do infinito.

AXIOMA DO INFINITO: Existe um conjunto indutivo.

É através do axioma do infinito que entra na teoria dos conjuntos os conjuntos na

aritmética standard. Este é o primeiro ordinal infinito, que estudaremos em detalhes
no próximo capítulo.

Portanto 𝜔 = {0,1,2,3, … } e ℕ é o rótulo que damos a este conjunto, cujos elementos

também são conjuntos.

Introdução à Lógica e Programação Página 72

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

PRINCÍPIO DA INDUÇÃO (FINITA) – PIF:

A natureza dos números naturais (ordinais finitos) nos garante que dentro da teoria
axiomática dos conjuntos, se uma propriedade 𝑃 satisfizer essas características
(vamos simplificar a notação, esquecendo o enunciado completo que leva em
consideração a existência de constantes na fórmula indutiva):

a) 𝑃(0) é satisfeita;

b) Se para qualquer 𝑛 natural for o caso que se 𝑃(𝑛) for o caso, então 𝑃(𝑠(𝑛))
também será o caso.

Estas duas condições garantem que para qualquer 𝑛 natural vale a propriedade 𝑃,
isto é, ∀𝑛 ∈ ℕ 𝑃(𝑛).

DEMONSTRAÇÃO: Suponhamos que a fórmula 𝜑 = 𝑃(𝑥) com uma variável livre é

uma fórmula da teoria dos conjuntos.

Então existe um conjunto 𝑷 = {𝑥 | 𝑃(𝑥)} isto é, o conjunto formado por todos os

“conjuntos” que satisfazem a propriedade 𝑃.

Sabemos por a) que 𝑃(0) então ∅ ∈ 𝑷.

Mas vale, por b), que para qualquer número natural, é teorema da teoria a fórmula
𝑃(𝑛) → 𝑃(𝑠(𝑛)) para todo 𝑛 natural, ou seja, como 𝑛 + 1 denota o sucessor do ordinal
𝑛, isto significa que o conjunto 𝑷 é indutivo, logo ℕ ⊂ 𝑷.

EXERCÍCIOS

1. (ITA - adaptado) A soma dos cubos de três números inteiros consecutivos é

divisível por 9.

2. Prove as igualdades ou desigualdades.

𝑛(𝑛+1)
a) 1 + 2 + ⋯ + 𝑛 = ∀𝑛 ≥ 1
2

b) 1 + 3 + 5 + ⋯ + (2𝑛 − 1) = 𝑛2 ∀𝑛 ≥ 1

c) 𝑛! > 2𝑛 ∀𝑛 ≥ 4

3. A sequência de Fibonacci tem uma estrutura aritmética extremamente interessante

e que pode ser observada em vários lugares no mundo (pesquise). Ela é uma
sequência de recorrência, em que depois do segundo elemento, cada termo é igual à
soma dos dois anteriores:

𝐹1 = 1; 𝐹2 = 1; 𝐹𝑛+2 = 𝐹𝑛+1 + 𝐹𝑛 para todo 𝑛 ≥ 1

𝑛 𝑛
1+√5 1−√5
( ) −( )
2 2
Prove que outra fórmula para os termos dessa sequência é 𝐹𝑛 =
√5

Introdução à Lógica e Programação Página 73

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Aritmética dos números naturais

Dentro da axiomática de Peano para caracterizar a aritmética, utilizamos a função

definida pelos axiomas, a função sucessor, para determinar, por recursão, as
operações de soma e multiplicação de números naturais. Vamos fazer agora
construções similares, mas na teoria dos conjuntos, para determinar estas operações
sobre os números ordinais finitos (números naturais) a partir da função sucessor que
é definida explicitamente nesta teoria a partir dos axiomas.

DEFINIÇÃO: Existe uma função +: ℕ × ℕ → ℕ tal que:

a) ∀𝑛 ∈ ℕ + (𝑛, 0) = 𝑛

b) ∀𝑛∀𝑚 naturais, +(𝑛, 𝑚 + 1) = +(𝑛, 𝑚) + 1

Em que 𝑠(𝑎) = 𝑎 + 1 é uma notação simplificada usando o sinal de 𝑎 + 1 para denotar

a função +(𝑎, 1).

Veja que esta definição está bem formulada, pois a primeira entrada não tem
restrição, enquanto na segunda entrada, há uma definição da função por partes. Na
primeira parte ela define a função para 0 na segunda entrada, único número que não
é sucessor de outro, e na segunda parte da definição ela abrange todos os números
que são sucessores de alguém. Ela define adequadamente a operação de soma.

Propriedade associatividade: Para quaisquer números naturais 𝑛, 𝑚 e 𝑘:

(𝑛 + 𝑚) + 𝑘 = 𝑛 + (𝑚 + 𝑘)

Propriedade de comutatividade: A soma de números naturais é comutativa.

DEMONSTRAÇÃO: Temos de demonstrar que para quaisquer 𝑛 e 𝑚:

𝑚+𝑛 =𝑛+𝑚

Veja que podemos afirmar que o número 𝑛 comuta na soma se ele comuta com
qualquer valor de 𝑚. Portanto, se mostrarmos que para todo 𝑛 ∈ ℕ, 𝑛 comuta,
mostramos o resultado.

Então, mostremos primeiramente que o número 0 comuta.

I) ∀𝑚: 𝑚 + 0 = 0 + 𝑚

Por definição sabemos que +(𝑚, 0) = 𝑚 + 0 = 𝑚

Introdução à Lógica e Programação Página 74
 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Mostremos por indução sobre 𝑚 que +(0, 𝑚) = 0 + 𝑚 = 𝑚.

i) 0 + 0 = 0 por definição.

ii) Suponhamos que 0 + 𝑚 = 𝑚:

0 + (𝑚 + 1) =𝑎𝑠𝑠𝑜𝑠𝑐𝑖𝑎𝑡𝑖𝑣𝑎 (0 + 𝑚) + 1 =𝐻𝑖𝑝.𝐼 𝑚 + 1

Logo demonstramos que se 0 + 𝑚 = 𝑚 então 0 + (𝑚 + 1) = 𝑚 + 1, ou seja,

utilizando a indução sobre 𝑚 mostramos que para qualquer 𝑚:

0+𝑚 = 𝑚

II) Suponhamos que 𝑛 é um número tal que 𝑛 comuta; então mostremos que 𝑛 + 1
também comuta.

Se 𝑛 comuta, segue que para qualquer 𝑚: 𝑚 + 𝑛 = 𝑛 + 𝑚

Provemos que 𝑚 + (𝑛 + 1) = (𝑛 + 1) + 𝑚, isto é, 𝑛 + 1 comuta, utilizando

indução sobre 𝑚.

i) Para 𝑚 = 0 temos 0 + (𝑛 + 1) = (𝑛 + 1) + 0 válido, pela parte I.

ii) Suponhamos que 𝑚 + (𝑛 + 1) = (𝑛 + 1) + 𝑚 para algum 𝑚. Então:

(𝑚 + 1) + (𝑛 + 1) =𝑎𝑠𝑠𝑜𝑐. ((𝑚 + 1) + 𝑛) + 1 =𝑛 𝑐𝑜𝑚𝑢𝑡𝑎 (𝑛 + (𝑚 + 1)) + 1 =𝑎𝑠𝑠𝑜𝑐

((𝑛 + 𝑚) + 1) + 1 =𝑛 𝑐𝑜𝑚𝑢𝑡𝑎 ((𝑚 + 𝑛) + 1) + 1 =𝑎𝑠𝑠𝑜𝑐. (𝑚 + (𝑛 + 1)) + 1 =𝐻𝑖𝑝ó𝑡𝑒𝑠𝑒

((𝑛 + 1) + 𝑚) + 1 =𝑎𝑠𝑠𝑜𝑐. (𝑛 + 1) + (𝑚 + 1)

Portanto, usando a PIF sobre 𝑚:

∀𝑚: 𝑚 + (𝑛 + 1) = (𝑛 + 1) + 𝑚

Ou seja, provamos II.

Logo, utilizando I e II temos a demonstração por indução sobre 𝑛 que para quaisquer
valores de 𝑛 e 𝑚:

𝑛+𝑚 =𝑚+𝑛

EXERCÍCIOS

1. Prove a propriedade de associatividade da soma.

Introdução à Lógica e Programação Página 75

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

2. Mostre que a função definida por ⋅ : ℕ × ℕ → ℕ tal que:

a) ∀𝑛 ∈ ℕ ⋅ (𝑛, 0) = 0

b) ∀𝑛∀𝑚 naturais, ⋅ (𝑛, 𝑚 + 1) = ⋅ (𝑛, 𝑚) + 𝑚

Satisfaz a operação usual de produto de números naturais.

3. Mostre que o produto de números naturais, como definido no exercício anterior, é

associativa e comutativa.

4. Mostre que a função definida por 𝑒𝑥𝑝: ℕ × ℕ → ℕ tal que:

a) ∀𝑛 ∈ ℕ 𝑒𝑥𝑝(𝑛, 0) = 1

b) ∀𝑛∀𝑚 naturais, 𝑒𝑥𝑝(𝑛, 𝑚 + 1) = ⋅ (𝑒𝑥𝑝(𝑛, 𝑚), 𝑚)

Satisfaz a operação usual de exponenciação.

Cardinalidade

Existe uma ordem “natural” nos números naturais, que é denominada ORDEM
LINEAR. De fato, os naturais são os números ORDINAIS finitos, eles representam a
noção usual de ordem, com um primeiro elemento, o zero, depois seu sucessor, o
número 1, o sucessor do 1 e assim por diante, uma lista contínua e infinita.

DEFINIÇÃO: Definimos em ℕ × ℕ uma RELAÇÃO DE ORDEM, chamada de ordem

linear, que satisfaz:

a) Ela é reflexiva, isto é, para todo 𝑛: 𝑛 ≤ 𝑛

b) Ela é transitiva, isto é, para todos os valores de 𝑛, 𝑚 e 𝑘: se 𝑛 ≤ 𝑚 e 𝑚 ≤ 𝑘

ENTÃO 𝑛 ≤ 𝑘

c) Ela é antissimétrica, isto é, para todos os valores de 𝑛 e 𝑚: se 𝑛 ≤ 𝑚 e 𝑚 ≤ 𝑛

ENTÃO 𝑚 = 𝑛

d) Ela é total, isto é, para todos os valores de 𝑛 e 𝑚: 𝑛 ≤ 𝑚 ou 𝑚 ≤ 𝑛

Introdução à Lógica e Programação Página 76

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

DEFINIÇÃO: Dizemos que dois conjuntos A e B têm a mesma CARDINALIDADE ou

que eles são EQUIPOTENTES (têm o mesmo tamanho) se existir uma bijeção 𝑓 entre
eles, isto é, uma função 𝑓: 𝐴 → 𝐵 bijetora. Neste caso denotamos |𝐴| = |𝐵|.

Exemplo: Os conjuntos 𝐴 = {𝑎, 𝑏, 𝑐} e 𝐵 = {1,2,3} são equipotentes, pois ambos têm a

mesma cardinalidade, cada um deles tem exatamente 3 elementos.

E isso é em razão da existência de uma função 𝑓 bijetora que pode ser definida entre
estes dois conjuntos, por exemplo:

𝑓(𝑎) = 1

𝑓(𝑏) = 3

𝑓(𝑐) = 2

Verifique que esta função é de fato bijetora.

Como vimos, o conjunto dos números naturais é o primeiro conjunto infinito da Teoria
dos Conjuntos, ele é o menor dos conjuntos indutivos e está contido em todo conjunto
indutivo, portanto os conjuntos indutivos são todos infinitos.

De fato, na Teoria dos Conjuntos podemos demonstrar que o primeiro conjunto infinito
tem um tamanho diferente de outros conjuntos que também são infinitos, mas que ele
também tem um tamanho igual a outros conjuntos infinitos, ou seja, existem diferentes
infinitos.

A cardinalidade de um conjunto equipotente ao conjunto 𝜔 é chamada de infinito

enumerável, pois podemos enumerar seus elementos, fazer uma lista com todos
eles. Este número é chamado de CARDINALIDADE e as cardinalidades infinitas
formam, elas mesmas, uma sequência.

O primeiro infinito, de cardinalidade enumerável, é denominado ALEF ZERO:

|ℕ| = ℵ0

Há depois uma lista (infinita) de outras cardinalidades infinitas, todas NÃO

enumeráveis.

ℵ1 , ℵ2 , ℵ3 , …

Teorema: A quantidade de números naturais pares é igual à quantidade de números

naturais ímpares, que é igual à quantidade de números naturais.

Introdução à Lógica e Programação Página 77

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

DEMONSTRAÇÃO: Sejam 𝑃 = {0,2,4,6, … } e 𝐼 = {1,3,5,7, … } os conjuntos dos

números naturais pares e ímpares, respectivamente.

𝑓: ℕ → 𝑃 uma função definida por 𝑓(𝑛) = 2 ⋅ 𝑛.

Esta função é bijetora (verifique), portanto |𝑃| = |ℕ| e temos a mesma quantidade de
números naturais pares que a quantidade de números naturais.

𝑔: ℕ → 𝐼 uma função definida por 𝑓(𝑛) = 2 ⋅ 𝑛 + 1

Esta função é bijetora (verifique), portanto |𝐼| = |ℕ| e temos a mesma quantidade de
números naturais pares que a quantidade de números naturais.

De fato, uma das definições de infinito, dada pelo matemático Dedekind, é aquela que
afirma que “um conjunto é infinito se existe uma sobrejeção do conjunto em uma parte
própria dele mesmo”, ou seja, a função 𝑓, por exemplo, é uma sobrejeção que leva
TODO o conjunto dos números naturais em uma parte própria dele, a parte que
contém somente os naturais pares.

Vamos por ora supor que a operação de subtração está bem definida no conjunto dos
números inteiros.

Teorema: Os conjuntos ℕ, ℤ e ℚ, conjunto dos números naturais, inteiros e racionais,

respectivamente, são todos equipotentes.

DEMONSTRAÇÃO: Precisamos demonstrar que todos estes conjuntos, o dos

números naturais, dos números inteiros e dos números racionais, têm cardinalidade
infinita e enumerável, isto é, cardinalidade ℵ0 .

Para isso, precisamos estabelecer bijeções entre estes conjuntos e ℕ.

Seja 𝑓: ℕ → ℤ uma função definida por:

𝑛
; 𝑠𝑒 𝑛 𝑓𝑜𝑟 𝑝𝑎𝑟
2
𝑓(𝑛) = { 𝑛+1
−( ) ; 𝑠𝑒 𝑛 𝑓𝑜𝑟 í𝑚𝑝𝑎𝑟
2

Verifique que esta função é uma bijeção e, portanto, os conjuntos naturais e inteiros
têm a mesma cardinalidade. ∎

Existe um resultado, que você irá demonstrar nos exercícios, que afirma que se 𝐴1 e
𝐴2 forem conjuntos enumeráveis, então 𝐴1 × 𝐴2 é um conjunto enumerável.

Introdução à Lógica e Programação Página 78

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

𝑎
Como ℚ = {𝑏 | 𝑎, 𝑏 ∈ ℝ 𝑒 𝑏 ≠ 0}, então podemos dizer que ℚ=ℤ × ℤ∗ (estamos
fazendo um abuso de notação aqui).

Como demonstramos que ℤ é enumerável, então ℤ∗ também é enumerável e,

portanto, do resultado afirmado acima, também é enumerável. ∎

Note que interessante:

Na teoria ingênua dos conjuntos escrevemos ℕ ⊂ ℤ ⊂ ℚ para representar que estas

estruturas numéricas são “subconjuntos”. Mas mostramos que, na verdade, embora
pareça que estes conjuntos contenham TODOS os elementos do conjunto anterior e
muito mais, na verdade eles têm a MESMA cardinalidade.

Isso ocorre pois a cardinalidade dos conjuntos é infinita e, no infinito, as nossas

intuições falham para tentar nos mostrar o que é ou o que representa o infinito.

Como todos estes três conjuntos são enumeráveis, isso significa que podemos ter
uma “regra” para colocar todos seus elementos em uma fila, numa ordem linear. A
ordem de ℕ é óbvia (embora possamos escolher outras infinitas ordens), mas
podemos também criar uma lista com os números inteiros e também com os
racionais, o que parece ainda mais “estranho”. Pesquise sobre a forma de “contar” os
racionais usando o argumento diagonal.

Teorema: O conjunto dos números reais é NÃO enumerável.

DEMONSTRAÇÃO: Para demonstrar este teorema utilizaremos um argumento como

apresentado por Cantor, uma prova por contradição ou redução ao absurdo.

Sejam 𝑝 e 𝑞 proposições. É fórmula tautológica (portanto teorema da lógica clássica)

a fórmula (𝑝 → (𝑞 ∧ ¬𝑞)) → ¬𝑝 (faça uma tabela-verdade para confirmar).

Esta fórmula exemplifica o método de prova por redução ao absurdo. Se supormos

uma proposição 𝑝 verdadeira e, com ela, obtermos uma contradição “do tipo 𝑞 ∧ ¬𝑞”,
então podemos concluir que nossa suposição era falsa e, pelo princípio do terceiro
excluído, é o caso a negação de nossa suposição.

A prova da não enumerabilidade dos reais dado por Cantor é pelo processo de
diagonalização.

Suponhamos que ℝ seja um conjunto enumerável. Neste caso, para facilitar o

argumento, o intervalo (0,1) ⊂ ℝ é um subconjunto próprio. Logo, se 𝑥 ∈ ℝ, a
Introdução à Lógica e Programação Página 79
 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

representação decimal deste número é da forma 0, 𝑎1 𝑎2 𝑎3 𝑎4 … em que cada 𝑎𝑖 é um

algarismo de 0 a 9. Veja que se a representação decimal for FINITA, isso significa que
a partir de um ponto, todos os 𝑎𝑖 são iguais a zero.

Mas o fato de ℝ ser enumerável, por hipótese, implica que uma pequena parte dele
também é. Logo, seja a lista a seguir uma enumeração de TODOS os elementos de
(0,1).

𝑥1 = 0, 𝑎11 𝑎12 𝑎13 𝑎14 …

𝑥2 = 0, 𝑎12 𝑎22 𝑎32 𝑎42 …

𝑥3 = 0, 𝑎13 𝑎23 𝑎33 𝑎43 …

Vamos construir um número 𝑦 = 0, 𝑏1 𝑏2 𝑏3 𝑏4 𝑏5 … que pertence ao intervalo (0,1) da

seguinte forma:

𝑏1 será um algarismo diferente de 𝑎11 .

𝑏2 será um algarismo diferente de 𝑎22 .

𝑏3 será um algarismo diferente de 𝑎33 .

𝑏4 será um algarismo diferente de 𝑎44 .

etc

Veja que o fato de 𝑦 ∈ (0,1) implica 𝑦 = 𝑥𝑛 para algum 𝑛 enumeração da listagem dos
elementos do intervalo. Analisemos.

Introdução à Lógica e Programação Página 80

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Analisando a diagonal destes números, notamos que se o algarismo 𝑏𝑖 é diferente do

algarismo 𝑎𝑖𝑖 do número 𝑥𝑖 , isso significa que o número 𝑦 não pode ser 𝑥1 , assim
como ele não pode ser igual ao número 𝑥2 , ou ao 𝑥3 etc.

Logo, o número 𝑦 não é nenhum dos números listados. O que é uma contradição (ou
absurdo), pois nossa suposição implicava que esta lista era completa ou exaustiva.

Usando o tipo de prova por redução ao absurdo, isso implica que nossa suposição
inicial é falsa, ou seja, o conjunto dos números reais ℝ tem cardinalidade infinita e
NÃO enumerável. ∎

Hipótese do Contínuo

Ao primeiro cardinal infinito não enumerável damos o nome de ALEF UM (ℵ1 ). Como
comentamos anteriormente, Cantor demonstrou haver uma cadeia infinita de cardinais
infinitos, cada um deles representando o “tamanho” de um conjunto infinito que é
maior do que o anterior. Será então que podemos dizer que |ℝ| = ℵ1 ?

Não necessariamente!

Mostra-se na Teoria dos Conjuntos que |ℝ| = 2ℵ0 .

É chamada de Hipótese do Contínuo a proposição que afirma 2ℵ0 = ℵ1, ou seja, que a
cardinalidade do conjunto dos números reais é igual a ao primeiro cardinal não
enumerável.

Foi-se provado que a Teoria dos Conjuntos é consistente tanto com a hipótese do
contínuo, quanto com sua negação, ou seja, dentro da Teoria dos Conjuntos, o
tamanho do conjunto dos números reais é algo que NÃO PODE SER PROVADO, o
que é dito como independência da hipótese do contínuo na Teoria dos Conjuntos
(ZFC).

EXERCÍCIOS

1. Mostre que se 𝐴1 e 𝐴2 forem conjuntos enumeráveis (finitos ou infinitos), então:

a) 𝐴1 ∪ 𝐴2 é enumerável

b) 𝐴1 × 𝐴2 é enumerável

c) 𝐴1 − {𝑎} é enumerável, para 𝑎 ∈ 𝐴1

d) 𝐴1 ∪ {𝑏} é enumerável, para 𝑏 ∉ 𝐴1

2. Mostre que o conjunto dos números irracionais não é enumerável.

Introdução à Lógica e Programação Página 81

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 10 – Noções de Aritmética transfinita: O hotel de Hilbert e a sequência

de Goodstein

No capítulo anterior vimos que os números naturais, na Teoria dos Conjuntos, são
conjuntos FINITOS obtidos a partir da aplicação da função sucessor 𝑠(𝑛) = 𝑛 ∪ {𝑛}
partindo do conjunto vazio.

Discutimos também como, a partir da axiomática da teoria dos conjuntos, excluindo o

axioma do infinito, somos capazes de criar, somente, outros conjuntos finitos e, por
esta razão, é necessária a inclusão desse axioma, para garantirmos a existência,
dentro da teoria, de um conjunto que nossa intuição sugere existir: um conjunto
infinito. Este conjunto postulado (ele é acrescentado na teoria por um axioma, sua
existência não pode ser PROVADA dentro da teoria - sem o axioma do infinito) tem o
tamanho de um conjunto infinito e enumerável, ele possui uma coleção de objetos que
podem ser colocados em uma fila infinita, com um primeiro elemento e uma sucessão
contínua de um após o outro. A este conjunto damos o nome de conjunto ômega 𝜔,
cuja CARDINALIDADE é nomeada por ℵ0 .

A revolução que Cantor trouxe para a Matemática ocidental foi de introduzir a ideia de
que existem outros conjuntos infinitos de cardinalidade diferente daquela infinita e
enumerável, ou seja, de conjuntos que são infinitos, mas NÃO enumeráveis ou
contáveis. Esta ideia não deveria ser chocante, pelo exemplo que apresentamos no
capítulo anterior com o argumento da diagonalização, mas vimos como ela foi
fortemente combatida no século XIX pela maioria dos matemáticos profissionais
contemporâneos a Cantor.

Mas se 𝜔 é um conjunto cuja existência é postulada na teoria, então além do número

0, o conjunto ∅, o próprio 𝜔 é um conjunto que NÃO é sucessor de nenhum outro. A
estes números ordinais que não são sucessores damos o nome de ORDINAL LIMITE.

O primeiro ordinal limite é o conjunto ∅, representado pelo número 0. O próximo

ordinal limite é o conjunto 𝜔, cuja existência é postulada pelo axioma do infinito.

Note que a forma como a função sucessor é construída pelo operador de união ∪ nos
mostra que podemos escrever este conjunto infinito FORA da teoria, usando esta
notação:

𝜔 = ⋃(𝑛 < 𝜔) 𝑛

Esta notação é exterior à teoria, pois denota uma união infinita, que não pode ser
escrita internamente à teoria. Utilizamos esta notação para representar uma noção de
LIMITE.

Portanto, o conjunto 𝜔 é o SUPREMO, o limite da união de TODOS os ordinais finitos.

Introdução à Lógica e Programação Página 82

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Ordinais infinitos

DEFINIÇÃO: Há duas categorias de ordinais:

1. Ordinais sucessores. São ordinais que são sucessores de um outro ordinal.

2. Ordinais limites. São ordinais que NÃO são sucessores de nenhum outro ordinal.

Exemplos:

a) Se 𝑛 é um número natural (ordinal finito), então 𝑛 + 3 é um ordinal sucessor, ele é

sucessor do ordinal 𝑛 + 2.

b) 𝜔 é um ordinal infinito (o primeiro ordinal infinito), então 𝑠(𝜔) = 𝜔 ∪ {𝜔} é um

ordinal sucessor, pois ele é sucessor de 𝜔. Veja que denotamos 𝑠(𝜔) = 𝜔 + [Link]
que um ordinal sucessor é sempre um ordinal “maior” do que o anterior, pois ele
contém o conjunto anterior unido com o unitário do conjunto anterior.

c) 0 é um ordinal limite.

d) 𝜔 é um ordinal limite, que pode ser escrito como o supremo de todos os ordinais
finitos, o limite da união de todos os números naturais.

Será que existem OUTROS ordinais limites? Pois já vimos que com a função
sucessor em ZF podemos construir outro ordinal infinito: 𝜔 + 1.

O Hotel de Hilbert

O paradoxo do Hotel de Hilbert é um experimento intelectual, proposto por David

Hilbert, criado para explorar as ideias contra-intuitivas que surgem ao pensarmos
sobre o infinito.

Imagine que um Hotel tem infinitos quartos, o quarto número 1, o quarto número 2, o
quarto número 3 e eternamente. Este hotel, durante certo dia, está totalmente lotado.
Nesta noite, chega uma pessoa procurando por uma vaga. É possível este hotel
receber um novo hóspede?

Primeiramente, você pode pensar que a resposta é NÃO, pois todos os quartos do
hotel estão lotados. Porém, a resposta para este paradoxo é SIM, e esta resposta
contra-intuitiva se deve ao fato de que este hotel, afinal, tem INFINITOS quartos.

Introdução à Lógica e Programação Página 83

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Portanto, basta arranjarmos de forma adequada os hóspedes para hospedar este

viajante. Veja como:

1. Mude o hóspede do quarto 1 para o quarto 2.

2. Mude o hóspede do quarto 2 para o quarto 3.

3. Mude o hóspede do quarto 3 para o quarto 4.

e assim sucessivamente, pois todos os hóspedes podem ser deslocados para o

quarto “vizinho” (sucessor).

Com essa ação, todos os outros hóspedes serão hospedados (pois com exceção do
quarto 1, todos os outros quartos possuem um sucessor), e o quarto 1 (o primeiro)
ficará vazio, pronto para hospedar o novo hóspede.

Este arranjo evidencia que se juntarmos um elemento a um conjunto infinito

enumerável, este novo conjunto continua sendo enumerável, como você demonstrou
no capítulo anterior.

Veja que este arranjo dos hóspedes no hotel pode ser descrito matematicamente
desta forma: 1 + 𝜔. Este rearranjo nos mostra que na aritmética dos ordinais infinitos,
temos 1 + 𝜔 = 𝜔.

Porém, o número 𝜔 + 1 é o SUCESSOR de 𝜔 (lembrando que 𝜔 + 1 é a notação para

o conjunto 𝜔 ∪ {𝜔}, obviamente diferente do conjunto 𝜔). Logo, 𝜔 + 1 ≠ 𝜔. Ou seja,
nos ordinais infinitos, não temos mais a propriedade de comutatividade da soma, já
que 𝜔 + 1 ≠ 1 + 𝜔.

EXERCÍCIOS

1. Mostre que se o Hotel de Hilbert estiver lotado e chegarem infinitos carros, cada um
deles com uma pessoa procurando por uma vaga neste famoso hotel, ainda assim
TODOS eles podem ser hospedados.

2. Suponha que o Hotel de Hilbert está lotado. Chegam neste hotel infinitos ônibus
com 30 lugares cada, todos ocupados com pessoas procurando vagas no hotel. Será
possível hospedá-las? Justifique.

Introdução à Lógica e Programação Página 84

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Aritmética Transfinita

Soma de números ordinais

Definimos a soma de ordinais, para todo ordinal 𝛽, da seguinte forma:

a. 𝛽 + 0 = 𝛽

b. 𝛽 + (𝛼 + 1) = (𝛽 + 𝛼) + 1 para todo ordinal 𝛼 (veja que 𝛼 + 1 é ordinal sucessor)

c. 𝛽 + 𝛼 = sup{𝛽 + 𝛾 | 𝛾 < 𝛼} para todo ordinal limite 𝛼 ≠ 0

Esta definição nos mostra como “somar” todos os ordinais. Chamamos de aritmética
ordinal transfinita a aritmética que envolve tanto os ordinais finitos (números naturais)
quanto os ordinais infinitos. Veremos que com esta definição, podemos obter números
ordinais infinitos sem fim, partindo de ordinais limites e chegando em outros ordinais
sucessores e outros ordinais limites a partir da operação união.

Se 𝛽 for um número natural, os casos a. e b. (para 𝛼 natural) são aquelas já definidas,

veja:

1001 + 0 = 1001

53 + (1001) = (53 + 1000) + 1 = 1054

Se 𝛼 = 𝜔 veja o que acontece com a cláusula c.

250 + 𝜔 = sup{250 + 𝛾 | 𝛾 < 𝜔}

Se 𝛾 < 𝜔 então 𝛾 é um número natural, portanto 250 + 𝛾 também será um número

natural, para qualquer 𝛾 número natural.

Logo, o sup{250 + 𝛾 | 𝛾 < 𝜔} representa o SUPREMO, LIMITE de TODOS os

números naturais. Mas sabemos que este supremo ou limite nada mais é do que:

⋃(𝑛<𝜔) 𝑛 = 𝜔

Ou seja, a cláusula c. nos diz que 250 + 𝜔 = sup{250 + 𝛾 | 𝛾 < 𝜔} = 𝜔.

Note que 250 + (𝜔 + 1) = (250 + 𝜔) + 1 = 𝜔 + 1, que é ordinal sucessor de 𝜔; ou

seja, quando somamos 250 à esquerda de 𝜔 + 1, continuamos tendo como resultado
o próprio número 𝜔 + 1. Isso se deve porque 250 é um ordinal finito, e 𝜔 + 1 é um
ordinal infinito sucessor do ordinal limite 𝜔, que está em outro “nível” de “infinitude”.

Quanto será a soma 𝜔 + 𝜔?

Introdução à Lógica e Programação Página 85

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Como 𝜔 é ordinal limite, usando a cláusula c. temos 𝜔 + 𝜔 = sup{𝜔 + 𝛾 | 𝛾 < 𝜔} =

= ⋃(𝜔 + 𝑛) = (𝜔 + 1) ∪ (𝜔 + 2) ∪ … ∪ (𝑤 + 1000) ∪ … = 𝜔 ⋅ 2
(𝑛<𝜔)

Acrescentamos aqui a notação da operação produto de ordinais para representar a

soma 𝜔 + 𝜔, que é a “soma” de dois ordinais infinitos que não são sucessores de
ninguém. Neste caso, 𝜔 ⋅ 2 também é um ordinal infinito e limite, de fato, é o primeiro
ordinal limite após 𝜔.

Com isso vemos que na aritmética transfinita temos uma sucessão infinita de níveis
infinitos de ordinais:

0, 1, 2, 3, 4, 5, … , 1000, … , 10523 , … , 5876 × 97089 , …

𝜔, 𝜔 + 1, 𝜔 + 2, 𝜔 + 3, … , 𝜔 + 1000, 𝜔 + 10523 , … , 𝜔 + 5876 × 97089 , …

𝜔 ⋅ 2, 𝜔 ⋅ 2 + 1, 𝜔 ⋅ 2 + 2, … , 𝜔 ⋅ 2 + 1000, 𝜔 ⋅ 2 + 10523 , … , 𝜔 ⋅ 2 + 5876 × 97089 , …

𝜔 ⋅ 3, 𝜔 ⋅ 3 + 1, 𝜔 ⋅ 3 + 2, … , 𝜔 ⋅ 3 + 1000, 𝜔 ⋅ 3 + 10523 , … , 𝜔 ⋅ 3 + 5876 × 97089 , …

Produto de números ordinais

Definimos o produto de ordinais, para todo ordinal 𝛽, da seguinte forma:

a. 𝛽 ⋅ 0 = 0

b. 𝛽 ⋅ (𝛼 + 1) = (𝛽 ⋅ 𝛼) + 𝛽 para todo ordinal 𝛼 (veja que 𝛼 + 1 é ordinal sucessor)

c. 𝛽 ⋅ 𝛼 = sup{𝛽 ⋅ 𝛾 | 𝛾 < 𝛼} para todo ordinal limite 𝛼 ≠ 0

Esta definição nos mostra como “multiplicar” todos os ordinais.

Se 𝛽 for um número natural, os casos a. e b (para 𝛼 natural) são aquelas já definidas,

veja:

1001 ⋅ 0 = 0

53 ⋅ (1001) = (53 ⋅ 1000) + 53 = 53053

Se 𝛼 = 𝜔 veja o que acontece com a cláusula c.

250 ⋅ 𝜔 = sup{250 ⋅ 𝛾 | 𝛾 < 𝜔}

Introdução à Lógica e Programação Página 86

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Se 𝛾 < 𝜔 então 𝛾 é um número natural, portanto 250 ⋅ 𝛾 também será um número

natural, para qualquer 𝛾 número natural.

Logo, o sup{250 ⋅ 𝛾 | 𝛾 < 𝜔} representa o SUPREMO, LIMITE de TODOS os números

naturais. Mas sabemos que este supremo ou limite nada mais é do que:

⋃(𝑛<𝜔) 𝑛 = 𝜔

Ou seja, a cláusula c. nos diz que 250 ⋅ 𝜔 = sup{250 + 𝛾 | 𝛾 < 𝜔} = 𝜔.

Por outro lado, 𝜔 ⋅ 250 = (𝜔 ⋅ 249) + 𝜔, que é um ordinal limite. Portanto 250 ⋅ 𝜔 ≠
𝜔 ⋅ 250, e o produto de ordinais (infinitos) também não é comutativo.

EXERCÍCIOS

1. Prove que vale a seguinte lei de associatividade para a soma e o produto de

números ordinais, para quaisquer ordinais 𝛼, 𝛽 e 𝛾.

a. 𝛼 + (𝛽 + 𝛾) = (𝛼 + 𝛽) + 𝛾

b. 𝛼 ⋅ (𝛽 ⋅ 𝛾) = (𝛼 ⋅ 𝛽) ⋅ 𝛾

2. Responda:

a. Mostre que vale a lei de distributividade do produto em relação à soma, pela

esquerda: 𝛼 ⋅ (𝛽 + 𝛾) = 𝛼 ⋅ 𝛽 + 𝛼 ⋅ 𝛾

b. Justifique porque a distributiva do produto em relação à soma, pela direita, não é

válida, isto é, não é necessariamente o caso que (𝛽 + 𝛾) ⋅ 𝛼 = 𝛽 ⋅ 𝛼 + 𝛾 ⋅ 𝛼.

3. Realize as operações, simplificando quando possível.

a. 27 + 𝜔

b. 𝜔 + 27

c. 𝜔 + (𝜔 + 4)

d. 43 ⋅ 𝜔 + 3 ⋅ (𝜔 + 3 ⋅ 𝜔)

e. 𝜔 ⋅ 43 + 3 ⋅ (3 ⋅ 𝜔 + 𝜔)

f. 𝜔 + 𝜔 ⋅ (15 + 100 ⋅ 𝜔)

Introdução à Lógica e Programação Página 87

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Sequências de Goodstein

Potência de números ordinais

Definimos o expoente de ordinais, para todo ordinal 𝛽, da seguinte forma:

a. 𝛽 0 = 1

b. 𝛽 𝛼+1 = 𝛽 𝛼 ⋅ 𝛽 para todo ordinal 𝛼 (veja que 𝛼 + 1 é ordinal sucessor)

c. 𝛽 𝛼 = sup{𝛽 𝛾 | 𝛾 < 𝛼} para todo ordinal limite 𝛼 ≠ 0

Façamos alguns exemplos:

4𝜔 = sup{4𝑛 | 𝑛 < 𝜔} = 𝜔

12𝜔+1 = 12𝜔 ⋅ 12 = 𝜔 ⋅ 12

EXERCÍCIO

Simplifique:

a. (𝜔 + 1) + 𝜔

b. 𝜔 + 𝜔2

c. 𝜔2 ⋅ (𝜔 + 1)

O combate de Hércules contra a Hidra

Na mitologia grega, o combate de Hércules contra uma Hidra é narrado quando o

herói precisou enfrentar o monstro, cujo corpo era de dragão com várias cabeças de
serpentes atadas a ele. O problema era que este monstro era um mortal inimigo: ele
matava os homens apenas com seu hálito e, para piorar as coisas, a cada cabeça do
monstro cortada, duas regeneravam naquele local.

Uma descrição moderna do conto dá instruções de como se comportava o animal ao

longo do embate com Hércules, transformando a luta em um jogo de lógica e
raciocínio. Pesquise qual foi a estratégia adotada por Hércules para derrotar o
monstro, de acordo com a narração mitológica tradicional.

Na abordagem contemporânea, as regras do embate são as seguintes:

1. A cada golpe Hércules corta somente uma cabeça;

Introdução à Lógica e Programação Página 88

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

2. Se a cabeça cortada estiver diretamente ligada ao corpo da Hidra, o monstro não

consegue repô-la;

3. Se a cabeça cortada estiver ligada a uma ramificação, e se 𝑛 for o número de

golpes já deferidos por Hércules até aquele momento, o número de cabeças ao lado
da cabeça decepada replica-se 𝑛 vezes.

Um teorema, demonstrado por Kirby e Paris enuncia que “Quaisquer que sejam a
forma inicial da Hidra, desde que ela tenha pelo menos uma cabeça ligada
diretamente ao corpo, e a estratégia utilizada por Hércules, ele sempre terminará por
matar o animal”.

Este teorema NÃO pode ser demonstrado na aritmética usual de Peano, ou seja,
usando os mecanismos de recursão que vimos anteriormente. Ele precisa ser
demonstrado dentro da aritmética dos ordinais, na teoria dos conjuntos, usando os
ordinais transfinitos.

Não vemos demonstrar este teorema aqui, mas mostraremos outro resultado
semelhante a este, que dá a ideia de como esta afirmação, um pouco exótica – de
que Hércules consegue matar a Hidra –, pode ser demonstrada usando as
ferramentas conjuntistas e a ideia de recursão transfinita, isso é, uma recursão que
vai para além dos princípios da recursão finita existente no conjunto dos números
naturais, mas que que extrapola para todos os ordinais, incluindo os ordinais limites.

Decomposição em bases: Sabemos que todo número natural 𝑏 ≥ 2 pode ser usado
como BASE para a decomposição de um número natural 𝑚. Já fizemos isso tanto
usando a base 10 como a base 2. Recordemos:

234 = 2 ⋅ 102 + 3 ⋅ 101 + 4 ⋅ 100 (𝑏 = 10)

234 = 1 ⋅ 27 + 1 ⋅ 26 + 1 ⋅ 25 + 1 ⋅ 23 + 1 ⋅ 21 (𝑏 = 2)

Podemos generalizar este resultado, colocando:

𝑚 = 𝑘1 ⋅ 𝑏 𝑎1 + 𝑘2 ⋅ 𝑏 𝑎2 + ⋯ + 𝑘𝑛 ⋅ 𝑏 𝑎𝑛

em que 𝑎1 > 𝑎2 > ⋯ > 𝑎𝑛 e 0 < 𝑘𝑖 < 𝑏 para 1 ≤ 𝑖 ≤ 𝑛.

DEFINIÇÃO: Uma sequência de Goodstein fraca começando no número ordinal 𝑚 >

0 é uma sequência do tipo (𝑚0 , 𝑚1 , 𝑚2 , … ) obtida da seguinte forma:

Introdução à Lógica e Programação Página 89

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

PASSO 0: Faça 𝑚0 = 𝑚

Escreva 𝑚0 = 2𝑎1 + 2𝑎2 + ⋯ +2𝑎𝑛 o número 𝑚0 na base 2.

PASSO 1: Aumente a base do número anterior da sequência decomposto de 2 para

3 e subtraia 1 do total, isto é:

Faça 𝑚1 = 3𝑎1 + 3𝑎2 + ⋯ 3𝑎𝑛 − 1

PASSO 2: Aumente a base do número anterior da sequência decomposto em uma

unidade (de 3 para 4) e subtraia 1 do total, obtendo 𝑚2 .

E assim sucessivamente.

EXEMPLO. Calculemos a sequência de Goodstein fraca para o número 21.

𝑚0 = 21 = 24 + 22 + 20

𝑚1 = 34 + 32 + 30 − 1 = 90 = 34 + 32

𝑚2 = 44 + 42 − 1 = 271 = 44 + 3 ⋅ 4 + 3 ⋅ 40

𝑚3 = 54 + 3 ⋅ 5 + 3 ⋅ 50 − 1 = 642

𝑚4 = 64 + 3 ⋅ 6 + 2 ⋅ 60 − 1 = 1315

etc...

Pode parecer contra-intuitivo, como praticamente tudo o que envolve o infinito, mas:

TEOREMA: Para cada 𝑚 > 0, a sequência de Goodstein fraca começando em 𝑚 irá

eventualmente, em algum passo 𝑛, terminar em zero, ou seja, 𝑚𝑛 = 0.

A sequência de Goodstein fraca vai “crescendo”, pois estamos sempre reescrevendo

o número anterior com uma potência de base maior. Porém, conseguimos mostrar
que no final, pode demorar um pouco, mas esta sequência de repente começará a
decrescer e finalmente “zerar”. É a mesma lógica para a demonstração do teorema
sobre a derrota da Hidra por Hércules!

Não vamos demonstrar este resultado aqui, mas antes vamos enunciar a mesma
versão deste teorema para a sequência de Goodstein, verificando alguns exemplos.

Introdução à Lógica e Programação Página 90

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

DEFINIÇÃO: [Forma normal] Todo ordinal 𝛼 > 0 pode ser expresso unicamente como:

𝛼 = 𝑘1 ⋅ 𝜔 𝑏1 + 𝑘2 ⋅ 𝜔 𝑏2 + ⋯ + 𝑘𝑛 ⋅ 𝜔 𝑏𝑛

em que 𝑏1 > 𝑏2 > ⋯ > 𝑏𝑛 e 𝑘1 > 0, .., 𝑘𝑛 > 0 são todos finitos.

A forma normal é uma maneira de generalizar para todo ordinal a ideia de

decomposição de todo número natural usando diferentes bases.

DEFINIÇÃO: Um número (ordinal) 𝑚 é dito estar escrito em pura base 𝑎 ≥ 2 se ele

estiver escrito na base 𝑎, assim como os expoentes e os expoentes dos expoentes,
etc.

324 na base 3 é escrito como 35 + 34 .

Mas 5 = 31 + 2 ⋅ 30 e 4 = 31 + 1 ⋅ 30 , portanto 324 em pura base 3 é 33+2 + 33+1.

DEFINIÇÃO: Uma sequência de Goodstein começando no número ordinal 𝑚 > 0 é

uma sequência do tipo (𝑚0 , 𝑚1 , 𝑚2 , … ) obtida da seguinte forma:

PASSO 0: Faça 𝑚0 = 𝑚

Escreva 𝑚0 na pura base 2.

PASSO 1: Troque todos os valores 2 de 𝑚0 por 3 e subtraia 1 do total, obtendo 𝑚1 ,

escrevendo o número resultante na pura base 3.

PASSO 2: Troque todos os valores 3 de 𝑚1 por 4 e subtraia 1 do total, obtendo 𝑚2 ,

escrevendo o número resultante na pura base 4.

E assim sucessivamente.

EXEMPLO. Calculemos a sequência de Goodstein para o número 21.

2
𝑚0 = 21 = 24 + 22 + 20 = 22 + 22 + 1
3
𝑚1 = 33 + 33 + 1 − 1 ≈ 7,6 × 1012
4 4
𝑚2 = 44 + 44 − 1 = 44 + 3 ⋅ 43 + 3 ⋅ 42 + 3 ⋅ 4 + 3 ≈ 1,3 × 10154

Introdução à Lógica e Programação Página 91

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

5
𝑚3 = 55 + 3 ⋅ 53 + 3 ⋅ 52 + 3 ⋅ 5 + 2 ≈ 1,9 × 102184
6
𝑚4 = 66 + 3 ⋅ 63 + 3 ⋅ 62 + 3 ⋅ 6 + 1 ≈ 2,6 × 1036305
7
𝑚5 = 77 + 3 ⋅ 73 + 3 ⋅ 72 + 3 ⋅ 7
8 8
𝑚6 = 88 + 3 ⋅ 83 + 3 ⋅ 82 + 3 ⋅ 8 − 1 = 88 + 3 ⋅ 83 + 3 ⋅ 82 + 2 ⋅ 8 + 7
9
𝑚7 = 99 + 3 ⋅ 93 + 3 ⋅ 82 + 2 ⋅ 9 + 6

etc...

Pode parecer contra-intuitivo, pois esta sequência cresce mais rapidamente do que a
sequência de Goodstein fraca, contudo:

TEOREMA: Para cada 𝑚 > 0, a sequência de Goodstein começando em 𝑚 irá

eventualmente, em algum passo 𝑛, terminar em zero, ou seja, 𝑚𝑛 = 0.

DEMONSTRAÇÃO: Para cada 𝑖-ésimo termo em pura base 𝑖, temos:

𝑚𝑖 = (𝑖 + 2)𝑎1 ⋅ 𝑘1 + ⋯ + (𝑖 + 2)𝑎𝑛 ⋅ 𝑘𝑛

Criamos para cada um destes termos um outro termo, denotado por 𝛼𝑖 , substituindo
cada valor 𝑖 + 2 por 𝜔. Então, necessariamente, como 𝑖 + 2 é um natural, temos que
para todo 𝑖:

𝑚𝑖 ≤ 𝛼𝑖

Veja o que está acontecendo com o exemplo feito anteriormente para 𝑚 = 21:
𝜔
𝛼0 = 𝜔 𝜔 + 𝜔 𝜔 + 1
𝜔
𝛼1 = 𝜔𝜔 + 𝜔𝜔
𝜔
𝛼2 = 𝜔𝜔 + 3 ⋅ 𝜔3 + 3 ⋅ 𝜔2 + 3 ⋅ 𝜔 + 3
𝜔
𝛼3 = 𝜔𝜔 + 3 ⋅ 𝜔3 + 3 ⋅ 𝜔2 + 3 ⋅ 𝜔 + 2
𝜔
𝛼4 = 𝜔𝜔 + 3 ⋅ 𝜔3 + 3 ⋅ 𝜔2 + 3 ⋅ 𝜔 + 1
𝜔
𝛼5 = 𝜔𝜔 + 3 ⋅ 𝜔3 + 3 ⋅ 𝜔2 + 3 ⋅ 𝜔
𝜔
𝛼6 = 𝜔𝜔 + 3 ⋅ 𝜔3 + 3 ⋅ 𝜔2 + 2 ⋅ 𝜔 + 7
𝜔
𝛼7 = 𝜔𝜔 + 3 ⋅ 𝜔3 + 3 ⋅ 𝜔2 + 2 ⋅ 𝜔 + 6

Introdução à Lógica e Programação Página 92

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Portanto, você verifica facilmente que ao trocarmos todas as bases pelo ordinal limite
𝜔, usando as operações da aritmética ordinal transfinita, a sequência obtida é
claramente decrescente, ou seja, 𝛼0 > 𝛼1 > 𝛼2 > ⋯.

Mas existe um PRIMEIRO ordinal, o número zero. Logo, em algum momento temos
que esta sequência (𝛼0 , 𝛼1 , 𝛼2 , … ) irá se anular e, portanto, existe um 𝑛 para o qual
𝛼𝑛 = 0.

Como 𝑚𝑖 ≤ 𝛼𝑖 para todo 𝑖, segue que 𝑚𝑛 = 0. ∎

Exemplos:

1. Façamos a sequência de Goodstein para 𝑚 = 3.

𝑚0 = 3 = 2 + 1 = 21 + 20

𝑚1 = 31 + 30 − 1 = 3 = 31

𝑚2 = 41 − 1 = 3 = 3 ⋅ 40

𝑚3 = 3 ⋅ 50 − 1 = 2 = 2 ⋅ 50

𝑚4 = 2 ⋅ 60 − 1 = 1 = 60

𝑚5 = 70 − 1 = 0

2. Quando assumimos 𝑚 = 4, a sequência de Goodstein “zera” após 3 ⋅ 2402653211 − 1

passos. Não vamos fazer eles aqui, tá?! Confira as 20 primeiras iterações:

𝑚0 = 22

𝑚1 = 33 − 1 = 26 = 2 ⋅ 32 + 2 ⋅ 3 + 2

𝑚2 = 2 ⋅ 42 + 2 ⋅ 4 + 2 − 1 = 41 = 2 ⋅ 42 + 2 ⋅ 4 + 1

𝑚3 = 2 ⋅ 52 + 2 ⋅ 5 + 1 − 1 = 60 = 2 ⋅ 52 + 2 ⋅ 5

𝑚4 = 2 ⋅ 62 + 2 ⋅ 6 − 1 = 83 = 2 ⋅ 62 + 1 ⋅ 6 + 5 ⋅ 60

𝑚5 = 2 ⋅ 72 + 1 ⋅ 7 + 5 − 1 = 109 = 2 ⋅ 72 + 1 ⋅ 7 + 4 ⋅ 70

𝑚6 = 2 ⋅ 82 + 1 ⋅ 8 + 4 − 1 = 139 = 2 ⋅ 82 + 1 ⋅ 8 + 3

𝑚7 = 2 ⋅ 92 + 9 − 1 = 170 = 2 ⋅ 92 + 8

𝑚8 = 2 ⋅ 102 + 7 = 207 = 2 ⋅ 102 + 7

𝑚9 = 2 ⋅ 112 + 6 = 248 = 2 ⋅ 112 + 6

𝑚10 = 2 ⋅ 122 + 5 = 293

Introdução à Lógica e Programação Página 93

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

𝑚11 = 2 ⋅ 132 + 4 = 342

𝑚12 = 2 ⋅ 142 + 3 = 395

𝑚13 = 2 ⋅ 152 + 2 = 452

𝑚14 = 2 ⋅ 162 + 1 = 513

𝑚15 = 2 ⋅ 172 = 578

𝑚16 = 2 ⋅ 182 − 1 = 647 = 182 + 17 ⋅ 18 + 17

𝑚17 = 192 + 17 ⋅ 19 + 16 = 700

𝑚18 = 202 + 17 ⋅ 20 + 15 = 755

𝑚19 = 212 + 17 ⋅ 21 + 14 = 812

EXERCÍCIOS

1. Calcule a sequência de Goodstein fraca para os números:

a. 𝑚 = 3

b. 𝑚 = 4

2. Calcule a sequência de Goodstein para 𝑚 = 2.

Depois, faça a substituição das bases da forma normal destes ordinais por 𝜔, como
foi feito na demonstração do teorema, para obter a sequência suporte dos números 𝛼,
realizando as operações com os ordinais infinitos para verificar que esta sequência,
de fato, converge para zero.

OBSERVAÇÃO: Não iremos explorar a aritmética cardinal neste material. Porém, é

importante ressaltar um fato curioso:

|2| = 2, em que o “2” do lado esquerdo representa o número ordinal {∅, {∅}} e o “2” do
lado direito o número cardinal.

|𝜔| = |𝜔 + 1| = |𝜔 ⋅ 2| = |𝜔2 | = ℵ0

Todos estes ordinais infinitos, embora em “diferentes níveis”, têm a mesma

cardinalidade, são todos enumeráveis. Todavia, podemos demonstrar em ZFC a
existência de um ordinal NÃO enumerável, que é obtido ao fazermos a união de
TODOS os ordinais enumeráveis. Este ordinal é denotado por 𝜔1 (limite), de
cardinalidade ℵ1 e possui um ordinal sucessor 𝜔1 + 1. Obviamente podemos montar
uma nova cadeia de outros ordinais cada vez maiores, cujos cardinais crescem muito
rapidamente.

Introdução à Lógica e Programação Página 94

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Capítulo 11 – Teoremas de Incompletude de Gödel e os limites para teorias

formais

Que tal voltarmos ao enigma do sistema-MIU?

Vamos resolver o enigma utilizando um subterfúgio que será muito importante para o
tema principal deste capítulo, os teoremas da incompletude de Gödel, que é o sistema
de numeração da linguagem da lógica.

Número de Gödel do sistema-MIU

Primeiramente, vamos mapear cada letra do sistema da seguinte forma:

𝑀 ⇔3

𝐼 ⇔1

𝑈 ⇔0

Assim, transformamos cada fórmula do sistema em um número, por exemplo, a

fórmula MU é identificada com o número 30, enquanto MIIU é identificada com o
número 3110.

Nessa transformação numérica das fórmulas do sistema-MIU, as regras para

obtenção dos teoremas a partir do axioma do sistema podem ser transformadas em
regras numéricas. Esta estratégia é uma “criação” especial de Gödel, usada para
demonstrar seus dois teoremas de incompletude, que iremos detalhar no final do
capítulo. Com esta estratégia, mudamos o enfoque da prova do caráter sintático da
lógica para seu caráter numérico.

Se transformarmos as quatro regras do sistema-MIU em regras numéricas

equivalentes, temos:

AXIOMA: O número 31 é correto no sistema, pois é a decodificação da palavra

legítima (axioma) MI.

Sejam 𝑚 e 𝑘 números naturais arbitrários e 𝑛 um número menor do que 10𝑚 .

Regra 1: Tendo o número correto 10𝑚 + 1, podemos inferir o número correto

10 × (10𝑚 + 1).

Exemplo: De 31001 podemos utilizar a regra, se 31001 for correto, para obter o
número 310010.

Introdução à Lógica e Programação Página 95

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Regra 2: Tendo o número correto 3 × 10𝑚 + 𝑛, podemos inferir o número correto

10𝑚 × (3 × 10𝑚 + 𝑛) + 𝑛.

Exemplo: De 3101 podemos utilizar a regra, se 3101for correto, para obter o número
3101101. Considere apenas 𝑚 = 3 e 𝑛 = 101 para verificar este exemplo.

Regra 3: Tendo o número correto 𝑘 × 10𝑚+3 + 111 × 10𝑚 + 𝑛, podemos inferir o

número correto 𝑘 × 10𝑚 + 𝑛.

Exemplo: De 31111 podemos utilizar a regra, se 31111 for correto, para obter o
número 301. Considere 𝑚 = 𝑛 = 1 e 𝑘 = 3.

Regra 4: Tendo o número correto 𝑘 × 10𝑚+2 + 𝑛, podemos inferir o número correto

𝑘 × 10𝑚 + 𝑛.

Exemplo: De 3010010 podemos utilizar a regra, se 3010010 for correto, para obter o
número 30110. Considere 𝑚 = 2, 𝑛 = 10 e 𝑘 = 301.

Veja nesta tabela um comparativo de derivações olhando para o sistema-MIU e sua

contraparte numérica.

Regra/Axioma Fórmula Número associado

Axioma MI 31
Regra 2 MII 311
Regra 2 MIIIII 31111
Regra 3 MUI 301
Regra 1 MUIU 3010
Regra 2 MUIUUIU 3010010
Regra 4 MUIIU 30110

Será que agora podemos utilizar estas propriedades numéricas dos números corretos,
traduções dos teoremas do sistema-MIU, para verificar se MU é um teorema, ou seja,
verificar se 30 é um número correto?

A regra 1 é uma regra de expansão, em que a acrescentamos um “0” à direita de um

número correto terminado em “1”. Veja que se o número inicial é múltiplo de 3, o
número resultante também será. Se ele não for, o número resultante NÃO será
múltiplo de 3.

A regra 2 é uma regra de expansão, em que acrescentamos dígitos “0” à direita de um

número correto e depois colamos um número 𝑛 em seu final, em que 𝑛 é
necessariamente menor do que do que a potência de 10 com tantos “0”’s quanto

Introdução à Lógica e Programação Página 96

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

aqueles adicionados. Veja que se o número inicial for múltiplo de 3, o número

resultante também será; se ele não for, o número resultante NÃO será múltiplo de 3.

Como só temos um número correto inicial, o número relacionado ao axioma MI, o

número 31, para chegarmos ao número 30 precisamos, necessariamente, utilizar uma
regra de contração.

As regras 3 e 4 são regras de contração, mas não é tão fácil verificar se o número 30
poderia ser validamente obtido utilizando estas regras. Nestas duas regras, se o
número inicial for múltiplo de 3, o número resultante também será múltiplo de 3. Por
outro lado, se ele não for múltiplo de 3, o número resultante também NÃO será
múltiplo de 3.

Todavia, conforme você deve ter resolvido no capítulo 4, nenhuma das nossas regras
numéricas altera o número obtido para um número que seja múltiplo de 3, a não ser
que ela inicie com um número que já seja múltiplo de 3. Todavia, existe somente um
axioma, o axioma 31, que não é múltiplo de 3.

Desta forma, reduzimos o problema de determinar se MU era um teorema do sistema-

MIU para verificar se os números corretos obtidos pela nossa identificação dos
símbolos com dígitos numéricos podem ser múltiplos de 3, como o número associado
à palavra MU, que como vimos, está associada ao número 30.

Teoremas da Incompletude de Gödel

O Teorema da Completude para a lógica de primeira ordem, primeiramente

demonstrado por Alfred Tarski, afirma a relação entre as abordagens sintática e
semântica para a lógica clássica, como já estudamos em capítulos anteriores.

Antes de falarmos sobre os Teoremas da Incompletude de Gödel, iremos falar sobre o

Programa de Hilbert, um matemático que viveu entre os séculos XIX e XX. Em 1900,
em uma conferência internacional de Matemática, realizada em Paris, David Hilbert
apresentou seu programa, constituindo de 23 problemas que ele desejava que a
comunidade matemática se concentrasse em resolver ao longo do século XX. Hilbert
é uma expoente da corrente que compreende a matemática como uma teoria
meramente formal, um formalista, uma filosofia da matemática que compreende-a
como uma coleção de regras que devem ser manipuladas para obtermos resultados,
diferentemente dos platonistas ou dos intuicionistas, por exemplo. Nesta abordagem
sobre os fundamentos da matemática, Hilbert acreditava que toda a matemática
poderia ser reduzida à linguagem formal lógica que o século XIX proporcionou, com a
teoria de Frege, que sistematizou a lógica clássica, como a utilizamos hoje, e a teoria

Introdução à Lógica e Programação Página 97

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

de conjuntos, que fundamenta a matemática construída a partir de elementos básicos,

os conjuntos. Um dos problemas de Hilbert, o segundo problema, a prova de que a
aritmética era consistente, ou seja, aquela estrutura lógica (seja a provinda em
formalização de teoria de primeira ordem pelos axiomas de Peano, seja aquela que
surge ao olharmos para a construção em ZFC) é incapaz de gerar uma contradição.
Isto é, ela nunca poderia provar algo falso. Por mais que ela fosse plenamente
utilizada naquela época, não existia ainda uma prova de sua consistência, ela
funcionava como teoria formal muito bem, provando todos os teoremas numéricos
que “sabíamos” (seja pela prática ou pela intuição) serem verdadeiros.

Todavia, no dia seguinte à apresentação de Hilbert, que já era um matemático

experiente e mundialmente conhecido, ocorreu a apresentação de um jovem lógico,
Kurt Gödel, que apresentou seus dois teoremas da incompletude para a lógica de
primeira ordem. Este dois teoremas destruíam dois dos objetivos de Hilbert,
primeiramente, a ideia de que TODA a matemática pudesse ser formalizada em
linguagem de primeira ordem, e por último afirmava ser IMPOSSÍVEL a resolução do
segundo problema de Hilbert.

O que afirmavam estes dois teoremas de Gödel e qual a relação com o Teorema da
Completude da lógica clássica?

A primeira resposta é: Não há relação com o Teorema da Completude para a lógica

clássica que estudamos. Aqui, nos teoremas de Gödel, a palavra “incompletude”
refere-se a outro aspecto da lógica de primeira ordem, e não sobre a relação entre as
abordagens sintática e semântica para esta lógica.

Vamos agora enunciar os dois teoremas:

Primeiro Teorema da Incompletude: Qualquer teoria axiomática recursivamente

enumerável e capaz de expressar algumas verdades básicas da aritmética não pode
ser, ao mesmo tempo, completa e consistente.

O que diz o primeiro teorema da incompletude? Que se tivermos uma teoria na lógica
clássica que contenha a aritmética, ou ela NÃO é capaz de demonstrar TODOS os
teoremas clássicos, ou ela NÃO é consistente (isto é, ela demonstra coisas que são
“falsas”).

Segundo Teorema da Incompletude: Uma teoria recursivamente enumerável e capaz

de expressar algumas verdades básicas da aritmética e alguns enunciados da teoria
da prova, pode provar sua própria consistência se e somente se for inconsistente.

O que diz o segundo teorema da incompletude? Que se uma teoria da lógica clássica,
que contenha a aritmética e mais algumas ferramentas capaz de expressar noções da
teoria da prova, como a expressão “a fórmula 𝛼 pode ser deduzida a partir de Γ”,
então esta teoria é capaz de provar ser consistente se e somente se for inconsistente,
isto é:

Introdução à Lógica e Programação Página 98

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

1– Se ela for inconsistente, ela prova ser consistente (óbvio, mas na lógica clássica
uma teoria inconsistente prova qualquer coisa, e ela é capaz de ter uma fórmula que
expressa que a teoria é consistente, dada as hipóteses);

2 – Se ela provar ser consistente, então ela é inconsistente. Este é o lado menos
“óbvio” da dupla implicação do teorema.

O primeiro teorema nos diz que não é possível termos uma teoria na lógica clássica
no qual podemos expressar TODOS os teoremas da matemática e, ao mesmo tempo,
esta teoria ser consistente.

O segundo teorema nos diz que não podemos, dentro da lógica clássica, em qualquer
teoria que contenha a aritmética, provar que esta teoria é consistente.

A estratégia usada por Gödel para demonstrar seus teoremas foi transformar as
fórmulas da lógica clássica em “números”, cada símbolo da matemática recebeu um
número, e existem diversas formas de se fazer esta enumeração, não somente
aquela que Gödel utilizou, de maneira que cada fórmula seja unicamente determinada
por um número correspondente, o número de Gödel da fórmula. Assim, falar sobre
fórmulas reduz-se a falar sobre propriedades numéricas.

O segredo utilizado por Gödel foi expressar uma fórmula que “fala” sobre ela mesma,
substituindo nessa autorreferência a fórmula por seu número correspondente:

seja 𝛼 a fórmula em linguagem de primeira ordem que expressa “A fórmula com

número de Gödel 𝑛 não pode ser provada”, em que 𝑛 é o número de Gödel da fórmula
𝛼.

Se 𝛼 for um teorema da teoria, então é verdade o que ela afirma e, portanto, a fórmula
com número de Gödel 𝑛 não pode ser provada, o que é uma contradição, já que
supomos que 𝛼 é um teorema.

Se 𝛼 não for um teorema da teoria, então é falso que “a fórmula com número de
Gödel 𝑛 não pode ser provada”, ou seja, na lógica clássica isto significa que “a
fórmula com número de Gödel 𝑛 PODE ser provada” e, portanto, 𝛼 seria um teorema,
o que é uma contradição.

A forma de prova é utilizar um tipo muito comum de paradoxo na lógica, que tem
vários “formatos”, todos eles relacionados à noção (problemática) de autorreferência.

O paradoxo do mentiroso: “Eu estou mentindo”. Quem fala isso está mentindo ou
dizendo a verdade?

Introdução à Lógica e Programação Página 99

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

O paradoxo do barbeiro: Em uma cidade existe somente um barbeiro. Todos os

homens dessa cidade se mantêm bem barbeados, de uma das seguintes formas:

1. ou eles se barbeiam;

2 ou eles são barbeados pelo barbeiro.

A pergunta que gera o paradoxo: “Quem barbeia o barbeiro”?

O paradoxo de Russel: “Seja 𝑋 o conjunto de todos os conjuntos que não contêm a si

mesmos”. 𝑋 é um elemento de 𝑋?

Se 𝑋 ∈ 𝑋 , então 𝑋 é um conjunto que NÃO contém a si mesmo, logo 𝑋 ∉ 𝑋.

Se 𝑋 ∉ 𝑋, então 𝑋 é um conjunto que NÃO contém a si mesmo, logo 𝑋 ∈ 𝑋.

Este paradoxo “desmontou” a teoria proposta por Frege para formalizar a teoria dos
conjuntos em lógica de primeira ordem, e a solução apresentada por Bertrand Russel
deu origem ao que conhecemos hoje como TEORIA DE TIPOS. É uma forma
alternativa de se trabalhar dentro de um sistema lógico, sem nos preocuparmos com a
ordem da lógica, pois dentro da teoria de tipos, existem variáveis para infinitas ordens
(é o que chamamos de tipo).

A teoria de tipos é uma construção lógica alternativa à lógica clássica, pois permite
usar, com uma mesma linguagem, quantificações para uma quantidade enumerável
de ordens (ela inclui TODAS as lógicas que seguem os princípios aristotélicos de
ordem finita).

Limites para a racionalidade

O que os teoremas da incompletude nos mostraram é que aquele paraíso lógico e

formal que se desvelou para os lógicos, matemáticos e filósofos, na virada do século
XIX, não era tão paradisíaco assim. Mostraram que há limites para aquilo que a
RAZÃO pode fazer. É por isso que o século XX viu uma ênfase tão grande na filosofia
da linguagem e da ciência, pois o formalismo e o racionalismo mostraram-se
abordagens limitadas para um discurso que se pretenda último sobre a forma como a
razão opera.

Por isso, no campo da lógica, tivemos o surgimento de infinitas lógicas, cada uma
procurando dar estrutura racional para determinado CONTEXTO RACIONAL. Por
exemplo, sabemos que dada uma configuração de um elétron, não podemos definir
de maneira precisa qual o seu “spin”, a forma como ele “gira” dentro do átomo. Por
isso, uma lógica que pretenda ser uma representação formal do discurso científico

Introdução à Lógica e Programação Página 100

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

utilizado para representar sentenças físicas deve ter um certo grau de “imprecisão”,
não podendo ser nela válido o princípio do terceiro excluído.

Outro exemplo físico é a natureza da onda na física contemporânea. A luz é tratada,

em muitos aspectos, como uma partícula – ver a teoria da física óptica. Em outros
aspectos, a luz deve ser tratada como uma onda – ver a teoria do eletromagnetismo.
Isto é o que é conhecido como “dualidade onda-partícula”, ou seja, à luz da física
contemporânea, a proposição p “a luz é uma onda” é ao mesmo tempo verdadeira e
falsa, portanto não seria válido, em uma lógica para esta teoria, o princípio da não
contradição (para estes casos, existem as lógicas PARACONSISTENTES, e um dos
principais responsáveis pela criação destas lógicas é o matemático, lógico e filósofo
brasileiro Newton da Costa, que foi orientador de meu orientador de doutorado).

Se pensarmos em um nível computacional, muitas demandas exigem uma

formalização não contínua para os valores de verdade de uma proposição, e por isso,
existem lógicas com infinitos valores de verdade ou até mesmo valores de verdade
que são “temporários”, como as lógicas probabilísticas e as lógicas do tipo fuzzy. Um
dos nomes mais importantes para o estudo de estruturas semânticas para lógicas
com muitos ou infinitos valores de verdade foi o da lógica e filósofa brasileira Andrea
Loparic, falecida em 2021, e que tive a honra de ser aluno.

Inteligência artificial

Somente com o advento de outras “lógicas” é que foi possível o desenvolvimento de

uma “inteligência artificial”. Se for possível termos uma formalização, em linguagem
simbólica e computacional, de sistemas em que o valor de verdade de uma
determinada proposição é indeterminado, podendo ser alterado a cada nova
informação adquirida pelo “sistema”, podemos ter um sistema eletrônico que acumula
“conhecimento” através de suas “experiências”. Esta é a lógica por trás da inteligência
artificial. Ela é capaz de executar ações de acordo com a forma que é programada,
mas também ela é capaz de assimilar novas informações (sobre o contexto que ela
“entende”, ou seja, que foi programada), e utilizar estas novas informações para
enriquecer suas tomadas de decisão no futuro, para além da programação que
recebeu “inicialmente”.

EXERCÍCIOS

1. Uma forma de prova de que NÃO existe um maior número primo é aquela
apresentada por Euclides. Ela começa supondo que existe O maior número primo e, a
partir desta hipótese, chegar a uma contradição. Tente usar este argumento para
provar que NÃO existe o maior número primo.

2. Prove por contradição que √2 não é um número racional. Suponha que ele seja e,
com isso, deduza uma contradição – é o que chamamos de prova por redução ao
absurdo ou prova por contradição.
Introdução à Lógica e Programação Página 101
 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Introdução à Lógica e Programação Página 102

 Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo – Campus Montanha

Bibliografia

DAURICIO, J. S. Algoritmos e Lógica de Programação. Editora e Distribuidora

Educacional S.A, Londrina. 2015.

DA COSTA, N. Ensaio Sobre os Fundamentos da Lógica. Editora Hucitec, São

Paulo. 2008.

BOOLOS, G. S.; BURGESS, J. P. Jeffrey, R. C. Computabilidade e Lógica. Editora

Unesp, São Paulo. 2012.

BUTTON, T. WALSH, S. Philosophy and Model Theory. Oxford University Press,

London. 2018.

COPI, I. M.; et al. Introduction to Logic. 4. ed. Pearson Education, Haslow. 2014.

FAJARDO, R. A. S. Lógica Matemática. EDUSP, São Paulo. 2017.

MORTARI, C. A. Introdução à Lógica. Editora UNESP, São Paulo. 2001.

RUGGIERO, M. A. G.; LOPES, V. L. da R. Cálculo Numérico: Aspectos Teóricos e

Computacionais. Pearson, São Paulo. 2000.

HOFSTADTER, D. R. Gödel, Escher, Bach: an eternal Golden Braid. Basic Books,

New York. 1999.

Introdução à Lógica e Programação Página 103