Recent Comments

    Categories

    Predicate Calculus: Its Simple Syntax, and Semantics

    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 true

    to 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

    1. All letters, upper- and lowercase.
    2. All digits from 0 to 9.
    3. The underscore, “_”.

    And all symbols must start with a letter. Some correct examples are

    Name   coffee3   stan_and_kyle   emma   XYZ   likes   partner_of

    And 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   Location

    Constants are specific objects in the world, and start with a lowercase.

    emma   small   pink     
    note: true and false are reserved as truth symbols

    Functions 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!

    Leave a Reply

    You can use these HTML tags

    <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>