a patica seria algo asi:
$sql4 = "SELECT nombre,apellido FROM TUTABLA where nombre='$nombre' and apellido='$apellido' ";
$result4 = mysql_query($sql4) or die("La siguiente consulta contiene algún error:<br>nSQL: <b>$sql</b>");
if (mysql_num_rows($result4) == 0)
{ echo "no encontrado...insertas en tu base de datos"}
else
{
echo " Nombre y apellido ya existen en la BD"
}
//espero q te sirva saludos