Encyclopedia > Classical two-valued logic

Article Content

Logic

Redirected from Classical two-valued logic

Roughly speaking, logic is the study of prescriptive systems of reasoning, i.e. systems that people ought to use to reason deductively and inductively. How people actually reason is usually studied under other headings, including cognitive psychology. Logic is a branch of mathematics, and a branch of philosophy.

As a science, logic defines the structure of statement and argument and devises formulae by which these are codified. Implicit in a study of logic is the understanding of what makes a good argument and what arguments are fallacious. Philosophical logic deals with formal descriptions of natural language. Most philosophers assume that the bulk of "normal" proper reasoning can be captured by logic, if one can find the right method for translating ordinary language into that logic.

Following are more specific discussions of some systems of logic.

Table of contents

6 Logic and computers

1 Quote

Aristotelian logic

Aristotelian logic was pioneered by Aristotle. Although it is possible that Aristotle was taught by someone else, the earliest study of reasoning can be attributed to Aristotle. Aristotle and his followers held that two of the most important principles of logic are the law of non-contradiction and the law of excluded middle. This kind of logic is now given various names to distinguish it from more recent systems of logic, e.g., Aristotelian logic or classical two-valued logic.

The law of non-contradiction states that no proposition is both true and false and law of excluded middle states that a proposition must either be true or false. In combination, these laws require two truth values that are mutually exclusive. A proposition can be either true or false, but cannot be both at the same time.

Formal logic

Formal logic, also called symbolic logic, is concerned primarily with the structure of reasoning. Formal logic deals with the relationships between concepts and provides a way to compose proofs of statements. In formal logic, concepts are rigorously defined, and sentences are translated into a precise, compact, and unambiguous symbolic notation.

Some examples of symbolic notation are:

Lowercase letter p, q and r with italic font are conventionally used to denote propositions:

p: 1 + 2 = 3

This statement defines p is 1 + 2 = 3 and that is true.

Two propositions can be combined using conjunction, disjunction or conditional. They are called binary logical operators. Such combined propositions are called compound propositions. For example,

p: 1 + 1 = 2 and "logic is the study of reasoning."

In this case, and is a conjunction. The two propositions can differ totally from each other.

In mathematics and computer science, one may want to state a proposition depending on some variables:

p: n is an odd integer.

This proposition can be either true or false according to the variable n.

A proposition with free variables is called propositional function with domain of discourse D. To form an actual proposition, one uses quantifiers. For every n, or for some n, can be specified by quantifiers: either the universal quantifier or the existential quantifier. For example,

for all n in D, P(n).

This can be written also as:

<math>\forall n\in D, P(n)</math>

When there are several free variables free, the standard situation in mathematical analysis since Weierstrass, the quantifications for all ... there exists or there exists ... such that for all (and more complex analogues) can be expressed.

Mathematical logic

Mathematical logic is the use of formal logic to study mathematical reasoning. At the beginning of the twentieth century, philosophical logicians including(Frege, Russell) attempted to prove that mathematics could be entirely reduced to logic. They held that in discovering the "logical form" of a sentence, you were somehow revealing the "right" way to say it, or uncovering some previously hidden essence. The reduction failed, but in the process, logic took on much of the notation and methodology of mathematics, and nowadays logic is accepted as an accurate way to describe mathematical reasoning.

Predicate logic

Gottlob Frege, in his Begriffsschrift, discovered a way to rearrange many sentences to make their logical form clear, to show how sentences relate to one another in certain respects. Prior to Frege, formal logic had not been successful beyond the level of sentential logic: it could represent the structure of sentences composed of other sentences using such words as "and", "or", and "not," but it could not break sentences down into smaller parts. It could not show how "Cows are animals" entails "Parts of cows are parts of animals."

Aristotelian logic was capable of dealing with objects and not just sentences, but it was known to have a number of fallacies, and no way had been found to remove these systematically. Frege's insight was that by discovering "quantifiers" in sentences, we can reduce many more of them into structures of term-and-predicate which we can operate on logically without running into the fallacies of Aristotelian logic.

Sentential logic explains the workings of words such as "and", "but", "or", "not", "if-then", "if and only if", and "neither-nor". Frege expanded logic to include words such as "all", "some", and "none". He showed how we can introduce variables and "quantifiers" to rearrange sentences.

"All humans are mortal" becomes "All things x are such that, if x is a human then x is mortal." which may be written symbolically

<math>\forall x (H(x)\Rightarrow M(x))</math>

"Some humans are vegetarian" becomes "There exists some (at least one) thing x such that x is human and x is vegetarian" which may be written symbolically

<math>\exists x (H(x)\wedge V(x))</math>.

Frege treats simple sentences without subject nouns as predicates and applies them to "dummy objects" (x). The logical structure in discourse about objects can then be operated on according to the rules of sentential logic, with some additional details for adding and removing quantifiers. Frege's work started contemporary formal logic; Aristotelian logic as a substantive research project effectively perished.

Frege adds to sentential logic (1) the vocabulary of quantifiers (upside-down A, backward E) and variables, (2) a semantics that explains that the variables denote individual objects and the quantifiers have something like the force of "all" "some" in relation to those objects, and (3) methods for using these in language. To introduce an "All" quantifier, you assume an arbitrary variable, prove something that must hold true of it, and then prove that it didn't matter which variable you chose, that would have held true. An "All" quantifier can be removed by applying the sentence to any particular object at all. A "Some" (exists) quantifier can be added to a sentence true of any object at all; it can be removed in favor of a term about which you are not already presupposing any information.

Multi-valued Logic

Classical logic systems such as Aristotle's are "two-valued" or "bivalent"; that is, the systems will assign to every sentence either the value "True" or the value "False." Systems which go beyond these two distinctions are known as non-Aristotelian logics, or multi-valued logics.

In the early 20th century Jan Lukasiewicz[?] investigated the extension of the traditional true/false values to include a third value, "possible".

Logics such as fuzzy logic have since been devised with an infinite number of "degrees of truth", e.g., represented by a real number between 0 and 1. Bayesian probability can be interpreted as a system of logic where probability is the subjective truth value.

Logic and computers

Logic is extensively used in the fields of artificial intelligence, and computer science.

In the 1950s and 1960s, researchers predicted that when human knowledge could be expressed using logic with mathematical notation, it would be possible to create a machine that reasons, or artificial intelligence. This turned out to be more difficult than expected because of the complexity of human reasoning. Logic programming is an attempt to make computers do logical reasoning and Prolog programming language is commonly used for it.

In symbolic logic and mathematical logic, proofs by humans can be computer-assisted. Using automated theorem proving the machines can find and check proofs, as well as work with proofs too lengthy to be written out by hand.

In computer science, Boolean algebra is the basis of hardware design, as well as much software design.

Quote Logic, logic, logic. Logic is the beginning of wisdom, Valeris, not the end. From Star Trek VI: The Undiscovered Country

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia

Search over one million articles, find something about almost anything!