Lecture
Propositional logic, sentential logic (Latin propositio — "statement" ) or propositional calculus , also zeroth-order logic, is a branch of symbolic logic that studies compound statements built from simple ones, and the relations between them. Unlike predicate logic, propositional logic does not consider the internal structure of simple statements; it takes into account only which connectives, and in what order, join simple statements into compound ones .
Despite its importance and wide range of applications, propositional logic is the simplest logic and has very limited means for investigating judgments[2
Below are some general facts about tautologies, so general that they are called the rules of propositional logic:
It follows from the last rule that formulas can be transformed, obtaining other formulas equivalent to them but simpler (containing fewer propositional connectives and variables). Any formula can now be reduced to some canonical form, and certain kinds of problems can be solved in this way. Moreover, some equivalences express the basic properties of propositional connectives. For example, the equivalences (Α ∧ B) ≡ (B ∧ Α) and (Α ∨ B) ≡ (Α ∨ B) express the commutative law of conjunction and of disjunction, respectively. All these questions (and others) are studied by the algebra of logic, the foundations of which were laid in the works of G. Boole (1847, 1854) and A. De Morgan (1847).
Let us note some equivalences that show how some connectives can be expressed through others: Α ∧ B ≡ ¬ (¬ Α ∨ ¬ Β), Α ∨ B ≡ ¬ (¬ Α ∧ ¬ B), Α ⊃ B ≡ ¬ Α ∨ B, (Α ≡ B) ≡ (Α ⊃ B) ∧ (B ⊃ Α). A system of propositional connectives M is called complete if every formula is equivalent to some formula containing only connectives from the system M, that is, if all truth functions can be expressed by means of such a system. Thus the systems of connectives {¬, ∧, ∨}, {¬, ∧}, {¬, ∨} and {¬, ⊃} are complete. This means that we can build propositional logic on the basis of any of these systems of connectives. It turns out that a system consisting of only one connective, |, called the "Sheffer stroke," can also be complete: the statement p|q is true if and only if it is false that p and q are both true. The sufficiency of the connective | follows from the tautologies: ¬ Α ≡ Α|Α, Α ∨ B ≡ (Α|Α) | (B|B).
Along with the concept of tautology, the concept of logical consequence is fundamental to propositional logic, since one of the main tasks of logic is to establish what follows from what, and thereby to indicate which statements are theorems under given conditions. Every theorem can be written as an implication, and its condition and conclusion can thus be singled out. One says that B logically follows from Α, or is a logical consequence of Α, and writes Α | = B, if in the truth tables for Α and B the formula B has the value T in all those rows where Α has the value T. It follows that Α | = B if and only if Α ⊃ B is a tautology. If the formula Α is a tautology, one sometimes writes | = Α. The given definition of logical consequence extends without difficulty to a system of formulas (a system of premises) Α1, … Αn, denoted by Γ, and one then writes Γ | = B. An example of logical consequence (inference) from premises is the already mentioned rule of modus ponens. The derivability of B from the statements Α and Α ⊃ B follows from the fact that the formula (Α ∧ (Α ⊃ B) ⊃ B is a tautology. It should also be noted that, by virtue of the truth tables for the implication connective, an identically true formula logically follows from any system of formulas. Α From the fact that there is a decision procedure for tautologies, we obtain that the problem of derivability of an arbitrary formula B from a given system of premises is also decidable.
If the concept of tautology is defined and the semantic concept of logical consequence is defined (as was done above), then a semantic presentation of propositional logic is said to be given, and propositional logic itself is often identified with the set of tautologies or with the relation of logical consequence itself. However, such a presentation raises a serious problem: how can one survey all tautologies, of which there are infinitely many? To solve this problem, one must move to the syntactic presentation of propositional logic.
The formal (symbolic) language of propositional logic and the concept of a formula remain the same. But now a certain finite subset of the whole set of tautologies is chosen (and, generally speaking, it can be chosen in more than one way), and its elements are called axioms. For example:
Thus, in contrast to the tabular definition, the logical connectives ¬, ∧, ∨, ⊃ are defined axiomatically. Then, with the help of the rules already known, but in a purely formal way, derivation is carried out — a transition from a statement or a system of statements to a statement: from Α and Α ⊃ B follows B (the rule of detachment); from Α (p) follows Α (B) (substitution). The propositional logic so given we shall denote by C2 and call classical.
Every axiomatic system that uses the rule of substitution can be reformulated as a system of axiom schemas, in which symbols for arbitrary statements (so-called metavariables) are used instead of propositional variables. In this case each axiom schema represents an infinite set of axioms, and the rule of substitution becomes superfluous.
A logical calculus given by some set of axioms and some set of inference rules is called a calculus of the Hilbert type. A derivation in it is any sequence Α1, … Αn of formulas such that for every i the formula Αi is either an axiom or an immediate consequence of some preceding formulas by one of the inference rules. A formula Α is called a theorem if there is a derivation whose last formula is Α; such a derivation is called a derivation of the formula Α. The notation |– Α serves as an abbreviation of the statement "Α is a theorem." If the formula Α is derivable from some set Γ of initial formulas, then the notation takes the form Γ |– Α.
Starting from the syntactic presentation of propositional logic, the latter is often identified with the set of theorems or, as is more customary, with the relation of derivability. Thus, in the semantic approach formulas are understood in terms of meaning (as functions on a set of two elements, T and F), while in the syntactic approach a formula is a particular string of symbols, and only theorems and non-theorems are distinguished. However, despite this difference, both approaches to building propositional logic essentially coincide and are, as it is said, adequate. This means that the concepts of logical consequence and of derivation coincide. Let us consider the following remarkable theorem, which is sometimes called the adequacy theorem: for all Α, |– Α if and only if |= Α.
The proof in one direction, namely: for all Α, if |– Α, then |= Α, is called the soundness theorem. This is the minimal condition that we require of a logical calculus, and it consists in the semantics we have presented being sound for the chosen axiomatization. To prove the theorem, one must check, first, that all the axioms (1)–(11) are tautologies, which is easily established by direct verification using truth tables, and, second, that the inference rules are chosen in such a way that they preserve tautologyhood. Therefore all the formulas of the sequence forming a proof of any theorem of the calculus C2, including the proved theorem itself, are tautologies. From this theorem follows the most important property of our propositional calculus C2: in C2 the formulas Α and ¬ Α are not simultaneously provable; that is, the propositional calculus C2 is consistent. If this were not so, then (using axiom (10) and applying modus ponens twice) any formula B would be provable in C2. For this reason an inconsistent propositional logic has no value. In it truth and falsity are indistinguishable, and therefore every theorem is both true and false at the same time.
The converse statement also holds: every tautology is provable; that is, for all Α, if |= Α, then |– Α. The proof of this theorem is not so trivial and is called the completeness theorem for the propositional calculus with respect to the proposed semantics. Essentially, it asserts here that the logical means, that is, the axioms and inference rules, of the propositional calculus C2 are fully sufficient for proving all tautologies. Thus the goal set has been achieved: using minimal means, one can survey the whole set of tautologies.
There are many different axiomatizations of C2, including ones consisting of a single axiom and containing only one connective (the Sheffer stroke). It is clear that the fewer the axioms, the more difficult the proofs. And in general, in Hilbert-type calculi, proving theorems and the very search for a derivation are quite cumbersome. Therefore other formulations of the calculus are used, more or less close to natural reasoning, such as the sequent calculus, the calculus of natural deduction, and others. But the relation between semantics and syntax is not so transparent there.
The first axiomatization of classical logic C2 was undertaken by G. Frege (1879). However, in terms of modern symbolic language, an axiomatization of C2 appeared in the "Principia Mathematica" of A. Whitehead and B. Russell (1910–1913). In both works the question of completeness simply did not arise. Their aim was to show that all of logic, and in fact all of mathematics, can be developed within their system. The first publication of a proof of completeness is due to E. Post (1921), who started from the system of Whitehead and Russell. Even earlier this had been done by P. Bernays. In both cases the two-valued truth tables (given above) were used to prove the adequacy theorem. In this case it is also said that these tables are characteristic for C2.
We can now proceed to characterize what is called classical propositional logic:
If, in the given axiomatization of C2, we discard the last axiom (the law of excluded middle), we obtain an axiomatization of propositional intuitionistic logic. It turns out that it has a continuum of extensions (V. L. Yankov, 1968) and that no finite-valued truth tables are characteristic for it (K. Gödel, 1932). There are logics that have only one extension, namely C2 itself.
As for the set of logics, Yankov's result says that there is a continuum of different propositional calculi of only a certain class, namely those logics that include intuitionistic logic (such logics are called superintuitionistic or intermediate). Moreover, in this class there is an infinite set of logics that have no finite axiomatization, an infinite set of undecidable logics, and there are also finite-valued logics with an arbitrary number of truth values.
It should be noted that algebraic methods are widely applied to solve various problems of propositional logic. This becomes possible primarily through the interpretation of propositional logic as a kind of lattice (in the sense of algebraic "lattice theory"). Thus a complemented distributive lattice (Boolean algebra) corresponds to classical propositional logic, while an implicative lattice, where implication is an analogue of division if conjunction is treated as multiplication (pseudo-Boolean algebras, or Heyting algebras), corresponds to intuitionistic propositional logic. In addition, the applications of Boolean algebra to logic rest on the interpretation of the elements of a Boolean algebra as statements.
In conclusion, attention should be drawn to the fact that it is precisely classical propositional logic that underlies the design of microchips for modern digital electronics, including computers, although recently similar work based on other logics — many-valued, fuzzy, paraconsistent — has been under way.
Comments