Ответы на экзаменационные вопросы. Введение
Скачать 389.99 Kb.
|
1.9. Полнота , непротиворечивость и разрешимость исчисления высказыванийПолнота формализованного исчисления высказываний состоит в совпадении множества доказуемых формул с множеством тавтологий. Теорема1. Если |-F, то |=F. Другими словами: всякая доказуемая в исчислении высказываний формула является тавтологией. Доказательство. Каждая аксиома является общезначимой формулой. Из общезначимых формул по правилу отделения получается снова общезначимая формула. Следовательно, в любом доказательстве в ИВ любая формула, в том числе последняя, общезначима. Теорема 2. Если |=F, то |-F . Другими словами: всякая тавтология доказуема в формализованном исчислении высказываний. Объединив обе теоремы, получим теорему о полноте: Теорема (о полноте).   Аксиоматическая теория полна, если присоединение к ее аксиомам формулы, не являющейся теоремой, делает теорию противоречивой. Аксиоматическая теория непротиворечива, если в ней нельзя доказать как формулу F, так и ее отрицание ¬F.   Следствие (теорема о непротиворечивости). В исчислении высказываний невозможно доказать формулу и ее отрицание. Доказательство (от противного). В самом деле, если для некоторой формулы F возможно одновременно |-F и |-¬F, то по теореме1 будет одновременно |=F и |= ¬F, что противоречит определению общезначимости. Аксиоматическая теория называется разрешимой, если существует алгоритм, позволяющий для любого утверждения, сформулированного в терминах теории, ответить на вопрос, будет или нет это утверждение теоремой данной теории. Исчисление высказываний разрешимо, если существует алгоритм, позволяющий для любой формулы установить, доказуема она или нет. Теорема (теорема о разрешимости). Формализованное исчисление высказываний есть разрешимая аксиоматическая теория.     Исчисление высказываний непротиворечиво, полно и разрешимо. 2. Логика предикатов 2.1. Предикаты В исчислении предикатов во внимание принимают не только истинностное значение элементарного высказывания, но и его предмет – тот объект, о котором идет речь в высказывании. Иначе говоря, высказывание в исчислении предикатов рассматривается не как нечто неделимое, но как состоящее из двух частей – собственно высказывания и предмета высказывания. Первая часть в нем – это что именно высказывается, а вторая – про что или про кого это высказывание. В переводе с английского predicate означает сказуемое, т.е. как раз то, что высказывается, поэтому первая часть в высказывании так и называется – предикат. Например, в высказывании «число 6 является простым» «число 6» будет предметом, а «является простым» – предикатом. В языке ИП предусматриваются средства для обозначения предикатов – предикатные переменные и предметов – предметные переменные. Истинностное значение высказывания, расчлененного на предикат и предмет, зависит как от того, так и другого.      Классификация предикатов:   Равносильность и следование предикатов.      Теорема1.   Теорема2.   Теорема3.   2.2. Логические и кванторные операции над предикатами Поскольку значениями предикатов являются высказывания, к предикатам можно применять все логические операции, определенные для высказываний. Отрицание.   Теорема.   Конъюнкция.   Теорема.   Дизъюнкция.    Теорема.   Импликация и эквивалентность.    Кроме того, над предикатами определяются две новые операции, называемые кванторными (кванторами). Как и операция ¬, каждый квантор является унарной операцией, т.е. действует на одиночный предикат, но, в отличие от ¬, связывает некоторый из аргументов последнего, давая в качестве результата предикат, не зависящий от этого аргумента и определяемый следующим образом. Квантор (все)общности.     .  К n-местному предикату можно применить n кванторов. Применение квантора к n-местному предикату (n≥1) дает (n-1)-местный предикат.   Квантор существования.        |
Похожие:
 | Ответы на экзаменационные вопросы по истории. Вопросы и ответы на экзаменационные вопросы по истории. | | Экзаменационные вопросы по культурологии А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные вопросы с ответами по физкультуре Вопросы и ответы к теоретической части экзамена по физкультуре | | Ответы на экзаменационные вопросы по литературе для 9 класса Вопросы из вариантов I и II (общеобразовательная школа, 31 и 21 билет соответственно; "старые", "Вестник образования" №4 февраль... |
| Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... Биология урок, тест, ответы, билеты, биология человека, общая биология, егэ 2006, школа, олимпиада, тестирование биология, экзамен,... |  | Экзаменационные вопросы по бжд для студентов специальности 110203.... Экзаменационные вопросы по бжд для студентов специальности 190603. 65 – «Сервис транспортных и технологических машин и оборудования... |
| Экзаменационные вопросы по нормальной физиологии Содержит ответы на 143 экзаменационных вопроса по охране труда, а также курсы лекций по охране труда | | Экзаменационные вопросы по истории и философии науки Курс «История и философия науки» Программы курса и экзаменационные вопросы по первым двум частям курса представлены ниже |
| Экзаменационные билеты по истории России (9 класс) Девятиклассники!... Билет № Вопрос Древняя Русь в IX – начале XII в.: возникновение государства, древнерусские князья и их деятельность | | Экзаменационные вопросы интернет-курсов интуит (intuit): 192. Введение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования |
| Экзаменационные вопросы интернет-курсов интуит (intuit): Введение... Анооспо «Оренбургский колледж менеджмента, туризма и гостиничного сервиса» (техникум) | | Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... | | Содержание введение Глава I. Из истории создания религиозных учебных заведений А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные билеты по литературе для 9 класса Билет №1 «Слово о полку Игореве» На этапе окончания основной школы девятиклассники, выбравшие экзамен по литературе, сдают его, как правило, в устной форме (собеседование,... | | Ответы на экзаменационные вопросы интернет-курсов интуит (intuit): 138. Микроэкономика фирмы Администрация региона Х ввела запрет на вывоз бананов со своей территории (бананы – главный продукт потребления жителей региона).... |
