45
Université de Bretagne Sud UFR Sciences et Sciences Pour l’Ingénieur TRAVAUX DIRIGES

Exercices de logique

  • Upload
    goulu

  • View
    550

  • Download
    7

Embed Size (px)

DESCRIPTION

Université de Bretagne SudUFR Sciences et Sciences Pour l’Ingénieur

Citation preview

Page 1: Exercices de logique

Université de Bretagne Sud

UFR Sciences et Sciences Pour l’Ingénieur

������������ ��

������������

TRAVAUX DIRIGES

����������� ����������� ��� �� ����������

���������

������������� �� �����������

�������� ��������� ����

����� ��������

Page 2: Exercices de logique

������������ ���������������������������

���������������������������

Page 3: Exercices de logique

������������ ���������������������������

���������������������������

Introduction à la logique

!����� ����" ���

Exercice 1 — Les profs de maths de lycée sont-ils de fieffés menteurs ? (contrôle continu 2001-2002)

������������ �����!�������"�� ����#������$��%�$���&������%����$��'(��������������!����������"�� ���

������)��#��$����#���$������*+��#����,) �����#����!��������������������� �����-

���������������� �������������������!��������������������"����#���

� ��� � .��/

��$������� �� ��������%

� ��� � .��/

Page 4: Exercices de logique

������������ ���������������������������

�������������������������0�

Logique des propositions (LP)

!����� ����" ���

Exercice 2 — Foules Sentimentales...

1�!�����������#��#�����������$�&���2" "3�����#������������#�!�� �$����������������43�������'���5����4"

43�������'�����!%�4"43�������'���!���5��4��46��� � ������������!������#���7���4

������!�����#%�������$#���&������������!%�!������#��#����������� �����-

���2 5��2∧� !��2 �

��2∧ ��3 ��3�2∨ � .���2⇔3�

��2∨ �∧�3����

��+�����������#��#���������������&���������#�����%����������������*

Exercice 3 — Météorologie logique

������������������&�����#��#���������������!����� ����-

��&����� ���������������'������������� �(����������)�������!���!��

��&����#���*������� ����� ��(��������"������#�����#���*��������� �����*� ���

0�+) ���������,��������*%������*��������� ���% ����������� ����� ��

Exercice 4 — Nécessaire ou suffisant ? (contrôle continu 2001-2002 ; 5’)

1�!����������!���������� ����"�/�������8��$�$��������!������'3�$#����"�99�"-�����,�������������

*� ��� ����*�� *���� ��� !�� �� ���%" :�!����� ��� ������ �� ;�� ��!�" #'�<��- .�/��� )� �0 �5���!� �� .���������

!��!���� �� ��������&�8=��� #�����' 3�#������"����!�#��&�� �8��� #�� ����-��� #����� #�� ��� !���������/���

!������*�0.���������!��!���� ��>

�#�������� �� ����&�� ��� #��#�������� �� �������� �/������ ����� �/�����!� �� #����� �� �/�����!� �� .��������

!��!���� �'1����������#���!������/���$��pause��concl usi ve'

����"�� ����#$�%��"�"��

Exercice 5 — Petit précis de géométrie euclidienne

�#��������������.��$����$���������&�����#��#������������%����$�������$�������� ����-

��&���������,�������������������������������! ��

5�$�������,����!���,���1���"�����������������

!�$���!���,�����2����������� ��������,�����������*����� ���!���,��

��$�������,��1����������*����� ���!���,������������,��

��3%�*������!� ��������������������!����(������ ����� ���

.�3�����1� �!���(�*%�*������������!���������� ����� ���������!� ��������

��3������ ������(�*%�*������������!���������� ����� ���

%�3%�*�������� #�������2�����������!������� ����� ���

Page 5: Exercices de logique

������������ ���������������������������

�������������������������?�

Exercice 6 — Rencontres logiques (examen 1999-2000 ; contrôle de Septembre ; environ 10’)

��������!%�!������#%�������� ����������.��$���������������#��#��������-

������������������!������������*���'��"���

5�4������������*��� ���'��"��(�!�������������5!���

!�6���������,� �����"����������!�������������������5!����

��7�'������#����*���'��"�����'����������5!����

Exercice 7 — Un peu de gastronomie...

1�!���������@����$5�����!���������!����� �����"�/�������@���$#��5�5��!�����@�!���%A�������'

&����!�������!�����*���� ����*�"��(�����!!�� �,������� ���*1��!�����*1���

&����!�������*���*������� ���!�������(�����!�����*��2����!���(������#�����'��,���������*�#���

+�����������*�#���� #���������#���8�*�'���!(�*��������*���,�

�#!�*����#���*(������#����*�#�����,���*��������*�'���!��#!��� �������

�#�������,!����.��$������������.��$��@������$5����.��$������������&�����#��#��������'

Exercice 8 — Le diplômé motivé (examen 1997-98 ; contrôle de Novembre)

�#������������@�2�"��#%����15��������������������!���@�$#���"#�������&����&����������.��$�������B��

����!������� �����������$$������$�����!�����#����������#��������#���#������������'�..�!�� �$���"����#����=

�@��������C<DE!������������#�������"(������� ���F���"���#����5������� �!�����������!��%�$���������

G����3�$#��H ��!'"��!�� �&��#����� �����������!���.' �$����=5��!"��#%����15����" ��#��!�#��� ������

#��$����F���#�����!�#���;����"�I�����!�� �&��'��!%�$��"��.�������������$������ �������!����������

#���!���&�����#��������!���!����������&���-

��-��!���*�,� #(�������������������*���������

��9� �����������1�*�������������������*:�#�������������!������� �������*��� ��������'�!���

0�3�$#����������#��)����!�����..�!����"��������2��1�����������)���)��*1�'�!��

?�;��*���������������*�*�����*:�#���������

C�$��!��������<�(�"���������� ����1�*������

3�3��!(������,� #� ��� �!��������'�!�

�������� = �@���� �@� ��� ��� � ���� ���#���� ��/ ��!������ ��� ������������� �H���!����" ��#%���� 15���� �����

�@�!�������������������������������������&�����#��#�������������������$���'�����,) ����@�����*

Exercice 9 — Après le 11 septembre : logique et géopolitique (contrôle continu 2001-2002 ; environ 5’)

�� (J$� &������� � �! �8����!� ��� ��� -6�� ��)� �� ��� ��!��������� �� *�� ���������� %��������� ����� ��

��,������������=���������

�.�%�� ;�K�������� ����$����L�/���$����

��3�$#����,�������!��������������&�����#��#�����������8����!���� ���-�������������6��������������� ��

������!���������� �����2���� ��%'

;���������� ��������� ;�!�.����

Exercice 10 — Histoires de connecteurs (contrôle continu 2000-2001 ; environ 10’)

��3�$#����,�������!��������������&�����#��#�����������8����!���� ���-4��,����� ��� ����������!���

��� ��������'����'

F����� �!%���� 2��%���

Page 6: Exercices de logique

������������ ���������������������������

�������������������������C�

��(J$�&�������� �!�8����!���� ���-9���� �� !��*� ����*����� �� ����*� ��������������"������ ��#���

�������*�����

1���� M������ ��� ��

� �:����,�������!��������������&�����#��#�����������8����!���� ���-4��������)��������*� (���������

!���%����������'���������#��

�:����,�������!��������������&�����#��#�����������8����!���� ���-3��������� ���!��(�!������"���

�����,���*����

����"�� ����#$# ������#���� ��

Exercice 11 — Logique, langage et littérature

:�������$#�"�������!�������!%��!%�=��#�����������������"$���.��������#���/!�����!�����#�����%�$����"

����.��$�����&��'�#��$����5���"!�#��N��#���#���7�����������5��';���/�$#��"��#�������,������.��$����$�

��������&�����#��#�����������!����������� �����-

���� ��(�*��!�"���� :��!�����":��!��������$��%����

5�������#���(�*��!�"���� 3�$��"�@����

!�>�����������������(������!�����������,� ����������"��5���-����� �������������������

��6���1)��� ���*1�����*�#�#�������*��� ����*�#�#� ��5���3�$��"�@�� ������@��������

���� ���"���������!�#������&�����O!%����!�$#��/�-�����#����������������&��������$��=������!�$#����

!����������5���������!�$#��%���������������#����� ��5����$�������!������(� �����(���#��������"#����

#�����$���������*�"2"�����"��"���"����'''� ����#��!�����������������':������&���!�$#��/��������&����

����&��$�������� ��� �� ������ #��� ��������� �� �� ��� �� .������ #��� �$#������' 2��� ��� ������� �� ��������

�!%�##���!�#���������N����=����#���������������&��'�����,������$J$�����#�����������!����������� �������

����&�����#��#��������"���������� ����������..����!����!������#�����������-

��;1���! *�2���� ��*����(����������*�"2�������*���� � 2���$��!%���"��5��5������� �����

5������"��1��'��(�!��1��� ����������������(�!1��������������������� �3�$��"3�������

!����#����"1�����������������!!��*����"� ����#�������� 2���$��!%���"��$���������������

���������������1�� �����*1������ ����������"�5'-��$������������������

��������?�����*�#����,�P��������Q���"����� ������������ �������"3�����#�����!��

.����������"�#��� �*�(������"��������"1����*� �!���"�����$�&���

��P��(Q"���������� ���� 3��������"��3���

Page 7: Exercices de logique

������������ ���������������������������

�������������������������<�

Calcul des propositions

!����� ����" ���

Exercice 12 — Tables de vérité

:���������5���� ��������#��#����������� �����-

�� �;∧+5� �;∨+�!� �;�+∧;��� �;∨+�⇔;��+�

Exercice 13 — Coût de la vie

(������������$�����.���������/�..��$��������� �����-

��&��!���'"��������(�������������!��

��3� ��(����!���'"�����!��(��������������� ������

�#��$���� ��!�����/�..��$��������$5����!�������!������'(�����,"=�8��������$��%��������5����� �����"&��

!������$5����#��#����������������.����5��'38���=����&��(������������$��8�#��.��!�$������N��������'''

�&�����������$�%��"�"��"�"��� ����

Exercice 14 — Question de rapidité : table de vérité ou calcul mental (contrôle continu 2000-2001 ; 5’)

:����,��������#���������������$��;"+�� #���/�$#��;R����S+R���/S R���/�&���������.��������

.��$������� �����-

�� ∧�;�+∨ �;��

�� P+� �;�Q∨� ∨;

Exercice 15 — Tautologies, contradictions

� � ;��!���," �� ��������� �� $��%��� ��� ��5��� �� �����" �� ��� .��$���� ��� ����� ���� ��� �����������" ���

!�������!�����"�����#��#����������$#��$��������.����5���'1�!%��!%���=��$������$�/�$�$���!��!���'

�� ;∧+�∧�;∨+�5� ;∨�;∧+�!� �;�;∧+��� ;�+��+�;�

�� ;�+�∧+� ��;� �

�'(����������������-5"!S.��$���������.����5���-�"�"�

��+�������$��&��#�����.��������N��������������*

Exercice 16 — Tautologies d'après A. Aho & J. Ullman, Concepts fondamentaux de l'informatique, Dunod

;��!���,"�������������$��%��������5����� �����"&��������������/#��������"#��$����.��$������� ����"&������

��������������'1�!%��!%���=��$������$�/�$�$���!��!���'

��;�+��;

Page 8: Exercices de logique

������������ ���������������������������

�������������������������D�

��;∧+∧ �;∨+0�;⇔+∨ ����+�;∨ �

�'(���������������-5

Exercice 17 — Tables de vérité et ou exclusif (contrôle continu 2002-2003; 10’)

;��!���," �� ��������� �� $��%��� ��� ��5��� �� �����" �� ������ ���������&��" �����.����5��" !�������!������ ���

�/#����������� �����'1�!%��!%���=��$������$�/�$�$���!��!���'

�� ;∨+�∧ ∧+�⊕�;⇔�+�

5� ;∧+�∨ ∨+�⇔�;⊕�+�

Exercice 18 — Equivalence logique

����� �,"=�8��������$��%��������5����� �����"����������@�&�� ����!���� �����-

�� ;∨+∧ � ≡ ;∨+�∧;∨ � ������5��� ����������N��!���������!��N��!�����

5� �;∧+� ≡ �;∨�+ ���������:�(������

!� ;≡;∧;∨+� ≡ ;∨;∧+� ������@�5���#�����

� ������)�������&����* ������$�%��"�"����"����"�� ��

Exercice 19 — Les cinq dernières minutes !

��!��$�%����5������!�$$��=�8��� ������ ��2����������-���;3���� ������8��.��$���&��&��.���������@��

������� ��!��� �� �@��� ������ �� $����" ��� ��� ��$#��!�� #�� ��� ����������� .��$5���� ���.�T �8���#�!����

(��������"!%������!������..�!�����&�J��"������� �=��������������#�!��'���!�������$���������#��������-

��������- @����*����!� �'���>��*���������2�#�����2�**����'

�2�2������- &����*������������!� �������>��*��������!��'

�3�3�����- ����������!��(����������*��*%�����������������!� �'�'

������&�� ������!�#�� �����#�!����"&����#�����!��N��!�����'

:��������.��$����!�����#��������/�������$����������"�2���3'3������$5����.��$�������)�������.����5��*

;�����#�����=!����&�������"������,�����..������!����!��#�5�����=�8�����8�����5���� �����'

�'(����+�,+-�.+����8����H������ ��5���� ������������������=!��#�U������!��#�5��������8�����!��!���

���/#��������"$���������#��$��#������!����#������������$�'

Exercice 20 — Déduction à l’aide de la méthode des tables de vérités

:��/�$��"&������$������N�$���"������!�� ��������-

2�������-�����(�������#�������*�!�*��������������6��'���A

;���- ��#������*���*%�!������3��'��*(�"�������������6��'��(�������(����"�����������������!���� ��

����������(�"����������6��'��'

2�������8��%�����"���������������������������������������6��'���A

;����8� +���!���"� %� ���������(�!���� �� ���!����#���� ������"����������� �� �� ���!���� ��%�������"��

������ ��

:�&��;������)��������$����$�����/*;������� ���"����#���������!%�&��#��#�������#�����.��$�������&��"��

�����������#����$��%��������5����� �����&����������#��������#��������.�����8����$5�����.��$����'

�'(����+�,+-�.+����'��*��!�*�'���������� ������!������*����)����� ��������)����� ���*%���

Page 9: Exercices de logique

������������ ���������������������������

�������������������������E�

CP : Mise sous forme normale

!����� ����" ���

Exercice 21 — Equivalence logique et formules de transformations

(�����,����&�� ����!����� ��������##��&�������.��$�����������.��$�������������&�����#��#��������-

�� �;∨+ ≡ ;∧+�∨�;5� ;∧+ ≡ ;∧�;∨+�

Exercice 22 — Vérification de la validité des formules par transformations

������������������������$#��.�!�����#���&�� ����!�����&�� �����!����"$�����,&��-

�� ;∧;�+����;∧+ ��������&��$����&�� �������'

5� ;�+��;�∧�; ���!�������!�����'

* ���� ����$�%��"�"��"�"��� ����

Exercice 23 — Formes normales conjonctives et disjonctives

��(���������.��$����$���!��N��!�� �"#������N��!�� ���.��$������ ����- ��≡;∧+�⇔�;�+�

�'(����.�!����≡�;∨+�∧�+∨;�S�5����������������

��(�����,"�����$��������!%��/����.��$�!��N��!�� ������N��!�� �"&��!��.��$�������� ������-

�� �5≡;�+�∨+� �

5� �;�+�∨;��+�

!� ;�+�∧;� ���;∧+��;∧ ��

Exercice 24 — Tautologies d'après A. Aho & J. Ullman, Concepts fondamentaux de l'informatique, Dunod

��!%��!%���=$��������.��$������� ���� ����.��$����$���"#��!������ !���/#��������������� �����������"���

!�������!���������$#��$������.��$���������.����5���'

��;∧+∧ �;∨+

��;�+�∧+� ���;� �

0�;�+��;

?�;⇔+∨ ����+�;∨ �

�'(����������������-�"�'

Exercice 25 — Equivalence logique (examen 1997-98 ; session Septembre)

:���!%�!�����!��#�����.��$������� �����"������/.��$��������)���������&��$����&�� �������*

�� �∧2�3 ��3�∨2�3�

�� �∨2�3 ��3�∨2�3�

0� � ��2���

�'(������&�� ����!�#������!�����0S ���#�� �,���� ����!�����)�/�$#��#�����!����

Page 10: Exercices de logique

������������ ���������������������������

�������������������������V�

Exercice 26 — Un peu d'autocontrôle : QCM (contrôle continu 1998-1999)

�#����,"�������������$��%����� ����!%��/��5����� �������.��$�����8�&�� ����!��"��/&���������� �����-

��+��#���)����������.��$�����3�⇔�∨3⇔2�

�'(����- ����������&�� ������.����5�� �!�������!�����

�����.��$������� ���������)���������&��$����&�� �������-

��2⇔3∨:� �� �∧2⇔:∧3∧�

�'(����- ��&�� ������� �����&�� �������

* ���� ����$#� &�����

Exercice 27 — Système complet de connecteurs (contrôle continu 2001-2002 ; 10’ environ)

��!%���&��W�"∧"∨X ��� �� �H���$� !�$#��� �� !����!����" ���� �, ��� ��������� �8�&�� ����!� &�� ��$������� &��

�8����$5����!����!�����W�"�X�����������!�$#���'3�$$������� ������#�������������������������H���$��

.��$���$���������������&�����#��#�������"!��H���$�����#��#���#����K����Y�!,'

��,+-�.+����������������������&�� ����!����!%��!%��������!����!�����Z

Exercice 28 — Complétude et connecteurs logiques (examen 1997-1998 ; session de Septembre)

������&��"�����$�4!�$#������4#����� J����� ������!!�#�������'��#��������!���!���������!�#�!����@���H���$�

.��$��=��$������ ��������� !����&���!������&������������ �����&��� ����� ��.��� �%����$��@��!�$#��������

F[���"#���/�$#���' ��#��������$��� ��� ��=!���!��������� ��..�!���� �������%$�&�� ��� #��5��$��� ��!���5�����'

�����"�� ���������/#�����������&������������������!����������#��5��$��#�-�/(��."!@���=����.������#�����

���#��5��$��&���@����������������&�@� �!����$#��/#��������=����$��������#��5��$�':���!���/��!�!�"

���������������������=���������$��!!�#��������!����$�"&��!��!�����������$5�����!����!���������&���'

�� ����$5�� �� !����!����� ��� �� �..�� ��� !�$#��� �� �� �����$��� �� ����� �/#������� ����&�� #��� �@�/#��$��

���&��$���=�@������!���#��������'�����"����� ��� ���!����&���@����$5��W∧"∨"�"�"⇔X!������������

�H���$�!�$#�����!����!�����#���������&�����#��#��������';���$������&�@������$5����!����!���������&���

���!�$#���"��.���������..����$������&�@��#����/#��$�����!����!������@��������H���$�!�$#�������!���� ��

����$5��';��������W∧"∨"�"�"⇔X"��$����������&��W∧"∨"�X!�����������H���$�!�$#����� �������������

�@�&�� ����!����� �����-

;�+ ≡ �;∨+

;⇔+ ≡ �;∨+�∧;∨�+�

��1�!���������!��@�#�������6�6:616)�������↑��.���!�$$���������������!��N��!����-

;↑+ ≡ �;∧+�

(�����, &�� �@����$5�� W ↑ X ������ = !� ���� �#������� !�������� �� �H���$� !�$#���' 3�� �#������� ��� ��

#��$�����$#�����!�����.��$���&���������!�����&��"#���&�@��#��$��=�����������#���������@����$5�����

.��!���������&�����!�������=��$�����\� �����!��!������������������'

��,+-�.+���(������&�8���H���$���!����!����������H���$�!�$#����� ����=$������&������!����!����

&���!��&��#��������!����������.��$��8���!�$5���������!����!��������H���$�'''������8�� ����T

� � 1� !�������� $��������� �@�#������� 61 616)1�� ���� ↓ �� ��.��� !�$$� �� �������� �� �� ���N��!����'

(�����,&���@����$5��W↓X!�������������������H���$�!�$#�����!����!�����'

Page 11: Exercices de logique

������������ ���������������������������

��������������������������9�

Fonctions booléennes

!����� ����" ���

Exercice 29 — Calcul en binaire d'après A. Aho & J. Ullman, Concepts fondamentaux de l'informatique, Dunod

:������,�����5�����]������%�������,����/#������������&���!�����#��������/!����� ����-

���@�/#�����������!������������������$��;"+" ���'������� �������&��$�������"���/�������#��$�!��

���$������ ����'

���@�/#�������� ��� !��������� ������ ���$��;"+" �� �'���� ��� ���� ���&��$��� �� �� #��� ���/ #��$� !��

���$������ ����'

0��@�/#�����������!������������������$��;"+" ���'������� �������&��$�����;+ �" ��!�$$�����$5��

5������"���� ���������!��$�����.�������=�9'

�&���%��0����1$�%��"�"��"�"��� ����

Exercice 30 — Tableaux de Karnaugh (année 1998-1999 ; Examen de Septembre ; 30' environ)

1�!����������.��$�������&������ ����"��������&�����#��#��������-

�≡�∨;∧+��∧;�+��∨� �+∨���

��:����������5������]������%����.��$����'������������.��$����$������N��!�� ���$#��.������'

��:��������.��$����$���!��N��!�� �����'

0���8��������5������]������%����"���������.��$����$�������!�$$����N��!�����������!��N��!�����'

�'(������≡;∧+�∨�;∧��∨�+∧ ∧���S��.�!�����8�5�����#��������5�����=#���������.�����S��≡;∧�+∧��∨�+∧� ∧���∨�;∧+∧���

Exercice 31 — Karnaugh et fnc D’après A. Aho & J. Ullman, Concepts fondamentaux de l'informatique, Dunod

1�!�����������/.��$������������&�����#��#��������������"!�������������������$��;"+�� "�����������

����5���� �����-

; + �� ��

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

�� �� #������ �� !�� ��5��� �� �����" �/#��$�, !�� .��$���� ���� �� .��$� �@��� .��$� ���$��� !��N��!�� � ��

���N��!�� �';�����$#��.��,)��=�@�������.��$�����@�&�� ����!��'

�� ����� �,!��������������##��&������$��%��������5����/��]������%'

�'(����.������≡;∨�+∧ �S��≡�;∧� �∨�;∧�+�

Page 12: Exercices de logique

������������ ���������������������������

����������������������������

Exercice 32 — C’est votre dernier mot, Jean-Pierre ? (contrôle continu 2001-2002 ; environ 10’)

����&�8�� ��� ��$������$����� ����.��$� ���$��� ���.��$���" ���/$��%���� ���� �� ������5���-�8�##��!�����

����!�� ��� .��$���� �8�&�� ����!�" �� �� $��%��� ��� ��5����/ �� ]������%' ��� ��� ��� !��" �8�##��!����� �8���

$��%������� �����#��.��������$���#�����#���&���8�����"!�&��#��� �8� ����!��!���������!����A���� ��$#�

��$���Z �����"�����,) ���.������5��!%��/������!����� ����*

��(���������.����.��$������ ����- ��∨2∨�3�∧�∨�2∨�3�∧��∨�2∨3�

��(���������.�!��.��$������ ����- ��∧�3�∨��∧�2�∨�2∧�3�∨�∧2∧3�

0�+�����$��%�������������, ���#���$���������.�!��.��$������ ����-��∧�:�∨��∧�2�∨�2∧�3�

Exercice 33 — Tableaux de Karnaugh (contrôle continu 1998-1999)

��1�!�����������.��!����5������������#��������� ����5�������&���;"+" ���'3����.��!���������.����

#������5����� �������� ����-

; + � ��

� � � � � �':����,��.��$����$������N��!�� �!�����#������=��-

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

� � � � � 5':����,��.��$����$���!��N��!��5�!�����#������=��-

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

��1�!����������.��$������ ����- 3∨�∧2���⇔3�∨2

(�������.��$������ ����������.��$����$�����#�����$#��#����5��'

"�"�����#� # ���� ��$�%��"�"��������1���

Exercice 34 — savez-vous diviser à la mode de chez nous ? (Contrôle continu 2002-2003)

:��� !�� �/��!�!�" �� ��#������� ��� ��$5��� ������� �� 5������ 5��� ��' ;��� !���" �� ������� &����� ����5���

5��������� "̂_" ̀���!�����#������=���5���#������!��������!�����������;���/�$#��"����$5��aDb�9�8�!���

��5������a9���b���������#�������#����� ����5��� ̂RF"_RV" ̀RV"�RV'

:����,�8�/#�����������.��!����5��������&����� ����������$5����#�������#�� "̂_" ̀�������� ���5��#��?��

#��C'1��������"��!%��/"!����.��$�������.��$����$���!��N��!�� �������.��$����$������N��!�� �'

Exercice 35 — Les soeurs ennemies

:������$J$�.�$����"3���������#���������3����$��������!�$$������"��#%����������!�������"�����������

��!����������������������!��:���F��$��������F����������'�����������#������@�#������@���#������#����

#��5��$���������������� ��.�$����" �@������&�� !���������� ������� ���������������� ���������$��� �����5���

����� ������ �� $J$� 5���' ���� �8�5���" �� ���!����� �� ������ ���#�!�� �$��� �� ���!%� �� �� ������ �����

��������������$�������=���!�� ���������#���&�8���$���'(�����#���"��.������!��������������.���������$��

Page 13: Exercices de logique

������������ ���������������������������

����������������������������

3%���! c 2�H��� = �� #��!%���� ���!���� #�������������" F��$���� �� ������ �� #�� ��� �@�$#J!%�� �� �� !��#�� ��

!%��������@�5���!��� ����� ����������!%�'��8�##���"���8�5���!��8����������F��$����"��#%����3�����

������� ���� 5���&��$�������#�!�����#�!�������)���������&��$��������"= !� �� ���.�$�����" �� ��$5���� ��

!�%�����&���8���#��������##����!��������$�N�����d#��������>�!������'

6���!%���!�$$��� ����������.��������&��!�������������#�����#������������!��#��5��"�����#��������!�������

�@����$�����=������&��-�����������������5���������/#����������������&�����#��#��������&����� ��������&��

�����������#�����!������&����#����!����#��5��$�'

!2��.+����������������$��%��������5����/��]������%"�������@�/#��������������.��$����$������N��!�� �

��#�����$#��#����5��'

Exercice 36 — Quelques mises sous forme normal plus complexes (contrôle continu 2000-2001 ; 15’)

+������.��$�����!�$#��/�.��"��#����������������!�������#��������������!��!���'''��$J$�&�8������������

#�����������!%��/����$��%�����$����#���5��#������� ��=���.���':����,"#����$��%����� ����!%��/"���

.��$�����$����!��N��!�� ������N��!�� ����#�����$#���#����5������.��$������ ����

��� ∧;∨+�⇔P;⊕+�∨ Q

�� �∧ ∧;⇔��∧ ���+�;∨��

Page 14: Exercices de logique

������������ ���������������������������

��������������������������0�

Déduction en LP

!����� ����" ���

Exercice 37 — Tables de vérité

(�����,"#����$��%��������5����� �����"&��-

�� ;⇔+ �$#��&������&��$��� ;�+

�� ;⇔�+ �@�$#��&��#������&��$��� ;�+

Exercice 38 — Tables de vérité et résolution

����.��,"����������������5����� �����#�����$��%���������������"�� ������������������$������� ����-

�� ;�+*

eRR +�;

5� �∨3��2*

eRR �∨2!� ���2"�3��

*

eRR 2�3

Exercice 39 — Un peu de recul sur le cours…

�3+��#���)���������8����!�!�)�������*

.�-����,���*�� �� ��������(���� ����"����*��������������'�����!�����*�!������� ���B

� ��� � .��/ � !�����#�������.5.

�3 1�!�����������.��$���$�������.��$�!������������&��������##��&����$��%���������������'+��#���)

�����������.��$����������� �-

�� =��������������� �������������&��V�

5� =��!����� ���∅�

� ��.��$������!�������!����� � ��.��$������ �����

� ��.��$������������.����5�� � ����#�����������

����"�� �$�%��"�"��"�"��� ����

Exercice 40 — Quelques déductions plus complexes

����.��," �� ��������� �� ��!����������� ��5��� �� ����� #�����$��%��� ������������"�� ������� �����������$����

��� ����-

�� ��2"��3"�2∨3�*

eRR :

�� �;��+∨ *

eRR �;�+��;∨ �

Exercice 41 — Raisonnements avec un grand nombre de propositions atomiques

�3 ���$#��H�����$��%���������������" ���.��,�� ������������������$������� ����-

�� ���2∨3"2��∧�3*

eRR 3�2

5� ���2"3���*

eRR ����3�2�

Page 15: Exercices de logique

������������ ���������������������������

��������������������������?�

!� ;� ∧�"�∨���+*

eRR �;∧+��� �� �∧;"+

*

eRR � ∧��∧;

�3 ����������!��!����������������$����������)��#�� ���5��*

�'(�������������$���� ������-5"!'

Exercice 42 — Un peu de réflexion avant de passer à l’action (contrôle continu 2001-2002 ; 10’)

�������������$��%���������������"���!�������� ������������������$������� ����'

4�+�����/��.� 4�+�����/��.�

��2∧3 �∨2�3

3⊕: 3⇔:

��:∨� �∨:��2

Exercice 43 — Une déduction avec « ou exclusif » (contrôle continu 2002-2003 ; 10’ maximum)

�������������$��%���������������"���!�������� �����������������$������ ���'

�⊕2"3�2∨�*

eR2∧3

Exercice 44 — Tautologie et méthode de résolution (examen 1997-98 ; session de Septembre)

(�����,&����.��$������ �������������������#��.4�+�$��%������..�������-;∧+�∨ ∨�+∧� �∨�;∧� �

����"�� �$#� &�������"����"�� �

Exercice 45 — Suicide alimentaire

���!�f�� ���&������ �"��5��N�������/�$�����.������$�����T3�$$�=�@�!!����$��"�����#������� �!��!��

��6�g�=���.��������#��������������'��� ���5����$$���&���&���!����%�����������������5����!���!���!�"

$����@�##�����@��5���!����.�����#��������#���.���'�����.�����#���"�� �.���������� �������������#����@��

������"�������4������ ��������4'����.������������������$������ ���-

�� $���� #�����*��� �� ���������%����

5� &��"����,���C�$��!���*�(�"������������%�!������������������������� ��!�������������*�

!� ��#������������,����C�$��!���*��

�� 3��!(�"��� ������� ���!��%���(�!1�����!����*��'����D

�$#���������#�����!������"$���������$J$���&����=�@���������������������!���$#������%������������$��

.���B����"�����@�������������� ��������������������$���-!� ������ ������$J$����#��������&����� ��#���

����'''(��%�������$���"���#��!���$���.�������$#����������������!����������&��'������,) ���!��������������

��.�������K�����������������$��%��������5����� ���������$��%���������������*

�'(���������������$������ �����'

Exercice 46 — Dès que le vent soufflera... (contrôle continu, 1998-1999)

1�!������������������$���!�)�������'

�� &1��������'�(�"�#��������

�� &�������������'���(��1�!����������

0� &���1�!����������(�"��� %����������

?� 4����������'������������������ ����*�%

3� ����#���� �������

Page 16: Exercices de logique

������������ ���������������������������

��������������������������C�

�'��������!���������$�������������&�����#��#��������

5'�������������$��%����� ����!%��/"������!���������$������ �����'

�'(���������������$������ �����'

Exercice 47 — Comment préparer ses examens (examen 1998-99 ; session de Septembre ; 20' environ)

f���)���������#��#���=�� ��������/�$�������#��$5��'����������!%�$5��"����.��!%����������������=���#���

�������������������$������ ���-

M��&���������'��*����(� �����"� �������#���������������"���� #��E�'

M���6��#�������'��*����'

M0�>����*�!�*��F�"�#�������#��������'������#���E�'

3�3��!(� ���!�������(�!����'����<�(����"���� #��E�(�"�#�������#������

����������,��������%H#��%��������!��!����������.��$���.��$��������&���'

������������$�����f���)����������)�� �����*f����.��,����#����#�������$��%������..�������'

�'(���������������$��������� �����'

Exercice 48 — Le retour de Ménardeau

3������$����"�@���#�!����(������������������..������ ����!������#��K���=�@�'2'�'�#���� �������������

�@����$5�������$����"�@���#�!����.�������������$������ ���-

&�������1�� �����!�����������������*�#��(�!1��������������#�����������������������&�������1��� ��

��#���(��������������1�� �����!������!���������2�������������������!������� � ���������&����!����������� � �

�����(����������������#���������������������@������,(������!1���'����<�8����������#����

3�� ���!� �� �� !��#�5����� �� ;���" (�������� �@�##�J�� = ���J��� !� �������' �� ��������,) ��� .���� * �������, ��

$��%���������������#��� ���.��������#���������� ��������������������$���':�������!�����)�/�$#����!��

����������$������ �����'

�'(���������������$��������� �����'

Exercice 49 — Adieu veaux, vaches, cochons, couvées

�@����!������ � ���N���� ��� �� !����� �� �� !������!���� ����#�����' ��N�� 5��� ��� ��� �$5��������� #��� ���

��� ����$���� ���!���/=��.��� ��$������ �� ���!����� �� #��$���� �$#�����!� �� �� ��������� !�U� 5���������

�������#���������������.�!������#��/����!����'���7!%�$�����$$�����N=��#����=�������5���$��������"(��!��

;�!%����"N����(����������@����!������".�������������$������ ���-

�� 9��� �*��������#��%�*���,��!�������������� ����#���� �������� �������*��������*�� ��%�

�� ��������*1��� ��*��*�������������!�����"���)������ ��*!������������!����#����!��� ������(

0� 9����#����'�����*��#��%�*���,��!����� ������������

?� ���1�#���(���������#����2����� ��%������� ��*!�����

3� 3��!�������������������(����������*���������� ��!�*�������������!������

3���������$������)�� �����*�������,��#���!�#�������������#�����#�����=!����&�������'

�'(���������������$������ �����'�� ����8���� �,#��=��$J$�!��!������"������,) ������!&���8�/�!������

�� ���������!����������&�����#��#������������������$���'

Exercice 50 — Le convive encombrant (examen 1996-97, session de Juin)

��!%�.�@������������ ������#���������!� ���#��!%����$��� ���� ������5�����$��� ����#��$������������� ����

%�������'�������������H�"!������!����7�#�������U�������!�� � �"��!��������������������������������#�H�

��!���#��$�����������!���#��#�������$���&�������#�����'������.�!�����/"��!%�.��#����!������@��H���

���.�������������!������������.��$������� ��������� ����-

Page 17: Exercices de logique

������������ ���������������������������

��������������������������<�

�� &1���*������� ���(���������������� ��!����� �������

�� 6������������,�<��� ����� ��!�����'���

0� &1���*������� ���������������������� ��!�

?� 6��*������� �������� �������

C� &1��������� ��������� ����� ���(����������������'���

�#�����������.��/���"����������������!�����#��#������.�����������=�@�������"!��"��������

3� 6��*�������'������� ��!�

:����,�����#���������������&����!���������$�����$�����,#�������$��%������..�������&��!����)!����������'

�'(���������������$��������� �����'

Exercice 51 — Le sens de la vie (examen 1996-97, session de Septembre)

2������)M���H;%�����#%�/"�����#�������� ����@�������".�������������$������ ���-

�� &�����#�������������������������!��'����� ����������(����������#�����������

�� &�����#��!������� � ����������������1�� ���*��������������#�������'��,�!������

0� &�����#���#������������!���������� � �������������������#���������� ����'��*�

?� &�����#���1��� �����'��,�!����������������1��� ���������

C� P:�����$H�%������H#%�Q��'���>������������������#���������'��*�

<� &�����#������������������������'��,�!����������������1��� ���'���

3� -��!������!�*����(���� ��!��!��������#�������!��G ���'��H�

��:����,�����#���������������&����!���������$���'

��3���������$������)�� �����*f����.��,!������������##��&������#���!�#�������������'

0�;���)�������������&�������#��!������&���� �����5����*

�'(����5��62��.+��������������$��������� �����'

#�� %��$�%��"�"��

Exercice 52 — Le paradoxe de la carte de Jourdain (examen 1997-98 ; contrôle de Novembre)

����� ����� ������&�� �$������.���$������ �� #�����/� #��#���= ��������$������� ����!�������������" �����

&�@��� 5���� !���������!� ��������&�� #��$�� �� ���$����� !� �H#� �� !�������!����� ���� #��5��$�' ���� ������

��������!���#�����/�#��#���#�����#��$����.���#����$��%�$���!����������;'�'2f����������V�0'

:�����#��$�����$#�"���������������=��#�����/��&�� �����=!������f�������"��&���@��������$��%�$���!���

!����$#����� '�$���H��������-;������������*�!���#�":�����'1������� �������7��#��#��������/�H#��

�@���� ���� - ��� #���" &�� �� $������ N�$���" �� ��� #����" &�� $������ ���N����' ���� ���!�����, ������� ���/

����!%�����"�����1�������&���@������������ �5��3%��#�����2�'3��/)!� �����!���������#�!�� �$���-

��C�'�������� ��

2����������� �

� � 3���� ���!����� �)�)���� ���$��� #� � ��� ����" �� ���)���� #�����/��� * ;��� ��#����� = !���� �������������"

!%��!%�,��!�����/����!��#�� ���J��������.����5�����$������$������##��&������!!���� �$������$��%�������

��5����� �������������������'

� �����$�����������#�����/�����!������f�������'�����!A���@���!��������!���-

���4�� ������!����*��1����!E���*�!���!�������#����

+����������������"����!�� �����������..��$�����-

�2�4�� ������!����*��1����!E���*�!���!������������

��(�����,&��!�#�����/�����&�� �������#��!���������������������#���������������&��'

Page 18: Exercices de logique

������������ ���������������������������

��������������������������D�

#�� %��$#� &�����

Exercice 53 — Quand les juges sont pires que leurs accusés (contrôle continu 2002 - 2003 ; adapté deR. Smullyan, Quel est le titre de ce livre, Dunod).

:���!���/��!�!�"���������� �H������#�����!���;�!�.�&�� ���6�%��%�)�����"�87��#��#������&��$�����;���

&����$������N�$��������;����&��$���������N�����'��8������8��#��!��!��!���������/7����������;��.�����

f����6����"��#��!�����6�!��������K����&���������������������87�����!����-

�������������������!� �'�

��4���!!����������� ���!� �'����������*%�2��������'

��:����,�������!����������&�����#��#���������������������!�����#������=!����!���������'1�H�����������

.���&����#��!�����6�!��������K����#���J�����;������;���T

7�����J���N���=!�#��!��'�� ���!����!���������"J���) ���!�#�5����#�� ����=���!��!������&����=��

!��#�5�����������/�!!����*

� �����;��.������!��#�5�� � �����;��.����������!��� � ����#�����������������

� f����6�������!��#�5�� � f����6�����������!��� � ����#�����������������

-�(�����.���"&��#����,) ����������!�������#��!�����*

� !8�����;�� � !8�����;��� � ����#�����������������

Exercice 54 — Panique à Nagano Adapté de E. Busser & G. Cohen, La Recherche, 302(1997), p. 108

��#��������������&��"�����!���������N��H�!����������!������������ ����@�����5N�!�� ���&�@�������� �����5��

�������������"�.�����������&������#����.��@��#�H��@�5��������#����������������!�$#���#�������!�$#��������'''

��������!��!����&���#��#��������"��������N����.�!�����/�������@�/��#�������!�$$���������������#����.�#��

��� �..��$������&�� ���� ����A� �����" ����A�.������'��������" ;����!�� �� ���H� ��������� 5��� �� ��� �� ����� ����

&����.���� ���� �� ������� ����#� �� ��.�������H$#�&��' �H��� #��� �� �������� ���#��� �/���&����������&�� ���

#��#��������" �����.��� �##��= �� !�$#����!�� #�����$J���!���!%� ���/' ������, ������ ����� �� �����������

$��%����� ����!%��/*

������������!����������..��$��������� �������#�����N��H-

6�K���h- 41��*�������������#��#���������

1$��- ���������������(������������!���������D

;����- 9�=���?���*������#������

�#���$�����.��/���"���������������N������@�!�����4f�����&����.���T4'���!������������������@������)����*

�'(��������"����������$��������������8���#�� �����'

��3@�����������;����!������#��������$���������.�!���/N����'

6�K���h- 3�����(�#����1���� �����������

1$��- 9��1�!��:� ��(�9�=���?���*���"���������#������

;����- ��������� ������#���*#:�!�����7����D�-�����(�*%�*1�������(��������(�#���������D

3��H���6�K���h���#�����";����!����#������J��5������$��$������4������ ��'�!�� �����1�� �*4'��

#����!��!������&�������)�)��������!��.�����*

�'(��������"����������$�����;����!����� �����'

0���.��"���H��..�����!��������5���&��'

6�K���h- ���1����1��!����2�*���8�����#���*�������#�������

1$��- &��#��������������(�!1�����9�=���?�#����������D

;����- 7����*������#�������-������!��(�"�#�������!���(�#���������������

��#��������!��N��!����"���H������#�������.�!���N��H'������,) ������� ����!��!������&���@��#��������

��!��������..��$������*

Page 19: Exercices de logique

������������ ���������������������������

��������������������������E�

Exercice 55 — Lewis Caroll et les paradoxes de l'implication (examen 1997-98 ; session de Juin)

������.�����������#������������&�������&����!��N��!����"�����N��!�������@�&�� ����!���#�����!��#��5��$�=

4�@%���J��%�$$�4"���@�� �#����$J$�#����@�$#��!�����'�@�������@���!���;�H����(�� ������"&����#�&������

����&��"�@���#��!%����!�#��5��$�������������������&��&�@��� ���������&)�'���!�4�,�!"�EV<�':�$J$�"����

��� ����!� �� *�� ����������� �VE9" ��' 2���!%����" ����� 3������� ���� !� &�@�� �##���� 4��� #�����/�� ��

�@�$#��!�����$���������4-

+���� ��� �� ��������� #����� ����� ���#������� +���� ��� �� ��������� ������ ����� ���#������� >���

�� ��������������� ������������ �� ���������G#������������HF�!���� �� ��������#������� �� ����

��� ����� ��� �� ��������� G������ �� #����H�� >�� ���*�%�� ���#���'��� G!��� !� ����� *�� !������!�

��!���������!��!�(���!���*�����1�� ��������)�� ��*�4�,��H��1% ������ �������������1�� ��!�����

�!��!����*����������� �����������������(������� ����1�� ����������������/���0�2����������������*� ��

���*���� ����*1�� ��!������/*�������#��!�����0��41�� ��!���������������G����;H�����,���������*� ����!!��8�I7����������(���;����#���I������ ��������� �� �������������;������������������ ���

��,������ �������!���8��1�� ��!���������#�������* ��������������G�����������;H���* ����;

���#����G������������H������2� �������������#�2�!��������� ���*�%��(�������%��� ������#����

>��#������� ���*�%������#���*1�������2�����*��!���!�����!������� �����,�������!������� ���*�%�

�J� �� '��� ���� #�,���� ��������� *� �1�'�������� +�� ��� ��� %� �� �� ��'� �� *� 4K��� >������ 8

P��##�����&��QI;��� ����C�F������P�����&��Q���� ������;��� ��������CF�;����������*�*���A

P'''Q�4K���>������P���#������#������ ��������!�$$��Q��������������8����;��� ����C(��������� ����'�

��;��� ��������CF�*��!����� �����1�� ����'�(��� ������������%�

�� �� �����������$��%��� �� ���� !%��/ ������������ ��5��� �� �������"$�����,&���� !��!������" �� ���!��

��������$���"����Y��3����������������'

�� +��������4$������4������$������������3�����&��#���#��5��$�';���&���*

�� ������$���"&�����!��!������#���)�������������/%H#��%�������������*(������&��!����!��!���������5���

���!����&���!�����&����!��#��$�����'

Page 20: Exercices de logique

������������ ���������������������������

��������������������������V�

Logique des prédicats du premier ordre (LP1)

!����� ����" ���

Exercice 56 — Un peu de syntaxe

:��� �� ����&�� ��� #����!��� �� #��$��� �����" �� !�������� �� .��$��� 5��� .��$�� ��� ���� -

∀/∀H∃, ./�"�H",�����/"H�∨�,����

�!����7���"����!����.��$�������H$5����.��!��������������H$5������#����!��';��!�������������'

Exercice 57 — Un peu de syntaxe, suite et fin

1���#��!�����������&�����#����!�����#��$������������!��������-

#����!���@������ ���� #����!����@������

.��� .��!������@������ % .��!�����@������

1���##����&��4R4�������!!���!��@�!������#�����#����!���@����������'1�!�����������.��$������� �����-

�� ∃/∀H∃, /����∨∃H�∀,�%/",�"/������

5� ∀/�./�"H�����∃/./"H����!� ∀,�/"H����∃H∀/�./�RH���∨�H",���

��+����������"#��$�!��.��$����"!�����&������5���.��$���*

����$#��.��,)���.��$����5���.��$��������� ������#�����%�������������������������������#��������'

0�:����$���,����!!�����!�������������!!�����!����5����������.��$����5���.��$���'

?��������������8�!��������!��.��$��������!�������$�������.��$�#��#���'

Exercice 58 — Un traduction primaire

��������������&�����#����!��������������8����$5�����������������!���������$���'

+������������� �����

4��*� ������������ ���*�� ������

6��)���*��*� �������������������,���

3��!���� ���� ��������������������������,��

����"�� �����#�$�%��"�"��

Exercice 59 — Mourir de faim ou de la vache folle ? (contrôle continu 2000-2001 ; 10’)

��!%�.����" ���$5����� ��$�����".�� �� �#%�����"�� !����$$�����.���B��� #��� �8����� �� ����� �� ����������

�������!� #������ #������� �� �� ��5��' ������$��� ���������� #�� ��� �����!�� ����$����� �� $����� #��� � ���� ��

������������ &�� �� ��.��/���" !������� #������ �8�$#������� ����� �� ������� ����� !%���5��� �8��� !������ �!������

#��#��������������������#�������������"�.����#�� �������� �����������������.�5������!��$����$#���������

%����#������/��6�#��'����������#����=!��!�$#����$����#����������-����!����=��������"���!=������&��'

(���#���!���"��������������#�����5��&���������#�������5�������!�������������&�����#����!��������

�����#���$����=5���!�#�����$$����������'3�$$��B������!#��&���&������ ��/#����&���'

1���$�������������������!��������������&�����#����!��������������������!��!�)�������'1����������#���

!������#����!������ ����-3����,.���c�"(�����c�"2���.c�"�������c�"����!���c�'

�� �!��'������������������#!�*�����������������

�� &����'�����!��������*�����������������!�������������� �������L����

0� ��������� ��!�����!����������*��*�>��:��*���!�'�������#����!��������*�'���

Page 21: Exercices de logique

������������ ���������������������������

��������������������������9�

Exercice 60 — Le panda est un loup pour le bambou (année 1998-1999 ; adapté de l’examen deDécembre ; 15' environ)

�H$5�������3%������������"��#������������$������������$����$���������������#����#�!�������"!�&���8���

#��.��� #���.������ �� ���$���&�� �/���!����' �� �� ������� �� �..��&����$��� �/!���� �$��� ��.������� �� 5�$5��'

����������&��#�����5�$5��"��#�����8�##�����#��!�$$���5������������������$�����"$����� �����5��

!��$����!������8%�$�����"����������������#����'(���&�������!����������������#�� ��5�$5��'''

�����������;��������!��!�)�#�����������������C#����!������ ����-

)(����/"H���� ������/$����H'

)M��5� ���/���� ������/��������$��%��5� ���'

)�������/���� ������/����� ������'

)2�$5��/���� ������/�����5�$5��'

);����/���� ������/�����#����'

�' 4����'�#���������,�����*��#�,���%'

�' �!����'�#��������,������) �*�#�,����'

0' 6��)���*��#�,���%��������,��!����'�#��'

?' 4�� ��*��������*����'�#���������!�����������*��'��'��'

Exercice 61 — Casse-tête breton : emplois du temps rue de la Loi (contrôle continu 2001-2002 ; 10’)

3%�&�������=���������"��!����$$������8��#��������$��������������$���������������������#����5�����

.������� ���8�2�'���� ���� �� �..�� �������� #����$J$�&�������- !�$$��� ���� ��= !���� �� �$#��� �� ��$#�

��!%���&������$5�������������#���5��������.����������$5��������#���8���������Z �������������#��!%���

��$�����$����������������%����!"&���� ������������&���&��#�����!%����"�����..�!����� ����8������������

!���������'���..��"5���������������������!���������#����8��������� �!!������ ��5��������-5������ ���" ��

.��������$��������!�$#�����5�������������#��N�!����" ������ ����#��N�!�����#����������������������������

��##��� �� !���� ��� ����������' ;���&�� !%�&�� ����� �� ��� ������ �8����!%��� ��� !%� ��/ = ��� !��!�!��� ��

�$#�������$#���/#������������"= ���$����������8�����#����$������������������!�������� �����Z

���������������!����� ��������������&�����#����!�������������'1����������#���!������#����!���r et r o/ 1"

vi déopr oj / 1" panne/ 1"amphi / 1" sal l e_t d/ 1" est _dans/ 2'

�� 7�����#���"����������� ��"!���*�����������*�+3'

5� 6����)��� ���*�#�*�� ��"!����������.�@��M�B'

!� +������#�*�� ��"!���������*����*���� ���'

�� &����)�����#�*�� ��"!������� ���(�!������������,���*����� ��'

�� 6����)�����*������� ��"!����*�������������*�+3'

Exercice 62 — Un peu de rangement (examen 1997-98 ; contrôle de Novembre)

:��/%�������$����'����#��.�������!�.������#�������5�����@�#���)$���"2�������f�$����� ������.����.����

���� ����������!����������&��'�#����9%�������!�$5���%�$���&���!�������$����������#��H!�#���&����

#��. ������5�� !%�&�� ��$����" �� !%�$5�� ��� �� ��� !�#%����i$':���&�@�� �.������ ���������� � ��� �@����� ��

!��!%��T;��!������ �!$��%���"2�������f�$���������!�-

��+��������������!���������*��������

���!��*��!���������!�������*1�#�� �

0�3�����1��*��!������(�����1)�����*���#�� ��

?�&1����1)��� ���*1�#�� ��*�������!������(�!1����1���������*����*����������

C�&��������#�*��������*������������(�������!������*��� ���)����#��*1�#�� ��

���������������!�� ��� ���� ��������� ��� #����!��� �� #��$��������'1� ��������� ? #����!��� ������� ��������=

�@������.�!���������5N�����!��������!������!��#���/�$#��" Feui l l e( x) �#��������.�!�����-/������.�������"

����#����!��Dans( x, y) ������������$�����/�������H'

Page 22: Exercices de logique

������������ ���������������������������

����������������������������

Exercice 63 — La réussite au bout du chagrin (adapté de l’examen 1999-2000 ; contrôle de Septembre)

d&�����!������ ��*� ���L��������"�*��������2����>"!%������ �����"&��� ����##���$$�����$��=�� �H����

.����!%�&��$����d��!��,���>'����� ���&�����H���$����!���.�##�������� ���=������=������*�=����������

!�$$� ��� !����� �8�5���!�� ���� ��.������� ��� � ��� ���� �8�5����� ��� ��#�A$��' �� ��$����� $��%�������$���

�8���#����������8��������!���/��!�!�'''

����������#����!��5������ /"H������8�����#�����������/�������H�����&����� ����5��������!�����������������=

����!%��/#��������������;��������!����� ����-

�' �������������� �������3-$N���������#�����������'

�' 9���� ���'���������3-$N���������!����2�����'�!'

0' 6��)�������������������'�!��������!������2���� �����*�!��*��'

?' &������������O�����������!�!(�!�����������*�"2��'�������3-$N'

Exercice 64 — Génétique logique (année 1998-1999 ; examen de Septembre ; 30' environ)

�������4H��/5����4���)��#����@��#�!�%�$������!���!������!����.����$������@��#������ ��������&��'����=

���&�������&��#���������#�������������������!���!����������� �����..��$������!�)�������'

�� 4���������*�*%� �������%�)%�'����������!��������)%�'���

5� 4������������������)%�'��(������ �� ����������������*%� �������������)%�'���

!� $��������*�*%� �������%�)%�'���� ���#�������)%�'�����'����

�� 4������� �����������)%�'���(���� ������������������������*����*%� �����������)%�'����

6��� ���� !����������� ���� !�� �/��!�!� �� ��#�������� �� ����&�� ��� #����!��� �� ��� ����� !%�!��� �� !��

�..��$������'1����������#���!������#����!������ ����-

)���)��.���)��/"H",���� ������������$�����/����8��.�����H����,'

)_��/L5����/���_��/L5����H����� �������#�!�� �$������/����H��/5������H���H��/5����'

:������������!��������&�����?����!��#��!������'

����"�� �����#�$##��"�� ��%��1����!���

Exercice 65 — Encore des mathématiques...

������������������&�����#����!�������..��$��������� �����"#���������������'�/#��$��!���������������������

�����'1��������������H$5����$��%�$���&���R"j��k"��#����!��������-����G�H�#����/#��$��&���� ����5�������

�������������&����#����!��5������≥'

��+�������������!�����*1�������

��+���������� ���!�������������*��!������*�*%������������

0�>����������������� ���!�������������*��!������*�*%������������

?��!��������1��� ���,���*���������������

����"�� �����#�$# ������#���� ��

Exercice 66 — Instruction civique...

:����,2����#������������������!����� ���������&�����#����!�����#��$��������-

�� 9�������������,�����������

5� 4������������������*�������'������,�%���*�����:�!�����������:��������8M�$$�����3���H�����<��U��DEV"����!��#��$����'

!� +�������������� ����������!���"��12�!��1�����������*�!�����!� �'�:�!�����������:��������8M�$$�����3���H�����<��U��DEV"����!��� �̂'

Page 23: Exercices de logique

������������ ���������������������������

����������������������������

�� 9����*�������� �������� ��� ���� ������(�P$J$������������Q ��#��� ������������������ ���'�� ��

�1��*�� '��!����'��� ���������:�!�����������:��������8M�$$�����3���H�����<��U��DEV"����!�� �̂'

Page 24: Exercices de logique

������������ ���������������������������

��������������������������0�

Calcul des prédicats du premier ordre

!����� ����" ���

Exercice 67 — Validité et domaine d'interprétation

1���#��!�����������&�����#����!�����#��$��������'1�!�����������#����!����@������-,����3����������

��!!���!���@�!�������������#�!�� �$���R��≠'���������.��$����-

�� /≠H∧H≠,∧,≠/5� /RH�∨/R,�∨/R��∨HR,�∨HR��∨,R��!� ∀�/≠H∧H≠,∧,≠/∧�R/∨�RH∨�R,���� ∃�/≠H∧H≠,∧,≠/∧�R/∨�RH∨�R,��

:����$���,�� ���������!��.��$���� �������"�����.����5�����" ��!��������!���������!��& �����#��������� ��� �����"

������#��������$�����@�����#�����������#�!��.�-

:�RW9X :�RW9"�X :0RW9"�"�X :?RW9"�"�"0X :CRΝ

:����������!��"�@�����#���������#���#����!��������$J$�- /RH ��� ������� /���� H���������/

/≠H ��� ������� /���� H�������..������

Exercice 68 — Transitivité et antisymétrie de la relation inférieure ou égale dans les entiers

1�!��������$���������������/.5.!�������� �����- φ�R∀/∀HP∃,;/",�∧;,"H���;/"H�Q

φ�R∀/∀HP;/"H�∧;H"/�⇔/RH�Q

:����$���,�� ������� ���������!��.��$����#����@�����#��������

�RW3RnS�#-;/� ������/≤HSR-�������X

:����"φ��8�����#����!�$$�-�����������%���������2�)������������#�*�������������������

��φ�!�$$�-!�������������������)�������*����!�����'�'

�����#����� ��$�%��"�"��

Exercice 69 — Logique et mathématique : de l'importance du domaine d'interprétation

1���������#������������������&�����#����!����������������%����$���� ���-��!�����*��������'��������

������'1�!��������#���!�����������#������������������$��������@����$5����������-3Rr'

�� �� ��������� ���&��$��� ��� ����5�� /" �� #����!�� ; �� ��� .��!���� ." ������ ��� .��$��� Φ ����

�@�����#�������� ���� �� !�����#���� �� �%����$� #��!����� !����.��$��� ���� ���! ����� ���� ���' ;��!���,

&������������������#����������#���.��#����!��;������.��!����.������'

5� ��.��$������!����'��������#��������������! ����#���������!�������� ����5��/'�� ������� �����

��#��� ����$���� �� ��$���� �@�����#��������: �����&�� ��� �����#��������� �# �� �. �� #����!�� ; �� ����

.��!����.';��� �����#��������"�����$���,�� ���������Φ#���������/�����#������������ �����-

��-W3RCS�#-;/���� ������ �/�b9S�.-./�R/�X

�0-W3RRS�#-;/���� ������/b9S�.-./�R/0X

�'(�������.��$������.�����#���������/�����#��������������0'

Page 25: Exercices de logique

������������ ���������������������������

��������������������������?�

Exercice 70 — Interprétation en LP1 (examen de 1997-98 ; session de Septembre)

:�������������!���������@���H$5�����#����!��������;���@���H$5�����#����!��5�������"��!�����������

���/.��$������� �����-

��� ∃/∀H∃,;/���/"H��∧;H�∧��H",��

��� ∃/∃,�,"/���/",���∀H�/"H��

1������������/�����#������������2��� �����-

�������$�������6S���������������@��������������;�����������$���������#���'

�5�����$������� S�/"H����������$�����HR/���;/����������$�����/�������$5�����������'

:�&������.��$������������������#������������2����)��������$������*

�'(����������5����������$����������'

Exercice 71 — Encore des mathématiques (examen de 1999-2000 ; session de Septembre)

C��&�������/#����!����8������������������#����!�������������'1�!��������������/.��$������� �����-

��� ∃/∀H /"H���/"H��

��� ∀/∃H /"H���/"H��

�� ��$���� �8�����#�������� ����8����$5�� ��� ������� �������� ��#�������������/=�'�8�����#�������� �� �����

���������8���������≤"!���������������������� ��������������� �������!����������.�����������������'

�' :�����"����!���������#��������"��� �������� ��������#�!�� �����.��$����������'

�'(���������RFS����RV'

�' ������������$J$�������#���������#��� ���"$���.�������$�����8�����#��������#���&��������/.��$����

������ �����'

Exercice 72 — Modèles et Interprétations (année 1998-1999 ; examen Décembre ; 30’ environ)

������#����!���8������������������#����!�������������'1�!���������������������#������������ �����-

��� ����$�����8�����#������������8����$5�����������������������;���������������.������������'

��� ����$�����8�����#������������8����$5������������������.�8��;���������������.������������'

�0� ����$�����8�����#�����������W∅"W�X"W5X"W�"5XX��;��������������8��!����������$5�����⊆'

�':��������.��$���&��#������ �����#�������������%������'

�':��������.��$���&��#������ �����#�������������%�����0'

0':��������.��$���&��#������ �����#��������0����%������'

��"1��"1���� �����$�%��"�"��

Exercice 73 — On est toujours le modèle de quelqu’un… (contrôle continu 2001-2002 ; 10’ environ)

1�!��������������/.��$����5���.��$��������;���� �����-

�� ∀/∃H;/�∧+/"H��� ∃/∀H;/�∧+/"H�

��:����,��$���������.��$�����#�����&�����.��$��������.�����'

5��� ����$���"�����,��$���������.��$�����#�����&�����.��$��������.�����'

Page 26: Exercices de logique

������������ ���������������������������

��������������������������C�

Exercice 74 — Gare au quanti-fi-eur ! (contrôle continu 2001-2002 ; 10’ environ)

1�!���������8����$5����.��$������������&�����#����!���������������� ���-

��∀/P;/��∃H+/"H�Q

��∃/P;/��∀H+/"H�Q

:����,��$���������.��$�����#�����&�����.��$��������.�����'

Exercice 75 — Modèle en LP1 (adaptation examen 1997-98 ; session de Septembre)

1���#��!�����������&�����#����!�����#��$��������'1�!��������"��������H$5���������������5�������������"

���/�H$5������.��!������������.���#�� �����!� ����� ����������#���������'1���.�������.��$������� �����-

��-∀/./�R�/��

��-∀/∀H./�R�H��

�0-∀/∃H./�R�H��

:�������$�����#���!%�!������.��$����-��∧���"��"���∧�0'

Exercice 76 — Modèle d'un système logique (examen 1996-97, session de Juin)

����A A A A ��������.5.��� �����-

��� ∀/∀H∀,;/"H�∧;H",��;/",��

���∀/;�"/�∧;/"2��

�0�∀/;/"./��

:����,��$�������AAAA'

�����#����� �$#� &�����

Exercice 77 — De quelques règles d’équivalence (exercice un peu plus théorique...)

:�$�����, �� ������� ��� .��$���� ��� ������� #������ �� �� ��.������� ��� �����#��������� ��� &�����.�!������

�/��������������� ������'

�� eRR∀/�/���/� �%����*�� �!����������

5� eRR∀/P�/�∧2/�Q⇔∀/�/�∧∀/2/� *�����'��#����*�∀����∧!� eRR∃/P�∧2/�Q⇔�∧∃/2/� *�����'��#����*�∃����∧�����������!���� ���%�� eRR∃/∀H /"H��∀H∃/ /"H� !�������#���� �������*�∃���∀�� eRR∃HP /"H�� /"/�Q

Page 27: Exercices de logique

������������ ���������������������������

��������������������������<�

Unification

!����� ����" ���

Exercice 78 — Unification : cas d’école

���� �," &���� �� �/����" �� ���.�!����� �� !%�!�� ��� ����$5��� �� !������ !�)�������' :����, �� ����� �� .5.

�������������@���.�!������#�������!��!������-

� F/".�"H�� F/"2� F/".�"�,���

5 ;�"�.�"5��"�� ;./"�,��"/".H"�5���

! F/"H� F./�"��

���*�"�� �$�%��"�"��

Exercice 79 — Quelques unifications trop tranquilles...

;���!%�&��!��"������������/.��$�������$�&����������.��5���������������!���!%���������.�!�����-

5 ./"�/"H�� .P�H",�"��%��"H�"%���Q

5 K/".�H��"./�� K%�",�".,�".%H",���

!� ;/"./�"�./�"/�� ;,"..���"�.��",��" ��

�� ;�"�.�"5��"�� ;./"�,��"/".H"�2���

�� ;/"./�"../��� ;..H��"H".H��

�'(�����.��$�������.��5���-5���'

Page 28: Exercices de logique

������������ ���������������������������

��������������������������D�

Résolution LP1

!����� ����" ���

Exercice 80 — Résolution : cas d’école

;��!����"���##��&������$��%���������������"���������$5�����!��������� ���������!�������!�����������'

�� �,� ���∨��� ����∨��H�

�� �+�� ;/"./� �;,"��∨+,�

0� ��� 62� ��/�∨�6/�

?� �;/�∨+./�� �+H�∨;.H��

��� ���� �$�%��"�"��

Exercice 81 — Quelques résolutions un peu plus complexes

;��!����"���##��&������$��%���������������"���������$5�����!��������� ���������!�������!�����������'

�� �;/�∨+�/�� �+/�∨;�/�� ;�� �;����������

�� ;�"H�∨;H"�� �+,�∨�,� � ��∨+�� ��/�

0� �M/�∨;/� �:H�∨�;H� M,�∨��,� :�� ���

Exercice 82 — Un petite résolution complète en LP1 ... sans Skolemisation

3�� �/��!�!� ��!������ ��� $��� ���� .��$� !������� �� .��$���� �� �� �;�' 6�� ������� �� ������ �� !���� %���

#�����$$�-�K���$��������"!���������.��$������������������!�����������!��'''

(�����,"=�@������#���!�#�������������"�� �����������������$������ ����������� ������@�$#��!������-

∀/;/��+/��"∀/+/�� /�� eR ∀/;/�� /��

Page 29: Exercices de logique

������������ ���������������������������

��������������������������E�

Clauses de Horn et Langage PROLOG

!����� ����" ���

Exercice 83 — Le retour d’Aristote

:���!���/��!�!�"��������������������H������$�����������!������ ���-

4��!���!��������*��!����

4��!����������*��!���*��

3��!����%����*��!���!�����������*��!���*��

1� ���!����.���)!� ���.����/#���$������$����� ���������!���������$���������������������#������;�����'

�� �&���!�����#����������%H#��%��������������$�����;�����*

�� �&���!�����#�������!��!��������!�$$��� ���.������������ �����������������$���*

�� (���������.��$���!������;�����"#��������,���!��������M���!�����#��������'

� ����.��,������� ���������!���������$������##��&������$��%���������������'

9� 3�$#���,!��������������� �!������������;������&�� ������'

�%��"�"��

Exercice 84 — Instruction civique européenne (examen 2001-2001 ; 10’)

�����&�����#�H�!�$$��8�������"�� �H��$�)�����"#�����!�$$���"���#�H��!������ ������!!�������������

���=���������������������������&�8��!���!�������#%����8����� �"��!�����#�����&��.���B������!%�������N�����

�5�����!����&�������'6���$����" ����� ��/ �!!������(������!%�" ����������������� ���8���������#��������#���

��#��� &���&��� ������ �8�� ��� ����� �� ��� �� ����!�' 1� !�������� �� #���� #�����$$� ;����� ���������� !����

���������-

f r ancai s( dupond ) .eur opeen( ger t ) .habi t e( ger t , Fr ance) .vot e( X) : - f r ancai s( X) .vot e( X) : - eur opeen( X) , habi t e( X, f r ance) .

�� :����,�������!����������&�����#����!�����������������&�������;�����-?- vot e( X) .

7� :����,�8����$5�� ��� !������ ��M��� !�����#������=�� �����!���� ������&�� ��� #����!��� �� �������� ��

#�����$$�������&�������'

-� :����,.�2.�������#������5������#���##��!���������$��%������������������!������$5����!��������

M���';���!%�&����������"�������������$5������$������������5������'

Exercice 85 — Do you speak clauses de Horn ? (examen 1997-98 ; session de Juin)

��� !������ �� M��� ��������� #�� ;����� �$#����� ��� !���������� ��� ��������5��� ��� �� �����!���� ����&�� ���

��������$����'���������������"!��!�����������������!�#������.�!���$��������.����5���'��#����!�����"�@�#�������

�� ������,&�� ���� ����������������� !�� �/��!�!� #��$������ �����.��$������� ���&����� ��� !������ #�����

#��5��$�'

1�!���������!��@����$5�����!��������� �����"�I;"+" ���������������.��$�������$�&���-

Page 30: Exercices de logique

������������ ���������������������������

��������������������������V�

�� ;∨+∨�

�� ;∨��0� +∨�

�� :���"#��$�!�������!������"���&������������#�����!��������M���'

��1��##����������,�*����@�#�������"�����P;→�;�Q"&��!�������=��$#��!�����������!�����;#���;�':�����������$5����!��������M����&�� �����=�@����$5��#��!����������������������$$����@����$5��

$���$����.��$�������$�&���'1�#��!������@����$5���������$$�����..�!����'

���!�������������..��$��������� ���������.��$���!������;�����

�� -��!���*�,� #(�"� ��*�������#����

�� &��"������!�#�)�,(�"� ��*�����������������#����

0� ;���!��������8�����)�����,� #���'���!������!������>� �*����*�*�����'����D

Page 31: Exercices de logique

������������ ���������������������������

�������������������������09�

Systèmes formels

!����� ����" ���

Exercice 86 — Un peu d'autocontrôle : QCM (contrôle continu 1998-1999)

��1�!�����������H���$�.��$���Ra�(�4(��(�Cb��.���!�$$�����-

�!�5�������RW�"5XS�������4R����$5�����$���!������!��5�������'

�/��$����- e��

�������@��.����!��C- ;� e� �;� � �!;����$��&���!��&�����4�

�; e� �;5

+����������.��$�������������%����$������ �!���#��������-

��5''''''�5 ��''''''�5''''''5 ��'''''�5''''''5�'''''�

l���c l���cl�#�c l���cl����cl���c

��1�!�����������H���$�.��$���Ra�(�4(��(�Cb��.���!�$$�����-

�!�5�������RW�"5XS�������4R����$5�����$���!������!��5�������'

�/��$����- e�� e�5

�������@��.����!��C- ;� e� �;5 � �!;����$��&���!��&�����4�

�; e� 5;�

;5 e� 5;�

5; e� �;5

�'�)�)��e��5�5* ���� ����

5'3�$5���H)�)�)������$�����������#������%����$�e��55*

�9!��@���#�����%����$�� �� �� �0 �?

�%��"�"��

Exercice 87 — Un premier système formel plus complexe (contrôle continu 2000-2001 ; 10’ environ)

1�!�����������H���$�.��$���Ra�(�4(��(�Cb��.���!�$$�����-

�!�5������ �RW�"$"�XS

������� 4R!%�7�����!���!�����&���!��&���!��������������'

�/��$��� �- e� ̂$� �I ̂��#����������!%�7��&���!��&��� ��������$��� ������'

�������@��.����!�� �� ;$+� e� ;$�+�+ � �!;"+" !%�7���&���!��&��������

Page 32: Exercices de logique

������������ ���������������������������

�������������������������0��

�� ;$+� e� ;�$+�;

�3�)�)��e��������������*

�33�$5���H)�)�)������$�����������#���e�����������*

Exercice 88 — Langage généré par un système formel (contrôle continu 2000-2001 ; 10’ environ)

1�!�����������H���$�.��$���RW�"�"�" X� �!�RW�"5"!X"����������!%�7�����!���!�����!����������������-

�/��$� �� e��

�������8��.����!� �� ; e�;!

�� ; e�5;

!2��.+���+����������.��$�������������%����$���#�������#���*

Exercice 89 — Arithmétique formelle Adapté de D. Hofstadter, Gödel, Escher, Bach, 2nde ed., Dunod (2000), p. 73-74

NP*�(�-�!��(�@�!�"�!���#��:������M�.�������"!������������ ������ ������������5��������� �� �����/ �����

����&��$��%�$���&����#�����������$�������8����������!�����.�!�����'��������8��������)�)��#��&������H���$��

.��$��� ���� ��� ��� #��!� �� !%��/ ���� ��� E99 #���� �� �8�� ����' :��� ��� #��$���� !%�#����� �� ��� �� ��"

M�.�������#�������#���������H���$��.��$���"�������H���$�:;�����&���������������� ����������!���/��!�!�'

1�#�����.����.��$����$���.��RW�"�"�" X!�$$�����-

�!�5������ �RW."�"kXS

������� 4R!%�7�����!���!�����&���!��&���!��������������'

�!%�$��8�/��$�� �- e� ̂.k� �I ̂��#����������!%�7��&���!��&���8�������dk>'

������@��.����!� � ̂._� ̀ e� ̂._� ̀^ � �! "̂_�� ̀!%�7���&���!��&����8��������

�����.��$������� ���������)���������%����$����.��-

��� QQ�QQQ,QQQQQQ

��� QQ�QQ,QQQ

��+����������.��$�������������%����$����.��'

��:����,�������������#����������.�� �����������%$���&��'

�'(���� � ��� ��� �� �%����$� !��������$��� = ���' ;��� �� �����" ����, ���! !�������� �8�� ���� �� :������

M�.�������=��5�5����%�&����� ���������'''

Page 33: Exercices de logique

������������ ���������������������������

�������������������������0��

Grammaires formelles

!����� ����" ���

Exercice 90 — Hiérarchie de Chomsky et notation BNF

��6��$3%�$�KH�������$#�$��&���@� ������������!%��!%�������������&��"�������$��&��5��

&�������� ��/���������$$�����.��$����������#���#�����!�!����#���.���������$���#�����"

���%����������������"��5���������� ����������.��$���!����������!���$'��"��#����&��"

!������ �������������$$�����������������%���)!����/����.�����#��3%�$�KH&������������=

�@��.��$���!���"���@���#�����������!����7����@����$5������%�����!%�������$$�������.�����#��

3%�$�KH'3���/��!�!� ���#��!���$���= �������$�$����'

1�!����������..����������$$�������.����� ����� �!�5������ ���$������RW�" 5X�� ���������

!�$$��/��$����H$5���������$����a�b-

�� <F> → <R><F> → a <R> b<R> → a<R> → b

2� <F> → a <R><R> → a<R> → b

3� <F> → <R><F> → a <R>a <R> → <F><R> → <R> b<R> → a<R> → b

�< :����,���H#�"������%�����!%����3%�$�KH"��!�����$$�����'

�< �/#��$�,������$$�����#��!�������&���������H#�%���)!����/������.��$�2�K��)6���26��'

Exercice 91 — Dérivation récursive

1�!��������������$$�����.��$������������!�)�������'3�����$$�����������.���������� �!�5���������$������

RW�"5X�����������!�$$��/��$����H$5���������$����a�b-

�� <S> → a <S><S> → b

2� <S> → a <S><S> → a <T><T> → b

��:����,���H#���!%�!���������$$�������� �����"��� �����%�����!%����3%�$�KH'

��:����,��.��$�������������������a�b#������=#��������8�/��$�#��!%�!���������$$�����'3��!������*

��:����,"#���!�����/���$$�����"�8��5�������� �����!�����#������=����&���!�-��5

Exercice 92 — Analyse descendante et ascendante

1�!�������������$$������� ����"��.��������� �!�5���������$������RW�X���8�/��$�a�b-

�� a�b → a <S> a

�� a�b → aa

��+���������H#���!�������$$����������%�����!%����3%�$�KH'

Page 34: Exercices de logique

������������ ���������������������������

�������������������������00�

��:����,��.��$�������������������a�b#������=#��������8�/��$�'

0�:������� ��!!������ ��� ����� #��!���� #�� �� ����H���� ���!������ ��$#�� � �! ������)������� �� ���� �����

���!%��"�������8����H��������&���!�����'

?�:���������!!��������������#��!����#��������H������!���������&��!������������!����"�������8����H��

������&���!����'

������� �$�%��"�"��

Exercice 93 — Hierarchie de Chomsky et pouvoir de génération

1�!�����������0���$$�������� �����"��.���������� �!�5��������RW�"5"!X� �!#����/��$�a�b'

�� <S> → <D> <SS>a <SS> → a <SACD>a <SS> → a <SACD>b <SS> → b <SB> <SA><SACD> → c <SA><SACD> → d <SA><SACD> → a <SACD><SA> → a<SA> → a <SA><SB> → b<SB> → b <SB><D> → a | b

2� <S> → <GA> <GQ> <GA><S> → <GB> <GA><GA> → a<GA> → a <GA><GB> → b<GB> → b <GB><GQ> → c | d

3� <S> → a <SA><S> → b <SB><SA> → a <SA><SA> → c <FA><SA> → d <FA><SB> → b <SB><SB> → a<SB> → a <FA><FA> → a<FA> → a <FA>

:� <S> → <D> <SS>a <SS> → a <SA> <SCD> <SA>b <SS> → b <SB> <SA>a <SA> → a<SA> → a<SA> → a <SA>b <SB> → b<SB> → b <SB><SCD> → c | d<D> → a | b

��:����,���H#���!%�!���������$$�������� �����"��� �����%�����!%����3%�$�KH'

��:����,��.��$������������#����!������a�b#��������#��!%�!���������$$�����'3��!������*+�����������

������ �, ������!���/�$#��*

�'(�����1������� ����!�!��#����!������8��!������������������������#��������$$��������H#����..������'

Page 35: Exercices de logique

������������ ���������������������������

�������������������������0?�

0�;���)��"���������$$����3�"!%������������<SB> → b <SB> #���������<SB> → b <FA> ����

!%������a�b*

Exercice 94 — Chips ou cacahouètes ? (année 1998-1999 ; examen de Décembre ; 30' environ)

��� ���$$����� #�� ���J��� ��������� ����!���������!� ���.��$�� #���" #�� �/�$#��"�� ���!��#���� �� !���!�����

���%����#%�&���' :� $J$�" �� #��� ��� �������� #��� ������� ��� $���.� ���#%�&���' 38��� �� !�� �� !���� #�����

���$$���������� �$�������.�!�����"��.��������� �!�5��������� ���-

�RW∈"∋"≡X

��5������������������ ����-

a�b →a:ba(�ba�b

a(�b →a(b

a(�b →a(ba �ba(b

a �b →a�ba�ba:b

a�b →∋a:b →∈a(b →≡

��:�����������/#����������..�����������������#�������$$����"�!!�$#��������������5�������� �����'

�� +�������.��$�������������/#������������������#�������$$����*

0 �#�2� ,+::+-+�� =+�:'4��-� ,� ;4�//�+4�3 � � &��� �H#� �� ���$$���� ��� ��� �� �H#������ �� 3%�$�KH�

�##�������!�������$$����*;���)�������������$J$��������#��������$$�����8���H#�#������ �*�����"

�����������������!�������$$����'

�'(����+�,+-�.+������������������#��!�������$$�������!�$#����8�/#���������#��������������#%�&��$���

�����������!�!�%������'''��������$5�� ���.�����!�������#��#���������%$���&��'

�����$�%��"�"��

Exercice 95 — Grammaire de parenthèsage adapté de Aho, Sethi & Ullman, Compilateurs, InterEditions

1�!�������������$$������� ����"!�������������� �!�5���������$������RW�SS�S"X���8�/��$�a�b'

( 1) <S> → ( <L> ) | a( 2) <L> → <L> , <S> | <S>

��:����������5����8����H�����0#%�������� �����-

�� G�(�H

5� G�(G�(�HH

!� G�(�GG�(�H(G�(�HHH

��:���������!!��������������!�����#������=�8����H�����8����!�5�#����������������!�������'

0�:���������!!��������������!�����#������=�8����H�����8����!�5�#���������������8����H�����!�������

� �!���� ��������!%���������)�������'

�'(�����;��5��$�����!���� ���=���!%��������������!��'

Exercice 96 — Un grammaire ambigüe d’après Aho, Sethi & Ullman, Compilateurs, InterEditions

1�!�������������$$������� ����"!�������������� �!�5���������$������RW�"5X���8�/��$�a�b'

( 1) <S> → a <L> b <S>( 2) <S> → b <L> a <S>( 3) <L> → ε

��(������&��!�������$$��������$5��i���!��������������/���� ���������!%����..�������#�����#%�����'�''

��!��������������5����8����H��!�����#������=!�����/���� ������'

Page 36: Exercices de logique

������������ ���������������������������

�������������������������0C�

Exercice 97 — La belle ferme le masque

1�!�������������$$������� ����"��������!����&���&���#%������H���/�&��$���!����!�������������.���B����-

( 1) <S> → <SUJ> <V> <COD>( 2) <S> → <SUJ> <Cl i t i que> <V>( 3) <SUJ> → <DET> <NC>( 4) <SUJ> → <DET> <ADJ> <NC>( 5) <COD> → <DET> <NC>( 6) <V> → f er me | masque( 7) <DET> → l e | l a( 8) <NC> → f er me | masque | bel l e( 9) <ADJ> → bel l e( 10) <Cl i t i que> → l a | l e

��+���������H#���!�������$$����������%�����!%����3%�$�KH*

��:����,�8��5���8����H��!�����#������=�8����!�d���'�������������>'3�������$$�������)�����$5��i�

*+������!��!�������#���)���������!��!��������.���B���*

0�������,�8��.����!���!�����$5���h��������������������������#��!�����"��!�������8����H�����8����!�"

#���������H��������#�!�� �$������!����������!����������&��!��/���������!����'3������H�����8���J����

=��#��$��������H������ ��'3��!������*

�'(������� ���$$���� ��� �$5��i� #���&�8�� � #� !��������� #��� �� $���� �� ����!� ���/ ��5��� �8����H��

��..������'�� !%��/�8��� ��������� �8����H�� #����!������#��$�� �� �� !����� ��&�8��� ����� ����H��$��� ��

������#��!�#��5��$���%���������������������-&�����&���8��5���8����H��!����� ������5��'''

��*����"�����������$�%��"�"��

Exercice 98 — Quelques grammaires trop tranquilles

1� ��$����" ���� !%�!��� ��� &�������� ��� �����" �@�!���� ��� ���$$���� #��$������ �� ������� ��� �/#��������

#��#����� �� #������ �� �!�5������ � R W �" 5" ! X #��� �� ������ �@��5�� �@����H�� �@��� �/#������� #����!������

!�����#�������' 1� !%��!%��� = !%�&�� .��� = �!���� ��� ���$$���� �� #��� ��� � #����5�� ���� �� %�����!%�� ��

3%�$�KH"��!%���&��#����@������@������$$���������� �"$����!����)!���� �%����&��$���!�U������� ���$����

��$#���!��!��'

���/#���������������������.��$�- �5�

�/#�������#����!������- �555

���/#���������������������.��$�- �5!��

�/#�������#����!������- �5!�5!

0��/#���������������������.��$�- ��5

#�/#�������#����!������- ����55

?��/#���������������������.��$�- ��5

;���)������ ��������$$����%���)!����/��&������������/#����������� �����-

C��/#���������������������.��$�- ��5

�!

�'(����������"���8���#��#����5���������������������������� �!������$$����%���)!����/��-!�����)!���

#�� ���#��d!�$#���>����#�� ������!�����������������������!%�7�����!���!�������$J$����������'

Exercice 99 — Le Becherelle de l'arithmétique d'après Aho & Ullman, Concepts fondamentaux de l'informatique, Dunod

1���#��#����@�!����������$$����&��#��$������������!�$#��������#����������������$5���������������

����������.��$���&���� ���������&��;�����'1���##����&����������#�� �������#������������..�������.�B���-

)�������@�����@����������������#���������!�$$�����- - 13

)����������������!�$���- - 13. 126

)��������������$���������!�$������/#�����������- 12. 43 E- 14 ����!��� - 23. 5 E+24

1��������N=������$$����#��$����������#����������������$5����������-

Page 37: Exercices de logique

������������ ���������������������������

�������������������������0<�

<chi f f r e> → 0 | 1 | 2 | . . . | 9

<ent i er > → <chi f f r e>

<ent i er > → <ent i er > <chi f f r e>

����#�������������$$����!�)������"�����,�����@�5���������$$����#��$����������#��������������������

.��$���!�$�������������'

��������,.�����$���!�������$$����#���#�� �����!�����@����$5�������#�������������������'

0�:����,�@��5���@����H��!�����#������������)12. 43 E- 17

Exercice 100 — Grammaire de la LP

1���##���������������!������!����������� ����.��$����5���.��$���.5.���������&�����#��#���������;�-

) ��� .��$���� ���$�&��� ���� ��� .5. ��#��������� #�� ��� ������ $�N��!��� �� ����� !%�7�� �� !���!�����

!�$$��B���#�����$�N��!����'

)���������.5.���;"�����- ��������.5.���;

��������.5.���;

)��;��+�������.5.���;�����- ;∧+������.5.���;;∨+������.5.���;

��:����,������$$����&��#��$��������!�������������.��$�������$�&��������;'

���������!�������$$����#�����!�����@����$5�������������������&�����#��#��������'

0�:�$J$�"������,) ���!���������������$$������������&�����#����!��������������;��*

#� &��������%��"�"��������1���

Exercice 101 — Grammaires et systèmes formels (contrôle continu 2001-2002 ; 10' environ)

1�!�����������H���$�.��$����"��.���!�$$���������� �!�5��������RW�"5"!X-

�/��$� �� e�5

�������8��.����!� �� ;e;! �� ;5e�;55

��3�$5�������$�����������#���)������ ��#����8�/#�����������'!'''!�*

7� +����������.��$�������������%����$������*

-�:�����������$$����%���)!����/��F��.��������� �!�5���������$������RW�"5"!X���8�/��$�a�b�����&��

����%����$������!�����#����������������F�������#��F'

Exercice 102 — Systèmes formels et grammaires formelles (contrôle continu 2000-2001 ; 10' environ)

3�$$� ���� �8� ��� ���� �� !����" �� �/���� ��� #��������� .���� ����� �H���$�� .��$��� �� ���$$����� .��$�����'

�8�/��!�!���� ��������8�!!��������� ���.���������/�$#��'

1�!�����������H���$�.��$���RW�"�"�" X� �!�RW�"5"!X"����������!%�7�����!���!�����!����������������-

�/��$� �� e��

�������8��.����!� �� ; e�;!

�� ; e�5;

��+����������.��$�������������%����$���#�������#���*

1�!������������������$$����.��$����FRW��"��"�";X� �!��RW�"5"!X�������������#����!������� �����-

a�b→�

a�b→a2b a�b→a3b

Page 38: Exercices de logique

������������ ���������������������������

�������������������������0D�

a2b→5a2b a3b→a3b!

a2b→a�b a3b→a�b

�� :����,��.��$���������������$�������F�'

���� ������������&��������#��!�������"#�� �,) ������������.��$�������#�����$#���������$$����F*

3����.��$�������������������������������26�.��$���2�!K��)6����'

�'(����+�,+-�.+������H���$�.��$���������$$����#������������$J$���/#��������N� ������������� ������

.��$����������';��������!�!������������8���#�����������������H���$�.��$��"�����#����5�������� �����

.��$���������$#��.����������$$����'

Exercice 103 — Jouons à l’interpréteur Prolog (contrôle continu 2001-2002 ; 20' environ)

1�!�������������$$������� ����"�������!�$#��.4>�(�4.+����/��.�����H���/����������;�����'����/��$�

���!��������#����!��������a#���b'3�������$$���������.��������� �!�5���������$������� �5��-��RW. S ( S) S, S:- S0 S1 Z 'S9 Sa Sb … Sz SA SB Z 'ZX

(1) <pr og> → <f ai t s>

(2) <f ai t s> → <pr ed> . (3) <f ai t s> → <pr ed> . <f ai t s>

(4) <pr ed> → <i d> ( <l t er m> ) (4) <pr ed> → <i d>

(6) <l t er m> → <l t er m> , <t er me> (5) <l t er m> → <t er me>

D� <i d> → a | b | … | z

(8) <t er me> → 0 | 1 | … | 9 | a | b | … | z | A | B | … | Z.

�� +���������H#���!�������$$�����������%�����!%����3%�$�KH�*

7� �#�������,!�������$$����������������2�!K��)6���26���8

1�!��������$�����������$���)#�����$$�;�����!���������8������.���- p( X, Y) .

-� 1����#����8��!�$#����������������!�������$$������� ������������������!�������':����,����!!���������

�����#��!�����#����!�$#��������������8����H����#�����$$�'

,� :����,�8��5���8����H��!�����#������=����#�������������!�#�����$$�'

�� +��� ������ ��� �� !�$#����$��� �� �8����H���� ��� ��� ��������� ���!�������' (���.��, �� ���$$���� #���

#��#�����������������#��5��$����!�����'

:� ���������;�����������#��!�������$$��������$�����/��������.����' �N����,=�����$$���������������

���!��������!��������=��$��������������!�������������;�����'

Exercice 104 — Grammaire et arithmétique (année 1998-1999 ; examen de Septembre ; 45' environ)

1� �� #��#��� �� ��.���� ��� ���$$���� &�� #��$���� �8��������� ��� �/#�������� &�� !�����#������ = �8�!������

�8�&������� ����%$���&���' ��� ���$�� ���� .������ #�� ��� ������� �" 5 �� !' ��� �#�������� ���� �8�������� �� ��

$����#��!�����'�����������$����#��!������8���#��.�����'���#�������#�����%���� �������� ��������������':��/

�/�$#������������&�����������-

�j5!��R�5��5�!�j�5R!��5�'

�� �!�5���������$������������!W�"5"!""�"j"RX'

��:�.����������)���$����/������������8������$$����#��$������ �8����������� �������&�������'+��������

�H#���!�������$$����*:����������5��������� ���������&�����������������/�$#��'

�� 1���������#���������������#�������#�����%������������-���������#�������#�����%����������������!������

���!�����$$��&��N��������A���8��.�!����������#������!�$$�!8�����!��������#��$�����&�������'

�!���������� �������$$����&��������!�$#����!����!�����������##��$�������'

Exercice 105 — Du bon usage du groupe nominal en français

����#������..������$��������F�� ������2�!%������"������������$$����.��$����!�$#������.���B���������

�O!%�&�@��!���������������.�)����������@���N�$���#�� ���=��������'����#����&����������$����������!�������

���$$�����&���������!�$#��������)���������#���/�$#��"���������&������!�$#�������������!�$��������

Page 39: Exercices de logique

������������ ���������������������������

�������������������������0E�

������ �!�����5��'''!�&����#�������������$J$��� ���$���#�#����@��Y������$��!%�������63�T�

������$���� �@�!!����= #�����&�@�� ��� �$#����5�� �� ��!���� !�$#����$����������� �������� #��M��� ���� ���

��$���'�����"����!���/��!�!�"������)��������������=��#%���$������������&������#��!��-������#���$������

.���B���' 3� #���� �/�$#�� ��..���= ��� ��������� ���� ���� !�$#��/������� �O!%� �� !%��!%��� ��������$���

����$���&������������'

�� #��$���� �##��/�$����� ���� ���������" �� ����#� ��$���� .���B��� #��� !�$#����� ���� �� ��$ #��#��" ���� ��

�����$��������� ��@����$"� ��������$�����!�����@��N�!��.�����#�����#���#���';���/�$#��-

��� �����

���'������ ����� �����*

���'������ �!��*

�������"�� ����#� ��$����#��������$��� !�$#������ �� !�$#��$��� �� ��$"&�� !�����#���.��$����$���= ��

����#���$����#��!����@���#��#�������*������������-

����� �*���� ����� �*����,���*�� �

���'������ �����*�*����,���*�� �� �������*����

���!����������$$�����������!�$#����!������#����$����/4$���$��/4�����/����5������������5���#���

!�$#��/����.���B���"�����,#���/�$#����/#��#�������������� ��- �1�����*����������#������!�� ��*

���� ����� �� *�'�� *� ������ *��� ��' ;��� ����� �/�$#��" �� !���������� ���&��$��� ��� !���������

�H���/�&������$��������� �����-

<NP> → Jean | Mar i e

<Nom> → soupe | v i ande | soupes | v i andes | pai n | pai ns

<Det > → l a | l e | l es | un | une | des

<Adj Avt > → bon | bonne | bons | bonnes

<Adj Pos> → f r oi d | f r oi de | f r oi ds | f r oi des

<Pr ep> → de

��:����,�@��5���@����H��!�����#������������#���$���� ���'������ �*����

0�1�������$�����������������#%���$�����@�!!���'� �!������$$����%���)!����/��"�����������!�������=

�!��������!����������H���/�&���������)!�����������#�������������������$5��';���/�$#��-

<Nom_f sg> → soupe | v i ande <Nom_f pl > → soupes | v i andes<Nom_msg> → pai n <Nom_mpl > → pai ns

��!������ ���$$���� �� ������ !�$#�� �� !��$���.�!������" �.�� �� �������� #%���$���� �@�!!��� ����� ��

��$5���������������#���$����'

1� !������� ��� !� #���� �/�$#��&�� !�����!������ ��� ���������� �� ��$5����#���$��� ���������5�� #��� ������� ���

�/�$#��� �����' 3�#������" !�������� ������ �%����&��� ��� $����� &�� ��� ������� ����)����#������ ������ &�� ��

.���B���#�� �����J���$���������#��������$$�����%���)!����/��!�#�!���������%����&��������������$5����

��������!��������'''������ ����=M����'�.����!������������������"����$5���/.��$����$��������#��#����

&��#��$����������!������!�������!��!�����������������&�� ���������/���$$�����%���)!����/��':��������!��"

�@���� ��� �@������������#����������� ��$5�� ���� ����� ��$�� !��!����' ;�� �/�$#��-Nom( m, sg) ��#�����������

!��������NC_msg'1� #���� ����� �� ���$$����� �@���.�!�������������� � ;��������� �!!��������� ����� #��

���.�!�������� ����5���!�����#��������/��$�"�����$����������N�!��.�'

?������������!���� ���.��$����$�"�����,������ ���� �������������$$����#��!������'

C��������$J$�#����5���@�$#�������!���������������� ����5��� �������������������!����������$$�����

%���)!����/��';���/�$#��-

aF66"F�bPFlR#�Q → '''''

������,) �����������!����#����5�����#����������!������!�����!��������#��#�������#��������$�����4����4

��4��4*

Page 40: Exercices de logique

������������ ���������������������������

�������������������������0V�

Expressions régulières

!����� ����" ���

Exercice 106 — Parenthèsage d'expressions d'après Aho & Ullman, Concepts fondamentaux de l'informatique, Dunod

���$�������#�����%�����������������������/#��������������������� �����-

�� �5�!��

�� �e5!�k��

0� ��e5�!e���

Exercice 107 — adapté de Aho & Ullman, Concepts fondamentaux de l'informatique, Dunod

1�!���������@�/#������������������� ����- �e�5�!e5!�

��:�!�� �,�����������.���#��!�����/#����������������'

��:����,���/�������/#������������������&����.���������/�!��$�����$J$��������'

�%��"�"��

Exercice 108 — d'après Aho & Ullman, Concepts fondamentaux de l'informatique, Dunod

�!�� �,����/#��������������������.���������������������� ����-

�������!%�7���������5������&������������������������������������#����';���/�$#��-555��5��������5

�����!%�7���!������������9�������#�����#����"!@���=�����H�������$5��#������'1�#����������&����

#�����#���@�����#�����!�$$���!��!�����������!%�7������$����������#�����#����"=�� ���������,��������

����!������#���������#�������&��$���#����,���'

0����������!%�7������"5��!������&���!���!�����������&����@�##���������#��=���#��������!����!��� ��'

Exercice 109 — d'après Aho & Ullman, Concepts fondamentaux de l'informatique, Dunod

:�!�� �,�������������.����#������/#��������������������� �����

�� ∅eε�� ε�0� �e5�k

?� �k5k�k

C� �k5�k5�k�k

<� εk

Exercice 110 — Expressions régulières et grammaires hors-contexte

1�� ���!����&��������$$�����%���)!����/�������#�� ���������������#��� �$#������&����� �/#��������

����������'3���/��!�!� �!��.��$��!�#�������&���&���#������/�$#���'�!%�&��.���"����$���������������

���$$����������������������������"����&��!����@� ���#����5��"�@�/#����������������!�����#������'

��1�!�����������������!�����������@����$5�����!%�7���&���!��&����������5'

��1�!�����������������!�����������!%�7������H#��� ������&���������!%�7��&���!��&�������5���

������������ ����'

0�1�!�����������������!�����������!%�7������H#���5

Page 41: Exercices de logique

������������ ���������������������������

�������������������������?9�

��� ������

G����� ��,����H

Page 42: Exercices de logique

������������ ���������������������������

�������������������������?��

LP1 — Mise sous forme clausale

Exercice 111 — Forme prenexe

(���������.��$�#����/����.��$������� �����

�� �∃/;/�∨∀/+/��∧ �∀/�/��

5� ��∃/;/�∨∀/+/��∧ �∀/�/���

!� ∀/;/�⇔∃/+/�

Exercice 112 — Formules closes

(���������.��$�!����������.5.��� �����-

�� ∀/∃H∀,P /"H",��∀�∃,��",�Q

5� ∀H∃/ /"H�⇔∀,∀/ ,"/�

!� ∀/∀HF;/"H��∃,;/",�∧;H",���

�� ∀/P;/�∧∀H∃��+�"H��∀, �"�"H��Q

�� ∀/∃HP H"/��∃� �"/�∧�∃� �"/�∧ �"H���Q�

Exercice 113 — Formules ouvertes

(���������.��$�!���������.5.��� ����-

∀/∃HP;/"�",��∃,�H","��Q

Page 43: Exercices de logique

������������ ���������������������������

�������������������������?��

Résolution LP1

Exercice 114 — Résolution et validité de formule

:�$�������� �����������!�������!��������.��$������ ����=�@��������$��%���������������-

∃/∀H ��/�⇔�H��∧∀/�/�

Exercice 115 — Résolution (examen 1997-98 ; contrôle de Novembre)

1�!����������������%H#��%������� �����-

M��∀/∀,∃H /"H",���,"/��

M��∀/∀H�/"H�Rb�./�".H���

M0�∀/∀H� /"H"/��

1�!��������$�����������������!��!���������� �����-

3��∃/��./�"./��3��∀/∃H��./�"H�30�∃H∀/��./�"H�

:����$����&�������������!����&���!������&������8����$5����������%H#��%����';���!%�!������!��!�������

&���8���#��!����&���!�����&�����%H#��%����"���� ����$��������%H#��%�����I��!��!���������.�����

Exercice 116 — Normalisation et résolution en LP1 (année 1998-1999 ; examen Décembre ; 30’ environ)

1�!�����������.��$������� �����-

��≡∀/∀H�/"H��∃/∃H2/"H�

��≡∃/∃H�/"H��2/"H��

��(���������.��$�!���������"������������������

��(���������.��$�!���������⇔2�

0�����������$��%���������������#���$������&����.��$������⇔������!�������!�����'

?�+��#���)��!��!����#������.��$����������*

Exercice 117 — Quelques raisonnements

(�������������������#���!�#�������������&�������������$������� �������� ������'

�� ∀/∃H ;/"H�

∀,∀� ;,"���+,��

∀� +��

5� ∀/ ;/��;../����

∀/ ;/�� ./���

∀/ /��;./���

!� ∃H∀/ ;/"H�

∀/∀H ;/"H��∀,+,��

∃, +,�

�� ∃/∀H ;/"H�∨;H"/��

Page 44: Exercices de logique

������������ ���������������������������

�������������������������?0�

∀, +,���,��

∀� ���+���

∀/ ;/"/��+/�∨ /��

∃/ �/�

�� ∀/ ;/��+�/���

∀/ +/��;�/���

;��

;����������

Exercice 118 — Ménardeau et Flipper le dauphin

:�$�����,�� ������������������$������� ����=�@������#���!�#�������������'

� +������������� �����

4��*� ������������ ���*�� ������

6��)���*��*� �������������������,���

3��!���� ���� ��������������������������,��

5 �����*���������������!%������������*���������,�������������!!�� �,����

>���������'���*����'��*����������������������!!�� �,����*� ������������, ���2����'��*�

�����*���1����������!����'��*����'��*�

6��)�*���#�����*��1��� ���� ��������'��*�

Exercice 119 — Un exemple d'indécidabilité en logique des prédicats du premier ordre

6���� ��� ���!����&��������&�����#����!�����#��$�����������������!���5��'6���������#��!���$����������

����!���/��!�!����/�$#��.��������@����!���5�����'

�##��&��,��#���!�#��������������������������$������ ���-

∀/;/��+./���"∀/+/��;./���";�� eR ∀/;/�

;���)�� !��!���� &�� �� ��������$��� ��� ����� * �� ���" ����H�, �� $������ &�� �� !��!������ �8��� #�� ���

!����&���!�����&�����%H#��%�������/%�5�����!�����)�/�$#��'

Exercice 120 — Art et logique (examen 1996-97, session de Septembre)

1�!��������������/��������$������� ����-

�� �����(�"1���#��1��� �������*1�� �����

6��%����*�� ���������������������*�������������

3��!�"1���#��1��� ��������*1�� �����*�������������

5� �����(�"1���#������ ��������*�>�:����

>�:������ ����*����'����������������

3��!�"1���#��1��� ��������*1�� �����*�������������

��3����������$���� ���#���������)��� ������*

��:����,�����#���������������&����!����������$������N����.��, ����#�����=��&�������#��!������#����

$��%����� ����!%��/'

Exercice 121 — Dès que le vent soufflera... (examen 1996-97, session de Juin)

F�5���� �� ��5������ ���� $�$5��� �� 36�� 3����� �����&�� �������)�������' ���� $�$5�� �� 36�� ���

���#���!%������������'��� ���#���!%�������$����� ����������������@��$���#����#����'F�5������$�����!�&��

��5�������@��$�#�����@��$�#������!�&����5��������$���H����!%����&����5��������$���#��F�5�����'

Page 45: Exercices de logique

������������ ���������������������������

�������������������������??�

����������!���..��$����������.��$�����&��'

��;���)�����������!���..��$������&�@��H���$�$5����36��&���������������� ���#���!%����*

Exercice 122 — De l'art de la contradiction (examen 1997-98 ; session de Juin)

1�!���������@����$5�����.��$������� �����-

�� ∀/∀H∀, P�/"H�∧�H",���F/"H�Q

�� ∀/∃H �H"/�

0� �P∀/∃H FH"/�Q

���������������#���!�#�������������"$�����,&��!������$5����!���������!�������!�����'

� � �� ���������� #��!������ $����� &�� !%�!��� ��� 0 .��$���� ��� ��!������� = �@��!��������!� �� �@����$5��'

(�����������&���@����$5�����!��������������=��������������.����5���������������$�����'�������

$J$�� �!��!��#�����.��$������0�'

Exercice 123 — Les chargés de la route (examen 1997-98; session de Septembre)

�������!��������.��$�����&�������������$����%�$�����������!���!�#����������&��'�����@�5���"����� ���

��� ������@�!!�������!��������&����$�������.��$�����&���@������!�������������������@�������#������ ���

����� ����"������!��'(����������"����������$���%�$�����!�����!��������������$#��!����&��"�������������#��

�/#��!�����"�����������������$�������&��������$�����!�%�����'�@�/�$#����� ���" ���������!����#%���$������

��#���������$����!H!�����" ��!������!��������#����'

2���&�����!��&��#�������@�&��#���������������������������$�N������ ���J��������!%�����&�����/����

��&�J���� �� �� #���!� N���!������4�� 5�.��!K �� ��� ��/ %��$����4" �!%��� �����&�� � ���N���� ��� � ��� ��

��!����=���#�������#��%�5��'�����$#���.���B������� ���#���)J����!������������������&��������@���������#��"

!������������&��'�@����!����7�5������#���!�#��"!����)!�#������..���..��$������!������&����!��!��������

��������$������ ���"=#��$���� ��!����!�"�@���#�����!����&���!�����&�����%H#��%����-

GMH &������*� �(��� %������,�,��(���������� ����

G�H &��������� ��!���(��� %�,�,������������*� ��������

G�H C�!���*������(�����1��� ������ ��!���(�,�,��*��� �#�

GRH C�!���*���������*�

6�����!%��!%�����#��=�� ����� �!%��������&������!��������7�������#��$����#��������@����!�0�T

����������!���������$��������������������&�����#����!�������������'

�����##��&������$��%���������������"$�����,&��!���������$����@���#�� �����'

��+������..��$�����"���.��$������������������$���!�)������"����#��$���������!��!����*+�����%H#��%���

!�$#����)�)�� �$#��!���$��� * ��������, ���� .��$� ����&�� !���� %H#��%��� �$#��!��� �� $�����, &�� ��

��������$�������..�!�� �$��� �����'

Exercice 124 — Un exemple d'indécidabilité en logique des prédicats du premier ordre

6��� ��������!����&��������&�����#����!�����#��$�����������������!���5��'6���������#��!���$����������

����!���/��!�!����/�$#��.��������@����!���5�����'

�##��&��,��#���!�#��������������������������$������ ���-

∀/;/��+./���"∀/+/��;./���";�� eR ∀/;/�

;���)�� !��!���� &�� �� ��������$��� ��� ����� * �� ���" ����H�, �� $������ &�� �� !��!������ �8��� #�� ���

!����&���!�����&�����%H#��%�������/%�5�����!�����)�/�$#��'