Skip to main content

Subsection 3.3.11 Back to Boolean Expressions in Programming

Recall that we’ve already seen that Boolean expressions play a key role in programming: they let programs respond to different circumstances, different sets of data, etc.

The Boolean identities that we’ve just proved are true of all Boolean expressions, including the ones in programs. So they can tell us that two Boolean expressions are equivalent and thus that two programs, one using one expression and the other using the other, will also be equivalent (up to possible efficiency issues that may arise if one expression is simpler than another).

Both of these Python programs describe the same, very lenient, way of assigning daily credit to students in a class:

 if not Late and not Sleeping: 
		GetFullCredit 
	Else: 
		Fail  
	if not (Late or Sleeping): 
		GetFullCredit  
	Else:   
		Fail

Programmers know that these two programs are equivalent because they know about De Morgan’s laws.

Exercises Exercises

Exercise Group.

1.

1. Consider the following program:

	if Hungry and not (Busy or Broke): 
		GetFood

Consider the following alternative programs:

  1. 	if Hungry and not Busy and not Broke: 
		GetFood 


  2. 	if (Hungry and not Busy) or Broke: 
		GetFood 


  3. 	if not (not Hungry or Busy or Broke): 
		GetFood

Which of them is/are equivalent to our original program?

  1. Just I.

  2. Just II.

  3. Just III.

  4. I and II.

  5. I and III.

Answer.
Correct answer is E.
Solution.

Explanation: I is equivalent. We can get from the original Boolean expression to its with a single application of De Morgan. II is not equivalent. III is equivalent. To see why, apply De Morgan once to its Boolean expression, which will produce I.