Logique Flashcards
Variable propositionnelle (= formule atomique dans le cas de la logique propositionnelle)
Une proposition, ou assertion, peut prendre la valeur vrai ou faux
Proposition logique (= formule logique dans le cas de la logique propositionnelle)
Une proposition logique est une variable propositionnelle ou une combinaison de variables propositionnelles
Loi ∧ et loi ∨ (relation et propriété)
Associativité de ∧ et ∨, distributivité de l’une par rapport à l’autre
Définition de logiquement équivalent
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
Lois de Morgan
¬(A∧B) ≡ ¬A∨¬B
¬(A∨B) ≡ ¬A∧¬B
Définition d’un système complet
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.
Définition d’un littéral
Un littéral est une variable propositionnelle ou la négation d’une variable propositionnelle.
Écriture disjonctive
P = A + B + …
+ correspond à “ou”
Écriture conjonctive
P = A.B. …
. correspond à “et”
Minterme
Conjonction de littéraux où chaque variable propositionnelle figure une unique fois
Maxterme
Disjonction de littéraux où chaque variable propositionnelle figure une unique fois
Forme normale disjonctive (FND)
Disjonction de mintermes
Ex : la FND de A <=> B est A.B + A(barre).B(barre)
(barre) correspond à NOT
Forme normale conjonctive (FNC)
Conjonction de maxtermes
Ex : la FNC de A <=> B est (A(barre) + B).(A + B(barre))
Définition de satisfiable
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)
Définition d’une tautologie
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)
Définition d’une antologie
P, une proposition logique, est une antologie si elle n’est pas satisfiable, c’est-à-dire ¬P est une tautologie
P une proposition logique
Définition d’un impliquant de P et d’un impliquant premier de P
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
Principe de construction d’un tableau de Karnaugh
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)
Obtention d’un impliquant premier dans un tableau de Karnaugh
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)
