В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 44
Текст из файла (страница 44)
д) 1оя,/(х) > 1оа, р(х) «» 1(0 < а < 1) л (/(х) > О) л л (/(х) < я(х))] ч 1(а > 1) л (я(х) > 0) л (/(х) > р(х))] «» 1(0 < < а < 1) л (О < /(х) < я(х))] ч 1(а > 1) л Ях) > я(х) > 0)]. 212 л) !Ь([1(х)])! = я(х) «=» (Ях) > 0 л ]!»Ях))] = я(х)) ч (Г(х) < 0 л л !Ь(-1(х))] = я(х)) ч [я(х) > 0 л (!»(! ~(х)!) = я(х) ч — !»(],Дх)[) = = ~(Х))] '=' [ЯХ) > 0 л ((Л(1(Х)) > 0 л ЛЯХ)) = я(Х)) ч (Л(ДХ)) < < 0 л — ЬЩх)) = я(х)))] ч [Ях) < 0 л ((Ь(-1(х)) > 0 л !»(-Дх)) = = я(х)) ч (Ь(- Г(х)) < 0 л -л(-Дх)) = я(х)))] ч [я(х) > 0 л ((Ях) > > О л ЫУ(х)) = я(х)) ч (Ях) < О л Ь(-Ях)) = я(х)) ч (У(х) > О л л -Ь(1(х)) = а(х)) ч Ях) < 0 л -л(-»'(х)) = Я(х)))]. 10.14.
Запишите решение следующих неравенств и уравнений в виде последовательности равносильных предикатов: Зх+ 5 х+5 а) <1; д) !ой, — >-2; 2х — 4 Зх — 3 э б) 15 — х >х+1; е) !оа,„(х' — 5х+ 6) < 1; в) 1оаз <-2; ж) ! ! 2х' — х ! — 3 ! < 2х'+ х+ 5; х — 3 г) 1ой3 < — 2; х+5 з) ) х — ] 4 — х ! ] = 2х+ 4. х — 3 Зх+ 5 Зх+ 5 Зх+ 5 — 2х+ 4 Решение. а) <1<» — 1 <Ос» <О е» 2х-4 2х-4 2х-4 «» — < 0 <» (х + 9 > 0 л 2х — 4 < 0) ч (х + 9 < 0 л 2х- 4 > 0) е» х+9 2х — 4 е» ((х > — 9) л (х < 2)) ч ((х < — 9) л (х > 2)) «=» ( — 9 < х < 2) ч ЛОЖЬ «=» «= -9 < х < 2. Символом ЛОЖЬ обозначен тождественно ложный предикат.
Здесь использовано следующее свойство предикатов: дизъюнкция любого предиката Р(х) и тождественно ложного предиката равносильна предикату Р(х). б) /5 — х > х+ 1»» [х+ 1 > 0 л 5 — х > (х+ 1)2] ч [х+ 1 < 0 л 5— — х > 0]»» [(х > -1) л (х2 + Зх — 4 < 0)] ч [(х < -1) л (х < 5)] «» Нх > > -1) л (-4 < х < 1)] ч (х < -1) «=» (-1 < х < 1) ч (х < -1) «» (х < 1). Логика этих преобразований такова.
Предикат х < 5 является следствием предиката х < -1, т.е. предикат (х < -1) -» (х < 5) является тождественно истинным, а значит, и предикат (х < -1) -+ ((х < < — 1) л (х < 5)) также тождественно истинен. Поскольку, кроме того, предикат с обратной импликацией ((х < -1) л (х < 5)) -+ -+ (х < -1), очевидно, тождественно истинный, то приходим к равносильности предикатов (х<-1) л(х< 5) и х<-1, чем мы и воспользовались в процессе преобразований. й 11. Формализованное исчисление предикатов Алфавит (чистого) исчисления предикатов состоит из предметных переменных х„х,, ..., предметных констант (символы выделенных элементов) с„с„..., предикатных букв Р„Р,, ..., Ри ..., а также знаков логических связок ~ и л, кванторов»;«и 3 и скобок (, ).
213 Понятие 4оормулы определяется индуктивно: а) если Є— предикатная буква, гн ..., г„— предметные пере- менные и(или) константы, то Р„Ц, ..., г„) — формула; при этом все вхождения переменных в эту формулу называются свободными; б) если Гн У~ — формулы, то формулами являются ~Гн (Г, -+ -э Г2); причем все вхождения переменных, свободные в Гн У~, являются свободными и в формулах указанных видов; кроме того, можно считать, что в Г, и Г2 нет предметных переменных, кото- рые связаны в одной формуле и свободны в другой; в) если Г(х) — формула, содержащая свободные вхождения переменной х, то (Ъ'х)(Г(х)) и (Лх)(Г(х)) — формулы; при этом вхождения переменной х в них называются связанными; вхожде- ния же всех остальных предметных переменных в эти формулы остаются свободными (связанными), если они были свободными (связанными) в формуле Г(х) (формула Г(х) называется облас- тью действия квантора); г) никаких других формул, кроме тех, которые строятся по правилам а), б), в), нет.
Система аксиом исчисления предикатов состоит из двух частей. Первая — это аксиомы формализованного исчисления выска- зываний: (А1) Г-+ (6-+ Г); (А2) (Г-+ (6-+ Н)) -+ ((Г-+ 6) -+ (Г-э Н)); (АЗ) (~6-+-аГ) -+(~6-+ Г) -+ 6), где под Г, 6, Н понимаются уже любые формулы исчисления предикатов. Вторая группа аксиом (схем аксиом) — это собственно преди- катные аксиомы (схемы аксиом), т.е. аксиомы с кванторами. Выбе- рем в качестве них следующие (называемые аксиомами Бернайса): (РА1) (Ъ'х)(Г(х)) -+ Г(у); (РА2) Г(у) -+ (Лх)(Г(х)), где Г(х) — любая формула, содержащая свободные вхождения х, причем ни одно из них не находится в области действия квантора по у (если таковой имеется); формула Г(у) получена из Г(х) за- меной всех свободных вхождений х на у. К правилу вывода модус Ропепв (МР) из исчисления выска- зываний добавляются еще два правила вывода: Г -+ 6(х) (, )(6(х)) (1г-правило, или правило обобщения); 6(х) -+ Г Г (Э-правило, или правило конкретизации) при условии, что 6(х) содержит свободное вхождение х, а Г не содержит.
Построение выводов из аксиом. Формула 6 называется выво- димой из гипотез Гн ..., Г„с фиксированными вхождениями (в 214 гипотезы) свободных переменных, если существует такая конечная последовательность формул В„Вы ..., В„, ..., В, =- 6, каждая формула, которая является либо аксиомой, либо гипотезой, либо получена из предыдущих формул последовательности по одному из правил вывода. (Сама эта последовательность называется выводом б из гипотез Гп ..., Г„.) При этом, если В» есть первая гипотеза, встречающаяся в выводе, то дальше в этом выводе не могут быть использованы ч'- и Л-правила вывода по любой переменной х, которая входит свободно хотя бы в одну из гипотез.
Обозначение: Уь ..., Г ~- 6. Если гипотезы отсугствуют, то говорят, что б выводима из аксиом (или просто выводима), и называют б теоремой формализованного исчисления предикатов, и пишут»-6. 11.1. Приведите пример, подтверждающий существенность того требования к аксиомам (РА1) и (РА2), что Г(х) — любая формула, содержащая свободные вхождения х, причем ни одно из них не находится в области действия квантора по у (если таковой имеется). 11.2.
Приведите пример, подтверждающий существенность того требования к ч'-правилу и Б-правилу, что 6(х) содержит свободное вхождение х, а Г(х) — не содержит. 11.3. Докажите, что в ФИП из выводимости формулы Г(х), содержащей свободные вхождения х, ни одно из которых не находится в области действия квантора по у, следует выводимость формулы Г(у) (правило переименования свободных переменных). Р е ш е н и е. Построим вывод формулы Г(у) при условии выводимости формулы Г(х): (1) Г(х) (выводима по условию); (2) б (любая доказуемая формула, не содержащая свободных вхождений х (это ограничение понадобится на шаге (5))); (3) Г(х) -+ (6-» Г(х)) (аксиома (А1)); (4) б-+ Г(х) (МР: (1), (3)); (5) б-+ (чх)(Г(х)) (В-правило: (4)); (б) (чх)(Г(х)) (МР: (2), (5)); (7) (чх)(Г(х)) -+ Г(у) (аксиома (РА1)); (8) Г(у) (МР: (6), (7)).
11.4. Докажите, что в формализованном исчислении предикатов а) из выводимости формулы (Ъх)(Г(х)) следует выводимость формулы ('ву)(Г(у)); б) из выводимости формулы (Зх)(Г(х)) следует выводимость формулы (Зу)(Г(у)) при условии, что формула Г(х) не содержит свободных вхождений у и содержит свободные вхождения х, ни одно из которых не входит в область действия квантора по у (правила переименования связанных переменных).
Решение. а) Построим вывод формулы (Ъу)(Г(у)) из формулы (ех)(Г(х)). С учетом выводимости (из аксиом) последней формулы это будет доказывать выводимость первой формулы: 215 (1) (Ъх)(Р(х)) (выводима по условию); (2) (чх)(Р(х)) -+ Р(у) (аксиома (РА1)); (3) (чх)(Р(х)) -+ (~у)(Р(у)) (ч'-правило: (2)); (4) (Ъу)(Р(у)) (МР: (1), (3)). 11.5. Докажите, что следующие формулы являются теоремами формализованного исчисления предикатов, для чего постройте выводы этих формул из аксиом: а) (Ъх)(Р(х)) -+ Ях)(Р(х)); б) (Ъх)(~у)(Р(х, у)) <-э ('Фу)(Ъх)(Р(х, у)); в) (Лх)(Зу)(Р(х, у)) ++ (Лу)(Лх)(Р(х, у)); г) (Зх)(чу)(Р(х, у)) -+ (чу)(Зх)(Р(х, у)).
Р е ш е н и е. в) Укажем последовательность шагов вывода: (1) Р(и, е) -+ (Зх)(Р(х, у)) (аксиома (РА2)); (2) Р(и, и) -+ (Зу)(Лх)(Р(х, у)) (аксиома (РА2)); (3) (3а)(Р(и, и)) -+ (Лу)(Бх)(Р(х, у)) (Э-правило: (2)); (4) (Ли)(Ло)(Р(и, о)) -+ (Лу)(Лх)(Р(х, у)) (3-правило: (3)); (5) (Лх)(Бу)(Р(х, у)) -+ (Зу)(Лх)(Р(х, у)) (переименование переменных); (6) (Зу)(3х)(Р(х, у)) -э (Эх)(Лу)(Р(х, у)) (доказывается аналогично (5)); (7) (Эх)(Лу)(Р(х, у) ++ (Зу)(3х)(Р(х, у)) (правило л-вв: (5), (6)). 11.6. Докажите, что следующие формулы являются теоремами формализованного исчисления предикатов, построив их выводы из аксиом: а) (Зх)(Р(х)) ++ ~(Чх)(~Р(х)); б) з(Эх)(Р(х)) ++ ('Фх)(-зР(х)).
Решение. а) Вывод состоит из последовательности шагов: (1) (Чх)(зР(х)) -+ -зР(у) (аксиома (РА1)); (2) -тзР(у) -+-з(~х)(-зР(х)) (получена из (1) по правилу ФИВ: Р— ь О >- -з Д -+ ~Р); (3) Р(у) -+-гзР(у) (теорема ФИВ); (4) Р(у) -+ ~(чх)(~Р(х)) (получена из (3), (2) по правилу силлогизма из ФИВ); (5) (Зу)(Р(у))-+ з(чх)(-зР(х)) (Э-правило: (4)); (6) (Бх)(Р(х)) -+ -з(чх)(зР(х)) (переименование: (5)); (7) Р(у) -+ (Зх)(Р(х)) (аксиома (РА2)); (8) з(Зх)(Р(х)) -+-зР(у) (получена из (7) по правилу контра- позиции из ФИВ); (9) -~(Лх)(Р(х)) -+ (чу)(~Р(у)) ('ч'-правило: (8)); (10) -з(ЛхКР(х)) -+ (чх)(~Р(х)) (переименование: (9)); (11) -з(чх)(-зР(х)) -+ -гч(3х)(Р(х)) (получена из (10) по правилу контрапозиции); (12) -т.з(Ех)(Р(х)) — э (Лх)(Р(х)) (теорема ФИВ: -ю-зР -+ Р); (13) ~(чх)(-чР(х)) -+ (Лх)(Р(х)) (получена из (11), (12) по правилу ФИВ силлогизма); (14) (Бх)(Р(х))+-э-з(чх) (-зР(х)) (правило л-вв: (6), (13)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
