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

Так, высказывательная форма р v Q(x) -> q является форму­ лой. В то же время высказывательная форма Зх Р(х) -» Q(x) не будет формулой, поскольку в формуле ЗхР(х) переменная х свя­ зана квантором существования, тогда как в формуле Q(x) эта же переменная свободна. . В чем ценность формальных теорий? Для описания каких объектов используется логика предикатов? Вообще говоря, ценность любой формальной теории заключа­ ется в возможности описывать с ее помощью произвольные объек­ ты и связи между ними. Теоремы. К числу основных равносильностей логики предика­ тов относят: 1. V хР(х) <=> ЗхР(х). 2. ЗхР(х) <=> \/хР(х). 3. \/хР(х) <=> ЗхР(х). 4. ЗхР(х) <=> \/хР{х). 5. Vx(/>(x) л Q(x)) <=> VxP(x) л Vx@(x). 6. Зх(Р(х) v Q(x)) <=> Зх/*(х) v 3xQ(x). Правила вывода исчисления предикатов: Правило заключения ( modus ponens) — правило, аналогичное тому, которое введено в исчислении высказываний. Правило обобщения (\/-введения, ug-правило) Я2: - ^ , где F -> VxG(x) G(x) содержит свободные вхождения х, тогда как F не содержит свободных х. Правило 3-введения (eg-правило) R3: ^ (* ) F 3xG(x) -» F Нарушение этих требований может привести к ложным выво­ дам, полученным из истинных высказываний. Например, даны предикаты Р(х): «натуральное х делится на 15», Q(x): «х делится на 5». Высказывание Р(х) -> Q(x) истинно для любых х е N. Приме­ ним для него правило обобщения. Имеем Р(х) -* \/xQ(x)\ «Если х делится на 15, то каждое число хделится на 5». Получили ложное утверждение, так как правило V-введения применимо к 0-мест- ным, а не к одноместным, как Р(х), предикатам. Можно доказанные теоремы делать новыми правилами вывода. Так, помимо правил V- и 3-введения можно ввести правила уда­ ления кванторов. Пусть выведена или дана формула 3 xF(x), например «Суще­ ствуют студенты, работающие по специальности». Из предметно­ го множества всех студентов выберем такого, о котором действи­ тельно известно, что он работает по специальности, и для него 236