Logical conjunction

From Free net encyclopedia

Image:AND.jpg In mathematics, logical conjunction (usual symbol and) is a logical operator that results in false if either of the operands is false.

1 Definition
2 Symbol
3 Associativity and Commutativity
4 Bitwise operation
5 Intersection
6 "And" and <math>\wedge</math>
7 "But"
8 See also
9 External links

[edit]

Definition

In logic and technical fields that use it, conjunction, or and, is a logical operator in logical calculi, and a rule of inference in deductive systems. The result of conjoining two propositions is also called their conjunction. The conjunction is true if both of the combined propositions are true; else it is false.

For two inputs A and B, the truth table of the operator is as follows.

A	B	A and B
F	F	F
F	T	F
T	F	F
T	T	T

Intuitively, the logical operator works the same as the common English word "and". The sentence "it's raining, and I'm inside" asserts that two things are simultaneously true: that it is raining outside, and that I am inside. Logically, this would be denoted by saying that A stands for "it's raining", B stands for "I'm inside", together A AND B.

For example, consider:

x > 13 AND x < 27.

If x is 36, then x > 13 is true, but x < 27 is false, so this sentence is false. But if x is 20, then both parts of the sentence are true, so the entire conjunction is also true.

The analogue of conjunction for a (possibly infinite) family of statements is universal quantification, which is part of predicate logic.

As a rule of inference. conjunction is a valid, simple argument form:

Therefore, A and B.

or in logical operator notation:

<math> \vdash A \and B </math>

The argument form has two premises. The first premise is the left conjunct, the second premise the right conjunct. From these two premises it can be logically concluded that A and B, must be true as well.

Here is an example of an argument that fits the form conjunction:

Everyone should vote.

Democracy is the best system of government.

Therefore, everyone should vote and Democracy is the best system of government.

[edit]

Symbol

The mathematical symbol for logical conjunction varies in the literature. In addition to the abbreviation "and", one may also see

a wedge ("∧", or ∧) is typically used for conjunction. For example: "A ∧ B" is read as "A and B". Such a conjunction is true if both A and B are true. In all other cases it is false.

All the following are conjunctions:

A ∧ B

¬A ∧ B<p> A ∧ ¬B ∧ ¬C ∧ D ∧ ¬E<p> The equivalent notion in set theory is the set-theoretic intersection.

[edit]

Associativity and Commutativity

One can also chain conjunctions, such as A AND B AND C, which is logically equivalent both to (A AND B) AND C and to A AND (B AND C). This statement is true if A, B, and C are simultaneously true. In fancier language, conjunction is associative. It's also commutative; A AND B is the same as B AND A.

[edit]

Bitwise operation

Logical conjunction is often used for bitwise operations. Examples:

0 and 0 = 0
0 and 1 = 0
1 and 0 = 0
1 and 1 = 1

1100 and 1010 = 1000

Note that in computer science, the AND operator can be used to set a bit to 0 by AND-ing the bit with 0 (A AND 0 = 0 for any (binary) value of A). This principle is called a "bit mask". For example, if you have a 4-byte-integer holding a color value, which could be described as 0xAABBGGRR (R-red; G-green; B-blue; A-alpha), you may want to select one of the colors. The bit mask for green would be 0x0000FF00. If you apply this bit mask to the 4-byte-integer, it only leaves the bits belonging to green intact (0x0000GG00).

[edit]

Intersection

The intersection used in set theory is defined in terms of a logical conjunction: x ∈ A ∩ B if and only if (x ∈ A) ∧ (x ∈ B). Because of this, logical conjunction satisfies many of the same identities as set-theoretic intersection, such as associativity, commutativity, distributivity, and de Morgan's laws.

[edit]

"And" and <math>\wedge</math>

At least on the face of it, English "and" has properties not captured by logical conjunction. Unlike <math>\wedge</math>, "and" is not commutative: "They got married and had a baby" is not equivalent to "They had a baby and got married". Some lists conjoined by "and" do not allow an operation analogous to logical <math>\wedge</math>-elimination: "The American flag is red, white and blue" does not permit us to infer that the whole American flag is white.

[edit]

"But"

A minor issue of logic and language is the role of the word "but". Logically, the sentence "it's raining, but the sun is shining" is equivalent to "it's raining, and the sun is shining", so logically, "but" is equivalent to "and". However, in natural language, "but" and "and" are semantically distinct. The former sentence suggests that the latter sentence is usually a contradiction.

One way to resolve this problem of correspondence between symbolic logic and natural language is to observe that the first sentence (using "but"), implies the existence of a hidden but mistaken assumption, namely that the sun does not shine when it rains. We might say that, given probability p that it rains and the sun shines, and probability 1 − p that it rains and the sun does not shine, or that it does not rain at all, we would say "but" in place of "and" when p was low enough to warrant our incredulity.

That implication captures the semantic difference of "and" and "but" without disturbing their logical equivalence. On the other hand, in Brazilian logic, the logical equivalence is broken between A BUT NOT B (where "BUT NOT" is a single operator) and A AND (NOT B), which is a weaker statement.

"But" is also sometimes disjunctive (It never rains but it pours); sometimes minutive (She was but a girl at the time); sometimes contrastive (It's not black, but blue); sometimes a spatial preposition (He's waiting but the house); and sometimes interjective (My, but that's a lovely boat). These uses await semantic assimilation with conjunctive "but".

Like "and", "but" is sometimes non-commutative: "He got here, but he got here late" is not equivalent to "He got here late, but he got here". This example shows also that unlike "and", "but" can be felicitously used to conjoin sentences that entail each other; compare "He got here late, and he got here".

[edit]