---
Title: FoLo - Cours 1:\ Logique propositionnelle
tags: folo, cours, MiMos
---
{%hackmd theme-dark %}

# Formalisation Logique - Cours 1: Logique propositionnelle

[`video`](https://web.microsoftstream.com/video/21992a7b-8da2-4ce7-bb45-a2e6fde013ac?channelId=72a2ac7e-b1c9-4e29-9bb0-5c203649f700)
[`slide`](https://moodle.cri.epita.fr/mod/resource/view.php?id=9729)

## Définition

- Une **proposition** est une phrase qui peut seulement être vraie ou fausse.

## Connecteurs Logiques

### Le connecteur $\land$(ET)

$A\land B$ : **vraie** si et seulement si A ET B sont vraie, sinon c'est **faux**.

### Le connecteur $\lor$(OU)

$A\lor B$ : **vraie** si A ET/OU B est vraie (OU inclusif), sinon c'est **faux**.

### Le connecteur implication $\implies$

$A\implies B$ : **vraie** si et seulement si B est vraie.
Remarque :

- Si $A$ est faux : $A\implies B$ est vraie (false permiss)
- Si $A$ et $A\implies B$ sont vraies alors B est vraie (modus pones)
- Si $A\implies B$ et $B\implies C$ sont vraies alors $A\implies C$ est vraie (transitivité)

### Le connecteur négatif $\neg$

$\neg A$ : **vraie** si $A$ est faux.
Remarque : $\neg\neg A \equiv A$

### Le connecteur equivalence logique $\iff$

$A\iff B$ : **vraie** si $A$ et $B$ ont la même valeurs.

Remarque :

- $A\iff B$ est vraie si et seulement si $A\implies B$ et $B\implies A$ sont vraies.
- $A \equiv B$ : **vraie** si A et B sont équivalent, c'est-à-dire, qu'ils ont une écriture synthaxique differente mais veulent dire la même chose ($2+2 \equiv 4$).

## Formuler une proposition vraie

### Quelques intuitions

- Cas particulier d'une proposition générale
- Vérifier une définition
- Formuler des implications à l'aide de propositions connues
- Prouver qu'un objet appartient à un type connu qui verifient les propriétés de ce type

## Le $\land$ et $\lor$

- Si $A \land B$ est une hypothèse, on utilise A et B comme on le souhaite.
- Si on cherche $A \land B$ vraie, on doit montrer que A puis B sont vraies. (Il peut y avoir un lien entre A et B donc l'ordre compte)

## Preuve par l'absurde

- si $P$, ... faux, alors $\neg P$

$\sqrt 2$ est rationnel $\implies \frac{n}{q}$

$$
p = 2 p'
\sqrt{2} \frac{2n'}{q}
2 = \frac{4p'}{q^2}
q^2 = 2p^2
$$

## Preuve par contraposition

$$
P \implies Q \equiv \lnot Q \implies \lnot P
$$

Exemple:

$$
m \geq 3 \land m \text{ premier} \implies m \text{ impaire}
$$

utilisation de la contraposé

$$
m \text{ paire} \implies m \leq 2 \lor m \text{ non premier}
$$

## Analyse Synthèse

Mon résultat est vérifié qu'est ce que je peux en faire

**Exemple :**
Résoudre $x = \sqrt{2 - x}$

Analyse:

si

$$
x = \sqrt{2-x}
$$

alors

$$
x^2 = 2-x \\
x^2 +x = 2
$$

équation du 2nd deg $x = -2 \lor x = 1$

Synthèse:

Si $x = 1$, on a $x = \sqrt{2-x}$
mais le cas $-2$ marche pas évidemment $\implies$ contrainte à ajouter pour faire cette preuve.

## Exemple de démonstration

## Démonstration fausse

On suppose que $a$ et $b$ sont du même signe (hypothèse)
$$
\frac{a+b}{2} \geq \sqrt{ab} \\
(\frac{a+b}{2})^2 \geq ab \\
a^2+b^2+2ab \geq 4ab \\
a^2 + b^2 - 2ab \geq 0 \\
(a-b)^2 \geq 0 \\
$$

Ainsi, $\frac{a+b}{2} \geq \sqrt{ab}$ est vraie.

Cette démonstration est fausse pour deux raisons :

- On fait ici une implication et donc on ne peut pas dire que le début du calcul est vraie quand la fin est vraie sachant que le début de ce calcul n'est pas notre hypothèse
- Comme a et b sont de même signe si a et b sont négatifs alors la partie gauche de l'inégalité sera négative or une racine carré n'est jamais négative donc l'inégalité est impossible
- Truc avec un carré ????

## Prouver $P \land Q$

Soit $p, q \in \mathbb N^2$

$$
p^2 + q^2 \not\equiv 3[4]
$$

On a 4 cas:

- $p$ pair $q$ pair
- $p$ impair $q$ pair
- $p$ pair $q$ impair
- $p$ impair $q$ impair

pout $p$ paire $q$ impaire:

$$
\begin{align}
p^2 + q^2 & \equiv (2 p')^2 + (2q' + 1)^2 \\
& \equiv 3 p'^2 + (2q' + 1)^2 \\
& \equiv 1[4] \\
& \not\equiv 3[4]
\end{align}
$$

## Prouver $P\lor Q$

si $\lnot P$, pouvez $Q$