Série de révision Logique Mathématique
Question 1: (Opérations sur les formules)
Montrer que les deux formules suivantes sont équivalentes en utilisant les lois algèbre des propositions:
(𝑃 ∨ 𝑄) → 𝑅 ≡ (𝑃 → 𝑅) ∧ (𝑄 → 𝑅)
(𝑃 ∨ 𝑄) → 𝑅 ≡¬(𝑃 ∨ 𝑄) ∨ 𝑅
Commutativité
Morgan
≡ (¬𝑃 ∧ ¬𝑄) ∨ 𝑅 ≡𝑅 ∨ (¬𝑃 ∧ ¬𝑄) ≡ (𝑅 ∨ ¬𝑃) ∧ (𝑅 ∨ ¬𝑄) ≡ (¬𝑃 ∨ 𝑅) ∧ (¬𝑄 ∨ 𝑅) ≡ (𝑃 → 𝑅) ∧ (𝑄 → 𝑅)
Distributivité Commutativité
Question 2 : (Table de Beth)
Montrer que l’assertion ( la formule) suivante est une tautologie (Théorème) en utilisant le raisonnement par l’absurde: 𝑃 → (𝑄 → 𝑅) ⊢ (𝑃 ∧ 𝑄) → 𝑅
𝑃 → (𝑄 → 𝑅) ⊢ (𝑃 ∧ 𝑄) → 𝑅 𝑒𝑠𝑡 é𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑒 à (𝑃 → (𝑄 → 𝑅)) → ((𝑃 ∧ 𝑄) → 𝑅) : 𝑓(𝑃, 𝑄, 𝑅) (𝑃 → (𝑄 → 𝑅)) → ((𝑃 ∧ 𝑄) → 𝑅) contradiction.
est une tautologie ssi sa réfutation conduit à une
(𝑃 → (𝑄 → 𝑅)) → ((𝑃 ∧ 𝑄) → 𝑅)
*
𝑃 → (𝑄 → 𝑅)
* (𝑃 ∧ 𝑄) → 𝑅 * 𝑃 ∧ 𝑄
𝑅 𝑃 𝑄
𝑃
⊥
𝑄 → 𝑅
*
𝑄 𝑅 ⊥
⊥
Toutes les branches de l’arbre de Beth sont closes donc la réfutation de la formule 𝑓(𝑃, 𝑄, 𝑅) est une contradiction et par suite la formule tautologie.
(𝑃 → (𝑄 → 𝑅)) → ((𝑃 ∧ 𝑄) → 𝑅)
est une
Question 3 (démonstration)
Prouver que la formule suivante est un théorème en utilisant une déduction naturelle (théorie de la démonstration) ( (𝑃 ∨ 𝑄
) → 𝑅) → (𝑅 → 𝑆) → ¬𝑆 → ¬𝑃
Il s’agit d’une démonstration d’implication donc le cas de figure d'application du théorème de la déduction: { ( (𝑃 ∨ 𝑄
( (𝑃 ∨ 𝑄 ) → 𝑅); 𝑅 → 𝑆; ¬𝑆
) → 𝑅) → (𝑅 → 𝑆) → ¬𝑆 → ¬𝑃
en appliquant 3 fois le TDD
est équivalente à
}⊢¬𝑃
) → 𝑅; 𝑅 → 𝑆; ¬𝑆 } ) → 𝑅
Déduction sous hypothèses ( { 𝑃 ∨ 𝑄 1- ℎ𝑦𝑝 𝑃 ∨ 𝑄 ( 2- ℎ𝑦𝑝 𝑅 → 𝑆 3- Règle de la transitivité de l’implication sur 1&2: (remarque règle de la transitivité de l’implication 𝐴 → 𝐵; 𝐵 → 𝐶 { 4-ℎ𝑦𝑝 ¬𝑆 5- mtt sur 3&4: (remarque mtt 𝐴 → 𝐵; ¬𝐵 6- 𝐴 : (¬𝑃 ∧ ¬𝑄) → ¬𝑃 4
{ ( 𝑃 ∨ 𝑄 {
) → 𝑆; ¬𝑆
{ ( 𝑃 ∨ 𝑄
}⊢¬𝐴)
* }⊢¬(𝑃 ∨ 𝑄) ¬(𝑃 ∨ 𝑄) ≡ ¬𝑃 ∧ ¬𝑄
or
) → 𝑅; 𝑅 → 𝑆
}⊢ 𝑃 ∨ 𝑄
(
* ) → 𝑆
}⊢𝐴 → 𝐶)
7- 𝑚𝑝𝑝 𝑠𝑢𝑟 5&6: ¬𝑃 ∧ ¬𝑄; (¬𝑃 ∧ ¬𝑄) → ¬𝑃 Conclusion : ¬𝑃
Publicité
{
}⊢¬𝑃
Question 4 :( Argumentation) L’argument suivant est-il valide? Justifier. “Si carlo a remporté la compétition, Mario est arrivé second ou Sergio est arrivé troisième. Sergio n’est pas arrivé troisième. Ainsi, si Mario n’est pas arrivé deuxième, Carlo n’a pas gagné la compétition”.
a- Définir des propositions:
C “ Carlo remporte la compétition” M “ mario est arrivé second” S” sergio est arrivé troisième”
b- formalisme:
𝐶 → (𝑀 ∨ 𝑆)
● ● ¬𝑆 ● ¬𝑀 → ¬𝐶
; 𝐶 → (𝑀 ∨ 𝑆) ¬𝑆⊢¬𝑀 → ¬𝐶 𝐶 → (𝑀 ∨ 𝑆) ¬𝑆
c- Condition de validité de l’argument: L’argument fois que les prémisses et (Remarque la condition de validité d’un argument (théorème): l’argument ⊢¬𝑀 → ¬𝐶 une tautologie ) d- Table de vérité
est valide ssi le résultat sont vraies. (définition)
est valide ssi la formule
¬𝑀 → ¬𝐶
𝑓(𝐶, 𝑀, 𝑆): ((𝐶 → (𝑀 ∨ 𝑆)) ∧ ( ¬𝑆)) → (¬𝑀 → ¬𝐶)
est vrai chaque
; 𝐶 → (𝑀 ∨ 𝑆) ¬𝑆 est
l’argument s’écrit en fonction de trois atomes C, S et M donc la table de vérité contient 8 lignes. b
𝐶 𝑀 𝑆 ¬𝐶 ¬𝑀 ¬𝑆 𝑀 ∨ 𝑆 𝐶 → (𝑀 ∨ 𝑆) ¬𝑀 → ¬𝐶 (𝐶 → (𝑀 ∨ 𝑆)) ∧ ¬𝑆
𝑓( 𝐶, 𝑀, 𝑆)
f
f
f
f
v
v
v
v
f
f
v
v
f
f
v
v
f
v
v v
f
v
v v
f
f
v f
f
f
v f
v
v
f
Publicité
f
v
v
f
f
v
f
v
f
v
f
v
f
f
v
v
v
f
v
v
v
v
v
v
v
f
v
v
v
v
v
v
v
f
f
v
v
v
f
v
f
f
f
v
f
v
v
v
v
v
Publicité
v
v
v
e- conclusion les deux prémisses sont vraies sur les lignes 1, 3 et 7;le résultat est aussi vrai sur ces lignes donc l’argument est valide. NB : on remarquera que la formule une tautologie.
𝑓( 𝐶, 𝑀, 𝑆): ((𝐶 → (𝑀 ∨ 𝑆)) ∧ ( ¬𝑆)) → (¬𝑀 → ¬𝐶)
est
Question 5 (Formalisme ) Formaliser les énoncés suivants:
● Un logicien a été champion du monde de cyclisme ● tout le monde a menti à quelqu’un dans sa vie.
Un logicien a été champion de monde du cyclisme: ∃𝑥 ( 𝑙𝑜𝑔𝑖𝑐𝑖𝑒𝑛(𝑥) ∧ 𝑐ℎ𝑎𝑚𝑝𝑖𝑜𝑛(𝑥))
Tout le monde a menti à quelqu’un dans sa vie: ∀𝑥∃𝑦 𝑚𝑒𝑛𝑡𝑖𝑟 (𝑥, 𝑦)
Question 6 ( Interprétation de formule) Soit la proposition d’interprétation de x et de y est : ● l’ensemble des réel IR ● l’ensemble des entiers naturels IN
∀𝑥 ∃𝑦(𝑥² ≥ 𝑦²).
Quelle est sa valeur de vérité lorsque le domaine
Soit le domaine d’interprétation 𝐷 = 𝐼𝑅:
𝐼(∀𝑥 ∃𝑦(𝑥² ≥ 𝑦²)) = 𝑣 𝑠𝑠𝑖 𝑝𝑜𝑢𝑟 𝑡𝑜𝑢𝑡 𝑑 ∈ 𝐼𝑅, 𝑜𝑛 𝐼
(∃𝑦(𝑥² ≥ 𝑦²)) = 𝑣.
𝑥=𝑑
𝑂𝑟 𝐼
(∃𝑦(𝑥² ≥ 𝑦²)) = 𝑣 𝑠𝑠𝑖 𝑖𝑙 𝑒𝑥𝑖𝑠𝑡𝑒 𝑑' ∈ 𝐼𝑅 𝑡𝑒𝑙𝑙𝑒 𝑞𝑢𝑒:
𝑥=𝑑
(𝑥² ≥ 𝑦²) = 𝑣
𝐼 𝑥=𝑑, 𝑦=𝑑' ( 𝑐𝑒 𝑞𝑢𝑖 𝑒𝑠𝑡 é𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡 à 𝑑𝑖𝑟𝑒 𝑝𝑜𝑢𝑟 𝑛'𝑖𝑚𝑝𝑜𝑟𝑡𝑒 𝑞𝑢𝑒𝑙 𝑑 ∈ 𝐼𝑅 , 𝑜𝑛 𝑝𝑒𝑢𝑡 𝑡𝑟𝑜𝑢𝑣𝑒𝑟 𝑑' / 𝑑² ≥ 𝑑'²
Pour : 𝑑' = 1 − 𝑑 𝑜𝑛 𝑎𝑢𝑟𝑎 𝑥² ≥ 𝑦² ⇒ 𝑑² ≥ (1 − 𝑑)² ⇒ 𝑑² ≥ 1 − 2𝑑 + 𝑑² ⇒ − 1 + 2𝑑 ≥ 0 𝑠𝑠𝑖 𝑑 ≥ 1/2
Donc
𝐼 𝑥=𝑑, 𝑦=𝑑'
(𝑥² ≥ 𝑦²) = 𝑣
𝐼(∀𝑥 ∃𝑦(𝑥² ≥ 𝑦²)) = 𝑓𝑎𝑢𝑥.
ssi
𝑑 ≥ 1/2
donc ce n’est pas pour tout d donc
(Remarque ; on aurait pu faire le même raisonnement avec 𝑑' = 𝑑 + 1 𝑜𝑛 𝑎𝑢𝑟𝑎 𝑥² ≥ 𝑦² ⇒ 𝑑² ≥ (𝑑 + 1)² ⇒ 𝑑² ≥ 1 + 2𝑑 + 𝑑² ⇒ − 1 + 2𝑑 ≤ 0 𝑠𝑠𝑖 𝑑 ≤ 1/2 Donc
donc ce n’est pas pour tout d donc
(𝑥² ≥ 𝑦²) = 𝑣
𝑑 ≤ 1/2
ssi
𝐼 𝑥=𝑑, 𝑦=𝑑'
𝐼(∀𝑥 ∃𝑦(𝑥² ≥ 𝑦²)) = 𝑓.
)
Si le domain était 𝐷 = 𝐼𝑁 𝐼(∀𝑥 ∃𝑦(𝑥² ≥ 𝑦²)) = 𝑣 𝑠𝑠𝑖 𝑝𝑜𝑢𝑟 𝑡𝑜𝑢𝑡 𝑑 ∈ 𝐼𝑁, 𝑜𝑛 𝐼
𝑠𝑠𝑖 𝑖𝑙 𝑒𝑥𝑖𝑠𝑡𝑒 𝑑' ∈ 𝐼𝑁 𝑡𝑒𝑙𝑙𝑒 𝑞𝑢𝑒 𝐼
𝑥=𝑑, 𝑦=𝑑'
𝑥=𝑑 (𝑥² ≥ 𝑦²) = 𝑣
(∃𝑦(𝑥² ≥ 𝑦²)) = 𝑣. 𝑂𝑟 𝐼
(∃𝑦(𝑥² ≥ 𝑦²)) = 𝑣
𝑥=𝑑
( 𝑐𝑒 𝑞𝑢𝑖 𝑒𝑠𝑡 é𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡 à 𝑑𝑖𝑟𝑒 𝑝𝑜𝑢𝑟 𝑛'𝑖𝑚𝑝𝑜𝑟𝑡𝑒 𝑞𝑢𝑒𝑙 𝑑 ∈ 𝐼𝑅 , 𝑜𝑛 𝑝𝑒𝑢𝑡 𝑡𝑟𝑜𝑢𝑣𝑒𝑟 𝑑' / 𝑑² ≥ 𝑑'² la condition est sur 𝑑 ≥ 1/2 𝑞𝑢𝑖 𝑛'𝑒𝑠𝑡 𝑝𝑎𝑠 𝑢𝑛 𝑒𝑛𝑡𝑖𝑒𝑟 𝑛𝑎𝑡𝑢𝑟𝑒𝑙 𝑑𝑜𝑛𝑐 . 𝐼(∀𝑥 ∃𝑦(𝑥² ≥ 𝑦²)) = 𝑣