How to convert cond statements that produces a boolean value into an expression involving only not, and and or

Question

I am learning about racket/scheme and came across an online resource that said, if a function written using a cond gives true or false, it can be rewritten using only not, and, and or. I have worked out some simple examples where I was able to to convert cond statements into a statement only involving not and and or. My question is if there is a way that the logic can be "seen" right away when converting between these two types of statements. I understand that it is not always practical to convert every cond statement into a combination of not's and's and or's but I am interested in learning about the logic behind the process of converting. Thanks in advance.

(If something about the question does not make sense, leave a comment and I will try clarifying what I want to understand)

Answer 1

First of all, you need to desugar cond language into a sequence of if-then-else sequences, which is trivial.

After that, you can rewrite if conditionals into boolean operators. You can look into a manual of propositional logic to learn this. Or look here.

Btw. It is forbidden to paste your homework on stack overflow.

Answer 2

All conditional expressions (and not only those evaluating to true/false) can be rewritten using only boolean combinators. This is because of how logical operators are evaluated in Scheme/Racket. For instance, logically (and a b) would be true if both a and b are true, and otherwise false. But in Racket, the result of (and a b) is b if both a and b are truthy, and otherwise false. That is, evaluation proceeds to the right until either the last argument or a falsy value is encountered. At that point, evaluation stops and that value (which could be a boolean but needn't be) is returned. It's because and and or don't simply produce boolean output that they can be used to stand in for conditional expressions.

E.g.

(if #t 'hello 'bye) ;=> hello
(or (and #t 'hello) 'bye) ;=> hello
(if #f 'hello 'bye) ;=> bye
(or (and #f 'hello) 'bye) ;=> bye
(cond [#f 'hello]
      [#f 'bye]
      [#t 'aloha]) ;=> aloha
(or (and #f 'hello)
    (and #f 'bye)
    (and #t 'aloha)) ;=> aloha

But you wouldn't usually want to use them that way since they're hard to read. As a general guideline, use if and cond in most cases, rather than elementary boolean operators. If you only care about taking action on a positive or negative result of the conditional, then you could use when or unless. If you do care about handling both positive and negative results, but one of them is a boolean result such as this example:

(if (positive? n)
  #t
  (even? n))

... then this would be a case where a boolean operator would be preferable, like so:

(or (positive? n) (even? n))

If both arms of the if conditional are boolean values, like this:

(if (> n 3)
  #t
  #f)

... then just replace the entire conditional expression with the condition itself:

(> n 3)

Otherwise, stick to if and cond.

Answer 3

Once you convert a cond to nested ifs, you can always turn it into and or and not like this:

(if A B C) --> (or (and A B) (and (not A) C))

However, if you do this blindly, you will get a much more complicated expression than what you could get, so I would add a couple more transformations you can use:

(if A B #f) --> (and A B)
(if A B #t) --> (or (not A) B)
(if A #f C) --> (and (not A) C)
(if A #t C) --> (or A C)

(note: that or above might return a different truthy-value other than #t, making it technically different but equivalent-when-used-as-a-boolean)

Another thing I should note is that sometimes you can transform a multi-branch cond into and or not without transforming into ifs first. For example a 3-branch cond:

(cond [A B]
      [C D]
      [else E])
-->
(or (and A B)
    (and (not A) C D)
    (and (not A) (not C) E))

Or a 4-branch cond:

(cond [A B]
      [C D]
      [E F]
      [else G])
-->
(or (and A B)
    (and (not A) C D)
    (and (not A) (not C) E F)
    (and (not A) (not C) (not E) G))

Each and corresponds to a cond-branch, and each cond-branch's and has nots in it for every previous condition, in addition to its own condition.

A more generic rule you can apply:

for i from 1 through n,
(cond [Q_i A_i]
      ...
      [else E])
-->
on each i, for j from 1 through i-1,
(or (and (not Q_j) ... Q_i A_i)
    ...
    (and (not Q_i) ... E)