In

When all inputs are true, the output is true. falsehood-preserving: yes

When all inputs are false, the output is false. Walsh spectrum: (1,-1,-1,1) Non

Wolfram MathWorld: Conjunction

* {{Authority control

logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...

, mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

and linguistics
Linguistics is the scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure. Linguis ...

, And ($\backslash wedge$) is the truth-functional
In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: The input and output of a truth function are all truth values; a truth function will always output exactly one ...

operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...

that represents this operator is typically written as $\backslash wedge$ or .
$A\; \backslash land\; B$ is true if and only if $A$ is true and $B$ is true, otherwise it is false.
An operand of a conjunction is a conjunct.
Beyond logic, the term "conjunction" also refers to similar concepts in other fields:
* In natural language, the denotation of expressions such as English
English usually refers to:
* English language
* English people
English may also refer to:
Peoples, culture, and language
* ''English'', an adjective for something of, from, or related to England
** English national ide ...

"and".
* In programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...

s, the short-circuit and control structure
In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an ''imp ...

.
* In set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...

, intersection.
* In lattice theory
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper bou ...

, logical conjunction ( greatest lower bound).
* In predicate logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

, universal quantification
In mathematical logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all". It expresses that a predicate can be satisfied by every member of a domain of discourse. In other ...

.
Notation

And is usually denoted by an infix operator: in mathematics and logic, it is denoted by $\backslash wedge$, or ; in electronics, ; and in programming languages,`&`

, `&&`

, or `and`

. In Jan Łukasiewicz
Jan Łukasiewicz (; 21 December 1878 – 13 February 1956) was a Polish logician and philosopher who is best known for Polish notation and Łukasiewicz logic His work centred on philosophical logic, mathematical logic and history of logic. ...

's prefix notation for logic, the operator is K, for Polish ''koniunkcja''.
Definition

Logical conjunction is anoperation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Ma ...

on two logical value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false'').
Computing
In some progra ...

s, typically the values of two proposition
In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...

s, that produces a value of ''true'' if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is b ...

both of its operands are true.
The conjunctive identity
Identity may refer to:
* Identity document
* Identity (philosophy)
* Identity (social science)
* Identity (mathematics)
Arts and entertainment Film and television
* ''Identity'' (1987 film), an Iranian film
* ''Identity'' (2003 film), ...

is true, which is to say that AND-ing an expression with true will never change the value of the expression. In keeping with the concept of vacuous truth
In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be satisfied. For example, the statement "she d ...

, when conjunction is defined as an operator or function of arbitrary arity, the empty conjunction (AND-ing over an empty set of operands) is often defined as having the result true.
Truth table

Thetruth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...

of $A\; \backslash land\; B$:
Defined by other operators

In systems where logical conjunction is not a primitive, it may be defined as :$A\; \backslash land\; B\; =\; \backslash neg(A\; \backslash to\; \backslash neg\; B)$ or :$A\; \backslash land\; B\; =\; \backslash neg(\backslash neg\; A\; \backslash lor\; \backslash neg\; B).$Introduction and elimination rules

As a rule of inference,conjunction introduction
Conjunction introduction (often abbreviated simply as conjunction and also called and introduction or adjunction) is a valid rule of inference of propositional logic. The rule makes it possible to introduce a conjunction into a logical proof. I ...

is a classically valid, simple argument form. The argument form has two premises, ''A'' and ''B''. Intuitively, it permits the inference of their conjunction.
:''A'',
:''B''.
:Therefore, ''A'' and ''B''.
or in logical operator
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...

notation:
:$A,$
:$B$
:$\backslash vdash\; A\; \backslash land\; B$
Here is an example of an argument that fits the form ''conjunction introduction
Conjunction introduction (often abbreviated simply as conjunction and also called and introduction or adjunction) is a valid rule of inference of propositional logic. The rule makes it possible to introduce a conjunction into a logical proof. I ...

'':
:Bob likes apples.
:Bob likes oranges.
:Therefore, Bob likes apples and Bob likes oranges.
Conjunction elimination
In propositional logic, conjunction elimination (also called ''and'' elimination, ∧ elimination, or simplification)Hurley is a valid immediate inference, argument form and rule of inference which makes the inference that, if the conjunction ' ...

is another classically valid, simple argument form. Intuitively, it permits the inference from any conjunction of either element of that conjunction.
:''A'' and ''B''.
:Therefore, ''A''.
...or alternatively,
:''A'' and ''B''.
:Therefore, ''B''.
In logical operator
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...

notation:
:$A\; \backslash land\; B$
:$\backslash vdash\; A$
...or alternatively,
:$A\; \backslash land\; B$
:$\backslash vdash\; B$
Negation

Definition

A conjunction $A\backslash land\; B$ is proven false by establishing either $\backslash neg\; A$ or $\backslash neg\; B$. In terms of the object language, this reads :$\backslash neg\; A\backslash to\backslash neg(A\backslash land\; B)$ This formula can be seen as a special case of :$(A\backslash to\; C)\; \backslash to\; (\; (A\backslash land\; B)\backslash to\; C\; )$ when $C$ is a false proposition.Other proof strategies

If $A$ implies $\backslash neg\; B$, then both $\backslash neg\; A$ as well as $A$ prove the conjunction false: :$(A\backslash to\backslash negB)\backslash to\backslash neg(A\backslash land\; B)$ In other words, a conjunction can actually be proven false just by knowing about the relation of its conjuncts, and not necessary about their truth values. This formula can be seen as a special case of :$(A\backslash to(B\backslash to\; C))\backslash to\; (\; (A\backslash land\; B)\backslash to\; C\; )$ when $C$ is a false proposition. Either of the above are constructively valid proofs by contradiction.Properties

commutativity: yesassociativity
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...

: yes
distributivity
In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality
x \cdot (y + z) = x \cdot y + x \cdot z
is always true in elementary algebra.
For example, in elementary arithmeti ...

: with various operations, especially with '' or''
idempotency
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...

: yesmonotonicity
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of orde ...

: yes
truth-preserving: yesWhen all inputs are true, the output is true. falsehood-preserving: yes

When all inputs are false, the output is false. Walsh spectrum: (1,-1,-1,1) Non

linearity
Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...

: 1 (the function is bent)
If using binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...

values for true (1) and false (0), then ''logical conjunction'' works exactly like normal arithmetic multiplication.
Applications in computer engineering

In high-level computer programming anddigital electronics
Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals.
Digital electronic circuits are usual ...

, logical conjunction is commonly represented by an infix operator, usually as a keyword such as "`AND`

", an algebraic multiplication, or the ampersand symbol `&`

(sometimes doubled as in `&&`

). Many languages also provide short-circuit
A short circuit (sometimes abbreviated to short or s/c) is an electrical circuit that allows a current to travel along an unintended path with no or very low electrical impedance. This results in an excessive current flowing through the circuit. ...

control structures corresponding to logical conjunction.
Logical conjunction is often used for bitwise operations, where `0`

corresponds to false and `1`

to true:
* `0 AND 0`

= `0`

,
* `0 AND 1`

= `0`

,
* `1 AND 0`

= `0`

,
* `1 AND 1`

= `1`

.
The operation can also be applied to two binary words
A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no conse ...

viewed as bitstring
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level ...

s of equal length, by taking the bitwise AND of each pair of bits at corresponding positions. For example:
* `11000110 AND 10100011`

= `10000010`

.
This can be used to select part of a bitstring using a bit mask
In computer science, a mask or bitmask is data that is used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, Word (computer architecture), word, etc. can be set either on or off, or inverted fro ...

. For example, `10011101 AND 00001000`

= `00001000`

extracts the fifth bit of an 8-bit bitstring.
In computer networking
A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ...

, bit masks are used to derive the network address of a subnet
A subnetwork or subnet is a logical subdivision of an IP network. Updated by RFC 6918. The practice of dividing a network into two or more networks is called subnetting.
Computers that belong to the same subnet are addressed with an identical ...

within an existing network from a given IP address
An Internet Protocol address (IP address) is a numerical label such as that is connected to a computer network that uses the Internet Protocol for communication.. Updated by . An IP address serves two main functions: network interface ident ...

, by ANDing the IP address and the subnet mask
A subnetwork or subnet is a logical subdivision of an IP network. Updated by RFC 6918. The practice of dividing a network into two or more networks is called subnetting.
Computers that belong to the same subnet are addressed with an identical ...

.
Logical conjunction "`AND`

" is also used in SQL operations to form database
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases s ...

queries.
The Curry–Howard correspondence relates logical conjunction to product type
In programming languages and type theory, a product of ''types'' is another, compounded, type in a structure. The "operands" of the product are types, and the structure of a product type is determined by the fixed order of the operands in the prod ...

s.
Set-theoretic correspondence

The membership of an element of an intersection set inset theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...

is defined in terms of a logical conjunction: ''x'' ∈ ''A'' ∩ ''B'' if and only if (''x'' ∈ ''A'') ∧ (''x'' ∈ ''B''). Through this correspondence, set-theoretic intersection shares several properties with logical conjunction, such as associativity
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...

, commutativity and idempotence
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...

.
Natural language

As with other notions formalized in mathematical logic, the logical conjunction ''and'' is related to, but not the same as, thegrammatical conjunction
In grammar, a conjunction (abbreviated or ) is a part of speech that connects words, phrases, or clauses that are called the conjuncts of the conjunctions. That definition may overlap with that of other parts of speech and so what constitutes a ...

''and'' in natural languages.
English "and" has properties not captured by logical conjunction. For example, "and" sometimes implies order having the sense of "then". For example, "They got married and had a child" in common discourse means that the marriage came before the child.
The word "and" can also imply a partition of a thing into parts, as "The American flag is red, white, and blue." Here, it is not meant that the flag is ''at once'' red, white, and blue, but rather that it has a part of each color.
See also

*And-inverter graph
An and-inverter graph (AIG) is a directed, acyclic Graph (discrete mathematics), graph that represents a structural implementation of the logical functionality of a digital circuit, circuit or network. An AIG consists of two-input nodes represent ...

* AND gate
The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not al ...

* Bitwise AND
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic oper ...

* Boolean algebra (logic)
* Boolean algebra topics
This is a list of topics around Boolean algebra and propositional logic.
Articles with a wide scope and introductions
* Algebra of sets Talk:Algebra of sets,
* Boolean algebra (structure) Talk:Boolean algebra (structure),
* Boolean algebra ...

* Boolean conjunctive query
* Boolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as ...

* Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...

* Boolean-valued function
A Boolean-valued function (sometimes called a predicate or a proposition) is a function of the type f : X → B, where X is an arbitrary set and where B is a Boolean domain, i.e. a generic two-element set, (for example B = ), whose elements are i ...

* Conjunction elimination
In propositional logic, conjunction elimination (also called ''and'' elimination, ∧ elimination, or simplification)Hurley is a valid immediate inference, argument form and rule of inference which makes the inference that, if the conjunction ' ...

* De Morgan's laws
In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British math ...

* First-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

* Fréchet inequalities In probabilistic logic, the Fréchet inequalities, also known as the Boole–Fréchet inequalities, are rules implicit in the work of George BooleBoole, G. (1854). ''An Investigation of the Laws of Thought, On Which Are Founded the Mathematical Theo ...

* Grammatical conjunction
In grammar, a conjunction (abbreviated or ) is a part of speech that connects words, phrases, or clauses that are called the conjuncts of the conjunctions. That definition may overlap with that of other parts of speech and so what constitutes a ...

* Logical disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...

* Logical negation
* Logical graph A logical graph is a special type of diagrammatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic.
In his papers on '' qualitative logic'', '' entitative graphs'', and '' existential grap ...

* Operation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Ma ...

* Peano–Russell notation In mathematical logic, Peano–Russell notation was Bertrand Russell's application of Giuseppe Peano's logical notation to the logical notions of Frege and was used in the writing of ''Principia Mathematica'' in collaboration with Alfred North White ...

* Propositional calculus
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...

References

External links

*Wolfram MathWorld: Conjunction

* {{Authority control

Conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...

Semantics