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)

$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

Leave a Comment