Propositional Knowledge Bases and Reasoning
The meeting takes place if all members have been informed in advance, and it is quorate. It is quorate provided that there are at least 15 people present. Member will have been informed in advance if there is not a postal strike.
Consequence: If the meeting does not take place, we conclude that there were fewer than 15 members present, or there was a postal strike.
Let:
- $m$: The meeting takes place.
- $a$: All members have been informed.
- $p$: There is a postal strike.
- $q$: The meeting is quorate.
- $f$: There are at least 15 members present.
Then the text can be formalised as the following knowledge base:
\[((a\wedge q)\Rightarrow m ), (f\Rightarrow q), (\neg p\Rightarrow a)\]Definition
A propositional knowledge base $X$ is a finite set of propositional formulas.
Suppose a propositional knowledge base $X$ is given. Then a propositional formula $P$ follows from $X$ if the following folds for ever interpretation $I$:
\[\text{If } I(Q) = 1 \text{ for all } Q\in X, \text{ then } I(P)=1\]This is denoted by:
\[X\models P\]Example
We have seen that:
\[\begin{aligned} &\{((a\wedge q)\Rightarrow m ), (f\Rightarrow q), (\neg p\Rightarrow a)\}\models\\ &(\neg m \Rightarrow(\neg f \vee p)) \end{aligned}\]Simpler Example
Show $\{(p_1\wedge p_2)\}\models(p_1\vee p_2)$
| $p_1$ | $p_2$ | $(p_1\wedge p_2)$ | $(p_1\vee p_2)$ |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 |
Thus, from $I(p_1\wedge p_2) = 1$ is follows that $I(P_1\vee p_2)=1$. We are basically seeing if the left hand side is a subset of the right hand side. “If the statement on the left is true, then the statement on the right is true.”
Reasoning
We want a computer to solve this for us so we should take the following into account:
- $X\models P$ if $I(P)=1$ for all interpretations $I$ such that $I(Q)=1$ for all $Q\in X$.
- There are $2^n$ different relevant interpretations if $P$ and $X$ together heave $n$ propositional atoms.
- Thus, to check $X\models P$ directly using truth tables, a table with $2^n$ rows is needed.
-
$X\models P$ can be checked using a SAT solver:
Assume that $X$ contains the propositional formula $P_1,\ldots,P_n$ and let
\[Q=P_1\wedge\ldots\wedge P_n\wedge\neg P\]Then:
$X\models P$ if and only if $Q$ is not satisfiable.
This means that the knowledge base is not satisfiable if when all propositions in the knowledge base are true but still the knowledge base is false.
Summary
- In KR&R knowledge is stored in a knowledge base. Reasoning is needed to make implicit knowledge explicit.
- We have considered rule-based and propositional knowledge bases and corresponding reasoning.
- in the rule-based case we have given reasoning algorithms.
- Databases only store atomic assertions. In contrast, knowledge bases store knowledge that goes beyond atomic assertions (such as rules and compound propositions.
- Knowledge stored in knowledge bases is mostly incomplete, whereas knowledge stored in databases is mostly complete.
- Many other KR&R languages with corresponding reasoning algorithms have been developed.