First-order predicate calculus or first-order logic is a theory in Symbolic logic that formalizes quantified statements such as "there exists an object with the property that..." or "for all objects, the following is true...". First-order logic is distinguished from higher-order logic in that it does not allow statements such as "for every property, the following is true..." or "there exists a set of objects such that...". Nevertheless, first-order logic is strong enough to formalize all of Set theory and thereby virtually all of Mathematics. It is the classical logical theory underlying mathematics.
Like any logical theory, first-order calculus consists of
There are two types of axioms: the logical axioms which embody the general truths about proper reasoning involving quantified statements, and the axioms describing the subject matter at hand, for instance axioms describing sets in set theory or axioms describing numbers in arithmetic.
While the set of inference rules in first-order calculus is finite, the set of axioms may very well be and often is infinite. However we require that there is a general Algorithm which can decide for a given well-formed formula whether it is an axiom or not. Furthermore, there should be an algorithm which can decide whether a given application of an inference rule is correct or not.
The well-formed formulas contain
The object, predicate and function constants will typically depend on the particular domain we are talking about.
Instead of giving the lengthy definition of well-formed formulas, we will simply look at some examples from arithmetic together with their ordinary interpretation. Our domain here is the set of natural numbers:
For every number x there exists a bigger number y. That's true.
There exists a number y which is bigger than every number x. That's not true.
If a number x is divisible by 6, then it is also divisible by 3. True.
There exists a number x such that there doesn't exist a smaller number y. True (take x=0).
Now one would have to write down 15 logical axioms and 2 inference rules to completely specify the first-order calculus. How can one be sure that those axioms and rules are enough? This is the subject of Gödel's completeness theorem: if you start out with some subject matter axioms and you look at a certain statement, then it is possible to prove that statement using only the subject matter axioms, the 15 logical axioms and the two inference rules if and only if the statement is true in every domain in which the subject matter axioms are true.
The Peano axioms for the natural numbers are sometimes formulated as second-order statements (the induction axiom talks about all "properties" or all "sets of numbers"), but this is not necessary if one is willing to allow infinitely many first-order axioms. A first-order version of the Peano axioms follows.
We are using the object constants 0 and 1, the function constants + and *, and the predicate constant =. Here are the axioms:
Axioms 1, 2 and 7 are the traditional Peano axioms while axioms 3-6 serve to define addition and multiplication. If one omits the function constant * and axioms 5 and 6 and allows in scheme 7 only formulas without *, then one gets the very interesting Presburger arithmetic
A logical calculus is a formal, axiomatic system for recursively generating well-formed formulas (wffs). Essentially, it's a definition of a vocabulary, rules for the formation of well-formed formulas (wffs), and rules of inference permitting the generation of all valid argument forms expressible in the calculus.
The propositional calculus is the foundation of Symbolic logic; more complex logical calculi are usually defined by adding new operators and rules of transformation to it. It is generally defined as follows:
The vocabulary is composed of:
The rules for the formation of wffs:
Repeated applications of these three rules permit the generation of complex wffs. For example:
The propositional calculus has ten inference rules. The first eight are non-hypothetical, meaning that they do not involve hypothetical reasoning: specifically, the introduction of hypothetical premises is not used; the last two rules are hypothetical. These rules are introduction and elimination rules for each logical operator, used for deriving argument forms.
Negative elimination is basically the rule of double negatives: "it's not the case that it's not raining" means that it's raining. Likewise, it's logically consistent to claim that "it's raining" means that "it's not not raining".
Formally:
¬ ¬ A ∴ A also
¬ ¬ ¬ A ∴ ¬ A
Conjunction introduction is the inference that, if A is true, and B is true, then the conjunction A and B is true.
For example, if it's true that it's raining, and it's true that I'm inside, then it's true that it's raining, and I'm inside.
Formally:
A B ∴ ( A ∧ B )
Conjunction elimination is the inference that, if the conjunction A and B is true, then A is true, and B is true.
For instance, if it's true that it's raining, and I'm inside, then one may assert either term of the conjunction alone: it's raining, or I'm inside.
Formally:
( A ∧ B ) ∴ A or
( A ∧ B ) ∴ B
Disjunction introduction is the principle that, if A is true, then it's true that either A or B is true.
For example, if it's true that it's raining outside, it's trivially true that either it's raining outside, or my car is freshly waxed. Since a disjunction is true if at least one of the terms is true, and we know that one of the terms is true, the second term is irrelevant for determining the truth value of the disjunction.
Formally:
A ∴ ( A ∨ B )
Disjunction elimination is the inference that, if A or B is true, and both A and B entail C, then we may justifiably infer C.
For example, it's true that either I'm inside or I'm outside. It's also true that if I'm inside, I have my wallet on me. It's also true that if I'm outside, I have my wallet on me. Given these three premises, it follows that I have my wallet on me.
Formally:
( A ∨ B ) ( A → C ) ( B → C ) ∴ C
Biconditional introduction is the inference that, if B follows from A, and A follows from B, then A if and only if B.
For example: if I'm breathing, then I'm alive; also, if I'm alive, then I'm breathing. Therefore, I'm breathing if and only if I'm alive.
Formally:
( A → B ) ( B → A ) ∴ ( A ↔ B )
Biconditional elimination allows one to infer a conditional from a biconditional: if ( A ↔ B ) is true, then one may infer one direction of the biconditional, either ( A → B ) or ( B → A ).
For example, if it's true that I'm breathing if and only if I'm alive, then it's true that if I'm breathing, I'm alive; likewise, it's true that if I'm alive, I'm breathing.
Formally:
( A ↔ B ) ∴ ( A → B ) also
( A ↔ B ) ∴ ( B → A )
Modus ponens (Latin: mode that affirms) is a valid, simple Argument form:
or in symbols:
P → Q
P
∴ Q
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:
For an amusing dialog that problematizes modus ponens, see Lewis Carroll's "What the Tortoise Said to Achilles".
Conditional proof takes the form of asserting a conditional, and proving that the premise or antecedent of the conditional necessarily leads to the conclusion. Proving this requires assuming the premise and deriving, from that assumption, the consequent of the conditional. By proving the connection between the antecedent and the consequent, the assumption of the antecedent is justified post hoc.
For example, I claim that "if you don't leave now, you'll be late for work". I prove it with the following argument:
∴ If you don't leave now, you'll be late for work.
Note that I haven't proved that you'll be late for work: I've only proven the conditional, that the consequent follows necessarily from the antecedent.
Introducing an hypothesis means adding a wff to a derivation not originally present as a premise; discharging the hypothesis means eliminating the wff justifiably--any wffs correctly derived from the hypothesis justify the introduction of the hypothesis after the fact.
With wffs and rules of inference, it's possible to derive wffs; the
derivation is a valid argument form, while the derived wff is known as a
Lemma.
Reductio ad absurdum (from Latin Reduced to an absurdity) is a tool of logic, also known as "proof by contradiction".
Say we wish to prove hypothesis A. The procedure is to show that assuming "not A" (i.e. that A is false) leads to a logical contradiction. Thus A cannot be false, and must therefore be true. For examples, see Irrational number and Cantor's diagonal argument.
It is important to note that to form a valid proof, it must be demonstrated that "not A" implies a property that is actually false or actually incompatible with "not A". The danger here is the logical fallacy of argument from lack of imagination, where it is proven that "not A" implies a property "B", which looks false, but is not really proven to be false. Historical examples of this fallacy include false proofs of the fifth postulate a.k.a. parallel postulate of Euclid (see Non-Euclidean geometry).
Symbolic logic, or formal or deductive logic, is an attempt to codify and formalize the processes of reasoning, or logic. Logical statements are expressed as symbolic strings, in a precise, compact and unambiguous notation (sometimes described as a logical calculus), similar to notations used in mathematics. Axioms, statements which are accepted without proof, are identified, and the valid rules of argumentation (transformation rules) are defined.
There are many different systems of symbolic logic. A system of symbolic logic has a number of components: the set of acceptable sentences, called well-formed formulas (or wffs); transformation rules for deriving new formulas from one or more initial formulas; the set of axioms, which is a subset of the set of wffs. The sets of wffs and axioms can be finite or infinite, so long as they are recursive; i.e. so long as there exists a procedure for determining whether any given sentence is a wff or axiom, which could be carried out in a finite number of steps by a device such as a Turing machine (sometimes, it is enough to require that these sets be recursively enumerable).
The theorems of the system are the axioms and all the wffs that can be derived from the axioms by a finite number of applications of the transformation rules. In systems of natural deduction the set of axioms is empty and the transformation rules correspond to patterns of reasoning such as modus ponens whose validity, or truth-preserving nature, is easily recognized.
For a symbolic logic system to be useful it helps to have two additional properties; soundness and completeness. These properties relate the system of symbolic logic to some underlying model. The property of soundness states that if a theorem can be proven in the symbolic system then it is also true in the model. The property of completeness states that if the theorem is true in a model, then there is some proof for it in the associated symbolic logic. A symbolic logic is said to be determined by a model if it is both sound and complete. Logics of this kind are useful for systems of mechanical theorem proving.
Metalogic is the study of different systems of symbolic logic, and their properties. We can not only prove statements in a logical system; we can also prove statements about logical systems. The most important result along these lines are Gödel's incompleteness theorems which essentially show that every sufficiently powerful logical system does contain sentences which can be neither proved nor refuted from within the system.
There are three main types of logical systems which are used: propositional calculus, predicate calculus, and modal logic.
Propositional logic deals with the logic of individual sentences. The primary system here is the classical system, which is the system most commonly used. Various alternatives to the classical system have been studied, including:
Predicate logic extends propositional calculus to deal with predication and quantification. Again we have a classical system, and various deviations from this system. Most of the different systems of propositional calculus can be extended in this manner to produce systems of predicate calculus. There are two main varieties of systems of predicate calculus: first-order predicate calculus, which allows quantification over objects and is the standard logic used in mathematics (see set theory); and higher-order predicate calculus, which permits in addition quantification over predicates and predication of predicates.
There exist proofs for the soundness and completeness of both predicate and first order logic (see Goedels completeness theorem). Second and higher order logics are not complete however; in other words in all second and higher order logics there are theorems which are true in any model but are not provable within the symbolic system.
The term modal logic has two meanings. In a restricted sense, it means the logic of necessity and possibility. But more broadly, it also includes other logics with a similar structure: deontic logics (which deal with ideas of permission and obligation), temporal logics (which deal with the relationships of past, present and future between events), and doxastic logic (which deals with belief). What all these systems have in common is that they involve the application of unary operators (called modal operators) to statements of either propositional or predicate calculus. It is in this broader sense that the term is used here.
The various systems of modal logic include K, M, S4, S5 and B. The systems differ in having different axioms.
In epistemology, an axiom is a self-evident truth upon which other knowledge must rest, from which other knowledge is built up. To say the least, not all epistemologists agree that axioms, understood in that sense, exist.
As the word "axiom" is understood in mathematics, an axiom is not a proposition that is self-evident. Rather, it simply means a starting point in a logical system. For example, in some rings, the operation of multiplication is commutative, and in some it is not; those rings in which it is are said to satisfy the "axiom of commutativity of multiplication." Another name for an axiom is postulate. An axiom is an elementary basis for a formal logic system that together with the rules of inference define a logic.
For instance, (misquoting Peano) simple arithmetic including addition can be defined and many theorems proven by assuming
Using these axioms, and defining the customary short names 1, 2, 3, and so on for inc(0), inc(inc(0)), inc(inc(inc(0))) respectively, we can show that:
and
1 + 2 = 1 + inc(1) Expansion of abbreviation (2 = inc(1))
1 + 2 = inc(1) + 1 Axiom 4
1 + 2 = 2 + 1 Abbreviation (2 = inc(1))
1 + 2 = 2 + inc(0) Expansion of abbreviation (1 = inc(0))
1 + 2 = inc(2) + 0 Axiom 4
1 + 2 = 3 Axiom 3
Any fact that we can derive from the axioms need not be an axiom. Anything that we cannot derive from the axioms and for which we also cannot derive the negation might reasonably added as an axiom.
Probably the most famous very early set of axiom are the 4+1 postulates of Euclid. These turn out to be fairly incomplete, actually, and many more postulates are necessary to completely characterize his geometry (Hilbert used 23).
I say 4+1 since the 5th postulate (through a point outside a line there is exactly one parallel) was suspected to be derivable from the first 4 for nearly two millennia. 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. The general theory of relativity is essentially a claim that mass gives space hyperbolic geometry.
The fact that alternative forms of geometry might exist was very troubling to mathematicians of the 19th century and in similar developments, say Boolean Algebra, there were generally elaborate efforts taken to derive the system from normal arithmetic systems. 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 algebraicly 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 twentieth century, Gödel's Incompleteness Theorem showed that no explicit list of axioms sufficiently large for ordinary mathematics could be both (1) complete (i.e. every statement can be either proved or disproved) and (2) consistent (i.e. no statement can be both proved and disproved).
Giuseppe Peano proposed the following 5 axioms for the natural numbers; they have come to be known as the Peano axioms or Peano postulates.
These axioms are sometimes paraphrased differently, starting at 1 instead of 0. These axioms are given here in a second-order predicate calculus form. See first-order predicate calculus for a way to rephrase these axioms to be first-order.
Although natural numbers satisfy these axioms, there are other, nonstandard models of arbitrary large cardinality - by Compactness theorem the existence of infinite natural numbers cannot be excluded in any axiomatization.
When the axioms were first proposed, people such as Bertrand Russell agreed these axioms implicitly defined what we mean by a "natural number". Henri Poincaré was more cautious, saying they only defined natural numbers if they were consistent. If a proof can exist that starts from just these axioms, and derives a contradiction such as P AND NOT P, then the axioms are inconsistent, and don't really define anything. David Hilbert posed a problem of proving consistency using only finite logic as one of the problems on his famous list. The motivation was to eliminate infinity, by justifying it with this proof, and show that it brings nothing new.
But in 1931, Kurt Goedel in his celebrated Second Incompleteness Theorem showed such a proof cannot exist. It is even impossible to prove consistency of Peano arithmetic while assuming the axioms themselves. Furthermore, we can never prove that any axiom system is consistent within the system itself, if it is at least as strong as Peano's axioms.
In 1936, Gerhard Gentzen proved the consistency of Peano's axioms, using transfinite induction. This was a proof using logic alone, but of course infinite. It gives an algorithm for simplifying a possible proof of contradiction by a series of simple transformations, until it becomes very short. To see that it becomes very short we need transfinite induction. Gentzen's proof has been humorously called "assuming the dubious to prove the obvious".
All mathematicians assume that Peano arithmetic is consistent, although this relies on intuition only. However, early forms of naive set theory also intuitively looked consistent, before the inconsistencies were discovered. This has been a source of confusion for a number of people, especially nonmathematicians.
The point is that we do have to rely on our intuition, and that it brings something new. Roger Penrose has argued that this intuition is what differs men from machines, but his arguments are dubious. The modern set theory often consideres axioms postulating existence of large cardinals - none of them can be proved within set theory, nor is it possible to prove consistency of these axioms. But mathematicians generally do not exclude possibility that some of these axiom systems are inconsistent. The intuition here is much less clear than in the case of natural numbers. Some people argue that even Peano arithmetic could be inconsistent - since intuition is not really a reliable source of truth. This argument can be extended and make us doubt even finite logic itself - these questions go back to Kant and his famous Critique of Pure Reason.
A theorem is a statement which can be proven true within some logical framework. Proving theorems is a central activity of mathematics. Note that 'theorem' is distinct from, but related to, 'theory'.
A mathematical statement which is believed to be true but has not been proven is known as a conjecture. See mathematics for a list of famous theorems and conjectures.
In mathematics, a logical system consists of a basic set of axioms, as well as a process of inference, which allows to derive new theorems from axioms and other theorems that have been derived earlier.
While in propositional logic, any proven statement is called a theorem, in general mathematics a statement must be interesting or important in some way to be called a theorem. Less important statements are called:
Recursion is a way of specifying a process by means of itself. More precisely (and to dispel the appearance of circularity in the definition), "complicated" instances of the process are defined in terms of "simpler" instances, and the "simplest" instances are given explicitly.
Examples of mathematical objects often defined recursively are functions and sets.
The canonical example of a recursively defined function is the following definition of the factorial function f(n):
Given this definition, also called a recurrence relation, we work out f(3) as follows:
f(3) = 3 · f(3-1)
= 3 · f(2)
= 3 · 2 · f(2-1)
= 3 · 2 · f(1)
= 3 · 2 · 1 · f(1-1)
= 3 · 2 · 1 · f(0)
= 3 · 2 · 1 · 1
= 6
Another example is the definition of Fibonacci numbers.
Here is another, perhaps simpler way to understand recursive processes:
A common method of simplification is to divide the problem into subproblems. Such a programming technique is called divide-et-impera or divide and conquer and is a fundamental part of dynamic programming.
Virtually all programming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer keeps track of the various instances of the function by using a stack. Conversely, every recursive function can be transformed into an iterative function by using a stack.
Any function that can be evaluated by a computer can be expressed in terms of
recursive functions, without use of
iteration. Indeed, some languages designed for
logic programming and
functional programming provide recursion as the only means of repetition
directly available to the programmer. Such languages generally make
tail recursion as efficient as iteration, letting programmers express other
repetition structures (such as
Scheme's map and for) in terms of recursion.
Recursion is deeply embedded in the theory of computation, with the theoretical equivalence of recursive functions and Turing machines at the foundation of ideas about the universality of the modern computer.
In set theory there is a theorem guaranteeing that recursively defined functions exist:
The recursion theorem. Given a set X, an element a of X and a function f : X -> X, there is a unique function F : N -> X (where N denotes the set of natural numbers) such that
[A proof of the recursion theorem from set theory is needed]
The canonical example of a recursively defined set is the natural numbers:
The natural numbers can be defined as the smallest set satisfying these two properties.
Another interesting example is the set of all true propositions in an axiomatic system.
[It needs to be pointed out that determining whether a certain object is in a recursively defined set is not an algorithmic task]
Logic is regarded as a branch both of philosophy and of mathematics. A system of logic (or simply "a logic") is a set of rules for reasoning about a given domain. Many different systems of logic have been devised. Such artificial systems of reasoning now find many practical applications in computing.
It was pioneered by Aristotle. Although it is possible that Aristotle himself had been 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.
Today, some other axioms or inference rules would be held to be at least as important. The ultimate goal of logic, if it can be said to have a goal, is valid argumentation and to avoid logical fallacy.
Logic as a science defines the structure of statement and argument and defines 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. Students of traditional logic--which studied standards of definition as well as of argument--were often made to memorize certain argument forms so that they could more easily create better arguments and disprove weaker ones thrown against them. The Jesuits emphasized this so highly, that their students were required to take part in a structured argument session with their peers.
Georg Hegel, who considered himself the modern Aristotle, created a dialectical logic (see The Science of Logic), arguing that all concepts necessarily overcome themselves by cancellation, preservation, and supersession--a process commonly called sublation. Contemporary logicians have naught but scorn for Hegel's logic, which they consider metaphysically spurious.
Mathematical logic or symbolic logic has changed this somewhat by axiomatizing logic and presenting all argument in the form of symbolic strings with very highly constrained forms that represent different statements. The rules of argumentation then are codified as legal transformations on these strings and the allowable starting points (the so-called axioms). Kurt Gödel in the 1930's proved his celebrated incompleteness theorem and thus derailed the idea (put forward by Hilbert and others) that all of reasoned thought could be axiomatized. This sea-change had been foreshadowed by the work of Bertrand Russell and Alfred North Whitehead in mathematics. At roughly the same time, Alonzo Church, Andrei Andreevich Markov, Alan Turing and others were realizing that all sufficiently powerful formal models of computation were equivalent. This led to the computational equivalent of the incompleteness theorem, the Halting Problem.
Propositional Logic can be illustrated either by truth tables or Johnston Diagrams.
In the early 20th century Jan Lukasiewicz investigated the extension of the traditional true/false values to include a third value. Logics have 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. Fuzzy logic is another such system.
In a logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. For example, considering the assertions "It's raining", and "I'm inside", we can form the compound assertions "it's raining, and I'm inside" or "it's not raining" or "if it's raining, then I'm inside."
The basic operators are "not" (¬), "and" (∧), "or" (∨), "conditional" (→), and "biconditional" (↔). "Not" is a unary operator--it takes a single term ( ¬ P ). The rest are binary operators, taking two terms to make a compound statement ( P ∧ Q, P ∨ Q, P → Q, P ↔ Q ).
Note the similarity between the symbols for "and" ( ∧ ) and "set theoretic intersection" ( ∩ ); likewise for "or" ( ∨ ) and "union ( ∪ ). This is not a coincidence: the definition of the intersection uses "and" and the definition of union uses "or".
Truth tables for these connectives:
| P | Q | ¬P | P ∧ Q | P ∨ Q | P → Q | P ↔ Q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
In order to reduce the number of necessary parentheses, one introduces precendence rules: ¬ has higher precedence than ∧, ∧ higher than ∨, and ∨ higher than →. So for example, P ∨ Q ∧ ¬ R → S is short for (P ∨ (Q ∧ (¬ R)) → S.
Note that the logical equivalence of certain compound statements entails that not all of these operators are necessary for a full-blooded logical calculus. For example, ¬ P ∨ Q is logically equivalent to P → Q; since logical equivalence means that equivalent terms may be subsituted for each other in an expression, it's not necessary to have a conditional operator. The five operators listed above are the basic set for the sake of convenience (and brevity).
One can also consider other connectives, such as NAND, XOR and NOR. It can be shown that all connectives can be expressed with NAND alone, and they can also all be expressed with NOR alone.
In boolean algebra, logical negation is a unary logical operator that reverses the truth value of its operand. The negation of the statement p is written in various ways:
It is read as "not p". For instance, if p denotes the statement "today is Saturday", then its negation ~p is the statement "today is not Saturday".
In classical logic, double negation means affirmation, i.e. the statements p and ~(~p) are logically equivalent.
(Redirected from Logical and)
Conjunction, or and, is a logical operator in logical calculi. The symbol "∧" is typically used, and "P ∧ Q" is read "P and Q". In boolean logic, logical conjunction returns TRUE if, and only if, all its inputs are TRUE.
| Input1 | Input2 | Output |
|---|---|---|
| FALSE | FALSE | FALSE |
| FALSE | TRUE | FALSE |
| TRUE | FALSE | FALSE |
| TRUE | TRUE | TRUE |
Intuitively, the logical operator works the same as the common English word "and". The sentence "it's raining, and I'm inside" asserts that two things are simultaneously true: that it's raining outside, and that I'm inside. Logically, this would be denoted by saying that A stands for "it's raining", B stands for "I'm inside", together A ∧ B.
"And" is a binary operator, meaning that it takes two terms and asserts that both are simultaneously true. However, it's common usage to chain conjunctions, such as A ∧ B ∧ C. Properly written, using parenthesis for proper grouping, this would be written as ( ( A ∧ B ) ∧ C ), but the intent is easily understood: the statement is true if A and B and C are simultaneously true. Notice that since "And" is both associative and commutative that the parenthesis are not strictly necessary.
The term "conjunction" can also be applied to a logical statement or formula that contains only literals separated by ANDs. For example, all of the following are considered conjunctions:
A ∧ B ¬A ∧ B A ∧ ¬B ∧ ¬C &and D &and ¬E ¬B
A minor issue of logic and language is the role of the word "but". Logically, the sentence "it's raining, but the sun is shining" is equivalent to "it's raining, and the sun is shining", so logically, "but" is equivalent to "and". However, as demonstrated by the preceding sentences, "but" and "and" are semantically distinct. The former sentences suggests that the latter sentence is usually a contradiction.
One way to resolve this problem of correspondence between symbolic logic and natural language is to observe that the first sentence (using "but"), implies the existence of a hidden but mistaken assumption, namely that the sun doesn't shine when it rains. That implication captures the semantic difference of "and" and "but" without disturbing their logical equivalence.
(Redirected from Logical or)
In logic and mathematics, a disjunction is an "or statement". For example "John skis or Sally swims" is a disjunction.
Note that while in everyday language, use of the word "or" can sometimes mean "either, but not both" (eg "would you like tea or coffee?"), when used formally, "or" allows for both parts of the or statement (its disjuncts) to be true.
The statement "P or Q" is often written as
Such a disjunction is false if both P and Q are false. In all other cases it is true.
More generally a disjunction is a logical formula that can have one or more literals separated only by ORs. A single literal is often considered to be a degenerate disjunction.
For example, all the following are disjunctions:
A ∨ B ¬A ∨ B A ∨ ¬B ∨ ¬C ∨ D ∨ ¬E ¬B
The equivalent notion in set theory is the set theoretic union.
A conditional statement, or simply a conditional for short, is an "if-then" statement, written in the form: 'if P, then Q'. Here, 'P' is the antecedent (the "if" part of the statement) and 'Q' is the consequent (the "then" part). For example, in "If you give me ten dollars, then I will be your best friend," the claim "you give me ten dollars" is the antecedent of the conditional, and "I will be your best friend" is the consequent.
In classical two-valued logic, an argument is said to have validity or to be valid if, and only if, it is the case that, if the premises of the argument are true, then the conclusion must be true. In other words, a valid argument is one where the premises make the conclusion true. There are many other ways to formulate this basic definition: the premises entail the conclusion; it cannot be the case both that the premises are true and the conclusion false; the falsehood of the conclusion entails the falsehood of at least one premise; etc.
A close examination of the definition of 'valid' should make a few things clear about validity. The definition says neither that the premises have to be true nor that that the conclusion has to be true. Validity is a conditional notion: what it says is that if the premises happen to be true, then the conclusion has to be true. As far as validity is concerned the premises might be completely and obviously false. Consider an example of a valid argument:
Bear in mind that 'valid' is a technical term in logic: this is a perfectly valid argument. What does that mean, in this example? Something like this: suppose it were true that all dogs had eight legs; and suppose, just suppose, that the President really were a dog; well, in that absurd imaginary world, the President would have to have eight legs. The conclusion has to be true, if the premises are true. So the argument is valid, even though it has false premises, not to mention a false conclusion.
Validity is not to be confused with soundness; a sound argument is not only valid, its premises are true as well. Not all valid arguments are valid in the loose and popular sense of this word, meaning 'good': not all valid arguments (valid, as this term is used in logic) are good, or successful, as the above example should show.
Argument form is what makes an argument valid. But a valid argument is one where, if the premises are true, then the conclusion must be true (and here is a way to put it more briefly: the premises make the conclusion necessary). Now put these two propositions together and draw a conclusion:
One can see whether the premises make the conclusion necessary just by looking at the form of the argument. That is why argument form is so important. Look, for example, at the following argument form. In fact, any argument that follows this form is valid. You can see that just by reading it:
Now examine the following argument. It fits that form and is (therefore) valid:
A lemma is the proof of a minor claim to be made in the proof of a major result. Of course, the distinction between theorems and lemmas is rather arbitrary, since one mathematician's major result is another's minor claim. Gauss's Lemma and Zorn's Lemma, for example, are interesting enough per se for some authors to stop at the nominal lemma without going on to use that result in any "major" theorem.
The test form of an argument is what results from replacing different words, or sentences, that make up the argument with letters; the letters are called variables.
Some examples of valid arguments forms are modus ponens, modus tollens, and disjunctive syllogism. One invalid argument form is affirming the consequent.
Just as variables can stand for various numbers in mathematics, variables can stand for various words, or sentences, in logic. Argument forms are very important in the study of logic. The parts of argument forms--sentence forms (see below)--are equally important. In a logic course one would learn how to determine what the forms of various sentences and arguments are.
The basic notion of argument form can be introduced with an example. Here is an example of an argument:
A All humans are mortal. Socrates is human. Therefore, Socrates is mortal.
We can rewrite argument A by putting each sentence on its own line:
B
To demonstrate the important notion of the form of an argument, substitute letters for similar items throughout B:
C
All we have done in C is to put 'S' for 'human' and 'humans', 'P' for 'mortal', and 'a' for 'Socrates'; what results, C, is the form of the original argument in A. So argument form C is the form of argument A. Moreover, each individual sentence of C is the sentence form of its respective sentence in A.
There is a good reason why attention to argument and sentence forms is important. The reason is this: form is what makes an argument valid or cogent.
In epistemology, a proposition that cannot be understood without knowing that it is true, is called a self-evident proposition. A self-evident proposition is one that can be known to be true without proof (but only if one understands what it says). Some epistemologists deny that any proposition can be self-evident.
My belief that I am conscious is considered by many to be self-evident; your belief that I am conscious is not.
In informal or colloquial speech, "self-evident" often merely means "obvious."
Certain forms of argument from self-evidence are considered fallacious or abusive in debate. An example is the assertion that since an opponent disagrees with a (claimed self-evident) proposition, that he must have misunderstood it.
Compare with: the concepts of primitive notion and axiom in mathematics
In mathematics, a set of symbols is frequently used in mathematical expressions. As mathematicians are familiar with these symbols, they are not explained each time they are used. So, for mathematical novices, the following table lists many common symbols together with their name, pronunciation and related field of mathematics. Additionally, the second line contains an informal definition, and the third line gives a short example.
Note: If some of the symbols don't display properly for you, then your browser does not completely implement the HTML 4 character entities. Mozilla does, although you may still need to install additional fonts to see everything.
| Symbol | Name | reads as | Category |
|---|---|---|---|
| ⇒ → |
material implication | implies; if .. then | propositional logic |
| A ⇒ B means: if A is true then
B is also true; if A is false then nothing is said about
B. → may mean the same as ⇒, or it may have the meaning for functions mentioned further down |
|||
| x = 2 ⇒ x2 = 4 is true, but x2 = 4 ⇒ x = 2 is in general false (since x could be −2) | |||
| ⇔ ↔ |
material equivalence | if and only if; iff | propositional logic |
| A ⇔ B means: A is true if B is true and A is false if B is false | |||
| x + 5 = y + 2 ⇔ x + 3 = y | |||
| ∧ | logical conjunction | and | propositional logic |
| the statement A ∧ B is true if A and B are both true; else it is false | |||
| n < 4 ∧ n > 2 ⇔ n = 3 when n is a natural number | |||
| ∨ | logical disjunction | or | propositional logic |
| the statement A ∨ B is true if A or B (or both) are true; if both are false, the statement is false | |||
| n ≥ 4 ∨ n ≤ 2 ⇔ n ≠ 3 when n is a natural number | |||
| ¬ / |
logical negation | not | propositional logic |
| the statement ¬A is true if and only if A
is false a slash placed through another operator is the same as "¬" placed in front |
|||
| ¬(A ∧ B) ⇔ (¬A) ∨ (¬B); x ∉ S ⇔ ¬(x ∈ S) | |||
| ∀ | universal quantification | for all; for any; for each | predicate logic |
| ∀ x: P(x) means: P(x) is true for all x | |||
| ∀ n ∈ N: n2 ≥ n | |||
| ∃ | existential quantification | there exists | predicate logic |
| ∃ x: P(x) means: there is at least one x such that P(x) is true | |||
| ∃ n ∈ N: n + 5 = 2n | |||
| = | equality | equals | everywhere |
| x = y means: x and y are different names for precisely the same thing | |||
| 1 + 2 = 6 − 3 | |||
| := :⇔ |
definition | is defined as | everywhere |
| x := y means: x is defined
to be another name for y P :⇔ Q means: P is defined to be logically equivalent to Q |
|||
| cosh x := (1/2)(exp x + exp (−x)); A XOR B :⇔ (A ∨ B) ∧ ¬(A ∧ B) | |||
| { , } | set brackets | the set of ... | set theory |
| {a,b,c} means: the set consisting of a, b, and c | |||
| N = {0,1,2,...} | |||
| { : } { | } |
set builder notation | the set of ... such that ... | set theory |
| {x : P(x)} means: the set of all x for which P(x) is true. {x | P(x)} is the same as {x : P(x)}. | |||
| {n ∈ N : n2 < 20} = {0,1,2,3,4} | |||
| ∅ {} |
empty set | empty set | set theory |
| {} means: the set with no elements; ∅ is the same thing | |||
| {n ∈ N : 1 < n2 < 4} = {} | |||
| ∈ ∉ |
set membership | in; is in; is an element of; is a member of; belongs to | set theory |
| a ∈ S means: a is an element of the set S; a ∉ S means: a is not an element of S | |||
| (1/2)−1 ∈ N; 2−1 ∉ N | |||
| ⊆ ⊂ |
subset | is a subset of | set theory |
| A ⊆ B means: every element of A
is also element of B A ⊂ B means: A ⊆ B but A ≠ B |
|||
| A ∩ B ⊆ A; Q ⊂ R | |||
| ∪ | set theoretic union | the union of ... and ...; union | set theory |
| A ∪ B means: the set that contains all the elements from A and also all those from B, but no others | |||
| A ⊆ B ⇔ A ∪ B = B | |||
| ∩ | set theoretic intersection | intersected with; intersect | set theory |
| A ∩ B means: the set that contains all those elements that A and B have in common | |||
| {x ∈ R : x2 = 1} ∩ N = {1} | |||
| \ | set theoretic complement | minus; without | set theory |
| A \ B means: the set that contains all those elements of A that are not in B | |||
| {1,2,3,4} \ {3,4,5,6} = {1,2} | |||
| ( ) [ ] { } |
function application; grouping | of | set theory |
| for function application: f(x) means:
the value of the function f at the element x for grouping: perform the operations inside the parentheses first |
|||
| If f(x) := x2, then f(3) = 32 = 9; (8/4)/2 = 2/2 = 1, but 8/(4/2) = 8/2 = 4 | |||
| : → | mapping arrow | from ... to | functions |
| f: X → Y means: the function f maps the set X into the set Y | |||
| If f(x) = x2, then we might take f: Z → N | |||
| N | natural numbers | N | numbers |
| N means: {0,1,2,3,...} | |||
| {|a| : a ∈ Z} = N | |||
| Z | integers | Z | numbers |
| Z means: {...,−3,−2,−1,0,1,2,3,...} | |||
| {a : |a| ∈ N} = Z | |||
| Q | rational numbers | Q | numbers |
| Q means: {p/q : p,q ∈ Z, q ≠ 0} | |||
| 3.14 ∈ Q; π ∉ Q | |||
| R | real numbers | R | numbers |
| R means: {limn→∞ an : ∀ n ∈ N: an ∈ Q, the limit exists} | |||
| π ∈ R; √(−1) ∉ R | |||
| C | complex numbers | C | numbers |
| C means: {a + bi : a,b ∈ R} | |||
| i = √(−1) ∈ C | |||
| < > |
comparison | is less than, is greater than | partial orders |
| x < y means: x is less than y; x > y means: x is greater than y | |||
| x < y ⇔ y > x | |||
| ≤ ≥ |
comparison | is less than or equal to, is greater than or equal to | partial orders |
| x ≤ y means: x is less than or equal to y; x ≥ y means: x is greater than or equal to y | |||
| x ≥ 1 ⇒ x2 ≥ x | |||
| √ | square root | the principal square root of; square root | real numbers |
| √x means: the positive number whose square is x | |||
| √(x2) = |x| | |||
| ∞ | infinity | infinity | numbers |
| ∞ means: an extended number that is greater than all real numbers; it often occurs in limits | |||
| limx→0 1/|x| = ∞ | |||
| π | pi | pi | Euclidean geometry |
| π means: the ratio of a circle's circumference to its diameter | |||
| A = πr˛ is the area of a circle with radius r | |||
| | | | absolute value | absolute value of | numbers |
| |x| means: the distance in the real line (or the complex plane) between x and zero | |||
| |a + bi| = √(a2 + b2) | |||
| ∑ | addition | sum over ... from ... to ... of | arithmetic |
| ∑k=1n ak means: a1 + a2 + ... + an | |||
| ∑k=14 k2 = 12 + 22 + 32 + 42 = 1 + 4 + 9 + 16 = 30 | |||
| ∏ | multiplication | product over ... from ... to ... of | arithmetic |
| ∏k=1n ak means: a1a2···an | |||
| ∏k=14 (k + 2) = (1 + 2)(2 + 2)(3 + 2)(4 + 2) = 3 × 4 × 5 × 6 = 360 | |||
| ∫ | integration | integral from ... to ... of ... with respect to | calculus |
| ∫ab f(x) dx means: the signed area between the x-axis and the graph of the function f between x = a and x = b | |||
| ∫0b x2 dx = b3/3; ∫x2 dx = x3/3 | |||
|
gradient | del, nabla, gradient of | calculus |
| ∇f (x1, …, xn) is the vector of partial derivatives (df / dx1, …, df / dxn) | |||
| If f (x,y,z) = 3xy + z˛ then ∇f = (3y, 3x, 2z) | |||
| insert more | |||
An argument by lack of imagination is the logical fallacy that states because something is currently inexplicable, that it did not happen, or that because one cannot conceive of something, it cannot exist. It is used often to attempt to invalidate a scientific theory by pointing out a phenomenon which the theory does not readily explain. This is rather simple to do because there are a lot of phenomena that are currently unexplained. However, the mistake is to assert that because a phenomenon is unexplained, it is unexplainable.
This logical fallacy should be distinguised from the logically valid method of reductio ad absurdum. In reductio ad absurdum it is necessary to show that A implies not A, not merely that A implies something which the speaker considers absurd.
Another example of this argument is Ayn Rand's defense of patent and copyright law. She argued that such laws were "obviously necessary" for authors and inventors to earn a living (or in other words, that she could not imagine any ways for them to earn a living without them, so such methods can't exist), so they should be supported. Rand's conclusion is falsified by, for example, the fact that a wealthy patron could commission a work, or that an author could control the work through trade secret law rather than through a copyright.
Richard Dawkins has called this fallacy "the argument from personal incredulity"; he uses it specifically in the context of arguments about creationism versus evolution, where it is often phrased in terms such as: "A mechanism that works so perfectly (for instance, the eye) could not have evolved by chance". In a more colorful example he counters a Bishop's implicit assumption that since polar bears are camouflaged even though they have no natural predators, their camouflage serves no evolutionary purpose--the polar bear benefits from the camouflage when hunting of course.
A decidable or recursive language is a formal language for which there exists an algorithm to solve the following decision problem: Given string w, does w belong to the language? The algorithm is not allowed to run into an infinite loop and has to produce a YES/NO answer for any input string after a finite amount of time. To formalize the rather vague term "algorithm", one usually employs Turing machines, but several other equivalent approaches are possible.
All regular, context-free and context-sensitive languages are recursive, but there exist recursively enumerable languages which are not recursive; one example is given by the halting problem.
The Turing machine is an abstract model of computer execution and storage introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the Church-Turing thesis.
Turing machines shouldn't be confused with the Turing test, Turing's attempt to capture the notion of artificial intelligence.
A Turing machine that is is able to simulate any other Turing machine is called a universal Turing machine.
A Turing machine consists of:
Note that every part of the machine is finite, but it is the potentially unlimited amount of tape that gives it an unbounded amount of storage space.
The following Turing machine has an alphabet {'0', '1'}, with 0 being the blank symbol. It expects a series of 1's on the tape, with the head initially on the leftmost 1, and doubles the 1's with a 0 in between, i.e., "111" becomes "1110111". The set of states is {s1, s2, s3, s4, s5} and the start state is s1. The action table is as follows.
Old Read Wr. New Old Read Wr. New St. Sym. Sym. Mv. St. St. Sym. Sym. Mv. St. - - - - - - - - - - - - - - - - - - - - - - - - s1 1 -> 0 R s2 s4 1 -> 1 L s4 s2 1 -> 1 R s2 s4 0 -> 0 L s5 s2 0 -> 0 R s3 s5 1 -> 1 L s5 s3 0 -> 1 L s4 s5 0 -> 1 R s1 s3 1 -> 1 R s3
A computation of this Turing machine might for example be: (the position of the head is indicated by displaying the cell in bold face)
Step State Tape Step State Tape
- - - - - - - - - - - - - - - - -
1 s1 11 9 s2 1001
2 s2 01 10 s3 1001
3 s2 010 11 s3 10010
4 s3 0100 12 s4 10011
5 s4 0101 13 s4 10011
6 s5 0101 14 s5 10011
7 s5 0101 15 s1 11011
8 s1 1101 -- halt --
The behavior of this machine can be described as a loop: it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skipping over 1's and the first 0 encountered. S3 then skips over the next sequence of 1's (initially there are none) and replaces the first 0 it finds with a 1. S4 moves back to the left, skipping over 1's until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1's until it finds the 0 that was originally written by s1. It replaces that 0 with a 1, moves one position to the right and enters s1 again for another round of the loop. This continues until s1 finds a 0 (this is the 0 right in the middle between the two strings of 1's) at which time the machine halts.
Every Turing machine computes a certain fixed partial function over the strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, as Alan Turing already described, we can encode the action table of every Turing machine in a string. Thus we might try to construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded Turing machine would have computed. As Turing showed, such a Turing machine is indeed possible and since it is able to simulate any other Turing machine it is called a universal Turing machine.
With this encoding of action tables as strings, it becomes in principle possible for Turing machines to answer questions about the behavior of other Turing machines. Most of these questions however are undecidable, see for instance the Halting problem, which was already shown to be undecidable in Turing's original paper, and Rice's theorem.
If we broaden the definition to include any Turing machine that simulates some Turing-complete computational model, not just Turing machines that directly simulate other Turing machines, a universal Turing machine can be fairly simple, using just a few states and a few symbols. For example, only 2 states are needed, since a 2×18 (meaning 2 states, 18 symbols) universal Turing machine is known. A complete list of the smallest known universal Turing machines is: 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. These simulate a computational model called tag-systems.
A universal Turing machine is Turing complete. It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.
It is not difficult to simulate a Turing Machine on a modern computer (except for the limited memory of actually existing computers).
It is also possible to build a Turing Machine on a purely mechanical basis. The mathematician Karl Scherer has indeed built such a machine in 1986 using metal and plastic construction sets, and some wood. The 1.5 meter high machine uses the pulling of strings to read, move and write the data (which is represented using ball bearing balls).
The machine is now exhibited in the entrance of the Department of Computer Science of the University in Heidelberg, Germany.
A partially decidable or recursively enumerable language is a formal language for which there is an algorithm for the following decision problem:
There are three potential outcomes: YES, NO, and LOOP. If the string is in the language, then the algorithm must output "YES", and halt. If the string is not in the language, then the algorithm may either output "NO" and halt, or it may run forever in an infinite loop that never outputs anything. To formalize the rather vague term "algorithm", one usually employs Turing machines, but several other equivalent approaches are possible.
Some partially decidable languages have an algorithm that always answers YES or NO correctly, and never has an infinite loop. Those languages are called decidable languages or recursive languages. Some problems are recursively enumerable but not recursive. One example is the halting problem, which is the problem:
All recursive, regular, context-free and context-sensitive languages are recursively enumerable. Some problems are so difficult that they aren't even recursively enumerable. One example is this problem:
The section on symbolic logic mentions axiomatic treatments of the subject. Here we say a bit about systems of natural deduction.
The name is suggestive. One of the popular ways of cashing out natural deduction is that it is an application of the laws (rules, whatever) of logic to our "natural modes" of inference.
For instance, if I say that
The general move is this. One begins a proof by assuming 'all x are such that, if x is A then x is M'. Next assume that something (call it 's') is not M, ie. assume 'it is not the case that s is M'. Now, a system of natural deduction will license the use of these assumptions. Moreover, the rules of the system will license the move from the first assumption 'all x, A(x) then M(x)' to 'A(s) then M(s)'[it would be called 'universal instantiation' or something]. We have 'not M(s)', and it readily follows that not 'A(s)'[the rule is called 'modus tollens', for those systems that countenance it - it need not be countenanced if there are other "simpler rules" capable of handling the inference. If such simpler rules are present, the abscence of modus tollens notwithstanding, the inference just takes more steps.].
Now, an axiomatic system COULD handle such an inference (since it's valid, and all such deductions are captured by non-wimpy axiomatic systems), but this would require a proof adhering to very restrictive syntactical (typographical, if one likes) rules. The advantage of a natural deduction system is that it has an apparatus for dealing with the sort of assumptions we just made. That is, one can assume whatever s/he likes, and proceed to deduce whatever can be deduced given the rules of the system. The method is thought to be more like argument, and more akin to the practice of mathematicians. Open your favorite math book. It's very unlikely that there are axiomatic proofs in that book (in any strict syntactical sense). Rather, the mathematician assumes something (which may be tentative, or an established fact- usually a fact) and then uses a bit of logic to show what must also be the case given the assumption (granted, s/he will almost always use certain "obvious" arithemtical properties in the proof-or other properties). In short, natural deduction systems are easier to work within. They are more natural.
An argument is sound if, and only if, (1) the argument is valid and (2) all of its premises are true.
So suppose we have a sound argument:
In this case we have an argument where, first, if the premises are all true, then the conclusion must be true (i.e., the argument is valid); and, second, it so happens that the premises are all true. It follows that the conclusion must be true. That is the nice thing about soundness: if you know an argument is sound, then you know that its conclusion is true. By definition, all sound arguments have true conclusions. So soundness is a very good quality for an argument to have.
In mathematical analysis, a metric space (M, d) is said to be complete if every Cauchy sequence of points in M has a limit in M.
Intuitively, a space is complete if it "doesn't have any holes", if there aren't any "points missing". For instance, the rational numbers are not complete, because √ 2 is "missing". It is always possible to "fill all the holes", leading to the completion of a given space. This will be explained below.
The rational numbers Q, with the standard metric given by the absolute value, are not complete. Consider for instance the sequence defined by x1 = 1 and xn+1 = (xn + 2/xn) / 2. This is a Cauchy sequence of rational numbers, but it does not converge towards any rational limit; in fact, it converges towards the irrational number √2 (see square root).
The open interval (0,1), again with the absolute value metric, is not complete either: The sequence 1/2, 1/3, 1/4, 1/5, ... is Cauchy, but does not have a limit in the space.
The real numbers and the complex numbers with the metric given by the absolute value are complete, so is Euclidean space Rn and, more generally, all Banach spaces.
The p-adic numbers are complete for any prime number p.
If S is an arbitrary set, then the set SN of all sequences in S becomes a complete metric space if we define the distance between the sequences (xn) and (yn) to be 1/N where N is the smallest index for which xN ≠ yN; if there is no such index, then the two sequences are the same and we define their distance to be 0. This space is homeomorphic to the product of a countable number of copies of the discrete space S. If S is finite, SN is therefore compact.
Every compact metric space is complete. In