Logical connective

In logic, a logical connective, also called a truth-functional connective, logical operator or propositional operator, is a logical constant which represents a syntactic operation on one or two well formed formulae, or the symbol for such an operation that corresponds to an operation on the logical values of those formulae. A logical connective serves to produce a compound well-formed formula, from one or two well-formed formulae. If all of the variables in a well-formed formula are bound then it is a sentence. If a truth-functional connective is applied to one or two sentences then the results is a compound sentence and the truth-value of the resultant compound sentence is determined by the truth-values(s) of the one or two other sentences. Consequently a logical connective can be seen as a function which when applied to sentences as arguments whose values are True or False returns in turn the value True or False; consequently logical connectives are called truth-functional connectives.

Introduction

For example the statements, "it is raining," and, "I am indoors", can be reformed using various different connectives to form sentences that relate the two in ways which augment their meaning:

• It is raining and I am indoors. (Conjunction (and))
• If it is raining then I am indoors. (Material implication (if...then))
• It is raining if I am indoors. (Biconditional (xnor) )
• It is raining if and only if I am indoors. (Biconditional (xnor) )
• It is not the case that it is raining. (Negation (not))

If we write 'P' for 'It is raining' and 'Q' for 'I am indoors' and we use the usual symbols for logical connectives, then the above examples could be represent in symbols like this:

P&Q (It is raining and I am indoors.)

PFailed to parse (Missing texvc executable; please see math/README to configure.): \to

Q (If it is raining then I am indoors.)

QFailed to parse (Missing texvc executable; please see math/README to configure.): \to

P (It is raining if I am indoors.)

PFailed to parse (Missing texvc executable; please see math/README to configure.): \leftrightarrow

Q (It is raining if and only if I am indoors.)

¬P (It is not the case that it is raining.)

or &)

or Failed to parse (Missing texvc executable; please see math/README to configure.): \supset

or Failed to parse (Missing texvc executable; please see math/README to configure.): =

Definitions

Truth tables

Venn diagrams

The binary logical operators may be expressed as Venn diagrams. The red area of each figure corresponds to "true" and the white to "false".

The above arrangement of Venn Diagrams is from The Geometry of Logic.

Note the similarity between the symbols for "and" (Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge ) and set-theoretic intersection (Failed to parse (Missing texvc executable; please see math/README to configure.): \cap ); likewise for "or" (Failed to parse (Missing texvc executable; please see math/README to configure.): \vee ) and set-theoretic union (Failed to parse (Missing texvc executable; please see math/README to configure.): \cup ). This is not a coincidence: the definition of the intersection uses "and" and the definition of union uses "or".

Functional completeness

Main article: Functional completeness

Not all of these operators are necessary for a functionally complete logical calculus. Certain compound statements are logically equivalent. For example, ¬P ∨ Q is logically equivalent to P → Q;. So the conditional operator "→" is not necessary if you have "¬" (not) and "∨" (or).

The smallest set of operators which still expresses every statement which is 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 functionally complete sets (of cardinality 2) of operators whose arities do not exceed 2:

{ ↓ }, { ↑ }, { Failed to parse (Missing texvc executable; please see math/README to configure.): \rightarrow , Failed to parse (Missing texvc executable; please see math/README to configure.): \neg  }, { Failed to parse (Missing texvc executable; please see math/README to configure.): \rightarrow , Failed to parse (Missing texvc executable; please see math/README to configure.): \not\leftrightarrow  }, { Failed to parse (Missing texvc executable; please see math/README to configure.): \neg , ⊂ }, { Failed to parse (Missing texvc executable; please see math/README to configure.): \rightarrow , ⊄ }, { Failed to parse (Missing texvc executable; please see math/README to configure.): \vee , Failed to parse (Missing texvc executable; please see math/README to configure.): \neg  }, { Failed to parse (Missing texvc executable; please see math/README to configure.): \rightarrow , ⊅ }, { ⊄, Failed to parse (Missing texvc executable; please see math/README to configure.): \neg  }, { ⊂, Failed to parse (Missing texvc executable; please see math/README to configure.): \not\leftrightarrow  }, { ⊅, Failed to parse (Missing texvc executable; please see math/README to configure.): \neg  }, { ⊂, ⊄ }, { Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge , Failed to parse (Missing texvc executable; please see math/README to configure.): \neg  }, { ⊂, ⊅ }, { Failed to parse (Missing texvc executable; please see math/README to configure.): \bot , Failed to parse (Missing texvc executable; please see math/README to configure.): \rightarrow  }, { ⊄, Failed to parse (Missing texvc executable; please see math/README to configure.): \leftrightarrow  }, { ⊅, Failed to parse (Missing texvc executable; please see math/README to configure.): \leftrightarrow  }

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:

• Associativity: Within an expression containing two or more of the same associative operators in a row, the order of the operations does not matter as long as the sequence of the operands is not changed.
• Commutivity: Each pair of variables connected by the operator may be exchanged for each other without affecting the truth-value of the expression.
• Distributivity:
• Idempotency:
• Absorption:

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(a₁, …, a_n) ≤ f(b₁, …, b_n) for all a₁, …, a_n, b₁, …, b_n ∈ {0,1} such that a₁ ≤ b₁, a₂ ≤ b₂, …, a_n ≤ b_n. E.g., Failed to parse (Missing texvc executable; please see math/README to configure.): \vee

, Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge , Failed to parse (Missing texvc executable; please see math/README to configure.): \top , Failed to parse (Missing texvc executable; please see math/README to configure.): \bot .

• affine: Each variable always makes a difference in the truth-value of the operation or it never makes a difference. E.g., Failed to parse (Missing texvc executable; please see math/README to configure.): \neg

, Failed to parse (Missing texvc executable; please see math/README to configure.): \leftrightarrow , Failed to parse (Missing texvc executable; please see math/README to configure.): \not\leftrightarrow , Failed to parse (Missing texvc executable; please see math/README to configure.): \top , Failed to parse (Missing texvc executable; please see math/README to configure.): \bot .

• self dual: To read the truth-value assignments for the operation from top to bottom on its truth table is the same as taking the complement of reading it from bottom to top, in other words f(¬a₁, …, ¬a_n) = ¬f(a₁, …, a_n). E.g., Failed to parse (Missing texvc executable; please see math/README to configure.): \neg

.

• 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., Failed to parse (Missing texvc executable; please see math/README to configure.): \vee

, Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge , Failed to parse (Missing texvc executable; please see math/README to configure.): \top , Failed to parse (Missing texvc executable; please see math/README to configure.): \rightarrow , Failed to parse (Missing texvc executable; please see math/README to configure.): \leftrightarrow , ⊂.

• 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., Failed to parse (Missing texvc executable; please see math/README to configure.): \vee

, Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge , Failed to parse (Missing texvc executable; please see math/README to configure.): \not\leftrightarrow , Failed to parse (Missing texvc executable; please see math/README to configure.): \bot , ⊄, ⊅.

Arity

Main article: arity

In two-valued logic there are 2 nullary operators (constants), 4 unary operators, 16 binary operators, 256 ternary operators, and Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{2^n}

n-ary operators. In three valued logic there are 3 nullary operators (constants), 9 unary operators, 19683 binary operators, 7625597484987 ternary operators, and Failed to parse (Missing texvc executable; please see math/README to configure.): 3^{3^n}
n-ary operators. An n-ary operator in k-valued logic is a function from Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{Z}_k^n \to \mathbb{Z}_k

. Therefore the number of such operators is Failed to parse (Missing texvc executable; please see math/README to configure.): |\mathbb{Z}_k|^{|\mathbb{Z}_k^n|} = k^{k^n} , 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, Failed to parse (Missing texvc executable; please see math/README to configure.): \binom{3}{2}\cdot 16

of them are such degenerate forms of binary or lower-arity operators. The ternary operator Failed to parse (Missing texvc executable; please see math/README to configure.): f(x,y,z)=\lnot x
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 Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge

Q, P Failed to parse (Missing texvc executable; please see math/README to configure.): \vee
Q, P → Q, P ↔ Q).

The set of logical operators Failed to parse (Missing texvc executable; please see math/README to configure.): \Omega\!

may be partitioned into disjoint subsets as follows:

Failed to parse (Missing texvc executable; please see math/README to configure.): \Omega = \Omega_0 \cup \Omega_1 \cup \ldots \cup \Omega_j \cup \ldots \cup \Omega_m \,.

In this partition, Failed to parse (Missing texvc executable; please see math/README to configure.): \Omega_j\!

is the set of operator symbols of arity Failed to parse (Missing texvc executable; please see math/README to configure.): j\!

.

In the more familiar propositional calculi, Failed to parse (Missing texvc executable; please see math/README to configure.): \Omega\!

is typically partitioned as follows:

nullary operators: Failed to parse (Missing texvc executable; please see math/README to configure.): \Omega_0 = \{\bot, \top \} \,

unary operators: Failed to parse (Missing texvc executable; please see math/README to configure.): \Omega_1 = \{ \lnot \} \,

binary operators: Failed to parse (Missing texvc executable; please see math/README to configure.): \Omega_2 \subseteq \{ \land, \lor, \rightarrow, \leftrightarrow \} \,

Order of precedence

As a way of reducing the number of necessary parentheses, one may introduce precedence rules: ¬ 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 the usual precedence of logical operators.

The order of precedence determines which connective is the "main connective" when interpreting a molecular formula.

Applications in computer science

Logical operators are implemented as logic gates in digital circuits. Practically all digital circuits (the major exception is DRAM) are built up from NAND, NOR, NOT, and transmission gates. 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.

Is some new technology (such as reversible computing, clockless logic, or quantum dots computing) "functionally complete", in that it can be used to build computers that can do all the sorts of computation that CMOS-based computers can do? If it can implement the NAND operator, only then is it functionally complete.

That fact that all logical connectives can be expressed with NOR alone is demonstrated by the Apollo guidance computer.

References

• Stanford Encyclopedia of Philosophy: "Logical constants"--by John MacFarlane.
• Cullinane, Steven H. (2007) "The geometry of logic."

See also

Logic Portal

da:Logisk operator

de:Boolescher Operator el:Λογικές συναρτήσεις ko:논리 연산 is:Rökaðgerð it:Connettivo logico he:פעולה בוליאנית mk:Логичка операција nl:Booleaanse operator ja:論理演算 pl:Funktor zdaniotwórczy ru:Логическая операция sv:Logisk operator th:ตัวดำเนินการทางตรรกศาสตร์