Sintaxe e Semântica

Sintaxe e semântica proposicional

A lógica proposicional trata de frases que são verdadeiras ou falsas. A sintaxe diz quais cadeias de símbolos são fórmulas. A semântica diz o que cada fórmula vale, depois de escolher verdadeiro ou falso para cada átomo — uma letra como $p$ ou $q$ que está no lugar de uma frase inteira.

Essa escolha de verdadeiro ou falso para cada átomo é a valoração. Sem valoração, $p\to q$ ainda não tem valor de verdade. Com valoração, a fórmula $p\to q$ fica verdadeira ou falsa.

Sintaxe: átomos, conectivos e FBF

Variáveis proposicionais (átomos) $p,q,r,\ldots$ representam declarações atômicas, sem estrutura interna. "Está chovendo" pode ser $p$; o valor $V$ ou $F$ não é da sintaxe.

Conectivos:

• Negação $\neg p$: verdadeira exatamente quando $p$ é falsa.
• Conjunção $p\land q$: verdadeira só quando $p$ e $q$ são ambas verdadeiras.
• Disjunção $p\lor q$: verdadeira quando pelo menos uma é verdadeira (inclusiva).
• Implicação $p\to q$: falsa somente se $p$ é verdadeira e $q$ é falsa; nos outros três casos é verdadeira.
• Bicondicional $p\leftrightarrow q$: verdadeira quando $p$ e $q$ têm o mesmo valor.

A implicação $p\to q$ não afirma que $p$ causa $q$. Só exclui o caso "$p$ vale e $q$ falha". Essa definição segue uma ideia simples: um compromisso condicional só é quebrado quando o lado esquerdo (antecedente) ocorre e o lado direito (consequente) falha. Se o antecedente não ocorreu, o compromisso não foi violado, por isso os dois casos com antecedente $F$ são $V$. Os quatro casos:

Se o antecedente é falso, $p\to q$ é verdadeira, o chamado caso vacuoso. Isso segue da definição do conectivo; não é preciso montar a tabela para justificar esse caso.

Precedência usual: $\neg$ primeiro, depois $\land$ e $\lor$, depois $\to$ e $\leftrightarrow$. Parênteses desfazem a dúvida: $(p\lor q)\land r$ não é $p\lor(q\land r)$.

Uma fórmula bem formada (FBF) é obtida pelas regras abaixo:

1. Cada variável é uma FBF.
2. Se $\varphi$ é FBF, $\neg\varphi$ é FBF.
3. Se $\varphi$ e $\psi$ são FBF, então $(\varphi\land\psi)$, $(\varphi\lor\psi)$, $(\varphi\to\psi)$ e $(\varphi\leftrightarrow\psi)$ são FBF.

Válidas: $p$, $\neg q$, $(p\land q)$, $(\neg p\lor(q\to r))$. Inválidas: $p\land\to q$, $\neg$ sozinho, $(p\,q)$.

As regras existem para que cada fórmula tenha uma árvore de construção: sabemos qual é o conectivo principal e quais são as subfórmulas. Sem isso, $p\lor q\land r$ poderia ser duas fórmulas diferentes, e a valoração não saberia por onde começar.

Em $p\to(q\land p)$ o conectivo principal é $\to$: o antecedente é o átomo $p$ e o consequente é a conjunção $q\land p$. Em $(p\to q)\land p$ o principal é $\land$. São fórmulas distintas; atribuir $V$ ou $F$ aos átomos pode tornar uma verdadeira e a outra falsa. Com $p=F$ e $q=V$: a primeira é $F\to(V\land F)$, ou seja $F\to F=V$; a segunda é $(F\to V)\land F$, ou seja $V\land F=F$.

Semântica: o que é uma valoração

Uma valoração (atribuição) $\nu$ escolhe, para cada átomo, um valor em $\{V,F\}$. A fórmula composta não escolhe o valor à parte: ela o herda dos átomos pelas regras dos conectivos.

Duas fórmulas diferentes podem coincidir em uma valoração e divergir em outra. Classificar uma fórmula (sempre verdadeira, sempre falsa, às vezes) exige varrer todas as valorações; uma única valoração não basta.

Regras (as mesmas dos conectivos, agora como função de $\nu$):

• $\nu(\neg\varphi)=V$ se e somente se $\nu(\varphi)=F$;
• $\nu(\varphi\land\psi)=V$ se e somente se ambos são $V$;
• $\nu(\varphi\lor\psi)=V$ se e somente se ao menos um é $V$;
• $\nu(\varphi\to\psi)=F$ se e somente se $\nu(\varphi)=V$ e $\nu(\psi)=F$;
• $\nu(\varphi\leftrightarrow\psi)=V$ se e somente se $\nu(\varphi)=\nu(\psi)$.

Uma valoração concreta

Tome $\nu(p)=V$, $\nu(q)=F$ e a fórmula $p\to(q\land p)$.

Primeiro $q\land p$: $F\land V=F$ (falta o $q$). Depois $p\to(q\land p)$: $V\to F=F$, o único caso em que a implicação é falsa. Nesta valoração a fórmula é falsa. Uma única linha não decide se ela é sempre verdadeira: esta pode ser o único contraexemplo, ou o começo de uma fórmula sempre falsa.

Com $\nu'(p)=V$ e $\nu'(q)=V$: $q\land p$ é $V$, logo $V\to V=V$. A mesma fórmula já foi $F$ e $V$: às vezes verdadeira, às vezes falsa.

Tautologia, contradição e implicação válida

Depois de fixar a linguagem, os rótulos leem o conjunto de todas as valorações:

• Tautologia: verdadeira em toda valoração. Exemplo: $p\lor\neg p$.
• Contradição (insatisfatível): falsa em toda valoração. Exemplo: $p\land\neg p$.
• Satisfatível: verdadeira em alguma valoração. Toda tautologia é satisfatível; uma contingência também é.
• Contingência: satisfatível, mas não tautologia, verdadeira em alguma valoração e falsa em outra.

Uma valoração em que a fórmula vale só mostra que ela é satisfatível; para ser tautologia, ela deve valer em toda valoração, e para ser contradição, deve falhar em toda valoração.

O conectivo $\to$ fica dentro da fórmula. O traço $\Rightarrow$ (ou "implica validamente") é uma afirmação sobre fórmulas: $\varphi\Rightarrow\psi$ significa que, em toda valoração em que $\varphi$ é verdadeira, $\psi$ também é, equivalentemente, $\varphi\to\psi$ é tautologia.

Não confundir:

• $p\to q$ pode ser contingente (vale ou não, conforme $p$ e $q$);
• $p\Rightarrow q$ afirma que essa implicação nunca falha.

Exemplo

Classifique as afirmações abaixo.

I. $L\to(\neg L\to M)$ é tautologia.

II. $\neg L\land(L\land\neg M)$ é contradição.

III. $(L\lor N)\land\neg N\Rightarrow L$.

IV. $M\leftrightarrow N$ é a mesma afirmação que $\neg M\lor N$.