Chapitre 5 option informatique Corrigé des exercices    Exercice 1 On obtie

Chapitre 5 option informatique Corrigé des exercices    Exercice 1 On obtient sans peine les tables de vérité suivantes : a b a | b 0 0 1 0 1 1 1 0 1 1 1 0 a a | a 0 1 1 0 De ceci on déduit les équivalences suivantes : ¬a ≡a | a a ∧b ≡¬(a | b) ≡(a | b) | (a | b) a ∨b ≡¬a | ¬b ≡(a | a) | (b | b) a ⇒b ≡a | ¬b ≡a | (b | b) a ⇔b ≡(a | b) | (¬a | ¬b) ≡(a | b) |  (a | a) (b | b)  Pour montrer que l’opérateur nor, que l’on note parfois ⊗, est lui aussi un système complet, il suffit de montrer qu’on peut exprimer le connecteur de Sheffer à l’aide du seul ⊗. a b a ⊗b 0 0 1 0 1 0 1 0 0 1 1 0 a a ⊗a 0 1 1 0 Il est facile de constater que a | b ≡¬(a ⊗b), donc a | b ≡(a ⊗b) ⊗(a ⊗b). Le nor forme donc lui aussi un système complet.    Exercice 2 Utilisons l’algèbre de Boole pour simplifier l’expression : ab(a + b)(a + b) ≡(a + b)(a + b)(a + b) ≡(ab + ab + b)(a + b) ≡(b + b)(a + b) ≡b(a + b) ≡ab donc l’expression proposée est équivalente à a ∧¬b.    Exercice 3 On calcule : ab + c + bc + ac ≡ab + c + (a + b)c ≡ab + c + abc ≡ab + c + ab + c ≡1 a + bc + ac + bc ≡a + (b + b)c + ac ≡a + c + ac ≡a + c + a + c ≡1 donc les deux expressions proposées sont bien des tautologies. http://info-llg.fr 5.2 option informatique    Exercice 4 Dressons la table de vérité de la formule logique F = (¬a ∨b) ∧c ⇐ ⇒a ⊕c : a b c ¬a ∨b (¬a∨b)∧c a ⊕c F 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 0 Sous forme normale disjonctive, nous avons F ≡abc + abc + abc + abc + abc. De même, F ≡abc + abc + abc, donc sous forme normale conjonctive on a F ≡(a + b + c)(a + b + c)(a + b + c). Formons maintenant le tableau de Karnaugh de F : 00 01 11 10 0 1 bc a 1 1 1 1 1 0 0 0 On en déduit que F ≡a + bc. Si on préfère une conjonction, on a F ≡ab + ac, donc F ≡(a + b)(a + c).    Exercice 5 Les tableaux de Karnaugh des formules F et G sont les suivants : 00 01 11 10 00 01 11 10 F cd ab 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 01 11 10 00 01 11 10 G cd ab 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 Nous avons donc F ≡ab + cd + ad + bc et G ≡a + bc.    Exercice 6 a) Posons F = ab + acd + bde ; alors le coffre peut être ouvert si et seulement si F ≡1. b) Le tableau de Karnaugh associé à F est le suivant : 000 001 011 010 110 111 101 100 10 00 01 11 cde ab 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 On observe que F ≡ab + bc + bd + ad + ae, donc F ≡(a + b)(b + c)(b + d)(a + d)(a + e). c) Ceci montre qu’il suffit de poser 5 serrures sur le coffre, et de fournir une clé de la première serrure à A et B, une clé de la deuxième serrure à B et C, une clé de la troisième serrure à B et D, une clé de la quatrième serrure à A et D, et enfin une clé de la cinquième serrure à A et E (soit 10 clés en tout). Corrigé des exercices 5.3    Exercice 7 La loi ⊕étant associative dans Z/2Z, nous avons : a ⊕(a ⊕b) ≡(a ⊕a) ⊕b ≡0 ⊕b ≡b et  a ⊕(a ⊕b)  ⊕(a ⊕b) ≡b ⊕(a ⊕b) ≡a. Considérons alors la séquence d’instructions suivante : v ←u ⊕v, u ←u ⊕v, v ←u ⊕v. Si au départ u contient l’entier a et v l’entier b, alors : – après la première instruction u contient a et v contient a ⊕b ; – après la deuxième instruction u contient a ⊕(a ⊕b) = b et v contient a ⊕b ; – après la troisième instruction u contient b et v contient b ⊕(a ⊕b) = a. Les deux références ont vu leur contenus échangés.    Exercice 8 Seule la première de ces assertions est une tautologie, ce qu’on peut prouver automatiquement : # let f = analyseur "((a => b) => a) => a" in est_une_tautologie f ;; − : bool = t r u e # let f = analyseur "((a => b) => a) => b" in satisfiabilite f ;; a = f a u x b = faux a = f a u x b = v r a i a = v r a i b = v r a i − : u n i t = ( ) L’assertion « ((a ⇒b) ⇒a) ⇒a est une tautologie » s’appelle la loi de Peirce ; en revanche la formule ((a ⇒b) ⇒ a) ⇒b n’est pas une tautologie puisqu’elle n’est pas vérifiée pour la distribution de vérité a = vrai et b = faux.    Exercice 9 Notons a la proposition « j’aime Marie » et b la proposition « j’aime Anne ». Les deux réponses du logicien peuvent se résumer par la formule F suivante :  (a ⇒b) ⇒a  ∧  a ⇒(a ⇒b)  . Formons la table de vérité de cette formule : a b a ⇒b (a ⇒b) ⇒a a ⇒(a ⇒b) F 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 1 1 1 1 On en déduit que le logicien aime à la fois Anne et Marie. Nous aurions aussi pu utiliser la fonction que nous avons définie en Caml : # let F = analyseur "((a => b) => a) et (a => (a => b))" in satisfiabilite F ;; a = v r a i b = v r a i − : u n i t = ( )    Exercice 10 Définissons les assertions suivantes : a : « x est écossais » ; b : « x porte des chaussures oranges » ; c : « x porte une jupe » ; d : « x est marié » ; e : « x sort le dimanche ». Le règlement du club indique que si x est un membre du club, alors la formule F = (¬a ⇒b) ∧(c ∨¬b) ∧(d ⇒¬e) ∧(e ⇔a) ∧(c ⇒a ∧d) ∧(a ⇒c) http://info-llg.fr 5.4 option informatique est satisfaite. Cherchons donc si cette formule peut être satisfaite : # let F = analyseur "(non a => b) et (c ou non b) et (d => non e) et (e <=> a) et (c => (a et d)) et (a => c)" ;; F : f o r m u l e = . . . # satisfiabilite F ;; − : u n i t = ( ) Il semble que F ne soit pas satisfiable, autrement dit que ¬F soit une tautologie. Vérifions-le : # est_une_tautologie (Op_unaire (neg, F)) ;; − : bool = t r u e Aucun membre du club ne peut répondre aux exigences de ce règlement ! uploads/s3/ 05-corrige-pdf.pdf

Tags
Administrationexercice contient formule serrure vérité
Documents similaires
  • 42
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager