Logical connective
Encyclopedia
In logic
, a logical connective (also called a logical operator) is a symbol
or word
used to connect two or more sentences
(of either a formal
or a natural
language) in a grammatically valid
way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences.
Each logical connective can be expressed as a function
, called a truth function. For this reason, logical connectives are sometimes called truth-functional connectives. The most common logical connectives are binary connectives (also called dyadic connectives) which join two sentences whose truth values can be thought of as the function's operand
s. Also commonly, negation
is considered to be a unary connective.
Logical connectives along with quantifiers are the two main types of logical constants used in formal system
s such as propositional logic and predicate logic
.
to form a grammatically compound sentence
. Some but not all such grammatical conjunctions are truth functions. For example, consider the following sentences:
The words and and so are grammatical conjunctions joining the sentences (A) and (B) to form the compound sentences (C) and (D). The and in (C) is a logical connective, since the truth of (C) is completely determined by (A) and (B): it would make no sense to affirm (A) and (B) but deny (C). However so in (D) is not a logical connective, since it would be quite reasonable to affirm (A) and (B) but deny (D): perhaps, after all, Jill went up the hill to fetch a pail of water, not because Jack had gone up the Hill at all.
Various English words and word pairs express truth functions, and some of them are synonymous. Examples (with the name of the relationship in parentheses) are:
The word "not" (negation) and the phrases "it is false that" (negation) and "it is not the case that" (negation) also express a logical connective – even though they are applied to a single statement, and do not connect two statements.
s. There are 16 binary truth tables, and so 16 different logical connectives which connect exactly two statements, that can be defined. Not all of them are in common use. These symbols are called "truth-functional connectives", "logical connectives", "logical operators" or "propositional operators". See well-formed formula
for the rules which allow new well-formed formulas to be constructed by joining other well-formed formulas using truth-functional connectives.
Venn diagrams illustrate the logical connective limitation of all quantifiers to a fixed domain of discourse
in a formal language.
Logical connectives can be used to link more than two statements. A more technical definition is that an "n-ary logical connective" is a function
which assigns truth values "true" or "false" to n-tuples of truth values.
For example, the meaning of the statements it is raining and I am indoors is transformed when the two are combined with logical connectives:
For statement P = It is raining and Q = I am indoors.
It is also common to consider the always true formula and the always false formula to be connective:
Some authors used letters for connectives at some time of the history: u. for conjunction (German's "und" for "and") and o. for disjunction (German's "oder" for "or") in earlier works by Hilbert (1904); N for negation, K for conjunction, A for disjunction, C for implication, E for biconditional in Łukasiewicz (1929).
outputs.
. For example, ¬P ∨ Q is logically equivalent to P → Q. The conditional operator "→" is therefore not necessary if "¬" (not) and "∨" (or) are already in use.
A minimal set of operators that can express every statement expressible in the propositional calculus
is called a minimal functionally complete set. A minimally complete set of operators is achieved by NAND alone {↑} and NOR alone {↓}.
The following are the minimal functionally complete sets of operators whose arities do not exceed 2:
One element: {↑}, {↓}.
Two elements: {
, ¬}, {
, ¬}, {→, ¬}, {←, ¬}, {→, 
}, {←, 
}, {→, 
}, {←, 
}, {→, 
}, {→, 
}, {←, 
}, {←, 
}, {
, ¬}, {
, ¬}, {
, 
}, {
, 
}, {
, 
}, {
, 
}.
Three elements: {
, 
, 
}, {
, 
, 
}, {
, 
, 
}, {
, 
, 
}, {
, 
, 
}, {
, 
, 
}.
A set of operators is functionally complete if and only if for each of the following five properties it contains at least one member lacking it:
, 16 binary operators
, 256 ternary operators
, and
n-ary operators. In three-valued logic there are 3 nullary operators (constants), 27 unary operators
, 19683 binary operators
, 7625597484987 ternary operators
, and
n-ary operators. In k-valued logic, there are k nullary operators, 
unary operators, 
binary operators, 
ternary operators, and 
n-ary operators. An n-ary operator in k-valued logic is a function from 
. Therefore the number of such operators is 
, which is how the above numbers were derived.
However, some of the operators of a particular arity are actually degenerate forms that perform a lower-arity operation on some of the inputs and ignores the rest of the inputs. Out of the 256 ternary boolean operators cited above,
of them are such degenerate forms of binary or lower-arity operators, using the inclusion-exclusion principle
. The ternary operator
is one such operator which is actually a unary operator applied to one input, and ignoring the other two inputs.
"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).
The set of logical operators
may be partition
ed into disjoint subsets as follows:
In this partition,
is the set of operator symbols of arity
.
In the more familiar propositional calculi,
is typically partitioned as follows:
: ¬ has higher precedence than
, 
higher than 
, and 
higher than →. So for example, P 
Q 
¬R → S is short for (P 
(Q 
(¬R))) → S.
Here is a table that shows a commonly used precedence of logical operators.
The order of precedence determines which connective is the "main connective" when interpreting a non-atomic formula.
s, logical connective symbols can be interpreted by means of an interpretation function and a functionally complete set of truth-functions (Gamut 1991), as detailed by the principle of compositionality
of meaning.
Let I be an interpretation function, let Φ, Ψ be any two sentences and let the truth function fnand be defined as:
Then, for convenience, fnot, for fand and so on are defined by means of fnand:
or, alternatively fnot, for fand and so on are defined directly:
Then
etc.
Thus if S is a sentence that is a string of symbols consisting of logical symbols v1...vn representing logical connectives, and non-logical symbols c1...cn, then if and only if I(v1)...I(vn) have been provided interpreting v1 to vn by means of fnand (or any other set of functional complete truth-functions) then the truth-value of I(s) is determined entirely by the truth-values of c1...cn, i.e. of I(c1)...I(cn). In other words, as expected and required, S is true or false only under an interpretation of all its non-logical symbols.
s in digital circuit
s. Practically all digital circuits (the major exception is DRAM
) are built up from NAND, NOR
, NOT
, and transmission gate
s. NAND and NOR gates with 3 or more inputs rather than the usual 2 inputs are fairly common, although they are logically equivalent to a cascade of 2-input gates. All other operators are implemented by breaking them down into a logically equivalent combination of 2 or more of the above logic gates.
The "logical equivalence" of "NAND alone", "NOR alone", and "NOT and AND" is similar to Turing equivalence.
That fact that all logical connectives can be expressed with NOR alone is demonstrated by the Apollo guidance computer
.
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, a logical connective (also called a logical operator) is a symbol
Symbol (formal)
For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...
or word
Word
In language, a word is the smallest free form that may be uttered in isolation with semantic or pragmatic content . This contrasts with a morpheme, which is the smallest unit of meaning but will not necessarily stand on its own...
used to connect two or more sentences
Sentence (linguistics)
In the field of linguistics, a sentence is an expression in natural language, and often defined to indicate a grammatical unit consisting of one or more words that generally bear minimal syntactic relation to the words that precede or follow it...
(of either a formal
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
or a natural
Natural language
In the philosophy of language, a natural language is any language which arises in an unpremeditated fashion as the result of the innate facility for language possessed by the human intellect. A natural language is typically used for communication, and may be spoken, signed, or written...
language) in a grammatically valid
Syntax (logic)
In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them...
way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences.
Each logical connective can be expressed as a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
, called a truth function. For this reason, logical connectives are sometimes called truth-functional connectives. The most common logical connectives are binary connectives (also called dyadic connectives) which join two sentences whose truth values can be thought of as the function's operand
Operand
In mathematics, an operand is the object of a mathematical operation, a quantity on which an operation is performed.-Example :The following arithmetic expression shows an example of operators and operands:3 + 6 = 9\;...
s. Also commonly, negation
Negation
In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...
is considered to be a unary connective.
Logical connectives along with quantifiers are the two main types of logical constants used in formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
s such as propositional logic and predicate logic
Predicate logic
In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified...
.
Natural language
In the grammar of natural languages two sentences may be joined by a grammatical conjunctionGrammatical conjunction
In grammar, a conjunction is a part of speech that connects two words, sentences, phrases or clauses together. A discourse connective is a conjunction joining sentences. This definition may overlap with that of other parts of speech, so what constitutes a "conjunction" must be defined for each...
to form a grammatically compound sentence
Compound sentence (linguistics)
A compound sentence is composed of at least two independent clauses. It does not require a dependent clause. The clauses are joined by a coordinating conjunction , a correlative conjunction , a semicolon that functions as a conjunction, or a conjunctive adverb preceded by a semicolon. A conjunction...
. Some but not all such grammatical conjunctions are truth functions. For example, consider the following sentences:
- A: Jack went up the hill.
- B: Jill went up the hill.
- C: Jack went up the hill and Jill went up the hill.
- D: Jack went up the hill so Jill went up the hill.
The words and and so are grammatical conjunctions joining the sentences (A) and (B) to form the compound sentences (C) and (D). The and in (C) is a logical connective, since the truth of (C) is completely determined by (A) and (B): it would make no sense to affirm (A) and (B) but deny (C). However so in (D) is not a logical connective, since it would be quite reasonable to affirm (A) and (B) but deny (D): perhaps, after all, Jill went up the hill to fetch a pail of water, not because Jack had gone up the Hill at all.
Various English words and word pairs express truth functions, and some of them are synonymous. Examples (with the name of the relationship in parentheses) are:
- "and" (conjunction)
- "or" (disjunction)
- "either...or" (exclusive disjunction)
- "implies" (implication)
- "if...then" (implication)
- "if and only if" (equivalence)
- "only if" (implication)
- "just in case" (equivalence)
- "but" (conjunction)
- "however" (conjunction)
- "not both" (NAND)
- "neither...nor" (NOR)
The word "not" (negation) and the phrases "it is false that" (negation) and "it is not the case that" (negation) also express a logical connective – even though they are applied to a single statement, and do not connect two statements.
Formal languages
In formal languages, truth functions are represented by unambiguous symbols; these can be exactly defined by means of truth tableTruth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
s. There are 16 binary truth tables, and so 16 different logical connectives which connect exactly two statements, that can be defined. Not all of them are in common use. These symbols are called "truth-functional connectives", "logical connectives", "logical operators" or "propositional operators". See well-formed formula
Well-formed formula
In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...
for the rules which allow new well-formed formulas to be constructed by joining other well-formed formulas using truth-functional connectives.
Venn diagrams illustrate the logical connective limitation of all quantifiers to a fixed domain of discourse
Domain of discourse
In the formal sciences, the domain of discourse, also called the universe of discourse , is the set of entities over which certain variables of interest in some formal treatment may range...
in a formal language.
Logical connectives can be used to link more than two statements. A more technical definition is that an "n-ary logical connective" is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
which assigns truth values "true" or "false" to n-tuples of truth values.
List of common logical connectives
Commonly used logical connectives include:- Negation (not)NegationIn logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...
(¬ or ~) - Conjunction (and)Logical conjunctionIn logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
(
, &, or · ) - Disjunction (or)Logical disjunctionIn logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
(∨) - Material implication (if...then)Material conditionalThe material conditional, also known as material implication, is a binary truth function, such that the compound sentence p→q is logically equivalent to the negative compound: not . A material conditional compound itself is often simply called a conditional...
(
, 
or 
) - Biconditional (if and only if) (iff) (xnor) (bi-implication)Logical biconditionalIn logic and mathematics, the logical biconditional is the logical connective of two statements asserting "p if and only if q", where q is a hypothesis and p is a conclusion...
(
, 
, or 
)
For example, the meaning of the statements it is raining and I am indoors is transformed when the two are combined with logical connectives:
- It is raining and I am indoors (P
Q) - If it is raining, then I am indoors (P
Q) - If I am indoors, then it is raining (Q
P) - I am indoors if and only if it is raining (P
Q) - It is not raining (P)
For statement P = It is raining and Q = I am indoors.
It is also common to consider the always true formula and the always false formula to be connective:
- True formula (⊤, 1 or T)
- False formula (⊥, 0, or F)
History of notations
- Negation: the symbol ¬ appeared in HeytingArend HeytingArend Heyting was a Dutch mathematician and logician. He was a student of Luitzen Egbertus Jan Brouwer at the University of Amsterdam, and did much to put intuitionistic logic on a footing where it could become part of mathematical logic...
in 1929. (compare to FregeGottlob FregeFriedrich Ludwig Gottlob Frege was a German mathematician, logician and philosopher. He is considered to be one of the founders of modern logic, and made major contributions to the foundations of mathematics. He is generally considered to be the father of analytic philosophy, for his writings on...
's symbol in his BegriffsschriftBegriffsschriftBegriffsschrift is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book...
); the symbol ~ appeared in Russell in 1908; an alternative notation is to add an horizontal line on top of the formula, as in
; another alternative notation is to use a prime symbolPrime (symbol)The prime symbol , double prime symbol , and triple prime symbol , etc., are used to designate several different units, and for various other purposes in mathematics, the sciences and linguistics...
as in P'. - Conjunction: the symbol ∧ appeared in Heyting in 1929 (compare to PeanoGiuseppe PeanoGiuseppe Peano was an Italian mathematician, whose work was of philosophical value. The author of over 200 books and papers, he was a founder of mathematical logic and set theory, to which he contributed much notation. The standard axiomatization of the natural numbers is named the Peano axioms in...
's use of the set-theoretic notation of intersectionIntersection (set theory)In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
∩ ); & appeared at least in SchönfinkelMoses SchönfinkelMoses Ilyich Schönfinkel, also known as Moisei Isai'evich Sheinfinkel , was a Russian logician and mathematician, known for the invention of combinatory logic.- Life :Schönfinkel attended the Novorossiysk University of Odessa, studying mathematics under Samuil Osipovich...
in 1924; . comes from BooleGeorge BooleGeorge Boole was an English mathematician and philosopher.As the inventor of Boolean logic—the basis of modern digital computer logic—Boole is regarded in hindsight as a founder of the field of computer science. Boole said,...
's interpretation of logic as an elementary algebraElementary algebraElementary algebra is a fundamental and relatively basic form of algebra taught to students who are presumed to have little or no formal knowledge of mathematics beyond arithmetic. It is typically taught in secondary school under the term algebra. The major difference between algebra and...
. - Disjunction: the symbol ∨ appeared in RussellBertrand RussellBertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
in 1908 (compare to PeanoGiuseppe PeanoGiuseppe Peano was an Italian mathematician, whose work was of philosophical value. The author of over 200 books and papers, he was a founder of mathematical logic and set theory, to which he contributed much notation. The standard axiomatization of the natural numbers is named the Peano axioms in...
's use of the set-theoretic notation of unionUnion (set theory)In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
∪); the symbol + is also used, in spite of the ambiguity coming from the fact that the + of ordinary elementary algebraElementary algebraElementary algebra is a fundamental and relatively basic form of algebra taught to students who are presumed to have little or no formal knowledge of mathematics beyond arithmetic. It is typically taught in secondary school under the term algebra. The major difference between algebra and...
is an exclusive or when interpreted logically in a two-element ringBoolean ringIn mathematics, a Boolean ring R is a ring for which x2 = x for all x in R; that is, R consists only of idempotent elements....
; punctually in the history a + together with a dot in the lower right corner has been used by Peirce, - Implication: the symbol → can be seen in HilbertDavid HilbertDavid Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
in 1917; ⊃ was used by Russell in 1908 (compare to Peano's inverted C notation);
was used in Vax. - Biconditional: the symbol ≡ was used at least by Russell in 1908; ↔ was used at least by TarskiAlfred TarskiAlfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
in 1940; ⇔ was used in Vax; other symbols appeared punctually in the history such as ⊃⊂ in GentzenGerhard GentzenGerhard Karl Erich Gentzen was a German mathematician and logician. He had his major contributions in the foundations of mathematics, proof theory, especially on natural deduction and sequent calculus...
, ~ in Schönfinkel or ⊂⊃ in Chazal. - True: the symbol 1 comes from BooleGeorge BooleGeorge Boole was an English mathematician and philosopher.As the inventor of Boolean logic—the basis of modern digital computer logic—Boole is regarded in hindsight as a founder of the field of computer science. Boole said,...
's interpretation of logic as an elementary algebraElementary algebraElementary algebra is a fundamental and relatively basic form of algebra taught to students who are presumed to have little or no formal knowledge of mathematics beyond arithmetic. It is typically taught in secondary school under the term algebra. The major difference between algebra and...
over the two-element ringBoolean ringIn mathematics, a Boolean ring R is a ring for which x2 = x for all x in R; that is, R consists only of idempotent elements....
; other notations include
to be found in Peano. - False: the symbol 0 comes also from Boole's interpretation of logic as a ring; other notations include
to be found in Peano.
Some authors used letters for connectives at some time of the history: u. for conjunction (German's "und" for "and") and o. for disjunction (German's "oder" for "or") in earlier works by Hilbert (1904); N for negation, K for conjunction, A for disjunction, C for implication, E for biconditional in Łukasiewicz (1929).
Table of binary logical connectives
There are sixteen Boolean functions associating the inputs P and Q with four-digit binaryBinary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
outputs.
Functional completeness
Not all of the above-mentioned operators are necessary for a functionally complete logical calculus. Certain compound statements are logically equivalentLogical equivalence
In logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other...
. For example, ¬P ∨ Q is logically equivalent to P → Q. The conditional operator "→" is therefore not necessary if "¬" (not) and "∨" (or) are already in use.
A minimal set of operators that can express every statement expressible in the propositional calculus
Propositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
is called a minimal functionally complete set. A minimally complete set of operators is achieved by NAND alone {↑} and NOR alone {↓}.
The following are the minimal functionally complete sets of operators whose arities do not exceed 2:
One element: {↑}, {↓}.
Two elements: {
, ¬}, {, ¬}, {→, ¬}, {←, ¬}, {→, }, {←, }, {→, }, {←, }, {→, }, {→, }, {←, }, {←, }, {, ¬}, {, ¬}, {, }, {, }, {, }, {, }.Three elements: {
, , }, {, , }, {, , }, {, , }, {, , }, {, , }.Properties
The logical connectives each possess different set of properties which may be expressed in the theorems containing the connective. Some of those properties that a logical connective may have are:- AssociativityAssociativityIn mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
: Within an expression containing two or more of the same associative connectives in a row, the order of the operations does not matter as long as the sequence of the operands is not changed. - CommutativityCommutativityIn mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
: The operands of the connective may be swapped without affecting the truth-value of the expression. - DistributivityDistributivityIn mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...
: A connective denoted by · distributes over another connective denoted by +, if a · (b + c) = (a · b) + (a · c) for all operands a, b, c. - IdempotenceIdempotenceIdempotence is the property of certain operations in mathematics and computer science, that they can be applied multiple times without changing the result beyond the initial application...
: Whenever the operands of the operation are the same, the connective gives the operand as the result. - AbsorptionAbsorption lawIn algebra, the absorption law or absorption identity is an identity linking a pair of binary operations.Two binary operations, say ¤ and *, are said to be connected by the absorption law if:...
: A pair of connectives
, 
satisfies the absorption law if 
for all operands a, b.
A set of operators is functionally complete if and only if for each of the following five properties it contains at least one member lacking it:
- monotonic: If f(a1, ..., an) ≤ f(b1, ..., bn) for all a1, ..., an, b1, ..., bn ∈ {0,1} such that a1 ≤ b1, a2 ≤ b2, ..., an ≤ bn. E.g.,
, 
, 
, 
. - affineAffine transformationIn geometry, an affine transformation or affine map or an affinity is a transformation which preserves straight lines. It is the most general class of transformations with this property...
: Each variable always makes a difference in the truth-value of the operation or it never makes a difference. E.g.,
, 
, 
, 
, 
. - self dual: To read the truth-value assignments for the operation from top to bottom on its truth tableTruth tableA truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
is the same as taking the complement of reading it from bottom to top; in other words, f(¬a1, ..., ¬an) = ¬f(a1, ..., an). E.g.,
. - truth-preserving: The interpretation under which all variables are assigned a truth value of 'true' produces a truth value of 'true' as a result of these operations. E.g.,
, 
, 
, 
, 
, ⊂. (see validityValidityIn logic, argument is valid if and only if its conclusion is entailed by its premises, a formula is valid if and only if it is true under every interpretation, and an argument form is valid if and only if every argument of that logical form is valid....
) - falsehood-preserving: The interpretation under which all variables are assigned a truth value of 'false' produces a truth value of 'false' as a result of these operations. E.g.,
, 
, 
, 
, ⊄, ⊅. (see validityValidityIn logic, argument is valid if and only if its conclusion is entailed by its premises, a formula is valid if and only if it is true under every interpretation, and an argument form is valid if and only if every argument of that logical form is valid....
)
Arity
In two-valued logic there are 2 nullary operators (constants), 4 unary operatorsUnary operation
In mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
, 16 binary operators
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
, 256 ternary operators
Ternary operation
In mathematics, a ternary operation is an n-ary operation with n = 3. A ternary operation on a set A takes any given three elements of A and combines them to form a single element of A. An example of a ternary operation is the product in a heap....
, and
n-ary operators. In three-valued logic there are 3 nullary operators (constants), 27 unary operatorsUnary operation
In mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
, 19683 binary operators
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
, 7625597484987 ternary operators
Ternary operation
In mathematics, a ternary operation is an n-ary operation with n = 3. A ternary operation on a set A takes any given three elements of A and combines them to form a single element of A. An example of a ternary operation is the product in a heap....
, and
n-ary operators. In k-valued logic, there are k nullary operators, unary operators, binary operators, ternary operators, and n-ary operators. An n-ary operator in k-valued logic is a function from . Therefore the number of such operators is , which is how the above numbers were derived.However, some of the operators of a particular arity are actually degenerate forms that perform a lower-arity operation on some of the inputs and ignores the rest of the inputs. Out of the 256 ternary boolean operators cited above,
of them are such degenerate forms of binary or lower-arity operators, using the inclusion-exclusion principleInclusion-exclusion principle
In combinatorics, the inclusion–exclusion principle is an equation relating the sizes of two sets and their union...
. The ternary operator
is one such operator which is actually a unary operator applied to one input, and ignoring the other two inputs."Not"
Negation
In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...
is a unary operator
Unary operation
In mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
, it takes a single term (¬P). The rest are binary operators
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
, taking two terms to make a compound statement (P
Q, P Q, P → Q, P ↔ Q).The set of logical operators
may be partitionPartition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
ed into disjoint subsets as follows:
In this partition,
is the set of operator symbols of arityArity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
.In the more familiar propositional calculi,
is typically partitioned as follows:-
-
- nullary operators:
- nullary operators:
-
-
-
- unary operators:
- unary operators:
-
-
-
- binary operators:
- binary operators:
-
Order of precedence
As a way of reducing the number of necessary parentheses, one may introduce precedence rulesOrder of operations
In mathematics and computer programming, the order of operations is a rule used to clarify unambiguously which procedures should be performed first in a given mathematical expression....
: ¬ has higher precedence than
, higher than , and higher than →. So for example, P Q ¬R → S is short for (P (Q (¬R))) → S.Here is a table that shows a commonly used precedence of logical operators.
| Operator | Precedence |
|---|---|
| ¬ | 1 |
 |
2 |
 |
3 |
| → | 4 |
| 5 |
The order of precedence determines which connective is the "main connective" when interpreting a non-atomic formula.
Principle of compositionality
Instead of using truth tableTruth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
s, logical connective symbols can be interpreted by means of an interpretation function and a functionally complete set of truth-functions (Gamut 1991), as detailed by the principle of compositionality
Principle of compositionality
In mathematics, semantics, and philosophy of language, the Principle of Compositionality is the principle that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them. This principle is also called Frege's Principle,...
of meaning.
Let I be an interpretation function, let Φ, Ψ be any two sentences and let the truth function fnand be defined as:
- fnand(T,T)=F; fnand(T,F)=fnand(F,T)=fnand(F,F)=T
Then, for convenience, fnot, for fand and so on are defined by means of fnand:
- fnot(x)=fnand(x,x)
- for(x,y)= fnand(fnot(x), fnot(y))
- fand(x,y)=fnot(fnand(x,y))
or, alternatively fnot, for fand and so on are defined directly:
- fnot(T)=F; fnot(F)=T;
- for(T,T)=for(T,F)=for(F,T)=T;for(F,F)=F
- fand(T,T)=T; fand(T,F)=fand(F,T)=fand(F,F)=F
Then
- I(~)=I=fnot
- I(&)=I(^)=I=fand
- I(v)=I= for
- I(~Φ)=I(Φ)=I(I(Φ))=fnot(I(Φ))
- I(ΦΨ) = I(I(Φ), I(Ψ))= fand(I(Φ), I(Ψ))
etc.
Thus if S is a sentence that is a string of symbols consisting of logical symbols v1...vn representing logical connectives, and non-logical symbols c1...cn, then if and only if I(v1)...I(vn) have been provided interpreting v1 to vn by means of fnand (or any other set of functional complete truth-functions) then the truth-value of I(s) is determined entirely by the truth-values of c1...cn, i.e. of I(c1)...I(cn). In other words, as expected and required, S is true or false only under an interpretation of all its non-logical symbols.
Computer science
Logical operators are implemented as logic gateLogic gate
A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...
s in digital circuit
Digital circuit
Digital electronics represent signals by discrete bands of analog levels, rather than by a continuous range. All levels within a band represent the same signal state...
s. Practically all digital circuits (the major exception is DRAM
Dram
Dram or DRAM may refer to:As a unit of measure:* Dram , an imperial unit of mass and volume* Armenian dram, a monetary unit* Dirham, a unit of currency in several Arab nationsOther uses:...
) are built up from NAND, NOR
Logical NOR
In boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...
, NOT
Negation
In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...
, and transmission gate
Logic gate
A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...
s. NAND and NOR gates with 3 or more inputs rather than the usual 2 inputs are fairly common, although they are logically equivalent to a cascade of 2-input gates. All other operators are implemented by breaking them down into a logically equivalent combination of 2 or more of the above logic gates.
The "logical equivalence" of "NAND alone", "NOR alone", and "NOT and AND" is similar to Turing equivalence.
That fact that all logical connectives can be expressed with NOR alone is demonstrated by the Apollo guidance computer
Apollo Guidance Computer
The Apollo Guidance Computer provided onboard computation and control for guidance, navigation, and control of the Command Module and Lunar Module spacecraft of the Apollo program...
.
See also
- Bitwise operationBitwise operationA bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...
- Boolean domainBoolean domainIn mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true...
- Boolean function
- Boolean logicBoolean logicBoolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...
- Boolean-valued functionBoolean-valued functionA boolean-valued function, in some usages is a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain....
- List of Boolean algebra topics
- Logical constant
- Modal operatorModal operatorIn modal logic, a modal operator is an operator which forms propositions from propositions. In general, a modal operator has the "formal" property of being non-truth-functional, and is "intuitively" characterised by expressing a modal attitude about the proposition to which the operator is applied...
- Propositional calculusPropositional calculusIn mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
- Truth tableTruth tableA truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
- Truth values
External links
- John MacFarlane (2005), "Logical constants", Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
.