Ternary Logic Task
Back to General discussions forum
Hi Friends!
Here is a draft of the new problem (not very puzzling, rather didactic). As it is some time since I created tasks myself, and as I'm known to make multiple mistakes in them - I invite you to test it gently. Checker should work, hopefully.
Rodion,
This looks like an interesting problem. Before giving it a try I would like to raise some points. I assume that the intention is to take the user's logic expression and then to translate this back into a truth table to see whether or not this matches the truth table set in the problem. It is clear that there are multiple correct answers to each problem but it might be helpful if the problem description could make this clear. Some alternative solutions involve fairly trivial rearrangements such as swapping the two operands of a binary operator. Other alternative solutions could be many times longer than the optimum solution. Are you intending to accept any correct solution, or will you expect one of minimal length, or perhaps give some limit for the length which will be accepted? Giving a length restriction would be problematic if the truth tables are created at random. For some truth tables I would expect the optimum length of the logic expression to be surprisingly long. However, if you are generating the truth tables from random (relatively simple) logic expressions then you can easily impose a limit on the length. I think it would be helpful if the problem description gives some guidance on the likely complexity of the logic expressions which need to be created.
Dear Clive, thank you for the feedback - really the statement looks weird without such clarification. I added a note, explaining that checker will try calculating whatever expression user may provide without any artificial limitation. Truth tables in the input are generated simply as a random set of nine ternary values - so honestly I myself do not know solution except straightforward generation of qvfwhapgvirabeznysbez (rot13) - which in this case may easily lead to expressions of about 100 characters long.
Rodion,
Thanks for your clarifications. I have written a program which creates correct (I think) logic expressions, without any attempt to keep them short. The average length of the expressions is 135 characters, although I am sure that some of the brackets are unnecessary. I submitted the problem and got a message "Seems to be correct" which I assume is because this is still a draft program. If the checker has decided that all 5 of my long complex expressions are correct then I think we can assume that everything is working. Certainly, writing a program to generate short expressions would be much more demanding, especially as some of the randomly generated truth tables probably cannot be turned into a shortish logic string. As it stands, the problem is probably solvable by a good number of Code Abbey members.
Clive, thank you for help and testing it! It is published now! I mostly was concerned about the checker "calculating" the expressions.
Certainly, writing a program to generate short expressions would be much more demanding
Yes, I don't think it is worthwhile in the form of the same task, though the more general problem of somehow "grouping" cells in the table (e.g. truth table) looks curious.
Although the problem does not require it, I couldn't stop thinking about ways to generate minimal logic expressions and have been investigating this for the last two days. I define a minimal logic expression as one which represents a given truth table, using the smallest number of characters in the expression.
I have now been able to generate minimal logic expressions for all 19683 truth tables. For most truth tables there are multiple ways of producing a minimal logic expression so these are certainly not unique. The most difficult truth table to deal with is TFF UTU TFT. My program (in Python) took 20 seconds to find a minimal expression for this truth table. The result was !(!(B^B)^!~A&(B|~!A)) with a length of 21 characters. This is the longest minimal expression found for any of the truth tables. The average length of all expressions is 14.3 characters.
I have just read the previous post which claims that the problem is now published. However, it does not seem to be present in the recent problems list.