In
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 prem ...
,
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. Ling ...
, And (
) is the
truth-functional 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
or .
is true if and only if
is true and
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 ...
"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
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 concern ...
,
intersection.
* In
lattice theory, logical conjunction (
greatest lower bound
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest ...
).
* In
predicate logic,
universal quantification.
Notation
And is usually denoted by an infix operator: in mathematics and logic, it is denoted by
,
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-Man ...
on two
logical values, typically the values of two
propositions, 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 bic ...
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), an ...
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, 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 arg ...
of
:
Defined by other operators
In systems where logical conjunction is not a primitive, it may be defined as
:
or
:
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 notation:
:
:
:
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 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 notation:
:
:
...or alternatively,
:
:
Negation
Definition
A conjunction
is proven false by establishing either
or
. In terms of the object language, this reads
:
This formula can be seen as a special case of
:
when
is a false proposition.
Other proof strategies
If
implies
, then both
as well as
prove the conjunction false:
:
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
:
when
is a false proposition.
Either of the above are constructively valid proofs by contradiction.
Properties
commutativity: yes
associativity: yes
distributivity: with various operations, especially with ''
or''
idempotency: yes
monotonicity: 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: 1 (the function is
bent)
If using
binary 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 usu ...
, 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
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, etc. can be set either on or off, or inverted from on to off (or vice versa) ...
. 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 within an existing network from a given
IP address, by ANDing the IP address and the
subnet mask.
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 ...
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
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 concern ...
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,
commutativity 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
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 constitu ...
''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 that represents a structural implementation of the logical functionality of a circuit or network. An AIG consists of two-input nodes representing logical conjunction, terminal nodes labele ...
*
AND gate
*
Bitwise AND
*
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
* Boolean algebra (structure)
* Boolean algebra
* Field of sets
* Logical connective
* Propo ...
*
Boolean conjunctive query In the theory of relational databases, a Boolean conjunctive query is a conjunctive query without distinguished predicates, i.e., a query in the form R_1(t_1) \wedge \cdots \wedge R_n(t_n), where each R_i is a relation symbol and each t_i is a tupl ...
*
Boolean domain
*
Boolean function
*
Boolean-valued function
*
Conjunction elimination
*
De Morgan's laws
*
First-order logic
*
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 constitu ...
*
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-Man ...
*
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 b ...
References
External links
*
Wolfram MathWorld: Conjunction*
{{Authority control
Conjunction
Semantics