Logical connective
You don't need to be Editor-In-Chief to add or edit content to WikiDoc. You can begin to add to or edit text on this WikiDoc page by clicking on the edit button at the top of this page. Next enter or edit the information that you would like to appear here. Once you are done editing, scroll down and click the Save page button at the bottom of the page.
 |
This article or section is in need of attention from an expert on the subject. WikiProject Mathematics may be able to help recruit one. |
 |
It has been suggested that Logical constant be merged into this article or section. (Discuss) |
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 a sentence, or the symbol for such an operation that corresponds to an operation on the logical values of those sentences. A logical connective serves to produce a compound sentence from one or two other sentences. 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.
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:
- PTemplate:AndQ (It is raining and I am indoors.)
- PTemplate:ImpQ (If it is raining then I am indoors.)
- QTemplate:ImpP (It is raining if I am indoors.)
- PTemplate:EqvQ (It is raining if and only if I am indoors.)
- Template:NotP (It is not the case that it is raining.)
|
The basic logical operators are :
|
Some others are: |
or 
)
)
Contents |
Definitions
Truth tables
| p | q | T | ↑ | → | ~p | ← | ~q | 
| ↓ | ∨ | 
| q | ⊄ | p | ⊅ | & | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | T | T | F | T | F | T | F | T | F | T | F | T | F | T | F | T | F |
| T | F | T | T | F | F | T | T | F | F | T | T | F | F | T | T | F | F |
| F | T | T | T | T | T | F | F | F | F | T | T | T | T | F | F | F | F |
| F | F | T | T | T | T | T | T | T | T | F | F | F | F | F | F | F | F |
Venn diagrams
The binary logical operators may be expressed as Venn diagrams. The white area of each figure corresponds to "true" and the black to "false".
|
Image:Johnston Diagram- A or Not A.svg tautology |
Image:Johnston Diagram- A nand B.png a nand b |
Image:Johnston Diagram- A implies B.svg if a then b |
|
|
Image:Johnston Diagram- B implies A.svg if b then a |
|||
|
Image:Johnston Diagram- B.svg b is true |
Image:Johnston Diagram- Not Converse of If A then B.png not the converse of if a then b |
||
|
Image:Johnston Diagram- A.svg a is true |
Image:Johnston Diagram Not If a Then b.png not if a then b |
Image:Johnston Diagram- A and Not A.svg contradiction |
The above arrangement of Venn Diagrams is from The Geometry of Logic.
Note the similarity between the symbols for "and" (
) and set-theoretic intersection (
); likewise for "or" (
) and set-theoretic union (
). This is not a coincidence: the definition of the intersection uses "and" and the definition of union uses "or".
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 { ↑ }.
All and only the following are functionally complete sets of operators:
{ ↓ }, { ↑ }, { 
, 
}, { , }, { , ⊂ },
{ , ⊄ },
{ , },
{ , ⊅ },
{ ⊄, },
{ ⊂, },
{ ⊅, },
{ ⊂, ⊄ },
{ , },
{ ⊂, ⊅ },
{ 
, },
{ ⊄, },
{ ⊅, }
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 functionally complete set of operators contains at least one member lacking each of these five qualities:
- monotonic : If f(a1, ... , an) ≤ f(b1, ... , bn) for all a1, ... , an
{0,1} such that a1 ≤ b1, a2 ≤ b2, ... , an ≤ bn { , , 
, }
- linear : Each variable always makes a difference in the truth-value of the operation or it never makes a difference { , , , , }
- 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 compliment of reading it from bottom to top. { }
- 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. { , , , , , ⊂ }
- 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. { , , , , ⊄, ⊅ }
Arity
In two-valued logic there are 4 unary operators, 16 binary operators, and 256 ternary operators. In three valued logic there are 9 unary operators, 19683 binary operators, and 7625597484987 ternary operators.
"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 partitioned 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:
- 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 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.
| Operator | Precedence |
|---|---|
| ¬ | 1 |
| | 2 |
| | 3 |
| → | 4 |
| ↔ | 5 |
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
See also
Template:Logical Operators Template:Logic Template:Logic-stubda:Logisk operator de:Boolescher Operator el:Λογικές συναρτήσεις ko:논리 연산 is:Rökaðgerð it:Connettivo logico he:פעולה בוליאנית mk:Логичка операција nl:Booleaanse operator ja:論理演算sv:Logisk operator th:ตัวดำเนินการทางตรรกศาสตร์
Acknowledgement and Attribution Regarding Sources of Content
Some of the initial content on this page may be incorporated in part from copyleft sources in the public domain including wikis such as Wikipedia and AskDrWiki. Drug information for patients came from the The National Library of Medicine. Infectious disease information may have come from the Centers for Disease Control (CDC). Differential Diagnoses are drawn from clinicians as well as an amalgamation of 3 sources: 1.The Disease Database; 2. Kahan, Scott, Smith, Ellen G. In A Page: Signs and Symptoms. Malden, Massachusetts: Blackwell Publishing, 2004:3; 3. Sailer, Christian, Wasner, Susanne. Differential Diagnosis Pocket. Hermosa Beach, CA: Borm Bruckmeir Publishing LLC, 2002:7 .
