Chapter 1
Deductive Systems and Matrix Semantics
By a propositional language we will understand some set C of propositional
connectives. The C-formulas are built in the usual way from the proposi-
tional variables P o
P i ? P 2
- - using the connectives in C. We denote the set
of all £-formulas by Frri£. (The subscript is omitted when the language C
is clear from context.) Light faced italic letters p^q.r,..., possibly with sub-
scripts, will be used as metavariables ranging over the set of propositional
variables. An assignment a : {po5PiP25...}—» Frrtc of formulas to variables
extends naturally to a map from Frrtc into itself, also denoted by cr, by setting
cr{(j)(po,. . . , P n - i ) ) = t(po/rpo, •• .,pn-i/(rPn-i)- * is called & substitution. By
a (finitary) inference rule over £ we mean any pair (I \ ip) where T is a finite set
of formulas and (p is a single formula. (From this point of view modus ponens
would take the form ({p,p —» q}:q).) A formula tp is directly derivable from
a set A of formulas by the rule (T,(p) if there is a substitution a such that
a(f = ip and cr(r) C A; (c(T) = {TI? : I? £ T}). A deductive system S (over C)
is defined by a (possible infinite) set of inference rules and axioms; it consists of
the pair S = ( £ , h $ ) where \~s is the relation between sets of formulas and in-
dividual formulas defined by the following condition: A h$ ip iff -0 is contained
in the smallest set of formulas that includes A together with all substitution
instances of the axioms of S, and is closed under direct derivability by the
inference rules of S. In informal remarks we often refer to a deductive system
as a logical system or simply a logic. The relation h$ is called the consequence
relation of S. It is easily seen to satisfy the following three conditions for all
T, A C Fm and £ , ip G Fm:
peT=T\-sr, (i)
r h
(^ and r C A = A h
^ ; (2)
r \~s W and A h
ip for every ip G T = A h j y. (3)
deceived by the editor April 19, 1987.
2 Work partially supported by NSF-grant DMS-8703743.
3 For a comprehensive account of most of the topics of this chapter see Wojcicki [47],[48].
Previous Page Next Page