Prove that $\hat{h}_1(S) = \hat{h}_2(S)$ in propositional logic.

by Oscar   Last Updated July 12, 2018 01:20 AM

I have the following task:

"For all sentences $S$ of propositional logic and for all evaluation functions $h_1$ and $h_2$, if $h_1$ & $h_2$ match for all atomic sentences in S, then $\hat{h}_1(S) = \hat{h}_2(S)$ obtains."

Progress so far:


h: The truth assignment function from the set of the atomic sentences of a language to the set $\{T,F\}$

$\hat{h}$: The result of extending h with the following rules:

  1. $\hat{h}(Q) = h(Q)$ for the atomic sentences Q.
  2. $\hat{h}(\perp) = F$
  3. $\hat{h}(\neg Q) = T$ iff $\ \hat{h}(Q) = F$
  4. $\hat{h}(Q \land R) = T$ iff $\ \hat{h}(Q) = \hat{h}(R) = T$
  5. $\hat{h}(Q \lor R) = F$ iff $\ \hat{h}(Q) = \hat{h}(R) = F$
  6. $\hat{h}(Q \to R) = F$ iff $\ \hat{h}(Q) = T \ \& \ \hat{h}(R) = F$
  7. $\hat{h}(Q \leftrightarrow R) = T$ iff $\ \hat{h}(Q) = \hat{h}(R)$

Atomic sentence: "A ... sentence which is either true or false ... and which cannot be broken down into other simpler sentences".


In my own words, I would begin by trying to make the following statements:

If $h_1$ and $h_2$ match for all atomic sentences in S, then they assign the always same truth values. Then, any time where $h_1$ is true, $h_2$ is true (and visa versa). Maybe I could apply this information to the definitions given for $\hat{h}$ to show that this logically implies that the extensions $\hat{h}_1$ and $\hat{h}_2$ must exhibit identical behavior (i.e, be true under the same conditions).

Am I thinking in the right direction?

If so, how can I formally state this as a proof?

Related Questions

Proving one compactness theorem from the other

Updated May 17, 2018 22:20 PM

Proofs Using Tautologies

Updated April 17, 2016 08:08 AM

Satifiability proof of formulas with pure literals

Updated April 22, 2015 21:08 PM