Working on the book: Derek Goldrei. "Propositional and Predicate Calculus" (p. 40)
The author briefly introduces the concept of a function v:
We talked informally about knowing whether, in a particular set of circumstances, each propositional variable is true or false. More formally and elegantly, thsi set of circumstances is a function $v \colon P \to \{T,F\}$, where $P$ is the set of propositional variables in our language.
Before introducing the concept of truth assignment, explains:
Let $Form(P, S)$ be the set of all formulas built up from propositional variables in a set $P$ using connectives in a set $S$ which includes $\land$. We shall say that a function $v \colon Form(P,S) \to \{T,F\}$ respects the truth table $\land$ if$$ v((\theta \land \psi))= \begin{cases} T, &\text{if } v(\theta))=v(\psi)=T\\ F, &otherwise, \\ \end{cases} $$for all formulas $\theta, \psi \in Form(P,S)$.
I see how function $v$ respects the truth table of $\land$. My question is:
- In which way are the truth value of $v(\theta)$ and $v(\psi)$ determined in that piecewise function ?
- What is the criteria for deciding whether $v(\theta)$ (or any propositional variable) is going to be $T$ or $F$ ?
3 Answers
$\begingroup$Ultimately the truth value $v(\varphi)$ of any formula $\varphi$ is determined by the truth values that $v$ assigns to the propositional variable appearing in $\varphi$. Consider, for instance the following formula $\varphi$:
$$(p\land\neg q)\lor(r\land q)\to p$$
If $v(p)=F$, $v(q)=T$, and $v(r)=F$, then:
- $v(\neg q)$ must be $F$ in order to respect to truth table for $\neg$;
- $v(p\land\neg q)$ must then also be $F$ in order to respect the truth table for $\land$;
- $v(r\land q)$ must be $F$ for the same reason;
- $v\big((p\land\neg q)\lor(r\land q)\big)$ must be $F$ in order to respect the truth table for $\lor$; and finally
- $v(\varphi)$ must be $T$ in order to respect the truth table for $\to$.
If we change the truth value of $r$ by setting $v(r)=T$, we must then have $v(r\land q)=T$, $v\big((p\land\neg q)\lor(r\land q)\big)=T$, and $v(\varphi)=F$.
In practice truth assignments are very often presented in the form of tables showing the truth values assigned to a particular formula under all possible assignments of truth values to its propositional variables. In this case we’d have the following table, and we could read off that $v(\varphi)=T$ for all truth assignments to $p,q$, and $r$ except the one mentioned immediately above, the one in the fifth line of the table:
$$\begin{array}{c|c|c} p&q&r&p\land\neg q&r\land q&(p\land\neg q)\lor(r\land q)&\varphi\\\hline T&T&T&F&T&T&T\\ T&T&F&F&F&F&T\\ T&F&T&T&F&T&T\\ T&F&F&T&F&T&T\\ F&T&T&F&T&T&F\\ F&T&F&F&F&F&T\\ F&F&T&F&F&F&T\\ F&F&F&F&F&F&T \end{array}$$
$\endgroup$ 8 $\begingroup$The above answers are thorough, but they overcomplicate matters by quite a bit
by being too formal. A truth assignment ν is simply a row of values of
atomic propositions in a truth table, nothing more, nothing less.
This row of atomic proposition values can be thought of as a functionν(φ) → {T, F}, which is true or T, if the value of the formula φ is true
with that combination of values of atomic propositions ν and false or F, if
the fomula φ is not true with said values. For example, if it is rainingand cloudy or raining = T and cloudy = T, then
raining ∧ cloudy = T ∧ T = T ,and the sequence raining cloudy = T T = ν for which ν(φ) = ν(raining ∧ cloudy) = T.
Another way of writing the fact that ν(φ) = T, or that φ is true with the
observed combination of values of the atomic propositions, is ν ⊧ φ, or ν is
a model of the formula φ. If φ is not true with the given combination
of atomic proposition values ν, we say that ν ̸⊧ φ, or that ν is a counter
model of φ.
Anyways, thinking about this in terms of truth tables is in my opinion more illustrative than most alternative presentations.
$\endgroup$ $\begingroup$See Dirk van Dalen, Logic and Structure (5th ed., 2013), page 17 for the definition and the basic result:
"If a valuation is only given for atoms then it is, by virtue of the definition by recursion, possible to extend it to all propositions."
What is a valuation ? Simply a function: $v : \text {PROP} \to \{ 0,1 \}$,
where [see page 7] $\text {PROP} = \{ p_0, p_1, \ldots \}$ is the collection of proposition symbols.
Side condition: van Dalen uses $\bot$ and consider it as a $0$-ary connective. Thus, he needs the clause: for every valuation $v$ we must have: $v(\bot)=0$.
Silly examples of valuations:
$v(p_i)=0$, for every $i$; $v'(p_i)=1$, for every $i$.
Starting with an assignment $v$, we can easily show how the truth tables for the basic connectives [see page 18] give us the recipe for computing the truth value for a formula $\varphi$ whatever.
Consider the formula $((p_0 ∧ p_1) → (\lnot p_0))$ [similar to the example used in your previous post] and build the usual truth table:
$$\begin{array}{c|c|c} p_0&p_1&(p_0 \land p_1)&(\lnot p_0)&((p_0\land p_1)\to(\lnot p_0))&\\\hline 1&1&1&0&0\\ 1&0&0&0&1\\ 0&1&0&1&1\\ 0&0&0&1&1\\ \end{array}$$
Consider now the following valuation: $v(p_0)=0$ and $v(p_1)=1$. It simply amounts to the third line in the table above.
Note: as we can imagine [but we can prove it: see Lemma 2.2.3, page 18], what matters are only the value that the valuation assigns to the propositional symbols occurring into the formula.
The "recipe" is:
(i) $v(p_0)=0$; thus $v[(\lnot p_0)]=1$.
(ii) $v(p_0)=0$ and $v(p_1)=1$; thus $v[(p_0 \land p_1)]=0$.
(iii) $v[(p_0 \land p_1)]=0$ and $v[(\lnot p_0)]=1$; thus $v[((p_0 \land p_1)\to (\lnot p_0))]=1$.
Note: in computing the truth value of the formula, we have followed the formation sequence [see Definition 2.1.4, page 9] of the formula:
$\endgroup$$p_0, p_1, (p_0 \land p_1), (\lnot p_0), ((p_0 \land p_1)\to (\lnot p_0))$.
