MDL-1-Logica-Matematica

Prévia do material em texto

19/04/2019
1
Universidade Federal do Maranhão
Departamento de Informática
Disciplina:
Matemática Discreta
e Lógica
Luciano Reis Coutinho, Prof.
lrc@deinf.ufma.br
2
 Lógica:
◦ Estudo dos princípios e métodos de raciocínio 
(processo de inferência) correto ou válido.
◦ Tipos: Dedutiva, Indutiva ou Abdutiva.
 Origens (Lóg. Dedutiva):
◦ Aristóteles (384-322 a.C): 
 “ORGANON”
 Lógica dos Silogismos (DEPRECATED!)
Lógica Matemática e Métodos de Prova
3
 Lógica:
◦ Estudo dos princípios e métodos de raciocínio 
(processo de inferência) correto ou válido.
◦ Tipos: Dedutiva, Indutiva ou Abdutiva.
 Origens (Lóg. Dedutiva):
◦ George Boole (1815-1864)
 “The Laws of Thought”
 Lógica (álgebra) Booleana;
 Origem da Lógica Matemática.
Lógica Matemática e Métodos de Prova
19/04/2019
2
4
 Lógica:
◦ Estudo dos princípios e métodos de raciocínio 
(processo de inferência) correto ou válido.
◦ Tipos: Dedutiva, Indutiva ou Abdutiva.
 Origens (Lóg. Dedutiva):
◦ Friedrich L. G. Frege (1848-1925)
 „Begriffsschrift“
 Predicados, Quantificadores;
 Origem da Lógica Formal.
Lógica Matemática e Métodos de Prova
5
 Evolução (Lóg. Dedutiva):
◦ Giuseppe Peano (1858-1932);
 “Arithmetices principia: nova methodo exposita”
◦ A. Whitehead (1861-1947) & B. Russell (1972-1970)
 “Principia Mathematica”
◦ Emil Leon Post (1897-1954)
 Introduction to a General Theory of Elementary Propositions
◦ D. Hilbert (1862-1943) & W. Ackermann (1896-1962)
 „ Grundzüge der Theoretischen Logik“
◦ Kurt Friedrich Gödel (1906-1978)
 „Die Vollständigkeit der Axiome des logischen 
Funktionenkalküls“
 „Über formal unentscheidbare Sätze der Principia Mathematica 
und verwandter Systeme, I.“
Lógica Matemática e Métodos de Prova
6
 Lógica Clássica (Dedutiva):
Lógica Matemática e Métodos de Prova
Lógica Silogística 
(Aristotélica)
Lógica Proposicional
(Álgebra de Boole)
Lógica de Predicados 
(1ª Ordem)
(2ª Ordem)
Teoria de Tipos
19/04/2019
3
7
 Importância
◦ Compreender o raciocínio matemático.
◦ Na computação:
 Projeto de circuitos eletrônicos,
 Análise de programas de computador,
 Construção de sistemas “inteligentes”,
 Consultas em bancos de dados,
 Etc.
Lógica Matemática e Métodos de Prova
8
 Lógica Proposicional
◦ Proposições
◦ Conectivos lógicos
◦ Tabelas-verdade
 Aplicações da Lógica
 Equivalências Proposicionais
 Predicados e Quantificadores
 Referência
◦ Rosen, K. H. (2009). Matemática Discreta e suas Aplicações 
(6th ed).
 Cap 1: Os fundamentos lógicos e demonstrações
Lógica Matemática e Métodos de Prova
9
 Blocos de construção básicos da Lógica:
◦ PROPOSIÇÕES
◦ CONECTIVOS 
 Uma proposição é uma sentença declarativa
(i.e., a declaração de um fato) que é de modo
exclusivo ou verdadeira, ou falsa.
Lógica Matemática e Métodos de Prova
19/04/2019
4
10
 D1 : Brasília é a capital do Brasil.
 D2 : 1 + 1 = 2
 D3 : 2 + 2 = 5
 D4 : Todo inteiro par maior que 2 pode ser 
expresso como a soma de dois primos.
Lógica Matemática e Métodos de Prova
11
 Algumas sentenças não são proposições:
◦ Q : Que horas são ? (interrogação)
◦ O : Leia as instruções. (ordem)
◦ E : Ola! (exclamação)
◦ D5 : 2+3 (sentença incompleta)
◦ D6 : x + 1 = 3 (sentença aberta)
◦ D7 : x + y = z (sentença aberta)
Lógica Matemática e Métodos de Prova
12
 Lógica Clássica (Aristotélica):
◦ Princípio da identidade: 
 Uma proposição verdadeira é verdadeira; uma 
proposição falsa é falsa.
◦ Princípio da Não-Contradição: 
 Nenhuma proposição poderá ser verdadeira e falsa ao 
mesmo tempo.
◦ Princípio do Terceiro Excluído: 
 Uma proposição ou será verdadeira, ou será falsa, não 
há outra possibilidade.
Lógica Matemática e Métodos de Prova
19/04/2019
5
13
 Letras--chamadas variáveis proposicionais--são
usadas para denotar proposições atômicas.
◦ Comumente usam-se letras minúsculas do fim do 
alfabeto:
 p, q, r, s, t, …
 Deste modo, variáveis proposicionais formam os 
átomos da linguagem da lógica proposicional.
 Proposições são então combinadas por meio de 
conetivos ou operadores lógicos para formar 
proposições compostas.
Lógica Matemática e Métodos de Prova
14
Sentença Afirmativa? Proposição? Atômica? Valor Lógico
Elefantes são 
maiores que ratos.
Sim Sim Sim VERDADEIRO
520 > 110
y > 5
Tchu biru biru bah.
Quem esta aí?
Está chovendo.
Lógica Matemática e Métodos de Prova
Sim Sim Sim VERDADEIRO
Sim
Não
Não
Sim Sim Sim
Não
15
Sentença Afirmativa? Proposição? Atômica? Valor Lógico
Hoje é janeiro E
10 > 11.
Se elefantes são 
verdes, então eles 
podem voar.
Não comprei uma 
caneta.
Hoje é quinta OU 
ontem foi quarta.
Ou hoje é quinta ou
ontem foi quarta.
Hoje é quinta E ontem 
não foi quarta.
x < y se e somente se 
y > x
Lógica Matemática e Métodos de Prova
Sim Sim Não FALSO
Sim Sim Não VERDADEIRO
Sim Sim Não FALSO
Sim Sim Não VERDADEIRO
Sim Sim Não FALSO
Sim Sim Não FALSO
Sim depende
19/04/2019
6
16
 Operadores Lógicos (ou Conectivos):
◦ Combinam proposições existentes (primitivas ou
não) formando novas proposições (compostas). 
Lógica Matemática e Métodos de Prova
17
 Tabela Verdade
◦ Esta tabela tem uma linha para cada valor verdade de uma
proposição p.
◦ Na coluna mais a direita, mostram-se os correspondentes
valores verdade da proposição composta ¬p. 
Lógica Matemática e Métodos de Prova
Outras notações
p
p’
~p
18
 Tabela Verdade
◦ p ∧ q é VERDADEIRO quando ambos p E q são
VERDADEIROs e é FALSO caso contrário.
Lógica Matemática e Métodos de Prova
[
Rato gosta de queijo (T) AND
a Lua é feita de queijo (F) 
] 
(FALSO)
19/04/2019
7
19
 Tabela Verdade
◦ p ∨ q é FALSO quando ambos p E q são FALSOs e é 
VERDADEIRO caso contrário.
Lógica Matemática e Métodos de Prova
[
Rato gosta de queijo (T) OR
a Lua é feita de queijo (F) 
]
(VERDADEIRO)
[
Assobio (T) OR
chupo cana (T) 
]
(VERDADEIRO)
OU
-inclusivo
20
 Tabela Verdade
◦ p ⊕ q é VERDADEIRO quando apenas um de p E q é 
VERDADEIRO e é FALSO caso contrário.
Lógica Matemática e Métodos de Prova
[
Rato gosta de queijo (T) XOR
a Lua é feita de queijo (F) 
]
(VERDADEIRO)
[
Assobio (T) XOR
chupo cana (T) 
]
(FALSO )
OU
-exclusivo
21
 Tabela Verdade
◦ p → q é FALSO quando p é VERDADEIRO e q é FALSO , e é 
VERDADEIRO caso contrário.
 p é chamada de Hipótese (ou antecedente, ou premissa).
 q é chamada de Conclusão (ou consequencia).
Lógica Matemática e Métodos de Prova
[IF
Rato gosta de queijo (T) THEN
a Lua é feita de queijo (F) 
]
(FALSO )
[IF
A Lua é feita de queijo (F) THEN
Rato gosta de queijo (T) 
]
(VERDADEIRO )
19/04/2019
8
22
 Terminologia:
◦ “Se p, então q” “Se p, q”
◦ “p implica q” “Quando p, q”
◦ “p somente/apenas se q”
◦ “p é (uma condição) suficiente para q”
◦ “q é (uma condição) necessária para p”
◦ “q se p” “q sempre que p”
◦ “q resulta de p” “q quando p”
◦ “q a menos que ¬p”
Lógica Matemática e Métodos de Prova
23
 Significado mais geral do que em Português
(Inglês)
 Por exemplo:
◦ Se fizer sol, então vou a praia!
◦ Intuitivamente, poderíamos imaginar que quando 
não faz sol, não vamos a praia!
◦ Mas essa interpretação nem sempre é correta:
 O condicional p→q é verdade mesmo quando não faz 
sol e efetivamente vamos a praia!
Lógica Matemática e Métodos de Prova
24
 Outro exemplo:
◦ Setenho um Ferrari, então 2 + 3 = 5”
 Neste caso, ficamos imaginado qual a relação de 
alguém ter uma Ferrari com um fato matemático 
verdadeiro!
◦ Na realidade não há relação alguma, e a sentença como 
um todo é verdadeira simplesmente porque o 
conseqüente é verdadeiro.
◦ Quer dizer, o condicional p→q independe ou não 
necessariamente expressa relação de causa-efeito.
Lógica Matemática e Métodos de Prova
19/04/2019
9
25
 Por fim:
◦ Linguagens de programação contêm comandos
 if p then S, 
onde p é uma proposição e S é um ou mais
comandos a serem executados. 
◦ Não confundir tais comandos com o condicional
p→q.
◦ No caso de if p then S há uma relação causa-efeito:
 S é executado se p for verdadeira, 
 Mas S nunca é executado quando p é falsa.
Lógica Matemática e Métodos de Prova
26
 Dado o condicional: p → q
 TÊM-SE:
◦ CONVERSO ou RECÍPROCO: q → p
◦ CONTRAPOSITIVO: ¬q → ¬p
◦ INVERSO ou CONTRÁRIO: ¬p → ¬q
 o condicional é EQUIVALENTE ao contrapositivo:
p → q ≡ ¬q → ¬p
 o converso é EQUIVALENTE ao contrário:
q → p ≡ ¬p → ¬q
Lógica Matemática e Métodos de Prova
27Lógica Matemática e Métodos de Prova
19/04/2019
10
28
 Exemplo:
◦ “Se chover, o time de casa ganha.”
 Contrapositivo
◦ “Se o time de casa não ganha, então não chove.”
 Converso
◦ “Se o time de casa ganha, então chove.”
 Inverso
◦ “Se não chove, então o time de casa não ganha.”
Lógica Matemática e Métodos de Prova
29
 Tabela Verdade
◦ p ↔ q é VERDADEIRO quando p E q têm os
mesmos valores, e FALSO caso contrário. 
 Bi-condicional ou bi-implicação.
Lógica Matemática e Métodos de Prova
[
Rato gosta de queijo (T) ↔
a Lua é feita de queijo (F) 
]
(FALSO )
[
A Lua é feita de queijo (F) ↔
Rato não gosta de queijo (F) 
]
(VERDADEIRO )
30
 Terminologia:
◦ “p é necessário e suficiente para q”,
◦ “se p então q, e vice-versa”,
◦ “p se e somente se q”,
◦ “p see q” , “p sse q”, “p iff q”. 
Lógica Matemática e Métodos de Prova
19/04/2019
11
31
 Equivalente a: (p → q) ∧ (q → p)
Lógica Matemática e Métodos de Prova
32
 Por exemplo:
◦ Se fizer sol, vou a praia.
◦ Se comer tudo, ganha a sobremesa.
 Nesses casos, em geral, o que realmente se quer
dizer é:
◦ Se, e somente se, fizer sol, vou a praia.
◦ Se, e somente se, comer tudo, ganha a sobremesa.
 Por causa desta imprecisão da linguagem natural, 
devemos analisar com cuidado e decidir quando um 
condicional implicitamente inclui seu converso. 
 Na matemática sempre se distingue o “se” do “se, 
somente se.”
Lógica Matemática e Métodos de Prova
33
 Proposições Atômicas
◦ Letras ou variável proposicionais: p, q, r, s, ...
 Conectivos
◦ Operadores Lógicos
Lógica Matemática e Métodos de Prova
α β ¬α α ∧ β α ∨ β α ⊕ β α → β α ↔β
V V F V V F V V
V F F F V V F F
F V V F V V V F
F F V F F F V V
19/04/2019
12
34
 Proposições (atômicas) e conectivos podem ser 
usadas para construir proposições mais complexas
(compostas).
◦ Expressões Proposicionais
◦ Fórmulas Proposicionais
 Definição (Fórmulas bem Formadas – wff)
◦ Toda letra proposicional p, q, r, s, … é uma fórmula;
◦ Se α é uma fórmula, então ¬α é uma fórmula;
◦ Se α e β são fórmulas, então as seguintes expressões também 
são fórmulas:
 (α ∧ β)
 (α ∨ β)
 (α ⊕ β)
 (α → β)
 (α ↔β)
Lógica Matemática e Métodos de Prova
35
 Podemos usar tabelas verdade para
determinar os valores verdade de tais
proposições compostas.
 Usamos colunas intermediárias para os
valores verdade de cada sub-expressão que
ocorre na proposição composta. 
 Os valores verdade da proposição composta
como um todo são registrados na coluna
mais a direita da tabela.
Lógica Matemática e Métodos de Prova
36
 Exemplo:
◦ Listar valores verdade de (p ∨ ¬q) →(p∧q)
Lógica Matemática e Métodos de Prova
19/04/2019
13
37
 Em geral, parênteses são
usados para especificar a 
ordem de aplicação dos 
operadores lógicos.
 No entanto, para reduzir
o número de parênteses
adota-se uma ordem de 
precedência para os
operadores.
Lógica Matemática e Métodos de Prova
38Lógica Matemática e Métodos de Prova
39Lógica Matemática e Métodos de Prova
19/04/2019
14
40Lógica Matemática e Métodos de Prova
41Lógica Matemática e Métodos de Prova
42Lógica Matemática e Métodos de Prova
19/04/2019
15
43Lógica Matemática e Métodos de Prova
44Lógica Matemática e Métodos de Prova
45
 Lógica Proposicional
◦ Proposições
◦ Conectivos lógicos
◦ Tabelas-verdade
 Aplicações da Lógica
 Equivalências Proposicionais
 Predicados e Quantificadores
 Referência
◦ Rosen, K. H. (2009). Matemática Discreta e suas Aplicações 
(6th ed).
 Cap 1: Os fundamentos lógicos e demonstrações
Lógica Matemática e Métodos de Prova
19/04/2019
16
46
 Muitas e importantes aplicações
◦ Matemática,
 Formalização de sentenças da linguagem natural
 Análise dos métodos de prova
◦ Ciência da Computação,
 Especificação de software e hardware
 Projeto de circuitos computacionais
 Criação de sistemas especialistas
 Definição de sistemas de busca
◦ Dentre outras.
Lógica Matemática e Métodos de Prova
47
 Objetivo:
◦ Remover imprecisão/ambiguidades
◦ Fazer análise lógica
 Tabelas verdade
 Raciocínio dedutivo
 Necessariamente, algumas suposições devem
ser feitas acerca do significado pretendido de 
sentenças em linguagem natural.
Lógica Matemática e Métodos de Prova
48
 Seja a sentença:
◦ “Voce pode acessar a Internet do campus apenas se você for um 
aluno de ciência da computação ou se você não é um calouro.”
 Tradução
◦ Identifique proposições atômicas e conectivos lógico;
 a ≡ “Você pode acessar a Internet do campus”
 g ≡ “Você é um aluno de ciência da computação” 
 c ≡ “Você é um calouro”
 Conectivos: “apenas se”, “ou” e “não”
◦ a → (g ∨ ¬c ) “apenas se” expressando condição necessária;
◦ (g ∨ ¬c ) → a “apenas se” expressando condição suficiente.
Lógica Matemática e Métodos de Prova
19/04/2019
17
49
 “Você não pode andar na montanha russa se voce 
tiver menos de 1,2m de altura a menos que você
tenha mais que 16 anos de idade.”
 Tradução
 r ≡ “Você pode andar na montanha russa”
 b ≡ “Você tem menos de 1,2m” 
 v ≡ “Você tem mais 16 anos”
 Conectivos: “se”, “a menos que”
◦ (b∧ ¬v) → ¬r “a menos que” como “e não”
Lógica Matemática e Métodos de Prova
50
 Engenheiros de sistemas devem ser capazes de 
traduzir requisitos escritos em linguagem natural 
para especificações não-ambíguas.
 Por exemplo:
◦ “A resposta automática não pode ser enviada quando o 
sistema de arquivos estiver cheio.”
 p ≡ “A resposta automática pode ser enviada”
 q ≡ “O sistema de arquivos está cheio”
 Conectivos: “não”, “quando”
◦ q → ¬p “quando” como condição suficiente
Lógica Matemática e Métodos de Prova
51
 Especificações devem ser consistentes
◦ Quer dizer, não devem conter requisitos conflitantes ou
contraditórios. 
 Considere os sequintes requisitos:
◦ “A mensagem de diagnóstico é armazenada no buffer ou
ela é retransmitida.”
◦ “A mensagem de diagnóstico não é armazenada no 
buffer.”
◦ “Se a mensagem de diagnóstico é armazenada no buffer, 
então ele é retransmitida.”
 Questão
◦ Estes requisitos são consistentes ??
Lógica Matemática e Métodos de Prova
19/04/2019
18
52
 Proposições atômicas:
◦ p ≡ “A mensagem de diagnóstico é armazenada no buffer”
◦ q ≡ “A mensagem de diagnóstico é retransmitida.” 
 A especificação pode ser escrita como:
◦ p ∨ q
◦ ¬p
◦ p → q
 Análise:
◦ p deve ser FALSO para que ¬p seja VERDADEIRO;
◦ Como p deve ser FALSO, p ∨ q só é verdadeirose q for VERDADEIRO;
◦ Por fim, p → q é VERDADEIRO quando p é FALSO e q é VERDADEIRO;
◦ Logo podemos concluir que a especificação é CONSISTENTE.
Lógica Matemática e Métodos de Prova
53Lógica Matemática e Métodos de Prova
p q p ∨ q ¬p p→ q
V V V F V
V F V F F
F V V V V
F F F V V
54
 Conectivos lógicos são amplamente utilizados para
realizar busca em coleções de informação.
◦ AND 
 Filtra registros que contêm dois (ou mais) termos, 
◦ OR
 Filtra registros que contêm ao menos um de dois (ou mais) 
termos,
◦ NOT 
 é usado para excluir um termo particular.
 Exemplos de Buscas
◦ São AND Luís AND Universidade
◦ (São AND Luís OR Teresina) AND Universidade
◦ (Teresina AND Universidade) NOT UFPI
Lógica Matemática e Métodos de Prova
19/04/2019
19
55
 Excelente maneira de praticar ou ilustrar o uso
das regras da lógica!
 Considere o seguinte (Smullyan 1978):
◦ Em uma ilha há dois tipos de habitantes,
 knights, que sempre falam a verdade,
 knaves, que sempre mentem.
◦ Você encontra duas pessoas A e B:
 A diz “B é um knight” 
 B diz “A e eu somos de tipos diferentes”
◦ Pergunta: qual o tipo de A e o tipo de B ?
Lógica Matemática e Métodos de Prova
56
 Sejam:
◦ p := A is a knight 
◦ q := B is a knight
 Primeiro, consideremos p como VERDADEIRA. 
◦ Se A é um knight, então ele diz a verdade quando afirma que B é um 
knight. Ou seja, q também deve ser VERDADEIRA, 
◦ Logo, A e B são do mesmo tipo: knights. 
◦ Mas, se B é um knight, então a afirmação de B dizendo que A e B são de 
tipos diferentes teria de verdadeira, o que contradiz a conclusão anterior 
de que A e B são ambos Knights.
◦ Consequentemente, podemos concluir que A não pode ser Knight.
 Se p é FALSA, ou seja, A é um knave, então
◦ Como knaves mentem, a afirmação de A sobre B ser um knight é falsa. 
◦ Isto significa que q é FALSA e B também é um knave.
◦ Agora, se B é um knave, então B mente ao dizer que A e B são de tipos
diferentes.
◦ Mas, isso é consistente com a conclusão de que ambos A e B são knaves. 
 Por fim, concluímos que A e B devem ser knaves.
Lógica Matemática e Métodos de Prova
57
 Lógica Proposicional pode ser aplicada ao
projeto de hardware de computador. 
 Um circuito lógico (ou circuito digital) recebe
um ou mais sinais de entrada [0 (off) ou 1 
(on)], e produz um ou mais sinais de saída. 
Lógica Matemática e Métodos de Prova
19/04/2019
20
58
 Circuitos complexos podem ser construídos a 
partir de três circuitos básicos chamados
portas lógicas: 
 Combinações destas três portas lógicas são
usadas para construir circuitos mais
complicados.
Lógica Matemática e Métodos de Prova
59Lógica Matemática e Métodos de Prova
p q r ¬q p∧¬q ¬r (p∧¬q)∨¬r
0 0 0 1 0 1 1
0 0 1 1 0 0 0
0 1 0 0 0 1 1
0 1 1 0 0 0 0
1 0 0 1 1 1 1
1 0 1 1 1 0 1
1 1 0 0 0 1 1
1 1 1 0 0 0 0
60
 Com relés:
Lógica Matemática e Métodos de Prova
19/04/2019
21
61Lógica Matemática e Métodos de Prova
in out
in
out
in
out
62
 Com relés
 Com válvulas
Lógica Matemática e Métodos de Prova
63
 Com relés
 Com válvulas
 Com transistores
 Circuitos integrados
Lógica Matemática e Métodos de Prova
19/04/2019
22
64
 Suponha que temos uma fórmula para a saída de um 
circuito digital em termos de negações, disjunções e 
conjunções. 
◦ (¬p ∧ q) ∨ (p ∧¬q)
 Podemos então construir um circuito digital da
seguinte maneira:
◦ Quebramos a fórmula em sub-fórmulas;
◦ Para cada sub-fórmula mais básica criamos o circuito
correspondente usando as portas lógicas adequadas;
◦ Ligamos os circuitos das sub-fórmulas respeitando a 
estrutura da fórmula global.
Lógica Matemática e Métodos de Prova
66
 (¬p ∧ q) ∨ (p ∧¬q)
 ¬p
 ¬q 
 (¬p∧ q)
 (p ∧¬q)
 (¬p ∧ q) ∨ (p ∧¬q)
Lógica Matemática e Métodos de Prova
¬pp
q
¬q
¬p∧q
p∧¬q
p∧¬q∨p ∧¬q
p
q
p⊕q
Porta XOR
p q (¬p ∧ q) ∨ (p ∧¬q)
0 0 0
0 1 1
1 0 1
1 1 0
67
 Tabuada
◦ 0 + 0 = 0
◦ 0 + 1 = 1
◦ 1 + 0 = 1
◦ 1 + 1 =10
◦ 0 + 0 = 00
◦ 0 + 1 = 01
◦ 1 + 0 = 01
◦ 1 + 1 = 10
Lógica Matemática e Métodos de Prova
19/04/2019
23
68
 Tabuada
◦ Ci a b Co S
◦ 0 + 0 + 0 = 0 0
◦ 0 + 0 + 1 = 0 1 
◦ 0 + 1 + 0 = 0 1 
◦ 0 + 1 + 1 = 1 0 
◦ 1 + 0 + 0 = 0 1
◦ 1 + 0 + 1 = 1 0 
◦ 1 + 1 + 0 = 1 0 
◦ 1 + 1 + 1 = 1 1 
Lógica Matemática e Métodos de Prova
69
 A = a
3
a
2
a
1
a
0
 B = b
3
b
2
b
1
b
0
-------------------------
 S = c s
3
s
2
s
1
s
0
Lógica Matemática e Métodos 
de Prova
a0 a1 a2 a3
b0 b1 b2 b3
s0 s1 s2 s3
c
70
 Exemplo
◦ C 1 1 1 0
◦ A = 1 0 1 1
◦ B = 0 1 1 0
◦ -----------
◦ S = 10 0 0 1
Lógica Matemática e Métodos de Prova
a0=1 a1=1 a2=0 a3=1
b0=0 b1=1 b2=1 b3=0
c=0
s0=1 s1=0 s2=0 s3=0
c=1 c=1
c=1
19/04/2019
24
71Lógica Matemática e Métodos de Prova
72Lógica Matemática e Métodos de Prova
73Lógica Matemática e Métodos de Prova
19/04/2019
25
74
◦ Em um determinado país, todos os habitantes são ou um 
contador de verdade que sempre fala a verdade ou 
mentirosos que sempre mentem. Viajando neste país, 
você encontra dois habitantes, Percival e Llewellyn. 
Percival diz "Se eu for um contador de verdades, 
Llewellyn também é um contador de verdades“. Percival 
é um mentiroso ou um contador de verdade? E 
Llewellyn?
◦ Represente por meio de portas lógicas as seguintes 
expressões proposicionais:
 p ∨ ¬q
 p ∧ ¬ (q ∨ r)
 p ∧ q ∧ r ∨ p ∧¬q ∧ r ∨ p ∧¬q∧¬r
Lógica Matemática e Métodos de Prova
75
 Lógica Proposicional
◦ Proposições
◦ Conectivos lógicos
◦ Tabelas-verdade
 Aplicações da Lógica
 Equivalências Proposicionais
 Predicados e Quantificadores
 Referência
◦ Rosen, K. H. (2009). Matemática Discreta e suas Aplicações 
(6th ed).
 Cap 1: Os fundamentos lógicos e demonstrações
Lógica Matemática e Métodos de Prova
76
 Uma operação importante na argumentação
matemática é a substituição de proposições
compostas por outras com a mesma tabela
verdade.
 Neste caso, as proposições envolvidas no 
processo de substituição são ditas
proposições equivalentes.
Lógica Matemática e Métodos de Prova
19/04/2019
26
77
 Def. (TAUTOLOGIA):
◦ Uma proposição composta que é SEMPRE VERDADEIRA, 
independentemente dos valores verdade das variáveis
proposicionais componentes é dita TAUTOLOGIA. 
 Def. (CONTRADIÇÃO):
◦ Uma proposição composta que é SEMPRE FALSA é 
chamada de CONTRADIÇÃO.
 Def. (CONTINGÊNCIA):
◦ Uma proposição composta que nem é uma tautologia, 
nem uma contradição, é dita CONTINGÊNCIA.
Lógica Matemática e Métodos de Prova
78
 Com apenas uma variável proposicional:
◦ p ∨ ¬p 
◦ p ∧ ¬p
Lógica Matemática e Métodos de Prova
79
 Com duas variáveis proposicionais:
◦ p ∧ q → p ∨ q
Lógica Matemática e Métodos de Prova
19/04/2019
27
80
 Com duas variáveis proposicionais
◦ [(p ∨ q)∧ ¬p] →q
Lógica Matemática e Métodos de Prova
81
 Com três variáveis proposicionais:
◦ p∧r → ¬q∨r
Lógica Matemática e Métodos de Prova
82
 Proposições compostas que têm os mesmos
valores verdade em todos os casos possíveis
são ditas logicamente equivalentes.
 Def. (EQUIVALÊNCIA)
◦ Duas proposições compostas P e Q são chamadas
de logicamente equivalentes se (P↔Q) for uma
tautologia.
 Obs.
◦ A notação P ≡ Q representa o fato de que P e Q 
são logicamente equivalentes.
Lógica Matemática e Métodos de Prova
19/04/2019
28
83
 Uma maneira de determinar equivalências é 
através das tabelas verdade de P e Q.
Lógica Matemática e Métodos de Prova
84Lógica Matemática e Métodosde Prova
 Uma maneira de determinar equivalências é 
através das tabelas verdade de P e Q.
85
 As leis de De Morgan são bastante úteis.
◦ Elas mostram como negar conjunções e disjunções:
 ¬(p ∨ q) ≡ ¬p ∧ ¬q
 ¬(p ∧ q) ≡ ¬p ∨ ¬q
 Exemplos
◦ A negação de
 “João foi ao cinema OU Maria ficou em casa”
◦ Fica
 “João NÃO foi ao cinema E Maria NÃO ficou em casa”
◦ A negação de
 “Sou flamengo E tenho uma nêga chamada Teresa”
◦ Fica
 “NÃO sou flamengo OU NÃO tenho nêga chamada Teresa”
Lógica Matemática e Métodos de Prova
19/04/2019
29
86Lógica Matemática e Métodos de Prova
87Lógica Matemática e Métodos de Prova
88Lógica Matemática e Métodos de Prova
19/04/2019
30
89Lógica Matemática e Métodos de Prova
90
 Mostre que ¬(p → q) ≡ p ∧ ¬q.
◦ ¬(p → q) ≡ ¬(¬p ∨ q) Eq. do condicional
◦ ≡ ¬(¬p) ∧ ¬q Lei de De Morgan
◦ ≡ p ∧ ¬q Dupla negação
Lógica Matemática e Métodos de Prova
91
 Mostre que ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q
◦ ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q)
◦ ≡ ¬p ∧ [¬(¬p) ∨ ¬q]
◦ ≡ ¬p ∧ (p ∨ ¬q)
◦ ≡ (¬p ∧ p) ∨ (¬p ∧ ¬q)
◦ ≡ F ∨ (¬p ∧ ¬q)
◦ ≡ (¬p ∧ ¬q) ∨ F
◦ ≡ ¬p ∧ ¬q
Lógica Matemática e Métodos de Prova
19/04/2019
31
92
 Mostre que (p ∧ q) → (p ∨ q) é uma
tautologia.
◦ (p ∧ q) → (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q)
◦ ≡ (¬p ∨ ¬q) ∨ (p ∨ q)
◦ ≡ (¬p ∨ p) ∨ (¬q ∨ q)
◦ ≡ T ∨ T
◦ ≡ T
Lógica Matemática e Métodos de Prova
93
 Além de tautologias e contradições, há as 
proposições contingentes.
 Tanto tautologias quanto contingências admitem 
atribuição de valores verdade para as proposições 
atômicas de tal modo que a proposição composta 
como um todo é verdadeira.
 Neste caso, se diz que a proposição composta é 
SATISFATÍVEL.
 Caso contrário, a proposição é dita INSATISFATÍVEL .
Lógica Matemática e Métodos de Prova
94
 Problema de Satisfatibilidade (SAT):
◦ Achar uma atribuição de valores verdades que torne 
a proposição composta verdadeira.
◦ Tal atribuição é dita SOLUÇÃO.
 Exemplos:
◦ (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p)
 SOLUÇÃO: p = T, q = T, r = T
◦ (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ 
(¬p ∨ ¬q ∨ ¬r) 
 Não hã SOLUÇÃO
Lógica Matemática e Métodos de Prova
19/04/2019
32
95
 Problemas em diversas áreas podem ser 
modelados em termos do problema de 
satisfatibilidade:
◦ Robótica, 
◦ Escalonamento de Tarefas,
◦ Projeto de circuitos integrados,
◦ Redes de computadores,
◦ Genética,
◦ e outros.
Lógica Matemática e Métodos de Prova
96
 De modo geral, o SAT pode ser resolvido por 
meio de tabelas verdade.
◦ No entanto, este não é um método prático!
◦ Por exemplo, para uma expressão com 20 variáveis
proposicionais há 220 = 1.048.576 linhas na tabela
verdade. 
◦ Para 100 variáveis:
 1267650600228229401496703205376
Lógica Matemática e Métodos de Prova
97
 O Fujitsu K computer (705.024 cores; 2011)
◦ 1010 MIPS ≡ 1010 * 106 = 1016 IPS
 Se cada instrução avaliasse uma linha:
◦ 126765060022822 , 9401496703205376
◦ Arredondando:
 126765060022823 SEGUNDOS
◦ Horas
 35212516673,00638888888888888889
◦ Dias
 1467188194,70859953703703703704
◦ Anos
 4019693,68413314941653982750
◦ Séculos
 40196,9368413314941653982750
◦ Milênios
 40,1969368413314941653982750
Lógica Matemática e Métodos de Prova
19/04/2019
33
98
 De modo geral, o SAT pode ser resolvido por 
meio de tabelas verdade.
◦ No entanto, este não é um método prático!
◦ Para 1000 variáveis:
 107150860718626732094842504906000181056140
481170553360744375038837035105112493612249
319837881569585812759467291755314682518714
528569231404359845775746985748039345677748
242309854210746050623711418779541821530464
749835819412673987675591655439460770629145
711964776865421676604298316526243868372056
68069376
Lógica Matemática e Métodos de Prova
99
 Não se conhece procedimento que possa
solucionar em tempo prático o problema SAT 
para um grande número de variáveis
proposicionais. 
◦ Problem NP-COMPLETO
 No entanto, há progressos na solução de tipos
particulares de SAT, e.g., a solução do Sudoku.
 Há várias algoritmos/programas já desenvolvidos
para resolver problemas SAT.
◦ https://en.wikipedia.org/wiki/Category:SAT_solvers
Lógica Matemática e Métodos de Prova
100Lógica Matemática e Métodos de Prova
19/04/2019
34
101Lógica Matemática e Métodos de Prova
102Lógica Matemática e Métodos de Prova
103
 Lógica Proposicional
◦ Proposições
◦ Conectivos lógicos
◦ Tabelas-verdade
 Aplicações da Lógica
 Equivalências Proposicionais
 Predicados e Quantificadores
 Referência
◦ Rosen, K. H. (2009). Matemática Discreta e suas Aplicações 
(6th ed).
 Cap 1: Os fundamentos lógicos e demonstrações
Lógica Matemática e Métodos de Prova
19/04/2019
35
104
 Há raciocínios na matemática e na linguagem 
natural que não podem ser adequadamente 
expressos na lógica proposicional.
 Por exemplo:
◦ Todo cachorro tem quatro patas.
◦ Eu sou um cachorro.
◦ Logo, eu tenho quatro patas.
◦ Eu tenho pulgas.
◦ Eu sou um cachorro.
◦ Logo, existe um cachorro pulguento.
 Tais raciocínios envolvem as noções:
◦ PREDICADOS
◦ QUANTIFICADORES
Lógica Matemática e Métodos de Prova
Penso 
logo existo.
105
 Aquilo que se atribui a algo.
◦ Propriedades
◦ Relações
 Proposição Predicativa
◦ “Eu sou um cachorro”
 Sujeito : “Eu”
 Predicado: “sou um cachorro”  PROPRIEDADE
◦ “O número 2 é par”
 Sujeitos : “o número 2”
 Predicado: “é par”  PROPRIEDADE
Lógica Matemática e Métodos de Prova
106
 Aquilo que se atribui a algo.
◦ Propriedades
◦ Relações
 Proposição Predicativa
◦ “2 é menor que 3”
 Sujeitos : “2”, “3”
 Predicado : “é menor que”  RELAÇÃO
Lógica Matemática e Métodos de Prova
19/04/2019
36
107
 Expressões como
◦ “x > 3,” 
◦ “x = y + 3,” 
◦ “x + y = z.”
◦ são sentenças abertas, sem valores verdade, pois as 
variáveis x, y e z são elementos indeterminados.
 Uma maneira de representar tais sentenças é 
através de Funções Proposicionais:
◦ Predicados atribuídos elementos não determinados 
x, y e z.
Lógica Matemática e Métodos de Prova
108
 “x > 3”
◦ Elemento não determinado : “x”
◦ Função Proposicional P(x) ≡ “x > 3”
◦ P(4) ≡ VERD.
◦ P(2) ≡ FALSO
 Função Proposicional
◦ P(x) : ELEM.  PROP.
Lógica Matemática e Métodos de Prova
Proposições Predicativas
109
 “x = y + 3”
◦ Elementos não determinados : “x”, “y”
◦ Função Proposicional Q(x,y) ≡ “x = y + 3”
◦ Q(4,1) ≡ VERD.
◦ Q(2,2) ≡ FALSO
 Função Proposicional
◦ Q(x,y) : ELEM.  ELEM.  PROP.
Lógica Matemática e Métodos de Prova
19/04/2019
37
110
 “x + y = z”
◦ Elementos não determinados : “x”, “y”, “z”
◦ Função Proposicional R(x,y,z) ≡ “x + y= z”
◦ R(4,1,5) ≡ VERD.
◦ R(2,2,5) ≡ FALSO
 Função Proposicional
◦ R(x,y,z) : ELEM.  ELEM.  ELEM.  PROP.
Lógica Matemática e Métodos de Prova
111
 Em geral, sentenças abertas envolvendo n 
variáveis podem ser denotadas por
◦ P(x1, x2, ..., xn).
◦ Para elementos particulares e1, e2, ..., en, a 
expressão P(e1, e2, ..., en) é uma proposição
predicativa, logo verdadeira ou falsa.
 A função proposicional P também é chamada
de predicado n-ário.
◦ O valor n é dito “aridade” de P.
Lógica Matemática e Métodos de Prova
112
 Quantificação
◦ Expressa a extensão de um dado domínio de elementos
sobre a qual um predicado é verdadeiro.
 Dois tipos básicos
◦ UNIVERSAL
 Predicado é verdadeiro para cada um dos elementos de um 
dado domínio.
◦ EXISTENCIAL
 Predicado é verdadeiro para um ou mais dos elementos do 
domínio.
 A Lógica que lidacom predicados e quantificadores é 
chamada de Lógica ou Cálculo de Predicados.
Lógica Matemática e Métodos de Prova
19/04/2019
38
113
 Quantificação Universal de P(x)
◦ “P (x) para todos os valores de x no domínio.”
 Domínio de Discurso (Universo de Discurso)
◦ Especifica os possíveis valores de das variáveis x.
 Notação: ∀xP(x)
◦ O símbolo ∀ é chamado de QUANTIFICADOR UNIVERSAL.
 Lê-se ∀xP(x) como:
◦ “para todo x P(x)” 
◦ “para cada x P(x)” 
 Um elemento do domínio para o qual P(x) seja
FALSO é dito um contra-exemplo de ∀xP(x).
Lógica Matemática e Métodos de Prova
114
 Seja a sentença aberta:
◦ P(x) := “se x > 0 então 0 < x”
 Domínio ℕ = {0, 1, 2, 3, ...}
◦ P(0) ≡ VERD.
◦ P(1) ≡ VERD.
◦ ...
◦ ∀xP(x) ≡ VERD.
Lógica Matemática e Métodos de Prova
115
 Seja a sentença aberta:
◦ Q(x) := “x < 2”
 Domínio ℕ = {0, 1, 2, 3, ...}
◦ Q(0) ≡ VERD.
◦ Q(1) ≡ VERD.
◦ Q(2) ≡ FALSO  CONTRA-EXEMPLO
◦ Q(3) ≡ FALSO  CONTRA-EXEMPLO
◦ ...
◦ ∀xP(x) ≡ FALSO
Lógica Matemática e Métodos de Prova
19/04/2019
39
116
 Geralmente, assume-se implicitamente que o 
universo de discurso não é vazio.
 Porém, se o domínio for vazio, então ∀xP(x) 
é VERDADEIRA para quaisquer funções
proposicionais P(x).
 A razão é que neste caso não há elementos x 
que sejam contra-exemplos de ∀xP(x).
Lógica Matemática e Métodos de Prova
117
 Quanto o domínio é finito
◦ D = {e1, e2, ..., en} 
 tem-se
◦ ∀xP(x) ≡ P (e1) ∧ P (e2) ∧ ··· ∧ P (en).
 Exemplo:
◦ “Todo computador do campus está conectado à 
Internet.”
Lógica Matemática e Métodos de Prova
118
 Saber o domínio realmente é importante.
 Qual o valor verdade de:
◦ ∀x(x2 ≥ x) ≡ ???
 Domínio ℝ
◦ ∀x(x2 ≥ x) ≡ FALSO
 Domínio ℤ
◦ ∀x(x2 ≥ x) ≡ VERD.
Lógica Matemática e Métodos de Prova
19/04/2019
40
119
 Quantificação existencial de P(x)
◦ “Existe elemento x no domínio tal que P(x).”
 Notação ∃xP(x)
◦ O símbolo ∃ é chamado de QUANTIFICADOR 
EXISTENCIAL
 Lê-se ∃xP(x) como
◦ “existe x tal que P(x)” 
◦ “há pelo menos um x tal que P(x)”
◦ “para algum x P(x)”
Lógica Matemática e Métodos de Prova
120Lógica Matemática e Métodos de Prova
121
 Seja a sentença aberta:
◦ P(x) := “x > 3”
 Domínio ℕ
◦ P(0) ≡ FALSO
◦ P(1) ≡ FALSO
◦ ...
◦ P(4) ≡ VERD.
◦ P(5) ≡ VERD.
◦ ...
◦ ∃xP(x) ≡ VERD.
Lógica Matemática e Métodos de Prova
19/04/2019
41
122
 Seja a sentença aberta:
◦ Q(x) := “x = x+1”
 Domínio ℕ
◦ Q(0) ≡ FALSO
◦ Q(1) ≡ FALSO
◦ ...
◦ Q(n) ≡ FALSO
◦ Q(n+1) ≡ FALSO
◦ ...
◦ ∃xQ (x) ≡ FALSO
Lógica Matemática e Métodos de Prova
123
 Geralmente, assume-se implicitamente que o 
universo de discurso não é vazio.
 Porém, se o domínio for vazio, então ∃xQ(x) 
é FALSA para quaisquer funções
proposicionais Q(x).
 A razão é que neste caso não há elementos x 
para os quais Q(x) seja verdadeira.
Lógica Matemática e Métodos de Prova
124
 Quanto o domínio é finito
◦ D = {e1, e2, ..., en} 
 tem-se
◦ ∃xP(x) ≡ P (e1) ∨ P (e2) ∨ ··· ∨ P (en).
 Exemplo:
◦ “Algum computador do campus está conectado à 
Internet.”
Lógica Matemática e Métodos de Prova
19/04/2019
42
125
 Outros quantificadores podem ser definidos:
◦ “Existe pelo menos 100 tal que ...”
◦ “Existe mais que 2 tal que ...”
◦ ...
 Quantificador de Unicidade
◦ “Existe um único x tal que P(x) seja VERDADEIRA”
 Notação
◦ ∃!x P(x)
◦ ∃1x P(x)
 Definição a partir de ∃ e ∀:
◦ ∃!x P(x) ≝ ∃x[ P(x) ∧ ∀y(P(y) → x=y) ] 
Lógica Matemática e Métodos de Prova
126
 Notação
◦ ∀x<0 (x2 > 0)
◦ ∃z >0 (z2 = 2)
 Tais sentenças têm a forma geral, e 
significam:
◦ ∀C(x) P(x) ≝ ∀x[C(x) →P(x)]
◦ ∃ C(z) Q(z) ≝ ∃z[C(z) ∧ P(x)]
 Logo
◦ ∀x<0 (x2 > 0) ≡ ∀x(x < 0 → x2 > 0)
◦ ∃z >0 (z2 = 2) ≡ ∃z(z > 0 ∧ z2 = 2)
Lógica Matemática e Métodos de Prova
127
 Os quantificadores ∀ e ∃ têm precedência
sobre todos os operadores proposicionais.
 Por exemplo ∀xP(x) ∨ Q(x) significa
◦ [∀xP (x)] ∨ Q(x)
ao invés de
◦ ∀x[P (x) ∨ Q(x)]
Lógica Matemática e Métodos de Prova
∀ e ∃ teriam precedência 0
19/04/2019
43
128
 Em uma expressão, quando um quantificador
é usado sobre uma variável x, diz-se que as 
ocorrências de x, no escopo do quantificador, 
são ligadas pelo quantificador.
 A ocorrência de uma variável que não é ligada
por um quantificador é dita ser livre.
 Em uma função proposicional P(x1,…,xn) as 
variáveis x1,…,xn devem ser variáveis livres.
Lógica Matemática e Métodos de Prova
129
 ∃x(x + y = 1)
◦ A variável x é ligada por ∃
◦ A variável y é livre (não-ligada)
◦ P(y) := ∃x(x + y = 1)
 ∃x(P(x) ∧ Q(x)) ∨ ∀x R(x)
◦ Todas as ocorrências de x são ligadas.
◦ Escopo do ∃x(...)
 P (x) ∧ Q(x)
◦ Escopo do ∀x...
 R(x)
◦ A expressão como um todo é uma Proposição, e não uma 
Função Proposicional.
Lógica Matemática e Métodos de Prova
130
 Sentenças com predicados e quatificadores
são logicamente equivalentes se, e somente
se, possuem o mesmo valor verdade, 
◦ não importando
 as interpretações dadas aos predicados,
 nem os domínios de discursos utilizados.
 Como na lógica proposicional, S ≡ T será
usada para denotar que duas sentenças S e T
da lógica de predicados são logicamente
equivalentes.
Lógica Matemática e Métodos de Prova
19/04/2019
44
131
 Considere a sentença:
◦ “Todo estudante de computação faz disciplina de 
cálculo.”
◦ Formalização
 Domínio : “estudantes de computação”
 Predicado C(x): “x faz disciplina de cálculo”
 ∀x C(x)
◦ Ou então:
 Domínio : “pessoas”
 Predicado E(x): “x é estudante de computação”
 ∀x [E(x) →C(x)]
Lógica Matemática e Métodos de Prova
132
 A sentença:
◦ “Todo estudante de computação faz disciplina de 
cálculo.”
◦ NÃO PODE ser formaliza como:
◦ ∀x [E(x) ∧ C(x)]
◦ Essa fórmula representa algo totalmente diferente:
 “Todo mundo é estudante e faz disciplina de cálculo.”
Lógica Matemática e Métodos de Prova
133
 A negação:
◦ ¬ ∀x C(x)
◦ ¬ ∀x [E(x) →C(x)]
◦ “NEM todo estudante de computação faz disciplina de 
cálculo”
 É equivalente a:
◦ “EXISTE estudante de computação que NÃO faz disciplina
de cálculo”
◦ ∃x ¬C(x)
◦ ∃x ¬[E(x) →C(x)] ≡ ∃x ¬[¬E(x) ∨ C(x)] 
◦ ≡ ∃x [E(x) ∧ ¬C(x)] 
Lógica Matemática e Métodos de Prova
19/04/2019
45
134
 Em suma:
◦ Não importanto, a interpretação dada à P(x), e nem
o domínio considerado:
 ∀x P(x) é falsa se, e apenas se, existir um elemento x 
do domínio para o qual P(x) é falsa.
 Ou seja, se somente se ∃x ¬P(x) é verdadeira. 
◦ Logo:
◦ ¬∀x C(x) ≡ ∃x ¬C(x)
◦ e
◦ ¬∀x [E(x) →C(x)] ≡ ∃x [E(x) ∧ ¬C(x)] 
Lógica Matemática e Métodos de Prova
135
 Considere a afirmativa:
◦ “Há um estudante de computação que passou no 
concurso.”
◦ Formalização
 Domínio : “estudantes de computação”
 Predicado C(x): “x passou no concurso”
 ∃x C(x)
◦ Ou então:
 Domínio : “pessoas”
 Predicado E(x): “x é estudante de computação”
 ∃x [E(x)∧C(x)]
Lógica Matemática e Métodos de Prova
136
 A sentença:
◦ “Há um estudante de computação que passou no 
concurso.”
◦ NÃO PODE ser formaliza como:
◦ ∃x [E(x) → C(x)]
◦ Pois essa fórmula é verdadeira mesmo não havendo
algum estudante de computação que tenha passado no 
concurso:
 Basta que haja uma pessoa que não seja estudante!
 Assim E(x) é falsa para essa pessoa e, consequentemente, 
E(x) → C(x) é verdadeira para algum x.
Lógica Matemática e Métodos de Prova
19/04/2019
46
137
 A negação:
◦ ¬ ∃x C(x)
◦ ¬ ∃x [E(x)∧C(x)]
◦ “NÃO há um estudante de computação que passou no 
concurso.”
 É equivalente a:
◦ “TODOestudante de computação NÃO passou no 
concurso.”
◦ ∀x ¬ C(x)
◦ ∀x ¬[E(x)∧C(x)] ≡ ∀x [¬E(x)∨¬C(x)]
◦ ≡ ∀x [E(x) → ¬C(x)]
Lógica Matemática e Métodos de Prova
138
 Em suma:
◦ Não importanto, a interpretação dada à P(x), e nem
o domínio considerado:
 ∃x P(x) é falsa se, e apenas se, não houver qualquer
elemento x do domínio para o qual P(x) seja verdade.
 Ou seja, se somente se ∀x ¬P(x) é verdadeira. 
◦ Logo:
◦ ¬∃x C(x) ≡ ∀x ¬C(x) 
◦ e
◦ ¬∃x [E(x)∧C(x)] ≡ ∀x [E(x) → ¬C(x)]
Lógica Matemática e Métodos de Prova
139
 Faça a negação de ∀x (x2 > x): 
◦ ¬∀x (x2 > x) ≡ ∃x ¬(x2 > x) 
◦ ≡ ∃x (x2 ≤ x) 
 Faça a negação de ∃x (x2 = 2)
◦ ¬∃x (x2 = 2) ≡ ∀x ¬(x2 = 2) 
◦ ≡ ∀x (x2 ≠ 2)
 Na Matemáticas as vezes se escreve
◦ ∄x... para expressar ¬∃x...
Lógica Matemática e Métodos de Prova
19/04/2019
47
140
 Especificação de Sistemas
◦ Req1
 “Todo e-mail maior que 1MB será compactada.”
◦ Formalização
 Domínio: qualquer elemento
 Predicados
 M(x) := x é um e-mail
 >(x,y):= x é maior que y
 C(x) := x será compactado
 Constante
 1MB
 ∀m [ M(m) → ( m > 1MB → C(m) ) ]
Lógica Matemática e Métodos de Prova
141
 Especificação de Sistemas
◦ Req2
 “Se um usuário está ativo, pelo menos um link de rede estará 
disponível.”
◦ Formalização de Req2
 Domínio : qualquer elemento
 Predicados
 S(x,y) := x está no estado y
 U(x) := x é um usuário
 L(x) := x é um link de rede
 Constantes
 ativo
 disponível
 ∃u [ U(u) ∧ S(u,ativo) ] → ∃l [ L(l) ∧ S(l,disponível) ]
Lógica Matemática e Métodos de Prova
142
◦ Todo cachorro tem quatro patas.
◦ Eu sou um cachorro.
◦ Logo, eu tenho quatro patas.
 Predicados
 C(x) := x é um cachorro
 Q(x) := x tem quatro patas
 Constantes
 eu
Lógica Matemática e Métodos de Prova
∀x [ C(x) → Q(x) ]
C(eu)
---------------
Q(eu)
19/04/2019
48
143
 Linguagem de Programação
◦ PROgramming in LOGic
◦ Inteligência Artificial
◦ Noções centrais
 Predicados
 Variáveis
 Constantes
 Fatos
 Regras
Lógica Matemática e Métodos de Prova
http://www.swi-prolog.org/
144
cachorro(rex).
cachorro(tob).
cachorro(dolly).
cachorro(baleia).
mae(baleia,rex).
mae(baleia,tob).
mae(dolly,baleia).
quatro_patas(X) :- cachorro(X).
irmao(X,Y) :- mae(Z,X), mae(Z,Y), X \= Y.
avo(X,Y) :- mae(X,Z), mae(Z,Y).
neto(X,Y) :- avo(Y,X).
Lógica Matemática e Métodos de Prova
145
 Considere as sentenças:
◦ “Todo mundo tem um melhor amigo.”
◦ “Em ℤ, todo número tem um inverso aditivo.”
 Como formalizá-las?
◦ ∀x ∃y Q(x,y)
 Domínio : Pessoas
 Q(x,y) := “y é o melhor amigo de x”
 Domínio : ℤ
 Q(x,y) := “( x + y = 0 )”
Lógica Matemática e Métodos de Prova
19/04/2019
49
146
 Em ∀x ∃y Q(x,y):
◦ O escopo de ∀x... é ∃y Q(x,y)
 Deste modo, diz-se que o ∃ ocorre ANINHADO ao ∀.
◦ A expressão como um todo é uma proposição composta.
◦ No entanto, 
 A sub-expressão ∃y Q(x,y) isoladamente é uma função 
proposicional pois nela a variável x é livre.
 Em ∃y Q(x,y):
◦ O escopo de ∃y... é Q(x,y)
◦ Q(x,y) é uma função proposicional pois as variáveis x e y 
são livres.
Lógica Matemática e Métodos de Prova
147
 ∀x∀y [(x > 0) ∧ (y < 0) → (xy < 0)],
◦ O que esta fórmula significa em ℝ?
◦ Resposta:
 Quando dois números reais
 o primeiro, um positivo qualquer
 o segundo, um negativo qualquer
 são multiplicados, o resultado necessariamente é um
número negativo.
Lógica Matemática e Métodos de Prova
148
 Possibilidades
◦ ∀x∀y Q(x,y)
◦ ∀y∀x Q(x,y)
◦ ∀x∃y Q(x,y)
◦ ∃x∀y Q(x,y)
◦ ∃x ∃y Q(x,y)
◦ ∃y ∃x Q(x,y)
Lógica Matemática e Métodos de Prova
19/04/2019
50
149
 Seja D = {e1, e2, ..., en} 
 Rotina avalia ∀x∀y Q(x,y)
para x := e1 até en faça
para y := e1 até en faça
se Q(x,y) ≡ FALSO 
retorne FALSO
fim_se
fim_para
fim_para
retorne VERDADEIRO
Lógica Matemática e Métodos de Prova
150
 Seja D = {e1, e2, ..., en} 
 Rotina avalia ∃x∃y Q(x,y)
para x := e1 até en faça
para y := e1 até en faça
se Q(x,y) ≡ VERDADEIRO
retorne VERDADEIRO
fim_se
fim_para
fim_para
retorne FALSO
Lógica Matemática e Métodos de Prova
151
 Rotina avalia ∀x∃y Q(x,y)
achou:= FALSO
para x := e1 até en faça
para y := e1 até en faça
se Q(x,y) ≡ VERDADEIRO
achou:= VERDADEIRO
break
fim_se
fim_para
se achou ≡ FALSO
retorna FALSO
senão
achou:= FALSO
fim_se
fim_para
retorne VERDADEIRO
Lógica Matemática e Métodos de Prova
19/04/2019
51
152
 Rotina avalia ∃x∀y Q(x,y)
achou:= VERDADEIRO
para x := e1 até en faça
para y := e1 até en faça
se Q(x,y) ≡ FALSO
achou:= FALSO
break
fim_se
fim_para
se achou ≡ VERDADEIRO
retorna VERDADEIRO
senão
achou:= VERDADEIRO
fim_se
fim_para
retorne FALSO
Lógica Matemática e Métodos de Prova
153
 Com quantificadores do mesmo tipo, a ordem 
não importa!
◦ A sentença
 “Para todos x e y, tem-se que x + y = y + x”
 Formalização
 ∀x∀y (x + y = y + x) ≡ ∀y∀x (x + y = y + x)
◦ A sentença
 “Existem x e y, tais que x + y = 1”
 Formalização
 ∃x∃y (x + y = 1) ≡ ∃y∃x (x + y = 1)
Lógica Matemática e Métodos de Prova
154
 No entanto, com quantificadores de tipos 
diferentes, a ordem é muito importante!
◦ Por exemplo, compare as duas fórmulas:
 ∃y∀x (x + y = 1)
 ∀x∃y (x + y = 1)
 ∃y∀x (x + y = 1)
◦ “Existe um valor y tal que, para todo x, x+y =1”
 Domínio ℝ
 ∃y∀x (x + y = 1) ≡ FALSO
 ∀x∃y (x + y = 1)
◦ “Para todo x, existe um valor y tal que x+y =1”
 Domínio ℝ
 ∀x∃y (x + y = 1) ≡ VERDADEIRO
Lógica Matemática e Métodos de Prova
19/04/2019
52
155
 Assim, em geral:
◦ ∃y∀x P(x,y) ≢ ∀x∃y P(x,y)
◦ No caso de ∃y∀x P(x,y),
 y é constante não dependente de x;
◦ No caso de ∀x∃y P(x,y),
 y pode variar dependendo de x.
 Todavia:
◦ ∃y∀x P(x,y) → ∀x∃y P(x,y)
Lógica Matemática e Métodos de Prova
156
 Considere a expressão
◦ “x + y = z”
◦ No domínio ℝ, analise o valor verdade de:
 ∀x∀y∃z (x+y=z) 
 ∃z∀x∀y (x+y=z) 
◦ ∀x∀y∃z (x+y=z) ≡ VERDADEIRO
 “Para todo x e y, existe z tal que x+y=z”
◦ ∃z∀x∀y (x+y=z) ≡ FALSO
 “Existe x tal que, para todo x e y, x+y=z”
Lógica Matemática e Métodos de Prova
157
 Define-se:
◦ Se, somente se, para todo ∊>0 existe um δ>0 tal que 
| f(x) – L | < ∊ quando 0 < |x-a| < δ.
 Formalização lógica:
◦ ≡ ∀∊>0 ∃δ>0 ∀x (
◦ 0<|x-a|<δ → |f(x)–L|<∊
◦ )
◦ ≡ ∀∊ {∊>0 → ∃δ [δ>0 ∧ ∀x (
◦ 0<|x-a|∧|x-a|<δ → |f(x)–L|<∊
◦ )]}
Lógica Matemática e Métodos de Prova
Lxf
ax


)(lim
Lxf
ax


)(lim
19/04/2019
53
158Lógica Matemática e Métodos de Prova
159Lógica Matemática e Métodos de Prova
160Lógica Matemática e Métodos de Prova
19/04/2019
54
161Lógica Matemática e Métodos de Prova
162Lógica Matemática e Métodos de Prova