Lógica proposicional

«Há autorização» ou é verdade ou é falso. Uma frase assim, que é verdadeira ou falsa sem meio termo, chama-se proposição, uma afirmação com valor de verdade $T$ ou $F$. «Abre a porta!» é uma ordem, por isso não é uma proposição: não faz sentido dizer que é verdadeira ou falsa.

A lógica proposicional, o estudo de como combinar proposições para decidir o valor do conjunto, parte destas frases simples. «A porta abre» quando «há autorização» e «o sistema não está bloqueado». Se escrevermos $p$ para «há autorização» e $q$ para «o sistema está bloqueado», com $\land$ a ler-se «e» e $\neg$ a ler-se «não», a condição escreve-se $p\land\neg q$. Não precisamos de saber como se obtém a autorização para calcular o valor de $p\land\neg q$.

Fórmulas e subfórmulas

Uma fórmula bem formada constrói-se pelas regras seguintes:

• Cada variável proposicional, como $p$, é uma fórmula.
• Se $\varphi$ é fórmula, $\neg\varphi$ também é.
• Se $\varphi$ e $\psi$ são fórmulas, $\varphi\land\psi$, $\varphi\lor\psi$ e $\varphi\to\psi$ também são.

Os parênteses indicam a construção. Usamos a precedência $\neg$, depois $\land$, depois $\lor$, depois $\to$. A implicação associa à direita: $p\to q\to r$ significa $p\to(q\to r)$.

Em $\neg(p\land q)\to r$, a conetiva principal é $\to$. As subfórmulas imediatas são $\neg(p\land q)$ e $r$. Descendo na construção encontramos $p\land q$, $p$ e $q$. Uma subfórmula é uma expressão completa da árvore sintática; $q)\to$ não é uma subfórmula.

Avaliação pela árvore sintática

Para $p \land \neg q$ com $p=T$ e $q=T$, calcula dentro para fora: $\neg q=F$ e depois $T \land F=F$. A conetiva principal é o $\land$ final; as subfórmulas imediatas são $p$ e $\neg q$. A árvore sintática é:

      ∧
     / \
    p   ¬
        |
        q

Lê a árvore de baixo para cima quando avalias e de cima para baixo quando identificas a regra principal.

As conetivas

A disjunção $\lor$ é inclusiva: aceita que ambas as partes sejam verdadeiras. “Exatamente uma” escreve-se $(p\lor q)\land\neg(p\land q)$.

Uma implicação é falsa apenas quando o antecedente é verdadeiro e o consequente é falso. No exemplo da porta, introduzimos $r$ para «a porta abre». A condição $(p\land\neg q)\to r$ só falha quando há autorização, o sistema não está bloqueado e a porta não abre. Saber essa condição não afirma que há autorização, nem que esta é a única forma de abrir a porta. A implicação inversa $r\to(p\land\neg q)$ é outra afirmação.

”$p$ só se $q$” escreve-se $p\to q$: $q$ é uma condição necessária para $p$. ”$p$ se $q$” escreve-se $q\to p$: $q$ é suficiente para $p$. “Se e só se” exige as duas direções, abreviadas por $p\leftrightarrow q$.

A partir de $p\to q$ formam-se três implicações diferentes. Só uma delas é equivalente à original:

No exemplo da porta, a recíproca $r\to(p\land\neg q)$ diz que a porta só abre com autorização e sistema desbloqueado. A contrapositiva $\neg r\to\neg(p\land\neg q)$ diz que, se a porta não abre, então faltou autorização ou o sistema estava bloqueado. Confundir a original com a recíproca é a falácia de afirmar o consequente: ver a porta aberta não prova que houve autorização, pois outra forma de abrir também satisfaz $p=F,q$ qualquer, $r=T$.

Atribuições e tabelas de verdade

Uma atribuição $v$ escolhe $T$ ou $F$ para cada variável. Estendemos $v$ às fórmulas aplicando as conetivas de dentro para fora. Escrevemos $\models_v\varphi$ quando $v(\varphi)=T$.

Para $\varphi=(p\lor q)\land\neg p$, calculamos primeiro $p\lor q$ e $\neg p$:

Há $2^n$ atribuições para $n$ variáveis distintas, porque cada variável tem duas escolhas independentes. Repetir $p$ na fórmula não cria uma variável nova.

• Uma tautologia é verdadeira em todas as atribuições, como $p\lor\neg p$.
• Uma fórmula satisfazível é verdadeira em pelo menos uma atribuição.
• Uma contradição, ou fórmula insatisfazível, é falsa em todas, como $p\land\neg p$.
• Uma fórmula contingente tem atribuições verdadeiras e falsas.

A tabela mostra que $\varphi$ é contingente. Em particular, é satisfazível e não é uma tautologia. Escrever $\not\models\varphi$ diz apenas que não é válida, não que é uma contradição.

Consequência e contraexemplos

$\Gamma\models\varphi$ significa que toda a atribuição que torna todas as premissas de $\Gamma$ verdadeiras também torna $\varphi$ verdadeira. Não interessa uma linha em que uma premissa já é falsa.

Por exemplo, $p\lor q,\neg p\models q$. A única atribuição que satisfaz as duas premissas tem $p=F$ e $q=T$.

Para refutar $p\to q,q\models p$, escolhemos $p=F,q=T$. Ambas as premissas são verdadeiras e a conclusão é falsa. Esta atribuição é um contraexemplo ao argumento.

Se as premissas são insatisfazíveis, não existe linha com todas verdadeiras. Nesse caso, qualquer conclusão é consequência semântica delas. Para premissas finitas, podemos usar o teste equivalente:

Acrescentar e retirar premissas

Se $\Gamma\models\varphi$ e $\Gamma\subseteq\Sigma$, então $\Sigma\models\varphi$. Uma atribuição que satisfaz todas as premissas de $\Sigma$ também satisfaz as de $\Gamma$, logo satisfaz $\varphi$. Acrescentar premissas reduz os casos que é preciso verificar; esta propriedade chama-se monotonia da consequência.

Retirar premissas pode perder a conclusão. Temos $\{p,p\to q\}\models q$, mas $\{p\to q\}\not\models q$: $p=F,q=F$ satisfaz a única premissa e falsifica $q$.

Também não podemos intersectar dois conjuntos de premissas só porque ambos implicam a mesma conclusão. $\{p\}\models p\lor q$ e $\{q\}\models p\lor q$, mas a interseção é vazia. Com $p=q=F$, a conclusão é falsa, por isso $\emptyset\not\models p\lor q$.

Enumerar contraexemplos

Para duas variáveis, podemos percorrer as quatro atribuições e conservar apenas as que satisfazem as premissas e falsificam a conclusão. No código, implica(p, q) implementa $p\to q$ como !p || q. && corresponde à conjunção e ! à negação.

O argumento inicial é o do exercício «Refutar uma consequência»: $p\to q,q\models p\land q$. Compara a atribuição encontrada com a justificação escrita acima. Depois troca a definição de conclusao por (p, q) => q. Por que deixa de aparecer um contraexemplo? A premissa $q$ já garante essa conclusão.

const implica = (a, b) => !a || b;
const premissas = (p, q) => implica(p, q) && q;
const conclusao = (p, q) => p && q;
const valor = (v) => (v ? 'T' : 'F');

let quantidade = 0;
for (const p of [false, true]) {
  for (const q of [false, true]) {
    if (premissas(p, q) && !conclusao(p, q)) {
      console.log(`Contraexemplo: p=${valor(p)}, q=${valor(q)}`);
      quantidade++;
    }
  }
}
console.log(`Atribuições verificadas: 4. Contraexemplos: ${quantidade}.`);

Aqui, percorrer as quatro atribuições é uma verificação exaustiva, porque só aparecem $p$ e $q$. Se introduzires $r$ nas fórmulas, tens também de enumerar os seus dois valores. Conferir alguns casos de uma afirmação sobre inteiros ou sobre relações arbitrárias não tem o mesmo alcance.

Equivalências

$\varphi\Leftrightarrow\psi$ diz que as fórmulas têm o mesmo valor em todas as atribuições. É uma relação entre fórmulas. Já $\varphi\leftrightarrow\psi$ é uma fórmula da linguagem, que será uma tautologia se houver essa equivalência.

As transformações seguintes preservam o valor de verdade:

Conjunção e disjunção são comutativas, associativas e idempotentes. A implicação não é comutativa. Por exemplo, $T\to F$ é falsa, enquanto $F\to T$ é verdadeira.

Formas normais

Um literal é uma variável ou a sua negação. Na forma normal negativa, as negações só aparecem em literais e usamos apenas $\land$, $\lor$ e $\neg$.

Para transformar $\neg(p\to(q\land r))$, eliminamos a implicação e levamos a negação até aos literais:

Esta fórmula já está em forma normal conjuntiva, FNC ou CNF, uma conjunção de disjunções de literais. Um literal sozinho também pode ser uma cláusula. Distribuindo a conjunção obtemos a forma normal disjuntiva, FND ou DNF:

Uma FND é satisfazível se pelo menos uma das suas conjunções não contiver literais opostos. Uma FNC é uma tautologia se cada cláusula contiver um literal e a sua negação. Estes critérios não trocam de papel: ter cláusulas individualmente satisfazíveis não garante que a sua conjunção seja satisfazível. $p\land\neg p$ é um contraexemplo.

Construir a partir da tabela

Para obter FND, usamos as linhas verdadeiras. Em cada linha, juntamos por $\land$ a variável se vale $T$ e a sua negação se vale $F$. Depois juntamos os termos por $\lor$.

Na tabela de $(p\lor q)\land\neg p$, só a linha $p=F,q=T$ é verdadeira. A FND é $\neg p\land q$.

Para obter FNC, usamos as linhas falsas. Cada cláusula deve ser falsa exatamente nessa linha, por isso escolhemos a negação de uma variável com valor $T$ e a variável sem negação se vale $F$. A FNC da mesma tabela é:

A primeira cláusula exclui $(T,T)$, a segunda exclui $(T,F)$ e a terceira exclui $(F,F)$. Não escolhemos os sinais por memória, verificamos que a cláusula é falsa na linha que queremos excluir.

Para a tabela sempre falsa, uma FND possível é $p\land\neg p$. Para a tabela sempre verdadeira, uma FNC possível é $p\lor\neg p$.

Conjuntos completos de conetivas

Uma fórmula com $n$ variáveis define uma função $\{T,F\}^n\to\{T,F\}$. Há $2^{2^n}$ funções destas: uma escolha de saída para cada uma das $2^n$ entradas.

Um conjunto de conetivas é completo se consegue representar qualquer função de verdade. A construção da FND mostra que $\{\neg,\land,\lor\}$ é completo. Para provar que $\{\neg,\to\}$ também é completo, podemos representar as conetivas que faltam:

Por outro lado, $\{\land,\lor\}$ não é completo. Qualquer fórmula construída só com estas conetivas vale $T$ quando todas as variáveis valem $T$, por isso não representa $\neg p$.

Circuitos, mapas de Karnaugh e portas NAND

Uma fórmula booleana também se lê como um circuito: cada ocorrência de conetiva é uma porta, sem partilhar saídas entre portas. $\neg$ usa uma porta NOT unária com uma entrada; $\land$ e $\lor$ usam portas binárias com duas entradas. Para a expressão

uma construção direta usa 4 portas NOT, 4 portas AND binárias e 2 portas OR binárias, uma por cada ocorrência na escrita. O circuito calcula a mesma função que a FND obtida por equivalências:

Esta FND é outra árvore sintática, por isso a contagem é outra. Sem partilhar subexpressões e com portas binárias, ela usa 6 ocorrências de NOT, 5 AND binários e 3 OR binários. Só a forma simplificada abaixo é que usa poucas portas.

Os termos desta FND não são todos mintermos. Um mintermo fixa as três variáveis e cobre uma só linha; um termo incompleto deixa variáveis de fora e cobre várias linhas. Aqui:

• $\neg B\land\neg A\land C$ cobre só $A=0,B=0,C=1$.
• $\neg B\land\neg C$ cobre $A=0,B=0,C=0$ e $A=1,B=0,C=0$.
• $A\land\neg B$ cobre $A=1,B=0,C=0$ e $A=1,B=0,C=1$.
• $A\land\neg C$ cobre $A=1,B=0,C=0$ e $A=1,B=1,C=0$.

A união dá as cinco linhas verdadeiras $000,001,100,101,110$. Para ver estes conjuntos, o mapa de Karnaugh dispõe as oito combinações numa grelha onde células vizinhas diferem numa só variável. As colunas seguem a ordem Gray $00,01,11,10$ para $BC$; as arestas opostas contam como vizinhas, como se o mapa desse a volta. Agrupamos os uns em retângulos com $1$, $2$, $4$ ou $8$ células. Cada grupo elimina as variáveis que mudam dentro dele.

No mapa, o bloco das duas primeiras colunas reúne as quatro células com $B=0$; elimina $A$ e $C$. O par da linha $A=1$ reúne as células $100$ e $110$, que são vizinhas pela borda direita e esquerda e partilham $A=1,C=0$; elimina $B$. A célula $100$ pertence aos dois grupos. A expressão simplificada é:

O circuito simplificado usa 2 portas NOT, 1 AND binário e 1 OR binário. A simplificação conserva a função de verdade: os dois blocos cobrem exatamente as cinco linhas verdadeiras listadas acima.

A mesma função escreve-se com um só tipo de porta. A porta NAND define-se por $P\uparrow Q=\neg(P\land Q)$. Como $\neg P\Leftrightarrow P\uparrow P$, obtemos NOT; negando um NAND obtemos AND; por De Morgan obtemos OR. Para a forma simplificada, a construção explícita com três NAND binários é:

Lê de dentro para fora: $C\uparrow C$ é $\neg C$; $A\uparrow(\neg C)$ é $\neg(A\land\neg C)$; $B\uparrow\neg(A\land\neg C)$ é $\neg B\lor(A\land\neg C)$. As oito atribuições dão $1,1,0,0,1,1,1,0$ por $ABC=000$ até $111$, tal como a original, a FND e a simplificada. A construção análoga com NOR usa $P\downarrow Q=\neg(P\lor Q)$. Escolher NAND ou NOR não muda a função representada, só o conjunto de portas permitido.

Conferir uma equivalência

Voltamos a $\varphi=(p\lor q)\land\neg p$. A FND obtida da tabela foi $\neg p\land q$. Podemos justificar a simplificação sem enumerar atribuições:

A primeira passagem distribui a conjunção. O termo $p\land\neg p$ nunca é verdadeiro, por isso não altera a disjunção. A última passagem troca a ordem da conjunção. A tabela e as transformações chegam à mesma condição: $p=F,q=T$.