Proposicions i formalització
Exercici 1
Indica quines de les següents expressions són proposicions:
- Finlandia pertany a la Unió Europea És proposició
- El famós Linus Torvalds No és proposició
- Catalunya té 5 provincies És proposició
- La víbora té orelles És proposició
- Quants anys han transcorregut No és proposició
- Visca la terra! No és proposició
- La taronja és un mineral És proposició
- 2X + 1 = 3 No és proposició
- L'ànec és un mamifer És proposició
Exercici 2
Simbolitza les següents preposicions:
- No vaig veure la pel·lícula, però vaig llegir la novel·la
- p = vaig veure la pel·lícula
- q = vaig llegir la novel·la
- ¬p ^ q
- Ni vaig veure la pel·lícula ni vaig llegir la novel·la
- p = vaig veure la pel·lícula
- q = vaig llegir la novel·la
- ¬p ^ ¬q
- No és cert que veiés la pel·lícula i llegís la novel·la
- p = vaig veure la pel·lícula
- q = vaig llegir la novel·la
- ¬(p ^ q)
- Vaig veure la pel·lícula encara que no vaig llegir la novel·la
- p = vaig veure la pel·lícula
- q = vaig llegir la novel·la
- p ^ ¬q
Exercici 3
Exercici 4
Taules de veritat
Exercici 3
Confecciona les següents taules de veritat e indica si es tracta de tautologies, contradiccions o contingències (indeterminacions).
- a. ¬p ˅ q
| p q |
¬p ˅ q
|
| 1 1 |
0 1 1
|
| 1 0 |
0 0 0
|
| 0 1 |
1 1 1
|
| 0 0 |
1 1 0
|
- Contingència
- b. (p ˄ q) → p
| p q |
(p ˄ q) → p
|
| 1 1 |
1 1 1 1 1
|
| 1 0 |
1 0 0 1 1
|
| 0 1 |
0 0 1 1 0
|
| 0 0 |
0 0 0 1 0
|
- Tautologia
- c. p ↔ ¬p
| p |
p ↔ ¬ p
|
| 1 |
1 0 0 1
|
| 0 |
1 0 1 0
|
- Contradicció
- d. (p ↔ ¬q) ˄ (p ˅ ¬q)
| p q |
(p ↔ ¬ q) ˄ (p ˅ ¬ q)
|
| 1 1 |
1 0 0 1 0 1 1 0 1
|
| 1 0 |
1 1 1 0 1 1 1 1 0
|
| 0 1 |
0 1 0 1 0 0 0 0 1
|
| 0 0 |
0 0 1 0 0 0 1 1 0
|
- Contingència
- e. (p ↔ ¬q) ˅ (p ˅ ¬q)
| p q |
(p ↔ ¬ q) ˅ (p ˅ ¬ q)
|
| 1 1 |
1 0 0 1 1 1 1 0 1
|
| 1 0 |
1 1 1 0 1 1 1 1 0
|
| 0 1 |
0 1 0 1 1 0 0 0 1
|
| 0 0 |
0 0 1 0 1 0 1 1 0
|
- Tautologia
- f. (¬p ˅ q) ↔ (p → q)
| p q |
(¬ p ˅ q) ↔ (p → q)
|
| 1 1 |
0 1 1 1 1 1 1 1
|
| 1 0 |
0 1 0 0 1 1 0 0
|
| 0 1 |
1 0 1 1 1 0 1 1
|
| 0 0 |
1 0 1 0 1 0 1 0
|
- Tautologia
Equivalències
Exercici 1
Demostra mitjançant taules de veritat les següents equivalències:
- a) p ∧ ¬p ≡ F
- b) p v ¬p ≡ V
- c) p ∧ p ≡ p
- d) p v p ≡ p
- e) p ∧ (p v q) ≡ p
| p |
q |
p v q |
p ∧ (p v q)
|
| V |
V |
V |
V
|
| V |
F |
V |
V
|
| F |
V |
V |
F
|
| F |
F |
F |
F
|
- f) p v (p ∧ q) ≡ p
| p |
q |
p ∧ q |
p v (p ∧ q)
|
| V |
V |
V |
V
|
| V |
F |
F |
V
|
| F |
V |
F |
F
|
| F |
F |
F |
F
|
- g) ¬¬p ≡ p
- h) ¬(p ∧ q) ≡ ¬p v ¬q
| p |
q |
p ∧ q |
¬(p ∧ q) |
¬p |
¬q |
¬p v ¬q
|
| V |
V |
V |
F |
F |
F |
F
|
| V |
F |
F |
V |
F |
V |
V
|
| F |
V |
F |
V |
V |
F |
V
|
| F |
F |
F |
V |
V |
V |
V
|
- i) ¬(p v q) ≡ ¬p ∧ ¬q
| p |
q |
p v q |
¬(p ∧ q) |
¬p |
¬q |
¬p ∧ ¬q
|
| V |
V |
V |
F |
F |
F |
F
|
| V |
F |
V |
F |
F |
V |
F
|
| F |
V |
V |
F |
V |
F |
F
|
| F |
F |
F |
V |
V |
V |
V
|
- j) p ∧ (q v r) ≡ (p ∧ q) v (p ∧ r)
| p |
q |
r |
q v r |
p ∧ (q v r) |
p ∧ q |
p ∧ r |
(p ∧ q) v (p ∧ r)
|
| V |
V |
V |
V |
V |
V |
V |
V
|
| V |
V |
F |
V |
V |
V |
F |
V
|
| V |
F |
V |
V |
V |
F |
V |
V
|
| V |
F |
F |
F |
F |
F |
F |
F
|
| F |
V |
V |
V |
F |
F |
F |
F
|
| F |
V |
F |
V |
F |
F |
F |
F
|
| F |
F |
V |
V |
F |
F |
F |
F
|
| F |
F |
F |
F |
F |
F |
F |
F
|
- k) p v (q ∧ r) ≡ (p v q) ∧ (p v r)
| p |
q |
r |
q ∧ r |
p ∧ (q ∧ r) |
p v q |
p v r |
(p v q) ∧ (p v r)
|
| V |
V |
V |
V |
V |
V |
V |
V
|
| V |
V |
F |
F |
V |
V |
V |
V
|
| V |
F |
V |
F |
V |
V |
V |
V
|
| V |
F |
F |
F |
V |
V |
V |
V
|
| F |
V |
V |
V |
V |
V |
V |
V
|
| F |
V |
F |
F |
F |
V |
F |
F
|
| F |
F |
V |
F |
F |
F |
V |
F
|
| F |
F |
F |
F |
F |
F |
F |
F
|
- l) p ⇒ q ≡ ¬q ⇒ ¬p
| p |
q |
¬q |
¬p |
p ⇒ q |
¬q ⇒ ¬p
|
| V |
V |
F |
F |
V |
V
|
| V |
F |
V |
F |
F |
F
|
| F |
V |
F |
V |
V |
V
|
| F |
F |
V |
V |
V |
V
|
- m) p ⇒ q ≡ ¬p v q
| p |
q |
¬p |
p ⇒ q |
¬p v q
|
| V |
V |
F |
V |
V
|
| V |
F |
F |
F |
F
|
| F |
V |
V |
V |
V
|
| F |
F |
V |
V |
V
|
- n) p⇔q ≡ (p ⇒ q) ∧ (q ⇒ p)
| p |
q |
p ⇒ q |
q ⇒ p |
(p ⇒ q) ∧ q ⇒ p) |
p ⇔ q
|
| V |
V |
V |
V |
V |
V
|
| V |
F |
F |
V |
F |
F
|
| F |
V |
V |
F |
F |
F
|
| F |
F |
V |
V |
V |
V
|
Exercici 2
Demostra, indicant en cada pas quina equivalència s'aplica, les següents equivalències:
- a) (p ⇒ q) ∧ (r ⇒ s) ≡ ¬p ∨ q ∧ ¬r ∨ s
1. (p ⇒ q) ∧ (r ⇒ s)
Implicació material a les dues implicacions {p ⇒ q ≡ ¬p v q}
2. ¬p ∨ q ∧ ¬r ∨ s
- b) ¬(p ∨ (q ∧ r)) ≡ ¬p ∧ (¬q ∨ ¬r)
1. ¬(p ∨ (q ∧ r))
Llei de De Morgan per a la disjunció {¬(p v q) ≡ ¬p ∧ ¬q}
2. ¬p ∧ ¬(q ∧ r)
Llei de De Morgan per a la conjunció a ¬(q ∧ r)
3. ¬p ∧ (¬q ∨ ¬r)
- c) (p ∨ q) ∧ (p ∨ ¬q) ≡ p
1. (p ∨ q) ∧ (p ∨ ¬q)
Distributivitat de la disjunció {p v (q ∧ r) ≡ (p v q) ∧ (p v r)}
2. p v (q ∧ ¬q)
Inversa de la conjunció {p ∧ ¬p ≡ F}
3. p v F
Neutre de la disjunció {p v F ≡ p}
4. p
- d) ¬(p ⇒ q) ≡ p ∧ ¬q
1. ¬(p → q)
Implicació material {p ⇒ q ≡ ¬p v q}
2. ¬(¬p v q)
Llei de De Morgan per a la disjunció {¬(p v q) ≡ ¬p ∧ ¬q}
3. ¬(¬p) ∧ ¬q
Doble negació {¬¬p ≡ p}
4. p ∧ ¬q
- e) p ∨ (¬p ∧ q) ≡ p ∨ q
1. p ∨ (¬p ∧ q)
Distributivitat de la disjunció {p v (q ∧ r) ≡ (p v q) ∧ (p v r)}
2. (p v ¬p) ∧ (p v q)
Inversa de la disjunció {p v ¬p ≡ V}
3. V ∧ (p v q)
Neutre de la conjunció {p ∧ V ≡ p}
4. p v q
- f) (¬p ∧ ¬q) ∨ (p ∧ q) ≡ p ↔ q
1. (¬p ∧ ¬q) ∨ (p ∧ q)
Distributivitat de la disjunció {p v (q ∧ r) ≡ (p v q) ∧ (p v r)}
2. [(¬p ∧ ¬q) ∨ p] ∧ [(¬p ∧ ¬q) ∨ q]
Distributivitat de la disjunció a cada part
3. [(¬p ∨ p) ∧ (¬q ∨ p)] ∧ [(¬p ∨ q) ∧ (¬q ∨ q)]
Inversa de la disjunció {p v ¬p ≡ V}
4. [V ∧ (¬q ∨ p)] ∧ [(¬p ∨ q) ∧ V]
Neutre de la conjunció {p ∧ V ≡ p}
5. (¬q ∨ p) ∧ (¬p ∨ q)
Implicació material {p ⇒ q ≡ ¬p v q}
6. q ⇒ p ∧ p ⇒ q
Commutativitat de la conjunció {p ∧ q ≡ q ∧ p}
7. p ⇒ q ∧ q ⇒ p
Definició d'equivalència material {p⇔q ≡ (p ⇒ q) ∧ (q ⇒ p)}
8. p⇔q
- g) (p → q) ∨ (q ⇒ p) ≡ True
1. (p ⇒ q) ∨ (q ⇒ p)
Implicació material {p ⇒ q ≡ ¬p v q}
2. (¬p v q) ∨ (¬q v p)
Associativitat de la disjunció {p v (q v r) ≡ (p v q) v r}
3. (¬p v p) ∨ (¬q v q)
Inversa de la disjunció {p v ¬p ≡ V}
4. V v V
5. True
- h) (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q) ≡ q ∨ ¬p
1. (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q)
Associativitat de la disjunció {p v (q v r) ≡ (p v q) v r}
2. [(p ∧ q) ∨ (¬p ∧ q)] ∨ (¬p ∧ ¬q)
Distributivitat de la conjunció a la part [] {p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)}
3. [q ∧ (p ∧ ¬p)] ∨ (¬p ∧ ¬q)
Inversa de la disjunció {p v ¬p ≡ V}
4. (q ∧ V) ∨ (¬p ∧ ¬q) (V: True)
Neutre de la conjunció {p ∧ V ≡ p}
5. q ∨ (¬p ∧ ¬q)
Distributivitat de la disjunció {p v (q ∧ r) ≡ (p v q) ∧ (p v r)}
6. (q v ¬p) ∧ (q v ¬q)
Inversa de la disjunció {p v ¬p ≡ V}
7. (q v ¬p) ∧ V (V: True)
Neutre de la conjunció {p ∧ V ≡ p}
8. q v ¬p
- i) (¬p ∨ q) ∧ (p ∨ q) ≡ q
1. (¬p ∨ q) ∧ (p ∨ q)
Distributivitat de la conjunció {p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)}
2. [(¬p ∨ q) ∧ p] ∨ [(¬p ∨ q) ∧ q]
Absorció de la conjunció en el segon terme {p ∧ (p ∨ q) ≡ p
3. [(¬p ∨ q) ∧ p] ∨ q
Distributivitat de la disjunció al primer terme {p v (q ∧ r) ≡ (p v q) ∧ (p v r)}
4. [(p ∧ ¬p) ∨ (p ∧ q)] ∨ q
Inversa de la conjunció {p ∧ ¬p ≡ F}
5. [F ∨ (p ∧ q)] ∨ q
Neutre de la disjunció {p ∨ F ≡ p}
6. (p ∧ q) v q
Absorció de la disjunció {p ∨ (p ∧ q) ≡ p
7. q
- j) ¬(¬p ∨ q) ∧ (p ∨ q) ≡ p ∧ ¬q
1. ¬(¬p ∨ q) ∧ (p ∨ q)
Llei de De Morgan per a la disjunció {¬(p v q) ≡ ¬p ∧ ¬q}
2. (¬¬p ∧ ¬q) ∧ (p ∨ q)
Doble negació {¬¬p ≡ p}
3. (p ∧ ¬q) ∧ (p ∨ q)
Distributivitat de la conjunció {p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)}
4. (p ∧ ¬q ∧ p) ∨ (p ∧ ¬q ∧ q)
Commutativitat de la conjunció {p ∧ q ≡ q ∧ p} i Associativitat de la conjunció {p ∧ (q ∧ r) ≡ (p ∧ q)∧ r}
5. [(p ∧ p) ∧ ¬q] ∨ [p ∧ (¬q ∧ q)]
Idempotència de la conjunció {p ∧ p ≡ p} i Inversa de la conjunció {p ∧ ¬p ≡ F}
6. (p ∧ ¬q) ∨ (p ∧ F)
Dominació de la conjunció {p ∧ F ≡ F}
7. (p ∧ ¬q) ∨ F)
Neutre de la disjunció {p ∨ F ≡ p}
8. p ∧ ¬q
- k) p ∨ ¬(p ∧ q) ≡ True
1. p ∨ ¬(p ∧ q)
Llei de De Morgan per a la conjunció {¬(p ∧ q) ≡ ¬p v ¬q}
2. p v (¬p v ¬q)
Associativitat de la disjunció
3. (p v ¬p) v ¬q
Inversa de la disjunció {p v ¬p} ≡ V
4. V v ¬q (V: True)
Dominació de la disjunció {p v V ≡ V}
5 V (V: True)
- l) (p ∧ q) ∨ [(p ∨ q)∧ ¬r] ∨ q ≡ q ∨ (p ∧ ¬r)
1. (p ∧ q) ∨ [(p ∨ q)∧ ¬r] ∨ q
Associativitat de la disjunció {p v (q v r) ≡ (p v q) v r}
2. [(p ∧ q) ∨ q] ∨ [(p ∨ q)∧ ¬r]
Absorció de la disjunció {p ∨ (p ∧ q) ≡ p
3. q ∨ [(p ∨ q)∧ ¬r]
Distributivitat de la conjunció {p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)}
4. q ∨ [(p ∧ ¬r) ∨ (q ∧ ¬r)]
Associativitat de la disjunció
5. [q ∨ (q ∧ ¬r)] ∨ (p ∧ ¬r)
Absorció de la disjunció
6. q ∨ (p ∧ ¬r
- m) (p ∨ q) ∨ ¬(¬p ∨ q ∨ r) ≡ p ∨ q
1. (p ∨ q) ∨ ¬(¬p ∨ q ∨ r)
Llei de De Morgan per a la disjunció {¬(p v q) ≡ ¬p ∧ ¬q}
2. (p ∨ q) ∨ (¬¬p ∧ ¬q ∧ ¬r)
Doble negació {¬¬p ≡ p}
3. (p ∨ q) ∨ (p ∧ ¬q ∧ ¬r)
Associativitat de la disjunció {p v (q v r) ≡ (p v q) v r}
4. [p ∨ (p ∧ ¬q ∧ ¬r)] ∨ q
Absorció de la disjunció {p ∨ (p ∧ q) ≡ p
5. p ∨ q
- n) ¬[(p ∨ q) ∧ (¬p ∨ r)] ≡ (¬p ∧ ¬q) ∨ (p ∧ ¬r)
1. ¬[(p ∨ q) ∧ (¬p ∨ r)]
Llei de De Morgan per a la conjunció {¬(p ∧ q) ≡ ¬p v ¬q}
2. ¬(p ∨ q) ∨ ¬(¬p ∨ r)
Llei de De Morgan per a la disjunció {¬(p v q) ≡ ¬p ∧ ¬q} als dos termes
3. (¬p ∧ ¬q) ∨ (¬¬p ∧ ¬r)
Doble negació {¬¬p ≡ p}
4. (¬p ∧ ¬q) ∨ (p ∧ ¬r)
Exercici 3
Simplifica, indicant en cada pas quina equivalència s'aplica, les següents fórmules proposicionals:
- a) q ∨ ¬[¬(p ∧ q) → ¬q]
1. q ∨ ¬[¬(p ∧ q) → ¬q]
Implicació material {p ⇒ q ≡ ¬p v q}
2. q ∨ ¬[¬¬(p ∧ q) v ¬q]
Doble negació {¬¬p ≡ p}
3. q ∨ ¬[(p ∧ q) v ¬q]
Llei de De Morgan per a la disjunció {¬(p v q) ≡ ¬p ∧ ¬q}
4. q ∨ [¬(p ∧ q) ∧ ¬¬q]
Doble negació {¬¬p ≡ p}
5. q ∨ [¬(p ∧ q) ∧ q]
Llei de De Morgan per a la conjunció {¬(p ∧ q) ≡ ¬p v ¬q}
6. q ∨ [(¬p ∨ ¬q) ∧ q]
Distributivitat de la conjunció {p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)}
7. q ∨ [(¬p ∧ q) ∨ (¬q ∧ q)]
Inversa de la conjunció {p ∧ ¬p ≡ F}
8. q ∨ [(¬p ∧ q) ∨ F]
Neutre de la disjunció {p ∨ F ≡ p}
9. q ∨ (¬p ∧ q)
Absorció de la disjunció {p ∨ (p ∧ q) ≡ p
10. q
- b) [¬(p ∨ q) ∨ (p ∨ ¬r)] → [r ∧ (r ∨ ¬t)]
1. [¬(p ∨ q) ∨ (p ∨ ¬r)] → [r ∧ (r ∨ ¬t)]
Absorció de la conjunció en el segon terme {p ∧ (p ∨ q) ≡ p
2. [¬(p ∨ q) ∨ (p ∨ ¬r)] → r
Llei de De Morgan per a la disjunció {¬(p v q) ≡ ¬p ∧ ¬q}
3. [(¬p ∧ ¬q) ∨ (p ∨ ¬r)] → r
Distributivitat de la disjunció {p v (q ∧ r) ≡ (p v q) ∧ (p v r)}
4. [(¬p ∨ (p ∨ ¬r) ∧ (¬q ∨ (p ∨ ¬r)) → r
Associativitat de la disjunció {p v (q v r) ≡ (p v q) v r}
5. [((¬p ∨ p) ∨ ¬r) ∧ (( ¬q ∨ p) ∨ ¬r)] → r
Inversa de la disjunció {p v ¬p} ≡ V
6. [(V ∨ ¬r) ∧ (( ¬q ∨ p) ∨ ¬r)] → r
Dominació de la disjunció {p v V ≡ V}
7. [V ∧ (( ¬q ∨ p) ∨ ¬r)] → r
Neutre de la conjunció {p ∧ V ≡ p}
8. ((¬q ∨ p) ∨ ¬r) → r
Implicació material {p ⇒ q ≡ ¬p v q}
9. ¬((¬q ∨ p) ∨ ¬r) ∨ r
Llei de De Morgan per a la disjunció {¬(p v q) ≡ ¬p ∧ ¬q}
10. (¬(¬q ∨ p) ∧ ¬¬r) ∨ r
Llei de De Morgan per a la disjunció {¬(p v q) ≡ ¬p ∧ ¬q}
11. (¬¬q ∧ ¬p) ∧ ¬¬r) ∨ r
Doble negació {¬¬p ≡ p}
12. ((q ∧ ¬p) ∧ r) ∨ r
Absorció de la disjunció {p ∨ (p ∧ q) ≡ p
13. r
- c) [q ∧ (q → ¬p)] → ¬(p ∧ q)
1. [q ∧ (q → ¬p)] → ¬(p ∧ q)
Implicació material {p ⇒ q ≡ ¬p v q}
2. [q ∧ (¬q ∨ ¬p)] → ¬(p ∧ q)
Distributivitat de la conjunció {p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)}
3. [(q ∧ ¬q) ∨ (q ∧ ¬p)] → ¬(p ∧ q)
Inversa de la conjunció {p ∧ ¬p ≡ F}
4. [F ∨ (q ∧ ¬p)] → ¬(p ∧ q)
Neutre de la disjunció {p ∨ F ≡ p}
5. (q ∧ ¬p) → ¬(p ∧ q)
Llei de De Morgan per a la conjunció {¬(p ∧ q) ≡ ¬p v ¬q}
6. (q ∧ ¬p) → (¬p ∨ ¬q)
Implicació material {p ⇒ q ≡ ¬p v q}
7. ¬(q ∧ ¬p) ∨ (¬p ∨ ¬q)
Llei de De Morgan per a la conjunció {¬(p ∧ q) ≡ ¬p v ¬q}
8. (¬q ∨ p) ∨ (¬p ∨ ¬q)
Associativitat de la disjunció {p v (q v r) ≡ (p v q) v r} i Commutativitat de la disjunció {p v q ≡ q v p}
9. (¬q ∨ ¬q) ∨ (p ∨ ¬p)
Idempotència de la disjunció {p ∨ p ≡ p}
10. ¬q ∨ (p ∨ ¬p)
Inversa de la disjunció {p ∨ ¬p ≡ V}
11. ¬q ∨ V
Dominació de la disjunció {p v V ≡ V}
12. V (Tautologia)
