Lógica Proposicional

Prévia do material em texto

Lógica Proposicional
A lógica proposicional clássica trata de
sentenças onde podemos atribuir um valor
de verdade (verdadeiro ou falso). Estas
sentenças chamamos de proposições. A
lógica proposicional é uma linguagem
formal e para trabalharmos com ela
precisamos primeiro, conhecê-la
INTRODUÇÃO
O alfabeto é constituído por:
LINGUAGEM
Símbolos de pontuação: ( ).
Símbolos proposicionais: P, Q, R,
S (podem aparecer em letras
minúsculas).
Conectivos: ¬ (não), ∧ (e), ∨ (ou),
→ (se-então), ↔ (se, e somente
se).
As fórmulas são construídas conforme as
regras a seguir:
Todo símbolo proposicional é
uma fórmula.
Se H é fórmula (¬H) é fórmula.
Se H e G são fórmulas, então H ∨
G, H ∧ G, H → G e H ↔ G são
fórmulas.
A ordem de precedência dos conectivos
proposicionais é definida por:
Maior precedência: ¬
Precedência intermediária: →, ↔ 
Menor precedência: ∧, ∨ 
Seja H uma fórmula, então:
H é subfórmula de H.
Se H = (¬G) então G é subfórmula
de H
Se H é do tipo (G ∨ E), (G ∧ E), (G 
→ E), (G ↔ E), então G e E são
subfórmulas de H.
Se G é subfórmula de H, então
toda subfórmula de G é
subfórmula de H.
Como representar as sentenças usando
fórmulas da Lógica Proposicional? Vejamos
os exemplos abaixo:
EXEMPLOS
Exemplo 1: “Se eu sou feliz, então você é
feliz". P = eu sou feliz; Q = você é feliz.
P → Q.
Exemplo 2: “Se eu sou feliz, você é infeliz, e
se você é infeliz, eu não sou feliz". P = eu
sou feliz; ¬P = eu não sou feliz; ¬Q = você é
infeliz
(P → (¬Q)) ∧ ((¬Q) → (¬P)) 
Exemplo 3: “Se a lua é de queijo, então
Pedro é inteligente". P = lua de queijo; Q =
Pedro inteligente
(P → Q) 
OBS: a fórmula H → G não precisa ser uma
relação de causa e consequência “natural”,
por exemplo, “Se chover, então a rua ficará
molhada”
Se H é uma fórmula, definimos o
comprimento de H por:
Se H = P, então comp[H] = 1.
comp[¬H] = comp[H] + 1.
comp[H ∨ G] = comp[H ∧ G] =
comp[H → G] = comp[H ↔ G] =
comp[H] + comp[G] + 1.
SEMÂNTICA
Uma interpretação I é uma função binária
na qual:
O domínio de I é o conjunto das
fórmulas.
O contradomínio de I é {T, F}.
Definimos indutivamente que:
I[¬H] = T se, e somente se, I[H] = F
I[H∨G] = T se, e somente se, I[H] =
T ou I[G] = T
I[H∧G] = T se, e somente se, I[H] =
T e I[G] = T
I[H→G] = T se, e somente se, I[H] =
F ou I[G] = T
I[H↔G] = T se, e somente se, I[H] =
I[G] 
Interpretação das fórmulas: Tabela-
verdade:
OBS: I[T] = T e I[F] = F.
PROPRIEDADES SEMÂNTICAS
O princípio do terceiro excluído: dada uma
proposição e sua negação, pelo menos
uma delas é verdadeira.
Princípio da não contradição: uma
proposição e sua negação não podem ser
verdadeiras para a mesma interpretação. 
Tautologia (fórmula válida):
Seja H uma fórmula. Então H é
uma tautologia (fórmula válida)
se, e somente se, para toda
interpretação I, I [H] = T.
Satisfabilidade:
Seja H uma fórmula da Lógica
Proposicional. Então H é uma
fórmula satisfatível (factível) se,
e somente se, existe
interpretação I tal que I [H] = T.
OBS: tautologia ⇒ satisfatível .
Seja β o conjunto de fórmulas β =
{H1, H2, ...}. Então β é um conjunto
satisfatível se, e somente se,
existe uma interpretação I tal que
I[H1] = I[H2] = ··· = T.
Contingência:
Seja H uma fórmula da Lógica
Proposicional. Então H é uma
contingência se, e somente se,
existem interpretações I e J tal
que I [H] = T e J [H] = F 
Se H é tautologia então H não é
contingência. 
Se H é contingência então H é
satisfatível. 
Contradição:
Seja H uma fórmula. Então H é
uma contradição se, e somente
se, para toda interpretação I, I [H]
= F. 
OBS: H é contradição se, e
somente se, (¬H) é tautologia. 
Equivalência Semântica:
Sejam H e G duas fórmulas da
Lógica proposicional. Então H e G
são equivalentes (H ≡ G ou H ⇔
G) se, e somente se, para toda
interpretação I, I [H] = I [G]. 
Dadas duas fórmulas G e H,
temos: H equivalente a G se, e
somente se, (H ↔ G) é tautologia.
Leis de Morgan:
¬(P ∨ Q) equivale a (¬P ∧ ¬Q) 
¬(P ∧ Q) equivale a (¬P ∨ ¬Q)
Implicação Semântica
Sejam H e G duas fórmulas.
Então H implica G (H |= G ou H ⇒
G) se, e somente se, para toda
interpretação I, se I [H] = T então I
[G] = T.
Sejam H e G duas fórmulas da
Lógica Proposicional. Então: H
não implica semanticamente G
se, e somente se, existe
interpretação I tal que I [H] = T e I
[G] = F.
Dadas duas fórmulas H e G,
temos H implica G se, e somente
se, (H → G) é tautologia. 
CONJUNTOS COMPLETOS
Seja ψ um conjunto de conectivos.
Dizemos que ψ é um conjunto completo
se as condições a seguir são satisfeitas:
Dada uma f´ormula H do tipo: ¬P,
(P ∨ Q), (P ∧ Q), (P → Q) ou (P ↔
Q) então é possível determinar
uma outra fórmula G equivalente
a H tal que G contém apenas
conectivos do conjunto ψ e os
símbolos P e Q presentes em H.
P∧Q equivale a ¬(¬P∨¬Q)
P → Q equivale a (¬P ∨ Q)
G = (¬P ∨ Q) ∧ (¬R ∨ ¬Q ∨ P) ∧
(P ∨ S) está na forma fnc.
Existe H fnd equivalente a H. 
Seja H uma fórmula da lógica
proposicional, então:
Construa a tabela verdade
Construa a tabela-verdade de H
H está na forma normal disjunta (fnd) se é
uma disjunção de conjunção de literais.
Extraia as linhas em que H é F:
Um literal é um símbolo proposicional ou
sua negação.
H = (¬P ∧ Q) ∨ (¬R ∧ ¬Q ∧ P) ∨
(P ∧ S) está na forma fnd. 
Exemplo: {¬, ∨} é completo:
P ↔ Q equivale a ¬(¬(¬P ∨ Q) ∨
¬(¬Q ∨ P))
O conectivo nand é definido pela
correspondência (P nand Q) = ¬(P ∧ Q). 
OBS: nand é completo.
O conectivo nor é definido pela
correspondência (P nor Q) = ¬(P ∨Q).
FORMAS NORMAIS
H está na forma normal conjuntiva (fnc) se
é uma conjunção de uma disjunção de
literais.
Existe H fnc equivalente a H. 
Vamos determinar uma fórmula fnd
equivalente a H = (P → Q) ∧ R: 
Extraia as linhas em que H é T
1ª Linha: I[P] = I[Q] = I[R] = T: P ∧ Q
∧ R
2ª Linha: ¬P ∧ Q ∧ R
3ª Linha: ¬P ∧ ¬Q ∧ R
Hfnd = (P ∧ Q ∧ R) ∨ (¬P ∧ Q ∧
R) ∨ (¬P ∧ ¬Q ∧ R)
Vamos determinar uma fórmula fnc
equivalente a H = (P → Q) ∧ R: 
1ª Linha: I[P] = I[Q] = T e I[R] = F: ¬P
∨ ¬Q ∨ R
2ª Linha: ¬P ∨ Q ∨ ¬R
3ª Linha: P ∨ Q ∨ R
4ª Linha: P ∨ ¬Q ∨ R
5ª Linha: P ∨ Q ∨ R
Hfnc = (¬P ∨ ¬Q∨ R)∧(¬P ∨Q∨
¬R)∧(P ∨Q∨ R)∧(P ∨ ¬Q∨
R)∧(P ∨Q∨ R)
OBS: As formas normais não são únicas. No
exemplo, H = (P → Q)∧R é equivalente a
Hfnc = (¬P ∨ Q) ∧ R.
Método da tabela-verdade: Em geral, se H
é uma fórmula com n símbolos
proposicionais diferentes e m símbolos
proposicionais com possíveis repetições.
No pior caso, o custo é proporcional a 2n *
m². Ou seja, computacionalmente, o
método da tabela-verdade nem sempre é
viável. 
((P → Q) ∧ (Q → R)) →F (P → R) 
((P → Q) ∧ (Q → R)) →F (P → R) 
((P → Q) ∧ (Q → R)) →F (P → ) 
((P → Q) ∧ (Q → )) →F (P → ) 
Exemplo: Prove, usando axiomatização,
que A → B, C → A, C B.
Um teorema A é uma fórmula tal que
existe uma dedução para A. Denotamos
um teorema por A.
(∨2) Q → (P ∨ Q)
(∨3) (P → R) → ((Q → R) → ((P ∨
Q) → R)) 
(¬1) (P → Q) → ((P → ¬Q) → ¬P) 
(¬2) ¬¬P → P
Regra de inferência: Modus ponens: Se P
implica Q é verdadeiro e P é verdadeiro,
então Q é verdadeiro, ou seja, ((P → Q) ∧
P) → Q.
A → B hipótese 1 
C → A hipótese 2 
C hipótese 3
A modus ponens 2,3
B modus ponens 1, 4
Dedução natural: As inferências são
realizadas por regras em que hipóteses
podem ser introduzidas na prova e que
deverão ser posteriormente descartadas
para consolidação da prova.
MÉTODOS DE DEDUÇÃO
Exemplo: Para provar que H = (((P → Q) ∧
(Q → R)) → (P → R)) é tautologia, suponha,
por absurdo, que H não é tautologia. Então
existe I, tal que I[H] = F. 
Método da negação ou redução ao
abusdo:
Negamos inicialmente aquilo que
queremos demonstrar
Utilizamos um conjunto de
deduções. Se ao final concluirmos
um fato absurdo, devemos rever
nossa suposição inicial
Dessa forma, caso se obtenha um
absurdo, a conclusão é que a
suposição inicial é falsa.
Logo, I[P] = T e I[R] = F:
Logo, I[Q] = T e I[Q] = F, Absurdo! Portanto,
H é tautologia.
Método da axiomatização: Um axioma é
uma premissa considerada
necessariamente evidente e verdadeira,
fundamento de uma demonstração.São os
axiomas da lógica:
(→1) P → (Q → P)
(→2) (P → (Q → R)) → ((P → Q) →
(P → R))
(∧1) P → (Q → (P ∧ Q)) 
(∧2) (P ∧ Q) → P
(∧3) (P ∧ Q) → Q
(∨1) P → (P ∨ Q) 
Uma dedução é uma sequência de
fórmulas tal que cada fórmula ou é um
axioma ou é obtido a partir de regras de
inferência (modus ponens).
Teorema da Dedução: Sejam β um
conjunto de fórmulas e A e B fórmulas,
então:
Regras de inferência:
Exemplo: DN (A → C) → ((B → C) → ((A ∨
B) → C)):
Teorema da Correção: Seja H uma fórmula
da lógica proposicional. Se H (H é
teorema) então H é tautologia. 
TABLEAUX SEMÂNTICO
Os tableaux semânticos são como árvores
e são expandidos a partir de regras de
inferência.
Regras de inferência:
Um ramo corresponde a um ramo da
árvore que descreve o tableaux. 
Um ramo é fechado se ele contém uma
fórmula e sua negação.
Um ramo é saturado se para toda fórmula
H do ramo, H já foi expandida por alguma
regra ou se não é possível aplicar nenhuma
regra em H. 
Um ramo é aberto se é saturado e não é
fechado. 
Um tableau é fechado quando todos os
seus ramos são fechados. 
Um tableau é aberto se algum dos seus
ramos é aberto.
Teorema da Completude: Seja H uma
fórmula da lógica proposicional. Se H é
tautologia então H (H é teorema).