<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">  <!--Converted with LaTeX2HTML 99.2beta8 (1.46) original version by:  Nikos Drakos, CBLU, University of Leeds * revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan * with significant contributions from:   Jens Lippmann, Marek Rouchal, Martin Wilck and others --> <HTML> <HEAD> <TITLE>Calcul des noncs</TITLE> <META NAME="description" CONTENT="Calcul des noncs"> <META NAME="keywords" CONTENT="mainIA"> <META NAME="resource-type" CONTENT="document"> <META NAME="distribution" CONTENT="global">  <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"> <META NAME="Generator" CONTENT="LaTeX2HTML v99.2beta8"> <META HTTP-EQUIV="Content-Style-Type" CONTENT="text/css">  <LINK REL="STYLESHEET" HREF="mainIA.css">  <LINK REL="previous" HREF="node266.html"> <LINK REL="up" HREF="node265.html"> <LINK REL="next" HREF="node268.html"> </HEAD>  <BODY > <!--Navigation Panel--> <A NAME="tex2html4285"   HREF="node268.html"> <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"  SRC="file:/usr/local/lib/latex2html/icons/next.png"></A>  <A NAME="tex2html4281"   HREF="node265.html"> <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"  SRC="file:/usr/local/lib/latex2html/icons/up.png"></A>  <A NAME="tex2html4277"   HREF="node266.html"> <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"  SRC="file:/usr/local/lib/latex2html/icons/prev.png"></A>  <A NAME="tex2html4283"   HREF="node1.html"> <IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"  SRC="file:/usr/local/lib/latex2html/icons/contents.png"></A>   <BR> <B> Next:</B> <A NAME="tex2html4286"   HREF="node268.html">Plus d'information sur Scheme</A> <B> Up:</B> <A NAME="tex2html4282"   HREF="node265.html">Rsolution en Logique</A> <B> Previous:</B> <A NAME="tex2html4278"   HREF="node266.html">Rappel sur les arbres</A>  &nbsp <B>  <A NAME="tex2html4284"   HREF="node1.html">Contents</A></B>  <BR> <BR> <!--End of Navigation Panel-->  <H1><A NAME="SECTION05520000000000000000"> Calcul des noncs</A> </H1> Correction de l'exercice&nbsp;<A HREF="node72.html#exo:ruyer">3.10</A> page&nbsp;<A HREF="node72.html#exo:ruyer"><IMG  ALIGN="BOTTOM" BORDER="1" ALT="[*]"  SRC="file:/usr/local/lib/latex2html/icons/crossref.png"></A>  <P> <DL> <DT><STRONG>Soluce : </STRONG></DT> <DD>  <BR> Construisons la table de vrit  partir des variables propositionnelles  a, b et c, et des dclarations respectives d'Arthur, Barnab et Casimir : <BR> <P> <TABLE CELLPADDING=3 BORDER="1"> <TR><TD ALIGN="CENTER">a</TD> <TD ALIGN="CENTER">b</TD> <TD ALIGN="CENTER">c</TD> <TD ALIGN="CENTER">Dit d'Arthur</TD> <TD ALIGN="CENTER">Dit de Barnab</TD> <TD ALIGN="CENTER">Dit de Casimir</TD> </TR> <TR><TD ALIGN="CENTER">&nbsp;</TD> <TD ALIGN="CENTER">&nbsp;</TD> <TD ALIGN="CENTER">&nbsp;</TD> <TD ALIGN="CENTER"><!-- MATH  $(a \wedge\ \neg b)$  --> <B><IMG  WIDTH="65" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img849.png"  ALT="$ (a \wedge\ \neg b)$"></B></TD> <TD ALIGN="CENTER"><!-- MATH  $(a \supset\ b)$  --> <B><IMG  WIDTH="58" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img850.png"  ALT="$ (a \supset\ b)$"></B></TD> <TD ALIGN="CENTER"><!-- MATH  $(\neg c \wedge (a \vee\ b))$  --> <B><IMG  WIDTH="102" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img851.png"  ALT="$ (\neg c \wedge (a \vee\ b))$"></B></TD> </TR> <TR><TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> </TR> <TR><TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> </TR> <TR><TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">1</TD> </TR> <TR><TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> </TR> <TR><TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> </TR> <TR><TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> </TR> <TR><TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> </TR> <TR><TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> <TD ALIGN="CENTER">1</TD> <TD ALIGN="CENTER">0</TD> </TR> </TABLE>  <P> On utilisera A pour dsigner ce que dit Arthur, B pour ce que dit Barnab et C pour ce que dit Casimir.  <OL> <LI>On considre les lignes o I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>C<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 0 et on trouve I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>A<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 0,   donc si Casimir ment, Arthur aussi. </LI> <LI>On considre les lignes o I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>C<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 0 et on trouve I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>B<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 1,   donc si Casimir ment, Barnab dit la vrit. </LI> <LI>Par hypothse on a I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>A<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>B<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>C<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 1, c'est la troisime   ligne et on trouve que I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>a<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>c<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 0 et I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>b<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 1, donc si tous   disent la vrit Arthur et Casimir sont innocents et Barnab est le   coupable. </LI> <LI>Par hypothse, on I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>a<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>b<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>c<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 1, c'est la huitime   ligne et on obtient I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>A<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>C<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 0 et I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>B<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 1, donc si tous   sont coupables Arthur et Casimir mentent, Barnab dit la vrit. </LI> <LI>On ne considre que les lignes telles que I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>a<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 1 - I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>A<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> et   I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>b<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 1 - I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>B<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> et I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>c<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = 1 - I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>C<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B>. Seule la ligne 6 est   possible, donc Barnab est innocent, Arthur et Casimir sont   coupables. </LI> <LI>On ne considre que les lignes telles que I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>a<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>A<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> et   I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>b<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>B<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> et I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>c<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B> = I<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img392.png"  ALT="$ [ \! [$"></B>C<B><IMG  WIDTH="10" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img393.png"  ALT="$ ] \! ]$"></B>. Aucune ligne ne correspond,   l'hypothse est contradictoire. </LI> </OL> <!-- MATH  $\heartsuit$  --> <B><IMG  WIDTH="16" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"  SRC="img852.png"  ALT="$ \heartsuit$"></B>  </DD> </DL> <P> Correction de l'exercie&nbsp;<A HREF="node57.html#exo:base">3.2</A> page&nbsp;<A HREF="node57.html#exo:base"><IMG  ALIGN="BOTTOM" BORDER="1" ALT="[*]"  SRC="file:/usr/local/lib/latex2html/icons/crossref.png"></A> <DL> <DT><STRONG>Soluce : </STRONG></DT> <DD>  <BR> Nous nous restreindrons  dmontrer les quivalences entre les   expressions n'utilisant que les connecteurs de la base pour exprimer   les expressions simples de <!-- MATH  ${\mathcal F}$  --> <B><IMG  WIDTH="17" HEIGHT="15" ALIGN="BOTTOM" BORDER="0"  SRC="img43.png"  ALT="$ {\mathcal F}$"></B>.    <OL> <LI>Ici, il suffit d'exprimer les connecteurs <B><IMG  WIDTH="16" HEIGHT="28" ALIGN="MIDDLE" BORDER="0"  SRC="img36.png"  ALT="$ \supset$"></B> et     <B><IMG  WIDTH="16" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"  SRC="img359.png"  ALT="$ \equiv$"></B>, comme <B><IMG  WIDTH="16" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"  SRC="img359.png"  ALT="$ \equiv$"></B> s'exprime  partir des connecteurs     <B><IMG  WIDTH="16" HEIGHT="28" ALIGN="MIDDLE" BORDER="0"  SRC="img36.png"  ALT="$ \supset$"></B> et <B><IMG  WIDTH="15" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"  SRC="img166.png"  ALT="$ \wedge$"></B><A NAME="tex2html89"   HREF="footnode.html#foot11500"><SUP>A.1</SUP></A>, il suffit de se concentrer sur     le seul connecteur <B><IMG  WIDTH="16" HEIGHT="28" ALIGN="MIDDLE" BORDER="0"  SRC="img36.png"  ALT="$ \supset$"></B>. La solution est d'ailleurs donne     dans le cours  la page&nbsp;<A HREF="node57.html#subsect:base"><IMG  ALIGN="BOTTOM" BORDER="1" ALT="[*]"  SRC="file:/usr/local/lib/latex2html/icons/crossref.png"></A>, lorsque l'on a     tabli que <!-- MATH  $\{ \neg, \supset \}$  --> <B><IMG  WIDTH="50" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img81.png"  ALT="$ \{ \neg, \supset \}$"></B> formait une base<A NAME="tex2html90"   HREF="footnode.html#foot11502"><SUP>A.2</SUP></A>. </LI> <LI>Dans le cas de l'oprateur ternaire, on a les quivalences     logiques suivantes <!-- MATH  $\mathtt{ite}(p,0,1) = \neg p$  --> <B><IMG  WIDTH="119" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img855.png"  ALT="$ \mathtt{ite}(p,0,1) = \neg p$"></B>,     <!-- MATH  $\mathtt{ite}(p,1,0) = p$  --> <B><IMG  WIDTH="109" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img856.png"  ALT="$ \mathtt{ite}(p,1,0) = p$"></B>, <!-- MATH  $\mathtt{ite}(p,1,q) = (p \vee q)$  --> <B><IMG  WIDTH="146" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img857.png"  ALT="$ \mathtt{ite}(p,1,q) = (p \vee q)$"></B>, <!-- MATH  $\mathtt{ite}(p,q,0) = (p \wedge q)$  --> <B><IMG  WIDTH="146" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img858.png"  ALT="$ \mathtt{ite}(p,q,0) = (p \wedge q)$"></B>. &#192; partir     de l, comme on sait que <!-- MATH  $\{\neg, \wedge, \vee \}$  --> <B><IMG  WIDTH="66" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img86.png"  ALT="$ \{ \neg, \wedge, \vee \}$"></B> est une base, on     peut construire les expressions reprsentant <!-- MATH  $(p \supset q)$  --> <B><IMG  WIDTH="53" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img75.png"  ALT="$ (p \supset q)$"></B> et     <!-- MATH  $(p \equiv q)$  --> <B><IMG  WIDTH="53" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img76.png"  ALT="$ (p \equiv q)$"></B>. </LI> <LI>Pour tablir que l'oprateur non-et constitue une base, il     suffit de prouver que cet oprateur  la mme puissance     d'expression qu'une autre base. <!-- MATH  $(p \uparrow p) = \neg p$  --> <B><IMG  WIDTH="89" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img859.png"  ALT="$ (p \uparrow p) = \neg p$"></B>,     <!-- MATH  $((p \uparrow p) \uparrow (p \uparrow p)) = \neg \neg p = p$  --> <B><IMG  WIDTH="203" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img860.png"  ALT="$ ((p \uparrow p) \uparrow (p \uparrow p)) = \neg \neg p = p$"></B>,     <!-- MATH  $(p \uparrow q) = \neg (p \wedge q) = (\neg p \vee \neg q)$  --> <B><IMG  WIDTH="215" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img861.png"  ALT="$ (p \uparrow q) = \neg (p \wedge q) = (\neg p \vee \neg q)$"></B>. Cette dernire expression, nous donne la clef pour exprimer     une expression utilisant le connecteur <B><IMG  WIDTH="15" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"  SRC="img166.png"  ALT="$ \wedge$"></B> et/ou le     connecteur <B><IMG  WIDTH="15" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"  SRC="img167.png"  ALT="$ \vee$"></B>. On obtient rapidement que <!-- MATH  $((p \uparrow p) \uparrow (q \uparrow q)) = (p \vee q)$  --> <B><IMG  WIDTH="190" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img862.png"  ALT="$ ((p \uparrow p) \uparrow (q \uparrow q)) = (p \vee q)$"></B> et que <!-- MATH  $((p \uparrow q) \uparrow (p \uparrow q)) = (p \wedge q)$  --> <B><IMG  WIDTH="190" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img863.png"  ALT="$ ((p \uparrow q) \uparrow (p \uparrow q)) = (p \wedge q)$"></B>. </LI> <LI>Pour tablir que l'oprateur non-ou constitue une base, il     suffit de prouver que cet oprateur  la mme puissance     d'expression qu'une autre base.  <!-- MATH  $(p \downarrow p) = \neg p$  --> <B><IMG  WIDTH="89" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img864.png"  ALT="$ (p \downarrow p) = \neg p$"></B>,     <!-- MATH  $((p \downarrow p) \downarrow (p \downarrow p)) = \neg \neg p = p$  --> <B><IMG  WIDTH="203" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img865.png"  ALT="$ ((p \downarrow p) \downarrow (p \downarrow p)) = \neg \neg p = p$"></B>,     <!-- MATH  $(p \downarrow q) = \neg (p \vee q) = (\neg p \wedge \neg q)$  --> <B><IMG  WIDTH="215" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"  SRC="img866.png"  ALT="$ (p \downarrow q) = \neg (p \vee q) = (\neg p \wedge \neg q)$"></B>. Cette dernire expression, nous donne la clef pour exprimer     une expression utilisant le connecteur <B><IMG  WIDTH="15" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"  SRC="img166.png"  ALT="$ \wedge$"></B> et/ou le     connecteur <B><IMG  WIDTH="15" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"  SRC="img167.png"  ALT="$ \vee$"></B>.    </LI> </OL> <!-- MATH  $\heartsuit$  --> <B><IMG  WIDTH="16" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"  SRC="img852.png"  ALT="$ \heartsuit$"></B>  </DD> </DL> <P> <HR> <!--Navigation Panel--> <A NAME="tex2html4285"   HREF="node268.html"> <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"  SRC="file:/usr/local/lib/latex2html/icons/next.png"></A>  <A NAME="tex2html4281"   HREF="node265.html"> <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"  SRC="file:/usr/local/lib/latex2html/icons/up.png"></A>  <A NAME="tex2html4277"   HREF="node266.html"> <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"  SRC="file:/usr/local/lib/latex2html/icons/prev.png"></A>  <A NAME="tex2html4283"   HREF="node1.html"> <IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"  SRC="file:/usr/local/lib/latex2html/icons/contents.png"></A>   <BR> <B> Next:</B> <A NAME="tex2html4286"   HREF="node268.html">Plus d'information sur Scheme</A> <B> Up:</B> <A NAME="tex2html4282"   HREF="node265.html">Rsolution en Logique</A> <B> Previous:</B> <A NAME="tex2html4278"   HREF="node266.html">Rappel sur les arbres</A>  &nbsp <B>  <A NAME="tex2html4284"   HREF="node1.html">Contents</A></B>  <!--End of Navigation Panel--> <ADDRESS> Marc-Michel Corsini (local) 2002-03-15 </ADDRESS> </BODY> </HTML> 
