Пропозициональные формулы

Под высказыванием (proposition) понимается утверждение, относительно которого можно сказать истинно оно или ложно, при этом оно не может быть и истинным, и ложным одновременно. Из простых высказываний с помощью логических операций, рассмотренных выше, строятся более сложные высказывания.

В исчислении высказываний рассмотренные выше символы логических (булевских) операций (функций) ù, &, Ú, →, º называют пропозициональными или логическими связками.

Логические (булевские) переменные, обозначаемые буквами латинского алфавита (иногда с индексами), называют пропозициональными переменными (пропозициональ­ными буквами).

Алфавит языка исчисления высказываний состоит из пропозициональных переменных (букв), логических связок и скобок: (,).

Правильно построенные выражения языка исчисления высказываний называются пропозициональными формулами или просто формулами.

Все пропозициональные переменные являются формулами.

Правила построения языка исчисления высказыва­ний задают его синтаксис.

Так как буквы, входящие в формулу, сами могут быть формулами, то каждую формулу можно рассматривать как схему бесконечного множества формул, получаемых заменой пропозициональных букв на соответствующие им формулы. Для того чтобы указать это, используют вместо термина пропозициональная формула термин пропозициональная форма.

Скобки (определяющие структуру формулы) могут опускаться в соответствии со сле­дующим приоритетом логических связок: ù, &, Ú, →, º. Любое вхождение знака ù относится к наименьшей формуле (пропозициональной форме), следующей за ним; после расстановки всех скобок для формул, содержащих знак ù, каждое вхождение знака & связывает наименьшие формулы, стоящие рядом с этим знаком; затем то же самое относится к знаку Ú, далее к → – импликации и потом к знаку º – эквива­лентности. В случае равного приоритета скобки расставляются слева направо.

Так например, пропозициональная формула A Ú B→C Ú D&E должна пониматься как ((A Ú В) → (С Ú (D & E))), поскольку сначала выполняется (применяется) опера­ция &, которая «старше», чем операция Ú, затем левая дизъюнкция, т. к. направле­ние чтения формул слева направо, потом правая дизъюнкция и далее импликация.

Приписывание значений истинности (true или false) пропозициональным переменным называется интерпретацией этих переменных. Под интерпретацией формулы понимается приписывание значений истинности переменным, входящим в эту фор­мулу.

Пропозициональная формула, истинная при любых значениях истинности входящих в нее пропозициональных переменных, т. е. истинная при любых интерпретациях, называется тождественно истинной, или общезначимой пропозициональной формулой, или тавтологией.

Пропозициональная формула, ложная при любых значениях истинности входя­щих в нее пропозициональных переменных, называется тождественно ложной, или невыполнимой пропозициональной формулой, или противоречием.

Пропозициональная формула, которая может принимать истинные значения при некоторых интерпретациях, называется выполнимой. Интерпретации, для кото­рых пропозициональная формула принимает истинное значение, называются ее моделями.