TheInfoList

OR: In logic,
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, And ($\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 on ...
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 that represents this operator is typically written as $\wedge$ or . $A \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 In linguistics and philosophy, the denotation of an expression is its literal meaning. For instance, the English word "warm" denotes the property of being warm. Denotation is contrasted with other aspects of meaning including connotation. For i ...
of expressions such as English "and". * In programming languages, the short-circuit and control structure. * In set theory,
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, thei ...
. * 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 boun ...
, logical conjunction ( greatest lower bound). * In predicate logic,
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 othe ...
.

# Notation

And is usually denoted by an infix operator: in mathematics and logic, it is denoted by $\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 an
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 ...
on two logical values, 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 ...
s, that produces a value of ''true'' if and only if both of its operands are true. The conjunctive identity 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, when conjunction is defined as an operator or function of arbitrary
arity Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematic ...
, the empty conjunction (AND-ing over an empty set of operands) is often defined as having the result true.

## Truth table The
truth 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 argum ...
of $A \land B$:

## Defined by other operators

In systems where logical conjunction is not a primitive, it may be defined as :$A \land B = \neg\left(A \to \neg B\right)$ or :$A \land B = \neg\left(\neg A \lor \neg B\right).$

# 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 In logic, logical form of a Statement (logic), statement is a precisely-specified Semantics, semantic version of that statement in a formal system. Informally, the logical form attempts to formalize a possibly Syntactic ambiguity, ambiguous sta ...
. 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 notation: :$A,$ :$B$ :$\vdash A \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 In logic, logical form of a Statement (logic), statement is a precisely-specified Semantics, semantic version of that statement in a formal system. Informally, the logical form attempts to formalize a possibly Syntactic ambiguity, ambiguous sta ...
. 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 notation: :$A \land B$ :$\vdash A$ ...or alternatively, :$A \land B$ :$\vdash B$

# Negation

## Definition

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

## Other proof strategies

If $A$ implies $\neg B$, then both $\neg A$ as well as $A$ prove the conjunction false: :$\left(A\to\negB\right)\to\neg\left(A\land B\right)$ 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 :$\left(A\to\left(B\to C\right)\right)\to \left( \left(A\land B\right)\to C \right)$ when $C$ is a false proposition. Either of the above are constructively valid proofs by contradiction.

# Properties

commutativity In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
: yes
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 replacemen ...
: 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 arithmet ...
: with various operations, especially with '' or'' idempotency: yes
monotonicity 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 order ...
: yes truth-preserving: yes
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
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 r ...
: 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 and
digital 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 usually ...
, 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 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 viewed as bitstrings 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. For example, 10011101 AND 00001000  =  00001000 extracts the fifth bit of an 8-bit bitstring. In computer networking, 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, 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 queries. The Curry–Howard correspondence relates logical conjunction to product types.

# Set-theoretic correspondence

The membership of an element of an intersection set in set theory 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 replacemen ...
,
commutativity In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
and idempotence.

# Natural language

As with other notions formalized in mathematical logic, the logical conjunction ''and'' is related to, but not the same as, the grammatical conjunction ''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.

*
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 *
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 ope ...
*
Boolean algebra (logic) In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas ...
* Boolean algebra topics * 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 ...
* Boolean 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 ar ...
*
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 *
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 quant ...
*
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 The ...
* Grammatical conjunction *
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 In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fal ...
* Logical graph *
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 *
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 ...