How can I prove if it holds or not for those operators?


closed as off-topic by choco_addicted, Daniel W. Farlow, user223391, user147263, Leucippus Apr 13 '16 at 0:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – choco_addicted, Daniel W. Farlow, Community, Leucippus
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ @DerekElkins Nand and nor are nonassociative. Who said anything about xor? $\endgroup$ – bof Apr 12 '16 at 19:33
  • $\begingroup$ @DerekElkins OOPS! I misread the question. I thought the OP was asking about nand and nor. I blame it on my bad eyes. Never mind! $\endgroup$ – bof Apr 12 '16 at 19:42
  • $\begingroup$ Nonassociativity of NAND (and NOR) is alleged in this old answer. Associativity of XOR was the subject of this old question and this one. $\endgroup$ – bof Apr 12 '16 at 19:52

The "grunt" approach would be to write out a massive truth table and manually check it, and that might be what's required. However, I think the easiest way to prove such a thing (if it's true) is to use the De Morgan laws, and the Distributivity laws. These are:

  • (De Morgan 1) $\neg (A \wedge B) \leftrightarrow \neg A \vee \neg B$;
  • (De Morgan 2) $\neg (A \vee B) \leftrightarrow \neg A \wedge \neg B$;
  • (Distributivity 1) $A \wedge (B \vee C) \leftrightarrow (A \vee B) \wedge (A \vee C)$;
  • (Distributivity 2) $A \vee (B \wedge C) \leftrightarrow (A \wedge B) \vee (A \wedge C)$.

(These can all be checked easily enough using truth tables.)

If it's false, then hopefully after fiddling around with the formulas without getting them equivalent you'll realise this. In this case, you might well have to write out the truth table to find a counterexample.

To demonstrate, let's look at the sheffer stroke. What we want to show is: $$ ((A \mid B) \mid C) \leftrightarrow (A \mid (B \mid C))$$ The sheffer stroke is also known as NAND, because it's equivalent to $\neg (A \wedge B)$. Again, you can see this easily enough by looking at a truth table. So it's enough to show: $$\neg (\neg (A \wedge B) \wedge C) \leftrightarrow \neg (A \wedge \neg (B \wedge C))$$ Using the De Morgan Laws, I find that I have for $(A \mid B) \mid C$: $$ \neg (\neg (A \wedge B) \wedge C) \leftrightarrow (\neg \neg (A \wedge B) \vee \neg C)$$ and for $A \mid (B \mid C)$: $$ \neg (A \wedge \neg (B \wedge C ) ) \leftrightarrow (\neg A \vee \neg \neg (B \wedge C))$$ Since we know that $\neg \neg A \leftrightarrow A$, the right-hand sides simplify to $\neg A \vee (B \wedge C)$ and $(A \wedge B) \vee \neg C$.

Hmm. These don't look equivalent: in the first expression, all we need is for $A$ to be false, and the whole thing comes out true; and in the second, if $C$ is true, then the whole thing comes out false. So if we just put $A$ false, $B$ whatever (say true) and $C$ true, then we have $(A \mid B) \mid C$ is true and $A \mid (B \mid C)$ is false. Hence they're not equivalent, so $\mid$ is not associative.

  • $\begingroup$ You consider a truth table with eight rows "massive"? $\endgroup$ – bof Apr 12 '16 at 18:05
  • $\begingroup$ Well, maybe not massive, but considering each row would be 2 calculations per formula, that's 32 in total - I'd say that's a fair few $\endgroup$ – Alex McKenzie Apr 12 '16 at 18:09
  • 1
    $\begingroup$ If you happen to know that the operation is commutative, then you only need to check two of the eight rows, e.g. the TTF and the FFT rows. $\endgroup$ – bof Apr 12 '16 at 18:13

HINT: I’ll write $\oplus$ for exclusive OR. The simplest approach is to check whether $(p\oplus q)\oplus r$ and $p\oplus(q\oplus r)$ have the same truth table. I’ve calculated the truth table for $(p\oplus q)\oplus r$; you can fill in the remaining two columns to check that in fact $(p\oplus q)\oplus r$ and $p\oplus(q\oplus r)$ do have the same truth table, and hence $\oplus$ is associative.

$$\begin{array}{c|c|c} p&q&r&p\oplus q&q\oplus r&(p\oplus q)\oplus r&p\oplus(q\oplus r)\\ \hline T&T&T&F&&T\\ T&T&F&F&&F\\ T&F&T&T&&F\\ T&F&F&T&&T\\ F&T&T&T&&F\\ F&T&F&T&&T\\ F&F&T&F&&T\\ F&F&F&F&&F\\ \end{array}$$

Once we know that $\oplus$ is associative, we can ignore parentheses and simply write

$$\bigoplus_{k=1}^np_k=p_1\oplus p_2\oplus\ldots\oplus p_n$$

for any positive integer $n$. You might try to prove that this is $T$ if and only if an odd number of the operands $p_k$ are $T$.

You can use the same approach to deal with the Sheffer stroke.


Not the answer you're looking for? Browse other questions tagged or ask your own question.