КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Определение 9.2
Определение 9.1. 1. Каждый символ переменного из Х или константы из σ0 есть терм. 2. Если f — символ n -арной операции из σ и t 1, …, tn — термы, то слово f (t 1, …, tn) есть терм. 3. Других термов нет. Таким образом, множество термов для М (σ) есть минимальное подмножество слов в алфавите Ҩ, содержащее множество σ È X и замкнутое относительно образования слов по правилу 2. Если вместо переменных из Х в терм t подставить элементы из М и произвести все указанные в t операции, то мы получим элемент из М, называемый значением терма t. Следовательно, терм t определяет функцию на M, зависящую от тех переменных, которые входят в t. Так, если M = N и σ = {0, 1, +}, то термами могут быть представлены все многочлены над N. Теперь определим понятие формулы. В формулах нам необходимо будет различать свободные и связанные вхождения переменных. Эти понятия удобнее определить параллельно с определением формулы. 1. Любой символ нуль-местного предиката σ есть формула. 2. Если р — символ n -местного предиката из σ, а t 1, …, tn — термы, то слово p (t 1, …, tn) есть формула. 3. Если А и В — формулы, то слова (A) & (B), (A) v (B), (A) -> (B), ┐(А)*[1] также являются формулами. В них каждое вхождение переменной является вхождением в формулу А или В и считается таким же (свободным или связанным), каким оно было соответственно в А или В. 4. Если А — формула, в которой есть свободное вхождение переменной xi, то слова " xi (A) и $ xi (A) являются формулами, в которых все вхождения переменных, отличных от xi, называются так же, как и в А, а все вхождения переменной xi называются связанными. При этом формула А называется областью действия записанного перед ней квантора " или $ по переменной xi.
5. Других формул нет. Формулы, определенные в пунктах 1-2, называются элементарными. Все вхождения переменных в элементарные формулы называются свободными. Замечание. В приведенном определении формулы на алгебраической системе М (σ) от М, по существу, использовалось лишь множество выделенных элементов σ0. Поэтому формулу М (σ) можно рассматривать также и как формулу на любой другой алгебраической системе сигнатуры σ0. В связи с этим формулы на алгебраической системе М (σ) называют просто формулами алгебры предикатов сигнатуры σ. Число всех логических операций, участвующих в записи формулы А, назовем рангом формулы А и обозначим через r (A). В частности, r (A) = 0 в том и только том случае, когда А — элементарная формула. Рассмотрим пример. Пусть р 1, р 2 — символы двухместных предикатов. Тогда выражение " x 1(($ x 1(p 1(x 2, x 1))) v (" x 2(()))) (9.1) есть формула, поскольку p 1(x 2, x 1), p 2(x 1, x 2) являются формулами по пункту 2, это элементарные формулы. Тогда есть формула по пункту 3, $ x 1(p 1(x 2, x 1)) и есть формулы по пункту 4 и, далее ($ x 1(p 1(x 2, x 1))) v (" x 2()) есть формула по пункту 3. В ней последнее вхождение х 1 свободно, а потому (9.1) есть формула по пункту 4. Заметим, что в формуле (9.1) все вхождения переменной х 1 связанные, первое вхождение переменной х 2 свободно, остальные — связанные. Число скобок при записи формул можно уменьшить, если условиться: не заключать в скобки элементарные формулы; не заключать в скобки формулу, над которой находится знак отрицания; считать, что операция & сильнее Ú, обе эти операции сильнее ®, а операции навешивания кванторов сильнее всех других операций; не заключать в скобки большие латинские буквы, являющиеся обозначениями формул; опускать скобки в формулах вида (…((A 1 & A 2) & A 3)…) & Ak, (…((A 1 v A 2) v A 3)…) v Ak; записывать формулу δ1 x 1(δ2 x 2(…(δ kxkA)…)) с кванторами δ1, …, δ k в виде δ1 x 1δ2 x 2 … δ kxkA и в виде δ1 x 1, x 2, …, xkA при совпадении кванторов δ1, …, δ k.
При указанных соглашениях формулу (9.1) можно записать в виде " x 1($ x 1 p 1(x 2, x 1) v " x 2 ). В дальнейшем для сокращения иногда будем опускать знак &, т.е. вместо А & В писать АВ. Если А — формула сигнатуры σ, то любое ее подслово, являющееся формулой, называют подформулой формулы А. Подробнее понятие подформулы можно определить индукцией по рангу формулы.
Дата добавления: 2014-12-29; Просмотров: 366; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |