8
$\begingroup$

From Discrete Math Rosen Textbook

I'm having trouble interpreting this highlighted sentence (from Discrete Math Rosen Textbook) properly due to using unless more than once in this sentence. I understand that q unless (not p) is the same as saying p implies q, but I'm not sure how to exactly apply that rule here for this sentence. Is it equivalent to saying (by rearranging the sentence a bit):

Unless every input value is tested (call it proposition "p"), unless the correctness of the program is established (call it proposition "q"), no amount of testing can show it produces the desired output for all input values (call it proposition "r").

or

If every input value is not tested, then if the correctness of the program is not established, no amount of testing can show it produces the desired output for all input values.

or

(not p) --> ( (not q) --> r)

or

( (not p) and (not q) ) --> r

Kindly please help me here.

It might just be the commas throwing me off (my bad english lol)

$\endgroup$
4
  • $\begingroup$ I think all four of your proposed interpretations are correct. In particular, the two "propositional" ones are always equivalent. They are therefore also both equivalent to the propositions obtained by swapping $p$ and $q$, which is perhaps the more "natural" interpretation of this sentence. But really I don't think this sentence was intended to be interpreted in formal logic, since it's an informal statement. $\endgroup$ Commented May 20 at 16:32
  • 2
    $\begingroup$ Without trying to recast using formal logic (as mentioned by @Izaak van Dongen), for me it means: "If the correctness of a computer program P is not known, then every input value needs to be tested to establish that P produces the desired output." To me, this is mathematically saying something like "if the equality of two sets is not known, then each element in each set needs to be tested for membership in the other set" OR "if the equality of two functions is not known, then each ordered pair belonging to each function's graph needs to be tested for membership in the other function's graph". $\endgroup$ Commented May 20 at 16:41
  • 1
    $\begingroup$ @IzaakvanDongen: While it's an informal statement as you said, it's really so easy to interpret it rigorously in propositional logic as shown in my answer, that I'm rather surprised it's not being explained... $\endgroup$
    – user21820
    Commented May 21 at 5:25
  • $\begingroup$ @Bob: Do you understand my answer? It's the obvious and simple solution. $\endgroup$
    – user21820
    Commented Jun 8 at 15:01

4 Answers 4

13
$\begingroup$

I would just rewrite the highlighted sentence like this:

If the correctness of a computer program has not been established by some means, then no amount of testing can show that it produces the desired output for all input values unless every single input value is tested.

$\endgroup$
1
  • $\begingroup$ Another rephrasing, avoiding the word "unless" entierly: "If the correctness of a computer program has not been established by some means, then the only way to show that it produces the desired outputs for every input is to test every single input." $\endgroup$
    – Cort Ammon
    Commented May 23 at 3:29
8
$\begingroup$

I agree with Lee Mosher's characterization of the sentence. I'll offer up this suggested rewrite:

No amount of testing can show that a computer program produces the desired output for all input values, unless either every single input value is tested, or the correctness of the program is [theoretically] established.

I appreciate you wanting to translate this into propositional logic, but it doesn't distinguish between truth that is established theoretically vs. experimentally. What the author is saying is that you can't experimentally verify a program without testing all cases.

$\endgroup$
8
$\begingroup$

You shouldn't be rephrasing "unless" using "implies". Instead, simply replace it with "or", and it works:

EITHER the correctness of a computer program is established
OR no amount of testing can show that it produces the desired output for all input values
OR every input value is tested

(The "either" and "or" here are inclusive.)

By the way, Rosen's "Discrete Mathematics" textbook has severe conceptual flaws and is very likely to impede mathematical understanding unless you are already mathematically trained or inclined.

$\endgroup$
2
  • $\begingroup$ Oh wait actually?! Wait but what flaws are there exactly, and where? Also, which discrete textbook would you recommend? $\endgroup$
    – Bob Marley
    Commented May 21 at 17:14
  • 1
    $\begingroup$ @BobMarley: "How to Prove It" by Daniel Velleman is quite good. Also Knuth's "Concrete Mathematics" is worth it if you can get a cheap copy. I don't have a copy of Rosen's textbook right now but I found fundamental conceptual errors in its explanations of logic, and I regularly get students who read it and get conceptual misunderstandings based on what it said. Many popular textbooks are like this because their success is largely due to marketing rather than value. $\endgroup$
    – user21820
    Commented May 22 at 3:27
2
$\begingroup$

There is essentially an "and" between the two "unless" phrases:

Note that unless (the correctness of a computer program is established and every input value is tested), no amount of testing can show that it produces the desired output for all input values.

So this is equivalent to "(not (the correctness of a computer program is established and every input value is tested)) -> (no amount of testing can show that it produces the desired output for all input values.)"

It could also be written as

Note that unless the correctness of a computer program is established, no amount of testing short of testing every input value can show that it produces the desired output for all input values.

Why did the author write it as they did? My guess would be that they felt that "testing every input value" was a qualifier of "testing every input value", and so belongs with that, rather than as a separate condition. It would be a bit weird to say "Unless everything is testing, no testing is enough", kind of like how it would be a bit weird to say "Unless a batter gets four balls, no amount of balls will give them a walk"; you're giving an amount that would be sufficient right before you're saying that no amount would be sufficient. Put the qualifier after the negation makes more sense because now there's something to qualify.

$\endgroup$
1
  • 1
    $\begingroup$ My guess would be that the author first wrote only "unless the correctness of the program is established, no amount of testing can show it produces the desired output for all input values", which is essentially correct in the many cases where the input space is infinite or at least so big that it would take longer than the lifetime of the universe to cover. But then someone noticed that it's not technically correct in general, and so they just appended the bit about exhaustive testing. $\endgroup$ Commented May 22 at 7:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .