[PDF] Qu - univency-educationcom

Calul Propositionnel Résumé de cours d’après les transparents

(du calcul propositionnel) variable propositionnelle Sont synonymes: formule (du calcul propositionnel) proposition (complexe) Les propositions ou formules sont définies ainsi: 1 Les propositions atomiques sont des propositions 2 Si Xest une proposition, alors (:X) ("non X", la négation de X) est une pro-position 3 Si Xet Ysont des

Support de cours Logique Mathématique

Le langage du calcul propositionnel 1 1 Introduction Le calcul des propositions ou calcul propositionnel est une théorie logique ayant pour objet l’étude des relations logiques entre «propositions» et définissant les lois for-melles selon lesquelles, au moyen de connecteurs logiques, les propositions se coor-

BTS IG - Math´ematiques - Alexandre Meslé

1 1 1 Introduction au calcul propositionnel Les deux propositions suivantes sont des constantes appel´ees valeurs de v´erit´e : – la proposition V (pour true) est toujours vraie – la proposition F (pour false) est toujours fausse Une variable propositionnelle x peut prendre soit la valeur V, soit la valeur F On construit des pro-

Qu - univency-educationcom

d'élaborer un calcul, que nous nommerons: calcul propositionnel Cela entraîne que les propositions soient traitées comme des variables, désignées par des lettres (p, q, r, ) et que l'on introduise des opérations permettant de combiner les valeurs de ces variables 11

MÉTHODES MATHÉMATIQUES POUR L’INFORMATIQUE

semestre : l’algèbre de Boole, le calcul propositionnel, les dénombrements, etc Puis d’autres, qui demandant davantage d’efforts, et qui constituent le cours du deuxième semestre Ceux-là ont pour thème sous-jacent les applications du calcul matriciel : on rencontre des matrices dans les codes, dans les graphes, dans les automates

[PDF] logique propositionnelle exercice corrigé

[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

1

Qu'est ce que la logique?

yOn peut dire que la logique est une formalisation des lois qui font si un raisonnement est correct, au-delà de son contenu.

Exemple:

sǯil neige, alors il fait froid.

Il neige,

doncil fait froid yDe la forme "si X alors Y» 2

Définitions de la logique

Définition 1

yLa logique(du grec logikê, terme signifiant à la fois raison, langage, et raisonnement) est l'étude des règles formelles que doit respecter toute argumentation correcte.

Définition 2

yLa logique peut se définir comme lǯétude des "raisonnements » : ȂRaisonnements " formels » : démonstrations mathématiques, preuves. ȂRaisonnements " informels » : étude des discours en langues naturelles, utilisation des connaissances. 3

Définitions de la logique

yDéfinition 3 La logique est la science des arguments validesen vertu de leur formeuniquement. Le but de la logique est de distinguer les arguments valides de part leur forme des autres. Pour cela, les logiciens ont construit des langages particuliers, des langages formels. Ces langages font complètement abstraction du contenu des expressions, pour ne retenir que leur structure logique. 4

Logique en informatique

La logique apparaît dans différents aspects de lǯinformatique :

ylǯanalyse formelle de programmes : formalisation des spécifications, preuves de programmes, optimisations...

yAider les mathématiques dans lǯétablissement de preuves: assistants de preuves, démonstrateurs automatiques.

La logique est une base de lǯintelligence artificielle:

yReprésentation, acquisition et utilisation de connaissances (systèmes experts ou àbase de connaissances) ;

yRésolution de problèmes (robots, jeux) ; yCompréhension et traitement des langues naturelles (linguistique informatique). 5

Notions élémentaires de logique

formelle Une logique est constituée des éléments suivants: yLangage : ce qui permet de définir les formules. ySyntaxe ou système formel= système de calcul purement syntaxique sur les formules formé d'Axiomes et de règles dǯinférence ySémantique : ce qui donne un sens aux formules 6

Définitions

yUne syntaxe: système de symboles et de règles pour les combiner sous formes de formules. yUne sémantique : permet d'interpréter, c'est-à-dire d'attacher aux formules ainsi qu'aux symboles une signification. yUn système de déduction permet de raisonner en construisant des démonstrations. 7

La logique classique

La logique comprend classiquement:

yla logique des propositions (aussi appelée calcul des propositions), yla logique des prédicats. Ces deux derniers points feront l'objet de notre cours. 8 9

Qu'est ce qu'une proposition?

yLes propositions (contrairement aux paradoxes) sont des affirmations qui ne peuvent être que vraies ou fausses.

Exemples:

y"le ciel est bleu", y"les coquelicots sont jaunes", y"2+2=4", y"2+2=5" 10

Logique propositionnelle

yOn appelle logique propositionnellela partie de la logique qui traite des propositions. yL'un des buts de la logique propositionnelle est d'élaborer un calcul, que nous nommerons: calcul propositionnel. yCela entraîne que les propositions soient traitées comme des variables, désignées par des lettres (p, q, r, ...) et que l'on introduise des opérationspermettant de combiner les valeursde ces variables. 11

Intérêt de la logique

propositionnelle

La logique propositionnelle permet:

yLa représentation des propositions d'une manière formelle (le langage du calcul propositionnel) yDéduction de nouvelles propositions à partir d'autres propositions (système déductif) yVérification de la validité des propositions d'une manière formelle (tables de vérité) 12

Les paradoxes

yLe paradoxeest une affirmation qui contient une contradiction logique (vraie et fausse en même temps), ou un raisonnement qui, bien que sans faille apparente, aboutit à une absurdité, ou encore une situation qui contredit l'intuition commune. 13

Paradoxe de l'autoréférence

yConsidérons la phrase suivante : "cette phrase est fausse". Est-elle vraie ou fausse? ySi cette phrase est vraie, alors elle est fausse. Et si elle est fausse de part son contenu, alors elle est vraie. 14

Paradoxe de Zénon d'Elée: La

course à pied yPour atteindre la ligne d'arrivée, un coureur doit d'abord parcourir la moitié de la distance qui le sépare de cette ligne, puis la moitié de la distance restante, et ainsi de suite à l'infini. Le coureur ne terminera donc jamais la course. yCe paradoxe dit de "la dichotomie" (c'est à dire division par deux) veut montrer l'impossibilité du mouvement:sion fait la somme (infinie) de toutes les distances du problème on trouve 1: 1/2+1/4+1/8+... La limite de cette suite vaut 1. Mais une limite est ce vers quoi on tend sans jamais l'atteindre... 15

Le tiers exclu

yToute proposition est soit vraie soit fausse. 16

Etude syntaxique

17

Dessymboles(alphabet)

Desexpressions(formules)

ySoitLp(,unlangagepropositionnel 18

L'alphabet

symboles:

Lessymboleslogiquesouconnecteurs,

Lessymbolesimpropres'('et')'

19

Les formules

delamanièresuivante: (simple) formulescomposées. desformules. yRemarque: 20

Autres connecteurs

21

Priorités

22

Exemples:

((A))) s'écrira A 23

Formule bien formée

On définit une formule bien formée (fbf) par : yP (variable propositionnelle) y(A ש y(A ר y(㻀A) y(A ĺB) : si A alors B y(A ļB) Où A et B sont des variables propositionnelles ou des formules bien formées. 24

Arbre syntaxique

yOn peut dessiner pour toute formule A de la logique propositionnelle un arbre de construction = un arbre de formation = un arbre syntaxique: yLa racine de lǯarbre correspond à la formule A. yLes feuilles de lǯarbre correspondront aux atomes propositionnels. yTout à—† ȋ Žǯexception des feuilles) a un ou deux successeurs. 25

Exemple:

26

FBF et arbre syntaxique

yPour toute formule Ȅtoute expression bien formée Ȅ il existe un et en seul arbre syntaxique : la manière de formation dǯune formule est uniquement déterminée par sa syntaxe. yTout essai de dessiner un arbre syntaxique pour une non-formule va échouer. 27

Le système déductif

Deux règles pour chaque connecteur:

yUne règle dǯintroduction yUne règle dǯélimination 28

Règles du

29

Règles du

30

Règles du

31

Règles du

32

Déduction

33

Notations

calcul propositionnel.

yȗɄ1ǡ Ʉ2, ǥ, Ʉn} ٥Ʌ ‡•- ±“—‹˜ƒŽ‡-  Ʉ1ǡ Ʉ2, ǥ, Ʉn٥

34

Calcul propositionnel

35

Étude sémantique

yla sémantique renvoie à l'étude de la façon dont les formules dénotent des valeurs de vérité. yDans la logique classique que nous étudions ici, il nǯy a que deux valeurs de vérité, le vrai et le faux. 36

Table de vérité

yC'est un énorme avantage de n'avoir que deux valeurs. En effet, si npropositions p1, p2, ..., pnentrent dans la définition d'un même "monde possible", celui-ci est complètement caractérisé par une situation des valeurs de vérité de ces propositions parmi 2npossibles. yAinsi si nous avons 3 propositions: p, q, r, elles déterminent un ensemble de 222 situations a priori possibles, qui seront modélisées sous forme d'une table appelée Table de vérité. 37
colonnespourlesmsous-formulesde˙. yOn dit que ˙ est satisfiable s'il existe une valuationpour laquelle ˙ est vraie. devérité. 38
39
40

Remarque:

41

Tautologie

d'autres termes, dans la table de vérité il n'y a que la valeur vraicomme résultat. 42

Tautologie, antilogie

yRemarque: yşɄ toutes les valuations•ƒ-‹•ˆ‘- Ʉ

yşɄ aucune valuation‡ •ƒ-‹•ˆƒ‹- Ʉǡ Ʉ ‡•- —‡ antilogie.

y٬ y٬Ʉ ȋ‘ -ƒ—-‘Ž‘‰‹‡Ȍ ֙ yşɄɅ şɄ ‡- şɅ y(şɄɅ ‡- şɄ Ȍ ٨֜

yşɄɅ ȋ"‘—" ...Šƒ“—‡ ‹•-ƒ...‹ƒ-‹‘ •‹ Ʉϋ˜ ƒŽ‘"• Ʌϋ˜Ȍ

valeurs de vérité) 43

Exemple:

AA AA 44

Equivalence logique

lesmêmesinstanciations. yRemarque: desformulesdeLp(, 45

Corollaire

formulequinecontientquelesconnecteurs(, ndiraalorsque{,estunsystèmecompletde connecteursSCC. yUn ensemble de connecteurs est un SCC si toutes s'exprimer à l'aide des connecteurs de . 46

Théorème de substitution

substituant toutes les occurrences de A par la formule

Alors : ՝Ʉ ֜

47

Exemple

˙: AB,

: AB

Montrer que ՝ ˙

Montrer que ՝˙

en utilisant le théorème de substitution 48

Théorème de remplacement

Soient :

et

Alors:

49
vérité n fois) 50

Aucun ensemble de connecteurs monairesne peut

former un SCC Il existe des SCC à deux connecteurs qui sont des SCC:

Il existedes SCC à trois connecteurs ou plus.

Il existe des SCC dont l'un des connecteurs est d'arité supérieure à 2. Il existe exactement deux SCC à un seul connecteur binaire. Ces connecteurs sont appelés barres de Shaffer.

Notons ce connecteur "|".

51
52
53

Nous obtenons deux nouveaux connecteurs:

ABؠ

ABؠ

1.{} est un SCC:

2.{} est un SCC:

54

Exercice:

yMontrer: 55
56

Littéraux, conjonction de deux littéraux

yUn littéral = une variable ou une négation de variable p , ¬p yEtant données deux variables propositionnelles A et B on peut construire les conjonctions de littéraux suivantes:

Conjonctionsdedeuxlittéraux

y1=AB y2=AB y3=AB y4=AB

Disjonction de deux littéraux

Etant données deux variables propositionnelles A et B on peut construire les disjonction de littéraux:

Disjonctionsdelittéraux

y1=AB y2=AB y3=AB y4=AB

Les formes normales

Considérons le littéral Ãi= Ai ou ¬Ai

FNCForme Normale Conjonctive

y=Vrai ssi

FNDForme Normale Disjonctive

y=Faux ssi 60

Définitions:

yOn appelle forme normale disjonctive (FND) toute disjonction de conjonction de littéraux. yOn appelle forme normale conjonctive (FNC) toute conjonction de disjonction de littéraux.

Théorème:

FND (respectivement à une FNC)

Comment construire une FND?

yDéterminer l'ensemble des lignesI={I1,ǥ,Im} de la table de vérité telles que Ʉ ϋ˜"ƒ‹ où Ãi = Aisi Ai vrai,

Ai siAi faux

ySi ˙est une antilogie alors =AiAi

Exemple FND

ABA Ѧ Bi

vvf fvv2= ¬Aӟ% =(Aӟ¬B) Ӡ (¬AӟB) Ӡ (¬Aӟ¬B)

Comment construire une FNC?

On adopte le même raisonnement en considérant les où Ãi= Aisi Ai vrai,

Ai siAi faux

ySi ˙est une tautologie alors =AiAi

Exemple FNC

ABA Ѩ Bi

vvf1= ¬AӠ¬B vff2= ¬AӠB fvf3= AӠ¬B ffv

Consistance et complétude

Théorème de consistance

Alors:

yCas particulier: ՛˙ ֜

Conséquence

yLes quatre règles du calcul propositionnel du langage bien sont consistantes.

Théorème de complétude

Alors:

yCas particulier: ՝ ˙֜

Définitions

yUn ensemble est dit inconsistants'il permet de produire une inconsistance. yUn ensemble est dit satisfaisable(ou satisfiable) s'il existe une instanciation qui vérifie toutes les formules (i.e. les formules peuvent être vraies en même temps). yUn ensemble est dit inconsistants'il permet de produire une contradiction . yLemme 1

Ʉ1ǡ Ʉ2,ǥ, Ʉn٥

yLemme 2 Tout ensemble de formules consistant est un ensemble satisfiable. yContraposée

ȗ Ʉ1ǡ Ʉ2ǡǥǡ Ʉn, ɄȘ ‘ •ƒ-‹•ˆ‹ƒ"Ž‡ ֜

yRésultat Un ensemble E sera dit inconsistant s'il existe un couple de littéraux de la forme (A, A), sinon E sera dit satisfiable.

Algorithme de réfutation

transformations suivantes (clauses): 73
yOn appelle ces transformations les clauses associées aux connecteurs , (éliminertouslesconnecteurs). yL'application des clauses permet de former un arbre dont la racine est l'ensemble ʼ et les feuilles sont des ensembles de littéraux. 74
yLa méthode de construction de l'arbre aboutit à une situation d'arrêt, puisque le nombre de connecteurs diminue à chaque étape jusqu'à l'obtention des littéraux. yA la fin de l'algorithme, deux cas peuvent se présenter: ySi tous les ensembles de littéraux sont inconsistants yS'il existe au moins un ensemble de littéraux 75

Conclusion

Ʉ1ǡ Ʉ2,ǥ, Ʉn٥

Le calcul propositionnel est décidable

76
77

Tout homme est mortel

Or Socrate est un homme

Donc Socrate est mortel

78
motivations Nécessité de dépasser la logique propositionnelle :quotesdbs_dbs5.pdfusesText_9