No need for both fields. A nullable timestamp column works fine: NULL until the record/row is deleted, at which point it holds the timestamp of when it happened.
You can derive a boolean "is it deleted" flag from that without adding another column to (mis)manage.