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 Failed to parse (Missing texvc executable; please see math/README to configure.): P(x) , where Failed to parse (Missing texvc executable; please see math/README to configure.): P

is a predicate letter and Failed to parse (Missing texvc executable; please see math/README to configure.): 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 bird.

Thus, no dog is a bird.

can be notated in the language of monadic predicate calculus as

Failed to parse (Missing texvc executable; please see math/README to configure.): (\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 Failed to parse (Missing texvc executable; please see math/README to configure.): D , Failed to parse (Missing texvc executable; please see math/README to configure.): M

and Failed to parse (Missing texvc executable; please see math/README to configure.): 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

Failed to parse (Missing texvc executable; please see math/README to configure.): \forall x\,P_1(x)\lor\cdots\lor P_n(x)\lor\neg P'_1(x)\lor\cdots\lor \neg P'_m(x)

or

Failed to parse (Missing texvc executable; please see math/README to configure.): \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)", Failed to parse (Missing texvc executable; please see math/README to configure.): (\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[link]

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[link]

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.

Logic portal

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please improve this article by introducing more precise citations. (July 2011)

In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified. Two common quantifiers are the existential ∃ ("there exists") and universal ∀ ("for all") quantifiers. The variables could be elements in the universe under discussion, or perhaps relations or functions over that universe. For instance, an existential quantifier over a function symbol would be interpreted as modifier "there is a function".

In informal usage, the term "predicate logic" occasionally refers to first-order logic. Some authors consider the predicate calculus to be an axiomatized form of predicate logic, and the predicate logic to be derived from an informal, more intuitive development.^[1]

Predicate logics also include logics mixing modal operators and quantifiers. See Modal logic, Saul Kripke, Barcan Marcus formulae, A. N. Prior and Nicholas Rescher.

Syntax[link]

Predicate calculus symbols may represent either variables, constants, functions or predicates.

1. Constants name specific objects or properties in the domain of discourse. Thus George, tree, tall and blue are examples of well formed constant symbols. The constants Failed to parse (Missing texvc executable; please see math/README to configure.): \top

(true) and Failed to parse (Missing texvc executable; please see math/README to configure.): \bot
(false) are sometimes included.

1. Variable symbols are used to designate general classes or objects or properties in the domain of discourse.
2. Functions denote a mapping of one or more elements in a set(called the domain of the function) into a unique element of another set(the range of the function). Elements of the domain and range are objects in the world of discourse. Every function symbol has an associated arity, indicating the number of elements in the domain mapped onto each element of range.

A function expression is a function symbol followed by its arguments. The arguments are elements from the domain of the function; the number of arguments is equal to the arity of the function. The arguments are enclosed in parentheses and separated by commas. e.g.:

• f(X,Y)
• father(david)
• price(apple)

are all well-formed function expressions.

Predicate logics may be viewed syntactically as Chomsky grammars. As such, predicate logics (as well as modal logics and mixed modal predicate logics) may be viewed as context-sensitive, or more typically as context-free, grammars. As each one of the four Chomsky-type grammars have equivalent automata, these logics can be viewed as automata just as well.

See also[link]

• Propositional logic
• First-order logic

Footnotes[link]

1. ^ Among these authors is Stolyar, p. 166. Hamilton considers both to be calculi but divides them into an informal calculus and a formal calculus.

References[link]

Logic portal

• A. G. Hamilton 1978, Logic for Mathematicians, Cambridge University Press, Cambridge UK ISBN 0-521-21838-1.
• Abram Aronovic Stolyar 1970, Introduction to Elementary Mathematical Logic, Dover Publications, Inc. NY. ISBN 0-486-64561
• George F Luger, Artificial Intelligence, Pearson Education, ISBN 978-81-317-2327-2