∀x.∀y. (P x y) ⇒ (P y x)
F2
Scrivere la formula che rappresenta il
fatto che un predicato P è transitivo.
∀x.∀y.∀z. ((P x y) ∧ (P y z)) ⇒ (P x z)
o
∀x.∀y.∀z. (P x y) ⇒ (P y z) ⇒ (P x z)
F3
Scrivere la formula che rappresenta il fatto che una funzione f
con un parametro è iniettiva. Si può
supporre l'esistenza di un predicato d'uguaglianza scritto x=y.
∀x.∀y. (f x)=(f y) ⇒ x = y
F4
Scrivere la formula che rappresenta il
fatto che una funzione f con un parametro è suriettiva.
∀y.∃x. y=(f x)
Deduzione naturale
G1
Dimostrare che
(∃x. ∀y. (P x y)) ⇒ (∀y. ∃x. (P x y)).
∃x. ∀y. (P x y)
∀y. (P a y) (P a c)
∃x. (P x c)
∃x. (P x c)
∀y. ∃x. (P x y)
(∃x. ∀y. (P x y)) ⇒ (∀y. ∃x. (P x y))
G2
Dimostrare che
(∀y. ∃x. (P x y)) ⇒ (∃x. ∀y. (P x y)).
Non esiste tale prova.
G3
Dimostrare che
(¬(∃x. (P x))) ⇒ (∀x. ¬(P x)).
(P c) ∃x. (P x)
¬(∃x. (P x)) False
¬(P c)
∀x. ¬(P x)
(¬(∃x. (P x))) ⇒ (∀x. ¬(P x))
G4
Dimostrare che
(∀x. ¬(P x)) ⇒ ¬ (∃ x. (P x)).
∃x. (P x)
(P c)
∀x. ¬(P x) ¬(P c)
False
False
¬(∃x. (P x))
(∀x. ¬(P x)) ⇒ ¬ (∃x. (P x))
G5
Dimostrare che (∃x. ¬(P x)) ⇒ ¬(∀x. (P x)).
∃x. ¬(P x)
∀x. (P x) (P c)
¬(P c) False
False
¬(∀x. (P x))
(∃x. ¬(P x)) ⇒ ¬(∀x. (P x))
G6
Dimostrare nella logica classica che
¬(∀x. (P x)) ⇒ (∃x. ¬(P x)).
¬(P c) ∃x. ¬(P x)
¬(∃x. ¬(P x)) False
(P c)
∀x. (P x)
¬(∀x. (P x)) False
∃x. ¬(P x) ¬(∀x. (P x)) ⇒ (∃x. ¬(P x)) G7
Dimostrare nella logica classica che
((∀x. (P x)) ⇒ Q) ⇒ ∃x. ((P x) ⇒ Q).
Prima supponiamo che ∀x. (P x) sia vero:
(∀x. (P x))⇒ Q
∀x. (P x)
Q
(P a) ⇒ Q
∃x. ((P x) ⇒ Q)
((∀x. (P x)) ⇒ Q) ⇒ ∃x. ((P x) ⇒ Q)
Secondo supponiamo che ¬(∀x. (P x)) sia vero, dunque per G1 si ha che ∃x. ¬(P x) è vero.
∃x. ¬(P x)
(P c) ¬(P c) False
Q
(P c) ⇒ Q
∃x. ((P x) ⇒ Q)
∃x. ((P x) ⇒ Q)
((∀x. (P x)) ⇒ Q) ⇒ ∃x. ((P x) ⇒ Q)
G8
Dimostrare che
(∃x. ((P x) ⇒ Q)) ⇒ ((∀x. (P x)) ⇒ Q).
∃x. ((P x)⇒Q)
(P a)⇒Q
∀x. (P x) (P a)
Q
Q
(∀x. (P x)) ⇒ Q (∃x. ((P x) ⇒ Q)) ⇒ ((∀x. (P x)) ⇒ Q)
G9
Dimostrare che
((∃x. (P x)) ⇒ Q) ⇒ ∀x. ((P x) ⇒ Q).
(∃x. (P x))⇒Q
(P c) ∃x. (P x)
Q (P c)⇒Q
∀x. ((P x) ⇒ Q) ((∃x. (P x)) ⇒ Q) ⇒ ∀x. ((P x) ⇒ Q)
G10
Dimostrare che
(∀x. ((P x) ⇒ Q)) ⇒ ((∃x. (P x)) ⇒ Q).
∃x. (P x)
∀x. ((P x) ⇒ Q) (P c) ⇒ Q
(P c)
Q
Q
(∃x. (P x)) ⇒ Q (∀x. ((P x) ⇒ Q)) ⇒ ((∃x. (P x)) ⇒ Q)
G11
Dimostrare che
(Q ⇒ (∀x. (P x))) ⇒ ∀x. (Q ⇒ (P x)) .
Q⇒ (∀x. ((P x))
Q
∀x. (P x)
(P c)
Q ⇒ (P c)
∀x. (Q ⇒ (P x))
(Q ⇒ (∀x. (P x))) ⇒ ∀x. (Q ⇒ (P x))
G12
Dimostrare che
(∀x. (Q ⇒ (P x))) ⇒ (Q ⇒ (∀x. (P x))).
∀x. (Q ⇒ (P x)) Q ⇒ (P c)
Q (P c)
∀x. (P x)
Q ⇒ (∀x. (P x))
(∀x. (Q ⇒ (P x))) ⇒ (Q ⇒ (∀x. (P x)))
G13
Dimostrare nella logica classica che
(Q ⇒ (∃x. (P x))) ⇒ (∃x. (Q ⇒ (P x))).
Supponiamo che la proposizione Q sia vera:
Q ⇒ (∃x. (P x))
Q
∃x.(P x)
(P c) Q ⇒ (P c)
∃x. (Q ⇒ (P x))
∃x. (Q ⇒ (P x))
(Q ⇒ (∃x. (P x))) ⇒ (∃x. (Q ⇒ (P x)))
Supponiamo che la proposizione ¬Q sia vera:
Q ¬Q False
(P a)
Q ⇒ (P a)
∃x. (Q ⇒ (P x))
(Q ⇒ (∃x. (P x))) ⇒ (∃x. (Q ⇒ (P x)))
G14
Dimostrare che
(∃x. Q ⇒ (P x)) ⇒ (Q ⇒ (∃x. (P x))).
∃x. (Q ⇒ (P x))
Q⇒ (P c)
Q
(P c)
∃x. (P x)
∃x. (P x)
Q ⇒ (∃x. (P x)) (∃x. Q ⇒ (P x)) ⇒ (Q ⇒ (∃x. (P x)))
G15
Dimostrare che
((∀x. (P x)) ∨ Q) ⇒ (∀x. (P x) ∨ Q).
(∀x. (P x))∨ Q
∀x. (P x) (P c)
(P c) ∨ Q
∀x. ((P x) ∨ Q)
Q (P c) ∨ Q
∀x. ((P x) ∨ Q)
(∀x. ((P x) ∨ Q)
((∀x. (P x)) ∨ Q) ⇒ (∀x. ((P x) ∨ Q))
G16
Dimostrare nella logica classica che
(∀x. ((P x) ∨ Q)) ⇒ ((∀x. (P x)) ∨ Q.
Supponiamo che la proposizione Q sia vera:
Q (∀x. (P x)) ∨ Q
(∀x. ((P x) ∨ Q)) ⇒ ((∀x. (P x)) ∨ Q)
Supponiamo che la proposizione ¬Q sia vera:
(∀x. (P x))∨ Q
∀x. (P x) (∀x. (P x))∨ Q
Q ¬Q False
(∀x. ((P x)) ∨ Q
(∀x. (P x)) ∨ Q
(∀x. ((P x) ∨ Q)) ⇒ ((∀x. (P x)) ∨ Q)
G17
Dimostrare che
((∃x. (P x)) ∨ Q) ⇒ ∃x. ((P x) ∨ Q).
(∃x. (P x))∨ Q
(∃x. (P x))
(P c) (P c) ∨ Q
∃x. ((P x) ∨ Q)
∃x. ((P x) ∨ Q)
Q (P a) ∨ Q
∃x. ((P x) ∨ Q)
(∃x. ((P x) ∨ Q)
((∃x. (P x)) ∨ Q) ⇒ (∃x. ((P x) ∨ Q))
G18
Dimostrare che
(∃x. ((P x) ∨ Q)) ⇒ (∃x. (P x)) ∨ Q.
∃x. ((P x) ∨ Q))
(P c) ∨ Q
(P c) ∃x. (P x)
(∃x. (P x)) ∨ Q
Q (∃x. (P x)) ∨ Q
(∃x. (P x)) ∨ Q
(∃x. (P x)) ∨ Q
(∃x. ((P x) ∨ Q)) ⇒ (∃x. (P x)) ∨ Q
G19*
Dimostrare che
(P a) ⇒ ((∀x. ((P x) ⇒ (Q x))) ⇒ (Q a)).
∀x. ((P x) ⇒ (Q x)) (P a) ⇒ (Q a)
(P a) (Q a)
(∀x. ((P x) ⇒ (Q x))) ⇒ (Q a) (P a) ⇒ ((∀x. ((P x) ⇒ (Q x))) ⇒ (Q a))
G20*
Dimostrare che
(∃x. ((P x) ⇒ (Q x))) ⇒ ((∀x. (P x)) ⇒ (∃x. (Q x))).
∃x. ((P x) ⇒ (Q x))
(P c) ⇒ (Q c)
∀x. (P x) (P c)
(Q c)
∃x. (Q x)
∃x. (Q x)
(∀x. (P x)) ⇒ (∃x. (Q x)) (∃x. ((P x) ⇒ (Q x))) ⇒ ((∀x. (P x)) ⇒ (∃x. (Q x)))
*G21
Dimostrare che
(∀x. (P x) ⇒ (Q x)) ⇒ ((∃x. (P x)) ⇒ (∃x. (Q x))) .
∃x. (P x)
∀x. ((P x) ⇒ (Q x)) (P c) ⇒ (Q c)
(P c) (Q c)
∃x. (Q x)
∃x. (Q x) (∃x. (P x)) ⇒ (∃x. (Q x))
(∀x. (P x) ⇒ (Q x)) ⇒ ((∃x. (P x)) ⇒ (∃x. (Q x))) *G22
Dimostrare che
(∃x. ((P x) ∧ (Q x))) ⇒ (∃x. ((Q x) ∧ (P x))).
∃x. ((P x) ∧ (Q x))
(P c) ∧ (Q c) (Q c)
(P c) ∧ (Q c) (P c)
(Q c) ∧ (P c) ∃x. ((Q x) ∧ (P x))
∃x. ((Q x) ∧ (P x))
(∃x. ((P x) ∧ (Q x))) ⇒ (∃x. ((Q x) ∧ (P x)))