Propositional Logic and a Liar Problem

To view the notebooks you'll need the LiveMath plug-in, found at
http://www.livemath.com/plugin/

The letters p and q, below, stand for statements which are true (T) or false (F), e.g, "1+1=2", "the moon is made of green cheese", etc.).

From these two elementary statements, compound statements can be constructed using five truth functions: not, and, or, ifthen, and iff. The latter is read "if and only if".

Here are the English translations of expressions using these functions and propositions.

ifthen(p, q): " p implies q", or "if p then q";

iff(p, q): "p if and only if q", or "p is logically equivalent to q";

or(p, q): "p or q";

and(p, q): "p and q";

not(p): "it is not the case that p".

Rather than saying "It is not the case that the moon is made of green cheese" we usually say "The moon is not made of green cheese". With the exception of not, which takes a single statement's truth value as input, the four other truth functions require two statements' truth values as inputs. In every case the output is either T or F. Truth tables are the "graphs" of these functions, i.e., a complete display of the output values associated with all possible input values. The truth tables for not and and are shown, below. Follow the instructions to see the truth tables of the other truth functions. Then scroll down and solve a Liar Problem.

A Liar Problem based on the puzzles of Raymond Smullyan . You wake up dazed and lost in the badlands, in front of a sign naming a town called "Saints and Sinners" (population 31). As you struggle forward another sign explains that this town has only two types of inhabitants, Saints who always tell the truth and Sinners who always lie. When you arrive, you find that the residents look completely normal, but you need to get out. With mountains to the north and south, there are only two other directions which possibly lead to safety - or certain death in the desert. Which single question, answerable by yes or no, can you ask any inhabitant that will give you the best chance of getting to safety? This is not an easy problem! Perhaps it would be better to read ahead and then return here. A solution is given in the truth tables, below, when you're can decipher them.