Спирина, М.С. Дискретная математика

сложение. Символ 0 обозначает, что можно дополнить N одним элементом, называемым нулем, так, что Ухе N х + 0 = х. Выбор некоего элемента, т.е. приписывание ему какого-то свойства, иногда называют нулярной операцией в отличие от унарных и бинарных. 4. Левая и правая скобки предназначены для знаков препи нания. II. Рассмотрим синтаксис теории S, т.е. правила образования формул. Существуют два класса слов: термы и формулы. До сих пор мы не оговаривали особо, каким образом можно выделять множество формул, т.е. способы их задания. На этом конкретном примере покажем, что индуктивное задание является основным. Дадим индуктивное определение терма: 1.0 —терм. 2 . Х\, х2, ... — термы. 3. Если / — терм, то (г) — терм. 4. Если / и г — термы, т о / + г и / г — термы. 5. Других термов, кроме определенных согласно 1—4, нет. В привычном понимании термы —это имена существительные в широком смысле, т.е. имена и именные формы. Дадим индуктивное определение формулы: 1. Если / и г — термы, то / = г — элементарная формула. 2. Если А — формула, то А — тоже формула. 3. Если А и В — формулы, то (А) -» (В) — формула. 4. Если А — формула, то Ух {А) — формула. 5. Других формул, кроме определенных согласно 1—4, нет. Так, если х,, хъ 5 — термы, то + х2 = 5 •х, — формула, включающая в себя термы х, + х2 и 5 •Xj. Если хь х2, 5 —термы по п. 2 определения термов, х\ + х 2 и 5 ■Xi — термы по п. 4, зна­ чит, X] + х 2 = 5 • х, —формула по п. 1 определения формул. Форму­ ла (Х| + х 2 = 5х]) -> (4 • х, = х2) включает в себя две другие, причем скобки можно по договоренности убирать. Выражение Ух {А) станет формулой только после того, когда вместо А будет подставлена формула. В теории S недостаточно зна­ ков для выражения всех отношений. Например, отношение «боль­ ше» (х! > х2) может быть выражено формулой Зх 3 (х! = х 2 + х3). Тогда недостающие знаки для записи всех возможных отношений можно включать в теорию, но заимствовать их из метаязыка. Определив синтаксис теории S, включающий алфавит и пра­ вила образования термов и формул, необходимо определить и пра­ вила вывода новых предложений предмета этой теории, т.е. всех натуральных чисел. Так, для любых формул А, В, С теории S справедливы форму­ лы, называемые логическими аксиомами: Р\. А => (В =>А); Р 2: А => {В => С) => ((Д => В1 =* (А =* С)); Ру. (А => В) ^ ((А => В) => Д); 268