Write a statement in propositional logic that says $x \in A Δ B$. Solution should use at most two connectives.

Question

We have two sets $A$ and $B$ and some object $x$. Let’s introduce two propositional variables:

• $a$, which states that $x \in A$, and

• $b$, which states that $x \in B$.

I get as far as $(a \lor b) \land \lnot(a \land b)$. But the questions asks for a solution that the total number of connectives used is just two. I have used 4: $\lor$, $\land$, $\lnot$ and another $\land$. How can I reduce even further?

Connected to this question: What does the connection between 𝐴△𝐵△C and A <=> B <=> C?

Answer 1

The symmetric difference $\triangle$ has essentially the logical meaning of the "exclusive or".

More precisely, $x \in A \triangle B$ means that \begin{align}\tag{1} (x \in A) \, \leftrightarrow \, \lnot (x \in B) \end{align} which is a statement with exactly two logical connectives, $\leftrightarrow$ and $\lnot$.

Indeed, according to the semantics of the biconditional $\leftrightarrow$, $(1)$ is true if and only if either $x \in A$ and $x \notin B$, or $x \notin A$ and $x \in B$, as required by the definition of $x \in A \triangle B$.

Answer 2

You can do $x \in A \oplus x \in B$

Here, the $\oplus$ is the symbol for the XOR