Logique

par **alexis6** » 26 Mar 2015, 20:06

Bonjour,

En ce moment, je travaille un peu de logique. Mais j'ai beaucoup de confusions avec un livre que je ne trouve pas très clair, pas très rigoureux...

On essaye d'abord d'introduire du vocabulaire comme énoncé, expression mathématique, proposition, formule propositionnelle, variable propositionnelle, vrai, faux, interprétation, quantification, objet mathématique. Ce vocabulaire semble assez évident, mais comme il n'est pas défini rigoureusement, ce n'est pas clair dans ma tête:
- qu'est ce qui est objet mathématique, qu'est ce qui n'est pas objet mathématique? Ca semble peut être bête, mais il me semble que c'est la plus petite " brique " en mathématique, et on parle vaguement.
- quelle est la différence entre un énoncé et une expression mathématique?
- la différence entre une formule propositionnelle et une variable propostionnelle?
- la différence entre proposition et énoncé mathématique? Une proposition, c'est juste un énoncé qu'on dit vrai ou faux?
- qu'est ce qui est vrai, qu'est ce qui est faux? Quelle est la nature de ces mots, et des dérivés plausible et satisfiable? Pour moi, ce qui est vrai c'est ce qui marche, qui fonctionne concrètement, lorsque les conditions sont réalisées. Cela reste vague...

Après, je n'ai pas vraiment compris la différence entre ce qui est et ce qui n'est pas logique. En particulier la phrase: " les énoncés ne sont quasiment jamais des formules propositionnelles ". Qu'est ce qui différencie une formule propositionnelle et une formule non propositionnelle. Comment passe t-on d'un énoncé avec des propositions aux énoncés quantifiées, ou à des propositions plus complexes. Quel est l'interêt de la logique, dans les calculs usuels?

Ensuite, on introduit les connecteurs logiques. Mais on ne les définit pas avec rigueur, encore une fois. On dit qu'on peut construire de nouvelles formules à partir de variables et de connecteurs logiques, mais on n'en précise pas les règles et les propriétés principales...

J'ai quelques questions sur ces connecteurs, en particulier, ce que je trouve le plus obscur, c'est l'implication et la négation:

- concernant l'implication: Personnellement, ce que je ne comprends pas, c'est la nature de l'implication... Je vois cela comme la modification d'une proposition, pour en arriver à une autre, une déduction. C'est un raisonnement, une démontration, avec une suite d'opérations vraies ou fausses.

Naïvement, on pourrait dire que si toutes les déductions sont vraies ( par exemple 2*3=6, 6-3=3, et 3+4=7 l'implication est donc 2*3 - 3 +4 = 7 ), l'implication est vraie, et si il existe une déduction fausse, alors l'implication est fausse. Par exemple si je dis que 6-3=2, mon implication finale sera fausse.
Mais c'est naïf, car à partir d'une proposition P vraie, on peut faire une déduction fausse, et en déduire une autre proposition Q fausse. Puis à partir de cette proposition Q, refaire une déduction fausse, et avoir une proposition vraie R ( puisque du faux peut impliquer du vrai ). Ainsi comme P est vraie, et Q est vraie, la logique nous dit que l'implication est vraie. Mais pourtant le raisonnement est tout à fait faux.

Finalement, il s'agit de savoir pour deux propositions P et Q, laquelle des deux assertions ci dessos est vraie:
- P est vrai, Q est vrai, alors l'implication est vraie
- l'implication est vraie, alors on est dans la configuration P vraie, Q vraie ou P faux, Q vraie ou faux

J'ai aussi l'impression que l'on se sert de l'implication pour définir l'implication. Ainsi si P est vrai, Q est vrai, l'implication est vraie. P vraie et Q vrai implique que l'implication est vraie... Ou l'implication vraie implique que " P vraie, Q vraie ", ou " P faux, Q vraie ou faux " .

- concernant la négation, on dit seulement que pour une proposition P, si P est vraie, non(P) est fausse, si P est fausse, non(P) est vraie. Ce qui m'embête, c'est que je n'ai pas l'impression d'avoir une vraie définition de la négation. Il me semble que pour une proposition P, la négation de celle-ci est unique. Or comme c'est défini on pourrait croire naïvement que si P est vraie, toute proposition fausse est la négation de P. Donc ma question, c'est comment construire la négation d'une proposition.

Bon voila, ça fait beaucoup de questions, j'espère que certains d'entre vous pourront m'aider pour certaines d'entre elles. J'espère avoir été assez clair pour mes questions.

Si, de plus, vous pourriez m'indiquer un bon ouvrage de logique, je suis également preneur

par **chombier** » 26 Mar 2015, 20:59

Ca devient généralement plus clair avec la logique du premier ordre, avec les quel que soit, il existe, etc. Par exemple :

est vraie car, quand on remplace x par n'importe quel entier, la proposition obtenue est vraie.

Avec x=7, on obtient 7>1 qui est vraie, et 49>4, qui est vraie.
Avec x=-1, on obtient 7>-1 qui est fausse, et 1>4 qui est fausse
Avec x=-7, on obtient -7>1 qui est fausse, et 49>4 qui est vraie

D'après la table de vérité de l'implication
avec x=7, (vrai => vrai) = vrai, donc tout va bien
avec x=-1, (faux => vrai) = vrai, donc tout va bien
avec x=7, (faux => faux) = vrai, donc tout va bien

(Et évidemment ça marche avec tous les autres nombres, à démontrer :lol3: ).

En revanche, la réciproque est fausse :

est fausse
avec x=7, (vrai => vrai) = vrai, donc tout va bien
avec x=-1, (vrai => faux) = faux, donc ON A TROUVE UN CONTRE EXEMPLE
avec x=7, (faux => faux) = vrai, donc tout va bien

L'implication est fausse puisque en remplacant x par -1, elle donne une expression fausse.

Un autre exemple assez parlant :

est vraie car la prémisse sera toujours fausse, on dit que la prémisse est vide.

par **mathelot** » 26 Mar 2015, 21:18

Pour le Vrai et le Faux, il y a une application qui transforme

en

par exemple,ie, il y a la possibilité
de calculer des booléens en remplaçant les prédicats par leurs valeurs de vérité 0 ou 1.

Krivine théorie des ensembles
J-F Pabion Logique mathématique chez Hermann
Demazure cours d'Algèbre
Modèles logique et systèmes d'I.A par Alain Dussauchoy chez Hermès
Elements d'I.A par Henri Farreny chez Hermès

ii) il ne faut pas confondre implication et déduction.
L'implication est un connecteur, comme un "point-virgule", assujeti
aux règles logiques par sa table de vérité.
La déduction se fait par "modus ponens", en supposant la prémisse vraie,
et en écrivant la conclusion.

par **alexis6** » 26 Mar 2015, 21:57

chombier a écrit:Ca devient généralement plus clair avec la logique du premier ordre, avec les quel que soit, il existe, etc. Par exemple :

est vraie car, quand on remplace x par n'importe quel entier, la proposition obtenue est vraie.

Avec x=7, on obtient 7>1 qui est vraie, et 49>4, qui est vraie.
Avec x=-1, on obtient 7>-1 qui est fausse, et 1>4 qui est fausse
Avec x=-7, on obtient -7>1 qui est fausse, et 49>4 qui est vraie

D'après la table de vérité de l'implication
avec x=7, (vrai => vrai) = vrai, donc tout va bien
avec x=-1, (faux => vrai) = vrai, donc tout va bien
avec x=7, (faux => faux) = vrai, donc tout va bien

(Et évidemment ça marche avec tous les autres nombres, à démontrer :lol3: )

est vraie car la prémisse sera toujours fausse, on dit que la prémisse est vide.

Merci pour cette réponse.

Je remarque que quand on démontre l'implication pour " tous les autres nombres ", on suppose juste la première proposition vraie, par exemple x>2, pour ensuite démontrer que si x>2 est vraie, x^2>4 est vrai. Et on a pas besoin de supposer les 3 autres cas.

Pour moi on ne démontre pas les autres cas pour deux raisons:
- si le faux implique du vrai, l'implication est vraie, et si le faux implique du faux, l'implication est vraie. Donc dans tous les cas, puisqu'une proposition ne peut être que vraie ou fausse, l'implication est vraie
- on n'a pas besoin de montrer que si la première proposition est vraie, la seconde est fausse est une implication fausse, puisqu'on a déjà montré que si la première était vraie la seconde était vraie était une implication vraie. En effet v --> f est la négation de v --> v ( ce qui est faux, c'est ce qui n'est pas vrai ).

Ainsi, il suffit juste de démontrer que si une première proposition est vraie, la seconde est également vraie.

Mais démontrer, c'est une suite d'arguments finalement. Je crois que l'on peut considérer l'implication comme une suite d'arguments.

Par exemple pour l'implication x>2 --> x^2>4
On peut décomposer en cette suite d'arguments:
x>2
1 - x>2 est vrai par hypothèse donc x est plus grand que tout nombre en dessous de 2 est vrai, en particulier x est plus grand que 0 est vrai.
2- x est plus grand que 0 est vrai, donc x est positif est vrai
3- dans une inégalité, on peut multiplier par un nombre positif sans changer le sens de l'inégalité
4- on peut prendre le nombre positif x
5- on obtient l'inégalité x*x>2x
6- x*x s'écrit x^2
7- on peut donc écrire x^2>2x
8- par hypothèse x>2 est vrai
9- 2 est un nombre positif est vrai, on peut donc multiplier par 2 cette inégalité
10 on obtient 2x>4 vrai
11 l'inégalité est transitive, donc si x^2>2x vrai et 2x>4 vrai alors x^2>4 vrai

Si j'avais écrit un de ces onze arguments faux, comme le faux peut impliquer du vrai ou du faux, le résultat final aurait pu être vrai ou faux. Dans le cas où j'ai démontré du vrai, je suis parti d'une proposition vraie, et j'en déduis une proposition vraie. Pourtant l'implication est-elle vraie? Non, puisque j'ai fait une erreur de raisonnement.

J'en déduis par conséquent que pour démontrer qu'une implication est vraie, il faut deux choses:
- que le vrai implique du vrai, que le vrai n'implique pas du faux.
- que tous les arguments que j'avance soient vrais

par **alexis6** » 26 Mar 2015, 22:06

mathelot a écrit:Pour le Vrai et le Faux, il y a une application qui transforme

en

par exemple,ie, il y a la possibilité
de calculer des booléens en remplaçant les prédicats par leurs valeurs de vérité 0 ou 1.

Krivine théorie des ensembles
J-F Pabion Logique mathématique chez Hermann
Demazure cours d'Algèbre
Modèles logique et systèmes d'I.A par Alain Dussauchoy chez Hermès
Elements d'I.A par Henri Farreny chez Hermès

ii) il ne faut pas confondre implication et déduction.
L'implication est un connecteur, comme un "point-virgule", assujeti
aux règles logiques par sa table de vérité.
La déduction se fait par "modus ponens", en supposant la prémisse vraie,
et en écrivant la conclusion.

Merci pour toutes ces suggestions intéressantes...

ii) je ne comprends pas la nuance... si je suppose la prémisse vraie, et que je conclus, j'écris bien une implication non? Je ne vois pas trop la différence.

par **Robic** » 26 Mar 2015, 22:21

ii) je ne comprends pas la nuance... si je suppose la prémisse vraie, et que je conclus, j'écris bien une implication non? Je ne vois pas trop la différence.

Je crois que l'implication est une sorte de relation, tandis que la déduction est un raisonnement.

La définition de a ==> b, c'est que c'est la négation de « a et non b », donc on a a ==> b dans trois cas : a et b, non a et b, non a et non b. Du coup, si a est faux, on a nécessairement a ==> b. Par exemple si x est un nombre réel, on peut dire que x²<0 implique pi est transcendant puisque x²<0 est faux. Mais je ne vois pas trop comment on pourrait déduire la transcendance de pi en partant de x²<0...

Comme cours, je trouve ça très bien : http://bkristof.free.fr/coursexercices/Cours%20-%20Rudiments%20de%20logique%20et%20vocabulaire%20ensembliste.pdf .

par **chombier** » 26 Mar 2015, 22:34

alexis6 a écrit:Merci pour cette réponse.

Je remarque que quand on démontre l'implication pour " tous les autres nombres ", on suppose juste la première proposition vraie, par exemple x>2, pour ensuite démontrer que si x>2 est vraie, x^2>4 est vrai. Et on a pas besoin de supposer les 3 autres cas.

Pour moi on ne démontre pas les autres cas pour deux raisons:
- si le faux implique du vrai, l'implication est vraie, et si le faux implique du faux, l'implication est vraie. Donc dans tous les cas, puisqu'une proposition ne peut être que vraie ou fausse, l'implication est vraie
- on n'a pas besoin de montrer que si la première proposition est vraie, la seconde est fausse est une implication fausse, puisqu'on a déjà montré que si la première était vraie la seconde était vraie était une implication vraie. En effet v --> f est la négation de v --> v ( ce qui est faux, c'est ce qui n'est pas vrai ).

Ainsi, il suffit juste de démontrer que si une première proposition est vraie, la seconde est également vraie.

Mais démontrer, c'est une suite d'arguments finalement. Je crois que l'on peut considérer l'implication comme une suite d'arguments.

Par exemple pour l'implication x>2 --> x^2>4
On peut décomposer en cette suite d'arguments:
x>2
1 - x>2 est vrai par hypothèse donc x est plus grand que tout nombre en dessous de 2 est vrai, en particulier x est plus grand que 0 est vrai.
2- x est plus grand que 0 est vrai, donc x est positif est vrai
3- dans une inégalité, on peut multiplier par un nombre positif sans changer le sens de l'inégalité
4- on peut prendre le nombre positif x
5- on obtient l'inégalité x*x>2x
6- x*x s'écrit x^2
7- on peut donc écrire x^2>2x
8- par hypothèse x>2 est vrai
9- 2 est un nombre positif est vrai, on peut donc multiplier par 2 cette inégalité
10 on obtient 2x>4 vrai
11 l'inégalité est transitive, donc si x^2>2x vrai et 2x>4 vrai alors x^2>4 vrai

Si j'avais écrit un de ces onze arguments faux, comme le faux peut impliquer du vrai ou du faux, le résultat final aurait pu être vrai ou faux. Dans le cas où j'ai démontré du vrai, je suis parti d'une proposition vraie, et j'en déduis une proposition vraie. Pourtant l'implication est-elle vraie? Non, puisque j'ai fait une erreur de raisonnement.

J'en déduis par conséquent que pour démontrer qu'une implication est vraie, il faut deux choses:
- que le vrai implique du vrai, que le vrai n'implique pas du faux.
- que tous les arguments que j'avance soient vrais

Oui, la table de vérité de l'implication "fonctionne bien" : pour montrer que P(x) implique Q(x) est vraie pour tout x, il suffit de montrer que, quel que soit x, si P(x) est vraie, alors Q(x) est vrai. Les autres cas ne sont pas intéressants.

Pour démontrer que si P(x) est vraie, alors Q(x) est vrai, il va falloir raisonner sur les objets (les "x") et les prédicats ("P(x)" et "Q(x)") qu'on manipule. On va le plus souvent, comme tu l'as fait, faire des déduction successives.

On pourra ensuite affirmer que, Quel que soit x, P(x) implique Q(x)

Les déductions sont des raisonnement logiques, qui permettent d'affirmer que l'implication est vraie.

par **alexis6** » 26 Mar 2015, 22:37

[quote="Robic"]Je crois que l'implication est une sorte de relation, tandis que la déduction est un raisonnement.

La définition de a ==> b, c'est que c'est la négation de « a et non b », donc on a a ==> b dans trois cas : a et b, non a et b, non a et non b. Du coup, si a est faux, on a nécessairement a ==> b. Par exemple si x est un nombre réel x, on peut dire que x²0 est vrai. 4 est un nombre pair est vrai.
Donc 2>0 implique 4 est un nombre pair.

Mais pourtant quand on parle d'implication, on parle en fait tout le temps de déduction. Il ne faurait donc pas parler d'implication mais de déduction... Les deux se confondent facilement, je trouve.

Ps: merci pour ce lien

par **chombier** » 26 Mar 2015, 22:40

Anecdote d'un prof de logique :

La phrase "si un solide n'est soumis à aucune force, alors son mouvement est rectiligne et uniforme" est logiquement vraie, puisque la prémisse est toujours fausse.

Un solide n'est en effet JAMAIS soumis à aucune force :zen:

par **alexis6** » 26 Mar 2015, 22:46

chombier a écrit:Les déductions sont des raisonnement logiques, qui permettent d'affirmer que l'implication est vraie.

D'accord, mais dans ce cas, j'imagine qu'une déduction peut également être vraie ou fausse. Ou je me trompe? Ca complexifie les choses.

par **chombier** » 26 Mar 2015, 22:47

alexis6 a écrit:D'accord, mais dans ce cas, j'imagine qu'une déduction peut également être vraie ou fausse. Ou je me trompe? Ca complexifie les choses.

Errare humanum est. C'est pour ça qu'il y a des comités de relecture dans toutes les revues scientifiques.

par **alexis6** » 26 Mar 2015, 22:55

chombier a écrit:Anecdote d'un prof de logique :

La phrase "si un solide n'est soumis à aucune force, alors son mouvement est rectiligne et uniforme" est logiquement vraie, puisque la prémisse est toujours fausse.

Un solide n'est en effet JAMAIS soumis à aucune force :zen:

Si j'ai bien compris,
La confusion vient du fait que l'on peut démontrer qu'une implication est vraie ou fausse de deux manières:
- en considérant les valeurs de vérités des deux variables. On peut conclure directement si la prémisse est fausse.
- en procédant par déductions vraies

Ce qu'on est plus porté à faire, ce qui semble le plus naturel, et le plus efficace, c'est de procéder par déduction vraies. Mais on est trop habitué à devoir faire des déductions entre deux propositions déjà considérées vraies.

L'autre point, c'est que quand on ne dit rien, on sous-entend le mot vrai. Ainsi quand on dit:
"si un solide n'est soumis à aucune force, alors son mouvement est rectiligne et uniforme"

on sous-entend:
"si un solide n'est soumis à aucune force est vrai, alors son mouvement est rectiligne et uniforme est vrai"

qui est une proposition fausse.

par **mathelot** » 26 Mar 2015, 23:28

une déduction n'a pas de valeur de vérité tandis qu'une implication , oui.

je te prend l'exemple de bases de données en intelligence artificielle,
par exemple, un moteur d'inférence qui aide au diagnostique médical.
Il y a la base des règles où l'on stocke les implications

si "un patient a de la température et le nez qui coule" alors "il est malade de la grippe"

et les bases des faits, où l'on stocke les propriétés vraies
"Bob a le nez qui coule", "Alice a de la fièvre"

le moteur d'inférence (programme intelligent)
va chercher l'implication dans la base des règles,
va chercher la prémisse dans la base des faits (Bob a le nez qui coule et de la température)
et vient écrire la conclusion du modus ponens (Bob souffre de la grippe)
dans la base des faits.

Les déductions n'ont pas de valeur de vérité, sauf erreur.
Quand l'enseignant barre à l'encre rouge une déduction,dans un raisonnement,
celle ci n'apparait plus, elle est "discarded"

par **mathelot** » 26 Mar 2015, 23:38

Les implications ont des valeurs de vérité

A ou B implique B et C

la valeur de vérité se calcule en remplaçant les propositions A,B,C par des 0 (faux) ou des uns (vrai)
et en calculant.
je pense qu'une implicaation est valide si c'est une tautologie dans le système d'axiomes
retenus.

(A implique B) implique (non B implique non A)
est une tautologie (toujours vraie), si le principe du tiers exclu,
qui permet de la démontrer,fait partie de la liste des axiomes retenus.

par **chombier** » 27 Mar 2015, 07:33

mathelot a écrit:Les implications ont des valeurs de vérité
A ou B implique B et C

Post trop tardif ?

Ce serait plutôt :

(A et B) implique A

et

(A et B) implique B

Il y a en effet tout une théorie là dessus (l'algèbre de Boole)

Mon opérateur préferé c'est XOR (le sherif de l'espace, aussi appelé "ou exclusif") car il permet à lui seul d'exprimer tous les autre :zen:

par **Robic** » 27 Mar 2015, 11:30

Pour moi, la différence entre l'implication et la déduction est une différence de nature.

Une implication est une relation logique. Une déduction n'est pas une relation logique, c'est un raisonnement, donc un ensemble de plein de choses qui s'enchaînent (dont des relations logiques comme l'implication).

C'est comme la différence entre une addition et un calcul. Une addition est un opérateur binaire. Un calcul n'est pas un opérateur binaire, c'est fait de plein de choses qui s'enchaînent (dont des opérateurs binaires comme l'addition).

Mais pourtant quand on parle d'implication, on parle en fait tout le temps de déduction. Il ne faurait donc pas parler d'implication mais de déduction... Les deux se confondent facilement, je trouve.

Un exemple concret : la définition de la limite d'une suite :

tend vers 0 signifie que pour tout

, il existe un N tel que

quelconque. Je vais démontrer que

convient (où E est la fonction partie entière). On a :

J'ai donc démontré qu'il existe N (c'est

) tel que l'implication

était vraie. J'en déduis que la suite tend vers zéro.

On voit bien les deux rôles différents de l'implication et de la déduction, non ?

par **mathelot** » 27 Mar 2015, 11:53

je reprends l'exemple du moteur d'inférence , programme d'intelligence artificielle,
qui aide au diagnostique médical.

Dans la base des faits, nous avons
"Bob a le nez qui coule", "Bob a de la température"
les affirmations ont des valeurs de vérité, elles sont toutes vraies.

dans la base des règles, il y a stockée
si "le patient a le nez qui coule et de la température", alors "le patient est grippé"

Le moteur d'inférence lit la règle dans la base des règles, lit la prémisse de cette
règle dans la base des faits et ajoute à cette base des faits la conclusion "Bob est grippé".
(On note que la prémisse a été instanciée par Bob--->patient)
Ce sont les prédicats , les assemblages dans la base des règles
qui ont des valeurs de vérité

(True)
j'ai eu la confirmation, la déduction n'a pas de valeur de vérité, ce n'est pas une
formule.
Ce qui est assez curieux, c'est qu'il y a pourtant une formule(formule=identité remarquable=tautologie)
qui est

(2)

(2) semble se comporter comme une identité remarquable.

par **mathelot** » 27 Mar 2015, 12:00

alexis6 a écrit:Si j'ai bien compris,
La confusion vient du fait que l'on peut démontrer qu'une implication est vraie ou fausse de deux manières:
- en considérant les valeurs de vérités des deux variables. On peut conclure directement si la prémisse est fausse.
- en procédant par déductions

Ces deux aspects interviennent parfois en même temps dans le type
de démo suivant qu'on a tous rencontré.

discussion des cas
cas 1
il n'y a rien à démontrer (sous entendu: on est trivialement dans

)
cas 2
blablabla...

par **chombier** » 27 Mar 2015, 14:40

mathelot a écrit:Ce qui est assez curieux, c'est qu'il y a pourtant une formule(formule=identité remarquable=tautologie)
qui est

Dans les faits, il y a deux choses différentes :
- La tautologie

(2) qui est une expression qui reste vraie quelles que soient les valeurs de A et B.

On est dans le domaine de l'algèbre de Boole

- la règle de déduction Modus Ponens qui dit que
si A et A=>B sont des tautologies, alors B est une tautologie.

Pour en revenir à la différence entre implication et déduction :

on peut en effet utiliser une implication pour faire une déduction (avec la règle du Modus Ponens) mais ce n'est qu'un outils parmi tant d'autres :
- le raisonnement par l'absurde,
- la preuve par récurrence,
- la preuve par disjonction des cas,
- la preuve par analyse synthèse,
- la preuve par contraposée,
- la preuve d'une équivalence par double implication
etc.

Chacun de ces type de déduction pouvant être prouvé par des règles de logique bien définies et en théorie reconnues comme valides par tous.

La seule qui soit parfois en ballotage est la preuve par l'absurde, puisqu'elle utilise le tiers exclus qui est refusé par certains logiciens (qui refusent le fait que "A ou non A" soit une tautologie).

Si on veut aller plus loin, on va se retrouver à parler d'axiomatique, et de preuve formelle.

On PEUT prouver par exemple, si une axiomatique de la logique du premier ordre est fournie, que si A et A=>B sont des tautologies, alors B en est une.

La déduction "de base" (Modus Ponens) s'apprend au collège, j'en fait tous les jours avec mes 5èmes :
"On sait que ABCD est un parallélogramme et que AB = 7 cm
Or si un quadrilatère est un parallélogramme alors ses côtés opposés ont la même longueur
Donc CD = AB = 7 cm"

Logique

Logique

Qui est en ligne