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:
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í:
( ( e | ! a ) & ( c = ! e ) & ( ! c : p ) & ( ! p ) ) : ! aY la salida seria:
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.
#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;
}
Tema: Programa que construye tablas de verdad de proposiciones logicas. (Leído 22813 veces)
Similar Topics
Noviembre 03, 2012, 02:40:44 pm