Математическая логика. Шапорев С.Д (1019113), страница 28
Текст из файла (страница 28)
1О. А-» А; 14.2.11 11. А — »А П, 12. Пхб(х) — » Г(у); 12. Е(у)-~ Пху(х). Рассмотрим теперь несколько правил образования выводимых формул. Заметим, чзо секвенннн в исчислении прелнкатоа опрсделаются так же, как в исчислении высказываний. !вв Чвсм !. Магемагич слаллогила !. Правлю тлялючелия (лростоги злялгочянняй Оно такое же, как в исчислении высказываний, только объем формул, к которым применяется зто правило, шире. ~-А;! — Л вЂ” ьВ ! — В 2. Нрпегыо подсмагговкя. В исчислении высказываний заменялись толька переменные высказывания в выводимой формуле на любую формулу. В исчислении предикатов можно заменять переменные высказынания и переменные предикаты. Зто требует учета некоторых дополнительных условий, чтобы в результате подстановки получилась формула нсчислеин» предикатов.
а) Замела переменного высксгывилня. Пусть формула А(В) содержит переменное высказывание В. Тогда можно заменить В любой формулой 6, удовлетворяющей следующим условиям: ° свободные веременные в б обозначены буквами, отличными ог связанных перемм!ных в А, и связанные переменныс в С вЂ” буквами, отличными от свободных перемениьж в А; ° если В в А находится в области действиа квантора, обозначенного какой-то буквой,то зта буква не входщ в С .
Тогда с ) (А(В)) ~ — А(й). е Пример 1. Пусть А(В) ='4~Му(Сч ЗУзН(з,х)л (С г Р(х,у))). Здесь С нельзя заменить, например, формулой зухы(х) нлн Зху(х), т, к, не будет соблюдаться второе условие коллизии переменных. Замена жс высиживания С формулой ЗУх!Уг(Сл Н(-, )и Вл Р(х,!)) возможна, т к.
оба условна будут выполнены. В результате получим выражение, являющееся формулой тУхтУР(зУсзУ\(СлН(ж г)ч Ел Р(х,!))чтУгН(,х)л л 'уз'у! С л Н з, ! и Е л Р' х. ! и Р(х, у)) . б) Замена иер манного прсдггяалга. Пусть формула А(Р) содержит переменный преднкат Р от и переменных и пусть имеется формула 0(г„гз,...,г„), содержащая и свободных переменных гмгз,...,г„фсли свободные переменные а С обозначены буквами, отличнымн от сва- Гласа 4. Искл ление лредияаше !55 таиных переменных в Р, т. е выполняется первое правила замены переменных и следующее правило: если Р в А находится в обяастл дсйсгнвя квантора, связывающего какую-либо букву, го зта буква пе входит в 6 ( тогда возможна подстановка формулы Р в А вместо прсдиката Г .
При подсзанокке ну кно следить (указынать), какой из переменных г,,(„...,г„в 6 соотвшствуст каждое пустое место в Р( ). Например, пусть А = ЛхЭу35(Р(т, у) и Р(х, х)). Требуется заменить Р формуяой ЫиВАН(н, г, )ч Н(г, ! )). Здесь выполнено пересе и тре~ье условие. следовательно, подстановка возможна. Лучше отдельно вь!писать, чему равно Р в «шкдом несю формулы А. н жпвраппь старые переменные. Тогда Р(х,у)= Чнбг(Л(л,х)м Н(г,у)) и Р(х,г)=)(иЭз(Н(п,ь)~ Н(з,с)) фарьгула А будет иметь вид = ' т('.( (..г)'(.
)Нвддат.з гяРЭ)) Если жс первое и третье условия не выполняются, то могут получиться выражения, це явлнющисся фо(зчуламн Например, пусть А=Вхгз)хР(х) и необходимо подставить ()(х) высота В Получигся выражение ()(х) с !Ухр(х), которое не является формулой, т к нарушено первое условие Аналоги«цо, пуст~ А = з)х( — з )"(х)) и надо подставизь вместо В (гхНг(х) Получим з)х(((хН(х)-ь Р(х)). Это не формуяа исчисления предикатов, ибо прн подстановке нарушена третье условие. Операция подстановки переменного прсдиката в общем случае вырасйз. 4,) жается слелуюнгим образом. ~(А).
Это правила можно выразить так. Вели формуяа А содержит переменный предикат Г, !о полгпановка применяется, если дяя формул 6(г„(„...,(„) н А ныполняются первое и третье условия и, кроме тога, слелуюшес: отмеченные псременныс г,,г„..,,(я не должнь! входить в формулу А. Прн этом справедливы слслующие формуньс а г ) ((гхд (х)) сс! ь зух/(Л(г)) о(я ь '"" ' ° . "" я'(("г.»' Е( ) П ) твв Часп 1 ДГ»геметпчесяеп мппк а е » с),ч ! ) (Э»Л (х)) есть Эк) (А(к)) аб, к,) (ЭхЛ (х)) есть Эх ~ (А(х)) г1 ) в) Замени свободной пред еппюй перемеююй.
Пусть формула А »в~»»ется выводимой формулой в исчислении предикатов, а формула А' получена из А заменой любой свободной предметной переменной лруюй свободной предметной переменной так, что заменяема» переменная замен»ется одинаковым образом всюду, где она входит в А, тогда А' является выводимой формулой в исчислении предикатов. Например, )Гх(Р(х) — з 6(у))л (Р(у) — з Эх6(х)). Заменим у на к, получим з)к(Г(х) — з 6(х))л (Р(к) ь Эхб(х)). Здесь нельзя заменить переменную у переменной т, т. к.
свободная переменив» должна заменятыя только свободной переменной. г) Прмлып переименования се»шинн» п)идмепзнык перемепнмк. Если ~ — А в исчислении предикщов, то А', полученная заменой в А связаннык перемеииык другими связзнньщн переменными, отличными ст всех ыюбодныз переменнык формулы А, также выводима в исчислении предиютов. При зюм заменяемая связанная переменная в формуле А должна заменатьс» одинаковым обрззам всюду в области действия кююпра, связывающего данную переменную, и в самом кванзоре. Например, если Эку(х) з )гх)~х), то вазмолгны слелующие варианты переименованил' Э! Р(у) — з )Укб(к) илн Эку(х) — з )Гк6(х) аии Эз Р(у) — г з)хб(х).
Приведе»! теперь лва правила авязывания квантором: 1. Если 6 — ь А(х) — выводима» формула в исчислении преднкатов и 6 не содержит переменной х, то формула 6 -+ »У»А (х) тоже выводима в ис- )-6-+ А(х) числении предикатов, т. е., ) — 6 -з зУ»А (х) 2. Если А(х)е 6 — ям»одина» формула в исчиаленни предикатов и 6 не содерзкит переменной х, то формула ЭхА(к)-+ 6 тоже выводима в ис- )-А(х)-з 6 числении предиказов, т, е., ' ' '1-Эю)(х)- 6' Клава 4 Ис нсление лредиквгов гву 4.3. Производные правила вывода в исчислении предикатов Пусть 6,л,Ф вЂ” произвольныс формулы, Г,ГоГ„Г, — «онечиые последовательности формул, возможно цусть~с, а 6(!) получаетсв из 6(х) заме.
1юй всех свободных вхождений х на г, à — канечнав ооследовательносгь формул, не содержащая х свободно. Тогда в исчислении предикатоа верны влелующие правила вывода: Г,~-61Г,(- Г 1. — правило введения коныонкции. 1;,Гз~ — С л с 1) — 6л и 11-6 2. — правило удалена» конъюнкции. 1) — 6 л Е Ц-6 1) — бог 3, — правило введения дизъюнкции.
11 в г Т)- 6 о г Г!~-6 о Г' Гз,6~- Ф! Гз,й,— Ф 4. правило удаления дизъюнкции. ГиГ,,Гз~-Ф Г,6~- Г 5. ' — правило введения импликации. 11 — 6 — ь Р Г,~-б-ь ГИГ,~-6 б. ' ' ' — правило удаления имгщикации. 1;,Г,~- Г Г,6~- — правило введения отрицания. Г~- 6 14ти!) г 3 зэьь другие правила вывода рассьютрнм по мере нсобкодимосги. Их, как н в ис- Числении высказываний, довогжно много Чяс1ь 1 Маюмяпемамая лопма г,ЯЯ. — — правило удалеии» отрицания. 11-6 Г~-61Г,~-6 9. — правило сведения к противоречию. г„г,~- Г(- 1О. — правило утончения.
11-6 ! 1. — правило расширения. Г,Р)-6 Гоб,Р,гт)-Ф 12. ' — правило перестановки. ГпР,6,Г,!-Ф Г„6,6,Г,~-Ф 13. — правило сокращения. Г„О,Г,)-Ф г,~-6(х) 14., — правило введения квантора всеобщности. Г, ~ — Чх 6(х) ! ) — ~х6(х) 15. — правило удаления квантора всеобщности. г~ 6(!) г)-6(!) 16... — правило введения квацтора существования. ' Г)-ЗХ6(х) Г,6(х)- и !7. ~ .
— правило удаления «вантора существования. ' г„з Щ-и 4.4. Некоторые теоремы исчисления предикатов Так как все формулы, выводимые в исчислении выскшываний, являются также выводимыми в исчислении предикатов, то, совершая подстановки в выводимые формучы исчисленив высказываний, но кно получить новме вы и еодимые формулы исчисления предикатов. Обнаружить выводимость фор- Гл ее Е Исчиелмен л ияетов мулы в исчислении вмсквзыввний не представляет особого труда. Для этого нет необходимости проводить ее формальный вывод, достаточно уста.
повить, что формула являетсв тождественно истинной в смысле алгебры высказываний гф Например, ~ — АтА. ) (Ао А)м — ~-Е(х)згВ(х). Можно взять и более длинную формулу ~ — А -ь (В л С -ь В) л А = 1, тогда мг< Утгнб~ ) (1) ) — А — + (эхб(х)л 'чу11(г) — з Зхуг(х))л А. в.г Все произвопные правила, выведенные лля исчисления высказываний, остаются в силе в исчислении предикатов, например правила сложной подстановки н сложного заключения,правило силлогизма и др. Выведем последнее упомянутое правило — правило силлогизма — 6 — зЕ~-Е' — ьЛ В исчислении преднкатов это правило выводится ) — 6-ь Р из доказуемой формулы (А — эВ)-+((В-ьС)-+(А-ьС)). Поскольку правило подстановки в исчислении прсдинатов имеет место, то )-(6 — э Г) — ь ((г — з Л) — ь (6-ь Р)).
Коллизии переменных здесь ие мозкет возникнуть, т. к иначе имела бы место коллизия в какой-нибудь из формул 6,В илн Л либо между переменными какой-нибудь пары этих формул. Однако каждая пара представляет импяикацию 6 -+ Е', Г -з Р или 6 — ь Р, поэтому козшизия имела бы место по крайней мере в одной из этих пар. чего по предположению нет, т. к. все эти пары входят в правило си.члогпзма.
Тогда по правилу сложного заключении ~-6 ~Е;! В +Р;(-(6.,В),((В з Р) — з(6-эЛ)) )-6-з Р Выведем еще одно производное правило вывода исчисления предикатов— ~ — 6(х) правило связывания квантором ~- УЗх6(х) Пусть дано ! — 6(х). В исчисяении предикатов выводима формула А — ь В. Член |. Ыа вм шю<я ало вк тао Тогда применим подстановку ) (А — з В)— = ~ — А-» 6(х). Осталось восполь- е основным правилом зоваться первым связывания квантором ~-6-з А(х) ~- А — у 6(х) ...
где 6 ие содержит переменной х. Итак, — 6 — т зУхй (х) ' ~- А -з Утхб~х) Можно предпояожить, что А не входит в 6(х), т. к. ее всегда можно так выбрать Дюгее, пусть Ф вЂ” произвольная выводимая формула. Тогда ) (А -з зУх6(х)) и ( — Ф -+ ох 6(х). Наконец, по правилу простого заключе- (-Ф;)-Ф- Утхб(х) ! — 'зтх6(х) Пример П Доказать л ы води ность формулы ~ — 'техт у(Е(х) ь (6(у) — з В(х))). Воспользуемся первой аксиомой А-ь ( — з А) и сделаем и ней слег М.отй дующую подстановку ) (А — з (В ь А)) н ~- г (х) — ь (6(у) — з Г(х)), же По только что доказанному правилу связывания квантором имеем зУх(л (х) — з (6(у) — з Г(х))). Применяя еше раз зто же правило, пояучаем / — зУхтУу(г (х) — з (6(у) — + Г(х))).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
