ДНФ = (¬A∧¬B) ∨ C (мінімізована), КНФ = (A∨¬B∨C)∧(¬A∨B∨C)∧(¬A∨¬B∨C).
Задача 3. Modus ponens та ланцюговий силогізм
Умова: Дано: «Якщо йде дощ, то вулиця мокра» (P→Q). «Якщо вулиця мокра, то будьте обережні» (Q→R). «Сьогодні йде дощ» (P). Виведіть «Будьте обережні» (R).
1
Запишемо формально: Аксіоми: P→Q, Q→R, P.
2
Modus Ponens (MP): з φ і φ→ψ можна вивести ψ.
3
Крок 1: з P і P→Q (MP) → Q («вулиця мокра»).
4
Крок 2: з Q і Q→R (MP) → R («будьте обережні»).
Формальне виведення у гільбертовому числення:
1. P→Q (гіпотеза)
2. Q→R (гіпотеза)
3. P (гіпотеза)
4. Q (MP на 1,3)
5. R (MP на 2,4) ← Q.E.D.
Ланцюговий силогізм: (P→Q)∧(Q→R) ⊢ (P→R)
Теорема дедукції: (Γ,φ ⊢ ψ) ⟺ (Γ ⊢ φ→ψ)
Тут: {P→Q, Q→R, P} ⊢ R ⟺ {P→Q, Q→R} ⊢ P→R
Відповідь:
R виводиться двократним застосуванням modus ponens. Висновок: «Будьте обережні».
Задача 4. Предикатна логіка: квантори і заперечення
Умова: Запишіть формально і знайдіть, яке з тверджень є сильнішим: (a) «Існує студент, який виконав всі задачі» (b) «Для кожної задачі існує студент, що її виконав». Чи є вони еквівалентними?
P(s,t) = «студент s виконав задачу t»
S = {студенти}, T = {задачі}
(a) ∃s∈S ∀t∈T P(s,t) ← «один студент виконав ВСЕ»
(b) ∀t∈T ∃s∈S P(s,t) ← «кожну задачу хтось виконав»
1
Зверніть увагу на порядок кванторів — він критичний!
2
Якщо (a) виконане → зафіксований студент s₀ виконав все → для кожного t маємо студента s₀ → (b) виконане. Отже: (a) ⟹ (b).
3
Контрприклад для ←: 2 задачі t₁,t₂, 2 студенти. Студент А виконав t₁, студент Б виконав t₂ → (b) виконане, але (a) ні.
Законы кванторів:
¬∀x φ(x) ≡ ∃x ¬φ(x)
¬∃x φ(x) ≡ ∀x ¬φ(x)
(a) ⟹ (b) але (b) ⟹ (a) неправда
Тобто (a) є СИЛЬНІШИМ твердженням (більш обмежувальним)
Відповідь:
(a) суворо сильніше (b): (a)⟹(b) але не навпаки. Порядок кванторів ∃∀ ≠ ∀∃.
Задача 5. Метод резолюції для SAT
Умова: Покажіть, що формула F = (A∨B) ∧ (¬A∨C) ∧ (¬B∨¬C) ∧ ¬C є незадовільною (unsatisfiable) методом резолюції.
1
Запишемо клаузи (вже в КНФ): C₁=(A∨B), C₂=(¬A∨C), C₃=(¬B∨¬C), C₄=(¬C).
2
Правило резолюції: з α∨L і β∨¬L виводимо α∨β (резолвент). Мета: отримати порожню клаузу □.
Крок 1: Резолюція C₂=(¬A∨C) і C₄=(¬C):
L=C: з (¬A∨C) і (¬C) → (¬A) ← нова клауза C₅=(¬A)
Крок 2: Резолюція C₁=(A∨B) і C₅=(¬A):
L=A: з (A∨B) і (¬A) → (B) ← нова клауза C₆=(B)
Крок 3: Резолюція C₃=(¬B∨¬C) і C₄=(¬C):
L=C: якщо C=⊥ завжди (з C₄), то з C₃ маємо (¬B) ← C₇=(¬B)
Альтернативно: C₃ і C₄: вже знаємо ¬C, тому C₃→(¬B)
Крок 4: Резолюція C₆=(B) і C₇=(¬B):
L=B: з (B) і (¬B) → □ ← ПОРОЖНЯ КЛАУЗА → СУПЕРЕЧНІСТЬ!
3
Порожня клауза □ означає суперечність — формула НЕЗАДОВІЛЬНА (немає жодного задовільного набору).
Відповідь:
За 4 кроки резолюції отримана порожня клауза. F незадовільна (UNSAT). Це основа методу DPLL і сучасних SAT-солверів.
Задача 6. Теорема Ґьоделя про неповноту — концептуально
Умова: Пояснити суть першої теореми Ґьоделя і навести аналог «парадоксу брехуна» у формальній арифметиці.
1
Кодування Ґьоделя: кожній формулі φ ставимо у відповідність ціле число ⌈φ⌉ (гьоделів номер). Тоді можна говорити про формули як про числа всередині арифметики.
2
Самопосилання: побудуємо формулу G: «Ця формула не доводиться у системі F». У числовому вигляді: G(n) ≡ «формула з номером n не має доведення».
3
Лема про діагоналізацію: існує G таке, що F ⊢ (G ↔ ¬Provable(⌈G⌉)).
4
Аналіз: якщо G доводиться → F ⊢ ¬Provable(⌈G⌉) → суперечність (якщо F несуперечлива). Якщо G не доводиться → G істинна, але недоводима.
1-а теорема Ґьоделя (1931):
Нехай F — несуперечлива формальна система,
що містить арифметику Пеано (або Q, слабшу).
Тоді ∃ речення G:
• F ⊬ G (G не доводиться)
• F ⊬ ¬G (¬G не доводиться)
Тобто G є «незалежним» від F.
2-а теорема:
Con(F) — «F несуперечлива» — не доводиться у F
(якщо F справді несуперечлива)
Аналогія: «Парадокс брехуна»
S = «Це речення є хибним»
Якщо S істинне → S хибне → суперечність
Якщо S хибне → S істинне → суперечність
В арифметиці G = «Це речення не доводиться»:
НЕ суперечність (лише неповнота)
5
Наслідок: жодна несуперечлива аксіоматична система, що містить арифметику, не може бути одночасно несуперечливою і повною. (Мрія Гільберта — програма аксіоматизації — неможлива.)
Відповідь:
G ≡ «Я не доводимий» — ґьоделівське речення. Якщо F несуперечлива, то G істинна, але недоводима у F. F неповна. Перша теорема Ґьоделя 1931.
Методика розв'язання
Ця сторінка містить докладно розв'язані задачі з покроковими поясненнями. Мета — показати не лише відповідь, а сформувати розуміння методу, яке можна перенести на аналогічні задачі.
Як вчитися на прикладах
Перед переглядом розв'язку спробуйте вирішити задачу самостійно. Якщо застрягли — зверніться до першого кроку, потім знову спробуйте самі. Пояснюйте кожен крок уголос — це радикально покращує засвоєння.
Часті запитання (FAQ)
Які методи розв'язання задач з розв'язані задачі демонструються на цій сторінці?
Сторінка демонструє стандартні та нестандартні методи розв'язання задач з 'Розв'язані задачі': аналітичні підходи, числові методи та графічні інтерпретації. Кожен крок супроводжується поясненням логіки.
Якого рівня складності задачі з розв'язані задачі представлені?
Представлені задачі охоплюють рівні: типові задачі з підручників (базовий), задачі підвищеної складності (середній) та нетипові варіанти (просунутий). Кожна задача чітко позначена за рівнем.
Як вчитися на розв'язаних задачах з розв'язані задачі найефективніше?
Ефективна техніка: прочитайте умову → спробуйте розв'язати самостійно → порівняйте з розв'язком → якщо помилилися, проаналізуйте де саме → через 2–3 дні повторіть задачу без підказок. Це формує стійкі навички.
Чи є в розв'язках покрокові пояснення всіх перетворень?
Так, кожен розв'язок розв'язані задачі містить детальні покрокові пояснення: записується перетворення, обґрунтовується його правомірність, вказуються використані теореми та формули. Підхід 'показати думку', а не лише відповідь.
Як ці задачі з розв'язані задачі допомагають при підготовці до контрольних та іспитів?
Розв'язані задачі з 'Розв'язані задачі' покривають типові варіанти університетських контрольних і іспитних завдань. Після їх опрацювання ви будете впізнавати тип задачі та одразу знати метод — це вирішальна перевага на іспиті.