Knowledge Representation with Non-Classical Logic

• Modal logics
  • Narrowly construed, modal logic studies reasoning that involves the use of the expressions "necessarily" and "possibly". However, the term "modal logic" is used more broadly to cover a family of logics with similar rules and a variety of different symbols.
  • A list describing the best known of these logics follows.

    Logic	Symbols	Expressions Symbolized
    Modal Logic	□	It is necessary that ...
    	◊	It is possible that ...
    Deontic Logic	O	It is obligatory that ...
    	P	It is permitted that ...
    	F	It is forbidden that ...
    Temporal Logic	G	It will always be the case that ...
    	F	It will be the case that ...
    	H	It has always been the case that ...
    	P	It was the case that ...
    Epistemic Logic	KA	A knows that ...
    	EG	Every A ∈ G knows that ...
    	CG	It is common knowledge in G that ...

• Standard Modal Logic

  The most familiar logics in the modal family are constructed from a weak logic called K (after Saul Kripke). Under the narrow reading, modal logic concerns necessity and possibility. A variety of different systems may be developed for such logics using K as a foundation.

  • The symbols of K extend propositional logic with
    • □ for the modal operator "it is necessary that".
    • ◊ for "it is possible that"
    • ◊ can be defined from □ by ◊A = ~□~A.
  • K results from propositional logic ...
    • Modus Ponens
    • Uniform substitution
    • An axiomatic basis, e.g., ...
      (P|P) => P
      Q => (P|Q)
      (P|Q) => (Q|P)
      (Q=>R) => (P|Q)=>(P|R)
      
    ... and then adding the following ...
    • Distribution axiom K: □(A=>B) => (□A=>□B).
    • Necessitation Rule: From A infer □A. (Note: This is not the same as A => □A. Inference requires A to valid, while implication requires only that A is true.)
    • Example
  • The system K is too weak to provide an adequate account of necessity. The following axiom is not provable in K, but it is clearly desirable.
    • (M) □A=>A
    • Modal logic M results from adding (M) to K
    • Example
  • Many logicians believe that M is still too weak to correctly formalize the logic of necessity and possibility. They recommend further axioms to govern the iteration, or repetition of modal operators.
    • (4) □A=>□□A
    • S4 is the system that results from adding (4) to M
    • In S4, □□...□ = □ and ◊◊...◊ = ◊. This amounts to the idea that iteration of the modal operators is superfluous. Saying that A is necessarily necessary is considered a uselessly long-winded way of saying that A is necessary.
    • (5) ◊A=>□◊A
    • S5 is the system that results from adding (5) to M
    • In S5, 00...□ = □ and 00...◊ = ◊, where each 0 is either □ or ◊ This amounts to the idea that strings containing both boxes and diamonds are equivalent to the last operator in the sequence. Saying that it is possible that A is necessary is the same as saying that A is necessary.
  • One could engage in endless argument over the correctness or incorrectness of these and other iteration principles for □ and ◊. The controversy can be partly resolved by recognizing that the words "necessarily" and "possibly", have many different uses. So the acceptability of axioms for modal logic depends on which of these uses we have in mind. For this reason, there is no one modal logic, but rather a whole family of systems.
    • (B) A=>□◊A
    • The system B (for the logician Brouwer) is formed by adding (B) to M.
    • (B) says that if A is the case, then A is necessarily possible. One might argue that (B) should always be adopted in any modal logic. However ...
      • ◊□A=>A is provable from (B).
      • ◊□A=>A says that if A is possibly necessary, then A is the case.
      • Why does (B) seem obvious, while one of the things it entails seems not obvious at all?
    • S5 can be formulated by adding (B) to S4.
  • Modal logic can be extended to multi-modal logic, where the □ and ◊ operators are annotated with the identifier of the agent who has that knowledge, e.g., ◊_kingrule_for_ever.

• Temporal Logic
  • In temporal logic (also known as tense logic), there are two basic operators, G for the future, and H for the past.
    • G is read "it always will be that" and the defined operator F (read "it will be the case that"), can be introduced by FA = ~G~A.
    • H is read: "it always was that" and P (for "it was the case that") is defined by PA=~H~A.
  • Examples:
    • Gp => Fp - "What will always be, will be"
    • Fp => FFp - "If it will be the case that p, it will be that it will be"
    • ~Fp => F~Fp - "If it will never be that p then it will be that it will never be that p"
    • PGp - "There was a time after which p"
  • A basic system of temporal logic called Kt results from adopting the principles of K for both G and H, along with two axioms to govern the interaction between the past and future operators:
    • Necessitation rules: If A is a theorem then so are GA and HA. (If A is always derivable, it always was and will be.)
    • Distribution axioms:
      • G(A=>B) => (GA=>GB)
      • H(A=>B) => (HA=>HB)
    • Interaction axioms:
      • A=>GPA
      • A=>HFA
  • The interaction axioms raise questions concerning asymmetries between the past and the future.
    • A standard intuition is that the past is fixed, while the future is still open.
    • The first interaction axiom (A=>GPA) conforms to this intuition in reporting that what is the case (A), will at all future times, be in the past (GPA).
    • A=>HFA may appear to have unacceptably deterministic overtones, for it claims, apparently, that what is true now (A) has always been such that it will occur in the future (HFA).
  • Note that the characteristic axiom of modal logic, (M): □A=>A, is not acceptable for either H or G, since A does not follow from ‘it always was the case that A’, nor from ‘it always will be the case that A’. However, it is acceptable in a closely related temporal logic where G is read ‘it is and always will be’, and H is read ‘it is and always was’.
  • Depending on which assumptions one makes about the structure of time, further axioms must be added to temporal logics. A list of axioms commonly adopted in temporal logics is:
    • GA=>GGA and HA=>HHA
    • GGA=>GA and HHA=>HA
    • GA=>FA and HA=>PA
  • Tense 1st order logic is obtained by adding the temporal operators to first order logic. Examples:
    • ∃X (philosopher(X) & F king(X)) - Someone who is now a philosopher will be a king at some future time
    • ∃X F(philosopher(X) & king(X)) - There now exists someone who will at some future time be both a philosopher and a king
    • F∃X (philosopher(X) & F king(X)) - There will exist someone who is a philosopher and later will be a king
    • F∃X (philosopher(X) & king(X)) - There will exist someone who is at the same time both a philosopher and a king

• Epistemic Logic
  • Introduce three new operators:
    • K_iA - agent i knows A
    • E_GA - each agent in the group G knows A
    • C_GA - A is common knowledge among the agents in the group G. Common knowledge is defined as "everyone knows A, and everyone knows that everyone knows A, and ..."
  • The following axiom system is sound and complete.
    • A1. All propositional tautologies
    • A2. K_iA & K_i(A=>B) => K_iB
    • A3. K_iA => A
    • A4. K_iA => K_iK_iA
    • A5. ~K_iA => K_i~K_iA
    • R1. From A and A=>B infer B
    • R2. From A infer K_iA
    • C1. E_GA => & _{i in G} K_iA
    • C2. C_GA => E_G(A & C_GA)
    • RC1. From A => E_G(A & B) infer A =>C_GB
  • Meanings
    • A2 says that an agent's knowledge is closed under implication.
    • A3 says that an agent knows only things that are true. This axiom is usually taken to distinguish knowledge from belief, i.e., false statements may be believed but not known.
    • A4 and A5 are axioms of introspection; these are usually rejected by philosophers.
    • C2 (fixed point axiom) says that common knowledge of A holds exactly when everyone in the group knows A and that A is common knowledge.
  • A logic of knowledge is used as a tool for analyzing multi-agent systems
    • Players in a poker games
    • Processes in a computer network
    • Robots on an assembly line.
  • The three wise men example

    A king, wishing to know which of his three advisers is the wisest, paints a white spot on each of their foreheads, tells them the spots are black or white and that there is at least one white spot, and asks them to tell him the color of their own spots. After a time the first wise man says, "I do not know whether I have a white spot". The second, hearing this, also says he does not know. The third (truly!) wise man then responds, "My spot must be white".

    • The formalization for the two-man version of the puzzle starts with three propositions:
      • A knows that if A doesn't have a white spot, B will know that A doesn't have a white spot.
      • A knows that B knows that either A or B has a white spot.
      • A knows that B doesn't know whether or not B has a white spot.
  • Sum and Product Puzzle

    Two persons, Sally and Paul, find themselves in a room, of which they do not know the dimensions breadth b and length l, both integers. Sally is told (in secret) the sum of the two integers, and Paul is told (again in secret) their product. It is common knowledge among them that Sally knows the sum and Paul the product, as well as the constraint that 2 <= b <= l <= 99. At this point, the following dialogue arises:
      Paul: I don't know the numbers.
      Sally: I knew you didn't know. I don't know either.
      Paul: Now I know the numbers.
      Sally: Now I know them too.
    What are the numbers?

• Situation and Event Calculi

Exam Style Questions

• Rewrite the following in English: K₁K₂A & ~K₂K₁K₂A.
• Express symbolically, Dean doesn't know whether Nixon knows that Dean knows that Nixon knows that McCord burgled O'Brien's office at Watergate. Hint: let A be the statement "McCord burgled O'Brien's office at Watergate".
• Express symbolically, Everyone in G knows p, but p is not common knowledge.
• Interpret axiom A4: K_iA -> K_iK_iA
• Interpret axiom A5: ~K_iA -> K_i~K_iA.