$testo = explode(" ", $_POST["testo"]);
$parola1 = $testo[0];
$parola2 = $testo[1];

$leggi = "SELECT * FROM prenotazioni
WHERE
nome LIKE '%$parola1%' OR
nome LIKE '%$parola2%' OR
cognome LIKE '%$parola1%' OR
cognome LIKE '%$parola2%'"


Questo dovrebbe andare allora...