:: wikimiki.org ::

Deductive Reasoning

Deductive reasoning

In traditional Aristotelian logic, deductive reasoning is inference in which the conclusion is of lesser or equal generality than the premises, as opposed to inductive reasoning, where the conclusion is of greater generality than the premises. Other theories of logic define deductive reasoning as inference in which the conclusion is just as certain as the premises, as opposed to inductive reasoning, where the conclusion can have less certainty than the premises. In both approaches, the conclusion of a deductive inference is necessitated by the premises: the premises can't be true while the conclusion is false. (In Aristotelian logic, the premises in inductive reasoning can also be related in this way to the conclusion.) inductive reasoning

Examples

Valid: :All men are mortal. :Socrates is a man. :Therefore Socrates is mortal. :The picture is above the desk. :The desk is above the floor. :Therefore the picture is above the floor. Invalid: :Every criminal opposes the government. :Everyone in the opposition party opposes the government. :Therefore everyone in the opposition party is a criminal. This is invalid because the premises fail to establish commonality between membership in the opposition party and being a criminal. This is the famous fallacy of undistributed middle.

Axiomatization

More formally, a deduction is a sequence of statements such that every statement can be derived from those before it. Naturally, this leaves open the question of how we prove the first sentence (since it cannot follow from anything). Axiomatic propositional logic solves this by requiring the following conditions for a proof to be met: A proof of α from an ensemble Σ of wffs is a finite sequence of wffs: :β1,...,βi,...,βn where :βn = α and for each βi (1 ≤ i ≤ n), either :
- βi ∈ Σ or :
- βi is an axiom, or :
- βi is the output of Modus Ponens for two previous wffs, βi-g and βi-h. Different versions of axiomatic propositional logics contain a few axioms, usually three or more than three, in addition to one or more inference rules. For instance Gottlob Frege's axiomatization of propositional logic, which is also the first instance of such an attempt, has six propositional axioms and two rules. Bertrand Russell and Alfred North Whitehead also suggested a system with five axioms. For instance a version of axiomatic propositional logic due to Jan Lukasiewicz (1878-1956) has a set A of axioms adopted as follows: :
- [PL1] p → (q → p) :
- [PL2] (p → (q → r)) → ((p → q) → (p → r)) :
- [PL3] (¬p → ¬q) → (q → p) and it has the set R of Rules of inference with one rule in it that is Modu Ponendo Ponens as follows: :
- [MP] from α and α → β, infer β. The inference rule(s) allows us to derive the statements following the axioms or given wffs of the ensemble Σ.

Natural Deductive Logic

In one version of natural deductive logic presented by E.J. Lemmon that we should refer to it as system L, we do not have any axiom to begin with. We only have nine primitive rules that govern the syntax of a proof. The nine primitive rules of system L are: #The Rule of Assumption (A) #Modus Ponendo Ponens (MPP) #The Rule of Double Negation (DN) #The Rule of Conditional Proof (CP) #The Rule of ∧-introduction (∧I) #The Rule of ∧-elimination (∧E) #The Rule of ∨-introduction (∨I) #The Rule of ∨-elimination (∨E) #Reductio Ad Absurdum (RAA) In system L, a proof has a definition with the following conditions: #has a finite sequence of wffs (well-formed-formula) #each line of it is justified by a rule of the system L #the last line of the proof is what is intended (Q.E.D, quod erat demonstrandum, is a Latin expression that means: which was the thing to be proved), and this last line of the proof uses the only premise(s) that is given; or no premise if nothing is given. Then if no premise is given, the sequent is called theorem. Therefore, the definitions of a theorem in system L is:
- a theorem is a sequent that can be proved in system L, using an empty set of assumption. or in other words:
- a theorem is a sequent that can be proved from an empty set of assumptions in system L An example of the proof of a sequent (Modus Tollendo Tollense in this case): An example of the proof of a sequent (a theorem in this case): Each rule of system L has its own requirements for the type of input(s) or entry(es) that it can accept and has its own way of treating and calculating the assumptions used by its inputs.

References

- Jennings, R. E., Continuing Logic, the course book of 'Axiomatic Logic' in Simon Fraser University, Vancouver, Canada
- Zarefsky, David, Argumentation: The Study of Effective Reasoning Parts I and II, The Teaching Company 2002

Aristotelian logic

:This article is about Aristotle's logical works. For other meanings of the term 'Organon', see Organon (disambiguation). For a discussion of Aristotelian logic as a system, see term logic. The Organon is the name given by Aristotle's followers, the Peripatetics, for the standard collection of six of his works on logic. The system of logic described in two of these works, namely On Interpretation and the Prior Analytics, often called Aristotelian logic, is discussed in the article on term logic.

Constitution of the texts

The order of the works is not chronological (which is now hard to determine), but was deliberately chosen by the Peripatetics to constitute a well-structured system; indeed some parts of them seem to be a scheme of a lecture on logic. The arranging of the works was conducted by Andronicus of Rhodes around 40 BC. Aristotle's Metaphysics has many points of intellectual overlap with the works making up the Organon, but is not traditionally considered part of it; additionally there are works on logic attributed, with varying degrees of plausibility, to Aristotle that were not known to the Peripatetics.

On Interpretation

On Interpretation (Latin: De Interpretatione) introduces Aristotle's conceptions of proposition and judgement, and treats contrarieties between them. It contains Aristotle's principal contribution to philosophy of language.

Prior Analytics

The Prior Analytics (Latin: Analytica Priora) introduces his syllogistic method, which is discussed in the article on term logic, argues for its correctness, and discusses inductive inference.

Posterior Analytics

The Posterior Analytics (Latin: Analytica Posteriora) discusses correct reasoning in general.

Topics

The Topics (Latin: Topica) treats issues in constructing valid arguments, and inference that is probable, rather than certain. It is in this treatise that Aristotle mentions the idea of the Predicables, which was later developed by Porphyry and the scholastic logicians.

On Sophistical Refutations

On Sophistical Refutations (Latin:De Sophisticis Elenchis) gives a treatment of logical fallacies, and provides a key link to Aristotle's work on rhetoric.

The influence of the Organon

Aristotle's works on logic, (collectively called the Organon), are the only significant works of Aristotle that were never "lost"; all his other books were "lost" from his death, until rediscovered in the 11th century. The Organon was used in the school founded by Aristotle at the Lyceum, and some parts of the works seem to be a scheme of a lecture on logic. So much so that after Aristotle's death, his publishers (e.g. Andronicus of Rhodes in 50 BC) collected these works. In these works we can find the first ontological category theory (relevant in some branches of intensional logic), the first development of formal logic, the first known serious scientific inquisitions on the theory of (formal and informal) reasoning, the foundations of modal logic, and some antecedents of methodology of sciences. The Organon was not always popular during the Hellenistic era. Stoic logic was predominant, particularly the work of Chrysippus (none of whose work has survived). In the 8th century the Scholastics, in non-Arab Europe, studied and promoted the study of logic based on the Organon. One of the greatest Scholastics was Dominican monk Albertus Magnus (1206–1280), the teacher of Thomas Aquinas (1226–1274). The books of Aristotle were available in the Arab Empire and were studied by Islamic and Jewish scholars, including Rabbi Moses Maimonides (1135–1204) and Muslim Judge Ibn Rushd (1126 - 1198); both lived in Cordoba, Spain. Cordoba had 70 libraries, one of them with over 40,000 volumes; the two largest libraries in non-Arab Europe each had only 2,000 volumes. Thomas Aquinas used the writings and comments of Aristotle ("the philosopher"), Albert, Maimonides ("the Rabbi") and Ibn Rushd ("the commentator") and many others. In the Enlightenment there was a revival of interest in logic as the basis of rational enquiry, and a number of texts, most successfully the Port-Royal Logic, polished Aristotelian term logic for pedagogy. During this period, while the logic certainbly was based on that of Aristotle, Aristotle's writings themselves were less often the basis of study. There was a tendency in this period to regard logical inference as trivial, which in turn no doubt stifled innovation in this area. Immanuel Kant thought that there was nothing else to invent after the work of Aristotle, and a famous logic historian called Carl Prantl claimed that any logician who said anything new about logic was "confused, stupid or perverse." These examples illustrate the general tendency during the period between the 13th century and the 19th century to accept without question the work of Aristotle. He had already become known by the Scholastics (medieval Christian scholars) as "The Philosopher." The dogmatism created by the Scholastics in favor of Aristotle took a long time to disappear. Since the historical discoveries and logic innovations of the 19th century, particularly the discovery of Indian logic, George Boole's algebraic logic and the formulation of predicate logic, Aristotelian logic no longer has such prestige and is mainly studied out of historical interest. There is, however, a mostly pedagogical interest in term logic deriving from its close structure to the actual forms of reasoning encountered in natural language.

References

- All of the books of the Organon are available freely in english translation:
- # [http://classics.mit.edu/Aristotle/categories.html Text of Categories]
- # [http://etext.library.adelaide.edu.au/a/a8/intrpret.html Text of On Interpretation]
- # [http://classics.mit.edu/Aristotle/prior.html Text of Prior Analytics]
- # [http://classics.mit.edu/Aristotle/posterior.html Text of Posterior Analytics]
- # [http://classics.mit.edu/Aristotle/topics.html Text of Topics]
- # [http://classics.mit.edu/Aristotle/sophist_refut.html Text of On Sophistical Refutations]
- I. M. Bocheński, I. M., 1951. Ancient Formal Logic. North-Holland, Amsterdam.
- Louis Couturat, 1961. La Logique de Leibniz. Georg Olms Verlagsbuchhandlung, Hildesheim.
- Hammond and Scullard, 1992. The Oxford Classical Dictionary. Oxford University Press, ISBN 0198691173.
- Jan Lukasiewicz, 1951. Aristotle's Syllogistic, from the Standpoint of Modern Formal Logic. Clarendon Press, Oxford.
- Parry and Hacker, 1991. Aristotelian Logic. State University of New York Press, Albany.
- Terence Parsons, 1999. '[http://plato.stanford.edu/entries/square/ Traditional Square of Opposition]'. Article at the Stanford Encyclopedia of Philosophy.
- Lynn E. Rose, 1968. Aristotle's Syllogistic. Clarence C. Thomas, Springfield.
- Robin Smith, 2004. '[http://plato.stanford.edu/entries/aristotle-logic Aristotle's Logic]'. Article at the Stanford Encyclopedia of Philosophy.
- W. Turner, 1903. '[http://www.nd.edu/Departments/Maritain/etext/hop.htm History of Philosophy]'. Ginn and Co, Boston. All references in this article are to [http://www.nd.edu/Departments/Maritain/etext/hop11.htm Chapter nine on 'Aristotle'].

External links

- J. Evans, '[http://www.webster.edu/~evansja/guides/aristotle/logic.html A summary of the Organon]'. Class notes.
- [http://www.iep.utm.edu/a/aristotl.htm Aristotle article] at the Internet Encyclopedia of Philosophy.

Notes

Hammond, p. 64, "Andronicus Rhodus" Category:Aristotle Category:Ancient Greek works Category:History of logic

Inductive reasoning

:This article is about induction in philosophy and logic. Inductive reasoning is the complement of deductive reasoning. For other article subjects named induction see induction. Induction or inductive reasoning, sometimes called inductive logic, is the process of reasoning in which the premises of an argument support the conclusion, but do not ensure it. It is to ascribe properties or relations to types based on limited observations of particular tokens; or to formulate laws based on limited observations of recurring phenomenal patterns. Induction is used, for example, in using specific propositions such as:
- The ice is cold.
- A billiard ball moves when struck with a cue. to infer general propositions such as:
- All ice is cold. or: There is no ice in the Sun.
- For every action, there is an equal and opposite re-action.

Examples

Valid: :All observed crows are black. :Therefore all crows are black. This exemplifies the nature of induction: inducing the universal from the particular. And clearly the conclusion is not certain. Unless we've seen every crow - and how do we know that? - maybe there are some rare blue ones. Invalid: :I always hang pictures on nails. :Therefore all pictures are hung from nails. In this example, the premise is built upon a certainty: "I always hang pictures on nails", but not all people hang pictures on nails and those that do use nails may only do some of the time. There are a number of objects that may be used to hang picture, including, but not limited to: screws, bolts, and clips. The conclusion I draw is an overgeneralization and is, in some instances, false. :Teenagers get lots of speeding tickets. :Therefore all teenagers speed. In this example, the foundational premise is not built upon a certainty: not every teenager we've observed speeding has received a ticket. It may be in the general nature of teenagers to speed - as it is crows to be black - but the premise is based more on wishful thinking than direct observation.

Validity

Formal logic as most people learn it is deductive rather than inductive. Some philosophers claim to have created systems of inductive logic, but it is controversial whether a logic of induction is even possible. In contrast to deductive reasoning, conclusions arrived at by inductive reasoning do not necessarily have the same degree of certainty as the initial assumptions. For example, a conclusion that all swans are white is obviously wrong, but may have been thought correct in Europe until the settlement of Australia. Inductive arguments are never binding but they may be cogent. Inductive reasoning is deductively invalid. (An argument in formal logic is valid if and only if it is not possible for the premises of the argument to be true whilst the conclusion is false.) In induction there are always many conlucsions that can reasonably be related to certain premises. Inductions are open; deductions are closed. The classic philosophical treatment of the problem of induction, meaning the search for a justification for inductive reasoning, was by the Scotsman David Hume. Hume highlighted the fact that our everyday reasoning depends on patterns of repeated experience rather than deductively valid arguments. For example we believe that bread will nourish us because it has in the past, but it is at least conceivable that bread in the future will poison us. Someone who insisted on sound deductive justifications for everything would starve to death, said Hume. Instead of unproductive radical skepticism about everything, he advocated a practical skepticism based on common-sense, where the inevitability of induction is accepted. 20th Century developments have framed the problem of induction very differently. Rather than a choice about what predictions to make about the future, it can be seen as a choice of what concepts to fit to observation (see the entry for grue) or of what graphs to fit to a set of observed data points. Induction is sometimes framed as reasoning about the future from the past, but in its broadest sense it involves reaching conclusions about unobserved things on the basis of what is observed. Inferences about the past from present evidence (e.g. archaeology) count as induction. Induction could also be across space rather than time, e.g. conclusions about the whole universe from what we observe in our galaxy or national economic policy based on local economic performance.

Types of inductive reasoning

;Generalization :A generalization, or inductive generalization, proceeds from a premise about a sample to a conclusion about the population. #A proportion Q of the sample has attribute A. #Conclusion: Q of the population has A. The support which the premises provide for the conclusion is dependent on the number of individuals in the sample group compared to the number in the population, and the randomness of the sample. The hasty generalization and biased sample are fallacies related to generalization. ;Statistical syllogism :A statistical syllogism proceeds from a generalization to a conclusion about an individual. #A proportion Q of population P has attribute A. #An individual I is a member of P. #Conclusion: There is a probability which corresponds to Q that I has A. The proportion in premise 1 can be a word like '3/5 of', 'all' or 'few'. Two dicto simpliciter fallacies can occur in statistical syllogisms. They are "accident" and "converse accident". ;Simple Induction :Simple induction proceeds from a premise about a sample group to a conclusion about another individual. #Proportion Q of known instances of population P has attribute A. #Individual I is another member of P. #Conclusion: There is a probability which corresponds to Q that I has A. This is actually a combination of a generalization and a statistical syllogism, where the conclusion of the generalization is also the first premise of the statistical syllogism. ;Argument from analogy :An (inductive) analogy proceeds from known similarities between two things to a conclusion about an additional attribute that is common to both things: #Thing P is similar to thing Q. #P has attribute A. #Conclusion: Q has attribute A. An analogy relies on the inferrence that the known shared properties (similarities) imply that A is also a shared property. The support which the premises provide for the conclusion is dependent upon the relevance and number of the similarities between P and Q. ;Causal inference :A causal inference draws a conclusion about a causal connection based on the conditions of the occurrence of an effect. Premises about the correlation of two things can indicate a causal relationship between them, but additional factors must be confirmed to establish the exact form of the causal relationship. ;Prediction :A prediction draws a conclusion about a future individual from a past sample. #Proportion Q of observed members of group G have had attribute A. #There is a probability which corresponds to Q that the next observed member of G will have A. ;Argument from authority :An argument from authority draws a conclusion about the truth of a statement based on the proportion of true propositions which a sources says. It has the same form as a prediction. #Proportion Q of the claims of authority A have been true. #There is a probability which corresponds to Q that this claim of A is true. Example: :All observed claims from websites about logic are true. :This information came from websites about logic. :Therefore, this information is (probably) true.

Bayesian inference

Of the candidate systems of inductive logic, the most influential is Bayesianism, which uses probability theory as a framework for induction. Bayes theorem is used to calculate how much the strength of one’s belief in a hypothesis should change, given some evidence. There is debate around what it is that informs the original degree of belief. Objective Bayesians seek an objective value for the degree of probability of a hypothesis being correct, and so do not avoid the philosophical criticisms of objectivism. Subjective Bayesians hold that the prior probabilities represent subjective degrees of belief, but that repeated application of Bayes’ theorem leads to a high degree of agreement on the posterior probability. They therefore fail to provide an objective standard for choosing between conflicting hypotheses. The theorem can be used to rationally justify belief in some hypothesis, but at the expense of rejecting objectivism. Such a scheme cannot be used, for instance, to objectively decide between conflicting scientific paradigms. Edwin Jaynes, an outspoken physicist and Bayesian, argued that 'subjective' elements are present in all of inference (e.g. in choosing axioms for deductive inference, in choosing initial degrees of belief or prior probabilities, and in choosing likelihoods), and sought a series of principles for assigning probabilities from qualitative knowledge. Maximum entropy (a generalization of the principle of indifference) and transformation groups are the two resulting tools he produced; both attempt to alleviate the subjectivity of probability assignment in specific situations by converting knowledge of e.g. symmetries of a situation into unambiguous choices for probability distributions. Bayesians feel entitled to call their system an inductive logic because of Cox's Theorem, which derives probability from a set of logical constraints on a system of inductive reasoning.

External links

- [http://www.uncg.edu/phi/phi115/induc4.htm Four Varieties of Inductive Argument]
- [http://plato.stanford.edu/entries/logic-inductive/ Stanford Encyclopedia of Philosophy entry on Inductive Logic] Category:Logic Category:Epistemology ja:帰納

Modus ponens

In Logic, Modus ponens (Latin: mode that affirms) is a valid, simple argument form (often abbreviated to MP): :If P, then Q. :P. :Therefore, Q. or in logical operator notation: :P → Q :P :⊢ Q where ⊢ represents the logical assertion. or may also be written: :P P → Q : Q In Metalogics the modus ponens is the cut-rule. The cut-elimination theorem says that the cut is valid (admissible rule) in some logical calculus (sequent calculus). The argument form has two premises. The first premise is the "if-then" or conditional claim, namely that P implies Q. The second premise is that P, the antecedent of the conditional claim, is true. From these two premises it can be logically concluded that Q, the consequent of the conditional claim, must be true as well. Here is an example of an argument that fits the form modus ponens: :If democracy is the best system of government, then everyone should vote. :Democracy is the best system of government. :Therefore, everyone should vote. The fact that the argument is valid cannot assure us that any of the statements in the argument are true; the validity of modus ponens tells us that the conclusion must be true if all the premises are true. It is wise to recall that a valid argument within which one or more of the premises are not true is called an unsound argument, whereas if all the premises are true, then the argument is sound. In most logical systems, Modus ponens is considered to be valid. However, the instances of its use may be either sound or unsound. :If the argument is modus ponens and its premises are true, then it is sound. :The premises are true. :Therefore, it is a sound argument. A propositional argument using modus ponens is said to be deductive. Modus ponens can also be referred to as affirming the antecedent or "Law of Detachment". For an amusing dialog that problematizes modus ponens, see Lewis Carroll's "What the Tortoise Said to Achilles."

Axioms

In epistemology, an axiom is a self-evident truth upon which other knowledge must rest, from which other knowledge is built up. Not all epistemologists agree that any axioms, understood in that sense, exist. In mathematics, an axiom is not necessarily a self-evident truth but rather, a formal logical expression used in a deduction to yield further results. Mathematics distinguishes two types of axioms: logical axioms and non-logical axioms.

Etymology

The word axiom comes from the Greek word αξιωμα (axioma), which means that which is deemed worthy or fit or that which is considered self-evident. The word comes from αξιοειν (axioein), meaning to deem worthy, which in turn comes from αξιος (axios), meaning worthy. Among the ancient Greek philosophers an axiom was a claim which could be seen to be true without any need for proof.

Mathematics

In the field of mathematical logic, a clear distinction is made between two notions of axioms: logical axioms and non-logical axioms.

Logical axioms

These are certain formulas in a language that are universally valid, that is, formulas that are satisfied by every structure under every variable assignment function. More colloquially, these are statements that are true in any possible universe, under any possible interpretation and with any assignment of values. Usually one takes as logical axioms some minimal set of tautologies that is sufficient for proving all tautologies in the language.

Examples

In the propositional calculus it is common to take as logical axioms all formulas of the following forms, where

\phi

\psi

, and

\chi

can be any formulas of the language: #

\phi \to (\psi \to \phi)

(\phi \to (\psi \to \chi)) \to ((\phi \to \psi) \to (\phi \to \chi))

(\lnot \phi \to \lnot \psi) \to (\psi \to \phi)

Each of these patterns is an axiom schema, a rule for generating an infinite number of axioms. For example, if

A

B

, and

C

are propositional variables, then

A \to (B \to A)

and

(A \to \lnot B) \to (C \to (A \to \lnot B))

are both instances of axiom schema 1, and hence are axioms. It can be shown that with only these three axiom schemata and modus ponens, one can prove all tautologies of the propositional calculus. It can also be shown that no pair of these schemata is sufficient for proving all tautologies with modus ponens. These axiom schemata are also used in the predicate calculus, but additional logical axioms are needed.

Example. Let

\mathfrak\,

be a first-order language. For each variable

x\,

, the formula

x = x

is universally valid.

This means that for any variable symbol

x\,

, the formula

x = x\,

can be regarded as an axiom. Also, in this example, for this not to fall into vagueness and a never-ending series of "primitive notions", either a precise notion of what we mean by

x = x\,

(or, for all what matters, "to be equal") has to be well established first, or a purely formal and syntactical usage of the symbol

=\,

has to be enforced, and mathematical logic does indeed do that. Another, more interesting example, is that which provides us with what is known as universal instantiation:

Example. Given a formula

\phi\,

in a first-order language

\mathfrak\,

, a variable

x\,

and a term

t\,

that is substitutable for

x\,

\phi\,

, the formula

\forall x. \phi \to \phi^x_t

is universally valid.

Informally speaking, this example allows us to state that if we know that a certain property

P\,

holds for every

x\,

and that if

t\,

stands for a particular object in our structure, then we should be able to claim

P(t)\,

. Again, we are claiming that the formula

\forall x. \phi \to \phi^x_t

is valid, that is, we must be able to give a "proof" of this fact, or more properly speaking, a metaproof. Actually, these examples are metatheorems of our theory of mathematical logic since we are dealing with the very concept of proof itself. Aside from this, we can also have existential generalization:

Axiom scheme. Given a formula

\phi\,

in a first-order language

\mathfrak\,

, a variable

x\,

and a term

t\,

that is substitutable for

x\,

\phi\,

, the formula

\phi^x_t \to \exists x. \phi

is universally valid.

Non-logical axioms

Non-logical axioms are formulas that play the role of theory-specific assumptions. Reasoning about two different structures, for example the natural numbers and the integers, may involve the same logical axioms; the non-logical axioms aim to capture what is special about a particular structure (or set of structures, such as groups). Thus non-logical axioms, unlike logical axioms, are not tautologies. Another name for a non-logical axiom is postulate. Almost every modern mathematical theory starts from a given set of non-logical axioms, and it was thought that in principle every theory could be axiomatized in this way and formalized down to the bare language of logical formulas. This turned out to be impossible and proved to be quite a story (see below). Non-logical axioms are often simply referred to as axioms in mathematical discourse. This does not mean that it is claimed that they are true in some absolute sense. For example, in some groups, the group operation is commutative, and this can be asserted with the introduction of an additional axiom, but without this axiom we can do quite well developing (the more general) group theory, and we can even take its negation as an axiom for the study of non-commutative groups. Thus, an axiom is an elementary basis for a formal logic system that together with the rules of inference define a deductive system.

Examples

This section gives examples of mathematical theories that are developed entirely from a set of non-logical axioms (axioms, henceforth). A rigorous treatment of any of these topics begins with a specification of these axioms. Basic theories, such as arithmetic, real analysis (sometimes referred to as the theory of functions of one real variable), linear algebra, and complex analysis (a.k.a. complex variables), are often introduced non-axiomatically in mostly technical studies, but any rigorous course in these subjects always begins by presenting its axioms. Geometries such as Euclidean geometry, projective geometry, symplectic geometry. Interestingly one of the results of the fifth Euclidean axiom being a non-logical axiom is that the three angles of a triangle do not by definition add to 180°. Only under the umbrella of Euclidean geometry is this always true. The study of topology in mathematics extends all over through point set topology, algebraic topology, differential topology, and all the related paraphernalia, such as homology theory, homotopy theory. The development of abstract algebra brought with itself group theory, rings and fields, Galois theory. This list could be expanded to include most fields of mathematics, including axiomatic set theory, measure theory, ergodic theory, probability, representation theory, and differential geometry.

Arithmetic

The Peano axioms are the most widely used axiomatization of arithmetic. They are a set of axioms strong enough to prove many important facts about number theory and they allowed Gödel to establish his famous second incompleteness theorem. We have a language

\mathfrak_ = \\,

where

0\,

is a constant symbol and

S\,

is a unary function and the following axioms: #

\forall x. \lnot (Sx = 0)

\forall x. \forall y. (Sx = Sy \to x = y)

((\phi(0) \land \forall x.\,(\phi(x) \to \phi(Sx))) \to \forall x.\phi(x)

for any

\mathfrak_\,

formula

\phi\,

with one free variable. The standard structure is

\mathfrak = \langle\N, 0, S\rangle\,

where

\N\,

is the set of natural numbers,

S\,

is the successor function and

0\,

is naturally interpreted as the number 0.

Euclidean geometry

Probably the oldest, and most famous, list of axioms are the 4 + 1 Euclid's postulates of plane geometry. This set of axioms turns out to be incomplete, and many more postulates are necessary to rigorously characterize his geometry (Hilbert used 23). The axioms are referred to as "4 + 1" because for nearly two millennia the fifth (parallel) postulate ("through a point outside a line there is exactly one parallel") was suspected of being derivable from the first four. Ultimately, the fifth postulate was found to be independent of the first four. Indeed, one can assume that no parallels through a point outside a line exist, that exactly one exists, or that infinitely many exist. These choices give us alternative forms of geometry in which the interior angles of a triangle add up to less than, exactly, or more than a straight line respectively and are known as elliptic, Euclidean, and hyperbolic geometries.

Real analysis

The object of study is the real numbers. The real numbers are uniquely picked out (up to isomorphism) by the properties of a complete ordered field. However, expressing these properties as axioms requires use of second-order logic. The Löwenheim-Skolem theorems tell us that if we restrict ourselves to first-order logic, any axiom system for the reals admits other models, including both models that are smaller than the reals and models that are larger. Some of the latter are studied in non-standard analysis.

Role in mathematical logic

Deductive systems and completeness

A deductive system consists of a set

\Lambda\,

of logical axioms, a set

\Sigma\,

of non-logical axioms, and a set

\\,

of rules of inference. A desirable property of a deductive system is that it be complete. A system is said to be complete if, for all formulas

\phi

, if

\Sigma \models \phi

then

\Sigma \vdash \phi

that is, for any statement that is a logical consequence of

\Sigma

there actually exists a deduction of the statement from

\Sigma\,

. This is sometimes expressed as "everything that is true is provable", but it must be understood that "true" here means "made true by the set of axioms", and not, for example, "true in the intended interpretation". Gödel's completeness theorem establishes the completeness of a certain commonly-used type of deductive system. Note that "completeness" has a different meaning here than it does in the context of Gödel's first incompleteness theorem, which states that no recursive, consistent set of non-logical axioms

\Sigma\,

of the Theory of Arithmetic is complete, in the sense that there will always exist an arithmetic statement

\phi\,

such that neither

\phi\,

nor

\lnot\phi\,

can be proved from the given set of axioms. There is thus, on the one hand, the notion of completeness of a deductive system and on the other hand that of completeness of a set of non-logical axioms. The completeness theorem and the incompleteness theorem, despite their names, do not contradict one another.

Further discussion

Early mathematicians regarded axiomatic geometry as a model of physical space, and obviously there could only be one such model. The idea that alternative mathematical systems might exist was very troubling to mathematicians of the 19th century and the developers of systems such as Boolean algebra made elaborate efforts to derive them from traditional arithmetic. Galois showed just before his untimely death that these efforts were largely wasted, but that the grand parallels between axiomatic systems could be put to good use, as he algebraically solved many classical geometrical problems. Ultimately, the abstract parallels between algebraic systems were seen to be more important than the details and modern algebra was born. In the modern view we may take as axioms any set of formulas we like, as long as they are not known to be inconsistent.

External links

- [http://us.metamath.org/mpegif/mmset.html#axioms Metamath axioms page] Category:Algebra Category:Logic ko:공리 ja:公理

Gottlob Frege

Friedrich Ludwig Gottlob Frege (November 8, 1848 – July 26, 1925) was a German mathematician, logician, and philosopher who is regarded as a founder of both modern mathematical logic and analytic philosophy.

Frege's life

Frege was born in Wismar. He started studying at the University of Jena in 1869 and moved to Göttingen after two years, where he received his Ph.D. in 1873. After returning to Jena two years later, he became lecturer of mathematics. In 1879, he was made associate professor and in 1896 became professor of mathematics. He died in Bad Kleinen in 1925.

Frege's contributions

Frege is widely regarded as one of the greatest logicians since Aristotle. His revolutionary Begriffsschrift, or Concept Script from 1879 marked the beginning of a new epoch in the history of logic by displacing the old Term Logic that had held sway virtually unchanged since Aristotle. The Begriffsschrift was ground-breaking, and made contributions that are nowadays ubiquitous in mathematics, such as the use of quantification, which solved the medieval problem of multiple generality, and a clean treatment of functions and variables. Frege was the first to devise an axiomatization of propositional logic and of predicate logic, the latter of which was his own invention. The quantification so essential to Bertrand Russell's theory of descriptions, and to Russell and Alfred North Whitehead's Principia Mathematica, was also due to Frege. His work was largely unrecognized in his own day, and his ideas spread chiefly through those he influenced, particularly Giuseppe Peano and Russell. Ludwig Wittgenstein and Edmund Husserl were among the other philosophical notables strongly influenced by Frege. Frege is regarded as one of the founding fathers of analytic philosophy, due to his deeply systematic contributions to the philosophy of language, most fundamentally his function-argument analysis of the proposition, his distinction between the sense and reference (Sinn und Bedeutung) of a proper name (Eigenname), the advocacy of a mediated reference theory, his distinction between concept and object (Begriff und Gegenstand), and his advancement of the context principle. He corresponded with many leading logicians and philosophers of his time such as Russell, Peano and Husserl. Frege was a major proponent of logicism about arithmetic (the view that arithmetic is reducible to logic). His Grundgesetze der Arithmetik was an attempt to explicitly derive the laws of arithmetic from logic. After the first volume was published (at the author's expense), Russell discovered the paradox which bears his name, and that the axioms of the Grundgesetze led to this contradiction; he wrote to Frege, who acknowledged the contradiction in an appendix to volume two of the Grundgesetze, noting what he perceived to be the faulty axiom. Frege never did manage to amend his axioms to his satisfaction, although later work by Russell and by John von Neumann suggested ways to resolve the problem. He was also a philosopher of mathematics, who loathed appealing to psychologistic or "mental" explanations for meanings (such as idea theories of meaning). His original purpose was very far from answering questions about meaning -- he wanted to use modern logic to further develop the foundations of arithmetic. He first undertook to answer the question, "what is a number?" or "what objects do number-words ("one", "two", etc.) refer to?". But in pursuing these matters, he was eventually confronted with the task of analysing and explaining what meaning is, and came to several memorable conclusions in that regard. Despite this, and despite the generosity of Bertrand Russell's praise for Frege, he remained an obscure figure through his lifetime; had it not been for his influence on Wittgenstein-- of whom both major works, the Tractatus and the Philosophical Investigations, revolved around a coming to terms with Frege's ideas about logic and language-- Frege's worth as a philosopher might never have been recognised. Leading authorities on Frege include Michael Dummett and Hans Sluga.

Principal works

- Begriffsschrift (Concept Script), eine der arithmetischen nachgebildete Formelsprache des reinen Denkens, Halle a. S., 1879
- Die Grundlagen der Arithmetik (The Foundations of Arithmetic): eine logisch-mathematische Untersuchung über den Begriff der Zahl, Breslau, 1884
- "Funktion und Begriff" ("Function and Concept"): Talk given in a Meeting on January 9, 1891 of the Jenaischen Gesellschaft für Medizin und Naturwissenschaft, Jena, 1891
- "Über Sinn und Bedeutung" ("On Sense and Denotation"), in Zeitschrift für Philosophie und philosophische Kritik, C (1892): 25-50
- "Über Begriff und Gegenstand" ("On Concept and Object"), in Vierteljahresschrift für wissenschaftliche Philosophie, XVI (1892): 192-205
- Grundgesetze der Arithmetik ("Basic Laws of Arithmetic"), Jena: Verlag Hermann Pohle, Band I (1893), Band II (1903)
- Was ist eine Funktion? ("What is a Function?"), in Festschrift Ludwig Boltzmann gewidmet zum sechzigsten Geburtstage, February 20, 1904, S. Meyer (ed.), Leipzig, 1904, pp. 656-666
- "Der Gedanke" ("The Thought") Eine logische Untersuchung, in Beiträge zur Philosophie des Deutschen Idealismus I (1918-1919): 58-77
- "Die Verneinung" ("Negation"), in Beiträge zur Philosophie des deutschen Idealismus I (1918-1919): 143-157
- "Gedankengefüge" ("Compound Thought"), in Beiträge zur Philosophie des Deutschen Idealismus III (1923): 36-51 Frege intended these last three papers to be published in a book to be called Logical Investigations; in 1975 they were posthumously published (in English translation, at least) under this title. A complete chronological [http://www.ocf.berkeley.edu/~brianwc/frege/fenglish.html bibliography of Frege's works] and their English translations is provided by [http://www.ocf.berkeley.edu/~brianwc/frege/ Gottlob Frege (1848-1925)], which attempts to be a comprehensive resource of Fregean material available on the web.

External links

- [http://plato.stanford.edu/entries/frege/ "Gottlob Frege" in Stanford Encyclopedia of Philosophy]
- [http://plato.stanford.edu/entries/frege-logic/ "Frege's Logic" in Stanford Encyclopedia of Philosophy]
- [http://www.utm.edu/research/iep/f/frege.htm "Gottlob Frege" in Internet Encyclopedia of Philosophy]
- [http://www.formalontology.it/fregeg.htm Frege on Being, Existence and Truth] Frege, Gottlob Frege, Gottlob Frege, Gottlob Frege, Gottlob Frege, Gottlob Frege, Gottlob Frege, Gottlob Frege, Gottlob Frege, Gottlob Frege, Gottlob Frege, Gottlob Frege, Gottlob ko:고틀로프 프레게 ja:ゴットロープ・フレーゲ

Alfred North Whitehead

Alfred North Whitehead, OM (February 15 1861, Ramsgate, Kent, UK – December 30 1947, Cambridge, MA) was a British philosopher, physicist, and mathematician who worked in logic, mathematics, philosophy of science and metaphysics. His best known work in mathematics is the Principia Mathematica which he wrote with Bertrand Russell. Whitehead did most of his work in mathematics while at Cambridge (UK) from 1884 to 1910. The next phase of his career, at London (University College London and Imperial College London) from 1910 to 1924, dealt with philosophies of science and education. In 1924 he moved to Harvard University for the last phase. While there, Whitehead is perhaps most well known for conceiving process philosophy. He was invited to give the Gifford Lectures for 1927 at the University of Edinburgh, which resulted in the formidable but respected book Process and Reality. Process philosophy was later developed into process theology by theologian/philosophers Charles Hartshorne, John B Cobb, Jr, and David Ray Griffin. Process theology is a way of understanding God and the universe found to be fruitful by some in Christian and Jewish faiths. Just as the entire universe is in constant flow and change, God, as source of the universe, is viewed as growing and changing. Whitehead's rejection of mind-body dualism is similar to elements in oriental faith traditions such as Buddhism. In physics his best known work was a theory of gravity that competed with Einstein's general relativity for many decades. Whitehead's theory received less attention than Einstein's, and was generally discredited by 1972 with a comparison of experimental and predicted variability of the gravitational constant G. See [http://www.asahi-net.or.jp/~sn2y-tnk/tanaka_4_4.htm A Comparison with Einstein's Theory], or Clifford Will's book, Theory and Experiment in Gravitational Physics, Cambridge University Press 1993 (ISBN 0521439736 ). Whitehead's political views were, roughly, libertarian without the label. He wrote: "Now the intercourse between individuals and between social groups takes one of two forms, force or persuasion. Commerce is the great example of intercourse by way of persuasion. War, slavery, and governmental compulsion exemplify the reign of force."

Books

- Alfred North Whitehead and Bertrand Russell, Principia Mathematica to
- 56, (originally 1910), Cambridge University Press, 2nd edition of abridged vol. 1, 2002 paperback, ISBN 0521626064
- A N Whitehead, Introduction To Mathematics, (orig. 1911), Oxford University Press, 1990 paperback, 191 pages, ISBN 0195002113
- A N Whitehead, The Concept of Nature, (orig. pub. 1920), (The Tarner Lectures delivered at Trinity College in November 1919 on philosophy of science), Cambridge University Press 1964, Prometheus Books, 2004 paperback, 208 pages, ISBN 1591022142
- A N Whitehead, Science and the Modern World, (orig. 1925), Talcott Parsons (preface), Free Press (Simon & Schuster), 1997 paperback, 212 pages, ISBN 0684836394
- A N Whitehead, Religion in the Making, (orig. 1926), New American Library, reprint 1974, ISBN 0452007232, Fordham University Press, 1996 hardcover with Judith A. Jones introduction, 256 pages , ISBN 0823216454; paperback, 175 pages, ISBN 0823216462
- A N Whitehead, Symbolism, Its Meaning and Effect: Barbour-Page Lectures, University of Virginia, 1927, Fordham University Press, 1985, paperback, 88 pages, ISBN 082321138X
- A N Whitehead, The Aims of Education and Other Essays, (orig. 1929), Free Press, 1985 paperback, ISBN 0029351804
- A N Whitehead, Process and Reality: An Essay in Cosmology, (orig. 1929), David Ray Griffin and Donald W. Sherburne (editors), Free Press, 1979 paperback, ISBN 0029345707
- A N Whitehead, Function of Reason, (orig. 1929), Beacon Press, 1971 paperback, ISBN 0807015733
- A N Whitehead, Adventures of Ideas, (orig. 1933), Free Press, 1967 paperback, 307 pages, ISBN 0029351707
- A N Whitehead, Modes of Thought, (orig. 1938), Free Press, 1968 paperback, 179 pages, ISBN 002935210X
- A N Whitehead, Dialogues of Alfred North Whitehead, Lucien Price (editor), Sir Ross David (introduction), (orig. 1954), Greenwood Press Reprint, 1977 hardback, 396 pages, ISBN 0837193419; David R. Godine Publisher edition, Caldwell Titcomb (forward), 2001 paperback, 385 pages, ISBN 1-56792-129-9

External links

- [http://plato.stanford.edu/entries/whitehead/ Stanford Encyclopedia of Philosophy]
- [http://arxiv.org/abs/physics/0505027 Whitehead's Principle of Relativity - Lectures by J. L. Synge] on arXiv.org
- Whitehead, Alfred North Whitehead, Alfred North Whitehead, Alfred North Whitehead, Alfred North Whitehead, Alfred North Whitehead, Alfred North Whitehead, Alfred North ko:앨프리드 노스 화이트헤드 ja:アルフレッド・ノース・ホワイトヘッド

Defeasible reasoning

Defeasible reasoning (sometimes called defeasible logic) is the study of forms of reasoning that, while convincing, are not as formal and rigorous as deductive reasoning. It has been discussed in philosophy and, more recently, in artificial intelligence. Other alternatives to deductive reasoning include inductive reasoning and retroductive reasoning. These are not traditionally covered by most uses of the term "defeasible reasoning".

Origins in philosophy

Though Aristotle differentiated the forms of reasoning that are valid for logic and philosophy from the more general ones that are used in everyday life (see dialectics and rhetoric), subsequent philosophers mainly concentrated on deductive reasoning. It wasn't until logical positivism started falling out of favour that philosophers like Roderick Chisholm and John L. Pollock renewed an interest in defeasible reasoning.

Artificial intelligence

Around the same time period, developments in artificial intelligence led pioneers like John McCarthy and Patrick J. Hayes to represent a form of defeasible reasoning as they encountered the frame problem and the qualification problem. Several forms of defeasible reasoning were proposed:
- McCarthy suggested that the solution was in a logical principle of circumscription
- Raymond Reiter proposed a system of default logic and a formalization of the closed world assumption
- McDermott and Doyle proposed non-monotonic logic
- Robert C. Moore proposed autoepistemic logic

External links

- [http://plato.stanford.edu/entries/reasoning-defeasible/ Article on Defeasible Reasoning] in the Stanford Encyclopedia of Philosophy
- [http://william-king.www.drexel.edu/top/prin/txt/Intro/Eco112c.html An example of defeasible reasoning in action] Defeasible reasoning Defeasible reasoning

Inductive reasoning

Examples

Validity

Types of inductive reasoning

Bayesian inference

External links

Propositional calculus

In mathematical logic the propositional calculus or sentential calculus is a formal deduction system whose atomic formulas are propositional variables. (Compare this to the predicate calculus which is quantificational and whose atomic formulas are propositional functions, and modal logic which may be non-truth-functional.) A calculus is a logical system which is used to prove valid formulas (i.e. its theorems) and arguments. It is a set of axioms (which may be an empty or countably infinite set) or axiom schemata, and inference rules for deriving valid inferences. A formal grammar (or syntax) recursively defines the expressions and well-formed formulas (wffs) of the language. In addition a semantics is given which defines truth and valuations (or interpretations). It allows us to determine which wffs are valid (i.e. theorems). In the propositional calculus the language consists of propositional variables (or placeholders) and sentential operators (or connectives). A wff is any atomic formula or a formula built up from sentential operators. In what follows we will outline a standard propositional calculus. Many different formulations exist which are all more or less equivalent but differ in (1) their language (i.e. which operators and variables are part of the language); (2) which (if any) axioms they have; (3) which inference rules are employed.

Grammar

The language consists of: # The capital letters of the alphabet, standing as propositional variables. These are atomic formulas. Conventionally, either the Latin alphabet (A, B, C) or the Greek alphabet (χ, φ, ψ) is used, but the two are not mixed. # Symbols denoting the following connectives (or logical operators): ¬, ∧, ∨, →, ↔. (We may do with fewer operators (and thus symbols) by having some abbreviate others — e.g. P → Q is equivalent to ¬ P ∨ Q.) # The left and right parentheses: (, ). The set of well-formed formulas (wffs) is recursively defined by the following rules: # Basis: Letters of the alphabet (usually capitalized such as A, B, φ, χ, etc.) are wffs. # Inductive clause I: If φ is a wff, then ¬ φ is a wff. # Inductive clause II: If φ and ψ are wffs, then (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), and (φ ↔ ψ) are wffs. # Closure clause: Nothing else is a wff. Repeated applications of these three rules permit the generation of complex wffs. For example: # By rule 1, A is a wff. # By rule 2, ¬ A is a wff. # By rule 1, B is a wff. # By rule 3, ( ¬ A ∨ B ) is a wff.

Calculus

For simplicity, we will use a natural deduction system, which has no axioms; or, equivalently, which has an empty axiom set. Derivations using our calculus will be laid out in the form of a list of numbered lines, with a single wff and a justification on each line. Any premises will be at the top, with a "p" for their justification. The conclusion will be on the last line. A derivation will be considered complete if every line follows from previous ones by correct application of a rule. (For a contrasting approach, see proof-trees).

Axioms

Our axiom set is the empty set.

Inference rules

Our propositional calculus has ten inference rules. These rules allow us to derive other true formulas given a set of formulas that are assumed to be true. The first eight simply state that we can infer certain wffs from other wffs. The last two rules however use hypothetical reasoning in the sense that in the premise of the rule we temporarily assume an (unproven) hypothesis to be part of the set of inferred formulas to see if we can infer a certain other formula. Since the first eight rules don't do this they are usually described as non-hypothetical rules, and the last two as hypothetical rules. ; Double negative elimination: From the wff ¬ ¬ φ, we may infer φ ; Conjunction introduction: From any wff φ and any wff ψ, we may infer ( φ ∧ ψ ). ; Conjunction elimination: From any wff ( φ ∧ ψ ), we may infer φ and ψ ; Disjunction introduction: From any wff φ, we may infer (φ ∨ ψ) and (ψ ∨ φ), where ψ is any wff. ; Disjunction elimination: From the wffs of the form ( φ ∨ ψ ), ( φ → χ ), and ( ψ → χ ), we may infer χ. ; Biconditional introduction: From the wffs of the form ( φ → ψ ) and ( ψ → φ ), we may infer ( φ ↔ ψ ). ; Biconditional elimination: From the wff ( φ ↔ ψ ), we may infer ( φ → ψ ) and ( ψ → φ ). ; Modus ponens: From the wffs of the form φ and ( φ → ψ ), we may infer ψ. ; Conditional proof: If ψ can be derived while assuming the hypothesis φ, we may infer ( φ → ψ ). ; Reductio ad absurdum: If we can derive both ψ and ¬ ψ while assuming the hypothesis φ, we may infer ¬ φ.

Example of a proof

The following is an example of a (syntactical) demonstration:
Prove:

A \rightarrow A

Proof:
Interpret

A \vdash A

as "Assuming A, infer A". Read

\vdash A \rightarrow A

as "Assuming nothing, infer that A implies A," or "It is a tautology that A implies A," or "It is always true that A implies A."

Soundness and completeness of the rules

The crucial properties of this set of rules are that they are sound and complete. Informally this means that the rules are correct and that no other rules are required. These claims can be made more formal as follows. We define a truth assignment as a function that maps propositional variables to true or false. Informally such a truth assignment can be understood as the description of a possible state of affairs (or possible worlds) where certain statements are true and others are not. The semantics of formulas can then be formalized by defining for which "state of affairs" they are considered to be true, which is what is done by the following definition. We define when such a truth assignment A satisfies a certain wff with the following rules:
- A satisfies the propositional variable P iff A(P) = true
- A satisfies ¬ φ iff A does not satisfy φ
- A satisfies (φ ∧ ψ) iff A satisfies both φ and ψ
- A satisfies (φ ∨ ψ) iff A satisfies at least one of either φ or ψ
- A satisfies (φ → ψ) iff it is not the case that A satisfies φ but not ψ
- A satisfies (φ ↔ ψ) iff A satisfies both φ and ψ or satisfies neither one of them With this definition we can now formalize what it means for a formula φ to be implied by a certain set S of formulas. Informally this is true if in all worlds that are possible given the set of formulas S the formula φ also holds. This leads to the following formal definition: We say that a set S of wffs semantically entails (or implies) a certain wff φ if all truth assignments that satisfy all the formulas in S also satisfy φ. Finally we define syntactical entailment such that φ is syntactically entailed by S iff we can derive it with the inference rules that were presented above in a finite number of steps. This allows us to formulate exactly what it means for the set of inference rules to be sound and complete: ; Soundness : If the set of wffs S syntactically entails wff φ then S semantically entails φ ; Completeness : If the set of wffs S semantically entails wff φ then S syntactically entails φ For the above set of rules this is indeed the case.
Sketch of a soundness proof
(For most logical systems, this is the comparatively "simple" direction of proof) Notational conventions: Let "G" be a variable ranging over sets of sentences. Let "A", "B", and "C" range over sentences. For "G syntactically entails A" we write "G proves A". For "G semantically entails A" we write "G implies A". We want to show: (A)(G)(If G proves A then G implies A) We note that "G proves A" has an inductive definition, and that gives us the immediate resources for demonstrating claims of the form "If G proves A then . . ." So our proof proceeds by induction.
- I. Basis. Show: If A is a member of G then G implies A
- [II. Basis. Show: If A is an axiom, then G implies A]
- III. Inductive step: (a) Assume for arbitrary G and A that if G proves A then G implies A. (If necessary, assume this for arbitrary B, C, etc. as well) ::(b) For each possible application of a rule of inference to A, leading to a new sentence B, show that G implies B. (N.B. Basis Step II can be omitted for the above calculus, which is a natural deduction system and so has no axioms. Basically, it involves showing that each of the axioms is a (semantic) logical truth.) The Basis step(s) demonstrate(s) that the simplest provable sentences from G are also implied by G, for any G. (The is simple, since the semantic fact that a set implies any of its members, is also trivial.) The Inductive step will systematically cover all the further sentences that might be provable--by considering each case where we might reach a logical conclusion using an inference rule--and shows that if a new sentence is provable, it is also logically implied. (For example, we might have a rule telling us that from "A" we can derive "A or B". In III.(a) We assume that if A is provable it is implied. We also know that if A is provable then "A or B" is provable. We have to show that then "A or B" too is implied. We do so by appeal to the semantic definition and the assumption we just made. A is provable from G, we assume. So it is also implied by G. So any semantic valuation making all of G true makes A true. But any valuation making A true makes "A or B" true, by the defined semantics for "or". So any valuation which makes all of G true makes "A or B" true. So "A or B" is implied.) Generally, the Inductive step will consist of a lengthy but simple case-by-case analysis of all the rules of inference, showing that each "preserves" semantic implication. By the definition of provability, there are no sentences provable other than by being a member of G, an axiom, or following by a rule; so if all of those are semantically implied, the deduction calculus is sound.
Sketch of completeness proof
(This is usually the much harder direction of proof.) We adopt the same notational conventions as above. We want to show: If G implies A, then G proves A. We proceed by contraposition: We show instead that If G does not prove A then G does not imply A.
- I. G does not prove A. (Assumption)
- II. If G does not prove A, then we can construct an (infinite) "Maximal Set", G
- , which is a superset of G and which also does not prove A.
- (a)Place an "ordering" on all the sentences in the language. (e.g., alphabetical ordering), and number them E1, E2, . . .
- (b)Define a series Gn of sets (G0, G1 . . . )inductively, as follows. (i)G0=G. (ii) If proves A, then G(k+1)=Gk. (iii) If does not prove A, then G(k+1)=
- (c)Define G
- as the union of all the Gn. (That is, G
- is the set of all the sentences that are in any Gn).
- (d) It can be easily shown that (i) G
- contains (is a superset of) G (by (b.i)); (ii) G
- does not prove A (because if it proves A then some sentence was added to some Gn which caused it to prove A; but this was ruled out by definition); and (iii) G
- is a "Maximal Set" (with respect to A): If any more sentences whatever were added to G
- , it would prove A. (Because if it were possible to add any more sentences, they should have been added when they were encountered during the construction of the Gn, again by definition)
- III. If G
- is a Maximal Set (wrt A), then it is "truth-like". This means that it contains the sentence "A" only if it does not contain the sentence not-A; If it contains "A" and contains "If A then B" then it also contains "B"; and so forth.
- IV. If G
- is truth-like there is a "G
- -Canonical" valuation of the language: one that makes every sentence in G
- true and everything outside G
- false while still obeying the laws of semantic composition in the language.
- V. A G
- -canonical valuation will make our original set G all true, and make A false.
- VI. If there is a valuation on which G are true and A is false, then G does not (semantically) imply A. Q.E.D.
Alternative calculus
It is possible to define another version of propositional calculus, which defines most of the syntax of the logical operators by means of axioms, and which uses only one inference rule.
Axioms
Let φ, χ and ψ stand for well-formed formulas. (The wffs themselves would not contain any Greek letters, but only capital Roman letters, connective operators, and parentheses.) Then the axioms are
- THEN-1: φ → (χ → φ)
- THEN-2: (φ → (χ → ψ)) → ((φ → χ) → (φ → ψ))
- AND-1: φ ∧ χ → φ
- AND-2: φ ∧ χ → χ
- AND-3: φ → (χ → (φ ∧ χ))
- OR-1: φ → φ ∨ χ
- OR-2: χ → φ ∨ χ
- OR-3: (φ → ψ) → ((χ → ψ) → (φ ∨ χ → ψ))
- NOT-1: (φ → χ) → ((φ → ¬ χ) → ¬ φ)
- NOT-2: φ → (¬ φ → χ)
- NOT-3: φ ∨ ¬ φ Axiom THEN-2 may be considered to be a "distributive property of implication with respect to implication." Axioms AND-1 and AND-2 correspond to "conjunction elimination". The relation between AND-1 and AND-2 reflects the commutativity of the conjunction operator. Axiom AND-3 corresponds to "conjunction introduction." Axioms OR-1 and OR-2 correspond to "disjunction introduction." The relation between OR-1 and OR-2 reflects the commutativity of the disjunction operator. Axiom NOT-1 corresponds to "reductio ad absurdum." Axiom NOT-2 says that "anything can be deduced from a contradiction." Axiom NOT-3 is called "tertium non datur" (Latin: "a third is not given") and reflects the semantic valuation of propositional formulas: a formula can have a truth-value of either true or false. There is no third truth-value, at least not in classical logic. Intuitionistic logicians do not accept the axiom NOT-3.
Inference rule
The inference rule is modus ponens:
- $\phi, \ \phi \rightarrow \chi \vdash \chi$ . If the double-arrow equivalence operator is also used, then the following "natural" inference rules may be added:
- IFF-1: $\phi \leftrightarrow \chi \vdash \chi \rightarrow \phi$
- IFF-2: $\phi \rightarrow \chi, \ \chi \rightarrow \phi \vdash \phi \leftrightarrow \chi$
Meta-inference rule
Let a demonstration be represented by a sequence, with hypotheses to the left of the turnstile and the conclusion to the right of the turnstile. Then the deduction theorem can be stated as follows: : If the sequence :: $\phi_1, \ \phi_2, \ ... , \ \phi_n, \ \chi \vdash \psi$ : has been demonstrated, then it is also possible to demonstrate the sequence :: $\phi_1, \ \phi_2, \ ..., \ \phi_n \vdash \chi \rightarrow \psi$ . This deduction theorem (DT) is not itself formulated with propositional calculus: it is not a theorem of propositional calculus, but a theorem about propositional calculus. In this sense, it is a meta-theorem, comparable to theorems about the soundness or completeness of propositional calculus. On the other hand, DT is so useful for simplifying the syntactical proof process that it can be considered and used as another inference rule, accompanying modus ponens. In this sense, DT corresponds to the natural conditional proof inference rule which is part of the first version of propositional calculus introduced in this article. The converse of DT is also valid: : If the sequence :: $\phi_1, \ \phi_2, \ ..., \ \phi_n \vdash \chi \rightarrow \psi$ : has been demonstrated, then it is also possible to demonstrate the sequence :: $\phi_1, \ \phi_2, \ ... , \ \phi_n, \ \chi \vdash \psi$ in fact, the validity of the converse of DT is almost trivial compared to that of DT: : If :: $\phi_1, \ ... , \ \phi_n \vdash \chi \rightarrow \psi$ : then :: 1: $\phi_1, \ ... , \ \phi_n, \ \chi \vdash \chi \rightarrow \psi$ :: 2: $\phi_1, \ ... , \ \phi_n, \ \chi \vdash \chi$ : and from (1) and (2) can be deduced :: 3: $\phi_1, \ ... , \ \phi_n, \ \chi \vdash \psi$ : by means of modus ponens, Q.E.D. The converse of DT has powerful implications: it can be used to convert an axiom into an inference rule. For example, the axiom AND-1, : $\vdash \phi \wedge \chi \rightarrow \phi$ can be transformed by means of the converse of the deduction theorem into the inference rule : $\phi \wedge \chi \vdash \phi$ which is conjunction elimination, one of the ten inference rules used in the first version (in this article) of the propositional calculus.
Example of a proof
The following is an example of a (syntactical) demonstration, involving only axioms THEN-1 and THEN-2:
Prove: A → A (Reflexivity of implication).
Proof: :1. (A → ((A → A) → A)) → ((A → (A → A)) → (A → A)) ::Axiom THEN-2 with φ = A, χ = A → A, ψ = A :2. A → ((A → A) → A) ::Axiom THEN-1 with φ = A, χ = A → A :3. (A → (A → A)) → (A → A) ::From (1) and (2) by modus ponens. :4. A → (A → A) ::Axiom THEN-1 with φ = A, χ = A :5. A → A ::From (3) and (4) by modus ponens.
Other logical calculi
Propositional calculus is about the simplest kind of logical calculus in any current use. (Aristotelian "syllogistic" calculus, which is largely supplanted in modern logic, is in some ways simpler--but in other ways more complex--than propositional calculus.) It can be extended in several ways. The most immediate way to develop a more complex logical calculus is to introduce rules that are sensitive to more fine-grained details of the sentences being used. When the "atomic sentences" of propositional logic are broken up into terms, variables, predicates, and quantifiers, they yield first-order logic, or first-order predicate logic, which keeps all the rules of propositional logic and adds some new ones. (For example, from "All dogs are mammals" we may infer "If Rover is a dog then Rover is a mammal.) With the tools of first-order logic it is possible to formulate a number of theories, either with explicit axioms or by rules of inference, that can themselves be treated as logical calculi. Arithmetic is the best known of these; others include set theory and mereology. Modal logic also offers a variety of inferences that cannot be captured in propositional calculus. For example, from "Necessarily p" we may infer that p. From p we may infer "It is possible that p". Many-valued logics are those allowing sentences to have values other than true and false. (For example, neither and both are standard "extra values"; "continuum logic" allows each sentence to have any of an infinite number of "degrees of truth" between true and false.) These logics often require calculational devices quite distinct from propositional calculus.
See also

- List of Boolean algebra topics
- Gödel, Escher, Bach
- Boolean logic
- Frege's propositional calculus
External links

- [http://www.iep.utm.edu/p/prop-log.htm Article on Propositional logic] at the Internet Encyclopedia of Philosophy
- [http://www.ltn.lv/~podnieks/mlog/ml2.htm Introduction to Mathematical Logic] Category:Mathematical logic th:แคลคูลัสเชิงประพจน์

Retroductive reasoning

Similar to induction, but predicated on a known or assumed relationary rule(s) and an observation(s) that contains at least one of the predicates(predictors) of the rule. Another predicate(s) of the relationary rule is then generalized to the observation due to the coincidence of the other predicate(s) in both the observation and the rule. This is commonly applied in police work to determine the initial suspects of a crime via means, motive and opportunity. The most common forms of logic systems built up through retroductive reasoning involve or are related to complexity theory.

External links

[http://www.cuyamaca.net/bruce.thompson/Fallacies/retroduction.asp Retroduction]

Category:Logic

Logic, in its purest form, is the reasoning used to take a set of assumptions and reach a conclusion. More specifically, logic is the study of prescriptive systems of reasoning, that is, systems proposed as guides for how people (as well, perhaps, as other intelligent beings/machines/systems) ought to reason. Logic says which forms of inference are valid and which are not. Traditionally, logic is studied as a branch of philosophy, but it can also be considered a branch of mathematics and computer science. How people actually reason is usually studied under other headings, including cognitive psychology. :See table of logic symbols for explanations of symbols used in logic. Category:Abstraction Category:Branches of philosophy Category:Interdisciplinary fields ja:Category:論理学

Gillett Grove, Iowa

Gillett Grove esas urbo en Clay Komtio, Iowa. Segun la 2000 kontado, la populo esas 55.

Geografio

2000 Gillett Grove jacas a . Segun la Usana Kontado Ministerio, la urbo havas tota areo di 0.5 km² (0.2 mi²). 0.5 km² (0.2 mi²) di qua esas lando e nulo di qua esas aquo.

Demografio

Segun la kontado di 2000 esas 55 homi, 28 hemanari, e 19 familii qui rezidas en la urbo. La lojanto-denseso esas 111.8/km² (291.6/mi²). Esas 30 domi kun mezala denseso di 61.0/km² (159.1/mi²). La rasi en la urbo inkludas 98.18% Blanka, 0.00% Nigra o Afrika-usana, 0.00% Indijena amerikana, 0.00% Aziana, 0.00% Pacifika Insulana, 0.00% de altra rasi, e 1.82% de du o plu rasi. 0.00% de la populo esas Hispania o Latina de irga raso. Esas 28 heminari di qua 32.1% havas pueri sub la evo di 18 en la domo, 46.4% esas mariajita e habitas kune, 10.7% havas homina domo-maestro sen spozulo, e 32.1% esas ne-familii. 32.1% de omna hemanari facesas ek individui e 10.7% havas ulo qua habitas sole qua evas 65 yari o plu evoza. La mezala grandeso di hemanari esas 1.96 e la mezala grandeso di familii esas 2.21. La nombro di lojanti e lia evi esas: 18.2% sub la evo di 18, 10.9% de 18 til 24, 21.8% de 25 til 44, 25.5% de 45 til 64, e 23.6% qui evas 65 yari o plu evoza. La mezala evo esas 44 yari. Po 100 homini esas 89.7 homuli. Po singla 100 homini 18 yari o plus esas 87.5 homuli. La mezala revenuo di hemanaro en la urbo esas $21,429, e la mezala revenuo por familio esas $17,292. Homuli havas mezala revenuo di $18,750 kontre $21,250 por homini. La revenuo per capita por la urbo esas $12,337. 28.3% de la populo e 13.3% de familii esas sub la povreso-lineo. De la tota populo, 18.2% di qui sub la evo di 18 e 0.0% de ti qui evas 65 o plus habitas sub la povreso-lineo. Category:Urbi en Iowa Category:Clay Komtio, Iowa

Opony gu Links Malaga accommodation prag hotel gry zr�czno�ciowe

aukcje internetowe EuroFont 2.5 PicasSo2 Iwona-program k-little code fotografia

:: RELATED NEWS ::

Община Ветово
Община Ветово се намира в Северна България и е една от съставните общини на Русенска област. Общината има 7 населени места с общо население 18096 жители (12 населени места с общо население 11767 жители