06-04-2012, 04:48 PM
Predicate Logic
10 Predicate Logic.pdf (Size: 114.7 KB / Downloads: 261)
Introduction
Predicate logic builds heavily upon the ideas of proposition logic to provide a more
powerful system for expression and reasoning. As we have already mentioned, a
predicate is just a function with a range of two values, say false and true. We already
use predicates routinely in programming, e.g. in conditional statements of the form
Validity
It is common to be concerned with a fixed interpretation (of domains, predicates, and
functions) and allow the assignment to vary over individuals in a domain. If a formula
evaluates to true for all assignments, it is called valid with respect to the interpretation.
If a formula is valid with respect to every interpretation, it is called valid. A special case
of validity is where sub-expressions are substituted for proposition symbols in a
tautology. These are also called tautologies. However, not every valid formula is a
tautology, as is easily seen when we introduce quantifiers later on.
Database Application
An important use of predicate logic is found in computer databases and the more general
notion of "knowledge base", defined to be a database plus various computation rules. In
this application, it is common to use predicate expressions containing variables as above
as "queries". The predicates themselves represent the underlying stored data, computable
predicates, or combinations thereof. A query asks the system to find all individuals
corresponding to the variables in the expression such that the expression is satisfied
(evaluates to 1). Next we demonstrate the idea of querying a database using the Prolog
language as an example. Prolog is not the most widely-used database query language;
Prolog Database Example
There are many ways to represent the predicates in a database, such as by structured files
representing tables, spreadsheet subsections, etc. In the language Prolog, one of the ways
to represent a predicate is just by enumerating all combinations of values for which the
predicate is true. Let us define the predicates mother and father in this fashion. These
predicates provide a way of modeling the family "tree" on the right
Defining grandmother using Prolog
The Prolog language allows us to present queries and have them answered automatically
in a style similar to the above. Moreover, Prolog allows us to define new predicates using
logic rather than enumeration.