Игошин Математическая логика и теория алгоритмов (1019110), страница 52

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 52)

Это означает, что если Р ~ И, то Я П П Р ~ И, и заключение силлогизма выполняется. Если же Р = И, то при выполнении условий силлогизма его заключение может и не выполняться: Яй Р= И. Пример 24. 1б. Силлогизм Ге!арбоп имеет вид: Мер МПР=И, Ма5 Мс 5 Бор ЯФ Р. Допустим, что условия верны, но Я~ Р.

Тогда М<- Р, т.е. М П Р = = М, а значит, М= И. Таким образом, при М= И из выполнимости условий силлогизма может не следовать выполнимость его заключения. Аналогична теоретико-множественная ситуация с силлогизмом Гезаро. Итак, четыре рассмотренных силлогизма с теоретико-множественной точки зрения не выполняются в тех случаях, когда в них участвуют пустые множества. С точки зрения логики предикатов это означает, что мы не исключаем тождественно ложных предикатов. Это означает, что в теоретико-множественной теории силлогизмов, находящейся в рамках логики предикатов, имеется лишь 15 верных силлогизмов. Если же мы исключим из рассмотрения в логике предикатов тождественно ложные предикаты, то мы будем иметь 19 верных силлогизмов.

Что же касается классической аристотелевской силлогистики, то в ней изначально не предполагались пустые термины, т.е. предикаты с пустым множеством субъектов, или, в нашей терминологии, тождественно ложные предикаты. Поэтому классическая аристотелевская силлогистика включает 19 верных силлогизмов. Отметим, что М. В.Ломоносов (!711 — 1765), осуществляя нововведения в традиционную логику, не признавал правильными «плохие» силлогизмы 1)агарг1, Ге!аргюп, Вгатапйр и Гезаро. Это 213 красноречиво говорит о том, насколько глубоко этот гениальный ученый проник и в эту область научного знания.

О других методах рассуждений. Аристотелевская силлогистика охватывает далеко не все типы умозаключений так называемой логики свойств, к которой эту силлогистику принято относить. Полная формализация таких умозаключений осуществляется в логике (одноместных) предикатов. Рассмотрим еще ряд некоторых типов умозаключений. Пример 24.17. Вот один такой широко распространенный способ рассуждений. Приведем сначала примеры таких рассуждений. «Все люди смертны. Сократ — человек. Следовательно, Сократ смертен». «Всякое нечетное натуральное число является разностью двух квадратов. 7 есть нечетное натуральное число.

Следовательно, 7 является разностью двух квадратов». Приведенные рассуждения основаны на следующей схеме: (~ух)(Н(х) -» Р(х)), Н(а) Р(а), означающей, что третья формула является логическим следствием первых двух. Проверим, что это действительно так. Пусть первые две формулы превратились в истинные высказывания ('Фх)(А(х) -+ В(х)) и А(а) при подстановке вместо предикатных переменных Ни Р некоторых конкретных предикатов А(х) и В(х) соответственно, определенных на некотором множестве М. Истинность высказывания (тх)(А(х) -» В(х)) означает тождественную истинность предиката А(х) — > В(х), откуда, в частности, вытекает истинность высказывания А(а) — » В(а).

Наконец, из истинности высказываний А(а) и А(а) -+ В(а) следует истинность высказывания В(а), полученного из заключительной формулы Р(а) в результате подстановки конкретного предиката В на место предикатной переменной Р. Тем самым справедливость приведенной схемы рассуждений доказана. И аристотелевские силлогизмы, и приведенная схема рассуждений обосновываются с привлечением лишь одноместных предикатов. Приведем пример рассуждения, для обоснования которого уже нельзя обойтись только одноместными предикатами. Пример 24.18.

«Бинарное отношение < на множестве натуральных чисел транзитивно и антирефлексивно. Следовательно, оно несимметрично». Символически: ('Фх)('Фу)(~уз)(х < у л у < е -+ х < 7), (Чх)(- (х < х)) (лх)('Фу)(х < у -+ — (у < х)). 214 Это рассуждение основано на следующей схеме с двухместным предикатом Р(х, у): (чх)('Фу)(Чз)(Р(х, у) л Р(у, г) -~ Р(х, г)), (Мх)( Р(х, х)) (Ух)(Му)(Р(х, у) -+ -Р(у, х)). Проверим справедливость этой схемы. Отметим вначале, что тавтологию закона удаления квантора общности (теорема 21.13, а) в терминах логического следования можно трактовать так: формула Р(у) является логическим следствием формулы ('Фх)(Р(х)). На основании данного закона из первой формулы рассматриваемой схемы следует формула Р(х, у) л Р(у, х) — > Р(х, х) (1) (переменную з переименовали в х). Далее, из второй формулы рассматриваемой схемы по тому же закону удаления квантора общности следует формула — Р(х, х).

(2) При фиксированных х и у две последние формулы превращаются в формулы алгебры высказываний: (А л В) -~ С, — С. Используя методы алгебры высказываний (см. В 6), нетрудно проверить, что (АлВ)-~ С,— СмА-+-~В. (3) Переводя полученную формулу А -~ —,В на первоначальный язык, получим формулу Р(х, у) -э ~Р(у, х). Таким образом, выводимость (3) показывает, что формула Р(х, у) — > — Р(у, х) является логическим следствием формул (!) и (2) для каждого значения х и у. Следовательно, и формула (Чх)(Му)(Р(х, у) -+ — Р(у, х)) будет превращаться в истинное высказывание при всякой такой подстановке вместо предикатной переменной Р конкретного предиката, а вместо предметных переменных х и у — конкретных предметов, при которой в истинные высказывания превращаются формулы (1) и (2). Этим завершается проверка справедливости схемы умозаключения.

В заключение приведем пример доказательства математической теоремы, целиком основанного на одной тавтологии логики предикатов. По существу здесь мы имеем пример теоремы из конкретного раздела математики, доказательство которой носит не математический, а чисто логический характер. Пример 24. 19.

Рассмотрим следующую тавтологию логики предикатов (см. Задачник, Хв 9АЗ, м): ('Фх)(Р(х)) -+ (Чх)(Р(х) ч Д(х)). (1) 215 Покажем, как она может быть применена к доказательству следующего утверждения: «Наименьший элемент (если он существует) упорядоченного множества минимален.» Напомним определения. Отношением порядка на множестве А называется бинарное отношение -< на А, удовлетворяющее условиям: 1) рефлексивностгк ('Фх)(х < х); 2) антисимметричностьс (чх, у, г)((х .< у л у .< х) » х = у); 3) транзитивностгс (Чх, у, г)((х -«у л у -«г) -» х < г). Множество А вместе с заданным на нем отношением порядка < называется упорядоченным и обозначается < А; < >.

Элемент а упорядоченного множества < А; «> называется наименьшим, если он меньше всех элементов этого множества: (Чх)(а -< х), и называется минимальным, если меньше его нет элемента в этом множестве: (Эх)(х < а). Таким образом, утверждение, которое мы хотим доказать, на языке логики предикатов записывается так: (2) ('Фх)(а -< х) -+ — (Зх)(х -< а). С помощью равносильных преобразований преобразуем сначала заключение этой импликации: -~(3х)(х -< а) н (чх)[ \(х < а)1 н (чх)[а < х ч ( -1(а и х) л -1(х < .< а))1 н (~ух)[(а < х ~~ †,(а < х)) л (а < х г - (х .< а))] =- (~ух)(а .< -« х ч - (х -< а)). Тогда утверждение (2) имеет вид (~ух)(а -< х) -+ (Чх)(а -< х г (х -< а)).

(3) Именно в это высказывание и превращается формула (1) при подстановке в нее вместо переменной Р(х) предиката «а < х», а вместо переменной Д(х) — предиката «(х.< а)». Поскольку формула (1), как мы доказали, общезначима, то высказывание (3), а вместе с ним и высказывание (2) истинны. Принцип полной дизъюнкции в нреднкатной форме. Теореме 7.18 об обратимости системы импликаций можно придать следующий предикатный вид.

Теорема 24.20. Пусть справедливы все следующие прямые теоремы (т > 2): (Чх)(Р,(х) -+ О,(х)), (чх)(Рг(х) -+ Дг(х)), ..., ~4х)(Р„,(х) -+ Я„(х)). Причем для посылок известно, что истинно утверждение (Мх)(РЯх) г ч Рг(х) г ... г Р„(х)), а следствия попарно исключают друг друга, т.е. истинны все высказывания — (Бх)((г;(х) л О,(х)) (1, 7 = 1, ..., т, 1 в у ).

Тогда справедливы и все обратные иипликаиии: (~х)(Д,(х) » Р,(х)), (чх)(ог(х) -» Рг(х)), ..., (чх)(Я„(х) » Р„,(х)). (Предполагается, конечно, что все предикаты заданы над одним и тем же множеством М.) 216 Доказательство. Покажем сначала, что истинна первая обратная импликация: (Чх)(Д,(х) — ~ Р,(х)). Пусть а в М. Если высказывание Д,(а) ложно, то импликация Д,(а) — > Р,(а) истинна. Предположим, что высказывание Д,(а) истинно. Покажем, что тогда все высказывания Р,(а), ..., Р (а) ложны. Допустим противное: например, пусть Р,(а) истинно.

В силу истинности (по условию) универсального высказывания ('Фх)(Р,(х) — > Д,(х)) будет истинна и импликация Рз(а) -+ Д,(а), что вместе с истинностью ее посылки Рг(а) приводит к истинности следствия Д,(а). Итак, высказывания Д,(а) и Д,(а) истинны. Значит, истинна конъюнкция Д,(а) п Ща), а вместе с ней истинно экзистенциальное высказывание (Зх)(Д,(х) п Д,(х)), что противоречит условию, согласно которому истинно отрицание этого высказывания. Таким образом, все высказывания Рз(а), ..., Р (а) ложны. Тогда высказывание Р,(а) должно быть истинно, ибо если и оно будет ложным, то ложной будет и дизъюнкция Р,(а) ~~ Рг(а) ч ...

ч Р„(а), а вместе с ней и универсальное высказывание ('ох)(Р,(х) г ... ~~ Р (х)), что противоречит условию. Итак, высказывания Д,(а) и Р,(а) истинны. Следовательно, истинна импликация Д,(а) — ь Р,(а). Итак, мы доказали, что, каким бы ни был элемента е М(превращающим предикат Д,(х) в ложное высказывание или превращающим его в истинное высказывание), импликация Д,(а) — ~ Р,(а) будет истинной. Следовательно, будет истинно и высказывание (чх)( Д,(х) -+ Р,(х)).

Совершенно аналогично устанавливается истинность и остальных обратных импликаций: ('Фх)(Дг(х) — > Рз(х)), ..., (чх)(Д„,(х) -+ — э Р (х)). П Частным видом рассмотренной теоремы об обратимости системы импликаций при т = 2 является следующая теорема. Теорема 24.21. Пусть справедливы следующие две прямые теоремы: ('чх)(Р(х) -+ Д,(х)) и ('Фх)(- Р(х) -+ Дз(х)), причем следствия Д~(х) и Дз(х) взаимно исключают друг друга, т.е. истинно высказывание — (Зх)(Д,(х) п Дз(х)). Тогда справедливы обратные теоремы: ('Фх)(Д,(х) — > Р(х)) и (~ух)(Дз(х) — э — Р(х)). Для того чтобы д о к а з а т ь, что данная теорема действительно является частным видом теоремы предыдущего пункта, заметим, что ее условие удовлетворяет требованиям условия предыдущей теоремы.

Характеристики

Список файлов книги