Predicati e funzioni

F1

 Scrivere la formula che rappresenta il fatto che un predicato P è simmetrico.

∀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)))

Laurent Théry
Last modified: Tue Apr 30 01:42:15 MEST 2002