Monadic predicate calculus


Monadic predicate calculus

In logic, the monadic predicate calculus is the fragment of predicate calculus in which all predicate letters are monadic (that is, they take only one argument), and there are no function letters. All atomic formulae have the form P(x), where P is a predicate letter and x is a variable.

Monadic predicate logic can be contrasted with polyadic predicate logic, which uses predicates (called many-place predicates) that take two or more arguments. For example, "x is mortal" or "Mx" is a one-place predicate, while "x loves y" or "Lxy" is a two-place predicate and "x lies between y and z" or "Bxyz" is a three-place predicate.[1]

The absence of polyadic predicates severely restricts what can be expressed in the monadic predicate calculus. That calculus is so weak that, unlike the full predicate calculus, it is decidable whether a given formula of that calculus is logically valid (true for all nonempty domains).[2][3] (However, adding a single binary predicate letter to monadic logic would result in a system with the expressive power of the full predicate calculus.) Because the monadic predicate calculus is decidable, it is ipso facto inadequate for general mathematical reasoning, if only because the tiny fragment of mathematics called Peano arithmetic is known to be undecidable.

Notwithstanding the above deficiencies, the need to go beyond monadic logic was not appreciated until the work on the logic of relations, by Augustus DeMorgan and Charles Sanders Peirce in the 19th century, and by Frege in his little-read 1879 Begriffsschrifft. Prior to the work of these three men, syllogistic term logic was widely considered adequate for formal deductive reasoning.

Inferences in term logic can all be represented in the monadic predicate calculus. For example the syllogism

All dogs are mammals
No mammal is a herbivore
Thus, no dog is a herbivore

can be notated in the language of monadic predicate calculus as

(\forall x\,D(x)\Rightarrow M(x))\land \neg(\exists y\,M(y)\land H(y)) \Rightarrow \neg(\exists z\,D(z)\land H(z))

where D, M and H denote the predicates of being, respectively, a dog, a mammal, and a herbivore.

Conversely, monadic predicate calculus is not significantly more expressive than term logic. It is easily proved that every formula in the monadic predicate calculus is equivalent to a formula in which quantifiers appear only in closed subformulae of the form

\forall x\,P_1(x)\lor\cdots\lor P_n(x)\lor\neg P'_1(x)\lor\cdots\lor \neg P'_m(x)

or

\exists x\,\neg P_1(x)\land\cdots\land\neg P_n(x)\land P'_1(x)\land\cdots\land P'_m(x),

Each of these formulas is the negation of the other, and the quantifiers do not nest. These formulas also generalize slightly the form of basic judgements considered in term logic. For example, this form allows statements such as "Every mammal is either a herbivore or a carnivore (or both)", (\forall x\,\neg M(x)\lor H(x)\lor C(x)). Reasoning about such statements can, however, still be handled within the framework of term logic, although not by the 19 classical Aristotelian syllogisms alone.

Taking propositional logic as given, every formula in the monadic predicate calculus expresses something that can likewise be formulated in term logic. On the other hand, a modern view of the problem of multiple generality in traditional logic concludes that quantifiers cannot nest usefully if there are no polyadic predicates to relate the bound variables.

Variants

The formal system describe in this entry is sometimes called the pure monadic predicate calculus, where "pure" signifies the absence of function letters. Allowing monadic function letters changes the logic only superficially, whereas admitting even a single binary function letter would result in a system with the expressive power of the full predicate calculus.

Monadic predicate calculus is also called monadic first-order logic. Monadic second-order logic keeps the requirement that all predicates be unary, but allows for quantification over predicates as well as variables.

Footnotes

  1. ^ http://www.earlham.edu/~peters/courses/log/terms3.htm
  2. ^ Heinrich Behmann, Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem, in Mathematische Annalen (1922)
  3. ^ Löwenheim, L. (1915) "Über Möglichkeiten im Relativkalkül," Mathematische Annalen 76: 447-470. Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort, 1967. A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press: 228-51.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • monadic — A predicate is monadic if it requires only one singular term to make a sentence: ‘…is mortal’ is monadic. The contrast is with n adic predicates (relational predicates) that require n places to be filled where n > 1. The monadic predicate… …   Philosophy dictionary

  • Predicate functor logic — In mathematical logic, predicate functor logic (PFL) is one of several ways to express first order logic (formerly known as predicate logic) by purely algebraic means, i.e., without quantified variables. PFL employs a small number of algebraic… …   Wikipedia

  • Propositional calculus — In mathematical logic, a propositional calculus or logic (also called sentential calculus or sentential logic) is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules… …   Wikipedia

  • First-order predicate — A first order predicate (also called a monad) is a predicate that takes only individual(s) constants or variables as argument(s). Compare second order predicate and higher order predicate. ee also*First order predicate calculus *Monadic predicate …   Wikipedia

  • logic — logicless, adj. /loj ik/, n. 1. the science that investigates the principles governing correct or reliable inference. 2. a particular method of reasoning or argumentation: We were unable to follow his logic. 3. the system or principles of… …   Universalium

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • First-order logic — is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic (a less… …   Wikipedia

  • Metalogic — is the study of the metatheory of logic. While logic is the study of the manner in which logical systems can be used to decide the correctness of arguments, metalogic studies the properties of the logical systems themselves.[1] According to… …   Wikipedia

  • Function (mathematics) — f(x) redirects here. For the band, see f(x) (band). Graph of example function, In mathematics, a function associates one quantity, the a …   Wikipedia

  • Second-order logic — In logic and mathematics second order logic is an extension of first order logic, which itself is an extension of propositional logic.[1] Second order logic is in turn extended by higher order logic and type theory. First order logic uses only… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.