HOME

TheInfoList



OR:

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 (\wedge) 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 \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 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 \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-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 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(A \to \neg B) or :A \land B = \neg(\neg A \lor \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 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 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: : 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(A\land B) This formula can be seen as a special case of :(A\to C) \to ( (A\land B)\to C ) 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: :(A\to\negB)\to\neg(A\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\to(B\to C))\to ( (A\land B)\to C ) when C 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