De Morgan's Laws in Action

Augustus De Morgan, originally uploaded by Mike Lynch.

Logic: It's a beautiful thing. It's not everyday, however, that I get to implement it so explicitly as I did today.

One of the hallmarks of mathematical logic are some rules set out by Augustus De Morgan called, appropriately, De Morgan's Laws. They go something like this: Take two (or more) statements A and B. These can be things like "The sky is blue" and "We are on Earth." These statements have complements, namely, "The sky is not blue" and "We are not on Earth."

De Morgan gives an equivalence between the relation of these statements' complements and the complement of the relation of these statements. In (better) English, we could say that the complement of A and B is the complement of A or the complement of B. So, in our example, De Morgan tells us that the complement of "The sky is blue AND we are on Earth" is the same thing as saying "The sky is not blue OR we are not on Earth." Confused? Try out the formal statements for a bit of clarification:

where we read "c" as complement,

and

Why would this ever arise in practice, you might ask? In fact, just today I wanted to add a stopping condition to a WHILE loop I had in a program. A WHILE loop runs (loops) for as long as a given statement is true. My loop ran for as long as the variable called FLAG was true. Essentially, I wanted to cheat a little and add a different stopping criterion that would bounce out of the loop if a different variable hadn't been changing for a while.

So in my head, the loop should run while FLAG was true, and it should stop when COUNTER was bigger than 20 and W(COUNTER)==W(COUNTER-20). But, just my luck, you can't really tell a WHILE loop when not to run, you have to tell it when it has to run. But guess, what? These conditions are complements! Enter De Morgan.

My situation was that I want to stop the loop when

is true. Which means that I want to NOT stop (i.e. run) when

is true.

Bonus! We get to use both flavors of De Morgan. First apply the first equation from up top, then apply the second to the B parentheses. After all is said and complemented, I want to run my WHILE loop while FLAG is true AND (COUNTER is less than 20 OR W(COUNTER)~=W(COUNTER-20)). Cool huh?

Stay Logical.

How to Peek Around a Corner - Part 1

around the corner,, originally uploaded by ~Faiz.

Occasionally in my reading, I come across a particularly well-posed question that I feel is not only accessible to "lay" readers but also interesting to them. The problem of how to best look (or "peek") around a corner is just one of these questions.

As a warning, I will pose the question in this post and then solicit ideas and answers from the readers. Then next week I'll post a solution and hopefully an example.



First, the setting: You are Bruce Willis in Die Hard. You are pursuing and being pursued by bloodthirsty terrorists in a strange office building. You find yourself walking in a smoky room with your hand against a wall in order to not get lost. All of a sudden, you notice that your wall comes to an end exactly one meter in front of you. You pause and analyze how to best approach this corner in the wall in order to be able to see down the adjoining wall.





If you knew the angle that the adjoining wall intersected your wall (and this angle was acute), the quickest path would be one that departed the wall you were following at an angle of
90-\phi and traveled in a straight line for \sin\phi meters. This would take you directly to the "extension" of the line of the adjoining wall and would afford you an unobstructed view down that wall. Conversely, if the angle is obtuse, it would be quickest to just go directly along the wall to the corner. This concept is illustrated in the figure below (courtesy R. Dorrigiv and A. Lopez-Ortiz):




The tension between these two approaches (curl out into the room versus proceed directly to the corner) represent the crux of this path-planning problem.

Let me finally pose the question: Starting from one unit "south" of a corner with unknown acute angle (between 0 and 90 degrees, inclusive), what is the best approach path, and what does "best" mean to you?

A solution---and my take on it---coming soon.