Exemplos

O Labirinto do Minotauro

$$\Huge \begin{array}{:c:c:c:c:} \hdashline \phantom{a}^{\cvPerM}_{\phantom{c}} & \phantom{A_b^c} & \phantom{a}_{\cvPerP}^{\phantom{c}} & \cvP_{\phantom{a}^{\phantom{c}}} \cr \hdashline \cvM & \cvA^{\cvPerM}_{\cvPerP} & \cvP & \phantom{a}_{\cvPerP} \cr \hdashline \phantom{a}^{\cvPerM} & \phantom{A_b^c} & \phantom{a}_{\cvPerP} & \cr \hdashline \cvT &\phantom{a}_{\cvPerP} & \cvP & \phantom{a}_{\cvPerP} \cr \hdashline \end{array} $$

• O labirinto consiste numa rede de salas ligadas por corredores.
• Algures no labirinto está o Minotauro, $\cvM$, que devora quem entrar nessa sala.
• O Minotauro pode ser morto por Teseu, $\cvT$, que tem uma única seta e perceciona apenas a sala em que se encontra.
• Algumas salas têm um poço, $\cvP$, onde todos, exceto o minotauro, caem quando entram.
• Numa única sala está Ariadne, $\cvA$, que Teseu procura.
• Nas salas adjacentes ao Minotauro fede, $\cvPerM$.
• Nas salas adjacentes aos poços sente-se uma brisa, $\cvPerP$.

N.B. “adjacente” exclui as diagonais.

Formalização

Dadas as seguintes proposições atómicas:

• $\lit{m}_{ij}$ o Minotauro está na sala $ij$.
• $\lit{f}_{ij}$ fede na sala $ij$.
• $\lit{p}_{ij}$ está um poço na sala $ij$.
• $\lit{b}_{ij}$ há brisa na sala $ij$.
• $\lit{t}_{ij}$ Teseu está na sala $ij$.
• $\lit{a}_{ij}$ Ariadne está na sala $ij$.

A base de conhecimento inicial de Teseu, admitindo que “deteta” tudo na sala em que está: $$ \begin{aligned} & \lit{t}_{11} \land \neg \lit{m}_{11} \land \neg \lit{p}_{11} \land \neg \lit{a}_{11} \land \neg \lit{f}_{11} \land \neg \lit{b}_{11} \land \cr & \lit{f}_{11} \liff \del{\lit{m}_{12} \lor \lit{m}_{21}} \land \lit{f}_{12} \liff \del{\lit{m}_{11} \lor \lit{m}_{22} \lor \lit{m}_{13}} \land & \cdots \cr & \lit{b}_{11} \liff \del{\lit{p}_{12} \lor \lit{p}_{21}} \land \lit{b}_{12} \liff \del{\lit{p}_{11} \lor \lit{p}_{22} \lor \lit{p}_{13}} \land & \cdots ~ \end{aligned} $$

Exercícios

Use os predicados atómicos $\lit{m}_{ij}, \lit{f}_{ij}, \lit{p}_{ij}, \lit{b}_{ij}, \lit{t}_{ij}, \lit{a}_{ij}$ e:

1. Deduza $\neg \lit{m}_{21}$ por Teseu. Também pode deduzir $\neg \lit{a}_{21}$?

2. Descreva, numa proposição, a sala $32$ do exemplo anterior.

Suponha que o labirinto tem apenas $2\times 2$ salas e formalize:

1. Existe apenas um minotauro no labirinto.
2. Existe apenas um poço no labirinto.
3. Existem dois poços no labirinto.
4. O minotauro está na mesma sala que Ariadne.
5. O minotauro está numa sala diferente de Ariadne.
6. Teseu está na mesma linha que o minotauro.
7. Ariadne está na mesma coluna que Teseu.
8. Teseu está numa sala adjacente a Ariadne.

Porque não consegue formalizar “Cada sala tem quanto muito um poço”? E se for possível existirem dois poços na mesma sala?

Exemplo de Dedução

$$ \begin{array}{:c:c:c:} \hdashline ~ & ~ & ~ \cr \hdashline _{12}~({\cvT}) & ~ & ~ \cr \hdashline _{11}~\cvT_{\cvPerP} &_{21}~({\cvP}) & \cvP \cr \hdashline \end{array} $$

Quando Teseu passa da sala $12$, onde não há um poço, para a sala $11$, deteta uma brisa. Conclui então que há um poço na sala $21$, ainda não visitada.

1. Transcrever a regra das brisas, $\lit{b}_{11} \liff \del{\lit{p}_{12} \lor \lit{p}_{21}}$, para a FNC: $$ \del{\neg \lit{b}_{11} \lor \lit{p}_{12}\lor \lit{p}_{21}} \land \del{\neg \lit{p}_{12} \lor \lit{b}_{11}} \land \del{\neg \lit{p}_{21} \lor \lit{b}_{11}}. $$
2. Listar as proposições relevantes, incluindo:
   • O poço não está em $12$: $\neg \lit{p}_{12}$.
   • Sente-se uma brisa em $11$: $\lit{b}_{11}$.
   • A negação da tese: $\alert{\neg \lit{p}_{21}}$.
3. Aplicar a resolução: $$ \dfrac{ \dfrac{ \dfrac{ \neg \lit{b}_{11} \lor \lit{p}_{12}\lor \lit{p}_{21} \qquad \lit{b}_{11}} {\lit{p}_{12}\lor \lit{p}_{21}} \qquad \neg \lit{p}_{12}} {\lit{p}_{21}} \qquad \alert{\neg \lit{p}_{21}} }{\bot} $$