Validez y Satisfacibilidad

Aritmética

La aritmética es una rama de las matemáticas que se ocupa del estudio de los números y las operaciones fundamentales sobre ellos, como la suma, la resta, la multiplicación y la división.

Acá veremos la formalidad de conceptos matemáticos como números y aritmética. Se introduce la sintáxis para construir expresiones matemáticas y su estructura definida. Las cuales son:

Un número, por ejemplo: $1, 35, 8$ . A estas expresiones les llamaremos constantes.
Una letra, por ejemplo: $x, y, z$ . A estas expresiones les llamaremos variables.
Al combinar dos expresiones con un operador y encerrar el resultado entre paréntesis, se pueden crear expresiones más complejas. Los operadores utilizados son +, −, *, /, ˆ (para potenciación). Por ejemplo, al usar el operador − entre la variable $z$ y la constante $6$ , se forma la expresión $(z − 6)$ . Los paréntesis redundantes se pueden eliminar según las reglas que se explicarán más adelante.
A su vez, cada una de estas expresiones puede volver a combinarse con otras formando expresiones más complejas, por ejemplo: ((x + y)/(2ˆx)) + (6/3) Para poder expresar propiedades como 2 + 1 es igual a la expresión 3, o que x es menor a x + 1 agregaremos símbolos de relación.
Al combinar dos expresiones con un símbolo de relación, creamos una fórmula. Las fórmulas son un tipo específico de expresión. Los símbolos de relación que consideramos incluyen $=, <, ≤, >, ≥$ . Por ejemplo, al tomar las expresiones 2 * 6 y x + 7 con el símbolo de relación $=$ , obtenemos la fórmula 2 + 6 = x + 7.

Precedencia y Tipado

La precedencia establece el orden de las operaciones en una expresión

El tipado asigna tipos de datos para definir qué se puede hacer con ellos.

La precedencia de los operadores nos permite escribir fórmulas extensas de manera clara. Cuando un operador tiene mayor precedencia que otro, podemos escribir la fórmula sin necesidad de paréntesis y sigue teniendo un significado único.

El operador * tiene mayor precedencia que +, por lo que interpretamos 2 + 4 * 3 como 2 + (4 * 3).
Sin embargo, esto no siempre se aplica, como en (2 + 4) * 3 , que 2 + 4 * 3 , donde los paréntesis cambian el significado de la expresión.

Los operadores asociativos permiten eliminar paréntesis cuando se aplican múltiples veces.
Por ejemplo, (2 + 4) + 7 = 2 + (4 + 7), se puede escribir: 2 + 4 + 7. Los operadores + y * son asociativos.

El concepto de tipado en las expresiones matemáticas nos ayuda a asegurar que las expresiones tengan sentido y representen valores coherentes. Cada operador o función tiene un tipo que indica qué tipo de valores acepta como entrada y qué tipo de valor produce como salida.

En el contexto algebraico, los valores suelen ser de tipo número $Num$ , o booleano $Bool$ . Por ejemplo, en una operación de suma, tanto los operandos como el resultado deben ser números. Además, debemos considerar los operadores de relación, como el igual ( $=$ ) y los símbolos de desigualdad ( $≤, < , ≥, >$ ), los cuales devuelven valores booleanos que representan la comparación entre dos expresiones. Estos conceptos son esenciales para garantizar la coherencia y el significado claro de las expresiones matemáticas, incluyendo la capacidad de expresar conceptos de verdad y falsedad.

Ejemplo 1:

Sacamos paréntesis innencesarios teniendo en cuenta la precedencia de los operadores y la asociatividad de los mismos.

(8 − 6) * x = (6 * (x^2)) + 3

≡ { precedencia de * por sobre + } Se puede eliminar porque se sabe que el * tiene mayor precedencia que el +.

(8 − 6) * x = 6 * (x^2) + 3

≡ { precedencia de 2 sobre * } En este caso el 2 tiene mayor precedencia que el * por lo que se puede eliminar el parentesis.

(8 − 6) * x = 6 * x^2 + 3

En este punto los parentésis que quedan son importantes por lo tanto aca termina el proceso de eliminacion de parentesis innecesarios.

Tabla de precedencias

De mayor a menor precedencia:

$\sqrt{},\; \^{}$	Raíces y potencias
$*, \; /$	Producto y división
$max, \; min$	Máximo y mínimo
$+, \; -$	Suma y resta
$=, \; \leq, \; <, \; \geq, \; >$	Operadores de comparación
$\neg$	Negación
$\lor, \land$	Disyunción y conjunción
$\implies, \Longleftarrow$	Implicación y consecuencia
$\equiv, \not\equiv$	Equivalencia y discrepancia

Precedencia y tipado con operaciones booleanas

Un booleano es un tipo de dato que puede tener uno de dos valores: verdadero (true) o falso (false).
Se utiliza en la lógica y la programación para representar condiciones de verdad o falsedad.

La lógica proposicional usa True y False con operadores booleanos ( $\land, \lor, \implies, \iff, \neg$ ) para expresar relaciones lógicas simples, como “si a > b y b > c, entonces a > c”.

(a > b) ∧ (b > c) \implies (a > c)

Al complejizarse el lenguaje, es necesario establecer reglas de notación para poder escribir las expresiones con mayor claridad y sin ambigüedades.

Ejemplo 1:

Debemos sacar todos los paréntesis que sean superfluos según las reglas de precedencia de los operadores booleanos.

(((p \implies q) ∧ (q \implies p)) \implies (p ≡ q))

Sacamos el paréntesis mas grande que contiene a todos los demás.

((p \implies q) ∧ (q \implies p)) \implies (p ≡ q)

Sacamos el paréntesis que contiene a $(p \implies q) ∧ (q \implies p)$ ya que el operador $\land$ tiene mayor precedencia que el operador $\implies$ .

(p \implies q) ∧ (q \implies p) \implies (p ≡ q)

Una vez que se eliminaron los paréntesis superfluos, se da por terminado el proceso de eliminación de paréntesis innecesarios.

Ejemplo 2:

Ahora al revés, debemos agregar paréntesis para que la expresión sea clara y no ambigua.

p \implies q ≡ p ∨ q ≡ q

Agregamos paréntesis en $\implies$ y $∨$ para que la expresión sea clara.

(p \implies q) ≡ (p ∨ q) ≡ q

Como $q$ no opera con nadie, no es necesario agregar paréntesis.

Validez y Satisfactibilidad

Una expresión es válida si cumple las reglas lógicas sin importar los valores específicos de las variables.

Una expresión es satisfacible al ser verdadera en al menos una interpretación.

La validez es independiente de los valores de las variables, mientras que para demostrar la no validez es suficiente encontrar un contraejemplo. Una fórmula es no satisfactible si no existe ningún valor que la haga verdadera.

En el siguiente ejemplo veremos en qué valores de x satisface la ecuación.

Ejemplo 1:

6 * x + 8 = x + 3

≡ { restar x en ambos miembros }

6 * x + 8 − x = x + 3 − x

≡ { aritmética }

5 * x + 8 = 3

≡ { restar 8 en ambos miembros }

5 * x + 8 − 8 = 3 − 8

≡ { aritmética }

5 * x = −5

≡ { dividir por 5 en ambos miembros, aritmética }

x = −1

Por lo tanto, la ecuación es satisfactible para $x = −1$ .

En el siguiente ejemplo demostraremos que las siguientes ecuaciones son válidas.

Ejemplo 2:

4 * x + 14 = 2 * (2 * x + 5) + 4

≡ { distributividad de * con +, def. de * }

4 * x + 14 = 4 * x + 10 + 4

≡ { def. de + }

4 * x + 14 = 4 * x + 14

≡ { reflexividad de = (e = e) }

True

En el siguiente ejemplo veremos que la siguiente ecuación no es válida, es decir, que no es verdadera para todos los valores de x.

Ejemplo 3:

Para la ecuación $3 * x + 1 = 3 * (x + 1)$ . Definimos contraejemplo: $x := 5$ falsifica la fórmula ya que:

3 * 5 + 1=3 * 5 + 3

≡ { def. de * }

15 + 1 = 15 + 3

≡ { def. de + }

16 = 18

≡ { igualdad de números }

False

Por lo tanto, la ecuación no es válida.

Tabla de operadores

$p$	$q$	$\neg p$	$p \land q$ Conjunción	$p \lor q$ Disyunción	$p \implies q$ Implicación	$p \equiv q$ Equivalencia	$p \not\equiv q$ Discrepancia
$False$	$False$	$True$	$False$	$False$	$True$	$True$	$False$
$False$	$True$	$True$	$False$	$True$	$True$	$False$	$True$
$True$	$False$	$False$	$False$	$True$	$False$	$False$	$True$
$True$	$True$	$False$	$True$	$True$	$True$	$True$	$False$

Introducción (IAA)Lógica Proposicional