---
title: "folo - TD 2: subject"
tags: folo, td
---
{%hackmd theme-dark %}

$$
\newcommand{\vt}[3]{
\begin{pmatrix}
{#1} \\
{#2} \\
{#3}
\end{pmatrix}
}
\newcommand{\limto}[1]{\xrightarrow[#1]{}}
\newcommand{\p}[1]{\left(#1\right)}
$$

# Formalisation Logique - TD2 : Subject

[`video`](url_video)
[`cours`](url_cours)
[`slides`](url_slides)

## Exercice 1

$$
\equiv_f \text{ relation binaire (d'équivalence ?) }
$$
**Reflexivité** : $x \equiv_f x \iff f(x) = f(x)$ or $f$ est une application donc $f(x) = f(x)$ est vérifié $\forall x \in E$.

**Symétrie** : [$x \equiv_f y \implies y \equiv_f x$] à prouver
Si $x \equiv_f y$ alors $f(x) = f(y)$ mais aussi $f(y) = f(x)$ soit aussi $y \equiv_f x$

**Transitivité** : [$x \equiv_f y \land y \equiv_f z$] $\implies (x \equiv_f z)$ à prouver

Si $x \equiv_f y$ et $y \equiv_f z$ alors $f(x) = f(y)$ et $f(y) = f(z)$ comme $f$ est réflexive, symétrique et une application donc $f(x) = f(z)$ soit $x \equiv_f z$.

$E/\equiv_f$ = $\{\overline{x}; x \in E\}$ où $\overline{x}$ = $\{x' \in E \land x \equiv_f x'\}$

Considérons $\varphi$ :

$$
\begin{align}
E/\equiv_f \text{ } &\to F &\text{(Nb : } Im(f) \subset F)\\
C &\mapsto f(x) &\text{où } x \in C\\
(C : Classe)
\end{align}
$$

$\varphi$ est bien défénie en effet $\forall (x_1, x_2) \in C^2 f(x_1) = f(x_2)$ puisque $x_1 \equiv_f x_2$.

**Injectivité** : Soient $C_1$ et $C_2$ deux classes de $F/\equiv_f$. Supposons $\varphi(C_1) = \varphi(C_2)$ ce qui donne comme relation $x_1\in C_1$ et $x_2 \in C_2$, on a donc $f(x_1) = f(x_2)$ d'ou $x_1 \equiv_f x_2$ Soit aussi $x_2 \in C_1$ et $x_1 \in C2$ d'ou

$$
C_1 \cap C_2 \neq \emptyset \implies C_1 = C_2
$$

> ### Lemme
>
> Si $C_1\cap C_2 \neq \emptyset$ avec $C_1$ et $C_2$ 2 classes d'equivalence Alors $C_1 = C_2$
>
> **Demonstration:**
>
> prenons $x ín C_1 \cap C_2$
>
> Soit $w \in C_1$ on a $w \in C_1$ et $x \in C_2$ d'ou ??

**Surjecivité:** Soit $y \in m(f)$ on a $f(x) = y$ avec $x \in E$ (existe par $y$) on a $\varphi(\bar x) f(x) = y$

## Exercice 2

**Initialisation**: n = 1

carre de $2^1 \times 2^1$

████
██░░ 

**Recurence**

on proposition est validee pour $n$ et il manque un carre dans un des coint (le carre etant sable par rotation il peux etre dans nimporte quel coint).

on dispose les carre d'odre $n$ comme ceci:

████████
██░░░░██
██░░████
██████░░

on peut donc rajoute au millieux une piece ce qui nous donne un carre d'ordre $n + 1$ avec un carre vide dans un coint.

████████
████████
████████
██████░░

## Exercice 3

$\chi_{E \cap F} =^? \chi_E.\chi_F$

$$
\begin{align}
\chi_A : x \mapsto & 1 \text{ si } x \in A\\
&0 \text{ si } x \not\in A
\end{align}
$$

On a :
$$
\begin{align}
\chi_E(x).\chi_F(x) = 0 &\iff \chi_E(x) = 0 \text{ ou } \chi_F(x) = 0\\
&\iff \neg(\chi_F(x) \not= 0 \text{ et } \chi_F \not= 0)\\
&\iff \neg(\chi_E(x) = 1 \text{ et } \chi_F = 1) \text{ car } \chi_*(\Omega) = \{0, 1\}
\end{align}
$$

Finalement :
$$
\chi_E(x).\chi_F = 1 \iff x \in E \cap F \iff \chi_{E \cap F}(x) = 1
$$

Pour le deuxième : $\chi_{E \cap F} + \chi_{E \cup F} = \chi_E + \chi_F$.

| |$E$|pas $E$|
|---|------------|
|$F$|||
|pas $F$|||

## Exerice 4

Montrons que $\chi : \mathcal P(F) \to (\{0;1\}^F)$ est injective

Soit $A$ et $B$ 2 parties de $F$.

Supposons $\chi(A) = \chi_A = \chi_B = \chi(B)$

Si on avait $A \neq B$ alors soit il existe $x \in B \setminus A$ ou $x \in A \setminus B$

Traiton $x \in A \setminus B$: par definition $x \in A$ donc $\chi_A(x) = 1$ et $x \notin B$ d'ou $\chi_B(x) = 0 \neq \chi_A(x)$.

On ne peut que avoir $\chi_A = \chi_B$ donc Absurde.

Don
$A = B$