Autor Tema: Logica y longitud de una fbf

0 Usuarios y 1 Visitante están viendo este tema.

23 Septiembre, 2022, 05:50 pm
Leído 863 veces

SofiaMC

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 27
  • País: co
  • Karma: +0/-0
Mostrar que el conjunto \(  \{ \alpha \in F (p1, \cdots , p_n) \, :  \) longitud de \(  \alpha \leq k \}  \) tiene cardinal menor o igual que \(  (n + 7) ^ k  \). 

\(  (F(p_1, p_2, \cdots , p_n)   \) representa el conjunto de todas las formulas bien formadas (fbfs) con esas letras proposicionales, ejemplo: \(   p_1, (p_1) \vee (p_2))  \)

Estaba tratando de hacerlo por induccion en k, pero no llegue a nada, me dijeron que utilizara el principio de la suma y la multiplicacion de probabilidad pero nose como hacerlo o la relación que hay.

23 Septiembre, 2022, 09:26 pm
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 4,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Esto dependerá de los detalles que te hayan dado para la sintaxis. Es decir, ¿qué símbolos pueden aparecer en una fórmula?

Si como sospecho son variables proposicionales, los conectores \( \neg, \vee, \wedge, \to, \leftrightarrow \) y los paréntesis \( (,) \), entonces hay \( (n+7)^k \) cadenas de longitud \( k \) que puedes formar con las \( n \) variables proposicionales \( p_1,\dots, p_n \) y los siete símbolos de arriba. Como cada fórmula bien formada es en particular una cadena de este tipo, tienes tu cota.

Ahora bien, ten en cuenta que esta cota es bastante gruesa: para \( k \) grande habrá muchas menos fórmulas bien formadas que \( (n+7)^k \).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

26 Septiembre, 2022, 01:18 am
Respuesta #2

SofiaMC

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 27
  • País: co
  • Karma: +0/-0
Entiendo que por el principio de la suma cada elemento \(  \alpha  \), vamos a tener \(  n+7  \) posibilidades, \( n  \) letras proposicionales y \( 7  \) conectores, por eso el \(  n+7   \), pero no entiendo, porque se multiplica \(  n+7   \) con \(  n+7   \) - k-veces, eso aun no lo entiendo.