Учебное пособие по математической логике для студентов заочного отделения




НазваниеУчебное пособие по математической логике для студентов заочного отделения
страница4/5
Дата публикации28.08.2013
Размер0.96 Mb.
ТипУчебное пособие
skachate.ru > Математика > Учебное пособие
1   2   3   4   5

^ Полнота, разрешимость и непротиворечивость исчисления высказываний. Независимость системы аксиом исчисления высказываний.

Исчисление высказываний полно (обладает свойством полноты), если всякая доказуемая в этом исчислении формула является тождественно истинной формулой (тавтологией) алгебры высказываний, и наоборот, любая тавтология алгебры высказываний является доказуемой формулой этого исчисления, то есть . Существуют доказательства, что исчисления ИВ и ИС полны.

Аксиоматическая теория называется разрешимой, если существует алгоритм, позволяющий для любого утверждения, сформулированного в терминах этой теории, ответить на вопрос, является ли это утверждение теоремой этой теории. Для доказательства разрешимости исчисления высказываний надо предъявить такой алгоритм. И он действительно существует и состоит в составлении таблицы истинности формулы. Если она содержит лишь единицы, то является тавтологией, а значит, поскольку исчисление полно, теоремой исчисления. Если есть хотя бы один ноль, это не тавтология, следовательно, не теорема.

Аксиоматическая теория называется непротиворечивой, если ни для какого утверждения , сформулированного в терминах этой теории, само утверждение и его опровержение не могут быть одновременно теоремами этой теории. Можно показать, что исчисления ИВ и ИС непротиворечивы.

Система аксиом называется независимой, если ни одну из аксиом этой системы нельзя вывести из остальных. Системы аксиом исчислений ИВ и ИС независимы.
^ 4. Логика предикатов
Высказывание с точки зрения исчисления высказываний – предельно простой объект, оно имеет лишь одну характеристику, оно может либо истинным, либо ложным. Высказывания совершенно не структурированы. Но реальные суждения всегда говорят что-то о чем-то или ком-то. Главные члены предложения – подлежащее и сказуемое. Подлежащее означает тот объект, о котором говорится в предложении, а сказуемое – то, что в предложении говорится об этом объекте. Сказуемое иначе называется предикатом.

В математической логике определенным на множествах -местным предикатом называется выражение , содержащее переменных , и превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств соответственно. Переменные называют предметными, а элементы множеств конкретными предметами.

Всякий -местный предикат, определенный на множествах , является функцией аргументов, заданной на этих множествах и принимающей значения во множестве всех высказываний.

Рассмотрим пример. Предложение “Река впадает в Каспийское море” является одноместным предикатом, определенным на множестве всех названий рек. Подставив вместо названия “Волга”, “Урал” или “Терек”, получим истинные высказывания, а подставив “Днепр”, “Нил” или “Ориноко”, получим ложные высказывания.

Примером двухместного предиката является неравенство . Этот предикат задан на двух экземплярах множества вещественных чисел R. Он превращается в истинное высказывание, в частности, при , а в ложное – при .
^ Классификация предикатов.

Предикат , определенный на множествах , называется a) тождественно истинным, если при любой подстановке вместо переменных любых конкретных предметов из множеств соответственно он превращается в истинное высказывание; b) тождественно ложным, если при любой подстановке вместо переменных любых конкретных предметов из множеств соответственно он превращается в ложное высказывание; c) выполнимым (опровержимым), если существует по крайней мере один набор конкретных предметов из множеств , при подстановке которых вместо соответствующих предметных переменных в этот предикат он превратится в истинное (ложное) высказывание.

Например, предикат , определенный на множестве вещественных чисел ^ R, является тождественно истинным, предикат , определенный на R, является тождественно ложным, а предикат “Город расположен на берегу Волги” является выполнимым и одновременно опровержимым.

^ Множество истинности предиката.

Множеством истинности предиката , определенного на множествах , называется совокупность всех упорядоченных наборов конкретных предметов из множеств соответственно, таких, что – истинное высказывание.

Обозначим множество истинности предиката через . Таким образом,

.

^ Равносильность и следование предикатов.

Два -местных предиката и заданных над одними и теми же множествами , называются равносильными, если набор конкретных предметов из множеств соответственно превращает первый предикат в истинное высказывание в том и только том случае, когда этот же набор превращает второй предикат в истинное высказывание . Иначе говоря, предикаты равносильны, если их множества истинности совпадают: .

Например, равносильны предикаты: и .

Предикат , заданный над множествами , называется следствием предиката , заданного над теми же множествами, если он превращается в истинное высказывание наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат . Иначе говоря, .

Например, предикат является следствием предиката , но эти предикаты не равносильны, поскольку первое неравенство справедливо и при .

^ Логические операции над предикатами.

Отрицанием предиката , заданного над множествами , называется новый предикат, заданный над теми же множествами, обозначаемый (читается: “неверно, что ”), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых предикат превращается в ложное высказывание.

Например, предикат является отрицанием предиката . Для предиката , определенного на множествах , множество истинности предиката является дополнением множества истинности предиката : .

Конъюнкцией -местного предиката , определенного на множествах , и -местного предиката , определенного на множествах , называется новый -местный предикат, определенный на множествах , , обозначаемый (читается “ и ”), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания.

Например, конъюнкцией предикатов и является предикат .

Дизъюнкцией -местного предиката , определенного на множествах , и -местного предиката , определенного на множествах , называется новый -местный предикат, определенный на множествах , , обозначаемый (читается “ или ”), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых хотя бы один из исходных предикатов превращается в истинное высказывание.

Например, дизъюнкцией предикатов и является предикат “ или ”.

Импликация определяется как такой предикат, что для любых предметов , высказывание является импликацией высказываний и .

Например, импликацией предикатов и является предикат “Если , то и ”.

Эквиваленция определяется как такой предикат, что для любых предметов , высказывание является эквиваленцией высказываний и .

Например, эквиваленцией предикатов и является предикат “Если и только если , то ”.

^ Кванторные операции над предикатами.

Операцией связывания квантором общности по переменной называется правило, по которому каждому одноместному предикату , определенному на множестве , ставится в соответствие высказывание (читается “для всякого ” ), которое истинно в том и только том случае, когда предикат тождественно истинен, и ложно в противоположном случае, а -местному предикату , определенному на множествах , ставится в соответствие новый -местный предикат, обозначаемый (читается “для всех ”), который для любых предметов превращается в высказывание , истинное в том и только том случае, когда одноместный предикат , определенный на множестве , тождественно истинен и ложное в противоположном случае.

Операцией связывания квантором существования по переменной называется правило, по которому каждому одноместному предикату , определенному на множестве , ставится в соответствие высказывание (читается “существует , такое, что ”), которое ложно в том и только том случае, когда предикат тождественно ложен, и истинно в противоположном случае, а -местному предикату , определенному на множествах , ставится в соответствие новый -местный предикат, обозначаемый (читается “существует , такое, что ”), который для любых предметов превращается в высказывание , ложное в том и только том случае, когда одноместный предикат , определенный на множестве , тождественно ложен и истинное в противоположном случае.

В выражениях типа и переменная называется связанной. Остальные переменные называются свободными.

Формулы логики предикатов.

Алфавит логики предикатов состоит из следующих символов:

предметные переменные: ^ N);

нульместные предикатные переменные: N);

-местные предикатные переменные:

( N) с указанием числа свободных мест в них;

символы логических операций: ;

кванторы: ;

вспомогательные символы: (, ), ,.

Каждая нульместная предикатная переменная есть формула, если -местная предикатная переменная, то – формула, в которой все переменные свободны, если – формула, то – тоже формула, свободные (связанные) предметные в этой формуле те же, что и в формуле ; если – формулы, то выражения также являются формулами, при этом предметные переменные, свободные (связанные) хотя бы в одной из формул , являются свободными (связанными) и в новых формулах; если – формула, а – предметная переменная, входящая в свободно, то выражения и – тоже формулы, в которых переменная связанная, а все остальные предметные переменные, входящие в формулу свободно или связанно, остаются и в новых формулах такими же. Никаких других формул логики предикатов нет.

Если в формулу логики предикатов вместо каждой предикатной переменной подставить конкретный предикат, определенный на некотором множестве , то формула превратится в конкретный предикат, определенный на множестве . Если исходная формула замкнута, то полученный предикат будет нульместным, то есть высказыванием, а если открыта, то полученный предикат будет зависеть от некоторых предметных переменных. Если теперь подставить вместо них конкретные предметы из множества , то получится конкретное высказывание.

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

Формула логики предикатов называется выполнимой (опровержимой) на множестве , если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат.

Формула логики предикатов называется тождественно истинной (тождественно ложной) на множестве , если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат.

Формула логики предикатов называется общезначимой, или тавтологией (тождественно ложной или противоречием), если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на каких угодно множествах, она превращается в тождественно истинный (тождественно ложный) предикат.

Например, формула является противоречием (тождественно ложной).

^ Тавтологии логики предикатов.

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

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

Специфичны для логики предикатов тавтологии, которые являются выражениями, содержащими кванторы.

Законы де Моргана для кванторов. Следующие формулы являются тавтологиями логики предикатов:

1) ;

2) .

Следствия этих формул:

1) ;

2) .

Законы пронесения кванторов через конъюнкцию и дизъюнкцию. Следующие формулы являются тавтологиями логики предикатов:

1) ;

2) ;

3) ;

4) .

Законы пронесения кванторов через импликацию. Следующие формулы являются тавтологиями логики предикатов:

1) ;

2) ;

3) ;

4) .

Законы удаления квантора общности и введения квантора существования. Следующие формулы являются тавтологиями логики предикатов:

1) ;

2) .

Законы коммутативности для кванторов. Следующие формулы являются тавтологиями логики предикатов:

1) ;

2) ;

3) .
1   2   3   4   5

Похожие:

Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по ботанике для студентов 3 курса заочного отделения...
Учебное пособие предназначено для самостоятельной работы студентов 3 курса заочного отделения фармацевтического факультета. Пособие...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы...
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по фармацевтической химии для студентов 4 курса заочного...
Авторы учебного пособия для студентов 4 курса заочного отделения фармацевтического факультета «Общие и частные методы анализа лекарственных...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие содержит характеристику основных разделов фармацевтической...
В пособии приведена рабочая программа по фармацевтической химии для студентов заочного отделения, даны рекомендации по её освоению...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы студентов
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconРекомендации о разработке методических указаний и контрольных заданий...
Разработчик: методист заочного учебного отделения высшего профессионального образования С. С. Кудрявцева
Учебное пособие по математической логике для студентов заочного отделения iconСамостоятельная работа, часов
Смолова Л. М. Химия. Рабочая программа, методические указания, элементы теории, вопросы для самопроверки и контрольные задания для...
Учебное пособие по математической логике для студентов заочного отделения iconКонтрольная работа №2 по английскому языку для студентов заочного...
Данное пособие можно взять в библиотеке Политехнического колледжа или получить в электронном виде. Также необходимо изучить материалы...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница