logic(redirected from Classical two-valued logic)
Also found in: Dictionary, Thesaurus, Medical, Legal, Wikipedia.
logic,the systematic study of valid inference. A distinction is drawn between logical validity and truth. Validity merely refers to formal properties of the process of inference. Thus, a conclusion whose value is true may be drawn from an invalid argument, and one whose value is false, from a valid sequence. For example, the argument All professors are brilliant; Smith is a professor, therefore, Smith is brilliant is a valid inference, but the argument All professors are brilliant; Smith is brilliant; therefore, Smith is a professor is an invalid inference, even if Smith is a professor.
In Western thought, systematic logic is considered to have begun with Aristotle's collection of treatises, the Organon [tool]. AristotleAristotle
, 384–322 B.C., Greek philosopher, b. Stagira. He is sometimes called the Stagirite. Life
Aristotle's father, Nicomachus, was a noted physician. Aristotle studied (367–347 B.C.
..... Click the link for more information. introduced the use of variables: While his contemporaries illustrated principles by the use of examples, Aristotle generalized, as in: All x are y; all y are z; therefore, all x are z. Aristotle posited three laws as basic to all valid thought: the law of identity, A is A; the law of contradiction, A cannot be both A and not A; and the law of the excluded middle, A must be either A or not A.
Aristotle believed that any logical argument could be reduced to a standard form, known as a syllogismsyllogism,
a mode of argument that forms the core of the body of Western logical thought. Aristotle defined syllogistic logic, and his formulations were thought to be the final word in logic; they underwent only minor revisions in the subsequent 2,200 years.
..... Click the link for more information. . A syllogism is a sequence of three propositions: two premises and the conclusion. By varying the form of the proposition and the modifiers (such as all, no, and some), a few specific forms may be delimited. Although Aristotle was concerned with problems in modal logic and other minor branches, it is usually agreed that his major contribution in the field of logic was his elaboration of syllogistic logic; indeed, the Aristotelian statement of logic held sway in the Western world for 2,000 years. Nonetheless, various logicians did, during that time, take issue with parts of Aristotle's thought.
One of Aristotle's tacit assumptions was that there is a correspondence linking the structures of reality, the mind, and language (and hence logic). This position came to be known in the Middle Ages as realismrealism,
in philosophy. 1 In medieval philosophy realism represented a position taken on the problem of universals. There were two schools of realism. Extreme realism, represented by William of Champeaux, held that universals exist independently of both the human mind and
..... Click the link for more information. . The opposing school of thought, nominalismnominalism,
in philosophy, a theory of the relation between universals and particulars. Nominalism gained its name in the Middle Ages, when it was contrasted with realism.
..... Click the link for more information. , is exemplified by William of OccamWilliam of Occam or Ockham
, c.1285–c.1349, English scholastic philosopher. A Franciscan, Occam studied and taught at Oxford from c.
..... Click the link for more information. , a medieval logician, who maintained that the structure of language and logic corresponds only to the structure of the mind, not to that of reality. Since knowledge is a study of generalizations, while nature occurs in myriad single instances, the distinction between the world and our conception of it is stressed by the nominalists.
In the 19th cent. John Stuart MillMill, John Stuart,
1806–73, British philosopher and economist. A precocious child, he was educated privately by his father, James Mill. In 1823, abandoning the study of law, he became a clerk in the British East India Company, where he rose to become head of the examiner's
..... Click the link for more information. noticed the same dichotomy between man's generalizations and nature's instances, but moved toward a different conclusion. Mill held that the scientist or experimenter is not interested in moving from the general to the specific case, which characterizes deductive logic, but is concerned with inductive reasoning, moving from the specific to the general (see inductioninduction,
in logic, a form of argument in which the premises give grounds for the conclusion but do not necessitate it. Induction is contrasted with deduction, in which true premises do necessitate the conclusion.
..... Click the link for more information. ). For example, the statement The sun will rise tomorrow is not the result of a particular deductive process, but is based on a psychological calculation of general probability based on many specific past experiences. Mill's chief contribution to logic rests on his efforts to formulate rules of inductive logic. Although since the criticisms of David Hume there has been disagreement about the validity of induction, modern logicians have argued that inductive logic does not need justification any more than deductive logic does. The real problem is to establish rules of induction, just as Aristotle established rules of deduction.
Mathematics and Logic
With the development of symbolic logicsymbolic logic
or mathematical logic,
formalized system of deductive logic, employing abstract symbols for the various aspects of natural language. Symbolic logic draws on the concepts and techniques of mathematics, notably set theory, and in turn has contributed to
..... Click the link for more information. by George BooleBoole, George,
1815–64, English mathematician and logician. He became professor at Queen's College, Cork, in 1849. Boole wrote An Investigation of the Laws of Thought (1854) and works on calculus and differential equations.
..... Click the link for more information. and Augustus De MorganDe Morgan, Augustus
, 1806–71, English mathematician and logician, b. India. A noted teacher, he was professor of mathematics (1828–31, 1836–66) at University College (now part of the Univ.
..... Click the link for more information. in the 19th cent., logic has been studied in more purely mathematical terms, and mathematical symbols have replaced ordinary language. Reference to external interpretations of the symbols (formulated in ordinary language) was also rejected by the formalist movement of the early 20th cent. Bertrand RussellRussell, Bertrand Arthur William Russell, 3d Earl,
1872–1970, British philosopher, mathematician, and social reformer, b. Trelleck, Wales.
..... Click the link for more information. and Alfred North WhiteheadWhitehead, Alfred North,
1861–1947, English mathematician and philosopher, grad. Trinity College, Cambridge, 1884. There he was a lecturer in mathematics until 1911. At the Univ.
..... Click the link for more information. , in Principia Mathematica (3 vol., 1910–13), attempted to develop logical theory as the basis for mathematics. Pure formal logic attempts to prove that a logical system is dependent only on the perceptual recognition and valid manipulation of symbols and requires no interpretive reference to content.
Intuitionism, rejecting such formalism, holds that words and formulas have significance only as a reflection of activity in the mind. Thus a theorem has meaning only if it represents a mental construction of a mathematical or logical entity. Kurt GödelGödel, Kurt
, 1906–78, American mathematician and logician, b. Brünn (now Brno, Czech Republic), grad. Univ. of Vienna (Ph.D., 1930). He came to the United States in 1940 and was naturalized in 1948.
..... Click the link for more information. , in the 1930s, brought forth his "incompleteness theorem," which demonstrates that an infinitude of propositions that are underivable from the axioms of a system nevertheless have the value of true within the system. Neither these Gödel Propositions, as they are called, nor their negations are provable. One implication for the modern logician is that Aristotle's law of the excluded middle (either A or not A) is neither so simple nor so self-evident as it once seemed.
logicthe branch of PHILOSOPHY concerned with analysis of the universal and context-free (A PRIORI) principles of sound reasoning and valid inference by which conclusions may be drawn from initial premises. These general principles are ‘formal’ in that they are abstract in character, and are usually also capable of being expressed in symbolic notation. An early formulation of logic, which held sway until modern times, was ARISTOTLE's systematization of the basis of the syllogism (also known as propositional logic). This was added to in the 19th-century by highly technical forms of logic, increasingly linked with mathematics. See also INDUCTION AND INDUCTIVE LOGIC, ANALYTIC AND SYNTHETIC, DIALECTIC, COVERING-LAW MODEL AND DEDUCTIVE NOMOLOGICAL EXPLANATION, POSITIVISM.
the science of the acceptable methods of reasoning. In its contemporary usage, the word “logic” has many meanings, although it lacks the fine shades of meaning of the Greek word logos from which it is derived.
Logic is traditionally divided into three main branches. The first branch, ontology, or the logic of things, deals with the necessary connections between phenomena of the objective world (Democritus). The second, epistemology, or the logic of cognition, is concerned with the necessary connections between concepts by means of which “essence and truth” are known (Plato). The third branch of logic, demonstrative (deductive) logic, or logic proper, the logic of proofs and disproofs, deals with the necessary connection between judgments (propositions) in reasoning (inference), the compelling persuasiveness, or “universal validity,” of which in deductive logic follows only from the form of this connection, irrespective of whether these propositions express “essence and truth” (Aristotle). The first two branches of logic belong to philosophy and dialectical logic, while the last branch is the domain of logic proper, or contemporary logic, which is sometimes called formal logic, according to Kant’s use of that term.
Historically, the scope of logic proper has been limited to the “cataloging” of correct arguments, that is, those methods of reasoning that always result in true conclusion-propositions when the premise-propositions are true. The set of rules for correct argumentation has been well known since antiquity; it was identified with the process of deduction. Traditional logic, which is based on Aristotle’s syllogistic, employs the methods of deductive reasoning. As the properties of demonstrative reasoning were subjected to more rigorous examination, the scope of traditional logic gradually broadened by incorporating nonsyllogistic—although still deductive—methods of reasoning and also methods of induction. Insofar as induction did not fit into the framework of logic as deductive theory (or a group of deductive theories), it ultimately became the subject of a separate theory called inductive logic.
Contemporary logic is the historical successor of traditional logic and, to some extent, its direct continuation. Unlike traditional logic, however, contemporary logic deals with the construction of various formalized theories of logical inference, called logical “formalisms” or logical calculi. Logical calculi provide the means for conducting a rigorous analysis of logical inference, thereby permitting a fuller description of the nature of logical reasoning (see below: Subject and method of contemporary logic). The use of logical calculi as a means of representing logical reasoning has led to a more adequate expression of the idea of logos as the unity of language and thought than in antiquity and in all eras preceding the 20th century. In contemporary logic this expression is so obvious that it is sometimes necessary to speak of different “styles of logical thinking” in terms of the various formalisms.
M. M. NOVOSELOV
History. Two theories of deduction, formulated in the fourth century B.C., form the historical basis of contemporary logic, namely, the theory of Aristotle and the theory of his philosophical opponents, the dialecticians of the Megarian school. Both Aristotle and the Megarians pursued the same goal—to discover the “universally valid” laws of the logos of which Plato had spoken. The two opposing theories exchanged, as it were, their preliminary approaches to this goal. The founder of the Megarian school, Euclid of Megara, made extensive use not only of proof by contradiction (reductio ad absurdum) but also of arguments that in form resemble the syllogism; many of the extant sophistries of the Megarians are syllogistic in form. Aristotle, in turn, in his Topics formulated as a proof the fundamental law of the propositional calculus, namely, the law of detachment: given the truth of the propositions “if A, then “B” and “A”, “the law permits the detachment of the proposition “B” as a true conclusion.
If Aristotle abandoned his logic of propositions, it was largely due to the influence of the sophistries of the Megarians, which led him to search for the logical elements of language in its most basic unit, the sentence. It was in this connection that Aristotle introduced the concept of the proposition as true or false speech; he discovered, distinct from grammatical form, the attributive form of speech as the affirmation or denial of “something about something.” He defined the “simple” proposition as a relation of attribution between two terms and discovered that this relation is isomorphic to the relation between the extensions of those terms. Aristotle was the first to make use of the axiom and the rules of the syllogism.
Aristotle created a theory that, although greatly limited in its possibilities, was nevertheless a finished whole—the syllogistic. Within the framework of the logic of classes the syllogistic provided an algorithm for the deduction of conclusions. The Aristotelian syllogistic put an end to the “syllogistic” of the Megarians, whose last representative was Eubulides of Miletus. In his writings, Eubulides criticized Aristotle; Eubulides is the author of the well-known paradoxes of the Liar, the Bald Man, and the Heap, and of several sophistries.
Other followers of Euclid turned to the analysis of conditional propositions, believing that conclusions about “what is implied by something” that are expressed by the figures of the syllogism require a more general foundation. Diodorus Cronus of Iasus and his pupil, Philo of Megara, introduced the concept of implication and studied the connection between implication and the relation of following from, anticipating the idea of a deduction theorem. Although they agreed that the conditional proposition, or implication, is true when the conclusion follows from the premise, Diodorus and Philo differed in their interpretation of the concept “follows.” According to Diodorus, B follows from A when the implication A ⊃ B (“if A, then B) is necessary, so that it is impossible to assert that if A and B remain the same propositions, the implication is true in one case and false in another. Philo, on the other hand, thought that the concept “A” follows from A” is completely determined by the concept of “material implication,” which Philo introduced, having defined the set of its truth values. Thus, there arose a theory of the criteria for logical consequence, which was later incorporated into the teachings of the Stoics. It is not known whether the Megarian school ever considered the question of the axiomatization of logic, although Diogenes Laertius asserted that Clitomachus, a follower of Euclid, was the first to write a treatise (not extant) on axioms and predicates.
The Megarians’ ideas about logic were assimilated by the philosophical school of the Stoics, which was founded about 300 B.C. The most prominent figure in the Stoic school was Chrysippus, who accepted Philo’s criterion for implication and the principle of bivalence as the ontological premise of logic. In the works of the Stoics the logic of propositions preceded the Aristotelian syllogistic and took the form of a system of rules for constructing and rules for deducing propositions. The rules for the deduction of propositions were also called syllogisms, following Aristotle’s example. The Stoics formulated the concept of deduction more precisely than did the Megarians; the Stoic prescription for deduction was the following: the truth of the implication (A1 & A2& …& An) ⊃ is a condition for the formal correctness of inferring B from the premises A1, A2, . . ., An.
Arguments based on the interpretation of propositions solely as truth functions were called formal arguments by the Stoics. Formal arguments can lead from false premises to true conclusions. If the material truth of the premises was being considered, formal arguments were called true arguments. If the premises and conclusions in true arguments were related to each other as cause and effect, respectively, the arguments were called demonstrative. In general, the demonstrative arguments of the Stoics presupposed the concept of natural laws. The Stoics considered that their demonstrative arguments were analytic and rejected the possibility of proving them by means of analogy and induction. Thus, the Stoics’ theory of proof went beyond the limits of logic and entered into the theory of knowledge; it is here that the “deductivism” of the Stoics came up against its philosophical opponent—the radical empiricism of the school of Epicurus.
The Epicurean school was the last important school of logic in ancient times. In their dispute with the Stoics, the Epicureans defended experience, analogy, and induction. The Epicureans laid the foundations for inductive logic; in particular, they pointed out the role of the counter-instance in the problem of the grounding of induction, and they formulated a number of rules for inductive generalization.
The history of logical thought in early antiquity ends with the Epicurean canon. Later antiquity eclectically combined Aristotelianism and Stoicism; the contribution to logic of this later period is limited for all intents and purposes to the work of translation and commentary by the late Peripatetic philosophers (Boethus of Sidon, Alexander of Aegae, Adrastus, Herminus, Alexander of Aphrodisias, Galen) and the Neoplatonists (Porphyry, Proclus, Simplicius, Marius Victorinus, Apuleius, St. Augustine, Boethius, Cassiodorus). Noteworthy among the innovations of the Helleno-Roman logicians are Apuleius’ square of opposition; the dichotomous division and treatment of the terms of the syllogism as constituting a volume in the works of Porphyry; Galen’s ideas about the axiomatization of logic and the logic of relations; the beginnings of a history of logic in the works of Sextus Empiricus and Diogenes Laertius; and, finally, the translations of Greek texts into Latin (in particular, Marius Victorinus’ translation of Porphyry’s Isagoge and Boethius’ translation of works from Aristotle’s Organon), which prepared the way for the terminology of medieval logic. In his dictionary of logic, Boethius introduced, apparently for the first time, the terms “subject,” “predicate,” and “copula,” which for many centuries following were used by logicians in their analysis of propositions. Under the influence of a Stoic doctrine borrowed by Neoplatonism, the study of logic gradually became more closely allied with the study of grammar. In the encyclopedia of that era, Martianus Capella’s Satyricon, logic, as one of the seven liberal arts, was declared a necessary part of a humanistic education.
The logical thought of the early European Middle Ages (seventh to 11th centuries) assimilated the scientific legacy of the ancient world through the prism of Christian consciousness; early medieval logic was considerably less creative than Helleno-Roman logic. Logic developed as an independent science only in the countries of Arab culture, where philosophy was relatively independent of religion. In Europe there developed a logic that was basically scholastic in the true sense of the word. Logic became a discipline in ecclesiastical schools; it was used to adapt elements of Peripatetic logic to the task of substantiating and systematizing Christian dogma. Only in the 12th and 13th centuries, after all of Aristotle’s works had received the official sanction of the church, did there appear an original medieval (nonscholastic) logic, known as logica modernorum.
The general outline of medieval nonscholastic logic can already be seen in the Dialectica of Abelard; however, nonscholastic logic received its final form during the late 13th century and the first half of the 14th century in the works of William of Shyreswood, Petrus Hispanus, John Duns Scotus, Walter Bur-ley, William of Ockham, Jean Buridan, and Albert of Saxony. The works of these authors outlined for the first time a prototype of a “universum of speech” and the idea of the twofold use of language: the “use” of terms to express ideas about extralinguistic facts and the “mention,” or autonymous use of terms to express thoughts about language itself.
The doctrine of propositional connectives and quantifiers that symbolize the nature of a logical relation served medieval logicians as a natural foundation for the distinction between the form and content of judgments. The concept of the “scope” of logical operations was used implicitly by the logicians of the Middle Ages to deal with the problem of the unambiguous “reading” of the syntactic structure of a sentence. Their theory of “consequence” was based on the distinction between material implication and formal, or tautological, implication; counterexamples can be provided only for material implications. Material implication was therefore considered as the expression of material or factual “consequence”; formal implication was a logical “consequence.” Medieval logicians discovered many laws, now well-known, of the logic of propositions, upon which their theory of deduction was based. Like the Stoics, the logicians of the Middle Ages considered the logic of propositions to be more general than the Aristotelian syllogistic. During this period the idea of mechanizing the process of logical deduction was first conceived and the first attempts to put this project into practice were undertaken by R. Lully.
During the following two centuries, the age of the Renaissance, deductive logic underwent a period of crisis. Deductive logic was regarded as the prop for the habits of thought of the scholastics and as the logic of “artificial thinking” that sanctified schematic conclusions whose premises were established by the authority of faith rather than that of knowledge. The thinkers of the Renaissance, guided by the common dictum of the era, “experience instead of abstractions,” set deductive logic in opposition to “natural thought,” which was usually understood as intuition and imagination. Leonardo da Vinci and F. Bacon, who rediscovered the ancient idea of induction and the inductive method, sharply criticized the syllogism. Only a few Renaissance thinkers, such as Zabarella of Padua (16th century), attempted to bring traditional logical deduction back into the methodology for scientific thought, after first having freed it from the scholastic philosophical interpretation.
Zabarella’s books exerted a significant influence on the status of logic in the 17th century. By the time of Hobbes and Gassendi deductive logic had been completely freed from its ties with theology and Peripatetic philosophy. Somewhat earlier, Galileo, the founder of exact natural science, reinstated the rights of abstraction. He justified the need for abstractions that would “complement” the data of experimental observations. Galileo pointed out the necessity of incorporating these abstractions as hypotheses, or as postulates or axioms, into a deductive system that would include the subsequent comparison of the results of deduction with the results of observations.
The critical attitude toward the scholastics and the simultaneous rehabilitation of the deductive method, along with a lessening of interest in the formal aspect of proofs, was characteristic of Cartesian logic, which was based on the methodological ideas of Descartes. This logic was systematically set forth in A. Arnauld’s and P. Nicole’s La Logique, ou l’art de penser (1662); this system of logic has been called the Port-Royal logic. In their book, Arnauld and Nicole presented logic as the working tool of all the other sciences and of practical experience, insofar as logic requires the strict formulation of thought.
The Cartesian concept of a mathesis universalis exerted the greatest influence on the logic of the mid-17th and early 18th centuries, and the work of G. W. Leibniz was of particular importance in the development of this concept. Leibniz, following the ideas of Descartes, Hobbes, and the Port-Royal logicians, believed that it was possible to create a “universal characteristic,” a unique artificial language that would be free of the ambiguities inherent in natural spoken languages, that would be understood without a dictionary, and that would be capable of expressing thoughts precisely and unambiguously. Such a language could serve as an auxiliary international language and as a tool for discovering new truths from known truths. By analyzing the categories of Aristotle, Leibniz arrived at the idea of isolating the simplest initial concepts and propositions, which could then make up an “alphabet of human thoughts.” These primary and indefinable concepts, if combined according to specific rules, would be capable of providing all the remaining exactly defined concepts. Leibniz thought that it would be possible to create, in conjunction with this analysis of concepts, a universal algorithm that would permit all known truths to be proved; proved truths would be compiled in an “encyclopedia of proofs.” In order to accomplish this project, Leibniz provided several variants for the arithmetization of logic. In one variant, to each initial concept is assigned a prime number and to each compound concept is assigned the product of the primes associated with the initial concepts. This idea, remarkable for its simplicity, later played an exceptionally important role in mathematics and logic owing to the works of G. Cantor and K. Gôdel.
Leibniz also originated many methodologically important features of modern logic. For example, he attached great importance to the problem of identity. Accepting the scholastic principle of individuation (the principle of “inner difference”), upon which he based his monadology, Leibniz rejected the ontologization of identity, defining identity instead as a mutual substitutability in context that preserves truth, thereby paving the way for a construction of theories of identity founded on abstraction based on the process of identification.
Although Leibniz did not undertake a study of inductive logic per se, he was fully aware of the problems that a theory of induction entails. In particular, such problems are reflected in Leibniz’ distinction between “truths of reason” and “truths of fact.” According to Leibniz, the laws of Aristotelian logic are sufficient for the verification of the truths of reason. To verify truths of fact, that is, empirical truths, the principle of sufficient reason—which Leibniz formulated—is also needed. Leibniz thus considered the problem, posed by Galileo, of verifying general propositions about reality by means of empirical facts, thus becoming one of the founders of the theory of the hypothetico-deductive method.
Bacon’s ideas on methodology served as the starting point for modern inductive logic. This logic—a logic that investigates “generalizing inferences” as conclusions based on the establishment of the causal relation between phenomena—was systematically developed by J. S. Mill (1843), relying on concepts of J. Herschel. Mill’s theory of inductive inference was subjected to elaboration and criticism in 19th- and 20th-century logic, for example, in the works of the Russian logicians M. I. Karinskii and L. B. Rutkovskii and the Russian statistician A. A. Chuprov. The theory of induction was associated with problems in probability theory, on the one hand, and with the algebra of logic, on the other (as in the works of W. S. Jevons). The inductive logic of the 19th century was mostly concerned with methods of grounding empirical inferences about the lawlike (regular) connections among phenomena; in the 20th century inductive logic became probability logic, on the one hand, and, on the other, went beyond logic proper, was further elaborated and acquired new life in contemporary mathematical statistics and theories of experiment design.
Inductive logic, however, was not the chief trend in the development of theories of logic. Rather, the principal trend was the development of a strictly deductive, or mathematical, logic, whose sources could be found in Leibniz’ work. Although most of Leibniz’ legacy in logic remained unpublished until the beginning of the 20th century, the spread of his ideas during his lifetime exerted a significant influence on the development of algebraic methods in logic. During later development an elaborated logical theory of an algebraic nature—already discernible in the 19th century in the works of A. De Morgan, G. Boole, the German mathematician E. Schröder, and P. S. Poretskii—was constructed by applying mathematical, chiefly algebraic, methods to logic, on which the contemporary algebra of logic was based.
The central figure in this “algebra-of-logic” stage in the history of logic was Boole. He developed his own distinctive algebra of logic (the expression “algebra of logic” was introduced later by C. Peirce) as a typical algebra of that time rather than as a deductive system in the later sense of the word. It is not surprising that in his algebra of logic Boole strove to preserve all the arithmetical operations, including subtraction and division, which were difficult to interpret logically. Boole’s algebra of logic—which was interpreted primarily as a logic of classes, that is, a logic of the extensions of concepts—was greatly simplified and perfected by Jevons, who removed the operations of subtraction and division from logic. In Jevons we already encounter the algebraic system that subsequently was called Boolean algebra. Boole, who used an operation in his algebra corresponding to the exclusive logical connective “or,” that is, strict disjunction, and not the usual weak disjunction widespread in contemporary logic, did not explicitly formulate a Boolean algebra proper.
Rigorous methods of solving logical equations were proposed by Schröder (1877) and Poretskii (1884). Schrö der’s multivolume Vorlesungen über die Algebra der Logik (1890–1905) and Poretskii’s works up to 1907 were the high points in the development of the algebra of logic in the 19th century.
The history of the algebra of logic began with attempts to transfer all the operations and laws of arithmetic to logic, but gradually logicians came to doubt not only the legitimacy but the advisability of this transfer. They developed operations and laws that were specific to logic. Geometrical—more exactly, graphic—methods have long been used in logic together with algebraic methods. The ancient commentators of Aristotle represented the modes of syllogisms by means of geometric figures. The use of circles for this purpose, usually ascribed to L. Euler, was already known to J. K. Sturm (1661) and to Leibniz; the latter also employed methods different from Euler’s. J. H. Lambert and B. Bolzano made use of methods of geometrically interpreting propositional logic; these methods received their most extensive treatment in the works of J. Venn, who developed a graphic apparatus of diagrams that was in fact completely equivalent to the logic of classes and that was no longer merely illustrative but also heuristic.
Toward the end of the 19th century deductive logic underwent a profound revolution that was associated with the works of G. Peano, C. S. Peirce, and G. Frege. These three succeeded in overcoming the narrowness of the purely algebraic approach of previous authors; they realized the value of mathematical logic for mathematicians, and they applied mathematical logic to questions concerning the foundations of arithmetic and set theory. The achievements of this period, which in particular were related to the axiomatic construction of logic, are most clearly visible in the works of Frege. Beginning with his Begriffsschrift (1879), Frege developed a highly rigorous axiomatic construction of the propositional and predicate calculus. His formalized logic contained all the fundamental elements of modern logic calculi: propositional variables, individual variables, quantifiers (for which he introduced special symbols), and predicates. He stressed the difference between logical laws and the rules of logical inference and between variables and constants, and also distinguished (although he did not introduce special terms) between language and metalanguage. Frege’s study of the logical structure of natural language and the semantics of logical calculi (as well as similar work done by Peirce) laid the foundations for logical semantics. Frege’s great achievement was the development of a system of formalized arithmetic that was based on his predicate logic. These works of Frege, and the difficulties that arose in conjunction with them, served as the starting point for the development of a modern theory of mathematical proof.
Frege made use of an original symbolism, which was two-dimensional in contrast to the usual one-dimensional symbolism; however, Frege’s two-dimensional symbolism did not catch on. The contemporary system of notation in logic derives from the symbolism proposed by Peano. It was accepted with some modifications by B. Russell, coauthor with A. N. Whitehead of the three-volume Principia mathematica, a work which systematized and further developed the deductive-axiomatic construction of logic with the purpose of providing a logical foundation of mathematical analysis. The modern period in the study of logic dates from the publication of the Principia and D. Hilbert’s works on mathematical logic, the first of which appeared in 1904.
M. M. NOVOSELOV, Z. A. KUZICHEVA, and B. V. BIRIUKOVSubject and method of contemporary logic. Contemporary logic has developed into an exact science that employs mathematical methods. It has become, in the words of Poretskii, a mathematical logic that treats the subject of logic using mathematical methods. Logic has thereby become suitable for correctly stating and for solving logical problems that arise in mathematics, in particular those related to the provability and unprovability of specific propositions in mathematical theories. An exact formulation of these problems requires first and foremost a refinement of the concept of proof. Every mathematical proof consists of the consistent application of specific logical methods to the primitive propositions. But the logical methods are not something absolute and established once and for all. They have been developed in the course of many centuries of human practical activity. “The practical activity of man had to lead his consciousness to the repetition of various logical figures thousands of millions of times in order that these figures could obtain the significance of axioms” (V. I. Lenin, Poln. Sobr. Soch., 5th ed., vol. 29, p. 172).
However, human practical experience is limited at each historical stage, although its total volume is constantly growing. The logical methods that satisfactorily reflect the working of human thought at a given stage of historical development or in a given sphere of activity may turn out to be inappropriate in the following stage or in another sphere. Therefore, as the object being examined changes in content, the way of looking at the object also changes; that is, the logical methods change. This is particularly true in the case of mathematics with its far-reaching and repeated abstractions. It would be quite senseless to speak here of logical methods as an integral whole or as something absolute. On the other hand, it is reasonable to examine logical methods that are employed in concrete situations encountered in mathematics. The establishment of logical methods for a given mathematical theory is exactly what constitutes the desired refinement of the concept of proof as applied to this theory. The importance of this refinement in the development of mathematics has become particularly evident in problems dealing with the foundations of mathematics. Mathematicians studying set theory encountered a number of special and difficult problems. The first such problem was that of the power of the continuum, which was put forward by Cantor in 1883; no way of dealing with this problem was discovered until 1939. Other problems that just as obstinately defied solution were encountered in descriptive set theory, a theory that is being successfully developed by Soviet mathematicians. It gradually became clear that the difficulties in these problems were of a logical nature and were due to an incomplete clarification of the logical methods applied; mathematicians realized that the only solution to these problems lay in the refinement of logical methods.
It therefore became clear that the solution to these problems called for a new mathematical science—mathematical logic. The application of mathematical logic to problems in mathematics has proved successful. This is particularly true as regards the problem of the continuum, which was completely solved by K. Gôdel (1939) and P. Cohen (1963). Gödel proved that Cantor’s generalized continuum hypothesis is consistent with the axioms of set theory, assuming that those axioms themselves are consistent. Making the same assumption, Cohen demonstrated that the continuum hypothesis was not dependent on the axioms of set theory; that is, the continuum hypothesis cannot be proved from these axioms. Similar results were obtained by P. S. Novikov (1951) in his treatment of a number of problems in descriptive set theory. The refinement of the concept of proof in mathematical theory by the adoption of acceptable logical methods was an essential stage in the development of mathematical theory. Theories that have passed through this stage are called deductive theories, and it is only for deductive theories that the problems of provability and consistency—problems of great interest to mathematicians—may be precisely formulated. In contemporary logic, the method of formalization of proofs is one of the fundamental methods of solving these problems. The essence of the method is as follows:
Formulations of theorems and axioms of a theory that is being developed are completely transcribed into formulas that use a special symbolism including, in addition to the usual mathematical symbols, symbols for the logical connectives used in mathematics, such as “and,” “or,” “if… , then … ,” “it is false that… ,” “for every … ,” and “there exists … , such that ….” Rules of inference, by means of which new formulas are derived from previously derived formulas, are made to correspond to all the logical methods by which theorems are derived from axioms. These rules are formal; that is, in order to verify the correct application of such rules it is not necessary to examine the meaning of the formulas to which they are applied or the meaning of the formula obtained as a result. It is only necessary to verify that these formulas are constructed from a particular set of symbols and are arranged in a particular way. The proof of a theorem is represented by the derivation of the formula that expresses the theorem. This derivation is regarded as a series of formulas at the end of which is the formula to be derived. Every formula in the derivation either expresses an axiom or is obtained from one or several preceding formulas by one of the rules of inference. A formula is considered derivable if its derivation can be constructed.
If the rules of inference properly correlate with the logical methods employed, it becomes possible to make judgments concerning the provability of theorems in a given theory in terms of the derivability of the formulas in which they are expressed. A decision as to the derivability or nonderivability of a formula is not a problem that requires far-reaching abstractions. In fact, comparatively elementary methods may often be sufficient for solving this problem.
D. Hilbert first formulated a method for the formalization of proofs. The formulation of such a method was possible only because of the previous development of mathematical logic (see above: History).
The use of formalization of proofs is usually associated with the separate study of the logical part of the deductive theory under consideration. This logical part is, like the whole theory, formulated in a calculus, that is, a system of formalized axioms and formal rules of inference; the logical part may then be considered an independent whole.
The propositional calculus, both classical and intuitionist, is the simplest of the logical calculi. The propositional calculus uses the following symbols: (1) logical variables, the letters A, B, C, . .. that denote arbitrary “propositions” (the meaning of this term will be explained below); (2) symbols for the logical connectives &, V, ⊃ and ⌝, which designate “and,” “or,” “if. . ., then . . .,” and “it is false that . . .,” respectively; and (3) parentheses, which are used to show the structure of formulas.
The logical variables and any expression that can be obtained from them by the repeated application of given operations are considered the formulas in these calculi. These operations include (1) the placing of the symbol ⌝ to the left of a previously constructed expression and (2) the writing of two previously constructed expressions one after the other and separated by one of the symbols &, V, or ⊃, with the entire expression enclosed in parentheses. The following expressions are formulas:
(1) (A ⊃ (B ⊃ A))
(2) ((A ⊃ (B ⊃ C)) ⊃ ((A ⊃ B) ⊃ (A ⊃ C)))
(3) ((A & B) ⊃ A)
(4) ((A & B) ⊃ B)
(5) (A ⊃ (B ⊃ (A & B)))
(6) ((A ⊃ C) ⊃ ((B ⊃ C) ⊃ ((A V B) ⊃ C)))
(7) (A ⊃ (A V B))
(8) (B ⊃ (A V B))
(9) (⌝ A (A ⊃ B))
(10) (A ⊃ B) ⊃ ((A ⊃ ⌝B) ⊃ ⌝ A))
(11) (A V ⌝ A)
The same rules of inference—the substitution rule and modus ponens—are used in both the classical and intuitionist propositional calculi.
In the substitution rule, a new formula is derived from a given formula by substituting an arbitrary formula everywhere for some logical variable.
In the modus ponens, is derived from and .
These rules reflect the ordinary modes of reasoning, that is, the transition from the general to the particular and the drawing of consequences from proven premises.
The two propositional calculi differ in their sets of axioms. Whereas the classical propositional calculus uses formulas (1)-(11) as axioms, intuitionist propositional calculus employs only the first ten of them as axioms. The 11th formula, which expresses the law of the excluded middle (see below) was found to be nondeducible in the intuitionist calculus. In order to represent the inference of formulas in propositional calculi, we shall derive the formula ⌝ (A & ⌝A), which expresses the law of noncontradiction in the intuitionist calculus.
Let us apply the substitution rule to axioms (3) and (4), substituting the formula ⌝A for the variable B. We then have:
(1) ((A & ⌝ A) ⊃ A)
(2) ((A & ⌝ A) ⊂ ⌝ A)
Then, by substituting the formula (A & ⌝ A) for A, in axiom (10), we obtain:
(3) (((A & ⌝ A) ⊂ B) (((A & ⌝ A)
⊃ ⌝ B) ⊃ ⌝ (A & ⌝ A)))
Further, by substituting A for the variable B in formula (3), we obtain:
(4) (((A & ⌝ A) ⊃ A) ⊃ (((A & ⌝ A) ⊃ ⌝ A)
⊃ ⌝ (A & ⌝ A)))
By applying modus ponens to (1) and (4) we obtain
(5) (((A & ⌝ A) ⊃ ⌝ A) ⊃ ⌝ (A & ⌝ A))
Finally, by applying modus ponens to (2) and (5) we obtain the formula ⌝ (A & ⌝ A), which is thus derivable in the intuitionist propositional calculus.
The formal difference between the two propositional calculi reflects a profound difference between their interpretations, a difference that bears on the meaning of the logical variables, that is, the very understanding of the term “proposition.” In the conventional interpretation of the classical propositional calculus this term has been roughly understood as “judgment” in the Aristotelian sense. It is assumed that a proposition is necessarily true or false. A substitution of arbitrary propositions, that is judgments, for logical variables in a formula yields a logical combination of these judgments, which can also be considered a judgment. The truth or falsity of this judgment is determined exclusively by the truth or falsity of the judgments that can be substituted for the logical variables in accordance with the definitions of the meaning of the logical connectives given below.
A judgment of the type (P & Q) is called a conjunction of the judgments P and Q: the judgment is true when both the judgments are true, and false when at least one of them is false. A judgment of the type (P ∨ Q) is called a disjunction of the judgments P and Q; it is true when at least one of these judgments is true, and is false when both are false. A judgment of the type (P ⊃ Q) is called an implication of the judgements P and Q; it is false when P is true and Q false, and is true in all other cases. A judgment of the type ⌝ P is called the negation of the judgment P; it is true when P is false and false when P is true.
It should be noted that, according to the above definition, implication does not completely coincide in meaning with the everyday usage of the connective “if. . ., then . . .“However, in mathematics this connective is normally used precisely in the sense of this definition of implication. In proving a theorem of the type “if P, then Q,” where P and Q are certain mathematical judgments, a mathematician assumes the truth of P and then proves the truth of Q. He will continue to consider the theorem to be true if P later proves to be false or if the truth of Q is proved without assuming the truth of P. He will consider this theorem to have been disproved only if the truth of P is established together with the falsity of Q. This is entirely consistent with the definition of the implication (P ⊃ Q).
It should also be emphasized that a nonexclusive type of disjunction is usual in mathematical logic. The disjunction (P ⊃ Q) by definition is also true when both P and Q are true.
The formula is called universally valid in the classical sense if every proposition that can be obtained from as a result of substituting any propositions whatever for the logical variables is true. Formula (11), for example, is universally valid in the classical sense. Its universal validity precisely expresses the law of the excluded middle in the form “if one of two propositions is the negation of the other, then at least one of them is true.” This principle expresses the fundamental property of propositions, namely, that propositions are either true or false. (For the usual formulation of this law, which also includes the law of noncontradiction, seeEXCLUDED MIDDLE, LAW OF THE.)
It can be easily verified that all the axioms (1)–(11) are universally valid in the classical sense and that the rules of inference applied to formulas that are universally valid in the classical sense yield only formulas that are universally valid in the classical sense. It therefore follows that all derivable formulas of the classical propositional calculus are universally valid in the classical sense. The converse is also true: every formula that is universally valid in the classical sense can be derived in the classical propositional calculus, which accounts for the completeness of this calculus.
A different treatment of the logical variables forms the basis of the intuitionist interpretation of the propositional calculus. According to this treatment, every mathematical proposition requires a mathematical construction with certain specified properties. A proposition can be asserted only after this construction has been completed. The conjunction (A & B) of the two propositions A and B can be asserted if and only if both A and B can be asserted.
The disjunction (A ∨ B) can be asserted if and only if at least one of the propositions A and B can be asserted. The negation ⌝ A of the proposition A can be asserted if and only if we have a construction that leads to the contradiction of the assumption that the construction required by the proposition A has been carried out. (“Lead to a contradiction” is here considered as a primitive concept.) The implication (A ⊃ B) can be asserted if and only if we have available a construction that, when adjoined to any construction required by A, will yield the construction required by B.
The formula is called universally valid in the intuitionistic sense if and only if it is possible to assert every proposition that can be obtained from as a result of substituting any mathematical propositions for the logical variables; more precisely, such a formula is universally valid in the intuitionistic sense whenever there exists a general method that, when such arbitrary substitution is employed, yields a construction that is required by the results of the substitution. The intuitionists also consider the concept of a general method as a primitive concept.
Formulas (1)–(10) are universally valid in the intuitionistic sense, whereas formula (11), which expresses the classical law of the excluded middle, is not universally valid in the intuitionistic sense.
The viewpoint of constructive mathematics, which refines the somewhat diffuse intuitionistic concepts of implication and general method by its use of the precise concept of an algorithm, is to a certain degree similar to that of intuitionism. From the point of view of constructive mathematics, the law of the excluded middle is also rejected. The logic of constructive mathematics is still in the development stage.
The concept of a formal system is associated with the method by which proofs are formalized. A formal system includes the following elements.
(1) A formalized language with an exact syntax consisting of exact and formal rules for the construction of meaningful expressions that are called the formulas of a given language.
(2) A clear-cut semantics of this language, consisting of conventions that define the way in which formulas are to be understood and which thus determine their truth conditions.
(3) A calculus (see above) consisting of formalized axioms and formal rules of inference. These rules must be consistent with the semantics, when such is present, that is, they must yield true formulas when applied to true formulas.
The calculus determines the derivations (see above) and the formulas that can be derived, that is, the concluding formulas of the derivations. There exists a decision algorithm for derivations. The decision algorithm offers a unified and general method by means of which it is possible to recognize whether any string of symbols that are used in the calculus is a derivation. There are cases in which it is impossible to set up a decision algorithm for derivable formulas; an example is the predicate calculus.
A calculus is said to be consistent if it contains no derivable formula 21 together with the formula ⌝21. The problem of establishing the consistency of calculi used in mathematics is one of the principal tasks of mathematical logic. A calculus is said to be complete within the scope of some specific field of mathematics if every formula expressing a true assertion in this field is derivable in the calculus. A second notion of completeness of a calculus involves the need to have either a proof or a disproof for every assertion that can be formulated in a given calculus. Gödel’s theorem, which states that the completeness requirements are incompatible with the consistency requirement for a rather broad class of calculi, is of paramount importance for these concepts. According to Gödel’s theorem, no consistent calculus from this class can be complete with respect to arithmetic. For every such calculus, it is possible to construct a true arithmetical assertion that can be formalized but not deduced in the calculus. Although this theorem does not diminish the importance of mathematical logic as a powerful organizing method for science, it does destroy all hopes that this discipline might in some way be capable of including mathematics within the framework of a single formal system. Hopes of this kind were expressed by many scholars, among them the founder of mathematical formalism, D. Hilbert.
In the 1970’s the concept of a semiformal system was developed. A semiformal system is also a system of certain rules of inference. Some of these rules, however, can substantially differ from the rules of inference of a formal system. For example, they may permit a new formula to be derived after the logician has intuitively arrived at the conviction that any formula of the same type is derivable. The conjunction of this concept with concepts of a stage-by-stage construction of mathematical logic is the foundation of one of the contemporary constructions of the logic of constructive mathematics. Both the classical and the intuitionist predicate calculi are often used in applications of mathematical logic.
Mathematical logic is organically related to cybernetics, in particular to the mathematical theory of control systems and mathematical linguistics. Applications of mathematical logic to [electrical] relay-contact circuits are based on the fact that every two-terminal relay-contact circuit is an analogue of some formula 21 of the classical propositional calculus in the following sense: if the circuit is controlled by n relays, then 21 contains the same number of different propositional variables, and if we denote by 23i, the proposition “the i th relay is functioning,” the circuit will be closed if and only if the result of substituting the propositions 23i for the corresponding logical variables in 21 is true.
The construction of such an analogous formula describing the operating conditions of a circuit proved to be particularly simple for π-circuits that are obtainable from elementary circuits connected in parallel and in series; this is true because parallel and series connections of circuits simulate, respectively, disjunction and conjunction of propositions. In fact, a circuit obtained by a parallel (series) connection of the circuits C1 and C2 is closed if and only if the circuit C1 is closed and/or the circuit C2 is closed. The application of the propositional calculus to relay-contact circuits has provided a successful approach to important problems of contemporary technology. Many new and difficult problems in mathematical logic have been stated and partially solved as a result of this application; one of the most important problems is the minimization problem, which consists in finding effective methods for determining the simplest formula equivalent to a given formula.
Relay-contact circuits are special cases of the control networks used in contemporary automated mechanisms. Other types of control circuits, in particular, circuits made of electron tubes or semiconductor elements, are of even greater practical value and can also be developed using mathematical logic, which provides adequate means for both the analysis and the synthesis of such circuits. The language of mathematical logic has also proved to be applicable to programming theory, which is being developed in conjunction with the development of computer mathematics. Finally, the apparatus of the calculi created in mathematical logic has proved to be useful in mathematical linguistics, which studies language by mathematical methods.
A. A. MARKOV
Scientific institutions and publications. Teaching and research work in logic are indispensable elements of the scientific and cultural life of most countries. In the USSR scholarly and scientific research in logic is chiefly conducted at research centers in Moscow, Leningrad, Novosibirsk, Kiev, Kishinev, Riga, Vilnius, Tbilisi, and Yerevan; the mathematical institutes of the Academy of Sciences of the USSR and the Academy of Sciences of the Union republics; institutes of philosophy; departments of logic at universities and other institutions of higher learning.
Works on logic in the USSR are published in nonperiodical publications in the form of collections and monographs that deal with specific questions in logic, in particular, beginning in 1959, in the series Matematicheskaia logika i osnovaniia matematiki (Mathematical Logic and the Foundations of Mathematics); in nonperiodical issues of Tr. Matematich. in-ta im. V. A. Steklova AN SSSR (Transactions of the V. A. Steklov Mathematical Institute of the Academy of Sciences of the USSR, published since 1931); in the collections Algebra i logika (Algebra and Logic; Novosibirsk, since 1962); in Zapiski (Notes) from seminars on logic; and in mathematical and philosophical journals. Works of Soviet and foreign authors on logic are regularly reviewed and summarized in Matematika (Mathematics), a journal of abstracts, and in the abstract journals of the Institute for Scholarly Information in the Social Sciences of the Academy of Sciences of the USSR.
The best known specialized foreign journals that deal with problems in logic are the international series of monographs Studies in Logic (Amsterdam, since 1965), and the journals The Journal of Symbolic Logic (Providence, since 1936), Zeitschrift für mathematische Logik und Grundlagen der Mathematik (Berlin, since 1955), Archiv für mathematische Logik und Grundlagenforschung (Stuttgart, since 1950), Logique et analyse (Louvain, since 1958), Journal of Philosophical Logic (Dordrecht, since 1972), International Logic Review (Bologna, since 1970), Studia logica (Warsaw, since 1953), and the Notre Dame Journal of Formal Logic (Notre Dame, since 1960).
Fundamental work associated with the exchange of scholarly information in logic is carried out under the auspices of the UN through the Association for Symbolic Logic. The association organizes international congresses on logic and on the methodology and philosophy of science. The first such congress was held in 1960 at Stanford (USA), the second in 1964 in Jerusalem, the third in 1967 in Amsterdam, and the fourth in 1971 in Bucharest.
Z. A. KUZICHEVA and M. M. NOVOSELOV
Fundamental classical worksAristotle. Analitiki pervaia i vtoraia. Moscow, 1952. (Translated from Greek).
Leibniz, G. W. Fragmente zur Logik. Berlin, 1960.
Kant, I. Logika. Petrograd, 1915. (Translated from German).
Mill, J. S. Sistema logiki sillogisticheskoi i induktivnoi, 2nd ed. Moscow, 1914. (Translated from English.)
De Morgan, A. Formal Logic, or the Calculus of Inference, Necessary and Probable. London, 1847. (Reprinted, London, 1926.)
Boole, G. The Mathematical Analysis of Logic, Being an Essay Toward a Calculus of Deductive Reasoning. London-Cambridge, 1847. (Reprinted, New York, 1965.)
Schröder, E. Der Operationskreis des Logikkalkuls. Leipzig, 1877.
Frege, G. Begriffsschrift: Eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle, 1879.
Jevons, S. Osnovy nauki: Traktat o logike i nauchnom metode. St. Petersburg, 1881. (Translated from English.)
Poretskii, P. S. Osposobakh resheniia logicheskikh ravenstv i ob obratnom sposobe matematicheskoi logiki. Kazan, 1884.
Whitehead, A. N., and B. Russell. Principia mathematica, 2nd. ed., vols. 1–3. Cambridge, 1925–27.
HistoryVladislavlev, M. Logika. St. Petersburg, 1872. (See Appendix.)
Troitskii, M. Uchebnik logiki s podrobnym ukazaniem na istoriiu i sovremennoe sostoianie etoi nauki ν Rossii i ν drugikh stranakh. Vols. 1–3. Moscow, 1885–88.
Ianovskaia, S. A. “Osnovaniia matematiki i matematicheskaia logika.” In Matematika ν SSSR za tridtsat’ let, Moscow-Leningrad, 1948.
Ianovskaia, S. A. “Matematicheskaia logika i osnovaniia matematiki.” In Matematika ν SSSR za sorok let, vol. 1. Moscow, 1959.
Popov, P. S. Istoriia logiki novogo vremeni. Moscow, 1960.
Kotarbiński, T. Lektsii po istorii logiki: Izbr. proizv. Moscow, 1963. Pages 353–606. (Translated from Polish.)
Stiazhkin, N. I. Formirovanie matematicheskoi logiki. Moscow, 1967.
Prantl, K. Geschichte der Logik im Abendlande, vols. 1–4. Leipzig, 1855–70.
Bochenski, I. M. Formale Logik Munich, 1956.
Minio Paluello, L. Twelfth Century Logic: Texts and Studies, vols. 1–2. Rome, 1956–58.
Scholz, H. Abriss der Geschichte der Logik. Freiburg-Munich, 1959.
Lewis, C. I. A Survey of Symbolic Logic. New York, 1960.
Jø rgensen, J. A Treatise of Formal Logic: Its Evolution and Main Branches With Its Relation to Mathematics and Philosophy, vols. 1–3. New York, 1962.
Kneale, W., and M. Kneale. The Development of Logic, 2nd ed. Oxford, 1964.
Dumitriu, A. Istoria logicii. Bucharest, 1969.
Blanché, R. La Logique et son histoire: D’Aristote à Russell. Paris, 1971.
Berka, K., and L. Kreiser. Logik-Texte: Kommentierte Auswahlzur Geschichte der modernen Logik. Berlin, 1971.
TextbooksHilbert, D., and W. Ackermann. Osnovy teoreticheskoi logiki. Moscow, 1947. (Translated from German.)
Tarski, A. Vvedenie ν logiku i metodologiiu deduktivnykh nauk. Moscow, 1948. (Translated from English.)
Novikov, P. S. Elementy matematicheskoi logiki. Moscow, 1959.
Church, A. Vvedenie ν matematicheskuiu logiku, vol. 1. Moscow, 1960. (Translated from English.)
Goodstein, R. L. Matematicheskaia logika. Moscow, 1961.
Grzegorczyk, A. Populiarnaia Logika. Obshchedostupnyi ocherk logiki predlozhenii. Moscow, 1965. (Translated from Polish.)
Mendelson, E. Vvedenie ν matematicheskuiu logiku. Moscow, 1971. (Translated from English.)
Markov, A. A. O logike konstruktivnoi matematiki. Moscow, 1972.
MonographsKleene, S. C. Vvedenie ν metamatematiku. Moscow, 1957. (Translated from English.)
Heyting, A. Intuitsionizm. Moscow, 1965. (Translated from English.)
Curry, H. B. Osnovaniia matematicheskoi logiki. Moscow, 1969. (Translated from English.)
Hilbert, D., and P. Bernays. Grundlegung der Mathematik, vols. 1–2. Berlin, 1934–39.
Markov, A. A. Essai de construction d’une logique de la mathématique constructive. Brussels, 1971.
Encyclopedias and dictionariesFilosofskaia entsiklopediia, vols. 1–5. Moscow, 1960–70.
Kondakov, N. I. Logicheskii Slovar’. Moscow, 1971.
Encyclopedia of Philosophy, vols. 1–8. New York, 1967.
Mata encyklopedia logiki. Wroctaw-Warsaw-Kraków, 1970.
BibliographyPrimakovskii, A. P. Bibliografiia po logike: Khronologicheskii ukazatel’ proizvedenii po voprosam logiki, izdannykh na russkom iazyke ν SSSR ν 18–20 vv. Moscow, 1955.
Ivin, A. A., and A. P. Primakovskii. “Zarubezhnaia literatura po problemam logiki (1960–66).” Voprosy filosofii, 1968, no. 2.
Church, A. “A Bibliography of Symbolic Logic.” The Journal of Symbolic Logic, 1936, vol. 1, no. 4.
Church, A. “Additions and Corrections to ‘A Bibliography of Symbolic Logic’” The Journal of Symbolic Logic, 1938, vol. 3, no. 4.
Beth, E. W. Symbolische Logik und Grundlagen der exakten Wissenschaften. Bern, 1948. [Bibliographische Einführung in das Studium der Philosophie, vol. 3.]
Brie, G. A. de. Bibliographia Philosophica 1934–45, vols. 1–2. Brussels, 1950–54.
Küng, G. “Bibliography of Soviet Works in the Field of Mathematical Logic and the Foundations of Mathematics, From 1917–1957.” Notre Dame Journal of Formal Logic, 1962, no. 3.
Hänggi, J. Bibliographie der Sowjetischen Logik, vol. 2. Winterthur, 1971.
the logic elements permitting the realization of any functional logic diagram of a computer. A set consisting of an AND element and a NOT element or of an OR element and a NOT element is the set of logic elements that has the smallest number of element types yet still is functionally complete, from the point of view of the performance of logical operations. Such elements permit the construction of the simple computer memory element known as the static flip-flop. In addition to the basic logic elements, computers make use of special elements for such purposes as signal shaping, signal amplification, and time delay.
The logic circuits of a computer generally include several versions of the basic logic elements. These versions differ in fan-in and fan-out or in certain additional circuit possibilities. As a result, greater efficiency and flexibility can be obtained in the functional design. In addition, the number of logic levels can be reduced, and the effective speed of the computer units can be increased. All elements in a system of logic elements must be compatible with respect to signal level, time characteristics, and power supply requirements. A computer may include several systems of logic elements in accordance with the speed requirements at each level of the functional diagram of the machine. In this case, special coordinating elements are incorporated in the system of logic elements.
Depending on the type of signals used to represent information (logical variables), systems of logic elements are classified as pulse, potential, and pulse-potential types. Pulse-type logic was used primarily in early computers—for the most part, first-generation computers. Potential and pulse-potential logic has been used in second-generation and, especially, third-generation computers.
The design and principle of operation of the logic elements are different for each generation. First-generation computers use electron-tube elements, second-generation computers use transistors and semiconductor diodes, and third-generation computers use integrated circuits. Depending on the active components used in the basic logic circuits, several types of logic are distinguished. Examples are diode-resistor logic (DRL), resistor-transistor logic (RTL), diode-transistor logic (DTL), transistor-transistor logic (TTL), and emitter-coupled logic (ECL). RTL, DTL, TTL, and ECL are used in the inte-grated-circuit logic systems of present-day computers.
The low-speed and medium-speed computers of the Unified System of Computers use TTL, and the high-speed machines use ECL. In the USSR, the most common TTL system is the series IS 133/155 (Logika-2), which has an average signal delay time of about 15 nanoseconds and an average power dissipation of 15 milliwatts. The series includes more than 20 versions of integrated circuits, including that of an average level of integration (more than ten elements); examples are counters, registers, decoders, and memory units. ECL is used in the USSR in the series IS 137/187, which has a delay time of 4–7 nanoseconds and a power dissipation of 70–35 milliwatts. This series includes 19 versions of integrated circuits with an integration level of two or three elements in one package.
REFERENCEKagan, B. M., and M. M. Kanevskii. Tsifrovye vychislitel’-nye mashiny i sistemy, 2nd ed. Moscow, 1973.
IU. P. SELIVANOV
Logic is concerned with what is true and how we can know whether something is true. This involves the formalisation of logical arguments and proofs in terms of symbols representing propositions and logical connectives. The meanings of these logical connectives are expressed by a set of rules which are assumed to be self-evident.
Boolean algebra deals with the basic operations of truth values: AND, OR, NOT and combinations thereof. Predicate logic extends this with existential and universal quantifiers and symbols standing for predicates which may depend on variables. The rules of natural deduction describe how we may proceed from valid premises to valid conclusions, where the premises and conclusions are expressions in predicate logic.
Symbolic logic uses a meta-language concerned with truth, which may or may not have a corresponding expression in the world of objects called existance. In symbolic logic, arguments and proofs are made in terms of symbols representing propositions and logical connectives. The meanings of these begin with a set of rules or primitives which are assumed to be self-evident. Fortunately, even from vague primitives, functions can be defined with precise meaning.
Boolean logic deals with the basic operations of truth values: AND, OR, NOT and combinations thereof. Predicate logic extends this with existential quantifiers and universal quantifiers which introduce bound variables ranging over finite sets; the predicate itself takes on only the values true and false. Deduction describes how we may proceed from valid premises to valid conclusions, where these are expressions in predicate logic.
Carnap used the phrase "rational reconstruction" to describe the logical analysis of thought. Thus logic is less concerned with how thought does proceed, which is considered the realm of psychology, and more with how it should proceed to discover truth. It is the touchstone of the results of thinking, but neither its regulator nor a motive for its practice.
See also fuzzy logic, logic programming, arithmetic and logic unit, first-order logic,
See also Boolean logic, fuzzy logic, logic programming, first-order logic, logic bomb, combinatory logic, higher-order logic, intuitionistic logic, equational logic, modal logic, linear logic, paradox.
logicThe sequence of operations performed by hardware or software. It is the computer's "intelligence." Hardware logic is contained in the electronic circuits and follows the rules of Boolean logic. Software logic (program logic) is contained in the placement of instructions written by the programmer. Software logic is called "business logic" when it refers to the transactions of the business rather than underlying infrastructure such as the operating system, database management system (DBMS) or network.
Logic Is Not Logical
The term "logic" is not the same as "logical." Logic refers to algorithms and operational sequences; whereas, "logical" refers to a higher-level view of hardware, software or data that is not tied to physical structures (see logical vs. physical). See also logical expression.