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

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

•(нет). Такое высказывание, как, называется отрицанием высказывания. ^итерал представляет собой либо атомарное высказывание (положительный литерал), либо отрицаемое атомарное высказывание (отрицательный литерал).

• (и). Высказывание, основной связкой которого является л, такое как , называется конъюнкцией; его части называются конъюнктами.

(Символнапоминает букву "А" в слове "And" — "И".)

•    v (или). Высказывание, в котором используется связка, такое как , называется дизъюнкцией дизъюнктов

и W2,2 (Исторически обозначение v произошло из латинского слова "vel", которое означает "или". Большинство людей находят, что форму этой связки проще всего запомнить как перевернутый символ.)

•(влечет за собой). Такое высказывание, как, называется импликацией (или условным высказыванием). Его предпосылкой, или антецедентом, является, а его заключением, или консек-вентом, является. Импликации называют также правилами, или утверждениями if—then (если—то). В других книгах символ импликации иногда записывается как

•(если и только если). Высказывание наподобиеназывается двухсторонней импликацией.

Формальная грамматика пропозициональной логики показана в листинге 7.2; те, кто не знаком с системой обозначений BNF, должны обратиться за дополнительными сведениями на с. 1.

Листинг 7.2. Грамматика высказываний пропозициональной логики в форме BNF (Backus-Naur Form — форма Бэкуса-Наура)