Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ENSI Logique formelle 1 Logique formelle: Plan Partie I - Le calcul des prédica

ENSI Logique formelle 1 Logique formelle: Plan Partie I - Le calcul des prédicats Formalisation Chp.1- Le calcul des propositions (CP0) Chp.2- Le calcul des prédicats (CP1) Partie II - Les méthodes de calcul Déduction Chp.3- Notions fondamentales Chp.4- La méthode de résolution de Robinson ENSI Logique formelle 2 Partie I - Le calcul des prédicats Modélisation CP0. Le calcul des Prédicats d’ordre 0 (Propositions) CP1. Le calcul des Prédicats d’ordre 1 (Prédicats) Partie II - Les méthodes de calcul Déduction Logique formelle ENSI Logique formelle 3 Logique formelle Chapitre 1 Le calcul des Propositions Calcul propositionnel Logique d’ordre 0 CP0 ENSI Logique formelle 4 Calcul des propositions I – Syntaxe 1. Définition du langage 2. Arbre de décomposition d’une formule 3. Substitution dans une formule II – Sémantique ENSI Logique formelle 5 1- Définition du langage Calcul des propositions Syntaxe Un langage logique est défini par une syntaxe, qui est définie par un ensemble de symboles (alphabet) et un ensemble de règles permettant de combiner ces symboles sous forme de mots (séquence de symboles) appelées formules (bien formées). C’est l’aspect structurel et grammatical du langage. On associe au langage une sémantique qui permet de lui donner un sens (l’interpréter). C'est-à-dire attacher aux formules ainsi qu'aux symboles une signification (paragraphe II). Pour définir un langage, on doit commencer par définir son alphabet. ENSI Logique formelle 6 Des variables propositionnelles (atomes) R 0 = { p, q, … } évent. indicées { p1, q1, p2, q2, … } Des symboles logiques (connecteurs)  négation (« non ») unaire ∨ disjonction (« ou ») binaire ∧ conjonction (« et ») « ⇒ implication (« implique » ) « ⇔ équivalence (« si et seulement si » ) « Des constantes V (vrai) F (faux) Des symboles auxiliaires ’(’ ’)’ Calcul des propositions Syntaxe ENSI Logique formelle 7 Calcul des propositions Syntaxe Une formule propositionnelle est un mot construit sur l’alphabet A0 = R 0 U {∨, ∧, , ⇒, ⇔} U { F,V } U Comment ? Selon quelles règles ? ENSI Logique formelle 8 Définition Formules propositionnelles L’ensemble des formules propositionnelles (noté L0 ) est le plus petit ensemble de mots construits sur l’alphabet A0 et qui vérifie les propriétés suivantes : il contient R 0 U { V, F } à chaque fois qu’il contient le mot A, il contient le mot (A ) à chaque fois qu’il contient les mots A et B, il contient les mots : ( A ∨B ) , ( A ∧B ) , ( A ⇒B ) , ( A ⇔B ) Calcul des propositions Syntaxe ENSI Logique formelle 9 Autrement dit L’ensemble L0 des propositions bâtis sur l’alphabet A0 est le plus petit ensemble qui contient R 0 U { V, F } et qui vérifie les propriétés suivantes : A ∈L0  ( A ) ∈L0 A , B ∈L0  ( A ∨B ) ∈L0 ( A ∧B ) ∈L0 ( A ⇒B ) ∈L0 ( A ⇔B ) ∈L0 Calcul des propositions Syntaxe ENSI Logique formelle 10 Autrement dit Soit L0 l’ensemble des formules propositionnelles, alors : 1. un atome est une formule (R 0 ⊂L0 ) 2. V et F sont des formules ( { V,F } ⊂L0 ) 3. si A et B sont des formules alors ( A ∨B ) , ( A ∧B ) , ( A ⇒B ) , ( A ⇔B ) sont des formules 4. si A est une formule alors (A ) est une formule 5. rien d’autre n’est une formule (toutes les formules propositionnelles sont générées par application des quatre règles précédentes uniquement) Calcul des propositions Syntaxe ENSI Logique formelle 11 Exemples Les mots suivants sont des formules (p ⇒((( q ∧r )) ∨p )) ( p ⇔q ) (F ⇔V) ( ( p ∨q ) ∨q ) (p ) ((p ) ∨(q )) F q Les mots suivants ne sont pas des formules ( p q ∨) ((p ) ⇒⇔(q )) Calcul des propositions Syntaxe Remarque L’ensemble L0 des formules propositionnelles est appelé le langage d’ordre 0 ou le langage du (calcul) des propositions (ou des prédicats d’ordre 0) ou propositionnel ENSI Logique formelle 12 Remarque On peut enlever le parenthésage en l’absence de toute ambiguïté Il faut fixer une priorité (poids) pour les opérateurs Ordre de priorité :  ∧ ∨ ⇒ ⇔ + priorité la plus faible (par convention) - Calcul des propositions Syntaxe + - (par coutume) ENSI Logique formelle 13 La formule p ∧q ⇒r ∧s ⇒p ⇔u ∨v sera parenthésée : ( ( ( ( p ∧q ) ⇒( r ∧s ) ) ⇒(p ) ) ⇔( u ∨v ) ) 2 5 3 6 1 7 4 Calcul des propositions Syntaxe ( ( ( p ⇒( ( (q ⇔r ) ∨s ) ∨( t ∧p ) ) ) ⇒((p ∨r )) ) ⇔t ) La formule p ⇒(q ⇔r) ∨s ∨t ∧p ⇒(p ∨r) ⇔t sera parenthésée : ENSI Logique formelle 14 A : ( ( p ∧(q ⇒p ) ) ∧ (q ∨r) ) ⇒ ( q ⇒p ) A11 A12 A1 A2 Calcul des propositions Syntaxe 2- Arbre de décomposition d’une formule On peut représenter cette décomposition sous forme d’un arbre A11: p ∧( q ⇒ p ) A12 : ( q ∨ r ) A111 A1121 A1122 A121 A122 A112 A2 : ( q ⇒ p ) A21 A22 ENSI Logique formelle 15 Calcul des propositions Syntaxe A221 p A ∧ ∨ ⇒ ∧ A21 q A22:  A122: r A121: q ⇒ A1122  A11221 p A1121  A111 p ⇒ A1 A2 A11 A12 A112 A11211 q ENSI Logique formelle 16 Calcul des propositions Syntaxe ⇒ ∧ ∨ ⇒ ∧ q  p  r  q ⇒  p  q p Les opérateurs à traiter en premier se trouvent au bas de l’arbre ENSI Logique formelle 17 Théorème de lecture unique Pour toute formule A ∈L0 , un et un seul des 3 cas suivants se présente : 1. A ∈R 0 U { V, F } 2. il existe une unique formule B ∈L0 telle que A = (B) 3. il existe un unique symbole de connecteur binaire # ∈{ ∨, ∧, ⇒, ⇔} et un unique couple de formules ( B, C ) ∈L0 2 tels que A = (B # C) " = " égalité syntaxique Calcul des propositions Syntaxe ENSI Logique formelle 18 Corollaire L’arbre de décomposition d’une formule est unique Calcul des propositions Syntaxe Remarque On dit que le langage des propositions est non ambigu ENSI Logique formelle 19 3- Substitution dans une formule Calcul des propositions Syntaxe Définition Soient • A et B deux formules propositionnelles • p une variable propositionnelle de A A [ p ←B ] est le mot obtenu en substituant la formule B à la variable p La substitution s’applique à toutes les occurrences de la variable p Autre notation : A (B / p) ENSI Logique formelle 20 Exemple A : p ⇒(q ∨p) B : q ⇒r • La variable p a 2 occurrences dans A • La variable q a une seule occurrence dans A A [ p ←B ] = B ⇒(q ∨B) = (q ⇒r) ⇒( q ∨(q ⇒r)) Calcul des propositions Syntaxe ENSI Logique formelle 21 On peut étendre la substitution à un ensemble de formules A [ p1 ←B1 , p2 ←B2 , … , pn ←Bn ] est le mot obtenu en substituant respectivement les formules B1, B2 , …, Bn à toutes les occurrences des variables p1, p2, …, pn Calcul des propositions Syntaxe ENSI Logique formelle 22 Théorème Soient • A , B1 , B2,…, Bn des formules propositionnelles • p1, p2, …, pn des variables propositionnelles alors le mot A [ p1 ←B1, p2 ←B2, … , pn ←Bn ] est une formule propositionnelle Calcul des propositions Syntaxe ENSI Logique formelle 23 Exemples A : p ∧q B : q ∨r C : p ∧r • A [ p ←B, q ←C] = B ∧C = (q ∨r ) ∧(p ∧r ) • A [r ←C] = A Calcul des propositions Syntaxe ENSI Logique formelle 24 Remarque La substitution simultanée (remplacement en parallèle) est différente de la substitution séquentielle (remplacement en série) A [ p1 ←B1, p2 ←B2] ≠ (A [ p1 ←B1] ) [ p2 ←B2 ] substitution simultanée substitution séquentielle Calcul des propositions Syntaxe ENSI Logique formelle 25 Exemples A : p ∧q B : p ∨q C : p ⇒q • A [ p ←B, q ←C] =( p ∨q ) ∧( p ⇒q ) (A [ p ←B ] ) [ q ←C] = ( ( p ∨q ) ∧q ) [ q ←C] = ( p ∨( p ⇒q ) ) ∧( p ⇒q ) • A [ q ←C, p ←B] = ( p ∨q ) ∧( p ⇒q ) • (A [ q ←C] ) [ p ←B ] = ( p ∨q ) ∧( p ⇒q ) = uploads/s3/ cp0-pdf.pdf