Учебно-методическое обеспечение

КОНТРОЛЬНЫЕ ВОПРОСЫ

Задания к выполнению работы

Решение

Пример 9.6

Определить класс формулы .

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

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

Пусть имеется предикат «», определенный в бесконечной области , где , тогда формула (читается «для всякого существует , для которых выполняется предикат , в данном случае предикат-условие «») тождественно истинная в области М и, следовательно, выполнима в этой области. Таким образом, исходная формула при данных условиях относится к классу выполнимых

Рассмотрим этот же предикат в конечной области , где . Тогда формула будет тождественно ложной в области , поскольку при условие «» не выполняется и, следовательно, не выполнима в области .

Из рассмотренного выше следует, что формула не общезначима.

Общезначимость и выполнимость связаны между собой, что устанавливают следующие теоремы.

Теорема 1. Для того, чтобы формула А была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.

Так, если формула А общезначима, то тогда – тождественно ложная формула в любой области, и поэтому формула невыполнима.

Теорема 2. Для того чтобы формула А была выполнимой, необходимо и достаточно, чтобы ее отрицание было не общезначимо.

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

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

1) ;

2) при выполняется равенство ;

3) ;

4) существует такое число , что ;

5) ;

6) однозначное число кратно 2;

7) ;

8) ;

9) ;

10) .

Решение примера 1.

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

Решение примера 2.

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

Решение примера 9.

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

2. Какие из следующих предикатов являются тождественно истинными:

1) ;

2) ;

3) ;

4) ;

5) .

Решение примера 1.

Согласно определению, «тождественно истинный предикат – это предикат, принимающий значение 1 при всех значениях . Для него выполняется условие ». Предикат 1 отвечает данному определению, поскольку при любых значениях и выполняется приведенное выражение, следовательно, это тождественно истинный предикат.

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

1) Земля ближе к солнцу, чем Венера;

2) Планеты и принадлежат Солнечной системе;

3) ;

4) ;

5) ;

6) Любое простое число не имеет делителей, отличных от себя и 1;

7) Ромб АВСD равен ромбу ;

8) Натуральное число не меньше 1;

9) ;

10) ;

11) .

Решение примера 1.

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

Решение примера 2.

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

Область определения этого предиката – множество планет, существующих во Вселенной, в том числе, и в Солнечной системе.

Множество истинности данного предиката – это множество всех планет, при которых предикат принимает значение «истина». Такое условие выполняется для всех планет Солнечной системы ={Меркурий, Венера, Земля, Марс,…}.

4. На множестве заданы два предиката : « – простое число», : « – нечетное число». Составить их таблицы истинности. Равносильны ли предикаты и на множествах:

1) ,

2) ,

3) ,

4) .

Решение примера на множестве .

Таблица истинности предикатов:

В таблице единицей обозначено истинное значение предиката и нулем – ложное.

Из таблицы видно, что данные предикаты неравносильны.

5. Найти множество истинности предикатов.

1) ; 2) ;

3) ; 4) ;

5) ; 6) ;

7) ; 8) .

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

Решение примера 1.

Согласно определению «множество истинности предиката – это множество всех элементов , при которых предикат принимает значение «истина (1)». В примере квадратное уравнение имеет корни , при которых оно становится истинным. Следовательно, множество истинности этогопредиката или более короткая запись: .

Решение примера 2.

Уравнение корней не имеет, следовательно, .

6. Найти множество истинности конъюнкций следующих предикатов, в которых предметные переменные принадлежат множеству всех действительных чисел R.

1) , 2) ,

3) , 4) ,

5) 6) 7) .

Решение примера 1.

Множество истинности предикатов , . , . Отсюда множество истинности конъюнкции предикатов .

7. Среди нижеследующих выражений установить, какие из них являются формулами предикатов, а какие не являются.

1) ,

2) ,

3) ,

4) ,

5) ,

6) .

Решение примера 1.

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

Решение примера 2.

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

8. На множестве однозначных натуральных чисел даны два предиката: предикат : «число 3 делитель »; предикат : «». Найти множество истинности предикатов

1) , 2) ,

3) , 4) ,

5) , 6) ,

7) , 8) .

Решение примера 1.

Множество истинности данных предикатов на множестве однозначных натуральных чисел : ; : . Тогда множество истинности дизъюнкции данных предикатов будет равно их объединению:

.

Решение примера 7.

Сначала приводим предикат к конъюктивно-дизъюнктивной форме:

Далее находим множество истинности предикатов и :

: ;

: .

Тогда множество истинности исходного предиката

9. На множестве заданы предикаты:

: « не делится на 5»;

: « – четное число»;

: « – простое число 5»;

: « кратно 3».

Найти множество истинности следующих предикатов:

1) ; 2) ;

3) ; 4) ;

5) ; 6) ;

7) ; 8) ;

9) ; 10) ;

11) ; 12) ;

13) ; 14) ;

15) ; 16) ;

17) ; 18) ;

19) ; 20) .

Решение примера 19.

Приводим предикат к конъюнктивно-дизъюнктивной форме

Находим множество истинности простых предикатов, составляющих исходный сложный предикат примера:

.

.

.

.

10. Установить, какие из следующих высказываний истинны, а какие ложны, при условии, что область определения предикатов совпадает с множеством действительных чисел R.

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) .

Решение примера 1.

Для решения необходимо находить либо корни уравнений, представленных в предикатах, либо множества действительных чисел, для которых они выполняются.

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

11. Предикат : « есть простое число»; предикат : « есть действительное число»; предикат : « меньше »; предикат : « есть рациональное число»;. Записать следующие утверждения, используя кванторы:

1) каждое рациональное число есть действительное число;

2) существует число, которое является простым;

3) для каждого числа существует такое число , что .

Решение примера 1.

.

12. Получить нормальную форму для формул:

1) ;

2) ;

3) ;

4) .

Решение примера 1.

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

Для начала приводим формулу к нормальной форме, то есть форме, которая содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания относится к элементарным формулам

Далее используем равносильность (1): для преобразования предиката с отрицанием

Затем применяем закон де Моргана для снятия общего отрицания

Наконец, используя правила выноса кванторов за скобки, получим

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

1) Друг моего друга – мой друг.

2) Если всякий разумный философ – циник, и только женщины являются разумными философами, то тогда, если существуют разумные философы, некоторые из женщин – циники.

3) Все политики – лицедеи. Некоторые лицедеи – лицемеры. Значит, некоторые политики – лицемеры.

4) Глупец был бы способен на это. Я на это не способен. Значит, я не глупец.

5) Каждый любит сам себя. Значит, кого-то кто-нибудь любит.

6) Все греки – люди. Все люди – смертны. Следовательно, все греки смертны.

Решение примера 1.

– друг моего друга; – мой друг.

.

3. В чем заключается необходимость в расширении логики высказываний и введения логики предикатов?

4. Дать определение логики предикатов, субъекта и предиката.

3.Что такое одноместный предикат, область определения и множество истинности предиката, тождественно истинный (ложный) предикат?

4. Понятие многоместного предиката, двухместный предикат.

5. Дать определение пяти логических операций над предикатами.

6. Что такое квантор?Понятия квантора всеобщности и существования, примеры их применения.

7. К каким восьми возможным высказываниям приводит использование кванторных операций к предикату ? Какие из них ложны, а какие истинны?

8. Дать подробную символику и определение формулы логики предикатов.

9. От каких переменных зависит логическое значение формулы предикатов?

10. Какие формулы логики предикатов являются равносильными?

11. Привести основные равносильности логики предикатов.

12. Нормальная и предваренная нормальная форма логики предикатов.

13. Дать определения выполнимых и общезначимых формул.

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

1. Лихтарников, Л. М. Математическая логика: курс лекций / Л. М. Лихтарников, Т. Г. Сукачева. – СПб.: Лань, 1998.

2. Игошин, В. И. Математическая логика и теория алгоритмов / В. И. Игошин. – М.: ACADEMA, 2004.

3. Шапорев, С. Д. Математическая логика: курс лекций и практических занятий / С. Д. Шапорев – СПб.: БХВ – Петербург, 2005.

4. Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М.: АЙРИС ПРЕСС, 2007.

Дата добавления: 2017-02-01; Просмотров: 97; Нарушение авторских прав?; Мы поможем в написании вашей работы!