Correction d'un exercice

Bonjour à tous,

Je souhaite prendre de l'avance en maths et je viens donc de commencer mon premier TD de logique. J'ai fait le premier exo, et j'aimerais m'assurer que mes réponses sont correctes !

Voici l'énoncé

Parmi les suites de symboles¹ suivantes, lesquelles sont des formules² ?

Explications

J'ai pris soin d'ajouter des explications pour être sûr qu'on utilise bien les mêmes mots et ainsi pour ne pas vous perdre

¹ : en logique des propositions, un "symbole" est un élément du vocabulaire du système qui est, entre autres, une phrase élémentaire (c'est-à-dire une proposition³), généralement représentée par une variable propositionnelle. Dans le cadre de l'exo, il n'y a pas de variable mais bien les propositions (les phrases) en brut. Un symbole peut donc être une proposition, mais aussi un connecteur logique (XOR, implication, AND…), les parenthèses, etc. mais dans le cadre de cet exercice, cette info n'a pas d'importance.

² : une formule est une suite finie de symboles du vocabulaire.

³ : une proposition est un énoncé qui vaut soit vrai, soit faux.

Mes réponses

Selon moi, l'une de ces suites n'est pas une formule si elle contient au moins un symbole (une proposition) ne faisant pas partie du vocabulaire.

Note à votre intention : la plupart des suites ci-dessous ne contiennent qu'une seule proposition je crois bien.

a) L'univers est fini.

Oui, c'est une proposition donc c'est un symbole donc c'est bien une suite finie de symboles donc c'est une formule.

b) Il ne gèle pas.

Idem

c) L'or est une plante.

Idem

d) Les sanglots longs des violons de l'automne.

Ce n'est pas une proposition, donc ce n'est pas un symbole, donc ce n'est pas une formule.

e) S'il neige, alors il ne neige pas.

On a deux propositions, donc deux symboles donc c'est bien une suite de symboles et donc c'est bien une formule.

f) Je suis venu, j'ai vu, j'ai vaincu.

Nope, pas de proposition, pas de symbole, pas de suite de symboles, donc non ce n'est pas une formule.

g) Il fait beau donc nous irons à la campagne.

Yep, deux propositions donc formule.

h) Viens ici !

Nan pas formule

i) Quelle heure est-il ?

Idem

j) Pierre et Paul sont venus.

Formule.

k) Les citoyens français peuvent se rendre en Italie ou en Allemagne sans passeport.

Formule (deux propositions).

l) Tous les hommes sont menteurs

Alors là j'ai hésité, connaissant le Paradoxe du menteur. Mais bon je ne me suis pas pris la tête, a priori oui, c'est bien une proposition donc une formule.

Deuxième question : Parmi ces formules, lesquelles sont simples (atomiques), et lesquelles sont composées (moléculaires) ?

Dans le cas des formules composées, définissez les atomes dont elles sont composées.

Mes réponses :

Formules simples : a ; b ; c ; j ; k ; l.

Formules composées : e (atomes : "S'il neige" et "il ne neige pas") ; g (atomes : "Il fait beau" et "nous irons à la campagne").

Pour identifier les atomes bein je me pose la question : peut-il valoir vrai ou faux ? (un atome étant une proposition, je pense que c'est la bonne méthode).

Exemples : "Il fait beau" peut très bien être vrai ou faux donc c'est une proposition donc c'est un atome. Idem pour "S'il neige", ou pour "nous irons à la campagne", etc.

C'est un peu long de te faire une correction … Surtout que cette notion de langage me semble pas si courante. Est-ce que y a des points litigieux où tu as besoin de notre avis en priorité ?

Ah non pas du tout

Je voulais juste savoir si mes réponses sont correctes ou pas en fait. Ça a l'air long à corriger c'est sûr, mais en fait pas tant que ça je pense :-/

Tu saurais comment traduire les éléments que tu as qualifié de formule en "formule mathématiques" ? Comment tu l'exprimerais avec les symboles du dessus ?

Ca m'a l'air correct en regardant rapidement, mais le second exercice est ambigüe à cause de la langue pour le j) par exemple : peux-tu aussi dire que P1: Pierre est venu, P2: Paul est venu et que l'énoncé est simplement P1 ET P2, parce que la langue ferait difficilement la répétition "Pierre est venu et Paul est venu" ?

De même, pour la k) : tu peux avoir P1: se rendre en Italie, P2: se rendre en allemagne, et P3: ne pas avoir de passeport, l'énoncé peut alors s'écrire (P1 ou P2) et P3.

Pour savoir si tes phrases sont biens des formules, il faut savoir quels sont les symboles autorisés non ? A priori si ton vocabulaire est l'alphabet toutes les phrases sont bien composées de symboles donc des formules non ? Tu n'as pas plus d'info dans l’énoncé ?

Pour la question deux que veux dire "atomique" et "moléculaire" ? Pour moi ce genre de distinction n'a aucune sens dans un systéme logique…

Je dois d'avouer que cette façon d'aborder la logique formelle me laisse très perplexe… J'ai du mal à comprendre le but de cet exercice.

Salut unidan,

Bein en logique propositionnelle, une formule c'est juste une suite de symboles. Et un symbole ça peut être, entre autres, une proposition. Et une proposition c'est juste un énoncé qui est soit vrai soit faux.

Du coup je dirais :

<formule> ::= <symbole> | <formule>

<symbole> ::= P0 | P1 | etc. avec PX une proposition (donc un énoncé, une phrase)

J'ai bien répondu à ta question ?

Sinon effectivement, je me suis posé la question pour la j) et la k)… :-/

Du coup je ne sais pas trop si ce que j'ai écrit est correct, j'imagine pourtant qu'il n'y a qu'une et une seule solution.

===============================

Demandred,

Pour savoir si tes phrases sont biens des formules, il faut savoir quels sont les symboles autorisés non ? A priori si ton vocabulaire est l'alphabet toutes les phrases sont bien composées de symboles donc des formules non ? Tu n'as pas plus d'info dans l’énoncé ?

Pour la question deux que veux dire "atomique" et "moléculaire" ? Pour moi ce genre de distinction n'a aucune sens dans un systéme logique…

Je dois d'avouer que cette façon d'aborder la logique formelle me laisse très perplexe… J'ai du mal à comprendre le but de cet exercice.

Non attention, ici le vocabulaire n'a rien à voir avec l'alphabet, on est dans la logique propositionnelle et non dans la théorie des langages

Le vocabulaire, en logique propositionnelle, est constitué par :

1. Un ensemble infini dénombrable de phrases élémentaires (les propositions), généralement représentées par des variables propositionnelles (genre P0 = "les chats sont gris", P0 est la variable propositionnelle et "les chats sont gris" est la proposition). Dans cet exo, y a pas de variables propositionnelles mais directement des propositions. Synonyme de ces propositions : "atomes".

2. Les deux constantes T et "T-à-l'envers".

3. Un ensemble de connecteurs logiques (XOR, AND, implique…)

4. Les parenthèses ( et ).

Et une formule est une suite finie de symboles du vocabulaires (un symbole est un élément du vocabulaire).

Dans l'exo, y a ni parenthèse, ni connecteur, ni constante : tous les symboles de l'exos sont donc, selon moi mais ça me paraît vraiment logique, les atomes (les propositions, donc les phrases qui valent soit vrai soit faux par définition).

Et chaque a) b) c), etc., est en réalité une suite de symboles. La plupart de ces suites n'ont qu'un symbole (qu'une seule proposition), mais certaines en ont deux. D'où le terme de "suite". Voilà voilà. Je ne pense pas me tromper sur ce point.

=====

Concernant les termes "atomique" et "moléculaire" : si une formule (donc une suite) ne contient qu'un seul symbole, je pense qu'elle est dite "atomique". Sinon, "moléculaire".

on est dans la logique propositionnelle et non dans la théorie des langages

Je n'ai jamais compris l’intérêt de la logique propositionnelle : on ne peut rien faire avec car on n'est incapable de savoir ce qui est vrai ou faux. Si je te dis "l'amour est bleu" comment attribuer une valeur de vérité à cette phrase ? Ou a un paradoxe comme celui du barbier ?

De plus si je ne dis pas de bêtise la logique propositionnelle est un langage formelle (on a bien des symboles, des axiomes et plus ou moins des règles de production d'expression), le seul soucis vient quand on essaye de remplacer les propositions P par des choses en français dont on est incapable d'attribuer une logique de vérité…

Personnellement je trouve que ça donne une fausse image de la logique formelle aux étudiants…

Wut ? "L'amour est bleu" ça veut déjà rien dire en français, c'est super bizarre comme exemple. Je sais pas si tu as déjà fait de la logique propositionnelle en cours (ça m'étonnerait franchement, sinon tu aurais vu pourquoi c'est utile). J'ai absolument rien compris à ton raisonnement.

La logique propositionnelle c'est très utile. Par exemple, il existe plein d'énigmes qui deviennent bien plus faciles à résoudre lorsqu'on sort la logique propositionnelle. Un autre: le sudoku. Un sudoku tu peux l'encoder sous forme de formule logique à satisfaire. Arriver à satisfaire cette formule logique c'est arriver à résoudre la grille. Tu peux jeter un oeil à ce papier. Après on peut utiliser des algorithmes (SAT-solver) pour trouver des valeurs satisfaisant la formule logique.

Simplifier les conditions logiques en programmation, simplifier des circuits logiques, tout ça se fait avec de la logique propositionnelle.

Mais du coup faudrait vraiment que tu m'expliques ce que tu as voulu dire, parce que la logique formelle c'est un outil mathématique, pas une formule magique permettant de dire si l'amour est bleu.

Et si tu te renseignes sur le paradoxe du barbier, il a une formulation en logique du premier ordre. Et justement cela prouve que l'existence d'un tel barbier est impossible.

Wut ? "L'amour est bleu" ça veut déjà rien dire en français, c'est super bizarre comme exemple.

C'est bien le problème, on ne peut pas attribuer une valeur de vérité à cette proposition… Je prends un exemple volontairement absurde mais il y a plein de cas où on ne peut pas vraiment dire si une proposition est vrai ou fausse.

Je sais pas si tu as déjà fait de la logique propositionnelle en cours (ça m'étonnerait franchement, sinon tu aurais vu pourquoi c'est utile).

Si j'en ai fais en maths, même si en économie c'est clairement un truc inutile xD. Mais c'est un sujet que je connais pas trop mal de par ma culture personnelle (en particulier la logique formelle et l'histoire de axiomatisation des mathématiques jusqu'aux travaux et démonstrations de Gödel sur le sujet).

La logique propositionnelle c'est très utile. Par exemple, il existe plein d'énigmes qui deviennent bien plus faciles à résoudre lorsqu'on sort la logique propositionnelle. Un autre: le sudoku. Un sudoku tu peux l'encoder sous forme de formule logique à satisfaire. Arriver à satisfaire cette formule logique c'est arriver à résoudre la grille.

Oui là je suis d'accord et je comprends ! Mais pas avec des phrases en français ! On ne peut rien faire avec ça… C'est ça que je reproche surtout.

Mais du coup faudrait vraiment que tu m'expliques ce que tu as voulu dire, parce que la logique formelle c'est un outil mathématique, pas une formule magique permettant de dire si l'amour est bleu.

Pour moi le but de la logique formelle c'est de décrire quelque chose en évitant les paradoxes et les erreurs de raisonnement. Typiquement décrire les maths en évitant les paradoxes. Un systéme formel demande un alphabet (une liste fini de symboles utilisables) et des règles de production/dérivations qui décrivent comment combiner ces symboles entre eux pour former des propositions. Toute proposition dérivée de ces règles est considérée comme valide par le systéme.

Un exemple simple de systéme logique : un alphabet qui est {"le chat", "le chien", "mange", "aime", "les croquettes", "la viande" } et des règles de productions qui disent : "les deux premiers éléments de l'alphabet sont des sujets, les deux seconds des verbes, les deux suivants des compléments". "Une phrase valide est de la forme : sujet - verbe - complément".

Ainsi avec un tel systéme tu peux écrire une phrase comme "le chat mange les croquettes" ou encore "le chien aime la viande". Mais une phrase comme "le chien mange le chat" ne respect pas les règles et ne peux pas être produite par le systéme.

Avec un systéme de ce genre on peut représenter les mathématiques (plus ou moins^{^) et s'assurer qu'on ne produira pas de contradiction ni de paradoxe ! Ainsi on évite le paradoxe du Russel en maths que pose la théorie des ensembles et on peut axiomatiser les maths sans avoir d'erreur (mais au prix d'une incomplétude, ce qui est un autre problème}^).

La logique propositionnelle peut s'écrire de cette façon (exemple ici ), c'est en ce sens que je dis que la logique propositionnelle est un langage formelle. On retrouve bien un alphabet et des règles d'utilisation (ici pas d'axiomes on remarquera).

Le problème arrive quand on remplace le P par une phrase en français et qu'on fait des trucs du genre "il pleut donc le sol est mouillé" ou qu'on attribu des notions de "vrai" ou "faux" à ces phrases… Ceci ne sert strictement à rien en français… J'ai déja eu un prof (quelqu'un d'assez connu en plus :() qui m'a expliquer qu'ainsi on pouvait débusquer la vérité du discours des politiciens…

Et si tu te renseignes sur le paradoxe du barbier, il a une formulation en logique du premier ordre. Et justement cela prouve que l'existence d'un tel barbier est impossible.

Je ne connais pas trop ce qu'est la logique du premier ordre, mais je sais en tt cas que c'est typiquement pour éviter ça qu'on a inventer les systèmes logiques. Dans un systéme logique, impossible d'écrire un paradoxe (sauf si le systéme est mal fait xD).

Wut ? "L'amour est bleu" ça veut déjà rien dire en français, c'est super bizarre comme exemple.

C'est bien le problème, on ne peut pas attribuer une valeur de vérité à cette proposition… Je prends un exemple volontairement absurde mais il y a plein de cas où on ne peut pas vraiment dire si une proposition est vrai ou fausse.

A priori, si tu te mets en logique propositionnelle, tu peux autant évaluer la proposition comme fausse que vraie, c'est seulement l'interprétation/le sens qui n'existera pas. Le calcul propositionnel n'a absolument rien à voir avec le contenu de l'énoncé.

La logique propositionnelle c'est très utile. Par exemple, il existe plein d'énigmes qui deviennent bien plus faciles à résoudre lorsqu'on sort la logique propositionnelle. Un autre: le sudoku. Un sudoku tu peux l'encoder sous forme de formule logique à satisfaire. Arriver à satisfaire cette formule logique c'est arriver à résoudre la grille.

Oui là je suis d'accord et je comprends ! Mais pas avec des phrases en français ! On ne peut rien faire avec ça… C'est ça que je reproche surtout.

L'objectif dans ce genre d'exercice, c'est de résoudre une énigme modulo certaines hypothèses (qui changent selon les questions). Et l'exercice est posé textuellement, la première question étant souvent de mathématiser le problème. On fait beaucoup ça en option info en spé.

Pour moi le but de la logique formelle c'est de décrire quelque chose en évitant les paradoxes et les erreurs de raisonnement. Typiquement décrire les maths en évitant les paradoxes. Un systéme formel demande un alphabet (une liste fini de symboles utilisables) et des règles de production/dérivations qui décrivent comment combiner ces symboles entre eux pour former des propositions. Toute proposition dérivée de ces règles est considérée comme valide par le systéme.

Un exemple simple de systéme logique : un alphabet qui est {"le chat", "le chien", "mange", "aime", "les croquettes", "la viande" } et des règles de productions qui disent : "les deux premiers éléments de l'alphabet sont des sujets, les deux seconds des verbes, les deux suivants des compléments". "Une phrase valide est de la forme : sujet - verbe - complément".

Ainsi avec un tel systéme tu peux écrire une phrase comme "le chat mange les croquettes" ou encore "le chien aime la viande". Mais une phrase comme "le chien mange le chat" ne respect pas les règles et ne peux pas être produite par le systéme.

Avec un systéme de ce genre on peut représenter les mathématiques (plus ou moins) et s'assurer qu'on ne produira pas de contradiction ni de paradoxe ! Ainsi on évite le paradoxe du Russel en maths que pose la théorie des ensembles et on peut axiomatiser les maths sans avoir d'erreur (mais au prix d'une incomplétude, ce qui est un autre problème^^).

Le paradoxe de Russel, il nait de la non restriction du principe de compréhension, qui permet de dire (avec les mains) qu'à une certaine proposition dépendant de certaines variables correspond un ensemble d'élements qui vérifient la proposition. Grammaire ou pas, ça n'y changera rien. Par contre, il faut distinguer logique formelle (qui désigne plutôt un champ d'étude assez vaste en logique) et logique propositionnelle qui est un outil de calcul. En particulier, il n'y a pas de quantificateur en logique propositionnelle.

Le problème arrive quand on remplace le P par une phrase en français et qu'on fait des trucs du genre "il pleut donc le sol est mouillé" ou qu'on attribu des notions de "vrai" ou "faux" à ces phrases… Ceci ne sert strictement à rien en français… J'ai déja eu un prof (quelqu'un d'assez connu en plus :() qui m'a expliquer qu'ainsi on pouvait débusquer la vérité du discours des politiciens…

On est parfaitement d'accord sur la valeur des énoncés que cela produit, il n'empêche que ces énoncés disposent d'une négation, et c'est la seule chose dont on demande en logique propositionnelle pour calculer.

Mais pourquoi vous vous focalisez sur les valeurs de validité et de vérité de mes énoncés ? J'ai juste besoin de savoir si j'ai bien identifié les bonnes formules, et si j'ai également bien identifié les formules atomiques et moléculaires. Ca n'a pas grand-chose à voir avec la validité/vérité des énoncés.

Est-ce que vous pourriez donner votre avis pour d'abord répondre à mon topic, puis ensuite discuter de la validité et de la vérité des énoncés dans le cadre de la logique des propositions svp ?

Ok, bein merci à tous !