$str = "cat dog rat elephant giraffe";
$searchstr = "cat dog";

@array = split (/\s+/, $searchstr);

foreach $animal (@array)
{
  # Here I build my IF statement, which I will execute
  # when I have finished my loop!

  $execute .= "$str =~ /$animal/ && ";
}

#finish off the string...chop off hanging &&
$execute =~ s/ && //;

# HOW DO I DO THIS???
# THIS OBVIOUSLY DOESNT WORK !!!
if ($execute}
{
  print "Found a DOG and a CAT!\n\n";
}