Logical Operations
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 | |||||
|---|---|---|---|---|---|
| p... | T | T | F | F | |
| q... | T | F | T | F | |
| Identically true ............ | T.... | T | T | T | T |
| Identically false............ | F. . . | F | F | F | F |
| P .................... | p.... | T | T | F | F |
| Negation of p............. | ⌝p.... | F | F | T | T |
| Q .................... | q.... | T | F | T | F |
| Negation of q............. | ⌝q.... | F | T | F | T |
| Conjunction .............. | p & q.... | T | F | F | F |
| Anticonjunction (Sheffer stroke) .. | P ∨ q.... | F | T | T | T |
| Disjunction.............. | p V q.... | T | T | T | F |
| Antidisjunction............. | p ṽ Q.... | F | F | F | T |
| Equivalence.............. | p ~q.... | T | F | F | T |
| Anti-equivalence ........... | p ≁ q.... | F | T | T | F |
| Implication............... | p ⊃ q.... | T | F | T | T |
| Anti-implication ............ | P ⊅ q.... | F | T | F | F |
| Inverse implication .......... | p ⊂ q.... | T | T | F | T |
| Inverse anti-implication........ | p ⊄ q.... | F | F | T | F |
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.
REFERENCE
Church, A. Vvedenie ν matematicheskuiu logiku, vol. 1. Moscow, 1960. Paragraphs 05, 06, and 15. (Translated from English.)IU. A. GASTEV