Sistema Axiomático Pa (Lógica)
Uma tentativa de tentar entender como isso funciona.
Definições
Antes de tudo é bom a gente ter algumas definições em mente.
TODO: o que é Pa??
Axioma :: uma "afirmação" que é considerada verdadeira não porque pode ser provada, mas porque foi decidido que ela é verdadeira.
Em um sistema, um axioma é usado como a base para todo o funcionamento do sistema.
Exemplo: eu não acho que 1+1=2 é um axioma, exatamente, mas ele pelo menos funciona com base em algum, porque a soma entre números não é algo que existe exatamente na natureza... ela foi inventada para poder auxiliar nos cálculos.
O método "Pa" é um método puramente sintático, em contraste a alguns outros.
TODO: eu não sei exatamente o que isso implicaria. Mas dá a ideia de que, mesmo sabendo que uma coisa implica em outra, você não pode simplesmente pular para aquilo, e tem que usar somente as regras definidas para esse método.
Antes de tudo, vamos definir implicação:
Tenhamos um conjunto de fórmulas C, e uma fórmula H.
Ao dizer "C |- H", estamos afirmando que, sabendo que as fórmulas de C são verdadeiras, a fórmula H também será verdadeira.
As fórmulas presentes em C são chamadas de hipóteses.
Exemplo: C = {A -> B, A} e H = B
Ao dizer "C |- H", estamos afirmando que {A -> B, A} |- B
Ou seja, se I[A -> B] = T e I[A] = T, então I[B] = T
Mas, se dissermos "|- H", estaremos afirmando que H é verdadeira, sem precisar saber de outras coisas - ou seja, H é sempre verdade, uma tautologia.
Exemplo: H = P v ¬P
Ao dizer "|- H", estamos afirmando que |- P v ¬P
Ou seja, I[P v ¬P], para qualquer I.
E essa afirmação está correta porque se I[P] = F, vamos ter [false v ¬false] = [false v true] = true
E, se I[P] = T, vamos ter [true v ¬true] = [true v false] = true
O sistema Pa tem três axiomas "base":
Ax1: |- (H v H) -> H
Ax2: |- G -> (H v G)
Ax3: |- (H v G) -> ((E v H) -> (E v G))
Note como todas essas "afirmações" são no formato "|- H". Como falei anteriormente, isso quer dizer que elas são sempre verdades - ou seja, tautologias, e portanto podem ser usadas em qualquer situação.
TODO: tentar explicar intuitivamente cada um dos axiomas
TODO: E PORQUE ESCOLHERAM ESSES? PARECE HORRIVEL
Além dos três axiomas apresentados, ainda há algumas regras disponíveis:
Modus Ponens
Na verdade eu já acabei mostrando ela como exemplo, mas vou definir ela mais formalmente:
Tenhamos duas fórmulas, H e G.
i. H
ii. H -> G
iii. Portanto, G
Explicação intuitiva: se sabemos que H implica G, e sabemos que H é verdadeiro, então G tem que ser verdadeiro.
Regra da substituição
Tenhamos um conjunto de fórmulas C, e uma conclusão H, tal que C |- H.
Se H não possui nenhum símbolo proposicional presente em C, então podemos também dizer que |- H, porque H é verdadeiro independentemente de C ser verdade ou não.
Exemplo: C = {P -> Q}, H = R v ¬R
P -> Q não tem como nos ajudar a concluir que R v ¬R, porque nem fala sobre R - fala sobre P e Q.
Portanto, R v ¬R é verdade, mas não por causa que P -> Q é verdade, e portanto podemos concluir |- R v ¬R.
E, quando sabemos que |- H, ao trocarmos qualquer símbolo presente em H por qualquer coisa, |- H ainda vai ser verdadeiro.
Exemplo: |- (P ^ (P -> Q)) -> Q
Dizer que isso é verdade é dizer que, se I[P] = T e I[P -> Q] = T, então I[Q] = T. E faz sentido (é o modus ponens!)
E, se você trocar P por X e Q por J, teremos |- (X ^ (X -> J)) -> J, que ainda faz sentido.
A regra da substituição pode ser, de certo modo, considerada um dos princípios (se não "o princípio") da álgebra, eu acho, que é que, quando você tem uma variável livre em uma afirmação, se vocẽ trocar ela por qualquer outra coisa (a grosso modo) a afirmação ainda vai ser verdadeira.
Exemplo: x² > 0. Se você trocar x por 1, é verdade. Se trocar por -1, é verdade.
Usando o sistema Pa para provar coisas
Para usar esse sistema para provar a afirmação C |- H, você basicamente faz uma lista numerada de afirmações, até conseguir afirmar C |- H.
Lembrando que, se a afirmação é |- H, é a mesma coisa que dizer que C é vazio (C = {})
As afirmações podem ser:
- Um modus ponens de duas afirmações anteriores;
- Uma das hipóteses disponíveis (no conjunto C, ou, no caso de uma questão, que o professor disponibilizou);
- Um dos três axiomas (você pode usar a regra da substituição para trocar os H/G/E de lá);
Lembre sempre de anotar quais passos foram feitos naquela linha (geralmente à direita).
Exemplo: C |- R, onde C = {P, P -> (Q -> R), (Q v Q)}
| 1. | C |- P | do conjunto C |
| 2. | C |- (Q v Q) | do conjunto C |
| 3. | C |- (Q v Q) -> Q | Ax1, onde H = Q |
| 4. | C |- Q | Modus ponens de 2. e 3. |
| 5. | C |- P -> (Q -> R) | do conjunto C |
| 6. | C |- Q -> R | Modus ponens de 1. e 5. |
| 7. | C |- R | Modus ponens de 4. e 6. |
c.q.d.
Bibliografia
- Aulas na universidade [...]