Autor Tema: Relaciones (Lógica Proposicional)

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

04 Noviembre, 2021, 04:36 pm
Leído 2029 veces

randox

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • País: cl
  • Karma: +0/-0
Sea \( C \) un conjunto y \( R \) una relación de orden (reflexiva) sobre \( C \). Si \( (x,y)\not\in R \) e \( (y,x)\not\in R \) (Es decir \( x \) e \( y \) son incomparables), ponemos \( R_{x,y}=R\cup \{(x,y)\}\cup \{(a,b)\in C^2:(a,x)\in R\textsf{ e }(y,b)\in R\} \). Por construcción, la relación binaria \( R_{x,y} \) extiende a \( R \) y es transitiva.

(a) Mostar que \( R_{x,y} \) es reflexiva.

(b) Mostrar que\(  R_{x,y} \) es antisimétrica (en particular, si \( C \) es finito, entonces \( R \) se
puede extender a un orden total). Indicación: dado un par \( (u, v) \) tal que  \( (u, v)\in R_{x,y} \) y
\( (v, u) \in R_{x,y} \),  se podría asumir que  \( (u, v) \notin R \) y estudiar cuatro casos.

(c) Consideremos la lógica proposional con conjunto de variables \( \mathcal{V} = C\times C \). Dar
un conjunto de fórmulas \( \mathcal{O}_{C,R} \) que es satisfacible si y solo si existe un orden total \( S \) sobre
\( C  \)que extiende a \( R \).

(d) deducir que \( R \) es extendible a un orden total



Bienvenido al foro.

Recuerda leer y seguir  las reglas del mismo así como el tutorial del LaTeX para escribir las fórmulas matemáticas correctamente.

En particular no debes de poner el texto del mensaje en una imagen adjunta, sino teclearlo directamente en el mismo.

Te hemos escrito desde la administración parte del enunciado. Completa el resto.



04 Noviembre, 2021, 05:22 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Sea \( C \) un conjunto y \( R \) una relación de orden (reflexiva) sobre \( C \). Si \( (x,y)\not\in R \) e \( (y,x)\not\in R \) (Es decir \( x \) e \( y \) son incomparables), ponemos \( R_{x,y}=R\cup \{(x,y)\}\cup \{(a,b)\in C^2:(a,x)\in R\textsf{ e }(y,b)\in R\} \). Por construcción, la relación binaria \( R_{x,y} \) extiende a \( R \) y es transitiva.

(a) Mostar que \( R_{x,y} \) es reflexiva.

Es inmediato. Por ser \( R \) reflexiva, \( (c,c)\in R \) para todo \( c\in C \). Pero \( R\subset R_{x,y} \).

Saludos.

04 Noviembre, 2021, 05:40 pm
Respuesta #2

randox

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • País: cl
  • Karma: +0/-0


Hola

Sea \( C \) un conjunto y \( R \) una relación de orden (reflexiva) sobre \( C \). Si \( (x,y)\not\in R \) e \( (y,x)\not\in R \) (Es decir \( x \) e \( y \) son incomparables), ponemos \( R_{x,y}=R\cup \{(x,y)\}\cup \{(a,b)\in C^2:(a,x)\in R\textsf{ e }(y,b)\in R\} \). Por construcción, la relación binaria \( R_{x,y} \) extiende a \( R \) y es transitiva.

(a) Mostar que \( R_{x,y} \) es reflexiva.

Es inmediato. Por ser \( R \) reflexiva, \( (c,c)\in R \) para todo \( c\in C \). Pero \( R\subset R_{x,y} \).

Saludos.

Muchas Gracias por la corrección, perdón por no haberla escrito en LaTeX, como se podria hacer la parte b) y c)?

Saludos

04 Noviembre, 2021, 05:42 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Muchas Gracias por la corrección, perdón por no haberla escrito en LaTeX, como se podria hacer la parte b) y c)?

Escribe el texto en el mensaje y te contesto. Si tienes problemas con las fórmulas no te preocupes, escríbelas como puedas y yo te las corrijo.

Saludos.

04 Noviembre, 2021, 05:55 pm
Respuesta #4

randox

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • País: cl
  • Karma: +0/-0
Hola

Muchas Gracias por la corrección, perdón por no haberla escrito en LaTeX, como se podria hacer la parte b) y c)?

Escribe el texto en el mensaje y te contesto. Si tienes problemas con las fórmulas no te preocupes, escríbelas como puedas y yo te las corrijo.

Saludos.

Listo, corregi el tema principal y lo escribi en LaTeX, gracias por la paciencia

04 Noviembre, 2021, 07:07 pm
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

(b) Mostrar que\(  R_{x,y} \) es antisimétrica (en particular, si \( C \) es finito, entonces \( R \) se
puede extender a un orden total). Indicación: dado un par \( (u, v) \) tal que  \( (u, v)\in R_{x,y} \) y
\( (v, u) \in R_{x,y} \),  se podría asumir que  \( (u, v) \notin R \) y estudiar cuatro casos.

Tienes que probar que si \( (u,v)\in R_{x,y} \) con \( u\neq v \), entonces \( (v,u)\not\in R_{x,y} \).

- Si \( (u,v)\in R \) con \( u\neq v \) sabes que \( (v,u)\not\in R \) (por ser \( R \) de orden). Si \( (v,u)\in R_{x,y} \) entonces o bien \( (v,u)=(x,y) \) (pero es no es posible porque \( (x,y)\not\in R \)) o bien \( (v,x)\in R \) e \( (y,u)\in R \). Pero como además \( (u,v)\in R \) por transitividad \( (u,x)\in R \) y \( (y,x)\in R \), lo cuál es falso por hipótesis.

-  Si \( (u,v)\not\in R \) (pero si en \( R_{x,y} \):

-- O bien \( (u,v)=(x,y) \) pero entonces \( (v,u)=(y,x)\not\in R  \) por hipótesis. Además si \( (y,x)\in R_{x,y} \) entonces \( (y,x)\in R \) e \( (y,x)\in R \), lo cuál no es cierto por hipótesis.

--- O bien \( (u,x),(y,v)\in R \). Si tuviésemos \( (v,u)\in R_{x,y} \):

----- O bien \( (v,u)\in R \) y por transitividad \( (y,x)\in R \). ¡No!.
----- O bien \( (v,u)=(x,y) \) y entonces \( (y,x),(x,y)\in R \). ¡No!.
----- O bien \( (v,x),(y,u)\in R \) y por transitividad junto con \( (u,x)\in R \) tendríamos \( (y,x)\in R \). ¡No!.

Saludos.

04 Noviembre, 2021, 07:35 pm
Respuesta #6

randox

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • País: cl
  • Karma: +0/-0
Hola

(b) Mostrar que\(  R_{x,y} \) es antisimétrica (en particular, si \( C \) es finito, entonces \( R \) se
puede extender a un orden total). Indicación: dado un par \( (u, v) \) tal que  \( (u, v)\in R_{x,y} \) y
\( (v, u) \in R_{x,y} \),  se podría asumir que  \( (u, v) \notin R \) y estudiar cuatro casos.

Tienes que probar que si \( (u,v)\in R_{x,y} \) con \( u\neq v \), entonces \( (v,u)\not\in R_{x,y} \).

- Si \( (u,v)\in R \) con \( u\neq v \) sabes que \( (v,u)\not\in R \) (por ser \( R \) de orden). Si \( (v,u)\in R_{x,y} \) entonces o bien \( (v,u)=(x,y) \) (pero es no es posible porque \( (x,y)\not\in R \)) o bien \( (v,x)\in R \) e \( (y,u)\in R \). Pero como además \( (u,v)\in R \) por transitividad \( (u,x)\in R \) y \( (y,x)\in R \), lo cuál es falso por hipótesis.

-  Si \( (u,v)\not\in R \) (pero si en \( R_{x,y} \):

-- O bien \( (u,v)=(x,y) \) pero entonces \( (v,u)=(y,x)\not\in R  \) por hipótesis. Además si \( (y,x)\in R_{x,y} \) entonces \( (y,x)\in R \) e \( (y,x)\in R \), lo cuál no es cierto por hipótesis.

--- O bien \( (u,x),(y,v)\in R \). Si tuviésemos \( (v,u)\in R_{x,y} \):

----- O bien \( (v,u)\in R \) y por transitividad \( (y,x)\in R \). ¡No!.
----- O bien \( (v,u)=(x,y) \) y entonces \( (y,x),(x,y)\in R \). ¡No!.
----- O bien \( (v,x),(y,u)\in R \) y por transitividad junto con \( (u,x)\in R \) tendríamos \( (y,x)\in R \). ¡No!.

Saludos.

oh muchas gracias, había planteado algo similar en lso casos pero no estaba 100% seguro. Y la c) como podría hacerla?

Saludos

04 Noviembre, 2021, 08:29 pm
Respuesta #7

geómetracat

  • Moderador Global
  • Mensajes: 4,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
La idea para c) es pensar que la variable proposicional \[ (x,y) \] es verdadera si y solo si \[ (x,y)\in S \]. Con esta interpretación en mente, puedes ir añadiendo fórmulas que expresen que \[ S \] es una relación de orden total que extiende a \[ R \].
Por ejemplo, para expresar que es reflexiva, añades todas las variables del tipo \[ (x,x) \] con \[ x\in C \]. Para expresar que es transitiva, añades las fórmulas \[ \phi_{x,y,z}:= (x,y)\wedge (y,z) \to (x,z) \] para todo \[ x,y,z\in C \]. Que sea un orden total se traduce en las fórmulas \[ \psi_{x,y}:=(x,y)\vee (y,x) \] para todo \[ x,y \in C \] (de hecho, mientras escribo me doy cuenta de que esta incluye a la reflexiva). Faltan fórmulas que expresen 
la antisimetría (que quizás es la más delicada) y que extiende a \[ R \], te lo dejo a ti.

Una vez tienes todo esto expresado, c) es fácil: si existe el orden total \[ S \] el conjunto de fórmulas es satisfacible sin más que interpretar la variable \[ (x,y) \] como verdadera si y solo si \[ (x,y)\in S \]. Y si el conjunto de fórmulas es satisfacible, defines \[ S \] como la relación dada por \[ (x,y)\in S \] si y solo si \[ (x,y) \] es verdadera en una valoración que haga \[ \mathcal{O}_{C,R} \] verdadera.

Finalmente, d) se hace usando el teorema de compacidad: para ver que \[ \mathcal{O}_{C,R} \] es satisfacible basta ver que es finitamente satisfacible, pero esto se sigue del apartado b) (donde dice que en particular si \[ C \] es finito entonces \[ R \] se puede extender a un orden total).

La ecuación más bonita de las matemáticas: \( d^2=0 \)

04 Noviembre, 2021, 09:03 pm
Respuesta #8

randox

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • País: cl
  • Karma: +0/-0
La idea para c) es pensar que la variable proposicional \[ (x,y) \] es verdadera si y solo si \[ (x,y)\in S \]. Con esta interpretación en mente, puedes ir añadiendo fórmulas que expresen que \[ S \] es una relación de orden total que extiende a \[ R \].
Por ejemplo, para expresar que es reflexiva, añades todas las variables del tipo \[ (x,x) \] con \[ x\in C \]. Para expresar que es transitiva, añades las fórmulas \[ \phi_{x,y,z}:= (x,y)\wedge (y,z) \to (x,z) \] para todo \[ x,y,z\in C \]. Que sea un orden total se traduce en las fórmulas \[ \psi_{x,y}:=(x,y)\vee (y,x) \] para todo \[ x,y \in C \] (de hecho, mientras escribo me doy cuenta de que esta incluye a la reflexiva). Faltan fórmulas que expresen 
la antisimetría (que quizás es la más delicada) y que extiende a \[ R \], te lo dejo a ti.

Una vez tienes todo esto expresado, c) es fácil: si existe el orden total \[ S \] el conjunto de fórmulas es satisfacible sin más que interpretar la variable \[ (x,y) \] como verdadera si y solo si \[ (x,y)\in S \]. Y si el conjunto de fórmulas es satisfacible, defines \[ S \] como la relación dada por \[ (x,y)\in S \] si y solo si \[ (x,y) \] es verdadera en una valoración que haga \[ \mathcal{O}_{C,R} \] verdadera.

Finalmente, d) se hace usando el teorema de compacidad: para ver que \[ \mathcal{O}_{C,R} \] es satisfacible basta ver que es finitamente satisfacible, pero esto se sigue del apartado b) (donde dice que en particular si \[ C \] es finito entonces \[ R \] se puede extender a un orden total).

Muchísimas gracias por la respuesta, me sirvió muchísimo

Saludos
PD: postee un ejercicio en el subforo de teoría de conjuntos por si me puedes ayudar con ese también por favor  :(