Logique 1 Flashcards
Qu’est-ce que la preuve par cas ?
Diviser le problème en plusieurs cas distincts et les prouver séparément.
Comment prouver l’implication mutuelle entre P et Q ?
Montrer que P implique Q et que Q implique P.
Quel est le principe de la contraposition ?
Pour prouver P → Q, prouver que ¬Q → ¬P.
Qu’est-ce que la méthode de preuve par absurde ?
Prouver P en montrant que ¬P conduit à une contradiction.
Quelle est la définition de la logique propositionnelle ?
Utiliser des règles de déduction pour établir la validité de propositions simples.
Qu’est-ce que la logique des prédicats ?
Utiliser des règles de déduction pour des assertions complexes impliquant des quantificateurs.
Qu’est-ce que l’unification des termes ?
Trouver une substitution qui rend deux termes identiques.
Quelles sont les techniques d’élimination des quantificateurs ?
Transformer des expressions logiques pour supprimer les quantificateurs existentiels et universels.
Qu’est-ce que la preuve par contraposée ?
P → Q équivaut à ¬Q → ¬P.
Qu’est-ce que le Modus Ponens ?
A → B, A ⊢ B.
Comment introduire une implication ?
Si Γ, A ⊢ B alors Γ ⊢ A → B.
Qu’est-ce que l’élimination de l’implication ?
Si Γ ⊢ A → B et Γ ⊢ A alors Γ ⊢ B.
Qu’est-ce que l’élimination de la quantification existentielle ?
∀x (A(x)) ⇒ A(t).
Comment introduire la quantification existentielle ?
Si Γ ⊢ A[t/x] alors Γ ⊢ ∃x A.
Qu’est-ce que l’élimination de la quantification universelle ?
Si Γ ⊢ ∀x A alors Γ ⊢ A[t/x].
Comment introduire la quantification universelle ?
Si Γ, A[x/y] ⊢ B alors Γ ⊢ ∀x A → B.
Qu’est-ce que l’algorithme d’unification ?
Un processus itératif pour trouver une substitution qui rend deux termes identiques.
Quel est le principe de résolution ?
Technique pour prouver l’insatisfiabilité de formules logiques en calculant des résolvantes.
Qu’est-ce que la skolémisation ?
Processus pour éliminer les quantificateurs existentiels en introduisant des fonctions de Skolem.
Qu’est-ce qu’un modèle en logique ?
Interprétations qui satisfont des formules logiques.
Qu’est-ce qu’une théorie en logique ?
Ensembles de formules logiques fermées par déduction.
Qu’est-ce qu’une axiomatisation ?
Définir des structures à partir d’ensembles d’axiomes.
Qu’est-ce que la démonstration par l’absurde ?
Supposer la négation de la proposition à prouver et montrer que cela mène à une contradiction.
Qu’est-ce que le raisonnement par contraposition ?
Prouver P → Q en prouvant ¬Q → ¬P.
Élimination des quantificateurs : procédure utilisée pour obtenir des formules sans quantificateurs.
Techniques pour obtenir des formules équivalentes sans quantificateurs.
