Answer to Question #155078 in Discrete Mathematics for Tanveer shahzad

Question

A town has two type of people Knave always speak lie and knative always speak truth, you meet a group of six people A, B, C, D, E and F they communicate with you as following,

A Said: All are the knative .

B Said: Atleast three are knative 

C Said: A, B are knaves 

D Said: All are Knaves except me

E Said: A, C are knaves

Answer 1

Let's introduce boolean variables A, B, C, D, E and F, which return true , if the corresponding people is knative, and else return false.

Let's write down the logical propositions we have from the given statesments.

The sentence "A Said: All are the knative." is equivalent to the formula A = A & B & C & D & E & F (i.e. if the formula on the right side is true, then the man A says truth, and the variable A returns 'true' and vice versa.)

The sentence "D Said: All are Knaves except me" is equivalent to the formula D = ¬A & ¬B & ¬C & D & ¬E & ¬F. Multiplying these two formulas, we have A & D = (A & B & C & D & E & F) & (¬A & ¬B & ¬C & D & ¬E & ¬F) = false. Thus, A = (A & D) & (C & B & E & F) = false.

The sentence "C Said: A, B are knaves" is equivalent to the formula

C = ¬A & ¬B.

As A = 0, we have C = ¬(false) & ¬B = ¬B.

Also we have D = (¬A & ¬B) & ¬C & (D & ¬E & ¬F) = C & ¬C & (D & ¬E & ¬F) = false.

The sentence "E Said: A, C are knaves" is equivalent to the formula

E = ¬A & ¬C.

Therefore, E = ¬(false) & ¬(¬B) = B.

If B = true, then C = ¬B = false, E = B = true, the number of knatives must be at least 3, and hence, F = true.

If B = false, then C = ¬B = true, E = B =false, and the number of knatives will be at most 2 regardless of F.

So, we have three variants:

1) A, C, D are Knaves and B, E, F are Knatives.

2) A, B, D, E, F are Knaves, and C is a Knative.

3) A, B, D, E are Knaves, and C, F are Knatives.