It turns out this is yet another problem with missing and/or inconsistent documentation.
The correct predicate in this case is the following one:
[NSPredicate predicateWithFormat:@"(excludedOccurrences.@count == 0) OR (0 == SUBQUERY(excludedOccurrences, $sub, $sub.day == %@).@count)", today]
In the predicate, a subquery is used to test if the number of related excludedOccurrences with a date matching your test date is equal to zero. However, the documentation is misleading. Here is what the Predicate Programming Guide says regarding the use of predicates in conjunction with to-many relationships.
Using Predicates with Relationships
If you use a to-many relationship, the construction of a predicate is slightly different. If you want to fetch Departments in which at least one of the employees has the first name “Matthew,” for instance, you use an ANY operator as shown in the following example:
NSPredicate *predicate = [NSPredicate predicateWithFormat:
@"ANY employees.firstName like 'Matthew'"];
If you want to find Departments in which all the employees are paid more than a certain amount, you use an ALL operator as shown in the following example:
float salary = ... ;
NSPredicate *predicate = [NSPredicate predicateWithFormat:
@"ALL employees.salary > %f", salary];