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