Математическая логика и теория алгоритмов

знака & связывает наименьшие формы, окружающие это вховдение; затем (т.е. после расстановки всех скобок, относящихся ко всем вхож­ дениям знаков 1 и &) каждое вхождение знака v связывает наимень­ шие формы, окружающие это вхождение, и аналогично для и s . При применении этого правила к одной и той же связке продвигаемся слева направо. Пример. В форме А='] А&В:=>Су~\ D скобки восстанавливаются следующими шагами: AЦ^A)&B=>Cv(]D); АЦ(\А)&В)^СУ(]0)- A^i(]A)&B)^(Cv(]D)y, A^(((]A)&B)=>iCv(\D))); (JK((1^4)&5)=>(C V (1D)))). Однако не всякая форма может быть записана без скобок. Например, нельзя опустить оставшиеся скобки в формах: A&(B=i-Q, А^(В=>С), liAvB). Приходится порой простые мысли доказывать всерьез, как теоремы. О. Сулеймепов* § 4. Тавтологии (общезначимые формулы). Противоречия Тавтологией {тождественно истинной пропозициональной формой или общезначимой формулой) называется пропозициональная форма, которая принимает значение И при любой совокупности ис­ тинностных значений пропозициональных букв, входящих в нее. Таблица истинности тавтологии имеет результирующий стол­ бец, состоящий только из И. Примером тавтологии является пропозициональная форма Aw] А, в чем легко убедиться, составив таблицу истинности. Другие примеры тавтологий: А^А, (А=В)= {В=А). ' * Казахстанский поэт. 21