Logique, axiomes et théories

[theguitarist]

Bonjour !
Et voilà c'est l'heure des révisions de l'année de sup, et j'ai un peu de mal concernant la démonstration de la proposition suivante :

(P=>Q) <=> (nonP ou Q)

la formule en elle même est plutôt logique, d'ailleurs elle est vite faite en faisant les tables de vérité, mais en cours on utilise les théorèmes et les théories issues de certains axiomes


Avant d'énoncer la proposition, on avait posé que les axiomes suivants :

soit une théorie T:
- R1 : si T contient P et si T contient (P=>Q) alors T contient Q
- R2 : si T' est la théorie obtenue en adjoignant P à T et si T' contient Q alors T contient (P=>Q)
- R3 : si T contient P et non P alors on T est dite contradictoire, donc si T'=T+P et si T' contradictoire, alors T contient non P
- R4 : si non(non P) est un théorème de T, alors P aussi
- R5 : si P et Q sont des théorèmes de T alors (P ou Q) en est un aussi.
- R6 : si (P=>R) et (Q=>R) sont des théorèmes de T, alors ((P ou Q) => R) est un théorème de T


voilà voilà désolé pour le baratin, maintenant voici la démonstration faite en cours :


(1) (P=>Q) = > (nonP ou Q)
T'=T+(P=>Q)
T' contient (nonP => (nonP ou Q)) (ceci a été démontré auparavant)
T''=T'+P
T'' contient (P=>Q)
T'' contient P
T'' contient Q (R1)
T'' contient (P ou Q) (R5)
T' contient P=>(non P ou Q) je ne comprend pas cette ligne
T' contient (nonP => (nonP ou Q))
T' contient ( (P ou non P) => (non P ou Q) ) (R6)
T' contient (non P ou Q) (R1)
T contient ( (P=>Q) => (non P ou Q) ) (R2)


voilà mis à part cette ligne qui est un vrai mystère pour moi, le reste de la démonstration est bien assimilée, mais comme j'aime pas me contenter de d'apprendre par cœur, j'espère que quelqu'un pourra m'éclairer =D

Merci d'avance !

Quentin
-----

[karlp]

Bonjour

Je connais quelqu'un ici qui pourra sans doute vous aider vraiment (c'est à dire qu'il ne vous donnera peut-être pas la solution tout de suite).

Je vous avoue que je ne parviens pas même à comprendre comment vous obtenez la formule T'=T+(P=>Q) à partir des axiomes

[theguitarist]

T' est une théorie, un ensemble de théorèmes.

Elle est définie de telle sorte que ce soit T à laquelle on ajoute un théorème supplémentaire, à savoir (P=>Q). On ne l'a pas prouvé, mais juste définie comme ça.

[Tiky]

Bonjour,

Il faut je pense appliquer la règle 2. T'' est obtenu en adjoignant à T' la proposition P.
Si tu montres que (non P) ou Q appartient à T'', c'est gagné.

[A voir en vidéo sur Futura]

[karlp]

T' est une théorie, un ensemble de théorèmes.

Elle est définie de telle sorte que ce soit T à laquelle on ajoute un théorème supplémentaire, à savoir (P=>Q). On ne l'a pas prouvé, mais juste définie comme ça.

Ce que je ne comprends pas c'est que R2 dit que T' est obtenue en adjoignant P à T , et pas en adjoignant (P implique Q) à T: comment parvenez vous à ce résultat ?

[theguitarist]

Haa d'accord !
mais à ce moment là j'ai peut être la solution mais il me faut recourir à un axiome supplémentaire, qu'on a vus dans le cours (mais comme on les à vus juste après la démonstration je me suis dit que ça ne servirait pas..)

en fait voici R7 (la conjonction) :

R7 : si (P et Q) est un théorème de T alors P est un théorème de T et Q est un théorème de T également.

maintenant si on reprend la démo :


T'=T+(P=>Q)
T' contient (nonP => (nonP ou Q)) (ceci a été démontré auparavant)
T''=T'+P
T'' contient (P=>Q)
T'' contient P
T'' contient Q (R1)
T'' contient (P ou Q) (R5)

---------------------------------
T'''=T''+ (P et non Q)
T''' contient P,Q,(P et non Q), non Q (R7) contradiction !
T'' contient non ( P et non Q) (R3 règle de l'absurde)
T'' contient (Q ou non P) (règle de Morgan)
---------------------------------

T' contient P=>(non P ou Q) (donc du fait de R2 comme l'a dit Tiky)
T' contient (nonP => (nonP ou Q))
T' contient ( (P ou non P) => (non P ou Q) ) (R6)
T' contient (non P ou Q) (R1)
T contient ( (P=>Q) => (non P ou Q) ) (R2)


j'avoue que je ne sais pas pourquoi le prof n'a écrit R7 qu'après, mais je ne vois pas d'autres façon de faire... est ce quand même correct ?

[karlp]

Désolé theguitarist de vous ennuyer avec ma question alors que c'est vous qui demandiez de l'aide.
Accepterez vous de répondre uniquement à la question que j'ai posée au message 5 ? et je vous promets de ne pas pas vous harceler au delà .

[theguitarist]

Ce que je ne comprends pas c'est que R2 dit que T' est obtenue en adjoignant P à T , et pas en adjoignant (P implique Q) à T: comment parvenez vous à ce résultat ?

hum R2 ne stipule par que T' est obtenue en adjoignant P à T, c'est justement une condition nécessaire à la conclusion : (P=>Q) appartient à T.

Si T est une théorie quelconque. T' = T + P. Si au fil de la démonstration, on arrive à montrer que T' contient un théorème Q, le théorème R équivalent à P=>Q est un théorème de T.

[theguitarist]

Le temps d'écrire mon avant dernier post, je n'avais pas vu que vous en aviez publié un excusez moi !

[karlp]

hum R2 ne stipule par que T' est obtenue en adjoignant P à T, c'est justement une condition nécessaire à la conclusion : (P=>Q) appartient à T.

Si T est une théorie quelconque. T' = T + P. Si au fil de la démonstration, on arrive à montrer que T' contient un théorème Q, le théorème R équivalent à est un théorème de T.

Merci pour votre réponse. j'avais en effet mal lu (manqué le "si").