When no terms are chosen as filters in a view all results are returned I have a view with exposed filters that are taxonomy terms. These are multiple select. 

When none of the options are selected the nodes are not filtered by that vocabulary so everything is returned. But what I need to happen is only noes not tagged with any of those terms be shown. Can this be done?
So you want the inverse of a search? Or have I misunderstood?

If thats what you mean I think you can change that inside your view settings. 

Go to Structure > Views > edit your view 

Then select your filter criteria and edit it. I think you need to check the following check box.