Infinitesimal Logic

I don’t know if infinitesimal logic is the best idea I’ve ever had, but it’s definitely the best name.

So here’s the idea: a multivalued logic in which there are truth values that are not nearly as true as ‘standard’ truth, and others that are not nearly as false as ‘standard’ falsity.

An example should help. Suppose  you go to the travel agent and ask if if you can get a flight (1) to Ottawa and (2) in an aisle seat. If the agent says “yes” (meaning true in the standard sense), you’re done. However, if the agent says “no” (meaning false in the standard sense) you don’t know where you stand – maybe there is no flight to Ottawa, or maybe you just can’t get an aisle seat. You can always ask another question, but it would have been more helpful if the agent had given you some indication of the difficulty of flying to Ottawa in an aisle seat.

Here’s where infinitesimal logic can help. In addition to the standard value F (false), there is also the extra value εF, which you can think of as being not nearly as false as F. The agent’s system could return εF if you can get to Ottawa, but not in an aisle seat; and return F if you can’t get to Ottawa at all.

This convention encodes a priority: you must get to Ottawa but you merely prefer to travel in an aisle seat. Of course, you can’t expect the agent’s database query software to know your preferences. Your query must make this explicit. With infinitesimal logic you can use a nonstandard, preferential conjunction that I call “and, if possible”. So the query could be

Dest='Ottawa' and-if-possible SeatType='aisle'

Clearly (omitting details) if you had an even less false value ε2F, you could have two levels of preference, so for example by requesting an aisle seat on the right of the aircraft. When your query is submitted, you may get several answers, in which case you choose one with the least false value (assuming there is one whose value is not F). My Masters student Ruchi Agarwal for her thesis implemented a prototype movie database using a formalization of infinitesimal with preferential conjunction and disjunction.

So why is this logic called “infinitesimal” (ε often in math being an arbitrarily small quantity)? Because, in terms of the example above, requirements are usually infinitely more important than preferences. You can imagine the agent offering you a flight with an aisle seat on the right hand side where you will be served pink champagne in a crystal glass. Only one problem: the flight is going to Saskatoon. You would reject this offer, because to you no amount of pink champagne can compensate for flying to Saskatoon (or anywhere other than Ottawa).

Infinitesimal logic was originally developed by me and my former PhD student P. Rondogiannis to give a model theory for pure Prolog with negation – but I’ll save that for a later post.

Advertisements

About Bill Wadge

I am a Professor in Computer Science at UVic.
This entry was posted in research. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s