Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Efeito da Contradição

A regra $\ndEContr$ pode ser lida como “de uma contradição é sempre possível concluir qualquer proposição”.

Em termos práticos a lógica e a dedução natural são utilizadas para descrever e analizar um certo problema. Por exemplo, um programa, uma empresa, etc.

Supondo que a Dona Entrelinha é gestora (CEO!) de uma padaria e vai aplicar a lógica e a dedução natural para descrever e analisar o fluxo de trabalho. Começou com um conjunto de regras para o dia-a-dia da padaria:

$$ H = \left\lbrace \begin{aligned} \lit{pão} &\to \lit{ingredientes}, \cr \lit{lucro} &\to \lit{clientes} \land \lit{pão}, \cr \lit{clientes} \land \neg\lit{pão} & \to \neg \lit{lucro}, \cr \neg \lit{clientes} & \to \neg \lit{lucro}, \cr \lit{clientes} \lor \neg\lit{clientes} & \end{aligned} \right\rbrace $$

Certo dia houve falta de farinha, pelo que a Dona Entrelinha acrescentou $\neg \lit{ingredientes}$ às regras e antecipou que, nesse dia, não teria lucro: $H, \neg\lit{ingredientes} \vdash \neg\lit{lucro}$ porque

LinhaProposiçãoRegraHipóteses
1$\neg\lit{ingredientes}$$H_a$não há ingredientes
2$\lit{pão}$$H_b$admitindo que faz pão (5) descarte
3$\lit{ingredientes}$$\ndEImpl$2, $H_1$
4$\bot$$\ndIContr$2, 6
5$\neg\lit{pão}$$\ndEContr$1 - 3
6$\lit{clientes} \lor \neg\lit{clientes}$$\ndTE$(regra derivada!)
Caso 1 de 6
7$\qquad\lit{clientes}$$H$(15) descarte
8$\qquad\lit{clientes} \land \neg\lit{pão}$$\ndIConj$7, 5
9$\qquad\neg\lit{lucro}$$\ndEImpl$8, $H_3$
Caso 2 de 6
10$\qquad\neg\lit{clientes}$$H$(15) descarte
11$\qquad\neg\lit{lucro}$$\ndEImpl$10, $H_4$
12$\neg\lit{lucro}$$\ndEDisj$6, 7-9, 10-11

Tentado manter o lucro, a Dona Entrelinha foi a uma padaria rival e comprou pão. Mas, com o stress da situação, esqueceu-se de retirar das hipóteses as proposições sobre os ingredientes. Ficou então com hipóteses $$ H, \neg \lit{ingredientes}, \lit{pão} $$

Ora, neste caso

LinhaProposiçãoRegraHipóteses
1$\lit{pão}$$H$
2$\neg \lit{ingredientes}$$H$(5)
3$\lit{ingredientes}$$\ndMP$1, $H_1$
4$\bot$$\ndIContr$3, 2
5$\alert{\text{\it o que quisermos!}}$$\ndEContr$4

Na linha 5 podemos escrever qualquer proposição, i.e. qualquer proposição é consequência de $H, \neg \lit{ingredientes}, \lit{pão}$ !

Esta situação não é desejável porque qualquer teoria (conjunto de hipóteses) “útil” deve distinguir “verdade” de “falso”; os “factos” dos “enganos”.

Uma teoria que permita contradições não é “útil” porque qualquer proposição é consequência dessa teoria.

E, se qualquer proposição é consequência, também a sua negação o é; se $H \vdash p$ para qualquer proposição $p$, então também $H \vdash \neg p$.

Programação Lógica

As hipóteses iniciais da Dona Entrelinha podem ser descritas pelo seguinte programa ASP:

ingredientes :- pao.
clientes :- lucro.
pao :- lucro.
-lucro :- clientes, -pao.
-lucro :- -clientes.
clientes ; -clientes.

Como é normal em programação lógica:

  • Em vez de $a \to b$ escreve-se $b \leftarrow a$ usando a sintaxe b :- a, que se lê “b se a”. Adicionalmente,
  • A negação $\neg a$ é representada por -a.
  • A conjunção $a \land b$ por a, b.
  • A disjunção $a \lor b$ por a; b.

Pode-se perguntar em que circunstâncias este programa é satisfeito. O resultado é

Solving...
Answer: 1
-clientes -lucro
Answer: 2
clientes
SATISFIABLE

Isto é, há duas formas (answer sets) destas regras serem cumpridas:

  • Ou não há clientes nem lucro (Answer: 1).
  • Ou há clientes, mas não a garantia de lucro (Answer: 2) .

Recursos