UNIP UNIVERSIDADE
PAULISTA
Professor: Yure de Queiroz Lima
E-mail: [email protected]
Ordem de Precedência
 Na Lógica Proposicional, a ordem de
precedência dos conectivos proposicionais é
definida por:
 Maior precedência: ⌐
 Precedência intermediária: →, ↔
 Menor precedência: ᴧ, v
 Exemplo: P → Q ↔ R
Possui duas interpretações: ((P→Q)↔R) ou
(P→(Q↔R))
Omissão de Símbolos
 Assim como na língua portuguesa é freqüente a
omissão de símbolos de pontuação.
 Algo análogo também é considerado na Lógica
Proposicional.
 Exemplo:
 (((P v R) → true) ↔ (QᴧS))
Pode ser reescrita como:
(P v R) → true
↔
QᴧS
 Ou ainda: ((P v R) → true) ↔ (Q ᴧ S)
Comprimento de uma fórmula
 Se H é um símbolo proposicional ou de verdade
então comp[H]=1
 Se H e G são fórmulas da Lógica Proposicional,
então
comp[¬H] = comp[H]+1
comp[H v G] = comp[H] + comp[G]+1
comp[H ᴧ G] = comp[H] + comp[G]+1
comp[H → G] = comp[H] + comp[G]+1
comp[H ↔ G] = comp[H] + comp[G]+1
Comprimento de uma fórmula
 Os
símbolos de pontuação não são
considerados no cálculo.
 São considerados somente os símbolos
proposicionais, de verdade e os conectivos
proposicionais.
 Exemplo: As Fórmulas
(P ᴧ Q) e ((P → Q) ↔ R)
Têm comprimentos iguais a 3 e 5,
respectivamente.
Definição (subfórmula)
Seja H uma fórmula da Lógica Proposicional. Uma
subfórmula de H é definida por.
 H é uma subfórmula de H
 Se H = (¬ G), então G é uma subfórmula de H
 Se H é uma fórmula do tipo: (G v E), (G ᴧ E), (G →
E) ou (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
- Informalmente, uma subfórmula de H é um pedaço de
H que é fórmula.
Exercícios
- 1 Considere as concatenações de símbolos do alfabeto da
-
Lógica Proposicional dadas a seguir. Identifique aquelas
que são fórmulas da Lógica Proposicional. Considere a
forma simplificada de representação de fórmulas, onde os
símbolos de pontuação podem ser omitidos.
a) (PQ v true)
b) (P ᴧ Q) → ((Q ↔ P) v ¬¬R)
c) ¬¬R
d) v Q
e) (P ᴧ Q) → (( Q ↔ ¬R))
f ) (P v Q) ↔ (( Q ᴧ R) → ᴧ)
Exercícios
- 2 Existe fórmula sem símbolo de pontuação?
- 3 Determine o comprimento e as subfórmulas das
fórmulas a seguir.
- a) ((P v Q) ↔( P→ Q)) ᴧ true
- b) P → ((Q → R) → ((P → R) → (P → R )))
- c) ((P →¬P) ↔ ¬P) v Q
- d) ¬(P → ¬P)
- e) (P v Q)
- f) ((P ᴧ Q) → R)
- g) ((P v Q) ↔ (P ᴧ Q))
Exercícios
- 4 Elimine o maior número possível de parênteses da
fórmula, sem alterar seu significado original:
- a) ((¬X) v ((¬(X v Y )) v Z)). Saltar 4 linhas
- b) ((¬ (¬ P)) ↔ ((¬ (( ¬ ( ¬ (P v Q))) → R)) ᴧ P))
Perguntas?