Introdução à Lógica para Computação

Prévia do material em texto

Lo´gica para Computac¸a˜o
Lo´gica para Computac¸a˜o
Davi Romero de Vasconcelos
Universidade Federal do Ceara´ em Quixada´, Brasil
daviromero@ufc.br
26 de agosto de 2013
Lo´gica para Computac¸a˜o
Introduc¸a˜o
Lo´gica
O que e´ lo´gica?
“E´ o estudo (ou arte) do racioc´ınio”
“Estudo do Pensamento Correto e Verdadeiro”
“Tentativa de conceituac¸a˜o do Razoa´vel”
“E´ o estudo da (boa) argumentac¸a˜o”
O que e´ lo´gica matema´tica?
“E´ o estudo do tipo de racioc´ınio utilizado pelos matema´ticos”
Lo´gica para Computac¸a˜o
Introduc¸a˜o
Racioc´ınio
Se esta´ chovendo, enta˜o a rua esta´ molhada
Esta´ chovendo
A rua esta´ molhada
Se ϕ, enta˜o ψ
ϕ
ψ
Lo´gica para Computac¸a˜o
Introduc¸a˜o
Racioc´ınio
Todo homem e´ mortal
So´crates e´ um homem
So´crates e´ mortal
∀x(ϕ(x)→ ψ(x))
ϕ(s)
ψ(s)
Lo´gica para Computac¸a˜o
Introduc¸a˜o
Racioc´ınio
Se o trem tivesse chegado atrasado e na˜o houvesse ta´xi na
estac¸a˜o, enta˜o John se atrasaria para seu compromisso.
John na˜o se atrasou para seu compromisso.
O trem chegou atrasado.
Portanto, havia ta´xis na estac¸a˜o.
Se tivesse chovendo e Jane na˜o estivesse com seu
guarda-chuva, enta˜o ela se molharia.
Jane na˜o esta´ molhada.
Esta´ chovendo.
Portanto, Jane esta´ com seu guarda-chuva.
(ϕ ∧ ¬ψ)→ σ
¬σ
ϕ
ψ
Lo´gica para Computac¸a˜o
Introduc¸a˜o
Racioc´ınio
Raciocinar consiste na construc¸a˜o de um encadeamento de
entidades lingu´ısticas que seguem a relac¸a˜o “segue de”
As entidades lingu´ısticas no contexto das lo´gicas que sera˜o
apresentadas sa˜o as sentenc¸as declarativas, ou seja,
entidades que expressam um pensamento completo.
Esta´ chovendo
Todo homem e´ mortal
2 + 2 = 4
5 ∈ {2, 3, 5, 7}
O Corinthians e´ o melhor time do Brasil
Em geral, as sentenc¸as interrogativas (“Qual o pior time do
Brasil?”) e imperativas (“Tire nota DEZ!”) na˜o sa˜o objetos
de estudo da Lo´gica
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Alfabeto da Lo´gica Proposicional
Lo´gica Proposicional
Definic¸a˜o
O Alfabeto da Lo´gica Proposicional e´ constitu´ıdo de:
S´ımbolos de pontuac¸a˜o: ( e )
Um conjunto enumera´vel de s´ımbolos proposicionais:
P = {p0, p1, p2, . . .}
Conectivos proposicionais: ¬,∧,∨,→,↔, onde
o s´ımbolo ¬ (leˆ-se “NA˜O”) denota a negac¸a˜o
o s´ımbolo ∧ (leˆ-se “E”) denota a conjuc¸a˜o lo´gica
o s´ımbolo ∨ (leˆ-se “OU”) denota a disjunc¸a˜o lo´gica
o s´ımbolo → (leˆ-se “SE-ENTA˜O”) denota a implicac¸a˜o lo´gica
o s´ımbolo ↔ (leˆ-se “SE-SOMENTE-SE”) denota a
equivaleˆncia lo´gica
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
A Linguagem da Lo´gica Proposicional
A Linguagem da Lo´gica Proposicional
Definic¸a˜o
O conjunto LLP das fo´rmulas proposicionais e´ definido
indutivamente como o menor conjunto, satisfazendo as seguintes
regras de formac¸a˜o:
1 Caso Ba´sico: Todos os s´ımbolos proposicionais esta˜o em LLP ,
ou seja, P ⊆ LLP . Os s´ımbolos proposicionais sa˜o chamados
de fo´rmulas atoˆmicas, ou a´tomos
2 Caso Indutivo ¬: Se ϕ ∈ LLP , enta˜o (¬ϕ) ∈ LLP
3 Caso Indutivo ∧: Se ϕ,ψ ∈ LLP , enta˜o (ϕ ∧ ψ) ∈ LLP
4 Caso Indutivo ∨: Se ϕ,ψ ∈ LLP , enta˜o (ϕ ∨ ψ) ∈ LLP
5 Caso Indutivo →: Se ϕ,ψ ∈ LLP , enta˜o (ϕ→ ψ) ∈ LLP
6 Caso Indutivo ↔: Se ϕ,ψ ∈ LLP , enta˜o (ϕ↔ ψ) ∈ LLP
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
A Linguagem da Lo´gica Proposicional
A Linguagem da Lo´gica Proposicional
Exemplo
Sa˜o fo´rmulas de LLP :
p
(p ∧ q)
(p ∨ (¬p))
(p → (q → p))
Na˜o sa˜o fo´rmulas de LLP
pq
p∧
(p¬ ∧ q)
(p → (→ p))
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
A Linguagem da Lo´gica Proposicional
Linguagem-Objeto e Meta-Linguagem
Quando estudamos ingleˆs, dizemos sentenc¸as do tipo:
“I love Quixada´” e´ uma sentenc¸a com sujeito, verbo e objeto.
Neste caso a l´ıngua portuguesa (a meta-linguagem) e´ utilizada
para falar sobre sentenc¸as da l´ıngua inglesa (a
linguagem-objeto)
No caso da lo´gica, utilizamos uma linguagem natural, a
meta-linguagem, (e.g. portugueˆs) para estudarmos a
linguagem lo´gica, linguagem-objeto.
Tambe´m utilizamos meta-varia´veis, para expressarmos
proposic¸o˜es. Na definic¸a˜o de fo´rmulas utilizamos as
meta-varia´veis ϕ,ψ para expressarmos sentenc¸as.
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Provas por Induc¸a˜o
Provas por Induc¸a˜o sobre os naturais
Princ´ıpio de Induc¸a˜o Matema´tica
Seja A uma propriedade sobre os naturais, enta˜o A(n) para todo
inteiro n ≥ 1 se {
A(1)
∀k (A(k)⇒ A(k + 1))
Example
Para todo n ≥ 1, temos que
20 + 21 + 22 + . . .+ 2n = 2n+1 − 1
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Provas por Induc¸a˜o
Prova do Exemplo
Caso Ba´sico (n = 1):
20 + 21 = 21+1 − 1
1 + 2 = 22 − 1
3 = 4− 1
3 = 3
Passo Indutivo (n = k + 1):
20 + 21 + 22 + . . . + 2k+1 = 2k+1+1 − 1 (1)
Hipo´tese de Induc¸a˜o (HI):
20 + 21 + 22 + . . . + 2k = 2k+1 − 1 (2)
20 + 21 + 22 + . . . + 2k + 2k+1
= 2k+1 − 1 + 2k+1, por HI
= 2(2k+1)− 1
= 2k+1+1 − 1
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Provas por Induc¸a˜o
Provas por Induc¸a˜o sobre as estruturas das fo´rmulas
Princ´ıpio de Induc¸a˜o
Seja A uma propriedade, enta˜o A(ϕ) para toda fo´rmula ϕ ∈ LLP se
A(pi ),∀pi ∈ P
A(ϕ)⇒ A((¬ϕ))
A(ϕ),A(ψ)⇒ A((ϕ�ψ)), onde � ∈ {∧,∨,→,↔}
Example
Para toda fo´rmula ϕ ∈ LLP , temos que
O nu´mero de pareˆnteses de ϕ e´ par
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Provas por Induc¸a˜o
Prova do Exemplo
Caso Ba´sico (pi ): Cada a´tomo tem 0 pareˆnteses e 0 e´ par
Passo Indutivo ((¬ϕ)):
Hipo´tese de Induc¸a˜o (HI):
Suponha que ϕ tenha 2n
(¬ϕ) tem 2 + 2n = 2(n + 1)
Passo Indutivo ((ϕ�ψ)):
Hipo´tese de Induc¸a˜o (HI):
Suponha que ϕ,ψ tenham 2n e 2m pareˆnteses,
respectivamente
(ϕ�ψ) tem 2 + 2n + 2m = 2(1 + n + m)
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Provas por Induc¸a˜o
Example
p∧ 6∈ LLP
Demonstrac¸a˜o.
Suponha que p∧ ∈ X e X satisfaz todos os itens da Definic¸a˜o 2.
Da´ı iremos provar que Y = X \ {p∧} tambe´m satisfaz todos os
itens.
Caso Ba´sico: como pi ∈ X , temos que pi ∈ Y .
Caso ¬: temos que se ϕ ∈ Y , enta˜o ϕ ∈ X . Como X satisfaz
item ¬, temos que (¬ϕ) ∈ X . Da forma das expresso˜es
(¬ϕ) 6= p∧, assim (¬ϕ) ∈ X\{p∧} = Y .
Os outros casos sa˜o semelhantes.
Da´ı temos que X na˜o e´ o menor conjunto que satisfaz todos os
itens da Definic¸a˜o 2. Logo, p∧ na˜o pode pertencer a LLP .
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Definic¸o˜es Recursivas
Definic¸o˜es Recursivas
Em matema´tica e em computac¸a˜o usualmente definimos func¸o˜es por
recursa˜o. Por exemplo, o fatorial e´ definido por
n! =
{
1, se n = 0
n ∗ (n − 1)!
Em lo´gica temos um princ´ıpio similar na nossa sintaˆxe. Por exemplo, o
nu´mero f (ϕ) de pareˆnteses de ϕ pode ser definido como segue:
f (ϕ) = 0, para ϕ atoˆmico
f ((¬ϕ)) = f (ϕ) + 2
f ((ϕ�ψ)) = f (ϕ) + f (ψ) + 2
f ((p → (q → p))) =
= f (p) + f ((q → p)) + 2
= f (p) + f (q) + f (p) + 2 + 2
= 4
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
O tamanho ou complexidade |ϕ| de ϕ e´ definido por
|ϕ| = 1, para ϕ atoˆmico
|(¬ϕ)| = |ϕ|+ 1
|(ϕ�ψ)| = |ϕ|+ |ψ|+ 1
|(p → (q → p))| =
= |p|+ |(q → p)|+ 1
= |p|+ |q|+ |p|+ 1 + 1
= 5
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
O conjunto Subf de subfo´rmulas de ϕ e´ definido por
Subf (ϕ) = {ϕ}, para ϕ atoˆmico
Subf ((¬ϕ)) = Subf (ϕ) ∪ {(¬ϕ)}
Subf ((ϕ�ψ)) = Subf (ϕ) ∪ Subf (ψ) ∪ {(ϕ�ψ)}
Subf ((p → (q → p))) =
= Subf (p) ∪ Subf ((q → p)) ∪ {(p → (q → p))}
= {p} ∪ Subf (q) ∪ Subf (p) ∪ {(q → p)} ∪ {(p → (q → p))}
= {p} ∪ {q} ∪ {p} ∪ {(q → p)} ∪ {(p → (q → p))}
= {p, q, (q → p), (p → (q → p))}
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Definic¸o˜es Recursivas
Definic¸o˜es Recursivas
Teorema (Definic¸a˜o por Recursa˜o)
Dados os mapeamentos Hp : P → A, H¬ : A→ A e
H� : A× A→ A, enta˜o existe exatamente um mapeamento
F : LLP → A tal que
F (ϕ) = Hp(ϕ), para ϕ atoˆmico
F ((¬ϕ)) = H¬(F (ϕ))
F ((ϕ�ψ)) = H�(F (ϕ),F (ψ))
Lo´gica para Computac¸a˜o
Lo´gica Proposicional
Definic¸o˜esRecursivas
Definic¸o˜es Recursivas
Example
Considere as seguintes func¸o˜es:
Hp : P → N, onde Hp(pi ) = 0, para toda proposic¸a˜o pi ∈ P.
H¬ : N→ N, onde H¬(x) = x + 2.
H� : N× N→ N, onde H�(x , y) = x + y + 2
Aplicando o teorema da definic¸a˜o recursiva, temos a definic¸a˜o da
func¸a˜o F : LLP → N que calcula o nu´mero de pareˆnteses de uma
fo´rmula:
F (pi ) = Hp(pi ) = 0
F ((¬ϕ)) = H¬(F (ϕ)) = F (ϕ) + 2
F ((ϕ�ψ)) = H�(F (ϕ),F (ψ)) = F (ϕ) + F (ψ) + 2
Lo´gica para Computac¸a˜o
Especificac¸a˜o de Problemas em Lo´gica
Especificac¸a˜o de Problemas em Lo´gica
A lo´gica pode ser utilizada para representar (parte) do mundo,
ou seja, podemos especificar fatos acerca do mundo na
linguagem lo´gica
Podemos utilizar a lo´gica para “raciocinar”atrave´s de sua
relac¸a˜o de consequ¨eˆncia lo´gica (|=)
Mundo
Racioc´ınio
Conclusa˜o
Fo´rmulas Lo´gicas
especifica-se
=⇒
Fo´rmula
especifica-se
=⇒
|=
Lo´gica para Computac¸a˜o
Especificac¸a˜o de Problemas em Lo´gica
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Na lo´gica proposicional, utilizamos os s´ımbolos proposicionais
para representar as sentenc¸as declarativas, tais como:
A sentenc¸a “esta´ chovendo”pode ser representada pelo a´tomo
p
A sentenc¸a “a rua esta´ molhada”pode ser representada pelo
a´tomo q
Na lo´gica podemos utilizar os conectivos lo´gicos para formar
sentenc¸as mais complexas, a exemplo:
A sentenc¸a “Se esta´ chovendo, enta˜o a rua esta´ molhada”e´
representada pela fo´rmula (p → q)
Lo´gica para Computac¸a˜o
Especificac¸a˜o de Problemas em Lo´gica
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Expressa˜o em Portugueˆs Conectivo Fo´rmula
e; mas; tambe´m; alem disso ∧ (A ∧ B)
ou ∨ (A ∨ B)
Se A, enta˜o B → (A→ B)
A implica B
A, logo B
A so´ se B; A somente se B
B segue de A
A e´ uma condic¸a˜o suficiente para B; basta A para B
B e´ uma condic¸a˜o necessa´ria para A
A se e somente se B ↔ (A↔ B)
A e´ condic¸a˜o necessa´ria e suficienta para B
na˜o A ¬ (¬A)
E´ falso que A
Na˜o e´ verdade que A
Lo´gica para Computac¸a˜o
Especificac¸a˜o de Problemas em Lo´gica
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Exemplo
1 O Corinthians e´ o melhor time e ele tem a maior torcida
“O Corinthians e´ o melhor time”representado por P
“O Corinthians tem a maior torcidal”representado por Q
(P ∧ Q)
2 O Corinthians tem a maior torcida e ele e´ o melhor time do
Brasil
“O Corinthians tem a maior torcida”representado por Q
“O Corinthians e´ o melhor time”representado por P
(Q ∧ P)
Lo´gica para Computac¸a˜o
Especificac¸a˜o de Problemas em Lo´gica
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Exemplo
1 O processador e´ ra´pido, mas a impressora e´ lenta
“O processador e´ ra´pido”representado por P
“A impressora e´ lenta”representado por Q
(P ∧ Q)
2 O processador e´ ra´pido ou a impressora e´ lenta
“O processador e´ ra´pido”representado por P
“A impressora e´ lenta”representado por Q
(P ∨ Q)
Lo´gica para Computac¸a˜o
Especificac¸a˜o de Problemas em Lo´gica
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Exemplo
1 Uma condic¸a˜o suficiente para a falha de uma rede ele´trica e´
que a chave central desligue
“Chave central deligue”representado por P
“Falha de uma rede ele´trica”representado por Q
(P → Q)
2 E´ falso que Joa˜o seja alto
“Joa˜o e´ alto”representado por P
(¬P)
Lo´gica para Computac¸a˜o
Especificac¸a˜o de Problemas em Lo´gica
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Especificac¸a˜o de Problemas em Lo´gica Proposicional
Exemplo
A negac¸a˜o de Joa˜o e´ alto e magro pode ser expressa da seguinte
forma:
1 E´ falso que Joa˜o seja alto e magro
“Joa˜o e´ alto”representado por P
“Joa˜o e´ magro”representado por Q
¬(P ∧ Q)
2 Joa˜o na˜o e´ alto ou na˜o e´ magro
“Joa˜o e´ alto”representado por P
“Joa˜o e´ magro”representado por Q
((¬P) ∨ (¬Q))
Lo´gica para Computac¸a˜o
Especificac¸a˜o de Problemas em Lo´gica
Conectivos em Linguagem Natutal versus em Lo´gica Proposicional
Conectivos em Linguagem Natutal versus em Lo´gica
Proposicional
Os Conectivos podem ter mais de um significado em linguagem
natural
1 Joa˜o dirigiu e atropelou um pedestre (JD ∧ JAP)
2 Joa˜o atropelou um pedestre e dirigiu (JAP ∧ JD)
3 Se eu abrir a janela, enta˜o teremos ar fresco (AJ → AF )
4 Se eu abrir a janela, enta˜o 1 + 3 = 4 (AJ → E )
5 Joa˜o esta´ trabalhando ou ele esta´ em casa (JT ∨ JC )
6 Euclides era um Grego ou um matema´tico (EG ∨ EM)
Lo´gica para Computac¸a˜o
Especificac¸a˜o de Problemas em Lo´gica
Conectivos em Linguagem Natutal versus em Lo´gica Proposicional
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Exemplo
(Problema do Vestido) Treˆs irma˜s - Ana, Maria e Cla´udia - foram a
uma festa com vestidos de cores diferentes. Uma vestia azul, a
outra branco e a terceira preto. Chegando a` festa, o anfitria˜o
perguntou quem era cada uma delas. A resposta foi como segue:
A de azul respondeu: “Ana e´ que esta´ de branco”
A de branco falou: “Eu sou Maria”
A de preto disse: “Cla´udia e´ quem esta´ de branco”
O anfitria˜o foi capaz de identificar corretamente quem era cada pessoa
considerando que:
Ana sempre diz a verdade
Maria a`s vezes diz a verdade
Cla´udia nunca diz a verdade
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Semaˆntica da Lo´gica Proposicional
A semaˆntica da lo´gica cla´ssica proposicional consiste na
atribuic¸a˜o de significado a`s fo´rmulas da linguagem.
Atribuic¸a˜o de valores verdade para fo´rmulas, onde verdadeiro
e falso sa˜o representados por 1 e 0, respectivamente.
O valor de verdade de uma fo´rmula depende unicamente dos
valores verdade atribu´ıdos aos a´tomos.
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Semaˆntica da Lo´gica Proposicional
Definic¸a˜o
Seja v : P → {0, 1} uma func¸a˜o de valorac¸a˜o que mapeia os s´ımbolos atoˆmicos
em um valor verdade. Define-se v¯ : LLP → {0, 1} como segue:
1 v¯(P) = v(P).
2 v¯((¬ϕ)) =
{
1, se v¯(ϕ) = 0
0, caso contra´rio
3 v¯((ϕ ∧ ψ)) =
{
1, se v¯(ϕ) = 1 E v¯(ψ) = 1
0, caso contra´rio
4 v¯((ϕ ∨ ψ)) =
{
1, se v¯(ϕ) = 1 OU v¯(ψ) = 1
0, caso contra´rio
5 v¯((ϕ→ ψ)) =
{
1, se v¯(ϕ) = 0 OU v¯(ψ) = 1
0, caso contra´rio
6 v¯((ϕ↔ ψ)) =
{
1, se v¯(ϕ) = v¯(ψ)
0, caso contra´rio
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Semaˆntica da Lo´gica Proposicional
Definition
A definic¸a˜o da func¸a˜o de valorac¸a˜o pode ser dada pela tabela
abaixo.
v¯(ϕ) v¯(ψ) v¯((¬ϕ)) v¯((ϕ ∧ ψ)) v¯((ϕ ∨ ψ)) v¯((ϕ→ ψ)) v¯((ϕ↔ ψ))
1 1 0 1 1 1 1
1 0 0 0 1 0 0
0 1 1 0 1 1 0
0 0 1 0 0 1 1
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Semaˆntica da Lo´gica Proposicional
Exemplo
1 “O processador e´ ra´pido”representado por P
2 “A impressora e´ lenta”representado por Q
3 Sejam v(P) = 1 e v(Q) = 1. Da´ı, o valor verdade de
O processador e´ ra´pido, mas a impressora e´ lenta
v¯((P ∧ Q)) = 1
O processador e´ ra´pido ou a impressora e´ lenta
v¯((P ∨ Q)) = 1
4 Sejam v(P) = 0 e v(Q) = 1. Da´ı, o valor verdade de
O processador e´ ra´pido, mas a impressora e´ lenta
v¯((P ∧ Q)) = 0
O processador e´ ra´pido ou a impressora e´ lenta
v¯((P ∨ Q)) = 1
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Especificac¸a˜o em Linguagem Proposicional
Exemplo
Utilize os s´ımbolos proposicionais C para “esta´ chovendo”e N para
“esta´ nevando”. Especifique as sentenc¸as abaixo em lo´gica
proposicional.
1 Esta´ chovendo, mas na˜o esta´ nevando.
2 Na˜o e´ o caso que esta´ chovendo ou nevando.
3 Se na˜o esta´ chovendo, enta˜o esta´ nevando.
4 Na˜o e´ o caso que se esta´ chovendo enta˜o esta´ nevando.
5 Esta´ chovendo se e somente se esta´ nevando.
6 Se esta´ nevando e chovendo, enta˜o esta´ nevando.
7 Se na˜o esta´ chovendo, enta˜o na˜o e´ o caso que esta´ nevando e
chovendo.Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Semaˆntica da Linguagem Proposicional
Exemplo
1 Esta´ chovendo, mas na˜o esta´ nevando.
(C ∧ (¬N))
2 Na˜o e´ o caso que esta´ chovendo ou nevando.
(¬(C ∨ N))
3 Se na˜o esta´ chovendo, enta˜o esta´ nevando.
((¬C)→ N)
4 Na˜o e´ o caso que se esta´ chovendo enta˜o esta´ nevando.
(¬(C → N))
5 Esta´ chovendo se e somente se esta´ nevando.
(C ↔ N)
6 Se esta´ nevando e chovendo, enta˜o esta´ nevando.
((N ∧ C)→ N)
7 Se na˜o esta´ chovendo, enta˜o na˜o e´ o caso que esta´ nevando e chovendo.
((¬C)→ (¬(N ∧ C)))
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Semaˆntica da Linguagem Proposicional
Example
Utilizando a func¸a˜o de valorac¸a˜o v(C ) = 1 e v(N) = 0, encontre a
func¸a˜o valorac¸a˜o v¯ para as fo´rmulas abaixo.
1 v¯((C ∧ (¬N)))
2 v¯((¬(C ∨ N)))
3 v¯(((¬C)→ N))
4 v¯((¬(C → N)))
5 v¯((C ↔ N))
6 v¯(((N ∧ C)→ N))
7 v¯(((¬C)→ (¬(N ∧ C))))
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Definic¸o˜es Recursivas
Example (Teorema da Definic¸a˜o Recursiva em Fo´rmulas)
Considere as seguintes func¸o˜es:
Hp : P → {0, 1}, onde Hp(pi ) = v(pi ), para toda proposic¸a˜o pi ∈ P.
H¬ : {0, 1} → {0, 1}, onde H¬(x) =
{
1, se x = 0
0, caso contra´rio
H∧ :{0, 1}×{0, 1}→{0, 1}, onde H∧(x , y) =
{
1, se x = 1 E y = 1
0, caso contra´rio
H∨ :{0, 1}×{0, 1}→{0, 1}, onde H∨(x , y) =
{
1, se x = 1 OU y = 1
0, caso contra´rio
H→ :{0, 1}×{0, 1}→{0, 1}, onde H→(x , y) =
{
1, se x = 0 OU y = 1
0, caso contra´rio
H↔ :{0, 1}×{0, 1}→{0, 1}, onde H↔(x , y) =
{
1, se x = y
0, caso contra´rio
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Definic¸o˜es Recursivas
Example (Teorema da Definic¸a˜o Recursiva em Fo´rmulas)
Aplicando o teorema da definic¸a˜o recursiva, temos a definic¸a˜o da
func¸a˜o v¯ : LLP → {0, 1} como segue:
1 v¯(pi ) = Hp(pi ) = v(pi ).
2 v¯((¬ϕ)) = H¬(v¯(ϕ)) =
{
1, se v¯(ϕ) = 0
0, caso contra´rio
3 v¯((ϕ ∧ ψ)) = H∧(v¯(ϕ), v¯(ψ)) =
{
1, se v¯(ϕ) = 1 E v¯(ψ) = 1
0, caso contra´rio
4 v¯((ϕ ∨ ψ)) = H∨(v¯(ϕ), v¯(ψ)) =
{
1, se v¯(ϕ) = 1 OU v¯(ψ) = 1
0, caso contra´rio
5
v¯((ϕ→ ψ)) = H→(v¯(ϕ), v¯(ψ)) =
{
1, se v¯(ϕ) = 0 OU v¯(ψ) = 1
0, caso contra´rio
6 v¯((ϕ↔ ψ)) = H↔(v¯(ϕ), v¯(ψ)) =
{
1, se v¯(ϕ) = v¯(ψ)
0, caso contra´rio
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Abreviac¸o˜es da Linguagem Proposicional
Apesar do uso de pareˆnteses ser obrigato´rio na definic¸a˜o de
fo´rmulas, usamos abreviac¸o˜es na pra´tica:
Os pareˆnteses mais externos podem ser omitidos. Por
exemplo, P ∧ Q em vez de (P ∧ Q), (P ∨ Q)→ P
O uso repetido dos conectivos ∧ e ∨ dispensa o uso de
pareˆnteses. Por exemplo, P ∧ Q ∧ R em vez de P ∧ (Q ∧ R)
O uso repetido do conectivo → dispensa o uso de pareˆnteses,
so´ que os pareˆnteses aninham-se a` direita. Por exemplo,
P → Q → R em vez de P → (Q → R)
Nas fo´rmula que ha´ uma combinac¸a˜o de conectivos, existe
uma precedeˆncia entre eles, dada pela ordem :¬,∧,∨,→,↔.
Por exemplo:
¬P ∧ Q representa ((¬P) ∧ Q)
P ∨ Q ∧ R representa (P ∨ (Q ∧ R))
P ∨ ¬Q → R representa ((P ∨ (¬Q))→ R)
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Satisfatibilidade e Validade
Satisfatibilidade e Validade
Definic¸a˜o
Uma fo´rmula ϕ e´ dita satisfat´ıvel se existe uma func¸a˜o de
valorac¸a˜o v tal que v¯(ϕ) = 1.
Uma fo´rmula ϕ e´ dita insatisfat´ıvel se toda func¸a˜o de
valorac¸a˜o v e´ tal que v¯(ϕ) = 0.
Uma fo´rmula ϕ e´ dita va´lida (ou uma tautologia) se toda
func¸a˜o de valorac¸a˜o v e´ tal que v¯(ϕ) = 1.
Neste caso escrevemos |= ϕ.
Uma fo´rmula ϕ e´ dita falsifica´vel se existe uma func¸a˜o de
valorac¸a˜o v tal que v¯(ϕ) = 0.
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Satisfatibilidade e Validade
Satisfatibilidade e Validade
Theorem
A fo´rmula P ∨ ¬P e´ va´lida
Demonstrac¸a˜o.
Suponha v uma func¸a˜o de valorac¸a˜o qualquer.
Da´ı, devemos demonstrar que v¯(P ∨ ¬P) = 1.
v¯(P ∨ ¬P) = 1 ⇐⇒ v¯(P) = 1 OU v¯(¬P) = 1
⇐⇒ v¯(P) = 1 OU v¯(P) = 0.
⇐⇒ v(P) = 1 OU v(P) = 0.
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Satisfatibilidade e Validade
Satisfatibilidade e Validade
Theorem
A fo´rmula P ∧ ¬P e´ insatisfat´ıvel
Demonstrac¸a˜o.
Suponha por contradic¸a˜o que exista uma func¸a˜o de valorac¸a˜o v
qualquer tal que v¯(P ∧ ¬P) = 1.
v¯(P ∧ ¬P) = 1 ⇐⇒ v¯(P) = 1 E v¯(¬P) = 1
⇐⇒ v¯(P) = 1 E v¯(P) = 0.
⇐⇒ v(P) = 1 E v(P) = 0↙
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Satisfatibilidade e Validade
Satisfatibilidade e Validade
Theorem
A fo´rmula (¬P ∧ ¬Q)↔ ¬(P ∨ Q) e´ va´lida
Demonstrac¸a˜o.
Suponha v uma func¸a˜o de valorac¸a˜o qualquer.Devemos demonstrar que
v¯(¬P ∧ ¬Q) = v¯(¬(P ∨ Q)).
1
v¯(¬P ∧ ¬Q) = 1 ⇐⇒ v¯(¬P) = 1 E v¯(¬Q) = 1
⇐⇒ v(P) = 0 E v(Q) = 0
⇐⇒ v¯(P ∨ Q) = 0
⇐⇒ v¯(¬(P ∨ Q)) = 1
2
v¯(¬P ∧ ¬Q) = 0 ⇐⇒ v¯(¬P) = 0 OU v¯(¬Q) = 0
⇐⇒ v(P) = 1 OU v(Q) = 1
⇐⇒ v¯(P ∨ Q) = 1
⇐⇒ v¯(¬(P ∨ Q)) = 0
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Consequ¨eˆncia Lo´gica
Consequ¨eˆncia Lo´gica
Definic¸a˜o
Sejam Γ um conjunto de fo´rmulas e ϕ uma fo´rmula. Escrevemos
Γ |= ϕ para indicar que a fo´rmula ϕ e´ consequ¨eˆncia lo´gica de Γ,
i.e., se para toda valorac¸a˜o v
(v¯(ψ) = 1 para todo ψ ∈ Γ) =⇒ v¯(ϕ) = 1.
Escrevemos Γ 6|= ϕ se Γ |= ϕ na˜o e´ o caso.
Usualmente, escrevemos ϕ1, . . . , ϕn |= ψ para representar {ϕ1, . . . , ϕn} |= ψ
Duas fo´rmulas ϕ e ψ sa˜o logicamente equivalentes, representado por ϕ ≡ ψ, se
ϕ |= ψ e ψ |= ϕ.
Example
ϕ,ψ |= ϕ ∧ ψ ϕ,ϕ→ ψ |= ψ ϕ→ ψ,¬ψ |= ¬ϕ
|= ϕ→ ϕ |= ¬¬ϕ→ ϕ |= ϕ ∨ ψ ↔ ψ ∨ ϕ
ϕ→ ψ ≡ ¬ϕ ∨ ψ ¬¬ϕ ≡ ϕ ϕ→ ψ ≡ ¬ψ → ¬ϕ
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Consequ¨eˆncia Lo´gica
Consequ¨eˆncia Lo´gica
Theorem
ϕ,ψ |= ϕ ∧ ψ
Demonstrac¸a˜o.
Suponha v uma func¸a˜o de valorac¸a˜o qualquer tal que
v¯(ϕ) = v¯(ψ) = 1.
Devemos demonstrar que v¯(ϕ ∧ ψ) = 1.
Trivial.
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Consequ¨eˆncia Lo´gica
Consequ¨eˆncia Lo´gica
Theorem
¬¬ϕ |= ϕ
Demonstrac¸a˜o.
Suponha v uma func¸a˜o de valorac¸a˜o qualquer tal que v¯(¬¬ϕ) = 1.
Devemos demonstrar que v¯(ϕ) = 1.
v¯(¬¬ϕ) = 1 ⇐⇒ v¯(¬ϕ) = 0
⇐⇒ v¯(ϕ) = 1
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Consequ¨eˆncia Lo´gica
Consequ¨eˆncia Lo´gica
Theorem
ϕ→ ψ,¬ψ |= ¬ϕ
Demonstrac¸a˜o.
Suponha v uma func¸a˜o de valorac¸a˜o qualquer tal que
v¯(ϕ→ ψ) = v¯(¬ψ) = 1. Devemos demonstrar que v¯(¬ϕ) = 1.
v¯(¬ψ) = 1 ⇐⇒ v¯(ψ) = 0 (3)
v¯(ϕ→ ψ) = 1 ⇐⇒ v¯(ϕ) = 0 OU v¯(ψ) = 1
=⇒ v¯(ϕ) = 0 pela equac¸a˜o 3
=⇒ v¯(¬ϕ) = 1
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Me´todo da Tabela da Verdade
Me´todo da Tabela da Verdade
Para a verificac¸a˜o da satisfatibilidade de uma fo´rmula,
podemos utilizar o me´todo da tabela da verdade como abaixo:
1 A tabela possui uma coluna para cada subfo´rmula de ϕ.
2 Para cada func¸a˜o de valorac¸a˜o, insere-se uma linha com os
valores da valorac¸a˜o dos a´tomos.
3 Em seguida, a valorac¸a˜o dos a´tomos e´ propagada para as
subfo´rmulas, obedecendo-se a definic¸a˜o da valorac¸a˜o.
Exemplo
P Q ¬P ¬Q P ∨ Q ¬P ∨ ¬Q (P ∨ Q) ∧ (¬P ∨ ¬Q)
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Me´todo da Tabela da Verdade
Me´todo da Tabela da Verdade
Para a verificac¸a˜o da satisfatibilidade de uma fo´rmula,
podemos utilizar o me´todo da tabela da verdade como abaixo:
1 A tabela possui uma coluna para cada subfo´rmula de ϕ.
2 Para cada func¸a˜o de valorac¸a˜o, insere-se uma linha com os
valores da valorac¸a˜o dos a´tomos.
3 Em seguida, a valorac¸a˜o dos a´tomos e´ propagada para as
subfo´rmulas, obedecendo-se a definic¸a˜o da valorac¸a˜o.
Exemplo
P Q ¬P ¬Q P ∨ Q ¬P ∨ ¬Q (P ∨ Q) ∧ (¬P ∨ ¬Q)
1 1
1 0
0 1
0 0
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Me´todo da Tabela da Verdade
Me´todo da Tabela da Verdade
Para a verificac¸a˜o da satisfatibilidade de uma fo´rmula,
podemos utilizar o me´todo da tabela da verdade como abaixo:
1 A tabela possui uma coluna para cada subfo´rmula de ϕ.
2 Para cada func¸a˜o de valorac¸a˜o,insere-se uma linha com os
valores da valorac¸a˜o dos a´tomos.
3 Em seguida, a valorac¸a˜o dos a´tomos e´ propagada para as
subfo´rmulas, obedecendo-se a definic¸a˜o da valorac¸a˜o.
Exemplo
P Q ¬P ¬Q P ∨ Q ¬P ∨ ¬Q (P ∨ Q) ∧ (¬P ∨ ¬Q)
1 1 0 0 1
1 0 0 1 1
0 1 1 0 1
0 0 1 1 0
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Me´todo da Tabela da Verdade
Me´todo da Tabela da Verdade
Para a verificac¸a˜o da satisfatibilidade de uma fo´rmula,
podemos utilizar o me´todo da tabela da verdade como abaixo:
1 A tabela possui uma coluna para cada subfo´rmula de ϕ.
2 Para cada func¸a˜o de valorac¸a˜o, insere-se uma linha com os
valores da valorac¸a˜o dos a´tomos.
3 Em seguida, a valorac¸a˜o dos a´tomos e´ propagada para as
subfo´rmulas, obedecendo-se a definic¸a˜o da valorac¸a˜o.
Exemplo
P Q ¬P ¬Q P ∨ Q ¬P ∨ ¬Q (P ∨ Q) ∧ (¬P ∨ ¬Q)
1 1 0 0 1 0
1 0 0 1 1 1
0 1 1 0 1 1
0 0 1 1 0 1
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Me´todo da Tabela da Verdade
Me´todo da Tabela da Verdade
Para a verificac¸a˜o da satisfatibilidade de uma fo´rmula,
podemos utilizar o me´todo da tabela da verdade como abaixo:
1 A tabela possui uma coluna para cada subfo´rmula de ϕ.
2 Para cada func¸a˜o de valorac¸a˜o, insere-se uma linha com os
valores da valorac¸a˜o dos a´tomos.
3 Em seguida, a valorac¸a˜o dos a´tomos e´ propagada para as
subfo´rmulas, obedecendo-se a definic¸a˜o da valorac¸a˜o.
Exemplo
P Q ¬P ¬Q P ∨ Q ¬P ∨ ¬Q (P ∨ Q) ∧ (¬P ∨ ¬Q)
1 1 0 0 1 0 0
1 0 0 1 1 1 1
0 1 1 0 1 1 1
0 0 1 1 0 1 0
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica Proposicional
Me´todo da Tabela da Verdade
Me´todo da Tabela da Verdade
Ao final da execuc¸a˜o do me´todo da Tabela da Verdade, pode-se
classificar ϕ da seguinte maneira:
1 A fo´rmula ϕ e´ satisfat´ıvel se alguma linha da coluna de ϕ
contiver 1
2 A fo´rmula ϕ e´ va´lida se todas as linhas da coluna de ϕ
contiverem 1
3 A fo´rmula ϕ e´ falsifica´vel se alguma linha da coluna de ϕ
contiver 0
4 A fo´rmula ϕ e´ insatisfat´ıvel se todas as linhas da coluna de ϕ
contiverem 0
dizer se a fo´rmula ϕ e´ consequ¨eˆncia lo´gica de Γ (representado
por Γ |= ϕ), i.e., se para cada linha que contiver 1 em todas
as colunas das fo´rmulas de Γ, enta˜o conte´m 1 na coluna de ϕ
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
De Morgan: |= ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
Exerc´ıcio: Satisfatibilidade e Validade
Theorem
A fo´rmula ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ) e´ va´lida
Demonstrac¸a˜o.
Suponha v uma func¸a˜o de valorac¸a˜o qualquer.
Devemos demonstrar que v¯(¬(ϕ ∧ ψ)) = v¯(¬ϕ ∨ ¬ψ).
1. v¯(¬(ϕ ∧ ψ)) = 1 ⇐⇒ v¯(ϕ ∧ ψ) = 0
⇐⇒ v¯(ϕ) = 0 OU v¯(ψ) = 0
⇐⇒ v¯(¬ϕ) = 1 OU v¯(¬ψ) = 1
⇐⇒ v¯(¬ϕ ∨ ¬ψ) = 1
2. v¯(¬(ϕ ∧ ψ)) = 0 ⇐⇒ v¯(ϕ ∧ ψ) = 1
⇐⇒ v¯(ϕ) = 1 E v¯(ψ) = 1
⇐⇒ v¯(¬ϕ) = 0 E v¯(¬ψ) = 0
⇐⇒ v¯(¬ϕ ∨ ¬ψ) = 0
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
De Morgan: |= ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
A fo´rmula ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ) e´ va´lida
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ ∧ ψ ¬(ϕ ∧ ψ) (¬ϕ ∨ ¬ψ) ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
De Morgan: |= ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
A fo´rmula ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ) e´ va´lida
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ ∧ ψ ¬(ϕ ∧ ψ) (¬ϕ ∨ ¬ψ) ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
1 1
1 0
0 1
0 0
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
De Morgan: |= ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
A fo´rmula ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ) e´ va´lida
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ ∧ ψ ¬(ϕ ∧ ψ) (¬ϕ ∨ ¬ψ) ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
1 1 0 0 1
1 0 0 1 0
0 1 1 0 0
0 0 1 1 0
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
De Morgan: |= ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
A fo´rmula ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ) e´ va´lida
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ ∧ ψ ¬(ϕ ∧ ψ) (¬ϕ ∨ ¬ψ) ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
1 1 0 0 1 0 0
1 0 0 1 0 1 1
0 1 1 0 0 1 1
0 0 1 1 0 1 1
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
De Morgan: |= ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
A fo´rmula ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ) e´ va´lida
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ ∧ ψ ¬(ϕ ∧ ψ) (¬ϕ ∨ ¬ψ) ¬(ϕ ∧ ψ)↔ (¬ϕ ∨ ¬ψ)
1 1 0 0 1 0 0 1
1 0 0 1 0 1 1 1
0 1 1 0 0 1 1 1
0 0 1 1 0 1 1 1
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Contrapositiva: |= (ϕ→ ψ)↔ (¬ψ → ¬ϕ)
Exerc´ıcio: Satisfatibilidade e Validade
Theorem
A fo´rmula (ϕ→ ψ)↔ (¬ψ → ¬ϕ) e´ va´lida
Demonstrac¸a˜o.
Suponha v uma func¸a˜o de valorac¸a˜o qualquer.
Devemos demonstrar que v¯(ϕ→ ψ) = v¯(¬ψ → ¬ϕ).
1. v¯(ϕ→ ψ) = 1 ⇐⇒ v¯(ϕ) = 0 OU v¯(ψ) = 1
⇐⇒ v¯(¬ϕ) = 1 OU v¯(¬ψ) = 0
⇐⇒ v¯(¬ψ) = 0 OU v¯(¬ϕ) = 1
⇐⇒ v¯(¬ψ → ¬ϕ) = 1
2. v¯(ϕ→ ψ) = 0 ⇐⇒ v¯(ϕ) = 1 E v¯(ψ) = 0
⇐⇒ v¯(¬ϕ) = 0 E v¯(¬ψ) = 1
⇐⇒ v¯(¬ψ) = 1 E v¯(¬ϕ) = 0
⇐⇒ v¯(¬ψ → ¬ϕ) = 0
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Contrapositiva: |= (ϕ→ ψ)↔ (¬ψ → ¬ϕ)
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
A fo´rmula (ϕ→ ψ)↔ (¬ψ → ¬ϕ) e´ va´lida
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ→ ψ ¬ψ → ¬ϕ (ϕ→ ψ)↔ (¬ψ → ¬ϕ)
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Contrapositiva: |= (ϕ→ ψ)↔ (¬ψ → ¬ϕ)
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
A fo´rmula (ϕ→ ψ)↔ (¬ψ → ¬ϕ) e´ va´lida
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ→ ψ ¬ψ → ¬ϕ (ϕ→ ψ)↔ (¬ψ → ¬ϕ)
1 1
1 0
0 1
0 0
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Contrapositiva: |= (ϕ→ ψ)↔ (¬ψ → ¬ϕ)
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
A fo´rmula (ϕ→ ψ)↔ (¬ψ → ¬ϕ) e´ va´lida
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ→ ψ ¬ψ → ¬ϕ (ϕ→ ψ)↔ (¬ψ → ¬ϕ)
1 1 0 0 1 1
1 0 0 1 0 0
0 1 1 0 1 1
0 0 1 1 1 1
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Contrapositiva: |= (ϕ→ ψ)↔ (¬ψ → ¬ϕ)
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
A fo´rmula (ϕ→ ψ)↔ (¬ψ → ¬ϕ) e´ va´lida
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ→ ψ ¬ψ → ¬ϕ (ϕ→ ψ)↔ (¬ψ → ¬ϕ)
1 1 0 0 1 1 1
1 0 0 1 0 0 1
0 1 1 0 1 1 1
0 0 1 1 1 1 1
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Modus Ponens: {ϕ, ϕ→ ψ} |= ψ
Exerc´ıcio: Consequ¨eˆncia Lo´gica
Theorem
{ϕ,ϕ→ ψ} |= ψ
Demonstrac¸a˜o.
Suponha v uma func¸a˜o de valorac¸a˜o qualquer.
Devemos demonstrar que se
(
v¯(ϕ) = 1
v¯(ϕ→ ψ) = 1
)
enta˜o v¯(ψ) = 1.
Trivial.
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Modus Ponens: {ϕ, ϕ→ ψ} |= ψ
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
{ϕ,ϕ→ ψ} |= ψ
Demonstrac¸a˜o.
ϕ ψ ϕ→ ψ
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Modus Ponens: {ϕ, ϕ→ ψ} |= ψ
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
{ϕ,ϕ→ ψ} |= ψ
Demonstrac¸a˜o.
ϕ ψ ϕ→ ψ
1 1
1 0
0 1
0 0
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Modus Ponens: {ϕ, ϕ→ ψ} |= ψ
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
{ϕ,ϕ→ ψ} |= ψ
Demonstrac¸a˜o.
ϕ ψ ϕ→ ψ
1 1 1
1 0 0
0 1 1
0 0 1
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Modus Tolens: {¬ψ, ϕ→ ψ} |= ¬ϕ
Exerc´ıcio: Consequ¨eˆncia Lo´gica
Theorem
{¬ψ,ϕ→ ψ} |= ¬ϕ
Demonstrac¸a˜o.
Suponha v uma func¸a˜o de valorac¸a˜o qualquer.
v¯(¬ψ) = 1
v¯(ϕ→ ψ) = 1
}
v¯(ψ) = 0
v¯(ϕ) = 0 OU v¯(ψ) = 1
}
v¯(ϕ) = 0 =⇒ v¯(¬ϕ) = 1
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Modus Tolens: {¬ψ, ϕ→ ψ} |= ¬ϕ
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
{¬ψ,ϕ→ ψ} |= ¬ϕ
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ→ ψ
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Modus Tolens: {¬ψ, ϕ→ ψ} |= ¬ϕ
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
{¬ψ,ϕ→ ψ} |= ¬ϕ
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ→ ψ
1 1
1 0
0 1
0 0
Lo´gica para Computac¸a˜o
Exerc´ıcios Semaˆntica da Lo´gica Proposicional
Modus Tolens: {¬ψ, ϕ→ ψ} |= ¬ϕ
Exerc´ıcio: Me´todo da Tabela da Verdade
Theorem
{¬ψ,ϕ→ ψ} |= ¬ϕ
Demonstrac¸a˜o.
ϕ ψ ¬ϕ ¬ψ ϕ→ ψ
1 1 0 0 1
1 0 0 1 0
0 1 1 0 1
0 0 1 1 1Lo´gica para Computac¸a˜o
Teorema da Deduc¸a˜o
Teorema da Deduc¸a˜o
Theorem
Sejam Γ um conjunto de fo´rmulas e ϕ e ψ fo´rmulas.
Γ, ϕ |= ψ ⇐⇒ Γ |= ϕ→ ψ
Demonstrac¸a˜o (=⇒).
De Γ, ϕ |= ψ, temos que se
(
v¯(σ) = 1, para todo σ ∈ Γ
v¯(ϕ) = 1
)
enta˜o v¯(ψ) = 1
Suponha por contradic¸a˜o que Γ 6|= ϕ→ ψ. Da´ı, temos que
v¯(σ) = 1, para todo σ ∈ Γ
v¯(ϕ→ ψ) = 0
(
v¯(σ) = 1, para todo σ ∈ Γ
v¯(ϕ) = 1
)
︸ ︷︷ ︸ E v¯(ψ) = 0
v¯(ψ) = 1↙
Lo´gica para Computac¸a˜o
Teorema da Deduc¸a˜o
Teorema da Deduc¸a˜o
Theorem
Sejam Γ um conjunto de fo´rmulas e ϕ e ψ fo´rmulas.
Γ, ϕ |= ψ ⇐⇒ Γ |= ϕ→ ψ
Demonstrac¸a˜o (⇐=).
De Γ |= ϕ→ ψ, temos que se (v¯(σ) = 1, para todo σ ∈ Γ) enta˜o
v¯(ϕ→ ψ) = 1
Suponha por contradic¸a˜o que Γ, ϕ 6|= ψ. Da´ı, temos que
v¯(σ) = 1, para todo σ ∈ Γ
v¯(ϕ) = 1
v¯(ψ) = 0
v¯(σ) = 1, para todo σ ∈ Γ︸ ︷︷ ︸E v¯(ϕ→ ψ) = 0
v¯(ϕ→ ψ) = 1↙
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Sistema Dedut´ıvel
Existem diversas formas de definir um sistema dedut´ıvel.
Um sistema dedutivo e´ um mecanismo que permite a
construc¸a˜o de argumentos formais
Um sistema dedutivo e´ um mecanismo que permite
estabelecer concluso˜es a partir de hipo´teses.
Um sistema dedutivo e´ um conjunto de regras (as vezes
axiomas) que permite “chegar” a concluso˜es (sentenc¸as) a
partir de hipo´teses (sentenc¸as).
Escrevemos Γ `D ϕ para indicar ϕ e´ provado com o mecanismo de
deduc¸a˜o D a partir de um conjunto de fo´rmulas Γ
Correc¸a˜o: Γ `D ϕ =⇒ Γ |= ϕ
Completude: Γ |= ϕ =⇒ Γ `D ϕ
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Axioma´tico
Sistema Axioma´tico
Existem diversos sistemas axioma´ticos.
Sistema de Hilbert e Bernays.
Conte´m os seguintes esquemas axioma´ticos:
Axioma 1: ϕ→ (ψ → ϕ)
Axioma 2: (ϕ→ (ψ → σ))→ ((ϕ→ ψ)→ (ϕ→ σ))
Axioma 3: (¬ψ → ¬ϕ)→ ((¬ψ → ϕ)→ ψ)
Conte´m apenas uma regra de infereˆncia (Modus Ponens)
ϕ ϕ→ ψ
ψ
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Axioma´tico
Exemplo
Prove que `Ax A→ A
Aplicando os esquemas axioma´ticos abaixo
Axioma 1: ϕ→ (ψ → ϕ)
Axioma 2: (ϕ→ (ψ → σ))→ ((ϕ→ ψ)→ (ϕ→ σ))
temos que
Axioma 1: ϕ = A e ψ = B → A A→ ((B → A)→ A)
Axioma 1: ϕ = A e ψ = B A→ (B → A)
Axioma 2: ϕ = A, ψ = B → A e σ = A (A→ ((B → A)→ A))→ (A→ (B → A))→ (A→ A)
A→ (B → A)
A→ ((B → A)→ A) (A→ ((B → A)→ A))→ (A→ (B → A))→ (A→ A)
(A→ (B → A))→ (A→ A)
A→ A
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Axioma´tico
Exemplo
Prove que {A→ B,B → C} `Ax A→ C
Aplicando os esquemas axioma´ticos abaixo
Axioma 1: ϕ→ (ψ → ϕ)
Axioma 2: (ϕ→ (ψ → σ))→ ((ϕ→ ψ)→ (ϕ→ σ))
temos que
Axioma 1: ϕ = B → C e ψ = A (B → C)→ (A→ (B → C))
Axioma 2: ϕ = A, ψ = B e σ = C (A→ (B → C))→ (A→ B)→ (A→ C)
A→ B
B → C (B → C)→ (A→ (B → C))
A→ (B → C) (A→ (B → C))→ (A→ B)→ (A→ C)
(A→ B)→ (A→ C)
A→ C
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Regras de Deduc¸a˜o Natural
ϕ ψ
ϕ ∧ ψ ∧I
ϕ ∧ ψ
ϕ ∧E
ϕ ∧ ψ
ψ
∧E
ϕ
ϕ ∨ ψ ∨I
ψ
ϕ ∨ ψ ∨I
ϕ ∨ ψ
[ϕ]
.
.
.
α
[ψ]
.
.
.
α
α ∨E
[ϕ]
.
.
.
ψ
ϕ→ ψ → I
ϕ ϕ→ ψ
ψ
→ E
[ϕ]
.
.
.
⊥
¬ϕ ¬I
ϕ ¬ϕ
⊥ ¬E
⊥
ϕ ⊥
[¬ϕ]
.
.
.
⊥
ϕ RAA
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que A ∧ (B ∧ C ) `DN (A ∧ B) ∧ C
A ∧ (B ∧ C )
A
A ∧ (B ∧ C )
B ∧ C
B
A ∧ B
A ∧ (B ∧ C )
B ∧ C
C
(A ∧ B) ∧ C
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que A ∨ (B ∨ C ) `DN (A ∨ B) ∨ C
A ∨ (B ∨ C )
[A]1
A ∨ B
(A ∨ B) ∨ C
[B ∨ C ]1
[B]2
A ∨ B
(A ∨ B) ∨ C
[C ]2
(A ∨ B) ∨ C
(A ∨ B) ∨ C
2
(A ∨ B) ∨ C
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que `DN A→ (B → A)
[A]1
(B → A)
A→ (B → A)
1
Prove que `DN (A→ B)→ ((B → C )→ (A→ C ))
[A]3 [(A→ B)]1
B [B → C ]2
C
A→ C 3
(B → C )→ (A→ C )
2
(A→ B)→ ((B → C )→ (A→ C ))
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que A→ (B → C ) `DN (A ∧ B)→ C
A→ (B → C )
[A ∧ B]1
A
B → C
[A ∧ B]1
B
C
(A ∧ B)→ C
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que `DN A→ (¬A→ B)
[A]1 [¬A]2
⊥
B
¬A→ B 2
A→ (¬A→ B)
1
Prove que ¬A ∨ B `DN A→ B
¬A ∨ B
[A]2 [¬A]1
⊥
B
A→ B 2
[B]1
A→ B
A→ B 1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que `DN A ∨ ¬A
[A]2
A ∨ ¬A [¬(A ∨ ¬A)]1
⊥
¬A 2
A ∨ ¬A [¬(A ∨ ¬A)]1
⊥
A ∨ ¬A 1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que `DN (A→ B) ∨ (B → A)
[A]2
B → A
(A→ B) ∨ (B → A) [¬((A→ B) ∨ (B → A))]1
⊥
B
A→ B
2
(A→ B) ∨ (B → A) [¬((A→ B) ∨ (B → A))]1
⊥
(A→ B) ∨ (B → A)
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Exemplo
(Problema do Vestido) Treˆs irma˜s - Ana, Maria e Cla´udia - foram a
uma festa com vestidos de cores diferentes. Uma vestia azul, a
outra branco e a terceira preto. Chegando a` festa, o anfitria˜o
perguntou quem era cada uma delas. A resposta foi como segue:
A de azul respondeu: “Ana e´ que esta´ de branco”
A de branco falou: “Eu sou Maria”
A de preto disse: “Cla´udia e´ quem esta´ de branco”
O anfitria˜o foi capaz de identificar corretamente quem era cada pessoa
considerando que:
Ana sempre diz a verdade
Maria a`s vezes diz a verdade
Cla´udia nunca diz a verdade
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Para cada irma˜, temos que
por exemplo, a Maria veste algum vestido: MA ∨MB ∨MP
E somente um deles:
(MA→ (¬MB ∧ ¬MP))
(MB → (¬MA ∧ ¬MP))
(MP → (¬MA ∧ ¬MB))
Para cada vestido, temos que
por exemplo, o Azul sera´ usado por alguma irma˜: MA ∨ AA ∨ CA
E somente um deles:
(MA→ (¬AA ∧ ¬CA))
(AA→ (¬MA ∧ ¬CA))
(CA→ (¬AA ∧ ¬MA))
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Como Ana sempre diz a verdade, temos que
Se Ana esta´ de Azul: AA→ AB
Se Ana esta´ de Branco: ¬AB
Se Ana esta´ de Preto: AP → CB
De Maria dizer a`s vezes a verdade, na˜o podemos inferir nada.
Como Cla´udia nunca diz a verdade, temos que
Se Cla´udia esta´ de Azul: CA→ ¬AB
Se Cla´udia esta´ de Branco: Na˜o acrescenta informac¸a˜o
Se Cla´udia esta´ de Preto: CP → ¬CB (ja´ foi definido)
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja Γ a teoria (contendo as fo´rmulas definidas anteriormente),
podemos provar que Γ `DN AP ∧ CB ∧MA
Seja
∏
1 a prova de que Γ `DN AP
Seja
∏
2 a prova de que Γ `DN CB
Seja
∏
3 a prova de que Γ `DN MA
∏
1
AP
∏
2
CB
AP ∧ CB
∏
3
MA
(AP ∧ CB) ∧MA
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
1 a prova de que Γ `DN AP
(AA ∨ AB) ∨ AP
[AA ∨ AB]1
[AA]2
[AA]3 AA→ AB
AB ¬AB
⊥
¬AA
3
⊥
AP
[AB]2 ¬AB
⊥
AP
AP
2
[AP]1
AP
1
Seja
∏
2 a prova de que Γ `DN CB
∏
1
AP AP → CB
CB
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
1 a prova de que Γ `DN AP
(AA ∨ AB) ∨ AP
[AA ∨ AB]1
[AA]2 AA→ AB
AB ¬AB
⊥
AP
[AB]2 ¬AB
⊥
AP
AP
2
[AP]1
AP
1
Seja
∏
2 a prova de que Γ `DN CB
∏
1
AP AP → CB
CB
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
3 a prova de que Γ `DN MA
MA ∨ (MB ∨ MP) [MA]1
[MB ∨ MP]1
∏
2
CB
[MB]2 MB → (¬CB ∧ ¬AB)
¬CB ∧ ¬AB
¬CB
⊥
MA
∏
1
AP
[MP]2 MP → (¬CP ∧ ¬AP)
¬CP ∧ ¬AP
¬AP
⊥
MA
MA
2
MA
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Especificac¸a˜o do Problema do Crime em Lo´gica
Proposicional
Exemplo
(Problema do Crime) Uma pessoa comete um crime e ha´ quatro
suspeitos: Maria, Joa˜o, Simone e Pedro. Ao serem interrogados
eles fazem as seguintes declarac¸o˜es:
Maria: Joa˜o e´ o culpado;
Joa˜o: Pedro e´ o culpado;
Simone: Eu na˜o sou culpada;
Pedro: Joa˜o mente quando diz que eu sou culpado.
Sabendo que somenteum dos quatro diz a verdade, e´ poss´ıvel,
somente com esses dados saber quem foi o culpado? Caso
afirmativo, quem foi o culpado?
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Especificac¸a˜o do Problema do Crime em Lo´gica
Proposicional
De somente uma pessoa e´ culpada, temos que
MC ∨ JC ∨ SC ∨ PC
(MC → (¬JC ∧ ¬SC ∧ ¬PC))
(JC → (¬MC ∧ ¬SC ∧ ¬PC))
(SC → (¬JC ∧ ¬MC ∧ ¬PC))
(PC → (¬JC ∧ ¬SC ∧ ¬MC))
De somente uma pessoa falar a verdade, temos que
MV ∨ JV ∨ SV ∨ PV
(MV → (¬JV ∧ ¬SV ∧ ¬PV ))
(JV → (¬MV ∧ ¬SV ∧ ¬PV ))
(SV → (¬JV ∧ ¬MV ∧ ¬PV ))
(PV → (¬JV ∧ ¬SV ∧ ¬MV ))
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Especificac¸a˜o do Problema do Crime em Lo´gica
Proposicional
Sabendo que cada suspeito disse que:
Maria: Joa˜o e´ o culpado;
Joa˜o: Pedro e´ o culpado;
Simone: Eu na˜o sou culpada;
Pedro: Joa˜o mente quando diz que eu sou culpado.
Considerando que Maria diz a verdade, temos que
(MV → (JC ∧ ¬PC ∧ SC ∧ PC))
Considerando que Joa˜o diz a verdade, temos que
(JV → (¬JC ∧ PC ∧ SC ∧ PC))
Considerando que Simone diz a verdade, temos que
(SV → (¬JC ∧ ¬PC ∧ ¬SC ∧ PC))
Considerando que Pedro diz a verdade, temos que
(PV → (¬JC ∧ ¬PC ∧ SC ∧ ¬PC))
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
1 a prova de que Γ `DN ¬MV
[MV ]1 MV → (JC ∧ ¬PC ∧ SC ∧ PC)
JC ∧ ¬PC ∧ SC ∧ PC
¬PC ∧ SC ∧ PC
¬PC
[MV ]1 MV → (JC ∧ ¬PC ∧ SC ∧ PC)
JC ∧ ¬PC ∧ SC ∧ PC
¬PC ∧ SC ∧ PC
SC ∧ PC
PC
⊥
¬MV
1
Seja
∏
2 a prova de que Γ `DN ¬PV
[JV ]1 JV → (¬JC ∧ PC ∧ SC ∧ PC)
¬JC ∧ PC ∧ SC ∧ PC
¬JC ∧ PC ∧ SC
¬JC ∧ PC
PC PC → (¬JC ∧ ¬SC ∧ ¬MC)
¬JC ∧ ¬SC ∧ ¬MC
¬JC ∧ ¬SC
¬SC
[JV ]1 JV → (¬JC ∧ PC ∧ SC ∧ PC)
¬JC ∧ PC ∧ SC ∧ PC
¬JC ∧ PC ∧ SC
SC
⊥
¬JV
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
3 a prova de que Γ `DN ¬SV
[SV ]1 SV → (¬JC ∧ ¬PC ∧ ¬SC ∧ PC)
¬JC ∧ ¬PC ∧ ¬SC ∧ PC
PC
[SV ]1 SV → (¬JC ∧ ¬PC ∧ ¬SC ∧ PC)
¬JC ∧ ¬PC ∧ ¬SC ∧ PC
¬JC ∧ ¬PC ∧ ¬SC
¬JC ∧ ¬PC
¬PC
⊥
¬SV
1
Seja
∏
4 a prova de que Γ `DN PV
MV ∨ JV ∨ SV ∨ PV
MV ∨ JV ∨ SV
[MV ∨ JV ]2
[MV ]3
∏
1
¬MV
⊥
PV
[JV ]3
∏
2
¬JV
⊥
PV
PV
3
[SV ]2
∏
3
¬SV
⊥
PV
PV
2
[PV ]1
PV
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
5 a prova de que Γ `DN SC∏
4
PV PV → (¬JC ∧ ¬PC ∧ SC ∧ ¬PC )
¬JC ∧ ¬PC ∧ SC ∧ ¬PC
¬JC ∧ ¬PC ∧ SC
SC
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Exemplo
(Problema da Maratona) Apo´s uma prova de maratona uma
pessoa encontra seus 5 colegas que chegaram nas 5 primeiras
posic¸o˜es. Como esta pessoa teve um problema durante a corrida e
na˜o viu o final, ele perguntou a seus colegas, que afirmaram:
A: eu na˜o fui o u´ltimo dos 5;
B: C ficou em terceiro;
C: A ficou atra´s de E;
D: E foi o segundo;
E: D na˜o foi o u´ltimo dos 5
Sabendo que o primeiro e o segundo mentiram, diga qual foi a
verdadeira classificac¸a˜o.
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Especificac¸a˜o do Problema da Maratona em Lo´gica
Proposicional
Para cada maratonista, temos que
por exemplo, o Maratonista A ficou em uma das cinco
colocac¸o˜es: A1 ∨ A2 ∨ A3 ∨ A4 ∨ A5
E somente em uma das colocac¸o˜es:
A1→ (¬A2 ∧ ¬A3 ∧ ¬A4 ∧ ¬A5)
A2→ (¬A1 ∧ ¬A3 ∧ ¬A4 ∧ ¬A5)
A3→ (¬A1 ∧ ¬A2 ∧ ¬A4 ∧ ¬A5)
A4→ (¬A1 ∧ ¬A2 ∧ ¬A3 ∧ ¬A5)
A5→ (¬A1 ∧ ¬A2 ∧ ¬A3 ∧ ¬A4)
Para colocac¸a˜o na maratona, temos que
por exemplo, um dos maratonistas obteve a primeira
colocac¸a˜o: A1 ∨ B1 ∨ C1 ∨ D1 ∨ E1
E somente um deles:
A1→ (¬B1 ∧ ¬C1 ∧ ¬D1 ∧ ¬E1)
B1→ (¬A1 ∧ ¬C1 ∧ ¬D1 ∧ ¬E1)
C1→ (¬A1 ∧ ¬B1 ∧ ¬D1 ∧ ¬E1)
D1→ (¬A1 ∧ ¬B1 ∧ ¬C1 ∧ ¬E1)
E1→ (¬A1 ∧ ¬B1 ∧ ¬C1 ∧ ¬D1)
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Especificac¸a˜o do Problema da Maratona em Lo´gica
Proposicional
De “A: eu na˜o fui o u´ltimo dos 5”, temos que A↔ ¬A5
De “B: C ficou em terceiro”, temos que B ↔ C3
De “C: A ficou atra´s de E”, temos que
C ↔

(E1 ∧ (A2 ∨ A3 ∨ A4 ∨ A5))
∨(E2 ∧ (A3 ∨ A4 ∨ A5))
∨(E3 ∧ (A4 ∨ A5))
∨(E4 ∧ (A5))

De “D: E foi o segundo”, temos que D ↔ E2
De “E: D na˜o foi o u´ltimo dos 5”, temos que E ↔ ¬D5
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Especificac¸a˜o do Problema da Maratona em Lo´gica
Proposicional
De “Sabendo que o primeiro e o segundo mentiram”, temos
que
¬A↔ (A1 ∨ A2)
¬B ↔ (B1 ∨ B2)
¬C ↔ (C1 ∨ C2)
¬D ↔ (D1 ∨ D2)
¬E ↔ (E1 ∨ E2)
De que somente dois mentiram e os outros falaram a verdade,
temos, por exemplo, que
(A ∧ C ∧ D)↔ (¬B ∧ ¬E)
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
A a prova de que Γ `DN A
¬A→ (A1 ∨ A2) [¬A]1
A1 ∨ A2
¬A5→ A
A1→ ¬A5 [A1]2
¬A5
A [¬A]1
⊥
¬A5→ A
A2→ ¬A5 [A2]2
¬A5
A [¬A]1
⊥
⊥
2
A
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
BC a prova de que Γ `DN B → C
¬C → (C1 ∨ C2) [¬C ]2
C1 ∨ C2
C3→ ¬C1
[B]1 B → C3
C3
¬C1 [C1]3
⊥
C3→ ¬C2
[B]1 B → C3
C3
¬C2 [C2]3
⊥
⊥
3
C
2
B → C
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
NDNE a prova de que Γ,B `DN ¬D ∧ ¬E
∏
A
A
B
B
∏
BC
B → C
C
B ∧ C
A ∧ B ∧ C (A ∧ B ∧ C)→ (¬D ∧ ¬E)
¬D ∧ ¬E
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
NB a prova de que Γ `DN ¬B
¬E → D5
[B]1∏
NDNE
¬D ∧ ¬E
¬E
D5
¬D → (D1 ∨ D2)
[B]1∏
NDNE
¬D ∧ ¬E
¬D
D1 ∨ D2
[D1]2 D1→ ¬D5
¬D5
[D2]2 D2→ ¬D5
¬D5
¬D5
2
⊥
¬B
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
E2 a prova de que Γ `DN E 2
∏
D
D D → E2
E2
Seja
∏
B1 a prova de que Γ `DN B1
¬B ¬B → (B1 ∨ B2)
B1 ∨ B2 [B1]1
[B2]1
∏
E2
E2 E2→ ¬B2
¬B2
⊥
B1
B1
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Exerc´ıcios
Exerc´ıcio de Especificac¸a˜o de Problemas em Lo´gica
Proposicional
Seja
∏
D5 a prova de que Γ `DN D5
∏
NE
¬E
[¬E ]1
[¬D5]2 ¬D5→ E
E
⊥
D5
2
¬E → D5
1
D5
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Tableaux
Sistema Tableau
Os sistemas Axioma´tico e Deduc¸a˜o Natural permitem
demonstrar quando uma fo´rmula e´ derivada de um conjunto
de fo´rmulas (Γ ` ϕ). Contudo, nenhum desses me´todos nos
permite inferir que Γ 6` ϕ.
Note que Γ 6` ϕ na˜o implica em Γ ` ¬ϕ.
O me´todo da Tabela da Verdade e´ um procedimento de
decisa˜o que nos permite Γ ` ϕ e Γ 6` ϕ. Contudo, esse
procedimento tem um crescimento no nu´mero de linhas
exponencial em relac¸a˜o ao nu´mero de s´ımbolos proposicionais.
O sistema de infereˆncia de Tableau Anal´ıtico (Semaˆntico) e´
um me´todo de decisa˜o que na˜o necessariamente gera provas
de tamanho exponencial.
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Tableaux
Sistema Tableau
Tableau e´ um me´todo de infereˆncia baseado em refutac¸a˜o:
para provarmos Γ ` ϕ, afirmamos a veracidade de Γ e a
falsidade de ϕ, na esperanc¸a de derivarmos uma contradic¸a˜o.
Por outro lado, se na˜o for obtida uma contradic¸a˜o, enta˜o
teremos constru´ıdo um contra-exemplo, i.e., uma valorac¸a˜o
que satisfaz Γ e na˜o satisfaz ϕ.
Para afirmar a veracidade ou falsidade de uma fo´rmula, o
me´todo dos tableaux anal´ıticos marca as fo´rmulas com os
s´ımbolos 1 para verdade e 0 para falsidade.
O passo inicial na criac¸a˜o de um tableau e´ marcar todas as
fo´rmulas de Γ com 1 e a fo´rmula ϕ com 0.
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Tableaux
Sistema Tableau
A partir do tableau inicial, utiliza-se regras de expansa˜o do
tableau que adicionam novas fo´rmulas ao final de um ramo
(regras do tipo α) ou que bifurcam um ramo em dois (regras
do tipo β).
Tipo α 1ϕ ∧ ψ
1ϕ
1ψ
0ϕ ∨ ψ
0ϕ
0ψ
0ϕ→ ψ
1ϕ
0ψ
1¬ϕ
0ϕTipo β 0ϕ ∧ ψ
0ϕ 0ψ
1ϕ ∨ ψ
1ϕ 1ψ
1ϕ→ ψ
0ϕ 1ψ
0¬ϕ
1ϕ
Note que as regras α e β na˜o sa˜o aplicadas aos a´tomos.
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Tableaux
Sistema Tableau
Em cada ramo, uma fo´rmula so´ pode ser expandida uma
u´nica vez.
Um ramo que na˜o possui mais fo´rmulas para expandir e´ dito
saturado.
Um ramo que possui uma par de fo´rmulas 1ϕ e 0ϕ e´ dito
fechado. Um ramo fechado na˜o precisa mais ser expandido.
Um tableau que tem todos os seus ramos fechados e´ dito
fechado, ou seja, Γ ` ϕ.
Um ramo saturado e na˜o fechado nos fornece um
contra-exemplo, ou seja, Γ 6` ϕ.
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Tableaux
Exemplos de Provas em Tableaux Semaˆnticos
`TA A ∨ ¬A
0A ∨ ¬A
0A
0¬A
1A
↙
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Tableaux
Exemplos de Provas em Tableaux Semaˆnticos
A→ B,B → C `TA A→ C
1A→ B
1B → C
0A→ C
1A
0C
0A
↙
1B
0B
↙
1C
↙
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Tableaux
Exemplos de Provas em Tableaux Semaˆnticos
A,A ∧ B → C 6`TA C
1A
1A ∧ B → C
0C
0A ∧ B
0A
↙
0B
1C
↙
A valorac¸a˜o v(A) = 1 e v(B) = v(C ) = 0 (contra-exemplo)
demonstra que A,A ∧ B → C 6`TA C .
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Lo´gica de Primeira-Ordem
A Lo´gica Proposicional possui: sistemas corretos e completos
(axioma´tico, Deduc¸a˜o Natural, Tableaux Semaˆnticos, etc) e
decibilidade (existe um procedimento que verifica se Γ |= ϕ).
No exemplo abaixo, podemos expressar as sentenc¸as abaixo.
Contudo, na˜o temos que W segue de P e Q, i.e., P,Q 6|= W
1 Todo homem e´ mortal P
2 So´crates e´ um homem Q
3 So´crates e´ mortal W
Em lo´gica de primeira-ordem (predicados), iremos demonstrar
que podemos expressar de uma melhor forma as sentenc¸as
(veja abaixo), bem como iremos mostrar que
∀x(H(x)→ M(x)),H(s) |= M(s)
1 Todo homem e´ mortal ∀x(H(x)→ M(x))
2 So´crates e´ um homem H(s)
3 So´crates e´ mortal M(s)
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Lo´gica de Primeira-Ordem
Podemos expressar a matema´tica na Liguagem da Lo´gica de
Primeira-Ordem.
Podemos utilizar |= para provar os teoremas da matema´tica.
Existem diversos sistemas dedut´ıveis corretos e completos
(Teorema da Completude de Go¨del).
Infelizmente, a lo´gica de primeira-ordem e´ indecid´ıvel, ou seja,
na˜o existe um procedimento que decide se Γ |= ϕ
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Lo´gica de Primeira-Ordem
Example (Teoria dos Grupos)
Usamos ◦ para denotar a multiplicac¸a˜o em grupos e e para a
identidade. Os axiomas podem ser definidos como segue
1 Para todo x , y , z : (x ◦ y) ◦ z = x ◦ (y ◦ z)
2 Para todo x : (x ◦ e) = x
3 Para todo x existe um y : (x ◦ y) = e
Um grupo e´ uma tripla 〈G , ◦G , eG 〉 que satisfaz 1, 2 e 3.
〈R,+, 0〉 e´ um exemplo de um grupo. A partir dos axiomas,
podemos provar que o teorema abaixo e´ va´lido para todos os
grupos.
Theorem
Para todo x existe um y: (y ◦ x) = e
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Lo´gica de Primeira-Ordem
Example (Teoria dos Grupos em Lo´gica)
Podemos modelar os axiomas 1, 2 e 3 conforme as fo´rmulas
abaixo1.
1 ∀x∀y∀z((x ◦ y) ◦ z = x ◦ (y ◦ z))
2 ∀x((x ◦ e) = x)
3 ∀x∃y((x ◦ y) = e)
O teorema pode ser expresso pela fo´rmula ∀x∃y((y ◦ x) = e)
Podemos demonstrar que o teorema acima e´ va´lido utilizando
|= (ou `).
1Na verdade, como veremos posteriormente, estamos utilizando uma
convenc¸a˜o para os termos
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Lo´gica de Primeira-Ordem
Example (Teoria das Relac¸o˜es Equivalentes)
Dizemos quem a relac¸a˜o xRy (leˆ-se x e´ equivalente a y) e´ uma
relac¸a˜o de equivaleˆncia se
1 Para todo x : xRx
2 Para todo x , y : Se xRy , enta˜o yRx
3 Para todo x , y , z : Se xRy e yRz , enta˜o xRz
Theorem
Se x e y sa˜o equivalentes a um terceiro elemento, enta˜o eles sa˜o
equivalentes para os mesmos elementos, i.e.,
Para todo x , y se existe um u tal que xRu e yRu, enta˜o para todo
z xRz se, e somente se, yRz
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Lo´gica de Primeira-Ordem
Example (Teoria das Relac¸o˜es Equivalentes)
Podemos modelar os axiomas 1, 2 e 3 conforme as fo´rmulas
abaixo2.
1 ∀x(xRx)
2 ∀x∀y((xRy)→ (yRx))
3 ∀x∀y∀z(((xRy) ∧ (yRz))→ (xRz))
O teorema pode ser expresso pela fo´rmula
∀x∀y(∃u(((xRu) ∧ (yRu))→ ∀z((xRz)↔ (yRz))))
Podemos demonstrar que o teorema acima e´ va´lido utilizando
|= (ou `).
2Na verdade, como veremos posteriormente, estamos utilizando uma
convenc¸a˜o para a relac¸a˜o R
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Alfabeto da Lo´gica de Primeira-Ordem
Alfabeto da Lo´gica de Primeira-Ordem
Definition
O Alfabeto da Lo´gica de Primeira-Ordem e´ constitu´ıdo de:
S´ımbolos Lo´gicos:
S´ımbolos de pontuac¸a˜o: ( e )
Conectivos: ¬,∧,∨,→,↔
S´ımbolo de igualdade: ≈
Um conjunto enumera´vel de varia´veis: V = {v0, v1, v2, . . .}
Quantificadores: ∀ (leˆ-se “qualquer” ou “para todo”) e
∃ (leˆ-se “existe pelo menos um” ou “existe”)
S´ımbolos na˜o-Lo´gicos Σ = 〈C , (Fn)n∈N, (Pn)n∈N〉, onde:
para cada inteiro positivo n, um conjunto Pn de s´ımbolos
predicativos de aridade n
um conjunto C de s´ımbolos constantes
para cada inteiro positivo n, um conjunto Fn de s´ımbolos
funcionais de aridade n
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Alfabeto da Lo´gica de Primeira-Ordem
Alfabeto da Lo´gica de Primeira-Ordem
Example (Teoria dos Grupos)
A linguagem na˜o-lo´gica da Teoria dos Grupos ΣTG e´ constitu´ıda
de:
Nenhum s´ımbolo predicativo, ou seja, para todo n Pn = ∅.
C = {e}.
F2 = {o} e para todo n 6= 2 Fn = ∅.
Example (Teoria das Relac¸o˜es Equivalentes)
A linguagem na˜o-lo´gica da Teoria das Relac¸o˜es Equivalentes ΣTRE
e´ constitu´ıda de:
P2 = {R} e para todo n 6= 2 Pn = ∅.
C = ∅.
Nenhum s´ımbolo funcional, ou seja, para todo n Fn = ∅.
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
A Linguagem da Lo´gica de Primeira-Ordem
A Linguagem da Lo´gica de Primeira-Ordem
A partir de uma linguagem na˜o-lo´gica Σ = 〈C , (Fn)n∈N, (Pn)n∈N〉,
podemos definir o conjunto dos termos e o conjunto de fo´rmulas
da linguagem de primeira-ordem.
Definition
O conjunto T (Σ) de termos de Σ, que sera´ denotado por T (Σ) e´
definido indutivamente como o menor conjunto, satisfazendo as
seguintes regras de formac¸a˜o:
1 Se v ∈ V (e´ uma varia´vel), enta˜o v ∈ T (Σ)
2 Se c ∈ C (e´ uma constante), enta˜o c ∈ T (Σ)
3 Se fn ∈ Fn (e´ um s´ımbolo funcional de aridade n) e
t1, . . . , tn ∈ T (Σ) (sa˜o termos), enta˜o fn(t1, . . . , tn) ∈ T (Σ)
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
A Linguagem da Lo´gica de Primeira-Ordem
A Linguagem da Lo´gica de Primeira-Ordem
Definition
O conjunto LFO das fo´rmulas da linguagem de primeira-ordem e´
definido indutivamente como o menor conjunto, satisfazendo as
seguintes regras de formac¸a˜o:
1 Se pn ∈ Pn (e´ um s´ımbolo predicativo de aridade n) e
t1, . . . , tn ∈ T (Σ) (sa˜o termos), enta˜o pn(t1, . . . , tn) ∈ LFO
2 Se t1, t2 ∈ T (Σ) (sa˜o termos), enta˜o t1 ≈ t2 ∈ LFO
3 Se ϕ ∈ LFO , enta˜o (¬ϕ) ∈ LFO
4 Se ϕ,ψ ∈ LFO , enta˜o (ϕ�ψ) ∈ LFO , onde � ∈ {∧,∨,→,↔}
5 Se ϕ ∈ LFO e v ∈ V (e´ uma varia´vel), enta˜o ((∃v)ϕ) ∈ LFO
6 Se ϕ ∈ LFO e v ∈ V (e´ uma varia´vel), enta˜o ((∀v)ϕ) ∈ LFO
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
A Linguagem da Lo´gica de Primeira-Ordem
A Linguagem da Lo´gica de Primeira-Ordem
Example (Teoria dos Grupos)
x , e, y ∈ T (ΣTG ) e ◦(x , e) ∈ T (ΣTG ).
◦(x , e) ≈ y ∈ LFOTG .
Example (Teoria das Relac¸o˜es Equivalentes)
x , y , z ∈ T (ΣTRE ).
R(x , y) ∈ LFOTRE .
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Provas por Induc¸a˜o
Provas por Induc¸a˜o em Lo´gica de Primeira-Ordem
Princ´ıpio de Induc¸a˜o sobre Termos
Seja A uma propriedade, enta˜o A(t) para todo termo t ∈ T (Σ) se A(x),∀x ∈ VA(c),∀c ∈ Σ
A(t1), . . .A(tn) e fn ∈ Σ⇒ A(f (t1, . . . , tn))
Princ´ıpio de Induc¸a˜o sobre Fo´rmulas
Seja A uma propriedade, enta˜o A(ϕ) para toda fo´rmula ϕ ∈ LFO se
A(R(t1, . . . , tn))
A(t1 ≈ t2)
A(ϕ)⇒ A((¬ϕ))
A(ϕ),A(ψ)⇒ A((ϕ�ψ)), onde� ∈ {∧,∨,→,↔}
A(ϕ)⇒ A((∀xϕ)) e A((∃xϕ))
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Provas por Induc¸a˜o
Provas por Induc¸a˜o em Lo´gica de Primeira-Ordem
Example
O s´ımbolo vazio ε na˜o e´ um termo T (Σ)
Demonstrac¸a˜o.
Seja A a propriedade de que qualquer termo na˜o e´ vazio.
Termos da forma x (varia´vel) na˜o sa˜o vazios.
Termos da forma c (constantes) na˜o sa˜o vazios.
Termos da forma fn(t1, . . . , tn) na˜o sa˜o vazios.
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
O tamanho ou complexidade |t| de t e´ definido por
|x | = 1, para x varia´vel
|c | = 1, para c constante
|fn(t1, . . . , tn)| = 1 + |t1|+ . . .+ |tn|
| ◦ (x , e)| =
= 1 + |x |+ |e|
= 1 + 1 + 1
= 3
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
O tamanho ou complexidade |ϕ| de ϕ e´ definido por
|R(t1, . . . , tn)| = 1 + |t1|+ . . .+ |tn|
|t1 ≈ t2| = 1 + |t1|+ |t2|
|(¬ϕ)| = 1 + |ϕ|
|(ϕ�ψ)| = 1 + |ϕ|+ |ψ|
|(∀xϕ)| = 1 + |ϕ|
|(∃xϕ)| = 1 + |ϕ|
|∀x ◦ (x , e) ≈ x | = 1 + | ◦ (x , e) ≈ x |
= 1 + 1 + | ◦ (x , e)|+ |x |
= 1 + 1 + 3 + 1
= 6
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
O conjunto de subfo´rmulas Sub(ϕ) de ϕ e´ definido por
Sub(R(t1, . . . , tn)) = {R(t1, . . . , tn)}
Sub(t1 ≈ t2) = {t1 ≈ t2}
Sub((¬ϕ)) = {(¬ϕ)} ∪ Sub(ϕ)
Sub((ϕ�ψ)) = {(ϕ�ψ)} ∪ Sub(ϕ) ∪ Sub(ψ)
Sub(∀xϕ) = {∀xϕ} ∪ Sub(ϕ)
Sub(∃xϕ) = {∃xϕ} ∪ Sub(ϕ)
Sub(∀x ◦ (x , e) ≈ x) = {∀x ◦ (x , e) ≈ x} ∪ Sub(◦(x , e) ≈ x)
= {∀x ◦ (x , e) ≈ x} ∪ {◦(x , e) ≈ x}
= {∀x ◦ (x , e) ≈ x , ◦(x , e) ≈ x}
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
O conjunto de varia´veis var(t) de t e´ definido por
var(x) = {x}, para x varia´vel
var(c) = ∅, para c constante
var(fn(t1, . . . , tn)) = var(t1) ∪ . . . ∪ var(tn)
var(◦(x , e)) =
= var(x) ∪ var(e)
= {x} ∪∅
= {x}
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
O conjunto de varia´veis var(ϕ) de ϕ e´ definido por
var(R(t1, . . . , tn)) = var(t1) ∪ . . . ∪ var(tn)
var(t1 ≈ tn) = var(t1) ∪ var(t2)
var((¬ϕ)) = var(ϕ)
var((ϕ�ψ)) = var(ϕ) ∪ var(ψ)
var(∀xϕ) = {x} ∪ var(ϕ)
var(∃xϕ) = {x} ∪ var(ϕ)
var(∀x(◦(x , e) ≈ x)) = {x} ∪ var(◦(x , e) ≈ x)
= {x} ∪ var(◦(x , e)) ∪ var(x)
= {x} ∪ var(x) ∪ var(e) ∪ {x}
= {x} ∪ {x} ∪∅ ∪ {x}
= {x}
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
O conjunto de varia´veis livres VL(ϕ) de ϕ e´ definido por
VL(R(t1, . . . , tn)) = var(t1) ∪ . . . ∪ var(tn)
VL(t1 ≈ tn) = var(t1) ∪ var(t2)
VL((¬ϕ)) = VL(ϕ)
VL((ϕ�ψ)) = VL(ϕ) ∪ VL(ψ)
VL(∀xϕ) = VL(ϕ)\{x}
VL(∃xϕ) = VL(ϕ)\{x}
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Definic¸o˜es Recursivas
Definition
Dizemos que uma fo´rmula ϕ e´ um sentenc¸a se o conjunto de
varia´veis livres e´ vazio.
Exemplo
A fo´rmula abaixo e´ uma sentenc¸a.
VL(∀x(◦(x, e) ≈ x)) = VL(◦(x, e) ≈ x)\{x}
= (var(◦(x, e)) ∪ var(x))\{x}
= ((var(x) ∪ var(e)) ∪ {x})\{x}
= (({x} ∪∅) ∪ {x})\{x}
= ({x} ∪ {x})\{x}
= {x}\{x}
= ∅
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
VL(∃x(R(y, z) ∧ ∀y((¬y ≈ x) ∨ R(y, z)))) = (VL(R(y, z) ∧ ∀y((¬y ≈ x) ∨ R(y, z))))\{x}
= (VL(R(y, z)) ∪ VL(∀y((¬y ≈ x) ∨ R(y, z))))\{x}
= (var(y) ∪ var(z) ∪ (VL((¬y ≈ x) ∨ R(y, z))\{y}))\{x}
= ({y, z} ∪ ((VL(¬y ≈ x) ∪ VL(R(y, z)))\{y}))\{x}
= ({y, z} ∪ ((VL(y ≈ x) ∪ var(y) ∪ var(z))\{y}))\{x}
= ({y, z} ∪ (var(y) ∪ var(x) ∪ {y, z})\{y})\{x}
= ({y, z} ∪ ({y} ∪ {x} ∪ {y, z})\{y})\{x}
= ({y, z} ∪ ({x, y, z}\{y}))\{x}
= ({y, z} ∪ {x, z})\{x}
= {x, y, z}\{x}
= {y, z}
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
A substituic¸a˜o de uma varia´vel x por um termo t em um termo σ
(denotada por σxt ) e´ definido por
y xt =
{
t, se x = y
y , caso contra´rio
cxt = c
fn(t1, . . . , tn)
x
t = fn(t1
x
t , . . . , tn
x
t )
◦(x , e)xe =
= ◦(xxe , exe )
= ◦(e, e)
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
A substituic¸a˜o de uma varia´vel x por um termo t em uma fo´rmula
ϕ (denotada por ϕxt ) e´ definido por
(R(t1, . . . , tn))
x
t = R(t1
x
t , . . . , tn
x
t )
(t1 ≈ tn)xt = t1xt ≈ t2xt
(¬ϕ)xt = (¬ϕxt )
(ϕ�ψ)xt = (ϕxt�ψxt )
(∀yϕ)xt =
{ ∀yϕ, se x = y
∀y(ϕxt ), caso contra´rio
(∃xϕ)xt =
{ ∃yϕ, se x = y
∃y(ϕxt ), caso contra´rio
Lo´gica para Computac¸a˜o
Lo´gica de Primeira-Ordem
Definic¸o˜es Recursivas
Exemplos de Definic¸o˜es Recursivas
Exemplo
1 ϕxx = ϕ
2 (Q(x)→ ∀xP(x))xy = (Q(y)→ ∀xP(x))
3 (¬∀y(x ≈ y))xz = (¬∀y(z ≈ y))
4 (¬∀y(x ≈ y))xy = (¬∀y(y ≈ y)), a varia´vel x tornou-se
quantificada quando substitu´ıda por y .
Definition
Dizemos que uma varia´vel x e´ substitu´ıvel em uma fo´rmula ϕ por
um termo t se para cada varia´vel y ocorrendo em t, na˜o existe
nenhuma subfo´rmula de ϕ da forma ∀yα ou ∃yα onde x ocorre
livre em α.
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Na lo´gica proposicional, damos significado as fo´rmulas atrave´s
da atribuic¸a˜o de valores verdade para as fo´rmulas atoˆmicas.
Para darmos significado as fo´rmulas lo´gicas, precisamos
interpretar:
1 O universo de discurso.
2 Os s´ımbolos predicativos.
3 Os s´ımbolos constantes.
4 Os s´ımbolos funcionais.
5 As varia´veis.
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Formalmente, uma interpretac¸a˜o I (tambe´m chamada de
estrutura) para uma linguagem lo´gica e´ uma func¸a˜o cujo
dom´ınio e´ a linguagem na˜o-lo´gica Σ = 〈C , (Fn)n∈N, (Pn)n∈N〉
e e´ tal que:
1 I atribui um conjunto na˜o vazio |I| chamado de universo (ou
dom´ınio) de I.
2 I atribui, para cada s´ımbolo predicativo pn de aridade n, uma
relac¸a˜o de aridade n pIn ⊆ |I|n, i.e., pIn e´ um conjunto de
n-tuplas dos elementos do universo.
3 I atribui, para cada s´ımbolo constante c , um elemento cI do
universo |I|
4 I atribui, para cada s´ımbolo funcional fn de aridade n, uma
func¸a˜o de aridade n f In : |I|n → |I|
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Example
Seja Σ a linguagem na˜o-lo´gica definida abaixo.
1 C = {s, a, z}
2 Fn = ∅ para todo n
3 P1 = {H,M} e para todo n 6= 1 Pn = ∅
Uma estrutura I1 para essa linguagem na˜o-lo´gica poderia ser:
1 Universo de |I1| = {Socrates,Aristoteles,Zeus,Heitor}
2 As constantes sa˜o interpretadas como sI1 = Socrates,
aI1 = Aristoteles e zI1 = Zeus
3 Os s´ımbolos predicativos sa˜o interpretados como
HI1 = {〈Socrates〉, 〈Aristoteles〉} e
MI1 = {〈Socrates〉, 〈Aristoteles〉}.
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Example (Continuac¸a˜o)
Dada a interpretac¸a˜o (estrutura) I1, qual seria o valor de verdade
das fo´rmulas abaixo?
1 H(s)
2 H(z)
3 ∃xM(x)
4 ∀xH(x)
5 ∀xM(x)
6 ∀x(H(x)→ M(x))
7 ∃x¬(x ≈ s ∨ x ≈ a ∨ x ≈ z)
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Example (Grafo)
Seja ΣG a linguagem na˜o-lo´gica definida abaixo.
1 C = ∅
2 Fn = ∅ para todo n
3 P2 = {E} e para todo n 6= 2 Pn = ∅
Uma estrutura IG para essa linguagem na˜o-lo´gica poderia ser:
1 Universo de |IG | = {a, b, c , d} (conjunto de no´s)
2 O s´ımbolo predicativo e´ interpretado como
EIG = {〈a, b〉, 〈b, a〉 〈b, c〉, 〈c , c〉} (os arcos)
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Example (Grafo)
Dada a interpretac¸a˜o (estrutura)IG , qual seria o valor de verdade
das fo´rmulas abaixo?
1 ∃xE (x , x)
2 ∀xE (x , x)
3 ∀x∃yE (x , y)
4 ∀x∀y(E (x , y)↔ E (y , x))
5 ∃x∀y¬E (y , x)
6 ∃x∀y¬E (x , y)
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Example (Naturais)
Seja ΣN a linguagem na˜o-lo´gica definida abaixo.
1 C = {c}
2 F1 = {f } e para todo n 6= 1 Fn = ∅
3 P2 = {p} e para todo n 6= 2 Pn = ∅
Uma estrutura IN para essa linguagem na˜o-lo´gica poderia ser:
1 Universo de |IN| = N (o conjunto dos nu´meros naturais)
2 O s´ımbolo c e´ interpretado como o valor 0, i.e., cIN = 0.
3 O s´ımbolo funcional f e´ interpretado como a func¸a˜o sucessor,
i.e., f IN(n) = n + 1
4 O s´ımbolo predicativo p e´ interpretado pelos pares 〈a, b〉 tal
que m ≤ n
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Example (Naturais)
Dada a interpretac¸a˜o (estrutura) IN, qual seria o valor de verdade
das fo´rmulas abaixo?
1 f (c) ≈ c
2 P(c , f (c))
3 ∃x(x ≈ c)
4 ∀xP(c , x)
5 ∀xP(x , x)
6 ∀x(¬P(f (x), x))
7 ∀x∃y(f (x) ≈ y)
8 ∀x∃y(x ≈ f (y))
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Podemos ter varia´veis livres ocorrendo em uma fo´rmula.
Assim, precisamos interpreta´-las, i.e., s : V → |I| uma func¸a˜o
do conjunto V das varia´veis no conjunto universo |I| de I
Definimos s(x |d) exatamente como a func¸a˜o s exceto por
uma coisa: no lugar da varia´vel x assume-se o valor d . Isto
pode ser expresso na seguinte equac¸a˜o:
s(x |d)(y) =
{
s(y), se y 6= x
d , caso contra´rio
Example (Naturais)
Seja s : V → N a func¸a˜o s(vi ) = i , i.e., s(v0) = 0, s(v1) = 1, . . .
1 s(v2|1)(v0) = 0
2 s(v2|1)(v2) = 1
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Como trabalhamos com termos, definimos uma func¸a˜o
s¯ : T (Σ)→ |I| dos termos no conjunto universo |I|. A func¸a˜o s¯ e´
definida recursivamente como:
1 Para cada varia´vel x ∈ V, s¯(x) = s(x).
2 Para cada s´ımbolo constante c ∈ C , s¯(c) = cI .
3 Se t1, . . . , tn ∈ T (Σ) sa˜o termos e fn ∈ Fn, enta˜o
s¯(f (t1, . . . , tn)) = f
I(s¯(t1), . . . , s¯(tn))
Example (Naturais)
1 s¯(c) = cIN = 0
2 s¯(f (c)) = f IN(s¯(c)) = s¯(c) + 1 = 0 + 1 = 1
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Satisfatibilidade da Lo´gica de Primeira-Ordem
Satisfatibilidade da Lo´gica de Primeira-Ordem
Definition
Escrevemos |=I ϕ[s] para indicar que a estrutura I satisfaz a
fo´rmula ϕ com s. A definic¸a˜ de |= e´ como segue:
1 |=I p(t1, . . . , tn)[s] ⇐⇒ 〈s¯(t1), . . . , s¯(tn)〉 ∈ pI
2 |=I t1 ≈ t2[s] ⇐⇒ s¯(t1) = s¯(t2)
3 |=I (¬ϕ)[s] ⇐⇒ NA˜O |=I ϕ[s]
4 |=I (ϕ ∧ ψ)[s] ⇐⇒ |=I ϕ[s] E |=I ψ[s]
5 |=I (ϕ ∨ ψ)[s] ⇐⇒ |=I ϕ[s] OU |=I ψ[s]
6 |=I (ϕ→ ψ)[s] ⇐⇒ SE |=I ϕ[s] ENTA˜O |=I ψ[s]
7 |=I ∃xϕ[s] ⇐⇒ Existe um d ∈ |I| tal que |=I ϕ[s(x |d)]
8 |=I ∀xϕ[s] ⇐⇒ Para todo d ∈ |I| temos que |=I ϕ[s(x |d)]
Escrevemos 6|=I ϕ[s] para indicar que a estrutura I na˜o satisfaz a
fo´rmula ϕ com s.
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Satisfatibilidade da Lo´gica de Primeira-Ordem
Satisfatibilidade da Lo´gica de Primeira-Ordem
Example (Naturais)
Dada a interpretac¸a˜o (estrutura) IN e a func¸a˜o s(vi ) = i , temos
que
1 |=IN v0 ≈ c[s] ⇐⇒ s¯(v0) = s¯(c) ⇐⇒ 0 = 0
2 6|=IN f (c) ≈ c[s] ⇐⇒ s¯(f (c)) 6= s¯(c) ⇐⇒ 1 6= 0
3 |=IN p(c , v1)[s] ⇐⇒ 〈s¯(c), s¯(v1)〉 ∈ pIN i.e. 0 ≤ 1
4 |=IN ∀v1(p(c, v1))[s]
⇐⇒ para todo n ∈ N temos que |=IN p(c , v1)[s(v1|n)]
⇐⇒ para todo n ∈ N temos que 〈s¯(v1|n)(c), s¯(v1|n)(v1)〉 ∈ pIN
⇐⇒ para todo n ∈ N temos que 〈0, n〉 ∈ pIN i.e. 0 ≤ n
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Satisfatibilidade da Lo´gica de Primeira-Ordem
Satisfatibilidade e Validade
Definic¸a˜o
Uma fo´rmula ϕ e´ dita satisfat´ıvel se existem uma estrutura I
e uma func¸a˜o s tal que |=I ϕ[s].
Uma fo´rmula ϕ e´ dita insatisfat´ıvel se toda estrutura I e
toda func¸a˜o s sa˜o tais que 6|=I ϕ[s].
Uma fo´rmula ϕ e´ dita va´lida (ou uma tautologia) se toda
estrutura I e toda func¸a˜o s sa˜o tais que |=I ϕ[s].
Neste caso escrevemos |= ϕ.
Uma fo´rmula ϕ e´ dita falsifica´vel se existem uma estrutura I
e uma func¸a˜o s tal que 6|=I ϕ[s].
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Satisfatibilidade da Lo´gica de Primeira-Ordem
Satisfatibilidade e Validade
Theorem
Demonstre que |= ¬∀xϕ→ ∃x¬ϕ ( va´lida)
Demonstrac¸a˜o.
Suponha I uma estrutura qualquer e s uma func¸a˜o qualquer.
Devemos demonstrar que SE |=I ¬∀xϕ[s] ENTA˜O |=I ∃x¬ϕ[s].
|=I ¬∀xϕ[s]
=⇒ 6|=I ∀xϕ[s]
=⇒ Na˜o e´ o caso de que ∀d ∈ I tal que |=I ϕ[s(x |d)]
=⇒ ∃d ∈ I tal que 6|=I ϕ[s(x |d)]
=⇒ ∃d ∈ I tal que |=I ¬ϕ[s(x |d)]
=⇒ |=I ∃x¬ϕ[s]
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Satisfatibilidade da Lo´gica de Primeira-Ordem
Satisfatibilidade e Validade
Theorem
∀x(P(x) ∨ I (x))→ ∀xP(x) ∨ ∀xI (x) e´ falsifica´vel
Demonstrac¸a˜o.
Devemos mostrar uma estrutura I e s uma func¸a˜o tais que
6|=I ∀x(P(x) ∨ I (x))→ ∀xP(x) ∨ ∀xI (x)[s]
Seja IN uma estrutura tal que
1 |IN| = N
2 PIN e´ interpretado como a relac¸a˜o Par
3 I IN e´ interpretado como a relac¸a˜o I´mpar
Basta demonstrar que para qualquer s, temos que
6|=IN ∀x(P(x) ∨ I (x))→ ∀xP(x) ∨ ∀xI (x)[s]
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Satisfatibilidade da Lo´gica de Primeira-Ordem
Semaˆntica da Lo´gica de Primeira-Ordem
Theorem
Sejam s1 e s2 func¸o˜es de V em |I| tais que ambas atribuem o
mesmo valor para cada varia´vel livre ocorrendo em ϕ 3.
|=I ϕ[s1]⇐⇒|=I ϕ[s2]
Corollary
Para uma sentenc¸a ϕ, temos que ou
1 I satisfaz a fo´rmula ϕ com todas as func¸o˜es s4; ou
2 I na˜o satisfaz a fo´rmula ϕ com nenhuma func¸a˜o s.
3Formalmente, ∀x(x ∈ VL(ϕ)→ s1(x) = s2(x))
4Dizemos que a estrutura I e´ um modelo de ϕ (escrito como |=I ϕ).
Lo´gica para Computac¸a˜o
Semaˆntica da Lo´gica de Primeira-Ordem
Consequ¨eˆncia Lo´gica
Consequ¨eˆncia Lo´gica
Definic¸a˜o
Sejam Γ um conjunto de fo´rmulas e ϕ uma fo´rmula. Escrevemos
Γ |= ϕ para indicar que a fo´rmula ϕ e´ consequ¨eˆncia lo´gica de Γ,
i.e., se para toda estrutura I e toda func¸a˜o s
(|=I ψ[s] para todo ψ ∈ Γ) =⇒|=I ϕ[s].
Escrevemos Γ 6|= ϕ se Γ |= ϕ na˜o e´ o caso.
Usualmente, escrevemos ϕ1, . . . ϕn |= ψ para representar
{ϕ1, . . . ϕn} |= ψ
Dizemos que ϕ e ψ sa˜o logicamente equivalentes sse ϕ |= ψ e ψ |= ϕ
Example
∀xϕ |= ¬∃x¬ϕ ∃xϕ |= ¬∀x¬ϕ ∀x(ϕ→ ψ) |= (∀xϕ→ ∀xψ)
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Axioma´tico
Sistema Axioma´tico
Existem diversos sistemas axioma´ticos corretos e completos
em relac¸a˜o a semaˆntica.
Ale´m de todos os esquemas axioma´ticos da lo´gica
proposicional, temos os seguintes esquemas axioma´ticos:
Axioma 4: ∀xϕ→ ϕxt , onde x e´ substitu´ıvel em ϕ por t
Axioma 5: ∀x(ϕ→ ψ)→ (∀xϕ→ ∀xψ)
Axioma 6: ϕ→ ∀xϕ, onde x na˜o ocorre livre em ϕ
Axioma 7: x ≈ x
Axioma 8: x ≈ y → (ϕ→ ϕ′), onde ϕ e´ atoˆmico e ϕ′ e´
obtido a partir de ϕ pela substituic¸a˜o
de x zero ou mais vezes por y
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Regras de Deduc¸a˜o Natural
Todas as regras da Lo´gica Proposicional e as seguintes regras
ϕ(a)
∀xϕ(x) ∀I
5
∀xϕ(x)
ϕ(t)
∀E 6
ϕ(t)
∃xϕ(x) ∃I
7
∃xϕ(x)
[ϕ(a)]
...
α
α ∃E 8
5a na˜o ocorre em nenhuma hipo´tese da qual a deduc¸a˜o de ϕ(a) dependa.
6x e´ substitu´ıvel por t em ϕ.
7x e´ substitu´ıvel por t em ϕ.
8a na˜o ocorre em ∃ϕ(x), nem em α e nem em qualquer outra hipo´tese da
qual a deduc¸a˜o de α dependa que na˜o as ja´ descarregadas pela regra.
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Sem a restric¸a˜o “a na˜o pode ocorrer em ϕ” de ∃xϕ(x), e´ poss´ıvel
deduzir incorretamente que:
∃xϕ(x) [ϕ(a)]1
ϕ(a)
1
∀x(ϕ(x))
Sem a restric¸a˜o “a na˜o pode ocorrer em ∃xϕ(x)” de ∀y∃x(y < x),
e´ poss´ıvel deduzir incorretamente que:
∀y∃x(y < x)
∃x(a < x)
[a < a]1
∃x(x < x)
∃x(x < x)
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
ExemplosSem a restric¸a˜o “a na˜o pode ocorrer em qualquer hipo´tese em que
a deduc¸a˜o de α dependa”, e´ poss´ıvel deduzir incorretamente que:
∃xPar(x)
∃xImpar(x)
[Par(a)]1 [Impar(a)]2
Par(a) ∧ Impar(a)
∃x(Par(x) ∧ Impar(x))
∃x(Par(x) ∧ Impar(x))
2
∃x(Par(x) ∧ Impar(x))
1
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que ∀xϕ(x),∀xψ(x) `DN ∀x(ϕ(x) ∧ ψ(x))
∀xϕ(x)
ϕ(a)
∀xψ(x)
ψ(a)
ϕ(a) ∧ ψ(a)
∀x(ϕ(x) ∧ ψ(x))
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que ∃x(ϕ(x) ∧ ψ(x)) `DN ∃xϕ(x) ∧ ∃xψ(x)
∃x(ϕ(x) ∧ ψ(x))
[ϕ(a) ∧ ψ(a)]1
ϕ(a)
∃xϕ(x)
∃xϕ(x)
1
∃x(ϕ(x) ∧ ψ(x))
[ϕ(a) ∧ ψ(a)]2
ψ(a)
∃xψ(x)
∃xψ(x)
2
∃xϕ(x) ∧ ∃xψ(x)
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que ∃x∀yϕ(x , y) `DN ∀y∃xϕ(x , y)
∃x∀yϕ(x , y)
[∀yϕ(a, y)]1
ϕ(a, b)
∃xϕ(x , b)
∃xϕ(x , b)
1
∀y∃xϕ(x , y)
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Exemplos
Prove que ϕ→ ∃xψ(x) `DN ∃x(ϕ→ ψ(x))
[ϕ]2 ϕ→ ∃xψ(x)
∃xψ(x)
[ψ(b)]3
ϕ→ ψ(b)
∃x(ϕ→ ψ(x)) [¬(∃x(ϕ→ ψ(x)))]1
⊥
⊥
3
ψ(a)
ϕ→ ψ(a)
2
∃x(ϕ→ ψ(x)) [¬(∃x(ϕ→ ψ(x)))]1
⊥
1
∃x(ϕ→ ψ(x))
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Lo´gica de Primeira-Ordem
Example (Teoria das Relac¸o˜es Equivalentes)
Seja Γ o conjunto de fo´rmulas abaixo.
∀x(xRx)
∀x∀y((xRy)→ (yRx))
∀x∀y∀z(((xRy) ∧ (yRz))→ (xRz))
Podemos demonstrar que
Γ ` ∀x∀y(∃u(((xRu) ∧ (yRu))→ ∀z((xRz)↔ (yRz))))
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Lo´gica de Primeira-Ordem
Seja
∏
1 a prova de que ∃u(aRu ∧ bRu) ` aRb
[∃u(aRu ∧ bRu)]1
[aRd ∧ bRd ]3
aRd
[aRd ∧ bRd ]3
bRd
∀x∀y((xRy)→ (yRx))
bRd → dRb
dRb
aRd ∧ dRb
∀x∀y∀z(((xRy) ∧ (yRz))→ (xRz))
(aRd ∧ dRb)→ aRb
aRb
aRb
3
Seja
∏
2 a prova de que ∃u(aRu ∧ bRu), bRd ` aRd∏
1
aRb [bRd ]2
aRb ∧ bRd
∀x∀y∀z(((xRy) ∧ (yRz))→ (xRz))
(aRb ∧ bRd)→ aRd
aRd
Lo´gica para Computac¸a˜o
Sistema Dedut´ıvel
Deduc¸a˜o Natural
Lo´gica de Primeira-Ordem
Seja
∏
3 a prova de que ∃u(aRu ∧ bRu), aRd ` bRd
[∃u(aRu ∧ bRu)]1
∏
1
aRb
∀x∀y(xRy → yRx)
aRb → bRa
bRa [aRd ]2
bRa ∧ aRd
∀x∀y∀z(((xRy) ∧ (yRz))→ (xRz))
(bRa ∧ aRd)→ aRd
bRd
A partir de
∏
1,
∏
2 e
∏
3, temos que
∏
2
aRd
∏
3
bRd
(aRd)↔ (bRd)
2
∀z((aRz)↔ (bRz))
∃u(((aRu) ∧ (bRu))→ ∀z((aRz)↔ (bRz)))
1
∀x∀y(∃u(((xRu) ∧ (yRu))→ ∀z((xRz)↔ (yRz))))
	Súmario
	Introdução
	Lógica Proposicional
	Alfabeto da Lógica Proposicional
	A Linguagem da Lógica Proposicional
	Provas por Indução
	Definições Recursivas
	Especificação de Problemas em Lógica
	Especificação de Problemas em Lógica Proposicional
	Conectivos em Linguagem Natutal versus em Lógica Proposicional
	Semântica da Lógica Proposicional
	Satisfatibilidade e Validade
	Conseqüência Lógica
	Método da Tabela da Verdade
	Exercícios Semântica da Lógica Proposicional
	De Morgan: |-3mu()()
	Contrapositiva: |-3mu()()
	Modus Ponens: {,}|-3mu
	Modus Tolens: {,}|-3mu
	Teorema da Dedução
	Sistema Dedutível
	Axiomático
	Dedução Natural
	Exercícios
	Tableaux
	Lógica de Primeira-Ordem
	Alfabeto da Lógica de Primeira-Ordem
	A Linguagem da Lógica de Primeira-Ordem
	Provas por Indução
	Definições Recursivas
	Semântica da Lógica de Primeira-Ordem
	Satisfatibilidade da Lógica de Primeira-Ordem
	Conseqüência Lógica
	Sistema Dedutível
	Axiomático
	Dedução Natural