[PDF] [PDF] Calcul propositionnel Calcul propositionnel La logique propositionnelle

View - Download [PDF] Calcul propositionnel

Previous PDF

Next PDF

Chapitre 3

Calcul propositionnel

Lalogique propositionnellepermet essentiellement de discuter des connecteurs grammaticaux comme la négation, la conjonction et la disjonction, en composant des propositions à partir de propositions données. Ces connecteurs sont parfois appelés aristotéliciens, car ils ont été mis en évidence par Aristote. Lecalcul propositionnelpermet essentiellement de parler defonctions booléennes, c"est-à-dire de fonctions def0;1gn! f0;1g. En effet, les variables, c"est-à-direles propositions, ne peuvent prendre que deux valeurs,vraioufaux. Le calcul propositionnel tient une grande place en informatique : ne serait-ce parce que nos ordinateurs actuels sont digitaux, et travaillent en binaire. Ce qui fait que nos processeurs sont essentiellement constitués de portes binaires du type de celles que l"on va étudier dans ce chapitre. D"un point de vue expressivité logique, le calcul propositionnel reste très limité : par exemple, on ne peut pas écrire en calcul propositionnel l"existence d"un objet ayant

une propriété donnée. Le calcul des prédicats, plus général, que nous étudierons dans

le chapitre 5Calcul des prédicatschapter.5, permet lui d"exprimer des propriétés d"ob- jets et des relations entre objets, et plus généralement de formaliser le raisonnement mathématique. Puisque le calcul propositionnel forme toutefois la base commune de nombreux systèmes logiques, et nous allons nous y attarder dans ce chapitre.

3.1 Syntaxe

Pour définir formellement et proprement ce langage, nous devons distinguer la syn- taxe de la sémantique : la syntaxe décrit comment on écrit les formules. La sémantique décrit leur sens. Fixons un ensemble fini ou dénombrableP=fp0;p1;gde symboles que l"on appellevariables propositionnelles. Définition 3.1 (Formules propositionnelles)L"ensembledesformulespropositionnelles FsurPest le langage sur l"alphabetP [ f:;^;_;);,;(;)gdéfini inductivement par les règles suivantes : 1

2CHAPITRE 3. CALCUL PROPOSITIONNEL

(B)il contientP: toute variable propositionnelle est une formule proposition- nelle; (I)siF2 Falors:F2 F; (I)siF;G2 Falors(F^G)2 F,(F_G)2 F,(F)G)2 F, et(F,G)2 F. précédent. Il s"agit d"une définition inductive non ambiguë : on peut reformuler ce fait par la proposition suivante, parfois appeléthéorème de lecture unique. Remarque 3.1La non-ambiguïté vient essentiellement des parenthèses explicites. On

utilise ici l"astuce utilisée dans le chapitre précédent qui considéraitArith0plutôt que

Arithpour permettre d"écrire des expressions sans aucune ambiguïté de lecture. Proposition 3.1 (Décomposition / Lecture unique)SoitFune formule proposition- nelle. AlorsFest d"une, et exactement d"une, des formes suivantes 1. une variable pr opositionnellep2 P;

2.:G, oùGest une formule propositionnelle;

3.(G^H)oùGetHsont des formules propositionnelles;

4.(G_H)oùGetHsont des formules propositionnelles;

5.(G)H)oùGetHsont des formules propositionnelles;

6.(G,H)oùGetHsont des formules propositionnelles.

De plus dans les cas 2., 3., 4., 5. et 6., il y a unicité de la formuleGet de la formuleH avec ces propriétés. Le fait qu"une formule se décompose toujours dans un des6cas plus hauts est facile

à établir inductivement. L"unicité de la décomposition découle de l"exercice suivant :

Exercice 3.1.Montrer que la définition inductive précédente est non-ambiguë, c"est- à-dire queGetHsont uniquement définis dans chacun des cas plus haut.

On pourra procéder de la façon suivante.

Montr erque dans toute formule Fle nombre de parenthèses ouvrantes est égal au nombre de parenthèses fermantes. Montr erque dans tout mot Mpréfixe deF, on ao(M)f(M), oùo(M)est le nombre de parenthèses ouvrantes, etf(M)le nombre de parenthèses fermantes. Montr erque pour toute formule Fdont le premier symbole est une parenthèse ouvrante, et pour tout motMpréfixe propre deF, on ao(M)> f(M). Montr erque tout mot Mpréfixe propre deFn"est pas une formule.

En déduir ele résultat.

On appellesous-formuledeFune formule qui apparaît dans la décomposition récursive deF.

3.2. SÉMANTIQUE3p:pqp_qp^qp)qp,q0100011

1001000

0111010

1011111

FIGURE3.1 - Tableau de vérité.

3.2 Sémantique

à-dire le sens qu"on lui donne.

Lavaleur de véritéd"une formule se définit comme l"interprétation de cette for- mule, une fois que l"on s"est fixé la valeur de vérité des variables propositionnelles : le principe est d"interpréter les symboles:,_,^,),,par la négation logique, leoulo- gique (appelé aussi disjonction), leetlogique (appelé aussi conjonction), l"implication et la double implication (aussi appelée équivalence ) logique.

Formellement,

Définition 3.2 (Valuation)Unevaluationest une distribution de valeurs de vérité aux variables propositionnelles, c"est-à-dire une fonction dePversf0;1g. Dans tout ce qui suit,0représente faux, et1représente vrai. On représente souvent les conditions de la définition suivante sous la forme d"un tableau de vérité: voir la figure 3.1.

Proposition 3.2Soitvune valuation.

Par le théorème 2.5Fonction définie inductivementtheorem.2.5, il existe une unique fonctionvdéfinie sur toutFqui vérifie les conditions suivantes (B)vétendv: pour toute variable propositionnellep2 P,v(p) =v(p); (I)la négation s"interprète par la négation logique : siFest de la forme:G, alorsv(F) = 1ssiv(G) = 0; (I)^s"interprète comme le et logique : siFest de la formeG^H, alorsv(F) = 1ssiv(G) = 1etv(H) = 1; (I)_s"interprète comme le ou logique : siFest de la formeG_H, alorsv(F) = 1ssiv(G) = 1ouv(H) = 1; (I))s"interprète comme l"implication logique : siFest de la formeG)H, alorsv(F) = 1ssiv(H) = 1ouv(G) = 0; (I),s"interprète comme l"équivalence logique : siFest de la formeG,H, alorsv(F) = 1ssiv(G) =v(H). On écritvj=Fpourv(F) = 1, et on dit quevestun modèledeF, ou quev satisfaitF. On notev6j=Fdans le cas contraire. La valeur dev(F)pour la valuation vest appeléela valeur de vérité deFsurv.

4CHAPITRE 3. CALCUL PROPOSITIONNEL

3.3 Tautologies, formules équivalentes

On souhaite classer les formules selon leur interprétation. Une classe particulière de formules est celles qui sont toujours vraies que l"on appelle lestautologies. Définition 3.3 (Tautologie)Unetautologieest une formuleFqui est satisfaite par toute valuation. On note dans ce casj=F. Définition 3.4 (Equivalence)Deux formulesFetGsont diteséquivalentessi pour toute valuationv,v(F) =v(G). On écrit dans ce casFG. Exemple 3.1La formulep_ :pest une tautologie. Les formulespet::psont équi- valentes. Remarque 3.2Il est important de bien comprendre queest un symbole que l"on utilise pour écrire une relation entre deux formules, mais queFGn"est pas une formule propositionnelle. Exercice 3.2.Montrer queest une relation d"équivalence sur les formules.

3.4 Quelques faits élémentaires

Exercice 3.3.Montrer que pour toutes formulesFetG, les formules suivantes sont des tautologies : (F)F); (F)(G)F)); (F)(G)H)))((F)G))(F)H))): Exercice 3.4.[Idempotence] Montrer que pour toute formuleFon a les équiva- lences : (F_F)F; (F^F)F: Exercice 3.5.[Associativité] Montrer que pour toutes formulesF,G,Hon a les

équivalences :

(F^(G^H))((F^G)^H); (F_(G_H))((F_G)_H): En raison de l"associativité, on note souventF1_F2__Fkpour(((F1_F2)_ F

3) _Fk), etF1^F2^ ^Fkpour(((F1^F2)^F3) ^Fk).

3.5. REMPLACEMENTS D"UNE FORMULE PAR UNE AUTRE ÉQUIVALENTE5

Remarque 3.3Exactement comme on le fait avec les expressions arithmétiques : on écrit1+2+3pour((1+2)+3)comme pour(1+(2+3)). Voir toutes les discussions surArithetArith0dans le chapitre précédent. Exercice 3.6.[Commutativité] Montrer que pour toutes formulesFetGon a les

équivalences :

(F^G)(G^F); (F_G)(G_F): Exercice 3.7.[Distributivité] Montrer que pour toutes formulesF,G,Hon a les

équivalences :

(F^(G_H))((F^G)_(F^H)); (F_(G^H))((F_G)^(F_H)): Exercice 3.8.[Lois de Morgan] Montrer que pour toutes formulesFetGon a les

équivalences :

:(F^G)(:F_ :G); :(F_G)(:F^ :G): Exercice 3.9.[Absorption] Montrer que pour toutes formulesFetGon a les équi- valences : (F^(F_G))F; (F_(F^G))F:

3.5 Remplacements d"une formule par une autre équi-

valente Nous connaissons maintenant quelques équivalences entre formules, mais nous al- lons maintenant nous convaincre qu"on peut utiliser ces équivalences de façon com- positionnelle : si l"on remplace dans une formule une sous-formule par une formule équivalente, alors on obtient une formule équivalente.

6CHAPITRE 3. CALCUL PROPOSITIONNEL

3.5.1 Une remarque simple

Observons tout d"abord que la valeur de vérité d"une formule ne dépend que des variables propositionnelles présentes dans la formule : lorsqueFest une formule, on noteraF(p1;;pn)pour dire que la formuleFs"écrit avec les variables proposition- nellesp1;;pnseulement. Proposition 3.3SoitF(p1;;pn)une formule. Soitvune valuation. La valeur de vérité deFsurvne dépend que de la valeur devsurfp1;p2;;png. Démonstration: La propriété s"établit facilement par induction structurelle.

3.5.2 Substitutions

Il nous faut définir ce que signifie remplacerpparGdans une formuleF, noté

F(G=p).

Cela donne la définition un peut pédante qui suit, mais nous devons en passer par là : Définition 3.5 (Substitution depparGdansF)La formuleF(G=p)est définie par induction sur la formuleF: (B)SiFest la variable propositionnellep, alorsF(G=p)est la formuleG; (B)SiFest une variable propositionnelleq, avecq6=p, alorsF(G=p)est la formuleF; (I)SiFest de la forme:H, alorsF(G=p)est la formule:H(G=p); (I)SiFest de la forme(F1_F2), alorsF(G=p)est la formule(F1(G=p)_ F

2(G=p));

(I)SiFest de la forme(F1^F2), alorsF(G=p)est la formule(F1(G=p)^ F

2(G=p));

(I)SiFest de la forme(F1)F2), alorsF(G=p)est la formule(F1(G=p)) F

2(G=p));

(I)SiFest de la forme(F1,F2), alorsF(G=p)est la formule(F1(G=p), F

2(G=p)).

3.5.3 Compositionnalité de l"équivalence

On obtient le résultat promis : si l"on remplace dans une formule une sous-formule par une formule équivalente, on obtient une formule équivalente. Proposition 3.4SoientF;F0;GetG0des formules. Soitpune variable proposition- nelle.

Si Fest une tautologie, alorsF(G=p)aussi.

Si FF0, alorsF(G=p)F0(G=p).

Si GG0alorsF(G=p)F(G0=p).

Exercice 3.10.Prouver le résultat par induction structurelle.

3.6. SYSTÈME COMPLET DE CONNECTEURS7

3.6 Système complet de connecteurs

Proposition 3.5Toute formule propositionnelle est équivalente à une formule qui est construite uniquement avec les connecteurs:et^. Démonstration: Cela résulte d"une preuve par induction sur la formule. C"est vrai pour les formules qui correspondent à des variables propositionnelles. Supposons la propriété vraie pour les formulesGetH, c"est-à-dire supposons queG(respectivement H) est équivalente à une formuleG0(respectivementH0) construite uniquement avec les connecteurs:et^. SiFest de la forme:G, alorsFest équivalente à:G0et l"hypothèse d"induction est préservée. SiFest de la forme(G^H), alorsFest équivalente à(F0^H0)et la propriété d"induction est préservée. SiFest de la forme(G_H), en utilisant la deuxième loi de Morgan et le fait que K ::Kpour éliminer les doubles négations, on obtient queF :(:G0^ :H0) qui est bien construite en utilisant uniquement les connecteurs:et^. SiFest de la forme(G)H), alorsFest équivalente à(:G0_H0)qui est équivalente à une formule construite uniquement avec les connecteurs:et^par les cas précédents. SiFest de la forme(G,H), alorsFest équivalente à(G0)H0)^(H0)G0) qui est équivalente à une formule construite uniquement avec les connecteurs:et^ par les cas précédents. Un ensemble de connecteurs qui a la propriété plus haut pourf:;^gest appelé un système complet de connecteurs. Exercice 3.11.Montrer quef:;_gest aussi un système complet de connecteurs. Exercice 3.12.Donner un connecteur logique binaire tel qu"à lui seul il constitue un système complet de connecteurs.

3.7 Complétude fonctionnelle

SupposonsP=fp1;p2;;pngfini. SoitVl"ensemble des valuations surP. Puisqu"une valuation est une fonction def0;1gndansf0;1g,Vcontient2néléments. Chaque formuleFsurPpeut être vue comme une fonction deVdansf0;1g, que l"on appellevaleur de vérité deF: cette fonction est la fonction qui à une valuationv associe la valeur de vérité de la formule sur cette valuation. Il y a22nfonctions deVdansf0;1g. La question qui se pose est de savoir si toutes les fonctions peuvent s"écrire comme des formules. La réponse est positive : Théorème 3.1 (Complétude fonctionnelle)SupposonsP=fp1;p2;;pngfini.Soit Vl"ensemble des valuations surP. Toute fonctionfdeVdansf0;1gest la valeur de vérité d"une formuleFsurP.

8CHAPITRE 3. CALCUL PROPOSITIONNEL

Démonstration: La preuve se fait par récurrence sur le nombre de variables pro- positionnellesn. Pourn= 1, il y a quatre fonctions def0;1g1dansf0;1g, qui se représentent par les formulesp,:p,p_ :p,p^ :p. Supposons la propriété vraie pourn1variables propositionnelles. Considérons P=fp1;;pnget soitfune fonction def0;1gndansf0;1g. Chaque valua- tionv0surfp1;p2;;pn1gpeut se voir comme la restriction d"une valuation sur fp1;;png. Soitf0(respectivementf1) la restriction defà la valuationvtelle quev(pn) = 0(resp.v(pn) = 1). Les fonctionsf0etf1sont des fonctions défi- nies des valuations surfp1;;pn1gdansf0;1get se représentent par des formules G(p1;;pn1)etH(p1;;pn1)respectivement par hypothèse de récurrence. La fonctionfpeut alors se représenter par la formule (:pn^G(p1;;pn1))_(pn^H(p1;;pn1)) ce qui prouve l"hypothèse de récurrence au rangn. Remarque 3.4Notre lecteur assidu aura remarqué que la proposition 3.5 peut aussi se voir comme la conséquence de cette preuve.

3.8 Formes normales

3.8.1 Formes normales conjonctives et disjonctives

On cherche souvent à ramener les formules sous une forme équivalente la plus simple possible. Définition 3.6Unlittéralest une variable propositionnelle ou sa négation, i.e. de la formep, ou:p, pourp2 P. Définition 3.7Uneforme normale disjonctiveest une disjonctionF1_F2_Fkdek formules,k1où chaque formuleFi,1ikest une conjonctionG1^G2^G` de`littéraux (`pouvant dépendre dei). Exemple 3.2Les formules suivantes sont des formes normales disjonctives ((p^q)_(:p^ :q) ((p^q^ :r)_(q^ :p)) (p^ :q) Définition 3.8Uneforme normale conjonctiveest une conjonctionF1^F2^Fkde de`littéraux (`pouvant dépendre dei).

3.8. FORMES NORMALES9

Exemple 3.3Les formules suivantes sont des formes normales conjonctives (:p_q)^(p_ :q) (:p_q)^ :r (:p_q) Théorème 3.2Toute formule sur un nombre fini de variables propositionnelles est équivalente à une formule en forme normale conjonctive. Théorème 3.3Toute formule sur un nombre fini de variables propositionnelles est équivalente à une formule en forme normale disjonctive. Démonstration: Ces deux théorèmes se prouvent par récurrence sur le nombren de variables propositionnelles. Dans le cas oùn= 1, on a déjà considéré dans la preuve précédente des for- mules qui couvrent tous les cas possibles et qui sont en fait à la fois en forme normale conjonctive et disjonctive. On suppose la propriété vraie pourn1variables propositionnelles. Soitfla fonction valeur de vérité associée à la formuleF(p1;;pn). Comme dans la dernière preuve, on peut construire une formule qui représentef, en écrivant une formule de la forme (:pn^G(p1;;pn1))_(pn^H(p1;;pn1)): disjonctive

G(G1_G2_ _Gk)

H(H1_H2_ _H`)

On peut alors écrire

(:pn^G)(:pn^G1)_(:pn^G2)_ _(:pn^Gk) qui est en forme normale disjonctive et (pn^H)(pn^H1)_(pn^H2)_ _(pn^Hk) qui est aussi en forme normale disjonctive. La fonctionfest donc représentée par la disjonction de ces deux formules, et donc par une formule en forme normale disjonc- tive. Si l"on veut obtenirFen forme normale conjonctive, alors l"hypothèse d"induction produit deux formes normales conjonctivesGetH. L"équivalence que l"on utilise est alors

F((:pn_H)^(pn_G)):

Remarque 3.5Notre lecteur assidu aura remarqué que le théorème précédent, comme la proposition 3.5 peuvent aussi se voir comme la conséquence de cette preuve.

10CHAPITRE 3. CALCUL PROPOSITIONNEL

3.8.2 Méthodes de transformation

En pratique, il existe deux méthodes pour déterminer une forme normale disjonc- tive, ou conjonctive équivalente à une formule donnée. La première méthode consiste à transformer la formule par équivalences successives à l"aide des règles suivantes ap- pliquées dans cet ordre : 1.

élimination des connecteurs )par

(F)G)(:F_G) 2. entrée des nég ationsle plus à l"intérieur possible : :(F^G)(:F_ :G) :(F_G)(:F^ :G) 3. distrib utivitéde _et^l"un par rapport à l"autre

F^(G_H))((F^H)_(F^H))

F_(G^H))((F_H)^(F_H))

Exemple 3.4Mettre la formule:(p)(q)r))_(r)q)sous forme normale disjonctive et conjonctive.

On utilise les équivalences successives

:(:p_(:q_r))_(:r_q) (p^ :(:q_r))_(:r_q) (p^q^ :r)_(:r_q) qui est une forme normale disjonctive. (p^q^ :r)_(:r_q) (p^ :r_q)^(:r_q) L"autre méthode consiste à déterminer les valuationsvtelles quev(F) = 1, et à écrire une disjonction de conjonction, chaque conjonction correspondant à une valua- tion pour laquellev(F) = 1. gant les valuations donnant la valeur1avec celles donnant la valeur0, et en échangant conjonction et disjonction. Exercice 3.13.Montrer que la forme normale conjonctive et disjonctive d"une for- mule peut être exponentiellement plus longue que la taille de la formule. La taille d"une formule est définie comme la longueur de la formule vue comme un mot.

3.9. THÉORÈME DE COMPACITÉ11

3.9 Théorème de compacité

3.9.1 Satisfaction d"un ensemble de formules

On se donne cette fois un ensemblede formules. On cherche à savoir quand est-ce qu"on peut satisfaire toutes les formules de.

Commençons par fixer la terminologie.

Définition 3.9Soitun ensemble de formules.

Une valuation satisfaitsi elle satisfait chaque formule de. On dit aussi dans ce cas que cette valuation estun modèlede. -est ditconsistant(on dit aussisatifiable) s"il possède un modèle. En d"autres termes, s"il existe une valuation qui satisfait. -est ditinconsistant, oucontradictoire, dans le cas contraire. Définition 3.10 (Conséquence)SoitFune formule. La formuleFest diteune consé- quencedesi tout modèle deest un modèle deF. On note alorsj=F. Exemple 3.5La formuleqest uneconséquence de l"ensemble de formulesfp;p)qg.

L"ensemble de formulesfp;p)q;:qgest inconsistant.

On peut déjà se convaincre du résultat suivant, qui relève d"un jeu sur les défini- tions. Proposition 3.6Toute formuleFest une conséquence d"un ensemblede formules si et seulement si[ f:Fgest inconsistant. Démonstration: Si toute valuation qui satisfaitsatisfaitF, alors il n"y a pas de valuation qui satisfait[f:Fg. Réciproquement, par l"absurde : s"il y a une valuation qui satisfaitet qui ne satisfait pasF, alors cette valuation satisfaitet:F. Exercice 3.14.Montrer que pour toutes formulesFetF0,fFg j=F0si et seulement siF)F0est une tautologie. Plus fondamentalement, on a le résultat surprenant et fondamental suivant. Théorème 3.4 (Théorème de compacité (1ère version))Soitun ensemble de for- mules construites sur un ensemble dénombrablePde variables propositionnelles. Alorsest consistant si et seulement si toute partie finie deest consistant. Remarque 3.6Remarquons que l"hypothèsePdénombrable n"est pas nécessaire, si l"on accepte d"utiliser l"hypothèse de Zorn (l"axiome du choix). On se limitera au cas

Pdénombrable dans ce qui suit.

En fait, ce théorème peut se reformuler sous la forme suivante Théorème 3.5 (Théorème de compacité (2ième version))Soitunensembledefor- mules construites sur un ensemble dénombrablePde variables propositionnelles. Alorsest inconsistant si et seulement sipossède une partie finie inconsistante.

12CHAPITRE 3. CALCUL PROPOSITIONNEL

Ou encore sous la forme suivante :

Théorème 3.6 (Théorème de compacité (3ième version))Pour tout ensemblede formules propositionnelles, et pour toute formule propositionnelleFconstruites sur un ensemble dénombrablePde variables propositionnelles,Fest une conséquence de si et seulement siFest une conséquence d"une partie finie de. L"équivalence des trois formulations n"est qu"un simple exercice de manipulations de définitions. Nous allons prouver la première version du théorème. Une des implications est triviale : siest consistant, alors toute partie deest consistant, et en particulier les parties finies. Nous allons donner deux preuves de l"autre implication. Une première preuve qui fait référence à des notions de topologie, en particulier de compacité, et qui s"adresse à ceux qui connaissent ces notions, et qui sont amateurs de topologie. Démonstration:[Preuve topologique] L"espace topologiquef0;1gP(muni de la topologie produit) est un espace compact, car il s"obtient comme un produit de com- pacts (Théorème de Tychonoff). Pour chaque formule propositionnelleF2, l"ensembleFdes valuations qui la d"un nombre fini de variables, celles qui apparaissent dans la formule. Il est également fermé puisque celles qui ne satisfont pasFsont celles qui satisfont:F. L"hypothèse du théorème entraîne que toute intersection finie deFpourF2est non-vide. Commef0;1gPest compact, l"intersection de tous lesFpourF2est donc non-vide.

Voici une preuve qui évite la topologie.

Démonstration:[Preuve directe] ConsidéronsP=fp1;p2;;pk;gune

énumération deP.

Nous allons prouver le lemme suivant : supposons qu"il existe une applicationv defp1;p2;;pngdansf0;1gtelle que tout sous-ensemble fini deait un modèle dans lequelp1;;pnprennent les valeursv(p1), ...,v(pn). Alors on peut étendrev

àfp1;p2;;pn+1gavec la même propriété.

En effet, siv(pn+1) = 0ne convient pas, alors il existe un ensemble finiU0de qui ne peut pas être satisfait quandp1;;pn;pn+1prennent les valeurs respectives v(p1), ...,v(pn)et0. SiUest un sous-ensemble fini quelconque de, alors d"après l"hypothèse faite surv,U0[Ua un modèle dans lequelp1;;pnprennent les valeurs v(p1);;v(pn). Dans ce modèle, la propositionpn+1prend donc la valeur1. Autre- ment dit, tout sous-ensemble finiUdea un modèle dans lequelp1;;pn;pn+1 prennentlesvaleursrespectivesv(p1),...,v(pn)et1.Ditencoreautrement,soitv(pn+1) =

0convient auquel cas on peut fixerv(pn+1) = 0, soitv(pn+1) = 0ne convient pas

auquel cas on peut fixerv(pn+1) = 1qui convient. En utilisant ce lemme, on définit ainsi une valuationvtelle que, par récurrence sur n, pour chaquen, tout sous-ensemble fini dea un modèle dans lequelp1;;pn prennent les valeursv(p1), ...,v(pn). Il en résulte quevsatisfait: en effet, soitFune formule de.Fne dépend que d"un ensemble finipi1;pi2;;pikde variables propositionnelles (celles qui ap- paraissent dansF). En considérantn= max(i1;i2;;ik), chacune de ces variables

3.10. EXERCICES13

p ijest parmifp1;;png. Nous savons alors que le sous ensemble finifFgréduit àquotesdbs_dbs5.pdfusesText_9

[PDF] calcul des propositions exercices corrigés

[PDF] le resultat dune multiplication est

[PDF] comment calculer le taux de possession du stock

[PDF] cout de stockage annuel

[PDF] calcul du stock moyen

[PDF] exercice cout de passation et possession

[PDF] calcul tangente formule

[PDF] calcul tangente fonction

[PDF] calcul tangente en ligne

[PDF] calculer tangente calculatrice

[PDF] a quoi sert le sinus

[PDF] taux d'évolution successif

[PDF] imc 22 femme

[PDF] tableau imc femme

[PDF] imc 23 femme