Extension (predicate logic)  

From The Art and Popular Culture Encyclopedia

Jump to: navigation, search

Related e

Wikipedia
Wiktionary
Shop


Featured:

The extension of a predicate - a truth-valued function - is the set of tuples of values that, used as arguments, satisfy the predicate. Such a set of tuples is a relation.

Examples

For example, the statement "d2 is the weekday following d1" can be seen as a truth function associating to each tuple (d2, d1) the value true or false. The extension of this truth function is, by convention, the set of all such tuples associated with the value true, i.e.

{(Monday, Sunday),
 (Tuesday, Monday),
 (Wednesday, Tuesday),
 (Thursday, Wednesday),
 (Friday, Thursday),
 (Saturday, Friday),
 (Sunday, Saturday)}

By examining this extension we can conclude that "Tuesday is the weekday following Saturday" (for example) is false.

Using set-builder notation, the extension of the n-ary predicate <math>\Phi</math> can be written as

<math>\{ (x_1,...,x_n) \mid \Phi(x_1,...,x_n) \}\,.</math>

Relationship with characteristic function

If the values 0 and 1 in the range of a characteristic function are identified with the values false and true, respectivelyTemplate:Spaced ndashmaking the characteristic function a predicateTemplate:Spaced ndash, then for all relations R and predicates <math>\Phi</math> the following two statements are equivalent:

  • <math>\Phi</math> is the characteristic function of R
  • R is the extension of <math>\Phi</math>

See also




Unless indicated otherwise, the text in this article is either based on Wikipedia article "Extension (predicate logic)" or another language Wikipedia page thereof used under the terms of the GNU Free Documentation License; or on research by Jahsonic and friends. See Art and Popular Culture's copyright notice.

Personal tools