Exercices option informatique mp lycee cezanne Théorie ...

Théorie des langages : Exercices option informatique mp lycee cezanne

Télécharger PDF

Notions de logique en informatique

La logique est essentielle en mathématiques et joue un rôle fondamental en informatique. Elle permet de structurer les démonstrations et les raisonnements, notamment dans les domaines suivants :

Invariants de boucle
Preuves de terminaison et de correction de programmes
Modélisation de structures de données

1.1 Introduction aux formules propositionnelles

Les formules propositionnelles, ou expressions logiques, sont des phrases construites à partir d'un vocabulaire et d'une grammaire précise. Elles forment un langage où les mots sont des propositions et l'alphabet un ensemble de symboles.

1.1.1 Retour sur le cours de mathématiques

En mathématiques, certaines propositions exprimées en langage naturel peuvent être formalisées. Par exemple, les trois phrases suivantes :

Si le train arrive en retard et s’il n’y a pas de taxis à la gare, je serai en retard à mon rendez-vous.
Le train arrive en retard.
Je ne suis pas en retard.

peuvent être traduites en formules propositionnelles avec les variables suivantes :

p : Le train arrive en retard.
q : Il y a des taxis à la gare.
r : Je suis en retard à mon rendez-vous.

La première phrase devient alors : ((p ∧ ¬q) ⇒ ¬r). En combinant avec les deux autres propositions, on obtient :

((p ∧ ¬q) ⇒ ¬r) ∧ p ∧ ¬r.

La logique permet de déduire que q est vrai, ce qui se note : ((p ∧ ¬q) ⇒ ¬r) ∧ p ∧ ¬r |= q.

1.1.2 Point de vue formel

Les formules propositionnelles reposent sur un vocabulaire et une grammaire définis. Le vocabulaire inclut :

Deux symboles : ⊥ (faux) et ⊤ (vrai).
Un ensemble dénombrable P de variables propositionnelles, souvent notées par des lettres minuscules.
Trois connecteurs logiques binaires : ∧ (et), ∨ (ou), ⇒ (implique).
Un connecteur logique unaire : ¬ (non).
Les parenthèses ( ), utilisées pour lever les ambiguïtés.

La grammaire des expressions logiques est définie récursivement comme suit :

Toute variable propositionnelle p ∈ P ainsi que les symboles ∧ et ∨ sont des expressions.
Si φ ∈ E, alors ¬φ ∈ E et (φ) ∈ E.
Si φ₁, φ₂ ∈ E, alors φ₁ ∧ φ₂, φ₁ ∨ φ₂ et φ₁ ⇒ φ₂ sont des expressions.

Par exemple, l'expression (a ∨ b) ⇒ (¬c ∨ (a ∧ ⊤)) est bien formée.

1.1.3 Sémantique

La sémantique permet d'attribuer une valeur de vérité (vrai ou faux) à une expression logique en fonction d'une fonction d'interprétation ρ.

Une fonction d'interprétation associe à chaque variable propositionnelle p ∈ P une valeur parmi {Vrai, Faux}. On note [[φ]]ρ la valeur de vérité de φ sous ρ.

Les règles de calcul récursif de [[φ]]ρ sont :

[[⊤]]ρ = Vrai, [[⊥]]ρ = Faux.
Si φ ∈ P, alors [[φ]]ρ = ρ(φ).
Si φ = ¬ψ, alors [[φ]]ρ = Vrai si [[ψ]]ρ = Faux, et [[φ]]ρ = Faux si [[ψ]]ρ = Vrai.
Si φ = (ψ), alors [[φ]]ρ = [[ψ]]ρ.
Si φ = ψ₁ ∨ ψ₂, alors [[φ]]ρ = Vrai si au moins une des valeurs [[ψ₁]]ρ ou [[ψ₂]]ρ est vraie.
Si φ = ψ₁ ∧ ψ₂, alors [[φ]]ρ = Vrai uniquement si [[ψ₁]]ρ et [[ψ₂]]ρ sont toutes deux vraies.
Si φ = ψ₁ ⇒ ψ₂, alors [[φ]]ρ = Faux uniquement si [[ψ₁]]ρ = Vrai et [[ψ₂]]ρ = Faux.

1.1.4 Algèbre de Boole

L'algèbre de Boole permet de représenter les valeurs de vérité et les connecteurs logiques à l'aide des ensembles {0, 1} et des opérations + (ou) et · (et).

Les tables de vérité pour + et · sont :

+ : 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 1.
· : 0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1.

Les lois de De Morgan sont vérifiées : a + b = (a · b) + (a · b) et a · b = (a + b) · (a + b).

1.1.5 Calcul de [[φ]]ρ

Le calcul de [[φ]]ρ se fait à partir de l'arbre syntaxique de φ. Chaque feuille est remplacée par sa valeur de vérité donnée par ρ, puis on calcule récursivement la sémantique des nœuds parents.

1.1.6 Tables de vérité

Les tables de vérité permettent de calculer la valeur de vérité d'une expression logique en fonction de toutes les combinaisons possibles des valeurs de ses variables.

Par exemple, pour l'expression (a ∨ b) ⇒ (¬c ∨ (a ∧ ⊤)), on établit une table avec 8 combinaisons possibles pour les variables a, b et c.

1.1.7 Vocabulaire de la sémantique

Une expression logique φ est dite satisfiable si une fonction d'interprétation ρ existe telle que [[φ]]ρ = Vrai.

Elle est une tautologie si toutes les fonctions d'interprétation ρ satisfont φ (c'est-à-dire [[φ]]ρ = Vrai pour toute ρ).

Elle est insatisfiable si aucune fonction d'interprétation ne satisfait φ.

1.1.8 Formes normales conjonctives/disjonctives

Les formes normales conjonctives (FNC) et disjonctives (FND) sont des représentations standardisées des expressions logiques, facilitant leur analyse.

1.1.9 Satisfiable ? Tautologie ?

Pour déterminer si une expression logique est satisfiable ou une tautologie, on examine sa table de vérité.

Si au moins une ligne contient Vrai, l'expression est satisfiable.
Si toutes les lignes contiennent Vrai, l'expression est une tautologie.

1.2 Cas des expressions arithmétiques

Les expressions arithmétiques peuvent aussi être analysées sous l'angle de la logique propositionnelle.

1.2.1 Grammaire et environnement

Les expressions arithmétiques sont construites à partir d'une grammaire et d'un ensemble de valeurs numériques.

1.2.2 Syntaxe abstraite

La syntaxe abstraite d'une expression arithmétique se représente par un arbre syntaxique similaire à celui des formules propositionnelles.

1.2.3 Implémentation

L'implémentation des expressions arithmétiques suit les mêmes principes que celles des formules propositionnelles.

1.3 La logique aux concours

Les questions de logique aux concours (comme ceux de la CCP) testent la capacité à formaliser des énoncés et à effectuer des calculs sur les expressions logiques.

FAQ

Qu'est-ce qu'une tautologie en logique ?

Une tautologie est une expression logique qui est toujours vraie, quelle que soit la fonction d'interprétation choisie.

Comment déterminer si une expression logique est satisfiable ?

On construit la table de vérité de l'expression et on vérifie si au moins une combinaison des valeurs des variables donne Vrai.

Quelle est la différence entre les connecteurs logiques ⇒ et ⇔ ?

⇒ signifie "implique" (si p est vrai, alors q est vrai), tandis que ⇔ signifie "équivalent" (si p est vrai, alors q est vrai et réciproquement).