Charadas de Smullyan: diferenças entre revisões

Adicionar hiperligações
Origem: Wikipédia, a enciclopédia livre.
Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
← branqueio de página
Linha 1: Linha 1:
== Introdução ==
Desde o final dos anos 1970 ao final de 1990, [[Raymond_Smullyan|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 ([[Especial:Fontes_de_livros/0688007481|Alice in the Pluzze-Land]]), Os Cavaleiros da Arábia ([[Especial:Fontes_de_livros/0192861247|The Chess Mysteries of the Arabian Knights]]) e Sherlock Holmes ([[Especial:Fontes_de_livros/0394737571|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? ([[Especial:Fontes_de_livros/0139550623|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.<br />
'''B''': Eu sou um lobisomem.<br />
'''C''': No máximo um de nós é um cavaleiro.<br />

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.<br />
'''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 ([[Especial:Fontes_de_livros/0812921178|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.<br />
'''Porta 2''': Esta sala está vazia.<br />
'''Porta 3''': Ou a placa de 5 é certo ou a placa da 7 está errada.<br />
'''Porta 4''': A placa de 1 está errada.<br />
'''Porta 5''': Ou a placa de 2 ou a de 4 está certa.<br />
'''Porta 6''': A placa de 3 está errada.<br />
'''Porta 7''': A senhora não está na sala 1.<br />
'''Porta 8''': Esta sala contém um tigre e sala 9 está vazia.<br />
'''Porta 9''': Esta sala contém um tigre e assinar seis está errado.<br />

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, <math>x = [x 1, x 2, .., x c]</math>, <math>Fx</math> é uma função linear de x e U e L são os limites superior e inferior, respectivamente, <math>Fx</math>.

d = 1 se F x ³ n, 0 caso contrário<br />
F x - (U - n +1) d R n - 1 (1)<br />
F x - (n - L) d L ³ (2)<br />

d = 1 se F x £ n, 0 caso contrário<br />
F x + (n +1 - L) d ³ n +1 (3)<br />
F x + (U - L) d R n + U - L (4)<br />

d = 1 se F x = n, 0 caso contrário<br />

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<br />
F x - (U - n +1) d 1 R n - 1 (5)<br />
F x - (n - L) d 1 L ³ (6)<br />

(Ii) d2 = 1 se F x R n, 0 caso contrário<br />
F x + (n +1 - L) d 2 ³ n +1 (7)<br />
F x + (U - L) d 2 R n + U - L (8)<br />
(Iii) d = 1 se F x R n Ù F x ³ n, 0 caso contrário<br />

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<br />
Restrições (5) a (8) pode ser aplicada e restrição (9) passa a ter<br />
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<br />
X 1 X 2 Ú é equivalente a d 1 + d 2 ³ 1<br />
~ X 1 é equivalente a d 1 = 0<br />
® X 1 X 2 é equivalente a d £ 1 d 2<br />
X 1 «X 2 é equivalente a d 1 = d 2<br />
X 1 " ~ X 2 é equivalente a d 1 = 1 - d 2<br />

==== 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<br />
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

y 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

ea 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.

== Conclusão ==
Nossa experiência indica que o desafio de resolver quebra-cabeças cada vez mais difícil fornece aos alunos com motivação suficiente para dominar as técnicas de modelagem lógica e da labuta normalmente associada com exercícios broca é pouco notado.

Finalmente, uma mais-valia educacional em estabelecer paralelos entre situações-problema diversas é que pode levar os estudantes a inferir a necessidade de pensar lateralmente na busca de soluções para a miríade de complexos problemas de negócios do mundo real.

== Referências ==
http://www.chlond.demon.co.uk/academic/papers/Smullyan.htm (Tradução)

[[Categoria:Lógica]]
[[Categoria:Quebra-cabeças]]

Revisão das 20h41min de 26 de junho de 2012

Obtida de "https://pt.wikipedia.org/w/index.php?title=Charadas_de_Smullyan&oldid=30929906"