10182

Algebraic Problems in Propositional Logic

Problem 1. On the island of Knights and Knaves, knights always tell the truth and knaves always lie. A logician visits the island and meets an inhabitant. The logician wants to know whether there is gold on the island. Is there a statement such that from its truth the logician can infer that gold is on the island and from its negation that there is not? Let mean that the native is a knight, and that there is gold. If the native answers "yes" to the question "Is true?", the logician knows . Is it possible that (i.e. infers )? Simultaneously, this should hold: . So we must find a propositional expression in variables and such that and are both tautologies. This is equivalent to the statement that and are simultaneously inconsistent (unsatisfiable), that is, ) is inconsistent. The DNF (disjunctive normal form) of the last expression is .
Each disjunct in it must be false, so , , , , or equivalently, , , , . So the condition for is
. (Here means and ). In this case, and are equivalent to .
Generally a problem involving the inconsistency of a propositional expression in variables that include the variable has a solution for if each disjunct in the DNF of the expression contains either or and is a tautology, or a contradiction. This is the case when each disjunct of and each disjunct in contains a contradictory pair of literals (for instance, one and the other ). Suppose there is an assignment of variables making true. Then at least one of its disjuncts (say ) is true, so all literals in are true (a literal is an atomic sentence or the negation of an atomic sentence). Since must be false, all its disjuncts must be false. So each of these disjuncts must contain a negation of a literal of .
Problem 2. On the island of Knights, Knaves, and Normals, knights always tell the truth, knaves always lie, and those called normal can either lie or tell the truth. One day a logician met a native who made a statement from which the logician inferred that the native was normal.
Let mean the native is a knight and let mean the native is a knave; then means the native is normal; means that if the native is a knight, the statement is true; means that if the native is a knave, his statement is false; and means that if the native is a knight, he is not a knave.
So we are looking for such that is inconsistent. The problem has four solutions.
Problem 3. There are three natives , , and . One is a knight, one is a knave, and one is normal. Is there a statement such that with the question "Is true?" posed to , a logician can infer:
if the answer is "yes" then is not normal, and if the answer is "no" then is not normal.
We use the following notations:
The conditions of problems are (between and , one is a knight or one is a knave), (if is a knight, then he is not a knave), , , and .
Can we make the following two sets simultaneously inconsistent?
(1) conditions , , ;
(2) conditions , ,

DETAILS

References
[1] R. H. Cowen, "Solving Algebraic Problems in Propositional Logic by Tableau," Archive for Mathematical Logic, 22, 1982 pp. 187–190.
[2] R. Smullyan, The Lady or the Tiger?, New York: Alfred A. Knopf, 1983.

PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.