First Order Logic and Knowledge Bases

A brief and shallow description of first order logic and knowledge bases

What is First Order Logic?

First order logic is a structure of logic consisting of constants, variables, predicates, functions, and sentences. Constants can be thought of as terms (ex. 1, 2, 3). Variables are variables that represent such terms (x representing numbers). Predicates are relationships consisting of two terms. For example, divisible(1, 2) (the statement 1 divides 2) would return true. divisible(2, 3) would return false. Functions return true or false given one variable. For example, divides3(1) will return true but divides3(2) will return false. Functions can also return terms. For example, divisors(3) will return 1, 3because 1, 3 are divisors of 3.

Finally, sentences contain functions, predicates, etc. but more importantly, quantifiers. Quantifiers describe the variables or constants. There are two quantifiers: the for all quantifier and the existential quantifier (there exists). For example, a sentence could be for all integers x, there exists some integer y that divides x.

What is a Knowledge Base?

A knowledge base is a collection of facts. They are statements that we know to be true. From this knowledge base, we can do several things, but first, there are three assumptions we make:

1. Unique Names: every term that is different has a unique name. For example 2 is called 2 and 3 is called 3. We cannot represent 2 with 3 or vice versa.
2. Closed Domain: If we are operating on a domain of integers, no first order function can have a result that is outside of this domain.
3. Known Functions: Every function will have a known result. There will be no ambiguity.

Inference

From knowledge bases, we can make inferences. That is, given a list of things we know, we can infer other statements. We verify these statements by proving them with statements from the knowledge base. Axioms, are statements that can be proven without any assumptions from the knowledge base. There are 2 characteristics to be noted about inferences:

1. Soundness: Soundness implies that all statements that can be proven are true.
2. Completeness: Completeness implies that all statements that are true can be proven (it’s up to us to prove it)

Note that this was a really short overview of First Order Logic, which I hope was intuitive and helpful as I couldn’t find anything of this nature online. First Order Logic is much more complicated and takes longer to appreciate and understand.