World Library  
Flag as Inappropriate
Email this Article

Monadic predicate calculus

Article Id: WHEBN0008015680
Reproduction Date:

Title: Monadic predicate calculus  
Author: World Heritage Encyclopedia
Language: English
Subject: Predicate logic, Mathematical logic, Vector logic, Regular language, Decidability (logic)
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Monadic predicate calculus

In logic, the monadic predicate calculus (also called monadic first-order logic) is the fragment of first-order logic in which all relation symbols in the signature are monadic (that is, they take only one argument), and there are no function symbols. All atomic formulas are thus of the form P(x), where P is a relation symbol and x is a variable.

Monadic predicate calculus can be contrasted with polyadic predicate calculus, which allows relation symbols that take two or more arguments.

Expressiveness

The absence of polyadic relation symbols severely restricts what can be expressed in the monadic predicate calculus. It is so weak that, unlike the full predicate calculus, it is decidable - there is a decision procedure that determines whether a given formula of monadic predicate calculus is logically valid (true for all nonempty domains).[1][2] Adding a single binary relation symbol to monadic logic, however, results in an undecidable logic.

Relationship with term logic

The need to go beyond monadic logic was not appreciated until the work on the logic of Charles Sanders Peirce in the nineteenth century, and by Frege in his 1879 Begriffsschrifft. Prior to the work of these three men, term logic (syllogistic 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 bird.
Thus, no dog is a bird.

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 B(y)) \Rightarrow \neg(\exists z\,D(z)\land B(z))

where D, M and B denote the predicates of being, respectively, a dog, a mammal, and a bird.

Conversely, monadic predicate calculus is not significantly more expressive than term logic. Each formula in the monadic predicate calculus is equivalent to a formula in which quantifiers appear only in closed subformulas 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),

These formulas slightly generalize the 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 described above 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 results in an undecidable logic.

Monadic second-order logic allows predicates of higher arity in formulas, but restricts second-order quantification to unary predicates, i.e. the only second-order variables allowed are subset variables.

Footnotes

  1. ^ Heinrich Behmann, Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem, in Mathematische Annalen (1922)
  2. ^ 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.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.