# Charadas de Smullyan

Desde o final dos anos 1970 ao final de 1990, Raymond Smullyan, um professor de Matemática e Filosofia de Nova York, publicou vários livros contendo uma mistura eclética de enigmas, quebra-cabeças de lógica e quebra-cabeças para atrair adultos e crianças. Os puzzles são ao mesmo tempo singulares e desafiadores e muitos são incorporados em cenários tirados da literatura popular e do folclore, como Alice no País das Maravilhas (Alice in the Pluzze-Land), Os Cavaleiros da Arábia (The Chess Mysteries of the Arabian Knights) e Sherlock Holmes (The Chess Mysteries of Sherlock Holmes).
Além de sua respeitada carreira acadêmica, Smuyllan foi músico, escritor humorista, e até mágico para crianças. O carisma e charme de sua escrita introduziu muitos recém-chegados ao prazer de quebra-cabeças mental.

## Quebras-Cabeças
### Cavaleiros, escudeiros e lobisomens

Os dois primeiros puzzles são tirados Qual é o nome deste livro? (What Is the Name of This Book?). Suponha que você está visitando uma floresta em que cada habitante seja um cavaleiro ou um escudeiro. Cavaleiros sempre dizem a verdade e os escudeiros sempre mentem. Além disso, alguns dos habitantes são lobisomens e tem o irritante hábito de às vezes se transformarem em lobos e devorarem pessoas. Um lobisomem pode ser um cavaleiro ou de um patife.

#### Lobisomens II

Você está entrevistando três habitantes, A, B e C, e sabe-se que exatamente um deles é um lobisomem. Eles fazem as seguintes declarações:
A: Eu sou um lobisomem. B: Eu sou um lobisomem. C: No máximo um de nós é um cavaleiro.
Dê uma classificação completa de A, B e C.

#### Lobisomens IV

Desta vez, temos as seguintes declarações:
A: Pelo menos um dos três de nós é um escudeiro. B: C é um cavaleiro.
Dado que há exatamente um lobisomem e que ele é um cavaleiro, que é o lobisomem?

### Senhoras ou tigres?

Os próximos dois puzzles são tomadas a partir de A Dama ou o Tigre (The Lady or the Tiger?). O capítulo em questão, senhoras ou tigres, contém 12 puzzles de dificuldade crescente. Em cada quebra-cabeça de um prisioneiro é confrontado com uma decisão onde ele deve abrir uma das várias portas. Nos primeiros exemplos de cada quarto contém tanto uma senhora ou um tigre e nos quartos mais difíceis, podem estar vazios. A seguir temos um exemplo simpels e um difícil.
Se o prisioneiro abre uma porta para encontrar uma senhora que ele vai se casar com ela e se ele abre uma porta para encontrar um tigre que ele vai ser comido vivo. Assumimos que o prisioneiro prefere se casar do que vivo comido. Supõe-se também que a senhora é, de alguma forma especial para o prisioneiro e ele preferiria encontrar e se casar com ela ao invés de um abrir uma porta para dentro e sala vazia.
Cada uma das portas tem uma placa com uma declaração que pode ser verdadeira ou falsa.

#### O segundo julgamento

Este quebra-cabeça envolve dois quartos.
A declaração na porta de um diz: "Pelo menos um destes quartos contém uma dama." A declaração na porta de dois diz: "Um tigre está no outro quarto." As declarações são ou ambas verdadeiras ou ambas falsas.

#### Um labirinto lógico

O enigma final do livro envolve nove quartos. As declarações sobre as nove portas são:
Porta 1: A senhora está em uma sala ímpar. Porta 2: Esta sala está vazia. Porta 3: Ou a placa de 5 é certo ou a placa da 7 está errada. Porta 4: A placa de 1 está errada. Porta 5: Ou a placa de 2 ou a de 4 está certa. Porta 6: A placa de 3 está errada. Porta 7: A senhora não está na sala 1. Porta 8: Esta sala contém um tigre e sala 9 está vazia. Porta 9: Esta sala contém um tigre e assinar seis está errado.
Além disso, o prisioneiro é informado de que apenas um quarto contém uma senhora; cada um dos outros ou contém um tigre ou está vazio. A placa na porta da sala contendo a senhora é verdade, os sinais em todas as portas contendo tigres são falsas, e os sinais nas portas de salas vazias pode ser verdadeira ou falsa.
O quebra-cabeça como indicado não tem uma solução única, até o prisioneiro é dito ou não sala oito é vazia e esse conhecimento permite-lhe encontrar uma solução única.

## Ferramentas de modelagem
### Variáveis de Indicador

É útil para desenvolver restrições lineares para forçar uma variável indicadora para 1 se e somente se uma proposição particular é verdadeira. Quatro exemplos são apresentados a seguir.
Em cada caso, $x=[x1,x2,..,xc]$, $Fx$ é uma função linear de x e U e L são os limites superior e inferior, respectivamente, $Fx$.
* d = 1 se F x ³ n, 0 caso contrário
* F x - (U - n +1) d R n - 1 (1)
* F x - (n - L) d L ³ (2)
* d = 1 se F x £ n, 0 caso contrário
* F x + (n +1 - L) d ³ n +1 (3)
* F x + (U - L) d R n + U - L (4)
* d = 1 se F x = n, 0 caso contrário
Nos dois casos especiais, onde n = n = L ou U, é equivalente e mais simples para modelar as expressões F x £ n ou F x ³ n, respectivamente, ao invés de F x = n. Se nenhum desses for o caso, podemos fazer valer a condição de em três etapas como segue:
* (I) d1 = 1 se F x ³ n, 0 caso contrário
* F x - (U - n +1) d 1 R n - 1 (5)
* F x - (n - L) d 1 L ³ (6)
* (Ii) d2 = 1 se F x R n, 0 caso contrário
* F x + (n +1 - L) d 2 ³ n +1 (7)
* F x + (U - L) d 2 R n + U - L (8)
* (Iii) d = 1 se F x R n Ù F x ³ n, 0 caso contrário
Uma declaração equivalente é d = 1 se d 1 + d 2 = 2, 0 caso contrário. Note-se que pelo menos uma das condições (i) e (ii) deve manter, portanto, d 1 + d 2 ³ 1. Assim, a única restrição d = D 1 + d 2-1 (9) é suficiente.
* d = 1 se F x ¹ n, 0 caso contrário
Restrições (5) a (8) pode ser aplicada e restrição (9) passa a ter
* d = 2 - d1 - d2 (10)

### Constrangimentos lógicos

O uso de variáveis ​​indicadoras em conjunto com proposições como mostrado acima pode ser estendido para as relações entre proposições.
Nós definimos variáveis ​​indicadoras d i tais que d i = 1 se i proposição X é verdadeiro e 0 se X i é falsa. As equivalências a seguir retirado Williams (1999) vai ser útil.
* Ù X 1 X 2 é equivalente a d 1 + d 2 = 2
* X 1 X 2 Ú é equivalente a d 1 + d 2 ³ 1
* ~ X 1 é equivalente a d 1 = 0
* ® X 1 X 2 é equivalente a d £ 1 d 2
* X 1 «X 2 é equivalente a d 1 = d 2
* X 1 " ~ X 2 é equivalente a d 1 = 1 - d 2

### Funções Objetivas

O objetivo do quebra-cabeças é encontrar uma solução em que todas as declarações são consistentes. Na maioria dos casos, portanto, podemos escolher qualquer função objetivo.

## Modelos
### Lobisomens II

Definir variáveis ​​x i = 1 i se a pessoa é um cavaleiro e um valete 0 se e y i = 1 i se a pessoa é um lobisomem e 0 caso contrário para i = 1 .. 3.
Como afirmado acima, escolha uma função objetivo arbitrária, por exemplo
Maximizar x 1 Sujeita às condições estabelecidas modelado como segue.
Apenas uma pessoa é um lobisomem
* y 1 + y 2 + y 3 = 1
Se a declaração feita por A é verdade então A é um cavaleiro. Mais formalmente
* y 1 = 1 " x 1 = 1
e esta é modelada simplesmente pela
* y 1 = x 1
Da mesma forma, se a declaração feita por B é verdadeiro então B é um cavaleiro é representado por
* y 2 = x 2
Se a declaração feita pelo C for verdade, então C é um cavaleiro ou
* x 1 + x 2 + x 3 R 1 « x 3 = 1
e isso pode ser modelado usando restrições (3) e (4) e substituindo F x = x 1 + x 2 + x 3, d = x 3, n = 1, U = 3 e L = 0 da seguinte forma
* x 1 + x 2 + 3 3x ³ 2
* x 1 + x 2 + 4x 3 £ 4

### Lobisomens IV

Se a declaração por A é verdade então A é um cavaleiro. Mais formalmente,
* x 1 + x 2 + x 3 R 2 « x 1 = 1
e isso pode ser modelado usando restrições (3) e (4) e substituindo F x = x 1 + x 2 + x 3, d = x 1, n = 2, U = 3 e L = 0 da seguinte forma
* 4x 1 + x 2 + x 3 ³ 3
* 4x 1 + x 2 + x 3 £ 5
Se a declaração do B é verdadeiro então B é um cavaleiro, ou
* x 3 = 1 « x 2 = 1
que é modelada por
* x 3 = x 2
Apenas uma pessoa é um lobisomem
* 1 + y 2 + y 3 = 1
O lobisomem é um cavaleiro
* x ³ i y i para i = 1 .. 3

### O segundo julgamento

Definir índices i = 1 .. 2 para portas e j = 1 .. 2 a prêmios (1 - dama, 2 - tigre) e as variáveis ​​da seguinte forma:
x i, j = 1 se i porta esconde prêmio j, 0 caso contrário t i = 1 if i na porta é verdade, 0 caso contrário Qualquer função objetivo
* Max x 1,1
Cada porta esconde um prêmio
A condição lógica que queremos um modelo para a porta é
* t 1 = 1 "x 1,1 + 2,1 x ³ 1
e as restrições para impor essa condição são
* x 1,1 + x 2,1 - 2t £ 1 0
* x 1,1 + x 2,1 - t 1 ³ 0
A condição implícita na declaração na porta 2 é
* t 2 = 1 "x 1,2 = 1
e a restrição é necessária
* t = 2 x 1,2
Além disso, devemos restringir que as duas afirmações são ou ambos verdadeiros ou ambos falsos como se segue.
* t 1 = t 2

### Um Labirinto Lógico

Vamos agora aplicar as estruturas de modelagem acima para o bem mais quebra-cabeça difícil Labyrinth Lógico da Seção 2.2.2.
Definir índices i = 1 .. 9 e j = 1 .. 3 (1 - dama, 2 - tigre, 3 - vazio) e como variáveis ​​acima são
x i, j = 1 se i porta esconde prêmio j, 0 caso contrário
t i = 1 if i na porta é verdade, 0 caso contrário
Vamos começar usando a função seguinte objetivo arbitrária
* Max x 1,1
Temos agora a lista de depoimentos de nove portas e estadual a relação entre a verdade ou falsidade de cada afirmação e as t apropriado i variável. Restrições lineares são desenvolvidos em cada caso, para reforçar essas relações.
Porta 1 - a senhora está em uma sala de ímpares.
* t 1 = 1 "x 1,1 + 3,1 x + x + 5,1 x 7,1 x 9,1 + = 1
Isto pode ser reforçado pela
* t 1 = x 1,1 + 3,1 x + x + 5,1 x 7,1 x 9,1 +
Porta 2 - Esta sala está vazia.
* t 2 = 1 "x 2,3 = 1
imposta pelo
* t = 2 x 2,3
Porta 3 - Ou sinal de 5 é certo ou é errado sinal 7.
* 3 = 1 t «t 5 + x 1,1 ³ 1
imposta pelo
* t + 5 x 1,1 - 2t 3 £ 0
* t + 5 x 1,1 - t 3 ³ 0
4 portas - Registe-1 é errado.
* 4 = 1 t «t 1 = 0
imposta pelo
* t 4 = 1 - t 1
5 portas - Ou sinal de 2 ou 4 é sinal certo.
* 5 = 1 t «t 2 + t 4 ³ 1
imposta pelo
* t 2 + t 4 - 2t 5 £ 0
* t 2 + t 4 - t 5 ³ 0
Porta 6 - Registe-3 é errado.
* 6 = 1 t «t 3 = 0
* t 6 = 1 - t 3
Porta 7 - A senhora não está na sala 1.
* t 7 = 1 "x 1,1 = 0
imposta pelo
* t 7 = 1 - t 11
Porta 8 - Esta sala contém um tigre e sala 9 está vazia.
* t 8 = 1 "x 8,2 x 9,3 + 2 ³
imposta pelo
* x 8,2 x 9,3 + - 8 £ 2t 1
* x 8,2 x 9,3 + - 8 2t ³ 0
Porta 9 - Esta sala contém um tigre e sala 9 está vazia
* t 9 = 1 "x 9,2 t ³ + 3 2
imposta pelo
* x 9,2 + t 3 - 2t 9 £ 1
* x 9,2 + t 3 - 2t ³ 9 0
Outras condições do quebra-cabeça são modelados como se segue.
Cada porta esconde um prêmio
Apenas uma sala contém uma senhora.
O sinal na porta da senhora é verdade.
* t i ³ x i, 1 para i = 1 .. 9
O sinal nas portas dos tigres são falsas.
* t i £ 1 - x i, 2 para i = 1 .. 9
Experimentação com o modelo revela que se o preso tinha sido dito que o quarto estava vazio oito ele não poderia ter identificado a localização, a senhora. Ou seja, se x 8,3 é forçado a uma não existe uma solução única viável. Ele deve, portanto, foram informados de que oito sala não estava vazia. Este recurso adicional requer a restrição
x 8,3 = 0
e o modelo de revista identifica o paradeiro da senhora.