Recı́procamente, de una fórmula se pueden eliminar paréntesis
siempre y cuando se puedan restaurar. Por ejemplo, de la fórmula
(B → (¬(¬A)))
se pueden eliminar todos los paréntesis:
B → ¬¬A
pues estos se pueden restaurar a la fórmula original. Pero de la
fórmula
((P → Q) → R)
no se pueden eliminar todos los paréntesis, pues si lo hacemos
queda
P→Q→R
que de acuerdo a nuestras convenciones se restaura a
(P → (Q → R))
que no es la fórmula original.
Tarea
Eliminar tantos paréntesis como sea posible:
1. ((B → (¬A)) ∧ C )
2. ((A ∨ B) ∨ C )
3. (((A ∧ (¬B)) ∧ C ) ∨ D)
4. ((B ∨ (¬C )) ∨ (A ∧ B))
5. ((A ↔ B) ↔ (¬(C ∨ D)))
6. ((¬(¬(¬(B ∨ C )))) ↔ (B ↔ C ))
7. (¬((¬(¬(B ∨ C ))) ↔ (B ↔ C )))
8. ((((A → B) → (C → D)) ∧ (¬A)) ∨ C )
Tarea
Restaurar paréntesis.
1. C ∨ ¬A ∧ B
2. B → ¬¬¬A ∧ C
3. C → ¬(A ∧ B → C ) ∧ A ↔ B
4. C → A → A ↔ ¬A ∨ B
Tarea
Determinar cuáles de las siguientes expresiones son fórmulas de
PL, y de las que lo sean, restaurar sus paréntesis.
1. ¬¬A ↔ A ↔ B ∨ C
2. ¬(¬A ↔ A) ↔ B ∨ C
3. ¬(A → B) ∨ C ∨ D → B
4. A ↔ (¬A ∨ B) → (A ∧ (B ∨ C )))
5. ¬A ∨ B ∨ C ∧ D ↔ A ∧ ¬A
6. ((A → B ∧ (C ∨ D) ∧ (A ∨ D))
Tarea
Si escribimos ¬F en lugar de (¬F), → FG en lugar de (F → G),
∧FG en lugar de (F ∧ G) y ∨FG en lugar de (F ∨ G ), entonces no
hay necesidad de paréntesis. Por ejemplo, ((¬A) ∧ (B → (¬D))),
la cual ordinariamente se abrevia como ¬A ∧ (B → ¬D), se
convierte en ∧¬A → B¬D. Esta forma de escritura se llama
notación polaca.
1. Escribir ((C → (¬A)) ∨ B y (C ∨ ((B ∧ (¬D)) → C )) en
notación polaca.
2. Escribir las fórmulas de la primera tarea en notación polaca.
Semántica
La semántica de la Lógica le provee significado: true, false, donde
true6=false.
Definición
Una interpretación (asignación, modelo) I es una asignación de
cada letra proposicional de un único valor de verdad.
Por ejemplo,
I : P 7→ true
Q→ 7 false
..
.
o bien
I : P 7→ 1
Q→ 7 0
..
.
Dada una interpretación I y una fórmula F de PL se puede calcular
el valor de verdad de F. La forma más popular es mediante tablas:
F ¬F
0 1
1 0
F1 F2 F1 ∧ F2 F1 ∨ F 2 F1 → F2 F1 ↔ F2
0 0 0 0 1 1
0 1 0 1 1 0
1 0 0 1 0 0
1 1 1 1 1 1
Ejemplo
Sea F : P ∧ Q → P ∨ ¬Q con interpretación
I : {P 7→ true, Q 7→ false}
entonces F es verdadera, pues
P Q ¬Q P ∧Q P ∨ ¬Q F
1 0 1 0 1 1
Una definición más precisa se obtiene haciendo la propia definición
de forma inductiva.
Definición
Sea F una fórmula, I una interpretación. Se pone
1. I |= F ssi F se valua a true bajo I .
2. I 6|= F ssi F se valua a false bajo I .
El sı́mbolo |= se lee valida, modela.
Definición
1. Para cualquier interpretación I se cumplen:
I |= >, I 6|= ⊥
2. Si P es letra proposicional y I interpretación,
I |= P ssi I [P] = true
esto es, I |= P ssi I le asigna a P el valor true. O
equivalentemente
I 6|= P ssi I [P] = false
3. Si F, F1 , F2 son fórmulas, I interpretación,
3.1 I |= ¬F ssi I 6|= F
3.2 I |= F1 ∧ F2 ssi I |= F1 y I |= F2
3.3 I |= F1 ∨ F2 ssi I |= F1 ó I |= F2
3.4 I |= F1 → F2 ssi ( si I |= F1 entonces I |= F2 )
3.5 I |= F1 ↔ F2 ssi (I |= F2 y I |= F2 ) ó (I 6|= F1 y I 6|= F2 )
Nótese que I 6|= F1 → F2 ssi (I |= F1 entonces I |= F2 ) es falso lo
cual ocurre sólo si I |= F1 es verdadero y I |= F2 es falso. Esto es
I 6|= F1 → F2 ssi I |= F1 y I 6|= F2 .
Para calcular valores de verdad se hace siguiendo el orden para
subfórmulas; de fórmulas menos complejas a las más. Esto es, F1
precede a F2 si F1 es subfórmula de F2 .
Ejemplo
Sean F : P ∧ Q → P ∨ ¬Q, I : {P 7→ true, Q 7→ false}, entonces,
1. I |= P pues I [P] = true
2. I 6|= Q, pues I [Q] = false
3. I |= ¬Q, semántica de ¬
4. I 6|= P ∧ Q por (2) y semántica de ∧
5. I |= P ∨ ¬Q por (1) y semántica de ∨
6. I |= F, por (4) y semántica de →
Definición
1. Una fórmula F es satisfactible si existe una interpretación I
tal que
I |= F.
2. Una fórmula F es válida (tautologı́a) si para toda
interpretación I se cumple
I |= F.
3. Una fórmula se dice insatisfactible si no es satisfactible.
Hay cierta relación entre satisfactibilidad y validez: ¬F es
insatisfactible si para toda interpretación I se cumple I 6|= ¬F lo
cual ocurre ssi para toda interpretación I , I |= F ssi F es válida.
En resumen:
¬F es insatisfactible ssi F es válida.
Hay varias formas de determinar validez y satisfactibilidad:
1. Tablas de verdad.
2. Argumentos semánticos.
(pero éstas no son las únicas).
Tablas de verdad
Ejemplo
Sea F : P ∧ Q → P ∧ ¬Q ¿Es F válida?
Sol. Construimos la tabla de verdad.
P Q P ∧Q ¬Q P ∨ ¬Q F
0 0 0 1 1 1
0 1 0 0 0 1
1 0 0 1 1 1
1 1 1 0 1 1
Cada renglón representa una posible interpretación. De hecho,
para toda interpretación I , I |= F, ası́ F es válida.
Ejemplo
Sea F : P ∨ Q → P ∧ Q. ¿Es F satisfactible?
Sol. La tabla de verdad:
P Q P ∧Q P ∨Q F
I1 : 0 0 0 0 1
I2 : 0 1 0 1 0
I3 : 1 0 0 1 0
I4 : 1 1 1 1 1
Podemos observar que hay interpretaciones que validan a la
fórmula. Por ejemplo, I4 : {P 7→ true, Q 7→ true} cumple
I4 |= F
por tanto F es satisfactible (por cierto F no es válida).
