Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Синтаксис логики Печать

Синтаксис пропозициональной логики определяет допустимые высказывания. Атомарные высказывания (неделимые синтаксические элементы) состоят из одного пропозиционального символа. Каждый такой символ обозначает высказывание, которое может быть либо истинным, либо ложным. Для обозначения подобных символов в данном разделе используются прописные буквы: Р, Q, R и т.д. Эти обозначения являются произвольными, но часто выбираются таким образом, чтобы они имели для читателя какое-то мнемоническое значение. Например, символ W1,3, может использоваться для обозначения высказывания, согласно которому вампус находится в квадрате [1,3]. (Напомним, что символы, W1,3, подобные являются атомарными; это означает, что W, 1 и 3 не следует рассматривать как осмысленные части этого символа.) Существуют два пропозициональных символа, имеющих постоянный смысл: True — тождественно истинное высказывание, а False — тождественно ложное высказывание.

Сложные высказывания формируются из более простых высказываний с помощью логических связок. Широко применяются пять описанных ниже логических связок.

  • ¬ (нет). Такое высказывание, как ¬W1,3, называется отрицанием высказывания W1,3. Литерал представляет собой либо атомарное высказывание (положительный литерал), либо отрицаемое атомарное высказывание (отрицательный литерал).
  • ˆ (и). Высказывание, основной связкой которого является ˆ, такое как W1,3 ˆ P3,1, называется конъюнкцией; его части называются конъюнктами. Символ ˆ напоминает букву "А" в слове "And" — "И".)
  • v (или). Высказывание, в котором используется связка v, такое как (W1,3 ˆ P3,1) v W2,2, называется дизъюнкцией дизъюнктов (W1,3 ˆ P3,1) и W2,2. (Исторически обозначение v произошло из латинского слова "vel", которое означает "или". Большинство людей находят, что форму этой связки проще всего запомнить как перевернутый символ ˆ.)
  • => (влечет за собой). Такое высказывание, как (W1,3 ˆ P3,1) => ¬W2,2, называется импликацией (или условным высказыванием). Его предпосылкой, или антецедентом, является (W1,3 ˆ P3,1), а его заключением, или консеквентом, является ¬W2,2. Импликации называют также правилами, или утверждениями ifthen (если—то). В других источниках символ импликации иногда записывается как →.
  • <=> (если и только если). Высказывание наподобие W1,3 <=>W2,2 называется двухсторонней импликацией.

Формальная грамматика пропозициональной логики показана в листинге;


Грамматика высказываний пропозициональной логики в форме BNF (Backus-Naur Form — форма Бэкуса-Наура)
            Sentence —> AtomicSentence | ComplexSentence
  AtomicSentence —> True | False | Symbol
               Symbol
> P | Q | R | ...
ComplexSentence —> UlSentence
                            | ( Sentence a Sentence )
                            | ( Sentence v Sentence )
                            | ( Sentence => Sentence )
                            | ( Sentence <=> Sentence )


Обратите внимание на то, что эта грамматика предъявляет строгие требования к использованию круглых скобок: каждое высказывание, сформированное с помощью бинарных связок, должно быть заключено в круглые скобки. Это гарантирует полную непротиворечивость синтаксиса. Такое требование также означает, что следует писать, например, ((A ˆ B) => C), например, вместо A ˆ B => C. Но для удобства чтения мы будем часто опускать круглые скобки, полагаясь вместо них на использование порядка предшествования связок. Это аналогично правилам предшествования, используемым в арифметике, например, выражение ab+c читается как ((ab) +с), а не как а(b+с), поскольку операция умножения имеет более высокий приоритет, чем сложение. Порядок предшествования в пропозициональной логике (от высшему к низшему) состоит в следующем: ¬, ˆ, v, => и <=>. Поэтому высказывание
¬P v Q ˆ R => S эквивалентно высказыванию ((¬P) v (Q ˆ R)) => S

Определение порядка приоритета не позволяет устранить неоднозначность при чтении таких высказываний, как A ˆ B ˆ C, которое может быть прочитано как ((A ˆ B) ˆ C) или (A ˆ (B ˆ C)). Но поскольку эти два прочтения, согласно семантике, описанной в следующем разделе, означают одно и то же, допускаются высказывания, подобные A ˆ B ˆ C.

Разрешаются также высказывания наподобие A v B v C и A <=> B <=> C. А такие высказывания, как A => B => C, не допускаются, поскольку для них соответствующие два прочтения имеют разный смысл; мы настаиваем на том, что в этом случае должны использоваться круглые скобки. Наконец, иногда вместо круглых скобок используются квадратные, если это позволяет немного упростить понимание данного высказывания.