Movatterモバイル変換

[0]ホーム

Jump to content

Logical conjunction

Edit links

From Wikipedia, the free encyclopedia

Logical connective AND

Not to be confused withCircumflex Agent (^),Capital Lambda (Λ),Turned V (Λ), orExterior Product (∧).

Logical conjunction
AND

Definition	$x y {\displaystyle xy}$
Truth table	$(1000) {\displaystyle (1000)}$
Logic gate
Normal forms
Disjunctive	$x y {\displaystyle xy}$
Conjunctive	$x y {\displaystyle xy}$
Zhegalkin polynomial	$x y {\displaystyle xy}$
Post's lattices
0-preserving	yes
1-preserving	yes
Monotone	yes
Affine	no
Self-dual	no
v t e

Logical connectives

NOT	$\neg A,-A,{\overline {A}},{\sim }A$
AND	$A\land B,A\cdot B,AB,A\mathop {\&} B,A\mathop {\&\&} B$
NAND	$A\mathrel {\overline {\land }} B,A\uparrow B,A\mid B,{\overline {A\cdot B}}$
OR	$A\lor B,A+B,A\mid B,A\parallel B$
NOR	$A\mathrel {\overline {\lor }} B,A\downarrow B,{\overline {A+B}}$
XNOR	$A\odot B,{\overline {A\mathrel {\overline {\lor }} B}}$
└equivalent	$A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B$
XOR	$A\mathrel {\underline {\lor }} B,A\oplus B$
└ nonequivalent	$A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B$
implies	$A\Rightarrow B,A\supset B,A\rightarrow B$
nonimplication (NIMPLY)	$A\not \Rightarrow B,A\not \supset B,A\nrightarrow B$
converse	$A\Leftarrow B,A\subset B,A\leftarrow B$
converse nonimplication	$A\not \Leftarrow B,A\not \subset B,A\nleftarrow B$

Related concepts

Applications

Notation

[edit]

And is usually denoted by an infix operator: in mathematics and logic, it is denoted by a "wedge" $\wedge$ (UnicodeU+2227 ∧LOGICAL AND),^[1] $\&$ or $\times$ ; in electronics, $\cdot$ ; and in programming languages&,&&, orand. InJan Łukasiewicz'sprefix notation for logic, the operator is $K {\displaystyle K}$ , for Polishkoniunkcja.^[4]

In mathematics, the conjunction of an arbitrary number of elements $a_{1},\ldots ,a_{n}$ can be denoted as aniterated binary operation using a "big wedge" ⋀ (UnicodeU+22C0 ⋀N-ARY LOGICAL AND):^[5]

$\bigwedge _{i=1}^{n}a_{i}=a_{1}\wedge a_{2}\wedge \ldots a_{n-1}\wedge a_{n}$

Definition

[edit]

Inclassical logic,logical conjunction is anoperation on twological values, typically the values of twopropositions, that produces a value oftrueif and only if (also known as iff) both of its operands are true.^[2]^[1]

The conjunctiveidentity 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 ofvacuous truth, when conjunction is defined as an operator or function of arbitraryarity, the empty conjunction (AND-ing over an empty set of operands) is often defined as having the result true.

Truth table

[edit]

Conjunctions of the arguments on the left — Thetrue bits form aSierpinski triangle.

Thetruth table of $A\land B$ :^[1]^[2]

$A {\displaystyle A}$	$B {\displaystyle B}$	$A\land B$
F	F	F
F	T	F
T	F	F
T	T	T

Defined by other operators

[edit]

In systems where logical conjunction is not a primitive, it may be defined as^[6]

A\land B=\neg (A\to \neg B)

It can be checked by the following truth table (compare the last two columns):

$A {\displaystyle A}$	$B {\displaystyle B}$	$\neg B$	$A\rightarrow \neg B$	$\neg (A\rightarrow \neg B)$	$A\land B$
F	F	T	T	F	F
F	T	F	T	F	F
T	F	T	T	F	F
T	T	F	F	T	T

A\land B=\neg (\neg A\lor \neg B).

It can be checked by the following truth table (compare the last two columns):

$A {\displaystyle A}$	$B {\displaystyle B}$	$\neg A$	$\neg B$	$\neg A\lor \neg B$	$\neg (\neg A\lor \neg B)$	$A\land B$
F	F	T	T	T	F	F
F	T	T	F	T	F	F
T	F	F	T	T	F	F
T	T	F	F	F	T	T

Introduction and elimination rules

[edit]

As a rule of inference,conjunction introduction is a classicallyvalid, simpleargument form. The argument form has two premises, $A {\displaystyle A}$ and $B {\displaystyle B}$ . Intuitively, it permits the inference of their conjunction.

A {\displaystyle A}

B {\displaystyle B}

Therefore,A andB.

or inlogical operator notation, where \vdash expresses provability:

\vdash A,

\vdash B

\vdash A\land B

Here is an example of an argument that fits the formconjunction introduction:

Bob likes apples.

Bob likes oranges.

Therefore, Bob likes apples and Bob likes oranges.

Conjunction elimination is another classicallyvalid, simpleargument form. Intuitively, it permits the inference from any conjunction of either element of that conjunction.

A {\displaystyle A}

and

B {\displaystyle B}

Therefore,

A {\displaystyle A}

...or alternatively,

A {\displaystyle A}

and

B {\displaystyle B}

Therefore,

B {\displaystyle B}

Inlogical operator notation:

\vdash A\land B

\vdash A

...or alternatively,

\vdash A\land B

\vdash B

Negation

[edit]

Definition

[edit]

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 {\displaystyle C}$ is a false proposition.

Other proof strategies

[edit]

If $A {\displaystyle A}$ implies $\neg B$ , then both $\neg A$ as well as $A {\displaystyle A}$ prove the conjunction false:

(A\to \neg {}B)\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 {\displaystyle C}$ is a false proposition.

Either of the above are constructively valid proofs by contradiction.

Properties

[edit]

commutativity: yes

$A\land B$	$\Leftrightarrow$	$B\land A$
	$\Leftrightarrow$

associativity: yes^[7]

$A {\displaystyle ~A}$	$~~~\land ~~~$	$(B\land C)$	$\Leftrightarrow$			$(A\land B)$	$~~~\land ~~~$	$C {\displaystyle ~C}$
	$~~~\land ~~~$		$\Leftrightarrow$		$\Leftrightarrow$		$~~~\land ~~~$

distributivity: with various operations, especially withor

$A {\displaystyle ~A}$	$\land$	$(B\lor C)$	$\Leftrightarrow$			$(A\land B)$	$\lor$	$(A\land C)$
	$\land$		$\Leftrightarrow$		$\Leftrightarrow$		$\lor$

others

withexclusive or:

$A {\displaystyle ~A}$	$\land$	$(B\oplus C)$	$\Leftrightarrow$			$(A\land B)$	$\oplus$	$(A\land C)$
	$\land$		$\Leftrightarrow$		$\Leftrightarrow$		$\oplus$

withmaterial nonimplication:

$A {\displaystyle ~A}$	$\land$	$(B\nrightarrow C)$	$\Leftrightarrow$			$(A\land B)$	$\nrightarrow$	$(A\land C)$
	$\land$		$\Leftrightarrow$		$\Leftrightarrow$		$\nrightarrow$

with itself:

$A {\displaystyle ~A}$	$\land$	$(B\land C)$	$\Leftrightarrow$			$(A\land B)$	$\land$	$(A\land C)$
	$\land$		$\Leftrightarrow$		$\Leftrightarrow$		$\land$

idempotency: yes

$A {\displaystyle ~A~}$	$~\land ~$	$A {\displaystyle ~A~}$	$\Leftrightarrow$	$A {\displaystyle A~}$
	$~\land ~$		$\Leftrightarrow$

monotonicity: yes

$A\rightarrow B$	$\Rightarrow$			$(A\land C)$	$\rightarrow$	$(B\land C)$
	$\Rightarrow$		$\Leftrightarrow$		$\rightarrow$

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

$A\land B$	$\Rightarrow$	$A\land B$
	$\Rightarrow$
		(to be tested)

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

$A\land B$	$\Rightarrow$	$A\lor B$
	$\Rightarrow$
(to be tested)

Walsh spectrum: (1,-1,-1,1)

Nonlinearity: 1 (the function isbent)

If usingbinary values for true (1) and false (0), thenlogical conjunction works exactly like normal arithmeticmultiplication.

Applications in computer engineering

[edit]

In high-level computer programming anddigital electronics, 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 provideshort-circuit control structures corresponding to logical conjunction.

Logical conjunction is often used for bitwise operations, where0 corresponds to false and1 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 binarywords viewed asbitstrings 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 abit mask. For example,10011101 AND 00001000 = 00001000 extracts the fourth bit of an 8-bit bitstring.

Incomputer networking, bit masks are used to derive the network address of asubnet within an existing network from a givenIP address, by ANDing the IP address and thesubnet mask.

Logical conjunction "AND" is also used inSQL operations to formdatabase queries.

TheCurry–Howard correspondence relates logical conjunction toproduct types.

Set-theoretic correspondence

[edit]

The membership of an element of anintersection set inset theory is defined in terms of a logical conjunction: $x\in A\cap B$ if and only if $(x\in A)\wedge (x\in B)$ . Through this correspondence, set-theoretic intersection shares several properties with logical conjunction, such asassociativity,commutativity andidempotence.

Natural language

[edit]

As with other notions formalized in mathematical logic, the logical conjunctionand is related to, but not the same as, thegrammatical conjunctionand 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 isat once red, white, and blue, but rather that each color is a part of the flag.

References

[edit]

^^a ^b ^c ^d"2.2: Conjunctions and Disjunctions".Mathematics LibreTexts. 2019-08-13. Retrieved2020-09-02.
^^a ^b ^c"Conjunction, Negation, and Disjunction".philosophy.lander.edu. Retrieved2020-09-02.
^Beall, Jeffrey C. (2010).Logic: the basics (1. publ ed.). London: Routledge. p. 17.ISBN 978-0-203-85155-5.
^Józef Maria Bocheński (1959),A Précis of Mathematical Logic, translated by Otto Bird from the French and German editions, Dordrecht, South Holland: D. Reidel, passim.
^Weisstein, Eric W."Conjunction".MathWorld--A Wolfram Web Resource. Retrieved24 September 2024.
^Smith, Peter."Types of proof system"(PDF). p. 4.
^Howson, Colin (1997).Logic with trees: an introduction to symbolic logic. London; New York: Routledge. p. 38.ISBN 978-0-415-13342-5.

External links

[edit]

Wikimedia Commons has media related toLogical conjunction.

"Conjunction",Encyclopedia of Mathematics,EMS Press, 2001 [1994]
Wolfram MathWorld: Conjunction
"Property and truth table of AND propositions". Archived fromthe original on May 6, 2017.

v t e Commonlogical connectives
Tautology/True $\top$
Alternative denial (NAND gate) ${\overline {\wedge }}$ Converse implication $\Leftarrow$ Implication (IMPLY gate) $\Rightarrow$ Disjunction (OR gate) $\lor$
Negation (NOT gate) $\neg$ Exclusive or (XOR gate) $\oplus$ Biconditional (XNOR gate) $\odot$ Statement (Digital buffer)
Joint denial (NOR gate) ${\overline {\vee }}$ Nonimplication (NIMPLY gate) $\nRightarrow$ Converse nonimplication $\nLeftarrow$ Conjunction (AND gate) $\land$
Contradiction/False $\bot$
Philosophy portal

Commonlogical symbols

∧ or &

¬ or ~

↔ or ≡

universal
quantification

∃

existential
quantification

General

Theorems (list)
and paradoxes

Logics

Traditional	Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram
Propositional	Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞
Predicate	First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus

Set theory

Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities
Types ofsets	Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann
Maps and cardinality	Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary
Set theories	Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive