Unsolved: Goldbach's Conjecture

In 1742, Christian Goldbach, in a letter to Leonhard Euler, conjectured that every odd integer n, n > 5, is the sum of three primes. Euler replied that this conjecture is equivalent to the conjecture that every even integer n, n > 2, is the sum of two primes. The conjecture that every even integer n, n > 2, is the sum of two primes is now called Goldbach's conjecture. We can check this conjecture for small even numbers. For example, 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 7 + 3, 12 = 7 + 5, and so on. Goldbach's conjecture was verified by hand calculations for numbers up to the millions prior to the advent of computers. With computers it can be checked for extremely large numbers. As of early 2006, the conjecture has been checked for all positive even integers up to

Although no proof of Goldbach's conjecture has been found, most mathematicians believe it is true. Several theorems have been proved, using complicated methods from analytic number theory far beyond the scope of this book, establishing results weaker than Goldbach's conjecture. Among these are the result that every even positive integer greater than 2 is the sum of at most six primes (proved in 1995 by O. Ramare) and that every sufficiently large positive integer is the sum of a prime and a number that is either prime or the product of two primes (proved in 1966 by 1. R. Chen). Perhaps Goldbach's conjecture will be settled in the not too distant future.

Logic Puzzle: Who is the knave?

Problem:

In [Sm78] Smullyan posed many puzzles about an island that has two kinds of inhabitants, Extra ­ knights, who always ­ell the truth, and their opposites, knaves, who always lie. You encounter ­ two people A and B. What are A and B if A says "B is a knight" and B says "The two of us are opposite types"? ­

Solution:

Let p and q be the statements that A is a knight and B is a knight, respectively, so that -p and -q are the statements that A is. a knave and that B is a knave, respectively.

We first consider the possibility that A is a knight; this is the statement that p is true. If A is a knight, then he is telling the truth when he says that B is a knight, so that q is true, and A and B are the same type. However, if B is a knight, then B's statement that A and B are of opposite types, the statement (p & -q) V (-p & q), would have to be true, which it is not, because A and B are both knights. Consequently, we can conclude that A is not a knight, that is, that p is false.

If A is a knave, then because everything a knave says is false, A's statement that B is a knight, that is, that q is true, is a lie, which means that q is false and B is also a knave. Furthermore, if B is a knave, then B's statement that A and B are opposite types is a lie, which is consistent with both A and B being knaves. We can conclude that both A and B are knaves.

Problem: System Specifications Consistency

Problem:

Determine whether these system specifications are consistent:
­"The diagnostic message is stored in the buffer or it is retransmitted."
"The diagnostic message is not stored in the buffer."
"If the diagnostic message is stored in the buffer, then it is retransmitted."

­

Solution:

To determine whether these specifications are consistent, we first express them using logical expressions. Let p denote "The diagnostic message is stored in the buffer" and let q denote "The diagnostic message is retransmitted." The specifications can then be written as p v q, -,p, and p -* q. An assignment of truth values that makes all three specifications true must have p false to make -'p true. Because we want p v q to be true but p must be false, q must be true. Because p -* q is true when p is false and q is true, we conclude that these specifications are consistent because they are all true when p is false and q is true. We could come to the same conclusion by use of a truth table to examine the four possible assignments of truth values to p and q . ­