Логіка й доведення: правила, за якими міркують у ШІ

Висловлення, зв’язки й таблиці істинності, пастка з імплікацією, квантори та види доведень — і чому XOR зупинив перші нейронні мережі.

14 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 7 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

Кожне означення в цій серії — це логічне твердження, а кожне «тому» після нього — шматочок доведення. Логіка — це правила гри: вона каже, коли твердження істинне і як із істинних тверджень правильно вивести інші. А в штучному інтелекті вона присутня двічі — як мова, якою говорять про алгоритми, і як окрема галузь, з якої виросли перші «мислячі» програми.

Символи ¬, ∧, ∨, ⇒, ∀ і ∃ ми вперше зустріли в частині про математичний запис. Тут ми з’ясуємо, як саме вони працюють, де в них найчастіше помиляються і як із них складається доведення.

1. Висловлення та значення істинності

Означення — висловлення

Висловлення — це твердження, про яке має сенс сказати, істинне воно чи хибне. Його значення істинності — 1 (істина) або 0 (хиба).

З простих висловлень P, Q, … за допомогою логічних зв’язок складаються складені висловлення. Істинність складеного висловлення залежить лише від істинності його частин.

2. Логічні зв’язки й таблиці істинності

Як працює зв’язка, найкраще показує таблиця істинності: по одному рядку для кожної комбінації значень P і Q. Дві змінні мають 2 · 2 = 4 комбінації, n змінних — 2ⁿ.

• Заперечення ¬P обертає значення.
• Кон’юнкція P ∧ Q («і») істинна, лише коли істинні обидві частини.
• Диз’юнкція P ∨ Q («або») істинна, коли істинна хоча б одна — або обидві.
• Імплікація P ⇒ Q («якщо…, то») хибна лише в одному випадку: P істинне, а Q — ні.
• Еквівалентність P ⇔ Q істинна, коли обидві частини мають однакове значення.
• Виключне «або» P ⊕ Q (XOR) істинне, коли істинна рівно одна з них.

3. Імплікація: найпоширеніша пастка

Означення — обернена імплікація й контрапозиція

Для імплікації P ⇒ Q оберненою імплікацією є Q ⇒ P, а контрапозицією — ¬Q ⇒ ¬P.

Теорема. Імплікація еквівалентна своїй контрапозиції, але не оберненій імплікації.

Таблиця показує це без суперечок: стовпці імплікації та контрапозиції однакові, обернена імплікація відрізняється у двох рядках.

Друга пастка — рядки з P = 0: коли припущення хибне, імплікація істинна, хоч би яким було Q. «Якщо 7 — парне, то я Папа Римський» — істинне висловлення. Звучить дивно, але має сенс: імплікація обіцяє щось лише про ситуацію, коли P істинне, і цю обіцянку неможливо порушити, коли P хибне.

4. Тавтології та еквівалентні висловлення

Означення — тавтологія, суперечність, еквівалентність

Тавтологія — це складене висловлення, істинне за будь-яких значень змінних (напр. P ∨ ¬P). Суперечність завжди хибна (P ∧ ¬P).

Висловлення A і B логічно еквівалентні, A ≡ B, якщо A ⇔ B — тавтологія: вони мають однаковий стовпець у таблиці істинності.

Так можна перевірити закони де Моргана з частини про множини: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. Стовпці однакові:

Перевіряти тавтологію таблицею надійно, але для n змінних це означає 2ⁿ рядків. Для 300 змінних це більше рядків, ніж атомів у Всесвіті. Питання, чи можна висловлення взагалі виконати (задача SAT), — одна з найвідоміших важких задач інформатики.

5. Чому XOR зупинив перші нейронні мережі

Намалюймо чотири комбінації P і Q як точки на площині й розфарбуймо їх за результатом. І для «і», і для «або» зелені точки можна відокремити від помаранчевих однією прямою. Для XOR це неможливо — зелені точки лежать на одній діагоналі, а помаранчеві на іншій:

P ∧ Q

P ∨ Q

P ⊕ Q

Перцептрон, найпростіша нейронна мережа, уміє розділяти точки лише прямою. 1969 року Мінський і Пейперт показали, що через це він не впорається навіть із такою простою функцією, як XOR, і інтерес до нейронних мереж на роки згас. Рішення — додати шар: XOR можна скласти з простіших функцій, (P ∨ Q) ∧ ¬(P ∧ Q), і двошарова мережа це вміє. Тут починається історія глибинного навчання.

6. Предикати й квантори

Означення — предикат і квантори

Предикат P(x) — це висловлення зі змінною: для кожного x із заданої множини він стає висловленням («x — парне»).

∀x ∈ M : P(x) істинне, коли P(x) виконується для всіх x ∈ M. ∃x ∈ M : P(x) істинне, коли воно виконується хоча б для одного.

Порядок різних кванторів має значення: ∀x ∃y : P(x, y) загалом не означає того самого, що ∃y ∀x : P(x, y).

Означення в ШІ сповнені кванторів. Допустима евристика з частини про пошук — це «∀n : h(n) ≤ h*(n)», і щоб її спростувати, досить одного стану, де оцінка перебільшує.

7. Що таке доведення

Означення — доведення і modus ponens

Доведення твердження T — це скінченна послідовність висловлень, яка закінчується T і в якій кожне висловлення або є припущенням (аксіомою, раніше доведеною теоремою), або випливає з попередніх за правилом виведення.

Основне правило виведення — modus ponens: з P і P ⇒ Q випливає Q. Правило коректне, бо (P ∧ (P ⇒ Q)) ⇒ Q — тавтологія.

8. Види доведень

Пряме доведення

Від припущень крок за кроком доходимо до твердження. Твердження: сума двох парних чисел парна. Доведення: парні числа — це 2a і 2b для цілих a, b. Їхня сума дорівнює 2a + 2b = 2(a + b), тобто подвоєному цілому числу — парному числу. ∎

Доведення контрапозицією і від супротивного

Замість P ⇒ Q доводимо еквівалентне ¬Q ⇒ ¬P — або припускаємо, що твердження хибне, і доходимо до абсурду. Твердження: простих чисел нескінченно багато. Доведення від супротивного (Евклід): якби їх було скінченно багато, p₁, …, p_k, візьмемо N = p₁ · … · p_k + 1. Жодне p_i не ділить N — завжди залишається 1. Отже, N має простий дільник, якого немає в списку. Суперечність. ∎

Контрприклад

Твердження «для всіх» спростовується одним прикладом. «Кожне непарне число, більше за 1, просте» виконується для 3, 5 і 7 — і падає на 9 = 3 · 3. Три приклади нічого не доводять, один контрприклад спростовує.

Математична індукція

Означення — принцип математичної індукції

Якщо виконується P(1) (база) і для кожного n ≥ 1 виконується P(n) ⇒ P(n + 1) (крок індукції), то P(n) виконується для всіх n ∈ ℕ.

Твердження: 1 + 2 + … + n = n(n + 1)/2. База: для n = 1 ліворуч 1, а праворуч 1 · 2/2 = 1. Крок: якщо формула виконується для n, то 1 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2, а це формула для n + 1. ∎ Той самий результат показує й малюнок: дві сходинки з крапок разом утворюють прямокутник n × (n + 1).

В інформатиці індукцією доводять правильність алгоритмів: «після k кроків циклу виконується…». Так доводять, наприклад, що UCS розгортає стани в неспадному порядку вартості — і тому знаходить найдешевший шлях.

9. Логіка в штучному інтелекті

• Символьний ШІ — перші системи штучного інтелекту були логічними: знання, записані як правила «якщо–то», і виведення за modus ponens. На цьому трималися експертні системи вісімдесятих років.
• SAT-розв’язувачі розв’язують задачу «чи можна виконати це висловлення?» для мільйонів змінних — вони планують, перевіряють апаратне забезпечення і шукають помилки в програмах.
• Верифікація ШІ — логікою доводять властивості систем: що автопілот ніколи не дасть двох суперечливих команд або що нейронна мережа не змінить рішення через непомітний шум.
• Мовні моделі й доведення — сучасні моделі вміють писати доведення, а їх потім перевіряють формальні інструменти, які механічно перевіряють кожен крок.

10. Підсумок

• Висловлення або істинне, або хибне; зв’язки ¬ ∧ ∨ ⇒ ⇔ ⊕ точно визначені таблицею істинності.
• Імплікація еквівалентна контрапозиції, а не оберненій імплікації — і з хибним припущенням вона завжди істинна.
• XOR неможливо розділити однією прямою, тому нейронній мережі потрібно більше шарів.
• Порядок кванторів має значення; твердження «для всіх» спростовує один контрприклад.
• Доведення — це ланцюжок перевірюваних кроків: пряме, контрапозицією, від супротивного або індукцією.

Маєте іншу думку? Напишіть на support@coden-app.com.