1

Let us consider for simplicity only Kripke structures with a single agent whose knowledge is described by the modal operator K. We know that in all the corresponding Kripke structures where K is interpreted by equivalence there holds for any formula A

a) the formula KA -> A (Knowledge Axiom) is valid ,
b) but the formulas A -> KA and ¬KA are not valid.

Utilize these facts to show that such a behaviour of the modal operator K cannot be encoded by any boolean function (ie. Truth values defined by a table).

Hint: Suppose the truth value of KA can be calculated from the truth value of A using a truth table for K (in the same way as ¬A is calculated form A). Consider all possible truth tables for K and show that none of them grants the properties a) and b) mentioned above.

I dont understand that hint... making truth table of K is like constructing truth table of negation symbol ¬ , which in my mind doesnt make sense I think it makes sense only to make negation of something and not just negation

duplode
  • 33,731
  • 7
  • 79
  • 150
David
  • 112
  • 1
  • 8
  • 1
    It's quite common to say "truth table of _some logical operation_" as a short-hand for "truth table of the formula applying _some logical operation_ to variables". So the truth table of ¬ is the truth table of ¬p, the truth table of & is the truth table of p & q, etc. – Alexey Romanov May 21 '17 at 07:13
  • thank you, that means this problem is quite easy... for A i have T or F and then I just need to make all possible truth tables for KA ( T T, T F, F T , F F) and evaluate those formulas and I will see that if we were trying encode K as boolean function sometimes KA -> A would be False and not always b) properties would be False – David May 21 '17 at 12:21
  • Yes, that's it. – Alexey Romanov May 21 '17 at 13:00
  • I'm voting to close this question as off-topic because it isn't directly about programming. (It would have been a good fit on either [philosophy.se] or [math.se].) – duplode Jul 15 '19 at 22:07

1 Answers1

2

Consider all possible truth tables for K:

| A | K₁A | K₂A  | K₃A | K₄A |
—————————————————————————————
| 1 |  1  |  1  |  0  |  0  |
—————————————————————————————
| 0 |  1  |  0  |  1  |  0  |

Show that none of them grants the properties a) and b) mentioned above.

Case 1

| A | KA  | KA->A | A->KA | ¬KA |
—————————————————————————————————
| 1 |  1  |   1   |   1   |  0  |
—————————————————————————————————
| 0 |  1  |   0   |   1   |  0  |

In this case, KA->A is not a tautology.

Case 2

| A | KA  | KA->A | A->KA | ¬KA |
—————————————————————————————————
| 1 |  1  |   1   |   1   |  0  |
—————————————————————————————————
| 0 |  0  |   1   |   1   |  1  |

In this case, A->KA is a tautology.

Case 3

| A | KA  | KA->A | A->KA | ¬KA |
—————————————————————————————————
| 1 |  0  |   1   |   0   |  1  |
—————————————————————————————————
| 0 |  1  |   0   |   1   |  0  |

In this case, KA->A is not a tautology.

Case 4

| A | KA  | KA->A | A->KA | ¬KA |
—————————————————————————————————
| 1 |  0  |   1   |   0   |  1  |
—————————————————————————————————
| 0 |  0  |   1   |   1   |  1  |

In this case, ¬KA is a tautology.

Can desired behaviour of K be encoded by many-valued matrix?

For alethic modal systems, the answer is the following:

  • 3 values are insufficient,
  • 4 values are sufficient for the so-called basic modal logic,
  • any finite number of values is insufficient for syntactically “full” and deductively “natural” modal system.

See, e. g., introductory parts in the article by Jean-Yves Beseau.
I hope these results are relevant for epistemic modal systems.

Stanislav Kralin
  • 11,070
  • 4
  • 35
  • 58
  • 1
    Thank you very much, I had this same idea I was just confused a little bit if this is what the problem was about. – David May 21 '17 at 12:38