semble P de variables propositionnelles, notées p, q, r, , et les connecteurs lo- giques {¬ Définition 3 (Sous-formules) ´Etant donnée une formule logique A,
Previous PDF | Next PDF |
[PDF] Cours 2: Calcul propositionnel Calcul des prédicats Complétude
Soit T un ensemble de formules propositionnelles, et F une formule propositionnelle Une preuve de F `a partir de T est une suite finie F1,F2,··· ,Fn de formules
[PDF] Cours Logique et Calculabilité - CNU 27 Marseille
Les formules (ou phrases, ou énoncés) du calcul propositionnel sont de deux types : ou bien une formule est une proposition atomique, ou bien elle est composée
[PDF] Logique et Calcul Propositionnel
Definition (Formule bien formée) On définit une formule bien formée (fbf) par : p, o`u p est une variable propositionnelle (A ∨ B) (A ∧ B) (¬A) (A → B) : si A
[PDF] Le calcul propositionnel - IRIF
formule propositionnelle A Fixer une interprétation qui donne V ou F à chaque lettre propositionnelle Dé nir la fonction booléenne unaire FB¬ : BOOL → BOOL
[PDF] Cours Logique et Calculabilité - CNU 27 Marseille
18 mar 2017 · Les formules (ou phrases, ou énoncés) du calcul propositionnel sont de deux types : ou bien une formule est une proposition atomique,
[PDF] Logique : le calcul propositionnel - IRISA, Rennes
Introduction Syntaxe du calcul propositionnel Sémantique du calcul propositionnel Grands théor`emes du calcul propositionnel L'ensemble L des formules du calcul propositionnel est le plus petit ensemble tel que : (admis dans ce cours)
[PDF] calcul propositionnel - LIRMM
6 oct 2001 · 1 1 Pourquoi un cours de logique? Nombreuses utilisations de la logique en informatique – intérêt immédiat en algo: écrire des conditionnelles
[PDF] Calcul Propositionnel - DI ENS
Dans ce cours, nous introduisons le calcul propositionnel Cette logique permet d 'écrire des formules à propos de variables atomiques, connectées par des
[PDF] CALCUL PROPOSITIONNEL - LAMA
Calcul propositionnel Exercice : Montrer que les deux méthodes de démonstration formelles sont équivalentes Les cours de 1ère année s'arrête ici concernant
[PDF] Cours logique - Mémo n˚1 Logique propositionnelle - CNRS
semble P de variables propositionnelles, notées p, q, r, , et les connecteurs lo- giques {¬ Définition 3 (Sous-formules) ´Etant donnée une formule logique A,
[PDF] calcul propositionnel exercices corrigés
[PDF] logique propositionnelle table de vérité
[PDF] calcul propositionnel formel
[PDF] calcul des propositions exercices corrigés
[PDF] le resultat d'une 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
Cours logique - Memo n1
Logique propositionnelle
Emmanuel Coquery
1 Syntaxe
Denition 1 (Formules logiques)Soient les deux constantes>et?, un en- semblePdevariables propositionnelles, noteesp;q;r;:::, et lesconnecteurs lo- giquesf:;_;^;);,g. {>,?,poupest une variable propositionnelle sont des formules. { SiAest une formule, alors(:A)est une formule. { SiAetBsont des formules alors(A_B),(A^B),(A)B)et(A,B) sont des formules. On pourra se passer des parentheses en utilisant les regles suivantes ::est plus prioritaire que les autres operateurs et_et^sont plus prioritaires que)et,. Denition 2 (Formules atomiques)Une formule estatomiquesi c'est>,?ou si c'est une variable propositionnelle.Denition 3 (Sous-formules)
Etant donnee une formule logiqueA, l'ensemble
de sessous-formulesest donne par la fonctionsf(A), denie inductivement comme suit : { SiAest atomique,sf(A) =fAg. { SiAest de la forme:B, alorssf(A) =fAg [sf(B). { SiAest de la formeB_C,B^C,B)CouB,C, alorssf(A) =fAg [sf(B)[sf(C). Denition 4 (Arbre de syntaxe abstraite)L'arbre de syntaxe abstraiteASA(A) associe a une formuleAest un arbre dont les noeud sont etiquete par des connec- teurs logiques ou des variables propositionnelles. Il est inductivement deni comme suit : { SiAest atomique, alorsASA(A)est une feuille etiquetee parA. { SiA=:B, alorsASA(A)est un arbre dont la racine est etiquetee par:et qui a un seul ls :ASA(B). { SiA=B_C, alorsASA(A)est un arbre dont la racine est etiquetee par_ et qui a deux ls. Le ls gauche estASA(B)et le ls droit estASA(C). { SiA=B^C, alorsASA(A)est un arbre dont la racine est etiquetee par^ et qui a deux ls. Le ls gauche estASA(B)et le ls droit estASA(C). { SiA=B)C, alorsASA(A)est un arbre dont la racine est etiquetee par )et qui a deux ls. Le ls gauche estASA(B)et le ls droit estASA(C). { SiA=B,C, alorsASA(A)est un arbre dont la racine est etiquetee par ,et qui a deux ls. Le ls gauche estASA(B)et le ls droit estASA(C).2 Semantique
Denition 5L'ensemble desbooleens, noteB, est l'ensemblef0;1g.0denote la valeurfauxet1la valeurvrai. Denition 6Unefonction booleenneanarguments est une fonctionBn! B. 1 Denition 7La fonction booleennef:associee au connecteur:est donnee par la table de verite suivante :xf :(x)10 01 Les fonction booleennesf_,f^,f)etf,associees aux connecteurs_,^,)et ,sont donnees par la table de verite suivante :x yf _(x;y)f ^(x;y)f )(x;y)f ,(x;y)1 111111 01000
0 11010
0 00011
Denition 8Uneinterpretationpour un ensemble de variable propositionnellesP est une fonctionI:P! B. Denition 9Lavaleur de verited'une formuleApar rapport a une interpretation I, notee[A]Iest denie inductivement de la maniere suivante : { Sipest une variable propositionnelle,[p]I=I(p). {[>]I= 1et[?]I= 0. { SiAest une formule logique alors[:A]I=f:([A]I). { SiAetBsont deux formules logiques alors : {[A_B]I=f_([A]I;[B]I) {[A^B]I=f^([A]I;[B]I) {[A)B]I=f)([A]I;[B]I) {[A,B]I=f,([A]I;[B]I) Denition 10Une interpretationIest unmodeled'une formuleA, noteIj=A, si et seulement si[A]I= 1. Une interpretationIest un modele d'un ensemble de formulesE=fA1;:::;Ang, noteIj=E, si pour toute formuleAi2E,Ij=Ai. Denition 11Une formuleAest ditesatisablesi il existe une interpretationI telle queIj=A. Une ensemble de formulesE=fA1;:::;Angest satisable si il existe une in- terpretationIqui est un modele deE. Une formule (resp. un ensemble de formules) qui n'est pas satisable est dit insatisable. Denition 12Le problemeSATconsiste a determiner si une formule est satis- able. Autrement dit,SAT(A) =truesiAest satisable. SinonSAT(A) =false. L'algorithme naf pour resoudre ce probleme consiste a enumerer toutes les in- terpretations possibles deApour verier si une de ces interpretations est un modele deA. On peut remarquer que siApossedenvariables, il existe 2ninterpretations possibles pourA. Il n'existe cependant pas d'algorithme connu permettant de faire mieux dans tous les cas (le probleme est dit NP-Complet). Denition 13Une formuleAestvalide, si toute interpretation est un modele de A. On notej=Ale fait queAsoit valide. On dit egalement queAest unetautologie. Un ensemble de formules est valide si toutes ses formules sont valides. Propriete 1Une formuleAest valide si et seulement si:Aest insatisable. 2 Preuve:(Inter^et de la preuve : comprendre les interactions entre les denitions 7,9, 10, 11 et 13.)
Aest valide si et seulement si (notessi) pour toute interpretationI,Ij=A, i.e. ssi [A]I= 1. D'apres les denitions 7 et 9 [A]I= 1 ssi [:A]I= 0. DoncAest valide ssi pour toute interpretationI,I6j=:A, i.e. si:Aest insatisable.2 Denition 14SoitE=fA1;:::;Angune ensemble de formules etBune formule. Best une consequence logique deE, noteEj=Bsi tout modele deEest un modele deB.Propriete 2
{fA1;:::;Ang j=Bsi et seulement si(A1^:::^An))Best valide. { SiEest insatisable, alors pour toute formuleB,Ej=B. { SiBest valide, alors pour toutE,Ej=B. {Ej=Bsi et seulement siE[ :Best insatisable.Preuve:A faire en TD2
3 Equivalence de formules
Denition 15Deux formulesAetBsont dites equivalentes, noteAB, siAj=BetBj=A.
Propriete 3 (Principe de substitution)SoientA,BetCdes formules telles queABetAest une sous-formule deC. Toute formuleC0obtenue en remplacant une occurrence deAparBdansCest equivalente aC.Preuve:A faire en TD.2
Denition 16Soitfune fonction booleenne anarguments. SoitAune formule ayantnvariablesp1;:::;pn. Si, pour toute interpretationIdeA, on af(I(p1);:::;I(pn)) = [A]I, alors ont dit quefestrealisee parA. Denition 17SoitCun ensemble de connecteurs.Cest ditfonctionnellement completsi pour toute fonction booleennefil existe une formuleAne contenant que des connecteurs deCet telle quefsoit realisee parA. Propriete 4f:;_;^g,f:;^g,f:;_getf:;)gsont fonctionnellement complets. Preuve:(Inter^et de la preuve : voir une preuve par recurrence, preuve constructive : on peut en faire un programme.) On commence par prouver quef:;_;^gest fonctionnellement complet. Soitf:Bn! B. On montre par recurrence qu'il existe une formuleAfayant p1;:::;pncomme variables telle que pour tout (b1;:::;bn)2 Bn, en posantI(p1) =
b1;:::;I(pn) =bn, on a [Af]I=f(b1;:::;bn).
Considerons le cas de basen= 1.
Il n'y a que 4 fonctions booleennes a 1 argument, decrites dans le tableau ci- dessous :f(0)f(1)f 111f 210
f 301
f 400
3 Le tableau ci-dessous donne pour chaquefila formuleAiqui la realise (i.e. telle que pour toutb12 f0;1g, en posantI(p1) =b1, on a [Ai]I=fi(b1) :A 1p