What sort of Index for 'AND' columns?

I have a Table with people, and want to select where the person is not deleted. I have a non-clustered primary key on the ID (PersonID). 'Deleted' is a DATETIME, nullable, and is populated when deleted.

So, my query looks like this:

SELECT * FROM dbo.Person
WHERE PersonID = 100
AND Deleted IS NULL

This table can grow to around 40,000 people. Should I have an index that covers the Deleted flag as well?

I may also query things like:

   SELECT * FROM Task t
   INNER JOIN Person p
      ON p.PersonID = t.PersonID
      AND p.Deleted IS NULL
   WHERE t.TaskTypeId = 5
   AND t.Deleted IS NULL

Task table can estimate is 1.5 million rows.

I think I need one that covers both the pk and the deleted flag on both tables? (Task.TaskId, Task.Deleted) and (Person.PersonID and Person.Deleted)?

via Chebli Mohamed