Forme normale disjonctive et

fatiboud

Bonjour à tous,
Pourriez-vous m'aider pour cet exercice.

Transformer en Forme Normale Disjonctive

~ ( ( p => q ) => r )

Faire sa Table de Vérité.
Passer de la FND à la FNDTD (Forme Normale totalement développée)

J'ai fait la table de vérité mais je bloque pour le FND et la FNDTD

serge burckel

Pour la FND, il suffit de décrire les cas où la fonction est vraie (T). Par exemple $p\implies q$ est vraie dans les cas suivants :
$$\lnot p\wedge \lnot q, \lnot p\wedge q, p\wedge q
$$ et sa FND est donc obtenue à partir de
$$(\lnot p\wedge \lnot q)\vee(\lnot p\wedge q)\vee(p\wedge q)
$$ qui se simplifie en $\lnot p\vee q$

PetitLutinMalicieux

FND : $(\lnot p\wedge \lnot r )\vee(q\wedge \lnot r )$

Pour la FNDTD, qu'il reste à déterminer, il faut que chaque expression dans ta chaîne de disjonctions contienne les 3 variables.
Donc tu vas introduire "vrai" dans chaque morceau qui ne contient pas une variable A et remplacer "vrai" par $A\vee\lnot A$ et développer.
Comme ici, tu as deux groupes, auxquels il manque une variable à chacun, tu devrais arriver à 4 groupes de 3 variables.

christophe c

non ((A=>B) => C) =
(A=>B) et (non C) =
( (non A) ou B ) et (non C) =
((non A) et (non C)) OU (B et (non C))



Rappels:
(U=>V) = ((non U) ou V)
[ non (U =>V) ]= [ U et (non V) ]

J'ai décidé de dire (U sans V) plutôt que U et (non V) pour le cas où on s'adresse au citoyen de la rue.

christophe c

Si tu veux une mnémotechnie:

[ (tu avances) => (je tire) ] = [(tu n'avances pas) ou (je tire) ] = [ non ( [tu avances] et [je ne tire pas] ) ]

En français, "n'avance pas ou je tire" = "halte ou je tire"

Auteur: Jean Coret (logicien, mort il y a quelques années d'un cancer des poumons)

Chaurien

Il faut deviner que ~ est synonyme de $\lnot$.
Il faut deviner que $T$ est l'initiale de Vrai. Le globish, c'est plus classe faut croire. L'esclave doit parler la langue du maître.
Quant à $\Rightarrow $ et $\rightarrow $ ça va sans doute de soi.
Après on bataillera avec les élèves pour distinguer $\rightarrow $ et $ \mapsto$.

Foys

Dommage que les notations inventées par Jan Lukasiewicz (inventeur de l'écriture polonaise) n'aient pas eu plus de succès.
Les connecteurs sont C (implication), K (conjonction), A (disjonction), N (négation).

Ainsi si on n'aime pas "~((p => q) => r)" on peut toujours écrire NCCpqr
et la réponse de Serge devient AAKNpNqKNpqKpq.

Le prof d'analyse de Foys a écrit:

Ne soyez pas esclaves de vos notations

Plus sérieusement il n'y a pas vraiment de notations consensuelles en logique contrairement à ce qui se passe dans le reste de mathématiques. Certains auteurs écrivent $\supset$ à la place de $\Rightarrow$, ou encore $\bigvee$ à la place de $\exists$ par exemple.

PetitLutinMalicieux

Perso, j'utilise la notation additive pour le "ou inclusif" et la notation multiplicative (souvent sous-entendue) pour le "et". Certains diront que c'est ambigu. Mais on ne fait jamais "3 fois vrai" ou "faux plus pi". Soit on est dans l'algèbre des réels, soit dans l'algèbre booléenne. Et dans l'écriture, on allège grandement. Cela évite des "$\wedge\wedge\wedge\wedge\wedge\vee\wedge\wedge\wedge\wedge\wedge\vee\wedge\wedge\wedge\wedge\wedge$" ou des "AAKNpNqKNpqKpq".
Exemple : pqr+st=1
et pas :
$p\wedge q\wedge r\vee s\wedge t = 1$

Du coup, le "plus entouré" est le "ou exclusif"; caractère rejeté par le forum :-).
$a\oplus b=a\overline b + \overline ab$

PetitLutinMalicieux

Chaurien écrivait:

---

> Il faut deviner que $T$ est l'initiale de Vrai

Euh ... t'es sûr, ou tu conjectures ? Est-ce le "t" de "true" ou le "T" de "Tautologie" ?

Chaurien

Ca m'amuse de tenter de répondre à la question, en souvenir de l'époque ancienne où je bénéficiais des cours de Daniel Lacombe, qui nous a quittés en 2016.
Moi j'aime bien les notations booléennes $\vee$ et $\wedge $ fonctionnant comme $\cup$ et $ \cap $, associativité, commutativité, distributivité. Je note $\overline{p}$ pour $\lnot p$, et les calculs se font avec les lois de De Morgan : $\overline{ p\vee q}=\overline{p}\wedge \overline{q}$, $\overline{ p \wedge q}=\overline{p}\vee \overline{q}$.
Pour la question posée, on a : $(p\Rightarrow q)=\overline{p}\vee q$, d'où :
$((p\Rightarrow q)\Rightarrow r)=\overline{(\overline{p}\vee q)}\vee
r=(p\wedge \overline{q})\vee r=(p\vee r)\wedge (\overline{q}\vee r)$, et enfin :
$\lnot ((p\Rightarrow q)\Rightarrow r)=\overline{(p\vee r)\wedge (\overline{q%
}\vee r)}=\overline{(p\vee r)}\vee \overline{(\overline{q}\vee r)}=(%
\overline{p}\wedge \overline{r})\vee (q\wedge \overline{r})$.
Bonne soirée.
Fr. Ch.

Chaurien

Par contre, je ne trouve pas satisfaisante une notation qui remplacerait $\wedge$ par $\cdot$ et $\vee$ par $+$. La distributivité de ce $+$ sur ce $\cdot$ se traduit par : $p+(q \cdot r)=(p+ q)\cdot(p+ r)$, étrange calcul dont je ne vois pas l'intérêt, alors que la double distributivité de $\wedge$ et $\vee$ est tout à fait plaisante et efficace. Et elle s'applique dans d'autres situations, comme PGCD et PPCM.
Comme l'on sait, il y a bien une structure d'anneau (booléen) dont l'addition, qu'on note $p+q$ ou $p\oplus q$ si l'on le trouve plus joli, est le « ou » exclusif, correspondant à la différence symétrique : $p+q=(p\wedge \overline{q})\vee (\overline{p}\wedge q)$, avec la multiplication : $p\cdot q=p\wedge q$.
Bonne soirée.
Fr. Ch.
Edit. Corrigé d'après la remarque de PetitLutinMalicieux plus bas.

PetitLutinMalicieux

Oui ! Tu as tout de suite vu la faille. (Par contre, c'est $p+(q.r)=(p+q).(p+r)$, n'est-ce pas ? On avait rectifié de nous-même. Ou alors $pq+r$).

christophe c

chaurien a écrit:

Moi j'aime bien les notations booléennes $\vee$ et $\wedge $ fonctionnant comme $\cup$ et $ \cap $, associativité, commutativité, distributivité.

Tu ne crois pas si bien dire. CE SONT les mêmes opérations quand tu te restreins à $P(\{0\})$.