Using spreadsheets for solving logic puzzles

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]