Map of the basic concepts of logic
Pronouncing logic is as easy as αβγ. Just follow the examples below.
Logic | Pronunciation |
---|---|
true | true |
⊤ | true |
⊥ | false |
F | false |
ff | false |
tt | true |
a | A |
¬ b | not B |
d ∧ ⊤ | D and true |
c ∨ ⊥ | C or false |
∀x (x = x) | For every x, x equals x |
∃y (y ≠ y) | For some y, y does not equal y |
⊢ S | S is valid |
R ⊢ S | R implies S |
R ⇔ S | R is logically equivalent to S |
It is important to distinguish logical statements, operators, and relationships from meta-logical statements, operators, and relationships. Logical statements are those that state something about objects in the domain of discourse, or something about a logical relationship between sentence variables. Meta-logical statements, on the other hand, say something about one or more logical statements. Examples: “A ∧ B” and “¬ (¬ A ∨ ¬ B)” are logical statements; “ ‘A ∧ B is logically equivalent to ‘¬ (¬ A ∨ ¬ B)’ ” is a meta-logical statement.
Quine characterizes this as a distinction between mentioning and using [Quine1982-ml p.50], or perhaps more vigorously as a difference between stating and naming. When I state that A ∧ B and that ¬ (¬ A ∨ ¬ B), I have used those two logical statements, not mentioned them. When I state that “A ∧ B is logically equivalent to ¬ (¬ A ∨ ¬ B)”, on the other hand, I have named the two statements (by presenting them in quotes), not used them, and I have said something about the statements (by naming them and stating a relationship).
The authors whose work is collated here keep this distinction in part by being quite specific about what the syntactic form of a logical statement is, and thus excluding all other statements. Thus all meta-logical statements can be syntactically distinguished from logical statements, if one follows the rules fastidiously. See formula, sentence in the glossary below.
This section summarizes in tabular form some of the notation and usage for the authors discussed here.
Citation | true | false | not | and | or | if | iff | univ. | exist. | ident. |
[Bell+DeVidi+Solomon2001-lo] | ⊤ | ⊥ | ¬ | ∧ | ∨ | → | ||||
[Barwise+Etchemendy1992-lfol] | TRUE | FALSE | ¬ | ∧ | ∨ | → | ↔ | ∀x | ∃x | = |
[Boolos+Jeffrey1989-cl] | 1 | 0 | - | & | v | → | ↔ | ∀x | ∃x | = |
[Kleene1967-ml] | t | ƒ | ¬ | & | ∨ | ⊃ | ∼ | ∀x | ∃x | |
[Quine1982-ml] | ⊤ | ⊥ | p, - | pq | ∨ | → | ↔ | |||
(Hilbert) | & | → | ||||||||
[Whitehead+Russell1910-13-pm] | ~ | ∨ | ⊃ | ≡ | (x) | (∃x) | ||||
(Peano) | - | ⊃ | ∃ | |||||||
(Pierce) | p |
Description | Example | Citations |
Negation by overbar | p | Quine1982-ml, (Pierce) |
Conjunction by catenation | ab | Quine1982-ml |
Grouping by dots | a.b∨ c | Quine1982-ml, Whitehead+Russell1910-13-pm, (Peano) |
[Boolos+Jeffrey1989‑cl] | [Barwise+Etchemendy1992‑lfol] | [Quine1982‑ml] | [Bell+DeVidi+Solomon2001‑lo] |
not | negation | ||
and | conjunction | ||
or | disjunction | ||
if … then | material implication | implication | |
iff | material biconditional | biconditional |
Citation | implies | valid | equivalent | interpretation |
[Boolos+Jeffrey1989-cl] | ⊢ | ⊢ | ≅ | I |
[Barwise+Etchemendy1992-lfol] | ⇔ |
Citation | name | function | sentence | predicate |
[Boolos+Jeffrey1989-cl] | a b c … | f(a) | S | xLy xFy … |
[Barwise+Etchemendy1992-lfol] | a b c … | ab(a) bc(a,b) … | A(a) B(a,b) … | |
[Quine1982-ml] | Fx Gy … |
See sentence.
In a formula ∀x F or ∃x F, the variable x is bound.
See free variable, quantifier, variable.
Informally, a formal system is complete if every true statement can be derived in it.
A theory is complete and consistent if for every possible sentence A in the language of T, exactly one of A or ¬A is a theorem of T [Boolos+Jeffrey1989-cl p.177].
Compare consistent. See Gödel's first incompleteness theorem.
α | β | α ∧ β |
true | true | true |
true | false | false |
false | true | false |
false | false | false |
A conjunction is frequently written as α ∧ β. Some other notations are listed in the table of logical symbols.
A useful mnemonic for ∧ is that it resembles the ‘A’ in “and”.
Informally, a system is consistent if there is no sentence A for which it is possible to derive both A and ¬A in the system.
See satisfiable.
Synonyms: bearer, denotation, reference.
α | β | α ∨ β |
true | true | true |
true | false | true |
false | true | true |
false | false | false |
A disjunction is frequently written as α ∨ β. Some other notations are listed in the table of logical symbols.
The ∨ symbol is not an arbitrary choice, but rather derives from the Latin vel whose meaning corresponds to disjunction [Quine1982-ml p.12]. (Latin also possesses a word aut for exclusive or – A or B but not both.)
Example: in logic, a domain that is frequently of interest is the domain of the integers and their operations and relations.
Also called universe, universe of discourse.
Example:
Church uses a single dot to mean the same as a left bracket at that location and a right bracket at the end of the sentence [Church1958-iml p.42].
An existential quantification is written as ∃x F; occasionally the notation ∃x.F is seen, but it is obsolete (see dot).
The quantifier ∃x is said to bind x (see bound variable, free variable). Any unbound instance of x in F becomes bound in ∃x (F).
See existential quantifier, quantification, universal quantification.
See second-order logic.
A syntactically-correct utterance in a logical language that may contains zero or more free variables.
Utterances with precisely zero free variables are also called sentences.
For Boolos and Jeffrey, a formula is one of the following, where α, and β are also formulae [Boolos+Jeffrey1989-cl p.101]:
1. | -α | (negation) |
2. | (α&β) | (conjunction) |
3. | (αvβ) | (disjunction) |
4. | (α→ β) | (material implication) |
5. | (α↔ β) | (material biconditional) |
6. | ∀v α | (universal) |
7. | ∃v α | (existential) |
In addition, any atomic sentence is a formula.
Barwise and Etchemendy define formulae similarly, but using their own logical symbols [Barwise+Etchemendy1992-lfol p.117].
Quine uses open sentence for this concept [Quine1982-ml p.134].
Compare sentence.
A free variable is one whose relation to the objects in the domain is unknown.
See bound variable, variable.
Compare predicate which takes one or more domain objects and produces either true or false.
Informally, the proof uses what is termed the Gödel statement, G, which is "G cannot be proven true." If G can be proven under the extension of Q, then the extension would be inconsistent (as G states that it can't be proven); and if G can't be proven, then it is true, and the extension is incomplete.
Formally, the proof proceeds by representing any possible statement in the language by a number, so that (after a number of intermediate stages) provability of statements reduces to decidability of the set of numbers corresponding to them. (I was told by my logic professor that only a few dozen people in the world, including himself, really understand this proof in its entirety.)
Compare logical equivalence which is a meta-logical comparison of two sentences.
If sentence S_{1} implies sentence S_{2}, we write S_{1} ⊢ S_{2} [Boolos+Jeffrey1989-cl p.104].
Implication can be generalized to sets ΓS_{1},S_{2},…,S_{n}} of sentences: Γ implies sentence S_{n+1} if for every I that is an interpretation of all n+1 sentences, S_{n+1} is true in I if each of S_{1},S_{2},…,S_{n} is true in I.
Implication is a meta-logical operation, not to be confused with the logical formula of material implication.
An interpretation may also be viewed as a operator that takes a sentence and gives either true or false. Boolos and Jeffrey write this operation on sentence S as I(S) [Boolos+Jeffrey1989-cl p.101].
Interpretations are also known as models (but see glossary entry for model) or interpretation.
Symbol | Domain and range |
variable | → objects in the domain |
name | → a specific object in the domain |
function symbol | n-tuple of domain objects → domain object |
predicate letter | n-tuple of domain objects → true or false |
sentence letter | → true or false |
See model.
See satisfiable, unsatisfiable, valid.
Logical equivalence is a meta-logical relationship, not to be confused with the logical operation material biconditional.
Various authors use different terminology for the logical operators, summarized in the table of logical terminology.
Various authors also use different rules for parenthesization.
α | β | α ↔ β |
true | true | true |
true | false | false |
false | true | false |
false | false | true |
A material biconditional is almost universally written as α ↔ β. Other notations are listed in the table of logical symbols.
α ↔ β is logically equivalent to (α ∧ β) ∨ (¬ α ∧ ¬ β), and is probably best considered to be an abbreviation for it.
The material biconditional is a logical formula, not to be confused with the meta-logical relation of logical equivalence. Perhaps because of this potential confusion, the material biconditional does not seem to be used as commonly now as in the past.
α | β | α → β |
true | true | true |
true | false | false |
false | true | true |
false | false | true |
A material implication is frequently written as α→β. Some other notations are listed in the table of logical symbols.
α→β is logically equivalent to (¬ α) ∨ β, and is probably best considered as an abbreviation for it. Many authors have noted that a material implication seems to be making a statement about one thing causing another (“if α then β”), but in fact doesn't have anything to do with causality. See paradoxes of classical logic.
The material implication is a logical formula, not to be confused with the meta-logical relation of implication. Perhaps because of this potential confusion and the recognition that material implication isn't appropriate for describing cause and effect, the material implication does not seem to be used as commonly now.
Also known as conditional.
The meta-logical operators and properties include implication, satisfiability validity, logical equivalence, and interpretation. See also metavariable.
Compare variable; sentence letter, name.
It is possible for an object to have more than one name; but each name refers to only one object.
α | ¬ α |
true | false |
false | true |
A negation is frequently written as ¬ α. Some other notations are listed in the table of logical symbols.
Of course, each language may have its own conventions for the use of its symbols; the language of arithmetic uses its own functions and predicates 2+3×4, 5^2, and 6<4, as does set theory a ∈ b and T ∪ U. General, non-specific usage for various texts is summarized in the table of non-logical syntax.
Examples that are true since strawberries are red:
Examples that are true since the moon is not made of green cheese:
One may argue that each of these examples is obviously true, assuming that material implication is what was meant. That doesn't seem to be very useful, though. Why use → to express "if … then …" if it doesn't mean what people ordinarily mean by "if … then …"? Reasoning almost always uses some property of the things being reasoned about that is not included in their truth values, and on that basis it is not helpful to try to express that reasoning using →.
[Epstein2001-pl p.89 ff.]
It appears universal that ¬ binds the tightest and always applies to the next symbol, negation, or parenthesized expression; and that ∧ and ∨ bind tighter than any remaining operators. However there is no established custom for the relative priority of ∧ and ∨. It appears safest to use parentheses to disambiguate them. Here are some conventions, beginning with the most recent:
See the table of logical symbols.
Also known as a sentence letter.
Quantifiers use variables as parameters to direct the ranging over the domain. A quantifier is said to bind the variable that is its parameter [Barwise+Etchemendy1992-lfol p.115].
Satisfaction can be generalized to sets ΓS_{1},S_{2},…,S_{n}} of sentences: Γ is satisfiable if there is an interpretation I that satisfies every sentence in Γ [Boolos+Jeffrey1989-cl p.105]. (Note that by this definition ∅ is satisfiable.)
Quine uses consistent for the closely related concept of a truth-functional schema that is true for at least one interpretation of its (sentence) letters; he names the three possibilities inconsistent (false for every sentence letter interpretation), consistent (true for some interpretation), and valid (true for all interpretations). [Quine1982-ml p.40].
Compare unsatisfiable, valid.
Always true | valid | satisfiable |
---|---|---|
Sometimes true, sometimes false |
unsatisfiable | |
Always false | invalid |
In appearance like a formula, but in which letters stand not for atomic sentences but for subformula whose specifics are abstracted away for now [Quine1982-ml p.33].
A schema thus stands for (typically) an infinite number of actual formulae, in which each letter of the schema has been replaced by some subformula.
Where the letters of the schema are replaced only by “true” or “false”, no complication ensues. However, where the letters are replaced by formulae, caution must be used as the formulae may not be independent of each other. For example, an inconsistent schema remains inconsistent (and a valid schema remains valid) if its letters are replaced by formulae; but a consistent schema does not necessarily remain consistent if its letters are replaced by formulae, because the dependence among the subformulae may make some lines of the schema’s truth table impossible [Quine1982-ml p.44].
Epstein uses metavariables as components of formulae; a formula containing one or more metavariables appears to be indistinguishable from a schema.
Epstein also uses “schema” as its own plural, rather than either “schemata” or “schemas.”
A well-known example of a second-order statement is Leibniz's definition of identity ∀x ∀y [ x=y ↔ ∀P (Px ↔ Py) ]
See first-order logic.
A sentence has one of the following seven forms, and contains no free variables [Boolos+Jeffrey1989-cl p.101]. In the list of forms, S, S_{1}, and S_{2} are also sentences; F is a formula; L_{S} is a sentence letter; L_{P1}, L_{P2}, L_{P3}, … are one-, two-, three-, … place predicate letters; and T_{1}, T_{2}, … are terms.
1. | -S | (negation) |
2. | (S_{1}&S_{2}) | (conjunction) |
3. | (S_{1}∨S_{2}) | (disjunction) |
4. | S_{1}→ S_{2}) | (material implication) |
5. | (S_{1}↔ S_{2}) | (material biconditional) |
6. | ∀v F | (universal) |
7. | ∃v F | (existential) |
8. | L_{S} | (sentence letter) |
9. | T_{1}=T_{2} | (identity predicate) |
10. | L_{P1} T_{1} or T_{1} L_{P2} T_{2} or L_{P3}(T_{1},T_{2},T_{3}) or … |
(predicate) |
Because a sentence may have no free variables, the formula F in items 6 and 7 must have (at most) one free variable, and it must be the quantifier parameter v.
Quine uses statement or closed sentence for this concept, and open sentence for what we are terming a formula [Quine1982-ml p.134].
Compare formula.
This is termed an elementary statement or statement letter by Bell et al. [Bell+DeVidi+Solomon2001-lo p.6-7], and a propositional variable by Epstein, who says they stand for any proposition “whose internal structure won’t be under consideration” [Epstein2001-pl p.13].
Compare name which is a constant reference to a domain object.
See interpretation which (among other things) assigns true or false to each sentence letter.
Compare valid.
A theory always contains all valid sentences of K, as these are implied by any set of sentences of K. Thus, for example, every theory contains ∀x (x=x) as this is valid in every language. These sentences can be thought of as the basis of the theory, and that the theory, which by definition is closed under the operation of implication, can be constructed by applying implication successively using the sentences already in the theory.
Note that in general there are true sentences in K that are not in a particular theory T. In particular, for every theory of any language that includes the language of arithmetic, there are true statements that are not in the theory. See complete.
Truth tables are also used for analyzing more complex sentences by hand. Then the truth values of the smallest sub-sentences are filled in under the operator that defines them, continuing to larger sub-sentences until the entire table is filled (or until the desired result is obtained, for example demonstrating satisfiability). An example table appears below: first the possible values for A, B, and C are entered, then the values for (A∧B) and ¬ C; finally, the values for (A∧B)∨ ¬ C are entered under the ∨ [Barwise+Etchemendy1992-lfol p.53-4].
A | B | C | (A∧B) | ∨ | ¬ C |
A | B | C | (A∧B) | ∨ | ¬ C |
T | T | T | |||
T | T | F | |||
T | F | T | |||
T | F | F | |||
F | T | T | |||
F | T | F | |||
F | F | T | |||
F | F | F |
A | B | C | (A∧B) | ∨ | ¬ C |
T | T | T | T | F | |
T | T | F | T | T | |
T | F | T | F | F | |
T | F | F | F | T | |
F | T | T | F | F | |
F | T | F | F | T | |
F | F | T | F | F | |
F | F | F | F | T |
A | B | C | (A∧B) | ∨ | ¬ C |
T | T | T | T | T | F |
T | T | F | T | T | T |
T | F | T | F | F | F |
T | F | F | F | T | T |
F | T | T | F | F | F |
F | T | F | F | T | T |
F | F | T | F | F | F |
F | F | F | F | T | T |
The table of logical symbols lists the symbols used by various authors for true and false.
All formulae as defined here are truth-functional (e.g. conjunction, disjunction, material biconditional, etc.), but natural language sentences are generally not (e.g. “Don’t crush that dwarf, hand me the pliers”).
“Being truth-functional means that the truth value of a complex sentence built up using these connectives depends on nothing more than the truth values of the simpler sentences from which it is built” [Barwise+Etchemendy1992-lfol p.35].
A universal quantification is written as ∀x (F); occasionally this notation is seen ∀x.F, but it is obsolete (see dot).
The quantifier ∀x is said to bind x (see bound variable, free variable). Any unbound instance of x in F becomes bound in ∃x (F).
See universal quantification, quantification, existential quantifier.
See satisfiable, valid.
If S is valid, we write ⊢S [Boolos+Jeffrey1989-cl p.104].
Compare tautology.
See satisfiable, unsatisfiable.
See bound variable, free variable; compare metavariable, name, sentence letter.
The concept of a wff seems to demand that a formula may potentially be ill-formed; other authors appear to use “formula” for “wff,” or for emphasis use “syntactically correct formula.”
A somewhat biased and incomplete summary of the history of logic:
The study of logic dates back about two and a half millennia to Aristotle. From the perspective of the current day, Aristotleian logic seems to consist of some propositional logic without a good notation and a proof system in which the inference rule is essentially the subset operation on categories of objects. From this substantial beginning nothing of much interest developed until Frege developed a first-order formal logic that supported quantifiers and n-ary predicates and functions, and in which semantics followed syntax. For a time logic appeared to be primarily the study of mathematical proof systems, led by Whitehead and Russell and to a lesser extent Hilbert. Gödel’s Incompleteness Theorem gave this program a severe setback, but the view that logic is the handmaiden to mathematical proof continues to thrive (to some extent, for example, in Bell et al. [Bell+DeVidi+Solomon2001-lo]). The main thrust of logic, however, shifted to computability and related concepts, models and semantic structures, expressiveness, extensions of classical logic for other situations, and the study of logical systems as subjects of interest in their own right.
One of the motivations for the present work is the diversity in symbology, terminology, and ontology of concepts among prominent authors. Thus is is of interest to see where and when various approaches originated, and consider how they have affected the present day. Most of the information about symbols and approaches from before 1950 are from Quine [Quine1982-ml], who gives a historical note at the end of most sections.
(It is interesting to note how the points of view of various authors, including me, is expressed in their views of what was important in the history of logic. One important point of view is “logic as the basis of mathematical proofs”; this point of view seems to go along with the idea that modern logic began with Boole, and that Frege was unimportant.)
∀x (xLx → ∃y xLy) [Boolos+Jeffrey1989-cl p.96].
∀x [ ∃y (xLy & yLa) → −xLa] [Boolos+Jeffrey1989-cl p.96]. I would say that this is expressed by
∀x [ −∃y (xLy & yLa) → xLa]
∀x ∀y ∀z [ (xFz&yFz) → x=y] [Boolos+Jeffrey1989-cl p.96].
aLf(f(a)) [Boolos+Jeffrey1989-cl p.97].