Lógica Proposicional: Ordem de Precedência, Comprimento e Subfórmulas

Prévia do material em texto

UNIP UNIVERSIDADE 
PAULISTA
Professor: Yure de Queiroz Lima
E-mail: yureql@hotmail.com
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: ᴧ, v
Menor precedência: →
Ultimo a ser resolvido ↔
Exemplo:
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?