» CS1: Lecture 17 – Short-circuiting and Venn Diagrams

CS1: Lecture 17 – Short-circuiting and Venn Diagrams

October 11, 2019 by Chris Johnson. Filed under cs1, fall 2019, lectures.

Dear students,

Today’s our last day of talking about booleans as an independent idea. We will examine an unexpected behavior of our logical operator friends and then discuss one more way to visualize logic: the Venn diagram.

Short-circuiting

Next up we’ll examine the following piece of code. What is the output from each statement?

public static boolean getTrue() {
  System.out.print("T");
  return true;
}

public static boolean getFalse() {
  System.out.print("F");
  return false;
}

public static void main(String[] args) {
  boolean b;

  // Ands
  b = getTrue() && getTrue();
  b = getTrue() && getFalse();
  b = getFalse() && getTrue();
  b = getFalse() && getFalse();

  // Ors
  b = getTrue() || getTrue();
  b = getTrue() || getFalse();
  b = getFalse() || getTrue();
  b = getFalse() || getFalse();
}

I expect that you printed two letters for each statement. However, when we actually run this, we observe that some statements only print one letter. What gives? Well, we know that && requires both its operands to be true. If the first is false, why bother even asking about the second? This is called short-circuiting because we give up early. With ||, if the the first operand is true, who cares about the second?

This idea is not unique to programming. It is common in other areas of human logic. Suppose you’re crossing a street and there’s traffic in the nearest lane. You needn’t bother even checking the far lane. Suppose you want to bake cookies, but have no chocolate chips. Why bother checking the cupboards for flour and baking powder? These examples are both short-circuited ANDs. Consider this OR short-circuiting: suppose you are a merchant who accepts cash or credit. If somebody gives you cash, you don’t also ask for a credit card.

You might think of short-circuiting as just a technical curiosity, but it is more important than that. It often comes in handy to guard against a possibly unsafe operation. We position the unsafe operation as the right operand and the safeguard as the left:

safeguard && unsafe

If the safeguard condition isn’t met, we don’t do the unsafe thing. Consider this unsafe method:

public static boolean hasSameFirstTwoLetters(String s) {
  return s.charAt(0) == s.charAt(1);
}

This is unsafe because s might not have two letters. We can safeguard it:

public static boolean hasSameFirstTwoLetters(String s) {
  return s.length() >= 2 && s.charAt(0) == s.charAt(1);
}

Venn

In the late 1800s, logician John Venn invented a diagram for showing ideas of logic. He writes:

I began at once somewhat more steady work on the subjects and books which I should have to lecture on. I now first hit upon the diagrammatical device of representing propositions by inclusive and exclusive circles. Of course the device was not new then, but it was so obviously representative of the way in which any one, who approached the subject from the mathematical side, would attempt to visualise propositions, that it was forced upon me almost at once.

Next we’ll have a look at the logical operators through the lens of Venn diagrams. Our two predicates will be isDeciduous and isConiferous. We will examine a variety of subsets of the these two populations and craft logical expressions to represent them.

One thing we’ll see in this exercise is that if we can craft an expression for the opposite of our criteria, we can just negate that opposite expression to get the expression we really want. Then we can apply DeMorgan’s Law, which tells us that the following expressions are equivalent:

!(a && b) == !a || !b
!(a || b) == !a && !b

DeMorgan’s Law demonstrates that we can effectively distribute the negation inside the parentheses be negating the operands and alternating the logical operator. That said, we don’t need to distribute the negation if our logic is easier to understand in the negative.

TODO

This rounds out our formal focus on the various boolean operators. Next time, we start talking about conditional statements, which use these booleans to decide what to execute next.

Here’s your TODO list to complete before we meet again:

Our midterm is Monday. Study the old exams. Topics that you can expect on the exam include:
- types
- variables
- naming conventions
- casting and other conversions
- operators (arithmetic, relational, logical)
- methods, parameters, and return types
- objects (constructing and invoking methods)
- String, Scanner, Random, and File
- I/O
If you have prior approval for extended time, please talk to me after lecture today.
The SpecChecker for homework 3 has been updated thanks to a bug report. Update your SpecCheckers by pulling from the template remote.
We will not have labs next week. Any incomplete checkpoints from last lab will just carry over to the next time we meet.

See you next class!

Sincerely,

P.S. It’s time for a haiku!

|| unions two sets
&& finds their intersection
Voting divides them

P.P.S. Here’s the code we wrote together in class…

Booleans.java

package lecture1011.cs145;

public class Booleans {
  public static boolean getTrue() {
    System.out.print("T");
    return true;
  }

  public static boolean getFalse() {
    System.out.print("F");
    return false;
  }

  public static void main(String[] args) {
    boolean b;

    System.out.println(hasSameFirstTwo("."));

    // Ands
//    b = getTrue() && getTrue();
//    System.out.println();
//    b = getTrue() && getFalse();
//    System.out.println();
//    b = getFalse() && getTrue();
//    System.out.println();
//    b = getFalse() && getFalse();
//    System.out.println();
  }

  public static boolean hasSameFirstTwo(String s) {
    return s.length() >= 2 && s.charAt(0) == s.charAt(1);
  }
}

TrueFalse.java

package lecture1011.cs148;

public class TrueFalse {
  public static boolean getTrue() {
    System.out.print("T");
    return true;
  }

  public static boolean getFalse() {
    System.out.print("F");
    return false;
  }

  public static void main(String[] args) {
    boolean b;

    // Ands
    b = getTrue() && getTrue();
    System.out.println();
    b = getTrue() && getFalse();
    System.out.println();
    b = getFalse() && getTrue();
    System.out.println();
    b = getFalse() && getFalse();
    System.out.println();
  }
}

Short.java

package lecture1011.cs148;

public class Short {
  public static void main(String[] args) {
    System.out.println(hasFirstTwoSamesies("eel"));
    System.out.println(hasFirstTwoSamesies("oops"));
    System.out.println(hasFirstTwoSamesies("llama"));
    System.out.println(hasFirstTwoSamesies("eerily"));
    System.out.println(hasFirstTwoSamesies("ooze"));
    System.out.println(hasFirstTwoSamesies("eek"));
    System.out.println(hasFirstTwoSamesies("cchris"));
    System.out.println(hasFirstTwoSamesies("zebra"));
    System.out.println(hasFirstTwoSamesies("a"));
  }

  public static boolean hasFirstTwoSamesies(String s) {
    return s.length() > 1 && s.charAt(0) == s.charAt(1);
  }
}