Logical connective


Logical connective

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 operands. 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 systems such as propositional logic and predicate logic.

Contents

In language

Natural language

In the grammar of natural languages two sentences may be joined by a grammatical conjunction to form a grammatically compound sentence. 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 tables. 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.

Common logical connectives

List of common logical connectives

Commonly used logical connectives include:

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 \wedge Q)
  • If it is raining, then I am indoors (P \rightarrow Q)
  • If I am indoors, then it is raining (Q \rightarrow P)
  • I am indoors if and only if it is raining (P \leftrightarrow 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 Heyting in 1929.[1][2] (compare to Frege's symbol Begriffsschrift connective1.svg in his Begriffsschrift); the symbol ~ appeared in Russell in 1908;[3] an alternative notation is to add an horizontal line on top of the formula, as in \overline{P}; another alternative notation is to use a prime symbol as in P'.
  • Conjunction: the symbol ∧ appeared in Heyting in 1929[1] (compare to Peano's use of the set-theoretic notation of intersection[4]); & appeared at least in Schönfinkel in 1924;[5] . comes from Boole's interpretation of logic as an elementary algebra.
  • Disjunction: the symbol ∨ appeared in Russell in 1908 [3] (compare to Peano's use of the set-theoretic notation of union ∪); the symbol + is also used, in spite of the ambiguity coming from the fact that the + of ordinary elementary algebra is an exclusive or when interpreted logically in a two-element ring; punctually in the history a + together with a dot in the lower right corner has been used by Peirce,[6]
  • Implication: the symbol → can be seen in Hilbert in 1917;[7] ⊃ was used by Russell in 1908[3] (compare to Peano's inverted C notation); \Rightarrow was used in Vax.[8]
  • Biconditional: the symbol ≡ was used at least by Russell in 1908;[3] ↔ was used at least by Tarski in 1940;[9] ⇔ was used in Vax; other symbols appeared punctually in the history such as ⊃⊂ in Gentzen,[10] ~ in Schönfinkel[5] or ⊂⊃ in Chazal.[11]
  • True: the symbol 1 comes from Boole's interpretation of logic as an elementary algebra over the two-element ring; other notations include \bigwedge to be found in Peano.
  • False: the symbol 0 comes also from Boole's interpretation of logic as a ring; other notations include \bigvee 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).[12]

Table of binary logical connectives

There are sixteen Boolean functions associating the inputs P and Q with four-digit binary outputs.

Contradiction
Notation Equivalent
formulas
Truth table Venn diagram
\bot P \wedge ¬P
Opq
  Q
0 1
P 0    0   0 
1    0   0 
Venn0000.svg


Tautology
Notation Equivalent
formulas
Truth table Venn diagram
\top P \vee ¬P
Vpq
  Q
0 1
P 0    1   1 
1    1   1 
Venn1111.svg


Proposition P
Notation Equivalent
formulas
Truth table Venn diagram
P Ipq
  Q
0 1
P 0    0   0 
1    1   1 
Venn0101.svg


Negation of P
Notation Equivalent
formulas
Truth table Venn diagram
¬P
~P
Np
Fpq
  Q
0 1
P 0    1   1 
1    0   0 
Venn1010.svg


Proposition Q
Notation Equivalent
formulas
Truth table Venn diagram
Q Hpq
  Q
0 1
P 0    0   1 
1    0   1 
Venn0011.svg


Negation of Q
Notation Equivalent
formulas
Truth table Venn diagram
¬Q
~Q
Nq
Gpq
  Q
0 1
P 0    1   0 
1    1   0 
Venn1100.svg


Conjunction
Notation Equivalent
formulas
Truth table Venn diagram
P \wedge Q
P & Q
P · Q
P AND Q
P \not\rightarrow¬Q
¬P \not\leftarrow Q
¬P \downarrow ¬Q
Kpq
  Q
0 1
P 0    0   0 
1    0   1 
Venn0001.svg


Alternative denial
Notation Equivalent
formulas
Truth table Venn diagram
PQ
P | Q
P NAND Q
P → ¬Q
¬PQ
¬P \lor ¬Q
Dpq
  Q
0 1
P 0    1   1 
1    1   0 
Venn1110.svg


Disjunction
Notation Equivalent
formulas
Truth table Venn diagram
P \lor Q
P OR Q
P \leftarrow ¬Q
¬PQ
¬P ↑ ¬Q
¬(¬P \wedge ¬Q)
Apq
  Q
0 1
P 0    0   1 
1    1   1 
Venn0111.svg


Joint denial
Notation Equivalent
formulas
Truth table Venn diagram
PQ
P NOR Q
P \not\leftarrow ¬Q
¬P \not\rightarrow Q
¬P \wedge ¬Q
Xpq
  Q
0 1
P 0    1   0 
1    0   0 
Venn1000.svg


Material nonimplication
Notation Equivalent
formulas
Truth table Venn diagram
P \not\rightarrow Q
P \not\supset Q
P \wedge ¬Q
¬PQ
¬P \not\leftarrow ¬Q
Lpq
  Q
0 1
P 0    0   0 
1    1   0 
Venn0100.svg


Material implication
Notation Equivalent
formulas
Truth table Venn diagram
PQ
P \supset Q
P ↑ ¬Q
¬P \lor Q
¬P ← ¬Q
Cpq
  Q
0 1
P 0    1   1 
1    0   1 
Venn1011.svg


Converse nonimplication
Notation Equivalent
formulas
Truth table Venn diagram
P \not\leftarrow Q
P \not\subset Q
P ↓ ¬Q
¬P \wedge Q
¬P \not\rightarrow ¬Q
Mpq
  Q
0 1
P 0    0   1 
1    0   0 
Venn0010.svg


Converse implication
Notation Equivalent
formulas
Truth table Venn diagram
P \leftarrow Q
P \subset Q
P \lor ¬Q
¬PQ
¬P → ¬Q
Bpq
  Q
0 1
P 0    1   0 
1    1   1 
Venn1101.svg


Exclusive disjunction
Notation Equivalent
formulas
Truth table Venn diagram
P \not\leftrightarrow Q
P \not\equiv Q
P \oplus Q
P XOR Q
P \leftrightarrow ¬Q
¬P \leftrightarrow Q
¬P \not\leftrightarrow ¬Q
Jpq
  Q
0 1
P 0    0   1 
1    1   0 
Venn0110.svg


Biconditional
Notation Equivalent
formulas
Truth table Venn diagram
P \leftrightarrow Q
PQ
P XNOR Q
P IFF Q
P \not\leftrightarrow ¬Q
¬P \not\leftrightarrow Q
¬P \leftrightarrow ¬Q
Epq
  Q
0 1
P 0    1   0 
1    0   1 
Venn1001.svg


Functional completeness

Not all of the above-mentioned 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. 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
{\vee, ¬}, {\wedge, ¬}, {→, ¬}, {←, ¬}, {→, \bot}, {←, \bot}, {→, \not\leftrightarrow}, {←, \not\leftrightarrow}, {→, \not\to}, {→, \not\leftarrow}, {←, \not\to}, {←, \not\leftarrow}, {\not\to, ¬}, {\not\leftarrow, ¬}, {\not\to\top}, {\not\leftarrow\top}, {\not\to\leftrightarrow}, {\not\leftarrow\leftrightarrow}.
Three elements
{\lor, \leftrightarrow, \bot}, {\lor, \leftrightarrow, \not\leftrightarrow}, {\lor, \not\leftrightarrow, \top}, {\land, \leftrightarrow, \bot}, {\land, \leftrightarrow, \not\leftrightarrow}, {\land, \not\leftrightarrow, \top}.

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 connectives in a row, the order of the operations does not matter as long as the sequence of the operands is not changed.
  • Commutativity: The operands of the connective may be swapped without affecting the truth-value of the expression.
  • Distributivity: A connective denoted by · distributes over another connective denoted by +, if a · (b + c) = (a · b) + (a · c) for all operands a, b, c.
  • Idempotence: Whenever the operands of the operation are the same, the connective gives the operand as the result.
  • Absorption: A pair of connectives \land, \lor satisfies the absorption law if a\land(a\lor b)=a 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 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.
  • 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, fa1, ..., ¬an) = ¬f(a1, ..., an). E.g., \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., \vee, \wedge, \top, \rightarrow, \leftrightarrow, ⊂. (see validity)
  • 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., \vee, \wedge, \not\leftrightarrow, \bot, ⊄, ⊅. (see validity)

Arity

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. In k-valued logic, there are k nullary operators, kk unary operators, k^{k^2} binary operators, k^{k^3} ternary operators, and k^{k^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:

\Omega = \Omega_0 \cup \Omega_1 \cup \ldots \cup \Omega_j \cup \ldots \cup \Omega_m \,.

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

As a way of reducing the number of necessary parentheses, one may introduce precedence rules: ¬ has higher precedence than \wedge, \wedge higher than \vee, and \vee higher than →. So for example, P \vee Q \wedge ¬RS is short for (P \vee (Q \wedgeR))) → S.

Here is a table that shows a commonly used precedence of logical operators.

Operator Precedence
¬ 1
\wedge 2
\vee 3
4
\leftrightarrow 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 tables, 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:

  • 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(\lor)= 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 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.

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

See also

Portal icon Logic portal
Portal icon Thinking portal

Notes

  1. ^ a b Heyting (1929) Die formalen Regeln der intuitionistischen Logik.
  2. ^ Denis Roegel (2002), Petit panorama des notations logiques du 20e siècle (see chart on page 2).
  3. ^ a b c d Russell (1908) Mathematical logic as based on the theory of types (American Journal of Mathematics 30, p222–262, also in From Frege to Gödel edited by van Heijenoort).
  4. ^ Peano (1889) Arithmetices principia, nova methodo exposita.
  5. ^ a b Schönfinkel (1924) Über die Bausteine der mathematischen Logik, translated as On the building blocks of mathematical logic in From Frege to Gödel edited by van Heijenoort.
  6. ^ Peirce (1867) On an improvement in Boole's calculus of logic.
  7. ^ Hilbert (1917/1918) Prinzipien der Mathematik (Bernays' course notes).
  8. ^ Vax (1982) Lexique logique, Presses Universitaires de France.
  9. ^ Tarski (1940) Introduction to logic and to the methodology of deductive sciences.
  10. ^ Gentzen (1934) Untersuchungen über das logische Schließen.
  11. ^ Chazal (1996) : Éléments de logique formelle.
  12. ^ See Roegel

References

  • Bocheński, Józef Maria (1959), A Précis of Mathematical Logic, translated from the French and German editions by Otto Bird, D. Reidel, Dordrecht, South Holland.
  • Enderton, Herbert (2001), A Mathematical Introduction to Logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3 
  • Gamut, L.T.F (1991), "Chapter 2", Logic, Language and Meaning, 1, University of Chicago Press, pp. 54–64, ISBN 0-226-28285-3 

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • logical connective — loginė funkcija statusas T sritis automatika atitikmenys: angl. logical connective; logical function vok. Logikfunktion, f; logische Funktion, f; logische Verknüpfung, f rus. логическая связка, f; логическая функция, f pranc. fonction logique, f …   Automatikos terminų žodynas

  • Logical harmony — Logical harmony, a name coined by Sir Michael Dummett, is a supposed constraint on the rules of inference that can be used in a given logical system.The logician Gerhard Gentzen proposed that the meanings of logical connectives could be given by… …   Wikipedia

  • Connective — may be referring to: Bains::connective Logical connective Connective tissue Discourse connective, in linguistics, a word or phrase like therefore or in other words . See also Connection (disambiguation) This disambiguation page lists articl …   Wikipedia

  • Logical constant — In symbolic logic, a logical constant of a language L is a symbol that has the same semantic value in all models of (the expressions of) L . Two important types of logical constants are logical connectives and quantifiers. The equality predicate… …   Wikipedia

  • Logical disjunction — Disjunction redirects here. For separation of chromosomes, see Meiosis. For disjunctions in distribution, see Disjunct distribution. Venn diagram of the logical disjunction of A and B …   Wikipedia

  • Logical biconditional — In logic and mathematics, the logical biconditional (sometimes known as the material biconditional) is the logical connective of two statements asserting p if and only if q , where q is a hypothesis (or antecedent) and p is a conclusion (or… …   Wikipedia

  • logical function — loginė funkcija statusas T sritis automatika atitikmenys: angl. logical connective; logical function vok. Logikfunktion, f; logische Funktion, f; logische Verknüpfung, f rus. логическая связка, f; логическая функция, f pranc. fonction logique, f …   Automatikos terminų žodynas

  • Logical implication — In logic and mathematics, logical implication is a logical relation that holds between a set T of formulae and a formula B when every model (or interpretation or valuation) of T is also a model of B . In symbols,# T models B, # T Rightarrow B # T …   Wikipedia

  • connective — connectively, adv. connectivity /kon ek tiv i tee/, n. /keuh nek tiv/, adj. 1. serving or tending to connect: connective remarks between chapters. n. 2. something that connects. 3. Gram. a word used to connect words, phrases, clauses, and… …   Universalium

  • connective — In formal logic a connective is an element of a sentence that joins parts in such a way that the logical properties of the whole are a defined function of the logical properties of the parts. The most familiar connectives are those expressing the …   Philosophy dictionary


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.