Predicate Logic

Logic as a formal system can be used by linguistics compare and analyze natural language. This formal system can be defined very clearly and thus be also used in computer science, for example: In the field of Artificial Intelligence formal logic can be used for reasoning. We will look at some basic logic formalism and then briefly look at Lambda calculus.

Introduction

In sentential (or propositional) logic sentences (or propositions) are the smallest unit, these sentences can either be true or false. This is called a Boolean, a variable that can only take on the values true or false. Usually variables are represented by single capital letters. Let us see some examples:

We can see that both these propositions can have a true or false (boolean) value.

Operations

Furthermore, we can combine simple sentences to form more complex utterances. These combinations can be seen as operations on the propositions, returning again either true or false.

Conjunction

The conjunction can be translated as the word “and”. It yields true if both conjuncts are true and false if any of the conjuncts is false. Let us first define some sentences:

Now we can perform a conjunction to combine these, changing the resulting boolean.

This translates to: “Saturn has a ring and Jupiter is a gas giant”, which is true.

This translates to: “The moon is made of green cheese and Jupiter is a gas giant”, which is false.

All operations have a so called “truth table”, which shows the result given any input.

Disjunction

The disjunction can be translated as the word “or”. It yields true if one of the disjuncts is true and is denoted by the $\lor$ symbol.

The truth table for the disjunction:

Negation

The negation can be translated as the word “not”. It yields the opposite value of whatever input is given, true becomes false and vice versa. It is denoted by the $\neg$ symbol.

The truth table for the negation:

Conditional

The condition, or implication, can be translated as “if … then”. It is denoted by the $\rightarrow$ symbol.

The truth table for the condition:

Note, that from a false proposition, anything follows (ex falso quodlibet).

Predicates

As we have seen, propositional logic is a rather blunt instrument, that can not seen beyond sentences. Predicate logic solves this problem by expanding the logic formalism we have looked at so far. It does so by using smaller units than sentences, its basic unit is an entity, which corresponds to a thing in the real world. Furthermore, these entities have properties (predicates) assigned to them. Let see an example, let us define three simple entities:

New let us now use simple predicates to give these entities some properties. Predicates are written in uppercase letters and use parenthesis to take arguments.

This will translate as: “Hal is a Robot” and “Dave is a Human”. These predicates can also take on a boolean value, this happens as they are evaluated according to the universe in which they defined. In the universe $U$, in which Hal is a robot and Dave is a human, both sentences would be true.

Predicates can also define actions of entities:

This will translate as: “Dave jogs”. This will also evaluate to true or false depending on the state of the universe. As you can see we defined an intransitive verb as and action of an entity. This also applies to transitive verbs, in that case the predicate will take two arguments.

This will translate as: “Dave likes Hal”. The same way ditransitive verbs can be written as a predicate with three arguments:

This will translate as: “Hal gives Dave the report”. We can also apply the same operations we have seen before to modify and combine sentences.

This will translate as: “Hal is a Robot and Frank is alive”. In the universe in which Hal is a robot and Frank is dead, this will evaluate to:

Quantifiers

So far we have looked at simple nominal phrases, now we introduce a concept that will allow for generic utterances. Quantifiers can be extend a predicate to make more broad statements. There are two types of quantifiers: the universal quantifier $\forall$ and the existential quantifier $\exists$. Let us see how we can modify statements with these quantifiers:

This would translate as: “Everything is a robot”. The quantifier is valid for one variable, in this case $x$, which is written directly after the quantifier. So $\forall$ is interacting with the variable $x$ and not any other variable in the universe. This means if we want to apply a quantifier to more than one variable, we have to write a quantifier for every variable.

This would translate as: “Everything likes everything”. The second quantifier is the existential quantifier. It states, that there is at least one entity with the applied predicate:

This would translate as: “Something is a man” or “There is a entity x with the property of being a man”. of course, we can apply the operations we have seen before to these quantifiers.

This would translate as: “Nobody loves Raymond” or “There is no entity x with the property of loving Raymond”.

Let’s now look at a more complex example:

This would translate as: “Every man is mortal” or “Every man must die” or “Valar Morghulis”. A more literal translation would be: “For every entity x, if x is a man, then x is mortal”.

Lambda Calculus