¿Cómo se valida que dos expresiones matemáticas son iguales?

Question

Digamos que tienes unas expresiones como las siguientes:

$$\begin{array}((x+17)^2 \\ x^2 + 34x + 289 \end{array} \\ 288 + \frac{x^2}{2} + \frac{x^2}{2} + 34x + 1 \\ [...]$$

Ya te haces una idea: hay un número infinito de formas de representar la misma expresión. El reto es que mi aplicación está validando respuestas a problemas matemáticos, introducidas por estudiantes de matemáticas que practican un determinado concepto. Me gustaría asegurarme de que cada vez que envíen una respuesta, el verificador sea completamente insensible a las cuestiones de ordenación, simplificación, formato, etc., lo que sería sencillamente frustrante. También me gustaría admitir más de una variable como x, y, z en la misma expresión.

¿Cuál es una forma fiable de comprobar que dos expresiones son iguales? La forma más bruta que se me ocurre sería simplemente introducir un número en cada variable de cada expresión y ver cuál es el resultado.

Sin embargo, tengo la corazonada de que podría haber formas de obtener falsos positivos de esta manera. Eso, y puede que me esté perdiendo algo realmente obvio sobre esto, o puede que haya una mejor manera de hacer la comparación.

Me encantaría escuchar su opinión.

Answer 1

En general, este es un problema difícil. Para las clases de expresiones para las que existe una forma canónica, como los polinomios (en cualquier número de variables), la respuesta es sencilla: dos expresiones son iguales si y sólo si tienen la misma forma canónica. (Una forma canónica significa que para cada expresión hay una y sólo una expresión canónica a la que es igual, y existe un procedimiento eficaz para calcular la forma canónica de cualquier expresión dada). Entonces se puede obtener un algoritmo para comparar dos expresiones: calcular la forma canónica de cada expresión y comprobar si las formas canónicas son idénticas.

Los estudiantes de álgebra aprenden a hacer exactamente esto para decidir ellos mismos si dos polinomios son iguales. (Los estudiantes de aritmética aprenden un método análogo para decidir si dos expresiones aritméticas son iguales, por ejemplo convirtiendo la expresión $2\cdot(3+4)$ en la forma canónica $14$ ; este algoritmo es una subrutina del que reduce las expresiones polinómicas a la forma canónica). Una forma canónica para polinomios es combinar todos los términos similares, listar los términos en orden descendente de grado, con los términos de igual grado listados en orden lexicográfico por las variables que contienen, o algo por el estilo. Calcular una forma canónica para un polinomio arbitrario no es un asunto difícil. Es el tipo de cosa que un programador competente puede producir en un par de horas; o, como han sugerido otras personas aquí, puedes poner las soluciones en un sistema de álgebra computacional, que contendrá exactamente este tipo de algoritmo para varios tipos de expresiones diferentes.

Pero para expresiones más generales puede ser extremadamente difícil, o incluso imposible, decidir si las dos expresiones son iguales. No existe una forma canónica, y reconocer cuándo dos expresiones concretas son iguales puede ser un teorema importante. Por ejemplo, consideremos las expresiones $\cos 2x$ y $\left(\cos x\right)^2 - \left(\sin x\right)^2$ . Son iguales, pero no es evidente. O para un ejemplo más difícil, considere las dos expresiones $$0$$ y $$\sum_{a,b,c > 1\atop n>2} I(a^n + b^n - c^n)$$ (donde $I(x)$ denota la función que tiene $I(0)=1$ y $I(x)=0$ para $x\ne 0$ ). Se conjeturó durante algún tiempo que estas dos expresiones eran iguales, pero la prueba resultó ser algo complicada.

El párrafo anterior era una broma, pero es una broma seria: una parte sustancial de las matemáticas es precisamente cómo realizar esos cálculos y reconocer cuándo dos expresiones que parecen diferentes son iguales. Euler es famoso (entre otras cosas) por reconocer que $e^{ix}$ y $\cos x + i\sin x$ son expresiones iguales. Dejando de lado las bromas, un teorema de Daniel Richardson dice que para una clase bastante pequeña y bastante natural de expresiones, hay no que pueda determinar de forma fiable la igualdad en todos los casos.

Por lo tanto, para obtener una respuesta, tiene que ser más específico sobre cuál es su pregunta. Si sólo necesitas comparar polinomios, la respuesta es bastante sencilla. Si tus expresiones son más complicadas que eso, puede que haya o no una respuesta; depende de lo que contengan.

[ Addendum: Veo que has añadido comentarios diciendo que sólo te interesan los polinomios, y que quieres saber si tu idea de sustituir los valores de prueba por $x$ es sólida. Es sólido, pero introducir un número no es suficiente, ni siquiera para los polimios simples. Los polinomios $x+1, 3x-1$ y $3-x$ todos tienen el mismo valor en $x=1$ . Pero puede evitar fácilmente los falsos positivos comprobando $n+1$ diferentes valores para un $n$ polinómico de tercer grado. Un polinomio de grado $n$ está completamente determinada por sus valores en $n+1$ puntos, por lo que si dos polinomios de grado $n$ estar de acuerdo en $n+1$ diferentes puntos puede estar seguro de que son idénticos; ni siquiera importa qué $n+1$ valores de la muestra. (En el ejemplo anterior, cualquier valor de $x$ que no sea $x=1$ es suficiente para distinguir los tres polinomios). Del mismo modo, si el polinomio tiene tres variables $x$ , $y$ y $z$ de grados $n_x, n_y,$ y $n_z$ basta con seleccionar $n_x+1$ valores para $x$ , $n_y+1$ valores para $y$ y $n_z+1$ valores para $z$ , y luego comprueba todos los $(n_x+1)(n_y+1)(n_z+1)$ triples de esos valores. ]

Answer 2

@AlexandrKurilin Creo que el enfoque matemático no es el problema. El software es la clave. Dos expresiones $A$ y $B$ son iguales si: se puede pasar de $A$ a $B$ , o puede ir de $B$ a $A$ , o puede ir de $A$ a $C$ y de $B$ a $C$ . Donde Ir a significa que sólo se utiliza si operaciones.

Como ha mencionado, puede haber infinitas representaciones. Así que las soluciones que se me ocurren para tu problema son:

• Pida a los alumnos que expresen la solución en una totalmente simplificado expresión. Esto depende de la aplicación, puede que algunas veces no sea única. Pero como ejemplo, si la respuesta debe ser un polinomio, entonces puedes pedirles que lo factoricen, o que lo expandan completamente y agrupen los términos similares, etc.
• Proporcionar una lista de posibles respuestas o plantillas de respuestas. No soy particularmente aficionado a los problemas de opciones múltiples en matemáticas, pero tal vez pueda proporcionarles pautas de cómo podrían expresarse las diferentes respuestas posibles. A partir de ahí, crear un analizador sintáctico como el que sugieres sería más fácil.
• Utiliza un motor como Mathematica o Mapple que pueda comparar las soluciones por ti. La automatización que buscas puede lograrse codificando en esos programas. Aquí el aspecto matemático de tu pregunta se resolvería completamente.

Su sugerencia de utilizar valores es muy propensa a errores por dos razones. 1. A menos que esté codificando en un entorno con capacidades de álgebra de precisión arbitraria, entonces dos expresiones correctas diferentes podrían dar resultados (ligeramente) diferentes. 2. 2. A menos que se pruebe con todos los valores posibles de las variables, no se puede confirmar que la solución propuesta sea igual a la expresión correcta.

Teniendo en cuenta esto, entonces probaría sobre una lista de valores de prueba y no sólo uno. Una manera fácil en una variable sería definir los extremos a un segmento $a$ y $b$ y un tamaño de paso $\delta$ y rellenar la lista con $a$ , $a+\delta$ , $a+2\delta$ , $\cdots$ , $b$ . Llamémosles $x_1$ , $x_2$ , $\cdots$ , $x_n$ y que $A(x)$ y $B(x)$ las dos expresiones a comparar. Debido a los errores numéricos, definiría una métrica y una tolerancia para compararlas y las declararía iguales si, por ejemplo, $$\sum_{i=1}^n\left[A(x_i)-B(x_i)\right]^2<\epsilon$$

La tolerancia $\epsilon$ puede ser necesario adaptarlo para los problemas que tienen regiones sensibles.

Answer 3

En el caso de los polinomios, se pueden expandir todos los productos y reunir los términos similares para obtener una forma canónica. O puedes calcular el máximo grado posible d y comprobar que dos polinomios tienen los mismos valores en d+1 puntos.