FACTOID # 16: In the 2000 Presidential Election, Texas gave Ralph Nader the 3rd highest popular vote count of any US state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Connective" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Connective

In logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. For example, considering the assertions "It's raining", and "I'm inside", we can form the compound assertions "it's raining, and I'm inside" or "it's not raining" or "if it's raining, then I'm inside."


A new statement or proposition combining two statements is called a compound statement or compound proposition.


The basic operators are "not" (, or ~), "and" (∧, , or &), "or" (∨), "conditional" (→), and "biconditional" (iff) (↔). "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).


Note the similarity between the symbols for "and" () and "set theoretic intersection" (∩); likewise for "or" (∨) and "union (∪). This is not a coincidence: the definition of the intersection uses "and" and the definition of union uses "or".


Truth tables for these connectives:

P Q P P ∧ Q P ∨ Q P → Q P ↔ Q
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T


In order to reduce the number of necessary parentheses, one introduces precendence rules: has higher precedence than ∧, ∧ higher than ∨, and ∨ higher than →. So for example, P ∨ Q ∧ R → S is short for (P ∨ (Q ∧ ( R))) → S.


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


For the sake of convenience (and brevity), only the five most-commonly used operators (in math) are listed above. One can also consider other connectives, such as NAND ("not-and"), XOR ("not-biconditional"), and NOR ("not-or").


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.


If you throw away all the operators that are not necessary, what operators are you left with ? Which conditionals are the crucial must-have ones ? Surprisingly, there is more than one answer to that question.

  • All connectives can be expressed with NAND alone.
  • Since NAND can be built from NOT and AND, and we know that all connectives can be built from NAND alone, clearly all connectives can be built from combinations of NOT and AND.
  • ... and several other answers.

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, quantum dots computing, or Tinker Toys) is "logically 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 logically complete.


See also


  Results from FactBites:
 
SIU SOM Histology INTRO (5924 words)
Connective tissue is derived from mesenchyme (unlike most epithelial tissue which is derived from ectoderm and endoderm).
Connective tissue may be distinguished as either loose or dense, depending on the proportion of fibers.
Dense elastic connective tissue is found wherever the elasticity of elastin is of paramount importance, as in the ligamentum flavum (flavum refers to the yellow color conferred by the elastin) and the aorta.
Connective tissue - Wikipedia, the free encyclopedia (341 words)
Connective tissue is any type of biological tissue with an extensive extracellular matrix and often serves to support, bind together, and protect organs.
Loose connective tissue or Areolar connective tissue holds organs and epithelia in place, and has a variety of proteinaceous fibers, including collagen and elastin.
Reticular connective tissue is a network of reticular fibers (fine collagen) that form a soft skeleton to support the lymphoid organs (lymph nodes, bone marrow, and spleen.)
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m