Logique combinatoire: structures

[ale252]

Bonjour,

Je suis en train de préparer des examens, et il y a une partie du cours de logique combinatoire que je n'ai pas compris.

Un exemple de question dit:

Quel des structures suivantes UA = (UA, IA) sont des models pour la formule:
F = z y x (P(x, y) P(z, y) P(x, z) ¬P(z, x))?

a) UA = N, IA(P) = {(m, n) | m, n N, m > n}.
b) UA = N, IA(P) = {(m + 1, m) | m N}.
c) UA = 2N (the set of all subsets of N), IA(P) = {(A, B) | A, B N, A B}.


Je n'ai pas compris ce que sont les structures et par conséquent je ne peux répondre à la question. Est-ce que quelqu'un peut m'aider ou m'orienter un peu?

Merci beaucoup
Salutations

[Robot]

Je pense que la réponse est dans ton cours. Je peux la deviner : pour a), l"'univers" dans lequel se promènent les variables est l'ensemble des entiers naturels, et la relation P(x,y) est interprétée comme x>y. On se demande alors si


est vraie.

[ale252]

Bonjour,

Merci pour la réponse. Après quelques recherches j'ai trouvé la réponse au problème dans mes notes, mais je ne les comprend pas vraiment.

Est-ce que quelqu'un comprend et peut me donner quelques explications?

Solution:

Pour prouver qu'une structure est un model pour F, nous devons trouver x,y,z Ua tel que (x,y);)Pa, (z,y);)Pa, (x,z);)Pa et (z,x);)(appartient pas) Pa

a.- C'est un model. Il faut prendre (x,y,z)=(1,3,2). Nous avons donc 1<3,2<3,1<2 et 2 <(pas plus petit) 1

b.- Ce n'est pas un model. Nous devons trouver x,y,z € N tel que:
1 x+1 = y
2 z+1 = y
3 x+1 = z
4 z+1 =(pas égale) x

Nous avons pour 1 et 3 z = y ce qui est en contradiction avec 2.

c. C'est un model. Prenons x={1}, y={1,2,3} et z={1,2}
Nous avons donc:
x y, z y, x z et z (non) x

[Robot]

a.- C'est un model. Il faut prendre (x,y,z)=(1,3,2). Nous avons donc 1<3,2<3,1<2 et 2 <(pas plus petit) 1

Je t'avais donné tout ce qu'il fallait dans ma réponse. Il suffisait de faire l'effort de la comprendre. Pour vérifier que la formule que je t'ai indiquée est vraie, il suffit effectivement de prendre x=1, y=3, z=2.

Mets-y un peu du tien ! Relis ton cours.

[Robot]

Je note d'ailleurs une maladresse du corrigé : il y est écrit "il faut prendre", alors qu'il conviendrait écrire "il suffit de prendre".

[ale252]

Lire le cours, je l'ai fait déjà quelques fois, mais j'ai un peu de mal. D'ailleurs j'ai lus également un certain nombre d'autres cours sur le net, mais...

Procédons par étapes. Je ne comprends déjà pas ce que m et n viennent faire ici. Ca commence mal je sais bien...

[ale252]

Je note d'ailleurs une maladresse du corrigé : il y est écrit "il faut prendre", alors qu'il conviendrait écrire "il suffit de prendre".

Ah oui, là c'est plutôt ma traduction de l'anglais qui pose problème...

[Robot]

Je ne comprends déjà pas ce que m et n viennent faire ici. Ca commence mal je sais bien...

Dans la notation {(m, n) | m, n N, m > n}, m et n sont des variables muettes : on peut les remplacer par ce qu'on veut, par exemple
{(x,y) | x,y N, x > y}
ou encore
{(chou, betterave) | chou, betterave N, chou > betterave}.
Ca désigne toujours l'ensemble des couples d'entiers dont le premier est strictement plus grand que le deuxième.

[ale252]

D'accord donc maintenant je comprend déjà nettement mieux.

Je suppose donc que savoir si une de ses structures est un model, veut dire savoir si ils remplissent toutes les conditions.

D'autres part, que veulent dire les (il existe du début), z y x?

[Robot]

Tu l'as écrit, z veut dire "il existe z".
Quel est le sens de ta question ? Elle me fait l'effet d'une mauvaise blague.

[Robot]

Lire le cours, je l'ai fait déjà quelques fois, mais j'ai un peu de mal. D'ailleurs j'ai lus également un certain nombre d'autres cours sur le net

Ce n'est pas une méthode de travail sérieuse. Il faut lire le cours de façon approfondie et le travailler pour bien le maîtriser. Tu as du mal, c'est normal, ça ne vient pas sans effort ! Ca ne sert à rien de papilloner sur le net en espérant trouver ailleurs un texte miracle qui te fera comprendre sans effort.

Sans compréhension suffisante du cours, il est illusoire d'essayer de faire les exercices qui l'accompagnent. La compréhension du cours et la résolution des exercices doivent aller de pair, on ne peut pas faire l'impasse sur la première.

[ale252]

Mais souvent me manque quelques petits détails comme ici et maintenant j'ai compris une bonne partie du cours, sans quoi j'ai passé des heures et ne rien avoir compris...