Sufficiently connected

Sufficiently connected

In propositional logic, a set of Boolean operators is called sufficient if it permits the realisation of any possible truth table.

Example truth table (Xor):

Using a complete Boolean algebra which does not include XOR (such as the well-known AND OR NOT set), this function can be realised as follows:

(a or b) and not (a and b).

However, other complete Boolean algebras are possible, such as NAND or NOR (either gate can form a complete Boolean algebra by itself – the proof is detailed on their pages).

Note that just because a set of gates forms a complete Boolean algebra does not mean that the resulting expressions will be simple. To gain an XOR function using only NAND gates, for example, is a fairly complex expression – the important thing is that it exists.

See also

* Sheffer stroke

References

*


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Henry of Ghent and Duns Scotus — Stephen Dumont LIFE AND WORKS Henry of Ghent Henry of Ghent was arguably the most influential Latin theologian between Thomas Aquinas and Duns Scotus, regent as a leading master of theology at the University of Paris for the better part of the… …   History of philosophy

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Congressional power of enforcement — A Congressional power of enforcement is included in a number of amendments to the United States Constitution. The language The Congress shall have power to enforce this article by appropriate legislation is used, with slight variations, in… …   Wikipedia

  • Dormant Commerce Clause — The Dormant Commerce Clause, also known as the Negative Commerce Clause, is a legal doctrine that courts in the United States have inferred from the Commerce Clause in Article I of the United States Constitution. The Commerce Clause expressly… …   Wikipedia

  • Pinnate — is a term used to describe feather like or multi divided features arising from both sides of a common axis in plant or animal structures, and comes from the Latin word pinna meaning feather , wing , or fin . A similar term is pectinate, which… …   Wikipedia

  • Leaf shape — Chart illustrating leaf morphology terms. Click the image for the details. Oddly pi …   Wikipedia

  • Unifund Assurance Co. v. Insurance Corp. of British Columbia — SCCInfoBox case name=Unifund Assurance Co. v. Insurance Corp. of British Columbia full case name= heard date=December 12, 2002 decided date=July 17, 2003 citations= docket=28745 history= ruling= Appeal allowed ratio= SCC=2002 2003 Majority=Binnie …   Wikipedia

  • I — Roman numeral for 1. The personal pronoun in the singular of the nominative case. Sufficiently connected with the person executing the instrument where it appears in the body of a deed, that he is bound, although his name does not appear above… …   Ballentine's law dictionary

  • we — The personal pronoun in the plural of the nominative case. Sufficiently connected with the persons executing the instrument where it appears in the body of the deed, that they are bound, although their names do not appear in the instrument above… …   Ballentine's law dictionary

  • HEBREW GRAMMAR — The following entry is divided into two sections: an Introduction for the non specialist and (II) a detailed survey. [i] HEBREW GRAMMAR: AN INTRODUCTION There are four main phases in the history of the Hebrew language: the biblical or classical,… …   Encyclopedia of Judaism

Share the article and excerpts

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