LOGICA DISCRETA

TAUTOLOGIA

• "Tautología (del griego = discurso o razonar autoexplicativo)"




• "Se entiende por tautología aquella proposición cuya tabla de verdad da siempre el valor de verdad V en todos los casos posibles de los valores de verdad (V, F) de cada una de las proposiciones que la integran."




• "Tautología: en todos los casos la forma del argumento ofrece un resultado verdadero, por lo que el argumento es válido."




• "En lógica lo tautológico se convierte en la esencia del discurso deductivo, o mejor dicho de la inferencia deductiva."




• "La tabla de verdad del esquema de inferencia que enlaza el antecedente y el consecuente da siempre el valor de verdad V, y en todos los casos posibles de los valores de verdad de las proposiciones que la integran, es una tautología. Su validez lógica consiste precisamente en que no puede darse el caso de que siendo verdad el antecedente, no lo sea el consecuente."




• "Los argumentos deductivos válidos son, por definición, tautologías."




• "Algunas tautologías pueden ser consideradas como leyes lógicas, es decir como modelos aplicables para las inferencias"




• "La tautología se trata de una proposición que necesariamente es verdadera (A es = A), con independencia de que represente un hecho real o no. De este modo se acepta "a priori" (= previo a la experiencia) y sirve de premisa obvia. (Wittgenstein)"




• En un sistema de CALCULO AXIOMATICO, se llaman AXIOMAS a las leyes lógicas que sirven de base para derivar todo su contenido. Estos AXIOMAS son tautologías. El cálculo lógico así puede utilizarse como demostración argumentativa




• Igual que la lógica, las matemáticas pueden ser consideradas como una ciencia de hacer tautologías particularmente elaboradas de una forma rigurosa.




• Un teorema matemático es un ejemplo de tautología.

OPERACIONES LOGICAS

más conocida por su nombre en inglés AND, realiza la función booleana de producto lógico. Su símbolo es un punto (•), aunque se suele omitir. Así, el producto lógico de las variables A y B se indica como AB, y se lee A y B o simplemente A por B. La ecuación característica que describe el comportamiento de la puerta AND es:

Su tabla de verdad es la siguiente:

Tabla de verdad puerta AND

Entrada A Entrada B Salida AB 0 0 0 0 1 0 1 0 0 1 1 1

Su definición se puede dar, como una compuerta que entrega un 1 lógico sólo si todas las entradas están a nivel alto 1. • La puerta lógica O, más conocida por su nombre en inglés OR, realiza la operación de suma lógica. La ecuación característica que describe el comportamiento de la puerta OR es:

Su tabla de verdad es la siguiente:

Tabla de verdad puerta OR

Entrada A Entrada B Salida A + B 0 0 0 0 1 1 1 0 1 1 1 1

Podemos definir la puerta O como aquella que proporciona a su salida un 1 lógico si al menos una de sus entradas está a 1.

• La puerta lógica O-exclusiva, más conocida por su nombre en inglés XOR, realiza la función booleana A’B+AB’. Su símbolo es el más (+) inscrito en un círculo. En la figura de la derecha pueden observarse sus símbolos en electrónica. La ecuación característica que describe el comportamiento de la puerta XOR es:

Su tabla de verdad es la siguiente: Tabla de verdad puerta XOR Entrada A Entrada B Salida A B

0 0 0 0 1 1 1 0 1 1 1 0 Se puede definir esta puerta como aquella que da por resultado uno, cuando los valores en las entradas son distintos. ej: 1 y 0, 0 y 1 (en una compuerta de dos entradas). Si la puerta tuviese tres o más entradas, la XOR tomaría la función de suma de paridad, cuenta el número de unos a la entrada y si son un número impar, pone un 1 a la salida, para que el número de unos pase a ser par. Esto es así porque la operación XOR es asociativa, para tres entradas escribiríamos: a (b c) o bien (a b) c. Su tabla de verdad sería: XOR de tres entradas Entrada A Entrada B Entrada C Salida A B C 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

• La puerta lógica NO (NOT en inglés) realiza la función booleana de inversión o negación de una variable lógica. La ecuación característica que describe el comportamiento de la puerta NOT es:

Su tabla de verdad es la siguiente: Tabla de verdad puerta NOT Entrada A Salida

0 1 1 0 Se puede definir como una puerta que proporciona el estado inverso del que esté en su entrada.

CONVERSIONES DE LOS DIFERENTES SISTEMAS DE NUMERACION

CONVERSIÓN DE UN NUMERO DECIMAL A BINARIO

Para esta transformación es necesario tener en cuenta los pasos que mostraremos en el siguiente ejemplo: Transformemos el numero 42 a numero binario

1. Dividimos el numero 42 entre 2
2. Dividimos el cociente obtenido por 2 y repetimos el mismo procedimiento hasta que el cociente sea 1.
3. El numero binario lo formamos tomando el primer dígito el ultimo cociente, seguidos por los residuos obtenidos en cada división, seleccionándolos de derecha a izquierda, como se muestra en el siguiente esquema.

CONVERSIÓN DE UN NUMERO DECIMAL FRACCIONARIO A UN NUMERO BINARIO

1. la parte entera se transforma de igual forma que el ejemplo anterior.
2. La parte fraccionaria de la siguiente manera:


Multiplicamos por el numero 2 y tomamos la parte entera del producto que ira formando el numero binario correspondiente

Tomamos nuevamente la parte entera del producto, y la parte fraccionaria la multiplicamos sucesivamente por 2 hasta llegar a 0

Tomamos nuevamente la parte entera, y como la parte fraccionaria es 0, indica que se ha terminado el proceso. El numero binario correspondiente a la parte decimal será la unión de todas las partes enteras, tomadas de las multiplicaciones sucesivas realizadas durante el transcurso del proceso , en donde el primer dígito binario corresponde a la primera parte entera , el segundo dígito a la segunda parte entera , y así sucesivamente hasta llegar al último .Luego tomamos el numero binario , correspondiente a la parte entera , y el numero binario , correspondiente a la parte fraccionaria y lo unimos en un solo numero binario correspondiente a el numero decimal.

MAPAS DE KARNAVGH

Cuando se tiene una función lógica con su tabla de verdad y se desea implementar esa función de la manera más económica posible se utiliza este método.

Ejemplo: Se tiene la siguiente tabla de verdad para tres variables.

Se desarrolla la función lógica basada en ella. (primera forma canónica). Ver que en la fórmula se incluyen solamente las variables (A, B, C) cuando F cuando es igual a "1".

Si A en la tabla de verdad es "0" se pone A, si B = "1" se pone B, Si C = "0" se pone C, etc.

MAXITERMINOS Y MINITERMINOS.

Ejemplo: Expresar la función F = A+B’C en una suma de miniterminos.

F= A+B’C F(A,B,C) A= A(B+B’) = AB+AB’

= AB(C+C’) + AB’(C+C’)

= ABC + ABC’ + AB’C +AB’C’

B’C = B’C (A+A’)

= AB’C + A’B’C

F = ABC+ABC’+AB’C+AB’C’+AB’C+A’B’C F = A’B’C+AB’C’ +AB’C+ABC’+ABC F = m1+ m4+m5+ m6+ m7 F(A,B,C)=SUM(1,4,5,6,7)

La sumatoria representa al operador OR que opera en los términos y números siguientes son los minitérminos de la función.

COMPUERTAS LOGICAS

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.

CIRCUITOS LOGICOS CON COMPUERTAS

el sistema matematico llamado algebra pooleana en honor del matematico george boole que especifica la operacion de cada compuerta.
El algenra pooleana tambien se utiliza para describir la interconexion de compuertas digitales y para transformar diagramas de circuitos en expresiones algebraicas.

Lògica Binaria

Tiene que ver con variables que asumen 2 valores discretos y con operaciones que asumen un significado logico los 2 valores que toman las variables son 1 y 0. Y su nombre es designado por letras del alfabeto .
Existen 3 operaciones logicas asociadas con los valores binarios llamados:
AND
OR
NOT

TABLAS DE VERDAD

La interpretación de una fórmula queda completamente determinado por los valores de verdad de las variables proposicionales (VP) que dicha interpretación asigna a las letras enunciativas que aparecen en esa fórmula. Una vez que conocemos el valor de verdad que la interpretación asigna a cada VP y tenemos presentes las definiciones de los conectivos resulta fácil determinar el valor de verdad que le corresponde a la fórmula completa.
El procedimiento de determinación requiere ir por pasos, estableciéndolos valores correspondientes a los diferentes niveles de subfórmulas (indicados por los paréntesis) hasta alcanzar el nivel de la fórmula completa. Así obtenemos una tabla de verdad para la fórmula en cuestión.

Una tabla de verdad establece las diferentes posibles combinaciones de valores de verdad de las VP de una fórmula y determina los valores correspondientes a esa fórmula para cada una de esas combinaciones, es decir, cada renglón será una interpretación posible para esa fórmula a partir de las diferentes combinaciones de valores de verdad para las VP que la compongan.

Cada tabla requiere un número de interpretaciones que se corresponde con el número de combinaciones de valores de verdad para las VP que aparezcan en la fórmula. El criterio para determinar cuantas interpretaciones posibles tiene una fórmula depende del número de VP distintas que aparezcan en ella. Dado que según el Principio de Bivalencia que rige la Lógica Clásica una fórmula sólo puede tener dos valores de verdad (a saber, V o F) para una fórmula que contenga n VP, ese número es 2n. Así la tabla de verdad de una fórmula que tenga 2 variables tendrá 22 = 4 renglones, una que tenga 3, tendrá 23 = 8, una que tenga 4 24 = 16 y así sucesivamente.

TABLAS DE VERDAD

ALGEBRA DE BOOLE

INTRODUCCION AL ALGEBRA DE BOOLE

Muchos componentes utilizados en sistemas de control, como contactores y relés, presentan dos estados claramente diferenciados (abierto o cerrado, conduce o no conduce). A este tipo de componentes se les denomina componentes todo o nada o también componentes lógicos.

Para estudiar de forma sistemática el comportamiento de estos elementos, se representan los dos estados por los símbolos 1 y 0 (0 abierto, 1 cerrado). De esta forma podemos utilizar una serie de leyes y propiedades comunes con independencia del componente en sí; da igual que sea una puerta lógica, un relé, un transistor, etc...

Atendiendo a este criterio, todos los elementos del tipo todo o nada son representables por una variable lógica, entendiendo como tal aquella que sólo puede tomar los valores 0 y 1. El conjunto de leyes y reglas de operación de variables lógicas se denomina álgebra de Boole, ya que fue George Boole el que desarrolló las bases de la lógica matemática.

Operaciones lógicas básicas

Sea un conjunto formado por sólo dos elementos que designaremos por 0 y 1. Llamaremos variables lógicas a las que toman sólo los valores del conjunto, es decir 0 o 1.
En dicho conjunto se definen tres operaciones básicas:

SUMA LOGICA:

Denominada también operación "O" (OR). Esta operación responde a la siguiente tabla:

a b a+b
0 0 0
0 1 1
1 0 1
1 1 1

PRODUCTO LOGICO:

Denominada también operación "Y" (AND). Esta operación responde a la siguiente tabla:

a b a*b
0 0 0
0 1 0
1 0 0
1 1 1


NEGACION LOGICA:

Denominada también operación "N" (NOT). Esta operación responde a la siguiente tabla:

a a'
0 1
1 0


Propiedades del álgebra de Boole

Las propiedades del conjunto en el que se han definido las operaciones (+, *, ') son las siguientes:

PROPIEDAD CONMUTATIVA:

De la suma: a+b = b+a
Del producto: a*b = b*a

PROPIEDAD ASOCIATIVA:

De la suma: (a+b)+c = a+(b+c) = a+b+c
Del producto: (a*b)*c = a*(b*c) = a*b*c

LEYES DE IDEMPOTENCIA:

De la suma: a+a = a ; a+a' = 1
Del producto: a*a = a ; a*a' = 0

PROPIEDAD DISTRIBUTIVA:

De la suma respecto al producto: a*(b+c) = (a*b) + (a*c)
Del producto respecto a la suma: a + (b*c) = (a+b) * (a+c)

LEYES DE DE MORGAN:

(a+b+c)' = a'*b'*c'
(a*b*c)' = a'+b'+c'

Otras operaciones lógicas

A partir de las operaciones lógicas básicas se pueden realizar otras operaciones booleanas, las cuales son:

NAND, cuya tabla correspondiente es:

a b (a*b)'
0 0 1
0 1 1
1 0 1
1 1 0


NOR, cuya tabla correspondiente es:

a b (a+b)'
0 0 1
0 1 0
1 0 0
1 1 0


XOR, también llamada función OR-EXCLUSIVA. Responde a la tabla:

a b a(+)b
0 0 0
0 1 1
1 0 1
1 1 0


Compuertas lógicas




Toda puerta lógica consta de 1 o más entradas y 1 o 2 salidas (puede darse el caso de proporcionarse la salida y su negada). En todos los símbolos las entradas se encuentran a la izquierda y las salidas a la derecha.

Estas puertas las podemos encontrar empaquetadas dentro de distintos circuitos integrados. Por ejemplo, para la familia lógica TTL tenemos las siguientes referencias:

54/74 (LS) 00 Cuádruple puerta NAND de dos entradas
54/74 (LS) 02 Cuádruple puerta NOR de dos entradas
54/74 (LS) 04 Séxtuple puerta NOT
54/74 (LS) 08 Cuádruple puerta AND de dos entradas
54/74 (LS) 10 Triple puerta NAND de tres entradas
54/74 (LS) 11 Triple puerta AND de tres entradas
54/74 (LS) 20 Doble puerta NAND de cuatro entradas
54/74 (LS) 21 Doble puerta AND de cuatro entradas
54/74 (LS) 27 Triple puerta NOR de tres entradas
54/74 (LS) 30 Puerta NAND de ocho entradas
54/74 (LS) 32 Cuádruple puerta OR de dos entradas

Las puertas lógicas más frecuentes, baratas, y fáciles de encontrar son las NAND. Debido a esto se suelen implementar circuitos digitales con el mayor número de dichas puertas.
Hay que mencionar en este punto que los niveles de tensión que se corresponden con los niveles lógicos 1 y 0 dependen de la familia lógica empleada. De momento basta saber que la familia TTL se alimenta con +5V, por lo que los niveles de tensión se corresponderán con +5V para el 1 lógico y 0V para el 0 lógico (idealmente hablando, claro).

Funciones lógicas

La aplicación más directa de las puertas lógicas es la combinación entre dos o más de ellas para formar circuitos lógicos que responden a funciones lógicas. Una función lógica hace que una o más salidas tengan un determinado valor para un valor determinado de las entradas.

Supongamos que tenemos dos entradas, A y B, y una salida F. Vamos a hacer que la salida sea 1 lógico cuando A y B tengan el mismo valor, siendo 0 la salida si A y B son diferentes.

En primer lugar veamos los valores de A y B que hacen 1 la función:

A = 1 y B = 1
A = 0 y B = 0

Es decir, podemos suponer dos funciones de respuesta para cada caso:

F1 = A*B (A y B a 1 hacen F1 1)
F2 = A'*B' (A y B a 0 hacen F2 1)

La suma de estas funciones será la función lógica final que buscamos:

F = F1 + F2 = (A*B)+(A'*B')

A continuación vamos a ver como en muchos casos es posible simplificar la función lógica final en otra más simple sin alterar el funcionamiento del circuito.

Simplificación de funciones

Supongamos que tenemos un circuito donde "F" es la respuesta (salida) del mismo en función de las señales A, B, y C (entradas):

F = A*B*C + A'*B*C + B*C

Esta función puede ser simplificable aplicando las propiedades del álgebra de Boole. En primer lugar aplicamos la propiedad distributiva:

F = B*C*(A+A') + B*C

Ahora aplicamos las leyes de idempotencia:

F = B*C + B*C = B*C

Como hemos podido ver en este ejemplo en muchas ocasiones se puede simplificar la función (y por tanto el circuito) sin que ello afecte al resultado. Más adelante veremos como simplificar funciones empleando otros métodos más sencillos y fiables.

Tablas de verdad

DEFINICION:

Es una forma de representación de una función en la que se indica el valor 0 o 1 para cada valor que toma ésta por cada una de las posibles combinaciones que las variables de entrada pueden tomar.

Anteriormente hemos visto las tablas de respuesta de cada una de las operaciones lógicas; estas tablas son tablas de verdad de sus correspondientes puertas lógicas.

La tabla de verdad es la herramienta que debemos emplear para obtener la forma canónica de la función del circuito, para así poder simplificar y conseguir la función más óptima.

Veamos un ejemplo de la tabla de verdad para una NAND de cuatro entradas:


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


Como podemos ver, si simplificamos la función obtenemos:

F = (A*B*C*D)'

es decir, un puerta NAND de 4 entradas.

TEOREMA DEL ALGEBRA DE BOOLE

Álgebra de Boole (también llamada Retículas booleanas) en informática y matemática, es una estructura algebraica que rigorizan las operaciones lógicas Y, O y NO, así como el conjunto de operaciones unión, intersección y complemento.

Se denomina así en honor a Jeorge Boole, (2 de noviembre de 1815 a 8 de diciembre de 1864), matemático inglés que fue el primero en definirla como parte de un sistema lógico a mediados del siglo XIX. Específicamente,

el álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. En la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito del diseño electrónico. Claude Shannon fue el primero en aplicarla en el diseño de circuitos de conmutación eléctrica biestables, en 1938.

TALLER RECUPERACION LOGICA 2do PERIODO

TALLER DE RECUPERACION DE 2do PERIODO LOGICA

TALLER DE RECUPERACION LOGICA 2do PERIODO

ÁLGEBRA DE BOOLE.

El álgebra de Boole se llama así debido a George Boole, quien la desarrolló a mediados del siglo XIX. El álgebra de Boole denominada también álgebra de la lógica, permite prescindir de la intuición y simplificar deductivamente afirmaciones lógicas que son todavía más complejos.

El objetivo principal de este tema es llegar a manejar los postulados y teoremas del álgebra de Boole como herramienta básica en el análisis y síntesis de circuitos digitales.

Si lo desea, elija alguna opción haciendo clic sobre ella.

TEOREMA DEL ALGEBRA DE BOOLE

Álgebra de Boole (también llamada Retículas booleanas) en informática y matemática, es una estructura algebraica que rigorizan las operaciones lógicas Y, O y NO, así como el conjunto de operaciones unión, intersección y complemento.

Se denomina así en honor a Jeorge Boole, (2 de noviembre de 1815 a 8 de diciembre de 1864), matemático inglés que fue el primero en definirla como parte de un sistema lógico a mediados del siglo XIX. Específicamente, el álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. En la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito del diseño electrónico. Claude Shannon fue el primero en aplicarla en el diseño de circuitos de conmutación eléctrica biestables, en 1938.

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(').

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.

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).

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 2ⁿ. 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.

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.

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 = 1011₂ = 11₁₀

A’ + B + C’ + D’ = 0100₂ = 4₁₀

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 = Σ₃(2, 4, 5, 6) = Π₃(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(2ⁿ-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 = Σ₃(2, 4, 5, 6) = [Σ₃(2, 4, 5, 6)]' ' = [Σ₃(0, 1, 3, 7)]' = Π₃(0, 4, 6, 7)