SIMPLIFICACION DE CIRCUITOS LÓGICOS :
Una vez que se obtiene la expresión booleana para un circuito lógico, podemos reducirla a una forma más simple que contenga menos términos, la nueva expresión puede utilizarse para implantar un circuito que sea equivalente al original pero que contenga menos compuertas y conexiones.



SIMPLIFICACIÓN ALGEBRAICA.
El álgebra booleana (Algebra de los circuitos lógicos tiene muchas leyes o teoremas muy útiles tales como :


1. Ley de Morgan :
◦1. A + B = A·B

2. A·B = A + B 2. Ley Distributiva :

◦3. A+(B·C) = (A+B)·(A+C)

4. A·(B+C) = A·B+A·C

Ademas de las leyes formales para las funciones AND y OR :

■5. A·0 = 0 ; A+0 = A

6. A·1 = A ; A+1 = 1

7. A·A = A ; A+A = A

8. A·A = 0 ; A+A = 1

y la Ley de la Involución:

■9. A(negada) = A

Considerar la expresión booleana A·B + A·B + A·B = Y, un diagrama lógico de ésta expresión aparece en la Figura 1. Observar que deben utilizarse seis puertas para implementar este circuito lógico, que realiza la lógica detallada en la tabla de verdad (Tabla 1)

Figura 1: Circuito lógico no simplificado





ENTRADAS SALIDA

B A Y
0 0 0
0 1 1
1 0 1
1 1 1


Figura 2: Circuito lógico simplificado

Aplicando el álgebra booleana :

A·B + A·B + A·B = Y

RAZONES

= A·B + (A·B + A·B) , Propiedad asociativa

= A·B + B·(A+A) , 4. [A·(B + C) = A·B + A·C]

= A·B + B·1 , 8. [A + A = 1]

= A·B + B , 6. [B·1 = B]

= B + A·B , Propiedad conmutativa

= (B + A)·(B + B) , 3. [A + (B·C) = (A + B)·(A + C)]

= (B + A)·1 , 8. [A + A = 1]

= B + A , 6. [A * 1 = A]

Concluimos entonces que una sola puerta OR de dos entradas realiza la misma función (¡ De hecho la tabla 1 corresponde a la función OR !)

CIRCUITOS LOGICOS CON COMPUERTAS

Circuito lógico es aquel que maneja la información en forma de "1" y "0", dos niveles lógicos de voltaje fijos. "1" nivel alto o "high" y "0" nivel bajo o "low".

Los circuitos lógicos están compuestos por elementos digitales como la compuerta AND (Y), compuerta OR (O), compuerta NOT (NO)......
y combinaciones poco o muy complejas de los circuitos antes mencionados.

Estas combinaciones dan lugar a otros tipos de elementos digitales como los compuertas, entre otros.

- compuerta nand (No Y)
- compuerta nor (No O)
- compuerta or exclusiva (O exclusiva)
- mutiplexores o multiplexadores
- demultiplexores o demultiplexadores
- decodificadores
- codificadores
- memorias
- flip-flops
- microprocesadores
- microcontroladores


La electrónica moderna usa electrónica digital para realizar muchas funciones.

Aunque los circuitos electrónicos podrían parecer muy complejos, en realidad se construyen de un número muy grande de circuitos muy simples.

En un circuito lógico digital se transmite información binaria (ceros y unos) entre estos circuitos y se consigue un circuito complejo con la combinación de bloques de circuitos simples.

La información binaria se representa en la forma de:
- "0" ó "1",
- "abierto" ó "cerrado" (interruptor),
- "On" y "Off",
- "falso" o "verdadero", etc.

Los circuitos lógicos se pueden representar de muchas maneras. En los circuitos de los gráficos anteriores la lámpara puede estar encendida o apagada ("on" o "off"), dependiendo de la posición del interruptor. (apagado o encendido)

Los posibles estados del interruptor o interruptores que afectan un circuito se pueden representar en una tabla de verdad.

ECUACIONES BOOLEANAS

Se denomina función lógica o booleana a aquella función matemática cuyos simbolos son binarias y están unidas mediante los operadores del álgebra de Boole suma lógica (+), producto lógico (·) o negación(').


Modos de representación
Existen distintas formas de representar una función lógica, entre las que podemos destacar las siguientes:

Algebraica
Por tabla de verdad
Numérica
Gráfica
El uso de una u otra, como veremos, dependerá de las necesidades concretas en cada caso.

Algebraica
Se utiliza cuando se realizan operaciones algebraicas. A continuación se ofrece un ejemplo con distintas formas en las que se puede expresar algebraicamente una misma función de tres variables.

a) F = [(A + BC’)’ + ABC]’ + AB’C
b) F = A’BC’ + AB’C’ + AB’C + ABC’
c) F = (A + B + C)(A + B + C’)(A + B’ + C’)(A’ + B’ + C’)
d) F = BC’ + AB’
e) F = (A + B)(B’ + C’)
f) F = [(BC’)’(CB)´ (AB’)’]’
g) F = [(A + B)’ + (B’ + C’)’]’

La expresión a) puede proceder de un problema lógico planteado o del paso de unas especificaciones a lenguaje algebraico. Las formas b) y c) reciben el nombre expresiones canónicas: de suma de productos (sum-of-products, SOP, en inglés), la b), y de productos de sumas (product-of-sums, POS, en inglés), la c); su característica principal es la aparición de cada una de las variables (A, B y C) en cada uno de los sumandos o productos. Las d) y e) son funciones simplificadas, esto es, reducidas a su mínima expresión. Las dos últimas expresiones tienen la particularidad de que exclusivamente utiliza funciones NO-Y, la f), o funciones NO-O, la g).

Por tabla de verdad
Una tabla de verdad contiene todos los valores posibles de una función lógica dependiendo del valor de sus variables. El número de combinaciones posibles para una función de n variables vendrá dado por 2n. Una función lógica puede representarse algebraicamente de distintas formas como acabamos de ver, pero sólo tiene una tabla de verdad. La siguiente tabla corresponde a la función lógica del punto anterior.

A B C F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

La forma más cómoda para ver la equivalencia entre una tabla de verdad y una expresión algebraica es cuando esta última se da en su forma canónica. Así, la función canónica de suma de productos (o forma canónica disyuntiva)

F = A’BC’ + AB’C’ + AB’C + ABC’
nos indica que será 1 cuando lo sea uno de sus sumandos, lo que significa que tendrá por lo tanto cuatro combinaciones que lo serán (010 para A’BC’, 100 para AB’C’, 101 para AB’C y 110 para ABC’) siendo el resto de combinaciones 0. Con la función canónica de producto de sumas (o forma canónica conjuntiva) se puede razonar de forma análoga, pero en este caso observando que la función será 0 cuando lo sea uno de sus productos.

También es fácil obtener la tabla de verdad a partir de la función simplificada, pero no así a la inversa.

Numérica
La representación numérica es una forma simplificada de representar las expresiones canónicas. Si consideramos el criterio de sustituir una variable sin negar por un 1 y una negada por un 0, podremos representar el término, ya sea una suma o un producto, por un número decimal equivalente al valor binario de la combinación. Por ejemplo, los siguientes términos canónicos se representarán del siguiente modo (observe que se toma el orden de A a D como de mayor a menor peso):

AB’CD = 10112 = 1110
A’ + B + C’ + D’ = 01002 = 410
Para representar una función canónica en suma de productos utilizaremos el símbolo Σn (sigma) y en producto de sumas Πn (pi), donde n indicará el número de variables. Así, la representación numérica correspondiente a la tabla de verdad del punto anterior quedará como:

F = Σ3(2, 4, 5, 6) = Π3(0, 1, 3, 7)
Matemáticamente se demuestra, que para todo término i de una función, se cumple la siguiente ecuación:

F = [Σn(i)]' = Πn(2n-1-i )
A modo de ejemplo se puede utilizar esta igualdad para obtener el producto de sumas a partir de la suma de productos del ejemplo anterior:

F = Σ3(2, 4, 5, 6) = [Σ3(2, 4, 5, 6)]' ' = [Σ3(0, 1, 3, 7)]' = Π3(0, 4, 6, 7)

La representación gráfica es la que se utiliza en circuitos y esquemas electrónicos. En la siguiente figura se representan gráficamente dos funciones algebraicas, una con símbolos no normalizados, superior, y la otra con normalizados, inferior (véanse los símbolos de las puertas lógicas)


Representación gráfica de dos funciones lógicas[editar] Métodos de simplificación
Por simplificación de una función lógica se entiende la obtención de su mínima expresión. A la hora de implementar físicamente una función lógica se suele simplificar para reducir así la complejidad del circuito.

A continuación se indican los modos más usuales de simplificar una función lógica.

Algebraico
Para la simplificación por este método no sólo bastará con conocer todas las propiedades y teoremas del álgebra de Boole, además se debe desarrollar una cierta habilidad lógico-matemática que se adquiere fundamentalmente con la experiencia.

Como ejemplo se simplificará la siguiente función:

F = A’C’ + ABC + BC’ + A’B’C + A’BC
Observando cada uno de los sumando podemos ver que hay factores comunes en los sumandos 2º con 5º y 4º con 5º que conllevan simplificación:

F = A’C’ + BC’ + BC(A + A’) + A’C(B + B’)
Note que el término 5º se ha tomado dos veces, de acuerdo con la propiedad que diceque A + A´ = 1. Aplicando las propiedades del álgebra de Boole, queda

F = A’C’ + BC’ + BC + A’C
Repitiendo nuevamente el proceso,

F = A’( C’ + C) + B( C’ + C) = A’ + B
No siempre las funciones son tan fáciles de simplificar como la anterior. El método algebraico, por lo general, no resulta cómodo para los no expertos, a los cuales, una vez simplificada una ecuación le pueden quedar serias dudas de haber conseguido la máxima simplificación.

Gráfico de Karnaugh
Véase también Mapa de Karnaugh

Este método consiste en formar diagramas de 2n cuadros, siendo n el número de variables. Cada cuadro representa una de las diferentes combinaciones posibles y se disponen de tal forma que se puede pasar de un cuadro a otro en las direcciones horizontal o vertical, cambiando únicamente una variable, ya sea en forma negada o directa.

Este método se emplea fundamentalmente para simplificar funciones de hasta cuatro variables. Para un número superior utilizan otros métodos como el numérico. A continuación pueden observarse los diagramas, también llamados mapas de Karnaugh, para dos, tres y cuatro variables.


Mapas de Karnaugh para dos, tres y cuatro variablesEs una práctica común numerar cada celda con el número decimal correspondiente al término canónico que albergue, para facilitar el trabajo a la hora de plasmar una función canónica.

Para simplificar una función lógica por el método de Karnaugh se seguirán los siguientes pasos:

1º) Se dibuja el diagrama correspondiente al número de variables de la función a simplificar.

2º) Se coloca un 1 en los cuadros correspondientes a los términos canónicos que forman parte de la función.

3º) Se agrupan mediante lazos los unos de casillas adyacentes siguiendo estrictamente las siguientes reglas:

a) Dos casillas son adyacentes cuando se diferencian únicamente en el estado de una sola variable.
b) Cada lazo debe contener el mayor número de unos posible, siempre que dicho número sea potencia de dos (1, 2, 4, etc.)
c) Los lazos pueden quedar superpuestos y no importa que haya cuadrículas que pertenezcan a dos o más lazos diferentes.
d) Se debe tratar de conseguir el menor número de lazos con el mayor número de unos posible.
4º) La función simplificada tendrá tantos términos como lazos posea el diagrama. Cada término se obtiene eliminando la o las variables que cambien de estado en el mismo lazo.

A modo de ejemplo se realizan dos simplificaciones de una misma función a partir de sus dos formas canónicas:

F = Σ3(0,2,3,4,7) = Π3(1,2,6)
De acuerdo con los pasos vistos anteriormente, el diagrama de cada función quedará del siguiente modo:


Simplificación de una función de tres variablesLa función simplificada tendrá tres sumandos en un caso y dos productos en el otro. Si nos fijamos en el mapa correspondiente a la suma de productos, observamos que en el lazo 1 cambia la variable A (en la celda 0 es negada y en la 4 directa), en el lazo 2 es la C y en el lazo 3 vuelve a ser A. por lo tanto, la ecuación simplificada es:

F = B’C’ + A’B + BC
Razonando de modo similar en el mapa de productos de sumas, nos quedará lo siguiente:

F = (B + C’)(A’ + B’ + C)
Numérico de Quine-McCluskey
El algoritmo Quine-McCluskey permite la simplificación de funciones lógicas de cualquier número de variables y es el que se utiliza para diseñar aplicaciones informáticas en las que se necesite obtener funciones simplificadas.

A continuación se indican los pasos a seguir en este método a partir de un ejemplo.

1º) Se expresa la función a simplificar en su forma canónica de suma de productos.

Sea la siguiente función a simplificar:

F = S4 (0,1,2,3,5,9,11,12,13,15)
2º) Se forma una tabla con el valor decimal de la combinación, el estado de las variables y el índice (número de unos que contiene el estado de las variables).

Comb. Estado Índice
0 0000 0
1 0001 1
2 0010 1
3 0011 2
5 0101 2
9 1001 2
11 1011 3
12 1100 2
13 1101 3
15 1111 4

3º) Se agrupan las combinaciones cuyos estados difieren en una sola variable, sustituyéndola por un guión bajo (_). Las combinaciones utilizadas se marcan con un aspa (X). Hay que fijarse en las combinaciones cuya diferencia entre sus respectivos índices es la unidad.


Agrupación de las combinaciones4º) Se repite el proceso anterior las veces que sean necesarias y se van eliminando estados idénticos.


Nueva agrupación de las combinaciones5º) Se forma una tabla con las combinaciones finales y las no agrupadas. Se toman como filas las combinaciones finales y las no agrupadas y como columnas los valores decimales de dichas combinaciones. Cada celda que contenga el valor decimal de una combinación se marca con un aspa. A continuación nos fijamos en aquellas columnas con una sola aspa; sus combinaciones serán esenciales. Finalmente se toman aquellas combinaciones de los valores decimales no seleccionados, teniendo precaución de no tomar aquellas combinaciones cuyos valores decimales hayan sido ya tomados en otras combinaciones. La función simplificada final viene dada por las combinaciones esenciales y estas últimas.

Funciones incompletas
Hasta ahora todas las funciones estudiadas tienen definido un valor lógico, 0 ó 1, para cada una de las posibles combinaciones. Estas funciones se denominan completas o totalmente definidas. También existen funciones con una o varias combinaciones no definidas, llamadas funciones incompletas. Esta situación puede deberse por las dos causas siguientes:

1.Hay combinaciones de entrada que no existen, por lo que a la salida se le puede asignar indistintamente el valor 0 o el 1.
2.En ciertas combinaciones de entrada la salida del sistema lógico está inhibida, siendo por lo tanto su valor indiferente.
En la tabla de verdad de una función incompleta, los términos indiferentes se designan mediante una equis (X). En cuanto a la forma canónica se separan los términos definidos de los que no lo son (indicados mediante el símbolo φ).

A la hora de simplificar una función incompleta, los términos indiferentes servirán como “comodines” a la hora de tomar lo lazos, esto es, si nos interesa que sea un 1 porque así el lazo es mayor, lo tomaremos como 1, y en caso contrario como 0.

Minitérmino
Para una función booleana de n variables x1,...xn, un producto booleano en el que cada una de las n variables aparece una sola vez (negada o sin negar) es llamado minitérmino. Es decir, un minitérmino es una expresión lógica de n variables consistente únicamente en el operador conjunción lógica (AND) y el operador complemento o negación (NOT). Por ejemplo, abc, ab'c y abc' son ejemplos de minitérminos para una función booleana con las tres variables a, b y c.

Maxitermino
Un maxitérmino es una expresión lógica de n simbolos que consiste únicamente en la disyunción lógica y el operador complemento o negación. Los cuales están unidos por los operadores del algebra de boole (+ . ‘) Por ejemplo, los siguientes términos canónicos son maxitérminos:

1.a + b' + c
2.a' + b + c

COMPUERTAS LÓGICAS

Las computadoras digitales utilizan el sistema de números binarios, que tiene dos dígitos 0 y 1. Un dígito binario se denomina un bit. La información está representada en las computadoras digitales en grupos de bits. Utilizando diversas técnicas de codificación los grupos de bits pueden hacerse que representen no solamente números binarios sino también otros símbolos discretos cualesquiera, tales como dígitos decimales o letras de alfabeto. Utilizando arreglos binarios y diversas técnicas de codificación, los dígitos binarios o grupos de bits pueden utilizarse para desarrollar conjuntos completos de instrucciones para realizar diversos tipos de cálculos.

La información binaria se representa en un sistema digital por cantidades físicas denominadas señales, Las señales eléctricas tales como voltajes existen a través del sistema digital en cualquiera de dos valores reconocibles y representan una variable binaria igual a 1 o 0. Por ejemplo, un sistema digital particular puede emplear una señal de 3 volts para representar el binario "1" y 0.5 volts para el binario "0". La siguiente ilustración muestra un ejemplo de una señal binaria.

Como se muestra en la figura, cada valor binario tiene una desviación aceptable del valor nominal. La región intermedia entre las dos regiones permitidas se cruza solamente durante la transición de estado. Los terminales de entrada de un circuito digital aceptan señales binarias dentro de las tolerancias permitidas y los circuitos responden en los terminales de salida con señales binarias que caen dentro de las tolerancias permitidas.

La lógica binaria tiene que ver con variables binarias y con operaciones que toman un sentido lógico. La manipulación de información binaria se hace por circuitos lógicos que se denominan Compuertas.

Las compuertas son bloques del hardware que producen señales en binario 1 ó 0 cuando se satisfacen los requisitos de entrada lógica. Las diversas compuertas lógicas se encuentran comúnmente en sistemas de computadoras digitales. Cada compuerta tiene un símbolo gráfico diferente y su operación puede describirse por medio de una función algebraica. Las relaciones entrada - salida de las variables binarias para cada compuerta pueden representarse en forma tabular en una tabla de verdad.

A continuación se detallan los nombres, símbolos, gráficos, funciones algebraicas, y tablas de verdad de las compuertas más usadas.




Compuerta AND:

Cada compuerta tiene dos variables de entrada designadas por A y B y una salida binaria designada por x.
La compuerta AND produce la multiplicación lógica AND: esto es: la salida es 1 si la entrada A y la entrada B están ambas en el binario 1: de otra manera, la salida es 0.
Estas condiciones también son especificadas en la tabla de verdad para la compuerta AND. La tabla muestra que la salida x es 1 solamente cuando ambas entradas A y B están en 1.
El símbolo de operación algebraico de la función AND es el mismo que el símbolo de la multiplicación de la aritmética ordinaria (*).
Las compuertas AND pueden tener más de dos entradas y por definición, la salida es 1 si todas las entradas son 1.

Compuerta OR:

La compuerta OR produce la función sumadora, esto es, la salida es 1 si la entrada A o la entrada B o ambas entradas son 1; de otra manera, la salida es 0.
El símbolo algebraico de la función OR (+), es igual a la operación de aritmética de suma.
Las compuertas OR pueden tener más de dos entradas y por definición la salida es 1 si cualquier entrada es 1.

Compuerta NOT:

El circuito NOT es un inversor que invierte el nivel lógico de una señal binaria. Produce el NOT, o función complementaria. El símbolo algebraico utilizado para el complemento es una barra sobra el símbolo de la variable binaria.
Si la variable binaria posee un valor 0, la compuerta NOT cambia su estado al valor 1 y viceversa.
El círculo pequeño en la salida de un símbolo gráfico de un inversor designa un inversor lógico. Es decir cambia los valores binarios 1 a 0 y viceversa.

Compuerta Separador (yes):

Un símbolo triángulo por sí mismo designa un circuito separador, el cual no produce ninguna función lógica particular puesto que el valor binario de la salida es el mismo de la entrada.
Este circuito se utiliza simplemente para amplificación de la señal. Por ejemplo, un separador que utiliza 5 volt para el binario 1, producirá una salida de 5 volt cuando la entrada es 5 volt. Sin embargo, la corriente producida a la salida es muy superior a la corriente suministrada a la entrada de la misma.
De ésta manera, un separador puede excitar muchas otras compuertas que requieren una cantidad mayor de corriente que de otra manera no se encontraría en la pequeña cantidad de corriente aplicada a la entrada del separador.


Compuerta NAND:

Es el complemento de la función AND, como se indica por el símbolo gráfico, que consiste en una compuerta AND seguida por un pequeño círculo (quiere decir que invierte la señal).
La designación NAND se deriva de la abreviación NOT - AND. Una designación más adecuada habría sido AND invertido puesto que es la función AND la que se ha invertido.
Las compuertas NAND pueden tener más de dos entradas, y la salida es siempre el complemento de la función AND.


Compuerta NOR:

La compuerta NOR es el complemento de la compuerta OR y utiliza el símbolo de la compuerta OR seguido de un círculo pequeño (quiere decir que invierte la señal). Las compuertas NOR pueden tener más de dos entradas, y la salida es siempre el complemento de la función OR.

LOGICA COMBINATORIA

La lógica combinatoria es la lógica última y como tal puede ser un modelo simplificado del cómputo, usado en la teoría de computabilidad (el estudio de qué puede ser computado) y la teoría de la prueba (el estudio de qué se puede probar matemáticamente.)

Introducción

La teoría, a causa de su simplicidad, captura las características esenciales de la naturaleza del cómputo. La lógica combinatoria (LC) es el fundamento del cálculo lambda, al eliminar el último tipo de variable de éste: la variable lambda. En LC las expresiones lambda (usadas para permitir la abstracción funcional) son substituidas por un sistema limitado de combinadores, las funciones primitivas que no contienen ninguna variable libre (ni ligada). Es fácil transformar expresiones lambda en expresiones combinatorias, y puesto que la reducción de un combinador es más simple que la reducción lambda, LC se ha utilizado como la base para la puesta en práctica de algunos lenguajes de programación funcionales no-estrictos en software y hardware.

Sumario del cálculo lambda

El cálculo lambda se refiere a objetos llamados lambda-términos, que son cadenas de símbolos de una de las formas siguientes:

v
λv.E1
(E1 E2)

donde v es un nombre de variable tomado de un conjunto infinito predefinido de nombres de variables, y E1 y E2 son lambda-términos. Los términos de la forma λv.E1 son llamadas abstracciones. La variable ν se llama el parámetro formal de la abstracción, y E1 es el cuerpo de la abstracción.

El término λv.E1 representa la función que, si es aplicada a un argumento, liga el parámetro formal v al argumento y entonces computa el valor resultante de E1--- esto es, retorna E1, con cada ocurrencia de ν substituido por el argumento.

Los términos de la forma (E1 E2) son llamados aplicaciones. Las aplicaciones modelan la invocación o ejecución de una función: La función representada por E1 es invocada, con E2 como su argumento, y se computa el resultado. Si E1 (a veces llamado el aplicando) es una abstracción, el término puede ser reducido: E2, el argumento, se puede substituir en el cuerpo de E1 en lugar del parámetro formal de E1, y el resultado es un nuevo término lambda que es equivalente al antiguo. Si un término lambda no contiene ningún subtérmino de la forma (λv.E1 E2) entonces no puede ser reducido, y se dice que está en forma normal.

La expresión E[a/v] representa el resultado de tomar el término E y substituyendo todas las ocurrencias libres de v por el a. Escribimos así

(λv.E a) ⇒ E[a/v]

por convención, tomamos (b c d... z) como abreviatura para (... (((a b) c) d)... z). (Regla de asociación por izquierda).

La motivación para esta definición de la reducción es que captura el comportamiento esencial de todas las funciones matemáticas. Por ejemplo, considérese la función que computa el cuadrado de un número. Se puede escribir el cuadrado de x es x*x (usando "*" para indicar la multiplicación.) x aquí es el parámetro formal de la función. Para evaluar el cuadrado para un argumento particular, digamos 3, lo insertamos en la definición en lugar del parámetro formal:

El cuadrado de 3 es 3*3

para evaluar la expresión que resulta 3*3, tendríamos que recurrir a nuestro conocimiento de la multiplicación y del número 3. Puesto que cualquier cómputo es simplemente una composición de la evaluación de funciones adecuadas con argumentos primitivos adecuados, este principio simple de substitución es suficiente para capturar el mecanismo esencial del cómputo. Por otra parte, en el cálculo lambda, nociones tales como '3' y '*' puede ser representado sin ninguna necesidad de operadores primitivos externamente definidos o de constantes. Es posible identificar los términos que en el cálculo lambda, cuando están interpretados convenientemente, se comportan como el número 3 y el operador de la multiplicación.

El cálculo lambda es computacionalmente equivalente en poder a muchos otros modelos plausibles para el cómputo (máquinas de Turing incluidas); es decir, cualquier cálculo que se pueda lograr en cualesquiera de estos otros modelos se puede expresar en el cálculo lambda, y viceversa. Según la tesis de Church-Turing, ambos modelos pueden expresar cualquier cómputo posible. Quizás parezca sorprendente que el cálculo lambda pueda representar cualquier cómputo concebible usando solamente las nociones simples de abstracción funcional y aplicación basado en la substitución textual simple de términos por variables. Pero aún más notable es que incluso la abstracción no es requerible. La Lógica Combinatoria es un modelo del cómputo equivalente al cálculo lambda, pero sin la abstracción.

Cálculos Combinatorios

Puesto que la abstracción es la única manera de fabricar funciones en el cálculo lambda, algo debe sustituirlo en el cálculo combinatorio. En vez de la abstracción, el cálculo combinatorio proporciona un conjunto limitado de funciones primitivas y de las cuales las otras funciones pueden ser construidas.

Términos combinatorios

Un término combinatorio tiene una de las formas siguientes:

V
P
(E1 E2)
donde V es una variable, P es una de las funciones primitivas, E1 y E2 son términos combinatorios. Las funciones primitivas mismas son combinadores, o funciones que no contienen ninguna variable libre.

Ejemplos de combinadores

El ejemplo más simple de un combinador es I, el combinator identidad, definido por

(I x) = x
para todos los términos x. otro combinator simple es K, que produce funciones constantes: (K x) es la función que, para cualquier argumento, devuelve x, así que decimos

((K x) y) = x
para todos los términos x y y. O, siguiendo la misma convención para el uso múltiple que en el cálculo lambda,

(K x y) = x
Un tercer combinador es S, que es una versión generalizada de la aplicación:

(S x y z) = (x z (y z))
S aplica x a y después de substituir primero a z en cada uno de ellos.

Dados S y K, aun el mismo I es innecesario, puesto que puede ser construido por los otros dos:

((S K K) x)
= (S K K x)
= (K x (K x))
= x

para cualquier término x. Nótese que aunque ((S K K) x) = (I x) para cualquier x, (S K K) en sí mismo no es igual a I. Decimos que los términos son extensionalmente iguales.

La igualdad extensional

La igualdad extensional captura la noción matemática de la igualdad de funciones: que dos funciones son 'iguales' si producen siempre los mismos resultados para las mismos argumentos. En contraste, los términos mismos capturan la noción de igualdad intensional de funciones: que dos funciones son 'iguales' solamente si tienen implementaciones idénticas. Hay muchas maneras de implementar una función identidad; (S K K) y I están entre estas maneras. (S K S) es otro. Utilizaremos la palabra equivalente para indicar la igualdad extensional, reservando igual para los términos combinatorios idénticos.

Un combinador más interesante es el combinador de punto fijo o combinator Y, que se puede utilizar para implementar la recursión.

Completitud de la base S-K

Es, quizás, un hecho asombroso que S y K se puedan componer para producir los combinadores que son extensionalmente iguales a cualquier término lambda, y por lo tanto, por la tesis de Church, a cualquier función computable. La prueba es presentar una transformación, T[ ], que convierte un término arbitrario lambda en un combinador equivalente. T[ ] puede ser definido como sigue:

T[V] ⇒ V T[(E1 E2)] ⇒ (T[E1] T[E2]) T[λx.E] ⇒ (K E) (si x no está libre en E) T[λx.x] ⇒ I T[λx.λy.E] ⇒ T[λx.T[λy.E]] (si x está libre en E) T[λx.(E1 E2)] ⇒ (S T[λx.E1] T[λx.E2])

Conversión de un término lambda a un término combinatorio equivalente

Por ejemplo, convertiremos el término lambda λx.λy.(y x)) a un combinador:

T[λx.λy.(y x)]
= T[λx.T[λy.(y x)] ] (por 5)
= T[λx.(S T[λy.y] T[λy.x])] (por 6)
= T[λx.(S I T[λy.x])] (por 4)
= T[λx.(S I (K x))] (por 3)
= (S T[λx.(S I)] T[λx.(K x)]) (por 6)
= (S (K (S I)) T[λx.(K x)]) (por 3)
= (S (K (S I)) (S T[λx.K] T[λx.x])) (por 6)
= (S (K (S I)) (S (K K) T[λx.x])) (por 3)
= (S (K (S I)) (S (K K) I)) (por 4)

si aplicamos este combinator a cualesquiera dos términos x y y, reduce como sigue:

(S (K (S I)) (S (K K) I) x y)
= (K (S I) x (S (K K) I x) y)
= (S I (S (K K) I x) y)
= (I y (S (K K) I x y))
= (y (S (K K) I x y))
= (y (K K x (I x) y))
= (y (K (I x) y))
= (y (I x))
= (y x)

La representación combinatoria, (S (K (S I)) (S (K K) I)) es mucho más larga que la representación como término lambdaλx.λy.(y x). Esto es típico. En general, la construcción de T[ ] puede ampliar un término lambda de la longitud n a un término combinatorio de la longitud Θ(3n).

Explicación de la transformación T[ ]

La transformación T[ ] es motivada por un deseo de eliminar la abstracción. Dos casos especiales, reglas 3 y 4, son triviales: λx.x es claramente equivalente a I, y λx.E es claramente equivalente a (K E) si x no aparece libre en E.

Las primeras dos reglas son también simples: Las variables se convierten en sí mismas, y las aplicaciones permitidas en términos combinatorios, son convertidas los combinadores simplemente convirtiendo el aplicando y el argumento a combinadores.

Son las reglas 5 y 6 las que tienen interés. La regla 5 dice simplemente esto: para convertir una abstracción compleja a un combinador, debemos primero convertir su cuerpo a un combinator, y después eliminamos la abstracción. La regla 6 elimina realmente la abstracción.

λx.(E1E2) es una función que toma un argumento, digamos a, y lo substituye en el término lambda (E1 E2) en lugar de x, dando (E1 E2)[a/x]. Pero substituir a en (E1 E2) en lugar de x es precisamente igual que sustituirlo en E1 y E2, así que

(E1 E2)[a/x] = (E1[a/x] E2[a/x])
(λx.(E1 E2) a) = ((λx.E1 a) (λx.E2 a))
= (S λx.E1 λx.E2 a)
= ((S λx.E1 λx.E2) a)

Por igualdad extensional,

λx.(E1 E2) = (S λx.E1 λx.E2)

Por lo tanto, para encontrar un combinador equivalente a λx.(E1 E2), es suficiente encontrar un combinador equivalente a (S λx.E1 λx.E2), y

(S T[λx.E1] T[λx.E2])

evidentemente cumple el objetivo. E1 y E2 contienen cada uno estrictamente menos aplicaciones que (E1 E2), así que la repetición debe terminar en un término lambda sin aplicación ninguna-ni una variable, ni un término de la forma λx.E.

Simplificaciones de la transformación

η-reducción
Los combinador

es generados por la transformación T[ ] pueden ser hechos más pequeños si consideramos la regla de η-reducción:

T[λx.(E x)] = T[E] (si x no está libre en E)
[[λx.(E x)]] es la función que toma un argumento, x, y aplica la función E a él; esto es extensionalmente igual a la función E misma. Es por lo tanto suficiente convertir E a la forma combinatoria.

Tomando esta simplificación en cuenta, el ejemplo arriba se convierte en:

T[λx.λy.(y x)]
= ...
= (S (K (S I)) T[λx.(K x)])
= (S (K (S I)) K) (por η-reducción)

Este combinador es equivalente al anterior, más largo:

(S (K (S I)) K x y)
= (K (S I) x (K x) y)
= (S I (K x) y)
= (I y (K x y))
= (y (K x y))
= (y x)

semejantemente, la versión original de la transformación T[ ] transformó la función identidad λf.λx.(f x) en (S (S (K S) (S (K K) I)) (K I)). Con la regla de η-reducción, λf.λx.(f x) se transformó en I.

los combinadores B, C de Curry

Los combinadores S, K se encuentran ya en Schönfinkel (aunque el símbolo C se usaba por el actual K) Curry introdujo el uso de B, C, W (y K), ya antes de su tesis doctoral de 1930. En Lógica combinatoria T. I, Se ha vuelto a S, K pero se muestra, (vía algoritmos de Markov) que el uso de B y C pueden simplificar muchas reducciones. Esto parece haberse utilizado mucho después por David Turner, cuyo nombre ha quedado ligado a su uso computacional. Se introducen dos nuevos combinadores:

(C a b c) = (a c b)
(B a b c) = (a (b c))

Usando estos combinadores, podemos extender las reglas para la transformación como sigue:

1.T[V] ⇒ V
2.T[(E1 E2)] ⇒ (T[E1] T[E2])
3.T[λx.E] ⇒ (K E) (if xno está libre en E)
4.T[λx.x] ⇒ I
5.T[λx.λy.E] ⇒ T[λx.T[λy.E]] (si x está libre en E)
6.T[λx.(E1 E2)] ⇒ (S T[λx.E1] T[λx.E2]) (si x está libre tanto en E1 como en E2)
7.T[λx.(E1 E2)] ⇒ (C T[λx.E1] E2) (si x está libre en E1 pero no en E2)
8.T[λx.(E1 E2)] ⇒ (B E1 T[λx.E2]) (si x está libre en E2 pero no en E1)

Usando los combinadores B y C, la transformación de λx.λy.(y x) se ve así:

T[λx.λy.(y x)]
= T[λx.T[λy.(y x)]]
= T[λx.(C T[λy.y] x)] (por la regla 7)
= T[λx.(C I x)]
= (C I) (η-reducción)
= C*(notación canónica tradicional: X* = XI)
= I'(notación canónica tradicional: X' = CX)
Y, ciertamente, (C I x y) se reduce a (y x):

(C I x y)
= (I y x)
= (y x)

La motivación aquí es que B y C son versiones limitadas de S. En tanto S toma un valor y lo substituye tanto en el aplicando como en el argumento antes de efectuar la aplicación, C realiza la substitución sólo en el aplicando, y B sólo en el argumento.

Conversión reversa

La conversión L[ ] de términos combinatorios a términos lambda es trivial:

L[I] = λx.x
L[K] = λx.λy.x
L[C] = λx.λy.λz.(x z y)
L[B] = λx.λy.λz.(x (y z))
L[S] = λx.λy.λz.(x z (y z))
L[(E1 E2)] = (L[E1] L[E2])

Nótese, sin embargo, que esta transformación no es la transformación inversa de ninguna de las versiones de T[ ] que se han visto.

Indecidibilidad del Cálculo Combinatorio

Es indecidible cuándo un término combinatorio general tiene forma normal; cuando dos términos combinatorios son equivalentes, etc. Esto es equivalente a la indecidibilidad de los correspondientes problemas para términos lambda. No obstante, una prueba directa es como sigue:

Primero, obsérvese que el término

A = (S I I (S I I))

no tiene forma normal, porque se reduce a sí mismo en tres pasos, como sigue:

(S I I (S I I))
= (I (S I I) (I (S I I)))
= (S I I (I (S I I)))
= (S I I (S I I))

y claramente ningún otro orden de reducción puede hacer la expresión más corta.

Ahora, supongamos que N fuera un combinador para detectar formas normales, tal que

(N x) ⇒ T, si x tiene forma normal
F, en caso contrario.
(Donde T y F son las transformaciones de las definiciones convencionales en cálculo lambda de verdadero y falso, λx.λy.x y λx.λy.y. Las versiones combinatorias tienen T = K y F = (K I) = 0 = K'.)

Ahora sea

Z = (C (C (B N (S I I)) A) I)

y consideremos el término (S I I Z). Tiene (S I I Z) una forma normal? La tiene si y sólo si:

(S I I Z)
= (I Z (I Z))
= (Z (I Z))
= (Z Z)
= (C (C (B N (S I I)) A) I Z) (definición de Z)
= (C (B N (S I I)) A Z I)
= (B N (S I I) Z A I)
= (N (S I I Z) A I)

Ahora debemos aplicar N a (S I I Z). O bien (S I I Z) tiene una forma normal, o no la tiene. Si tuviera forma normal, entonces se reduce como sigue:

(N (S I I Z) A I)
= (K A I) (definición de N)
= A

pero A no tiene una forma normal, por tanto tenemos una contradicción. Pero si (S I I Z) no tiene una forma normal, se reduce como sigue:

(N (S I I Z) A I)
= (K I A I) (definición de N)
= (I I)
I

operaciones lógicas

Una proposición o enunciado es una oración que puede ser falsa o verdadera pero no ambas a la vez, La proposición es un elemento fundamental de la lógica matemática. A continuación se tienen algunos ejemplos de proposiciones válidas y no válidas, y se explica el porqué algunos enunciados no son proposiciones; Las proposiciones se indican por medio de una letra minúscula, dos puntos y la proposición propiamente dicha.
Ejemplo:

p: La tierra es plana.
q: −17 + 38 = 21
r: x > y-9
s: El Morelia será campeón en la presente temporada de Fut-Bol.
t: Hola ¿como estas?
w: Lava el coche por favor.

Los incisos p y q sabemos que pueden tomar un valor de falso o verdadero, por lo tanto son proposiciones validas. El inciso r también es una proposición valida, aunque el valor de falso o verdadero depende del valor asignado a las variables x y y en determinado momento. La proposición del inciso s también esta perfectamente expresada aunque para decir si es falsa o verdadera se tendría que esperar a que terminara la temporada de fut-boll. Sin embargo los enunciados t y w no son válidos, ya que no pueden tomar un valor de falso o verdadero, uno de ellos es un saludo y el otro es una orden.
Conectivos lógicos y proposiciones compuestas

Existen conectores u operadores lógicos que permiten formar proposiciones compuestas (formadas por varias proposiciones).
Los operadores o conectores básicos son:

Operador and (y)

Se utiliza para conectar dos proposiciones que se deben cumplir para que se pueda obtener un resultado verdadero. Su símbolo es: ∧
Ejemplo:
Sea el siguiente enunciado
“El coche enciende cuando tiene gasolina en el tanque y tiene corriente la batería”

Sean:

p: El coche enciende.
q: Tiene gasolina el tanque.
r: Tiene corriente la batería.

De tal manera que la representación del enunciado anterior usando simbología lógica es como sigue:
q ∧ r

Su tabla de verdad es como sigue:

q r q ∧ r
V V V
V F F
F V F
F F F

En la tabla anterior el valor de q= v significa que el tanque tiene gasolina, r= v significa que la batería tiene corriente y p = q ∧ r=v significa que el coche puede encender. Se puede notar que si q o r son falso implica que el auto no tiene gasolina y que por lo tanto no puede encender.

Operador Or (o)

Con este operador se obtiene un resultado verdadero cuando alguna de las proposiciones es verdadera. Se indica por medio de los siguientes símbolos: { ∨,+,∪ }. Se conoce como la suma lógica.

Ejemplo:
Sea el siguiente enunciado:

“Una persona puede entrar al cine si compra su boleto u obtiene un pase”

p: Entra al cine.
q: Compra su boleto.
r: Obtiene un pase.

q r q ∨ r
V V V
V F V
F V V
F F F

Operador Not (no)

Su función es negar la proposición. Esto significa que sí alguna proposición es verdadera y se le aplica el operador not se obtendrá su complemento o negación (falso). Este operador se indica por medio de los siguientes símbolos: {~, ¬,- }.
Ejemplo:
p ¬p
V F
F V


Además de los operadores básicos (and, or y not) existe el operador xor, cuyo funcionamiento es semejante al operador or con la diferencia en que su resultado es verdadero solamente si una de las proposiciones es cierta, cuando ambas son verdaderas el resultado es falso. En este momento ya se pueden representar con notación lógica enunciados más complejos.

Ejemplo:
p: Hoy es domingo.
q: Tengo que estudiar teorías del aprendizaje.
r: Aprobaré el curso.

El enunciado: “Hoy es domingo y tengo que estudiar teorías de aprendizaje o no aprobaré el curso”.

Se puede representar simbólicamente de la siguiente manera:
p ∧ q ∨ r
Por otro lado con ayuda de estos operadores básicos se pueden formar los operadores compuestos Nand (combinación de los operadores Not y And), Nor (combina operadores Not y Or) y Xnor (resultado de Xor y Not).

Proposiciones condicionales

Una proposición condicional, es aquella que está formada por dos proposiciones simples o compuesta p y q. La cual se indica de la siguiente manera:

p → q Se lee “Si p entonces q”

Ejemplo:

El candidato del PRI dice “Si salgo electo presidente de la República recibirán un 50% de aumento en su sueldo el próximo año”. Una declaración como esta se conoce como condicional. Su tabla de verdad es la siguiente:

Sean
p: Salió electo Presidente de la República.
q: Recibirán un 50% de aumento en su sueldo el próximo año.
De tal manera que el enunciado se puede expresar de las siguiente manera.

p → q
Su tabla de verdad queda de la siguiente manera:

q r q → r
V V V
V F F
F V V
F F V



La interpretación de los resultados de la tabla es la siguiente:
Considere que se desea analizar si el candidato presidencial mintió con la afirmación del enunciado anterior. Cuando p= v; significa que salió electo, q= v y recibieron un aumento de 50% en su sueldo, por lo tanto p → q = v significa que el candidato dijo la verdad en su campaña. Cuando p=v y q=f significa que p → q = f; el candidato mintió, ya que salió electo y no se incrementaron los salarios. Cuando p=f y q=v significa que aunque no salió electo hubo un aumento del 50% en su salario, que posiblemente fue ajeno al candidato presidencial y por lo tanto; tampoco mintió de tal forma que p → q = v.

proposiciones simples

En matemáticas, una proposición simple es un enunciado del cual se puede afirmar que es verdadero o que es falso pero no ambos a la vez.

Ejemplos:
-La caja de madera. (caja=madera)
-Está lloviendo......... (tiempo=lloviendo)

Las proposiciones compuestas son aquellas que se forman por unión de proposiciones simples mediante los conectivos lógicos.

Ejemplo: La caja es de madera y está lloviendo
(caja=madera) AND (tiempo=lloviendo)
En lógica proposicional, aquella proposición que no puede descomponerse en otras. También se la denomina proposición atómica. Se denominan variables o letras proposicionales a los símbolos que las representan.