In my previous post I talked about propositional calculus. Today we will talk about predicate calculus and its syntax and semantics. Predicate calculus builds on this concept by allowing us to describe the relationships in our logical assertions. We could have a statement like “it snowed on Saturday” (it did… it sucks), and represent that as
weather(saturday, snow)We can now add variables and start to generalize. For example if we use the X as a variable for the day of the week, we can say
weather(X, snow) is trueto say that it snows every day of the week (I hope not!). As usual, we first need to define the words in our language, that is the syntax.
The essential quality of a proof is to compel belief.
Fermat
Predicate Calculus Syntax and Semantics
In predicate calculus we use improper symbols to describe objects and their relationship in the world. These are parentheses “( )”, commas “,”, and periods “.”.
We define the symbols as strings of characters and digits. No spaces or special characters can be used, although the “_” can be used for readability. That is the valid characters used are
- All letters, upper- and lowercase.
- All digits from 0 to 9.
- The underscore, “_”.
And all symbols must start with a letter. Some correct examples are
Name coffee3 stan_and_kyle emma XYZ likes partner_ofAnd some invalid examples are
7John stan and kyle ta%ble ###123 lookout!!!These symbols can represent variables, constants, functions, or predicates.
Variables are used for the abstract concept of classes. Any symbol beginning with a capital is a variable.
X Name LocationConstants are specific objects in the world, and start with a lowercase.
emma small pink
note: true and false are reserved as truth symbolsFunctions also start with a lowercase, and are used the map elements in a set. In this writers world, the function
aunt(emma)evaluates to nancy. Functions also have an arity associated with them. In the previous example the arity would be 1. An example of an arity of 2 could be
loves(nancy, emma)Another simple example would be
subtract(nine, two)which evaluates to seven.
A predicate term is a constant, variable, or function expression of a specific arity. We use these terms to describe the problem domain. This leads to another definition, the atomic sentence. It is simply a predicate of N arity followed by N terms in parentheses separated by commas. It is the the most primitive unit of a predicate term. An example of an atomic sentence is
loves(aunt(emma), partner_of(nancy))Now that we have our basic unit, we can build predicate sentences. First some definitions of symbols
- ∧ : logical and
- ∨ : logical or
- ¬ : logical not
- → : logical implies
- ≡ : logical equivalent to
- ∀ : universal quantifier (reads “sentence is true for all values”)
- ∃ : existential quantifier (reads “sentence is true for at least one value”)
To end our discussion on syntax I’ll show another example[efn_note](Luger, George F.; Stubblefield, William A, Artificial intelligence: structures and strategies for complex problem solving 1998)[/efn_note].
mother(eve, abel)
mother(eve, cain)
father(adam, abel)
father(adam, cain)
∀ X ∀ Y father(X, Y) ∨ mother(X, Y) → parent(X, Y)
∀ X ∀ Y ∀ Z parent(X, Y) ∧ parent(X, Z) → sibling(Y, Z)The first 4 lines describe the world. The second two sentences define rules of the world. The first states that for all X’s and all Y’s, if the X is the father of Y or mother of Y, than X is implied to be a parent of Y. The second states that for all X’s, Y’s, and Z’s if a parent of Y is X, and a parent of Z is X, then it is implied that the sibling of Y is Z. If this still confuses you, I encourage you to plug in the variables and see how that looks on paper.
If you want more check out the MIT OpenCourseWare video here!
Tags: logic, predicate calculus