(Last modified Thu May 22 15:27 2008)

For questions A and B, I suggest you write each pair of letters in a Cartesian product as simply the two letters, rather than as an ordered pair.  For example, write Un rather than (U,n).  It will be unambiguous because each element is a single letter. 

1. Here are two groups of elevator states:  U = "moving up", S = "stopped at a floor", and D = "moving down";  and n = "doors opening", o = "doors open", b = "doors closing" and c = "doors closed".  Assume that a particular elevator at a particular time is described by exactly one of U, S, or D, and exactly one of n, o, b, or c. 
   1. 4 pts • What does the Cartesian product {U,S,D}×{n,o,b,c} describe? 
   2. 6 pts • How big is this product?  • Enumerate its elements. 
   3. 6 pts • Enumerate the subset of this product that describe acceptable states of a properly-working elevator.  • Briefly (one sentence) explain for each acceptable state why it is acceptable.  You may wish to explain what desired activities happen during the state, or what goals are being achieved.  You can use the same explanation for more than one state. 
2. Now assume the letters U, S, D, n, o, b, c are logical propositions that can be true or false (about a particular elevator):  for example, U now stands for "The elevator is moving up", and o for "The elevator's doors are open".  As in question A, assume that a particular elevator at a particular time is described by exactly one of U, S, or D, and exactly one of n, o, b, or c;  thus, U∨S∨D is true and U∧S, U∧D, and S∧D are false, and n∨o∨b∨c is true and n∧o, n∧b, n∧c, o∧b, o∧c, and b∧c are false. 
   1. 6 pts • Write a PL expression that is true for all acceptable states of the elevator, and false otherwise.  Use ¬, ∧, and ∨ and produce something like ¬U∨o∧D∨(¬S∨n) (that isn't the answer, by the way).  • Show that it produces the correct value for each possible state (acceptable and unacceptable both).  Hint:  it is possible to make the expression very brief (fewer than 5 symbols total). 
   2. 4 pts • Write a PL expression that is true for all unacceptable states of the elevator.  • Briefly explain why it produces the correct values (preferably one explanation that compares it to your expression in the previous question, rather than an explanation for each possible state). 
   3. Consider the PL sentence ¬U∨o∧D.  This is equivalent to (¬U)∨(o∧D), of course. 

      If this sentence is true, what can we say about each of the following sentences — • is each one true, false, or "could be either"?  • How can you tell? 

      Note that ¬U∨o∧D does not describe an acceptable elevator (clearly!), so you can't argue from what an elevator should do;  instead, what can you infer only from knowing ¬U∨o∧D is true, and from knowing that an elevator either is going up, or down, or is stopped at a floor (we still assume these are the only possibilities) and its doors are either opening, open, closing, or closed?  You may wish to produce a truth table showing ¬U∨o∧D (and ¬U∨D) for every combination of values for U, o, and D, and think about what you can conclude from it. 

      1. 4 pts U
      2. 4 pts o
      3. 4 pts ¬U∨D
3. Now assume the letters describe actions the elevator can take:  U now stands for "The elevator moves up", S for "The elevator stops at a floor", n for "The elevator doors are opening", o for "The elevator doors become completely open", and so forth. 
   1. 4 pts • Write a sequence of the letters that expresses a scenario for the elevator's desired activities.  Assume that your scenario begins with the elevator stopped with doors closed.  End your scenario with any actions needed to have the elevator stopped with closed doors too.  Make your sequence no shorter than 6 letters and no longer than 12.  For example, "UnobDcS" is such a scenario (not a very good one, by the way).  • Also describe in words what your scenario expresses. 
   2. 4 pts • Why isn't "UoSnDc" a good scenario?  • What does it describe? 
   3. 6 pts • Write a Perl regular expression that describes all acceptable scenarios that begin and end with the elevator stopped with its doors closed.  Assume that an elevator that never does anything else (that is, the empty string) is correct although boring.  • Explain why your regular expression is correct.  • Show how it matches your scenario from C.1., and • give another scenario (6 to 12 letters) it matches and • explain how. 
4. Now assume a world in which there are elevators named α, β, γ, ... and floors named 1, 2, 3, .... The set of all elevators is E and the set of all floors is F.  (The elevators and floors are all in the same building.)  The letters are now predicates:  U(α) means α is moving up, S(α, 2) means α is stopped at 2, D(α) means α is moving down; n(α) means α's doors are opening, etc.  Consider the state of the elevators at a specific instant in time.  As in questions A and B, assume that a particular elevator at a particular time is described by exactly one of U, S, or D, and exactly one of n, o, b, or c;  thus, U∨S∨D is true and n∨o∨b∨c is true. 
   1. 4 pts Consider the sentence ∃e∈E U(e).  • What does it mean, in words?  • Is this sentence true, false, or "could be either"?  • Why? 
   2. 4 pts Consider the sentence ∀f∈F ∃e∈E S(e,f).  This is the same as ∀f∈F (∃e∈E S(e,f)), of course.  • What does it mean, in words?  • Is this sentence true, false, or "could be either"?  • Why?  • Does it depend on the number of floors and elevators? 
   3. 4 pts Consider the sentence ∀e∈E (U(e)∨S(e)∨D(e)).  • What does it mean, in words?  • Is this sentence true, false, or "could be either"?  • Why? 

Thomas A. Alspaugh
Assistant Professor, Informatics Dept.
School of Information and Computer Sciences