Logical Operations

Also found in: Dictionary, Thesaurus.

Logical Operations


(or logical connectives, logical operators), functions that transform propositions or propositional forms into other propositions or propositional forms; that is, expressions in predicate logic that contain variables and that become propositions when the variables are replaced by their concrete values.

Logical operations can be divided into two basic groups, quantifiers and propositional (sentential) connectives. In the formalized languages of mathematical logic, quantifiers fulfill the same functions as the quantifying words “all,” “any,” “some,” “there exists,” “only,” “not greater (less) than,” and cardinal numbers in natural language. A characteristic feature of quantifiers— when they are nonvacuously applied—is a decrease in the number of free variables in the transformed expression. The application of a quantifier to an expression containing η free variables generally leads to an expression containing η— 1 free variables; in particular, a propositional form with one free variable is transformed into a proposition by the application of a quantifier in whose scope the variable occurs.

The propositional connectives—unlike the quantifiers, whose introduction marks the transition to predicate logic—are used in the most elementary branch of logic, propositional logic. In formalized logical and logico-mathematical languages they fulfill functions entirely analogous to the functions of conjunctions used for forming complex sentences in natural languages. Thus, negation (⌝) is interpreted as the particle “not,” conjunction (&) is interpreted as the conjunction “and,” disjunction (V) is interpreted as (nonexclusive) “or,” implication (⊃), by the expression “if. . ., then . . .,” and equivalence (~), by the expression “if and only if.” However, there is not, by any means, a one-to-one correspondence between the logical operations and the tools of natural language. This is because, in the first place, propositions by definition can take only two truth values: truth (T) and falsity (F), so that the operations of propositional logic can be considered different functions that map a domain of two elements into itself. The number of different n-place logical operations (that is, operations with n arguments) is therefore determined by purely combinatorial considerations and is equal to 2n. In the second place, all semantic and, especially, stylistic nuances in the meanings

Table 1. Logical operations
Identically true ............T....TTTT
Identically false............F. . .FFFF
P ....................p....TTFF
Negation of p.............p....FFTT
Q ....................q....TFTF
Negation of q.............q....FTFT
Conjunction ..............p & q....TFFF
Anticonjunction (Sheffer stroke) ..P ∨ q....FTTT
Disjunction..............p V q....TTTF
Equivalence..............p ~q....TFFT
Anti-equivalence ...........pq....FTTF
Anti-implication ............Pq....FTFF
Inverse implication ..........pq....TTFT
Inverse anti-implication........pq....FFTF

of conjunctions, other than those that directly determine the truth value of the resulting complex sentence, are disregarded in the formalized languages of mathematical logic. In turn, connectives whose intuitive analogues do not, as a rule, possess special names in natural language are sometimes considered as logical operations. The Sheffer stroke (ǀ) used in Table 1 is an example of such a logical operation. Table 1 gives a complete list of all the 222 = 16 two-place operations of propositional logic. The truth values of certain “primitive” propositions p and q are given in the first two lines while the remaining lines give the truth values of propositions formed from them by means of the logical operations.

All conceivable two-place logical operations that correspond to every possible four-letter combination that can be formed from T and F are given in the table. It is therefore natural that “degenerate” operations are also to be found among these 16 logical operations. The first two connectives, for example, do not depend on any arguments; these connectives are the constants T and F and, clearly, there exist exactly 220 = 2 such zero-place connectives. Further, there are 221 = 4 one-place connectives, each of which depends only on one of the arguments p or q, leaving 16 — 2 — 4 = 10 strictly two-place logical operations. Further, we may consider 223 = 256 three-place logical operations, and so on. However, only a small number of the logical operations given in the table are needed to express, by means of their superposition (that is, successive application), any n-place logical operation, for any natural number n. The sets of connectives and &, ⌝ and V, ⌝ and ⊃, and even the single connective ǀ by itself, constitutes such functionally complete sets of connectives. Insofar as propositional logic can be isomorphically interpreted in terms of the logic of classes, there exists a set-theoretic operation corresponding to each logical operation. The set of such operations over sets (classes) forms the algebra of sets.


Church, A. Vvedenie ν matematicheskuiu logiku, vol. 1. Moscow, 1960. Paragraphs 05, 06, and 15. (Translated from English.)


References in periodicals archive ?
James Varnham, MD, EMEA, Logical Operations, said, "As a strong regional distributor,emt Distribution boasts an innovative solutions portfolio.
EMEA at Logical Operations. "Subela brings decades of experience in the ICT
So, it means all the Boolean functions and logical operations in modern processors (including cryptographic processors) are T--functions.
Output: watermark key data-sequence, [W.sub.KG1], based on aggregation of (DAC) and second key [W.sub.KG2] generated by a logical operation on [T.sub.0] and [W.sub.KG1] (1) Convert [W.sub.I] to a character-stream, [W.sub.CS].
Based on this implication relation the logical operations of conjunction, disjunction, negation, and hypothetical are defined for pictures.
Its feature set enables it to handle a wide range of applications, from simple multi-loop and data acquisition to and setpoint programming, mathematical and logical operations, and complex strategies such as cascade and ratio loops.
However, human experts prove extremely competent without much reliance on the logical operations that characterize typical machine reasoning.
All models feature 2000 samples/ second/channel, six digit engineering unit displays, limits, max/mm capture, analog and digital outputs, real time calculations, logical operations, serial communication and protected logic I/Os.
Members of the group that was taught classifying and ordering made significant gains in their understanding of those logical operations. Similarly, the group that was taught number concepts learned them.
If yes, in this case the information processing is not limited with the execution of sequences of logical operations (see, for example, (1,2)), but creates also illogical thoughts and operates with them, and possesses such qualities of human intellectual activity as creative thinking, emotions, intuition, consciousness, etc.
Although it may at first appear unlikely that all future computing paradigms, such as quantum computation, will subsume the capabilities of current computers, this is actually quite plausible since these capabilities are founded on simple, universal, mathematical, and logical operations whose future utility seems certain no matter what new capabilities are added to them.