1

Please provide an example with {→,⊕} that can't be realized with {¬,⊕}. I can't think of what I can't realize with {¬,⊕}.

I have a simple model where I think the bottom is more like YES ⊕ NO (and it doesn't at all look like YES OR NO even though the picture doesn't say that YES and NO can't both be true for the same input(?)

enter image description here

It depends what we want the algorithm to do but usually the output should be neither "both YES and NO" nor "neither YES nor NO".

I understand we might want the cases with no answer for one case of input or both yes and no answer for another case of input.

The system I was modelling would output 0 XOR 1 and never something else.

Niklas Rosencrantz
  • 2,265
  • 2
    Is $\oplus$ exclusive OR? – Brian M. Scott Mar 17 '13 at 20:10
  • Yes please. Thank you very much. – Niklas Rosencrantz Mar 17 '13 at 20:10
  • 1
    $\land$ should work. I will leave it to others to figure out exactly how :-) – Myself Mar 17 '13 at 20:12
  • @Myself Yes, we don't need ∧ for a binary output. – Niklas Rosencrantz Mar 17 '13 at 20:14
  • 1
    I don't understand your remark but the main thing is that $\land$ is not 'affine', i.e if you consider the isomorphism with the boolean algebra $\mathbb F_2[x,y]$ then $\land$ is non linear while $\lnot$ and $\oplus$ only permit linear functions. – Myself Mar 17 '13 at 20:15
  • @Myself I think you're right and that {¬,⊕} can't do → and can't do ∧ and those aren't needed(?) since ∧ can do → and vice versa.I mean to realize a YES (¬¬) or to realize a NO (¬) you won't need → or ∧. – Niklas Rosencrantz Mar 17 '13 at 20:17
  • 1
    I have written an answer that should clarify my remark. – Myself Mar 17 '13 at 20:30
  • Thank you. I mean the difference between {0⊕1} and {0∨1}. The output should be {0⊕1} and not {0∨1}. Do you agree? – Niklas Rosencrantz Mar 17 '13 at 20:51
  • 1
    @NickRosencrantz To show that a set of logical connectives is complete means to show that there is a connective that can't be realized with it, not that there is a value (0 or 1) that can't be realized with it. That is why the answers you are getting mention connectives (like $\vee$) that do not appear in the problem statement. – Trevor Wilson Mar 17 '13 at 21:14
  • Thank you so much for the information. I only deal with decision problems so all I need to do is excluding. http://upload.wikimedia.org/wikipedia/commons/0/06/Decision_Problem.svg You see the answer is 0 XOR 1 (which is not 0 OR 1 which is logically implossible. I interpret the statement TRUE OR FALSE as false and the statement TRUE ⊕ FALSE as always true. – Niklas Rosencrantz Mar 17 '13 at 21:54
  • 1
    In my answer to your previous question I linked to an earlier question with a concrete example of a function that cannot be produced with XOR alone. – hmakholm left over Monica Mar 17 '13 at 22:05
  • Thanks! That statement is not the output of a decision problem or is it? Is it true that XOR can output the output of any decision problem since the output of any decision problem is 0 XOR 1? Why do I need something else than the output from a decision problem? – Niklas Rosencrantz Mar 17 '13 at 22:07

3 Answers3

6

Show that $\lor$ cannot be produced using only $\neg$ and $\oplus$. One way to do this is to show that if $f(p,q)$ is any proposition in two variables constructed solely with $\neg$ and $\oplus$, the $4$-row truth table of $f$ has a $\mathsf{T}$ in an even number of rows. You can do this by structural induction on $f$: show that if $f$ has the property, then so does $\neg f$, and that if $f$ and $g$ have the property, then so does $f\oplus g$.

Note that you can replace $\lor$ by any connective that has an odd number of $\mathsf{T}$’s in its truth table; $\land$ works equally well, as does $\to$.

Brian M. Scott
  • 616,228
  • Many thanks Brian. It's very interesting but my answer won't need ∨ ever. I mean to realize a YES (¬¬) or to realize a NO (¬) you won't need →,∨ or ∧ anywhere. – Niklas Rosencrantz Mar 17 '13 at 20:22
  • 2
    @Nick: I don’t understand your comment. In order to show that ${\neg,\oplus}$ is not complete, you have to find a connective that it cannot generate, and $\lor$ is such a connective (though not, as I mentioned, the only one). – Brian M. Scott Mar 17 '13 at 20:23
  • I can't do →, &, ∨ but I don't understand the use for these if I just want to output 0 or 1. Thank you very much. I understand that I can't realize for instance A→B but the output {0⊕1} is never A→B. I mean the difference between {0⊕1} and {0∨1} – Niklas Rosencrantz Mar 17 '13 at 20:31
  • 1
    @Nick: I think that you don’t really understand what the problem is asking you to do. You are supposed to show that there is some Boolean connective (or function) that cannot be produced as a composition of $\neg$ and $\oplus$. I’ve suggested that you do this by showing that if $f(p,q)$ is a binary Boolean function that can be produced by composing $\neg$ and $\oplus$ in some way, then $0,2$, or $4$ of the values $f(0,0),f(0,1),f(1,0)$, and $f(1,1)$ must be $1$. But the function corresponding to $\lor$ is $f(0,0)=0,f(0,1)=f(1,0)=f(1,1)=1$, with three outputs of $1$, not $0,2$, or $4$, ... – Brian M. Scott Mar 17 '13 at 22:49
  • ... so it cannot be built up from $\neg$ and $\oplus$. Since there is then at least one Boolean connective/function that can’t be built up from $\neg$ and $\oplus$, ${\neg,\oplus}$ is not complete. – Brian M. Scott Mar 17 '13 at 22:50
3

It looks like you're confused about what "complete set of connectives" means.

By definition, what the claim "$\neg$ and $\oplus$ form a complete set of connectives" means is:

Every possible truth table is the truth table for the output of some expression built with only $\neg$ and $\oplus$ in addition to the input variables (and parentheses etc.)

Here, of course "possible truth table" implies that the ground rules for truth tables are followed -- every combination of input values must appear in exactly one line, but the output values are arbitrary, that is, no matter which output values we choose it must be possible to come up with an expression that produces exactly these outputs.

Since the claim we're investigating is one about "every truth table", it willl be false (and therefore $\{{\neg},{\oplus}\}$ is not a complete set) if we can find even a single truth table that doesn't have a matching expression. It is easy for an "every X" statement to go wrong, hard for it to hold.

Here's a truth table that has no matching expression built with only $\neg$ and $\oplus$:

 input 1     input 2   |   output
 --------------------------------
    0           0      |     0
    0           1      |     1
    1           0      |     1
    1           1      |     1

(It happens to be the truth table for $\lor$, but that is not important, except possibly as a way to name the truth table without writing it down explicitly. What is important here is that we're interested in whether $\{\neg,\oplus\}$ can make every truth table. Here's some random truth table -- can we make it or not?)

It turns out that we can't. It is quite possible to find an expression with two variables (and all connectives $\neg$ or $\oplus$) such that inputs 0,0 produce output 0, and a different expression such that inputs 0,1 produce output 1, and so forth. But there's no single expression that produces the right answer for every line of the truth table.

(For proof that this particular truth table cannot be made, see the answer I linked to earlier).

So we know that this particular truth table cannot be generated with $\neg$ and $\oplus$ alone. We can then stop worrying about which other truth tables are possible or not; the existence of even one that can't be produced means by definition that $\neg$ and $\oplus$ is not complete.

Community
  • 1
hmakholm left over Monica
  • 286,031
  • I understand. Thanks. My thoughts are about decision problems only and that could be slightly different from functional completeness. I never need any other logic than XOR and negation. – Niklas Rosencrantz Mar 17 '13 at 22:47
  • 1
    @NickRosencrantz: What do you mean by "my thoughts are about decision problems"? What about the decision problem "is the two-bit input in the set ${01,10,11}$?"? – hmakholm left over Monica Mar 17 '13 at 22:48
  • For instance what a decision problem can't model or what my "system" with XOR plus some other operator can't model. I don't know that. Thank you for the discussion. I will try and work with the problem you mention above. I look to learn how to model decision problems. – Niklas Rosencrantz Mar 17 '13 at 22:49
  • @NickRosencrantz: What do you mean by "what a decision problem can't model"? I don't understand where decision problems enter your train of thought at all. What are you doing (or proposing to do?) with a decision problem (or all decision problems?) that involves $\neg$ and $\oplus$? – hmakholm left over Monica Mar 17 '13 at 22:52
  • Economics for instance or any implication that can be modelled with XOR. We code ternary statements like A ? 1: 0 that always output 0 XOR 1. I put java and C code with ternary statements and it seemed that I could write anything with a ternary statement and that a ternary statement can be written with XOR. – Niklas Rosencrantz Mar 17 '13 at 22:55
  • 1
    @Nick: It is not true that A?1:0 always results in 0 XOR 1. If A is false, then A?1:0 evaluates to 0, but 0 XOR 1 is 1 which not the same as 0. – hmakholm left over Monica Mar 17 '13 at 22:57
  • I mean the output always has state 0 XOR 1so as long as I model output the output is 0 XOR 1 and that 0 XOR 1 is always true. In this case, A is false and output has the value 0 and 0 XOR 1 is always true. – Niklas Rosencrantz Mar 17 '13 at 22:59
  • 1
    Are you perhaps misunderstanding what "XOR" means? It is neither more nor less than the particular two-input function $f$ such that $f(0,0)=0$ and $f(1,0)=1$ and $f(0,1)=1$ and $f(1,1)=0$. There's nothing ternary or metaphysical about it. – hmakholm left over Monica Mar 17 '13 at 23:00
  • 1
    In particular, saying "the output is always either 0 or 1" is not the same as saying "the output is always $0\oplus 1$". The former means "it is always the case that the output is 0 or that the output is 1 but not both at the same time". The latter means "the output is always 1", because "$0\oplus 1$" is just a verbose way to write $1$. – hmakholm left over Monica Mar 17 '13 at 23:02
  • I do think a difference between "always either A or B" and "always A or (also) B" and it's not always easy to know whether to use or or xor, especially if we don't assume any timeline. – Niklas Rosencrantz Mar 17 '13 at 23:07
2

There are two ways to look at boolean connectives/functions. The usual way it to let $\mathbf B = \{0,1\}$, so you may think of them as functions $\mathbf B^i \to \mathbf B$. This is the classical interpretation with a truth table. For instance, $\land(0,1) = 0$.

But alternatively, you may think about boolean functions as polynomials over the field $\mathbf F_2 = \{0,1\}$. Then the 'addition' matches $\oplus$ and 'multiplication' matches $\land$. Now note that in this language

$$ \begin{aligned} \lnot x &= 1+x \\ x\land y &= xy \\ x\lor y &= \lnot(\lnot x \land \lnot y) = 1 + (1+x)(1+y) = x+y+xy \\ x \oplus y &= x+y\\ x\to y &= (\lnot x \lor y) = (1+x)\lor y = 1+x + y + y + xy = 1+x+xy\dots \end{aligned} $$

This means that if you are only allowed to combine $\oplus$ and $\lnot$, then the only functions you can make by composing these are the affine ones, this mean functions of the form $$ a_0 + a_1 x_1 + a_2 x_2 + \dots + a_nx_n. $$ Where $a_i \in \{0,1\}$. (In particular, for $2$ variables $x$ and $y$, there are $8$ affine functions namely $0$, $1$, $x$, $1+x$, $y$, $1+y$, $x+y$ and $1+x+y$.)

However, $\to$ is clearly non-affine, because it contains the second degree term $xy$, which shows that it cannot be created from composition of $\oplus$ and $\lnot$.

Myself
  • 8,781