MF

Exercice 1 Question 1

On a p : “Pierre a triché.”, t : “Thomas a triché.”, a :“Antoine a triché.”.

On veut "Si au moins l’un de nous trois a triché, alors nous avons triché tous les trois.”

Si ce traduit par implique

au moins l'un de nous ce traduit avec des ou (∨) d'où (p∨t∨a)⇒

tous les trois se traduit avec des et d'où (p ∨ t ∨ a) ⇒ (p ∧ t ∧ a)

Si Pierre a triché, alors Thomas a triché.

p=>t

Exercice 1 Question 2

Ce que je n'avais pas compris c'est que si on suppose que Pierre et Antoine mentent tojours alors on doit prendre la négation de leur affirmation

Pour comprendre la première négation

Pour la négation de l'affirmation d'Antoine il faut penser à

¬(A ⇒ B) est équivalent à A ∧ ¬B

Ceci donne les clauses C1 = p ∨ t ∨ a, C2 = ¬p ∨ ¬t ∨ ¬a, C3 = p et C4 = ¬t.

(une clause, c'est un ensemble de propositions atomiques (de la forme a ou ¬a) avec des "ou" entre eux, épicétou).

Exercice 2

Le top dans la déduction naturelle c'est les => et si on peut montrer le plus d'implications possibles c'est gagné

On utilise ainsi le plus souvent possible la règle I car dire que x=>y=>z ce serait top

((x ∧ y) ⇒ z ) ⇒ (x ⇒ (y ⇒ z ))

On suppose x ∧ y) ⇒ z |- vraie et on veut montrer x ⇒ (y ⇒ z )

On suppose x vraie et on veut montrer y=>z

On suppose y vraie et on veut montrer z

On aura besoin de la règle de conjonction illustrés comme les images ci dessous

Exercice 4 Question 1

last: Liste(alpha) - {Nil} -> alpha, qui extrait le dernier élément d'une liste n on vide.

changelast: alpha*Liste(alpha)->Liste(alpha) telle que changeLast(x,l) place l'élément x à la palace du denrier élement d el aliste l.

Exercice 4 Question 2

first(Cons(a,Cons(b,Cons(c,Nil))))=a est trop particulier

first(Cons(x,l))=x (2)

last(Cons(a,Cons(b,Cons(c,Nil))))=c est trop particulier

last(Cons(x , Nil)) = x< (3)/p>

last(Cons(x,l))=last(l) pour l # Nil (4)

changeFirst(a,Cons(b,Cons(c,Cons(d,Nil))))=Cons(a,Cons(c,Cons(d,Nil))) est trop particulier

changeFirst(a,Nil)=Nil (5)

changeFirst(x,Cons(y,l)) = Cons(x,l) (6)

changeLast(a,Cons(b,Cons(c,Cons(d,Nil))))=Cons(b,Cons(c,Cons(a,Nil))) est trop particulier

changelast(a,Nil)=Nil (7)

changeLast(x,Cons(y, Nil)) = Cons(x , Nil) (8)

changeLast(x,Cons(y,l)) = Cons(y,changeLast(x,l)) pour l # Nil (9)

On note 1. La prmeière hypothèse

On cherche à représenter cette hypothèse avec un axiome donc ici l'axiome 10.

d’une preuve, mais, dans cet exemple, on peut expliquer pourquoi l’auteur de cette preuve a choisi l’axiome 10, comme ceci :

On cherche à démontrer un théorème comportant des négations. Or, seuls les axiomes 9 et 10 contiennent des négations. L’axiome 9 ne fait qu’éliminer deux négations successives.

Cela ne semble pas approprié pour prouver ¬A à partir de ¬B. Il ne reste que l’axiome 10. On constate aussi que l’axiome 10, tel que, contient les hypothèses ¬A ⇒ B et ¬B.

Puis les lignes 2 et 3 utilisent l’hypothèse ¬A ⇒ V et la règle de modus ponens pour simplifier ce qui reste à prouver. On peut appliquer la règle de modus ponens P, ¬P ⇒ Q ⊢ Q en posant P = ( ¬A⇒ B) et Q = (( ¬A ⇒ ¬B) ⇒ ¬¬A ).

On a ainsi démontré la formule ((¬A ⇒ ¬B) ⇒ ¬¬A ).

¬B |- A

On suppose ¬B (hypothèse 2) et on veut montrer A.

Pour obtenir A , il suffit de démontrer ¬A ⇒ ¬B. Or P ⇒ ¬Q est une conséquence logique de ¬Q, qui est l’une des hypothèses. L’axiome 1 et le modus ponens permettent de démontrer ¬A ⇒ ¬B

Enfin, le modus ponens de l’étape 7 permet presque de déduire le résultat recherché à partir des formules démontrées dans les étapes 3 et 6.

On obtent ¬¬A Heuresement on peut compter sur l'axiome 9

On utilise le modus ponens et sur l'axiome 9 pour obtnenir A.