Занятие 6

Темы:

Понятие предиката, операции над предикатами.

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

Упражнения

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

1. x+5=1;

б) при x=2 выполняется равенство x²-1=0;

в) x+2<3x-4;

г) однозначное число x кратно 3;

д) x²+y²>0.

2. Пусть даны предикаты: P(x): “ x – четное число “ и Q(x): “x кратно 3”, определенные на множестве N. Найти области истинности предикатов:

а) ; в) ;

б) ; г) .

2. На множестве M={1,2,3,…,20} заданы предикаты:

а) A(x): ” x не делится на 5 “; в) C(x): “x – число простое “;

б) B(x): ”x – четное число “; г) D(x): “x кратно 3”.

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

а) ; е) ;

б) ; ж) ;

в) ; з) ;

г) ; и) .

д) ;

е) ;

4. Изобразите на координатной плоскости области истинности предикатов:

а) ;

б) ;

в) ;

г) .

5. Укажите, какие из следующих выражений являются формулами логики предикатов. В каждой формуле выделите свободные и связанные переменные:

а) ; в) ;

б) ; г) .

6. Показать, что кванторы общности и существования не перестановочны, то есть высказывания и могут, вообще говоря, иметь различные значения.

Занятие 7

Темы:

Ощезначимость и выполнимость формул логики предикатов;

Предваренная нормальная форма (ПНФ);

Применение языка логики предикатов.

Упражнения

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

1. ;

б) ;

в) ;

г) .

2. Найти отрицание следующих формул:

1. ; г) .

б) ;

в) ;

3. Привести к ПНФ следующие формулы логики предикатов:

1. ; г) ;

б) ; д) ;

в) ; е) .

2. Записать на языке логики предикатов:

1. определение предела числовой последовательности

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

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

1. “ Для лечения любой давно известной болезни в медицине имеется лекарство. Появились новые болезни, для лечения которых еще не существует лекарств”.

б) Каждый студент ЮРГТУ (НПИ), который учится отлично, получает повышенную стипендию. Иванов учится отлично, следовательно, Иванов получает повышенную стипендию”.

Литература

1. Горбатов В.А. Фундаментальные основы дискретной математики. – М.: Наука, 1999. – 540с.

2. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2000. – 301с.

3. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986. – 342с.

4. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984. – 319с.

5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логики и теории алгоритмов. – М.: Физматлит, 1995. – 255с.

6. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. – СПб.: Изд - во “Лань”, 1998. – 288с.

Учебно – практическое издание

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ ПО КУРСУ

”Дискретная математика”

Составители: Скоба Андрей Николаевич,

Панфилов Александр Николаевич

Редактор Н. А. Юшко

Темплан 2001г. ЛР№20417 от 12. 02. 97г. Подписано в печать 18.12. 2001г.

Формат 60х84 1/16. Бумага офисная. Печать оперативная.

Печ. Л. 0,7. Уч. – изд. Л . 0,75. Тираж 50