LOGICA MATEMATICA

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 forma simplificada de representação de fórmulas, onde os símbolos de pontuação podem ser omitidos.

a) (PQ v true)

Não é uma fórmula da Lógica Proposicional

b) (P ^ Q) → ((Q ↔ P) v ¬ ¬ R)

Sim é uma fórmula da Lógica Proposicional

c) ¬ ¬ P

Sim é uma fórmula da Lógica Proposicional

d) v Q

Não é uma fórmula da Lógica Proposicional

e) (P ^ Q) → ((Q ↔ ¬ R)

Sim é uma fórmula da Lógica Proposicional

2 – Responda as questões a seguir, justificando suas respostas.

a) Existe fórmula sem símbolo de pontuação?

Sim, as fórmulas mais simples podem possuir apenas o valor verdade, ou símbolo proposicional.

b) Quantos tipos de símbolos possui o alfabeto da Lógica Proposicional? Quais são estes símbolos?

Quatro tipos, símbolo de pontuação, símbolo de valor verdade, símbolos proposicionais e conectivos proposicionais.

c) Existe fórmula da Lógica Proposicional com algum conectivo, mas sem símbolo de pontuação?

Não, pois todas as fórmulas com conectivos, tem que possuir uma 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)

4 – Elimine o maior número possível de símbolos de pontuação das fórmulas a seguir, mantendo a representação da fórmula original.

a) ((¬ (¬ P)) ↔ ((¬ ((¬ (¬ (P v Q))) → R)) ^ P))

b) (¬ P → (Q v R)) ↔ ((P ^ Q) ↔ (¬ ¬ R v ¬ P))

c) ((P v Q) → (P → (¬ Q)))

5 – Considere as concatenações de símbolos a seguir. A partir da introdução de símbolos de pontuação, identifique quais fórmulas da Lógica Proposicional é possível obter.

a) P v ¬ Q → R ↔ ¬ R

b) Q → ¬ P ^ Q

c) ¬ P v Q ↔ Q

d) ¬ ¬ P → Q ↔ P ^ P ¬ ¬ R

6 – Conforme a definição de fórmula, os conectivos proposicionais diferentes de ¬ devem ser inscritos na forma infixa. Isto é, o conectivo ^ por exemplo deve ser escrito entre dois símbolos proposicionais