Логіка висловлювань

Логічний наслідок

Формула \( p \) є логічним наслідком множини формул \( S \) тоді і тільки тоді, коли кожна інтерпретація \( M \), що задовольняє всі формули в \( S \), також задовольняє \( p \):

\[S \models p\]

Іншими словами, \( p \) є логічним наслідком \( S \), якщо \( p \) має бути істинною в кожній інтерпретації, яка робить усі формули в \( S \) одночасно істинними. Розглянемо наступний приклад. Нехай:

• \( S = \{A,\, A \rightarrow B\} \)
• \( p = B \)

Ми хочемо перевірити, чи є \( B \) логічним наслідком \( S \). Таблиця істинності для формул у \( S \) є наступною:

\[ \begin{array}{cc|c} A & B & A \rightarrow B \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \end{array} \]

Єдиним рядком, у якому і \( A \), і \( A \rightarrow B \) є істинними, є перший, і в цьому рядку \( B \) також є істинною. Отже, ми отримуємо висновок, що \( S \models B \), і \( B \) дійсно є логічним наслідком \( S \).

Ця форма міркування, відома як modus ponens, є одним із найфундаментальніших правил виведення в пропозиційній логіці. Поняття логічного наслідку відіграє центральну роль не тільки у формальній логіці, а й у штучному інтелекті: воно лежить в основі обґрунтованості аргументів, правильності автоматизованого міркування та надійності висновків, зроблених системами ШІ з формалізованих знань.

Правила виведення

Поняття логічного наслідку, введене в попередньому розділі, визначає, коли формула має бути істинною за умови заданого набору засновків. Правила виведення — це схематичні моделі, які дозволяють виводити висновок з одного або кількох засновків, за умови, що ці засновки є істинними. Кожне правило є правильним у тому сенсі, що його висновок є логічним наслідком його засновків. Нижче представлено три найфундаментальніші правила виведення логіки пропозицій.

Modus ponens стверджує, що якщо \( p \) є істинним і імплікація \( p \rightarrow q \) є істинною, то \( q \) має бути істинним. У схематичній формі:

\[ \frac{p \qquad p \rightarrow q}{q} \]

Modus tollens стверджує, що якщо \( q \) є хибним і імплікація \( p \rightarrow q \) є істинною, то \( p \) має бути хибним. У схематичній формі:

\[ \frac{\neg q \qquad p \rightarrow q}{\neg p} \]

Гіпотетичний силогізм стверджує, що якщо \( p \rightarrow q \) та \( q \rightarrow r \) обидва є істинними, то \( p \rightarrow r \) також є істинним. У схематичній формі:

\[ \frac{p \rightarrow q \qquad q \rightarrow r}{p \rightarrow r} \]

У кожній схемі формули над горизонтальною лінією є засновками, а формула під нею — висновком.

Ці три правила не є незалежними один від одного. Modus tollens, наприклад, може бути виведений з modus ponens разом із еквівалентністю \( (p \rightarrow q) \equiv (\neg q \rightarrow \neg p) \), відомою як контрапозиція. Гіпотетичний силогізм, подібно до цього, випливає з двох послідовних застосувань modus ponens.

Як ілюстрацію, розглянемо наступні засновки:

• \( p = \) йде дощ.
• \( q = \) земля мокра.
• \( r = \) матч скасовано.

Припустимо, ми знаємо, що \( p \rightarrow q \) та \( q \rightarrow r \). За допомогою гіпотетичного силогізму ми можемо зробити висновок, що \( p \rightarrow r \). Якщо йде дощ, то матч скасовано. Якщо ми додатково знаємо, що \( p \) є істинним, одне застосування modus ponens дає \( r \): матч скасовано.

Нормальні форми

Кожну пропозиційну формулу можна переписати в логічно еквівалентній формі, що має регулярну синтаксичну структуру. Двома найважливішими такими структурами є кон'юнктивна нормальна форма та диз'юнктивна нормальна форма.

• Літералом є або атомарна пропозиція, або її заперечення. Якщо задано атомарну пропозицію \( p \), то і \( p \), і \( \neg p \) є літералами.

• Формула перебуває в кон'юнктивній нормальній формі (КНФ), якщо вона є кон'юнкцією диз'юнктів, де кожен диз'юнкт є диз'юнкцією літералів:

\[ (l_{1,1} \lor \cdots \lor l_{1,k}) \wedge (l_{2,1} \lor \cdots \lor l_{2,m}) \wedge \cdots \]

Формула перебуває в диз'юнктивній нормальній формі (ДНФ), якщо вона є диз'юнкцією кон'юнктов, де кожен кон'юнкт є кон'юнкцією літералів:

\[ (l_{1,1} \wedge \cdots \wedge l_{1,k}) \lor (l_{2,1} \wedge \cdots \wedge l_{2,m}) \lor \cdots \]

Можна показати, що кожна пропозиційна формула є логічно еквівалентною деякій формулі в КНФ та деякій формулі в ДНФ. Перетворення завжди можна виконати, застосовуючи наступні стандартні еквівалентності: усунення подвійного заперечення, закони де Моргана та дистрибутивність \( \wedge \) відносно \( \lor \) та \( \lor \) відносно \( \wedge \).

Найбільш вживаними еквівалентностями при перетворенні в нормальну форму є наступні: \( \neg \neg p \equiv p \), \( \neg(p \wedge q) \equiv \neg p \lor \neg q \), \( \neg(p \lor q) \equiv \neg p \wedge \neg q \), а також дистрибутивні закони \( p \wedge (q \lor r) \equiv (p \wedge q) \lor (p \wedge r) \) та \( p \lor (q \wedge r) \equiv (p \lor q) \wedge (p \lor r). \)

Як приклад, розглянемо формулу \( \neg(p \lor q) \rightarrow r \). Використовуючи еквівалентність \( \varphi \rightarrow \psi \equiv \neg \varphi \lor \psi \), формулу можна переписати наступним чином:

\[ \neg(p \lor q) \rightarrow r \;\equiv\; \neg\neg(p \lor q) \lor r \;\equiv\; (p \lor q) \lor r \]

Отримана формула \( (p \lor q) \lor r \) є одним диз'юнктом і, отже, вже перебуває в кон'юнктивній нормальній формі. Таким чином, початкова формула еквівалентна формулі в КНФ \( p \lor q \lor r \).

Нормальні форми відіграють центральну роль в автоматизованому виведенні. Більшість алгоритмів перевірки виконуваності, включаючи широко використовувану процедуру DPLL, вимагають, щоб вхідна формула була представлена в КНФ.