Исчисление высказываний

Исчисление высказываний (ЧВ) согласно поданной в разделе 1 схемой означаеться таким образом.

1. Алфавит исчисления высказываний состоит из элементарных и переменных высказываний (пропозицийних переменных) : a, b, c, d,...,x, y, z (возможно с индексами), знаков логических операций ,,, и круглых скобок ( но ).

2. Понятие формулы означаеться аналогично алгебре высказываний.

а) все пропозицийни переменные и элементарные высказывания являются формулами;

б) если A и B - формулы, то выражения(AB), (AB) (A) (AB) также являются формулами;

в) других формул, чем построены по правилам а) и б) нет.

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

Заметим также, что с целью уменьшения количеству (экономии) скобок в формулах вводят порядок выполнения (или приоритеты, старшинство) операций. В частности, конечно, опускают внешние скобки формул и вместо (A) записывают A;

3. Аксиомами исчисления высказываний будут такие формулы:

A1. a(ba)

A2. (ab)((a(bc))(ac))

A3. (ab)a

A4. (ab)b

A5. (ab)((ac)(a(bc)))

A6. a(ab)

A7. b(ab)

A8. (ac)((bc)((ab)c))

A9. (ab)(ba)

A10. aa

4. Правилами выведения являются:

1) правило подстановки. Если A - выводная формула, которая содержит букву p (обозначим этот факт A(p)), то выводной является и формула A(B), что добывается из A заменой всех вхождений буквы p на произвольную формулу B; записывается

A(p)



Вернуться назад