1 sur 3 e 1 (2.5 points) Le connecteur de Sheffer, noté \( \mid \) est défini pour deux assertions mathématiques \( P \) et \( Q \) par : \[ P \mid Q \equiv \operatorname{non}(P \text { et } Q) \] 1. Donner la table de vérité du connecteur \( \mid \). 2. Montrer que les connecteurs ou, \( \Rightarrow \) et non peuvent s'exprimer à l'aide du connecteur de Sheffer. Exercice 2 (2 points) Soit la suite de Fibonacci définie par \( u_{0}=0, u_{1}=1 \) et pour tout \( n \in N: \) \[ u_{n+2}=u_{n+1}+u_{n} \] Montrer par récurrence double que pour tout \( n \in N . u_{n}<2^{n+1} \)

### Exercice 1 #### 1. Table de vérité du connecteur \( \mid \) | \( P \) | \( Q \) | \( P \mid Q \) | |---------|---------|---------------| | Vrai | Vrai | Faux | | Vrai | Faux | Vrai | | Faux | Vrai | Vrai | | Faux | Faux | Vrai | #### 2. Expression des connecteurs en termes de \( \mid \) - \( P \text{ ou } Q \) : \( \operatorname{non}(\operatorname{non}P \mid \operatorname{non}Q) \) - \( P \Rightarrow Q \) : \( \operatorname{non}(P \mid \operatorname{non}Q) \) - \( \operatorname{non}P \) : \( P \mid P \) ### Exercice 2 #### Montrer par récurrence double 1. **Base** : \( u_{0} < 2^{0+1} \) et \( u_{1} < 2^{1+1} \) 2. **Inductive** : Si \( u_{n} < 2^{n+1} \) et \( u_{n-1} < 2^{n} \), alors \( u_{n+2} < 2^{n+2} \)