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
ALGEBRA DE BOOLE
OPERACIONES DEL ALGEBRA DE BOOLE
El álgebra booleana es un sistema matemático deductivo centrado en los valores cero y uno (falso y verdadero). Un operador binario " º " definido en éste juego de valores acepta un par de entradas y produce un solo valor booleano, por ejemplo, el operador booleano AND acepta dos entradas booleanas y produce una sola salida booleana.
Para cualquier sistema algebraico existen una serie de postulados iniciales, de aquí se pueden deducir reglas adicionales, teoremas y otras propiedades del sistema, el álgebra booleana a menudo emplea los siguientes postulados:
Cerrado. El sistema booleano se considera cerrado con respecto a un operador binario si para cada par de valores booleanos se produce un solo resultado booleano.
Conmutativo. Se dice que un operador binario " º " es conmutativo si A º B = B º A para todos los posibles valores de A y B.
Asociativo. Se dice que un operador binario " º " es asociativo si (A º B) º C = A º (B º C) para todos los valores booleanos A, B, y C.
Distributivo. Dos operadores binarios " º " y " % " son distributivos si A º (B % C) = (A º B) % (A º C) para todos los valores booleanos A, B, y C.
Identidad. Un valor booleano I se dice que es un elemento de identidad con respecto a un operador binario " º " si A º I = A.
Inverso. Un valor booleano I es un elemento inverso con respecto a un operador booleano " º " si A º I = B, y B es diferente de A, es decir, B es el valor opuesto de A.
Para nuestros propósitos basaremos el álgebra booleana en el siguiente juego de operadores y valores:
- Los dos posibles valores en el sistema booleano son cero y uno, a menudo llamaremos a éstos valores respectivamente como falso y verdadero.
- El símbolo · representa la operación lógica AND. Cuando se utilicen nombres de variables de una sola letra se eliminará el símbolo ·, por lo tanto AB representa la operación lógica AND entre las variables A y B, a esto también le llamamos el producto entre A y B.
- El símbolo "+" representa la operación lógica OR, decimos que A+B es la operación lógica OR entre A y B, también llamada la suma de A y B.
- El complemento lógico, negación ó NOT es un operador unitario, en éste texto utilizaremos el símbolo " ' " para denotar la negación lógica, por ejemplo, A' denota la operación lógica NOT de A.
- Si varios operadores diferentes aparecen en una sola expresión booleana, el resultado de la expresión depende de la procedencia de los operadores, la cual es de mayor a menor, paréntesis, operador lógico NOT, operador lógico AND y operador lógico OR. Tanto el operador lógico AND como el OR son asociativos por la izquierda. Si dos operadores con la misma procedencia están adyacentes, entonces se evalúan de izquierda a derecha. El operador lógico NOT es asociativo por la derecha.
Utilizaremos además los siguientes postulados:
P1 El álgebra booleana es cerrada bajo las operaciones AND, OR y NOT
P2 El elemento de identidad con respecto a · es uno y con respecto a + es cero. No existe elemento de identidad para el operador NOT
P3 Los operadores · y + son conmutativos.
P4 · y + son distributivos uno con respecto al otro, esto es, A· (B+C) = (A·B)+(A·C) y A+ (B·C) = (A+B) ·(A+C).
P5 Para cada valor A existe un valor A' tal que A·A' = 0 y A+A' = 1. Éste valor es el complemento lógico de A.
P6 · y + son ambos asociativos, ésto es, (AB) C = A (BC) y (A+B)+C = A+ (B+C).
Es posible probar todos los teoremas del álgebra booleana utilizando éstos postulados, además es buena idea familiarizarse con algunos de los teoremas más importantes de los cuales podemos mencionar los siguientes:
Teorema 1: A + A = A
Teorema 2: A · A = A
Teorema 3: A + 0 = A
Teorema 4: A · 1 = A
Teorema 5: A · 0 = 0
Teorema 6: A + 1 = 1
Teorema 7: (A + B)' = A' · B'
Teorema 8: (A · B)' = A' + B'
Teorema 9: A + A · B = A
Teorema 10: A · (A + B) = A
Teorema 11: A + A'B = A + B
Teorema 12: A' · (A + B') = A'B'
Teorema 13: AB + AB' = A
Teorema 14: (A' + B') · (A' + B) = A'
Teorema 15: A + A' = 1
Teorema 16: A · A' = 0
Los teoremas siete y ocho son conocidos como Teoremas de DeMorgan en honor al matemático que los descubrió.
Características:
Un álgebra de Boole es un conjunto en el que destacan las siguientes características:
1- Se han definido dos funciones binarias (que necesitan dos parámetros) que llamaremos aditiva (que representaremos por x
+ y) y multiplicativa (que representaremos por xy) y una función monaria (de un solo parámetro) que representaremos por x'.
2- Se han definido dos elementos (que designaremos por 0 y 1)
Y 3- Tiene las siguientes propiedades:
Conmutativa respecto a la primera función: x + y = y + x
Conmutativa respecto a la segunda función: xy = yx
Asociativa respecto a la primera función: (x + y) + z = x + (y +z)
Asociativa respecto a la segunda función: (xy)z = x(yz)
Distributiva respecto a la primera función: (x +y)z = xz + yz
Distributiva respecto a la segunda función: (xy) + z = (x + z)( y + z)
Identidad respecto a la primera función: x + 0 = x
Identidad respecto a la segunda función: x1 = x
Complemento respecto a la primera función: x + x' = 1
Complemento respecto a la segunda función: xx' = 0
Propiedades Del Álgebra De Boole
Idempotente respecto a la primera función: x + x = x
Idempotente respecto a la segunda función: xx = x
Maximalidad del 1: x + 1 = 1
Minimalidad del 0: x0 = 0
Involución: x'' = x
Inmersión respecto a la primera función: x + (xy) = x
Inmersión respecto a la segunda función: x(x + y) = x
Ley de Morgan respecto a la primera función: (x + y)' = x'y'
Ley de Morgan respecto a la segunda función: (xy)' = x' + y'
Función Booleana
Una función booleana es una aplicación de A x A x A x....A en A, siendo A un conjunto cuyos elementos son 0 y 1 y tiene estructura de álgebra de Boole.
Supongamos que cuatro amigos deciden ir al cinesi lo quiere la mayoría. Cada uno puede votar si o no. Representemos el voto de cada uno por xi. La función devolverá sí (1) cuando el numero de votos afirmativos sea 3 y en caso contrario devolverá 0.
Si x1 vota 1, x2 vota 0, x3 vota 0 y x4 vota 1 la función booleana devolverá 0.
Producto mínimo (es el número posible de casos) es un producto en el que aparecen todas las variables o sus negaciones.
El número posible de casos es 2n.
Siguiendo con el ejemplo anterior. Asignamos las letras A, B, C y D a los amigos. Los posibles casos son:
Votos Resultado
ABCD
1111 1
1110 1
1101 1
1100 0
1011 1
1010 0
1001 0
1000 0
0111 1
0110 0
0101 0
0100 0
0011 0
0010 0
0001 0
0000 0
Las funciones booleanas se pueden representar como la suma de productosmínimos (minterms) iguales a 1.
En nuestro ejemplo la función booleana será:
f(A,B,C,D) = ABCD + ABCD' + ABC'D + AB'CD + A'BCD
Diagramas De Karnaugh
Los diagramas de Karnaugh se utilizan para simplificar las funciones booleanas.
Se construye una tabla con las variables y sus valores posibles y se agrupan los 1 adyacentes, siempre que el número de 1 sea potencia de 2.
En esta página tienes un programa para minimización de funciones booleanas mediante mapas de Karnaugh
4. Álgebra Booleana y circuitos electrónicos
La relación que existe entre la lógica booleana y los sistemas de cómputo es fuerte, de hecho se da una relación uno a uno entre las funciones booleanas y los circuitos electrónicos de compuertas digitales. Para cada función booleana es posible diseñar un circuito electrónico y viceversa, como las funciones booleanas solo requieren de los operadores AND, OR y NOT podemos construir nuestros circuitos utilizando exclusivamente éstos operadores utilizando las compuertas lógicas homónimas
Un hecho interesante es que es posible implementar cualquier circuito electrónico utilizando una sola compuerta, ésta es la compuerta NAND
Para probar que podemos construir cualquier función booleana utilizando sólo compuertas NAND, necesitamos demostrar cómo construir un inversor (NOT), una compuerta AND y una compuerta OR a partir de una compuerta NAND, ya que como se dijo, es posible implementar cualquier función booleana utilizando sólo los operadores booleanos AND, OR y NOT. Para construir un inversor simplemente conectamos juntas las dos entradas de una compuerta NAND. Una vez que tenemos un inversor, construir una compuerta AND es fácil, sólo invertimos la salida de una compuerta NAND, después de todo, NOT ( NOT (A AND B)) es equivalente a A AND B. Por supuesto, se requieren dos compuertas NAND para construir una sola compuerta AND, nadie ha dicho que los circuitos implementados sólo utilizando compuertas NAND sean lo óptimo, solo se ha dicho que es posible hacerlo. La otra compuerta que necesitamos sintetizar es la compuerta lógica OR, ésto es sencillo si utilizamos los teoremas de DeMorgan, que en síntesis se logra en tres pasos, primero se reemplazan todos los "·" por "+" después se invierte cada literal y por último se niega la totalidad de la expresión:
A OR B
A AND B.......................Primer paso para aplicar el teorema de DeMorgan
A' AND B'.....................Segundo paso para aplicar el teorema de DeMorgan
(A' AND B')'..................Tercer paso para aplicar el teorema de DeMorgan
(A' AND B')' = A' NAND B'.....Definición de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita, bien hay dos buenas razones, la primera es que las compuertas NAND son las más económicas y en segundo lugar es preferible construir circuitos complejos utilizando los mismos bloques básicos. Observe que es posible construir cualquier circuito lógico utilizando sólo compuertas de tipo NOR (NOR = NOT(A OR B)). La correspondencia entre la lógica NAND y la NOR es ortogonal entre la correspondencia de sus formas canónicas. Mientras que la lógica NOR es útil en muchos circuitos, la mayoría de los diseñadores utilizan lógica NAND.
LOGICA DISCRETA
PROPOSICIONES LOGICA
Aunque existen lógicas polivalentes, en orden a la claridad del concepto, aquí consideramos únicamente el valor de Verdad o Falsedad.
Otro tipo de entes que se utilizan en computación que también está asociado a “dos” opciones, es lo que se conoce como expresiones booleanas. Estas expresiones, que deben su nombre a George Boole, se pueden ver caracterizadas como verdaderas ó falsas y de acuerdo a esta condición se desarrolla el estudio sobre dichos conceptos. Este tema se conoce como cálculo de proposiciones.
Un enunciado lingüístico (generalmente en la forma gramatical de una oración enunciativa) puede ser considerado como proposición lógica cuando es susceptible de ser verdadero o falso. “Es de noche”.Son A ,Ante ,bajo ,con ,contra ,de ,desde ,durante ,en ,entre ,hacia ,hasta ,para ,por ,segun ,sin ,sobre y tras
Los argumentos son una de las formas más comunes en matemáticas, en lógica y en computación de establecer razonamientos para llegar a la verdad. Si tenemos un conectivo lógico OR de dos valores de entrada y después un inversor, cuál es la salida. O si en un programa con una instrucción tipo if se tiene la condición X > 3 and X < 10 cómo se sabe si se ejecutó el comando. Desarrollo. La lógica matemática es la disciplina que trata de métodos de razonamiento. En un nivel elemental, la lógica proporciona reglas y técnicas para determinar si es o no valido un argumento dado. El razonamiento lógico se emplea en matemáticas para demostrar teoremas; en ciencias de la computación para verificar si son o no correctos los programas; en las ciencias física y naturales, para sacar conclusiones de experimentos; y en las ciencias sociales y en la vida cotidiana, para resolver una multitud de problemas. Ciertamente se usa en forma constante el razonamiento lógico para realizar cualquier actividad. Proposiciones y 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ógicas 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. Si símbolo es: {Ù, un punto (.), un paréntesis}. Se le conoce como la multiplicación lógica:
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:
p = q Ù r
Su tabla de verdad es como sigue:
q r p = q Ù r
1 1 1
1 0 0
0 1 0
0 0 0
Donde.
1 = verdadero
0 = falso
En la tabla anterior el valor de q=1 significa que el tanque tiene gasolina, r=1 significa que la batería tiene corriente y p = q Ù r=1 significa que el coche puede encender. Se puede notar que si q o r valen cero 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 eindica por medio de los siguientes símbolos: {Ú,+,È}. Se conoce como las suma lógica. Ejemplo.
Sea el siguiente enunciado “Una persona puede entrar al cine si compra su boleto u obtiene un pase”. Donde.
p: Entra al cine.
q: Compra su boleto.
r: Obtiene un pase.
q r p = q Ù r
1 1 1
1 0 0
0 1 0
0 0 0
q r
La única manera en la que no puede ingresar al cine (p=0), es que no compre su boleto (q=0) y que no obtenga un pase (r=0).
p =q Ú r
1 1 1
1 0 1
0 1 1
0 0 0
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.
La negación de está lloviendo en este momento (p=1), es no está lloviendo en este momento (p’=0)
p p’
1 0
0 1
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 con verdad el resultado es falso.
En este momento ya se pueden representar con notación lógica enunciados más complejos. Ejemplo
Sean las proposiciones:
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.
Como se menciono en el capitulo anterior, en computación se utiliza la representación binaria porque aparecen solo dos elementos distintos. El trabajar con solo 2 opciones facilita la implementación de los conceptos.
Otro tipo de entes que se utilizan en computación también esta asociado a “dos” opciones, es lo que se conoce como expresiones booleanas.
Estas expresiones, que deben su nombre a George Boole, se pueden ver caracterizadas como verdaderas ó falsas y de acuerdo a esta propiedad se desarrolla el estudio sobre dichos conceptos.
Empezaremos por clasificar las expresiones del lenguaje, distinguiendo lo que se puede considerar entre las experiencias booleanas y las que no.
EXPRESIONES:
Proposiciones lógicas
EXPRESIONES
BOLEANAS: Proposiciones abiertas
Frases indeterminadas
PROPOSICIÓN LÓGICA.
Es cualquier expresión que puede ser verdadera o falsa pero nunca ambas.
operaciones logicas
Las principales operaciones lógicas son: conjunción, disyunción, negación, condicional y Bicondicional.
A cada una de estas operaciones lógicas le corresponde una tabla de verdad.
p q
p Ù q
V V
V F
F V
F F
V
F
F
F
Conjunción. Dos proposiciones simples p y q relacionadas por el conectivo lógico "y" conforman la proposición compuesta llamada conjunción, la cual se simboliza así: p Ù q.
p q
p Ú q
V V
V F
F V
F F
V
V
V
F
Disyunción. Dos proposiciones simples p y q relacionadas por el conectivo lógico "O" conforman la proposición compuesta llamada disyunción, la cual se simboliza así: p Ú q.
~ p se lee: no p
o también: no es cierto que p
p
~ p
V
F
F
V
Negación. Dada una proposición simple p, esta puede ser negada y convertirse en otra proposición llamada negación de p, la cual se simboliza así:
p q
p Þ q
V V
V F
F V
F F
V
F
V
V
Condicional o Implicativa. Dos proposiciones simples p y q relacionadas por el conectivo lógico "entonces" conforman la proposición compuesta llamada condicional o implicativa, la cual se simboliza así: p Þ q:
Bicondicional. Dos proposiciones simples p y q relacionadas por el conectivo lógico "si y sólo si" conforman la proposición compuesta llamada conjunción, la cual se simboliza así: p « q.
p q
p Û q
V V
V F
F V
F F
V
F
F
V
proposicion simple
Es aquella que no se relaciona con otra. Ejemplo:
p: 17 es un número impar.
q: El Solno es una estrella.
r: La maca es una planta oriunda del Perú.
s: La suma de dos números pares es otro número impar.
CONECTIVOS LÓGICOS
Los conectivos lógicos sirven para enlazar dos o más proposiciones. Estos conectivos son "y", "o", "no es cierto que", "entonces", "si y solo sí", cuyos símbolos se ven en el siguiente cuadro:
CONECTIVO LÓGICO
SÍMBOLO
Y
O
No es cierto que
Entonces
Si y solo sí
Ù
Ú
~
Þ
Û
Suscribirse a:
Entradas (Atom)