x <- c(
    "The dog and the man play in the park.",
    "The man plays with the dog.",
    "That is the man's hat.",
    "Man I love that dog!",
    "I'm dog tired",
    "The dog park is no place for man.",
    "Park next to this dog's man."
)

grepl("^(?!.*park)(?=.*dog.*man|.*man.*dog)", x, ignore.case=TRUE, perl=T)
grepl("^(?!.*park)(?=.*dog)(?=.*man)", x, ignore.case=TRUE, perl=T)