Lecture
In logic, logical operations are actions that give rise to new concepts through the use of existing ones. In a narrower sense, the concept of a logical operation is used in mathematical logic and programming.
In logic , a logical connective (also called a logical operator , propositional connective , or sentential operator ) is a logical constant used to connect two or more formulas. For example , in the syntax of logic , the binary connective 
can be used to connect two atomic formulas 
as well as 
, yielding the complex formula 
.
Common connectives include negation , disjunction , conjunction and implication . In standard systems of classical logic these connectives are interpreted as truth functions , although they receive many alternative interpretations in non-classical logic . Their classical interpretations are similar to the meanings of natural-language expressions, such as the English «not», «or», «and», and «if», but are not identical — compositional semantics paired with robust pragmatics .
A logical connective is similar to, but not equivalent to, the syntax commonly used in programming languages called the conditional operator .
Logical operations on concepts — are mental actions that result in a change of the content or scope of concepts, as well as the formation of new concepts.
Operations that are primarily related to changing the content of concepts include:
Operations that are primarily related to the scope of concepts include:
These operations can be recorded mathematically using set theory.
The transition to mathematical logic is, in turn, connected with the concept of propositions and the establishment of operations on them with the aim of obtaining complex propositions.
Logical operation (logical operator, logical connective, propositional connective) — an operation on statements allowing new statements to be composed by combining simpler ones .
Among the basic ones are usually named conjunction (
or &), disjunction (), implication (
), negation (
). In the sense of classical logic, logical connectives can be defined through the algebra of logic. In asynchronous sequential logic a logico-dynamic connective is defined in the form of the venjunction operation (
).
Logical operation — in programming, an operation on expressions of the logical (Boolean) type, corresponding to some operation on statements in the algebra of logic. Like statements, logical expressions can take one of two truth values — «true» or «false». Logical operations serve to obtain complex logical expressions from simpler ones. In turn, logical expressions are usually used as conditions to control the sequence of program execution.
In some programming languages (for example, in the C language) numeric types are used instead of, or at the same time as, the logical type. In this case, a value other than zero is considered to correspond to logical truth, and zero — to logical falsehood.
The value of a single bit can also be regarded as logical, if 1 is taken to mean «true», and 0 — «false». This allows logical operations to be applied to individual bits, to bit vectors component-wise, and to numbers in binary representation bit by bit. Such simultaneous application of a logical operation to a sequence of bits is carried out by means of bitwise logical operations. Bitwise logical operations are used to operate on individual bits or groups of bits, and are applied for imposing bit masks and performing various arithmetic computations.
Among logical operations the best known are conjunction (&&), disjunction (||), negation (!). They are often confused with bitwise operations, although these are different things. For example, the following code in the C language:
if (action_required && some_condition())
{
/* some actions */
}
will not call the subroutine some_condition(), if the value of the logical variable action_required is false. In such an operation, the second argument of the «&&» operation is not evaluated at all.
The following table shows, for several programming languages, the built-in operators and functions that implement logical operations.
| Language | NOT | AND | OR | Excl. OR | Equiv. | Not equiv. | Other |
|---|---|---|---|---|---|---|---|
| C++ | ! | && | || | ^ | == | != | |
| Fortran | .NOT. | .AND. | .OR. | .XOR. | .EQV. | .NEQV. | |
| Java | ! | && | || | ^ | == | != | |
| Pascal | not | and | or | xor | = | <> | |
| PL/I | ¬ | & | | | ¬ | = | ¬= | BOOL |
| ^ | ^ | ^= | |||||
| Prolog | \+ | , | ; | ||||
| Python | not | and | or | xor | == | != | |
| Turbo Basic | NOT | AND | OR | XOR | EQV | <> | IMP |
The standard logical connectives of classical logic have rough equivalents in the grammars of natural languages . In English , as in many other languages, such expressions are usually grammatical conjunctions . However they can also take the form of complements , verb suffixes and particles . The denotations of natural-language connectives are a central topic of research in formal semantics , the field that studies the logical structure of natural languages.
The meanings of natural-language connectives are not quite identical to their closest equivalents in classical logic. In particular, disjunction may receive an exclusive interpretation in many languages. Some researchers have taken this fact as evidence that natural-language semantics is non-classical . However others support classical semantics, positing pragmatic explanations of exclusivity that create the illusion of non-classicality. In such cases exclusivity is usually treated as a scalar implicature . Related puzzles involving disjunction include free-choice inferences , Hurford's constraint , and the contribution of disjunction to alternative questions .
Other apparent discrepancies between natural language and classical logic include the paradoxes of material implication , donkey anaphora , and the problem of counterfactual conditionals . These phenomena have been taken as motivation for identifying the denotations of natural-language conditionals with logical operators, including strict conditionals , variably strict conditionals , as well as various dynamic operators.
The following table shows the standard classically-defined approximations for English connectives.
| English word | Connective | Symbol | Logic gate |
|---|---|---|---|
| not | negation | "¬" | NOT |
| and | conjunction | "∧" | AND |
| or | disjunction | "∨" | OR |
| if ... then | material implication | «→» | IMPLY |
| ...if | converse implication | «←» | |
| if and only if | biconditional | "↔" | XNOR |
| not both | alternative denial | «↑» | NAND |
| neither nor | joint denial | «↓» | NOR |
| but not | material nonimplication | "↛" | SIMPLY |
Some logical connectives possess properties that can be expressed in theorems containing the connective. Here are some of the properties a logical connective may possess:
Associativity
In an expression containing two or more identical associative connectives in a row, the order of operations does not matter as long as the sequence of operands is not changed.
Commutativity
The operands of a connective can be swapped, while preserving logical equivalence to the original expression.
Distributivity
A connective, denoted ·, distributes over another connective, denoted as +, if a · ( b + c ) = ( a · b ) + ( a · c ) for all operands a , b , c .
Idempotence
When the operands of the operation coincide, the compound is logically equivalent to the operand.
Absorption
A pair of connectives ∧, ∨ satisfies the absorption law if 
for all operands a , b .
Monotonicity
If f ( a 1 , ..., a n ) ≤ f ( b 1 , ..., b n ) for all a 1 , ..., a n , b 1 , ..., b n ∈ {0 , 1} such that a 1 ≤ b 1 , a 2 ≤ b 2 , ..., a n ≤ b n . For example, ∨, ∧, ⊤, ⊥.
Affinity
Each variable either always matters for the truth value of the operation, or never matters. For example, ¬, ↔, 
, ⊤, ⊥.
Duality
Reading the assignment of truth values for an operation from top to bottom of its truth table is the same as performing the complement of reading the table of the same or another connective from bottom to top. Without resorting to truth tables, it can be formulated as g̃ (¬ a 1 , ..., ¬ a n ) = ¬ g ( a 1 , ..., a n ) . For example, ¬.
Truth-preserving
The compound of all these arguments being tautologies is itself a tautology. For example, ∨, ∧, ⊤, →, ↔, ⊂ (see Validity ).
Falsehood-preserving
All these arguments being contradictions, this is itself a contradiction. For example, ∨, ∧,, ⊥, ⊄, ⊅ (see Validity ).
Involutivity (for unary connectives)
e ( e ( a )) = a . For example, negation in classical logic.
For classical and intuitionistic logic the symbol «=» means that the corresponding implications «… →…» and «… ←…» for the logical compounds can be proved as theorems, while the symbol «≤» means that «… →…» for the logical compounds is a consequence of the corresponding connectives «… →…» for the propositional variables. Some many-valued logics may have incompatible definitions of equivalence and order (consequence).
Both conjunction and disjunction are associative, commutative and idempotent in classical logic, most kinds of many-valued logic, and intuitionistic logic. The same holds for the distribution of conjunction over disjunction and of disjunction over conjunction, as well as for the law of absorption.
In classical logic and some kinds of many-valued logic, conjunction and disjunction are dual, and negation is self-dual; the latter is also self-dual in intuitionistic logic.
To reduce the number of parentheses required, precedence rules can be introduced : ¬ has higher precedence than ∧, ∧ is higher than ∨, and ∨ is higher than →. So, for example,
is shorthand for 
.
Here is a table that shows the commonly used precedence of logical operators. [18]
However not all compilers use the same order; for example, an order has also been used in which disjunction has lower precedence than implication or double implication. [19] Sometimes the precedence between conjunction and disjunction is not specified, and it must be indicated explicitly in a given formula with parentheses. The order of precedence determines which connective is the «main connective» when interpreting a non-atomic formula.
The functional approach to logical operators is implemented in the form of logic gates in digital circuits . Practically all digital circuits (the main exception being DRAM ) are built from NAND , NOR , NOT and transmission gates ; for more detailed information see the section « Truth function in computer science» . Logical operators on bit vectors (corresponding to finite Boolean algebras ) are bitwise operations .
But not every use of a logical connective in computer programming has Boolean semantics. For example, lazy evaluation is sometimes implemented for P ∧ Q and P ∨ Q , so these connectives are not commutative if one or both expressions P , Q have side effects . Furthermore, the conditional expression , which in some sense corresponds to the material conditional connective, is essentially not logical, because for if (P) then Q;, the consequent Q is not executed if the antecedent P is false (although the compound as a whole is successful — «true» in such a case). This is closer to the intuitionistic and constructivist views of material conditionals, rather than to the views of classical logic.
Comments