Практическое занятие № 13. Применение логики предикатов

 

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

Примеры выполнения заданий

Запишите определение на языке логики предикатов, используя ограниченные кванторы, и постройте его отрицание:

Функция f непрерывна в точке x₀, если и только если для всякого положительного числа e существует положительное число d такое, что для всякого x из области определения D функции f, если |x - x₀| < d, то
|f(x) - f(x₀)| < e.

Решение. Запишем это определение на языке логики предикатов двумя разными способами.

1 способ:

, где

2 способ, используя ограниченные кванторы:

Построим отрицание этого определения:

Задания для самостоятельного выполнения

 

1. Запишите аксиомы положительных величин на языке логики предикатов, используя ограниченные кванторы:

 

0) Коммутативность сложения

Для любых двух величин a, b Î A справедливо a + b = b + a.

1) Ассоциативность сложения

Для любых двух величин a, b, с Î A справедливо a + (b + c) = (a + b) + c.

2) Монотонность сложения

Для любых двух величин a, b Î A справедливо a + b > a.

3) Транзитивность отношения

Для любых трех величин a, b, с Î A. Если a < b и b < c, то a < c.

4) Возможность суммирования

Для любых двух величин a, b, с Î A существует однозначно определенная величина c = a + b.

5) Возможность вычитания

Для любых двух величин a, b, с Î A если a > b, то существует одна и только одна величина c Î A, для которой b + c = a.

6) Возможность деления

Какова бы ни была величина a Î A и натуральное число n, найдется такая величина b Î A, что n * b = a.

7) Возможность сравнения

Для любых двух величин a, b Î A имеет место одно из трех отношений:
a = b, a < b, a > b.

8) Аксиома Архимеда или Евдокса

Каковы бы ни были величины a, b Î A, существует такое n, что n* b > a

9) Аксиома соизмеримости отрезков

Пусть последовательность величин a_i Î A, i = 1…n обладает свойством
a₁ < a₂ <… < a_n <…, а последовательность b_i Î A, i = 1…n свойством
b₁ < b₂ <… < b_n <…, при этом a_i < b_i для любых i, j Î N.

Пусть для любого e > 0 существует такое N(e), что при всех n > N разность |a_n – b_n| < e. Тогда существует единственный элемент cÎ A, удовлетворяющий условиям a_i < с, с < bj для любых i, j Î N.

 

 

2. Подберите элементарные предикаты и запишите следующие высказывания:

0) a) каждое положительное действительное число является квадратом другого;

b) натуральное число, которое делится на 6, разделится и на 2;

1) a) для каждого натурального числа существует одно и только одно число, непосредственно следующее за ним;

b) каждое действительное число является кубом другого;

2) a) натуральное число, которое делится на 6, разделится и на 3;

b) произведение двух натуральных чисел, одно из которых четное, другое нечетное, есть число четное;

3) a) от перемены мест сомножителей произведение не меняется;

b) натуральное число, которое делится на 2 и 3, разделится на 6;

4) a) натуральное число, которое делится на 9, разделится на 3;

b) от перемены мест слагаемых сумма не меняется;

5) a) частное от деления двух натуральных четных чисел, если оно существует, есть число четное или нечетное;

b) если произведение двух натуральных чисел делится на 5, то хотя бы один из сомножителей делится на 5;

6) a) для чисел отличных от нуля существует наибольший общий делитель;

b) если произведение двух натуральных чисел делится на 12, то среди них есть четное число, делящееся на 3;

7) a) если произведение двух натуральных чисел делится на 18, то хотя бы один сомножитель делится на 6 или хотя бы один из сомножителей нечетный;

б) сумма двух натуральных чисел, имеющих различную четность, нечетна;

8) a) для чисел отличных от нуля существует наименьшее общее кратное;

б) если ни одно из двух натуральных чисел не делится на 11, то их произведение не делится на 11;

9) а) если произведение двух натуральных чисел делится на 12, то хотя бы один из сомножителей делится на 3 или хотя бы один из сомножителей четный;

б) сумма двух натуральных четных чисел, есть число четное.

 

 

Рекомендуемая литература

 

1. Акимов О.Е. Дискретная математика: логика, группы, графы.- М: Лаборатория Базовых Знаний, 2003 2. Верещагин Н.К., Лекции по математической логике и теории алгоритмов в 3-х т. МЦНМО 3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики - М.: Наука, 2003. 4. Горбатов В.А. Фундаментальные основы дискретной математики: информатика и математика.- М: Наука. Изд.фирма «Физ.-мат.лит», 2001 5. Гульден Я., Джексон Д. "Перечислительная комбинаторика", - М.: Наука, 2004. 6. Иванов Б.Н. Дискретная математика: алгоритмы и программы. Лаборатория Базовых Знаний, 2003 7. Карпов В.Г., Мощенский В.А. Математическая логика и дискретная математика. – Минск: Вышэйш. школа, 2001

8. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.:Энергоатомиздат, 2001 9. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 2001 10. Липский В. Комбинаторика для программистов. – М.: Мир, 2004. 11. Лихтарников Л.М, Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб: Лань, 2001

12. Лорьер Ж.Л. Системы искусственного интеллекта. – М.: Мир, 2001. 13. Мальцев А.И. "Алгоритмы и рекурсивные функции", - М.: Наука, 2005. 14. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 2002. 15. Новиков Ф. Дискретная математика для программистов. - СПб: Питер, 2000 16. Оре О. Теория графов. – М.: Наука, 2001. 17. Риордан Дж. "Введение в комбинаторный анализ", - М.: ИЛ. 2003. 18. Романовский И.В. Дискретный анализ. – СПб: Невский диалект, 2003 19. Фляйшнер Г. Эйлеровы графы и смежные вопросы – М.: Мир, 2002 20. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 2001

 

[1] Самая популярная формулировка принципа Дирихле звучит так:

"Если в n клетках сидит n+1 или больше зайцев, то найдётся клетка, в которой сидят, по крайней мере, два зайца".

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