Discrete Mathematics for Freshmen: Teacher Experience

Today I have an unusual text that is completely unrelated to machine learning (for new readers: this text is part of the blog of Surfingbird , in which I talked about different machine learning devices in the last few years in the annex to recommender systems). In this post there will be almost no mathematical part, but there will be a description of a very simple program that I wrote for my students. It is unlikely that someone will learn a lot of new content from this post, but it seems to me that the idea itself is of some value - many people simply don’t think that "it’s possible anyway." So…

Formulation of the problem

')

In this semester, I began a somewhat unusual activity: I teach discrete mathematics for freshmen in the St. Petersburg branch of the Higher School of Economics; I have been teaching for a long time, but it seems that I have never had students under the fourth or fifth year before. Under the link you can find a summary of the course, and even that is incomplete (the course is still under way), but this is not really about that.



I think most of the inhabitants of Habra even approximately remember what “discrete mathematics is for freshmen”: propositional logic, conjunctive and disjunctive normal forms, bases of Boolean functions, binary relations, partial orders ... In general, nothing is conceptually complex, but these are all things which must be mastered very firmly, any mathematical education rests on them, and the need to consciously think about them will quickly become an unaffordable luxury. Therefore, you need a lot of practical examples and tasks to "get a hand".



As one of the forms of reporting, I chose the “big homework”: several practical examples that need to be solved. This form has many advantages: students work at their own pace, I can also check how much you need, everything happens in writing, which is always convenient. But there are also disadvantages; the main disadvantage is simple - it is difficult to make and test fifty options for fifty students (there are about as many on the stream). And if you give one option to a large group, it is clear that you will get beautifully rewritten correct answers at the output, especially considering that in such basic discrete mathematics the “solution course” is often simply absent (how to build the SDNF — well, look at the truth table and write ...).



To get around this problem, I decided to write a simple program that will generate an individual homework for each student at random. The idea is extremely simple, but for some reason I never met her when I was a student, or in a later teaching experience - actually, that's why I am writing this post. I will give a minimal working example, and then I will show what I got as a result.

Templates in .tex and boost :: format

The basic technology is clear - you need to make a LaTeX-blank into which to insert specific tasks for each student. It doesn’t matter what language to do it, I am historically accustomed to writing small programs in C ++, so I’ll use it here. The easiest way to do this in C ++, which I know, is boost :: format : it is enough to make blanks with placeholders like% 1%,% 2%, and then you can insert anything there (boost :: format has other possibilities , but we do not need them now).



So, we make templates. First, the general template of the "abstract LaTeX document":







Then a specific template of the actual task - we will substitute it instead of% 1%. I here, as promised, give a minimal example. We will generate only one task: according to a given Boolean formula, translate it into several other forms.







And now we just need to generate, than fill in% 3% (instead of% 1% and% 2% the student’s name and group number will be substituted). For this you need to learn how to generate formulas. Immediately I warn you that I am a bad programmer, and the code below probably resembles spaghetti - in principle, it works, if someone advises an elegant refactoring, I will say thank you.



First you need to have a structure that will store different bundles and types of nodes in the formula; for our minimal example, this is unnecessary, but I had to do another task about formulas for algebra of sets (union, intersection and symmetric differences), and I wanted to reuse the code about formula trees. Therefore, here is a global object that stores basic information:







Here we created the “language of Boolean formulas”, which has five binary bundles (conjunction, disjunction, implication, XOR and equivalence) and one unary (negation). The seventh type of node is a variable, it has an arity of 0. In my homework, I limited myself to the formulas of four variables: less is not enough, and more is becoming too cumbersome. It is also convenient to write here the generators of a random type of a node, a random variable, a random binary connection (I used the distributions from boost :: random - again, very conveniently, although there is not much that is implemented, but we don’t need much now).



This structure will be easily reused for set algebra formulas (this is just for comparison, no further GSet will be used):







Now create a formula class. A Boolean formula is a tree whose leaves are variables, and the internal vertices are logical connectives. We want to be able to generate formulas of a given depth, so we will pass to the constructor if it’s time to make this node a leaf or, on the contrary, necessarily a binary bundle. If you need to create a random node, we will pass the type g-> TypesNo. If the node turns out to be a sheet, it needs to generate a variable (so that the variables are likely to fall into everything, we just take them in a circle - formulas, of course, are not completely random, but this is not terrible).







Now we begin to fill the class BNode. The main thing for us is that the formula is successfully printed in LaTeX:







In addition, you will need to be able to calculate the value of the formula on a given set of variables:







Let's leave BNode class for now (we'll return to it); now we can write a random formula generator. We will generate a formula with a specified minimum and maximum depth (to maintain the minimum depth, we added the must_not_be_leaf field to the constructor earlier):







Everything is self-evident; the only solution I took here was to make the unary functions (ie, negations) “free”, not considered for depth, otherwise the formulas would turn out to be too simple. In addition, in the Boolean formula it is logical to prohibit putting two negatives in a row, it is meaningless; for this we needed the must_be_binary flag in the constructor.



And you can write a file handler with a list of students:







and then main, which reads files with formats and processes files with student lists:







But wait, I hear the voice of the attentive reader. It will be nonsense to turn out - I suppose, a good half of the random formulas thus generated will turn out to be trivial! What is true is true - I don’t know about half, but even one randomly generated formula of the form \ varphi = x will considerably tarnish the reputation of our method. Let's learn how to check this. To do this, we simply calculate how many bundles and different variables are found in the formula, and demand that the variables meet all, and the bundles - at least two different. Add a formula traversal to BNode:







and enter the validation of the formula for reasonableness:







You may still want to check whether the formula is, say, always true, but I consciously decided not to do this - if a complex-looking formula suddenly turns out to be identically true, the more interesting this task will be for the student. And obvious subformulas of the type “x or not x” in our generator will not be obtained, because the variables are sorted out in turn, and not by chance.



Running the resulting program on a file with a list of students, we obtain a .tex file with quite adequately executed tasks (here is an example pdf compiled from such a file ).

Solutions

A skeptical reader at this place will reasonably argue: well, of course, you can generate over 9000 different tasks, but you will be tortured to check them later! Indeed, checking each student’s truth table is an exercise for very strong-minded people, whom I do not consider myself to be. Therefore, our program must be modified so that it can facilitate the verification process. It won't be possible to automate it completely (students will still hand over works written in free format by hand), so it will be enough just to do the most nasty part of this work in advance.



We get another LaTeX-template for the document with the answers:







I, again, limit myself to a minimal example — let's just derive a truth table. To do this, go through all the possible values ​​of the variables, calculate the truth value of the formula and beautifully draw the result in TeX. Add two methods to the BNode class:







and then add it to the process_one_student_file_boolean:







As a result, the corresponding decision file ( the same example, solutions ) is obtained in a pair to the task file ( example ), with which it becomes much easier to check.

Conclusion

And here's the result - half a day of work, and at the exit, as many tasks as you like with ready-made answers, everything is beautifully decorated and ready to be issued to students. If you are interested in how the real task turned out, here is an example of the final result . I will not post the answer file so as not to prompt the students once more - they are now solving this homework. I think that if my teaching at the HSE continues, this program will serve me more than once; The closest chance to apply it is tickets for the written exam in the same groups.



PS When I was preparing an article for Habr, I found a small bug in my formula generator; but did not correct. Exercise for the attentive reader: what formulas, in which, in principle, there is nothing bad, my generator will never be able to generate? (in addition to the notes on the selection of variables in order, which I have already done above)