From natural language to C++ expression

Question

Assignment:

Translate the following natural language expressions to C++ expressions. Assume that all the variables are non-negative numbers or boolean (of value true or false).

Natural Language:

Either a and b are both false or c is true, but not both.

My solution:

(a==0 && b==0)xor(c==1)

Professors solution:

(!a && !b) != c

Questions:

1. I think I slightly understand the first bracket, by saying "not-a" and "not-b" I think that a and b must then be wrong, provided a b are assumed to be non-zero in the beginning. Right?

2. But what about the part that says "unequal to c"?

3. I don't understand the Professors solution, can anyone break it down for me?

Thank you for the help!

Answer 1

I'll assume that a, b and c are bool.

Let's draw some truth tables:

| a | !a | a==1 | a==0 |
| 0 |  1 |   0  |   1  |
| 1 |  0 |   1  |   0  |

As you can see, a and a==1 are equivalent, and !a and a==0 are also equivalent, so we can rewrite (a==0 && b==0)xor(c==1) as (!a && !b) xor c.

Now some more truth tables:

| a | b | a xor b | a != b |
| 0 | 0 |    0    |    0   |
| 0 | 1 |    1    |    1   |
| 1 | 0 |    1    |    1   |
| 1 | 1 |    0    |    0   |

So a!=b is equivalent to a xor b, so we can rewrite (!a && !b) xor c to (!a && !b)!=c. As you see, your solutions are fully equivalent, just written with different 'signs'.

---

UPD: Forgot to mention. There are reasons why professor's solution looks exactly in that way.

The professor's solution is more idiomatic. While your solution is technically correct, it's not an idiomatic C++ code.

First little issue is usage of types. Your solution relies on conversion between int and bool when you compare boolean value to a number or use xor, which is a 'bit-wise exclusive or' operator acting on ints too. In a modern C++ it is much more appreciated to use values of correct types and not to rely on such conversions as they're sometimes not so clear and hard to reason about. For bool such values are true and false instead of 1 and 0 respectively. Also != is more appropriate than xor because while technically bools are stored as numbers, but sematically you haven't any numbers, just logical values.

Second issue is about idiomacy too. It lies here: a == 0. It is not considered a good practice to compare boolean expressions to boolean constants. As you already know, a == true is fully equivalent to just a, and a == false is just !a or not a (I prefer the latter). To understand the reason why that comparing isn't good just compare two code snippets and decide, which is clearer:

if (str.empty() == false) { ... }

vs

if (not str.empty()) { ... }

Answer 2

Think booleans, not bits

In summary, your professor's solution is better (but still wrong, strictly speaking, see further down) because it uses boolean operators instead of bitwise operators and treating booleans as integers. The expression c==1 to represent "c is true" is incorrect because if c may be a number (according to the stated assignment) then any non-zero value of c is to be regarded as representing true.

See this question on why it's better not to compare booleans with 0 or 1, even when it's safe to do so.

One very good reason not to use xor is that this is the bit-wise exclusive or operation. It happens to work in your example because both the left hand side and right hand side are boolean expressions that convert to 1 or 0 (see again 1).

The boolean exclusive-or is in fact !=.

Breaking down the expression

To understand your professor's solution better, it's easiest to replace the boolean operators with their "alternative token" equivalents, which turns it into better redable (imho) and completely equivalent C++ code: Using 'not' for '!' and 'and' for '&&' you get

    (not a and not b) != c

Unfortunately, there is no logical exclusive_or operator other than not_eq, which isn't helpful in this case.

If we break down the natural language expression:

Either a and b are both false or c is true, but not both.

first into a sentence about boolean propositions A and B:

Either A or B, but not both.

this translates into A != B (only for booleans, not for any type A and B).

Then proposition A was

a and b are both false

which can be stated as

a is false and b is false

which translates into (not a and not b), and finally

c is true

Which simply translates into c. Combining them you get again (not a and not b) != c.

For further explanation how this expression then works, I defer to the truth tables that others have given in their answers.

You're both wrong

And if I may nitpick: The original assignment stated that a, b and c can be non-negative numbers, but did not unambiguously state that if they were numbers, they should be limited to the values 0 and 1. If any number that is not 0 represents true, as is customary, then the following code would yield a surprising answer:

    auto c = 2; // "true" in some way
    auto a = 0; // "false"
    auto b = 0; // "false"

    std::cout << ((!a && !b) != c);

// this will output: 1 (!)
// fix by making sure that != compares booleans:

    std::cout << ((!a && !b) != (bool)c);