Fundamentals of Logic

An introduction into the fundamentals of logic for KBs

Imagem de capa

In my last post, I talked about knowledge-based agents and introduced the concepts behind knowledge bases (KBs) and the set of sentences we use to build them up. In this post, we’ll build on the idea of a sentence as a point to dive into logic and logical representation.

This article is the second of a multi-part discussion on knowledge-based agents, knowledge representation, and logic. See the previous posts here:

What’s in a Logic?

Syntax

Syntax is the way sentences are expressed. The syntax are the rules that determine whether or not a sentence is well formed.

For example, let’s look at the English language. If I wrote the sentence “name Hunter mine is,” you might be able to pick out what I was trying to say, but it definitely isn’t a well-formed sentence. One would expect me to say “my name is Hunter.” Likewise, let’s say our language is mathematics. “1+=2 3” is simply not obeying mathematical syntax. Instead, we want “1+2=3” to be happy.

All logics will have syntactic rules like this and expect their sentences to follow them. With KBs being assembled from a set of sentences, whatever logical syntax that is expected will surely need to be followed or else your KB will be incoherent.

Syntax Tree

Semantics

Where syntax is all about the rules behind creating sentences, semantics is all about the meaning behind the sentences we have. In logic, oftentimes the semantics we talk about whether a sentence is true or false.

Going back to our previous example in English, “my name is Hunter” has truthful semantics in this world with these states. If instead I had made the statement “my name is Paul” that would have the semantics of being false in this world where my name is not Paul. Likewise, if we have a math sentence “x=5,” this sentence has the semantics of being true only if the variable x is actually 5 and is false in all other states of the world.

A more concise way of saying “states of the world” is the term model. A model is a version of the environment where variable states take on a specific value, and this helps us evaluate the truthfulness of sentences. A model would be when x is 4 and another is when x is 5.3. The model in which x is 5 is the one in which our previous math sentence is true.

In fact, we have a special word for when a sentence is true under a particular model and that is “satisfies.” We’ll call model_5 the model where x is 5. With that we can say “model_5 satisfies the sentence x=5” and that model_5 is a model of x=5.

One more thing to note, if we call x=5 A then we can say M(A) is the set of all possible models that satisfy A.

Semantics are Wild

Entailment

We now have the tools to dive into understanding reasoning and, in particular, a type of logical relationship called an entailment. If sentence A entails sentence B, that means that if sentence A is true, then B follows. This looks like so in mathematical notation: A ⊢ B

To say this another way, A entails B if for every model in which A is true, B is always true as well. If A entails B, then A is referred to as the premise and B is the consequent. B is necessarily a consequence of A if A entails B.

For a mathematical example, x=1 entails xy=y. With this powerful tool of entailment, we can create logical inferences about new sentences that are also true in a given model. It’s easy to see this, as we can imagine having a KB where we are uncertain about the sentence xy=y and adding the sentence x=1 allowing us to assert that this is in fact true.

In fact, through logical inference, with the sentence x=1 we can infer that anything that we encounter where it is multiplied by x can be reduced to just itself. We can use this idea to think of a scenario where we have a KB and a new sentence, A. We can check if M(KB) is a subset of M(A), and if so, then KB entails A. In plain English: If every model in which our KB is true, A is also true, then our KB entails A.

When we add a new sentence to our KB, how do we find all the new sentences that are now entailed by our KB? Why that’s what we call our inference algorithm.

Entailment

Inference Algorithms

Inference algorithms are the algorithms by which we derive new, entailed sentences. Inference algorithms are called sound and truth preserving if and only if they only derive sentences that are entailed by our KB. For example, if an inference algorithm takes a KB and adds a new sentence to it that is not entailed by our current knowledge, it is essentially making things up. It is fabricating new truths. This is highly undesirable.

Another thing that we want for our inference algorithm is for it to be complete. Completeness is the idea that when we run an inference algorithm over our KB, it will find all of the entailed sentences. There will be nothing that it won’t find, so that we don’t miss future entailments we might wish to do after it. Now already, you might see where this could potentially cause some issues. In small models with a relatively small set of sentences, this might be easy to achieve. But if the environment is unbounded, this can be hard to handle. Luckily, there are algorithms that have efficient procedures for guaranteeing expressiveness and completeness in an inference algorithm.

Inference

The final thing to think about is an idea called grounding. This is the idea that we have our KB and it’s full of sentences, but is our KB grounded in the truth of the real world? Is it an accurate representation of what is actually true? Now this isn’t really something that is totally centered on the logic we use to represent things, but it is something that is worth considering. If we have an agent interacting in the real world, its perceptions are only as good as the sensors it has. If we have a learning algorithm, our KB may only be as grounded as our learning algorithm is accurate with the creation of learned sentences it passes to the KB. With good enough sensors and good enough learning, we can feel secure it the grounded nature of our KB and inference algorithm, but it is still worth acknowledging.

Grounding

Wrapping Up

So there we have it, an introduction of some of the fundamentals of logic. This is enough to get us started so that in our next post we can dive into propositional logic and dig a bit deeper into things.

If you have any questions, let me know! I am still learning a lot of things about the field of AI, myself, and discussions helps refine understanding.

If you enjoyed this post or found it helpful in any way, I would love you forever if you passed me along a dollar or two to help fund my machine learning education and research! Every dollar helps me get a little closer and I’m forever grateful.