
	INICIO Clientes \| Blog MATEMÁTICAS \| QUÍMICA \| FÍSICA \| Matemát. UNIVERSIDAD \| ALEMÁN

Portada del sitio > Lógica y Estructuras Discretas > 1 - Lógica de proposiciones y predicados de primer orden

1 - Lógica de proposiciones y predicados de primer orden

Todos los Ejercicios del Tema

Artículos de esta sección

Reescribe las fórmulas con todos sus paréntesis, sabiendo que la reposición correcta se obtiene aplicando el convenio fijado:

1.- $\newline (p\rightarrow q)\vee r$
2.- $\neg p\wedge q\leftrightarrow r\vee s$
3.- $((p\vee q)\wedge\neg r)\rightarrow \neg s$
4.- $(p\leftrightarrow s)\rightarrow s\wedge\top$
5.- $(\bot\rightarrow q\vee\top)\wedge r$
6.- $p\wedge q\wedge r\wedge s\wedge\bot\rightarrow\neg s$
7.- $p\vee q\vee r\vee s\rightarrow\neg(p\wedge s)$
8.- $(\top\rightarrow\bot)\wedge(p\vee \neg r\vee s)$
9.- $((p\vee r\vee s\vee\neg r)\wedge(p\vee r\vee s\vee\neg p))\vee s$
10.- $((p\wedge\neg p)\wedge(q\vee r\vee\neg p))\vee(r\vee (r\vee\neg r))$
Enumere cuáles de las diez fórmulas satisface la interpretación: p:0, q:1, r:0, s:1:

1.- $\newline (p\rightarrow q)\vee r$
2.- $\neg p\wedge q\leftrightarrow r\vee s$
3.- $((p\vee q)\wedge\neg r)\rightarrow \neg s$
4.- $(p\leftrightarrow s)\rightarrow s\wedge\top$
5.- $(\bot\rightarrow q\vee\top)\wedge r$
6.- $p\wedge q\wedge r\wedge s\wedge\bot\rightarrow\neg s$
7.- $p\vee q\vee r\vee s\rightarrow\neg(p\wedge s)$
8.- $(\top\rightarrow\bot)\wedge(p\vee \neg r\vee s)$
9.- $((p\vee r\vee s\vee\neg r)\wedge(p\vee r\vee s\vee\neg p))\vee s$
10.- $((p\wedge\neg p)\wedge(q\vee r\vee\neg p))\vee(r\vee (r\vee\neg r))$
Se propone la construcción de fórmulas con las siguientes restricciones: (a) sólo se usa, repetidamente, la proposición p, (b) finalizan todas ellas (tienen por conectiva principal) una conjunción (’y’, ∧), (c) sólo se usa, exactamente una vez, alguna de las otras cuatro conectivas.P. ej. (p ∧ (p ∨ p)).

a) ¿cuántas fórmulas distintas pueden generarse con esas restricciones?
b) la fórmula del ejemplo consta de 9 caracteres, ¿cuántas de esas fórmulas tienen exactamente 9 caracteres? ¿cuántas tienen otro número de caracteres?
c)partiendo de dos de esas fórmulas ¿puede construir, ya sin esas restricciones, una fórmula con exactamente 21 caracteres cuya conectiva principal es un condicional →?
Solución
En la construcción de la fórmula del ejemplo, (p ∧ (p ∨ p)), se han producido los siguientes tres resultados intermedios: p, (p ∨ p), (p ∧ (p ∨ p)).

a) ¿cuantos y cuáles son estos ’resultados intermedios’ en la fórmula ((p∧q)→((¬r)∨s))? (no se preocupe por el orden relativo de enumeración)
b) construya el árbol sintáctico de la fórmula ’de abajo arriba’, desde sus componentes hacia la fórmula propuesta, ¿cuantos nodos, cuantas posiciones, tiene este árbol?
Solución
El árbol sintáctico de la fórmula ((((p → q) → r) → s) → t), de arriba abajo, va creciendo siempre por la izquierda. Dibújelo. Desde el nodo de la fórmula completa hasta el nodo p, incluidos ambos, tiene una profundidad de 5 nodos.

a) sólo recolocando los paréntesis en esa fórmula, produzca otra que tenga una profundidad hasta el nodo t de 5 nodos
b) sólo recolocando paréntesis, produzca otra que tenga una profundidad hasta el nodo q de 4 nodos
c) ¿dónde hay que colocar los paréntesis para que el árbol resultante tenga, en su rama más larga, una profundidad 4? ¿hay varias opciones?
d) ¿es posible recolocar esos paréntesis para que el árbol resultante tenga, en su rama más larga, una profundidad 3?
Solución
¿Cuáles de las diez fórmulas satisface la interpretación p:1, q:1, r:0 y s:0?

1.- $\newline (p\rightarrow q)\vee r$
2.- $\neg p\wedge q\leftrightarrow r\vee s$
3.- $((p\vee q)\wedge\neg r)\rightarrow \neg s$
4.- $(p\leftrightarrow s)\rightarrow s\wedge\top$
5.- $(\bot\rightarrow q\vee\top)\wedge r$
6.- $p\wedge q\wedge r\wedge s\wedge\bot\rightarrow\neg s$
7.- $p\vee q\vee r\vee s\rightarrow\neg(p\wedge s)$
8.- $(\top\rightarrow\bot)\wedge(p\vee \neg r\vee s)$
9.- $((p\vee r\vee s\vee\neg r)\wedge(p\vee r\vee s\vee\neg p))\vee s$
10.- $((p\wedge\neg p)\wedge(q\vee r\vee\neg p))\vee(r\vee (r\vee\neg r))$
En algunas fórmulas no es necesario efectuar todos los cálculos. ¿Ha encontrado algún atajo a la hora de evaluar alguna fórmula?

1.- $\newline (p\rightarrow q)\vee r$
2.- $\neg p\wedge q\leftrightarrow r\vee s$
3.- $((p\vee q)\wedge\neg r)\rightarrow \neg s$
4.- $(p\leftrightarrow s)\rightarrow s\wedge\top$
5.- $(\bot\rightarrow q\vee\top)\wedge r$
6.- $p\wedge q\wedge r\wedge s\wedge\bot\rightarrow\neg s$
7.- $p\vee q\vee r\vee s\rightarrow\neg(p\wedge s)$
8.- $(\top\rightarrow\bot)\wedge(p\vee \neg r\vee s)$
9.- $((p\vee r\vee s\vee\neg r)\wedge(p\vee r\vee s\vee\neg p))\vee s$
10.- $((p\wedge\neg p)\wedge(q\vee r\vee\neg p))\vee(r\vee (r\vee\neg r))$
1) Con el convenio para la eliminación de paréntesis, ¿qué fórmula, con todos sus paréntesis, corresponde a la siguiente? ¬p ∨ ¬q → t ∨ (q ↔ s)

2) Se desea construir todas las interpretaciones con las que evaluar conjuntamente dos fórmulas. ¿Cuantas son las líneas de la tabla de verdad conjunta de estas dos fórmulas? (p → ¬q) → r (r ∧ s) ∨ t
Solución
Dada la fórmula (Pa ∧ Qb) ∨ (¬Pb ∧ Qa), se interpreta sobre Universo U=1,2,3,4, con P=1,3, Q=2 y los elementos para a y b que se indican en las opciones. Marque todas las opciones que completan esta interpretación y satisfacen la fórmula.

a) a=1, b=1
b) a=1, b=2
c) a=2, b=3
d) a=4, b=2
e) a=3, b=2
Solución
Dada la fórmula (Pa → Qb) ∨ (¬Pb → Qa), se interpreta sobre Universo U=1,2,3,4, con P=1,3, Q=2 y los elementos para a y b que se indican en las opciones. Marque todas las opciones que completan esta interpretación y satisfacen la fórmula.

a) a=2, b=1
b) a=1, b=4
c) a=1, b=1
d) a=4, b=4
e) a=3, b=4
Solución