# Showing that the following isn't complete

1. May 26, 2007

### Palindrom

Let's have a look at $$\left\{ \neg,\equiv\right\}$$. How could one show that this isn't complete?

I've tried finding some sort of invariance that propositions built with these might have, but I couldn't find anything... I'm going crazy!

2. May 27, 2007

### fopc

Proof? You might try to prove that operator -> can't be expressed by any combination of the operators ~ and <->.

A start would be to show that the truth table for any proposition that is made up of 2 or more propositional
symbols and only the operators ~ and <-> must have an even number of ones and an even number of zeros in its last column (call it the even property). I think it's pretty clear this would have to be done by induction.

Then argue that since -> has the odd property it can't be expressed using only ~ and <->.

(The operator -> could be replaced by either V or &.)

Last edited: May 27, 2007
3. Jun 1, 2007

### Palindrom

Thanks, I did do this eventually, and just came back here now to thank anyone that might have answered.

So thanks!