It is my belief that one reason so much computer software does bad input error detection is that most programmers know next to nothing about mathematical logic. Those with backgrounds in EE saw some logic in the guise of switching theory, but they don't apply it to software. Those with Computer Science degrees saw some logic in a Discrete Structures class but it looked useless and they didn't learn to apply it to anything at all.
There are many kinds of mathematical logic. You may have run into terms like "first order," "multi-valued," and "fuzzy." Some of these concepts are indeed useful for esoteric things, but the simplest and most basic form of logic is also the most generally useful.
What you must learn is often called the propositional calculus. It consists of simple propositions that lack phrases like "for every" and "there exists". It is the logic whose theorems you can often verify with truth tables.
Here's an example of what happens when you don't know the propositional calculus:
IF C does not imply P THEN handle an error situation
However, "does not imply" does not compute. You try something. It doesn't work. You are behind deadline and you remove the error check so the program will at least behave correctly when the input is correct.
This is a simple example. Many of you could get it right without knowing anything about the propositional calculus. Even so, if you are conscientious about handling errors and if you don't know about the propositional calculus, then I'll bet you've had a similar experience.
To take this
To say that two logical expressions (or in our case two propositions) are equivalent is to say one expression is true exactly when the other is. You can test this particular equivalence with a truth table but you have to know what "C IMPLIES P" means and how to construct a truth table.
Here is a truth table that defined "C IMPLIES P".
C P C IMPLIES P true true true true false false false true true false false true
This means that you can show that the claim "C IMPLIES P is true by showing it is impossible for C to be true when P is false. If such a thing were possible then the claim that "C IMPLIES P would be a claim that you can deduct false thing from a true thing. That's not the way we want our rules about reasoning to work. As for cases in which C is false, our rules about reasoning have little useful to say about what happens if you start out with false premises. You can think of the truth table as telling you that if you are willing to assume false things, then you can prove anything.
Here's the truth table for "NOT C OR P".
C P NOT C OR P true true true true false false false true true false false true
Because the pattern of true and false in the third column is the same for the two truth tables, "C IMPLIES P is true exactly when "NOT C OR P" is true. That means any IF or WHILE statement which used "NOT C OR P" would work the same way as one which tested whether C implies P.
In theory, you could make big multivariable truth tables to check the equivalence of any two boolean expressions. What you would be doing is simply testing all possible cases on paper. Of course, that isn't so simple when there are a lot of cases.
What the the propositional calculus gives you is ways of recognizing equivalent boolean expressions without resorting to truth tables. Actually, this interpretation of the propositional calculus is inherent in the name. The propositional calculus provides you methods of calculating the truth of propositions. By the way, what we call "calculus" has a similar meaning. By learning to manipulate integrals and deriviatives you learn to "calculate" things which had to be worked out with infinite series before the calculus was invented. Both systems of calculus give you algebraic manipulations in place of time consuming manipulations based on basic principles.
Memorizing these facts will be useful to you:
A IMPLIES B is equivalent to (NOT A) OR B NOT(A AND B) is equivalent to (NOT A) OR (NOT B) NOT(A OR B) is equivalent to (NOT A) AND (NOT B)
Appling these facts to our example we see that
Here's a way to stress test you software.
Write down a list of conditions which input data can satisfy, say:
C1 pressure is under 200 psi C2 pressure is over 150 psi C3 temperature is less than 250 centigrade C4 temperature is over 225 centigrade
or whatever. Then write for each interesting result write down a boolean expression that describes the conditions which create that result. Say
C1 AND C2 AND C3 AND C4
This tells you what data should produce the result and you need a test case like that. But you should also test what happens when the data isn't right. To get a list of possible test cases negate the expression and find an equivalent form which uses OR rather than AND as the top level boolean operator. For example,
(NOT C1) OR (NOT C2) OR (NOT C3) OR (NOT C4)
Now devise test cases which satisfy just one of the expressions between the OR's. Each of these will test how your software acts with a particular kind of failure.
Of course, with a real program the situation will be much more complex. Your original condition will probably use IMPLIES and it will not be obvious how to the the expression that breaks things into OR's. For that you need your logic textbook. It will show you how to convert any proposition written in the propositional calculus into an equivalent proposition that is in disjunctive normal form. From the disjunctive normal form you can easily make your test cases.
This tip is distributed to individuals free of charge from the Software Build and Fix web site. All other distribution (including but not limited to internal distribution within an organization and mirroring of any kind) is forbidden without written consent of the copyright holder.
Return to the top of this document.
Thanks to Phil Abercrombie <phila@tssc.co.nz>, Scott Renfro <srenfro@silvix.sirinet.net>, and Nils Jonsson <njonsson@.sccsi.com> for pointing out errors in previous versions of this tip.