Writing an NSPredicate that returns true if condition is not met

I'd recommend NSNotPredicateType as described in the Apple documentation.

You can build a custom predicate to negate the predicate that you already have. In effect, you're taking an existing predicate and wrapping it in another predicate that works like the NOT operator:

NSPredicate *pred = [NSPredicate predicateWithFormat:@"SELF contains '-'"];
NSPredicate *notPred = [NSCompoundPredicate notPredicateWithSubpredicate:pred];
[resultsArray filterUsingPredicate:pred];

The NSCompoundPredicate class supports AND, OR, and NOT predicate types, so you could go through and build a large compound predicate with all the characters you don't want in your array, then filter on it. Try something like:

// Set up the arrays of bad characters and strings to be filtered
NSArray *badChars = [NSArray arrayWithObjects:@"-", @"*", @"&", nil];
NSMutableArray *strings = [[[NSArray arrayWithObjects:@"test-string", @"teststring", 
                   @"test*string", nil] mutableCopy] autorelease];

// Build an array of predicates to filter with, then combine into one AND predicate
NSMutableArray *predArray = [[[NSMutableArray alloc] 
                                    initWithCapacity:[badChars count]] autorelease];
for(NSString *badCharString in badChars) {
    NSPredicate *charPred = [NSPredicate 
                         predicateWithFormat:@"SELF contains '%@'", badCharString];
    NSPredicate *notPred = [NSCompoundPredicate notPredicateWithSubpredicate:pred];
    [predArray addObject:notPred];
}
NSPredicate *pred = [NSCompoundPredicate andPredicateWithSubpredicates:predArray];

// Do the filter
[strings filterUsingPredicate:pred];

I make no guarantees as to its efficiency, though, and it's probably a good idea to put the characters which are likely to eliminate the most strings from the final array first so that the filter can short-circuit as many comparisons as possible.

I'm not an Objective-C expert, but the documentation seems to suggest this is possible. Have you tried:

predicateWithFormat:"not SELF contains '-'"