Calypso Module 14: Logic

Learning Goal: This module examines the relationship between Calypso rules and formal logic. You will learn how the logical operations AND, OR, and NOT, and the existential quantifier "there exists" are realized in Calypso.

Introduction

This module examines the relationship between Calypso rules and formal logic. Logic is a branch of Philosophy but also an important topic in computing. We're going to use a bit of technical terminology to make connections between Calypso and two flavors of logic called propositional logic and predicate logic. But if this theoretical material is not of interest, you can focus on just the programming aspect. The logical operations we'll be discussing are a useful way to think about and construct Calypso programs.

Propositional Logic

In logic, a proposition is a statement that is either true or false. The WHEN half of a rule can express a proposition, and if the proposition is true, the rule will fire. For example:

The rule fragment "WHEN see cube1" corresponds to the proposition "cube1 is visible in the world map."

Likewise, "WHEN see cube1 red" corresponds to the proposition "cube1 is visible in the world map AND cube1 is glowing red". To keep things from getting too verbose, we will sometimes just assume that cubes are visible in the world map.

More complex logical statements can be constructed in several ways. For example:

"WHEN see cube1 red sideways" corresponds to the statement "cube1 is glowing red AND cube1 is oriented sideways". (We've left out the part about cube1 being visible in the world map just for brevity.)

A Calypso rule can only refer to a single object, so propositions that reference multiple objects can't be collapsed into a single rule. Instead we write two rules, one indented underneath the other. The parent rule has an empty DO part, and because of the indentation, the child rule can only run if both the parent and child rule's WHEN parts are true. (This is a consequence of the Fourth Law of Calypso.) For example, the proposition "cube1 is glowing red and cube2 is glowing green" would be written with this two-rule structure:

If cube1 is glowing red, the indented rule can run, and if cube2 is glowing green, the indented rule's action can run, playing the "beeprobo" sound.

Negative Attributes

To express a negative attribute in Calypso we use something called a "NOT decorator". For example, to say that cube1 is not red we would use a "NOT-red" tile:

There are two ways to attach a NOT decorator to a tile. The first way is to select "NOT" from the menu and then select the tile to decorate, such as "red". The second way is to put the pencil on an existing tile and press the Y button. This toggles the NOT decorator, turning "red" into "NOT-red" or "NOT-red" into "red".

"WHEN see cube1 NOT-red" will be true if cube1 is visible in the world map ("see cube1" is true) AND cube1 is not glowing red. If cube1 is not visible in the world map, e.g., it's in the dock or not present at all, then "see cube1" will be false, so "see cube1 NOT-red" will also be false, whether or not the cube is glowing red.

The Head Tile of a WHEN

The head (i.e. first) tile in the WHEN part of a rule is special because it describes a relation that is true in the world or an event that occurred in the world. For example, "see" means "is visible in the world map", "bumped" means an "is close by in the world map", "got" means "character is holding", "hear" refers to a speech event, and "feel" refers to a cube tap event. The remaining tiles in the WHEN only specify properties of the object itself, such as "red" or "inverted".

Negating the head tile means the relationship does not hold in the world, or the described event did not occur during this time step. So "WHEN NOT-see cube1" will be true if cube1 is not currently visible in the world map. In other words, it will be false if cube1 is visible in the world map.

Negating the Head Tile Negates the Entire Proposition

When the NOT decorator is attached to the head tile of the WHEN part, such as the "see" tile above, it doesn't just negate the "see": it negates the entire entire proposition. So "WHEN NOT-see cube1 red" is interpreted as "NOT (see cube1 AND cube1 is red)". It will be false if we see cube1 AND cube1 is glowing red.

Sidebar: DeMorgan's Laws for Connectives

"WHEN NOT-see cube1 red", which means "NOT (see cube1 AND cube1 is glowing red)", will be true if either (we do NOT see cube1) OR (cube1 is NOT glowing red). Notice the change from AND to OR when we moved the NOT from outside the parentheses to inside. This is an instance of DeMorgan's Laws, which state the relationship between the AND and OR connectives with respect to NOT:

NOT(a AND b) is the same as NOT(a) OR NOT(b) NOT(a OR b) is the same as NOT(a) AND NOT(b)or alternatively:a AND b is the same as NOT(NOT(a) OR NOT(b)) a OR b is the same as NOT(NOT(a) AND NOT(b))

Specifically, "NOT (we see cube1 AND it is glowing red)" fits the pattern NOT(a AND b), while "(we do NOT see cube1) OR (cube1 is NOT glowing red)" fits the pattern NOT(a) OR NOT(b). DeMorgan's Laws tell us that these are equivalent.

What about more complex propositions? "WHEN NOT-see cube1 red sideways" will be false if we see cube1 AND it's glowing red AND it's oriented sideways. Conversely, the proposition will be true if we don't see cube1 at all, OR if it's not glowing red, OR if it's not oriented sideways.

Now consider the English expression "cube1 is not red or green". This enumerative "or" is a different use of the word than the logical OR that appears in DeMorgan's Laws. It actually expresses the statement "cube1 is not red AND cube1 is not green". We cannot combine two color attributes in a single WHEN, but we can use a nested rule to represent the statement. If we want to play a sound whenever we see cube1 and it is neither red nor green, we can write:

If cube1 is red then the first WHEN will be false, and if it's green the second WHEN will be false. But if cube1 is purple both WHEN's will be true and we will play a sound.

We can combine negation of the main predicate with negation of attributes to make even more complex statements. For example:

The WHEN part will be true as long as we don't see cube1 glowing non-red. So it will be true if we don't see cube1 at all, and it will also be true if we see cube1 but it is glowing red, because that means we don't see it glowing non-red. But it will be false if we see cube1 and it's glowing purple.

Conjunctions and Disjunctions

In logic, the AND connective expresses a conjunction of two conditions: both must be true in order for the AND to be true. The OR connective expresses a disjunction: if either condition is true (or if both are true), the disjunction is true.

While a conjunction can be represented using indented rules, there is no explicit representation in Calypso for a disjunction. Instead, each condition is simply encoded as a separate rule. So for an instruction such as "play a sound whenever cube1 is red OR cube1 is green", the two halves of the disjunction would each need their own rule:

What about negating a disjunction? Suppose we want to play a sound when it's not the case that cube1 is red or inverted. In logic this would be written "NOT(cube1 is red OR cube1 is inverted)". There is no direct representation for negated disjunctions in Calypso, but we can use DeMorgan's Laws to rewrite this expression, bringing the NOT inside the parentheses and changing the disjunction to a conjunction, i.e., changing the connective from OR to AND. This gives (cube1 is NOT-red) AND (cube1 is NOT-inverted), which can be written as this rule:

Let's try one more example. Now we want to add one to the yellow score when it is not the case that cube1 is red AND cube2 is green. In logic this is written "NOT(cube1 is red and cube2 is green)". We use DeMorgan's Laws to rewrite this as "cube1 is NOT-red OR cube2 is NOT-green". Now we have a disjunction, so we split it into two rules, giving this almost correct solution:

There's a subtle problem with the solution above: suppose that cube1 is not red and also cube2 is not green. Then we would perform the "+score" action twice, which was not our intent. The problem stems from the fact that an OR expression, which is true if either disjunct is true, is also true if both disjuncts are true. So when we split it into two simpler expressions, we replicate the action. To guard against taking the action twice, we should only initiate the second +score action if we know that the first action was not taken. We can express this as:

Predicate Logic

Predicates are functions that are true for some inputs and false for others. If we apply a predicate to a particular input, the result is essentially a proposition, e.g., the predicate expression "red(cube1)" is equivalent to the proposition "cube1 is glowing red". But it's also possible to apply a predicate to a variable, such as red(x), in which case the truth of the predicate depends on our choice of value for x. So red(x) might be true if we choose x equal to cube1, and false if we choose x equal to cube2.

Predicate logic provides two quantifiers for specifying the choice of values for x: the universal quantifier "for all" and the existential quantifier "there exists".

Variables in Calypso are always existentially quantified. For example, "WHEN see cube" is equivalent to "there exists an x such that x is seen in the world map and x is a cube". In logic notation this would be written:

Exists x: see(x) AND cube(x)

where "Exists x" means "there exists an x such that..."

This highlights an important difference between the "cube1" and "cube" tiles: "cube1" denotes a specific object, while "cube" denotes a predicate cube(x) that is true for objects that are cubes and false for other types of objects.

If we do see a cube in the world map, then we can choose it as the value for x in order to make cube(x) true.

Going further: "WHEN see cube red" is equivalent to "there exists an x such that see(x) AND cube(x) AND red(x)". The statement will be true if we can find at least one red cube. If there are multiple red cubes, the First Law of Calypso tells us to pick the closest one. If there are other cubes even closer, we will not pick them if they are not red.

Negating an attribute is still straightforward with existential quantification. "WHEN see cube NOT-red" will be true if we see at least one cube that is not red. It will be false if we don't see any cubes at all, or if all the cubes we see are red so there are no non-red ones.

Negating a Quantified Statement

Negating an entire quantified statement is a little trickier than negating an attribute. "WHEN NOT-see cube red" is only true if none of the cubes we see are red.

If no cubes are visible then the rule above is trivially satisfied. Otherwise we try to find a cube for which "see cube red" is true, and if we do find one, the negated statement is false. In other words, ALL the cubes we do see must be non-red in order for the "NOT-see cube red" to be true. This illustrates another form of DeMorgan's Laws.

Sidebar: DeMorgan's Laws for Quantifiers

The relationship between existential and universal quantifiers with respect to negation is similar in form to DeMorgan's Laws for connectives.

NOT (Exists x: p(x)) is the same as All x: NOT p(x) NOT (All x: p(x)) is the same as Exists x: NOT p(x)or equivalently:All x: p(x) is the same as NOT (Exists x: NOT p(x)) Exists x: p(x) is the same as NOT (All x: NOT p(x))

"All cubes are red" cannot be expressed directly in Calypso because Calypso lacks a universal quantifier. Instead we use DeMorgan's Laws to restate the universally quantified statement as an existentially quantified one: "all cubes are red" becomes "there does not exist any non-red cube". In Calypso this is written "NOT-see cube NOT-red".

In general, the way we handle a negated statement such as "NOT-see cube red" is by trying to find a value for x that makes the positive statement true. If we do find one, then the negated statement is false. Only if we fail to find a value for x that makes the positive statement true will we conclude that the negated statement is true.

In other words, "WHEN NOT-see cube red" is true only when we see no red cubes at all. If we see any red cubes then the WHEN is false; it doesn't matter if we also see a non-red cube.

If we instead wanted the rule to fire whenever we see a non-red cube, we would have written "WHEN see cube NOT-red".

The 'It' Tile

Not all predicates are existentially quantified. For example, "WHEN timer 2 seconds" or "WHEN scored red-score ≥ 5" make no reference to any objects in the world. The existentially quantified predicates are "see", "hear", "feel", "bumped", and "got". In order for one of these predicates to be true there must be some object that makes it true. When we use one of these predicates in the WHEN part of a rule, we can refer to that object in the DO part of the rule using the "it" tile. So, for example, when this rule fires:

the existentially quantified variable x will refer to some cube for which "see(x) AND cube(x)" is true, and in the DO half of the rule, the "it" tile will reference that cube.

An important difference between positive and negative predicates is that only positive predicates generate a value for "it". Thus, you cannot say:

because a negated predicate is true only when there is no value for x that will make the positive predicate true. Therefore there will be no value for "it" to reference.

Using "It" in the WHEN Part of an Indented Rule

If a rule establishes a value for "it", we can reference that value in the WHEN part of the child (indented) rules below it. For example, suppose we want to play a sound if the closest cube is red. "WHEN see cube red" would find the closest red cube, which may not be the closest cube. We have to find the closest cube first, which we can do thanks to the First Law, and then check whether that cube is red:

Here's another example. Suppose we want to play a sound when we see a cube inverted, and add one to the red score if that same cube is also red. We could write:

If there are two inverted cubes, the parent rule will pick the closest one, and that is the cube that the child (indented) rule will check for redness. If this cube is not red the indented rule will not run, even if there is some other inverted cube out there that is red. This is because the indented rule's "it" specifically references the cube found by its parent.

We can only use "it" in the WHEN part of a rule if the rule is indented and has a parent with a WHEN part that supplies a value for "it". If the parent doesn't supply this value, we will look to the parent's parent, and so on. If no parent supplies a value for "it", the "it" tile in the WHEN part will be marked as an error and highlighted in red.

Negated "It"

A negated "it" tile in the WHEN part of an indented rule can be used to force a different variable value than the value chosen by the parent rule. Consider the rules below:

The first rule will make "it" refer to the closest visible cube. The second rule, because of the NOT-it tile in the WHEN half, will choose the closest visible cube that is not the same as the first cube, i.e., the next closest visible cube. The use of "it" in the DO half of the chid rule has a different meaning than the "it" in the WHEN half of the parent. In the child rule's DO, "it" refers to the variable established by the child rule's WHEN half. Think of the parent rule as establishing a variable x₁ and the child rule, which references x₁ in its WHEN part, establising a separate variable x₂ that is referenced in its DO part. So these two rules together will glow the closest cube red and the next closest cube green.

Note that there is no way to extend this to associate a third rule's "it" with the third cube because we have no way to refer simultaneously to the first rule's "NOT-it" (the variable x₁) and the second rule's "NOT-it" (the variable x₂). In theoretical terms, we can say that this difficulty stems from Calypso's use of a non-standard version of predicate logic where there is only one variable name ("it"). In conventional predicate logic there are an infinite number of variable names available, such as x, y, z₁, z₂, etc., and we can use as many names as we like.

There is, however, a solution to the tricky problem of coloring the three cubes such that the closest is red, the next closest is green, and the farthest is blue, no matter what their initial colors might be. The solution relies on the Fifth Law of Calypso and requires a total of four rules, not three. See if you can work it out. To view the solution, click here.

Next Module

In the next module you'll learn ...

Back to Calypso Curriculum overview.