---
Title: Folo - TD 1
tags: folo, TD
---
{%hackmd theme-dark %}

$$
\newcommand{\f}[2]{\frac{#1}{#2}}
\newcommand{\p}[1]{\left(#1\right)}
$$

# Formalisation Logique - TD1

[`sujet`](https://moodle.cri.epita.fr/mod/resource/view.php?id=9731)
[`correction`](https://web.microsoftstream.com/channel/41cda1e0-6480-46dc-b88b-e2372bf2bb0a)

## Exercice 1

On étudie un raisonnement qui vise à montrer que $\forall x \in \mathbb R, sin(x+\pi) = -sin(x)$.

$$
sin(x+\pi) = sin(x) + sin(\pi)
$$

FAUX, car la distributivité du sinus n'existe pas.

On peut dire aussi que sinus c'est pas linéaire.

Autre technique :

$$
\neg (sin(x+\pi) = sin(x) + sin(\pi)) : \exists x \in \mathbb R, sin(x+\pi) \neq sin(x) + sin(\pi) \\
\text{Pour }x = \frac{\pi}{2}, sin(x+\pi) = sin(\frac{3\pi}{2}) = -1\\
sin(\frac{\pi}{2}) + sin(\pi) = 1\\
\text{On a donc } sin(\frac{\pi}{2}+ \pi) \neq sin(\frac{\pi}{2}) + sin(\pi)\\
\text{Donc } \neg (1) \text{ est VRAI}\\
\text{Autrement dit (1) est FAUX}
$$

Bon raisonnement :

$$
sin(x+\pi) = sin(x)cos(\pi) + sin(\pi)cos(x) \\
sin(x+\pi) = -sin(x) + 0 \\
sin(x+\pi) = -sin(x)
$$

## Exercice 2

La phrase de conclusion en langue maternelle est incorrecte.
Elle sugère que le raissonnement a été effectué par équivalence, ce qui n'est pas le cas !

En réalité on a juste prouvé que

$$
2 = 4 \implies 1 = 1 \text{ est vérifié}
$$

$2 = 4$ n'est qu'une hypothèse et ne prend pas le status de conclusion !

## Exercice 3

On sait que : $e^x < e^{x+1}$
Soit $M = e^{x+1}$
Donc $e^x < M$, FAUX car M est variable et ce n'est donc pas un majorant.

## Exercice 4

Soit $x \in \emptyset$ alors "$x \in \emptyset$" étant faux (ref : prédicat), on a d'après le tableau de vérité de $\implies$ :
$$
(x \in \emptyset) \implies (...) \text{ est vraie.}
$$

Ainsi :
$$
x \in \emptyset \implies (x \in A \cap \emptyset) \text{ et } x \in \emptyset \implies (x \in A \cup \emptyset)
\text{ sont vraies. }
$$

On a donc :
$$
\emptyset \subseteq A \cap \emptyset \text{ et } \emptyset \subseteq A \cup \emptyset
$$

Réciproquement, si $x \in A \cap \emptyset$ alors $x \in A$ et $x \in \emptyset$ et en particulier $x \in \emptyset$ donc :
$$
x \in A \cap \emptyset \implies x \in \emptyset
$$

soit $A \cap \emptyset \subseteq \emptyset$, si $x \in A$ alors $(x \in A \text{ ou } x \in \emptyset)$ donc :
$$
A \subseteq A \cup \emptyset
$$

Réciproquement, on a $x \in A \cup \emptyset$ lorsque $x \in A$ ou $x \in \emptyset$ et comme $x \in \emptyset$ est faux, on a que $x \in A \lor x \in \emptyset$ a la même valeur de vérité que $x \in A$ donc :
$$x \in A \cup \emptyset \iff x \in A \text{ soit } A \cup \emptyset = A$$

## Exercise 5 - A strange equation

> Let $E$ be a set and $A,B \in \mathcal P(E)$ be two subsets of $E$.
>
> Prove that $\forall X \in \mathcal P(E)$,
>
> $$
> (A \cap X = B) \iff (B \subseteq X) \land (X\subseteq B \cup A) \land (B \subseteq A)
> $$

| $A$ | $B$ | $X$ | $A \land X$ | $A \land X \iff B$ |
|:---:|:---:|:---:|:-----------:|:------------------:|
| $0$ | $0$ | $0$ | $0$ | $1$ |
| $0$ | $0$ | $1$ | $0$ | $1$ |
| $0$ | $1$ | $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ | $0$ | $0$ |
| $1$ | $0$ | $0$ | $0$ | $1$ |
| $1$ | $0$ | $1$ | $1$ | $0$ |
| $1$ | $1$ | $0$ | $0$ | $0$ |
| $1$ | $1$ | $1$ | $1$ | $1$ |

| $A$ | $B$ | $X$ | $B\implies X$ | $X\implies B \lor \lnot A$ | $B \implies A$ | $(B \subseteq X) \land (X\subseteq B \cup A) \land (B \subseteq A)$ |
|:---:|:---:|:---:|:-------------:|:--------------------------:|:--------------:|:-------------------------------------------------------------------:|
| $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ |
| $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ |
| $0$ | $1$ | $0$ | $0$ | $1$ | $0$ | $0$ |
| $0$ | $1$ | $1$ | $1$ | $1$ | $0$ | $0$ |
| $1$ | $0$ | $0$ | $1$ | $1$ | $1$ | $0$ |
| $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $0$ |
| $1$ | $1$ | $0$ | $1$ | $1$ | $1$ | $1$ |
| $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |

| $A$ | $B$ | $X$ | $\lnot A$ | $B \lor \lnot A$ | $X\implies B \lor \lnot A$ |
|:---:|:---:|:---:|:---------:|:----------------:|:--------------------------:|
| $0$ | $0$ | $0$ | $1$ | $1$ | $1$ |
| $0$ | $0$ | $1$ | $1$ | $1$ | $1$ |
| $0$ | $1$ | $0$ | $1$ | $1$ | $1$ |
| $0$ | $1$ | $1$ | $1$ | $1$ | $1$ |
| $1$ | $0$ | $0$ | $0$ | $0$ | $1$ |
| $1$ | $0$ | $1$ | $0$ | $0$ | $0$ |
| $1$ | $1$ | $0$ | $0$ | $1$ | $1$ |
| $1$ | $1$ | $1$ | $0$ | $1$ | $1$ |

Les prédicat d'appartenance ne sont pas égaux donc l'égalité est fausse.

Autre méthode :

Soit $A,B,X \subseteq E$

On veut montrer que :

$A\cap X = B \Leftrightarrow (B \subseteq X) \cap (X \subseteq B \cup A^C) \cap (B \subseteq C)$

- Etape 1: montrer $A \cap X \implies B \subseteq X$

$$
B = A \cap X \subseteq X
$$

- Etape 2: montrer $A \cap X \implies B \subseteq A$

$$
B = A \cap X \subseteq A
$$

- Etape 3: montrer que $A\cap X = B \implies X \subseteq B \cup A^C$

Cas 1 : $X \in A$
$$
X \in A\cap X\\
X \in B \text{ par hypothèse}
$$
Cas 2 : $X \in A^C$
$$
X \in A^C \subseteq A^C \cup X
$$
## Exercice 6
Le contraire de la question : "ABC est un triangle isocèle ?" est "ABC n'est pas isocèles"
## Exercice 7

Soit $a,b \in \mathbb{R}^2$

On a :
$$
\begin{cases} S = a + b \\ P = a \times b \end{cases} \\
\begin{cases} a = S - b \\ P = a \times b \end{cases} \\
\begin{cases} a = S - b \\ P = (S - b) \times b \end{cases} \\
\begin{cases} a = S - b \\ S\times b - b^2 - P = 0\end{cases}\\
\begin{cases} a = S - b \\ - b^2 + S\times b - P = 0\end{cases}\\
$$
En resolvant l'equation du second degré on trouve le résultat et voila. Disjonction de cas à faire...

## Exercice 8
Preuve par contraposé :
Supposons que $m$ est impaire.

Alors $m = 2k+1$ avec $k \in \mathbb{N}$
Ainsi :
$$
m^2 = (2k+1)^2\\
m^2 = (2k)^2+2\times2k\times1+1^2\\
m^2 = 4k^2+4k+1\\
m^2 = 2(2k^2+2k) + 1
$$
Ainsi $m^2$ est impaire si $m$ est impaire, c'est-à-dire que $m\text{ impaire}\implies m^2 \text{ impaire}$. Donc par contraposé,$m\text{ paire}\implies m^2 \text{ paire}$.

## Exercice 9 :

Utilisons la contraposé :
Soit $x\in (A \subseteq B)$ :
$$
A \subseteq B \iff (x \in A ) \implies (x \in B)\\
\iff (x \notin B ) \implies (x\notin A)\\
\iff (x\in B^C) \implies (x \in A^C)\\
\iff B^C \subseteq A^C
$$

Donc $A \subseteq B \iff B^C \subseteq A^C$.

On part de $B^\complement \subseteq A^\complement$

$$
\begin{align}
B^\complement \subseteq A^\complement &\iff B^\complement \not\subseteq A \\
&\equiv \forall x \in B^\complement, x \notin A
\end{align}
$$

Or

$$
\begin{align}
B^\complement \cap A &= \{x|(x \in B^\complement) \land (x \in A)\}\\
& = \{x|(x \notin A) \land (x \in A)\}\\
& = \{x|\lnot(x \in A) \land (x \in A)\}\\
& = \{x|\bot\}\\
& = \emptyset
\end{align}
$$

## Exercice 10
Prouvons $A \cap A^C = \emptyset$

++Par contradiction :++ supposons $A \cap A^C \neq \emptyset$ vraie. Alors :
$$
\begin{align}
A \cap A^C \not= \emptyset &\iff x \in A \cap A^C \\
&\iff x \in A \land x \in A^C \\
&\iff x \in A \land x \notin A\\
&\iff x \in A \land \neg x \in A
\end{align}
$$
Ceci est impossible et donc $A \cap A^C = \emptyset$ est vraie.

Prouvons que $A\cup A^C = E$ sachant que $A \in P(E)$

++Par double inclusion++: montrons d'abord que $E \subseteq A\cup A^C$, soit $x \in E$:
$$
\begin{align}
x \in E &\implies x \in A \lor \neg x \in A \text{ par hypothèse} \\
&\iff x \in A \lor x \notin A \\
&\iff x \in A \lor x \in A^C \\
&\implies x \in A\cup A^C
\end{align}
$$
Ainsi, $E \subseteq A\cup A^C$

Montrons ensuite que $A\cup A^C \subseteq E$, soit $x \in A\cup A^C$:
$$
\begin{align}
\text{Cas 1 : } x &\in A \\
x &\in A \subset E \\
\text{Cas 2 : } x &\in A^C \\
x &\subset E \text{ car } A^C = E \setminus A
\end{align}
$$
Ainsi $A\cup A^C \subseteq E$

Conclusion : $A\cup A^C = E$

## Exercice 11
### 1) $A \implies (B \land \neg(C\lor D))$

$$
\neg(A \implies (B \land \neg(C\lor D))) \\
\text{Rappel : } A \implies B \iff \neg A \lor B \\
\neg(\neg A \lor (B \land \neg(C\lor D)))\\
A \land \neg((B \land \neg(C\lor D))) \\
A \land (\neg B \lor (C\lor D))
$$

## Exercice 12
$$
A = \forall x \in E, P(x) \lor Q(x) \\
B = (\forall x \in E, P(x)) \lor (\forall x \in E, Q(x)) \\
\text{Par double implication : } A\implies B\\
$$
Soit : $P(x) =$ x est paire$ et $Q(x) =$ x est impaire. Dans ce cas, A est vraie mais B ne peut pas l'etre.