Implementación de Conjuntos en C/C++

Presentamos ahora la implementación de conjuntos en el lenguaje C/C++, el cual no cuenta con un tipo de datos específico, tal como el SET de Pascal, por lo que hemos recurrido a los operadores lógicos binarios, ya descritos en anteriores entradas (1)(2). 

Cada elemento de un conjunto de éstos está representado por un bit, y solamente permite datos de tipo base enteros, concretamente unsigned char. Se agrupan hasta 128 datos almacenados en un arreglo de 16 elementos. Veamos el código:

//Conjuntos.Cpp

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

/* Definiciones */

#define M 128   // Elementos del conjunto
#define N 16     // Elementos del arreglo. M /8

unsigned char A[N], B[N], *C;
unsigned char x, y;

/* Prototipos de funciones */
void Iniciar (unsigned char C[]);
unsigned char byte (unsigned char x);
unsigned char bit (unsigned char x);
unsigned char Pertenece (unsigned char x, unsigned char C[]);
void Incluir (unsigned char x, unsigned char C[]);
void Excluir (unsigned char x, unsigned char C[]);
unsigned char *Union(unsigned char A[], unsigned char B[]);
unsigned char *Interseccion (unsigned char A[], unsigned char B[]);
unsigned char *Diferencia(unsigned char A[], unsigned char B[]);
unsigned char *Complemento (unsigned char A[]);
unsigned char Iguales(unsigned char A[], unsigned char B[]);
void Escribir (unsigned char C[]);
void Listar (unsigned char C[]);

void main() {
    // Iniciamos los conjuntos A y B
    Iniciar(A); Iniciar(B);
  
    // Agregamos algunos elementos al conjunto A
    for (x = 1; x < M; x *= 2)           // Potencias de 2
       Incluir(x, A);
    printf("A = "); Escribir(A);
  
    // Agregamos al conjunto B los multiplos de 20
    for (x = 20; x < M; x += 20)
        Incluir(x, B);
    printf("B = "); Escribir(B);

    // Hallamos la union de A y B en C
    C = Union(A, B);
    printf("Union de A y B = "); Escribir(C);

    // Hallamos la interseccion de A y B en C
    C = Interseccion(A, B);
    printf("Interseccion de A y B = "); Escribir(C);

    // Hallamos la diferencia de A y B en C
    C = Diferencia(A, B);
    printf("Diferencia de A y B = "); Escribir(C);

    // Hallamos complemento del conjunto A
    C = Complemento(A);
    printf("Complemento de A = "); Escribir(C);

    // Determinamos si los conjuntos A y B son iguales o diferentes
    if (Iguales(A, B))
        printf("\nA y B son iguales. \n");
    else
        printf("\nA y B son diferentes. \n");
    printf("\nA = "); Escribir(A);
    printf("\nB = "); Escribir(B);

    // Determinamos si los conjuntos A y C son iguales o diferentes
    C = A;
    if (Iguales(A, C))
        printf("\nA y C son iguales. \n");
    else
        printf("\nA y C son diferentes. \n");
    printf("\nA = "); Escribir(A);
    printf("\nC = "); Escribir(C);

    // Eliminamos algunos elementos del conjunto A
    Excluir(8, A); Excluir(32, A);
    printf("Despues de eliminar 8 y 32 de A.\n");
    printf("\nA = "); Escribir(A);
    getch();
}

/* ************************************************ */

/* Iniciar el conjunto */
void Iniciar (unsigned char C[])  {
    unsigned char i;
    for (i = 0; i < N; i++)
        C[i] = 0;
}

/* Determinar byte que ocupa el elemento x */
unsigned char byte (unsigned char x)  {
    return (x / 8);
}

/* Determinar el bit del byte que ocupa el elemento */
unsigned char bit (unsigned char x) {
    return (x % 8);
}

/* Incluir un elemento al conjunto */
void Incluir (unsigned char x, unsigned char C[]) {
    C[byte(x)] |= (1 << bit(x));
}

/* Excluir un elemento del conjunto */
void Excluir (unsigned char x, unsigned char C[]) {
    C[byte(x)] &= (255 - (1 << bit(x)));
}

/* Determinar si un elemento pertenece al conjunto */
unsigned char Pertenece (unsigned char x, unsigned char C[]) {
    if (C[byte(x)] & (1 << bit(x)))  return 1;
    else return 0;
}

/* Unión de dos conjuntos */
unsigned char *Union(unsigned char A[], unsigned char B[]) {
unsigned char i, *C, *D;
    C = (unsigned char *)malloc(N);
    D = C;
    for (i = 0; i < N; i++)  {
        *C = A[i] | B[i];
        C++;
    }
    return D;
}

/* Intersección de dos conjuntos */
unsigned char *Interseccion (unsigned char A[], unsigned char B[]) {
unsigned char i, *C, *D;
    C = (unsigned char *) malloc(N);
    D = C;
    for (i = 0; i < N; i++)  {
        *C = A[i] & B[i];
        C++;
    }
    return D;
}

/* Diferencia entre dos conjuntos */
unsigned char *Diferencia(unsigned char A[], unsigned char B[]) {
unsigned char i, *C, *D;
    C = (unsigned char *)malloc(N);
    D = C;
    for (i = 0; i < N; i++ )  {
        *C = A[i] & ~B[i];
        C++;
    }
    return D;
}

/* Hallar el complemento de un conjunto */
unsigned char *Complemento (unsigned char A[]) {
unsigned char i, *C, *D;
    C = (unsigned char *) malloc(N);
    D = C;
    for (i = 0; i < N; i++)  {
        *C = ~A[i];
        C++;
    }
    return D;
}

/* Determinar si dos conjuntos son iguales */
unsigned char Iguales(unsigned char A[], unsigned char B[]) {
unsigned char i;
    for (i = 0; i < N; i++)
        if (A[i] != B[i])  return 0;
    return 1;
}

// Determinar si un conjunto esta vacio
unsigned char Vacio(unsigned char C[]) {
unsigned char x;
    for (x = 0; x < N; x++)
        if (C[x] != 0)  return 0;
    return 1;
}

/* Escribir conjunto */
void Escribir (unsigned char C[]) {
unsigned char x;
    if  (!Vacio(C))  {
        printf("{ ");
        for (x = 0; x < M; x++)
            if (Pertenece(x, C))  printf("%u, ", x);
        printf("\b\b }"); // Borra la coma y el espacio anteriores
    }
    else  printf("{ }");
    printf("\n\n");
}

Implementación de Conjuntos en Pascal

El lenguaje Pascal cuenta con el tipo de datos SET que permite manejar información aplicando los conceptos básicos de la Teoría de Conjuntos. La definición de una estructura de este tipo tiene la forma siguiente:

TYPE nombre = SET OF tipo_base;

Donde tipo_base puede ser cualquier tipo ordinal, incluyendo los enumerados y los subrangos, pero con la limitación de un máximo de 255 elementos. Algunos ejemplos de conjuntos serían los siguientes:

TYPE  
     Dias = (Lunes, Martes, Miercoles, Jueves, Viernes, Sabado, Domingo);
     Puntos = 1..20;

     Conjunto1 = SET OF Dias;
     Conjunto2 = SET OF Puntos;
     Conjunto3 = SET OF BYTE;  

VAR
     A : Conjunto1;
     B : Conjunto2;
     C : Conjunto3;

Para representar un conjunto por extensión en Pascal se utilizan los símbolos [ y ], por ejemplo:

A := [Lunes, Jueves, Sabado];
B := [5, 9, 12, 16, 18];
C := [0..9, 15, 25, 44, 80..99];

Como podrán ver, pueden usarse subrangos en la enumeración de los elementos de un conjunto, tal como se permite en las matemáticas. Para representar el conjunto vacío se escriben los corchetes sin elementos, como en el siguiente ejemplo:

A := [ ];

Las funciones básicas de conjunto se ejecutan mediantes los siguientes operadores:

Unión :              +
Intersección :   *
Diferencia :       -
Subconjunto :   <=        
Pertenencia :   IN

Como muestra, presentamos un programa en Pascal donde se aplican algunas de estas funciones.

PROGRAM Conjuntos;
     USES CRT;
     
     TYPE Conjunto = SET OF Byte;
     
     VAR   A, B, C, D : Conjunto;
                N : ARRAY[1..100] OF BYTE;
                k, y : INTEGER;

(* Escribe los elementos de un conjunto *)
PROCEDURE EscribirConjunto(S : Conjunto);
     VAR  k : BYTE;
Begin
    IF NOT (S = []) THEN
    begin
        Write('{ ');
        For k := 0 TO 255 DO
            IF k IN S THEN Write(k, ', ');
        Writeln(CHR(8), CHR(8),  ' }');
    end
    ELSE
    Writeln('{ }');
    Writeln; Writeln;
End;

(* Incluye elementos en el conjunto A *)
PROCEDURE IncluirElementos;
     VAR x, y : BYTE;
Begin
    REPEAT
         ClrScr;
         gotoXY(10, 10); Write('Escriba un número (0 - 255) : ');
         Readln(x);
         A := A + [x];
         gotoXY(10, 12); Write('Desea continuar (1 = Si, 2 = No) ? ');
         Readln(y);
    UNTIL (y = 2);
End;

(* Incluir en el conjunto B los números potencia de 2 *)
PROCEDURE CrearConjunto;
     VAR k : INTEGER;
Begin
    k := 2;
    WHILE (k <= 255) DO
    begin
        B := B + [k];
        k := k * 2;
    end;
End;

(* Rellenar un arreglo de números aleatorios sin repeticiones *)
PROCEDURE RellenarArreglo;
     VAR i, j, k, x, t : BYTE;
              S : Conjunto;
Begin
    S := []; (* Inicialmente el conjunto está vacío *)
    Randomize;
    FOR k := 1 TO 100 DO
    begin
        REPEAT
             x := Random(256);       (* El tipo BYTE acepta 256 valores. *)
        UNTIL NOT (x IN S);      (* Evita que hayan elementos repetidos. *)
        N[k] := x;
        S := S + [x];                        (* Incorporamos x al conjunto *)
    end;

(* Ordenamos el arreglo ascendentemente *)
FOR i := 1 TO 99 DO
     FOR j :=  i + 1 TO 100 DO
          IF N[i] > N[j] THEN
          begin
              t := N[i];
              N[i] := N[j];
              N[j] := t;
          end;
End;

PROCEDURE EscribirAyB;
Begin
    ClrScr;
    Write('A = '); EscribirConjunto(A);
    Write('B = '); EscribirConjunto(B);
    ReadKey;
End;

PROCEDURE OperacionesBasicas;
Begin
    ClrScr;
    A := [2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
    B := [3, 6, 9, 12, 15, 18, 21, 24, 27, 30];
    gotoXY(4, 10); Write('A = '); EscribirConjunto(A);
    gotoXY(4, 12); Write('B = '); EscribirConjunto(B);

    (* Unión de los conjuntos A y B *)
    C := A + B;
    gotoXY(4, 14); Write('A U B = '); EscribirConjunto(C);
    
    (* Intersección de los conjuntos A y B *)
    C := A * B;
    gotoXY(4, 16); Write('A ', CHR(239), ' B = '); EscribirConjunto(C);

    (* Diferencia entre los conjuntos A y B *)
    C := A - B;
    gotoXY(4, 18); Write('A - B = '); EscribirConjunto(C);
    ReadKey;
End;

PROCEDURE OtrasOperaciones;
Begin
    ClrScr;
    (* A es el conjunto de los pares *)
    A := [];
    k := 2;
    WHILE (k <= 255) DO
    begin
        A := A + [k];
        k := k + 2;
    end;
    
    (* C es el complemento de A *)
    C := [];
    FOR k := 0 TO 255 DO
         IF NOT (k IN A) THEN
            C := C + [k];
    
    (* D es el conjunto de los múltiplos de 4 *)
    D := [];
    k := 4;
    WHILE (k <= 255) DO
    begin
        D := D + [k];
        k := k + 4;
    end;
    Write('A = '); EscribirConjunto(A);
    Write('B = '); EscribirConjunto(B);
    Write('C = '); EscribirConjunto(C);
    Write('D = '); EscribirConjunto(D);

    (* D es subconjunto de A *)
    IF D <= A THEN         Writeln('D es subconjunto de A')
    ELSE
       Writeln('D no es subconjunto de A');
    ReadKey;
End;

PROCEDURE Arreglos;
Begin
    ClrScr;
    (* Un arreglo de 100 elemetos sin repeticiones *)
    RellenarArreglo;
    Writeln('Arreglo N: ');
    For k := 1 TO 100 DO
        Write(N[k]:4);
    ReadKey;
End;

PROCEDURE VaciarConjuntos;
Begin
    A := [];
    B := [];
    C := [];
    D := [];
End;

BEGIN
     REPEAT
          ClrScr;
           gotoXY(10, 4); Write('1. Incluir Elementos en A');
           gotoXY(10, 6); Write('2. Crear Conjunto B');
           gotoXY(10, 8); Write('3. Escribir A y B');
           gotoXY(10, 10); Write('4. Operaciones Básicas');
           gotoXY(10, 12); Write('5. Otras Operaciones');
           gotoXY(10, 14); Write('6. Arreglos');
           gotoXY(10, 16); Write('7. Vaciar Conjuntos');
           gotoXY(10, 18); Write('0. Salir');
           gotoXY(10, 20); Write('Su Selección --> ');
          Readln(y);
          CASE y OF
               1 : IncluirElementos;
               2 : CrearConjunto;
               3 : EscribirAyB;
               4 : OperacionesBasicas;
               5 : OtrasOperaciones;
               6 : Arreglos;
               7 : VaciarConjuntos;
               0 : Exit;
          End;
     UNTIL y = 0;
END.

TEORÍA DE CONJUNTOS - Conceptos Básicos

Operadores Lógicos Binarios – Segunda Parte

Presentamos ahora algunas aplicaciones utilizando los operadores lógicos binarios, implementando una biblioteca de funciones de utilidad general, y un pequeño programa demostrativo de dichas funciones, las cuales pasamos a describir brevemente, aclarando que los números manejados son del tipo unsigned char, es decir, números enteros positivos de un byte.

printbits: Recibe un número en decimal y lo escribe en binario. Utiliza la función condicional implícita.

onoff: Recibe un número en decimal y la posición de un bit, y determina si ese bit está encendido (1) o apagado (0).

put_on: Recibe un número en decimal y la posición de un bit y lo enciende, es decir, lo convierte en 1.

put_off: Recibe un número en decimal y la posición de un bit y lo apaga, es decir, lo convierte en 0.

right_rot : Recibe un número en decimal (x) y un número entre 0 y 7 (n), y rota n posiciones a la derecha los bits de x.

left_rot : Recibe un número en decimal (x) y un número entre 0 y 7 (n), y rota n posiciones a la izquierda los bits de x.

change_nibbles: Recibe un número en decimal e Intercambia sus nibbles.

right_nibble: Recibe un número en decimal y devuelve su nibble derecho

left_nibble: Recibe un número en decimal y devuelve su nibble izquierdo


// Biblioteca de funciones de manipulacion de bits
// bits.h

#include <stdio.h>

// Escribe un numero en binario
void printbits(unsigned char x) {
for (int i = 7; i >= 0; i--)
   printf("%c", (x & (1 << i)) ? '1' : '0');
}

// Determina si el bit n de un byte esta encendido (1) o apagado (0)
unsigned char onoff(unsigned char x, unsigned char n) {
     if (x & (1 << n)) return 1;
     else return 0;
}

// Enciende un bit
unsigned char put_on(unsigned char x, unsigned char n) {
     return x |(1 << n);
}

// Apaga un bit
unsigned char put_off(unsigned char x, unsigned char n) {
     return x & (255 - (1 << n));
}

// Realiza la rotacion a la derecha
unsigned char right_rot(unsigned char x, unsigned char n) {
     return (x >> n) | (x << (8 - n));
}

// Realiza la rotacion a la izquierda
unsigned char left_rot(unsigned char x, unsigned char n) {
    return (x << n) | (x >> (8 - n));
}

// Intercambia los nibbles (4 bits) de un byte
unsigned char change_nibbles(unsigned char x) {
     return (x << 4) | (x >> 4);
}

// Obtiene el nibble izquierdo
unsigned char left_nibble(unsigned char x) {
     return x >> 4;
}

// Obtiene el nibble derecho
unsigned char right_nibble(unsigned char x) {
     return x & 15;
}

Listado 1. bits.h


Y ahora el programa ejemplo para demostrar el uso de las funciones de la biblioteca.

// Manejo de bits
// bits.cpp

#include <stdio.h>
#include <conio.h>
#include <C:\BC5\Programas\bits.h>  // Ubicar la ruta del archive de biblioteca

unsigned char m1, m2, n1, n2, x, y, z;

void NuevaLinea();

void main() {
    m1 = m2 = 59;
    n1 = n2 = 172;

    printf("Valores originales.\n");
    printf(" 76543210\n");
    printf("m1 = %3d = ", m1); printbits(m1); NuevaLinea();
    printf("n1 = %3d = ", n1); printbits(n1); NuevaLinea();

    printf("El bit 4 de m1 vale %d\n", onoff(m1, 5) ? 1 : 0);
    printf("El bit 4 de n1 vale %d\n", onoff(n1, 4) ? 1 : 0);
    NuevaLinea();

    printf("Se enciende el bit 6 de %3d. Resultado en x.\n", m2);
    x = put_on(m2, 6);
    printf(" 76543210\n");
    printf(" x = %3d = ", x); printbits(x); NuevaLinea();
    printf("El bit 6 de x vale %d\n", onoff(x, 4) ? 1 : 0);
    NuevaLinea();

    printf("Se apaga el bit 5 de %3d. Resultado en y.\n", n2);
    y = put_off(n2, 5);
    printf(" 76543210\n");
    printf(" y = %3d = ", y); printbits(y); NuevaLinea();
    printf("El bit 5 de y vale %d\n", onoff(y, 5));
    NuevaLinea();

    m2 = m1; n2 = n1;
    printf("%3d se rota 3 bits a la derecha. Resultado en x.\n", m2);
    x = right_rot(m2, 3);
    printf(" 76543210\n");
    printf("m2 = %3d = ", m2); printbits(m2); NuevaLinea();
    printf(" x = %3d = ", x); printbits(x); NuevaLinea();
    NuevaLinea();

    printf("%3d se rota 3 bits a la izquierda. Resultado en y.\n", n2);
    y = left_rot(n2, 3);
    printf(" 76543210\n");
    printf("n2 = %3d = ", n2); printbits(n2); NuevaLinea();
    printf(" y = %3d = ", y); printbits(y); NuevaLinea();
    NuevaLinea();

    m2 = m1; n2 = n1;
    printf("Se intercambian los nibbles de %3d. Resultado en x.\n", m2);
    x = change_nibbles(m2);
    printf(" 76543210\n");
    printf("m2 = %3d = ", m2); printbits(m2); NuevaLinea();
    printf(" x = %3d = ", x); printbits(x); NuevaLinea();
    NuevaLinea();

    printf("Se intercambian los nibbles de %3d. Resultado en y.\n", n2);
    y = change_nibbles(n2);
    printf(" 76543210\n");
    printf("n2 = %3d = ", n2); printbits(n2); NuevaLinea();
    printf(" y = %3d = ", y); printbits(y); NuevaLinea();
    NuevaLinea();

    m2 = m1; n2 = n1;
    printf("Se obtiene el nibble izquierdo de %3d. Resultado en x.\n", m2);
    x = left_nibble(m2);
    printf(" 76543210\n");
    printf("m2 = %3d = ", m2); printbits(m2); NuevaLinea();
    printf(" x = %3d = ", x); printbits(x); NuevaLinea();
    NuevaLinea();

    printf("Se obtiene el nibble derecho de %3d. Resultado en y.\n", n2);
    y = right_nibble(n2);
    printf(" 76543210\n");
    printf("n2 = %3d = ", n2); printbits(n2); NuevaLinea();
    printf(" y = %3d = ", y); printbits(y); NuevaLinea();
    NuevaLinea();

getch();

}

void NuevaLinea() {
    printf("\n");
}

Listado 2. bits.cpp

Operadores Lógicos Binarios – Primera Parte

En el siglo XIX el matemático inglés George Boole formuló todo un cuerpo de teoría donde hace una correspondencia entre los valores veritativos de la Lógica Formal, verdadero y falso, con los números 0 y 1 respectivamente, y la cual se conoce hoy como el Álgebra de Boole. En aquella época quizás muchos se preguntarían para qué podría servir semejante conjunto de definiciones, operaciones y leyes basadas sólo en 2 números. Un siglo después Claude Shannon encontró otra correspondencia, esta vez entre el Álgebra de Boole y los conmutadores electrónicos, introduciendo así el concepto de bit, abriendo de esta manera el camino a la aplicación práctica de esta teoría, que se plasmaría en los denominados circuitos lógicos, base de los sistemas de computación modernos. (1)

Casi todos los lenguajes de programación implementan tipos de datos lógicos o booleanos, y sus respectivos operadores, conocidos generalmente por sus nombres en inglés (and para la conjunción, or para la disyunción inclusiva, xor para la disyunción exclusiva y not para la negación. La implicación está implícita en la sentencia condicional if) (2). Pero también podemos realizar las operaciones lógicas a nivel de los bits de números enteros, a través de los operadores lógicos binarios (bitwise), además de otras como el desplazamiento y la rotación de bits, en lenguajes como C.

Primero veamos los operadores lógicos formales, o sea, aquellos cuyos operandos son expresiones lógicas como las obtenidas mediante los operadores relacionales; recordando además que en el lenguaje C y sus derivados el 0 representa el valor lógico falso y cualquier otro número, generalmente el 1, representa el valor lógico verdadero.

La conjunción se realiza mediante el operador &&, y como hemos visto, el resultado sólo es verdadero si ambos operadores son verdaderos. Ejemplo:

int m = 4, n = 5, p;
p = (m > 0) && (n == 5);
// ambas operaciones relacionales son verdaderas.
// p toma el valor de 1 (verdadero)

if ( (m > n) && (n > 1) ) p = 10;
else p = 20;
// p vale 20, ya que (m > n) es falso y, por tanto, la conjunción
// es falsa

La disyunción inclusiva se lleva a cabo con el operador ||, y es falsa solamente si los dos operandos son falsos. Ejemplo:

int a = 1, b = 2, c = 3;
if ( (a > b) || (c >= a + b) ) c++;
else c = 0;
// como (c >= a + b) es verdadera, la disyunción inclusiva
// es verdadera, y c se incrementa en 1 (c++)

La negación tiene como operador el signo ! e invierte el valor de su único operando lógico. Ejemplo:

int x = 3, y;
if (!x) y = 100;
else y = 10;
// como x es distinto de 0, o sea, verdadero, al negarlo con ! se
// convierte en falso. La variable y vale 10

En cuanto a los operadores lógicos binarios, en C/C++ tenemos los siguientes:

Conjunción Binaria: &.

Sean m = 59 (00111011₂) y n = 172 (10101100₂), entonces m & n será:

Disyunción Inclusiva Binaria: |

Sean m = 59 (00111011₂) y n = 172 (10101100₂), entonces m | n será:

Disyunción Exclusiva Binaria: ^:

Sean m = 59 (00111011₂) y n = 172 (10101100₂), entonces m ^ n será:



Negación Binaria (Conocida también como complemento a 1): ~.

Sea m = 59 (00111011₂), entonces ~n será:


Si observamos el valor resultante, comprobamos que se trata del número 196 en decimal, el cual sumado al operando original, o sea el 59, nos da 255, lo que es lo mismo que 2⁸ - 1. En general, el complemento a 1 de un número m de n bits será: ~m = 2ⁿ - m - 1. Si se elimina el -1, hablaríamos del complemento a 2; por lo tanto, el complemento a 2 de un número m es: ~m + 1, que es utilizado para representar números enteros negativos en la computadora.

Las operaciones de desplazamiento de bits permiten justamente eso, mover los bits de un byte, bien sea a la derecha o a la izquierda. Son de mucha utilidad en diversas situaciones, incluso para realizar operaciones aritméticas. Veamos su implementación en el lenguaje C:

Desplazamiento a la Izquierda: <<.

Sea m = 59 (00111011₂), entonces n >> 2 será:

Obsérvese que los bits del número se desplazan 2 espacios a la izquierda, rellenando con 0 los bits menos significativos (los de la derecha). En este caso, si desplazamos más de 2 bits a la izquierda, se perderían bits, lo que se conoce como acarreo. En cuanto al valor resultante, vemos que se trata de 236, o sea, 59 * 4; en general, el desplazamiento a la izquierda de n bits de un número m es igual a: m << n = m * 2ⁿ, siempre y cuando no haya pérdida de bits (acarreo).

Desplazamiento a la Derecha: >>.
Sea n = 172 (10101100₂), entonces n >> 2 será:


Aquí los bits del número se desplazan 2 espacios a la derecha, rellenando con 0 los bits más significativos (los de la izquierda). Igualmente, si desplazamos más de 2 bits se perderían bits. El resultado es 43, es decir, 172 / 4; en general, el desplazamiento a la derecha de n bits de un número m es igual a: m >> n = m / 2ⁿ, siempre y cuando no haya pérdida de bits (acarreo).

Proposición Lógica

Definición. Una proposición es una oración con valor referencial o informativo, de la cual se puede predicar su veracidad o falsedad, es decir, que puede ser falsa o verdadera pero no ambas a la vez.

La proposición es la expresión lingüística del razonamiento, que se caracteriza por ser verdadera o falsa empíricamente, sin ambigüedades. Son proposiciones las oraciones aseverativas, las leyes científicas, las fórmulas matemáticas, las fórmulas y/o esquemas lógicos, los enunciados cerrados o claramente definidos. No son proposiciones las opiniones y suposiciones; los proverbios, modismos y refranes; los enunciados abiertos no definidos; las oraciones interrogativas, exclamativas, imperativas, desiderativas y dubitativas; las interjecciones en general; ni las operaciones aritméticas.

El valor de verdad de una proposición depende no solamente de las relaciones entre las palabras del lenguaje y los objetos en el mundo, sino también del estado del mundo y del conocimiento acerca de ese estado. El valor de verdad de la oración Juan canta depende no solamente de la persona denotada en Juan y el significado del verbo cantar, sino también del momento cuando esta oración es expresada. Juan probablemente canta ahora, pero ciertamente que no siempre está cantando.

De la misma manera, debemos hacer una distinción entre la oración gramatical propiamente dicha, a la que llamaremos enunciado, y el contenido o significado del enunciado, que es la proposición. Así los siguientes enunciados representan en realidad a la misma proposición:

• En Maracaibo hace mucho calor
  
• Maracaibo es una ciudad muy calurosa
  
• La temperatura media de Maracaibo es bastante alta
  
• El clima de Maracaibo es cálido
  
• Maracaibo is a hot city
  

Las siguientes expresiones son ejemplos de proposiciones:

• Bolívar libertó a Venezuela
  
• El hierro es un mineral
  
• Einstein fue un físico teórico
  
• 36 + 63 = 99
  
• La palabra "esdrújula" es esdrújula
  

Los siguientes son ejemplos de expresiones las cuales no son proposiciones

• El hombre más fuerte del mundo
  
• El director del periódico
  
• ¡Quién se ganara el Kino!
  
• 13 + 7
  
• ¡Tú te callas!
  
• X obtuvo el Premio Nobel en 1970
  
• ¿Cuánto cuesta ese reloj?
  

Las proposiciones se representan por letras minúsculas: p, q, r, s, t, u, etc. Por ejemplo, sea la proposición q igual a 34 + 56 = 90

CLASIFICACION

Proposiciones Simples o Atómicas

Son aquellas que carecen totalmente de conectivos lógicos y que, por lo tanto, son inseparables. En este grupo se encuentran las proposiciones predicativas, que son aquellas en la cual se afirma o atribuye una característica respecto de un objeto, como por ejemplo, Juan Pérez es profesor; y las proposiciones relacionales, en las cuales existe una relación de dependencia, estableciendo un enlace entre dos o más objetos, como por ejemplo, Caracas es la capital de Venezuela.

Proposición Compuesta o Molecular

Son aquellas que resultan de la combinación de varias proposiciones simples, unidas por uno o más conectivos lógicos y que pueden ser separadas y descompuestas en proposiciones más simples. Su valor de verdad depende del de las proposiciones que la componen.

CONECTIVOS LÓGICOS

NEGACION

Tabla de Verdad de la Negación

 
CONJUNCIÓN

 Tabla de Verdad de la Conjunción

DISYUNCION INCLUSIVA

 Tabla de Verdad de la Disyunción Inclusiva

DISYUNCION EXCLUSIVA

Tabla de Verdad de la Disyunción Exclusiva

IMPLICACIÓN

Tabla de Verdad de la Implicación

EQUIVALENCIA

Tabla de Verdad de la Equivalencia