CSE 250A LECTURE NOTES

ANNOUNCEMENTS

Here are three sample examination questions and here is the actual final examination from Winter 2000, slightly revised.  These documents are in postscript.
 
 

SEMI-DECIDABILITY

Here |= means logical entailment, which is a semantic notion, while |- means provability, which is a syntactic, i.e. algorithmic notion.  Completeness says that if A is true, then it can be proved eventually.

Given KB and A, it may be the case that KB |= A is not true and also KB |= ~A is also not true.  Completeness says nothing about this case, where neither A nor ~A is entailed by KB, that is KB leaves the truth value of A unsettled.

Definition: The proof algorithm |- is refutation-complete if whenever KB |= A then KB union { ~A} |- false eventually, in finite time.

Theorem: Resolution is refutation-complete.

This theorem says that if KB entails A, then resolution will demonstrate this fact eventually.  Again, nothing is said about the case where neither A nor ~A is entailed by KB.

Definition: The entailment relation |= is semi-decidable if a complete proof algorithm exists for it, while it is decidable if a proof algorithm exists that is complete and also always terminates in finite time.

Gödel's completeness theorem: First-order logic entailment |= is semi-decidable.
Gödel's incompleteness theorem: First-order logic entailment |= is not decidable.

Corollary: If A is not entailed by KB then resolution applied to KB union {~A} may fail to terminate.

Definition: A control strategy for resolution is complete if its use preserves refutation-completeness, i.e. if false can be proved, it can be proved while respecting the strategy.

If a policy allows only a finite number of possible resolutions, then theorem-proving always terminates in bounded time.  In this case completeness must fail because it would contradict the fact that FOL is only semi-decidable, and not decidable.

Any policy that places a fixed upper bound on the length of the clauses that may be used in a proof only allows a finite number of resolutions, hence is incomplete.  This means that allowing axioms to be used multiple times is not enough to preserve completeness.
 
 

SET OF SUPPORT STRATEGY

Usually, the set of support consists of the clauses obtained by negating the goal, plus all descendants of these clauses.  Intuitively, with this strategy, the goal "supports" each resolution, at least indirectly, so each resolution is relevant to obtaining a contradiction.

Theorem: This choice of the supporting set yields a complete strategy if the original knowledge base is consistent.
Proof idea: In this case we'll never obtain a contradiction without using the negated goal somehow.

Note that the set of support increases at each step of the proof because each descendant of the original set of support (i.e. the clauses making up the negated goal) is added to the set of support.

Set-of-support resolution works effectively on the dolphin example.  Given this knowledge base:

Those who can read are literate:      ~r(x) v l(x)
Dolphins are not literate:           ~d(y) v ~l(y)
Some dolphins are intelligent:              d(a)
                            i(a)

~i(z) v r(z)        i(a)
------------------------
              r(a)                ~r(x) v l(x)
              --------------------------------
                        l(a)                ~d(y) v ~l(y)
                        ---------------------------------
                                      ~d(a)     d(a)
                                      --------------
                                            false

FOUNDATIONS OF PROBABILISTIC REASONING

(1) probabilities are a language for representing knowledge about uncertainty;
(2) probability theory provides inference rules;
(3) AI provides algorithms for deduction and learning.

There is a common distinction between "frequentist" and "subjective" semantics for probabilities.  A subjective probability is one that summarizes a degree of belief, while a frequentist probability summarizes a set of actual occurrences that may occurred, or could occur in the future.

Neither probability theory nor other formalisms for reasoning under uncertainty have really successful extensions to the first-order case, i.e. to sentences involving quantifiers.  It is interesting to conjecture that quantifiers are in fact excessively general and abstract, and that they are in fact not used in everyday animal or human reasoning.
 
 

UNCONDITIONAL PROBABILITIES

An "event" is a predicate on outcomes, for example "odd" or "four or less".  We have

•  Pr(odd) = 0.5
•  Pr(four or less)

When the number of basic mutually exclusive outcomes is infinite, then typically the probability of each individual outcome is zero, but ranges have non-zero probabilities.  An individual outcome then has a non-zero probability density.
 
 

CONDITIONAL PROBABILITIES

                                                Pr(A & B)
By definition   Pr(A|B) = ---------   where A and B are events.
                                                     Pr(B)

If X and Y are discrete random variables then Pr(X|Y) is shorthand notation for a two-dimensional table.