Maintenant équipées des principes de la théorie logique ainsi que de la notation de base, il est temps d’explorer le concept d’équivalence en logique. Plus précisément, qu’est-ce qui rend deux locaux composés égaux?

Deux locaux composés X &Y sont logiquement équivalents si, pour chaque affectation de valeurs de vérité aux locaux primitifs qui composent X &Y, les instructions X &Y ont des valeurs de vérité identiques.

C’est une définition difficile à avaler, mais c’est l’application de cette définition que nous nous soucions d’apprendre. Pour y parvenir, nous allons parcourir de multiples exemples de plus en plus compliqués. Tout d’abord, faisons un détour pour en apprendre un peu plus sur notre Excalibur pour ce voyage — l’un des outils les plus simples mais les plus puissants pour les logiciens pour prouver l’équivalence logique: les tables de vérité.

Une table de vérité est un outil visuel, sous la forme d’un diagramme avec des lignes & colonnes, qui montre la vérité ou la fausseté d’une prémisse composée. C’est un moyen d’organiser les informations pour répertorier tous les scénarios possibles à partir des locaux fournis. Commençons par l’exemple le plus simple, une table de vérité représentant une seule manipulation de prémisse : une négation (~) d’une prémisse primitive (P)

div>

Les tables de vérité sont toujours lues de gauche à droite, avec une prémisse primitive à la première colonne. Dans l’exemple ci-dessus, notre prémisse primitive (P) se trouve dans la première colonne; tandis que la prémisse résultante (~P), post-négation, constitue la deuxième colonne.

Il est facile de trop penser aux choses ici — n’oubliez pas qu’une prémisse est simplement une déclaration vraie ou fausse. Puisque cet exemple n’a qu’une seule prémisse, nous n’avons besoin que de suivre deux résultats; ce qui donne deux lignes pour quand P est vrai ou quand il est faux. La première ligne décrit, en lisant de gauche à droite, que si P est vrai, alors la négation de P est fausse; la deuxième ligne affiche que si P est déjà faux, alors la négation de P est vraie.

Passons à un exemple plus compliqué de tables de vérité dans la nature en insérant un connectif que nous avons vu précédemment: l’implication (->). Afin de rendre cela un peu plus digeste, assignons à nos déclarations P&Q un contexte avant de construire notre table de vérité:

P: Thanos s’est cassé les doigts

Q:50% de tous les êtres vivants ont disparu

Avant de regarder ci-dessous, réfléchissons à cette structure compte tenu des détails ci-dessus. Premièrement, puisque nous avons deux prémisses primitives (P, Q), nous savons que nous aurons besoin d’au moins deux colonnes; de plus, nous devons nous préparer à la prémisse résultante avec le connectif d’implication (P-> Q), qui nécessitera une autre colonne. Un total de trois colonnes.

Qu’en est-il des lignes ? Puisque nous avons deux prémisses qui peuvent chacune être vraies ou fausses, afin de tenir compte de tous les scénarios possibles, nous avons besoin d’un total de quatre lignes (PS — un corollaire soigné peut être dérivé de cette observation: une table de vérité qui tient compte de N prémisses nécessite N2 lignes). Dessinons maintenant cette table & assurez-vous qu’elle est compréhensible:

Passez en revue la table de vérité ci-dessus ligne par ligne. La première rangée confirme que les deux Thanos se sont claqués les doigts (P) & 50% de tous les êtres vivants ont disparu (Q). Puisque les deux prémisses sont vraies, alors la prémisse résultante (l’implication ou conditionnelle) est également vraie :

La deuxième ligne est également directe dans la compréhension. Cette fois, P est toujours vrai, mais Q est maintenant faux. L’interprétation ici est « Thanos s’est claqué les doigts, mais 50% de tous les êtres vivants n’ont pas disparu.” Puisque nous nous efforçons de prouver la validité de l’implication, il est logique que l’instruction précédente rende la prémisse globale sans équivoque fausse :

Les deux dernières lignes sont un peu plus contre-intuitives. Il y a un raccourci ici: il suffit de regarder la première colonne pour enregistrer que l’implication est vraie. Dans les deux lignes trois & quatre, la prémisse antécédente (P) est fausse — ce qui est tout ce que nous devons savoir, quelle que soit la valeur de la prémisse Q, afin de déterminer l’implication comme vraie.

Pourquoi un faux antécédent conduit-il toujours à une véritable implication? Parce que dans l’univers de notre déclaration logique, puisque l’antécédent ne s’est pas produit, il est impossible d’éliminer tous les scénarios possibles qui auraient pu causer Q. Par exemple, la ligne 3 dit que « Thanos n’a pas claqué des doigts mais 50% de tous les êtres vivants ont disparu” de toute façon. Eh bien, pour tout ce que nous savons, un météore, une catastrophe naturelle, une invasion extraterrestre ou une myriade d’autres activités pourraient avoir causé cette extinction — dans n’importe lequel de ces scénarios, quel que soit celui-ci, l’implication reste vraie parce que nous ne pouvons toujours pas prouver ce qui se passe quand il claque des doigts.

Sur la preuve de l’équivalence

Les tables de vérité sont des diagrammes de suivi logique simples et pratiques qui apparaissent non seulement en mathématiques, mais aussi en informatique, en génie électrique &philosophie. La notation peut varier en fonction de l’industrie dans laquelle vous êtes engagé, mais les concepts de base sont les mêmes. C’est un outil polyvalent et interdisciplinaire, mais nous n’avons fait qu’effleurer la surface de leur utilité.

Maintenant équipé de tables de vérité, il est temps de progresser vers la preuve de l’équivalence entre plusieurs locaux composés. Dans le prochain article de cette série, nous tirerons parti de nos connaissances sur la composition pour prouver que deux prémisses composées distinctes, telles que l’implication & contre-positive, sont égales.

initialement publié sur

https://www.setzeus.com/