Доказать, что следующие функции вычислимы 1 страница

63-2009

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

к выполнению лабораторных работ 4-7

по дисциплине

«Математическая логика и теория алгоритмов»

для студентов специальности 230101

«Вычислительные машины, комплексы, системы и сети»

очной, сокращенной очной, заочной и сокращенной заочной форм обучения

Воронеж 2009

Составители: канд. техн. наук Л.В. Холопкина,

ст. преп. М.П. Носачева

УДК 681.3.06:800.92(075)

Методические указания к выполнению лабораторных работ 4-7 по дисциплине “Математическая логика и теория алгоритмов” для студентов специальности 230101 очной, сокращенной очной, заочной и сокращенной заочной форм обучения / ГОУВПО «Воронежский государственный технический университет»; сост. Л.В. Холопкина, М.П. Носачева. Воронеж, 2009. 54 с.

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

Предназначены для студентов второго курса.

Табл.1. Библиогр.: 5 назв.

Рецензент канд. техн. наук, доц. А.А. Кисурин

Ответственный за выпуск зав. кафедрой д-р техн. наук,

проф. С.Л. Подвальный

Печатается по решению редакционно-издательского совета Воронежского государственного технического университета

технический университет», 2009

ЛАБОРАТОРНАЯ РАБОТА № 4

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

1. ЦЕЛЬ РАБОТЫ

Целью работы является усвоение основных понятий теории предикатов и приобретение навыков практической работы с формулами логики предикатов.

2. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

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

Например, множество истинности для предиката - “ ” задаётся так: , где – множество целых чисел. Множеством истинности для предиката – “Диагонали параллелограмма перпендикулярны” является множество всех ромбов. Областью определения этого предиката является множество всех параллелограммов.

Предикат, определенный на множестве , называется тождественно истинным, если , и тождественно ложным, если .

Двуместным предикатом называется функция двух переменных и , определенная на множестве ( – области определения переменных и соответственно) и принимающая значения из множества . Например, предикат равенства ” ” определен на множестве ( – множество действительных чисел). Примерами двуместных предикатов являются: , , .

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

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

операции исчисления высказываний: отрицание, дизъюнкция, конъюнкция, импликация, эквиваленция и для них справедливы все эквивалентности исчисления высказываний.

2.1. Кванторные операции

Определим предикат - “число делится на число ”. . Истинность этого высказывания является частичной, так как можно выбрать числа и

такие, что не делится на . А предикат - “простое число делится только на самого себя и единицу” является универсально истинным, так является истинным для любого значения x.

В логике предикатов частичная и всеобщая истинность обозначается отдельными специальными знаками – кванторами.

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

1. Неопределенное высказывание истинно для всех .

2. Неопределенное высказывание истинно хотя бы для одного элемента , или другими словами, существует элемент множества , для которого - истинно.

Высказывания 1 и 2 в короткой форме будут выглядеть соответственно так:

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

Итак, под выражением понимается высказывание, истинное, когда истинно для каждого элемента из множества и ложное в противном случае. Это высказывание уже не зависит от . Под выражением понимается высказывание, которое является истинным, если существует элемент , для которого истинно, и ложным в противном случае.

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

Переменная , входящая в предикат , называется свободной переменной. Переменная , входящая в выражение , называется переменной, связанной квантором всеобщности. А переменная , входящая в выражение - переменная, связанная квантором существования.

Кванторные операции применимы и к многоместным

предикатам. Пусть на множестве задан предикат .

Применение кванторной операции к предикату по переменной ставит в соответствие двуместному предикату одноместный предикат , зависящий от переменной и не зависящей от переменной . К двуместному предикату можно применять кванторы, как по переменной , так и по переменной , при этом возможны следующие варианты: ; ; ; ; ; ; ; .

Правила перестановки кванторов.

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

являются общезначимыми.

Разноименные кванторы можно переставлять не всегда.

Справедлива теорема: Для каждой формулы и любых предметных переменных и формула

логически общезначима, а обратная импликация

не всегда является логически общезначимой.

2.2. Равносильности логики предикатов

Помимо эквивалентностей логики высказываний для логики предикатов справедливы следующие эквивалентности (, , - предикаты, a - высказывание):

Комбинация кванторов:

1. ;

2. ;

3. .

Комбинация кванторов и отрицаний:

;

Расширение области действия кванторов ( не зависит от ):

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Расширение области действия кванторов:

1. ;

2. ;

3. ;

4. ;

5. /

2.3. Предваренная, сколемовская нормальная и сколемовская стандартная формы

Нормальная форма. Формула логики предикатов имеет нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам. Например, для формулы нормальной формой будет .

Предварённая нормальная форма (ПНФ) - нормальная форма, в которой кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики. Например, для нормальной формы предваренной нормальной формой будет .

Всякую формулу логики предикатов можно свести к ПНФ, если использовать следующий алгоритм:

Шаг 1. Исключение логических связок и .

Шаг 2. Продвижение знака отрицания до атома. Многократно (пока это возможно) делаются замены:

Шаг 3. Переименование связанных переменных.

Шаг 4. Вынесение кванторов. Для вынесения кванторов используются формулы эквивалентности для исчисления предикатов.

После выполнения четвертого шага получаем ПНФ.

Остановимся более подробно на третьем пункте алгоритма - переименовании переменных.

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

Пример 1. Пусть имеем формулу . Нормальная формула имеет вид .

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

В полученной формуле переменную можно переименовать на в первой посылке и на во второй посылке, либо оставить во второй посылке без изменения

Формула называется ‑ формулой, если она представлена в ПНФ, причем кванторная часть состоит только из кванторов всеобщности, т.е. , где – бескванторная формула. Отсюда возникает задача устранения кванторов существования в формулах, представленных в ПНФ. Это можно сделать путем введения сколемовских функций.

Сколемовская нормальная форма (СНФ) строится в соответствии со следующими правилами:

1. Формула логики предикатов представляется в ПНФ.

2. Последовательно (слева направо) вычеркиваем каждый квантор существования, например , заменяя все вхождения переменной на новый еще не использованный функциональный символ , в качестве аргументов берем все переменные, связанные предшествующими кванторами всеобщности. Функциональный символ называется сколемовской функцией. Формула логики предикатов, полученная после выполнения шагов 1 и 2, называется сколемовской нормальной формой (СНФ).

Пример

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

На следующем шаге вычеркиваем квантор существования и все вхождения переменной заменяем на функцию

На последнем шаге вычеркиваем квантор .

3. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

Задание 1

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

1. Число - простое; 2. ; 3. ;

4. ; 5. Все подобные треугольники равны;

6. ;

7. Все четные числа делятся на число ;

8. Все четные числа делятся на 2;

9. 8 – нечетное число;

10. Имеется бесчисленное множество различных простых чисел;

11. Число не является простым.

Задание 2

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

1. ; 2. ;