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


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)$.

  • $\begingroup$ @pd456 this answer should help you clarify the meaning of homomorphism. But I find the statement in the notes where they rename ⊥=0 a bit "silly". Why start with {0,1} only to change it to {⊥,1} immediately afterwards? $\endgroup$ – magma Jan 13 '12 at 11:56
  • $\begingroup$ @magma: From the wording, I suspect that this renaming is only temporary, to show that there is a way in which $v$ can be viewed as a homomorphism. They probably felt that they had to do the renaming to get an honest homomorphism, since the wording suggests that they’re viewing $\bot$ as a constant of the language. $\endgroup$ – Brian M. Scott Jan 13 '12 at 12:09
  • 1
    $\begingroup$ This "v(f ⇒ g)=v(f) ⇒ v(g)" might come as more clear as "v(f ⇒ g)=(v(f) ⇒ v(g)), since "v(f ⇒ g)=v(f) ⇒ v(g)" could mean "(v(f ⇒ g)=v(f)) ⇒ v(g)" which I know is NOT what you mean. Maybe that's not necessary though. $\endgroup$ – Doug Spoonwood Jan 13 '12 at 17:10
  • $\begingroup$ Mmm.. You have a good point, but as far as I remember = has the lowest precedence in logical operators.. But for explanation purposes, you are absolutely correct! $\endgroup$ – aelguindy Jan 13 '12 at 22:04

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.

  • $\begingroup$ Though interesting information, I don't see this as relevant to the question. Also, the system he has for propositional logic might not have any of these axioms or rules of inference as primitive axioms or primitive rules of inference... he might only have the ability to derive them. On top of this, although classical propositional logic (cpl) does cohere with that of Boolean Algebra in an "intimate" way, that Boolean algebra "hides" behind cpl isn't necessarily true. In principle one can understand everything in the OP without Boolean Algebra as a pre-theory to cpl. $\endgroup$ – Doug Spoonwood Jan 13 '12 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.