Teorema de incompletitud de Gödel


Kurt F. Gödel, en «Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas afines» [paráfrasis]:

«Existen argumentos lógicos imposibles de ser deducidos verdaderos o falsos; entre ellos, la coherencia de dichos razonamientos.»

La existencia verdadera o falsa de algo (por ejemplo, las piedras; al contrario, las hadas), no implica que la misma sea demostrable así, ni que deba o no tenerse fe en cualquiera de estas posibilidades.

·

La creatividad surge de hallar –pensando diferente del resto– ideas absurdas, para así nuevamente pensarlas y darles coherencia.

Ahí la importancia de la Lógica: porque sólo con ella es posible tanto hallar los absurdos como obtener la coherencia.

·

jueves, 20 de diciembre de 2012

ESTRUCTURA ALGEBRAICA DE LA LÓGICA DIGITAL


Sean un conjunto {0,1} y dos leyes de composición interna + y ·, entonces se puede observar como funciona la siguiente estructura:

  • Para +:
    • 0+0=0
    • 0+1=1
    • 1+0=1
    • 1+1=1

  • Para · :
    • 0·0=0
    • 0·1=0
    • 1·0=0
    • 1·1=1

Por tanto cumple las siguientes propiedades:

  • Para +:
    • La asociativa: eg. 0+(1+0)=(0+1)+0
    • La conmutativa: eg. 0+1=1+0
    • La modular: eg. 1+0=1, 0+0=0
  • Para · :
    • La asociativa: eg. 0·(0·1)=(0·1)·1
    • La conmutativa: eg. 0·1=1·0
    • La modular: eg. 0·1=0, 1·1=1

Dadas las propiedades, la estructura algebraica planteada es un semianillo abeliano. Así se desarrolla la lógica matemática aplicada digitalmente a circuitos integrados. En general se puede establecer lo siguiente:

  • Sean los elementos a, b ∈ {0,1}, entonces se cumple para +, es decir, la disyunción:
    • La propiedad asociativa: a+(b+c)=(a+b)+c
    • La propiedad conmutativa: a+b=b+a
    • La propiedad modular: a+0=a; b+0=b
    • Nótese que a+a=a, en efecto, 0+0=0 y 1+1=1
  • Sean los elementos a, b ∈ {0,1}, entonces se cumple para ·, es decir, la conjunción:
    • La propiedad asociativa: a·(b·c)=(a·b)·c
    • La propiedad conmutativa: a·b=b·a
    • La propiedad modular: a·1=a; b·1=b
    • Nótese que a·a=a, en efecto, 0·0=0 y 1·1=1
  • Dado que es un semianillo abeliano y con a, b, c ∈ {0,1}, se cumple lo siguiente para ambas leyes de composición:
    • La propiedad distributiva: a·(b+c)=a·b+a·c

Ahora bien, se pueden desarrollar funciones dentro del semianillo abeliano que se ha observado:

  • La función de negación se define y se caracteriza como sigue:
    • ∀a | a ∈ {0,1}, a'={1. a'=0 | a=1, 2. a'=1 | a=0
    • O sea, que para esta función y sólo ésta, la ley de disyunción no está definida cuando b=a.
    • Nótese que a+a'=1, a·a'=0, (a')'=a.
  • Para la función de disyunción exclusiva se tiene:
    • ∀a, b | a, b ∈ {0,1}, a⊕b=a·b'+a'·b
    • Es una función compuesta por otras funciones (negación, diyunción y conjunción) y por dos variables.

En general todas las funciones, mientras sean deducidas con una variable y varios parámetros y estén definidas en todas las operaciones del semianillo, pueden ser deducidas a partir de las condiciones que se marquen, por ejemplo:

  • Sea la función como se muestra a continuación:
    • f(0,0)=1, f(0,1)=1, f(1,0)=1, f(1,1)=0.
    • Así que: f(a,b)=a'·b'+a'·b+a·b'
    • Sólo se operan disyuntivamente los valores de la función iguales a 1 dado que en la disyunción el 0 es el elemento neutro y por tanto no es determinante para la estructura de la misma.
    • Dado que sólo se toman los valores de 1 disyuntivamente, conjuntivamente se toman todos los casos 0 como funciones de negación de las variables y todos los casos 1 como las variables ya que así se procura la obtención de los 1 buscados. Así f(0,0) implica a'·b', f(0,1) implica a'·b, etc.
  • Sea la función como se muestra a continuación:
    • f(0,0,0)=1, f(0,0,1)=0, f(0,1,0)=1, f(0,1,1)=1, f(1,0,0)=1, f(1,0,1)=1, f(1,1,0)=0, f(1,1,0)=0, f(1,1,1)=0.
    • Así que: f(a,b,c)=a'·b'·c'+a'·b·c'+a'·b·c+a·b'·c'+a·b'·c, f(a,b,c)=a'·c'·(b'+b)+a'·b·c+a·b'·(c'+c), f(a,b,c)=a'·c'+a'·b·c+a·b', f(a,b,c)=a'·(c'+b·c)+a·b'
    • Se simplifica la función dada la propiedad distributiva y se halla al elemento neutro de la conjunción.
  • De la función de negación de la disyunción exclusiva se entiende lo siguiente:
    • ∀a, b | a, b ∈ {0,1}, a⨀b=a'·b'+a·b
    • Se puede demostrar que a⨀b=(a⊕b)'
    • Demostración: Se deduce la función dados los valores posibles (a⊕b)'=f(a,b); f(0,0)=1, f(0,1)=0, f(1,0)=0, f(1,1)=1. Así (a⊕b)'=a'·b'+a·b=a⨀b.

Háblese ahora de las funciones de Morgan:

  • Primera: (a+b)'=a'·b'=m₁(a,b)
    • Demostración: m₁(0,0)=1, m₁(0,1)=0, m₁(1,0)=0, m₁(1,1)=0 ⇔ m₁(a,b)=a'·b'
  • Segunda: (a·b)'=a'+b'=m₂(a,b)
    • Demostración: Dada la primera función de Morgan, (a'+b')'=a·b, así (a·b)'=a'+b'

Estas funciones pueden servir para demostrar nuevamente la negación de la disyunción exclusiva:

  • Sea a⨀b=(a⊕b)', dada la primera función de Morgan, a⨀b=(a·b'+a'·b)', a⨀b=(a·b')'·(a'·b)'.
  • Con la segunda función de Morgan a⨀b=(a'+b)·(a+b'), a⨀b=(a'+b)·a+(a'+b)·b', a⨀b=a·a'+a·b+a'·b'+b·b'.
  • Reduciendo las formas w·w' al elemento neutro de la disyunción, a⨀b=a·b+a'·b'. Como así se define la función a⨀b, la aseveración inicial es correcta.

Las funciones de Morgan son universales, es decir, son definitorias de la negación, la disyunción y la conjunción:

  • Respecto a la primera función:
    • Negación: ∀a | a ∈ {0,1}, a'=m₁(a,a)
    • Conjunción: ∀a, b | a, b ∈ {0,1}, a·b=m₁(m₁(a,a),m₁(b,b))
    • Disyunción: ∀a, b | a, b ∈ {0,1}, a+b=m₁(m₁(a,b),m₁(a,b))
  • Respecto a la segunda función:
    • Negación: ∀a | a ∈ {0,1}, a'=m₂(a,a)
    • Conjunción: ∀a, b | a, b ∈ {0,1}, a·b=m₂(m₂(a,b),m₂(a,b))
    • Disyunción: ∀a, b | a, b ∈ {0,1}, a+b=m₂(m₂(a,a),m₂(b,b))

Existe para el semianillo abeliano definido una clase de equivalencia de las funciones que comparten el mismo resultado con una función f de n variables. Se les llama a los valores que toman dichas variables códigos. Algunos ejemplos son:

  • Código BCD: f(0,0,0,0)=b(0,0,0,0), f(0,0,0,1)=b(0,0,0,1), f(0,0,1,0)=b(0,0,1,0), f(0,0,1,1)=b(0,0,1,1), f(0,1,0,0)=b(0,1,0,0), f(0,1,0,1)=b(0,1,0,1), f(0,1,1,0)=b(0,1,1,0), f(0,1,1,1)=b(0,1,1,1), f(1,0,0,0)=b(1,0,0,0), f(1,0,0,1)=b(1,0,0,1), y de f(1,0,1,0) hasta f(1,0,1,1) la función b queda indefinida. Los valores que las variables de b pueden tomar son fundamentalmente el código.
  • Código de exceso a 3 (XS-3): f(0,0,0,0)=x(0,0,1,1), f(0,0,0,1)=x(0,1,0,0), f(0,0,1,0)=x(0,1,0,1), f(0,0,1,1)=x(0,1,1,0), f(0,1,0,0)=x(0,1,1,1), f(0,1,0,1)=x(1,0,0,0), f(0,1,1,0)=x(1,0,0,1), f(0,1,1,0)=x(1,0,1,0), f(0,1,1,1)=x(1,0,1,1), y de f(1,0,0,0) hasta f(1,1,1,1) la función x está indefinida. Se caracteriza porque los valores que toman las variables en BCD tres combinaciones después en f son equivalentes en x, es decir, f(0,0,0,0)=x(0,0,1,1) pero tres combinaciones después de f se tiene f(0,0,1,1)=b(0,0,1,1) que es igual la combinación de BCD a la de XS-3.
  • Código Gray: f(0,0,0,0)=g(0,0,0,0), f(0,0,0,1)=g(0,0,0,1), f(0,0,1,0)=g(0,0,1,1), f(0,0,1,1)=g(0,0,1,0), f(0,1,0,0)=g(0,1,1,0), f(0,1,0,1)=g(0,1,1,1), f(0,1,1,0)=g(0,1,0,1), f(0,1,1,1)=g(0,1,0,0), f(1,0,0,0)=g(1,1,0,0), f(1,0,0,1)=g(1,1,0,1), f(1,0,1,0)=g(1,1,1,1), f(1,0,1,1)=g(1,1,1,0), f(1,1,0,0)=g(1,0,1,0), f(1,1,0,1)=g(1,0,1,1), f(1,1,1,0)=g(1,0,0,1), f(1,1,1,1)=g(1,0,0,0). Se caracteriza porque de una combinación a otra de g sólo cambia de valor una variable, ejemplo: f(0,0,1,1)=g(0,0,1,0), f(0,1,0,0)=g(0,1,1,0).

26 de Diciembre de 2010

No hay comentarios:

Publicar un comentario en la entrada