Вопрос 15
Пропозициональная логика: очень простая логика
В этом разделе будет представлена очень простая логика, называемая
пропозициональной логикой. Здесь рассматривается синтаксис пропозициональной логики и ее семантика— способ определения истинности высказываний.
Синтаксис
Синтаксис пропозициональной логики определяет допустимые высказывания.
Атомарные высказывания (неделимые синтаксические элементы) состоят из
одного пропозиционального символа. Каждый такой символ обозначает
высказывание, которое может быть либо истинным, либо ложным. Для обозначения подобных символов в данном разделе используются прописные буквы: Р, Q, R и т.д. Эти
обозначения являются произвольными, но часто выбираются таким образом, чтобы они
имели для читателя какое-то мнемоническое значение. Например, символ W 1;3
может использоваться для обозначения высказывания, согласно которому вампус
находится в квадрате [1,3]. (Напомним, что символы, подобные W 1;3 , являются
атомарными; это означает, что W, 1 и 3 не следует рассматривать как осмысленные
части этого символа.) Существуют два пропозициональных символа, имеющих
постоянный смысл: True — тождественно истинное высказывание, a False —
тождественно ложное высказывание.
¬ (нет). Такое высказывание, как ¬Wl;3, называется отрицанием
высказывания Wl;3. Литерал представляет собой либо атомарное высказывание
(положительный литерал), либо отрицаемое атомарное высказывание
(отрицательный литерал).
^ (и). Высказывание, основной связкой которого является ^, такое как
W 1;3^P3;1 называется конъюнкцией; его части называются конъюнктами.
(Символ ^ напоминает букву "А" в слове "And" — "И".)
• v (или). Высказывание, в котором используется связка v, такое как
(W 1;3^P3;1)v W2;2, называется дизъюнкцией дизъюнктов (W 1;3^P3;1)
и W2;2. (Исторически обозначение v произошло из латинского слова "vel",
которое означает "или". Большинство людей находят, что форму этой связки
проще всего запомнить как перевернутый символ ^.)
• => (влечет за собой). Такое высказывание, как (Wl;3 ^ P3;l) => ¬W2; 2,
называется импликацией (или условным высказыванием). Его предпосылкой,
или антецедентом, является (Wl;3 ^ P3;l Wli3 л p3,i) а его заключением, или консек-
вентом, является ¬W2; 2. Импликации называют также правилами, или
утверждениями if—then (если—то). В других книгах символ импликации иногда
записывается как э(тут символ принадлежит,только в обратную сторону) или —>.
• <=> (если и только если). Высказывание наподобие W1;3 <=> W2;2 называется
двухсторонней импликацией.
Семантика
Определив синтаксис пропозициональной логики, мы можем приступить к
определению ее семантики. Семантика диктует правила выявления истинности
высказывания по отношению к конкретной модели. В пропозициональной логике любая
модель просто фиксирует истинностное значение (true или false) для каждого
пропозиционального символа. Семантика пропозициональной логики должна определять, как следует вычислять истинностное значение любого высказывания при наличии модели. Эта процедура выполняется рекурсивно. Все высказывания формируются из атомарных
высказываний и пяти связок, поэтому необходимо указать, как следует вычислять истинность атомарных высказываний, а затем — как вычислять истинность высказываний, сформированных с помощью каждой из этих пяти связок. Задача вычисления истинности атомарных высказываний, как показано ниже, является простой.
• Высказывание True истинно в любой модели, а высказывание False ложно в
любой модели.
• Истинностное значение любого другого пропозиционального символа должно
быть указано непосредственно в модели.
Для определения истинности сложных высказываний применяются правила,
подобные приведенному ниже.
• Для любого высказывания s и любой модели m высказывание ¬s является
истинным в модели m тогда и только тогда, когда s является ложным в модели т.
• Высказывание True истинно в любой модели, а высказывание False ложно в
любой модели.
• Истинностное значение любого другого пропозиционального символа должно
быть указано непосредственно в модели. Например, в модели т1 приведенное
выше высказывание Р1/2 является ложным.
Для определения истинности сложных высказываний применяются правила,
подобные приведенному ниже.
• Для любого высказывания s и любой модели т высказывание -is является
истинным в модели т тогда и только тогда, когда s является ложным в модели т.