L0g1c4 p4r4 C0mput4c40

Prévia do material em texto

Lo´gica para Computac¸a˜o
Jose´ de Oliveira Guimara˜es
josedeoliveiraguimaraes@gmail.com
Campus de Sorocaba da UFSCar
Sorocaba - SP
20 de marc¸o de 2011
Suma´rio
1 Introduc¸a˜o e Histo´ria 3
1.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Histo´ria, Paradoxos e Princ´ıpios Ba´sicos . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Sistemas Formais 8
2.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Problematizando o Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Alfabetos, Axiomas e Regras de Sistemas Formais . . . . . . . . . . . . . . . . . . . 8
2.4 Visa˜o Alternativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Conexo˜es com a Computac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.1 Regras Como Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.2 Programas Como Sistemas Formais . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.3 Autoˆmato Celular e Jogo da Vida . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5.4 Grama´ticas Como Sistemas Formais . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.5 Suposic¸o˜es Impl´ıcitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.7 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Introduc¸a˜o ao Ca´lculo Proposicional 24
3.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 A Linguagem do Ca´lculo Proposicional . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Semaˆntica do Ca´lculo Proposicional 28
i
4.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Problematizando o Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Mapeamento de Frases para o Ca´lculo Proposicional . . . . . . . . . . . . . . . . . . 28
4.4 Verdade e Falsidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.5 Tabelas Verdade dos Conectivos Ba´sicos . . . . . . . . . . . . . . . . . . . . . . . . 30
4.6 Conectivos Derivados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.7 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.8 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5 Tabelas Verdade e Tautologias 34
5.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 Problematizando o Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.3 Tabelas Verdade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.4 Tautologias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.5 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6 Proposic¸o˜es sobre Tautologias e Equivaleˆncias Lo´gicas 42
6.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.2 Proposic¸o˜es sobre Tautologias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3 Equivaleˆncia Lo´gica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.4 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7 Minimizac¸a˜o de Fo´rmulas Lo´gicas 51
7.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.2 Problematizando o Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.3 Minimizac¸a˜o de Fo´rmulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.4 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
7.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
8 Conjunto Adequado de Conectivos e Formas Normais 56
8.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
8.2 Problematizando o Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
8.3 Conjunto Adequado de Conectivos e Formas Normais . . . . . . . . . . . . . . . . . 57
8.4 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
ii
8.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
9 Sintaxe do Ca´lculo Proposicional 71
9.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
9.2 Problematizando o Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
9.3 Sintaxe do Ca´lculo Proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.4 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
9.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
10 Relac¸a˜o Sintaxe/Semaˆntica 80
10.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
10.2 Relac¸a˜o entre Sintaxe e Semaˆntica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
10.3 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
10.4 Conexo˜es com a Computac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
10.4.1 Ana´lise Sinta´tica e Grama´tica da Linguagem do Ca´lculo Proposicional . . . 87
10.4.2 Enumerac¸a˜o das Fo´rmulas do Ca´lculo Proposicional . . . . . . . . . . . . . . 88
10.4.3 Axiomatizac¸a˜o do Ca´lculo Proposicional . . . . . . . . . . . . . . . . . . . . 88
10.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
11 Resoluc¸a˜o e Fo´rmulas de Horn 91
11.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
11.2 Problematizando o Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
11.3 Transformac¸a˜o de fo´rmulas para a FNC . . . . . . . . . . . . . . . . . . . . . . . . . 91
11.4 Algoritmo de Horn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
11.5 O Algoritmo da Resoluc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
11.6 Conexo˜es com a Computac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
11.7 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
11.8 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
12 Lo´gica de Primeira Ordem 105
12.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
12.2 Problematizando o Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
12.3 Introduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
12.4 A Linguagem da Lo´gica de Primeira Ordem . . . . . . . . . . . . . . . . . . . . .. 109
12.5 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
iii
12.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
13 Semaˆntica da Lo´gica de Primeira Ordem 118
13.1 Primeiras palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
13.2 Problematizando o Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
13.3 Introduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
13.4 Definic¸a˜o Formal de Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
13.5 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
13.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
14 Sintaxe da Lo´gica de Primeira Ordem 149
14.1 Axiomas e Regras de Deduc¸a˜o da Lo´gica de Primeira Ordem . . . . . . . . . . . . . 150
14.2 Meta-teoremas e Definic¸o˜es sobre as Teorias de Primeira Ordem . . . . . . . . . . . 152
14.3 Formas Normais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
14.4 Relac¸a˜o entre Sintaxe e Semaˆntica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
14.5 Alguns Exemplos de Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
14.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
A Quadrinhos 168
B Noc¸o˜es Ba´sicas de Matema´tica 170
B.1 Induc¸a˜o finita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
B.2 Prova por Contradic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
1
Prefa´cio
Imagine que algue´m queira comunicar como e´ uma certa pintura para uma outra pessoa. Uma
possibilidade seria converter a pintura para o formato digital, um retaˆngulo compostos por pontos
(cada um com uma cor), e depois escrever a cor de cada ponto, comec¸ando do canto superior es-
querdo e procedendo para baixo, linha por linha, ate´ o canto inferior direito. Esta na˜o e´ uma forma
muito inteligente de comunicac¸a˜o. Contudo, e´ mais ou menos isso que fazemos quando escrevemos
um livro de Matema´tica, F´ısica ou Lo´gica. Nestes livros, uma sequ¨eˆncia de definic¸o˜es, teoremas
e provas e´ descrita linearmente tentando descrever conceitos que na˜o podem ser compreendidos
desta forma. O leitor fica com a inteira responsabilidade de agrupar todos os conceitos e montar
a “figura” em sua mente, com pouco ou nenhum aux´ılio por parte do texto.
Neste livro tentamos fazer diferente na medida de nossas possibilidades. Para ajudar o leitor
a montar a imagem da lo´gica, recorremos a dois artif´ıcios: a) comenta´rios sobre os teoremas
e provas e b) meta-informac¸o˜es no texto. Sendo este um livro de lo´gica, as informac¸o˜es sobre
lo´gica constituem a maior parte do texto. Contudo, ha´ informac¸o˜es tambe´m sobre o pro´prio
texto: refereˆncias a pa´ginas (“veja os axiomas da pa´gina 23”) e figuras que descrevem a pro´pria
estrutura das definic¸o˜es, teoremas e provas. Estes dados adicionais sa˜o meta-informac¸o˜es. Com eles
procuramos mostrar como a lo´gica e´ estruturada, quais as relac¸o˜es entre os conceitos estudados.
Os comenta´rios no texto ajudam visualizar o quadro geral. Eles procuram apresentar uma outra
visa˜o do texto, podemos dizer “do alto”, fugindo da descric¸a˜o linear de definic¸o˜es/teoremas do
livro.
Ao final de cada Cap´ıtulo deste livro pode haver treˆs subsec¸o˜es: a) Visa˜o Alternativa; b)
Conexo˜es com a Computac¸a˜o e c) Suposic¸o˜es Impl´ıcitas. A subsec¸a˜o “Visa˜o Alternativa” procura
apresentar os conceitos do Cap´ıtulo ou parte dele de maneira diferente do que foi apresentado,
facilitando a compreensa˜o do texto. Alia´s, isto ja´ e´ feito em muitos comenta´rios por todo o livro e
na˜o apenas nesta subsec¸a˜o. Qualquer texto se torna dif´ıcil de entender se apenas uma u´nica visa˜o e´
apresentada. O leitor na˜o consegue formar uma ide´ia clara dos conceitos apresentados assim como
quando enxergamos com um u´nico olho na˜o temos a ide´ia de profundidade da cena observada.
A subsec¸a˜o “Conexo˜es com a Computac¸a˜o” apresenta os poss´ıveis relacionamentos entre o
Cap´ıtulo e a Computac¸a˜o. Na˜o se pretende fazer uma apresentac¸a˜o profunda de to´picos da com-
putac¸a˜o nesta sec¸a˜o. A subsec¸a˜o “Suposic¸o˜es Impl´ıcitas” apresenta as suposic¸o˜es impl´ıcitas para
que o Cap´ıtulo seja va´lido. Frequentemente se assume que algumas coisas sejam va´lidas ou abso-
lutamente necessa´rias quando isto nem sempre e´ o caso. Esta sec¸a˜o apresenta o que normalmente
supomos ao estudar o Cap´ıtulo. Note que esta subsec¸a˜o de certa forma se sobrepo˜e com a sec¸a˜o
“Visa˜o Alternativa”. Contudo, o objetivo de ambas e´ diferente. O objetivo da subsec¸a˜o “Visa˜o Al-
ternativa” e´ fazer o leitor compreender melhor o texto. O objetivo da sec¸a˜o “Suposic¸o˜es Impl´ıcitas”
e´ abrir a mente, despertar a criatividade, mostrar que qualquer texto supo˜e um certo racioc´ınio
do leitor implicitamente e que isto poderia ser diferente. O objetivo e´ despertar o leitor para a
pesquisa em Lo´gica, embora saibamos que este e´ apenas um texto introduto´rio de lo´gica.
2
Unidade 1
Introduc¸a˜o e Histo´ria
1.1 Primeiras palavras
Lo´gica e´ a disciplina que estuda o racioc´ınio dedutivo, o que se pode deduzir a partir de premissas
consideradas verdadeiras. Como exemplo inicial, a partir das frases “todo nu´mero par e´ divis´ıvel
por 2” e “6 e´ par”, pode-se concluir que “6 e´ divis´ıvel por 2”. Na˜o interessa a` lo´gica se as duas
primeiras frases sa˜o verdadeiras no mundo real — o que interessa e´ que, se sa˜o verdadeiras, pode-se
deduzir a terceira frase a partir delas. Mortari [9] da´ a seguinte definic¸a˜o de lo´gica:
Lo´gica e´ cieˆncia que estuda princ´ıpios de infereˆncia, tendo o objetivo principal de determinar em
que condic¸o˜es certas coisas se seguem (sa˜o consequ¨eˆncia), ou na˜o, de outras.
A lo´gica e´ atualmente um enorme corpo de conhecimento que engloba quatro diferentes a´reas:
teoria da prova, teoria dos modelos, teoria axioma´tica dos conjuntos e computabilidade. Neste
curso veremos uma introduc¸a˜o a` teoria da prova e a` teoria dos modelos. Computabilidade e´ uma
a´rea vista em disciplinas de Teoria da Computac¸a˜o ou Linguagens Formais e Autoˆmatos.
1.2 Histo´ria, Paradoxos e Princ´ıpios Ba´sicos
A lo´gica foi a criac¸a˜o de um u´nico homem, Aristo´teles (384 a.C.-322 a.C.). A lo´gica de Aristo´teles
era inteiramente verbal, sem o emprego de s´ımbolos. Como exemplo, de “Todos os homens sa˜o
mortais” e “So´crates e´ um homem”, pode-se deduzir que “So´crates e´ mortal”. Este e´ um dos tipos
de racioc´ınio catalogados pelo sa´bio grego. Havia outros vinte e quatro (dos quais cinco esta˜o
impl´ıcitos em outros), todos empregando apenas palavras. Ja´ na Antigu¨idade surgiu o primeiro
‘paradoxo’ lo´gico quando o cretense Epimeˆnides disse “Todos os cretenses sa˜o mentirosos”. Na
verdade, esta frase na˜o e´ paradoxal, pois ela pode ser tanto verdadeira quanto falsa sem que ocorra
uma contradic¸a˜o.1 Uma frase e´ paradoxal quando ela na˜o pode ser nem verdadeira nem falsa,
1Se um mentiroso e´ algue´m que mente ocasionalmente e toda mentira e´ exatamente o oposto da verdade, enta˜o
esta frase pode ser falsa: Epimeˆnides estava mentindo ocasionalmente ao pronuncia´-la. Se tomarmos ‘mentiroso’
como algue´m que mente sempre, enta˜o esta frase e´ falsa. Se fosse verdadeira, como foi dita por um cretense, ela
estaria dizendo que ela mesmo e´ falsa. Contradic¸a˜o. Como esta frase e´ falsa, Epimeˆnides queria dizer exatamente
3
como “esta frase e´ falsa”. Outro falso paradoxo e´ a frase “toda regra tem excec¸a˜o”.
Paradoxos em geral sa˜o frases que referenciam a si mesmas. Masnem todas as frases deste
tipo sa˜o paradoxais. Por exemplo, a frase “esta frase e´ verdadeira” na˜o e´ paradoxal. Ela pode
perfeitamente ser verdadeira. Grande parte dos paradoxos conte´m uma auto refereˆncia e uma
negac¸a˜o, como “esta frase e´ falsa”.
A lo´gica era uma das disciplinas estudadas tanto na Idade Antiga quanto na Idade Me´dia,
chegando aos tempos modernos. Contudo, aparentemente nada faltava ao estudo da lo´gica e esta
disciplina na˜o foi um to´pico se´rio de pesquisa ate´ meados do se´culo XIX quando recomec¸ou o
interesse no assunto, comec¸ando com Boole, Peano, Fregue e Bertrand Russel. O interesse destes
matema´ticos era prover uma base so´lida para a Matema´tica.
Ha´ inumera´veis tipos de lo´gica como lo´gica cla´ssica, modal, paraconsistente, multivalorada,
intuicionista, fuzzy, temporal, quaˆntica, ... A lo´gica que mais interessa a` Computac¸a˜o e´ a Lo´gica
Matema´tica, que abstrai os racioc´ınios utilizados em Matema´tica. Esta lo´gica utiliza treˆs princ´ıpios
colocados por Aristo´teles:
1. princ´ıpio da na˜o contradic¸a˜o: na˜o e´ verdade que uma proposic¸a˜o A e a sua negac¸a˜o sejam
verdadeiras ao mesmo tempo. Em s´ımbolos (que estudaremos mais tarde), escrevemos
¬(A ∧ ¬A)
2. princ´ıpio do terceiro exclu´ıdo: ou a proposic¸a˜o A ou a sua negac¸a˜o sa˜o verdadeiras. Em
s´ımbolos:
A ∨ ¬A
3. reflexividade da identidade: qualquer coisa e´ igual a si mesma. Em s´ımbolos:
∀x(x = x)
As lo´gicas chamadas cla´ssicas, entre as quais se incluem a lo´gica Matema´tica, seguem os treˆs
princ´ıpios acima. As lo´gicas na˜o cla´ssicas (paraconsistente, multivalorada, fuzzy, quaˆntica, etc)
na˜o seguem um, dois ou treˆs destes princ´ıpios.
No final do se´culo XIX e in´ıcio do se´culo XX surgiram diversos paradoxos lo´gicos, classificados
como sinta´ticos (ou lo´gicos) e semaˆnticos. O paradoxo sinta´tico mais conhecido foi descoberto por
Russel em 1902 enquanto estudava teoria dos conjuntos de Cantor. Os paradoxos aparecem quando
conjuntos podem ser definidos a partir de uma lei ou fo´rmula qualquer. Vejamos o paradoxo.
Considere o conjunto C de todos os conjuntos que na˜o pertencem a si mesmos:
C = {x : x 6∈ x}
A fo´rmula “x 6∈ x” que aparece depois dos “:” e´ a condic¸a˜o para um elemento pertencer ao
conjunto C. Chamaremos esta fo´rmula de A. Enta˜o,
• se um dado y obedece a esta fo´rmula/condic¸a˜o, enta˜o y pertence a C. Em outras palavras,
se y 6∈ y, enta˜o y ∈ C. Por outro lado, se y na˜o obedece a esta fo´rmula (y ∈ y), y 6∈ C. Isto
e´, se y ∈ y enta˜o y 6∈ y;
o contra´rio do que disse, que alguns cretenses na˜o sa˜o mentirosos ! Naturalmente, neste caso Epimeˆnides e´ um
mentiroso.
4
• qualquer y que pertence a C obedece a esta fo´rmula/condic¸a˜o; isto e´, se y ∈ C, enta˜o y 6∈ y.
Se y na˜o pertence a C enta˜o y na˜o obedece a` fo´rmula A. Isto e´, se y 6∈ C, enta˜o y ∈ y.
Pergunta-se: C pertence a C? Vejamos as duas possibilidades:
• sim, C ∈ C. Enta˜o C deve obedecer a` condic¸a˜o/fo´rmula A (x 6∈ x com x = C) do conjunto
C. Enta˜o C 6∈ C. Contradic¸a˜o, pois assumimos que C ∈ C;
• na˜o, C 6∈ C. Enta˜o C obedece a` condic¸a˜o/fo´rmula A necessa´ria para pertencer a` C (x 6∈ x
com x = C) e, portanto, C ∈ C. Contradic¸a˜o.
De qualquer forma, C pertencendo ou na˜o a si mesmo, chegamos a uma contradic¸a˜o.
Os matema´ticos e lo´gicos eliminaram este tipo de contradic¸a˜o da teoria dos conjuntos criando
uma teoria de conjuntos chamada de Zermelo-Fraenkel. Nesta teoria, a condic¸a˜o x 6∈ x na definic¸a˜o
do conjunto C na˜o e´ considerada va´lida. E enta˜o C na˜o e´ considerado um conjunto.
Este paradoxo e´ chamado de sinta´tico porque ele pode ser descrito utilizando a linguagem
formal da Lo´gica de Primeira Ordem (que ainda sera´ visto). Ja´ os paradoxos semaˆnticos na˜o
podem ser descritos utilizando uma linguagem formal.
Ha´ diversos paradoxos semaˆnticos descritos na literatura. Veremos alguns:
1. se a frase “esta frase e´ falsa” for verdadeira, enta˜o ela diz que e´ falsa. Contradic¸a˜o. Se ela
for falsa, enta˜o o contra´rio e´ verdadeiro, ou seja, ela e´ verdadeira;
2. paradoxo de Berry (1906). Ha´ um nu´mero finito de palavras em Portugueˆs e portanto um
nu´mero finito de frases com menos do que vinte palavras. Considere o conjunto de todos os
nu´meros naturais (N) que podem ser definidos com frases com menos do que vinte palavras.
Este conjunto sera´ chamado de M e conte´m os seguintes inteiros, pelo menos: 1 (“um”), 323
(“trezentos e vinte e treˆs”, frase com menos do que vinte palavras), 5 (“o terceiro nu´mero
primo”), 1024 (“a primeira poteˆncia de dois maior do que mil”), 21000000000!! (“o fatorial do
fatorial de dois elevado a um bilha˜o”). Ha´ um nu´mero finito de nu´meros naturais no conjunto
M . Mas quantos? Vamos calcular quantas frases de 20 palavras existem, no ma´ximo. Cada
palavra tem menos do que 100 letras (exagerando!). Enta˜o temos 100 ∗ 20 = 2000 caracteres
para as palavras. Supondo que temos 26 letras (agora o Portugueˆs usa 26 letras), temos no
ma´ximo 262000 frases diferentes com 20 palavras. Calcular o nu´mero ma´ximo de frases com
menos do que vinte palavras fica como exerc´ıcio (e´ uma progressa˜o geome´trica). De qualquer
forma, este nu´mero e´ finito, isto e´, o tamanho do conjunto M e´ finito.
Estariam em M o 0 (“zero”), o 125 (“primeiro quadrado perfeito depois de 100”) e
999999999999999999999999999999
(“um nu´mero composto por trinta noves”). Claramente existe um inteiro n que e´ o maior
elemento de M mais 1. Claramente n na˜o esta´ em M — ele e´ maior do que o maior
elemento de M , embora seja apenas uma unidade maior. Como n e´ apenas o maior elemento
de M mais 1 (e apenas +1), enta˜o n e´ o menor inteiro maior do que o maior elemento
de M , o conjunto dos inteiros que podem ser definidos com menos do que vinte palavras.
Enta˜o “n e´ o menor inteiro que na˜o pode ser definido com menos do que vinte palavras”.
Mas esta frase conte´m menos do que vinte palavras. Logo n pertence a M . Contradic¸a˜o,
pois assumimos que ele na˜o pertencia a este conjunto. Na˜o e´ poss´ıvel definir o conjunto M
sem cair em uma contradic¸a˜o;
5
3. paradoxo de Grelling (1908). Um adjetivo e´ chamado de autolo´gico se a propriedade que ele
denota se aplica a si mesmo, e de heterolo´gico em caso contra´rio. Por exemplo, “vermelho”
e´ heterolo´gico, pois este adjetivo na˜o e´ vermelho (adjetivos na˜o teˆm cor). Ja´ “polissila´bico”
e´ autolo´gico, pois esta palavra possui seis s´ılabas. “Monossila´bico” e´ heterolo´gico pois pos-
sui mais de uma s´ılaba. Pergunta-se: e´ “heterolo´gico” um adjetivo heterolo´gico? Se sim,
a propriedade heterolo´gica na˜o se aplica a` palavra “heterolo´gica” e enta˜o esta palavra e´
autolo´gica. Contradic¸a˜o, pois assumimos que a palavra e´ heterolo´gica. Se “heterolo´gico”
e´ autolo´gico, a propriedade heterolo´gica se aplica a` palavra “heterolo´gico” e portanto esta
palavra e´ heterolo´gica. Contradic¸a˜o novamente.
Os paradoxos semaˆnticos na˜o interessam a` lo´gica que estudaremos, a lo´gica Matema´tica. Eles
envolvem noc¸o˜es da linguagem natural (Portugueˆs) que na˜o ocorrem em Matema´tica.
Comec¸aremos o estudo da lo´gica apresentando os sistemas formais, que sa˜o sistemas capazes
de produzir “sentenc¸as”, chamadas de teoremas, a partir de axiomas e regras. Esta introduc¸a˜o
e´ necessa´ria porque toda lo´gica e´ um sistema formal. Na Sec¸a˜o 3.2, sera´ estudado o ca´lculo
proposicional, que e´ uma lo´gica bem simples e que faz parte da lo´gica que nos interessa, que e´ a
Lo´gica de Primeira Ordem, que sera´ estudada na Unidade 12. A Lo´gica de Primeira Ordem utiliza
os chamados quantificadores universais (para todo x vale a proposic¸a˜o P(x)) e existenciais (existe
x tal que P(x)).
1.3 Considerac¸o˜es Finais
Uma frase e´ paradoxal quando ela na˜o pode ser nem verdadeira nem falsa, como “esta frase e´
falsa”. Ha´ paradoxos sinta´ticos e semaˆnticos, sendo que paraa lo´gica matema´tica o que interessa
sa˜o os paradoxos sinta´ticos, como o paradoxo de Russel.
Ha´ inu´meros tipos de lo´gica: cla´ssica, modal, paraconsistente, fuzzy, quaˆntica, etc, sendo que
a lo´gica que veremos e´ a lo´gica matema´tica, uma das lo´gicas cla´ssicas. O ca´lculo proposicional,
que faz parte da lo´gica matema´tica, e´ a base para a construc¸a˜o de computadores.
1.4 Exerc´ıcios
Atividades Individuais
1.1. Cite treˆs lo´gicas. Qual estudamos neste curso? Por queˆ?
1.2. Fac¸a uma sentenc¸a que na˜o e´ verdadeira nem falsa diferente das que foram apresentadas no
texto.
1.3. Por queˆ a frase “toda regra tem excec¸a˜o” na˜o e´ paradoxal?
1.4. Explique com suas palavras o paradoxo de Berry.
1.5. Explique o paradoxo de Russel.
6
1.6. Procure na Internet algo mais sobre a histo´ria da lo´gica. Alguns to´picos e personagens
interessantes sa˜o:
1. lo´gica na idade me´dia
2. Leibniz
3. Fregue
4. Go¨del
5. Tarski
7
Unidade 2
Sistemas Formais
2.1 Primeiras palavras
Esta Unidade introduz sistemas formais de maneira informal. Um sistema formal e´ uma maneira
de gerar sequ¨eˆncias de s´ımbolos de maneira sistema´tica e precisa. Como exemplo, podemos ter um
sistema formal capaz de gerar todas as expresso˜es aritme´ticas com nu´meros inteiros e operadores
+, − e ∗ (multiplicac¸a˜o). Como exemplos de sequ¨eˆncias deste sistema formal temos 1 + 2, 1 ∗ 2 +
2 ∗ 3 + 3 ∗ 4 e 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 − 1. Sendo preciso, este sistema formal nunca geraria expresso˜es
incorretas como 1 + ∗2 ou 24∗. A lo´gica matema´tica que estudaremos e´ composta por um sistema
formal mais uma interpretac¸a˜o deste sistema — e´ por este motivo que estudaremos este to´pico.
2.2 Problematizando o Tema
Frequentemente temos um conjunto de elementos de qualquer coisa (nu´meros, palavras, s´ımbolos,
blocos de pla´stico, fo´rmulas, etc) que podem ser constru´ıdos a partir de algumas regras ba´sicas.
Isto e´, dadas as regras e um certo conjunto de pec¸as iniciais, pode-se construir o conjunto todo.
O conjunto pode mesmo ser infinito. Por exemplo, a partir do nu´mero 1 e da soma repetida
do nu´mero 2, podemos construir somas que, quando avaliadas, resultam no conjunto de todos os
nu´meros ı´mpares: 1, 1+2, 1+2+2), . . .. Esta unidade trata justamente deste tipo de “construc¸a˜o”
de conjuntos. A questa˜o e´ como definir esta construc¸a˜o de maneira formal, precisa. E´ este o to´pico
desta unidade.
2.3 Alfabetos, Axiomas e Regras de Sistemas Formais
O que e´ um sistema formal? E´ um sistema que consiste de
1. um alfabeto de s´ımbolos composto por quaisquer s´ımbolos que podem ser colocados no
papel;
8
2. sequ¨eˆncias1 bem definidas de s´ımbolos deste alfabeto chamadas de fo´rmulas. Deve ser
poss´ıvel definir precisamente o que e´ fo´rmula;
3. axiomas (um subconjunto das fo´rmulas) e
4. regras para produzir novas fo´rmulas a partir de outras.
Antes de mais nada, saiba que as palavras fo´rmula, axioma e teorema empregadas nesta
unidade sa˜o definidas de maneira bem diferente do que voceˆ conhece na Matema´tica. Utilize as
definic¸o˜es dadas neste texto e na˜o as relacione com as definic¸o˜es que voceˆ conhece. Em particular,
na˜o considere que um axioma e´ uma proposic¸a˜o verdadeira ou que um teorema e´ algo sobre alguma
entidade matema´tica.
Exemplo 2.1. Como exemplo, vamos definir um sistema formal que chamaremos de S. O alfabeto
poderia ser qualquer coisa, mas utilizaremos apenas os d´ıgitos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Enta˜o o
sistema S so´ utilizara´ estes s´ımbolos e nada mais. Note que e´ voceˆ, o criador do sistema formal,
que decide que s´ımbolos utilizar. O alfabeto pode ser qualquer conjunto de s´ımbolos, ate´ mesmo
s´ımbolos que na˜o estejam no teclado e que so´ possam ser desenhados a` ma˜o ou em alguma ferra-
menta de desenho. So´ que a´ı ficaria muito dif´ıcil fazer as coisas. Em resumo, para facilitar, utilize
apenas os s´ımbolos que esta˜o no teclado ou dispon´ıveis no Moodle (para facilitar, utilize apenas os
do teclado). Enta˜o temos que o alfabeto do sistema S e´ o conjunto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Note tambe´m que na˜o estamos nos referindo a estes d´ıgitos como nu´meros inteiros. Sa˜o apenas
s´ımbolos que na˜o sera˜o utilizados como nu´meros, pelo menos por enquanto.
O conjunto de todas as sequ¨eˆncias de s´ımbolos do alfabeto formam um conjunto infinito.
Chamaremos este conjunto de Σ?, que conte´m 0, 1, 2, . . . e qualquer concatenac¸a˜o de s´ımbolos do
alfabeto. Por exemplo, podemos concatenar 0 e 1 para obter 01 e enta˜o 01 ∈ Σ?. Ou podemos
concatenar va´rios s´ımbolos de uma so´ vez, em qualquer ordem, para obter uma sequ¨eˆncia qualquer,
que pertencera´ a` Σ?. Enta˜o os seguintes s´ımbolos pertencem a` Σ?: 01, 787, 754732104823, 5, 6666,
... Em resumo, qualquer nu´mero inteiro, quando considerado apenas como uma sequ¨eˆncia de
s´ımbolos do conjunto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, pertence a` Σ?.
Um sistema formal na˜o utiliza todas as sequ¨eˆncias de s´ımbolos do alfabeto, o conjunto Σ?. Em
geral, ele utiliza um conjunto menor de s´ımbolos que chamaremos de conjunto de fo´rmulas.
Algumas sequ¨eˆncias de Σ? sera˜o consideradas fo´rmulas e outras na˜o. Quem projeta o sistema
formal decide o que sera´ considerado fo´rmula. Podemos, por exemplo, considerar como fo´rmulas
todas as sequ¨eˆncias que terminam com 1, 3, 5, 7 e 9. Assim, seriam fo´rmulas:
1, 3, 5, 7 9 (um u´nico s´ımbolo termina com ele mesmo)
871, 41, 44445, 382578057, 89, 2323, 98973555
Mas na˜o seriam fo´rmulas as sequ¨eˆncias
8, 4, 44, 444, 382578058, 86, 232, 9897356
Naturalmente, neste caso ha´ infinitas sequ¨eˆncias que sa˜o fo´rmulas e infinitas que na˜o sa˜o.
Para facilitar a definic¸a˜o do nosso sistema S, consideraremos como fo´rmulas todas as sequ¨eˆncias
de s´ımbolos do alfabeto. Assim, o conjunto de fo´rmulas e´ igual a Σ?.
1strings em Ingleˆs
9
O terceiro item a ser definido para um sistema formal e´ o conjunto de axiomas. Um axioma
deve ser um dos elementos do conjunto de fo´rmulas. Voceˆ escolhe quantos e quais elementos deste
conjunto sera˜o axiomas. Escolheremos dois, 0 e 5.
Resta agora definir um conjunto de regras. Uma regra ensina como produzir um teorema.
Pode-se dizer que uma regra toma um ou mais teoremas e produz um outro teorema. Mas o que
e´ um teorema? Em primeiro lugar, por definic¸a˜o todo axioma e´ um teorema. Em segundo lugar,
um teorema e´ uma fo´rmula produzida por uma regra. Note que um teorema tem que ser uma
fo´rmula. Foi por isso que foi dada a definic¸a˜o de fo´rmula!
Como deve ser uma regra? Pode ser praticamente qualquer sequ¨eˆncia de instruc¸o˜es que voceˆ
possa imaginar que tome um ou mais teoremas como entrada e produza um teorema como sa´ıda.
Um exemplo poderia ser:
[R1 - Regra 1] Se x e y sa˜o teoremas, enta˜o xy e´ um teorema.
Sempre utilizaremos um s´ımbolo ao lado do outro, como “xy”, para representar a concatenac¸a˜o
dos s´ımbolos de x e y. Por exemplo, se x e´ 005 e y e´ 050, enta˜o xy e´ 005050.
A regra pega teoremas e produz teoremas, sendo que a definic¸a˜o de “teorema” envolve a
definic¸a˜o de “regra”. Isto parece uma definic¸a˜o circular. Mas na˜o e´, porque a definic¸a˜o de teorema
diz que todo axioma e´ um teorema. Enta˜o para produzir os teoremas do sistema S, comec¸amos
com os axiomas, 0 e 5 e podemos ir aplicando a regra R1 para produzir novos teoremas.
Vejamos alguns:
• 0, pois 0 e´ axioma e todo axioma e´ teorema;
• 5, pois 5 e´ axioma e todo axioma e´ teorema;
• 00, pois podemos usar R1 com x = 0 e y = 0;
• 55, pois podemos usar R1 com x = 5 e y = 5;
• 05, pois podemos usar R1 com x = 0 e y = 5;
• 5505, pois podemos usar R1 com x = 55 e y = 05. Sabemos que 55 e 05 sa˜o teoremas pelos
itens anteriores;
• ...
Em resumo, partimos dos axiomas e, aplicando a regra R1, podemos ir produzindo uma
sequ¨eˆncia infinita de teoremas. Note novamente que todosos axiomas sa˜o teoremas e que to-
dos os teoremas sa˜o fo´rmulas.
Voceˆ pode definir quantas regras quiser, de que modo for necessa´rio. Digamos que o seu
objetivo seja produzir como teoremas todas as fo´rmulas que terminam em 0 ou 5. Enta˜o deveriam
ser teoremas:
0, 5, 10, 15, 20, 25, 30, 35, . . ., 1000, 1005, 2967305, . . ., 98973555, . . .
Para isto, podemos adicionar uma outra regra ao sistema S:
10
Figura 2.1: Relac¸o˜es entre os conjuntos de um sistema formal
[R2 - Regra 2] Se x for um teorema, dx sera´ tambe´m um teorema, no qual d pode ser
qualquer s´ımbolo do alfabeto (mas um u´nico s´ımbolo).
Utilizando a regra R2, temos alguns novos teoremas:
• 10, com d = 1 e x = 0, pois 0 e´ axioma e todo axioma e´ teorema;
• 15, com d = 1 e x = 5, pois 5 e´ axioma e todo axioma e´ teorema;
• 20, com d = 2 e x = 0. Como sabemos, 0 e´ um teorema;
• 25, com d = 2 e x = 5. Como sabemos, 5 e´ um teorema;
• 325, com d = 3 e x = 25. Pelo item anterior, 25 e´ um teorema;
• 8325, com d = 8 e x = 325. Pelo item anterior, 325 e´ um teorema.
As regras podem ser aplicadas em qualquer ordem e qualquer nu´mero de vezes.
�
Voceˆ e´ agora estimulado a fazer o seu pro´prio sistema formal. Defina o alfabeto, o que e´ fo´rmula,
os axiomas e o conjunto de regras. Lembre-se de que, se Σ e´ o alfabeto,Σ? o conjunto de todas as
sequ¨eˆncias poss´ıveis de s´ımbolos do alfabeto, ∆ o conjunto de fo´rmulas, Γ o conjunto de axiomas
e Φ o conjunto de teoremas, as seguintes relac¸o˜es devem ser verdadeiras: Γ ⊂ Φ ⊂ ∆ ⊂ Σ?. Veja
a Figura 2.1.
Ha´ dois outros to´picos importantes sobre sistemas formais. O primeiro e´ o conceito de meta-
teorema. Um meta-teorema e´ um teorema sobre o pro´prio sistema formal. Nesta u´ltima frase
utilizamos a palavra “teorema” no sentido usual da Matema´tica, na˜o no sentido definido nesta
unidade para sistemas formais. Em resumo, um meta-teorema e´ uma proposic¸a˜o sobre o pro´prio
sistema formal. Por exemplo, estude este meta-teorema sobre o sistema formal S dado acima:
[Meta-teorema] Se x e´ um teorema do sistema formal S, enta˜o x termina com 0 ou 5.
Os axiomas sa˜o 0 e 5 e as regras R1 e R2 preservam estes d´ıgitos na u´ltima posic¸a˜o. Confira.
11
Depois que voceˆ define o alfabeto, fo´rmulas, axiomas e regras de um certo sistema formal, estes
obviamente ficam fixados. Se quiser, pode fazer outro sistema com outras regras. Mas as de um
certo sistema formal, como S, ficam fixas.
Veremos agora um outro conceito, que e´ o de “esquema de axioma”. Estudaremos um outro
exemplo de sistema formal para apresentar este conceito.
Exemplo 2.2. Faremos um sistema formal que produza como teoremas todas as combinac¸o˜es
poss´ıveis de consoante/vogal utilizando o alfabeto minu´sculo latino, qualquer nu´mero de vezes.
Mas precisamente, os teoremas devem ser do tipo c1v1c2v2...cnvn no qual ci e´ uma consoante, vi e´
uma vogal e n ∈ N. Isto e´, o sistema formal devera´ produzir todos os seguintes teoremas:
ba, be, bi, bo, bu, da, de, di, do, du, ... za, ze, zi, ze, zu, bada, bade, badi, ... badaca, badace, ...
tadefu, caravela, metalizado, ...
Chamaremos este sistema formal de T. Fica claro que o alfabeto de T deve ser { a, b, c, d, e, f,
g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z }. Agora temos que definir o que e´ fo´rmula. Temos
muitas opc¸o˜es e utilizaremos a mais fa´cil delas: uma fo´rmula e´ qualquer sequ¨eˆncia de s´ımbolos do
alfabeto de T. Enta˜o asfas, fdiemn, jnvcb, y, ym, iq, ... sa˜o fo´rmulas.
O problema esta´ agora. O que deve ser axioma? E o que deve ser regra? Temos que definir as
duas coisas juntas para que, combinadas, possam produzir os teoremas esperados. Uma forma e´
definir todas as combinac¸o˜es de consoante e vogal como axiomas. Assim, o conjunto de axiomas
seria
ba, be, bi, bo, bu, ca, ce, ci, co, cu, da, de, ..., za, ze, zi, zo, zu
Como isto e´ um sistema formal, na˜o poder´ıamos utilizar “...” na definic¸a˜o do conjunto. Ter´ıamos
que escrever todas as 21 ∗ 5 = 105 combinac¸o˜es de consoantes e vogais. E´ muita coisa. Mas feliz-
mente ha´ uma maneira mais fa´cil de fazer isto: utilizando um esquema de axioma:
[Esquema de axioma] Se C e´ uma consoante e V uma vogal do alfabeto de T, enta˜o CV e´ um
axioma.
Este esquema de axioma representa todas as 105 combinac¸o˜es poss´ıveis de axiomas. Qualquer
fo´rmula que se encaixe na definic¸a˜o do esquema de axioma e´ considerado um axioma, o que e´
exatamente o que queremos. Enta˜o ca e´ um axioma, pois “c” e´ uma consoante e “a” e´ uma vogal.
Falta fazer a regra de T. Simples:
[R1 - regra 1] Se x e y sa˜o teoremas, xy e´ teorema.
Enta˜o sa˜o teoremas
• ca, pois ca e´ axioma e todo axioma e´ teorema;
• ra, pois ra e´ axioma e todo axioma e´ teorema;
• cara, pois podemos usar R1 com x = ca e y = ra;
• ve, pois ve e´ axioma e todo axioma e´ teorema;
• carave, pois podemos usar R1 com x = cara e y = ve;
• la, pois la e´ axioma e todo axioma e´ teorema;
12
• caravela, pois podemos usar R1 com x = carave e y = la;
• ...
Podemos ter va´rios meta-teoremas para o sistema R. Vejamos alguns:
[Meta-teorema 1] todo teorema tem um nu´mero par de letras.
[Meta-teorema 2] todo teorema comec¸a com uma consoante.
[Meta-teorema 3] todo teorema termina com uma vogal.
�
O sistema T como definimos satisfaz todas as especificac¸o˜es iniciais. Mas esta na˜o e´ a u´nica
forma de satisfazer aquelas especificac¸o˜es. O que queremos e´ que o sistema produza como teoremas
todas as sequ¨eˆncias c1v1c2v2...cnvn no qual ci e´ uma consoante, vi e´ uma vogal e n ∈ N. Enta˜o
podemos definir um outro sistema U que produz estes teoremas.
Exemplo 2.3. O alfabeto de U e´ o mesmo de T, { a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r,
s, t, u, v, w, x, y, z }. A definic¸a˜o de fo´rmula pode ser: uma sequ¨eˆncia de s´ımbolos s e´ fo´rmula se
comec¸ar por uma consoante e terminar por uma vogal. Claramente, todos os teoremas sa˜o desta
forma, enta˜o esta definic¸a˜o na˜o vai “atrapalhar” a produc¸a˜o de teoremas.
Definiremos um u´nico esquema de axioma:
[Esquema de axioma] Ca, Ce, Ci, Co, e Cu sa˜o axiomas se C for uma consoante do alfabeto de U.
Enta˜o sa˜o axiomas as fo´rmulas ba, be, bi, bo, bu (usando C = b), ca, ce, ci, co, cu (usando C
= c), da, de, ..., za, ze, zi, zo, zu, como esperado.
E definiremos duas regras:
[R1 - regra 1] Se x for um teorema, Cax e Cex sera˜o teoremas, no qual C e´ uma consoante do
alfabeto de U.
[R2 - regra 2] Se x for um teorema, xCi, xCo e xCu sera˜o teoremas, no qual C e´ uma consoante
do alfabeto de U.
Por R1, cara e´ teorema. Vejamos porque: tomando C = c e x = ra, temos que Cax e´ cara. ra
e´ teorema por ser axioma. Este sistema formal e´ mais dif´ıcil de trabalhar do que o sistema T mas
define exatamente o mesmo conjunto de teoremas.
�
Um esquema de axioma pode representar infinitos axiomas. Por exemplo, em um sistema
formal que utiliza o alfabeto {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,+, ?}, um esquema de axioma poderia ser:
[Esquema de axioma] x+ y e´ um axioma se x e y forem sequ¨eˆncias de s´ımbolos compostos apenas
por d´ıgitos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Como existem infinitas sequ¨eˆncias de s´ımbolos usando os d´ıgitos, existem infinitos axiomas
neste sistema formal. Por exemplo, seriam axiomas 0 + 1, 28 + 344, 7879 + 45453899, etc.
Exemplo 2.4. Estudaremos apenas mais um exemplo de um sistema formal, que chamaremos de
V. Este sistema utiliza o alfabeto { 0, 1, a, b }. Em V, sa˜o fo´rmulas apenas as sequ¨eˆncias que
13
comec¸am com “a” ou com “0”, como “a0”, “0bb1a0a” e “a0aabbb111000”. Na˜o sa˜o fo´rmulas neste
sistema formal as seguintes sequ¨eˆncias: “b00” e “1bab”.
No sistema V, apenas 01 e ab sa˜o axiomas. As regras do sistema V sa˜o dadas abaixo, nas quais
y e´ uma sequ¨eˆncia de s´ımbolos qualquer do alfabeto de V, podendo inclusive ser vazia.
1. se 0y for um teorema, 0ay sera´ um teorema;2. se ay for um teorema, ayy sera´ um teorema.
Quais sa˜o enta˜o os teoremas de V? Comec¸ando pelos axiomas, os teoremas sa˜o:
1. 01 (axioma)
2. ab (axioma)
3. 0a1 (01 com regra 1)
4. 0aa1 (0a1 com regra 1)
5. ...
6. abb (ab com regra 2)
7. abbbb (abb com regra 2)
8. ...
�
Lembre-se das recomendac¸o˜es iniciais desta unidade: um axioma, como definido aqui, na˜o esta´
diretamente relacionado a` definic¸a˜o de “axioma” da Matema´tica. Em particular, na˜o faz sentido
dizer que um axioma e´ verdadeiro. No sistema S, por exemplo, na˜o faz sentido dizer que 0 e 5 sa˜o
verdadeiros ou falsos. O conceito simplesmente na˜o se aplica aqui.
Uma regra sempre toma um ou mais teoremas como entrada e produz um u´nico teorema como
sa´ıda. Mas ainda resta uma u´ltima questa˜o: o que pode ser uma regra? Praticamente qualquer
coisa que tome um ou mais teoremas e produza um teorema. Vamos dar alguns exemplos. Assuma
que os s´ımbolos que aparecem nos itens pertenc¸am ao alfabeto do sistema formal.
1. se x e y sa˜o teoremas, enta˜o xy e´ teorema (concatenac¸a˜o de x com y, como usual).
2. se x−→y e x sa˜o teoremas, enta˜o y e´ teorema.
3. se ¬A ∨B e A ∨ C sa˜o teoremas, enta˜o B ∨ C sa˜o teoremas;
4. se x e´ teorema e possui um nu´mero par de s´ımbolos, enta˜o 00x11 e´ teorema.
5. se A e´ teorema, enta˜o ∀x(A) e´ teorema.
6. se 0x1 e 000y sa˜o teoremas, enta˜o 1x2y e´ teorema.
14
7. ...
E o que na˜o pode ser uma regra? Vamos dar alguns exemplos:
1. se x e´ teorema e o nu´mero de estrelas no universo for par, enta˜o 0x1 e´ teorema. Na˜o sabemos
nem se o universo e´ finito, quanto mais se o nu´mero de estrelas e´ par ou na˜o;
2. se x e y sa˜o teoremas e se for chover em Paris no dia 30 de julho de 2500, enta˜o xy e´ teorema.
Sem comenta´rios.
Pode-se fazer “regras” na˜o va´lidas utilizando conhecimentos mais avanc¸ados de computac¸a˜o, o
que na˜o podemos mostrar aqui. Finalizando, a definic¸a˜o de regra va´lida e´: se voceˆ pode fazer um
programa de computador que implemente a regra, enta˜o a regra e´ va´lida.
2.4 Visa˜o Alternativa
Um sistema formal pode ser comparado a um conjunto de pec¸as de pla´stico com regras de como
combina´-las (brinquedos do tipo Lego). As pec¸as possuem salieˆncias e depresso˜es para se en-
caixarem umas nas outras. Duas pec¸as quaisquer na˜o necessariamente podem ser agrupadas, pois
elas podem na˜o se encaixar. As regras do sistema formal estariam subentendidas nas salieˆncias
e depresso˜es nas pec¸as. O alfabeto seriam as pro´prias pec¸as, cada pec¸a seria um axioma e um
teorema e´ qualquer agrupamento de pec¸as.
Um sistema formal nada mais e´ do que um jogo de compor pec¸as segundo regras. E observe
que, nestes brinquedos, os s´ımbolos do alfabeto (pec¸as) e os teoremas possuem treˆs dimenso˜es.
2.5 Conexo˜es com a Computac¸a˜o
2.5.1 Regras Como Algoritmos
Uma conexa˜o com a computac¸a˜o foi dada na definic¸a˜o de uma “regra” de um sistema formal. Uma
regra deve poder ser transformada em um algoritmo. E o que e´ exatamente um algoritmo? E´ uma
sequ¨eˆncia de instruc¸o˜es que pode ser colocada em um programa escrito em qualquer linguagem de
programac¸a˜o.2
Como um exemplo, a regra que conecta dois teoremas x e y para criar o teorema xy pode ser
codificada em linguagem Java como
String regra(String f1, String f2) {
return f1 + f2; // + aqui e´ a concatenac¸~ao de strings
}
2Rigorosamente, admite-se que o programa possa alocar uma quantidade potencialmente infinita de memo´ria, o
que na˜o e´ o caso real, ja´ que todos os computadores possuem uma memo´ria finita.
15
2.5.2 Programas Como Sistemas Formais
Podemos encontrar um sistema formal que faz a mesma coisa que um programa qualquer? Apare-
mentemente sim, pois afinal um programa e´ composto de algoritmos e as regras so sistema formal
tambe´m. Veremos que a resposta e´ “sim”. Um programa toma uma entrada, altera-a atrave´s de
sucessivas instruc¸o˜es e no final de sua execuc¸a˜o produz uma sa´ıda.3 Enta˜o um programa qualquer
toma uma sequ¨eˆncia de bits como entrada e produz uma sequ¨eˆncia de bits como sa´ıda feita atrave´s
de sucessivas modificac¸o˜es da entrada. Veremos enta˜o com converter um programa P qualquer em
um sistema formal.
A entrada do programa P corresponde ao u´nico axioma do sistema formal. Enta˜o para cada
combinac¸a˜o P/entrada temos um sistema formal diferente. As regras correspondem a`s alterac¸o˜es
feitas na entrada, pelo programa, atrave´s de suas instruc¸o˜es, ate´ se obter uma sa´ıda. A sa´ıda seria
um teorema do sistema formal. Pode-se assumir que um teorema e´ uma sa´ıda quando tiver um
s´ımbolo especial como u´ltimo cara´ter. Em um caso extremo, ter´ıamos uma u´nica regra que seria
aplicada uma u´nica vez. A regra toma o axioma, que corresponde a` entrada, e produz um teorema,
que corresponde a` sa´ıda. E fim.
Contudo, e´ mais dida´tico imaginarmos que a cada instruc¸a˜o do programa, seja ele feito em
uma linguagem de alto n´ıvel ou em assembler, corresponde a uma regra do sistema formal. Como
exemplo, estudaremos um sistema formal (incompleto !) equivalente a um programa que soma
uma sequ¨eˆncia de nu´meros. O axioma poderia ser a sequ¨eˆncia
100111− 10101− 11111− 1− 10
indicando que queremos calcular 100111 + 10101 + 11111 + 1 + 10.
As regras manipulam os bits de tal forma que o teorema final seja
1011110#
que e´ a soma dos nu´meros presentes no axioma. O # indicaria que nenhuma regra deveria ser
aplicada deste ponto em diante.
O que aconteceu foi que colocamos os nu´meros de entrada, 100111, 10101, 11111, 1 e 10 no
axioma em um formato apropriado, separados por −. Note que o alfabeto deste sistema formal
e´ {0, 1,−,#}. Depois de aplicar as regras do sistema va´rias vezes, obtemos um teorema (que
e´ sempre terminado por # por nossa convenc¸a˜o). As regras produzem uma sequ¨eˆncia de bits
que e´ exatamente a somato´ria dos nu´meros iniciais. Observe que temos que passar a entrada
para o formato esperado pelo sistema formal e interpretar a sa´ıda de acordo com a convenc¸a˜o
que utilizamos. Note que as regras nada sabem sobre esta nossa convenc¸a˜o — regras fazem
manipulac¸o˜es mecaˆnicas de s´ımbolos sem conhecer a semaˆntica deles. Naturalmente, as regras na˜o
violam o significado da nossa convenc¸a˜o, elas de alguma forma sa˜o coerentes com o que queremos
do programa.
E quanto a`s regras deste sistema formal, com seriam elas? Tudo o que podemos dizer e´ que
seriam um tanto complexas para serem colocadas aqui, mas que existem. Para compreender isto,
basta dizer que elas seriam equivalente a`s instruc¸o˜es do assembler de um computador como mov,
add, xor, etc.4
3Na˜o precisamos considerar os programas interativos que tomam entradas e produzem sa´ıdas durante a sua
execuc¸a˜o — simplesmente podemos considerar que estes programas comec¸am uma nova execuc¸a˜o apo´s uma nova
entrada e terminam a sua execuc¸a˜o apo´s uma sa´ıda.
4A primeira regra seria aplicada se a sequ¨eˆncia na˜o comec¸asse com #. A partir da´ı as regras iriam numerando
as sequ¨eˆncias ate´ que se chegue ao teorema final, que termina com #. Para exemplificar, se o axioma e´ 101 − 11,
16
Figura 2.2: Treˆs gerac¸o˜es de um autoˆmato celular
2.5.3 Autoˆmato Celular e Jogo da Vida
Existe uma aplicac¸a˜o direta, simples e interessante de sistemas formais em computac¸a˜o ? Sim,
existe, e se chama Jogo da Vida. O jogo da vida e´ um autoˆmato celular que pode (deve !) ser
implementado por um programa e que mostra o nascimento e morte de ce´lulas (quadradinhos) a
cada vez que suas regras sa˜o aplicadas. O jogo da vida, apesar do nome, na˜o e´ um jogo, e´ um
sistema formal cuja observac¸a˜o nos e´ muito u´til para a compreensa˜o dos sistemas formais.
Um autoˆmato celular [11] consiste de um conjunto quadriculado de ce´lulas infinito, cada uma
das quais podendo estar em um conjunto finito de estados, representados por cores. O quadriculadopode ter qualquer nu´mero finito de dimenso˜es, embora utilizaremos duas dimenso˜es nesta Unidade.
Enta˜o o autoˆmato pode ser representado no plano. A Figura 2.2 mostra treˆs autoˆmatos celulares
de duas dimenso˜es onde cada ce´lula pode estar em um de dois estados: branco ou preto. Um
autoˆmato celular se modifica em intervalos discretos de tempo. A cada passo, intervalo discreto,
novos valores de estado sa˜o calculados para cada ce´lula baseado em um nu´mero finito de ce´lulas
vizinhas. A ce´lula assume este novo estado no pro´ximo passo, tambe´m chamado de pro´xima
gerac¸a˜o. Por exemplo, o valor de uma ce´lula pode ser calculado considerando-se os estados das
duas ce´lulas verticais e duas ce´lulas horizontais adjacentes a ela. Se o autoˆmato tem n estados,
haveria n4 diferentes possibilidades de ca´lculo para cada ce´lula. Cada ce´lula utiliza a mesma func¸a˜o
de ca´lculo, independentemente de onde ela estiver. Esta func¸a˜o de ca´lculo sera´ chamada de “regra”
para ca´lculo do estado da ce´lula.
A Figura 2.2 mostra um autoˆmato onde a func¸a˜o que calcula o pro´ximo estado de uma ce´lula
considera todos os vizinhos imediatos da ce´lula: duas ce´lulas horizontais, duas verticais e quatro
diagonais. A func¸a˜o retorna o estado preto se o nu´mero de ce´lulas vizinhas pretas (sem contar
com a pro´pria ce´lula) for ı´mpar. Caso contra´rio retorna o estado branco. A Figura mostra treˆs
gerac¸o˜es de um autoˆmato. O leitor e´ convidado a conferir a mudanc¸a de cores das ce´lulas desta
Figura.
O jogo da vida [4] e´ um autoˆmato celular inventado por John Conway na de´cada de 60. O
autoˆmato utiliza dois estados, branco e preto. O jogo da vida pode utilizar regras quaisquer para
passar de uma gerac¸a˜o para outra. Citamos abaixo as regras originais de Conway. Estas regras
ensinam como calcular a cor de uma ce´lula baseada nas cores das ce´lulas adjacentes da gerac¸a˜o
anterior. Cada ce´lula possui oito vizinhos: dois horizontais, dois verticais e quatro diagonais.
a sequ¨eˆncia de teoremas poderia ser #0#101 − 11, #1#..., #2#..., ..., 1000#. O nu´mero no in´ıcio da sequ¨eˆncia
funciona com o contador de programa (PC) ou estado de uma ma´quina de estados finitos. Note que as regras podem
utilizar a sequ¨eˆncia sendo transformada para armazenar nu´meros intermedia´rios — seria a memo´ria do computador.
17
Figura 2.3: Quatro gerac¸o˜es de um jogo da vida
Regras:
• uma ce´lula preta com dois ou treˆs vizinhos pretos sobrevive para a pro´xima gerac¸a˜o; isto e´,
continua preta;
• uma ce´lula preta com um vizinho preto ou nenhum e´ substitu´ıda por uma ce´lula branca
(vazia). E´ como se a ce´lula morresse por solida˜o;
• uma ce´lula preta com quatro ou mais vizinhos pretos e´ substitu´ıda por uma ce´lula branca.
E´ como se a ce´lula morresse por superpopulac¸a˜o;
• uma ce´lula branca que possui exatamente treˆs ce´lulas vizinhas pretas e´ substitu´ıda por uma
ce´lula preta na pro´xima gerac¸a˜o.
A Figura 2.3 representa quatro gerac¸o˜es de um jogo, indicadas por g1, g2, g3 e g4. O leitor e´
convidado a aplicar as regras acima em uma gerac¸a˜o para conseguir chegar a` pro´xima. Cada regra
deve ser aplicada baseada na gerac¸a˜o anterior, na˜o na gerac¸a˜o que voceˆ esta´ montando atualmente.
Veremos como a gerac¸a˜o 2 foi constru´ıda a partir da 1. Por convenieˆncia, numeramos as ce´lulas.
As ce´lulas 10 e 12 de g1, brancas, sa˜o adjacentes a treˆs ce´lulas pretas. Estas ce´lulas ficam pretas na
gerac¸a˜o 2 — confira em g2. Em g1, a ce´lula preta 18 e´ adjacente a cinco ce´lulas pretas. Esta ce´lula
torna-se branca na gerac¸a˜o 2. As regras na˜o se aplicam a nenhuma outra ce´lula e terminamos a
sua aplicac¸a˜o, obtendo g2.
Para obter g3, note que as u´nicas ce´lulas que sera˜o modificadas sa˜o 4, 11, 16 e 20. A 4 se torna
preta, pois tem treˆs vizinhas pretas em g2. A ce´lula 11 tem quatro vizinhos pretos em g2 e enta˜o
fica branca em g4. Tanto 16 quanto 20 sa˜o brancas e teˆm treˆs vizinhos pretos em g2 e, portanto,
ficam pretas em g3.
O jogo da vida e´ um jogo fascinante, interessante, embora extremamente simples. Chamando a
configurac¸a˜o de ce´lulas brancas e pretas de “padra˜o”, ha´ padro˜es que, depois de um certo nu´mero
de gerac¸o˜es:
• se repetem, entrando enta˜o em um lac¸o infinito. A configurac¸a˜o pode ficar enorme e depois
diminuir ate´ conter apenas poucas ce´lulas pretas;
• atingem um estado esta´vel, na˜o mais se modificando. Como um exemplo, um quadrado
formado por quatro ce´lulas pretas, isoladas de quaisquer outras ce´lulas, nunca se modifica;
18
• se tornam sime´tricos, apesar do padra˜o iniciar na˜o o ser.
Ha´ ainda padro˜es que “se movem” atrave´s do quadriculado, que criam e disparam padro˜es que
se movem (como um canha˜o que atira um proje´til) e outros que crescem sem parar. O leitor e´
convidado a pesquisar na Internet e experimentar com as dezenas de implementac¸o˜es do jogo da
vida dispon´ıveis na world wide web.
2.5.4 Grama´ticas Como Sistemas Formais
Uma grama´tica G e´ uma qua´drupla (N, Σ, P, S) onde
• N e´ o conjunto de s´ımbolos na˜o-terminais;
• Σ e´ o conjunto de s´ımbolos terminais;
• P e´ um conjunto de produc¸o˜es;
• S e´ o s´ımbolo na˜o-terminal inicial da grama´tica.
Como um exemplo, considere uma grama´tica G que expressa algumas expresso˜es aritme´ticas
va´lidas. O conjunto N = { E, T, N }, Σ = { 0, 1, 2, . . . 9 }, S e´ o s´ımbolo E e o conjunto P e´
composto pelas “regras de produc¸a˜o” dadas a seguir:
1. E ::= E + T
2. E ::= T
3. T ::= T ∗ N
4. T ::= N
5. N ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 7 | 8 | 9
O s´ımbolo | na˜o faz parte da grama´tica, sendo utilizado apenas para significar “ou”. Assim,
na regra 5 acima, N e´ 0 ou 1 ou ... 9. Pode-se eliminar o s´ımbolo | escrevendo-se dez regras para
N:
N ::= 0
N ::= 1
. . .
N ::= 9
A grama´tica G e´ utilizada para produzir sequ¨eˆncias de s´ımbolos partindo-se do s´ımbolo inicial
E e substituindo-se E por E + T ou T de acordo com a primeira “regra de produc¸a˜o” dada acima.
A partir da´ı, pode-se substituir qualquer dos s´ımbolos na˜o terminais, do conjunto N, pelo lado
direito de “::=” de qualquer regra de produc¸a˜o. Por exemplo, pode-se substituir T por T ∗ N ou
N. Uma sequ¨eˆncia de substituic¸o˜es e´ chamada de derivac¸a˜o. Como exemplo, apresentamos uma
derivac¸a˜o de E onde cada passo e´ seguido do s´ımbolo =⇒ .
E =⇒ E + T =⇒ T + T =⇒ N + T =⇒ 1 + T =⇒ 1 + N =⇒ 1 + 2
No primeiro passo utilizamos a regra 1, no segundo a regra 2 e no terceiro a regra 4.
19
A cada grama´tica G pode-se associar um sistema formal SFG tal que alguns dos teoremas deste
sistema correspondem a`s sentenc¸as que podem ser produzidas pela grama´tica. SFG utiliza um
alfabeto contendo os s´ımbolos terminais e na˜o terminais de G. O u´nico axioma e´ o s´ımbolo inicial
da grama´tica. As regras de deduc¸a˜o de SFG sa˜o baseados nas regras de produc¸a˜o da grama´tica.
Uma regra de produc¸a˜o
A ::= α
resulta em uma regra
em um teorema qualquer, A pode ser substitu´ıdo por α
do sistema formal.
Na grama´tica dada acima, o sistema formal teria como alfabeto o conjunto { E, T , N , +, ∗,
0, 1, ... 9 }. O axioma seria o s´ımbolo E e as regras de deduc¸a˜o seriam:
1. Em um teorema qualquer, E pode ser substitu´ıdo por E + T ou T ;
2. Em um teorema qualquer, T pode ser substitu´ıdo por T ∗N ou N ;
3. Em um teorema qualquer, N pode ser substitu´ıdo por 0 ou 1 ou ... ou 9.
Faremos alguns exemplos de deduc¸a˜o de teoremas neste sistema formal:
(a) 1. E
2. E + T
3. T + T
4. N + T
5. N +N
6. 0 +N
7. 0 + 1
(b) 1. E
2. E + T
3. E + T ∗N
4. E + T ∗ 3
5. E +N ∗ 3
6. E + 5 ∗ 3
7. T + 5 ∗ 3
8. N + 5 ∗ 3
9. 7 + 5 ∗ 3
(c) 1. E
2. T
3. N
4. 2
20
Figura 2.4: Numerac¸a˜o de s´ımbolos em um sistema formal em duas dimenso˜es
Um teorema em que na˜o ocorre nenhum s´ımbolo na˜o terminal e´ chamado de sentenc¸a da
grama´tica.Assim, sa˜o sentenc¸as desta grama´tica os teoremas 0 + 1, 7 + 5 ∗ 3 e 2. Qualquer
linguagem de programac¸a˜o pode ser descrita por uma grama´tica e os programas va´lidos podem
ser gerados por um sistema formal como descrito acima.5
2.5.5 Suposic¸o˜es Impl´ıcitas
Ao apresentar um sistema formal, admitimos que o alfabeto deve ser apresentado em uma u´nica
dimensa˜o, uma linha. Poder´ıamos ter um sistema formal (SF) que utiliza duas dimenso˜es? Clara-
mente, sim. Mas este SF poderia ser mais poderoso do que qualquer SF convencional, unidimen-
sional? Isto e´, haveria um SF em duas dimenso˜es que jamais poderia ser simulado em uma u´nica
dimensa˜o?
Na˜o, qualquer sistema formal de duas dimenso˜es poderia ser simulado em uma u´nica dimensa˜o.
Para mostrar como, observe a figura 2.3. Um conjunto de s´ımbolos colocado neste quadriculado,
de duas dimenso˜es, poderia ser mapeado para uma dimensa˜o seguindo-se os nu´meros em ordem
crescente. Se um axioma fosse os nu´meros da figura (a), em duas dimenso˜es, o axioma correspon-
dente seria, em uma dimensa˜o, igual a 1, 2, 3, 4, 5, 6, 7, 8, . . .. As setas da figura (b) indicam como
seriam mapeados os s´ımbolos. Desta forma, pode-se converter qualquer fo´rmula bidimensional em
uma fo´rmula unidimensional. E mais importante, de maneira biun´ıvoca: a cada fo´rmula bidimen-
sional corresponde a uma u´nica fo´rmula unidimensional e vice-versa. Possivelmente ter´ıamos que
introduzir um s´ımbolo no sistema formal de uma dimensa˜o para representar um quadrado vazio
no sistema formal de duas dimenso˜es. Mas pode ser feito.
E quanto a`s regras? Podemos converter uma regra que manipula fo´rmulas em duas dimenso˜es
para uma regra que manipula fo´rmulas em uma dimensa˜o? Claramente, sim. Existe uma func¸a˜o
que mapeia cada posic¸a˜o do quadriculado em uma posic¸a˜o unidimensional. Utilizando esta func¸a˜o,
o mapeamento entre a regra bidimensional e a regra unidimensional torna-se trivial. Basta aplicar
a func¸a˜o sempre que a regra bidimensional referir-se a` posic¸a˜o um s´ımbolo. E que func¸a˜o e´ esta?
Se ela se chama f e adotarmos que a posic¸a˜o 0 do exemplo (a) e´ (0, 0), enta˜o ter´ıamos f(0, 0) = 0,
f(1, 0) = 1, f(1, −1) = 2, f(0, −1) = 3, etc. Fazer esta func¸a˜o fica como exerc´ıcio ao leitor.
Observe que racioc´ınio acima pode ser generalizado para treˆs ou mais dimenso˜es.
5O sistema formal certamente produzira´ alguns teoremas que na˜o correspondem a programas va´lidos, que neste
caso seriam programas sintaticamente corretos mas com erros semaˆnticos (utilizando a terminologia de Compi-
ladores).
21
Uma outra suposic¸a˜o impl´ıcita na apresentac¸a˜o dos sistemas formais foi a de que existe uma
quantidade finita de s´ımbolos do alfabeto. Esta suposic¸a˜o e´ necessa´ria pois pode-se provar que
nenhuma regra consegue manipular uma quantidade infinita de s´ımbolos. Afinal, as regras podem
ser implementadas em um computador e nenhum computador consegue manipular uma quantidade
infinita de informac¸a˜o. Contudo, poder-se-ia criar um sistema em que o alfabeto contivesse uma
quantidade na˜o enumera´vel de s´ımbolos. Como exemplo, o alfabeto poderia ser os nu´meros reais.
Mas este sistema na˜o seria um “sistema formal” como o conhecemos.
Na˜o seria poss´ıvel um sistema formal onde a criac¸a˜o de teoremas fosse feita de maneira cont´ınua?
Como definido neste Cap´ıtulo, um teorema e´ obtido depois de n passos, n inteiro. E se n pudesse
ser um nu´mero real? Uma regra deveria tomar na˜o so´ as premissas como paraˆmetros como tambe´m
n real. Haveria um cont´ınuo entre os axiomas e teoremas. Aparentemente, nada de novo poderia
ser ganho com esta ide´ia.
Um axioma e´ um conjunto bem definido de s´ımbolos. Esta e´ uma suposic¸a˜o impl´ıcita na
definic¸a˜o de sistema formal. Poderia ser diferente. Um axioma X poderia ser definido como todas
as fo´rmulas B tal que a distaˆncia entre A e B fosse menor do que 1, onde A e´ uma fo´rmula fixada.
A distaˆncia entre duas fo´rmulas poderia ser definida por um algoritmo. Enta˜o o axioma X seria
composto por todas as fo´rmulas cuja distaˆncia de A e´ menor do que 1. Um axioma e´ agora uma
nuvem de fo´rmulas, na˜o apenas uma.
2.6 Considerac¸o˜es Finais
Sistemas formais sa˜o uma forma de produzir novas sequ¨eˆncias de s´ımbolos a partir de regras e
s´ımbolos iniciais. Informalmente, podemos dizer que eles sera˜o usados em lo´gica para, a partir de
verdades, produzir outras verdades. Os axiomas da nossa lo´gica sera˜o as “verdades” e as regras
de infereˆncia sera˜o as regras da lo´gica, como “se A e B sa˜o verdades, enta˜o A e´ verdade” ou “Se
todos os peixes sa˜o vermelhos, enta˜o existe um peixe que e´ vermelho”. A primeira frase e´ o´bvia e
por isso pode ser dif´ıcil de entendeˆ-la.
2.7 Exerc´ıcios
2.1. Explique o que e´ um sistema formal, axioma, regra de deduc¸a˜o, teorema e meta-teorema.
2.2. Fac¸a um sistema formal que utilize um alfabeto de pelo menos dez s´ımbolos, tenha pelo menos
cinco axiomas e pelo menos treˆs regras de deduc¸a˜o.
2.3. Fac¸a um sistema formal produza os mesmos teoremas que o sistema S.
2.4. Explique o funcionamento de um autoˆmato celular. As regras podem ser modificadas ou
obrigatoriamente devem ser como definidas no texto?
2.5. Fac¸a configurac¸o˜es (que ce´lulas sa˜o pretas?) para o jogo da vida de tal forma que as cores
das ce´lulas nunca mudem.
2.6. Fac¸a um sistema formal que utilize os d´ıgitos como alfabeto e que produza como teoremas
sequ¨eˆncias de s´ımbolos s tal que s, quando interpretado como um nu´mero, seja divis´ıvel por 2.
22
Assim, seriam teoremas {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, . . .}. Fac¸a um meta-teorema para este
sistema formal.
2.7. Fac¸a um sistema formal produza os mesmos teoremas que o sistema S e que utilize um
esquema de axioma.
2.8. Seja S o sistema formal que utiliza o alfabeto { E, T , N , +, ∗, 0, 1, ... 9 }. O u´nico axioma
e´ E e qualquer sequ¨eˆncia de s´ımbolos e´ uma fo´rmula. As regras de deduc¸a˜o sa˜o:
1. Em um teorema qualquer, E pode ser substitu´ıdo por E + T ou T ;
2. Em um teorema qualquer, T pode ser substitu´ıdo por T ∗N ou N ;
3. Em um teorema qualquer, N pode ser substitu´ıdo por 0 ou 1 ou ... ou 9.
Escreva alguns teoremas deste sistema formal. Alguns teoremas nunca podera˜o ser utilizados
para a construc¸a˜o de outros teoremas, pois eles na˜o possuem as letras E, T ou N . Com o que se
parecem estes teoremas?
2.9. Fac¸a configurac¸o˜es (que ce´lulas sa˜o pretas?) para o jogo da vida de tal forma que as ce´lulas
pretas desaparec¸am:
(a) em uma u´nica gerac¸a˜o;
(b) em duas gerac¸o˜es;
(c) em treˆs gerac¸o˜es.
23
Unidade 3
Introduc¸a˜o ao Ca´lculo Proposicional
3.1 Primeiras palavras
Considere os seguintes fatos, considerados verdadeiros.
1. Joa˜o gosta de pizza ou gosta de futebol;
2. Se Joa˜o na˜o gosta de Maria, enta˜o Joa˜o na˜o gosta de pizza ;
3. Joa˜o na˜o gosta de futebol e Joa˜o na˜o mora em Sa˜o Paulo.
Pergunta-se: Joa˜o gosta da Maria? Usamos a palavra “ou” para indicar o “ou” na˜o exclusivo. Isto
e´, em “A ou B” podemos ter ambos verdadeiros.
Pode-se resolver esta questa˜o sem utilizar nenhuma te´cnica e nenhuma lo´gica formal. Contudo,
o objetivo desta disciplina e´ formalizar este tipo de questa˜o e formalizar te´cnicas para resolveˆ-
las. Em primeiro lugar, temos que converter estas frases para fo´rmulas que sejam mais facilmente
manipula´veis do que frases. Mas antes de fazer isto, temos que definir que linguagem utilizaremos.
E´ esta linguagem que este Cap´ıtulo define.
3.2 A Linguagem do Ca´lculo Proposicional
Uma lo´gica possui uma parte composta por axiomas, teoremas, provas e regras como definido na
Unidade 2. Esta parte e´ chamada de sintaxe, pois se interessa apenas pela forma dos axiomas e
teoremas, sem se importar com o que eles significam. Um teorema e´ apenas uma sequ¨eˆncia de
s´ımbolos que na˜o significam nada para o estudo sinta´ticoda lo´gica. Quando associamos significado
aos s´ımbolos, os teoremas passam a significar alguma coisa. Esse aspecto de uma lo´gica e´ chamada
de semaˆntica.
O Ca´lculo Proposicional (CP) e´ uma lo´gica bem simples que sera´ incorporada a` Lo´gica de
Primeira Ordem, a ser vista em Unidades futuras. O CP e´ um sistema formal (pois e´ uma lo´gica)
cuja linguagem usa o alfabeto composto por: ¬, ∨, (, ) e as letras Vi com inteiros positivos como
subscritos: V1, V2, ... Os s´ımbolos ¬ e ∨ sa˜o chamados de conectivos primitivos e as letras Vi sa˜o as
24
varia´veis. O s´ımbolo ¬ leˆ-se “negac¸a˜o” ou “na˜o e´ verdade que”. O s´ımbolo ∨ e´ chamado de “ou”.
Na˜o se confunda: estes conectivos possuem estes nomes mas sa˜o ta˜o somente s´ımbolos no papel
sem qualquer significado. Enta˜o “¬A” leˆ-se “na˜o A” mas no estudo sinta´tico isto na˜o significa que
estamos afirmando que A seja falsa. Sa˜o apenas dois s´ımbolos, ¬ e A, lado a lado.
As fo´rmulas do ca´lculo proposicional sa˜o definidas como
(a) uma varia´vel e´ uma fo´rmula;
(b) ¬A e (A ∨B) sa˜o fo´rmulas se A e B sa˜o fo´rmulas;
(c) fo´rmulas sa˜o descritas apenas pelos itens (a) e (b).
Enta˜o sa˜o fo´rmulas: V1, V5, ¬V2, (V1 ∨ V5), ¬(V14 ∨ V7), ¬¬(V1 ∨ (V2 ∨ V3)) e
(¬(V7 ∨ V1) ∨ (¬V1 ∨ V7)).
Quando um s´ımbolo e´ utilizado para significar uma fo´rmula qualquer, este s´ımbolo e´ chamado
de meta-fo´rmula. Neste livro utilizaremos as letras A, B, C, ... para meta-fo´rmulas a menos de
menc¸a˜o em contra´rio. Enta˜o se tivermos uma fo´rmula A ∨B, esta fo´rmula na verdade representa
infinitas fo´rmulas: tanto A como B podem ser substitu´ıdas por qualquer fo´rmula va´lida do Ca´lculo
Proposicional.
Definiremos agora outros conectivos lo´gicos a partir de ¬ e ∨:
D1 (A ∧B) e´ ¬(¬A ∨ ¬B);
D2 (A−→B) e´ (¬A ∨B);
D3 (A←→B) e´ (A−→B) ∧ (B−→A).
Estes sa˜o chamados de conectivos derivados. Estas definic¸o˜es sa˜o ta˜o somente abreviaturas: uma
fo´rmula V1∧V2, por exemplo, e´ apenas a abreviatura de ¬(¬A1∨¬A2). Os conectivos ∧, −→ e←→
leˆem-se “e”, “implica” e “se e somente se”. O conectivo←→ tambe´m e´ chamado de bicondicional.
Em A−→B, chamamos A de antecedente e B de consequ¨ente.
Para facilitar a escrita e leitura de fo´rmulas, omitiremos os pareˆnteses sempre que na˜o hou-
ver ambigu¨idade. E convencionaremos que os conectivos lo´gicos seguem a seguinte ordem de
precedeˆncia, do maior para o menor: ¬, ∧, ∨, −→ e ←→. Apesar de ∧ ter maior precedeˆncia do
que ∨, usualmente na˜o escreveremos A∧B∨C e sim o mais leg´ıvel (A∧B)∨C. Os conectivos sa˜o
associados a` esquerda: se B estiver entre dois conectivos iguais, B e´ associado com o conectivo da
esquerda. Assim, A−→B−→C e´ o mesmo que (A−→B)−→C.
Com esta convenc¸a˜o, as fo´rmulas podem ser escritas de maneira mais leg´ıvel:
fo´rmula original fo´rmula resumida
(¬A)←→(B ∧ C) ¬A←→B ∧ C
((A−→B)−→C)←→((B ∧ A) ∧D) A−→B−→C←→B ∧ A ∧D
Iremos mostrar como converter o exemplo dado no in´ıcio do Cap´ıtulo para uma fo´rmula do CP.
25
Exemplo 3.1. Associaremos letras a pedac¸os de frases que podem ser verdadeiros ou falsos (em-
bora, por enquanto, na˜o estamos interessados na verdade ou falsidade de fo´rmulas).
1. A e´ “Joa˜o gosta de pizza”
2. B e´ “Joa˜o gosta de futebol”;
3. C e´ “Joa˜o mora em Sa˜o Paulo”;
4. D e´ “Joa˜o gosta de Maria”.
Convertendo as frases para fo´rmulas, temos:
1. (A ∨B) para Joa˜o gosta de pizza ou gosta de futebol;
2. (¬D−→¬A) para Se Joa˜o na˜o gosta de Maria, enta˜o Joa˜o na˜o gosta de pizza;
3. (¬B ∧ ¬C) para Joa˜o na˜o gosta de futebol e Joa˜o na˜o mora em Sa˜o Paulo.
Queremos saber se estas fo´rmulas implicam em D, que significa “Joa˜o gosta de Maria”. A resposta
sera´ vista na Unidade 11.1.
�
3.3 Considerac¸o˜es Finais
A lo´gica precisa de uma linguagem formal para se expressar. Se as fo´rmulas lo´gicas fossem ex-
pressas utilizando a linguagem natural, Portugueˆs no caso, ter´ıamos ambigu¨idades, dificuldades
de entendimento e outros problemas de comunicac¸a˜o que sa˜o da l´ıngua portuguesa, na˜o da lo´gica.
E´ por isso que, para cada lo´gica, define-se uma linguagem formal e define-se exatamente o que e´
permitido nela.
3.4 Exerc´ıcios
3.1. Remova o maior nu´mero poss´ıvel de pareˆnteses das seguintes fo´rmulas
((A ∧B) −→ (¬(B) −→ (B −→ A)) ∧ C
(((A ∧B)−→(¬(B)−→(B−→A))) ∧ C)
(¬A−→(B ∨ C))←→(((A ∧B) ∨ C)←→A)
(A ∧B) ∧ C
(A ∨B)←→(A−→¬B)
3.2. Os conectivos ←→, ∧ e −→ fazem parte da linguagem do CP?
3.3. Joa˜o gosta de Maria?
26
3.4. Rigorosamente, e´ A∨B realmente uma fo´rmula do CP? Explique o que e´ uma meta-fo´rmula.
3.5. Quais sequ¨eˆncias de s´ımbolos abaixo sa˜o fo´rmulas do CP?
(a) ¬¬¬¬A−→A ∧ ¬A
(b) ∨ ∧ ABA
(c) ((A1−→A2) ∨ A1
27
Unidade 4
Semaˆntica do Ca´lculo Proposicional
4.1 Primeiras palavras
O estudo semaˆntico de uma lo´gica e´ o estudo do significado que podemos dar a`s fo´rmulas da
linguagem. No ca´lculo proposicional, associaremos o significado esperado a`s fo´rmulas. Isto e´, cada
fo´rmula podera´ ser verdadeira ou falsa de acordo com o valor de suas varia´veis.
4.2 Problematizando o Tema
Como associar um significado a uma fo´rmula como A ∨B ou A ∧B ∧ C? Claramente, a primeira
fo´rmula e´ verdadeira se A ou B e´ verdadeiro. Sera´ esta definic¸a˜o precisa? O que significa o “ou”
da frase “a primeira fo´rmula e´ verdadeira se A ou B e´ verdadeiro”? Sera´ que este “ou” significa
que se ambos A e B forem verdadeiros, a frase e´ falsa? Isto e´, o “ou” e´ exclusivo? Isto e´, A ∨B e´
falso se A e B forem verdadeiros? Para retirar a ambigu¨idade da definic¸a˜o de verdade por meio de
palavras, precisamos de uma definic¸a˜o mais precisa de verdade. E´ isso que esta Unidade apresenta.
Contudo, antes de estudar este to´pico, veremos como fazer a ligac¸a˜o entre o “mundo real” e as
fo´rmulas do CP.
4.3 Mapeamento de Frases para o Ca´lculo Proposicional
Algumas frases escritas em linguagem natural (exemplo: Portugueˆs) podem ser mapeadas na
linguagem do ca´lculo proposicional. Por exemplo, a frase “Se na˜o fizer sol hoje, vai chover” resulta
na fo´rmula “A−→B” na qual A e´ “na˜o vai fazer sol hoje” e B e´ “vai chover”. Se preferir, poderia
ser ¬A−→B, na qual A e´ “vai fazer sol hoje”. Estude as frases seguintes e suas fo´rmulas do CP
correspondentes:
1. Na˜o e´ verdade que, se na˜o fizer sol hoje, vai chover. A fo´rmula correspondente e´ ¬(¬A−→B)
na qual A e´ “vai fazer sol hoje” e B e´ “vai chover”;
28
2. Ele e´ o presidente ou o diretor. A fo´rmula correspondente e´ A ∨ B, na qual A e´ “Ele e´
presidente” e B e´ “Ele e´ diretor”;
3. Se o Joa˜o ou Pedro estivessem aqui, o problema seria resolvido. A fo´rmula correspondente e´
A∨B−→C, A e´ “Joa˜o esta´ aqui”, B e´ “Pedro esta´ aqui”, C e´ “O problema esta´ resolvido”.
Note que, quando lemos a fo´rmula lo´gica, mudamos os tempos verbais para o condicional;
4. Se i < 0, havera´ um erro e uma mensagem de erro sera´ impressa. A fo´rmula correspondente
e´ A−→B ∧ C, A e´ “i < 0”, B e´ “ha´ um erro”, C e´ “uma mensagem de erro e´ impressa”;
5. Se o supervisor vier hoje e souber do problema, ou seremos demitidos ou transferidos. A
fo´rmula correspondente e´ A ∧ B−→C ∨D, A e´ “o supervisor vem hoje”, B e´ “o supervisor
sabe do problema”, C e´ “seremos demitidos”, D e´ “seremos transferidos”;
6. Ele nasceu em Sa˜o Paulo, Minas ou Bahia, A ∨B ∨C, A e´ “Ele nasceu em Sa˜o Paulo”, B e´
“Ele nasceu em Minas”, C e´ “Ele nasceu na Bahia”;
7. o nu´mero sera´ ı´mpar se e somente se o seu quadrado for ı´mpar. A fo´rmula correspondente e´
A←→B onde A e´ “o nu´mero e´ ı´mpar” e B e´ “o quadrado do nu´mero e´ ı´mpar”;
8. Se o nu´mero for ı´mpar, o seu quadrado tambe´m o sera´. Se o quadrado do nu´mero for ı´mpar,
enta˜o o nu´mero sera´ ı´mpar. A fo´rmula correspondente e´ (A−→B) ∧ (B−→A) na qual A e´
“o nu´mero e´ ı´mpar” e B e´ “o quadrado do nu´mero e´ ı´mpar”;
4.4 Verdade e Falsidade
Cada varia´vel que aparece em umafo´rmula pode receber um de dois valores: V ou F. Tanto faz o
nome destes valores, poderia ser 0 e 1, T e F, qualquer coisa. A u´nica exigeˆncia e´ que sejam valores
distintos. Naturalmente, associamos V a verdadeiro e F a falso, o que e´ apenas uma associac¸a˜o
feita em nossas mentes e que na˜o interessa a` teoria.
Associando um valor (V ou F) a cada varia´vel de uma fo´rmula C, podemos calcular o valor da
fo´rmula. Como fazer isto ? Comecemos pelas fo´rmulas ba´sicas:
¬A e´ V se A for F e F se A for V;
A ∨B e´ V se A ou B for V ou se ambos forem V;
Os conectivos derivados possuem o significado esperado:
A ∧B e´ V se A e B forem ambos V;
A−→B e´ F se A for V e B for F, V em todos os outros casos.
A←→B e´ V se A e B forem ambos V ou se forem ambos F.
29
4.5 Tabelas Verdade dos Conectivos Ba´sicos
A descric¸a˜o de como calcular o valor verdade de uma fo´rmula que possui apenas um conectivo,
dada acima, na˜o esta´ boa. Esta descric¸a˜o ainda utiliza o Portugueˆs e na˜o pode ser facilmente
aplicada em uma fo´rmula qualquer. Nesta sec¸a˜o apresentaremos tabelas verdade, que definem
precisamente o valor de verdade de uma fo´rmula. Iniciaremos com as tabelas verdade de fo´rmulas
com apenas um u´nico conectivo.
A tabela verdade da negac¸a˜o e´
A ¬A
V F
F V
Ha´ duas colunas. Na primeira sa˜o colocados os valores verdade que A pode assumir. Natu-
ralmente, A pode ser V ou F. Na segunda coluna, sa˜o colocados os valores verdade da fo´rmula
¬A.
Pela segunda linha da tabela, quando A assume o valor V, mostra que ¬A assume o valor F.
A terceira linha diz que, quando A for F, ¬A sera´ V. Note que ao inve´s de colocarmos A como
varia´vel (V1, V2, ...), no´s a colocamos como fo´rmula. A e´ uma meta-fo´rmula — representa uma
fo´rmula qualquer. Como uma varia´vel e´ uma fo´rmula, tambe´m representa uma varia´vel qualquer.
A tabela verdade do “ou” e´ mostrada abaixo.
A B A ∨B
V V V
V F V
F V V
F F F
Ha´ quatro combinac¸o˜es diferentes para os valores verdade de A e B. Logo a tabela possui
quatro linhas.
Em Portugueˆs, quando se diz “vou almoc¸ar lazanha ou feijoada”, queremos dizer uma coisa
ou outra, mas na˜o as duas ao mesmo tempo (em geral, mas nem sempre!). Em geral, este e´ o
significado do “ou” em Portugueˆs. Contudo, no CP, ∨ quer dizer um ou outro ou ambos. Enta˜o
o significado de ∨ na˜o e´ exatamente o “ou” que conhecemos.
4.6 Conectivos Derivados
O CP utiliza alguns conectivos derivados, que na˜o pertencem a` linguagem, mas que sa˜o empregados
por comodidade. Estes conectivos ja´ foram definidos, mas repetimos aqui a sua definic¸a˜o:
D1 (A ∧B) e´ ¬(¬A ∨ ¬B);
30
D2 (A−→B) e´ (¬A ∨B);
D3 (A←→B) e´ (A−→B) ∧ (B−→A).
As tabelas verdade destes conectivos podem ser obtidas das tabelas do ¬ e −→ e sa˜o dadas
abaixo.
A B A ∧B
V V V
V F F
F V F
F F F
A B A−→B
V V V
V F F
F V V
F F V
A−→B e´ F apenas quando A e´ V e B e´ F. Enta˜o se A e´ F e B e´ V, A−→B e´ V. Mas sera´ que
isto faz sentido em Matema´tica? Afinal, estamos estudando lo´gica Matema´tica ! Para responder
isto, vamos examinar os racioc´ınios va´lidos nesta disciplina. Veja a seguinte deduc¸a˜o, criada por
Smullyan [1]:
5 = 5(subtraia 1)
4 = 4(substitua por algo equivalente)
22 = 22(substitua por algo equivalente)
22 = (−2)2(extraia a raiz)
2 = −2(subtraia 1)
1 = −3
Naturalmente, esta deduc¸a˜o esta´ errada, pois se a2 = b2, na˜o podemos deduzir que a = b. Mas
e a deduc¸a˜o “Se 1 = −3 enta˜o 5 = 5”? Refac¸a os passos ao contra´rio e na˜o encontrara´ nenhum
erro. A Matema´tica admite que se A e´ falso e B e´ verdadeiro, enta˜o A−→B e´ verdadeiro.
Um outro exemplo, citado por Mendelson [8], e´ a frase “se x e´ um inteiro ı´mpar, enta˜o x2 e´
um inteiro ı´mpar”. Esta frase e´ verdadeira em Matema´tica. Se x for par, queremos que a frase
inteira seja considerada falsa? Claramente na˜o. Considerando A como “x e´ um inteiro ı´mpar” e
B como “x2 e´ um inteiro ı´mpar”, enta˜o se x for par teremos um caso no qual A e´ F e queremos
que A−→B seja V. E´ por causa de racioc´ınios como estes, da Matema´tica, que a tabela verdade
de −→ considera A−→B verdadeiro sempre que A e´ F.
Em l´ıngua natural, sempre se exige alguma conexa˜o causal entre A e B quando se emprega
a sentenc¸a A−→B. Em Lo´gica Matema´tica, sendo uma disciplina formal, que nada conhece do
mundo f´ısico, na˜o se exige nenhuma conexa˜o entre o antecedente A e o consequ¨ente B. Enta˜o, as
sentenc¸as abaixo sa˜o verdadeiras na lo´gica que estudamos:
31
1. se 12 e´ primo, enta˜o o Sol na˜o existe;
2. se 6 e´ primo, hoje e´ quarta-feira.
Note que na u´ltima sentenc¸a, “hoje e´ quarta-feira” assume V ou F dependendo do dia em que a
frase e´ lida. Na˜o interessa se ela e´ V ou F. A sentenc¸a toda e´ verdadeira de qualquer forma.
A B A←→B
V V V
V F F
F V F
F F V
O operador bicondicional, representado por ←→, indica que duas sentenc¸as sa˜o logicamente
equivalentes: A←→B e´ V se e somente se A e´ V quando B e´ V e A e´ F quando B e´ F.
4.7 Considerac¸o˜es Finais
As tabelas verdade dos conectivos ba´sicos define precisamente como calcular os valores verdade
das fo´rmulas ¬A e A ∨ B dados os valores de A e B. Estas tabelas verdade sa˜o como tabuadas e
sera˜o empregadas futuramente para calcular o valor verdade de fo´rmulas mais complexas.
No in´ıcio desta sec¸a˜o, mapeamos frases em Portugueˆs para fo´rmulas do CP. Contudo, isto foi
feito apenas para introduzir os conceitos, facilitar o aprendizado. O CP na˜o se aplica ao mundo
real. Esta lo´gica foi feita para a Matema´tica e a´ı ela funciona perfeitamente. Em particular, se
A−→B e´ verdade, isto na˜o quer dizer que A “causa” B. Dizemos A “implica” B, mas a palavra
implica aqui na˜o tem o significado usual da palavra implica em Portugueˆs.
4.8 Exerc´ıcios
4.1. Fac¸a as tabelas verdade de todos os conectivos ba´sicos e derivados.
4.2. Podemos afirmar que, na Matema´tica, (7 < 1)−→(0 = 0)? E (7 < 1)−→(0 = 1)? Se sim,
fac¸a uma prova informal destes dois “teoremas”.
4.3. Converta as frases seguintes para fo´rmulas do ca´lculo proposicional. Escreva o que cada
varia´vel da fo´rmula significa.
(a) Este celular e´ um computador, caˆmera e um mp3 player ao mesmo tempo.
(b) Se o prec¸o do carro estiver bom, levaremos dois.
(c) Uma de duas coisas acontecera´: se ele for bom, resolvera´ o problema. E se ele na˜o for bom,
contratara´ algue´m para resolveˆ-lo.
(d) Ele e´ chato mas inteligente.
32
(e) Ele e´ engenheiro ou analista de sistemas. E e´ competente.
(f) O nu´mero e´ maior do que zero, ı´mpar, mas na˜o e´ primo.
(g) Se o nu´mero e´ primo, ele na˜o e´ divis´ıvel por quatro mas pode ser divis´ıvel por 3 e pode ser
divis´ıvel por 2.
(h) Uma figura de quatro lados e´ um quadrado se todos os lados sa˜o do mesmo tamanho e todos
os aˆngulos entre os lados sa˜o iguais.
4.4. A sentenc¸a “Se a terra e´ quadrada enta˜o o mar e´ lila´s ou o ce´u e´ verde” e´ verdadeira na lo´gica
que estudamos ? Isto quer dizer que o mar e´ lila´s ? Ou que o ce´u e´ verde ?
33
Unidade 5
Tabelas Verdade e Tautologias
5.1 Primeiras palavras
Esta unidade ensina como montar tabelas verdade para fo´rmulas que envolvem qualquer nu´mero
de conectivos. Ao final desta unidade voceˆ sera´ capaz de montar a tabela verdade de fo´rmulas
como A ∧B−→(¬C ∨ A ∨ ¬B). Definimos tambe´m o que sa˜o tautologias e como identifica´-las.
5.2 Problematizando o Tema
Na Unidade anterior, aprendemos como fazer tabelas verdade para fo´rmulas com um u´nico conec-
tivo ba´sico. Sera´ poss´ıvel estender este me´todo para fo´rmulas com dois ou mais conectivos, como
(¬A ∧B)−→A? Veremos que sim.
Sera´ que alguma fo´rmula da lo´gica sera´ sempre verdadeira independente dos valores de suas
varia´veis? Isto e´, podemos ter uma fo´rmula como A ∧ B−→(¬C ∨ A ∨ ¬B) que sera´ verdade
independente dos valores verdade que associemos a A, B, C e D? Ou sera´ isso