Programa que construye tablas de verdad de proposiciones logicas.

[csaralg]

Hola, seguro todos conocen las proposiciones lógicas... si esa vaina de: "Estudio o no apruebo matemática discreta. Voy al cine si y solo si no estudio. Si no voy al cine me pierdo el estreno. Ni loco me pierdo el estreno." Conclusión...  "No apruebo matemática discreta."  

Bueno eso mismo se puede expresar formalmente por medio de proposiciones:

Sean las variables (proposiciones):

e = Estudio
a = apruebo matemática discreta
c = voy al cine
p = me pierdo el estreno

[EDITADO, puedes saltarte esto si quieres...]

Cada variable puede tomar un valor de verdad que puede ser V (verdadero) o F (falso). Además podemos formar proposiciones mas complejas usando los operadores o conectivos lógicos que son:

NEGACION (~p) : Invierte el valor de la variable p. Se lee: No es cierto que p; o tambien: No p
CONJUNCION (p ^ q) : Es verdadero únicamente cuando p y q son verdaderos. Se lee: p y q
DISYUNCION (p v q) : Es falso únicamente cuando p y q son falsos. Se lee: p o q
IMPLICACION (p --> q) : Es falso únicamente cuando p es verdadero y q es falso. Se lee: p implica q; o tambien: Si p entonces q
BICONDICIONAL (p <--> q) : Es verdadero cuando p y q tienen el mismo valor de verdad (ambos falsos o ambos verdaderos). Se lee: p si y solo si q;

Ahora si usamos las variables que definimos para formalizar el enunciado inicial tenemos: (formalizamos oración por oración)

1. Estudio o no apruebo matemática discreta.  =  (e v ~a)
2. Voy al cine si y solo si no estudio. = (c <--> ~e)
3. Si no voy al cine me pierdo el estreno. = (~c --> p)
4. Ni loco me pierdo el estreno. =  (~p)

Ahora, el valor de verdad de cada una de estas proposiciones compuestas dependerá de los valores de sus variables. Si ordenamos en una tabla todas las posibles combinaciones de los valores de sus variables  y los evaluamos obtendremos la tabla de verdad de la proposición compuesta. Por ejemplo para la proposición 1:

Código: [Seleccionar]

e a | ( e v ~ a )

V V |   V V F V  
V F |   V V V F  
F V |   F F F V  
F F |   F V V F  

Hay que tener presente que hay un orden para evaluar una proposición. Primero se resuelven los paréntesis mas anidados. Luego la negación. Después las conjunciones y disyunciones. Luego las implicaciones y finalmente las bicondicionales. El operador que se resuelve al final se denomina de máxima jerarquía y es el que resume el valor de verdad de toda la proposición. En el ejemplo el operador de máxima jerarquía es la disyunción y se puede observar que la proposición sera falsa únicamente cuando "e" es falso y "a" es verdadero. Es decir cuando apruebe sin estudiar

Ahora podemos usar las proposiciones 1, 2, 3 y 4 para construir una inferencia. Una inferencia es cuando a partir de un conjunto de premisas (proposiciones que se asumen verdaderas) se llega a demostrar que otra proposición llamada conclusión es también verdadera. Ejemplo: Sean las premisas P1, P2 y P3 y la conclusión C construimos la inferencia:

(P1 ^ P2 ^ P3) --> C

Si la inferencia es correcta, al resolverse, la implicación debe ser siempre verdadera. Cuando una proposición es siempre verdadera se dice que es una "tautología".

En el enunciado inicial mi conclusión era: "No apruebo matemática discreta." entonces mi inferencia quedaría así:

( (e v ~a) ^ (c <--> ~e) ^ (~c --> p) ^ (~p) ) --> ~a

Para demostrar si la inferencia es correcta y por tanto mi conclusión es valida. Debo construir la tabla de verdad de toda esa expresión y revisar si es una tautología. Pero... como que esta algo grande no?  

Bueno aquí es donde entra en juego el programa que pondré a continuación pues sirve para construir la tabla de verdad de cualquier proposición lógica (o al menos esa es la idea  ).

[FIN EDITADO]

Los operadores lógicos los representare como:

!         NEGACION ( NO )
&        CONJUNCION ( Y )
|         DISYUNCION ( O )
:         IMPLICACION ( ENTONCES )
=        BICONDICIONAL ( SI Y SOLO SI )
( )       PARENTESIS

Se considera una proposición cualquier caracter diferente de los operadores. Se puede usar espacios en blanco mientras se escribe la proposición de todos modos son suprimidos al leer la entrada.

El ejemplo anterior se representaría así:

Código: [Seleccionar]

( ( e | ! a ) & ( c = ! e ) & ( ! c : p ) & ( ! p ) ) : ! a
Y la salida seria:

Código: [Seleccionar]

e a c p | ( ( e | ! a ) & ( c = ! e ) & ( ! c : p ) & ( ! p ) ) : ! a

V V V V |     V V F V   F   V F F V   F   F V V V   F   F V     V F V
V V V F |     V V F V   F   V F F V   F   F V V F   F   V F     V F V
V V F V |     V V F V   V   F V F V   V   V F V V   F   F V     V F V
V V F F |     V V F V   V   F V F V   F   V F F F   F   V F     V F V
V F V V |     V V V F   F   V F F V   F   F V V V   F   F V     V V F
V F V F |     V V V F   F   V F F V   F   F V V F   F   V F     V V F
V F F V |     V V V F   V   F V F V   V   V F V V   F   F V     V V F
V F F F |     V V V F   V   F V F V   F   V F F F   F   V F     V V F
F V V V |     F F F V   F   V V V F   F   F V V V   F   F V     V F V
F V V F |     F F F V   F   V V V F   F   F V V F   F   V F     V F V
F V F V |     F F F V   F   F F V F   F   V F V V   F   F V     V F V
F V F F |     F F F V   F   F F V F   F   V F F F   F   V F     V F V
F F V V |     F V V F   V   V V V F   V   F V V V   F   F V     V V F
F F V F |     F V V F   V   V V V F   V   F V V F   V   V F     V V F
F F F V |     F V V F   F   F F V F   F   V F V V   F   F V     V V F
F F F F |     F V V F   F   F F V F   F   V F F F   F   V F     V V F

Si se observa la salida debajo del ultimo ":" que representa la conclusión es todo V (verdadero) por lo tanto la proposición resulta una tautología y la conclusión es valida.

Bueno, gracias por leer. Espero sus comentarios, por favor si alguien encuentra un error coméntelo que este programa tengo que presentarlo la próxima semana al profe de mate discreta y si esta mal... saquen sus conclusiones...

Hasta luego, saludos.

Código: [Seleccionar]

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define LMAX 100

//DECLARACION DE PROTOTIPOS

int leer_entrada(char *prop);
int max_precedencia(char *prop, int ini, int fin);
int precedencia(char c);
bool validar_sintaxis(char *prop, int ini, int fin);
bool evaluar_proposicion(char *prop, bool *vals, char *vars, char *resp, int ini, int fin);
int buscar_variables(char *prop, char *vars);


//PROGRAMA PRINCIPAL

int main() {
char prop[LMAX];
char *vars;
char *resp;
bool *vals;


printf("Este programa construye la tabla de verdad de una exprecion logica.\n");
printf("Los operadores logicos validos son:\n\n");
printf("\"!\"\tNEGACION\n");
printf("\"&\"\tCONJUNCION\n");
printf("\"|\"\tDISYUNCION\n");
printf("\":\"\tIMPLICACION\n");
printf("\"=\"\tBICONDICIONAL\n\n");
printf("Puede usar expreciones anidadas con parentesis.\n\n");

printf("EXPRECION> ");
int n = leer_entrada(prop);

resp = new char[n];
vars = new char[n];
vals = new bool[n];
for(int i=0; i<n; i++) {
resp[i] = ' ';
vars[i] = '\0';
vals[i] = false;
}
resp[n-1] = '\0';

if(validar_sintaxis(prop, 0, n)) {
int nvars = buscar_variables(prop, vars);
int reps = (int)pow(2, nvars);

        printf("\n");
for(int i=0; i<nvars; i++)
printf("%c ", vars[i]);
printf("| ");
for(int i=0; i<n; i++)
printf("%c ", prop[i]);
printf("\n\n");
for(int i=0; i<reps; i++) {
for(int j=0; j<nvars; j++) {
if(i%(int)pow(2, nvars-j-1) == 0) {
vals[j] = !vals[j];
}
if(vals[j]) printf("V "); else printf("F ");
}
printf("| ");
evaluar_proposicion(prop, vals, vars, resp, 0, n);
for(int j=0; j<n; j++)
printf("%c ", resp[j]);
printf("\n");
}
}
else {
printf("ERROR LA SINTAXIS DE LA EXPRECION ES INCORRECTA.\n");
}
    system("pause>nul");
return 0;
}


//IMPLEMENTACION DE FUNCIONES

/*
Lee una exprecion por teclado anulando los espacios en blanco y devuelve el
numero de caracteres que conforman la exprecion.
*/
int leer_entrada(char *prop) {
char c; int i=0;
while((c=getchar()) != '\n' && i < (LMAX-1))
if(c!=' ')
prop[i++] = c;
prop[i] = '\0';
return i;
}

/*
Busca dentro de una exprecion el operador que tiene mayor precedencia, es decir,
el que se resolvera al final y devuelve su indice dentro de la exprecion.
*/
int max_precedencia(char *prop, int ini, int fin) {
int npar=0, prec=0, anid=0, index=0;
bool prim=true;
for(int i=ini; i<fin; i++) {
if(prop[i] == '(') {
npar++;
}
else if(prop[i] == ')') {
npar--;
}
else {
if(npar<0) return -1; //error de sintaxis
int p = precedencia(prop[i]);
if(prim) {
anid = npar;
prec = p;
index = i;
prim = false;
continue;
}
if(npar<anid) {
anid = npar;
prec = p;
index = i;
}
else if(anid==npar) {
if(p>prec) {
prec = p;
index = i;
}
else if(p==prec) {
if(prop[index] != prop[i])
return -1; //error de doble interpretacion
if(prop[index] != '!')
index = i;
}
}
}
}
if(npar != 0 || prim) return -1; //error de sintaxis
return index;
}

/*
Esta funcion recibe un caracter por parametro y devuelve un entero de 0 a 4 que
representa la precedencia del operador. Los operadores con menor precedencia
se resuelven primero y los que tienen mayor precedencia se resuelven al final.
*/
int precedencia(char c) {
switch(c) {
case '!': return 1; //negacion
case '&': return 2; //conjuncion
case '|': return 2; //disyuncion
case ':': return 3; //implicacion
case '=': return 4; //bicondicional
}
return 0;
}

/*
Esta funcion se encarga de validar la sintaxis de una exprecion de forma recursiva
usando la siguiente definicion:

P ::= p / (!P) / (P&Q) / (P|Q) / (P:Q) / (P=Q)

Devuelve verdadero si la proposicion cumple la definicion y falso si no.
*/
bool validar_sintaxis(char *prop, int ini, int fin) {
int index = max_precedencia(prop, ini, fin);
if(index == -1) return false;
if(prop[index] == '!') {
int npar=0, i=index+1, f;
for(f=i; f<fin; f++) {
if(prop[f]=='(') {
npar++;
}
else if(prop[f]==')') {
npar--;
if(npar<0) break;
}
}
return validar_sintaxis(prop, i, f);
}
else if(prop[index]=='&' || prop[index]=='|' || prop[index]==':' || prop[index]=='=') {
int npar=0, i, f=index;
bool p, q;
for(i=f-1; i>=ini; i--) {
if(prop[i]==')') {
npar++;
}
else if(prop[i]=='(') {
npar--;
if(npar<0) break;
}
}
p = validar_sintaxis(prop, i+1, f);
npar=0; i=index+1;
for(f=i; f<fin; f++) {
if(prop[f]=='(') {
npar++;
}
else if(prop[f]==')') {
npar--;
if(npar<0) break;
}
}
q = validar_sintaxis(prop, i, f);
return (p && q);
}
else {
int vars=0;
for(int i=ini; i<fin; i++)
if(prop[i]!='(' && prop[i]!=')')
vars++;
if(vars == 1)
return true;
}
return false;
}

bool evaluar_proposicion(char *prop, bool *vals, char *vars, char *resp, int ini, int fin) {
int index = max_precedencia(prop, ini, fin);
if(prop[index] == '!') {
int npar=0, i=index+1, f;
bool b;
for(f=i; f<fin; f++) {
if(prop[f]=='(') {
npar++;
}
else if(prop[f]==')') {
npar--;
if(npar<0) break;
}
}
b = !evaluar_proposicion(prop, vals, vars, resp, i, f);
if(b) resp[index] = 'V'; else resp[index] = 'F';
return b;
}
else if(prop[index]=='&' || prop[index]=='|' || prop[index]==':' || prop[index]=='=') {
int npar=0, i, f=index;
bool p, q, r;
for(i=f-1; i>=ini; i--) {
if(prop[i]==')') {
npar++;
}
else if(prop[i]=='(') {
npar--;
if(npar<0) break;
}
}
p = evaluar_proposicion(prop, vals, vars, resp, i+1, f);
npar=0; i=index+1;
for(f=i; f<fin; f++) {
if(prop[f]=='(') {
npar++;
}
else if(prop[f]==')') {
npar--;
if(npar<0) break;
}
}
q = evaluar_proposicion(prop, vals, vars, resp, i, f);
switch(prop[index]) {
case '&': r = p&&q; break;
case '|': r = p||q; break;
case ':': r = !p||q; break;
case '=': r = (!p||q)&&(!q||p); break;
}
if(r) resp[index] = 'V'; else resp[index] = 'F';
return r;
}
else {
for(int i=0; vars[i]!='\0'; i++)
if(prop[index] == vars[i]){
if(vals[i])
resp[index] = 'V';
else
resp[index] = 'F';
return vals[i];
}
}
}

int buscar_variables(char *prop, char *vars){
int nvars = 0;
for(int i=0; prop[i]!='\0'; i++) {
if(prop[i]!='(' && prop[i]!=')' && prop[i]!='!' && prop[i]!='&' && prop[i]!='|' && prop[i]!=':' && prop[i]!='=') {
bool existe = false;
for(int j=0; j<nvars && !existe; j++) {
if(prop[i] == vars[j]) {
existe = true;
}
}
if(!existe) {
vars[nvars++] = prop[i];
}
}
}
return nvars;
}

[[ZONIC]]

no entiendo mucho de esto pero parese estar bueno el code =) buen aportee

[myguestp]

no entiendo el para que sirve esto, xd es mas, no se que hace el programa

[csaralg]

Gracias [ZONIC], espero que este bien...

¿Alguien tiene alguna entrada maliciosa que haga caer el programa?

[csaralg]

Jajaja... vamos pensé que me había explicado bien... parece que no XD... Tampoco quiero explicar la clase de lógica proposicional... ummm... modifique el post para ver si se entiende mejor...

De todos modos quien quiera enterarse un poco mas de logica proposicional o logica booleana pueden revisar este link:

http://es.wikipedia.org/wiki/L%C3%B3gica_proposicional

Gracias por los comentarios

[myguestp]

lo que no entiendo es que utilidad le puedes dar a tu code, donde lo podrias usar

[csaralg]

Ah vale... jejeje... era eso bueno... ¿alguna ves se te a ocurrido pensar como funcionan los compiladores? osea tu escribes tu código C++ y el compilador lo traduce a ordenes en binario para el procesador. Pero antes de convertirlo tiene que hacer un análisis del lenguaje para verificar si tu código puede compilarse o tiene errores. A esto se le llama análisis de sintaxis. La sintaxis de un lenguaje son un conjunto de reglas que deben cumplirse para determinar si una expresión pertenece o no al lenguaje.

Bien pues, la lógica proposicional también es un lenguaje y su regla de sintaxis puede definirse así:

P = p / (~P) / (P^Q) / (PvQ) / (P-->Q) / (P<-->Q)

Es una definición recursiva. Lo que hace el programa es validar si una expresión cumple con esa definición o no y si cumple entonces crea la tabla de verdad de esa expresión.

Y... respondiendo a tu pregunta... Pues para que me serviría la tabla de verdad... pues para nada hombre!!! si esas cosas no sirven!!! XD

Esto es solo por un trabajo de matemática discreta como dije... y bueno de que funcione depende mi nota .

Ademas si a alguien le dejan la misma tareita pues... ahí tienen una referencia no?

Saludos.

[.xAk.]

¿fuiste al estreno?

[NRagh]

¿fuiste al estreno?

algo me dice que no 

Buenas!

estaria bueno para que te resuelva usando el metodo de las "leyes de morgan"

saludos!

Nragh

p.d.: http://www.mailxmail.com/curso-electronica-digital/leyes-morgan-1-ley

[.xAk.]

Sorry, estaba por las posibilidades que tiene del hacer, y me parecio que el estreno debe ser ... para no perderselo O:)

perdon, de veras, cuando los valores no hexa, char, .... tengo que seguir leyendo ... pero .... curiosidad. Seguro que, a lo mejor tambien empuja ver el estreno. Y pueda proporcionar, si duda en ello, no se, sorry

SaludOS

[csaralg]

Bueno... estoy leyendo el método de las leyes de Morgan

Gracias por los comentarios...

(Editado)

P.S.: Jajaja lo del estreno era solo un ejemplo...  en realidad espero pasar el curso :S

Saludos.

[.xAk.]

je, je. off topic en cinetube o pelisyonkis seguro mañana también ironman2 ... no te compliques con más estrenos si aparece ;)

Me cuesta un poco entender ... pero el tu primer mensaje, en el trato a booleano ha de pensar que tanto en C como C ++ .... mejor tepítete, igual es == que es verdadero o diferente de 0.

Un sólo signo de igualdad es asignación (Y se cumplira si se puede asignar el valor).

[csaralg]

je, je. off topic en cinetube o pelisyonkis seguro mañana también ironman2 ... no te compliques con más estrenos si aparece ;)

Si pues... menos mal existen esas soluciones alternativas y no todo es verdadero o falso, ceros y unos, apruebas o jalas!!! XD

[.xAk.]

apruebas o jalas!!! XD

El jajas se conoce. Aprueba ... y cuentanos.

[.xAk.]

seguro mañana también ironman2

Sigo en off, pero no puedo evitarme comentar que a sido rápido, la sorpresa ha sido verla aquí, como en cinetube.

SaludOS

[coredump]

No lo probé, pero se ve bueno el código.
Tal vez te interese, si es que no lo conoces, el paradigma lógico: Prolog

Hacer un intérprete es realmente apasionante, y un motor de inferencia todavía más.
Luego de que apruebes la materia, y sólo por festejar, puedes implementar punteros a funciones; eso va a hacer que tu código ocupe un tercio de lo que ocupa ahora.
Y si todavía sigues con ganas, puedes usar LEX y YACC, las clásicas herramientas de parseo, para fabricar analizatores sintácticos.

[csaralg]

Algunos términos nuevos para mi: Prolog, LEX, YACC

Ya los buscare, como dices, cuando apruebe y lleve Lenguajes y Traductores

Gracias por los datos...

Saludos.

[lpmartinez]

Me parece muy interesante tu programa, sin embargo no logro entiender que hace tu funcion buscar_variables. Tienes depronto un pseucodigo planteado para tu programa de manera en que se facilite un poco la comprension?

[nano20sm]

La verdad es que no habia visto este post, quedó bueno.

Haber si puedes calcularme este argumento logico y decirme si es contingencia, contradiccion o tautologia con tu programa.

Código: [Seleccionar]

       p | V


Código: [Seleccionar]

       p | F

donde p es una variable, V es una constante que indica verdadero y F es una constante que indica falso..

Te faltó agregar algo tan simple como las constantes. Los argumentos logicos en el calculo proposicional estan compuesto de variables y de constantes. ( para que decir la LPO  )

saludos!!

[Avoidance25]

No conocia este post, la verdad es que esta muy bueno. Justo hace unos dias hice un programa con la misma funcion.

Al pasarlo a php me di cuenta del chiste que es programar en php en comparacion con C
Lo subi al servidor de mi universidad, que tiene una buena capacidad de procesamiento, y me resuelve la funcion en un corto tiempo incluso si tiene las 26 variables permitidas

PD: Iba a poner el link, pero en la direccion esta mi nombre real, asi que .....