login or register
u
p
 remember me!
Logical Conjunction
Logical Conjunction
(logic, wiki, imported, Jon Awbrey)



missing image!
- AND.jpg -
AND Logic Gate


In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false.

Definition

Logical conjunction is an operation on two logical values, typically the values of two propositions, that produces a value of true if and only if both of its operands are true.

The truth table of p AND q (also written as p ∧ q, p & q, or p · q) is as follows:

|+ Logical Conjunction style="background:paleturquoise" ! style="width:15%" | p ! style="width:15%" | q ! style="width:15%" | p ∧ q
| F
| F
| F
| T



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

Introduction and elimination rules

As a rule of inference. conjunction introduction 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 and B


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

Everyone should vote.
Democracy is the best system of government.
Therefore, everyone should vote and Democracy is the best system of government.
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 alternately,

A and B.
Therefore, B.
In logical operator notation:

A and B

vdash A
...or alternately,

A and B

vdash B

Algebraic properties

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.

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).

Set-theoretic intersection

The intersection used in set theory is defined in terms of a logical conjunction: xAB if and only if (xA) ∧ (xB). 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.

Rhetorical considerations

The classical "trivium" divides the study of articulate argumentation into the disciplines of grammar, logic, and rhetoric. Grammar concerns those aspects of language that are internal to the language itself, in other words, that can be abstracted from considerations of the object world and the language user. Logic deals with the properties of language and reasoning that are independent of particular manners of interpretation and invariant over conceivable langagues. Rhetoric treats those aspects of language and its use in reasoning that necessarily take the nature of the interpreter into consideration.

Natural languages are evolved for many purposes beyond their use in logical argumentation, and so any study of logic in a natural language context must sort out those aspects of natural language that are pertinent to its use in logic and those that are not.

At least on the face of it, English "and" has properties not captured by logical conjunction. Unlike logical conjunction, the use "and" in English is not always commutative. For example, "They got married and had a baby" is not normally interpreted to have the same connotations as "They had a baby and got married". Some lists conjoined by "and" do not allow an operation analogous to logical and-elimination. For example, "The American flag is red, white, and blue" does not support the inference that the whole American flag is white.

There are everyday examples when the English word "and" is used with the meaning of logical disjunction or OR. The following two sentences are often interpreted the same. "Damage caused by scratches or dents is chargeable." "Damage caused by scratches and dents is chargeable."

Many examples of "or" in English seem to function as logical conjunctions. The sentence "It might work, or it might not" is equivalent to "It might work, and it might not". Arguably, the "or" in "You may have ice cream or you may have cake" functions conjunctively, since it quantifies truth universally, over both conjuncts---though obviously not also over an unstated third option, in which both ice cream and cake are eaten simultaneoously. Truth-functionality is what is at issue here, and this "or" guarantees the truth of both its conjuncts, even if in fact it forbids having both ice cream and cake. A "true" disjunction would function as a kind of existential quantifier, guaranteeing the truth of only one of the two elements it conjoined. In this sort of case an utterance of the cake sentence would initiate a kind of guessing game: one response might be "Is it ice cream?".

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 (Canada has had but three shots on goal); sometimes contrastive (He was not God, but merely an exalted man); 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".

See also

Logical operators

|+  


Related topics

|+  


External links






Some content adapted from the Wikinfo article "Logical conjunction" under the GNU Free Documentation License.

Konjunktion (logik) Konjunktion (Logik) Konjunkce_(matematika) Konjunkcio (logiko) Puerta AND Conjonction_logique AND 論理積 Логичка конјункција Logische conjunctie Konjunksjon (logikk) AND E (lógica) Konjunkcia (logika) การเชื่อมเชิงตรรกศาสตร์ Кон'юнкція

(last updated by Jon Awbrey, 6:54pm EDT - Sat, Apr 07 2007)
export article | talk about article