HOME

TheInfoList



OR:

In
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from prem ...
, the monadic predicate calculus (also called monadic first-order logic) is the fragment of
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
in which all relation symbols in the
signature A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and ...
are monadic (that is, they take only one argument), and there are no function symbols. All
atomic formula In mathematical logic, an atomic formula (also known as an atom or a prime formula) is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformu ...
s 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 In mathematics, a finitary relation over sets is a subset of the Cartesian product ; that is, it is a set of ''n''-tuples consisting of elements ''x'i'' in ''X'i''. Typically, the relation describes a possible connection between the eleme ...
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 In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
that determines whether a given formula of monadic predicate calculus is logically valid (true for all nonempty
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined ** Domain of definition of a partial function ** Natural domain of a partial function **Domain of holomorphy of a function * ...
s). 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. 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 relations, by Augustus De Morgan and
Charles Sanders Peirce Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for ...
in the nineteenth century, and by
Frege Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic p ...
in his 1879 ''Begriffsschrifft''. Prior to the work of these three men,
term logic In philosophy, term logic, also known as traditional logic, syllogistic logic or Aristotelian logic, is a loose name for an approach to formal logic that began with Aristotle and was developed further in ancient history mostly by his followers, ...
(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 argument : 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 Equivalence or Equivalent may refer to: Arts and entertainment *Album-equivalent unit, a measurement unit in the music industry * Equivalence class (music) *'' Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre *''Equiva ...
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
syllogism A syllogism ( grc-gre, συλλογισμός, ''syllogismos'', 'conclusion, inference') is a kind of logical argument that applies deductive reasoning to arrive at a conclusion based on two propositions that are asserted or assumed to be tru ...
s alone. Taking
propositional logic Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
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 In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory. First-order logic quantifies on ...
allows predicates of higher
arity Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. ...
in formulas, but restricts second-order quantification to unary predicates, i.e. the only second-order variables allowed are subset variables.


Footnotes

{{Mathematical logic Predicate logic Logical calculi