Formatos binarios
En un sentido estricto, cada número binario contiene una cantidad infinita de dígitos, también llamados bits que es una abreviatura de binary digits, por ejemplo, podemos representar el número siete de las siguientes formas:
111
00000111
000000000000111
Por conveniencia ignoraremos cualquier cantidad de ceros a la izquierda, sin embargo, como las instrucciones compatibles con los procesadores Intel 80x86 trabajan con grupos de ocho bits a veces es más fácil extender la cantidad de ceros a la izquierda en un múltiplo de cuatro u ocho bits, por ejemplo, el número siete podemos representarlo así: 01112 o 000001112. También es conveniente separar en grupos de cuatro dígitos los números binarios grandes, por ejemplo, el valor binario 1010111110110010 puede ser escrito así 1010 1111 1011 0010. Además, en una cadena binaria asignaremos al dígito de la extrema derecha como el bit de posición cero y cada bit subsecuente se le asignará el siguiente número sucesivo, de ésta manera un valor binario de ocho bits utiliza los bits cero al siete: X7 X6 X5 X4 X3 X2 X1 X0 Al bit cero se le conoce como el bit de bajo orden en tanto que al bit de la extrema izquierda diferente de cero se le llama bit de alto orden.
--------------------------------------------------------------------------------
jueves, 19 de agosto de 2010
CONVERSIONES ENTRE DIFERENTES SISTEMAS DE NUMERACION
Suma, Resta, Multiplicación y División
Dos números binarios se pueden sumar siguiendo este esquema: 0+0=0, 0+1=1, 1+1=10 . Ejemplos:
Suma:
10110
+ 01101
------
100011
Resta:
1011010
- 110101
________
100101
Multiplicacion:
101
* 1001
______
101
000
000
101
_______
101101
Las operaciones aritméticas con números en base 2 son muy sencillas. Las reglas básicas son: 1 + 1 = 10 y 1 × 1 = 1. El cero cumple las mismas propiedades que en el sistema decimal: 1 × 0 = 0 y 1 + 0 = 1. La adición, sustracción y multiplicación se realizan de manera similar a las del sistema decimal. Reglas de la divisiíon binaria: 0/0 no permitida, 1/0 no permitida,0/1=0, 1/1=1
Cambios de base de numeración
Existe un procedimiento general para cambiar una base cualquiera a otra cualquiera:
Para pasar de una base cualquiera a base 10, hemos visto que basta con realizar la suma de los productos de cada dígito por su valor de posición. Los valores de posición se obtienen como potencias sucesivas de la base, de derecha a izquierda, empezando por el exponente cero. Cada resultado obtenido se suma, y el resultado global es el número en base 10.
Para pasar de base 10 a otra base, en vez de multiplicar, dividimos el número a convertir entre la nueva base. El cociente se vuelve a dividir por la base, y así sucesivamente hasta que el cociente sea inferior a la base.El último cociente y los restos (en orden inverso) indican los dígitos en la nueva base.
El sistema binario trabaja de forma similar al sistema decimal con dos diferencias, en el sistema binario sólo está permitido el uso de los dígitos 0 y 1 (en lugar de 0-9) y en el sistema binario se utilizan potencias de 2 en lugar de potencias de 10. De aquí tenemos que es muy fácil convertir un número binario a decimal, por cada 1 en la cadena binaria, sume 2n donde n es la posición del dígito binario a partir del punto decimal contando a partir de cero. Por ejemplo, el valor binario 11001010 representa:
1*(27) + 1*(26) + 0*(25) + 0*(24) + 1*(23) + 0*(22) + 1*(21) + 0*(20) = 128 + 64 + 8 + 2 = 20210
Para convertir un número decimal en binario es un poco más difícil. Se requiere encontrar aquellas potencias de 2 las cuales, sumadas, producen el resultado decimal, una forma conveniente es trabajar en reversa por ejemplo, para convertir el número 1359 a binario:
(210)=1024, (211)=2048. Por tanto la mayor potencia de 2 menor que 1359 es (210). Restamos 1024 a 1359 y empezamos nuestro número binario poniendo un 1 a la izquierda. El resultado decimal es 1359-1024=335. El resultado binario hasta este punto es: 1.
La siguiente potencia de 2 en orden descendente es (29)=512 lo que es mayor que el resultado de la resta del punto anterior, por lo tanto agregamos un 0 a nuestra cadena binaria, ahora es: 10. El resultado decimal es aún 335.
La siguiente potencia es (28)=256 por lo que lo restamos a 335 y agregamos 1 a la cadena binaria: 101. El resultado decimal es: 79.
(27)=128, esto es mayor que 79. Agregamos un 0 a la cadena binaria: 1010 en tanto que el valor decimal es: 79.
Restamos (26)=64 a 79. La cadena binaria es ahora: 10101. El resultado decimal indica: 15.
15 es menor que (25)=32, por tanto, Binario=101010, el valor decimal sigue siendo: 15.
15 es menor que (24)=16, de aquí, Binario=1010100, el valor decimal continúa en: 15.
(23)=8 es menor que 15, así que agregamos un 1 a la cadena binaria: 10101001, en tanto que el nuevo valor decimal es: 7.
(22) es menor que 7. Binario es ahora: 101010011, el resultado decimal ahora vale: 3.
(21) es menor que 3. Binario=1010100111, el nuevo valor decimal es: 1.
Finalmente el resultado decimal es 1 lo que es igual a (20) por lo que agregamos un 1 a la cadena binaria. Nuestro resultado indica que el equivalente binario del número decimal 1359 es: 10101001111
--------------------------------------------------------------------------------
Dos números binarios se pueden sumar siguiendo este esquema: 0+0=0, 0+1=1, 1+1=10 . Ejemplos:
Suma:
10110
+ 01101
------
100011
Resta:
1011010
- 110101
________
100101
Multiplicacion:
101
* 1001
______
101
000
000
101
_______
101101
Las operaciones aritméticas con números en base 2 son muy sencillas. Las reglas básicas son: 1 + 1 = 10 y 1 × 1 = 1. El cero cumple las mismas propiedades que en el sistema decimal: 1 × 0 = 0 y 1 + 0 = 1. La adición, sustracción y multiplicación se realizan de manera similar a las del sistema decimal. Reglas de la divisiíon binaria: 0/0 no permitida, 1/0 no permitida,0/1=0, 1/1=1
Cambios de base de numeración
Existe un procedimiento general para cambiar una base cualquiera a otra cualquiera:
Para pasar de una base cualquiera a base 10, hemos visto que basta con realizar la suma de los productos de cada dígito por su valor de posición. Los valores de posición se obtienen como potencias sucesivas de la base, de derecha a izquierda, empezando por el exponente cero. Cada resultado obtenido se suma, y el resultado global es el número en base 10.
Para pasar de base 10 a otra base, en vez de multiplicar, dividimos el número a convertir entre la nueva base. El cociente se vuelve a dividir por la base, y así sucesivamente hasta que el cociente sea inferior a la base.El último cociente y los restos (en orden inverso) indican los dígitos en la nueva base.
El sistema binario trabaja de forma similar al sistema decimal con dos diferencias, en el sistema binario sólo está permitido el uso de los dígitos 0 y 1 (en lugar de 0-9) y en el sistema binario se utilizan potencias de 2 en lugar de potencias de 10. De aquí tenemos que es muy fácil convertir un número binario a decimal, por cada 1 en la cadena binaria, sume 2n donde n es la posición del dígito binario a partir del punto decimal contando a partir de cero. Por ejemplo, el valor binario 11001010 representa:
1*(27) + 1*(26) + 0*(25) + 0*(24) + 1*(23) + 0*(22) + 1*(21) + 0*(20) = 128 + 64 + 8 + 2 = 20210
Para convertir un número decimal en binario es un poco más difícil. Se requiere encontrar aquellas potencias de 2 las cuales, sumadas, producen el resultado decimal, una forma conveniente es trabajar en reversa por ejemplo, para convertir el número 1359 a binario:
(210)=1024, (211)=2048. Por tanto la mayor potencia de 2 menor que 1359 es (210). Restamos 1024 a 1359 y empezamos nuestro número binario poniendo un 1 a la izquierda. El resultado decimal es 1359-1024=335. El resultado binario hasta este punto es: 1.
La siguiente potencia de 2 en orden descendente es (29)=512 lo que es mayor que el resultado de la resta del punto anterior, por lo tanto agregamos un 0 a nuestra cadena binaria, ahora es: 10. El resultado decimal es aún 335.
La siguiente potencia es (28)=256 por lo que lo restamos a 335 y agregamos 1 a la cadena binaria: 101. El resultado decimal es: 79.
(27)=128, esto es mayor que 79. Agregamos un 0 a la cadena binaria: 1010 en tanto que el valor decimal es: 79.
Restamos (26)=64 a 79. La cadena binaria es ahora: 10101. El resultado decimal indica: 15.
15 es menor que (25)=32, por tanto, Binario=101010, el valor decimal sigue siendo: 15.
15 es menor que (24)=16, de aquí, Binario=1010100, el valor decimal continúa en: 15.
(23)=8 es menor que 15, así que agregamos un 1 a la cadena binaria: 10101001, en tanto que el nuevo valor decimal es: 7.
(22) es menor que 7. Binario es ahora: 101010011, el resultado decimal ahora vale: 3.
(21) es menor que 3. Binario=1010100111, el nuevo valor decimal es: 1.
Finalmente el resultado decimal es 1 lo que es igual a (20) por lo que agregamos un 1 a la cadena binaria. Nuestro resultado indica que el equivalente binario del número decimal 1359 es: 10101001111
--------------------------------------------------------------------------------
SISTEMAS DE NUMERACION
Los sistemas de numeración son conjuntos de dígitos usados para representar cantidades, así se tienen los sistemas de numeración decimal, binario, octal, hexadecimal, romano, etc. Los cuatro primeros se caracterizan por tener una base (número de dígitos diferentes: diez, dos, ocho, dieciseis respectivamente) mientras que el sistema romano no posee base y resulta más complicado su manejo tanto con números, así como en las operaciones básicas.
Los sistemas de numeración que poseen una base tienen la característica de cumplir con la notación posicional, es decir, la posición de cada número le da un valor o peso, así el primer dígito de derecha a izquierda después del punto decimal, tiene un valor igual a b veces el valor del dígito, y así el dígito tiene en la posición n un valor igual a: (bn) * A
donde:
b = valor de la base del sistema
n = número del dígito o posición del mismo
A = dígito.
Por ejemplo:
digitos: 1 2 4 9 5 3 . 3 2 4
posicion 5 4 3 2 1 0 . -1 -2 -3
El sistema numérico decimal
El sistema de numeración decimal es el más usado, tiene como base el número 10, o sea que posee 10 dígitos (o simbolos) diferentes (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). El sistema de numeración decimal fué desarrollado por los hindúes, posteriormente lo introducen los árabes en Europa, donde recibe el nombre de sistema de numeración decimal o arábigo. Si se aplica la notación posicional al sistema de numeración decimal entonces el dígito número n tiene el valor: (10n)* A
Este valor es positivo y es mayor o igual que uno si el dígito se localiza a la izquierda del punto decimal y depende del dígito A, en cambio el valor es menor que uno si el dígito se localiza a la derecha del punto decimal. Por ejemplo, el número 3489.125 expresado en la notación posicional es:
primero 9 * (100) = 9 --------- primero 1*(10-1) = 0.1
segundo 8 * (101) = 80 -------- segundo 2*(10-2) = 0.02
tercero 4 * (102) = 400 -------- tercero 5*(10-3) = 0.005
cuarto 3 * (103) = 3000
m = posición del dígito que se localiza a la derecha
k = posición del dígito que se localiza a la izquierda
b = valor de la base
n = posición del dígito a evaluar
a = dígito a evaluar
para el ejemplo:
= 5*(10-3) + 2*(10-2) + 1*(10-1) + 9*(100) + 8*(101) + 4*(102) + 3*(103)
= 0.005 + 0.02 + 0.1 + 9 + 80 + 400 + 3000
= 3489.125
Notación Posicional del Sistema
(10-6) = 0.000001
(10-5) = 0.00001
(10-4) = 0.0001
(10-3) = 0.001
(10-2) = 0.01
(10-1) = 0.1
(100) = 1
(101) = 10
(102) = 100
(103) = 1000
(104) = 10000
(105) = 100000
(106) = 10000000
Sistema Binario
El sistema de numeración más simple que usa la notación posicional es el sistema de numeración binario. Este sistema, como su nombre lo indica, usa solamente dos dígitos (0,1).
Por su simplicidad y por poseer únicamente dos dígitos diferentes, el sistema de numeración binario se usa en computación para el manejo de datos e información. Normalmente al dígito cero se le asocia con cero voltios, apagado, desenergizado, inhibido (de la computadora) y el dígito 1 se asocia con +5, +12 volts, encendido, energizado (de la computadora) con el cual se forma la lógica positiva. Si la asociación es inversa, o sea el número cero se asocia con +5 volts o encendido y al número 1 se asocia con cero volts o apagado, entonces se genera la lógica negativa.
A la representación de un dígito binario se le llama bit (de la contracción binary digit) y al conjunto de 8 bits se le llama byte, así por ejemplo: 110 contiene 3 bits, 1001 contiene 4 y 1 contiene 1 bit. Como el sistema binario usa la notación posicional entonces el valor de cada dígito depende de la posición que tiene en el número, así por ejemplo el número 110101b es:
1*(20) + 0*(21) + 1*(22) + 0*(23) + 1*(24) + 1*(25) = 1 + 4 + 16 + 32 = 53d
La computadora está diseñada sobre la base de numeración binaria (base 2). Por eso este caso particular merece mención aparte. Siguiendo las reglas generales para cualquier base expuestas antes, tendremos que:
Existen dos dígitos (0 o 1) en cada posición del número.
Numerando de derecha a izquierda los dígitos de un número, empezando por cero, el valor decimal de la posición es 2n.
Por ejemplo,11012 (en base 2) quiere decir:
1*(23) + 1*(22) + 0*(21) + 1*(20) = 8 + 4 + 0 + 1 = 1310
--------------------------------------------------------------------------------
Sistema Octal
El sistema de numeración octal es también muy usado en la computación por tener una base que es potencia exacta de 2 o de la numeración binaria. Esta característica hace que la conversión a binario o viceversa sea bastante simple. El sistema octal usa 8 dígitos (0,1,2,3,4,5,6,7) y tienen el mismo valor que en el sistema de numeración decimal. Como el sistema de numeración octal usa la notación posicional entonces para el número 3452.32q tenemos:
2*(80) + 5*(81) + 4*(82) + 3*(83) + 3*(8-1) + 2*(8-2) = 2 + 40 + 4*64 + 64 + 3*512 + 3*0.125 + 2*0.015625 = 2 + 40 + 256 + 1536 + 0.375 + 0.03125 = 1834 + 40625dentonces, 3452.32q = 1834.40625d
El subindice q indica número octal, se usa la letra q para evitar confusión entre la letra o y el número 0.
Sistema Hexadecimal
Un gran problema con el sistema binario es la verbosidad. Para representar el valor 20210 se requieren ocho dígitos binarios, la versión decimal sólo requiere de tres dígitos y por lo tanto los números se representan en forma mucho más compacta con respecto al sistema numérico binario. Desafortunadamente las computadoras trabajan en sistema binario y aunque es posible hacer la conversión entre decimal y binario, ya vimos que no es precisamente una tarea cómoda. El sistema de numeración hexadecimal, o sea de base 16, resuelve este problema (es común abreviar hexadecimal como hex aunque hex significa base seis y no base dieciseis). El sistema hexadecimal es compacto y nos proporciona un mecanismo sencillo de conversión hacia el formato binario, debido a ésto, la mayoría del equipo de cómputo actual utiliza el sistema numérico hexadecimal. Como la base del sistema hexadecimal es 16, cada dígito a la izquierda del punto hexadecimal representa tantas veces un valor sucesivo potencia de 16, por ejemplo, el número 123416 es igual a:
1*163 + 2*162 + 3*161 + 4*160
lo que da como resultado:
4096 + 512 + 48 + 4 = 466010
Cada dígito hexadecimal puede representar uno de dieciseis valores entre 0 y 1510. Como sólo tenemos diez dígitos decimales, necesitamos inventar seis dígitos adicionales para representar los valores entre 1010 y 1510. En lugar de crear nuevos simbolos para estos dígitos, utilizamos las letras A a la F. La conversión entre hexadecimal y binario es sencilla, considere la siguiente tabla:
Binario Hexadecimal
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 A
1011 B
1100 C
1101 D
1110 E
1111 F
Esta tabla contiene toda la información necesaria para convertir de binario a hexadecimal y visceversa. Para convertir un número hexadecimal en binario, simplemente sustituya los correspondientes cuatro bits para cada dígito hexadecimal, por ejemplo, para convertir 0ABCDh en un valor binario:
0 A B C D (Hexadecimal)
0000 1010 1011 1100 1101 (Binario)
Por comodidad, todos los valores numéricos los empezaremos con un dígito decimal; los valores hexadecimales terminan con la letra h y los valores binarios terminan con la letra b. La conversión de formato binario a hexadecimal es casi igual de fácil, en primer lugar necesitamos asegurar que la cantidad de dígitos en el valor binario es múltiplo de 4, en caso contrario agregaremos ceros a la izquierda del valor, por ejemplo el número binario 1011001010, la primera etapa es agregarle dos ceros a la izquierda para que contenga doce ceros: 001011001010. La siguiente etapa es separar el valor binario en grupos de cuatro bits, así: 0010 1100 1010. Finalmente buscamos en la tabla de arriba los correspondientes valores hexadecimales dando como resultado, 2CA, y siguiendo la convención establecida: 02CAh.
Los sistemas de numeración que poseen una base tienen la característica de cumplir con la notación posicional, es decir, la posición de cada número le da un valor o peso, así el primer dígito de derecha a izquierda después del punto decimal, tiene un valor igual a b veces el valor del dígito, y así el dígito tiene en la posición n un valor igual a: (bn) * A
donde:
b = valor de la base del sistema
n = número del dígito o posición del mismo
A = dígito.
Por ejemplo:
digitos: 1 2 4 9 5 3 . 3 2 4
posicion 5 4 3 2 1 0 . -1 -2 -3
El sistema numérico decimal
El sistema de numeración decimal es el más usado, tiene como base el número 10, o sea que posee 10 dígitos (o simbolos) diferentes (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). El sistema de numeración decimal fué desarrollado por los hindúes, posteriormente lo introducen los árabes en Europa, donde recibe el nombre de sistema de numeración decimal o arábigo. Si se aplica la notación posicional al sistema de numeración decimal entonces el dígito número n tiene el valor: (10n)* A
Este valor es positivo y es mayor o igual que uno si el dígito se localiza a la izquierda del punto decimal y depende del dígito A, en cambio el valor es menor que uno si el dígito se localiza a la derecha del punto decimal. Por ejemplo, el número 3489.125 expresado en la notación posicional es:
primero 9 * (100) = 9 --------- primero 1*(10-1) = 0.1
segundo 8 * (101) = 80 -------- segundo 2*(10-2) = 0.02
tercero 4 * (102) = 400 -------- tercero 5*(10-3) = 0.005
cuarto 3 * (103) = 3000
m = posición del dígito que se localiza a la derecha
k = posición del dígito que se localiza a la izquierda
b = valor de la base
n = posición del dígito a evaluar
a = dígito a evaluar
para el ejemplo:
= 5*(10-3) + 2*(10-2) + 1*(10-1) + 9*(100) + 8*(101) + 4*(102) + 3*(103)
= 0.005 + 0.02 + 0.1 + 9 + 80 + 400 + 3000
= 3489.125
Notación Posicional del Sistema
(10-6) = 0.000001
(10-5) = 0.00001
(10-4) = 0.0001
(10-3) = 0.001
(10-2) = 0.01
(10-1) = 0.1
(100) = 1
(101) = 10
(102) = 100
(103) = 1000
(104) = 10000
(105) = 100000
(106) = 10000000
Sistema Binario
El sistema de numeración más simple que usa la notación posicional es el sistema de numeración binario. Este sistema, como su nombre lo indica, usa solamente dos dígitos (0,1).
Por su simplicidad y por poseer únicamente dos dígitos diferentes, el sistema de numeración binario se usa en computación para el manejo de datos e información. Normalmente al dígito cero se le asocia con cero voltios, apagado, desenergizado, inhibido (de la computadora) y el dígito 1 se asocia con +5, +12 volts, encendido, energizado (de la computadora) con el cual se forma la lógica positiva. Si la asociación es inversa, o sea el número cero se asocia con +5 volts o encendido y al número 1 se asocia con cero volts o apagado, entonces se genera la lógica negativa.
A la representación de un dígito binario se le llama bit (de la contracción binary digit) y al conjunto de 8 bits se le llama byte, así por ejemplo: 110 contiene 3 bits, 1001 contiene 4 y 1 contiene 1 bit. Como el sistema binario usa la notación posicional entonces el valor de cada dígito depende de la posición que tiene en el número, así por ejemplo el número 110101b es:
1*(20) + 0*(21) + 1*(22) + 0*(23) + 1*(24) + 1*(25) = 1 + 4 + 16 + 32 = 53d
La computadora está diseñada sobre la base de numeración binaria (base 2). Por eso este caso particular merece mención aparte. Siguiendo las reglas generales para cualquier base expuestas antes, tendremos que:
Existen dos dígitos (0 o 1) en cada posición del número.
Numerando de derecha a izquierda los dígitos de un número, empezando por cero, el valor decimal de la posición es 2n.
Por ejemplo,11012 (en base 2) quiere decir:
1*(23) + 1*(22) + 0*(21) + 1*(20) = 8 + 4 + 0 + 1 = 1310
--------------------------------------------------------------------------------
Sistema Octal
El sistema de numeración octal es también muy usado en la computación por tener una base que es potencia exacta de 2 o de la numeración binaria. Esta característica hace que la conversión a binario o viceversa sea bastante simple. El sistema octal usa 8 dígitos (0,1,2,3,4,5,6,7) y tienen el mismo valor que en el sistema de numeración decimal. Como el sistema de numeración octal usa la notación posicional entonces para el número 3452.32q tenemos:
2*(80) + 5*(81) + 4*(82) + 3*(83) + 3*(8-1) + 2*(8-2) = 2 + 40 + 4*64 + 64 + 3*512 + 3*0.125 + 2*0.015625 = 2 + 40 + 256 + 1536 + 0.375 + 0.03125 = 1834 + 40625dentonces, 3452.32q = 1834.40625d
El subindice q indica número octal, se usa la letra q para evitar confusión entre la letra o y el número 0.
Sistema Hexadecimal
Un gran problema con el sistema binario es la verbosidad. Para representar el valor 20210 se requieren ocho dígitos binarios, la versión decimal sólo requiere de tres dígitos y por lo tanto los números se representan en forma mucho más compacta con respecto al sistema numérico binario. Desafortunadamente las computadoras trabajan en sistema binario y aunque es posible hacer la conversión entre decimal y binario, ya vimos que no es precisamente una tarea cómoda. El sistema de numeración hexadecimal, o sea de base 16, resuelve este problema (es común abreviar hexadecimal como hex aunque hex significa base seis y no base dieciseis). El sistema hexadecimal es compacto y nos proporciona un mecanismo sencillo de conversión hacia el formato binario, debido a ésto, la mayoría del equipo de cómputo actual utiliza el sistema numérico hexadecimal. Como la base del sistema hexadecimal es 16, cada dígito a la izquierda del punto hexadecimal representa tantas veces un valor sucesivo potencia de 16, por ejemplo, el número 123416 es igual a:
1*163 + 2*162 + 3*161 + 4*160
lo que da como resultado:
4096 + 512 + 48 + 4 = 466010
Cada dígito hexadecimal puede representar uno de dieciseis valores entre 0 y 1510. Como sólo tenemos diez dígitos decimales, necesitamos inventar seis dígitos adicionales para representar los valores entre 1010 y 1510. En lugar de crear nuevos simbolos para estos dígitos, utilizamos las letras A a la F. La conversión entre hexadecimal y binario es sencilla, considere la siguiente tabla:
Binario Hexadecimal
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 A
1011 B
1100 C
1101 D
1110 E
1111 F
Esta tabla contiene toda la información necesaria para convertir de binario a hexadecimal y visceversa. Para convertir un número hexadecimal en binario, simplemente sustituya los correspondientes cuatro bits para cada dígito hexadecimal, por ejemplo, para convertir 0ABCDh en un valor binario:
0 A B C D (Hexadecimal)
0000 1010 1011 1100 1101 (Binario)
Por comodidad, todos los valores numéricos los empezaremos con un dígito decimal; los valores hexadecimales terminan con la letra h y los valores binarios terminan con la letra b. La conversión de formato binario a hexadecimal es casi igual de fácil, en primer lugar necesitamos asegurar que la cantidad de dígitos en el valor binario es múltiplo de 4, en caso contrario agregaremos ceros a la izquierda del valor, por ejemplo el número binario 1011001010, la primera etapa es agregarle dos ceros a la izquierda para que contenga doce ceros: 001011001010. La siguiente etapa es separar el valor binario en grupos de cuatro bits, así: 0010 1100 1010. Finalmente buscamos en la tabla de arriba los correspondientes valores hexadecimales dando como resultado, 2CA, y siguiendo la convención establecida: 02CAh.
TAUTOLOGIAS, CONTRADICCION Y CONTINGENCIA
Una tautología es una expresión lógica que es verdadera para todos los posibles valores de verdad de sus componentes atómicos.
En lógica 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, o de un modo más sencillo: la supuesta explicación de algo mediante una perogrullada, la “explicación” o definición de algo mediante una ligera variación de palabras que tienen en conjunto el mismo significado ya conocido de lo supuestamente explicado (Ej.: “Existe el calor porque lo provoca el calórico”).
Tautología: en todos los casos la forma del argumento ofrece un resultado verdadero, por lo que el argumento es válido.
Una contradiccion es uan expresion logica que es falsa para todos sus valores.
El procedimiento de la demostración por contradicción es semejante a la que se realizó por el método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción.
--------------------------------------------------------------------------------
Ejemplo 1:
La expresión ‘(p ^ q) → (p ∨ r)’ es una tautología
Tautologías Fundamentales
p ∨ ¬p Ley del medio excluido
¬ (p ^ ¬p) Ley de no contradicción
¬(¬p) ↔ p Doble Negación
¬(p ∨ q) ↔ ¬p ^ ¬q Ley 1 de De Morgan
¬(p ^ q) ↔ ¬p ∨ ¬q Ley 2 de De Morgan
((p → q)^p) → q Modus ponendo ponens
((p → q)^ ¬ q) → ¬ p Modus tollendo tollens
((p ∨ q) ∧ ¬ p) → q Silogismo Disyuntivo
((p → q) ∧ (q → r)) → (p → r) Silogismo Hipotético
(p → q) ↔ (¬ p ∨ q) Condicional como cláusula
((p → q) ↔ (¬ q → ¬ p) Contrapositiva
En lógica 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, o de un modo más sencillo: la supuesta explicación de algo mediante una perogrullada, la “explicación” o definición de algo mediante una ligera variación de palabras que tienen en conjunto el mismo significado ya conocido de lo supuestamente explicado (Ej.: “Existe el calor porque lo provoca el calórico”).
Tautología: en todos los casos la forma del argumento ofrece un resultado verdadero, por lo que el argumento es válido.
Una contradiccion es uan expresion logica que es falsa para todos sus valores.
El procedimiento de la demostración por contradicción es semejante a la que se realizó por el método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción.
--------------------------------------------------------------------------------
Ejemplo 1:
La expresión ‘(p ^ q) → (p ∨ r)’ es una tautología
Tautologías Fundamentales
p ∨ ¬p Ley del medio excluido
¬ (p ^ ¬p) Ley de no contradicción
¬(¬p) ↔ p Doble Negación
¬(p ∨ q) ↔ ¬p ^ ¬q Ley 1 de De Morgan
¬(p ^ q) ↔ ¬p ∨ ¬q Ley 2 de De Morgan
((p → q)^p) → q Modus ponendo ponens
((p → q)^ ¬ q) → ¬ p Modus tollendo tollens
((p ∨ q) ∧ ¬ p) → q Silogismo Disyuntivo
((p → q) ∧ (q → r)) → (p → r) Silogismo Hipotético
(p → q) ↔ (¬ p ∨ q) Condicional como cláusula
((p → q) ↔ (¬ q → ¬ p) Contrapositiva
TABLAS DE VERDAD
Conectivos Lógicos y Jerarquías
Como se mecionó en la sección anterior para formar expresiones compuestas necesitamos conectivos lógicos, empezaremos por un conectivo unitario; esto es, se aplica a una proposición sola.
La Negación
La operación unitaria de negación, no es cierto que se representa por “¬” y tiene la siguiente tabla de verdad de verdad
p ¬p
V F
F V
Ejemplo. Encuentre la negación de las expresiones siguientes:
i) Júpiter es un planeta
ii) El pizarrón es verde
iii) El número real x es negativo
iv) Algún elefante es de color rosa
v) Ningún pez respira fuera del agua
vi) Todos los leones son feroces
Solución:
i) Júpiter no es un planeta
ii) El pizarrón no es verde
iii) El número real x no es negativo o también El número real x es positivo ó cero
iv) Ningún elefante es de color rosa
v) Algún pez respira fuera del agua
vi) Algún león no es feroz
Nota: Las tres últimas proposiciones se derivan de proposiciones abiertas que veremos en la sección 1.4
Calculo de Predicados Definicion.
La conjunción de las proposiciones p, q es la operación binaria que tiene por resultado p y q, se representa por p^q, y su tabla de verdad es:
La conjunción nos sirve para indicar que se cumplen dos condiciones simultáneamente, así por ejemplo si tenemos:
La función es creciente y está definida para los números positivos, utilizamos
p ^ q, donde
p: la función es creciente
q: la función esta definida para los números positivos
Así también: p ^ q, donde
p: el número es divisible por 3
q: el número está representado en base 2
se lee: El número es divisible entre 3 y está representado en base 2.
Nota: Observamos que para la conjunción p ^ q sea verdadera las dos expresiones que intervienen deben ser verdaderas y sólo en ese caso como se indica por su tabla de verdad.
La disyunción de dos proposiciones p, q es la operación binaria que da por resultado p ó q, notación p v q, y tiene la siguiente tabla:
p q p v q
|| V || V || V ||
V F V
F V V
F F F
Con la disyunción a diferencia de la conjunción, representamos dos expresiones y que afirman que una de las dos es verdadera, por lo que basta con que una de ellas sea verdaera para que la expresión p ∨ q sea verdadera.
Así por ejemplo la expresión: el libro se le entregará a Juan o el libro se le entregará a Luis significa que si va uno de los dos, el libro se le entrega, si van los dos también se entrega y solamente en caso de que no vaya ninguno de los dos no se debe entregar.
Aquí debemos tener cuidado, porque en español muchas veces utilizamos la disyunción para representar otros operadores que aparentemente son lo mismo, pero que tienen diferente significado.
En español tenemos tres casos de disyunción:
La llamada y/o bancaria, lógica o matemática, que es la misma y se utliza en computación como el operador OR, este operadorcorresponde al mencionado anteriormente p v q y ya se mostró su tabla de verdad.
La o excluyente, que algunos también le llaman o exclusiva, y que indica que una de las dos proposiciones se cumple, pero no las dos. Este caso corresponde por ejemplo a: Hoy compraré un libro o iré al cine; se sobrentiende que una de las dos debe ser verdadera, pero no la dos. Se representa por p XOR q y su tabla de verdad es:
p q p XOR q
V V F
V F V
F V V
F F F
Por último, también es muy común utilizar una disyunción como la siguiente: El menú incluye café o té. En este caso se esta dando una disyuntiva diferente pues no se pueden las dos simultáneamente como en el caso anterior, pero aquí si es válido el caso donde las dos son falsas. Es el caso “no ámbas”, se puede representar por p § q y su tablas es
p q p § q
V V F
V F V
F V V
F F V
Nota: El último símbolo no es estándar y puede haber varias formas de representarlo.
Un buen ejercicio consiste en enunciar varias expresiones del español que utilizando los conectivos y o para analizar cuál de los operadores es.
Hay que tener mucho cuidado cuando se traduce del lenguaje usual por las costumbres, muchas veces depende del contexto o de la situación específica en la que se usan los conectivos, por ejemplo si decimos: Se pueden estacionar alumnos y maestros, en realidad se está queriendo decir un operador disyuntivo, en este caso la o matemática, o sea el primer operador que corresponde a la primera tabla de esta sección.
La condicional de dos proposiciones p, q da lugar a la proposición; si p entonces q, se representa por p → q, y su tabla de verdad está dada por:
p q p→q
V V V
V F F
F V V
F F V
Con respecto a este operador binario, lo primero que hay que destacar es que no es conmutativo, a diferencia de los dos anteriores la conjunción y la disyunción. El único caso que resulta falso es cuando el primero es verdadero y el segundo falso.
Por ejemplo, si p es llueve y q es hay nubes entonces:
p → q es si llueve entonces hay nubes.
También cabe señalar que este viene a ser el operador más importante en el proceso deductivo y que la mayoría de las leyes de inferencia y las propiedades en matemáticas se pueden enunciar utilizando este operador.
La bicondicional de dos proposiciones p, q da lugar a la proposición; p si y sólo si q, se representa por p ↔ q su tabla de verdad está dada por:
p q p ↔ q
V V V
V F F
F V F
F F V
Jerarquia de Operadores.
Combinando los operadores anteriores podemos formar nuevas expresiones.
En términos formales la negación de p, deberá ser ( ¬ p), así como la conjunción de p y q sería (p ^ q). Con el uso de paréntesis evitamos la ambiguedad, por ejemplo ¬p ^ q podría significar dos cosas distintas
Por un lado podría significar: (( ¬ p) ^ q) O también: ( ¬ (p ^ q)).
En la práctica para no usar tantos paréntesis se considera que el operador ¬ tiene jerarquia sobre ^, v, →, ↔. Así ¬ p ^ q significa (( ¬ p)^ q).
En algunos casos se considera ^, v tienen mayor jerarquía que ↔ por lo que p ↔ q v r sería (p ↔ (q v r)) y también que ^ tiene prioridad sobre v, por lo que p ^ q v r sería (p ^ q) v r.
Así por ejemplo, en electrónica, para representar circuitos lógicos se utiliza + en lugar de v y · en lugar de ^.
Por lo que p·q+r es ((p ^ q) v r).
En estos apuntes no se considerará jerarquía en ninguno de los operadores binarios ^, v, →, ↔ por lo que utilizaremos paréntesis. Sólo ¬ tiene prioridad sobre los demás operadores. Esto nos ahorrá algunos paréntesis, por ejemplo: ((( ¬ p) ^ q) v r) se representa por ( ¬ p ^ q) v r.
Contrucción de Tablas de Verdad
Como ya sabemos la sintaxis en lógica es la forma correcta de escribir una fórmula y la semántica es lo que significa. Como en lógica solamente tenemos dos valores una fórmula solamente puede ser verdadera o falsa. Para determinar su valor seguimos las reglas simples que dimos en las definiciones básicas de acuerdo a su tabla de verdad. Esto lo hacemos mediante interpretaciones. Una interpretación de una fórmula es un conjunto de valores que se les asignan a sus proposiciones atómicas.
Al interpretar una fórmula lo que finalmente vamos a obtener es un valor de verdad, bien sea verdadero o falso. Pero para poder encontrarlo muchas veces el proceso en laborioso porque puede estar formada por varias proposiciones atómicas. Primeramente se le asignan valores de verdad a los átomos y se puede encontrar el valor de la expresión.
Si deseamos hacerlo en general, debemos analizar todas las posibilidades, esto se puede hacer construyendo una tabla de verdad. Para fines prácticos cuando se tienen varios átomos las tablas de verdad no resultan prácticas por lo que analizaremos solamente expresiones con tres átomos como máximo.
Por supuesto que se puede construir una tabla para un número mayor de átomos, pero notemos que por cada átomo que se aumente el número de renglones se duplica. Esto es, para un átomos son dos renglones, para dos átomos son cuatro, para tres átomos son ocho, para cuatro dieciséis, etc.
Algoritmo para construir una tabla de verdad de una fórmula en lógica de proposiciones.
1. Escribir la fórmula con un número arriba de cada operador que indique su jerarquía. Se escriben los enteros positivos en orden, donde el número 1 corresponde al operador de mayor jerarquía. Cuando dos operadores tengan la misma jerarquía, se le asigna el número menor al de la izquierda.
2. Construir el árbol sintáctico empezando con la fórmula en la raíz y utilizando en cada caso el operador de menor jerarquía. O sea, del número mayor al menor.
3. Numerar las ramas del árbol en forma secuencial empezando por las hojas hacia la raíz, con la única condición de que una rama se puede numerar hasta que estén numerados los hijos. Para empezar con la numeración de las hojas es buena idea hacerlo en orden alfabético, así todos obtienen los renglones de la tabla en el mismo orden para poder comparar resultados.
4. Escribir los encabezados de la tabla las fórmulas siguiendo la numeración que se le dió a las ramas en el árbol sintáctico.
5. Asignarle a los átomos, las hojas del árbol, todos los posibles valores de verdad de acuerdo al orden establecido. Por supuesto que el orden es arbitrario, pero como el número de permutaciones es n!, conviene establecer un orden para poder comparar resultados fácilmente.
6. Asignar valor de verdad a cada una de las columnas restantes de acuerdo al operador indicado en el árbol sintáctico utilizando la tabla de verdad correspondiente del Tema 1.3 Conexiones Logicas y Jerarquias. Conviene aprenderse de memoria las tablas de los operadores, al principio pueden tener un resumen con todas las tablas mientras se memorizan.
7. La última columna, correspondiente a la fórmula original, es la que indica los valores de verdad posibles de la fórmula para cada caso.
Ejemplo. Construya la tabla de verdad de las siguientes expresiones lógicas:
i) (p → ¬q) v (¬p v r)
ii) p → (q ^ r)
iii) (p → ¬ r) ↔ (q v p)
iv) ¬(p ¬ q) → ¬ r
v) (¬p ^ q) → ¬(q v ¬r)
Solución:
i) Seguimos los pasos del algoritmo con la fórmula (p → ¬q) v (¬p v r)
1. Vemos que los operadores de los paréntesis tienen mayor jerarquía, empezamos por el paréntesis izquierdo por lo que la fórmula con jerarquías marcadas sería:
Attach:TablasVerdad11.jpg Δ
2. Contruir el arbol Sintáctico empezando a descomponer por el operador con el número mayor, seguir en orden descendiente hasta el último que es el que tiene el número 1.
Attach:TablasVerdad12.jpg Δ
3. Numerar las ramas del árbol
Attach:TablasVerdad13.jpg Δ
4. Escribir los encabezados de la tabla utilizando las fórmulas en el árbol siguiendo la numeración del paso 3.
5. Asignar valores de verdad a los átomos, en este caso, las tres primeras columas.
1 2 3
p q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F
6. Asignar los valores de verdad a la ¬ q.
1 2 3 4
p q r ¬ q
V V V F
V V F F
V F V V
V F F V
F V V F
F V F F
F F V V
F F F V
7. Asignar los valores de verdad a la ¬ p.
1 2 3 4 5
p q r ¬ q ¬ p
V V V F F
V V F F F
V F V V F
V F F V F
F V V F V
F V F F V
F F V V V
F F F V V
8. Asignar los valores de verdad basados en la tabla de la condicional con p(condicion 1) → ¬q(condicion 4).
1 2 3 4 5 6
p q r ¬ q ¬ p p → ¬q
V V V F F F
V V F F F F
V F V V F V
V F F V F V
F V V F V V
F V F F V V
F F V V V V
F F F V V V
9. Asignar los valores de verdad basados en la tabla disyuncion con la ¬p(condicion 4) v r(condicion 3).
1 2 3 4 5 6 7
p q r ¬ q ¬ p p → ¬q ¬p v r
V V V F F F V
V V F F F F F
V F V V F V V
V F F V F V F
F V V F V V V
F V F F V V V
F F V V V V V
F F F V V V V
10. Completar el resto de las condiciones utilizando las definiciones de los operadores,p → ¬q (condicion 6), v, ¬p v r (condicion 7).
1 2 3 4 5 6 7 8
p q r ¬ q ¬ p p → ¬q ¬p v r (p → ¬q) v (¬p v r)
V V V F F F V V
V V F F F F F F
V F V V F V V V
V F F V F V F V
F V V F V V V V
F V F F V V V V
F F V V V V V V
F F F V V V V V
11. La última columna es el resultado da cada interpretación establecida en los primeros tres renglones.
Los demás problemas son similares y se obtienen las tablas siguientes.
FALTA PONER LOS ÁRBOLES SINTÁCTICOS DE LOS EJEMPLOS 2 AL 5.
ii)
Attach:TablasVerdad2.jpg Δ
1 2 3 4 5
p q r q v r p → (q v r)
V V V V V
V V F V F
V F V V V
V F F V F
F V V V V
F V F V V
F F V F V
F F F F V
iii)
Attach:TablasVerdad3.jpg Δ
1 2 3 4 5 6 7
p q r ¬ r p → ¬ r q ∨ r (p → ¬ r) ↔ (q v r)
V V V F F V F
V V F V V V V
V F V F F V F
V F F V V F V
F V V F V V V
F V F V V V V
F F V F V V F
F F F V V F F
iv)
Attach:TablasVerdad14.jpg Δ
1 2 3 4 5 6 7 8
p q r ¬ q p ^ ¬ q ¬(p ^ ¬q) ¬ r ¬(p ^ ¬q) → ¬ r
V V V F F V F F
V V F F F V V V
V F V V V F F V
V F F V V F V V
F V V F F V F F
F V F F F V V V
F F V V F V F F
F F F V F V V V
v)
Attach:TablasVerdad5.jpg Δ
1 2 3 4 5 6 7 8 9
p q r ¬r ¬p q v ¬r ¬p ^ q ¬(q v ¬r) (¬p ^ q) → ¬(q v ¬r)
V V V F F V F F V
V V F V F V F F V
V F V F F F F V V
V F F V F F F V V
F V V F V V V F F
F V F V V V V F F
F F V F V V F F V
F F F V
EJEMPLOS DE TABLAS DE VERDAD
Como se mecionó en la sección anterior para formar expresiones compuestas necesitamos conectivos lógicos, empezaremos por un conectivo unitario; esto es, se aplica a una proposición sola.
La Negación
La operación unitaria de negación, no es cierto que se representa por “¬” y tiene la siguiente tabla de verdad de verdad
p ¬p
V F
F V
Ejemplo. Encuentre la negación de las expresiones siguientes:
i) Júpiter es un planeta
ii) El pizarrón es verde
iii) El número real x es negativo
iv) Algún elefante es de color rosa
v) Ningún pez respira fuera del agua
vi) Todos los leones son feroces
Solución:
i) Júpiter no es un planeta
ii) El pizarrón no es verde
iii) El número real x no es negativo o también El número real x es positivo ó cero
iv) Ningún elefante es de color rosa
v) Algún pez respira fuera del agua
vi) Algún león no es feroz
Nota: Las tres últimas proposiciones se derivan de proposiciones abiertas que veremos en la sección 1.4
Calculo de Predicados Definicion.
La conjunción de las proposiciones p, q es la operación binaria que tiene por resultado p y q, se representa por p^q, y su tabla de verdad es:
La conjunción nos sirve para indicar que se cumplen dos condiciones simultáneamente, así por ejemplo si tenemos:
La función es creciente y está definida para los números positivos, utilizamos
p ^ q, donde
p: la función es creciente
q: la función esta definida para los números positivos
Así también: p ^ q, donde
p: el número es divisible por 3
q: el número está representado en base 2
se lee: El número es divisible entre 3 y está representado en base 2.
Nota: Observamos que para la conjunción p ^ q sea verdadera las dos expresiones que intervienen deben ser verdaderas y sólo en ese caso como se indica por su tabla de verdad.
La disyunción de dos proposiciones p, q es la operación binaria que da por resultado p ó q, notación p v q, y tiene la siguiente tabla:
p q p v q
|| V || V || V ||
V F V
F V V
F F F
Con la disyunción a diferencia de la conjunción, representamos dos expresiones y que afirman que una de las dos es verdadera, por lo que basta con que una de ellas sea verdaera para que la expresión p ∨ q sea verdadera.
Así por ejemplo la expresión: el libro se le entregará a Juan o el libro se le entregará a Luis significa que si va uno de los dos, el libro se le entrega, si van los dos también se entrega y solamente en caso de que no vaya ninguno de los dos no se debe entregar.
Aquí debemos tener cuidado, porque en español muchas veces utilizamos la disyunción para representar otros operadores que aparentemente son lo mismo, pero que tienen diferente significado.
En español tenemos tres casos de disyunción:
La llamada y/o bancaria, lógica o matemática, que es la misma y se utliza en computación como el operador OR, este operadorcorresponde al mencionado anteriormente p v q y ya se mostró su tabla de verdad.
La o excluyente, que algunos también le llaman o exclusiva, y que indica que una de las dos proposiciones se cumple, pero no las dos. Este caso corresponde por ejemplo a: Hoy compraré un libro o iré al cine; se sobrentiende que una de las dos debe ser verdadera, pero no la dos. Se representa por p XOR q y su tabla de verdad es:
p q p XOR q
V V F
V F V
F V V
F F F
Por último, también es muy común utilizar una disyunción como la siguiente: El menú incluye café o té. En este caso se esta dando una disyuntiva diferente pues no se pueden las dos simultáneamente como en el caso anterior, pero aquí si es válido el caso donde las dos son falsas. Es el caso “no ámbas”, se puede representar por p § q y su tablas es
p q p § q
V V F
V F V
F V V
F F V
Nota: El último símbolo no es estándar y puede haber varias formas de representarlo.
Un buen ejercicio consiste en enunciar varias expresiones del español que utilizando los conectivos y o para analizar cuál de los operadores es.
Hay que tener mucho cuidado cuando se traduce del lenguaje usual por las costumbres, muchas veces depende del contexto o de la situación específica en la que se usan los conectivos, por ejemplo si decimos: Se pueden estacionar alumnos y maestros, en realidad se está queriendo decir un operador disyuntivo, en este caso la o matemática, o sea el primer operador que corresponde a la primera tabla de esta sección.
La condicional de dos proposiciones p, q da lugar a la proposición; si p entonces q, se representa por p → q, y su tabla de verdad está dada por:
p q p→q
V V V
V F F
F V V
F F V
Con respecto a este operador binario, lo primero que hay que destacar es que no es conmutativo, a diferencia de los dos anteriores la conjunción y la disyunción. El único caso que resulta falso es cuando el primero es verdadero y el segundo falso.
Por ejemplo, si p es llueve y q es hay nubes entonces:
p → q es si llueve entonces hay nubes.
También cabe señalar que este viene a ser el operador más importante en el proceso deductivo y que la mayoría de las leyes de inferencia y las propiedades en matemáticas se pueden enunciar utilizando este operador.
La bicondicional de dos proposiciones p, q da lugar a la proposición; p si y sólo si q, se representa por p ↔ q su tabla de verdad está dada por:
p q p ↔ q
V V V
V F F
F V F
F F V
Jerarquia de Operadores.
Combinando los operadores anteriores podemos formar nuevas expresiones.
En términos formales la negación de p, deberá ser ( ¬ p), así como la conjunción de p y q sería (p ^ q). Con el uso de paréntesis evitamos la ambiguedad, por ejemplo ¬p ^ q podría significar dos cosas distintas
Por un lado podría significar: (( ¬ p) ^ q) O también: ( ¬ (p ^ q)).
En la práctica para no usar tantos paréntesis se considera que el operador ¬ tiene jerarquia sobre ^, v, →, ↔. Así ¬ p ^ q significa (( ¬ p)^ q).
En algunos casos se considera ^, v tienen mayor jerarquía que ↔ por lo que p ↔ q v r sería (p ↔ (q v r)) y también que ^ tiene prioridad sobre v, por lo que p ^ q v r sería (p ^ q) v r.
Así por ejemplo, en electrónica, para representar circuitos lógicos se utiliza + en lugar de v y · en lugar de ^.
Por lo que p·q+r es ((p ^ q) v r).
En estos apuntes no se considerará jerarquía en ninguno de los operadores binarios ^, v, →, ↔ por lo que utilizaremos paréntesis. Sólo ¬ tiene prioridad sobre los demás operadores. Esto nos ahorrá algunos paréntesis, por ejemplo: ((( ¬ p) ^ q) v r) se representa por ( ¬ p ^ q) v r.
Contrucción de Tablas de Verdad
Como ya sabemos la sintaxis en lógica es la forma correcta de escribir una fórmula y la semántica es lo que significa. Como en lógica solamente tenemos dos valores una fórmula solamente puede ser verdadera o falsa. Para determinar su valor seguimos las reglas simples que dimos en las definiciones básicas de acuerdo a su tabla de verdad. Esto lo hacemos mediante interpretaciones. Una interpretación de una fórmula es un conjunto de valores que se les asignan a sus proposiciones atómicas.
Al interpretar una fórmula lo que finalmente vamos a obtener es un valor de verdad, bien sea verdadero o falso. Pero para poder encontrarlo muchas veces el proceso en laborioso porque puede estar formada por varias proposiciones atómicas. Primeramente se le asignan valores de verdad a los átomos y se puede encontrar el valor de la expresión.
Si deseamos hacerlo en general, debemos analizar todas las posibilidades, esto se puede hacer construyendo una tabla de verdad. Para fines prácticos cuando se tienen varios átomos las tablas de verdad no resultan prácticas por lo que analizaremos solamente expresiones con tres átomos como máximo.
Por supuesto que se puede construir una tabla para un número mayor de átomos, pero notemos que por cada átomo que se aumente el número de renglones se duplica. Esto es, para un átomos son dos renglones, para dos átomos son cuatro, para tres átomos son ocho, para cuatro dieciséis, etc.
Algoritmo para construir una tabla de verdad de una fórmula en lógica de proposiciones.
1. Escribir la fórmula con un número arriba de cada operador que indique su jerarquía. Se escriben los enteros positivos en orden, donde el número 1 corresponde al operador de mayor jerarquía. Cuando dos operadores tengan la misma jerarquía, se le asigna el número menor al de la izquierda.
2. Construir el árbol sintáctico empezando con la fórmula en la raíz y utilizando en cada caso el operador de menor jerarquía. O sea, del número mayor al menor.
3. Numerar las ramas del árbol en forma secuencial empezando por las hojas hacia la raíz, con la única condición de que una rama se puede numerar hasta que estén numerados los hijos. Para empezar con la numeración de las hojas es buena idea hacerlo en orden alfabético, así todos obtienen los renglones de la tabla en el mismo orden para poder comparar resultados.
4. Escribir los encabezados de la tabla las fórmulas siguiendo la numeración que se le dió a las ramas en el árbol sintáctico.
5. Asignarle a los átomos, las hojas del árbol, todos los posibles valores de verdad de acuerdo al orden establecido. Por supuesto que el orden es arbitrario, pero como el número de permutaciones es n!, conviene establecer un orden para poder comparar resultados fácilmente.
6. Asignar valor de verdad a cada una de las columnas restantes de acuerdo al operador indicado en el árbol sintáctico utilizando la tabla de verdad correspondiente del Tema 1.3 Conexiones Logicas y Jerarquias. Conviene aprenderse de memoria las tablas de los operadores, al principio pueden tener un resumen con todas las tablas mientras se memorizan.
7. La última columna, correspondiente a la fórmula original, es la que indica los valores de verdad posibles de la fórmula para cada caso.
Ejemplo. Construya la tabla de verdad de las siguientes expresiones lógicas:
i) (p → ¬q) v (¬p v r)
ii) p → (q ^ r)
iii) (p → ¬ r) ↔ (q v p)
iv) ¬(p ¬ q) → ¬ r
v) (¬p ^ q) → ¬(q v ¬r)
Solución:
i) Seguimos los pasos del algoritmo con la fórmula (p → ¬q) v (¬p v r)
1. Vemos que los operadores de los paréntesis tienen mayor jerarquía, empezamos por el paréntesis izquierdo por lo que la fórmula con jerarquías marcadas sería:
Attach:TablasVerdad11.jpg Δ
2. Contruir el arbol Sintáctico empezando a descomponer por el operador con el número mayor, seguir en orden descendiente hasta el último que es el que tiene el número 1.
Attach:TablasVerdad12.jpg Δ
3. Numerar las ramas del árbol
Attach:TablasVerdad13.jpg Δ
4. Escribir los encabezados de la tabla utilizando las fórmulas en el árbol siguiendo la numeración del paso 3.
5. Asignar valores de verdad a los átomos, en este caso, las tres primeras columas.
1 2 3
p q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F
6. Asignar los valores de verdad a la ¬ q.
1 2 3 4
p q r ¬ q
V V V F
V V F F
V F V V
V F F V
F V V F
F V F F
F F V V
F F F V
7. Asignar los valores de verdad a la ¬ p.
1 2 3 4 5
p q r ¬ q ¬ p
V V V F F
V V F F F
V F V V F
V F F V F
F V V F V
F V F F V
F F V V V
F F F V V
8. Asignar los valores de verdad basados en la tabla de la condicional con p(condicion 1) → ¬q(condicion 4).
1 2 3 4 5 6
p q r ¬ q ¬ p p → ¬q
V V V F F F
V V F F F F
V F V V F V
V F F V F V
F V V F V V
F V F F V V
F F V V V V
F F F V V V
9. Asignar los valores de verdad basados en la tabla disyuncion con la ¬p(condicion 4) v r(condicion 3).
1 2 3 4 5 6 7
p q r ¬ q ¬ p p → ¬q ¬p v r
V V V F F F V
V V F F F F F
V F V V F V V
V F F V F V F
F V V F V V V
F V F F V V V
F F V V V V V
F F F V V V V
10. Completar el resto de las condiciones utilizando las definiciones de los operadores,p → ¬q (condicion 6), v, ¬p v r (condicion 7).
1 2 3 4 5 6 7 8
p q r ¬ q ¬ p p → ¬q ¬p v r (p → ¬q) v (¬p v r)
V V V F F F V V
V V F F F F F F
V F V V F V V V
V F F V F V F V
F V V F V V V V
F V F F V V V V
F F V V V V V V
F F F V V V V V
11. La última columna es el resultado da cada interpretación establecida en los primeros tres renglones.
Los demás problemas son similares y se obtienen las tablas siguientes.
FALTA PONER LOS ÁRBOLES SINTÁCTICOS DE LOS EJEMPLOS 2 AL 5.
ii)
Attach:TablasVerdad2.jpg Δ
1 2 3 4 5
p q r q v r p → (q v r)
V V V V V
V V F V F
V F V V V
V F F V F
F V V V V
F V F V V
F F V F V
F F F F V
iii)
Attach:TablasVerdad3.jpg Δ
1 2 3 4 5 6 7
p q r ¬ r p → ¬ r q ∨ r (p → ¬ r) ↔ (q v r)
V V V F F V F
V V F V V V V
V F V F F V F
V F F V V F V
F V V F V V V
F V F V V V V
F F V F V V F
F F F V V F F
iv)
Attach:TablasVerdad14.jpg Δ
1 2 3 4 5 6 7 8
p q r ¬ q p ^ ¬ q ¬(p ^ ¬q) ¬ r ¬(p ^ ¬q) → ¬ r
V V V F F V F F
V V F F F V V V
V F V V V F F V
V F F V V F V V
F V V F F V F F
F V F F F V V V
F F V V F V F F
F F F V F V V V
v)
Attach:TablasVerdad5.jpg Δ
1 2 3 4 5 6 7 8 9
p q r ¬r ¬p q v ¬r ¬p ^ q ¬(q v ¬r) (¬p ^ q) → ¬(q v ¬r)
V V V F F V F F V
V V F V F V F F V
V F V F F F F V V
V F F V F F F V V
F V V F V V V F F
F V F V V V V F F
F F V F V V F F V
F F F V
EJEMPLOS DE TABLAS DE VERDAD
martes, 17 de agosto de 2010
TABLAS DE VERDAD
La tabla de verdad de una fórmula es una tabla en la que se presentan todas las posibles interpretaciones de las variables proposicionales que constituyen la fórmula y el valor de verdad de la fórmula completa para cada interpretación. Por ejemplo, la tabla de verdad para la fórmula
jueves, 5 de agosto de 2010
ECUACIONES BOOLEANAS
También pueden ser construidos con compuertas NAND, compuertas NOR, compuerta XOR, que son una combinación de las tres compuertas básicas.
La operación de los circuitos combinacionales se entienden escribiendo las ecuaciones booleanas y sus tablas de verdad.
Ejemplo de ecuación booleana: F = A . B + A . B
A B F
0 0 0
0 1 1
1 0 1
1 1 0
Suscribirse a:
Entradas (Atom)