[Ch1] Quelques notions de logique élémentaire

[Arthur - TitrOu]

I/ Propositions :

Définition : Une proposition est une assertion (affirmation) qui ne peut que prendre pour valeur "vrai" ou bien "faux". 0 et 1 sont appelés valeurs booléennes.

Exemple :

• 5 + 2 = 7 est une proposition vrai.
  
• 8< 3 est une proposition de valeur faux.
  
• "Il pleuvra demain" n'est pas une proposition.

On appel forme propositionnelle une proposition fonction d'autres propositions.

Exemple :

• Si P1 et P2 sont des propositions, alors la proposition P: "P1 et P2" est une forme propositionnelle.
  Si P1 vrai et P2 vrai alors P: vrai
  Sinon, P: faux

Définition et notation: La négation d'une proposition prenant la valeur 1 si P a pour valeur 0 (0 si P a pour valeur 1)

on la note ˥P ( on lit "non P")

Exemple : p: 5>7 alors ˥P : 5 ≤ 7
p : 0 ˥P : 1

[Arthur - TitrOu]

II/ Connecteurs logique (opérateurs binaires)

Soit P et Q deux propositions.

• a/ Conjonction
  
  On appelle conjonction de P et Q, on lit "P et Q" et on note P^Q
  La proposition qui prend la valeur 1 lorsque P et Q valent 1 simultanément, 0 sinon.
  
  
  
• b/ Disjonction (inclusive)
  
  On appelle disjonction de P et Q, on lit "P ou Q" et on note P v Q
  La proposition qui prend la valeur 0 lorsque P et Q valent 0 simultanément, 1 sinon.
  
  
  
• c/ Implication
  
  On note P => Q, on lit 'P implique Q" (ou "Si P, alors Q")
  La proposition prenant pour valeur 1 si P a pour valeur 0 ou si Q a pour valeur 1, 0 sinon.
  
  
  
  
• d/ Equivalence
  
  On note P <=> Q et on lit "P équivaut à Q"
  La proposition prenant pour valeur 1 si P et Q on même valeur, 0 sinon.
  
  
  
• e/ Disjonction exclusive
  
  On appelle disjonction exclusive de P et Q, on lit "P ou bien Q" et on note P ṿ Q
  La proposition prenant pour valeur 1 si P et Q non pas même valeur, 0 sinon.

Définition :
On appelle tautologie tout proposition ou forme propositionnelle qui ne prend que la valeur 1.
On appelle antilogie toute proposition ou forme propositionnelle qui ne prend que la valeur 0.

(P=>Q) <=> [(˥Q) => (˥P)] est une tautologie.

P ^ (˥P) est une antilogie.

[Arthur - TitrOu]

III/ "Quelques" propriétés des connecteurs logiques ^et v
(Soit P, Q et R trois propositions)

• Associativité :
  
  1/ (P^Q)^R |----| P^(Q^R)
  2/ (PvQ)vR |----| Pv(QvR)
  
  
• Commutativité :
  
  3/ P^Q |----| Q^P
  4/ PvQ |----| QvP
  
  
• Distributivité :
  
  5/ P^(QvR) |----| (P^Q)v(P^R)
  6/ Pv(Q^R) |----| (PvQ)^(PvR)
  
  
• Loi de Morgan :
  
  7/ ˥(P^Q) |----| (˥P)v(˥Q)
  8/ ˥(PvQ) |----| (˥P)^(˥Q)
  
  
• Idem potence :
  
  9/ P^P |----| P
  10/ PvP |----| P
  
  
• Absorption
  
  11/ P^(PvQ) |----| P
  12/ Pv(P^Q) |----| P
  13/ ˥(˥P) |----| P
  14/ P^(˥P) |----| 0
  15/ Pv(˥P) |----| 1
  16/ 0vP |----| P
  17/ 0^P |----| 0
  18/ 1vP |----| 1
  19/ 1^P |----| P
  20/ (˥0) |----| 1
  21/ (˥1) |----| 0

|----| signifie "tautologique à"

[Arthur - TitrOu]

IV/ Autres notations


a/ Notation algébrique

Soit a et b 2 booléens ou variable booléennes, ne pouvant prendre que la valeur 0 ou 1.

a^b est aussi noté a.b ou ab
aṿb est aussi noté aʘb
avb est aussi noté a+b
˥a est aussi noté ā ou a'
|---| est aussi noté =

Exemple / remarques

1.0 = 0.1 = 0
0+1 = 1+0 = 1
0.0 = 0
0+0 = 0
1.1 = 1
1+1 =1

Si a, b et c sont trois booléens, a+bc = (a+b)(a+c)

b/ Circuits

(Dessins a réaliser...)

[Contenu sponsorisé]