Tarea 1 matemáticas discretas 2023 - 1

[pic 1][pic 2][pic 3][pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22]NOMBRE:     Gustavo  Gonzalez  Spate 

SECCION:     1 

PUNTAJE: 

Pontificia  Universidad  Cat´olica  de  Chile 
Escuela  de  Ingenier´ıa 

IIC1253   —   Matem´ 

Tarea  1  –  Respuesta  Pregunta  1 

1.1 

Primero  definimos  nuestro  conjunto  S  como  el  conjunto  de  los  siguientes  conectivos  l´ 

S  :=  {⊥,  ⊤,  ∧} 

        Por  el  enunciado  ya  sabemos  que  el  conjunto  {¬,  ∧,  ∨}  es  funcionalmente  completo,  por  lo  que  una 
forma  de  probar  que  el  conjunto  S   es  funcionalmente  completo  ser´ıa  lograr  reescribir  nuestro  conjunto 

de  verdad  con  los  conectivos  de  mi  conjunto  S : 

p 

¬  p 

0 

1 

1 

0 

Ahora,  mediante  los  conectivos  {⊥,  ⊤,  ∧}  podemos  obtener  lo  siguiente  para  p: 

p     ⊥     ⊤ 

p  ∧  ⊥ 

p  ∧  ⊤ 

0     0      1 

0 

0 

1     0      1 

0 

1 

Aqui  podemos  ver  que  la  columa  de  la  formula  proposicional  p  ∧  ⊥  es  equivalente  a  ⊥,  y  adem´ 

Por  lo  tanto,  simplificando  la  tabla  de  verdad  para  estos  equivalentes  tenemos  lo  siguiente: 

p     ⊥ 

p  ∧  ⊥ 

0     0 

0 

1     0 

0 

        Y  con  esto  vemos  que  la  columna  equivalente  corresponde  a  ⊥.   Notemos  que  el  procedimiento  ser´ıa 
alogo  si  escogemos  otras  f´ormulas  de  conectivos  de  nuestro  conjunto  S .   Es  decir,  llegaremos  a  un  resul- 

Como  podemos  ver,  con  los  conectivos  l´ 

l´ 

1 

[pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48][pic 49]1.2 

alogo  al  anterior,  tenemos  que  nuestro  nuevo  conjunto  C  est´ 

C  :=  {→,  ⊥} 

Siguiendo  los  pasos  anteriores  ,  buscamos  construir  nuestro  conjunto  funcionalmente  completo  {¬,  ∧,  ∨} 

ogico  ¬  tenemos  lo  siguiente: 

¬  p  ≡  p  →  ⊥ 

Esto  se  puede  verificar  comparando  las  tablas  de  verdad  respectivas. 

p 

¬  p 

0 

1 

1 

0 

Y: 

p     ⊥ 

p  →  ⊥ 

0     0 

1 

1     0 

0 

Como  podemos  ver,  ambas  tablas  de  verdad  coinciden  para  las  mismas  valuaciones  de  p,  por  lo  que  esta 

es  una  equivalencia  v´alida. 

Ahora  bien,  para  ∨: 

p  ∨  q  ≡  ¬  p  →  q  ≡  (  p  →  ⊥  )  →  q 

Esto lo sabemos por De Morgan y por el inciso anterior.  Luego, comparando las tablas de verdad tenemos: 

p     q 

p  ∨  q 

0     0 

0 

0     1 

1 

1     0 

1 

1     1 

1 

Y: 

p     q     ⊥ 

p  →  ⊥ 

(  p  →  ⊥  )  →  q 

0     0     0 

1 

0 

0     1     0 

1 

1 

1     0     0 

0 

1 

1     1     0 

0 

1 

Por  lo  que  podemos  ver,  ambas  tablas  de  verdad  coinciden  para  las  mismas  valuaciones  de  p  y  q,  por  lo  que 
esta  es  una  equivalencia  v´alida. 

Y  finalmente  para  ∧: 

p  ∧  q  ≡  ¬  (  ¬  p  ∨  q  )  ≡  (  ¬  p  ∨  ¬  q  )  →  ⊥  ≡  (  (  p  →  ⊥  )  ∨  (  q  →  ⊥  )  )  →  ⊥ 

Esto  lo  sabemos  por  De  Morgan  y  por  los  incisos  anteriores.    Luego,  comparando  las  tablas  de  verdad 
tenemos: 

...