Logical connective

From Wikipedia, the free encyclopedia

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 (Enderton 2001:45). The truth value of the compound is uniquely determined by the truth values of the simpler sentences. Each logical connective therefore represents a function, called a truth function. For this reason, logical connectives are sometimes called truth-functional connectives.

The logical connectives commonly used in mathematics include conjunction (AND), disjunction (OR), and implication.

1 Truth functions in natural languages
2 Truth functions in formal languages
3 Examples
4 All binary logical connectives
5 Functional completeness
6 Truth functions and interpretation function
7 Properties
8 Arity
9 Order of precedence
10 Applications in computer science
11 See also
12 References
13 External links

[edit] Truth functions in natural languages

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 both 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 fetch a pail of water, not because Jack had gone up the Hill at all. Thus and is a logical connective but so is not.

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" (inclusive 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 "it is false that" (negation) "it is not the case that" (negation) are also English words expressing a logical connective, even though they are applied to a single statement, and do not connect two statements.

[edit] 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". 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.

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.

[edit] Examples

Commonly used logical connectives include:

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 $=$ )

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.
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 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 represented in symbols, respectively:

P & Q
P $\rightarrow$ Q
Q $\rightarrow$ P
P $\leftrightarrow$ Q
¬P

[edit] All binary logical connectives

There are sixteen different 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

		Q
		T	F
P	T	F	F
P	F	F	F

Tautology

Notation

Equivalent
formulas

Truth table

Venn diagram

$\top$

P $\vee$ ¬P

		Q
		T	F
P	T	T	T
P	F	T	T

Conjunction

Notation

Equivalent
formulas

Truth table

Venn diagram

P $\wedge$ Q
P & Q
P AND Q

P $\not\rightarrow$ ¬Q
¬P $\not\leftarrow$ Q
¬P $\downarrow$ ¬Q

		Q
		T	F
P	T	T	F
P	F	F	F

Alternative denial

Notation

Equivalent
formulas

Truth table

Venn diagram

P ↑ Q
P | Q
P NAND Q

P → ¬Q
¬P ← Q
¬P $\lor$ ¬Q

		Q
		T	F
P	T	F	T
P	F	T	T

Material nonimplication

Notation

Equivalent
formulas

Truth table

Venn diagram

P $\not\rightarrow$ Q
P $\not\supset$ Q

P & ¬Q
¬P ↓ Q
¬P $\not\leftarrow$ ¬Q

		Q
		T	F
P	T	F	T
P	F	F	F

Material implication

Notation

Equivalent
formulas

Truth table

Venn diagram

P → Q
P $\supset$ Q

P ↑ ¬Q
¬P $\lor$ Q
¬P ← ¬Q

		Q
		T	F
P	T	T	F
P	F	T	T

Proposition P

Notation

Equivalent
formulas

Truth table

Venn diagram

P

n/a

		Q
		T	F
P	T	T	T
P	F	F	F

Negation of P

Notation

Equivalent
formulas

Truth table

Venn diagram

¬P

n/a

		Q
		T	F
P	T	F	F
P	F	T	T

Converse nonimplication

Notation

Equivalent
formulas

Truth table

Venn diagram

P $\not\leftarrow$ Q
P $\not\subset$ Q

P ↓ ¬Q
¬P & Q
¬P $\not\rightarrow$ ¬Q

		Q
		T	F
P	T	F	F
P	F	T	F

Converse implication

Notation

Equivalent
formulas

Truth table

Venn diagram

P $\leftarrow$ Q
P $\subset$ Q

P $\lor$ ¬Q
¬P ↑ Q
¬P → ¬Q

		Q
		T	F
P	T	T	T
P	F	F	T

Proposition Q

Notation

Equivalent
formulas

Truth table

Venn diagram

Q

n/a

		Q
		T	F
P	T	T	F
P	F	T	F

Negation of Q

Notation

Equivalent
formulas

Truth table

Venn diagram

¬Q

n/a

		Q
		T	F
P	T	F	T
P	F	F	T

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

		Q
		T	F
P	T	F	T
P	F	T	F

Biconditional

Notation

Equivalent
formulas

Truth table

Venn diagram

P $\leftrightarrow$ Q
P ≡ Q
P XNOR Q

P $\not\leftrightarrow$ ¬Q
¬P $\not\leftrightarrow$ Q
¬P $\leftrightarrow$ ¬Q

		Q
		T	F
P	T	T	F
P	F	F	T

Disjunction

Notation

Equivalent
formulas

Truth table

Venn diagram

P $\lor$ Q
P OR Q

P $\leftarrow$ ¬Q
¬P → Q
¬P ↑ ¬Q

		Q
		T	F
P	T	T	T
P	F	T	F

Joint denial

Notation

Equivalent
formulas

Truth table

Venn diagram

P ↓ Q
P NOR Q

P $\not\leftarrow$ ¬Q
¬P $\not\rightarrow$ Q
¬P & ¬Q

		Q
		T	F
P	T	F	F
P	F	F	T

[edit] 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 not exceeding 2) of operators whose arities do not exceed 2:

{ ↓ }, { ↑ }, { $\rightarrow$ , $\neg$ }, { $\rightarrow$ , $\not\leftrightarrow$ }, { $\neg$ , ⊂ }, { $\rightarrow$ , ⊄ }, { $\vee$ , $\neg$ }, { $\rightarrow$ , ⊅ }, { ⊄, $\neg$ }, { ⊂, $\not\leftrightarrow$ }, { ⊅, $\neg$ }, { ⊂, ⊄ }, { $\wedge$ , $\neg$ }, { ⊂, ⊅ }, { $\bot$ , $\rightarrow$ }, { ⊄, $\leftrightarrow$ }, { ⊅, $\leftrightarrow$ }

[edit] Truth functions and interpretation function

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). Let I be an interpretation function, let Φ, Ψ be any two sentences and let the truth function f_nand be defined as:-

f_nand(T,T)=F; f_nand(T,F)=f_nand(F,T)=f_nand(F,F)=T

Then, for convenience, we define f_not, f_or f_and etc. by means of f_nand:-

f_not(x)=f_nand(x,x)
f_or(x,y)= f_nand(f_not(x), f_not(y))
f_and(x,y)=f_not(f_nand(x,y))

or, alternatively we define f_not, f_or f_and, etc directly:-

f_not(T)=F; f_not(F)=T;
f_or(T,T)=f_or(T,F)=f_or(F,T)=T;f_or(F,F)=F
f_and(T,T)=T; f_and(T,F)=f_and(F,T)=f_and(F,F)=F

Then

I(~)=I(¬)=f_not
I(&)=I(^)=I(&)=f_and
I(v)=I( $\lor$ )= f_or
I(~Φ)=I(¬Φ=I¬(I(Φ)=f_not(I(Φ))
I(Φ&Ψ) = I(&)(I(Φ), I(Ψ))= f_and(I(Φ), I(Ψ))

etc.

Thus if s is a sentence that is a string of symbols consisting of logical symbols v₁..v_n representing logical connectives, and non-logical symbols c₁..c_n , then if and only if I(v₁)..I(v_n) have been provided interpreting v₁ to v_n by means of f_nand (or any other set of functional complete truth-functions) then the truth-value of I(s) is determined entirely by the truth-values of c₁..c_n, i.e. of I(c₁)..I(c_n). In other words, as expected and required, S is true or false only under an interpretation of all its non-logical symbols.

[edit] 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.
Commutivity: 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.
Idempotency: Whenever the operands of the operation are the same, the connective gives the operand as the result.
Absorption: A pair of conenctives $\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(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., $\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 f(¬a₁, ..., ¬a_n) = ¬f(a₁, ..., a_n). 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$ , ⊂.
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$ , ⊄, ⊅.

[edit] Arity

Main article: 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. 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, P → Q, P ↔ Q).

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 \} \,$

[edit] 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 a commonly used precedence of logical operators.

Operator	Precedence
¬	1
∧	2
∨	3
→	4
$\leftrightarrow$	5

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

[edit] 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.

[edit] See also

Thinking portal

[edit] References

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). "2". Logic, languagage and Meaning,. 1: Introduction to Logic. University of Chicago Press. pp. 54..64. ISBN 0-226-28285-3.

[edit] External links

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

Logic portal

Logical connective

From Wikipedia, the free encyclopedia

Contents

[edit] Truth functions in natural languages

[edit] Truth functions in formal languages

[edit] Examples

[edit] All binary logical connectives

[edit] Functional completeness

[edit] Truth functions and interpretation function

[edit] Properties

[edit] Arity

[edit] Order of precedence

[edit] Applications in computer science

[edit] See also

[edit] References

[edit] External links

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages