It depends a bit on exactly how fuzzy you need your search to be. Are you searching for an exact match, or for a partial match in those fields?
Assuming the exact match, you just need a formula that looks in the multiple name fields, and multiple department fields for a match. Let's call the search query fields NameQuery and DepartmentQuery. Then you could construct this formula which would return true if the value in NameQuery is found within one of the name fields, and the value in DepartmentQuery is found in one of the department fields.
@IsMember(NameQuery; Name1:Name2:Name3) & @IsMember(DepartmentQuery; Department1:Department2:Department3:Department4);
If instead you need to search for a partial match, you could use the @LIKE formula. First, concatenate the name and department field values into a single string using @IMPLODE. You can then do a wildcard match. This isn't very efficient, mind you, so if you're working on tens of thousands of documents you might want to find a better solution.
AllNameItems := @Implode(Name1:Name2:Name3; " ");
AllDepartmentItems := @Implode(Department1:Department2:Department3:Department4; " ");
@Like(AllNameItems; "%" + NameQuery + "%") & @Like(AllDepartmentItems; "%" + DepartmentQuery + "%");