Lógica Proposicional - Sistema Semântico

Sistema Semântico

Se no sistema dedutivo abordámos as regras de inferência, que falam sobre as entidades da linguagem, no sistema semântico vamos abordar as fbfs e os símbolos lógicos sob o ponto de vista do seu significado. O sistema baseia-se no conceito de interpretação, conceito este que neste contexto é definido a partir de uma função de valoração.

Função de Valoração

Uma função de valoração é uma função vv que atribui valores lógicos (verdadeiro ou falso) a um conjunto de símbolos de proposição.

v:P{V,F}v: P \mapsto \{V, F\}

Uma função de valoração pode ser tal que:

v(P)=V,v(Q)=F.v(P) = V,\\ v(Q) = F.

Isto é, segundo esta função de valoração, a proposição PP tem valor verdadeiro, enquanto que a proposição QQ tem valor falso.

Associada ao conceito de função de valoração temos ainda a noção de interpretação:

Interpretação

Dada uma função de valoração vv, uma interpretação é uma função IvI_{v} que atribui valores lógicos a um conjunto de fbfs.

Iv:LLP{V,F}I_{v}:\mathcal{L}_{LP} \mapsto \{V, F\}

A interpretação é tal que:

  • Caso α\alpha seja uma fbf atómica, Iv(α)=v(α)I_{v}(\alpha) = v(\alpha);
  • Caso α\alpha seja uma fbf não atómica, IvI_{v} é definida através de uma tabela de verdade, como por exemplo:
Iv(α)I_{v}(\alpha) Iv(β)I_{v}(\beta) Iv(αβ)I_{v}(\alpha \wedge \beta) Iv(αβ)I_{v}(\alpha \vee \beta) Iv(αβ)I_{v}(\alpha \to \beta)
VV VV VV VV VV
VV FF FF VV FF
FF VV FF VV VV
FF FF FF FF VV

Por abuso de linguagem, referir-nos-emos a partir de agora à interpretação IvI_{v} através de II.

Outro conceito interessante a ter em conta é o da satisfação. Dadas uma fbf α\alpha e uma interpretação II, podemos dizer que II satisfaz α\alpha caso I(α)=VI(\alpha) = V, ou que α\alpha é verdadeira segundo a interpretação II. Caso contrário, claro, dizemos que II não satisfaz α\alpha/que α\alpha é falsa segundo II. A título de exemplo, podemos afirmar que a função de valoração acima satisfaz PQP \wedge Q mas não ¬PQ\neg P \wedge Q.

Exemplo - Tabela de Verdade + Satisfação
PP QQ PQP \wedge Q R (PQ)R(P \wedge Q) \to R
VV VV VV VV VV
VV VV VV FF FF
VV FF FF VV VV
VV FF FF FF VV
FF VV FF VV VV
FF VV FF FF VV
FF FF FF VV VV
FF FF FF FF VV

Através da tabela acima, podemos afirmar que a fbf (PQ)R(P \wedge Q) \to R apenas não é verdadeira no caso de ambos os símbolos de proposição PP e QQ serem verdadeiros e RR falso - a fbf não é satisfeita por nenhuma interpretação onde I(P)=V,I(Q)=V,I(R)=FI(P) = V, I(Q) = V, I(R) = F.

Uma fbf diz-se satisfazível caso exista pelo menos uma interpretação que a satisfaça. Assim sendo, a fbf do exemplo acima é satisfazível, visto que existem 7 interpretações que a satisfazem (e 1 que não a satisfaz, mas que para este efeito é irrelevante). Dentro do mesmo conceito, podemos olhar para as fbfs falsificáveis, precisamente opostas às satisfazíveis - existe pelo menos uma interpretação que não as satisfaz. O exemplo acima é também falsificável, visto que, lá está, existe 1 interpretação para a qual é falsa. Podemos, então, afirmar que uma fbf pode ser satisfazível e falsificável ao mesmo tempo. Temos, ainda, que uma fbf é satisfazível apenas se a sua negação for falsificável.

Podemos ainda olhar para uma fbf e comentar a sua tautologia - uma fbf diz-se tautológica (ou, por abuso de linguagem, válida) caso seja verdadeira para qualquer interpretação. Tal como com as últimas definições, podemos encontrar a oposta de uma fbf tautológica, uma fbf contraditória - caso não seja satisfeita por qualquer interpretação. Uma fbf α\alpha é tautológica caso a sua negação, α\alpha, seja contraditória. A fbf P¬PP \wedge \neg P, por exemplo, é contraditória.

A tabela de verdade abaixo mostra que a fbf (P(PQ))Q(P \wedge (P \to Q)) \to Q é tautológica:

PP QQ PQP \to Q P(PQ)P \wedge (P \to Q) (P(PQ))Q(P \wedge (P \to Q)) \to Q
VV VV VV VV VV
VV FF FF FF VV
FF VV VV FF VV
FF FF VV FF VV

Podemos ainda aplicar estas lógicas a conjuntos de fbfs.

Um conjunto de fbfs diz-se satisfazível caso exista pelo menos uma interpretação que satisfaça todas as fbfs desse conjunto. Diz-se, por outro lado, contraditório caso nenhuma interpretação satisfaça todas as fbfs desse conjunto. O conjunto {P,Q,PQ}\{P, Q, P \to Q\}, por ex., é satisfazível, visto que há uma interpretação (I(P)=V,I(Q)=VI(P) = V, I(Q) = V) que satisfaz todas as fbfs do conjunto.

Modelo do conjunto de fórmulas

Dado um conjunto de fbfs Δ\Delta, um modelo desse conjunto é qualquer interpretação que satisfaz todas as fbfs do conjunto.

Um argumento (Δ,α)(\Delta, \alpha) diz-se válido caso não exista nenhuma interpretação que torne todas as proposições de Δ\Delta verdadeiras e α\alpha falsa - nesse caso, podemos escrever Δα\Delta \models \alpha, ou "α\alpha é consequência semântica de Δ\Delta". Podemos também dizer que Δα\Delta \models \alpha caso todos os modelos de Δ\Delta satisfaçam α\alpha.

Por exemplo, dado o argumento ({PQ,R},PR)(\{P \wedge Q, R\}, P \wedge R), podemos verificar que o argumento é válido, visto que não existe nenhuma interpretação que torne as premissas verdadeiras e a conclusão falsa.

PP QQ RR PQP \wedge Q PRP \wedge R
VV VV VV VV VV
VV VV FF VV FF
VV FF VV FF VV
VV FF FF FF FF
FF VV VV FF FF
FF VV FF FF FF
FF FF VV FF FF
FF FF FF FF FF

Teorema da refutação

Dado um conjunto de fbfs Δ\Delta e uma fbf α\alpha, Δα\Delta \models \alpha se e só se Δ{¬α}\Delta \cup \{\neg \alpha\} não for satisfazível.

Note-se que no exemplo abaixo, os espaços marcados como irrelevantes devem-se às premissas não serem todas verdadeiras, pelo que nada podemos extrair em relação à validade do argumento.

PP QQ RR PRP \to R QRQ \to R PQP \vee Q (PQ)R(P \vee Q) \to R
VV VV VV VV VV VV VV
VV VV FF FF FF -- --
VV FF VV VV VV VV VV
VV FF FF FF VV -- --
FF VV VV VV VV VV VV
FF VV FF VV FF -- --
FF FF VV VV VV FF VV
FF FF FF VV VV FF VV

Acima, podemos ver o exemplo do argumento {PR,QR}(PQ)R\{P \to R, Q \to R\} \models (P \vee Q) \to R. As colunas 4 e 5 são as das premissas, a 7 a da conclusão - como podemos notar, não existe nenhuma interpretação onde as premissas sejam todas verdadeiras e a conclusão falsa. Podemos, portanto, dizer que o argumento é válido.

Podemos ainda demonstrar tautologias:

PP QQ ¬(PQ)\neg(P \wedge Q) ¬P¬Q\neg P \vee \neg Q ¬(PQ)(¬P¬Q)\neg(P \wedge Q) \leftrightarrow (\neg P \vee \neg Q)
VV VV FF FF VV
VV FF VV VV VV
FF VV VV VV VV
FF FF VV VV VV

Aqui, podemos afirmar que ¬(PQ)(¬P¬Q)\neg(P \wedge Q) \leftrightarrow (\neg P \vee \neg Q) é uma tautologia, ou seja, que ¬(PQ)(¬P¬Q)\models \neg(P \wedge Q) \leftrightarrow (\neg P \vee \neg Q)

Correção e Completude

A lógica proposicional é correta e completa.

  • Correção - Para quaisquer fbfs α1,,αk\alpha_{1}, \cdots, \alpha_{k} e β\beta, se pudermos derivar β\beta de {α1,,αk}\{\alpha_{1}, \cdots, \alpha_{k}\}, ou seja, se {α1,,αk}β\{\alpha_{1}, \cdots, \alpha_{k}\} \vdash \beta, então {α1,,αk}β\{\alpha_{1}, \cdots, \alpha_{k}\} \models \beta. Qualquer argumento demonstrável é válido de acordo com a semântica.

  • Completude - Para quaisquer fbfs α1,,αk\alpha_{1}, \cdots, \alpha_{k} e β\beta, se pudermos afirmar que β\beta é consequência semântica de {α1,,αk}\{\alpha_{1}, \cdots, \alpha_{k}\}, ou seja, se {α1,,αk}β\{\alpha_{1}, \cdots, \alpha_{k}\} \models \beta, então {α1,,αk}β\{\alpha_{1}, \cdots, \alpha_{k}\} \vdash \beta. Qualquer argumento válido de acordo com a semântica é demonstrável.

Podemos, então, voltar a olhar para a relação entre os sistemas dedutivo e semântico: