Главная » Просмотр файлов » Игошин Математическая логика и теория алгоритмов

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

Файл №1019110 Игошин Математическая логика и теория алгоритмов (Игошин Математическая логика и теория алгоритмов) 41 страницаИгошин Математическая логика и теория алгоритмов (1019110) страница 412017-07-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Посмотрим, в какие высказывания может превращаться данный предикат при подстановке вместо его переменных х и у конкретных предметов (чисел) из )у. Нетрудно понять, что двухместный предикат (Лг)(х у= г -» х+ у= г) превращается в истинное 167 высказывание при любой подстановке вместо его предметных переменных х и у натуральных чисел.

В самом деле, для натуральных т и и получаем высказывание (Лг)(т и = 7 -+ т + и = 7), Одноместный предикат (зависит от г) т . и = г -+ т + и = г, стоящий под знаком квантора Зг, выполним, потому что всегда можно найти такое натуральное число и, что т . и в и и т+ и в й, т.е. высказывания т и = /с и т+ и = lс будут ложны, а значит, высказывание т . и = и -~ т+ п = )с — истинно. А раз так, то высказывание (Зг)(т и = г — ~ т+ и = г) истинно. Поэтому высказывание (Лг)(т . и = г -+ т+ и = г) — > 2 = 4, в которое превращается данный предикат, ложно.

Итак, исходная открытая формула логики предикатов превращена в тождественно ложный предикат. Нетрудно понять, что если вместо предикатных переменных Р(х, у, г) и Ц(х, у, г) подставить только что рассмотренные предикаты, а вместо нульместной предикатной переменной Л— любое истинное высказывание, то исходная формула превратится в тождественно истинный предикат. Сформулируем классификационные определения для формул логики предикатов. Определение 21.4.

Формула логики предикатов называется выполнимой (опровержимой) на множестве М, если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат. Другими словами, формула выполнима (опровержима) на М, если существует истинная (ложная) ее интерпретация на М. Формула из примера 21.2 является как выполнимой, так и опровержимой. Еще один пример такой формулы приведен в Задачнике, № 9.35, л.

А в задаче № 9.54 подробно разбирается пример формулы, выполнимой на множестве из трех элементов и невыполнимой ни на каком множестве из двух элементов. Определение 21.5. Формула логики предикатов называется тождественно истинной (тождественно ложной) на множестве М, если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат. В задачах № 9.53, 9.58 Задачника приводятся примеры формул, тождественно истинных на одних множествах, но не являющихся таковыми на других множествах.

Определение 21.б. Формула логики предикатов называется общезначшиой, или тавтологией (тождественно ложной или противоречием), если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на каких угодно 168 множествах, она превращается в тождественно истинный (тождественно ложный) предикат. (Тот факт, что формула Г является тавтологией, обозначается, как и в алгебре высказываний, Е) Так, формула из примера 21.3 не является тавтологией, потому что хотя при одной подстановке она и превратилась в тождественно истинный предикат, при другой она оказалась превращенной в предикат тождественно ложный.

Поэтому данная формула не является и противоречием. Пример 21.7. Покажем, что формула —,Р(х) л (Чу)(Р(у)) является противоречием, т.е. тождественно ложной. В самом деле, допустим противное: на некотором множестве М имеется конкретный предикат А(х), такой, что данная формула превращается в выполнимый предикат (от х) -А(х) л ('-"у)(А(у)). Последнее означает: найдется предмет а в М, такой, что высказывание 4(а) л (чу)(А(у)) истинно. Истинность конъюнкции дает истинность высказываний -А(а) и (чу)(А(у)).

Из истинности первого следует, что высказывание А(а) ложно, а из истинности второго — что предикат А(у) тождественно истинный и, значит, для любого предмета из М, в том числе и для а е М, высказьгвание А(а) истинно. Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна. Нахождение тавтологий является одной из важнейших задач логики предикатов, как и алгебры высказываний. Но если в алгебре высказываний имеется общий метод определения, является или нет данная формула тавтологией (это — метод составления таблицы истинности для формулы), то в логике предикатов такого общего метода не существует.

Каждая формула подлежит изучению индивидуальным методом на тождественную истинность. Дело здесь в том, что каждое высказывание имеет только одно из двух логических значений: «истина» или «ложь», тогда как значение предиката зависит от выбора значений его предметных переменных, который, вообще говоря„можно сделать бесконечным числом способов. Мы вернемся к этой проблеме в Э 23 при рассмотрении ее лля формул некоторых частных видов. Тавтологии логики предикатов. Рассмотрим наиболее важные тавтологии логики предикатов. О значении тавтологий алгебры высказываний подробно говорилось в 5 3. Все сказанное там сохраняет свое значение и для тавтологий логики предикатов.

Но, как уже отмечалось, язык логики предикатов более тонок, а поэтому тавтологии логики предикатов более тонко отражают процессы логических умозаключений. Рассмотрение тавтологий логики предикатов начнем с установления того, что простейшие ее тавтологии получаются из тавтологий алгебры высказываний, а тавтологии алгебры высказываний образуют часть тавтологий логики предикатов. 169 Теорема 21.8. Всякая формула, получающаяся из тавтологии алгебры высказываний заменой входящих в нее пропозициональных переменных произвольными предикатными переменными, является тавтологией логики предикатов, Доказательство. Пусть Г(Х„Хь ..., Х„) — тавтология алгебры высказываний и Р~(хь х,, ..., х„,), Рг(уь уг* ", У и),, Р.(гь гь ..., г „) — предикатные переменные. Подставим их в данную формулу вместо пропозициональных переменных Хо Хг, ..., Х„соответственно.

Получим формулу логики предикатов: Р(Р,(х„„,,х,), Р„(гь ..., г )) . Если теперь вместо предикатных переменных подставить произвольные конкретные предикаты А,(х„хг, ...,х,), ..., А„(гн гг, ...,г ), то формула превратится в конкретный предикат Г(А,(хь ..., х,), ..., А„(г„...,г )). Этот предикат тождественно истинный, потому что подстановка вместо предметных переменных хь ..., х„,, ..., г„..., г любых конкретных предметов а„..., а „..., с„...,с из соответствующих множеств превращает данный предикат в высказывание Г(А,(хь ..., х„,), ..., А„(г, „, г„)), которое может быть получено также в результате подстановки в исходную тавтологию Р(Хь Хг, ..., Х) алгебры высказываний вместо пропозициональных переменных Хь Хг, ..., Х„конкретных высказываний А,(аь ..., а,), ..., А„(с„...,с ) соответственно и потому истинно.

Следовательно, формула Г(ЄЄ..., Р„) логики предикатов также является тавтологией. Теорема доказана. О В последующих теоремах приводятся наиболее важные тавтологии логики предикатов, не сводящиеся к тавтологиям алгебры высказываний. Все такие тавтологии содержат кванторы. Теорема 21.9 (законы де Моргана для кванторов). Следующие формулы логики предикатов являются тавтологиями: а) -(чхНР(х)) +-» (ЛхН-Р(х)); б) -(Лх)(Р(х)) +-» (чх)(- Р(х)). До ка з а тел ь с т в о.

Докажем тождественную истинность формулы а). (Тождественную истинность формулы б) предлагается проверить самостоятельно.) Данная формула замкнута, т.е. не имеет свободных предметных переменных. Поэтому, подставив в эту формулу вместо предикатной переменной Р(х) любой конкретный одноместный предикат А(х), определенный на некотором множестве М, получим высказывание — (чх)(А(х)) с-ь (Лх)( 4(х)). (1) Для доказательства его истинности нужно убедиться, что обе части эквивалентности одновременно истинны или одновременно ложны.

В самом деле, высказывание (Чх)(А(х)) истинно тогда и только тогда, когда высказывание ('Фх)(А(х)) ложно, что возможно на основании определения 20.1 тогда и только тогда, когда предикат А(х) опровержим. Далее, опровержимость предиката 170 А(х) означает выполнимость его отрицания -А(х) (обдумайте это!), что равносильно на основании определения 20.3 истинности высказывания (ЗхН-А(х)). Итак, высказывание (ехНА(х)) истинно тогда и только тогда, когда истинно высказывание (ЗхН 4(х)). Следовательно, высказывание (1) истинно, что и доказывает тождественную истинность формулы а). С! Непосредственно из этой теоремы и закона двойного отрицания (теорема 3.1, в) вытекает следствие. Следствие 21.10 (выражение кванторов одного через другой).

Следующие формулы логики лредикатов являются тавтологиями: а) (ехНР(х)) <-+ -(ЗхН- Р(х)); б) (ЗхНР(х)) <-+ — ('сгхН- Р(х)). Заметим, что законы де Моргана для кванторов напоминают аналогичные законы для конъюнкции и дизъюнкции в алгебре высказываний. Можно считать„что эти законы для кванторов представляют собой обобщения соответствующих законов для коньюнкции и дизъюнкции, подобно тому как сами операции квантификации являются обобщениями операций конъюнкции и дизьюнкции, что отмечалось в э 20. Теорема 21.11 (законы пронесения кванторов через конъюнкцию и дизъюнкцию). Следующие формулы логики лредикатов являются тавтологиями: а) (ехНР(х) л (г(х)) <-+ (вхНР(х)) а (ЧхНО(х)); б) (ЗхНР(х) ~ (г(х)) с-+ (ЗхНР(х)) ~~ (ЗхН(2(х)); в) (ЧхНР(х) ч Ц) е-> ('с'хНР(х)) ч Д; г) (ЗхНР(х) а О) с-+ (ЗхНР(х)) а (г.

Доказательство. а) Подставим вместо предикатных переменных Р(х) и (г(х) конкретные предикаты А(х) и В(х), определенные на некотором множестве М. Формула превратится в высказывание (чхНА(х) а В(х)) <-~ ('ехНА(х)) л (чхНВ(х)). (1) Докажем его истинность. На основании определения 20.1 высказывание (ехНА(х) а В(х)) истинно тогда и только тогда, когда предикат А(х) а В(х) тождественно истинен, что на основании следствия 19.7 возможно в том и только в том случае, когда оба предиката А(х) и В(х) тождественно истинны.

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

Тип файла
DJVU-файл
Размер
6,65 Mb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6505
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее