WOLFRAM|DEMONSTRATIONS PROJECT

Algebraic Problems in Propositional Logic

​
choose problem
1
2
3
show DNF
disjuncts as lists
implies x
implied by x
does solution exist?
joint condition
((t⧦x)∧¬g)∨((x⧦¬t)∧g)
(g∧t∧¬x)∨(g∧x∧¬t)∨(t∧x∧¬g)∨(¬g∧¬t∧¬x)
g
t
¬x
g
x
¬t
t
x
¬g
¬g
¬t
¬x
(g∧t)∨(¬g∧¬t)
(¬g∨t)∧(¬t∨g)
True
(g∧t)∨(¬g∧¬t)  x  (¬g∨t)∧(¬t∨g)
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
x
such that from its truth the logician can infer that gold is on the island and from its negation that there is not? Let
t
mean that the native is a knight, and
g
that there is gold. If the native answers "yes" to the question "Is
x
true?", the logician knows
t⇔x
. Is it possible that
t⇔x⊢g
(i.e.
t⇔x
infers
g
)? Simultaneously, this should hold:
t⇔¬x⊢¬g
. So we must find a propositional expression in variables
t
and
g
such that
(t⇔x)g
and
(t⇔¬x)¬g
are both tautologies. This is equivalent to the statement that
(t⇔x)∧¬g
and
(t⇔¬x)∧g
are simultaneously inconsistent (unsatisfiable), that is,
((t⇔x)∧¬g)∨((t⇔¬x)∧g
) is inconsistent. The DNF (disjunctive normal form) of the last expression is
(g∧t∧¬x)∨(g∧x∧¬t)∨(t∧x∧¬g)∨(¬g∧¬t∧¬x)
.
Each disjunct in it must be false, so
¬x(¬g∨¬t)
,
x(¬g∨t)
,
x(g∨¬t)
,
¬x(g∨t)
, or equivalently,
(g∧t)x
,
x(¬g∨t)
,
x(g∨¬t)
,
(¬g∧¬t)x
. So the condition for
x
is
(g∧t)∨(¬g∧¬t)x(¬g∨t)∧(g∨¬t)
. (Here
AxB
means
Ax
and
xB
). In this case,
A
and
B
are equivalent to
g⇔t
.
Generally a problem involving the inconsistency of a propositional expression in variables that include the variable
x
has a solution for
x
if each disjunct in the DNF of the expression contains either
x
or
¬x
and
AB
is a tautology, or
A∧¬B
a contradiction. This is the case when each disjunct of
¬B
and each disjunct in
A
contains a contradictory pair of literals (for instance, one
t
and the other
¬t
). Suppose there is an assignment of variables making
A
true. Then at least one of its disjuncts (say
C
) is true, so all literals in
C
are true (a literal is an atomic sentence or the negation of an atomic sentence). Since
¬B
must be false, all its disjuncts must be false. So each of these disjuncts must contain a negation of a literal of
C
.
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
x
from which the logician inferred that the native was normal.
Let
t
mean the native is a knight and let
f
mean the native is a knave; then
¬t∧¬f
means the native is normal;
tx
means that if the native is a knight, the statement
x
is true;
f¬x
means that if the native is a knave, his statement is false; and
t¬f
means that if the native is a knight, he is not a knave.
So we are looking for
x
such that
(t¬f)∧(tx)∧(f¬x)∧(t∨f)
is inconsistent. The problem has four solutions.
Problem 3. There are three natives
A
,
B
, and
C
. One is a knight, one is a knave, and one is normal. Is there a statement
x
such that with the question "Is
x
true?" posed to
A
, a logician can infer:
if the answer is "yes" then
B
is not normal, and if the answer is "no" then
C
is not normal.
We use the following notations:
knight
knave
normal
A
a
b
¬a∧¬b
B
c
d
¬c∧¬d
C
¬a∧¬c
¬b∧¬c
(a∨b)∧(c∨d)
The conditions of problems are
a∨b∨c∨d
(between
A
and
B
, one is a knight or one is a knave),
a¬b
(if
A
is a knight, then he is not a knave),
a¬c
,
b¬d
, and
c¬d
.
Can we make the following two sets simultaneously inconsistent?
(1) conditions
ax
,
b¬x
,
¬c∧¬d
;
(2) conditions
a¬x
,
bx
,
(a∨b)∧(c∨d)