Demostrar por inducción en fórmulas - Lógica matemática
a. Si N[a] = # negaciones en a y B[a] = # de conectivos binarios, entonces el número de paréntesis de a es 2N[a] + 4B[a].
b. Toda ocurrencia de ")" en una fbf (fórmula bien formada) va precedida de ")" o de una letra proposicional.
c. Ninguna fbf contiene la sucesión de símbolos )(, ni la sucesión ().
d. En toda fbf el número de paréntesis izquierdos es igual al de derechos.
e. Si P[a] = # de letras proposicionales de a y B[a] = # de conectivos binarios de a, entonces P[a] = B[a] + 1.
1 Respuesta
Si fuera posible me gustaría saber el libro que utilizas, tal vez pueda encontrarlo en Internet. Porque de este tema no tengo yo ningún libro de referencia y los artículos que encuentro en internet discrepan algunas veces. Lo mejor sería aplicar la teoría que venga en el mismo libro.
a) Al parecer se usan todos los paréntesis necesarios pero no más. Todas las fórmulas que van a ser negadas se colocan entre paréntesis y las que van a ser operadas también.
Para N(a)=0 y B(a)=0 se cumple porque un símbolo de constante o variable tiene 0 paréntesis:
A
B
Toda fbf se forma mediante la negación de una fbf o como operación de dos
Cuando se niega se encierra entre paréntesis la fbf anterior, incrementándose en dos el número de ellos
De A tenemos no(A)
De (a)^(b) tenemos no((a)^(b))
Cuando se operan dos fbf se encierran ambas fbf entre paréntesis y se incrementan estos en 4
De a y b tenemos (a)*(b)
De no(a) y (a)*(b) tenémos (no(a))*((a)*(b))
Así en la formación de toda fbf se incrementan en dos los paréntesis al negar y en 4 al operar con lo que
# paréntesis = 2Na+ 4Ba
b) Aparece un paréntesis ")" siempre al final de otra fbf, al negarla u operar dos. Si la fbf anterior. Entonces aparecerá después de otro ")" o de una letra proposicional esi esa letra no había sido negada u operada anteriormente. Y no aparece con otros motivos, luego irá siempre detrás de otro ")" o una letra proposicional
c) Cierto. Al negar u operar nuca se escribe )( porque en medio iría un símbolo conectivo. Ni () porque se encierra siempre una letra proposicional o una fbf que nunca es algo vacío.
d) Cierto, al negar u operar siempre se cumple esa regla, luego el resultado final la cumple.
e) Si P[a] = # de letras proposicionales de a y B[a] = # de conectivos binarios de a, entonces P[a] = B[a] + 1.
Para P[a] =1 se cumple
Supongamos se cumple para todos los números hasta n.
Si me dan una fbf con P[a]=n+1 tiene que tener algún conectivo, porque a base de negar no se aumenta el número de letras
Eliminamos las negaciones que pudiera haber al principio de la fbf hasta que la fbf resultante sea la operación de dos fbf. Estas fbf son de tamaño menor o igual que n, luego cumplen la hipótesis.
Si tienen i y j conectivos tienen i+1 y j+1 letras y por la forma de conseguirlas se cumple
i+j = n-1
luego al juntarlas mediante una operación la fbf que se obtiene tiene
i+1+j+1 = i+j+2 = n+1 letras
i+j+1 = n conectivos
luego letras = conectivos+1 para la fbf de n+1 letras que es lo queríamos demostrar.
Mándame el titulo del libro y si conoces el enlace de internet donde sale completo y gratis también.
Buen día,
El libro se llama Elementos de lógica y calculabilidad de Xavier Caicedo F. Yo lo tengo pero traté de buscarlo por internet y no lo encontré.
Muchas Gracias por ese aporte, me sirve mucho.
Un abrazo.
Si, yo también lo he intentado y no ha podido ser. Hay libros que obtienes sin ningún problema, pero este es imposible. Unicamente encontré un sitio donde aparece pero faltan casi todas las páginas y en concreto las referentes a las FBF no salen.
Si supieras otro parecido que esté entero mne lo dices. Es que yo no estudié logica proposicional, se algo de lógica por la carrera de matemáticas y por que me gusta programar pero no llego al nivel de la asignatura universitaria.
