Logique

Question 1

Variable propositionnelle (= formule atomique dans le cas de la logique propositionnelle)

Answer 1

Une proposition, ou assertion, peut prendre la valeur vrai ou faux

Question 2

Proposition logique (= formule logique dans le cas de la logique propositionnelle)

Answer 2

Une proposition logique est une variable propositionnelle ou une combinaison de variables propositionnelles

Question 3

Loi ∧ et loi ∨ (relation et propriété)

Answer 3

Associativité de ∧ et ∨, distributivité de l’une par rapport à l’autre

Question 4

Définition de logiquement équivalent

Answer 4

Deux propositions logiques P et Q sont dites logiquement équivalentes quand elles ont la même table de vérité. On note P ≡ Q
Par exemple P 𠪪P

Question 5

Lois de Morgan

Answer 5

¬(A∧B) ≡ ¬A∨¬B

¬(A∨B) ≡ ¬A∧¬B

Question 6

Définition d’un système complet

Answer 6

Un système de connecteurs est complet si toute proposition logique est logiquement équivalente à une proposition construite à partir des variables propositionnelles et de ces connecteurs.
Par définition, {¬ ; ∧ ; ∨} est complet.

Question 7

Définition d’un littéral

Answer 7

Un littéral est une variable propositionnelle ou la négation d’une variable propositionnelle.

Question 8

Écriture disjonctive

Answer 8

P = A + B + …

+ correspond à “ou”

Question 9

Écriture conjonctive

Answer 9

P = A.B. …

. correspond à “et”

Question 10

Minterme

Answer 10

Conjonction de littéraux où chaque variable propositionnelle figure une unique fois

Question 11

Maxterme

Answer 11

Disjonction de littéraux où chaque variable propositionnelle figure une unique fois

Question 12

Forme normale disjonctive (FND)

Answer 12

Disjonction de mintermes
Ex : la FND de A <=> B est A.B + A(barre).B(barre)
(barre) correspond à NOT

Question 13

Forme normale conjonctive (FNC)

Answer 13

Conjonction de maxtermes

Ex : la FNC de A <=> B est (A(barre) + B).(A + B(barre))

Question 14

Définition de satisfiable

Answer 14

P, une proposition logique, est satisfiable si elle prend la valeur vrai pour au moins une distribution de vérité (sa table de vérité comporte au moins un 1 en dernière colonne)

Question 15

Définition d’une tautologie

Answer 15

P, une proposition logique, est une tautologie si elle prend la valeur vrai pour toute distribution de vérité (sa table de vérité ne comporte que des 1 en dernière colonne)
Remarque : P est une tautologie <=> P ≡ 1
(P <=> Q est une tautologie) <=> (P ≡ Q)

Question 16

Définition d’une antologie

Answer 16

P, une proposition logique, est une antologie si elle n’est pas satisfiable, c’est-à-dire ¬P est une tautologie

Question 17

P une proposition logique

Définition d’un impliquant de P et d’un impliquant premier de P

Answer 17

Impliquant de P : conjonction de littéraux dont la valeur vrai implique P vrai
Impliquant premier de P : un impliquant de P qui n’en est plus un si on lui enlève un littéral
Remarque : un minterme d’une FND est un impliquant

Question 18

Principe de construction d’un tableau de Karnaugh

Answer 18

Le rangement des couples de 0 et 1 extérieurs (en première ligne ou en première colonne) s’effectue avec une seule variation entre deux colonnes et lignes consécutives (par exemple la ligne 01 ne peut être voisine de la ligne 10)

Question 19

Obtention d’un impliquant premier dans un tableau de Karnaugh

Answer 19

Il s’obtient à partir d’un rectangle ne contenant que des 1, de longueurs de côtés égales à des puissances de 2 et dont on ne peut doubler un côté en taille suivant aucune direction sans tomber sur un 0.
Ex : P une proposition logique faisant intervenir 4 variables propositionnelles A, B, C, D et dont la fonction booléenne associée vaut 1 si une des variables au plus prend la valeur vrai. Mq P ≡ A(barre)B(barre)C(barre) + A(barre)B(barre)D(barre) + A(barre)C(barre)D(barre) + B(barre)C(barre)D(barre)