Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

USTHB-FEI-Logique Mathématique 2ème Année Licence Informatique Section Acad (A,

USTHB-FEI-Logique Mathématique 2ème Année Licence Informatique Section Acad (A, B et C) et ISIL A Série N° 3 Calcul Propositionnel : Etude Sémantique 1 Exercice 1 (Application directe) 1. Vérifier si ces formules sont valides (tautologies) / satisfiables / insatisfiables (antilogies) en utilisant les Tables de vérité. a) pp b) pq(pr) c) pqp d) pq(pq) 2. Ces formules, ont-elles de modèles ? De contre-modèles ? Donnez-en un exemple de modèle et un exemple de contre-modèle. Exercice 2 (Equivalence Logique) 1. Montrer que : |=   |=  et  2. Montrer les équivalences suivantes sans utiliser les tables de vérité : a. (PvQ) PQ b. PQ P Q c. P(QR)  (PQ)( PR) d. P(QR)  (PQ)( PR) e. PQ  (PQ)PQ) Exercice 3 (Formaliser et Analyser) Ali, Kader et Madjid sont arrêtés suite à un vol. Ali déclare : « Kader a volé mais pas Madjid» Kader déclare : « Si Ali a volé alors Madjid aussi » Madjid déclare : « Je n’ai pas volé mais au moins l’un des deux autres a volé » On utilise les variables propositionnelles A, K, M pour exprimer que « Ali est un voleur », « Kader est un voleur » et « Madjid est un voleur » et on notera 1, 2 et 3 les trois FP associées aux déclarations Ali, Kader et Madjid. 1. Exprimer les formules 1, 2 et 3. 2. Exprimer 1, 2 et 3 dans un même tableau de vérité. 3. Les trois témoignages sont-ils compatibles ? Peut-on conclure qui a volé dans ce cas ? 4. On suppose dans cette question qu’aucun n’a volé. Qui a fait une fausse déclaration ? 5. On suppose dans cette question que toutes les déclarations sont fausses. Peut-on conclure qui a volé ? 6. On suppose dans cette question que tous les voleurs ont fait une fausse déclaration et seulement eux. Peut-on déduire qui a volé ? Exercice 4(Un peu de preuve) On considère dans cet exercice que les formules sont formées avec les connecteurs «  », «  » et «  » seulement. Etant donné une formule , on note : -« * » la formule obtenue à partir de  en remplaçant chaque variable propositionnelle par sa négation et en interchangeant «  » et «  ». -« # » la formule obtenue à partir de  en interchangeant «  » et «  ». -« + » la formule obtenue à partir de  en remplaçant chaque variable propositionnelle par sa négation.  Montrer par récurrence que * quelque soit  2. En déduire la négation de la formule suivante et la simplifier (A B)(CD) 3. Montrer que  est une tautologie si et seulement si + en est une.  Montrer que *  (#)+quelque soit  5. Montrer que ()  (##)+ 6. Montrer que () si et seulement si (##) USTHB-FEI-Logique Mathématique 2ème Année Licence Informatique Section Acad (A, B et C) et ISIL A Série N° 3 Calcul Propositionnel : Etude Sémantique 2 Exercice 5 (Un nouveau connecteur) Soit Lple langage propositionnel ne contenant que les connecteurs «  », «  » et «  ». On définit le connecteur «  » par la table de vérité suivante : P Q P  Q V V F V F F F V V F F F 1. Montrer que : a) (P Q≡ P  Q b)  (P  Q≡ P Q 2. Déduire que l’ensemble {,} est un système complet de connecteur ? 3. Ecrire la FND et la FNC de P Q 4. En utilisant la FND et la FNC, trouver le(s) modèle(s) et le(s) contre-modèle(s) de la formule PQ. Expliquer Exercice6 (Encore un autre nouveau connecteur) Soient le connecteur binaire \défini par leur table de vérité ci-dessous : A B A\B V V F V F V F V F F F F 1. Donner la FNC et la FND de A\B. 2. Montrer que {, \} est un système complet de connecteurs (SCC) sachant que {, } est un SCC. 3. Montrer que la formule suivante est une tautologie : = ((A\B)(BA)). 4. Déduire si l’ensemble {} est satisfaisable ou non. Quel est l'algorithme qui permet de le confirmer ? 5. Peut-on déduire si la déduction suivante est vérifiée : ┟ (A\B)(BA) ? uploads/Geographie/ serie3-logique-des-propositions.pdf