I've got an exercise that should help me introduce Interpratations / Assignements in (propositional) logic.
But sadly I cannot get my head around this concept, and I think I'm missing some basic definitions...

The exercise is the following:

Find a formula $F$ containing the three atomic formulas $A$, $B$, and $C$ with the following property:

  • For every assignment $\mathcal A ∶ \{A, B, C\} \to \{0, 1\}$, changing any of the values $\mathcal A(A)$, $\mathcal A(B)$, $\mathcal A(C)$ also changes $\mathcal A(F)$.

What I (think, I) understand, is that:

  • I need to find a formula (how? any random?),
  • Which has three atomic formulas (what is exactly an atomic formula? Is it just a term in propositional logic?), which are either $\{0, 1\}$ (true or false).
  • And that formula should change it's truth-value for any (??) change of either 3 sub-formulas/atomic formulas

If all that is correct, wouldn't $\mathcal A(F) = A \land B \land C$ with $A = 1, B = 1, C = 1$ be a correct answer?

Any help is greatly appreciated!

  • $\begingroup$ Yes; atomic formulas are the propositional letters of the language, denoted with $p_1, p_2, \ldots$ or in some simila way, according to the syntactical specifications of the language. $\endgroup$ – Mauro ALLEGRANZA Sep 4 '17 at 5:57
  • $\begingroup$ Formulas are either (i) atomic ones, or (ii) built-up from already existing formulas by way of conncetives. $\endgroup$ – Mauro ALLEGRANZA Sep 4 '17 at 5:58
  • $\begingroup$ An assignment is a function that maps atoms (or prop letters) into truth values: $\mathcal A : \{ p_i \} \to \{ 0,1 \}$. For every assigment $\mathcal A$, using the truth tables for the conncetives, we can compute the truth value of any "complex" formula. $\endgroup$ – Mauro ALLEGRANZA Sep 4 '17 at 6:00
  • $\begingroup$ Silly example with a single atom A instead of three: the formula $F$ will be $\lnot A$. In this case, whatever the assignment $\mathcal A : \{ A \} \to \{ 0,1 \}$ will be, changing the value of $\mathcal A (A)$ will "swap" the truth value of $\lnot A$. $\endgroup$ – Mauro ALLEGRANZA Sep 4 '17 at 6:02
  • 1
    $\begingroup$ It is the "standard" math symbol for function (compare with : $f: \mathbb R \to \mathbb R$ for a real-valued function). It means that the function $\mathcal A$ maps the atoms belonging to the set $\{ A, B , C \}$ into the values $0$ and $1$ (the atoms are the "inputs" and the truth-values are the "outputs"). Of course $\mathcal A$ assigns a specific value to each atom: not necessarily the same value to all inputs. $\endgroup$ – Mauro ALLEGRANZA Sep 4 '17 at 9:51

No, $A \land B \land C$ is not going to work, since if $A = B = C = 0$, then it is false, and changing any one of the values $A$, $B$, or $C$ is not going to change that.

What would work is $A \ XOR \ B \ XOR \ C$, since the generalized $XOR$ is true iff an odd number of its arguments are true.

If you can't use $XOR$, then use the $\leftrightarrow$. That is, $A \leftrightarrow (B \leftrightarrow C)$ will do the job as well. And if you can't use $\leftrightarrow$ either, but can only use the Boolean connectives $\land$, $\lor$, and $\neg$, then use:

$$(A \land B \land C) \lor (A \land \neg B \land \neg C) \lor (\neg A \land B \land \neg C) \lor (\neg A \land \neg B \land C)$$

(this is equivalent to $A \ XOR \ B \ XOR \ C$)

| cite | improve this answer | |
  • $\begingroup$ Thank you. In that case, would I write it as follow $\mathcal A(F)= A \oplus B \oplus C$? Or only $F = A \oplus B \oplus C$? I'm just struggling to understand what the assignment/interpretation role is... $\endgroup$ – user452306 Sep 4 '17 at 9:49
  • 1
    $\begingroup$ @user452306 $A \oplus B \oplus C$ is the formula, so that would be $F$. $\mathcal A$ is the truth assignment that maps atomic propositions into truth-values, and thereby formulas into truth-values as well. So, for example, with this $F$, if $\mathcal A(A)=1, \mathcal A(B)=0, \mathcal A(C)=1$, then $\mathcal A(F)=0$. Change any one truth-assignment, and the truth-assignment for $F$ changes as well. For example, if we keep $\mathcal A(A)=1, \mathcal A(B)=0$ but make $\mathcal A(C)=0$, then $\mathcal A(F)=1$ $\endgroup$ – Bram28 Sep 4 '17 at 12:07

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.