[МУЗЫКА] Продолжаем курс математической логики. В этой лекции мы рассмотрим проблему нахождения логического следствия из фактов. Основным вопросом, который мы будем рассматривать в этой лекции, является следующий: какой вывод можно сделать из всей имеющейся информации? Рассмотрим концепцию «возможных миров», которая введена еще Готфридом Лейбницем в XVII веке. «Возможные миры» — это структуры для логического анализа. Фактически, каждый «мир» — это некоторая ситуация, в которой атомарные утверждения — атомы — принимают конкретное истинностное значение. Так, например, в «мире» w0 атомы p и q истинны, а r — ложный. В «мире» w2 все атомы являются истинными. w3 — только q и r истинны, а p является ложным. Обычно те атомы, которые имеют значение «ложь», в этих «мирах» не показываются. Ясно, что при конкретной интерпретации атомарных утверждений одни формулы, построенные из этих атомов, истинны, а другие — нет. Некоторые формулы, например A∨¬ A, истинны в каждом «возможном мире». Такие формулы называются тавтологиями. Некоторые формулы, например A∧¬ A, в каждом «возможном мире» ложны. Такие формулы называются противоречивыми, или невыполнимыми. Рассмотрим очень важное определение в логике высказываний. Формула R называется логическим следствием множества формул, или гипотез U, если в любом «мире», то есть на любой интерпретации атомарных утверждений, в котором все формулы из U истинны, R тоже истинна. Это обозначается вот таким значком. Этот символ введён американским логиком Стефеном Клини в прошлом веке. Те «миры», на которых формула R истинна, называются моделями этой формулы. Такая запись означает, что в любом «возможном мире» при любой возможной интерпретации атомарных утверждений высказывание R выполняется, то есть R — тавтология, всегда истинная формула. Формула называется противоречивой, или невыполнимой, если она ложна в любом «мире» при любой интерпретации входящих в неё атомов. Рассмотрим понятие максимально сильного следствия из фактов. Рассмотрим следующее утверждение. Формула F, которая представлена как конъюнкция F1∧...∧Fn, является логическим следствием множества формул {F1, ..., Fn}, то есть справедливо вот такое соотношение F1∧...∧Fn. Доказательство этого утверждения достаточно просто, оно непосредственно следует из определения логического следования. Действительно, на всех интерпретациях, на которых истинны все формулы {F1, ..., Fn}, истинна и конъюнкция этих формул. Рассмотрим другое утверждение. Для любых формул F1, ..., Fn и R утверждение такого вида истинно тогда и только тогда, когда вот такая импликация является общезначимой, или тавтологией. Доказательство этого утверждения также непосредственно следует из опеределения логического следствия и свойства операции импликации. Наконец, введём следующее определение. Конъюнкция формул F1∧...∧Fn называется максимально сильным следствием множества формул {F1, ..., Fn}. Такое определение дано конъюнкции формул неслучайно. Любая формула, которая является логическим следствием множества формул {F1, ..., Fn}, является также и логическим следствием конъюнкции этих формул.