¿Selección de conectores lógicos {¬,∨,∧,⇒,⇔} en teoría de conjuntos?

Tampoco es exhaustivo, ya que en realidad hay 16 declaraciones compuestas posibles (y los conectores lógicos correspondientes) para elegir. (Dado que {¬,∨,∧,⇒,⇔} ya es redundante, ¿por qué no incluir los otros 11 conectores, algunos de los cuales son MUY útiles como "nand" ⊼ , "nor" ⊽ y "exclusive or" ⊻?)

Algunas de las "16 posibles declaraciones compuestas" son de hecho casos triviales (y también el ¬ aparece dos veces). En realidad, solo cinco de los dieciséis no se pueden hacer con uno de los cinco operadores estándar. Consulte la siguiente tabla:

Table   Name                       Value for x..y
------------------------------------------------------
0000    Contradiction              False
0001    Conjunction                x ∧ y
0010    Nonimplication                      ¬(x ⇒ y)
0011    Left projection            x
0100    Converse nonimplication             ¬(y ⇒ x)
0101    Right projection           y
0110    Exclusive disjunction               ¬(x ⇔ y)
0111    Inclusive disjunction      x ∨ y
1000    Nondisjunction                      ¬(x ∨ y)
1001    Equivalence                x ⇔ y
1010    Right complementation      ¬y
1011    Converse implication       y ⇒ x
1100    Left complementation       ¬x
1101    Implication                x ⇒ y
1110    Nonconjunction                      ¬(x ∧ y)
1111    Affirmation                True

Como puede ver, solo cinco (no implicación, no implicación inversa, disyunción exclusiva, no disyunción, no conjunción) no están en este 'conjunto estándar'. Sin embargo, hay libros que también introducen ⊻, disyunción exclusiva, como operador estándar.

Estoy ayudando en un curso de informática sobre matemáticas básicas y la semana pasada alguien me preguntó:

¿Por qué tenemos un símbolo para ⊆ (subconjunto), si ya tenemos ⊂ (subconjunto propio) y = (igualdad)? "a ⊆ b ≡ a ⊂ b ∨ a = b", por lo que el operador es redundante.

No pude encontrar una mejor respuesta que "Porque los matemáticos son vagos y quieren escribir las cosas lo más cortas posible ". Claramente, eso es saltar a conclusiones, pero de hecho creo que es bastante probable que haya algo de verdad allí. Uno podría preguntarse, "¿por qué se definió × (multiplicación)?", porque en los números naturales simplemente puede sumar: 5 × 3 = 5 + 5 + 5 = 3 + 3 + 3 + 3 + 3. Yendo más allá, puede pregunte: "¿Por qué se definieron 2 y 3, si también puede escribir 1+1 y 1+1+1?" En algún momento, realmente es mucho trabajo escribir todo, por lo tanto, se introdujo más notación.

Por supuesto, puede definir su propia notación. Al definir no implicación, disyunción exclusiva, no disyunción y no conjunción, tiene un conjunto exhaustivo. Defina los que necesita a menudo en la parte superior de su escritura.

Entonces, ¿cómo llegamos a este conjunto estándar de operadores lógicos? Utilizándolos y averiguando cuáles necesitamos con frecuencia. También tenga en cuenta que las cinco declaraciones que no existen pueden formarse negando otro operador (vea la cuarta columna en la tabla anterior) y que esto no es posible si deja fuera cualquiera de las cinco 'estándar'.

Generalmente se usa el conjunto {¬,∨,∧,⇒,⇔} porque incluye los "más naturales".

Si empezamos con un conjunto mínimo, como {¬,⇒}, los demás se suelen introducir como abreviaturas.

No hay una razón "profunda": principalmente la tradición, y un equilibrio "razonable" entre ahorro (minimalidad) y legibilidad (expresar p ∧ q como ¬(p ⇒ ¬q) no es tan "natural".

gnasher729 planteó un punto importante que merece alguna expansión: "En la lógica formal, la implicación x ⇒ y y la equivalencia x ⇔ y son obviamente muy útiles: expresan directamente los conceptos posiblemente más importantes de la lógica formal".

El punto principal que quiero mencionar es este: la teoría de conjuntos ingenua no es la única teoría de conjuntos importante, y la lógica clásica no es la única lógica importante. En la mayoría de las lógicas, no es cierto que P⇒Q sea lo mismo que ¬P∨Q. A medida que te adentres más en la lógica, te darás cuenta gradualmente de que la implicación es (en un sentido muy profundo) "más fundamental" que incluso la conjunción o la disyunción.

Pero puedo darte una probada de eso ahora. No necesita los otros conectores si tiene cuantificación sobre proposiciones e implicación. Usaremos la convención habitual de que la implicación se asocia a la derecha (es decir, A⇒B⇒C significa A⇒(B⇒C); puedes razonar sobre esto observando que A⇒B⇒C es equivalente a (A∧B )⇒C). Luego puede definirlos en términos de reglas de Gentzen:

• P∧Q es equivalente a ∀S.(P⇒Q⇒S)⇒S
• P∨Q es equivalente a ∀S.(P⇒S)⇒(Q⇒S)⇒S
• ¬P es equivalente a ∀SP⇒S

Puede que reconozca este último como ex falso quodlibet .

La cuantificación sobre proposiciones parece algo "nuevo", pero en realidad no lo es. De hecho, cuando dijo que "P⇒Q podría escribirse ¬P∨Q", en realidad está afirmando que alguna declaración es verdadera para todas las proposiciones P y Q, que es la cuantificación universal sobre las proposiciones. Tendemos a ocultar ese detalle a los estudiantes universitarios para que puedan familiarizarse con la lógica proposicional sin tener que pensar en la cuantificación.

Pensamiento final: El "sentido profundo" al que aludí anteriormente es que la implicación lógica es un morfismo en la teoría de categorías, y la implicación es un objeto exponencial. No espero que entiendas esa oración, pero un ejemplo puede ayudar.

Considere el modus ponens . Si tenemos P⇒Q y tenemos P, entonces podemos concluir Q. Sin embargo, en teoría de conjuntos, si tenemos una función f : A → B y un valor x : A, entonces podemos aplicar la función al valor, dando f(x) : B.

Resulta que esto no es solo un truco de notación o una coincidencia. Es una conexión que es muy profunda.

Hay dos posibles funciones lógicas sin entradas, "verdadero" y "falso". No usamos símbolos para ellos, solo nombres.

Hay cuatro funciones lógicas posibles con una entrada: "Verdadero" y "falso" (cualquiera que sea la entrada, la salida es "verdadera", o cualquiera que sea la entrada, la salida es "falsa"), identidad (salida = entrada) y negación (salida = opuesto de entrada). Tres de estos no requieren un símbolo. Para el cuarto usamos el símbolo ¬. Ese es uno de sus cinco símbolos, y realmente nos gustaría un símbolo para esa función.

Hay 16 funciones lógicas posibles con dos entradas. Seis de ellos en realidad no "usan" ambas entradas; si llamamos a las entradas x e y, estas seis funciones son "falso", "verdadero", x, y, ¬x e ¬y. Así que quedan 10 funciones.

En lógica formal, la implicación x ⇒ y y la equivalencia x ⇔ y son obviamente muy útiles: expresan directamente los conceptos posiblemente más importantes de la lógica formal. En otras áreas relacionadas con la lógica son mucho menos importantes, pero son extremadamente importantes en la lógica formal. Al tener un símbolo para "a implica b", en realidad no necesitamos uno para "a está implícito en b", simplemente podemos escribir "b implica a". (Puede usar una flecha de derecha a izquierda; algunos dirían que en realidad no es un símbolo diferente). Si agregamos las negaciones (sin símbolo extra para "a no es equivalente a b" y "a no implica b") entonces se cubren otras seis funciones, quedan cuatro.

Para los últimos cuatro, son posibles varias formas razonables de representarlos con símbolos. Tenemos un símbolo para lógico y ("ambos") y lógico o ("al menos uno", o "uno o ambos") y junto con sus negaciones todo está cubierto. Podríamos haber usado "ninguno", "como máximo uno", pero lógico y lógico o haber ganado la competencia. Agregue sus negaciones, y todo está cubierto.

Esa es la lógica formal; otras áreas que utilizan la lógica tienen otras demandas. En la toma de decisiones (utilizada a menudo en el desarrollo de software), los lógicos y, los lógicos o y la negación son los más utilizados. La implicación y la equivalencia rara vez se utilizan. En el hardware de computadora, nand (no (a y b)) y nor (no (a o b)) se implementan de forma bastante natural en el hardware de computadora más simple, y todo se basa en estas dos funciones. Sin embargo, esta es un área que no está destinada al consumo humano, a diferencia de la lógica formal.

Fuera de contextos lógicos muy fundamentales, realmente no hay mucho que ganar comenzando con un conjunto mínimo adecuado de conectores y definiendo el resto. Todo lo que hace es complicar indebidamente las cosas. Incluso en lógica, podríamos comenzar con el trazo de Sheffer en lugar de {~, ->}, pero preferimos no confundir indebidamente a nuestros estudiantes universitarios.

Permítanme darles una razón completamente diferente, por qué, al menos, presentar ∨,∧,⇒ por separado puede tener sus méritos.

La lógica clásica es buena y todo, pero algunas personas realmente se preocupan por la lógica intuicionista . En la lógica intuicionista no se puede definir ninguno de los conectores ¬,∨,∧,⇒ en términos de otros dos cualesquiera. Esto se debe a que muchas leyes familiares como (una de) las leyes de deMorgan o ¬A∨B ⇔ (A ⇒ B) no se cumplen. En realidad, existe un tipo de semántica para la lógica intuicionista (proposicional) dada por categorías cerradas bicartesianas . Desde este punto de vista, este "tema" es completamente natural:

En estas categorías cerradas bicartesianas tenemos productos binarios de proposiciones dados por "∧", coproductos binarios dados por "∨" y exponencialesdado por "⇒". Se podría decir, que todavía me falta el ¬. Las categorías cerradas bicartesianas tienen un objeto inicial. Corresponde al símbolo ⊥ de "falsedad" o "contradicción". La negación de una proposición A es entonces simplemente A ⇒ ⊥ (esto también funciona en la lógica clásica). No hay razón para creer (y sabemos que no es posible), que estas construcciones puedan reducirse entre sí (Tampoco funciona en categorías familiares, como las categorías de conjuntos y funciones, tampoco). Entonces, si te interesa la teoría de categorías o la lógica intuicionista, naturalmente introducirías ⊥, ∧, ∨ y ⇒ por separado (en realidad, me falta el objeto terminal ⊤, que denota "verdad", pero no es realmente importante aquí).

Dado esto, tampoco tiene sentido definir "todos los conectores binarios posibles" ya que no hay valores de verdad en la lógica intuicionista y, por lo tanto, hay infinitos conectores posibles (y no solo 16). Sin embargo, los conectores ∧, ∨ y ⇒ son, se podría decir, especiales, ya que cada uno satisface una propiedad de mapeo universal bastante básica (esto puede verse en parte por las reglas familiares de "eliminación" e "introducción" en "Deducción natural") .

Los matemáticos son flojos... Tan flojos que algunos usan computadoras... Pero las computadoras necesitan ser simples para ser implementadas y miniaturizadas electrónicamente... Entonces, como CISC .vs. RISC, solo se requiere negación, conjunción (y) y disyunción (inclusivo-o), o mejor NAND (no-y) y NOR (no-o) para expresar cualquier conjunto lógico (ver resolución de Karnaugh, teorema de Church-Turing, ASIC programación)

Después,

use presentaciones de alto nivel con muchos operadores para que parezca breve y luego aparentemente simple...

use un conjunto reducido de operadores para ejecutarlo fácil y rápidamente

Hay muchos 'compiladores' para convertir...