- •1.Совершенные нормальные формы.Правила приведения к сднф и скнф. Минимизация логических функций.
- •§8. Нормальные формы функций.
- •8.2 Нормальные формы.
- •8.3 Совершенные нормальные формы.
- •8.4 Правила приведения произвольной формулы алгебры логики к совершенной нормальной форме.
- •8.6 Способ составления снф для произвольной формулы алгебры логики по таблице истинности.
- •§ 1. Понятие формулы исчисления высказываний.
- •§ 2. Определение доказуемой (выводимой) формулы.
- •Правила вывода.
- •Определение выводимой (доказуемой ) формулы.
- •Правило сложной (одновременной) подстановки (спп).
- •Правило сложного заключения.
- •Правило силлогизма.
- •Правило контр позиции.
- •Правило снятия двойного отрицания.
- •§4.Понятие выводимости формул из совокупности формул.
- •§5. Понятие вывода.
- •§6. Правила выводимости.
- •H,w├a из совокупности формул : “Если а выводима из н, то она вы- водима из ”.
- •5. Теорема дедукции: h, c├ a .
- •§9.Проблемы аксиоматического исчисления высказываний.
- •2. Проблема непротиворечивости исчисления высказываний.
- •3.Проблема полноты исчисление высказываний.
- •4.Проблема независимости аксиом исчисления высказываний.
- •§1. Недостаточность логики высказываний. Понятие предиката.
- •§2. Логические операции над предикатами.
- •§3. Кванторные операции.
- •Квантор всеобщности.
- •Квантор существования.
- •Отрицание предложений с кванторами.
- •§4.Понятие формулы логики предикатов.
- •§5. Значение формулы логики предикатов.
- •§6. Равносильные формулы логики предикатов.
- •§7. Нормальные формы формул логики предикатов.
- •§8. Общезначимость и выполнимость формул. Проблема разрешимости.
- •§9. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений.
- •9.1 Запись математических предложений и определений в виде формул логики предикатов.
- •9.2. Построение противоположный утверждений.
- •9.3 Прямая, обратная и противоположная теоремы.
- •9.4 Необходимые и достаточные условия.
- •9.5. Доказательство теорем методом от противного.
- •Утверждения о свойствах объектов и отношениях между ними
- •Язык логики предикатов
- •Синтаксис: формулы логики предикатов
- •Семантика: системы и значения формул на их состояниях
- •Реляционные базы данных
- •Реляционная алгебра
- •Теоретико-множественные операции
- •Специальные реляционные операторы
- •Запросы
- •Ограничения целостности
- •Основные определения
- •Тьюрингово программирование
- •Стандартная заключительная конфигурация
- •Односторонние машины Тьюринга
- •Последовательная и параллельная композиции машин Тьюринга
- •Ветвление (условный оператор)
- •Повторение (цикл)
Квантор всеобщности.
Пусть Р(х) – предикат, определенный на множестве М. Под выражением понимают высказывание, истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: “Для всякого х Р(х) истинно ”.
Символ называют квантором всеобщности (общности). Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании же х называют связанной квантором всеобщности.
Квантор существования.
Пусть P(x) -предикат определенный на множестве М. Под выражением понимают высказывание, которое является истинным, если существует элемент , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).
Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат (или одноместный предикат ), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:
Рассмотрим предикат P(x) определенный на множестве M={a1,…,an}, содержащем конечное число элементов. Если предикат P(x) является тождественно - истинным, то истинными будут высказывания P(a1),P(a2),…,P(an). При этом истинными будут высказывания и конъюнкция .
Если же хотя бы для одного элемента P(ak)окажется ложным, то ложными будут высказывание и конъюнкция . Следовательно, справедлива равносильность .
Численные кванторы.
В математике часто встречаются выражения вида “по меньшей мере n” (“хотя бы n”), “не более чем n”, “n и только n” (“ровно n”), где n – натуральное число.
Эти выражения, называемые численными кванторами, имеют чисто логический смысл; они могут быть заменены равнозначными выражениями, не содержащими числительных и состоящими только из логических терминов и знака или ~, означающего тождество (совпадение) объектов.
Пусть n=1. Предложение “По меньшей мере один объект обладает свойством P” имеет тот же смысл, что и предложение “Существует объект, обладающий свойством P”, т.е. (*)
Предложение “не более чем один объект обладает свойством P” равнозначно предложению “Если есть объекты, обладающие свойством P, то они совпадают”, т.е. (**) Предложение “один и только один объект обладает свойством P” равнозначно конъюнкции вышеуказанных предложений (*) и (**).
Отрицание предложений с кванторами.
Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу “не”. Например, отрицанием предложения “Река х впадает в Черное море.” является предложение “ Река х не впадает в Черное море ”. Годится ли этот прием для построения отрицаний предложений с кванторами? Рассмотрим пример.
Предложения “Все птицы летают ” и “Все птицы не летают ” не являются отрицаниями друг друга, т. к. они оба ложны. Предложения “ Некоторые птицы летают ” и “ Некоторые птицы не летают ” не являются отрицанием друг друга, т. к. они оба истинны.Таким образом , предложения , полученные добавлением частицы “не” к сказуемому предложений “Все х суть Р” и “Некоторые х суть Р” не являются отрицаниями этих предложений.Универсальным способом построения отрицания данного предложения является добавление словосочетания “наверно, что” в начале предложения. Таким образом, отрицанием предложения “Все птицы летают” является предложение “Неверно, что все птицы летают”; но это предложение имеет тот же смысл, что и предложение “Некоторые птицы не летают”. Отрицанием предложения “Некоторые птицы летают” является предложение “Неверно, что некоторые птицы летают”, которое имеет тот же смысл, что и предложение “Все птицы не летают”.
Условимся отрицание предложения записывать как , а отрицание предложения – как . Очевидно, что предложение имеет тот же смысл, а следовательно, то же значение истинности, что и предложение , а предложение – тот же смысл, что . Иначе говоря, равносильно ; равносильно .
Кванторы общности и существования называют двойственными относительно друг друга. Выясним теперь, как строить отрицание предложения, начинающегося с нескольких кванторов, например, такого: .
Последовательно применяя сформулированное выше правило, получим: равносильно , что равносильно , что равносильно .