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:
-
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)?
-
How is best to think of the valuation map?
Any clarification on this would be most appreciated. Thanks
Best Answer
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)$.