-1
$\begingroup$

Everybody, Consider the $\%$ truth function. It has the same truth table for $\%$ is the same as a negated biconditional.

I need to determine whether all truth functions can be symbolized using only the $\%$ connective. But I already know that the set of connectives $\{\land, \lor, \neg\}$ is adequate insofar as all truth functions can be symbolized containing no connectives not in THAT set.

So, if the $\{\%\}$ is adequate then I can define every connective in $\{\land, \lor, \neg\}$ in terms of only $\{\%\}$.

I don't think that this can be done. A conjunction is a two-place truth function s.t.
i (1, 1) = 1
i (1, 0) = 0
i (0, 1) = 0
i (0, 0) = 0

However,it doesn't seem like there's any formula consisting in just the $\%$ connective that can capture this, as the two place function is true on the fist row (i.e., when any sentence letters in the formula are true) but if two sentence letters in $\phi\mathbin{\%}\psi$ are true then $\phi\mathbin{\%}\psi$ is false.

Does any have tips about how to proceed, i.e., how to go about giving a proof of whether all truth-functions can be symbolized by $\%$?

$\endgroup$
  • $\begingroup$ Hmm do you get my answer? Feel free to ask if you need clarification. And I noticed you haven't accepted any answer to any of your questions (not just this one). Are they all unsatisfactory to you? $\endgroup$ – user21820 Nov 20 '17 at 8:06
1
$\begingroup$

Your $\%$ operator appears to be what is often called XOR, with the truth table \begin{array}{ccc} x & y & x\% y \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array}

It is true that $\phi\%\psi$ is different from $\phi \land \psi$ when $\phi$ and $\psi$ both are true, but this is not conclusive. After all, the operator sometimes called NAND, defined by $x \mathop{\mathrm{NAND}} y := \lnot(x\land y),$ also has the property that $\phi\mathop{\mathrm{NAND}}\psi$ is different from $\phi \land \psi$ when $\phi$ and $\psi$ both are true, but all truth functions can be constructed from the NAND operator alone.

An interesting fact about XOR is that any sentence built from any combination of atoms and XOR connectives (without any other symbols) is true if and only if an odd number of the atoms are true, counting a true atom that appears $n$ times in the sentence as $n$ true atoms. If you have the right definitions for what makes a sentence, it should be possible to define this fact inductively. It should then be possible to show that none of the three operators $\{\land, \lor, \lnot\}$ can be implemented by XOR.

$\endgroup$
  • $\begingroup$ So my Base Then, doing Structural Induction on WFFs would be something like: every sentence letter is s.t. it is true if an odd number of its atoms is true? $\endgroup$ – Rusty Oct 25 '17 at 2:24
0
$\begingroup$

First, I should note that the % you have here is known as the $XOR$ (for which we sometimes use the symbol $\oplus$)

HINT

Use induction to show that any expression built up from $P$'s, $Q$'s, and any number of $XOR$'s will have an even number of $1$'s when evaluated on a truth table.

ALTERNATIVE HINT

Use induction to show that any expression $\phi$ using any variables and any number of $XOR$'s cannot capture the truth-function that would return True if all variables in $\phi$ are set to False.

Basic Set-up for latter:

Base: $\phi$ is some atomic statement $P$. Clearly this does not capture any truth-function that returns True if $P$ is False.

Step: Suppose $\phi=\phi_1 \ XOR \ \phi_2$, where by inductive hypothesis neither $\phi_1$ nor $\phi_2$ captures any truth-function that returns True when all variables in $\phi_1$ and $\phi_2$ are set to False respectively. Then neither $\phi_1$ nor $\phi_2$ captures any truth-function that returns True when all variables in $\phi$ are set to False, for setting all variables in $\phi$ to False implies setting all variables in $\phi_1$ and in $\phi_2$ to False. This means that when all variables in $\phi$ are set to False, both $\phi_1$ and $\phi_2$ evaluate to False, and hence $\phi = \phi_1 \ XOR \ \phi_2 = False \ XOR \ False = False$ ... meaning that $\phi$ cannot capture any truth-function that returns True when all variables in $\phi$ are set to False.

OK, so that concludes the inductive proof. Are we there yet? Not quite! Because all we have proven is that certain truth-functions as defined over certain variables cannot be proven using an expression built up from $XOR$'s and those very variables, but that does not immediately imply that you couldn't capture that truth-function using an expression built up from $XOR$'s and any variables (i.e including variables that may not be involved with the desired truth-function). To see why this is important, consider what would happen if we could somehow create some expression $\psi$ using some other variables, and suppose that this statement would be equivalent to a tautology ... then $\psi \ XOR \ P$ would be equivalent to $\neg P$, and so we'd be able to express $\neg P$ after all; something we seemed to have ruled out, but now realize might be possible after all.

So, how do we rule out the potential effect of any other variables? Well ... I must say I'm a bit stuck there myself ... Hmmm ... maybe you should go with my original HINT?

$\endgroup$
  • $\begingroup$ May I ask where this hint even came from when thinking about how to answer my question? I think I see where this is going but I have no idea how you thought of this. $\endgroup$ – Rusty Oct 25 '17 at 2:00
  • $\begingroup$ @Rusty Your % is better known as the XOR ... and I just know a thing or two about the XOR from experience :) $\endgroup$ – Bram28 Oct 25 '17 at 2:02
  • $\begingroup$ Thanks, Bram! But how can I deduce your hint given only what I know here? $\endgroup$ – Rusty Oct 25 '17 at 2:05
  • $\begingroup$ @Rusty You mean how would you come up with this particular claim about this particular connective? Good question ... like so many math theorems it can take a while to see something like that ... but it's typically a matter of observing some small cases, noticing some pattern, and then seeing if this pattern holds in general. So, maybe you should do exactly that: generate a few fairly statements involving some $P$'s, $Q$'s, and %'s, and work out their truth tables ... that'll give you some more feeling for how this operator works. $\endgroup$ – Bram28 Oct 25 '17 at 2:25
  • $\begingroup$ So my Base Then, doing Structural Induction on WFFs would be something like: every sentence letter is s.t. it is true if an odd number of its atoms is true? $\endgroup$ – Rusty Oct 25 '17 at 9:50
0
$\begingroup$

Here is a very short and clean answer. $ \def\xor{\oplus} \def\eq{\Leftrightarrow} $

First notice (as in the other answers) that $x\%y = x \xor y$, where "$\xor$" is the standard symbol for xor. Then notice that $x \xor y = ( x + y ) \bmod 2$ if you treat $true,false$ as $1,0$. Thus immediately you get (from basic properties of modulo arithmetic) that $\xor$ is associative and commutative. Hence given any boolean expression comprising only propositions joined by $\xor$, you can freely rearrange it such that all the instances of each proposition are together, without changing its value. Clearly pairs of the same proposition can now be eliminated. Finally observe that if you change the truth value of any proposition that is not completely eliminated (which means it had occurred an odd number of times originally), you will flip the output. So either the output is always $false$ or the output is $true$ for exactly half the possible truth assignments.

For example, $( a \xor b ) \xor ( ( a \xor ( b \xor c ) ) \xor a ) = ( a \xor a \xor a ) \xor ( b \xor b ) \xor c = a \xor c$, where we can drop the brackets because of associativity.


Further exercise: Use the same kind of analysis to show that $\{\neg,\xor,\eq,\top,\bot\}$ is also not adequate. Hint:

$\neg x = (x+1) \bmod 2$ and $x \eq y = (x+y+1) \bmod 2$.

$\endgroup$
  • $\begingroup$ 'select to see'? what does that mean? $\endgroup$ – user178403 Nov 10 '17 at 3:43
  • $\begingroup$ I don't see the relation with my exercise btw. I just have 2 elements in my set $\endgroup$ – user178403 Nov 10 '17 at 3:57
  • $\begingroup$ @MichelleGarcía: Use your mouse to select the blank to see the text. But you should be trying first. Also, I never said my answer answers your question in chat, but you had posted other questions on the main site that would have been trivially answered by the exact technique in my answer here. The goal is to understand the underlying mathematics rather than to just solve your questions. $\endgroup$ – user21820 Nov 10 '17 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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