Тема: «Предикаты. Кванторы. Предикатные формулы»

Цель занятия:

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

Пояснение к работе

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

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Какой предикат называется n -местным?

Какой предикат является высказыванием?

Какие операции можно выполнять над предикатами?

Что представляет собой область действия квантора?

Из чего состоит алфавит логики предикатов?

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

Какое выражение называется предикатной формулой?

2. Дать определение следующих понятий:

– предикат;

– квантор общности;

– квантор существования.

3. Выполнить задания для аудиторных занятий.

4. Выполнить задания для самостоятельной работы.

Предикаты

Предикатом Р (х ₁, х ₂, …, х _n) называется функция, переменные которой принимают значения из некоторого множества М, а сама функция принимает два значения: И (истинное) и Л (ложное), то есть

Р (х ₁, х ₂, …, х _n): М _n →{ И, Л }.

Предикат от n аргументов называют n -местным предикатом. Множество М значений переменных определяется математическим контекстом. Например, основное соотношение элементарной геометрии на плоскости – точки х, у, z лежат на одной прямой  – выражается предикатом L (х, у, z), где в качестве значений х, у, z рассматриваются конкретные точки.

Предикаты обозначаются большими буквами латинского алфавита. Иногда бывает удобно указывать число переменных у предикатов. В таких случаях у символов предикатов пишут верхний индекс, который и указывает число аргументов, например: Р^{( n)}(х ₁, х ₂, …, х _n) – n -местный предикат. Высказывания считаются нуль-местными предикатами.

Над предикатами на М как подмножествами М_Т можно производить логические операции и получать новые предикаты. Операции над предикатами – суть операции над соответствующими отношениями: конъюнкция, дизъюнкция, отрицание, импликация и др. Состав переменных и предметная область предиката, полученного в результате операции, определяются при этом естественным образом.

Пример.

Р (х ₁, х ₂, …, х _n) & Q(y ₁, y ₂, …, y_n) = R (х ₁, х ₂, …, х _n, y ₁, y ₂, …, y_n), х ₁ є M ₁, х ₂ є M ₂, …, х_n є M_n, у ₁ є N ₁, у ₂ є N ₂, …, у_n є N_n.

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

Примеры. 1. Пусть R (X, Y) = Р (Х) & Q(Y), X є M, Y є N, двуместный предикат R (X, Y) имеет область определения S = M · N.

2. R (X) = P (X) & Q (X), X є M, Y є M, но X и Y – разные предметные переменные; область определения двуместного предиката R (X, Y) – множество S = M².

3. R (X) = P (X) & Q (X): у предикатов P (X) & Q (X) – общая предметная область и одинаковая переменная; R (X) – одноместный предикат на М.

Существуют и другие операции над предикатами. Если P { X, Y) – двуместный предикат, то фиксирование одной переменной превращает его в одноместный предикат. Пусть, например, Р (Х, Y): "число X делится на число Y ", определенный на множестве пар натуральных чисел N, кроме пар (Х, 0). Тогда Р (Х, 5) – одноместный предикат на N, истинный для всех чисел, кратных 5. P (60, Y)  – одноместный предикат на N, кроме Y = 0, истинный для всех делителей числа 60, т. е. для элементов множества {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Заметим, что если зафиксировать значения всех переменных, то предикат превращается в истинное или ложное высказывание, которое можно считать 0-местным предикатом.

Кванторы

Для предикатов определяются две специфические операции, называемые навешиванием кванторов, которые превращают одноместный предикат Р (х)в 0-местный:

Квантор общности, или всеобщности, – высказывание: "для всех х выполнено Р (х)", обозначение " х: Р (х).

Квантор существования – высказывание: "существует x, для которого выполнено Р (х) ", обозначение $ х: Р (х).

Процедура навешивания кванторов применима не только к одноместным, но и к предикатам большей местности. Рассмотрим трехместный предикат P (x, y, z);он является истинным для некоторых троек (x, y, z). Предикату Р можно сопоставить выражения с кванторами " Х: P (x, y, z)и $ х: P (x, y, z); первое означает: "для всякого x выполнено Р (х, y, z)", второе – "существует х такой, что выполнено Р (х, y, z) ".

Пусть, например, P (x, y, z) = З х - 2 у > z с предметной областью – множеством действительных чисел R, область истинности предиката Р – полупространство по одну сторону от плоскости З х - 2 у = z. Ему можно сопоставить выражения:

Q_l(x, y) = " х: 3 х - 2 у > z и Q₂(x, y) = $ x: 3 x - 2 y > z.

Полученные двуместные предикаты зависят от y и z, но не зависят от x. Этот факт выражается так: переменная x в указанных предикатах связана квантором, а переменные y, z – свободные. Связанные (свободные) переменные – это переменные, на которые навешены (соответственно, не навешены) кванторы: " или $.

Область действия квантора – выражение, на которое навешивается квантор.

Предикатные формулы

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

– символы предметных переменных х ₁, х ₂,..., х _n.

– символы предикатов Р ₁, Р ₂, … Р _n;

– логические символы Ø, &, V, É, ~;

– символы кванторов $ и ";

– скобки и запятая.

Предикатные переменные будем обозначать через х, у, z, а символы предикатов – через P, S, Q, R и т. д. Предикатной формулой (одновременно определяются понятия свободных и связанных переменных) называется выражение, построенное по следующим правилам:

1. Если Р –  символ предиката, х ₁, х ₂,..., х_n – символы переменных (не обязательно различных), то Р (х ₁, х ₂,..., х_п) – предикатная формула; все ее переменные – свободные, связных переменных нет.

2. Если А – формула, то (Ø А) тоже формула. Свободные и связанные переменные этой формулы – это свободные и связанные переменные формулы А.

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

(А & В), (A v В), (А É В), (А ~ В)

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

4. Если А – формула, содержащая свободную переменную х, то выражения

(" х) А(х) и ($ х) А(х)

тоже предикатные формулы; в каждой из них переменная х переходит из множества свободных в множество связанных, т. е. число свободных переменных уменьшается, а число связанных увеличивается на 1. При этом формула А называется областью действия квантора " х и областью действия $ х.

5. Слово в алфавите логики предикатов является формулой только в том случае, если это следует из правил 1–4.

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

Пример 1. " х ₁$ х ₂: P (х ₁, х ₂, х ₃) É " х ₁: Р (х ₁, х ₄) –

формула, в которой х ₁, х ₂  – связанные, а х ₃, х ₄ – свободные переменные.

Пример 2. Выражение $ х ₁" х ₂: P ₁ (х ₄, х ₃) & Р ₂(х ₄, х ₂) не является формулой.

Задания

Для аудиторных занятий

1. Определить истинность следующих высказываний для х, у Î N:

" х " у: х < у; $ х $ у: х < у; " у $ х: х < у; $ у " х: < у.

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

а) если целое число k делится на 4, то оно делится и на 2;

б) каждое целое число, делящееся на 4, делится на 2;

в) (a + b)²  = a ² + 2 ab + b ²;

г) х ² + 2.

3. Среди следующих высказываний указать истинные:

а) если х ₁, х ₂ – действительные корни уравнения 2 х ² + 42 х + 446 = 0, то х ₁ + х ₂ = -21;

б) если натуральное число х делится на 3, то 2^х делится на 8.

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

а) (p Ú q) Ù ((p ® q) ® r);   б) (p Ú q ® r).

5. На примере предикатов P (х): х > 2 и Q (у): у < 5 построить предикаты P (х) & Q (х), P (х) Ú Q (х), P (х) → Q (х), Q (х) → P (х), P (х) Ú Q (у), P (х) & Q (у), P (х) → Q (у), P (у) & Q (х).

6. Пусть Р (х) означает предикат «х делится на два», Q (х) – предикат «х делится на 3». Что в этом случае означает предикат Р (х) & Q (х)? Какой из предикатов (" х)(Р (х) & Q (х)); ($ х)(Р (х) & Q (х)) является истинным или ложным?

7. Пусть Р (х) означает предикат «х = у». Он принимает значение И тогда и только тогда, когда х = у. При каких значениях х и у предикат

Ø Р (2)(х, х) É Р (2)(х, у) принимает значение И?

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

а) (" х) Р (х); б) (" х) Р (х) ® Р (у); в) ($ х) (А (х) Ù В (х)).

9. Примем следующие обозначения для предикатов: Р (х) – «х - простое число», Е (х) – «х – четное число», D (x, y) – «у делится на х», I (х, у) – «х равно у». Перевести на обычный язык:

а) Р (7); б) ($ х) (Е (х) Ù D (6, х)).

10. Используя только предикаты x / y и x = y, записать при помощи логических символов следующие предикаты от переменных, принимающих натуральные значения:

а) х имеет ровно два различных простых делителя; б) а и b – простые числа-близнецы.

Для самостоятельной работы

1. Определить истинность следующих высказываний для х, у Î N:

" х " у: х > у; $ х $ у: х > у; " у $ х: х > у; $ у " х: > у.

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

а) если целое число k делится на 8, то оно делится и на 12;

б) каждое целое число, делящееся на 8, делится на 12;

в) n ^{3 –} n делится на 3;

г) х ² > 2.

3. Среди следующих высказываний указать истинные:

а) существует действительное число х, такое, что х ² + 2 х – 3 = 0;

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

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

а) (p ® q) Ù Ø p ® Ø q; б) Ø p Ú q ® p Ù q.

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

а) (" у) Р (х) Ú В (у); б) (" х) (" у) Р (х) ® Р (у); в) ($ х) (Р (х) Ú А (х)).

6. Примем следующие обозначения для предикатов: Р (х) – «х - простое число», Е (х) – «х – четное число», D (x, y) – «у – делится на х». Перевести на обычный язык:

а) Е (2) Ù Р (2); б) (" х) (D (2, х) ® Е (х)).

7. Прочитайте следующие высказывания о целых положительных числах. Какие из них истинные, а какие ложные? Приняты обозначения: Р (х) – «х - простое число», x / y – «у делится на х», х c у – «у не делится на х»:

а) (" х) (Р (х) ® 2c х); б) ($ х) (" у) (х / у); в) (" х) ($ у) (Р (у) Ù у / х).

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

а) существует такое целое х, что х ² – 4 = 0;

б) существует единственное положительное число х, для которого

х ² – 4 = 0;

в) для любого действительного числа х существует такое действительное число у, что у ² = х.

9. Используя только предикаты x / y и x = y, записать при помощи логических символов следующие предикаты от переменных, принимающих натуральные значения:

а) х – простое число; б) а и b – взаимно простые числа.

10. Пусть Р (х) означает предикат «х делится на 3», Q (х) – предикат «х делится на 5». Что в этом случае означает предикат Р (х) Ù Q (х)? Какой из предикатов (" х)(Р (х) Ù Q (х)); ($ х)(Р (х) Ù Q (х)) является истинным или ложным?

Литература

1. Куликов, Л. Я. Сборник задач по алгебре и теории чисел / Л. Я. Куликов, А. И. Москаленко, А. А Фомин. – М.: Просвещение, 1993. – 288 с.

2. Нефедов, В. Н. Курс дискретной математики: учеб. пособие / В. Н. Нефедов, В. А. Осипова. – М.: Изд-во МАИ, 1992. – 264 с.

 

 

Людмила Ивановна Кухарева, Елена Васильевна Морозова

 

ПРАКТИКУМ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

 

Учебное пособие

 

Редактор Пчелинцева М. А.

Компьютерная верстка Сарафановой Н. М.

Темплан 2010 г., поз. № 38К.

Подписано в печать 10. 02. 2010 г. Формат 60×84 ¹/₁₆.

Бумага листовая. Печать офсетная.

Усл. печ. л. 4,25. Усл. авт. л. 4,06.

Тираж 100 экз. Заказ №

 

Волгоградский государственный технический университет

400131, г. Волгоград, пр. Ленина, 28, корп. 1.

Отпечатано в КТИ

403874, г. Камышин, ул. Ленина, 5, каб. 4.5