All Topics  
Logical conjunction

 
Logical Conjunction

 
   Email Print
   Bookmark   Link
 

 

Logical conjunction
 
 
  Topics Logical conjunction Topic Home

In logic
Logic

Logic is the study of the principles of valid demonstration and inference. Logic is a branch of philosophy, a part of the classical Trivium . The word derives from Greek language ?????? , fem....
 and/or mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
, logical conjunction or 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.

Truth table
The truth table
Truth table

A truth table is a mathematical table used in logic?specifically in connection with Boolean algebra , boolean functions, and propositional calculus?to compute the functional values of logical expression s on each of their functional arguments, that is, on each combination of values taken by their logical variables....
 of p AND q (also written as or in logic, in many programming languages, or pq in electronics):

Venn diagram
Venn diagram

Venn diagrams or set diagrams are diagrams that show all hypothetically possible logical relations between a finite collection of Set . Venn diagrams were invented around 1880 by John Venn....
 of "A and B" (the red area is true)

The analogue of conjunction for a (possibly infinite) family of statements is universal quantification
Universal quantification

In predicate logic, universal quantification formalizes the notion that something is true for everything, or every relevant thing.The resulting statement is a universally quantified statement, and we have universally quantified over the predicate....
, which is part of predicate logic
Predicate logic

In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic....
.

Introduction and elimination rules
As a rule of inference, conjunction introduction is a classically valid
Validity

The term Validity in logic applies to Argument or statements....
, simple argument form
Argument form

In logic, the argument form or test form of an argument results from replacing the different words, or sentences, that make up the argument with letters, along the lines of algebra; the letters represent logical variables....
.






Discussion
Ask a question about 'Logical conjunction'
Start a new discussion about 'Logical conjunction'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In logic
Logic

Logic is the study of the principles of valid demonstration and inference. Logic is a branch of philosophy, a part of the classical Trivium . The word derives from Greek language ?????? , fem....
 and/or mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
, logical conjunction or 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 value
Logical value

In logic and mathematics, a logical value, also called a truth value, is a value indicating the extent to which a proposition is truth.In classical logic, the only possible truth values are true and false....
s, typically the values of two proposition
Proposition

This article is about the term proposition in logic and philosophy; for other uses see PropositionIn logic and philosophy, proposition refers to either the "content" or Meaning of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence....
s, that produces a value of true if and only if both of its operands are true.

Truth table


The truth table
Truth table

A truth table is a mathematical table used in logic?specifically in connection with Boolean algebra , boolean functions, and propositional calculus?to compute the functional values of logical expression s on each of their functional arguments, that is, on each combination of values taken by their logical variables....
 of p AND q (also written as or in logic, in many programming languages, or pq in electronics):

Venn diagram

The Venn diagram
Venn diagram

Venn diagrams or set diagrams are diagrams that show all hypothetically possible logical relations between a finite collection of Set . Venn diagrams were invented around 1880 by John Venn....
 of "A and B" (the red area is true)

The analogue of conjunction for a (possibly infinite) family of statements is universal quantification
Universal quantification

In predicate logic, universal quantification formalizes the notion that something is true for everything, or every relevant thing.The resulting statement is a universally quantified statement, and we have universally quantified over the predicate....
, which is part of predicate logic
Predicate logic

In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic....
.

Introduction and elimination rules


As a rule of inference, conjunction introduction is a classically valid
Validity

The term Validity in logic applies to Argument or statements....
, simple argument form
Argument form

In logic, the argument form or test form of an argument results from replacing the different words, or sentences, that make up the argument with letters, along the lines of algebra; the letters represent logical variables....
. 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

Conjunction introduction is the inference that, if p is true, and q is true, then the logical conjunction p and q is true.For example, if it's true that it's raining, and it's true that I'm inside, then it's true that it's raining, and I'm inside....
:

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
Validity

The term Validity in logic applies to Argument or statements....
, simple argument form
Argument form

In logic, the argument form or test form of an argument results from replacing the different words, or sentences, that make up the argument with letters, along the lines of algebra; the letters represent logical variables....
. 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:

...or alternately,

Properties

The following properties apply to conjunction:

  • associativity
    Associativity

    In mathematics, associativity is a property that a binary operation can have. It means that, within an expression containing two or more of the same associative operators in a row, the order that the operations are performed does not matter as long as the sequence of the operands is not changed....
    :


  • commutativity
    Commutativity

    In mathematics, commutativity is the process to change the order of something without changing the end result. It is a fundamental property of many binary operations throughout mathematics, and many Mathematical proof depend on it....
    :


  • distributivity
    Distributivity

    In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalises the distributive law from elementary algebra....
    :


  • idempotency:


  • monotonicity:


  • truth-preserving: The interpretation under which all variables are assigned a truth value of 'true' produces a truth value of 'true' as a result of conjunction.


  • falsehood-preserving: The interpretation under which all variables are assigned a truth value of 'false' produces a truth value of 'false' as a result of conjunction.


If using binary
Binary numeral system

The binary numeral system, or notation with a radix of 2. Owing to its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used internally by all modern computers....
 values for true (1) and false (0), then logical conjunction works exactly like normal arithmetic multiplication
Multiplication

Multiplication is the Operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic .Multiplication is defined for Natural number in terms of repeated addition; for example, 4 multiplied by 3 can be calculated by adding 3 copies of 4 together:...
.

Applications in computer programming


In high-level computer programming and digital electronics, logical conjunction is commonly represented by an infix operator, usually as a keyword such as "AND", an algebraic multiplication, or the ampersand symbol "&". 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 bitstring
Bitstring

A bitstring is a sequence of bits. Anything on a discrete computer can be represented by a bitstring. In particular, any discrete computer can be encoded in a bitstring, usually called a software program....
s 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
Mask (computing)

In computer science, a mask is data that is used for bitwise operations.Using a mask, multiple bits in a byte, nibble, word can be set either on, off or inverted from on to off in a single bitwise operation....
. For example, 10011101 AND 00001000  =  00001000 extracts the fifth bit of an 8-bit bitstring.

In computer networking
Computer networking

Computer networking is the engineering discipline concerned with communication between computer systems or Peripheral devices. Networking, routers, routing protocols, and networking over the public Internet have their specifications defined in documents called Request for Commentss....
, bit masks are used to derive the network address of a subnet
Subnetwork

A subnetwork, or subnet, describes networked computers and devices that have a common, designated IP address routing prefix.Subnetting is used to break the network into smaller more efficient subnets to prevent excessive rates of Ethernet packet collision in a large network....
 within an existing network from a given IP address
IP address

An Internet Protocol address is a numerical identification that is assigned to devices participating in a computer network utilizing the Internet Protocol for communication between its nodes....
, by ANDing the IP address and the subnet mask
Subnetwork

A subnetwork, or subnet, describes networked computers and devices that have a common, designated IP address routing prefix.Subnetting is used to break the network into smaller more efficient subnets to prevent excessive rates of Ethernet packet collision in a large network....
.

Logical conjunction "AND" is also used in SQL
SQL

SQL is a database computer language designed for the retrieval and management of data in relational database management systems , database schema creation and modification, and database object access control management....
 operations to form database
Database

A database is a structured collection of records or data that is stored in a computer system. The structure is achieved by organizing the data according to a database model....
 queries.

Set-theoretic intersection


The intersection
Intersection (set theory)

In mathematics, the intersection of two Set A and B is the set that contains all elements of A that also belong to B , but no other elements....
 used in set theory
Set theory

Set theory is the branch of mathematics that studies Set , which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics....
 is defined in terms of a logical conjunction: x ? A n B if and only if (x ? A) ? (x ? B). Because of this, set-theoretic intersection shares several properties with logical conjunction, such as associativity
Associativity

In mathematics, associativity is a property that a binary operation can have. It means that, within an expression containing two or more of the same associative operators in a row, the order that the operations are performed does not matter as long as the sequence of the operands is not changed....
, commutativity
Commutativity

In mathematics, commutativity is the process to change the order of something without changing the end result. It is a fundamental property of many binary operations throughout mathematics, and many Mathematical proof depend on it....
, and idempotence
Idempotence

Idempotence describes the property of operations in mathematics and computer science which means that multiple applications of the operation does not change the result....
.

Natural language


The logical conjunction and in logic is related to, but not the same as, the grammatical conjunction
Grammatical conjunction

In grammar, a conjunction is a part of speech that connects two words, phrases or clauses together. This definition may overlap with that of other parts of speech, so what constitutes a "conjunction" should be defined for each language....
 and in natural languages.

English "and" has properties not captured by logical conjunction. For example, "and" sometimes implies order. 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


External links