Personal Blogs

Here we look deeper into using the Boolean operators provided by Python and consider how the missing logical operation implication works with the other operators. An example of joining conditions with or might be

if files_still_loading or preferences_not_initialized or no_user_input:
     sleep(5)

An example of joining with and might be

if no_workers_running and files_saved and not_cancelled:
    exit_program()

These examples are easy to comprehend because all the conditions are simple Boolean values but complex expressions joined with the logical operators may present more of a problem.

The 'happy' or 'sad' scenario can provide some additional insight into the meaning of these operators and the equivalence of implication to if ... then.

Suppose a person's happiness results from a number of conditions happy_1, happy_2, happy_3, etc. The condition happy_1 might be (holiday and sunny), happy_2: (workday and got_a_lot_done), happy_3: (15 < temperature_today < 30) and so on.

If the conditions are joined with or

happy_1 or happy_2 or happy_3 or ...

when any one condition is satisfied this person will be happy. A nice thought but probably not a match for many requirements.

If the conditions are joined using and

happy_1 and happy_2 and happy_3 and ...

for this person to be happy all the conditions must be satisfied and they are likely to be sad most of the time. Additionally some conditions are mutually exclusive, a holiday cannot also be a workday, so this person will never be happy. To avoid this problem such conditions can be grouped using or but do not forget the brackets 

(happy_1 or happy_2) and happy_3

Note that conditions containing not produce mutual exclusion when not is applied to the same variable or expression. Therefore we need to write

((not workday and sunny) or ( workday and got_a_lot_done)) and ...

Missed mutual exclusion may account for the occasional condition that is never True or always True. De Morgan's laws can sometimes simplify expressions or reveal hidden problems when not is used:

not(P and Q) is equivalent to (not P) or (not Q)

not(P or Q) is equivalent to (not P) and (not Q)

Equivalence means 'and vice versa' in both cases. These laws are fairly easy to remember: and -> or, or -> and when the bracket on the left is 'multiplied' out. 

Implication and short-circuit evaluation

Using or to deal with mutually exclusive conditions only works when exclusion can be guaranteed. Implication provides a catch-all alternative. Suppose that in a language (not Python) there is an implication operator imp and we can write

(holiday imp sunny) and (workday imp got_a_lot_done) and ...

Referring back to the truth table for implication we see that this operation returns True in all cases when its initial argument is False. If it is not a 'holiday' then (holiday imp sunny) evaluates to True whether or not it is sunny.  The falsehood that would have been got from (holiday and sunny) is no longer present and evaluation of workday can be taken into account.

Similarly (workday imp got_a_lot_done) evaluates to True when it is not a workday. This implication is therefore logically equivalent to the if statement in a function

def happy_2(workday, got_a_lot_done):
    if workday:
        return got_a_lot_done()
    else:
        return True 

Additionally, got_a_lot_done(), shown as a function passed as an argument to happy_2(), will only be executed on a workday. Even better, possible double evaluation of workday in the inline version of implication

(not workday or (workday and got_a_lot_done()))

Is eliminated by else and the unassailable logic that if it is not a workday then workday is False.

Python provides short-circuit evaluation of expressions containing the Boolean or and and operators. When evaluating an expression P or Q, Q will only be evaluated if P is False. If P is True then P or Q must be true whatever the value of Q and Q need not be considered. Evaluating P and Q, Q will only be evaluated if P is True.

Apart from improved efficiency, short-circuit evaluation is useful because P can guard Q against evaluation. Searching for a particular value in a sequence of values for example, execution of the search loop can only proceed if indexing into the sequence has not gone beyond its end:

while index < length_sequence and sequence[index] != required_value:
    index += 1 # increment index by 1

Here index < length_sequence guards sequence[index] != required_value: against evaluation when index is out of range.

Sadly, an implication operator P imp Q cannot be implemented as a general purpose function and maintain short-circuit evaluation of Q when Q is an expression. The Q expression must be evaluated before imp() can be called.

Python allows Q to be turned into a function and passed to imp() without evaluating it, as in happy_2()above, but then we get the problem of passing any arguments that function Q() requires. It seems custom rather than general purpose implication-functions may often be required but the logic of implication can be extremely useful so any substitute for an operator is worth considering.

Consider the common occurrence where various actions must be selected depending on the current value of a variable, actions in relation to a student's score in a test for example. A low score results in one set of actions but the boundary between a mid-score and a high score is not only flexible but could depend on an individual student's past performance. If Johny has shown a marked improvement he should get a commendation, perhaps.The ranges for mid score and high score overlap and special assessment is only done for marginal cases as part of high score actions.

These simple requirements can be implemented with a nested if statement:

def low_score():
    print('do low score actions')
    return False

def mid_score():
    print('do mid score actions')
    return True

def high_score():
    print('do high score actions')
    return True

def test_score(score):
    evaluation = False
    if score < 40:
        evaluation = low_score()
    else:
        if 40 <= score <= 85:
            evaluation = mid_score()
        if 75 <= score <= 100:
            evaluation = high_score()
    return evaluation

For more complex requirements a nested if can be come very complicated and error prone and may end up overflowing into the right margin.  Implications linked by and can reduce these statements to a single line of code although, for clarity, it will generally be better to put each implication on a separate line:

def imp(A, B):
    if A: return B()
    return True

def test_score(score):
    print('score', score)
    evaluation = imp(score < 40, low_score) and \
               imp(40 <= score <= 85, mid_score) and \
               imp(75 <= score <= 100, high_score)
    return evaluation

print(test_score(39),'\n')
print(test_score(50),'\n')
print(test_score(80),'\n')

In test_score, evaluation of the Boolean expression is secured by assigning its value to evaluation. A score less than 40 only requires the actions for a low_score. The low_score() function returns False and score evaluation ends. The effect is similar to including a break in a C or Java case statement.

The ranges for mid_score and high_score overlap so the mid_score() function returns True, score evaluation continues and the possibility of a high_score is considered.

A lot of functions get called here but this is not a pure functional approach because the actions of low_score() etc. rely on side effects from the functions. Possibly it could be made pure-functional by making these functions return a new evaluation with the required Boolean equivalent in each case but that is definitely something for later consideration.

To summarize: conditions joined by or test for success, any success. When a condition evaluates to True further conditions are not relevant. Conditions joined by and test for failure. When a condition evaluates to False the complete expression is False.

Implications joined with and introduce a test for applicability returning True if it fails allowing evaluation of further conditions. Under short_circuit evaluation a P imp Q operation is both logically and functionally equivalent to if P then Q. It can be replaced with a function containing such a construct but conditional evaluation will only be maintained if the logical expression Q is represented as and passed as a function.

When conditions are joined with or a similar test for applicability requires an operator that returns False in every case where P is False. This is of course the and operator only returning True when both P and Q are true. Operator precedence means that brackets are not required but to show the logic clearly they may be advisable:

... or (P and Q) or (R and S) ... 

Summary

In Algorithms 5 and 6 we have looked at some of the features of Boolean logic including operator precedence, short-circuit and eager evaluation and the results of applying conjunction, disjunction and implication to Boolean values. I hope I have convinced readers that implication can be of some use apart from supplying yet another operator to be evaluated in truth tables. In Python the logical equivalent provided by all data types supplies a useful paradigm that can simplify code in many situations but overuse should perhaps be resisted.

Bitwise logic, generally the application or the bitwise operators & (and), | (or), ~ (not) to all the bits of integers used as arrays of individual Boolean values, has been left aside for later investigation. 

[Algorithms 7: Logical reality   (c) Martin Humby 2015]