## Calypso Module 13: LogicLearning 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.
## IntroductionThis 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 calledpropositional 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 LogicIn 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 AttributesTo 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 WHENThe 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
## Negating the Head Tile Negates the Entire PropositionWhen 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.
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 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 DisjunctionsIn logic, the AND connective expresses aconjunction 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 LogicPredicates 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:
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 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 StatementNegating 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.
"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' TileNot 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 RuleIf 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
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 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 ModuleIn the
Back to Calypso Curriculum overview.
Copyright © 2020 Visionary Machines LLC. |