Fundamentos da Matemática para Computação

Prévia do material em texto

Sumário
Aula 1: Linguagem da Lógica de Predicados 15
1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 16
1.2 Linguagens . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Aspectos das Linguagens . . . . . . . . . . . . . . . 16
1.4 Linguagem da Lógica de Predicados . . . . . . . . 18
1.4.1 Sintaxe da Linguagem da Lógica de Predicados 19
1.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 24
1.6 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 24
1.7 Atividades . . . . . . . . . . . . . . . . . . . . . . . 25
1.8 Referências Bibliográficas . . . . . . . . . . . . . . 26
Aula 2: Conectivos e Quantificadores Lógicos 27
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Semântica da Linguagem da Lógica de Predicados . 28
2.3 Quantificadores . . . . . . . . . . . . . . . . . . . . 34
2.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 35
2.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6 Atividades . . . . . . . . . . . . . . . . . . . . . . . 36
2.7 Referências Bibliográficas . . . . . . . . . . . . . . 36
Aula 3: Valorações e Tabelas de Verdade 39
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 Valorações . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Álgebra de Boole . . . . . . . . . . . . . . . . . . . 41
3.4 Tabela de Verdade . . . . . . . . . . . . . . . . . . 42
3.4.1 Uso de Parêntese e Prioridade dos Conec-
tivos Lógicos . . . . . . . . . . . . . . . . . 44
3.5 Tautologia, Contradição e Contingência . . . . . . 46
3.6 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 48
3.7 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 48
3.8 Atividades . . . . . . . . . . . . . . . . . . . . . . . 50
3.9 Referências Bibliográficas . . . . . . . . . . . . . . 51
Aula 4: Regras de Inferência e Regras de Equivalência 53
4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 Regras de Equivalência . . . . . . . . . . . . . . . . 54
4.3 Subconjuntos Completos de Conectivos . . . . . . . 58
4.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 61
4.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 61
4.6 Atividades . . . . . . . . . . . . . . . . . . . . . . . 63
4.7 Referências Bibliográficas . . . . . . . . . . . . . . 63
Aula 5: Teorias Axiomáticas 65
5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 66
5.2 Sistemas Axiomáticos . . . . . . . . . . . . . . . . 66
5.2.1 Exemplos de Alguns Sistemas Axiomáticos . 68
5.3 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 72
5.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 72
5.5 Atividades . . . . . . . . . . . . . . . . . . . . . . . 73
5.6 Referências Bibliográficas . . . . . . . . . . . . . . 74
Aula 6: Teoria da Demonstração 75
6.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 76
6.2 Teoria da Demonstração . . . . . . . . . . . . . . . 76
6.3 Tipos de Demonstração . . . . . . . . . . . . . . . 78
6.3.1 Demonstração Direta . . . . . . . . . . . . . 78
6.3.2 Demonstração Indireta Contrapositiva . . . 79
6.3.3 Demonstração Indireta por Redução ao Ab-
surdo . . . . . . . . . . . . . . . . . . . . . 79
6.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 81
6.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 82
6.6 Atividades . . . . . . . . . . . . . . . . . . . . . . . 83
6.7 Referências Bibliográficas . . . . . . . . . . . . . . 84
Aula 7: Teoria de Cantor e Teoria de Zermelo -Fraenkel 85
7.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 86
7.2 Teoria dos Conjuntos de Georg Cantor . . . . . . . 86
7.2.1 Conceito de Conjunto . . . . . . . . . . . . 87
7.2.2 Linguagem da Teoria dos Conjuntos . . . . 87
7.2.3 Axiomas da Teoria dos Conjuntos . . . . . . 89
7.2.4 Alguns Tipos de Conjuntos . . . . . . . . . 90
7.3 Paradoxo de Russel . . . . . . . . . . . . . . . . . . 90
7.4 Teoria dos Conjuntos de Zermelo-Fraenkel . . . . . 92
7.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 97
7.6 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 98
7.7 Atividades . . . . . . . . . . . . . . . . . . . . . . . 99
7.8 Referências Bibliográficas . . . . . . . . . . . . . . 99
Aula 8: Operações com Conjuntos: União e Interseção101
8.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 102
8.2 União de Conjuntos . . . . . . . . . . . . . . . . . 102
8.2.1 Propriedades da União de Conjuntos . . . . 103
8.3 Interseção de Conjuntos . . . . . . . . . . . . . . . 103
8.3.1 Propriedades da Interseção de Conjuntos . . 104
8.3.2 Propriedades da União e Interseção de Con-
juntos . . . . . . . . . . . . . . . . . . . . . 104
8.3.3 Propriedades da Relação de Contido . . . . 105
8.4 Algumas Demonstrações . . . . . . . . . . . . . . . 105
8.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 108
8.6 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 108
8.7 Atividades . . . . . . . . . . . . . . . . . . . . . . . 109
8.8 Referências Bibliográficas . . . . . . . . . . . . . . 110
Aula 9: Operações com Conjuntos: Diferença e Complementar111
9.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 112
9.2 Diferença de Conjuntos . . . . . . . . . . . . . . . . 112
9.2.1 Propriedades da Diferença de Conjuntos . . 112
9.3 Diferença Simétrica de Conjuntos . . . . . . . . . . 113
9.3.1 Propriedades da Diferença Simétrica de Con-
juntos . . . . . . . . . . . . . . . . . . . . . 113
9.4 Complementar de Conjuntos . . . . . . . . . . . . . 114
9.4.1 Propriedades do Complementar de Conjuntos 114
9.5 Algumas Demonstrações . . . . . . . . . . . . . . . 115
9.6 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 119
9.7 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 119
9.8 Atividades . . . . . . . . . . . . . . . . . . . . . . . 121
9.9 Referências Bibliográficas . . . . . . . . . . . . . . 121
Aula 10: Operações com Conjuntos: Produto Cartesiano123
10.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 124
10.2 Par Ordenado . . . . . . . . . . . . . . . . . . . . . 124
10.3 Produto Cartesiano de Conjuntos . . . . . . . . . . 128
10.3.1 Propriedades do Produto Cartesiano . . . . 129
10.4 Algumas Demonstrações . . . . . . . . . . . . . . . 130
10.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . 133
10.6 Resumo . . . . . . . . . . . . . . . . . . . . . . . . 133
10.7 Atividades . . . . . . . . . . . . . . . . . . . . . . . 134
10.8 Referências Bibliográficas . . . . . . . . . . . . . . 135
Aula 11: Relações Binárias 137
11.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 138
11.2 Relações Binárias . . . . . . . . . . . . . . . . . . . 138
11.2.1 Propriedades das Relações Binárias . . . . . 141
11.3 Algumas Demonstrações . . . . . . . . . . . . . . . 144
11.4 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 146
11.5 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 146
11.6 ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 148
11.7 REFERÊNCIAS BIBLIOGÁFICAS . . . . . . . . 149
Aula 12: Relações de Ordem 151
12.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 152
12.2 Relações de Ordem . . . . . . . . . . . . . . . . . . 152
12.2.1 Cotas Superiores e Cotas Inferiores . . . . . 156
12.2.2 Elementos Maximal, Minimal, Máximo e Mí-
nimo . . . . . . . . . . . . . . . . . . . . . . 156
12.3 Algumas Demonstrações . . . . . . . . . . . . . . . 157
12.4 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 160
12.5 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 160
12.6 ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 162
12.7 REFERÊNCIAS BIBLIOGÁFICAS . . . . . . . . 162
Aula 13: Relações de Equivalência 165
13.1 Introdução . . . . . .. . . . . . . . . . . . . . . . . 166
13.2 Relações de Equivalência . . . . . . . . . . . . . . . 166
13.2.1 Partições e Classes de Equivalência . . . . . 168
13.3 Algumas Demonstrações . . . . . . . . . . . . . . . 171
13.4 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 175
13.5 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 175
13.6 ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 176
13.7 REFERÊNCIAS BIBLIOGÁFICAS . . . . . . . . 177
Aula 14: Funções 179
14.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 180
14.2 Funções . . . . . . . . . . . . . . . . . . . . . . . . 180
14.2.1 Imagem Direta e Imagem Inversa . . . . . . 182
14.3 Algumas Demonstrações . . . . . . . . . . . . . . . 185
14.4 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 188
14.5 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 189
14.6 ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 190
14.7 REFERÊNCIAS BIBLIOGÁFICAS . . . . . . . . 191
Aula 15: Tipos de Funções 193
15.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 194
15.2 Tipos de Funções . . . . . . . . . . . . . . . . . . 194
15.3 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 202
15.4 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 203
15.5 ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 204
15.6 REFERÊNCIAS BIBLIOGÁFICAS . . . . . . . . 204
Aula 16: Propriedades das Funções 207
16.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 208
16.2 Propriedades das Funções Injetoras . . . . . . . . . 208
16.3 Propriedades das Funções Sobrejetoras . . . . . . . 209
16.4 Propriedades das Funções Bijetoras . . . . . . . . . 209
16.5 Algumas Demonstrações . . . . . . . . . . . . . . . 210
16.6 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 214
16.7 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 214
16.8 ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 216
16.9 REFERÊNCIAS BIBLIOGÁFICAS . . . . . . . . 216
Aula 17: Números Naturais: Axiomas de Peano 219
17.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 220
17.2 Axiomas de Peano . . . . . . . . . . . . . . . . . . 220
17.3 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 226
17.4 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 226
17.5 ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 227
17.6 REFERÊNCIAS BIBLIOGÁFICAS . . . . . . . . 227
Aula 18: Operações em N 229
18.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 230
18.2 Soma no Conjunto dos Números Naturais . . . . . 230
18.3 Propriedades da soma . . . . . . . . . . . . . . . . 231
18.4 Produto no Conjunto dos Números Naturais . . . . 231
18.5 Propriedades do Produto . . . . . . . . . . . . . . . 232
18.6 Relação de Ordem no Conjunto dos Números Naturais232
18.7 Propriedades da Relação de Ordem . . . . . . . . . 232
18.7.1 Demonstração de Algumas Propriedades . . 233
18.8 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 238
18.9 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 238
18.10ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 240
18.11REFERÊNCIAS BIBLIOGÁFICAS . . . . . . . . 241
Aula 19: Princípio da Boa Ordem 243
19.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 244
19.2 Alguns Teoremas . . . . . . . . . . . . . . . . . . . 244
19.3 Princípio da Boa Ordem . . . . . . . . . . . . . . . 248
19.4 Primeiro Princípio da Indução Finita . . . . . . . . 252
19.5 Segundo Princípio da Indução Finita . . . . . . . . 252
19.6 Algumas Demonstrações . . . . . . . . . . . . . . . 254
19.7 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 257
19.8 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 258
19.9 ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 258
19.10REFERÊNCIAS BIBLIOGÁFICAS . . . . . . . . 259
Aula 20: Cardinalidade e Conjuntos Enumeráveis 261
20.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 262
20.2 Cardinalidade de um Conjunto . . . . . . . . . . . 262
20.2.1 Conjuntos Enumeráveis . . . . . . . . . . . 264
20.2.2 Algumas Demonstrações . . . . . . . . . . . 266
20.3 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . 270
20.4 RESUMO . . . . . . . . . . . . . . . . . . . . . . . 270
20.5 ATIVIDADES . . . . . . . . . . . . . . . . . . . . . 272
20.6 REFERÊNCIAS BIBLIOGRÁFICAS . . . . . . . . 272
1
AULA
1
LIVRO
Linguagem da Lógica
de Predicados
META:
Introduzir o conceito de Linguagem
da Lógica de Predicados
OBJETIVOS:
Ao fim da aula os alunos deverão
ser capazes de:
Distinguir entre linguagem natural
e linguagem artificial;
Compreender e utilizar a sintaxe da
linguagem da lógica de predicados.
Linguagem da Lógica de Predicados
1.1 Introdução
Caro aluno, seja bem-vindo a nossa primeira aula de Fun-
damentos de Matemática! Nela conheceremos o conceito de lin-
guagem, como ela está estruturada, as diferenças entre linguagens
naturais e linguagens artificiais e, por fim, nosso real objetivo,
estudar quais elementos que a compõe e como é estruturada a Lin-
guagem da Lógica de Predicados.
Linguagem “S. f. O
uso da palavra artic-
ulada ou escrita como
meio de expressão e co-
municação entre pes-
soas” (Dicionário Au-
rélio). Pode ser de-
finida também como
“conjunto de sentenças,
cada uma de compri-
mento finito e formadas
a partir de um conjunto
finito de símbolos”. A
primeira definição serve
para descrever as lin-
guagens naturais (Por-
tuguês, Inglês, e.t.c.) a
segunda para descrever
as linguagens formais
(Linguagens de Progra-
mação, Teoria dos Con-
juntos e.t.c.)
1.2 Linguagens
Vocês já se perguntaram o que é uma linguagem? Nos di-
cionários podemos obter algo do tipo: linguagem é um sistema
de símbolos que serve como meio de comunicação. Notem que
o vocábulo comunicação não se restringe à comunicação hunano-
humano. A linguagem serve também para comunicação humano-
máquina e máquina-máquina.
As definições de linguagem podem parecer um pouco vagas
e não expressar a verdadeira dimensão e alcance do objeto lin-
guagem. Não é pretensão definir corretamente linguagem, mas tão
somente deixar como tema de reflexão. O interesse é tão somente
estabelecer a linguagem da lógica de predicados, nosso maior ob-
jetivo.
1.3 Aspectos das Linguagens
As linguagens naturais apresentam três aspectos. A saber:
Morfológico diz respeito às regras de formação das palavras.
O Português, por exemplo, tem palavras baseadas em morfemas
16
Fundamentos da Matemática: Livro 1
1
AULA
que por sua vez são representados por cadeias de letras de um
conjunto de símbolos (alfabeto). Assim, as cadeias de letras “xz-
zcdzxx” e “aeeeeexxaeeeee” não representam palavras morfologi-
camente válidas na língua portuguesa, enquanto que as palavras
“gato”, “jardim”, “morro” e “subir” atendem a este requisito.
Semântico: diz respeito ao significado das palavras. No caso do
conjunto de palavras morfologicamente válidas “xakação”, “xitei-
ções”, “gato”, “jardim”, “morro” e “subir” apenas “gato”, “jardim”,
“morro” e “subir”, são semanticamente válidas, isto é tem signifi-
cado a elas associado.
Pragmático diz respeito ao uso das construções lingüísticas pe-
los usuários de uma linguagem. Em outras palavras, diz respeito
ao significado subentendido de uma sentença. Vamos exemplificar
com uma piada. Joaquim viaja para o Brasil e deixa seu gato de
estimação aos cuidados de seu amigo Manuel. Dois meses depois,
recebe uma carta do amigo: “Joaquim, seu gato morreu”. Joaquim
quase morreu de susto e tristeza. De volta a Portugal, procura o
amigo e pergunta como o gato morreu. Ô Quim, seu gato subiu
no telhado. No telhado encontrou outro gato. Começou a brigar.
Seu gato caiu do telhado. Eu o levei ao veterinário. Convalesceu
alguns dias.E morreu. Pois é, diz Joaquim, você podia ter me
preparado primeiro para a notícia. Escreveria várias cartas. Na
primeira me dizia “Joaquim, seu gato subiu no telhado”. Na se-
gunda “Joaquim, seu gato encontrou outro gato no telhado”. Até
me contar que ele morreu e eu estaria preparado para a notícia.
De volta ao Brasil, dois meses depois Joaquim recebe mais uma
carta de Manuel. “Joaquim, sua mãe subiu no telhado”. Piada à
parte, a frase “Joaquim sua mãe subiu no telhado”, não quer infor-
17
Linguagem da Lógica de Predicados
mar a Joaquim que sua genitora escalou a cobertura da casa e sim
(significado pragmático) que sua mãe faleceu. Significados prag-
máticos são encontrados em maior profusão na linguagem infor-
mal, sobretudo nas gírias em que o significado normal das palavras
e sentenças é subvertido.
Aristóteles 384-322
a.C Filósofo grego
nascido na cidade
de Estagira, um dos
maiores pensadores
de todos os tempos.
Prestou inigualáveis
contribuições para
o pensamento hu-
mano, destacando-se:
ética, política, física,
metafísica, lógica,
psicologia, poesia,
retórica, zoologia,
biologia, história nat-
ural e outras áreas de
conhecimento. É con-
siderado, por muitos,ao
Pai da Lógica.
As linguagens artificiais, por outro lado, têm apenas os aspec-
tos sintáticos e semânticos e são, convenientemente, destituídas
de significado pragmático. Afinal, não é desejável em um pro-
grama de computador significados pessoais e subtendidos dos pro-
gramadores. Isto daria um nó no interpretador da máquina.
1.4 Linguagem da Lógica de Predicados
Agora que você já conheceu um pouco sobre as linguagens na-
tural e artificial, passaremos ao estudo da Lógica de Predicados.
Ela é a primeira e talvez a mais importante parte da Lógica, pois
além de ser a mais antiga (desenvolvida inicialmente por Aristó-
teles) serve de base para as demais Lógicas. Em um curso inicial
como o nosso é justo, portanto, começarmos pela defição:
Definição 1.1. Uma proposição é uma sentença a que podemos
associar um de dois valores de verdade: falso 0 ou verdadeiro 1.
Exemplo 1.1. Os seguintes exemplos são proposições:
• “O gato é um mamífero”. Valor de verdade associado: ver-
dadeiro.
18
Fundamentos da Matemática: Livro 1
1
AULA
• “Pedro Álvares Cabral descobriu a Nova Zelândia”. Valor de
verdade associado: falso.
• “O hidrogênio é o primeiro elemento da tabela periódica”.
Valor de verdade associado: verdadeiro.
Exemplo 1.2. Os seguintes exemplos não são proposições:
• “Flamengo é o melhor time do mundo”. Exprime uma opinião
pessoal. Verdade apenas para os torcedores do Flamengo.
• “Um sonho azul da cor do mar”. Uma sentença poética.
• “Por favor, não grite!”. Uma sentença exclamativa.
1.4.1 Sintaxe da Linguagem da Lógica de Predicados
A lógica de predicados
é a base para o desen-
volvimento de inúmeras
outras lógicas como as
alética, deôntica, ep-
stemológica, paracon-
sistente, paracompleta,
fuzzy etc. Você pode
fazer uma busca, por
informações, na IN-
TERNET sobre estes
tipos de lógicas.
Definição 1.2. A linguagem da Lógica de Predicados em seu as-
pecto sintático é definida por:
• um conjunto enumerável de constantes individuais a, b, . . . , t,
a1, a2, . . . (letras latinas minúsculas até o t)
• um conjunto enumerável de variáveis u, v, x, y, w, z, u1, u1, . . .
(letras latinas minúsculas a partir de u)
• para cada número n natural um conjunto enumerável de
predicados enários A,B, . . . , a1, . . . (letras latinas maiúscu-
las)
• os conectivos negação (¬), conjunção (∧), disjunção (∨), im-
plicação (→), dupla implicação (↔).
• os quantificadores universal (∀) e existencial (∃)
19
Linguagem da Lógica de Predicados
• símbolos de pontuação parênteses () para indicar a ordem de
aplicação dos operadores.
OBS 1.1. Constantes individuais são como nomes, identificam um
indivíduo ou um objeto. Neste sentido ’a’ pode representar ’Gato’
e ’b’ pode representar ’Pedro Álvares Cabral’ e as proposições “Gato
é um mamífero” e “Pedro Álvarez Cabral descobriu a Nova Zelân-
dia” podem ser escrtitas respectivamente “a é um mamífero” e “b
descobriu a Nova Zelândia”.
OBS 1.2. Algumas vezes podemos e devemos substituir uma con-
stante individual por uma variável. Então, se a proposição “x é um
homem” e tomarmos para variável ’x’ o valor ’Gato’ ela será obvia-
mente FALSA, enquanto que se a variável ’x’ tomar o valor ’Pedro
Álvares Cabral’ a proposição será obviamente VERDADEIRA. De
modo geral, uma variável tem seus valores tomados sobre um con-
junto denominado Conjunto Universo para a citada variável.
OBS 1.3. Um predicado representa propriedades de um indivíduo
ou grupo de indivíduos ou relações entre indivíduos. Na sentença
“x é um poeta,” é um poeta indica, quando substituída a variável
x, que o indivíduo desta substituição tem a propriedade de ser um
poeta. A sentença “Mara senta entre Fernanda e Lígia” representa
uma relação ternária entre três indivíduos e pode ser reescrita como
“a senta entre b e c” se associarmos ’a’ à ’Mara’, ’b’ à ’Fernanda’
e ’c’ à ’Lígia’. Simbolizando a relação “x senta entre y e z” por
P (x, y, z), podemos reescrever a proposição como P (a, b, c). Nem
todo predicado tem necessariamente uma ou mais variáveis em seu
escopo. A sentença “choveu ontem” pode ser FALSA ou VER-
DADEIRA e não faz referência a nenhum indivíduo ou entidade,
20
Fundamentos da Matemática: Livro 1
1
AULA
sendo classificada como predicado zerário.
OBS 1.4. Os conectivos servem para modificar ou criar novas
proposições a partir de outras proposições. Excetuando-se o conec-
tivo de negação que é unário, os demais conectivos são binários, isto
é, conectam duas proposições para construir uma nova proposição.
Assim, a proposição “João é poeta e Fernando é jogador de fute-
bol” pode ser representada, fazendo-se as associações ’a’ ’João’, ’b’
’Fernando’ e os predicados P (x) para “x é poeta” e Q(x) para “x
é jogador de futebol” podemos representar a proposição usando o
conectivo de conjunção por: P (a) ∧Q(b).
OBS 1.5. O quantificador existencial diz respeito a proposições
do tipo “Alguem é poeta”. Nesta sentença estamos afirmando que
existe um indivíduo que tem a propriedade de ser poeta, sem, no
entanto especificar quem é este indivíduo. Já o quantificador uni-
versal diz respeito a proposições do tipo “Todo homem é mortal”.
Nesta sentença estamos afirmando que a totalidade dos homens
tem a propriedade de ser mortal.
Definição 1.3. Dado um predicado enário P (x1, . . . , xk, . . . , xn).
Dizemos que a variável xk é uma variável livre se, somente se xk
não está no escopo de nenhum quantificador.
Exemplo 1.3. Alguns exemplos:
• ∀x(x < 2). Nenhuma variável livre. A variável x está no
escopo de um ∀ quantificador universal.
• x < y2. x e y são variáveis livres. Pois, tanto x quanto y não
estão no escopo de nenhum quantificador.
21
Linguagem da Lógica de Predicados
• ∃x(x < y). Apenas y é variável livre. Pois a variável x está
no escopo do ∃ quantificador existencial.
Definição 1.4. Uma sentença em que aparecem uma ou mais vari-
áveis livres é denominada Sentença Livre ou Proposição Livre.
Definição 1.5. Seja P (x1, . . . , xn) um predicado enário. Defini-
mos como Átomos as proposição da forma P (a1, . . . , an) ou P (x1,
. . . , xn).
OBS 1.6. Em uma proposição atômica não podem aparecer conec-
tivos. Uma proposição em que aparecem um ou mais conectivos
são chamadas Proposições Moleculares.
Exemplo 1.4. As seguintes proposições são átomos:
• A em que A é um predicado zerário.
• P (x) ou P (a) onde P é um predicado unário.
• P (x, y, z) ou P (a, b, c) onde P é um predicado terciário.
Exemplo 1.5. As seguintes proposições são proposições molecu-
lares:• ¬A onde A é um predicado zerário. O conectivo de negação
¬ está modificando A.
• P (x)∧P (y) ou ¬P (a)∨A onde A e P são predicados zerário e
unário respectivamente. Na primeira proposição o conectivo
de conjunção ∧ liga dois átomos P (x) e P (y). Na segunda,
o conectivo de disjunção ∨ liga um átomo A à proposição
molecular ¬P (a).
22
Fundamentos da Matemática: Livro 1
1
AULA
• ∀x∃yP (x, y, z) ou ∃zP (a, b, z) onde P é um predicado ter-
ciário. A proposição atômica P (x, y, z) é modificada pelos
quantificadores universal ∀ e existencial ∃. E a proposição
atômica P (a, b, x) é modificada pelo quantificador ∃ existen-
cial.
Definição 1.6. As palavras (fórmulas) da linguagem do cálculo
de predicados são definidas por:
• um átomo é uma fórmula.
• se α e β são fórmulas então ¬α, α∧β, α∨β, α→ β e α↔ β
são fórmulas.
• Se P é um predicado enário e x1, . . . , xn n variáveis. en-
tão ∀x1, . . . , xnP (x1, . . . , xn) e ∃x1, . . . , xnP (x1, . . . , xn) são
fórmulas.
• nada mais é fórmula.
Exemplo 1.6. Os seguintes exemplos são fórmulas válidas na lin-
guagem do cálculo de predicados:
• α
• α ∧ (β → γ)
• (α→ (β ∧ ¬β))→ ¬α
• ∀x(∃y(x < y))
Exemplo 1.7. Os seguintes exemplos são fórmulas não válidas na
linguagem do cálculo de predicados:
• αβ dois átomos que não estão ligados por nenhum conectivo
binário.
23
Linguagem da Lógica de Predicados
• α ∧ (β∧ → γ) ∨ α os conectivos ∧ e → juntos.
• (α→ (β¬∧¬β))¬ → ¬α o conectivo ¬ aplicado ao conectivo
→.
• ∀∃x(∃∀y(x < y)) os quantificadores ∀ e ∃ juntos.
1.5 Conclusão
A linguagem é a ferramenta essencial para a comunicação. É
atraves dela que podemos descrever os mecanismos de raciocínio
lógico, na qual utilizamos uma linguagem denominada de Lin-
guagem da Lógica de Predicados. Com regras simples, mas uni-
versais, possibilita que, tanto um Matemático chinês quanto um
Matemático brasileiro possam, sem problemas, ler e compreender
um texto baseado em Lógica de Predicados.
1.6 Resumo
Vimos que as linguagens naturais apresentam três aspectos: o
sintático, o semântico e o pragmático; enquanto que as linguagens
artificiais apresentam apenas dois o sintático e o semântico. O
mofológico diz respeito as regras de construção de palavras e de
frases. O semântico diz respeito ao significado das palavras e das
frases. O pragmático diz respeito aos possíveis significados subten-
dido das frases. A Linguagem da Lógica de Predicados trabalha
com proposições que são frases para as quais podemos associar um
valor verdadeiro ou falso. Vimos também, que a sintaxe da lin-
guagem da lógica de predicados consiste de constantes individuais,
variáveis, predicados enários, dos conectivos negação ¬ (unário),
24
Fundamentos da Matemática: Livro 1
1
AULA
conjunção ∧, disjunção ∨, implicação → e dupla implicação ↔
(binários) e dos quantificadores existencial ∃ e universal ∀. Que
uma variável é dita livre se não está no escopo de nenhum quan-
tificador. Que um átomo é um predicado zerário ou um predicado
enário determinado em um conjunto de n constantes individuais
e/ou variáveis. Que as fórmulas (palavras) da lógica de predicados
são definidas por:
• átomos são fórmulas
• se α e β são fórmulas, ¬α, α ∧ β, α ∨ β, α→ β e α↔ β são
fórmulas.
• se P é um predicado enário e x1, . . . , xn n variáveis. então
∀x1, . . . , xnP (x1, . . . , xn) e ∃x1, . . . , xnP (x1, . . . , xn) são fór-
mulas.
• nada mais é fórmula.
1.7 Atividades
ATIV. 1.1. Escreva cinco exemplos de sentenças em seja seja pos-
sível encontrar aspectos pragmáticos da linguagem.
Comentário: Volte ao texto e reveja o que é significado prag-
mático.
ATIV. 1.2. Elabore a sintaxe de uma linguagem artificial com
apenas dois símbolos iniciais A e B.
Comentário: Observe a sintaxe da linguagem da lógica de predi-
cados.
25
Linguagem da Lógica de Predicados
1.8 Referências Bibliográficas
MORTARI, Cezar Augusto. Introdução à Lógica. Editora UNESP.
São Paulo. 2001.
GASPAR, Marisa. Introdução à Lógica Matemática. Disponível
em: http:// mjgaspar.sites.uol.com.br/logica/logica. Acessado em
13/01/2007
ABAR, Celina, Noções de Lógica Matemática. Disponível em:
http://www. pucsp.br/∼logica/. Acessado em 13/01/2007
26
2
AULA
1
LIVRO
Conectivos e
Quantificadores
Lógicos
META:
Introduzir os conectivos e quantifi-
cadores lógicos.
OBJETIVOS:
Ao fim da aula os alunos deverão
ser capazes de:
Compreender a semântica dos
conectivos lógicos;
Aplicar os quantificadores univer-
sal e existencial para modificar
proposições lógicas.
PRÉ-REQUISITOS
Aula-01 os conhecimentos da sin-
taxe da Linguagem da Lógica de
Predicados.
Conectivos e Quantificadores Lógicos
2.1 Introdução
Em nossa primeira aula, vimos a sintaxe da Linguagem da
Lógica de Predicados. Nesta segunda, complementaremos intro-
duzindo a semântica . Mais precisamente, como os conectivos e
quantificadores modificam o valor de verdade das proposições.
2.2 Semântica da Linguagem da Lógica de
Predicados
Chegamos ao ponto em que é preciso dotar a linguagem do
cálculo de predicados de uma Semântica, isto é, de significado.
Individualmente, a cada átomo podemos associar um de dois valo-
res de verdade: 0 (falso) ou 1 (verdadeiro). Porém, para as fórmu-
las moleculares, precisamos dizer como os conectivos associam um
dos dois valores de verdade à fórmula molecular a partir dos valores
de verdade das fórmulas atômicas que a compõem. Descrevemos
a semântica de uma fórmula molecular usando uma denominada
tabela de verdade, em que cada linha representa uma das possíveis
combinações de valores de verdade de cada átomo que compõem a
fórmula molecular. Na próxima aula, entraremos em detalhe sobre
o uso de tabelas de verdade para a avaliação de fórmulas molecu-
lares. Para uma proposição composta de n átomos são necessárias
2n entradas. Como a maioria dos conectivos são binários, isto é,
conectam duas proposições, o número de possíveis entradas são 4
(quatro). Os conectivos permitem a análise de proposições mais
complexas do tipo “Se Maria tem mais de 18 anos e é mental-
mente sadia, então Maria é juridicamente responsável pelos seus
28
Fundamentos da Matemática: Livro 1
2
AULA
atos”. Notem que esta regra não é válida apenas para Maria, seja
lá quem for Maria, vale para todos. Daí, podemos dizer que “To-
das as pessoas que têm mais de 18 anos e são mentalmente sadias
então são juridicamente responsáveis pelos seus atos”. Na segunda
proposição, além do uso de conectivos identificamos o uso do quan-
tificador universal quando dizemos que o predicado ou propriedade
vale para todos os indivíduos.
NEGAÇÃO A negação, como o próprio nome diz, nega a proposi-
ção que tem como argumento. Tem como símbolos ∼ α , ¬α, ou,
algumas vezes, uma barra sobre a variável lógica, α¯, ou o sinal nega-
tivo, −α, ou o símbolo barra invertida, /α, ou ainda, α′. Lembre-se
de que o símbolo nada mais é que uma simples representação da
negação. O que é relevante é que o significado do símbolo seja
explicitamente declarado. Aqui usaremos o simbólo ¬ para re-
presentar a negação daqui para frente. A semântica do conectivo
negação.
α ¬α
1 0
0 1
Tabela 2.1: semântica do conectivo de negação da Linguagem da
Lógica de Predicados
Exemplo 2.1. Alguns exemplos de uso do conectivo de negação:
• se α =Maria tem um gato, ¬α =Maria não tem um gato.
• se α =O gato é um mamífero, ¬α =O gato não é um mamífe-
ro.
• se α =O rato é um pássaro, ¬α =O rato não é um pássaro.
29
Conectivos e Quantificadores Lógicos
CONJUNÇÃO A conjunção estabelece uma adição entre duas
proposições de modo que se α e β são duas proposições, a con-
junção de α e β será verdade somenteno caso em que ambas α e
β forem verdadeiras. O símbolo mais utilizado para a conjunção é
α ∧ β, em Eletrônica Digital é o ponto α • β.
α β α ∧ β
1 1 1
0 1 0
1 0 0
0 0 0
Tabela 2.2: semântica do conectivo de conjunção da Linguagem
da Lógica de Predicados
Exemplo 2.2. Alguns exemplos de uso do conectivo de conjunção:
• caso α =Maria tem um gato malhado e β = O rato é um
pássaro amarelo, teremos então que α ∧ α =Maria tem um
gato malhado e o rato é um pássaro amarelo.
• caso α = A batata é um vegetal e β = Sergipe fica no
Nordeste do Brasil, teremos então que α ∧ β = A batata
é um vegetal e Sergipe fica no nordeste do Brasil.
• caso α = A é a última letra do alfabeto e β = Uma centopéia
tem apenas 11 pares de pernas, teremos então que α ∧ β =
A é a última letra do alfabeto e uma centopéia tem apenas
11 pares de pernas.
• caso α =Um juiz de Direito tem que ser formado em Medi-
cina e q =
√
4 = 2 teremos que α ∧ β =Um juiz de Direito
30
Fundamentos da Matemática: Livro 1
2
AULA
tem que ser formado em Medicina e
√
4 = 2.
DISJUNÇÃO A disjunção estabelece uma separação entre duas
proposições, entendida de modo inclusivo, de modo que se α e β
são duas proposições, a disjunção de α e β será falsa somente no
caso em que ambas α e β forem falsas. O símbolo mais utilizado
para a disjunção é α ∨ β, em Eletrônica Digital, é o mais α+ β.
α β α ∨ β
1 1 1
0 1 1
1 0 1
0 0 0
Tabela 2.3: semântica do conectivo de disjunção da Linguagem da
Lógica de Predicados
Exemplo 2.3. Alguns exemplos de uso do conectivo de disjunção:
• caso α = O décimo elemento da tabela periódica é o oxigênio
e β = O rato é um pássaro amarelo, teremos então que α∨β =
O décimo elemento da tabela periódica é o oxigênio ou o rato
é um pássaro amarelo.
• caso α =O elefante africano é cinza claro e β =O céu é azul
turquesa, teremos então que α ∨ β =O elefante africano é
cinza claro ou o céu é azul turquesa.
• caso α =Um litro de água pesa um quilo e β = Partículas de
carga elétrica iguais se repelem, teremos então que α∨β =Um
litro de água pesa um quilo ou partículas de carga elétrica
iguais se repelem.
31
Conectivos e Quantificadores Lógicos
• caso α = Uma tartaruga pode viver mais de cem anos e β =
A meningite é uma doença que só ataca as pessoas do sexo
feminino, teremos então que α ∨ β = Uma tartaruga pode
viver mais de cem anos ou a meningite é uma doença que só
ataca as pessoas do sexo feminino.
IMPLICAÇÃO A implicação estabelece uma condição entre
duas proposições: a primeira chamada antecedente e a segunda
de conseqüente, de modo que se α e β são duas proposições, a
implicação α implica em β será falsa somente no caso em que α
(antecedente) for verdadeira e β (conseqüente) é falsa. O símbolo
mais utilizado para a implicação é α→ β, menos usual α ⊃ β.
α β α→ β
1 1 1
0 1 1
1 0 0
0 0 1
Tabela 2.4: semântica do conectivo de implicação da Linguagem
da Lógica de Predicados
Exemplo 2.4. Alguns exemplos de uso do conectivo de impli-
cação:
• se α =Maria tem um gato e β =O rato é um pássaro, teremos
então que α→ β =Maria tem um gato leva a que o rato é
um pássaro.
• caso α =O elefante é cinza e β =O céu é azul, teremos que
α→ β =Se o elefante é cinza implica em que o céu é azul.
32
Fundamentos da Matemática: Livro 1
2
AULA
• caso α =Um litro de água pesa um quilo e β =O Brasil fica
na Ásia, teremos que α→ β = Se um litro de água pesa um
quilo então o Brasil fica na Ásia.
• caso α =Um time de futebol tem 5 jogadores e β = √4 = 2,
teremos que α→ β =Se um time de futebol tem 5 jogadores
em conseqüência
√
4 = 2.
OBS 2.1. A implicação lógica (condicional) pode, a princípio,
parecer estranha pelo fato de que uma implicação é falsa apenas
no caso em que o antecedente é verdadeiro e o conseqüente é falso.
Este fato é a base de toda a Matemática, ou seja, de uma infor-
mação verdadeira jamais raciocinando matematicamente chegare-
mos a uma conclusão falsa. Na linguagem coloquial, frases como a
do terceiro exemplo não fazem sentido muito embora para a Lógica
de Predicados elas sejam verdadeiras.
DUPLA IMPLICAÇÃO A dupla implicação (bi-condicional)
estabelece uma condição bidirecional entre duas proposições de
modo que se α e β são duas proposições; a dupla implicação será
verdade quando ambas α e β tiverem o mesmo valor de verdade.
O símbolo mais utilizado para a dupla implicação é α↔ β, menos
usual α ≡ β
Exemplo 2.5. Alguns exemplos de uso do conectivo de dupla
implicação:
• se α =Maria tem um gato e β =O rato é um pássaro, teremos
então que α ↔ β =Maria tem um gato se, somente se o
rato é um passaro.
• caso α =O elefante é cinza e β =O céu é azul, teremos então
33
Conectivos e Quantificadores Lógicos
α β α↔ β
1 1 1
0 1 0
1 0 0
0 0 1
Tabela 2.5: semântica do conectivo de dupla implicação da Lin-
guagem da Lógica de Predicados
que α ↔ β =O elefante é cinza se, somente se, o céu é
azul.
• caso α =Um litro de água pesa um quilo e β =o hidrogênio
tem peso atômico 17, teremos então que α ↔ β =Um litro
de água pesa um quilo se, somente se, o hidrogênio tem
peso atômico 17.
2.3 Quantificadores
Quantificadores, em Lógica de Predicados, são elementos que
especificam a extensão da validade de um predicado sobre um con-
junto de constantes individuais. Assim, na proposição “todos os
homens são mortais”, estamos estendendo a todos os elementos do
conjunto dos homens a propriedade de ser mortal e na proposição
“existe um planeta com duas luas”, estamos querendo dizer que do
conjunto de todos os planetas ao menos um deles tem duas luas.
QUANTIFICADOR UNIVERSAL Uma proposição é quan-
tificada universalmente quando refere-se à todo elemento do con-
junto do domínio do predicado. O símbolo para o quantificador
universal é ∀.
34
Fundamentos da Matemática: Livro 1
2
AULA
QUANTIFICADOR EXISTENCIAL Uma proposição é dita
quantificada existencialmente quando refere-se à algum elemento
do conjunto do domínio do predicado. O símbolo para o quantifi-
cador existencial é ∃.
Exemplo 2.6. Alguns exemplos de uso do quantificador universal
e do quantificador existencial:
• Todo homem é mortal. Podemos aqui representar por P =é
mortal, U =conjunto de todos os homens. Daí, a proposição
pode ser representada por: ∀x, P (x).
• Existe um mamífero de quatro patas. Podemos representar
por P =mamífero de quatro patas, U =conjunto de todos os
mamíferos. Temos então que a proposição pode ser represen-
tada por: ∃x, P (x).
OBS 2.2. A negação de proposições onde aparecem quantificadores
pode ser resumida por:
• ¬(∀x, P (x)) = ∃x,¬P (x).
• ¬(∃x, P (x)) = ∀x,¬P (x).
2.4 Conclusão
A Lógica de Predicados não teria muita utilidade sem os seus
conectivos. Eles ajudam a ligar proposições, de modo a formar
novas e mais complicadas proposições. Os conectivos exercem a
função de reunir fatos para que, posteriormente, possamos tirar
conclusões.
35
Conectivos e Quantificadores Lógicos
2.5 Resumo
A semântica dos conectivos da Linguagem da Lógica de Predi-
cados pode ser resumida na tabela abaixo.
α β ¬α α ∧ β α ∨ β α→ β α↔ β
1 1 0 1 1 1 1
0 1 1 0 1 1 0
1 0 0 0 1 0 0
0 0 1 0 0 1 1
Tabela 2.6: semântica dos conectivos da Linguagem da Lógica de
Predicados
2.6 Atividades
ATIV. 2.1. Para cada um dos conectivos da Lógica de Predicados
escreva três proposições logicamente válidas.
Comentário: Basei-se nos exemplos acima.
ATIV. 2.2. Para cada um dos quantificadores da Lógica de Pre-
dicados escreva uma proposição logicamente válidas.
Comentário: Basei-se nos exemplos acima.
2.7 Referências Bibliográficas
MORTARI, Cezar Augusto. Introdução à Lógica. Editora UNESP.
São Paulo. 2001.
GASPAR, Marisa. Introdução à LógicaMatemática. Disponível
em: http:// mjgaspar.sites.uol.com.br/logica/logica. Acessado em
13/01/2007
36
Fundamentos da Matemática: Livro 1
2
AULA
ABAR, Celina, Noções de Lógica Matemática. Disponível em:
http://www. pucsp.br/∼logica/. Acessado em 13/01/2007
37
3
AULA
1
LIVRO
Valorações e
Tabelas de Verdade
META:
Apresentar tabelas de verdade para
classificar proposições lógicas.
OBJETIVOS:
Ao fim da aula os alunos deverão
ser capazes de:
Aplicar valorações de um conjunto
de proposiçoes moleculares;
Usar tabelas de verdade para avaliar
as possíveis valorações de um con-
junto de proposições moleculares.
PRÉ-REQUISITOS
Aula-02 os conhecimentos da
semântica da Linguagem da Lógica
de Predicados.
Valorações e Tabelas de Verdade
3.1 Introdução
Caro aluno, na aula anterior, vimos as definições semânticas
dos conectivos lógicos e dos quantificadores. Hoje, continuare-
mos ainda que em ritmo de valsa, a navegar no mar da Lógica
Matemática aproveitando o passeio para conhecê-la melhor. Nesta
aula, conceituaremos valorações que é uma das formas de se avaliar
as proposições moleculares. Esperamos que o pré-requisito soli-
citado seja realizado, pois ele facilitará a compreensão e o bom
andamento de nossa aula.
3.2 Valorações
Valorações constituem-se em uma das formas de se avaliar uma
proposição molecular a partir de suas proposições atômicas. Para
compreendermos melhor, iniciaremos pela definição:
Definição 3.1. Seja Γ = {α1, . . . , αn} um conjunto com n proposi-
ções atômicas. Definimos uma valoração sobre Γ como uma função
v : Γ 7→ {0, 1}.
OBS 3.1. Uma valoração é uma função que associa a cada uma
das proposições de um conjunto de proposições um de dois valores
de verdade 0 para falso e 1 para verdade.
Exemplo 3.1. Como exemplo podemos tomar Γ = {α, β, γ} uma
possível valoração é v : Γ 7→ {0, 1} dada por:
v(α) = 1, v(β) = 0, v(γ) = 0
.
40
Fundamentos da Matemática: Livro 1
3
AULA
A lógica de predicados baseia-se no princípio de que a valoração
de uma proposição molecular é determinada unicamente pelas va-
lorações de suas proposições atômicas. Para estabelecer as regras
que deteminam a valoração de uma proposição molecular, vere-
mos primeiramente algumas operações sobre o conjunto {0, 1}, no
âmbito da álgebra de Boole.
George Boole nasceu
em Lincoln - Inglaterra
em 2 de Novembro
de 1815. Autodidata,
fundou aos 20 anos de
idade a sua própria
escola e dedicou-se ao
estudo da Matemática.
Em 1847 publicou The
Mathematical Analysis
of Logic em que in-
troduziu os conceitos
de lógica simbólica
demonstrando que
a lógica podia ser
reduzida a equações
algébricas. Wikipedia
3.3 Álgebra de Boole
A álgebra de Boole ou álgebra booleana foi criada pelo matemá-
tico inglês George Boole e consta do conjunto B = {0, 1} e três
operações + : B ×B 7→ B uma soma, • : B ×B 7→ B um produto
e ∗ : B 7→ B complementar. Definidas pelas tabelas abaixo:
+ 0 1 • 0 1 *
0 0 1 0 0 0 0 1
1 1 0 1 0 1 1 0
OBS 3.2. É fácil verificar (verificação direta) as seguintes pro-
priedades da álgebra de Boole:
• a+ b = b+ a,∀a, b ∈ B
• a+ (b+ c) = (a+ b) + c,∀a, b, c ∈ B
• a • b = b • a,∀a, b ∈ B
• a • (b • c) = (a • b) • c,∀a, b, c ∈ B
• a+ (b • c) = (a+ b) • (a+ c),∀a, b, c ∈ B
• a • (b+ c) = (a • b) + (a • c), ∀a, b, c ∈ B
41
Valorações e Tabelas de Verdade
• a+ a∗ = 1, ∀a ∈ B
• a • a∗ = 0, ∀a ∈ B
A partir de agora, caro aluno, podemos definir como calcular uma
valoração de uma proposição molecular a partir da valoração de
suas proposições atômicas. Para isto, usaremos a definição que
representa a semântica dos conectivos lógicos.
Definição 3.2. Sejam α e β proposições atômicas e v : {α, β} 7→
{0, 1} uma valoração então:
• v(¬α) = v(α)∗
• v(α ∧ β) = v(α) • v(β)
• v(α ∨ β) = v(α) + v(β)
• v(α→ β) = v(α)∗ + v(β)
• v(α↔ β) = (v(α)∗ + v(β) • (v(α) + v(β)∗)
3.4 Tabela de Verdade
Dada uma proposição molecular podemos especular sobre quais
os possíveis valores de verdade que ela pode ter para uma deter-
minada valoração de seus átomos. Mais ainda, podemos especular
sobre os valores de verdade que ela pode ter para todas as pos-
síveis valorações de seus átomos. Podemos reunir todas as pos-
síveis valorações de uma proposição molecular em uma tabela, a
qual denominamos de TABELA DE VERDADE. Os possíveis
valores para uma proposição molecular, como vocês já sabem, são
dois: falso 0 e verdadeiro 1. Desta forma, o número de todas as
42
Fundamentos da Matemática: Livro 1
3
AULA
possíveis combinações de valores de verdade para um conjunto de
n proposições atômicas é 2n.
OBS 3.3. Cada linha de uma tabela de verdade é denominada
uma instância ou simplesmente uma valoração.
Um conceito muito útil ao se manipular proposições moleculares
é o de subfórmula, que entre outras coisas serve para criação de
tabela de verdade. Vamos à definição:
Definição 3.3. Uma subfórmula é definida pelas seguintes regras:
• se α é uma fórmula então α é uma subfórmula.
• se α, β e γ são fórmulas e α = ¬β, α = β ∧ γ, α = β ∨ γ,
α = β → γ ou α = β ↔ γ então β e γ são subfórmulas de α.
• Se x é uma variável e α = ∀xP (x) ou α = ∃xP (x) então
P (x) é subfórmula de α.
• Se β é subfórmula de α e γ é subfórmula de β então γ é
subfórmula de α.
• nada mais é subfórmula.
Algoritmo s. m.
Sistema particular de
disposição que se dá
a uma sucessão de
cálculos numéricos.
Dicionário Prático
Michaelis
Vejamos a seguir como o conceito de subfórmula pode ser usado
na elaboração de um algoritmo para criar a tabela de verdade de
uma proposição molecular. Vamos ao algoritmo para construção
da tabela de verdade de uma proposição α molecular.
Passo 1 Contar o número n de símbolos proposicionais.
Passo 2 Montar uma tabela com 2n linhas e tantas colunas, quan-
tas forem as subfórmulas da proposição α.
43
Valorações e Tabelas de Verdade
Passo 3 Preencher as colunas dos símbolos proposicionais com 1
ou 0 alternando de cima para baixo para a primeira coluna
1010..., para a segunda coluna 11001100..., para a terceira
coluna 1111000011110000... e assim por diante alternando
sempre em potências de 2.
Passo 4 computar o valor de verdade das outras colunas usando
a semântica dos conectivos lógicos.
3.4.1 Uso de Parêntese e Prioridade dos Conectivos
Lógicos
O uso de parênteses na construção de proposições moleculares
mais complexas é inprescindível. Porém, mesmo em proposições
moleculares relativamente simples o uso de parênteses também é
necessário para evitar ambigüidades. Como exemplo a proposição
α ∨ β ∧ γ que pode ser interpretada de duas maneiras diferentes:
• α ∨ (β ∧ γ)
• (α ∨ β) ∧ γ
Daí, se não usarmos parênteses não poderemos decidir que inter-
pretação teremos.
Em proposições moleculares mais complexas, o número de parên-
teses pode ser reduzido usando-se o subterfúgio da ordem de pri-
oridade. Em palavras mais simples, quem é mais forte do que
quem aplica aos quantificadores lógicos. A convenção para a or-
dem de prioridade dos conectivos lógicos, em ordem crescente de
prioridade é:
44
Fundamentos da Matemática: Livro 1
3
AULA
• ¬ negação.
• ∧ conjunção e ∨ disjunção.
• → implicação e ↔ dupla implicação.
Onde, o conectivo ¬ negação é o mais fraco, tem prioridade mais
baixa. Os conectivos ∧ conjunção e ∨ disjunção vem a seguir com
mesmo nível de prioridade, seguidos da → implicação e ↔ dupla
implicação, que têm a maior prioridade, sendo os conectivos mais
fortes.
Desta forma, a proposição (α→ (β ∧ γ)) pode dispensar o par de
parênteses externos e passar a forma α→ (β ∧ γ) que por sua vez,
como a implicação→ tem prioridade sobre a conjunção ∧, o par de
parênteses restante pode sertambém dispensado. E a proposição
toma, sem ambigüidade, a forma final α → β ∧ γ. A propósito,
tomaremos esta proposição para exemplificar o algoritmo da tabela
de verdade. Primeiramente vemos que α→ β∧γ tem três átomos.
A saber, α, β e γ, o que nos dá 23 = 8 linhas na tabela de verdade
e como as subfórmulas são: α, β, γ, β ∧ γ e α → β ∧ γ teremos
5 colunas na tabela de verdade. Na coluna referente ao átomo α
alternamos 10101010, na coluna referente ao átomo β alternamos
11001100 e na coluna referente ao átomo γ alternamos 11110000,
construindo a tabela 3.1 .
Finalmente, completamos as colunas restantes (tabela 3.2)
usando a semântica dos conectivos lógicos aplicada a cada uma
das subfórmulas restantes. A saber:
45
Valorações e Tabelas de Verdade
α β γ β ∧ γ α→ β ∧ γ
1 1 1
0 1 1
1 0 1
0 0 1
1 1 0
0 1 0
1 0 0
0 0 0
Tabela 3.1: Proposição α→ β ∧ γ.
3.5 Tautologia, Contradição e Contingência
Você já pensou na possibilidade de que uma proposição molec-
ular possa ser verdadeira independente de quais os valores de ver-
dade de suas proposições atômicas componentes? Se você respon-
deu que já, você acabou de antecipar um conceito importante
TAUTOLOGIA. Para oficializar vamos à definição.
Definição 3.4. Uma fórmula molecular é dita uma tautologia,
denotada >, somente se seu valor de verdade for 1 verdade, para
qualquer combinação de valor de verdade de seus átomos.
A contrapartida da TAUTOLOGIA é a CONTRADIÇÃO que
é falsa independentemete dos valores de verdade de suas proposições
atômicas componentes. Vamos à definição.
Definição 3.5. Uma fórmula molecular é dita uma contradição,
denotada ⊥, somente se seu valor de verdade for 0 falso, para
qualquer combinação de valor de verdade de seus átomos.
46
Fundamentos da Matemática: Livro 1
3
AULA
α β γ β ∧ γ α→ β ∧ γ
1 1 1 1 1
0 1 1 1 1
1 0 1 0 0
0 0 1 0 1
1 1 0 0 0
0 1 0 0 1
1 0 0 0 0
0 0 0 0 1
Tabela 3.2: Proposição α→ β ∧ γ.
Definição 3.6. Uma fórmula molecular é dita uma contingência,
somente se não for uma tautologia nem uma contradição.
Exemplo 3.2. Como exemplos temos:
• ¬(β → α) uma contingencia.
• α→ (β → α) uma tautologia.
• α ∧ ¬(β → α) uma contradição.
Podemos confirmar verificando a tabela de verdade abaixo.
α β ¬α β → α ¬(β → α) α→ (β → α) α ∧ ¬(β → α)
1 1 0 1 0 1 0
0 1 1 0 1 1 0
1 0 0 1 0 1 0
0 0 1 1 0 1 0
Tabela 3.3: Contingência, tautologia e contradição.
47
Valorações e Tabelas de Verdade
Caro aluno, por hoje é só. Faremos um pequeno resumo do assunto
exposto nesta aula e propomos algumas atividades de reforço. As
referências bibliográficas fornecem material adicional de consulta,
caso você queira aprofundar-se mais sobre o conteúdo abordado na
aula de hoje.
3.6 Conclusão
Embora as valorações forneçam um modo elegante de definir
a semântica de proposições, as tabelas de verdade constituem um
método mais prático e visual de, também, definir a semântica de
proposições moleculares.
3.7 Resumo
Começamos definindo o conceito de valoração. A saber:
Definição: Seja Γ = {α1, . . . , αn} um conjunto com n proposições
atômicas. Definimos uma valoração sobre Γ como uma função
v : Γ 7→ {0, 1}.
Em seguida, vimos um tipo particular de álgebra definida sobre o
conjunto B = {0, 1} de valores de verdade, conhecida como álgebra
de Boole, e composta de três operações: uma soma, um produto e
um complementar, resumidos nas tabelas:
+ 0 1 • 0 1 *
0 0 1 0 0 0 0 1
1 1 0 1 0 1 1 0
Vimos que a álgebra de Boole permite definir de modo elegante e
conciso, a semântica dos conectivos lógicos, dada por:
48
Fundamentos da Matemática: Livro 1
3
AULA
Definição: Se α e β são proposições atômicas e v : {α, β} 7→
{0, 1} uma valoração então, a semântica para os conectivos lógicos
fica definida pelas valorações v(α) e v(β), das proposições α e β,
respectivamente, por:
• v(¬α) = v(α)∗
• v(α ∧ β) = v(α) • v(β)
• v(α ∨ β) = v(α) + v(β)
• v(α→ β) = v(α)∗ + v(β)
• v(α↔ β) = (v(α)∗ + v(β) • (v(α) + v(β)∗)
Que, para traçar a tabela de verdade, que resume todas as pos-
síveis valorações de uma proposição molecular, é útil o conceito de
subfórmula:
Definição: Uma subfórmula é definida pelas seguintes regras:
• se α é uma fórmula então α é uma subfórmula.
• se α, β e γ são fórmulas e α = ¬β, α = β ∧ γ, α = β ∨ γ,
α = β → γ ou α = β ↔ γ então β e γ são subfórmulas de α.
• Se x é uma variável e α = ∀xP (x) ou α = ∃xP (x) então
P (x) é subfórmula de α.
• Se β é subfórmula de α e γ é subfórmula de β então γ é
subfórmula de α.
• nada mais é subfórmula.
Que para traçar uma tabela de verdade para uma proposição mole-
cular usamos o seguinte algoritmo:
49
Valorações e Tabelas de Verdade
Passo 1 Contar o número n de símbolos proposicionais.
Passo 2 Montar uma tabela com 2n linhas e tantas colunas quan-
tas forem as subfórmulas da proposição p.
Passo 3 Preencher as colunas dos símbolos proposicionais com 1
ou 0 alternando de cima para baixo para a primeira coluna
1010..., para a segunda coluna 11001100..., para a terceira
coluna 1111000011110000... e assim por diante alternando
sempre em potências de 2.
Passo 4 computar o valor verdade das outras colunas usando as
a semântica dos conectivos lógicos.
Finalmente vimos as definições de tautologia, contradição e con-
tingência dadas por:
Definição: Uma fórmula molecular é dita uma tautologia, de-
notada > se, somente se seu valor de verdade é 1 verdade, para
qualquer combinação de valor de verdade de seus átomos
Definição: Uma fórmula molecular é dita uma contradição, de-
notada ⊥ se, somente se seu valor de verdade é 0 falso para qual-
quer combinação de valor de verdade de seus átomos
Definição: Uma fórmula molecular é dita uma contingência,
somente se não for uma tautologia nem uma contradição
3.8 Atividades
ATIV. 3.1. Construa a tabela de verdade para cada uma das
proposições moleculares abaixo:
• (α ∨ β) ∧ (α ∨ γ).
50
Fundamentos da Matemática: Livro 1
3
AULA
• α→ (β → γ).
Comentário: Reveja o algoritmo e exemplo da seção 3.4.
ATIV. 3.2. Verifique se cada uma das proposições moleculares
abaixo são tautologia, contradição ou contingência:
• (α↔ β) ∧ (β ↔ γ)→ (α↔ γ).
• (α ∧ β) ∨ (α ∧ γ).
• (α→ β) ∧ (α ∧ ¬β).
Comentário: Use a tabela de verdade para cada uma das proposi-
ções. Reveja o algoritmo e exemplo da seção 3.4
3.9 Referências Bibliográficas
MORTARI, Cezar Augusto. Introdução à Lógica. Editora UNESP.
São Paulo. 2001.
GASPAR, Marisa. Introdução à Lógica Matemática. Disponível
em: http:// mjgaspar.sites.uol.com.br/logica/logica. Acessado em
13/01/2007
ABAR, Celina. Noções de Lógica Matemática. Disponível em:
http://www. pucsp.br/∼logica/. Acessado em 13/01/2007
51
4
AULA
1
LIVRO
Regras de Inferência
e Regras de
Equivalência
META:
Introduzir algumas regras de
inferência e algumas regras de
equivalência.
OBJETIVOS:
Ao fim da aula os alunos deverão
ser capazes de:
Reconhecer se uma proposição é
uma regra de inferência;
Reconhecer se uma proposição é
uma regra de equivalência.
PRÉ-REQUISITOS
Aula-02 os conhecimentos da
semântica da Linguagem da Lógica
de Predicados.
Regras de Inferência e Regras de Equivalência
4.1 Introdução
Caro aluno, em nossas aulas anteriores, estabelecemos a lin-
guagem da lógica de predicados, conhecida também por lógica de
primeira espécie, estudamos como determinar a semântica de uma
proposição molecular usando tabelas de verdade. Aqui, daremos
um passo adiante, estudaremos as relações de equivalência e vere-
mos como usá-las na manipulação de proposição moleculares.
4.2 Regras de Equivalência
Começaremos nossa aula pela definição do que é uma regra deequivalência e em seguida, listaremos uma seqüência das principais
regras de equivalência da lógica de predicados. Vejamos:
Definição 4.1. Dizemos que uma fórmula α é semanticamente
equivalente a fórmula β, denotado α ≡ β, somente se α ↔ β for
uma tautologia.
Aqui temos algumas das principais regras de equivalência:
E01 α ∧ α ≡ α (Idempotência da conjunção).
E02 α ∨ α ≡ α (Idempotência da disjunção).
E03 α ∧ β ≡ β ∧ α (Comutativa da conjunção).
E04 α ∨ β ≡ β ∨ α (Comutativa da disjunção).
E05 (α ∧ β) ∧ γ ≡ α ∧ (β ∧ γ) (Associativa da conjunção).
E06 (α ∨ β) ∨ γ ≡ α ∨ (β ∨ γ) (Associativa da disjunção).
E07 α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ) (Distributiva da conjunção).
E08 α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ) (Distributiva da disjunção).
E09 ¬¬α ≡ α (Dupla negação).
54
Fundamentos da Matemática: Livro 1
4
AULA
E10 ¬(α ∧ β) ≡ ¬α ∨ ¬β (DeMorgan da conjunção).
E11 ¬(α ∨ β) ≡ ¬α ∧ ¬β (DeMorgan da disjunção).
E12 α→ β ≡ ¬α ∨ β (Implicação).
E13 α↔ β ≡ (α→ β) ∧ (β → α) (Dupla implicação).
Augustus De Morgan
nasceu em Madura,
na Índia, em 27 de
junho de 1806 - morreu
em Londres, 18 de
marco de 1871. Foi um
Matemático e Lógico
britânico. Formulou as
Leis de De Morgan e
foi o primeiro a tornar
rigorosa a idéia da
Indução Matemática.
Wikipedia
OBS 4.1. As propriedades comutativas e associativas da con-
junção e da disjunção significam que em uma proposição envol-
vendo só conjunções ou disjunções podemos dispensar o uso de
parênteses. Observamos também, que a dupla implicação também
possui propriedades comutativa e associativa. Por outro lado a
implicação não é comutativa (vide a propriedade contrapositiva)
nem associativa (vide propriedade da implicação).
OBS 4.2. As leis de De Morgan como o nome já indica foram
proposta pelo matemático inglês Augustus De Morgan e descrevem
como a negação é distribuída sobe a conjunção e sobre a disjunção.
OBS 4.3. Uma infinidade de outras regras de equivalência podem
ser propostas. As expostas acima são algumas das mais impor-
tantes, pois representam importantes propriedades dos conectivos
lógicos.
Da mesma forma definiremos primeiramente o que vem a ser uma
regra de inferência, para em seguida listar algumas das principais
regras de inferência da lógica de predicados. A saber:
Definição 4.2. Dizemos que uma fórmula β é semanticamente in-
ferida das fórmulas α1, . . . , αn, denotado α1, . . . , αn ` β se somente
se α1 ∧ · · · ∧ αn → β é uma tautologia.
Aqui temos algumas das principais regras de inferência:
I01 α, β ` α (Simplificação)
55
Regras de Inferência e Regras de Equivalência
I02 α ` α ∨ β (Adição)
I03 α, α→ β ` β (Modus pones)
I04 ¬β, α→ β ` ¬α (Modus Tollens)
I05 α→ β, β → γ ` α→ γ (Silogismo hipotético)
OBS 4.4. As regras de inferência, na lógica de predicados, são
infinitas. Porém, aqui listamos apenas algumas das mais impor-
tantes.
Completando as regras de inferência e de equivalência temos os
axiomas, sobre os quais a lógica de predicados é estabelecida. Axi-
omas são em si regras de inferências ou de equivalência tão especiais
que mereceram o status de axiomas isto é, proposições assumidas
como verdades absolutas. O conjunto de axiomas pode ter um ou
mais axiomas substituídos por outros. Mesmo o número de axi-
omas adotados pode variar dependendo da vontade, estilo ou telha
do Lógico Matemático que os propõe. Veremos aqui os axiomas
mais usuais. A saber:
A01 x = x Axioma da identidade.
A02 ((x = y) ∧ P (x)) ` P (y) Axioma da substituição.
A03 (α→ (β ∧ ¬β)) ` ¬α Axioma da não-contradição.
A04 (α→ β) ∧ (¬α→ β) ` β Axioma do terceiro excluído.
OBS 4.5. O axioma da identidade diz que qualquer objeto é igual
a si mesmo. Embora possa parecer óbvio que qualquer coisa é
igual a ela mesma, este objeto do conhecimento comum tem que
ser axiomatizado, visto que em Matemática não existe nada óbvio
56
Fundamentos da Matemática: Livro 1
4
AULA
tudo tem que ser provado, demonstrado ou axiomatizado isto é,
assumido como verdade.
OBS 4.6. O axioma da substituição, juntamente com o axioma da
identidade formam uma base sólida para muitas das demonstrações
em Matemática. Em particular o axioma da substituição diz que se
dois objetos matemáticos são iguais, onde aparecem uma instância
do primeiro, ela pode ser substituída pelo segundo.
OBS 4.7. O axioma da não-contradição cuida para que uma pro-
posição não possa ser provada dentro da lógica e que sua negação
também possa ser provada.
OBS 4.8. Um axioma do terceiro excluído, conhecido também
como axioma do meio termo excluído, diz que uma proposição
deverá ser ou falsa ou verdadeira, sendo vedado o direito de ser
falsa e verdadeira e também negado o direito de ser nem falsa nem
verdadeira. Estas duas proibições fincam a base da Matemática.
Porém, como a lógica é mais uma filosofia, desta forma a Lógica
Paraconsistente mantêm o princípio do terceiro excluído com ape-
nas a proibição de uma proposição ser nem falsa e nem verdadeira
e relaxando a proibição de ser falsa e verdadeira ao mesmo tempo.
Já a Lógica Paracompleta mantêm a proibição de uma proposição
ser falsa e verdadeira ao mesmo tempo, porém aceita que uma
proposição possa ser nem falsa e nem verdadeira.
Completando os axiomas acima, temos mais três esquemas de
axiomas. A saber:
A05 (α→ (β → α))
A06 ((α→ (β → γ))→ ((α→ β)→ (α→ γ)))
A07 ((¬β → ¬α)→ ((¬β → α)→ β))
57
Regras de Inferência e Regras de Equivalência
4.3 Subconjuntos Completos de Conectivos
O conceito de subconjunto completo de conectivos é importante
para quem deseja desenvolver a lógica de predicados de forma mais
compacta em seu aspecto sintático, porém ao diminuir a quanti-
dade de conectivos para representar uma dada proposição, aumen-
tamos drasticamente o número de parênteses que por sua vez é uma
complicação manter a paridade abre parêntese, fecha parêntese.
Definição 4.3. Denotamos e definimos o conjunto de conectivos
básicos da Lógica de Predicados por:
C = {¬,∧,∨,→,↔}
Definição 4.4. Seja A ⊂ C. Dizemos que A é completo, somente
se todos os conectivos de C poderem ser equivalentes a uma fór-
mula em que constem apenas conectivos de A.
Exemplo 4.1. A = {¬,∧,∨} é um conjunto completo de conec-
tivos.
PROVA:
01 α→ β ≡ ¬α ∨ β implicação
02 α↔ β ≡ (α→ β) ∧ (β → α) dupla implicação
03 α↔ β ≡ (¬α ∨ β) ∧ (¬β ∨ α) 1 em 2
Portanto, 1 e 3 garantem que A é um subconjunto completo de
conectivos de C. �
Vejamos também um segundo exemplo.
Exemplo 4.2. A = {¬,→} é um conjunto completo de conectivos.
58
Fundamentos da Matemática: Livro 1
4
AULA
PROVA:
01 α→ β ≡ ¬α ∧ β implicação
02 ¬α ∧ β ≡ α→ β α ≡ β ↔ β ≡ α
03 ¬¬α ∧ β ≡ ¬α→ β de 2 e α = ¬α
04 α ∧ β ≡ ¬α→ β de 3 e ¬¬α ≡ α
Antes de continuar com a prova é necessário uma nova inferência.
A saber: α ≡ β ` ¬α ≡ ¬β.
PROVA:
05 α ≡ β Premissa
06 α↔ β definição
07 (α→ β) ∧ (β → α) dupla implicação
08 (¬β → ¬α) ∧ (¬α→ ¬β) contrapositiva
09 (¬α→ ¬β) ∧ (¬β → ¬α) comut. da conjunção
10 ¬α↔ ¬β dupla implicação
11 ¬α ≡ ¬β definição
Podemos agora encontrar uma fórmula para disjunção. A saber:
12 ¬(α ∧ β) ≡ ¬(¬α→ β) aplicando 11 em 4
13 ¬α ∨ ¬β ≡ ¬(¬α→ β) De Morgan
14 ¬¬α ∨ ¬¬β ≡ ¬(¬¬α→ ¬β) α = ¬α e β = ¬β
15 α ∨ β ≡ ¬(α→ ¬β) ¬¬α ≡ α e ¬¬β ≡ β
Finalmente vamos encontrar uma fórmula para a dupla implicação.
A saber:
16 α↔ β ≡ (α→ β) ∧ (β → α) dupla implicação
17 α↔ β ≡ ¬(α→ β)→ (β → α) usando 4 em 16
Portanto, 4, 15 e 17 garantem que A é um subconjunto completo
de conectivos de C. �
Podemos também, definir novos conectivos partindo de um con-
junto completo de conectivos, como na tabela abaixo.
59
Regras de Inferência e Regras de Equivalência
Descrição Símbolo Definição do conectivo
Tautologia > α ∨ ¬α
Contradição ⊥ α ∧ ¬α
Ou excluusivo
�∨ (α ∧ ¬β) ∨ (¬α∧ β)
Não-e
−∧ ¬(α ∧ β)
Não-ou
−∨ ¬(α ∨ β)
Uma pergunta agora seria muito natural. Seria possível encontrar
um conjunto completo de conectivos com apenas um elemento?
A reposta é sim, e esses conectivos são chamados de “barras de
Sheffer” ou “conectivos de Sheffer”, definidos por:
Definição 4.5. Sejam α e β duas proposições atômicas. Defini-
mos os conectivos de Sheffer, denotados, α ↓ β e α|β, por:
α β α ↓ β α|β
1 1 0 0
0 1 0 1
1 0 0 1
0 0 1 1
OBS 4.9. Como ¬α ≡ α ↓ α e α ∧ β ≡ (α ↓ α) ↓ (β ↓ β) e
A = {¬,∧} é um conjunto completo. Logo B = {↓} é também um
conjunto completo.
OBS 4.10. Temos que, como ¬α ≡ α|α e α ∨ β ≡ (α|α)|(β|β) e
A = {¬,∨} é um conjunto completo. Logo B = {|} é também um
conjunto completo.
60
Fundamentos da Matemática: Livro 1
4
AULA
4.4 Conclusão
Ao final dessa aula, podemos concluir que é possível fazer a
Lógica de predicados com um número menor de conectivos, porém
resulta na complexidade das proposições geradas por estes novos
conjuntos de conectivos.
4.5 Resumo
Começamos por definir o que é uma regra de equivalência:
Definição: Dizemos que uma fórmula α é semanticamente equi-
valente a fórmula β, denotado α ≡ β, somente se α ↔ β for uma
tautologia.
Em seguida vimos vários tipos de regras de equivalência:
E01 α ∧ α ≡ α (Idempotência da conjunção).
E02 α ∨ α ≡ α (Idempotência da disjunção).
E03 α ∧ β ≡ β ∧ α (Comutativa da conjunção).
E04 α ∨ β ≡ β ∨ α (Comutativa da disjunção).
E05 (α ∧ β) ∧ γ ≡ α ∧ (β ∧ γ) (Associativa da conjunção).
E06 (α ∨ β) ∨ γ ≡ α ∨ (β ∨ γ) (Associativa da disjunção).
E07 α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ) (Distributiva da conjunção).
E08 α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ) (Distributiva da disjunção).
E09 ¬¬α ≡ α (Dupla negação).
E10 ¬(α ∧ β) ≡ ¬α ∨ ¬β (DeMorgan da conjunção).
E11 ¬(α ∨ β) ≡ ¬α ∧ ¬β (DeMorgan da disjunção).
E12 α→ β ≡ ¬α ∨ β (Implicação).
E13 α↔ β ≡ (α→ β) ∧ (β → α) (Dupla implicação).
Vimos também a definição de regras de inferência, dada por:
61
Regras de Inferência e Regras de Equivalência
Definição: Dizemos que uma fórmula β é semanticamente inferida
das fórmulas α1, . . . , αn, denotado α1, . . . , αn ` β se somente se
α1 ∧ · · · ∧ αn → β é uma tautologia.
E algumas poucas regras de inferência. A saber:
I01 α, β ` α (Simplificação)
I02 α ` α ∨ β (Adição)
I03 α, α→ β ` β (Modus pones)
I04 ¬β, α→ β ` ¬α (Modus Tollens)
I05 α→ β, β → γ ` α→ γ (Silogismo hipotético)
Vimos que a Lógica Matemática é baseada em alguns axiomas, que
são proposições tomadas como verdadeiras independentemente de
demonstrações. E um conjunto de axiomas pode ser dado por:
A01 x = x Axioma da identidade.
A02 ((x = y) ∧ P (x)) ` P (y) Axioma da substituição.
A03 (α→ (β ∧ ¬β)) ` ¬α Axioma da não-contradição.
A04 (α→ β) ∧ (¬α→ β) ` β Axioma do terceiro excluído.
Em seguida vimos a definição de conjunto completo de conectivos.
A saber:
Definição: Denotamos e definimos o conjunto de conectivos bási-
cos da Lógica de Predicados por: C = {¬,∧,∨,→,↔}
Definição: Seja A ⊂ C. Dizemos que A é completo, somente se
todos os conectivos de C poderem ser equivalentes a uma fórmula
em que constem apenas conectivos de A.
Finalmente vimos os conectivos de Sheffer, definidos pela tabela
de verdade abaixo:
Definição: Sejam α e β duas proposições atômicas. Definimos os
conectivos de Sheffer, denotados, α ↓ β e α|β, por:
62
Fundamentos da Matemática: Livro 1
4
AULA
α β α ↓ β α|β
1 1 0 0
0 1 0 1
1 0 0 1
0 0 1 1
4.6 Atividades
ATIV. 4.1. Mostre que A = {¬,∧} e A = {¬,∨} são conjuntos
completos de conectivos.
Comentário: Reveja os exemplos da seção 4.3
ATIV. 4.2. Considere os conectivos de Sheffer e mostre, usando
tabela de verdade, que:
• ¬α ≡ α ↓ α
• α ∧ β ≡ (α ↓ α) ↓ (β ↓ β)
• ¬α ≡ α|α
• α ∨ β ≡ (α|α)|(β|β)
Comentário: Reveja a aula anterior sobre tabelas de verdade.
4.7 Referências Bibliográficas
MORTARI, Cezar Augusto. Introdução à Lógica. Editora UNESP.
São Paulo. 2001.
GASPAR, Marisa. Introdução à Lógica Matemática. Disponível
em: http:// mjgaspar.sites.uol.com.br/logica/logica. Acessado em
13/01/2007
63
Regras de Inferência e Regras de Equivalência
ABAR, Celina. Noções de Lógica Matemática. Disponível em:
http://www. pucsp.br/∼logica/. Acessado em 13/01/2007
64
5
AULA
1
LIVRO
Teorias Axiomáticas
META:
Apresentar teorias axiomáticas.
OBJETIVOS:
Ao fim da aula os alunos deverão
ser capazes de:
Criar teorias axiomáticas;
Provar a independência dos axiomas
de uma teoria axiomática.
PRÉ-REQUISITOS
Aula-02 e Aula-04 os conhecimen-
tos da semântica da Linguagem
da Lógica de Predicados, das re-
gras de inferência e das regras de
equivalência .
Teorias Axiomáticas
5.1 Introdução
Caro aluno, em nossas aulas anteriores, estabelecemos a lin-
guagem da lógica de predicados, conhecida também por lógica de
primeira espécie. Vimos também como determinar a semântica de
uma proposição molecular usando tabelas de verdade. Estudamos
as relações de equivalência e vimos como usá-las na manipulação
de proposições moleculares. Na aula de hoje, dando continuidade
ao nosso estudo da Lógica, o assunto abordado será “Teorias Axi-
omáticas”.
Euclides, matemático
grego, nasceu em
Alexandria. Foi o
criador da famosa
geometria euclidiana.
Escreveu Stoichia
(Os elementos, 300
a.C.) composto de 13
livros: cinco sobre
geometria plana, três
sobre números, um
sobre a teoria das
proporções, um sobre
incomensuráveis e os
três últimos sobre
geometria no espaço.
Wikipedia
5.2 Sistemas Axiomáticos
O primeiro sistema axiomático conhecido é a Geometria Eu-
clidiana desenvolvida pelo Matemático grego Euclides. Embora
em uma forma rudimentar, a Geometria Euclidiana tem basica-
mente a mesma estrutura do que hoje denominamos de um sis-
tema axiomático. Seus críticos, no entanto, dizem que ela surgiu
da incapacidade de Euclides provar certas proposições da geome-
tria plana. Se isto é verdade ou não, não sabemos, mas o fato é que
a Geometria Euclidiana teve uma grande importância na história
do desenvolvimento da Matemática.
Definição 5.1. Um Sistema axiomático é uma estrutura consti-
tuída de:
• Termos indefinidos.
• Termos definidos a partir dos termos indefinidos.
• Proposições envolvendo os termos indefinidos e/ou os ter-
mos definidos, assumidas como verdadeiras e denominadas
66
Fundamentos da Matemática: Livro 1
5
AULA
axiomas.
OBS 5.1. Para os antigos filósofos gregos, um axioma era uma
reivindicação que poderia ser vista como verdadeira sem nenhuma
necessidade de prova.
OBS 5.2. Na Geometria Euclidiana, Euclides não faz uso de ter-
mos indefinidos. Por exemplo, definiu ponto como: “ponto é aquilo
que não tem dimensão”. No entanto esta definição é vazia, já que o
termo dimensão não foi por ele definido nem assumido como termo
indefinido. Dos três aspectos que definem uma teoria axiomática
apenas os termos definidos podem ser dispensáveis.
Definição 5.2. Um sistema axiomático é dito consistente somente
se, partindo de seus axiomas não podermos provar uma proposição
envolvendo seus termos definidos e/ou indefinidos e provar também
a sua negativa.
Definição 5.3. Um sistema axiomático é dito completo, somente
se for possível provar ou refutar qualquer proposição envolvendo
seus termos definidos e/ou indefinidos.
Definição 5.4. Um sistema axiomático é dito independente, so-
mente se cada um de seus axiomas não pode ser deduzido a partir
dos demais axiomas.
OBS 5.3. Kurt Goedel mostrou que um sistema axiomático pode
ter a propriedade de consistência ou de completude, nunca as
duas ao mesmo tempo. Das duas propriedades a mais impor-
tante para a Matemática é a consistência. Não é admissível poder,
em Matemática, provar queum teorema é ao mesmo tempo falso
67
Teorias Axiomáticas
e verdadeiro. Quanto a independência, alguns matemáticos ad-
mitem sistemas axiomáticos redundantes, cujos axiomas não são
independentes.
5.2.1 Exemplos de Alguns Sistemas Axiomáticos
Exemplo 5.1. Considere o seguinte sistema axiomático
• Termos Indefinidos
TI1 O conjunto A de “termos indefinidos um”
• Termos Definidos
TD1 O operador © : A×A 7→ A “operador um”
TD2 O operador � : A×A 7→ A “operador dois”
• Axiomas
A1 ∀a, b ∈ A, a© b = b© a
A2 ∀a, b, c ∈ A, (a© b)© c = a© (b© c)
A3 ∃x ∈ A|∀a ∈ A, a© x = a
A4 ∀a ∈ A,∃a∗ ∈ A|a© a∗ = x
A5 ∀a, b, c ∈ A, (a�b)�c = a�(b�c)
A6 ∀a, b, c ∈ A, a�(b© c) = (a�b)© (a�c), (b© c)�a =
(b�a)© (c�a)
68
Fundamentos da Matemática: Livro 1
5
AULA
Exemplo 5.2. Considere o seguinte sistema axiomático
• Termos Indefinidos
TI1 O conjunto A de “termos indefinidos um”, representados
por letras latinas maiúsculas
TI2 O conjunto a de “termos indefinidos dois”, representados
por letras latinas minúsculas
TI3 Uma relação de igualdade (=) entre os “termos indefinidos
um”
TI4 Uma relação binária (©) entre os “termos indefinidos
um” e os “termos indefinidos dois”
• Axiomas
A1 ∀A,B,¬(A = B),∃!x|A© x ∧B© x
A2 ∀x,∃A,B,¬(A = B)|A© x ∧B© x
A3 ∃x,∃A|¬(A© x)
Exemplo 5.3. Considere o seguinte sistema axiomático
• Termos Indefinidos
TI1 O conjunto A de “termos indefinidos um”, representados
por letras latinas maiúsculas
TI2 O conjunto a de “termos indefinidos dois”, representados
por letras latinas minúsculas
TI3 Uma relação de igualdade (=) entre os “termos indefinidos
um”
69
Teorias Axiomáticas
TI4 Uma relação binária (©) entre os “termos indefinidos
um” e os “termos indefinidos dois”
• Axiomas
A1 ∃A,B,C,¬(A = B),¬(A = C),¬(B = C)
A2 ∀A,∃!x|A© x
A3 ∀x,∃!A,B,¬(A = B)|A© x ∧B© x
Definição 5.5. Um modelo para um sistema axiomático é uma
estrutura bem definida que dá significado aos termos indefinidos e
satisfaz cada um de seus axiomas.
OBS 5.4. A existência de um modelo concreto para um sistema
axiomático prova a consistência do mesmo. Modelos servem tam-
bém para provar a independência dos axiomas de um sistema axi-
omático. Basta mostrar modelos em que cada um dos axiomas de
um sistema axiomático não é satisfeito, enquanto que os demais
são satisfeitos.
Vamos a alguns modelos para os sistemas axiomáticos exemplifi-
cados acima.
MODELO 5.1. Para o primeiro sistema axiomático, que em ál-
gebra define uma estrutura de anel, um modelo pode ser dado por
A = Z conjunto dos inteiros, © = + soma nos inteiros e � = •
produto nos inteiros. Os axiomas terão, então, os seguintes sig-
nificados: A1 propriedade comutativa da soma, A2 propriedade
associativa da soma, A3 existência do elemento neutro aditivo,
A4 existência do elemento simétrico A5 propriedade associativa
do produto e A6 propriedade distributiva.
70
Fundamentos da Matemática: Livro 1
5
AULA
OBS 5.5. Outros modelos envolvendo conjuntos numéricos
constituim-se em um anel como os racionais Q, os reais R e os
complexos C. Temos também em álgebra, muitos exemplos de
anéis finitos isto é, com um número finito de elementos.
MODELO 5.2. Para sistema axiomático do exemplo 2, conhecido
como primeira geometria da incidência, um modelo pode ser dado
por: A = {A,B,C} apenas três elementos, a = {{A,B}, {A,C}, {
B,C}} os três subconjuntos de A constituídos por dois elementos e
© =∈ a relação de pertinência, no sentido da teoria dos conjuntos.
Os axiomas são verificados por exaustão.
A1:
¬(A = B)→ ∃!x, x = {A,B}|A ∈ x ∧B ∈ x
¬(A = C)→ ∃!x, x = {A,C}|A ∈ x ∧ C ∈ x
¬(B = C)→ ∃!x, x = {B,C}|B ∈ x ∧ C ∈ x
Logo:
∀A,B,¬(A = B),∃!x|A© x ∧B© x
A2:
x = {A,B} → ∃A,B,¬(A = B)|A ∈ x ∧B ∈ x
x = {A,C} → ∃A,C,¬(A = C)|A ∈ x ∧ C ∈ x
x = {B,C} → ∃B,C,¬(B = C)|B ∈ x ∧ C ∈ x
Logo:
∀x,∃A,B,¬(A = B)|A© x ∧B© x
A3:
x = {B,C} → ¬(A ∈ x)
Logo:
∃x,∃A|¬(A© x)
Desta forma todos os três axiomas são satisfeitos pelo modelo.
OBS 5.6. Como foi possível encontrar um modelo para os sis-
71
Teorias Axiomáticas
temas axiomáticos dos exemplos 1 e 2, estes sistemas axiomáticos
são consistentes. Porém, o sistema axiomático do exemplo 3 é in-
consistente, desde que com três elementos é impossível satisfazer
os axiomas A2 e A3.
Caro aluno, por hoje é só. Mas como podemos perceber no decor-
rer de nossa aula, o conteúdo abordado exigiu um pouco mais de
atenção e dedicação para obtermos uma compreensão melhor, por
isso continuem estudando e releiam a aula o quanto for necessário.
Não abandone o lápis e o papel e procure repetir as argumentações
apresentadas
5.3 Conclusão
Na Matemática também é necessário acreditar em alguma coisa
e admiti-la como verdade sem nenhuma prova, isto é, são os Sis-
temas Axiomáticos que possiblitam a existência da Matemática
como a conhecemos hoje. Que, dos vários aspectos de uma teoria
axiomática a que mais importa para a Matemática é a sua con-
sistência.
5.4 Resumo
Começamos por estabelecer, via definição, o conceito de sis-
tema axiomático. A saber:
Definição: Um Sistema axiomático é uma estrutura constituída
de:
• Termos indefinidos.
• Termos definidos a partir dos termos indefinidos.
72
Fundamentos da Matemática: Livro 1
5
AULA
• Proposições envolvendo os termos indefinidos e/ou os ter-
mos definidos, assumidas como verdadeiras e denominadas
axiomas.
Em seguida definimos três importantes propriedades de sistemas
axiomáticos. A saber:
Definição: Um sistema axiomático é dito consistente, somente
se partindo de seus axiomas não podermos provar uma proposição
envolvendo seus termos definidos e/ou indefinidos e também provar
a sua negativa.
Definição: Um sistema axiomático é dito completo, somente se
for possível provar ou refutar qualquer proposição envolvendo seus
termos definidos e/ou indefinidos.
Definição: Um sistema axiomático é dito independente, somente
se cada um de seus axiomas não pode ser deduzido a partir dos
demais axiomas.
5.5 Atividades
ATIV. 5.1. Modifique os axiomas do exemplo 3 de modo que o
novo sistema axiomático, assim constituído, seja consistente.
Comentário: Volte ao texto e reveja o conceito de consistência.
ATIV. 5.2. Escreva um sistema axiomático com três axiomas e
proponha um modelo para o mesmo.
Comentário: Não é necessário provar nenhuma das propriedades
dos sistemas axiomáticos: independência, completude ou consistên-
cia.
ATIV. 5.3. Proponha um modelo para o sistema axiomático do
exemplo 2.
73
Teorias Axiomáticas
Comentário: Volte ao texto e reveja os exemplos.
5.6 Referências Bibliográficas
MORTARI, Cezar Augusto. Introdução à Lógica. Editora UNESP.
São Paulo. 2001.
GASPAR, Marisa. Introdução à Lógica Matemática. Disponível
em: http:// mjgaspar.sites.uol.com.br/logica/logica. Acessado em
13/01/2007
ABAR, Celina. Noções de Lógica Matemática. Disponível em:
http://www. pucsp.br/∼logica/. Acessado em 13/01/2007
74
6
AULA
1
LIVRO
Teoria da
Demonstração
META:
Introduzir os procedimentos
lógicos para uma demonstração
matemática.
OBJETIVOS:
Ao fim da aula os alunos deverão
ser capazes de:
Diferenciar de um teorema a
hipótese e a tese;
Aplicar as técnicas de demonstração
na prova de teoremas.
PRÉ-REQUISITOS
Aula-05 os conhecimentos de
sistemas axiomáticos.
Teoria da Demonstração
6.1 Introdução
Nas aulas anteriores, estabelecemos a linguagem da lógica de
predicados em seu aspecto sintático, conhecida também por lógi-
ca de primeira espécie. Estudamos também, como determinar a
semântica de uma proposição molecular. Fizemos um breve passeio
entre as regras de equivalência e das regras de inferência. Em
nossa