How do you express $F \oplus G$ by using some of the connectives $\land$, $\lor$, $\rightarrow$, $\lnot$?

Question

Here is the following task i need help with:

Our interpretation of the formulas is inclusive in the sense that (F $\lor$ G) is true if at least one, but also if both of the formulas F and G are true. If we had wanted to capture an exclusive, or, as we could for example have defined another connective, $\oplus$, and given the following truth value table.

$$\begin{array}{c|c|c|} F& \text{G} & \text{F $\oplus$ G} \\ \hline \text{1} & 1 & 0 \\ \hline \text{1} & 0 & 1 \\ \hline \text{0} & 1 & 1 \\ \hline \text{0} & 0 & 0 \\ \hline \hline \end{array}$$

How can I find a formula containing F, G and which is equivalent to (F $\oplus$ G) so I can express F $\oplus$ G by using some of the connectives, $\land$, $\lor$, $\rightarrow$, $\lnot$?

I would appreciate if you could give reasons for your answer.

Thanks alot!

Answer 1

HINT: I’m assuming that $\oplus$ is exclusive OR. Look at its truth table: $p\oplus q$ is true when exactly one of $p$ and $q$ is true. The statement $p\land\neg q$ says that $p$ is true and $q$ is false.

• Find a statement that says that $q$ is true and $p$ is false.
• Combine them to get a statement that says that exactly one of $p$ and $q$ is true.

Answer 2

Below are two equivalent ways to express the "exclusive or" (XOR, $\oplus$) using the connectives $\land,\; \lor,\; \lnot$:

$$\begin{align}F \oplus G & \equiv (F \lor G) \land \lnot(F \land G)\tag{1}\\ \\ &\equiv (F \land \lnot G) \lor (\lnot F \land G)\tag{2} \end{align}\\$$ \begin{array}{c|c|c|} F& \text{G} & \text{F $\oplus$ G} \\ \hline \text{1} & 1 & 0 \\ \hline \text{1} & 0 & 1 \\ \hline \text{0} & 1 & 1 \\ \hline \text{0} & 0 & 0 \\ \hline \hline \end{array}
\begin{array}{c|c|c|} F& G & (F \lor G) \land \lnot (F \land G) \\ \hline \text{1} & 1 & 0 \\ \hline \text{1} & 0 & 1 \\ \hline \text{0} & 1 & 1 \\ \hline \text{0} & 0 & 0 \\ \hline \hline \tag{1}\end{array}

\begin{array}{c|c|c|} F& G & (F \land \lnot G) \lor (\lnot F \land G) \\ \hline \text{1} & 1 & 0 \\ \hline \text{1} & 0 & 1 \\ \hline \text{0} & 1 & 1 \\ \hline \text{0} & 0 & 0 \\ \hline \hline \tag{2}\end{array}

Answer 3

There are many ways to do it. One is $ \lnot (( P \to Q) \land (Q \to P)) $ but that is a rather complicated one

Answer 4

In my opinion a very efficient and practical way to approach this sort of problem lies in rewriting all the connectives via a scheme developed by St. Lesniewski. I say this on the basis of finding short wffs equivalent to each of the binary and unary operators using just the connectives for "$\rightarrow$" and "$\lnot$", and having read that this scheme allows for efficient conversion to normal forms. This will not come as a complete description of the scheme here or how St. Lesniewski did it on paper exactly, but it does seem close enough for a start. First, I'll just write some of the connectives in this scheme. The "|-" here preferably will not get confused with "$\vdash$". I'll only list some of the members of each group.

    1st group: |-, |-|

---

           |               |   |
2nd group: o-,  o-,  -o-, -o-, o
                               |

For the members of the first group, if a false argument becomes true via the connective, then we draw a vertical line on the left end of the middle line. If a true argument becomes true, then we draw a vertical line on the right end of the middle line. If we do not draw a line in a position, then the argument represented by that position becomes false via the connective. Thus, for example, "-|" represents some connective for which the argument gets taken to a false value when the argument of the connective is false, and the argument gets taken to a true value when the argument of the connective is true.

For the members of the second group, if both arguments hold as false, and we have a line above the circle, then the connective takes that pair of values to a true value. If both arguments hold as true, and we have a line below the circle, then the connective takes that pair of values to a true value. If we have a line on the right side of the circle, and if the first argument qualifies as false and the second argument qualifies as true, then the connective takes that ordered pair of values to a true value. And the spot I've have mentioned comes as the other case as to when the connective takes the arguments to a true value, when we have a line in that spot. So, in St. Lesniewski's scheme

 |
 o- denotes the material conditional.
 |

and

 o denotes logical conjunction.
 |

and

 |- denotes logical negation.

and

-o- denotes logical disjunction.
 |

So, in St. Lesniewski's scheme, you've wanted to find a way to represent

 -o- using variables and the other connectives named above.

Counting the variables and the connectives both as symbols of the same class, it does come as possible to use only 8 symbols. I'll only write the connectives here unless you specifically request that I include the variables, instead of hinting at the 8 symbol solution that I know. Each of "( )", "[ ]", "{ }", "| |" represents some variable. You only need two symbols for variables. Here's the hint:

|  |                  |
o- o-  (  )  [  ]  |- o-   {  }  |  |
|  |                  |

Answer 5

Note that 'exclusive or' $\;\oplus\;$ is just the negation of equivalence $\;\leftrightarrow\;$. So if you are allowed to use the $\;\leftrightarrow\;$ operator, then the answer is just $$ \lnot(F \leftrightarrow G) $$ If you are not allowed to use $\;\leftrightarrow\;$, then you can rewrite $\;F \leftrightarrow G\;$ to one of its many equivalent forms, e.g., $\;(F \to G) \land (G \to F)\;$.

(Note. I usually write these operators as $\;\not\equiv\;$ and $\;\equiv\;$. This makes the symmetry between them more visible. It is also useful to know that both operators are associative, and that they are also mutually associative. So for instance $$ F \not\equiv G \equiv \lnot(F \equiv G) $$ is not ambiguous.)