Valuation in propositional logic

Question

Just started having a look at propositional logic and I'm confused about a statement in my notes.

It defines a set $P = \{p_1, p_2, ... \}$ of primitive statements. It then defines a set $L$ of statements inductively from $P$, where $L_1 = P \cup \{ \bot \}$ and $L_{n+1} = L_n \cup \{(p \implies q) : p,q \in L_n \} $. The set $L$ can be thought of as satisfying three properties:

i) $P \subset L$

ii) $\bot \in L$

iii) If $p,q \in L$ then $(p \implies q)\in L$

I can see that any proposition is a finite string of symbols from the alphabet $\bot, \implies, (), p_1, p_2, ... $. I can also see that every statement is built up from i) and ii) using iii) in a unique way.

The notes then go on to define a valuation on the set $L$ as a function $v:L \to \{0,1\}$ such that:

a) $v(\bot) = 0$

b) $v( p\implies q) = \left\{\begin{array}{c l} 0 & \mathrm{if} \ v(p) = 1, v(q) = 0 \\ 1 & \mathrm{otherwise} \end{array} \right. $

It seems like a valuation is some sort of "truth function" on the set of propositions, by which I mean "$p$ implies $q$ is true if $p$ being true implies $q$ being true", and so on for more complicated proposition (because $\bot$ is "false"). There is then the remark:

"On $\{0,1\}$, we can define a constant $\bot$ by $\bot = 0$, and an operation $\implies$ by $(a \implies b) = \left\{ \begin{array}{c l} 0 & \mathrm{if} \ a=1, b = 0 \\ 1 & \mathrm{otherwise} \end{array} \right.$

Then a valuation is precisely a map $v : L \to \{0,1\}$ that preserves the structure ($\bot$ and $\implies$), i.e. a homomomorphism."

Are we defining a propositional structure on $\{0,1\}$, in a similar way to how we defined an abstract $L$ to start with? i.e. taking $P = \{1\}$ and defining "$\implies$" in this way gives a set of propositions that satisfies i), ii) and iii) above. If so, I can sort of see how valuation is then a structure-preserving map, since $(p \implies q ) \mapsto (v(p) \implies v(q))$, but I don't see how this reconciles with the idea of valuation being a 'truth' function (if indeed it is one).

I suppose my real questions are:

1. What, precisely, is meant by a homomorphism between propositional structures (/is "propositonal structure" even a thing, I've just realised I made the term up)?

2. How is best to think of the valuation map?

Any clarification on this would be most appreciated. Thanks

Answer 1

First, let me start by noting that what you call valuation is normally (at least in the books I've seen) called interpretation. The valuation is a function from $P$ to $\{0, 1\}$. Logicians often abuse the word and call both valuation.

I'll start by answering the second question. You can think of the valuation as a row in the truth table. The valuation of every subformula is a function of the valuations of its subformulas (as in the inductive definition). The row assumes a certain truth assignment to the primitive statements, usually called propositions.

To answer your first question, a valuation is clearly just a map from the set of all formulas (composed of the set P), namely L, to $\{0, 1\}$. It is also a homomorphism because it "respects" the binary operator of the set L ($\Rightarrow$) in the sense that $v(f\ \Rightarrow\ g) = v(f)\ \Rightarrow\ v(g)$. So, applying the operator on the formula before valuation yields the same result as applying the operator on the results of valuating each formula.

To clarify homomorphisms even more, let me give you another example, the determinant of a matrix is a function from all $n$x$n$ matrices to the real numbers. It is a homomorphism because it respects the multiplication operator. That is, $det(A * B) = det(A) * det(B)$.

Answer 2

The algebraic structure which is hiding behind all this is that of boolean algebras, albeit one presented in a very minimalist way. Unfortunately, we must impose some additional axioms / equivalence relations in order to turn the set $L$ into a genuine boolean algebra:

1. Axiom K: $$(p \Rightarrow (q \Rightarrow p)) \equiv (\bot \Rightarrow \bot)$$

2. Axiom S: $$((p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow r))) \equiv (\bot \Rightarrow \bot)$$

3. Double negation elimination: $$((p \Rightarrow \bot) \Rightarrow \bot) \equiv p$$

4. Modus ponens / deduction theorem: $$(p \Rightarrow (q \Rightarrow r)) \equiv ((\lnot(p \Rightarrow (\lnot q))) \Rightarrow r)$$

These you should recognise as corresponding to the axioms and rules of inference of classical propositional logic. Once we take equivalence classes of $L$ under $\equiv$, we get a boolean algebra, with the ordinary boolean algebra operations are defined in the usual way:

$$\begin{align} \lnot p & = (p \Rightarrow \bot) & \top & = \lnot \bot \\ p \lor q & = ((\lnot p) \Rightarrow q) & p \land q & = \lnot (p \Rightarrow (\lnot q)) \end{align}$$

The fact that you can freely set the valuation of primitive propositions to be either $0$ or $1$ corresponds to the fact that the boolean algebra you obtain this way is the free boolean algebra generated by the primitive propositions: indeed, $L$ (modulo $\equiv$) is isomorphic to the boolean algebra $\mathscr{P}(P)$.

More generally, we can construct the Lindenbaum–Tarski algebra for various propositional logics (both classical and otherwise). The idea is this: if $p$ and $q$ are formulae, then we define $p \equiv q$ if $p \vdash q$ and $q \vdash p$. In order for the construction to work, the logic must be sufficiently strong so that the equivalence relation $\equiv$ is a congruence relation (i.e. respects the operations): so here we must have $$p \equiv p' \text{ and } q \equiv q' \text{ implies } (p \Rightarrow q) \equiv (p' \Rightarrow q')$$ and this does turn out to be the case, by using e.g. the deduction theorem. When this happens we say the logic is algebraisable.