STUDIA UNIV. BABES¸–BOLYAI, INFORMATICA, Volume LIV, Numbe 1, 2009
USING SPREADSHEETS FOR SOLVING LOGIC PUZZLES
M´
ARIA BAK´
O AND L´
ASZL´
O ASZAL´
OS
Abs ac . The consequence ela ion and pe ec usage o de i a ion is a
necessa y knowledge o laye s, economis s, enginee s and o hund eds o
o he di e en p o essionals. S uden s in he low and mid le el educa ion
sys em a e able o sol e simple logical puzzles wi hou any special ain-
ing, bu some o he puzzles in Smullyan’s books p esen a challenge e en
o uni e si y s uden s. Some o he logic and a i icial in elligence cou ses
con ain me hods o examining deduc ions and he s uden s migh e en
use special ools and so wa e o acili a e he p ocess. In his a icle we
would like o show you ha he well-known sp eadshee so wa e is a g ea
ool o sol e puzzles ha can be exp essed in sen ence (o in ze o-o de )
logic. Many s uden s he e o e will be able o sol e e en complica ed puz-
zles wi hou lea ning any special so wa es. This can be e y help ul o
eache s eaching deduc ion, bu i can be also help ul o he eache s
eaching sp eadshee so wa e usage, because hei s uden s would be able
o sol e challenging p oblems by lea ning o use new unc ions. The knowl-
edge o hese unc ions could be use ul la e sol ing o he ype o p oblems,
oo.
1. In oduc ion
The cu iculum o he elemen a y and he seconda y schools equi es he
eaching o in o ma ion echnology and aining in compu e skills.
A many schools s uden s a e p epa ing o he Eu opean Compu e D i -
ing License exam because i is an in e na ionally ecognized quali ica ion, and
helps he s uden s o boos hei p oduc i i y, la e on i helps hem o be
compe i i e on he labo ma ke and success ul a he en ance exams. The
s uden s a o i e opics a e he wo d p ocessing and he sp eadshee s so wa es
because hese a e he mos commonly used in he e e yday li e. Sp eadshee s
Recei ed by he edi o s: Decembe 6, 2008.
2000 Ma hema ics Subjec Classi ica ion. 03B35, 68T20.
1998 CR Ca ego ies and Desc ip o s. I.2.3 [Topic]: Deduc ion and Theo em P o ing –
case-based deduc ion; F.4.1 [Topic]: Ma hema ical logic – mechanical heo em p o ing .
Key wo ds and ph ases. Logic puzzles, Case-based deduc ion, Mecnahical heo em p o -
ing, Sp eadshee s.
This pape has been p esen ed a he 7 h Join Con e ence on Ma hema ics and Compu e
Science (7 h MaCS), Cluj-Napoca, Romania, July 3-6, 2008.
17
18 M ´
ARIA BAK ´
O AND L ´
ASZL ´
O ASZAL ´
OS
Table 1. T u h- able o ((A⊃B)⊃A)⊃A
A B A ⊃B(A⊃B)⊃A((A⊃B)⊃A)⊃A
a e good o budge ing o accoun ing planning, o calcula ions and analysis,
and u he mo e i is a good ool o p ac ice ma hema ics o di e en ma h-
ema ical concep s/ideas o some imes jus o play wi h. The jou nal Sp ead-
shee s in Educa ion [17] con ains lo s o in e es ing examples. In his a icle
we will show how we can u ilize sp eadshee s in he eaching o ma hema ics,
especially how o sol e logic puzzles in [14, 15, 16].
These puzzles a e sui able ools o show he elemen s o he deduc ion
[8, 20]. Many s uden s a uni e si y le el use only ue- ables o check he
alidi y o a logical consequence, and hey su i e wi h his knowledge while
hey wo k wi h oy p oblems. Bu one o he puzzles sol ed in he pape is
so complica e ha he co esponding u h- able has mo e han 4,500 ows.
The cons uc ion o he sp eadshee which sol es his puzzle is no a compli-
ca ed ask and use only simple unc ions. Hence his me hod can be used a
elemen a y schools le el, oo. Mo eo e he solu ion p ocess o logic puzzles is
a challenging p oblem, and di e s om he usual sp eadshee p oblems. This
kind o di e si y helps us o hold up he in e es o s uden s, which is he key
poin o he educa ion. We ema k ha he ma hema ical con es s a elemen-
a y school le el in Hunga y o en con ain hese kind u h- elle and lia logic
puzzles.
2. T u h- ables
We ha e se e al me hods o check logical consequences. In he case o
sound and comple e calculus we can eplace he consequence ela ion wi h de-
cidabili y, and we can use au oma ed heo em p o e s. In he case o sen ence
logic we can use he u h- ables. In he ows o his able a i s we lis
all he logical combina ions o he logical a iables, and nex we de e mine
he alues o he o mulae in hese cases. The Table 1 shows such a able,
whe e he columns belong o he sub o mulae o he o iginal o mula. In ou
u h- ables deno e he ue, deno es he alse logical alue. Ou o mula
has wo di e en logical a iables, so he able has 22 ows. In p ac ice we use
he a ian in he Table 2. I we use compu e s o ill he able, ou able on
Table 3 became mo e compac .
USING SPREADSHEETS FOR SOLVING LOGIC PUZZLES 19
Table 2. Compac u h- able o ((A⊃B)⊃A)⊃A
((A⊃B)⊃A)⊃A
In he case o he Table 1 he las column de e mines he p ope y o
he o mula. I all he alues in his column a e ue, hen he o mula is a
logical law. I all he alues in he column a e alse, hen he o mula is a
con adic ion; bu i he e is a leas one ue alue, he o mula is sa is iable.
The o mula Bis he logical consequence o o mulae A1, . . . An, i he
o mula A1∧ · · · An⊃Bis a logical law. This heo em is he eason why we
a e in e es ed in ue- ables.
Table 3. Ve y compac u h- able o ((A⊃B)⊃A)⊃A
A B ((A⊃B)⊃A)⊃A
3. Sp eadshee s and logic
The ue and alse logical alues can be eplaced wi h he numbe s 1 and
0, and we can w i e a i hme ical exp essions ins ead o logical exp essions. Fo
example ins ead o nega ion o x, conjunc ion o xand yand disjunc ion o x
and ywe can w i e 1 −x, min{x, y}and max{x, y}, espec i ely.
A he mos ecen sp eadshee s we do no need o use such icks. The
Excel, which is he mos augh and used sp eadshee , con ains he ollowing
logical unc ions: TRUE,FALSE,NOT,AND,OR and IF. Wi h hese unc ions we
can w i e any logical unc ion. The implica ion is no lis ed be o e, we need
o use he well-know ¬A∨B ans o ma ion o A⊃B. The usage o Excel
syn ax gi es sho e o mulae han he a i hme ic no a ion, we will use i in
he ollowing.
Le us see a simple p oblem: he o mula A∨Cis he consequence o
o mulae A∨Band B∨C? We ha e 3 logical a iables, so he u h- able has
8 ows. The Table 4 lis s all he cases. We can gi e hese da a by yping, bu
as we ha e mo e and mo e a iables i became a leng hly p ocedu e. Le us
20 M ´
ARIA BAK ´
O AND L ´
ASZL ´
O ASZAL ´
OS
Table 4. T u h- able o checking logical consequence
A B C A ⊃B A ⊃C B ⊃C
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
allow Excel o wo k! Le us w i e he numbe s om 0 o 7 in he i s column
o he wo kshee ! To simpli y he desc ip ion we use he ollowing no a ion:
A1←0, and A2←=A1+1. This means ha we w i e 0and =A1+1 in A1 and
A2, espec i ely. Finally copy he A2 o A3 : A8! Now lis he di e en
combina ions o logical a iables: B1←=ISEVEN(A1),C1←=ISEVEN(A1/2)
and D1←=ISEVEN(A1/4), by using he au oma ed con e sion o ISEVEN.
Nex we can copy B1 : D1 o B2 : D8, and we a e eady o w i e down ou
logical o mulae. We sugges o sa e his and simila iles as a empla e o
speed up he wo k on lessons. In Excel we can w i e down he hypo heses
A∨B,B∨Cand consequence A∨Cas E1←=OR(B1,C1),F1←=OR(B1,D1)
and G1←=OR(B1,D1), espec i ely. O cou se we need o copy E1 : G1 o
E2 : G8 o ill he u h- able.
Acco ding o he de ini ion o logical consequence he emaining ques ion
is he ollowing: is he e any ow whe e in he columns Eand F he alues
a e ue, and in he column G he alue is alse. In his small able we can
ind he sui able ow easily, bu in big u h ables we sugges o se up he
Excel’s au oma ed il e o columns E−G, and choose he e he igh logical
alues.
4. Smullyan’s puzzles
In his book “Wha is he name o his book?” Raymond M. Smullyan
used a lo o puzzles o illus a e he backg ound o he G¨odel incomple eness
heo em. These puzzles became popula and nowadays a e being published in
amusemen magazines, oo. In each sec ion o he book di e en condi ions
a e me . In he bes known ype o puzzles we ha e only wo ypes o people,
knigh s and kna es. Knigh s always ell he u h and kna es always lie.
USING SPREADSHEETS FOR SOLVING LOGIC PUZZLES 21
In he puzzles he inhabi an s make s a emen s abou hemsel es and
abou he o he s, o example “Ais a kna e.” o “B said ha she was no a
kna e.” Usually, o sol e a puzzle we mus de e mine he ype o pe sons.
In hese knigh -kna e puzzles we can use he unc ion ISEVEN again, o
example we could use he o mula =IF(ISEVEN(A1/4),"knigh ","kna e")
when we lis all he combina ion o ypes o inhabi an s.
In some Smullyan puzzle we ha e h ee kinds o pe sons: u h- elle , lia
and s o y- elle . The u h- elle always ell he u h, he lia always lies and
he s o y- elle s some imes ell he ue and some imes lie. The p oblem o
Z ´ınyi Ilona [5] con es , 1992/28 o K7 s uden s is he ollowing:
One o A,Band Cis he guil y. The guil y is a u h- elle
and he he o he s a e no u h- elle s. The inhabi an s said
A: I’m innocen .
B: I is ue.
C:Bis no a s o y- elle .
Who is he guil y?
Conside ing hese kind o puzzles he unc ion ISEVEN is no enough o
gene a e all he combina ions o ypes o pe sons. We can use he unc ions
MOD and CEILING ins ead o i . The comple e solu ion o he puzzle can be
ound in [4].
5. Lady and he ige
The p e ious puzzle could be sol ed easily wi hou a sp eadshee , o cou se.
Le us see a puzzle [15] which is mo e complica e:
The p isone is in o med ha he e is one oom wi h a lady
in i ; all he o he s ei he ha e a ige in hem o a e emp y.
The sign on he doo o he oom wi h he lady in i is ue,
he signs on all he doo s wi h ige s in hem a e alse, and he
signs on he doo s o emp y ooms can be ei he ue o alse.
The signs o he ooms a e he ollowing:
I The lady is an odd-numbe ed oom.
II This oom is emp y.
III Ei he sign on Room V is igh o sign on Room VII is
w ong.
IV Sign on Room I is w ong.
V Ei he sign on Room II o sign on Room IV is igh .
VI Sign on Room III is w ong.
VII The lady is no in Room I.
VIII This oom has a ige and Room IX is emp y.
IX This oom has a ige and sign on Room VI is w ong.

22 M ´
ARIA BAK ´
O AND L ´
ASZL ´
O ASZAL ´
OS
Whe e is he lady?
Fo he simple o maliza ion we say ha we ha e nine ooms, in any
oom can be a ige and he lady can be in any oom. By his we ha e
29×9 = 4608 cases, so he adi ional u h- able me hod does no wo k,
hence we use sp eadshee so wa e again. The comple e solu ion o he puzzle
can be ound again in [4].
We can use he au o il e o ind all he di e en solu ions, and i u ns
ou ha he lady could be in se e al oom. The ex o he o iginal puzzle
con ains a sen ence ha I no men ioned un il now. I we de e mine ha he
oom VIII is emp y o no , we could sol e he puzzle. So apply he il e o
he column T(s a us o oom VIII), and we can ealize, i his oom is emp y,
he lady can be in many ooms, bu i a ige is in oom VIII, hen he lady
can be only in he oom VII. So his is he solu ion.
A e sol ing his puzzle wi h ou s uden s, we can show hem he o iginal
solu ion o Smullyan, which is one page long solu ion. I is a good hing, i
he s uden s ealize, ha using sp eadshee s is only one o he possible sol ing
me hods, and maybe no he as es o simples one.
6. Discussion
The knigh -kna e logic puzzles a e e y popula ; he Knigh s and kna es
Wikipedia page gi es a long lis o compu e games, mo ies, ca oons and
comics whe e we can mee wi h such puzzles. You can mee egula ly on
Hunga ian ma hema ics con es s[1, 5]. These kind o puzzles a e in e es ing o
esea che s, oo. In he las hi y yea s since [14] published, se e al me hods
used o sol e hese kind o me hods. He e we gi e a no comple e lis o
di e en sol ing me hods:
•an ex ension o he classical p oposi ional logic [9],
• i s -o de logic, and au oma ed heo em p o e [11],
•p oposi ional logic and ableaux me hod [13],
•modal logic and ableaux me hod [3] o sol e all he puzzles in [14],
• ew i ing g aphs [10],
•CLIPS p og amming language [18],
•P olog p og amming language [2, 19],
•SHQL me a-que ies [7]
•Smodel sys em [12],
•SAT sol e [6].
F om his lis we can ealize, i ou s uden s would like o apply some o
he me hods men ioned be o e, hen hey need o lea n some special logic,
me hod o some new p og amming language. Mos o hese logics, me hods
and languages so speci ic, ha only he bes s uden s a he uni e si y le el
USING SPREADSHEETS FOR SOLVING LOGIC PUZZLES 23
a e able o unde s and. Ou al e na i e is he applica ion o a well-known
ool. Ou he s uden s a p ima y school a e able o use, ye . They do no
need o lea n a new so wa e, jus some unc ions o he amilia sp eadshee
so wa e, and hey a e able o sol e e y ha d puzzles, oo.
The sol ing o puzzles wi h and wi hou any ools a e di e en . When
somebody sol e a puzzle wi hou any ools, hen he needs o analyse he
p oblem, needs o conside all he aspec s o he p oblem, and needs o explo e
ela ionships and ules o cons uc he solu ion. I somebody use a sui able
ool, hen usually he only needs o o mula e he p oblem espec ing he ules
o he ool. Then he ool gi es all he solu ions o he p oblem.
Ob iously i is be e i a s uden can sol e such puzzles wi hou any
ool. Bu mos o hese puzzles a e ha d, and an o dina y s uden canno
sol e i alone. A sol ing puzzles wi h sp eadshee s, he eache can show
in e es ing ela ionships by il e ing ou he unin e es ing pa o he able.
Wi h his he eache can show/ each he elemen s o he deduc ion. Mo eo e
he can elimina e he s uden s misunde s andings showing coun e examples.
We hink, ha he success ul solu ion o ha d puzzles gene a e a posi i e
a i ude o s uden s, and his can help o aise he in e es o he s uden s
o logic.
7. Conclusion
In he a icle we ha e shown some in e es ing puzzles, ha a e e y much
liked and gladly sol ed by s uden s. Mo eo e we ha e p esen ed hei solu ion
me hod using u h ables. This p ocess can be speeded up using sp eadshee s.
These puzzles can be e eshing excep ions be ween s a is ical and economi-
cal exe cises. Fu he mo e he p ocess o sol ing hese kinds o puzzles is a
good p epa a ion o unde s anding and lea ning he logical consequence and
deduc ion.
Re e ences
[1] Abacus Jou nal o Ma hema ics h p://www.ma egye.hu/abacus/
[2] L. Aszal´os. Smullyan’s logical puzzles and i s au oma ed sol ing. Tech. Repo o Ins i u e
o Ma hema ics and In o ma ics, Uni e si y o Deb ecen, 2000/14, (in Hunga ian)
[3] L. Aszal´os Au oma ed puzzle sol ing. Jou nal o Applied Non-Classical Logics, 12(1):99-
116, 2002
[4] M. Bak´o and L. Aszal´os Solu ion o he puzzles o his a icle
h p://www.in .unideb.hu/∼aszalos/puzzle.xls, 2008
[5] Mih´aly Cso d´as, ´
E a H´a in´e Kun, Zsuzsa Janics, Tibo Nagy, M´a ia D . Palo ai-
n´e B¨o ¨oczki, and Is ´an Szab´o. Z ´ınyi Ilona Ma ema ika e seny elada ai 1992-2000,
7. osz ´aly. MATEGYE Alap´ı ´any, 2008.
[6] Elizabe h Cassell Knigh s and Kna es ansla o in o SAT ma ices
h ps:// wiki.soe.ucsc.edu/ wiki/bin/ iew/SoeClasses/CMPS240
24 M ´
ARIA BAK ´
O AND L ´
ASZL ´
O ASZAL ´
OS
[7] P. Dohe y, J. Kachnia z and A. Szalas Me a-Que ies on Deduc i e Da abases Funda-
men a In o ma icae, 40, 1, 17-30, 1999
[8] H. James Hoo e and Pio Rudnicki. Teching eshman logic wi h Miza -MSE. In DI-
MACS Symposium on Teaching Logic and Reasoning in an Illogical Wo ld, Ru ge s Uni-
e si y, Pisca away, New Je sey, 1996.
[9] A. Kolany. A gene al me hod o sol ing Smullyan’s puzzles. Logic. Log. Philos., No. 4.
97–103., 1996.
[10] B. Nagy SW- ype puzzles and hei g aphs, Ac a Cybe ne ica 16, 67-82., 2003
[11] H. J. Ohlbach P edica e Logic Hacke T icks, Jou nal o Au oma ed Reasoning 1, 435–
440, 1984
[12] D. W. O Ecological Li e acy: Educa ion and he T ansi ion o a Pos mode n Wo ld
SUNY P ess, 1992
[13] J. F. Pelle ie Using Seman ic Tableaux o Sol e Knigh and Kna e p oblems
h p://www.s u.ca/ je pell/Cogs300/KnKTableaux.pd
[14] R. M. Smullyan. Wha is he name o his book? (The iddle o D acula and o he logical
puzzles). P en ice Hall, Inc., 1978.
[15] R. M. Smullyan. The Lady o The Tige ? and O he Logical Puzzles. Al ed A. Knop ,
Inc., 1982.
[16] R. M. Smullyan. The iddle o Schehe azade, and o he amazing puzzles, an icen and
mode n. Al ed A. Knop , Inc., 1996.
[17] Sp eadshee s in Educa ion (ISSN 1448-6156) h p://epublica ions.bond.edu.au/ejsie/
[18] S uden g oup 1. P og amming language CLIPS h p://www. e .ne .ua/wo k/de -
26349.h ml (in Russian)
[19] P. Sze edi Teaching Cons ain s h ough Logic Puzzles in Recen Ad ances in Con-
s ain s, Sp inge LNCS 3010, 196–222, 2004.
[20] A. Zalewska. An applica ion o Miza MSE in a cou se in logic. In J. S zednicki, edi o ,
Ini ia i es in Logic, pages 224–230. Ma inus Nijho Publishe s, 1987.
Uni e si y o Deb ecen, Facul y o Pedagogy, Facul y o In o ma ics
E-mail add ess:[email p o ec ed], [email p o ec ed]