Exemplos

O Labirinto do Minotauro

$$\begin{array}{cccc}{}^{\text{f}}& & {}_{\text{b}}& \text{P}\\ \text{M}& {\text{A}}_{\text{b}}^{\text{f}}& \text{P}& {}_{\text{b}}\\ {}^{\text{f}}& & {}_{\text{b}}& \\ \text{T}& {}_{\text{b}}& \text{P}& {}_{\text{b}}\end{array}$$

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

N.B. "adjacente" exclui as diagonais.

Formalização

Dadas as seguintes proposições atómicas:

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

A base de conhecimento inicial de Teseu, admitindo que "deteta" tudo na sala em que está: $$\begin{array}{rlr}& {\text{t}}_{11}\wedge \neg {\text{m}}_{11}\wedge \neg {\text{p}}_{11}\wedge \neg {\text{a}}_{11}\wedge \neg {\text{f}}_{11}\wedge \neg {\text{b}}_{11}\wedge & \\ & {\text{f}}_{11}\leftrightarrow \left({\text{m}}_{12}\vee {\text{m}}_{21}\right)\wedge {\text{f}}_{12}\leftrightarrow \left({\text{m}}_{11}\vee {\text{m}}_{22}\vee {\text{m}}_{13}\right)\wedge & \cdots \\ & {\text{b}}_{11}\leftrightarrow \left({\text{p}}_{12}\vee {\text{p}}_{21}\right)\wedge {\text{b}}_{12}\leftrightarrow \left({\text{p}}_{11}\vee {\text{p}}_{22}\vee {\text{p}}_{13}\right)\wedge & \cdots \end{array}$$

Exercícios

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

1. Deduza $\neg {\text{m}}_{21}$ por Teseu. Também pode deduzir $\neg {\text{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}{ccc}& & \\ {}_{12}(\text{T})& & \\ {}_{11}{\text{T}}_{\text{b}}& {}_{21}(\text{P})& \text{P}\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, ${\text{b}}_{11}\leftrightarrow \left({\text{p}}_{12}\vee {\text{p}}_{21}\right)$, para a FNC: $$\left(\neg {\text{b}}_{11}\vee {\text{p}}_{12}\vee {\text{p}}_{21}\right)\wedge \left(\neg {\text{p}}_{12}\vee {\text{b}}_{11}\right)\wedge \left(\neg {\text{p}}_{21}\vee {\text{b}}_{11}\right).$$
2. Listar as proposições relevantes, incluindo:
   • O poço não está em $12$: $\neg {\text{p}}_{12}$.
   • Sente-se uma brisa em $11$: ${\text{b}}_{11}$.
   • A negação da tese: $\neg {\text{p}}_{21}$.
3. Aplicar a resolução: $$\frac{\frac{\frac{\neg {\text{b}}_{11}\vee {\text{p}}_{12}\vee {\text{p}}_{21}{\text{b}}_{11}}{{\text{p}}_{12}\vee {\text{p}}_{21}}\neg {\text{p}}_{12}}{{\text{p}}_{21}}\neg {\text{p}}_{21}}{\perp }$$