Fundamentals of Logic
A Brief Introduction
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 is the way sentences are expressed. The syntax are the rules that determine whether 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.
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
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.
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,
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.
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.
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.