Démontrer une implication
Hello tout le monde, la langue française n'est pas ma langue maternelle et c'est mon premier poste ici. veuillez patienter avec moi .
Ok, ma 1ere question est très basique. Je sais que lorsqu'on va démontrer une implication A-->B on suppose que la proposition A est vraie et on démontre que B est ainsi vraie. Mais, logiquement parlant, comment peut-on 'démontrer' une implication sans prendre toute les valeurs des 2 propositions A et B, comme on le fait dans un tableau de vérite ?
Merci pour tout !
Ok, ma 1ere question est très basique. Je sais que lorsqu'on va démontrer une implication A-->B on suppose que la proposition A est vraie et on démontre que B est ainsi vraie. Mais, logiquement parlant, comment peut-on 'démontrer' une implication sans prendre toute les valeurs des 2 propositions A et B, comme on le fait dans un tableau de vérite ?
Merci pour tout !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
hey, je n'ai pas compris ce tu vous veux dire. Sorry. Est-ce que tu peux élaborer encore plus ? Merci beaucoup !
[Inutile de recopier le dernier message. AD]
2/ Si A alors .......
Or ton premier post demande pourquoi on n'écrit que (2). Et bien parce que (1) est général et évident (ou un axiome si tu préfères)
"1/ Si non(A) alors (A=>B) est conséquence évidente " k, c'est la premiere fois que je vois ca, c'est pourqupoi j'ai pas compris. on appelle quoi ce theoreme ?
mon idee etait pourquoi lorsqu'on demande de prouver une implication pourquoi on prends toujous la proposition A comme vrai et on demontre que B est vrai ? pourquoi pas prendre A est fausse et arriver au meme resultat ? quel est l'utilite de tableau de verite de A-->B donc ?
( il ya un peu d'ambiguite dans le logique qui a traine avec moi depuis le college et je cherche a bien comprendre et l'illucider, c'est pourquoi je cherche a connaitre ces details qui semblre etre )
merci !
Donc si tu veux prouver A=>B, tu peux toujours dire:
dans le cas où non(A) (autrement dit A=>Tout), il est évident qu'alors A=>B
dans le cas où A, alors je dois travailler pour déduire B. Voici mon travail: blablabla
Cette structure est abrégée en :
Je veux prouver A=>B: bin, bin je suppose A (sinon c'est évident), blablabla.
[small]*** cette abréviation est légitime car on peut, à partir de choses incontestables prouver "sa vérité":
De non(A), tu peux déduire non(Tout)=>non(A), donc A=>Tout
De A=>Tout, tu peux déduire non(Tout)=>non(A), et, en admettant non(Tout), déduire non(A)[/small]
Petite: car de toute façon, la colonne de $A\to B$ sera contestée par les mêmes gens qui douteraient de ton raisonnement commençant par "supposons A" (et même bien plus de gens encore).
1°) $T\subseteq P(T)$
2°) pour tous $a,b\in X$, $a \Delta (b \Delta a)\in P(T)$
3°) pour tous $p,q,r\in X$, $[p \Delta (q \Delta r)] \Delta [(p \Delta q) \Delta (p \Delta r)] \in P(T)$
4°) pour tous $x,y\in X$, si $x\in P(T)$ et $x \Delta y\in P(T)$ alors $y \in P(T)$.
On a les résultats suivants:
A) pour tout $T \subseteq X$, $x \Delta x\in P(T)$.
En effet d'après 2°) (avec $a:= x$ et $b:= x \Delta x$), on a $x \Delta [(x \Delta x) \Delta x] \in P(T)$ et d'après 3°) (avec $p:= x$, $q:= \Delta x$ et $r:= x$) on a $\big ( x \Delta [ (x \Delta x) \Delta x]\big ) \Delta \big ( [x \Delta (x \Delta x)] \Delta (x \Delta x)\big ) \in P(T)$ donc on a aussi (d'après 4°) ) $[x \Delta (x \Delta x)] \Delta (x \Delta x) \in P(T)$ (*). Puique d'après 2°) (avec $a:=b:=x$) on a $x \Delta (x \Delta x) \in P(T)$, on a également d'après (*) et 4°), $x \Delta x \in P(T)$ ce qui est le résultat voulu.
pour tous $a,b\in X$ et pour toute partie $S$ de $X$, si $b \in P\left( S \cup \{a\}\right)$ alors $a \Delta b \in P(S)$.
Soit $R$ l'ensemble de tous les $x\in X$ tels que $a \Delta x \in P(S)$. Alors $a\in R$ d'après le résultat A ci-dessus. De plus, $S$ est contenu dans $R$ (en effet, soit $y\in S$. Alors d'après 2°), on a aussi $y \Delta (a \Delta y) \in P(S)$ et donc via 4°), $a \Delta y \in P(S)$).
Soient $u,v\in X$ tels que $u$ et $u \Delta v$ sont dans $R$. Montrons que $v \in R$. en effet on a par définition, $a \Delta u \in P(S)$ et $a \Delta (u \Delta v)$ in $P(S)$ mais aussi (cf 3°) $[a \Delta (u \Delta v)] \Delta [(a \Delta u) \Delta (a \Delta v)]\in P(S)$ et donc (4°) $(a \Delta u) \Delta (a \Delta v)\in P(S)$ puis $a \Delta v \in P(S)$ et donc $v \in R$. Compte tenu de la définition de $P(S \cup \{a\})$ (comme plus petit ensemble ayant les propriétés listées précédemment) on a donc $P(s \cup \{a\}) \subseteq R$ et donc $b \in R$ d'où le résultat.
Concluons ce paragraphe par trois remarques assez évidentes:
C) Soit $E, F$ des parties de $X$ avec $E\subseteq F$. Si pour tous $u,v \in X$ tels que $u$ et $u \Delta v$ dont dans $F$ alors $v\in F$, et si pour tous $x,y,z$, $x (\Delta y \Delta x)$ et $[x \Delta (y \Delta z)] \Delta [(x \Delta y) \Delta (x \Delta z)] $ appartiennent à $F$, alors $P(E) \subseteq F$.
Ceci n'edst rien d'autre qu'une reformulation de la définition de $E$ (comme plus petit ensemble ayant lesdites propriétés)
D) Si $G$ et $H$ sont des parties de $X$ telles que $G \subseteq H$ alors $P(G) \subseteq P(H)$.
C'est une conséquence immédiate de C) ci-dessus.
Par exemple $P (\emptyset) \subseteq P(K)$ pour toute partie $K$ de $X$.
LA réciproque de est vraie.
Soient $S\subseteq X$, $a,b \in X$, supposons que $a \Delta b \in P(S)$. Alors par D), $a\Delta b \in P(S \cup \{a\})$, mais on a aussi $a \in P(S \cup \{a\})$ et donc par 4°), $b \in P(S \cup \{a\})$.
********
C'est le résultat qui permet de faire les choses en pratique. Par exemple, on va établir que
pour tous $a,b,c\in X$, $[a \Delta (b \Delta c)] \Delta [b \Delta (a \Delta c)] \in P(\emptyset)$.
En effet, on voit que $a$ et $a \Delta (b \Delta c)$ appartiennent à $P\left( \{b,a,a \Delta (b \Delta c)\}\right)$. Donc (4°) $b \Delta c \in P\left( \{a,b,a \Delta (b \Delta c)\}\right)$). Donc puisque $b \in P\left( \{a,b,a \Delta (b \Delta c)\}\right)$, d'après (4°), $c \in P\left( \{a,b,a \Delta (b \Delta c)\}\right)$. Donc (d'après , $a \Delta c \in P\left( \{b,a \Delta (b \Delta c)\}\right)$. Donc à nouveau d' après , $b \Delta (a \Delta c) \in P\left( \{a \Delta (b \Delta c)\}\right)$. Donc à nouveau d'après , $[a \Delta (b \Delta c)] \Delta [b \Delta (a \Delta c)] \in P(\emptyset)$.
#########
APPLICATIONS DE CE QUI PRECEDE A LA LOGIQUE:
Dans la suite On considère l'ensemble $\mathfrak X$ des formules logiques propositionelles écrites avec des lettres et les symboles $\vee$ et $\neg$. Selon l'usage, si $A,B$ sont des formules, $A \Rightarrow B$ est l'abréviation de
$(\neg A) \vee B$. Il existe un sous-ensemble $\mathfrak T\subseteq \mathfrak X$ appelé "ensemble des théorèmes de logique classique" qui a notamment les propriétés suivantes:
i) pour toutes formules $A,B$, si $A \in \mathfrak T$ alors $A \vee B \in \mathfrak T$.
ii) pour toutes formules $A,B$, si $A \vee B \in \mathfrak T$ alors $B \vee A \in \mathfrak T$
iii) pour toutes formules $A,B,C$, si $A \vee (B \vee C)\in \mathfrak T$ alors $(A \vee \vee C \in \mathfrak T$ et réciproquement.
iv) pour toute formule $D \in \mathfrak X$, $(\neg D) \vee D \in \mathfrak T$.
v) pour toutes formules $A,B,C$, si $A \Rightarrow C$ et $B \Rightarrow C$ sont dans $\mathfrak T$ alors $(A \vee \Rightarrow C \in \mathfrak T$
vi)pour toutes formules $A,B$, si $A$ et $A \Rightarrow B$ sont dans $\mathfrak T$ alors $B\in \mathfrak T$ (modus ponens).
On va voir que $\mathfrak T$ possède des propriétés permettant l'application des résultats A,B,C et D ci-dessus. En effet:
Avant tout, une remarque (qui découle de i) et ii)):
vii)pour toutes formules $A,B$, si $A \in \mathfrak T$ alors $B \vee A \in \mathfrak T$.
Dans la suite nous abrégerons, pour une formule $S$, "$S \in \mathfrak T$ par $\vdash S$".
E) Pour toutes formules $A,B$, $A \Rightarrow (B \Rightarrow A) \in \mathfrak T$.
$A \Rightarrow (B \Rightarrow A)$ est l'abréviation de $(\neg A) \vee [\neg B \vee A]$.
On a successivement:
$\vdash (\neg A) \vee A$ (iv)
$\vdash A \vee (\neg A)$ (ii)
$\vdash (\neg \vee [A \vee (\neg A)]$ (vii)
$\vdash [(\neg \vee A] \vee (\neg A)$ (iii)
$\vdash (\neg A) \vee [(\neg \vee A]$ (ii).
Ce qui est le résultat annoncé.
F) Pour toutes formules $P,Q,R$, $[P \Rightarrow (Q \Rightarrow R)] \Rightarrow [(P \Rightarrow Q)\Rightarrow (P \Rightarrow R)] \in \mathfrak T$.
On convient que $\neg$ est prioritaire sur $\vee$ pour limiter l'usage des parenthèses et alléger les notations.
la formule de l'énoncé est l'abréviation de $\left [ \neg P \vee (\neg Q \vee R)\right ] \Rightarrow \left [ (P \Rightarrow Q) \Rightarrow (P \Rightarrow R) \right ]$. Ce qui va suivre est technique et peut être sauté en première lecture. Une remarque tout de même:
viii) pour toutes formules $A,B,C$, si $A \vee (B \vee C) \in \mathfrak T$ alors $C \vee (A \vee \in \mathfrak T$ et vice versa. En effet, $A \vee (B \vee C)$ si et seulement si $(A \vee B ) \vee C \in \mathfrak T$ par iii), si et seulement si $C \vee (A \vee \in \mathfrak T$ par (ii).
[size=x-small]d'après v), il suffit de montrer
e1) $\vdash \neg P \Rightarrow [(P \Rightarrow Q) \Rightarrow (P \Rightarrow R)]$ et
e2) $\vdash (\neg Q \vee R) \Rightarrow [(P \Rightarrow Q) \Rightarrow (P \Rightarrow R)]$.
Pour établir e2), il suffit d'après v) d'établir
e21) $\vdash \neg Q \Rightarrow [(P \Rightarrow Q)\Rightarrow (P \Rightarrow R) ]$ et
e22) $\vdash R \Rightarrow [(P \Rightarrow Q) \Rightarrow (P \Rightarrow R)]$.
Compte tenu de ce qu'abrège "$\Rightarrow $" et de la remarque viii), établir e21) revient à établir
e'21) $\vdash [(P \Rightarrow Q)] \Rightarrow [(P \Rightarrow R) \vee \neg \neg Q]$, ce qui revient encore à établir d'après v),
e211) $\vdash \neg P \Rightarrow [ (\neg P \vee R) \vee \neg \neg Q]$
e212) $\vdash Q \Rightarrow [(\neg P \vee R) \vee \neg \neg Q]$.
on montre ces points ci-dessous.
e1: $\vdash \neg \neg P \vee \neg P$ (iv)
$\vdash (\neg \neg P \vee \neg P) \vee R$ (i)
$\vdash \neg \neg P \vee (\neg P \vee R)$ (iii)
$\vdash (\neg P \vee R)\vee \neg \neg P$ (ii)
$\neg (\neg P \vee Q) \vee [(\neg P \vee R)\vee \neg \neg P] $ (vii)
$\vdash [\neg (\neg P \vee Q) \vee (\neg P \vee R)] \vee (\neg \neg P)$ (iii)
$\vdash \neg \neg P \vee [\neg (\neg P \vee Q) \vee (\neg P \vee R)]$ (ii)
$\vdash \neg P \Rightarrow [(P \Rightarrow Q) \Rightarrow (P \Rightarrow R)] $ (qualité d'abréviation de $\Rightarrow$)
e211: $\vdash \neg \neg P \vee \neg P$ (iv)
$\vdash (\neg \neg P \vee \neg P) \vee R$ (i)
$\vdash \neg \neg P \vee (\neg P \vee R)$ (iii)
$\vdash [\neg \neg P \vee (\neg P \vee R)] \vee \neg \neg Q$ (i)
$\vdash \neg \neg P \vee [(\neg P \vee R) \vee \neg \neg Q] = \neg P \Rightarrow [(\neg P \vee R) \vee \neg \neg Q] $ (iii) + abréviation $\Rightarrow$.
e212: $\vdash \neg \neg Q \vee \neg Q$ (iv)
$\vdash (\neg P \vee R) \vee (\neg \neg Q \vee \neg Q)$ (vii)
$\vdash [(\neg P \vee R) \vee \neg \neg Q] \vee \neg Q$ (iii)
$\vdash \neg Q \vee [(\neg P \vee R) \vee \neg \neg Q] = Q \Rightarrow [(\neg P \vee R) \vee \neg \neg Q]$ (ii) + abréviation
e22: $\vdash \neg R \vee R$ (iv)
$\vdash R \vee \neg R$ (ii)
$\vdash \neg P \vee (R \vee \neg R)$ (vii)
$\vdash (\neg P \vee R) \vee \neg R$ (iii)
$\vdash \neg (\neg P \vee Q) \vee [(\neg P \vee R) \vee \neg R]$ (vii)
$\vdash \neg R \vee [\neg (\neg P \vee Q) \vee (\neg P \vee R)] = R \Rightarrow [(P \Rightarrow Q) \Rightarrow (P \Rightarrow R)]$ (viii) et abréviation.
Comme annoncé plus haut, via v), e21 est conséquence de e211 et e212, e2 conséquence de e21 et e22 et la propriété voulue est conséquence de e1 et e2.[/size]
Les points E), F) et vi) garantissent que, en notant $\Delta$ l'application qui aux formules $A,B$ fait correspondre la formule $A \Rightarrow B$, $\mathfrak T$ satisfait les conditions des énoncés A,B,C,D et que en particulier, avec les notations de la première partie, $P (\mathfrak T) \subseteq \mathfrak T$, et donc notamment, $P(\mathfrak T)=\mathfrak T$.
En particulier , d'après la propriété B ci-dessus, pour montrer que $A\Rightarrow B \in \mathfrak T$, il suffit de montrer que $B \in P(\mathfrak T \cup \{A\})$ Cette manière de faire en mathématiques est précisément ce qui s'appelle supposer ("supposons, A, démontrons B et alors on aura montré que A implique B" ).
L' énoncé B de la première partie s'appelle parfois "théorème de déduction".
Un exemple (on abrège $F \in P(\mathfrak T \cup \{A,B,C,D,...\})$ par $A,B,C,D,... \vdash F$; le modus ponens est évidemment encore satisfait vu la définition de $P$).
G) Pour toutes formules $A,B,C$,
$\vdash (A \Rightarrow \Rightarrow [(B \Rightarrow C) \Rightarrow (A \Rightarrow C)]$ ("syllogisme")
en effet,
1.$A,A \Rightarrow B, B \Rightarrow C \vdash A$ (axiome).
2.$A,A \Rightarrow B, B \Rightarrow C \vdash A \Rightarrow B$ (axiome).
3.$A,A \Rightarrow B, B \Rightarrow C \vdash B$ (modus ponens 1 & 2).
4.$A,A \Rightarrow B, B \Rightarrow C \vdash B \Rightarrow C$ (axiome).
5.$A,A \Rightarrow B, B \Rightarrow C \vdash C$ (modus ponens 3 & 4).
6. $A \Rightarrow B, B \Rightarrow C \vdash A \Rightarrow C$ (théorème de déduction)
7. $A \Rightarrow B \vdash (B \Rightarrow C) \Rightarrow (A \Rightarrow C)$ (théorème de déduction)
8. $\vdash (A \Rightarrow \Rightarrow [(B \Rightarrow C) \Rightarrow (A \Rightarrow C)]$ (théorème de déduction).
On peut également faire du théorème de déduction un algorithme (qui produit des preuves gigantesques).
Merci de nouveau pour la réponse détaillée ! Ça a pris beaucoup de temps pour rédiger, merci !