Logical connective

In logic, two sentences (either in a formal language or a natural language) may be joined by means of a logical connective to form a compound sentence. The truth-value of the compound is uniquely determined by the truth-values of the simpler sentences. The logical connective therefore represents a function, and since the value of the compound sentence is a truth-value, it is called a truth-function and the logical connective is called a "truth-functional connective." The truth-functions include conjunction ("and"), disjunction ("or"), and implication ("if … then").


Mathematical logic is a mathematical representation of formal rules of human thought, which philosophers have been attempting to develop since Aristotle. Philosophical arguments are often incomprehensible due to obscure or ambiguous expressions. Logical connectives are basic units which constitute the logical structure of an argument. By applying these conceptual tools, arguments can become clearer, communicable, and comprehensible.

Truth functions in natural languages


A: Jack went up the hill.
B: Jill went up the hill.




Truth functions in formal languages

In formal languages truth-functions are represented by unambiguous symbols, and these can be exactly defined by means of truth tables. There are 16 binary truth tables, and so 16 different logical connectives which connect exactly two statements, 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."



The basic logical operators are:

  • Negation (not) (¬ or ~)
  • Conjunction (and) (\wedge or &)
  • Disjunction (or) (\vee)
  • Material implication (if...then) (\rightarrow, \Rightarrow or \supset)
  • Biconditional (if and only if) (xnor) (\leftrightarrow, \equiv, or =)

Some others are:

  • Exclusive disjunction (xor) (\not\leftrightarrow)
  • Joint denial (nor) (↓)
  • Alternative denial (nand) (↑)
  • Material nonimplication (\not\rightarrow)
  • Converse nonimplication (\not\leftarrow)
  • Converse implication (\leftarrow)
  • Tautology (\top)
  • Contradiction (\bot)


  • It is raining and I am indoors.
  • If it is raining then I am indoors.
  • It is raining if I am indoors.
  • It is raining if and only if I am indoors.
  • It is not raining.

If one writes "P" for It is raining and "Q" for I am indoors, and uses the usual symbols for logical connectives, then the above examples could be represented in symbols, respectively:

  • P & Q
  • P \to Q
  • Q \to P
  • P \leftrightarrow Q
  • ¬P

All binary logical connectives



Table of all logical connectives

Functional completeness

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



{  }, {  }, { \rightarrow\neg }, { \rightarrow\not\leftrightarrow }, { \neg }, { \rightarrow }, { \vee\neg }, { \rightarrow }, { \neg }, { \not\leftrightarrow }, { \neg }, {  }, { \wedge\neg }, {  }, { \bot\rightarrow }, { \leftrightarrow }, { \leftrightarrow }



(xy) • z = x • (yz)
xy = yx
  • Distributivity: Given a set S and two binary operations • and + on S, one says that the operation •
is left-distributive over + if, given any elements x, y, and z of S,
x • (y + z) = (xy) + (xz);
is right-distributive over + if, given any elements x, y, and z of S:
(y + z) • x = (yx) + (zx);
is distributive over + if it is both left- and right-distributive.
  • Idempotency: Multiple applications of the operation does not change the result. For example:
1 x 1 = 1
  • Absorption: An identity linking a pair of binary operations. For example, any two binary operations, say $ and %, are subject to the absorption law if:
a $ (a % b) = a % (a $ b) = a.
The operations $ and % are said to form a dual pair.


  • monotonic: If f(a1, ..., an) ≤ f(b1, ..., bn) for all a1, ..., an, b1, ..., bn ∈ {0,1} such that a1b1, a2b2, ..., anbn. E.g., \vee, \wedge, \top, \bot.
  • affine: Each variable always makes a difference in the truth-value of the operation or it never makes a difference. E.g., \neg, \leftrightarrow, \not\leftrightarrow, \top, \bot.
  • 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., \vee, \wedge, \top, \rightarrow, \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. For example, \vee, \wedge, \not\leftrightarrow, \bot, ⊄, ⊅.


In two-valued logic there are 2 nullary operators (constants), 4 unary operators, 16 binary operators, 256 ternary operators, and 2^{2^n} n-ary operators. In three valued logic there are 3 nullary operators (constants), 27 unary operators, 19683 binary operators, 7625597484987 ternary operators, and 3^{3^n} n-ary operators. An n-ary operator in k-valued logic is a function from \mathbb{Z}_k^n \to \mathbb{Z}_k. Therefore, the number of such operators is |\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, \binom{3}{2}\cdot 16 - \binom{3}{1}\cdot 4 + \binom{3}{0}\cdot 2 of them are such degenerate forms of binary or lower-arity operators, using the inclusion-exclusion principle. The ternary operator 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 \wedge Q, P, \vee Q, PQ, PQ).

The set of logical operators \Omega\! may be partitioned into disjoint subsets as follows:


In this partition, \Omega_j\! is the set of operator symbols of arity j\!.

In the more familiar propositional calculi, \Omega\! is typically partitioned as follows:

nullary operators: \Omega_0 = \{\bot, \top \} \,
unary operators: \Omega_1 = \{ \lnot \} \,
binary operators: \Omega_2 \subseteq \{ \land, \lor, \rightarrow, \leftrightarrow \} \,

Order of precedence



Operator Precedence
¬ 1
\leftrightarrow 5


Applications in computer science


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.




Basic logic symbols

Name Explanation Examples Unicode
Should be read as

material implication AB 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 ⇒ (the symbol may also indicate the domain and codomain of a function; see table of mathematical symbols).

⊃ may mean the same as ⇒ (the symbol may also mean superset).
x = 2  ⇒  x2 = 4 is true, but x2 = 4   ⇒  x = 2 is in general false (since x could be −2). 8658


implies; if .. then
propositional logic, Heyting algebra

material equivalence 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 8660


if and only if; iff
propositional logic

logical negation 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) ⇔ A
x ≠ y  ⇔  ¬(x =  y)

propositional logic

logical conjunction The statement AB 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. 8743

propositional logic
logical disjunction The statement AB 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. 8744 &or; \lor\lor
propositional logic

exclusive or The statement AB is true when either A or B, but not both, are true. A B means the same. A) ⊕ A is always true, AA is always false. 8853

&oplus; \oplus\oplus
propositional logic, Boolean algebra


logical truth The statement ⊤ is unconditionally true. A ⇒ ⊤ is always true. 8868 T \top\top
propositional logic, Boolean algebra


logical falsity The statement ⊥ is unconditionally false. ⊥ ⇒ A is always true. 8869 &perp;
propositional logic, Boolean algebra
universal quantification ∀ x: P(x) means P(x) is true for all x. ∀ n ∈ N: n2 ≥ n. 8704 &forall; \forall\forall
for all; for any; for each
predicate logic
existential quantification ∃ x: P(x) means there is at least one x such that P(x) is true. ∃ n ∈ N: n is even. 8707 &exist; \exists\exists
there exists
first-order logic
uniqueness quantification ∃! x: P(x) means there is exactly one x such that P(x) is true. ∃! n ∈ N: n + 5 = 2n. 8707 33 &exist; ! \exists !\exists !
there exists exactly one
first-order logic

definition x := y or x ≡ y means x is defined to be another name for y (but note that ≡ can also mean other things, such as congruence).

cosh x := (1/2)(exp x + exp (−x))

A XOR B :⇔ (A ∨ B) ∧ ¬(A ∧ B)
58 61


58 8660
: &equiv;
is defined as
( )
precedence grouping Perform the operations inside the parentheses first. (8/4)/2 = 2/2 = 1, but 8/(4/2) = 8/2 = 4. 40 41 ( ) (~) ( )
inference x y means y is derived from x. AB ¬B → ¬A 8866 \vdash\vdash
infers or is derived from
propositional logic, first-order logic

See also


  1. Although this character is available in LaTeX, the Mediawiki TeX system doesn't support this character.


  • Church, Alonzo. Introduction to Mathematical Logic. Princeton mathematical series, 17. Princeton: Princeton University Press, 1956.
  • Copi, Irving M. Symbolic Logic. New York: Macmillan, 1954.
  • Enderton, Herbert. A Mathematical Introduction to Logic, 2nd ed. Boston, MA: Academic Press, 2001. ISBN 978-0-12-238452-3.
  • Martin, Robert M. Introducing Symbolic Logic. Peterborough, ON: Broadview Press, 2004. ISBN 9781551116358.
  • Ochieng'-Odhiambo, F. Introductory Symbolic Logic. Guide to philosophy series, no. 7 (rev. ed.). Nairobi: Consolata Institute of Philosophy, 2003. ISBN 9789966820068.
  • Quine, W. V. Mathematical Logic. Cambridge: Harvard University Press, 1951.
  • Rosenbloom, Paul C. The Elements of Mathematical Logic. The Dover series in mathematics and physics. New York: Dover Publications, 1950.
  • Stoli︠a︡r, A. A. Introduction to Elementary Mathematical Logic. Cambridge, Mass: M.I.T. Press, 1970. ISBN 9780262190541.

External links

All links retrieved August 14, 2014.

General philosophy sources


