# Logic: Help me understand Interpretations (or $Assignements$) + Exercise

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!

• 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. – Mauro ALLEGRANZA Sep 4 '17 at 5:57
• Formulas are either (i) atomic ones, or (ii) built-up from already existing formulas by way of conncetives. – Mauro ALLEGRANZA Sep 4 '17 at 5:58
• 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. – Mauro ALLEGRANZA Sep 4 '17 at 6:00
• 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$. – Mauro ALLEGRANZA Sep 4 '17 at 6:02
• 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. – 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$)
• 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... – user452306 Sep 4 '17 at 9:49
• @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$ – Bram28 Sep 4 '17 at 12:07