TD 1 : Introduction

Énoncé

EX 1

\[𝜑 = ((P⟶Q)∨(\lnot P ⟶ \lnot Q)) ∧ (Q ∧ R ⟶ \lnot P) \\ ≡ (\lnot P∨ Q ∨ P ∨ \lnot Q) ∧ (Q ∧ R ⟶ \lnot P) \\ ≡ \top ∧ (Q ∧ R ⟶ \lnot P) \\ ≡ (Q ∧ R ⟶ \lnot P) \\\]

$P$	$Q$	$R$	$\lnot Q ∨ \lnot R ∨ \lnot P$	$𝜑$
$0$	$0$	$0$	$1$	$1$
$0$	$0$	$1$	$1$	$1$
$0$	$1$	$0$	$1$	$1$
$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$1$	$1$
$1$	$0$	$1$	$1$	$1$
$1$	$1$	$0$	$1$	$1$
$1$	$1$	$1$	$0$	$0$

EX 2

$2^{2^n}+1$ : ensemble d’ensembles + principe des tiroirs

EX 3

1.

Soit $I_1, ⋯, I_m$ une interprétation des variables propositionnelles.

Pour toute interprétation $I_j$, on pose

\[𝜑_{I_j} = \bigwedge_{P∈𝒫} f(P)\]

où

$f(P) = \begin{cases} P \text{ si } I(P) = true
\lnot P \text{ sinon} \end{cases}$

2.

M1 :

On pose

\[I_n ≝ \lbrace P_n \rbrace\]

pour tout $n∈ℕ$

Si il existait un ensemble de formules $E$ telles que l’ensemble des modèles est exactement $\lbrace I_n \rbrace_{n∈ℕ}$ :

alors comme, pour toute formule $𝜑$, il y a un nombre fini de variables apparaissant dans cette formule, pour tout modèle $I_N$ de $𝜑$, les interprétation obtenues à partir de $I_N$ en fixant à indifféremment à vrai ou à faux les variables qui n’apparaissent pas dans $𝜑$ sont un modèle de $𝜑$.

Soit $I_i$ une interprétation : elle satisfait toutes les $𝜑∈S$.

Or, il y a un nombre fini de variables apparaissant dans chaque $𝜑$ : donc il existe un $i$ tel qu’il existe une formule $𝜑$ telle que

\[I_i \vDash 𝜑\]

et $P_i \not∈ 𝜑$.

Donc la valuation qui à chaque variable associe $false$ satisfait $𝜑$; or, elle n’appartient pas aux interprétations $\lbrace I_n \rbrace_n$

---

Soit $𝜑∈E$, $∃x∈ X - Var(𝜑)$.

Mais

\[S ∋ \lbrace x \rbrace \vDash 𝜑 ∈ E\]

d’où

\[∅ \vDash 𝜑\]

donc

$∅\vDash E$ : absurde.

M2 : à la Cantor :

l’ensemble des variables propositionnelles étant dénombrable, l’ensemble des formules est dénombrable.

Or, l’ensemble des modèles est non dénombrable : on conclut.

EX 4

\[S ≝ \lbrace \lbrace x \rbrace \mid x∈\underbrace{X}_{\text{dénombrable}} \rbrace ∪ \lbrace ∅ \rbrace\]

Pour $i≠j$ :

$𝜑_{i,j} : x_i ⟹ \lnot x_j$

OU

$𝜑_k :$

\[\lnot x_1 ∧ ⋯ ∧ \lnot x_k \\ ∨ x_1 ∧ \lnot x_2 ∧ ⋯ ∧ \lnot x_k \\ ∨ \lnot x_1 ∧ x_2 ∧ \lnot x_3 ∧ ⋯ ∧ \lnot x_k \\ \vdots \\ ∨ \lnot x_1 ∧ ⋯ ∧ \lnot x_{k-1} ∧ x_{k} \\\]

EX 5

\[𝜃 ≝ 𝜑 ∧ (𝜑 ⟶ 𝜓)\]

EX 9