Using spreadsheets for solving logic puzzles

STUDIA UNIV. BABES¸–BOLYAI, INFORMATICA, Volume LIV, Number 1, 2009 USING SPREADSHEETS FOR SOLVING LOGIC PUZZLES M´ ARIA BAK´ O AND L´ ASZL´ O ASZAL´ OS Abstract. The consequence relation and perfect usage of derivation is a necessary knowledge for layers, economists, engineers and for hundreds of other different professionals. Students in the low and mid level education system are able to solve simple logical puzzles without any special training, but some of the puzzles in Smullyan’s books present a challenge even for university students. Some of the logic and artificial intelligence courses contain methods for examining deductions and the students might even use special tools and software to facilitate the process. In this article we would like to show you that the well-known spreadsheet software is a great tool to solve puzzles that can be expressed in sentence (or in zero-order) logic. Many students therefore will be able to solve even complicated puzzles without learning any special soft wares. This can be very helpful for teachers teaching deduction, but it can be also helpful for the teachers teaching spreadsheet software usage, because their students would be able to solve challenging problems by learning to use new functions. The knowledge of these functions could be useful later solving other type of problems, too. 1. Introduction The curriculum of the elementary and the secondary schools requires the teaching of information technology and training in computer skills. At many schools students are preparing for the European Computer Driving License exam because it is an internationally recognized qualification, and helps the students to boost their productivity, later on it helps them to be competitive on the labor market and successful at the entrance exams. The students favorite topics are the word processing and the spreadsheets softwares because these are the most commonly used in the everyday life. Spreadsheets Received by the editors: December 6, 2008. 2000 Mathematics Subject Classification. 03B35, 68T20. 1998 CR Categories and Descriptors. I.2.3 [Topic]: Deduction and Theorem Proving – case-based deduction; F.4.1 [Topic]: Mathematical logic – mechanical theorem proving . Key words and phrases. Logic puzzles, Case-based deduction, Mecnahical theorem proving, Spreadsheets. This paper has been presented at the 7th Joint Conference on Mathematics and Computer Science (7th MaCS), Cluj-Napoca, Romania, July 3-6, 2008. 17 18 M ´ ARIA BAK ´ O AND L ´ ASZL ´ O ASZAL ´ OS Table 1. Truth-table of ((A⊃B)⊃A)⊃A A B A ⊃B(A⊃B)⊃A((A⊃B)⊃A)⊃A t t t t t t f f t t f t t f t f f t f t are good for budgeting or accounting planning, for calculations and analysis, and further more it is a good tool to practice mathematics or different mathematical concepts/ideas or sometimes just to play with. The journal Spreadsheets in Education [17] contains lots of interesting examples. In this article we will show how we can utilize spreadsheets in the teaching of mathematics, especially how to solve logic puzzles in [14, 15, 16]. These puzzles are suitable tools to show the elements of the deduction [8, 20]. Many students at university level use only true-tables to check the validity of a logical consequence, and they survive with this knowledge while they work with toy problems. But one of the puzzles solved in the paper is so complicate that the corresponding truth-table has more than 4,500 rows. The construction of the spreadsheet which solves this puzzle is not a complicated task and use only simple functions. Hence this method can be used at elementary schools level, too. Moreover the solution process of logic puzzles is a challenging problem, and differs from the usual spreadsheet problems. This kind of diversity helps us to hold up the interest of students, which is the key point of the education. We remark that the mathematical contests at elementary school level in Hungary often contain these kind truth-teller and liar logic puzzles. 2. Truth-tables We have several methods to check logical consequences. In the case of sound and complete calculus we can replace the consequence relation with decidability, and we can use automated theorem provers. In the case of sentence logic we can use the truth-tables. In the rows of this table at first we list all the logical combinations of the logical variables, and next we determine the values of the formulae in these cases. The Table 1 shows such a table, where the columns belong to the subformulae of the original formula. In out truth-tables tdenote the true, fdenotes the false logical value. Our formula has two different logical variables, so the table has 22rows. In practice we use the variant in the Table 2. If we use computers to fill the table, our table on Table 3 became more compact. USING SPREADSHEETS FOR SOLVING LOGIC PUZZLES 19 Table 2. Compact truth-table of ((A⊃B)⊃A)⊃A ((A⊃B)⊃A)⊃A t t t t t t t t f f t t t t f t t f f t f f t f f f t f In the case of the Table 1 the last column determines the property of the formula. If all the values in this column are true, then the formula is a logical law. If all the values in the column are false, then the formula is a contradiction; but if there is at least one true value, the formula is satisfiable. The formula Bis the logical consequence of formulae A1, . . . An, if the formula A1∧ · · · An⊃Bis a logical law. This theorem is the reason why we are interested in true-tables. Table 3. Very compact truth-table of ((A⊃B)⊃A)⊃A A B ((A⊃B)⊃A)⊃A t t t t f t f t t f f t 3. Spreadsheets and logic The true and false logical values can be replaced with the numbers 1 and 0, and we can write arithmetical expressions instead of logical expressions. For example instead of negation of x, conjunction of xand yand disjunction of x and ywe can write 1 −x, min{x, y}and max{x, y}, respectively. At the most recent spreadsheets we do not need to use such tricks. The Excel, which is the most taught and used spreadsheet, contains the following logical functions: TRUE,FALSE,NOT,AND,OR and IF. With these functions we can write any logical function. The implication is not listed before, we need to use the well-know ¬A∨Btransformation of A⊃B. The usage of Excel syntax gives shorter formulae than the arithmetic notation, we will use it in the following. Let us see a simple problem: the formula A∨Cis the consequence of formulae A∨Band B∨C? We have 3 logical variables, so the truth-table has 8 rows. The Table 4 lists all the cases. We can give these data by typing, but as we have more and more variables it became a lengthly procedure. Let us 20 M ´ ARIA BAK ´ O AND L ´ ASZL ´ O ASZAL ´ OS Table 4. Truth-table for checking logical consequence A B C A ⊃B A ⊃C B ⊃C t t t . . . t t f . . . t f t . . . t f f . . . f t t . . . f t f . . . f f t . . . f f f . . . allow Excel to work! Let us write the numbers from 0 to 7 in the first column of the worksheet! To simplify the description we use the following notation: A1←0, and A2←=A1+1. This means that we write 0and =A1+1 in A1 and A2, respectively. Finally copy the A2 to A3 : A8! Now list the different combinations of logical variables: B1←=ISEVEN(A1),C1←=ISEVEN(A1/2) and D1←=ISEVEN(A1/4), by using the automated conversion of ISEVEN. Next we can copy B1 : D1 to B2 : D8, and we are ready to write down our logical formulae. We suggest to save this and similar files as a template to speed up the work on lessons. In Excel we can write down the hypotheses A∨B,B∨Cand consequence A∨Cas E1←=OR(B1,C1),F1←=OR(B1,D1) and G1←=OR(B1,D1), respectively. Of course we need to copy E1 : G1 to E2 : G8 to fill the truth-table. According to the definition of logical consequence the remaining question is the following: is there any row where in the columns Eand Fthe values are true, and in the column Gthe value is false. In this small table we can find the suitable row easily, but in big truth tables we suggest to set up the Excel’s automated filter for columns E−G, and choose there the right logical values. 4. Smullyan’s puzzles In his book “What is the name of this book?” Raymond M. Smullyan used a lot of puzzles to illustrate the background of the G¨odel incompleteness theorem. These puzzles became popular and nowadays are being published in amusement magazines, too. In each section of the book different conditions are met. In the best known type of puzzles we have only two types of people, knights and knaves. Knights always tell the truth and knaves always lie. USING SPREADSHEETS FOR SOLVING LOGIC PUZZLES 21 In the puzzles the inhabitants make statements about themselves and about the others, for example “Ais a knave.” or “B said that she was not a knave.” Usually, to solve a puzzle we must determine the type of persons. In these knight-knave puzzles we can use the function ISEVEN again, for example we could use the formula =IF(ISEVEN(A1/4),"knight","knave") when we list all the combination of types of inhabitants. In some Smullyan puzzle we have three kinds of persons: truth-teller, liar and story-teller. The truth-teller always tell the truth, the liar always lies and the story-tellers sometimes tell the true and sometimes lie. The problem of Zr´ınyi Ilona [5] contest, 1992/28 for K7 students is the following: One of A,Band Cis the guilty. The guilty is a truth-teller and the the others are not truth-tellers. The inhabitants said A: I’m innocent. B: It is true. C:Bis not a story-teller. Who is the guilty? Considering these kind of puzzles the function ISEVEN is not enough to generate all the combinations of types of persons. We can use the functions MOD and CEILING instead of it. The complete solution of the puzzle can be found in [4]. 5. Lady and the tiger The previous puzzle could be solved easily without a spreadsheet, of course. Let us see a puzzle [15] which is more complicate: The prisoner is informed that there is one room with a lady in it; all the others either have a tiger in them or are empty. The sign on the door of the room with the lady in it is true, the signs on all the doors with tigers in them are false, and the signs on the doors of empty rooms can be either true or false. The signs of the rooms are the following: I The lady is an odd-numbered room. II This room is empty. III Either sign on Room V is right or sign on Room VII is wrong. IV Sign on Room I is wrong. V Either sign on Room II or sign on Room IV is right. VI Sign on Room III is wrong. VII The lady is not in Room I. VIII This room has a tiger and Room IX is empty. IX This room has a tiger and sign on Room VI is wrong. 22 M ´ ARIA BAK ´ O AND L ´ ASZL ´ O ASZAL ´ OS Where is the lady? For the simpler formalization we say that we have nine rooms, in any room can be a tiger and the lady can be in any room. By this we have 29×9 = 4608 cases, so the traditional truth-table method does not work, hence we use spreadsheet software again. The complete solution of the puzzle can be found again in [4]. We can use the autofilter to find all the different solutions, and it turns out that the lady could be in several room. The text of the original puzzle contains a sentence that I not mentioned until now. If we determine that the room VIII is empty or not, we could solve the puzzle. So apply the filter to the column T(status of room VIII), and we can realize, if this room is empty, the lady can be in many rooms, but if a tiger is in room VIII, then the lady can be only in the room VII. So this is the solution. After solving this puzzle with our students, we can show them the original solution of Smullyan, which is one page long solution. It is a good thing, if the students realize, that using spreadsheets is only one of the possible solving methods, and maybe not the fastest or simplest one. 6. Discussion The knight-knave logic puzzles are very popular; the Knights and knaves Wikipedia page gives a long list of computer games, movies, cartoons and comics where we can meet with such puzzles. You can meet regularly on Hungarian mathematics contests[1, 5]. These kind of puzzles are interesting for researchers, too. In the last thirty years since [14] published, several methods used to solve these kind of methods. Here we give a not complete list of different solving methods: •an extension of the classical propositional logic [9], •first-order logic, and automated theorem prover [11], •propositional logic and tableaux method [13], •modal logic and tableaux method [3] to solve all the puzzles in [14], •rewriting graphs [10], •CLIPS programming language [18], •Prolog programming language [2, 19], •SHQL meta-queries [7] •Smodel system [12], •SAT solver [6]. From this list we can realize, if our students would like to apply some of the methods mentioned before, then they need to learn some special logic, method or some new programming language. Most of these logics, methods and languages so specific, that only the best students at the university level USING SPREADSHEETS FOR SOLVING LOGIC PUZZLES 23 are able to understand. Our alternative is the application of a well-known tool. Our the students at primary school are able to use, yet. They do not need to learn a new software, just some functions of the familiar spreadsheet software, and they are able to solve very hard puzzles, too. The solving of puzzles with and without any tools are different. When somebody solve a puzzle without any tools, then he needs to analyse the problem, needs to consider all the aspects of the problem, and needs to explorer relationships and rules to construct the solution. If somebody use a suitable tool, then usually he only needs to formulate the problem respecting the rules of the tool. Then the tool gives all the solutions of the problem. Obviously it is better if a student can solve such puzzles without any tool. But most of these puzzles are hard, and an ordinary student cannot solve it alone. At solving puzzles with spreadsheets, the teacher can show interesting relationships by filtering out the uninteresting part of the table. With this the teacher can show/teach the elements of the deduction. Moreover he can eliminate the students misunderstandings showing counterexamples. We think, that the successful solution of hard puzzles generate a positive attitude for students, and this can help to raise the interest of the students for logic. 7. Conclusion In the article we have shown some interesting puzzles, that are very much liked and gladly solved by students. Moreover we have presented their solution method using truth tables. This process can be speeded up using spreadsheets. These puzzles can be refreshing exceptions between statistical and economical exercises. Furthermore the process of solving these kinds of puzzles is a good preparation for understanding and learning the logical consequence and deduction. References [1] Abacus Journal of Mathematics http://www.mategye.hu/abacus/ [2] L. Aszal´os. Smullyan’s logical puzzles and its automated solving. Tech. Report of Institute of Mathematics and Informatics, University of Debrecen, 2000/14, (in Hungarian) [3] L. Aszal´os Automated puzzle solving. Journal of Applied Non-Classical Logics, 12(1):99116, 2002 [4] M. Bak´o and L. Aszal´os Solution of the puzzles of this article http://www.inf.unideb.hu/∼aszalos/puzzle.xls, 2008 [5] Mih´aly Csord´as, ´ Eva H´arin´e Kun, Zsuzsa Janics, Tibor Nagy, M´aria Dr. Palotain´e B¨or¨oczki, and Istv´an Szab´o. Zr´ınyi Ilona Matematikaverseny feladatai 1992-2000, 7. oszt´aly. MATEGYE Alap´ıtv´any, 2008. [6] Elizabeth Cassell Knights and Knaves translator into SAT matrices https://twiki.soe.ucsc.edu/twiki/bin/view/SoeClasses/CMPS240 24 M ´ ARIA BAK ´ O AND L ´ ASZL ´ O ASZAL ´ OS [7] P. Doherty, J. Kachniarz and A. Szalas Meta-Queries on Deductive Databases Fundamenta Informaticae, 40, 1, 17-30, 1999 [8] H. James Hoover and Piotr Rudnicki. Teching freshman logic with Mizar-MSE. In DIMACS Symposium on Teaching Logic and Reasoning in an Illogical World, Rutgers University, Piscataway, New Jersey, 1996. [9] A. Kolany. A general method of solving Smullyan’s puzzles. Logic. Log. Philos., No. 4. 97–103., 1996. [10] B. Nagy SW-type puzzles and their graphs, Acta Cybernetica 16, 67-82., 2003 [11] H. J. Ohlbach Predicate Logic Hacker Tricks, Journal of Automated Reasoning 1, 435– 440, 1984 [12] D. W. Orr Ecological Literacy: Education and the Transition to a Postmodern World SUNY Press, 1992 [13] J. F. Pelletier Using Semantic Tableaux to Solve Knight and Knave problems http://www.sfu.ca/ jeffpell/Cogs300/KnKTableaux.pdf [14] R. M. Smullyan. What is the name of this book? (The riddle of Dracula and other logical puzzles). Prentice Hall, Inc., 1978. [15] R. M. Smullyan. The Lady or The Tiger? and Other Logical Puzzles. Alfred A. Knopf, Inc., 1982. [16] R. M. Smullyan. The riddle of Scheherazade, and other amazing puzzles, anticent and modern. Alfred A. Knopf, Inc., 1996. [17] Spreadsheets in Education (ISSN 1448-6156) http://epublications.bond.edu.au/ejsie/ [18] Student group 1. Programming language CLIPS http://www.ref.net.ua/work/det26349.html (in Russian) [19] P. Szeredi Teaching Constraints through Logic Puzzles in Recent Advances in Constraints, Springer LNCS 3010, 196–222, 2004. [20] A. Zalewska. An application of Mizar MSE in a course in logic. In J. Srzednicki, editor, Initiatives in Logic, pages 224–230. Martinus Nijhoff Publishers, 1987. University of Debrecen, Faculty of Pedagogy, Faculty of Informatics E-mail address:[email protected], [email protected]