Metoda deductiei naturale in logica propozitionala si a predicatelor

Pe scurt

Metoda deducției naturale este un sistem formal de demonstrare a validității argumentelor logice, bazat pe reguli de inferență care reflectă modul natural de raționament. În logica propozițională, se pornește de la propoziții simple și conectori logici, iar în logica predicatelor se adaugă cuantificatorii universali și existențiali. Deducția naturală este esențială pentru Bac deoarece dezvoltă gândirea critică și capacitatea de a construi demonstrații riguroase, pas cu pas.

Elementele de bază ale logicii propoziționale

În logica propozițională, pornim de la propoziții simple (simbolizate cu litere: P, Q, R) și folosim conectori logici: conjunctia (∧), disjunctia (∨), implicatia (→), negatia (¬) și echivalenta (↔).

Regulile de bază includ

• Introducerea și eliminarea fiecărui conector
• Eliminarea implicatiei (modus ponens): din P și P→Q putem deduce Q
• Introducerea implicatiei: dacă dintr-o presupunere P deducem Q, atunci putem afirma P→Q, închizând presupunerea

Elementele specifice logicii predicatelor

În logica predicatelor, adăugăm cuantificatorii

• Universal (∀)
• Existențial (∃)

Precum și predicate (P(x), Q(x,y)) care atribuie proprietăți obiectelor dintr-un domeniu.

Regulile specifice includ

• Introducerea universalului: dacă o propoziție este adevărată pentru un element arbitrar, atunci este adevărată pentru toate
• Eliminarea existențialului: dacă există un element cu o proprietate, putem introduce un nume temporar pentru acesta, cu grijă să nu apară conflicte

Concepte cheie și aplicații

Concepte cheie

• Reguli de inferență: eliminare și introducere pentru ∧, ∨, →, ¬, ↔
• Subdemonstrație (subproof) și închiderea ipotezelor
• Cuantificatorii ∀ și ∃
• Variabile libere și legate
• Generalizarea universală și particularizarea existențială
• Silogismul disjunctiv, modus ponens, modus tollens
• Reguli de corectitudine: variabila nouă nu apare în concluzie la eliminarea ∃

Aplicații practice

• Aplicarea deducției naturale în rezolvarea problemelor de tip Bac
• Elevii trebuie să înțeleagă noțiunile de ipoteză, subdemonstrație, închidere a presupunerilor și corectitudinea regulilor

Atenționări

• Capcane frecvente: utilizarea greșită a variabilelor libere sau a cuantificatorilor

Exemple practice

Exemplul 1 (logica propozițională): Demonstrați că (P → Q) ∧ (Q → R) ⊢ (P → R)

Rezolvare

1. (P → Q) ∧ (Q → R) [premisa]
2. P → Q [eliminare ∧ din 1]
3. Q → R [eliminare ∧ din 1]
4. Presupunem P [ipoteză]
5. Din 2 și 4, prin eliminare → (modus ponens): Q
6. Din 3 și 5, prin eliminare →: R
7. Închidem presupunerea: P → R [introducere → din 4-6]

Astfel am demonstrat concluzia.

Exemplul 2 (logica predicatelor - universal): Demonstrați că ∀x (P(x) → Q(x)), ∀x P(x) ⊢ ∀x Q(x)

Rezolvare

1. ∀x (P(x) → Q(x)) [premisa]
2. ∀x P(x) [premisa]
3. Luăm un element arbitrar a (introducere universal)
4. P(a) → Q(a) [eliminare ∀ din 1]
5. P(a) [eliminare ∀ din 2]
6. Q(a) [eliminare → din 4 și 5]
7. Deoarece a a fost arbitrar, ∀x Q(x) [introducere ∀ din 3-6]

Concluzia e validă.

Exemplul 3 (cu existențial): Demonstrați că ∃x P(x), ∀x (P(x) → Q(x)) ⊢ ∃x Q(x)

Rezolvare

1. ∃x P(x) [premisa]
2. ∀x (P(x) → Q(x)) [premisa]
3. Presupunem P(a) [ipoteză pentru eliminare ∃]
4. P(a) → Q(a) [eliminare ∀ din 2]
5. Q(a) [eliminare → din 3 și 4]
6. ∃x Q(x) [introducere ∃ din 5]
7. Închidem ipoteza: din 1 și 3-6, prin eliminare ∃ (a nu apare în concluzie), obținem ∃x Q(x)

Demonstrația e completă.

Verifică-te!

1. Care sunt cele două reguli de bază pentru conectorul implicație (→) în deducția naturală?

1. Ce condiție trebuie respectată atunci când se aplică eliminarea existențialului (∃)?

1. În exemplul 2, de ce putem afirma ∀x Q(x) după ce am demonstrat Q(a) pentru un element arbitrar a?