Операции над предикатами
Практическое занятие № 15
1 Наименование работы: Операции над предикатами.
2 Цель работы: Научиться производить операции над предикатами.
3 Подготовка к занятию: Повторите тему: Предикаты. Кванторы.
4 Литература:
4.1 Конспект лекций по учебной дисциплине «Элементы математической логики»
4.2 Приложение к ПЗ №15
5 Перечень необходимого оборудования и материалов:
5.1 Бланк для отчета.
5.2 Канцелярские принадлежности.
6 Задание на занятие:
Основная часть
6.1 Заданы предикаты:
Используя , запишите высказывания:
а)
б)
в)
г)
6.2 Предикат P (x, y) задан следующей таблицей:
Y
|
|
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
|
2
|
1
|
0
|
1
|
0
|
0
|
1
|
|
3
|
0
|
0
|
1
|
0
|
1
|
0
|
|
4
|
1
|
1
|
1
|
1
|
0
|
1
|
X
Определите значение высказываний
а) xy P(x, y)
б) xy P(x, y)
в) xy P(x, y)
г) xy P(x, y)
д) yx P(x, y)
е) yx P(x, y)
6.3 Какие вхождения переменных являются свободными, а какие связанными в следующих формулах:
а) б)
6.4 На множестве М = {1, 2, 3...20}заданы предикаты:
Р(Х) - "число Х кратно 5"
Q(x) - "число Х четное"
R(x) - "число Х кратно 3"
S(x) - "число Х составное"
Сформулируйте следующие предикаты и найдите для каждого множество истинности
а) Р (Х)Q(x) б) Р(Х)Q(x)
в) P(x)S(x) г) P(x)S(x)
д) Р (Х)Q(x) S(x) е) Р(Х)Q(x)S(x)
ж) Р (Х)R(x) S(x) з) Р(Х)R(x)S(x)
6.5 На множестве M = {3, 6, 9, 12 42} определены предикаты:
P(x) - "число Х делится на 6"
Q(x) - "число Х 30"
Найдите область истинности предиката
Вариативная часть
6.6 Пусть известно, что (n нечетно() (n =2к+1)).
а) Какое их этих утверждений истинно?
7 нечетно () (7=2к+1));
6 нечетно () (6=2к+1)).
б) Какое из этих утверждений истинно и почему?
() (7=2к+1)); () (6=2к+1)).
6.7 Запишите приведенные ниже утверждения в символьной форме с помощью предикатов и кванторов.
а) Сумма любых трех последовательностей целых чисел делится на 3.
б) Среди трех любых целых чисел, найдутся два, сумма которых четна. Истинно ли это утверждение?
6.8 Запишите в виде высказывания
а) (ABC)(окр l )(A,B,C)*
б) ( a, b, R, a 0)( R)(ax = b)
6.9 Запишите приведенные ниже утверждения в символической форме, введя предикаты. В случае необходимости укажите предметную область.
а) Некоторые машины умнее людей.
б) Любой играет в теннис лучше Фрэда.
в) Для каждого действует существует равное и противоположно направленное противодействие.
г) Каждый игрок в гольф, в конце концов, будет обыгран более сильным игроком.
6.10 Если , то утверждение
ложно. Если универс – множество положительных целых чисел, то что можно сказать об истинности
а) ?
б) ?
в) ?
г) ?
___________________________________________
* знак читается, как «существует и, при том, только один (одна)».
7 Порядок выполнения работы:
Выполните практическую работу в соответствии с заданиями (основная часть 6.1 – 6.5) и сдайте зачет. В случае получения зачета, выполните вариативную часть (6.6 – 6.10).
8 Содержание отчета:
Решения задач в соответствии с заданием.
9 Контрольные вопросы:
1 Что обозначают и как читаются кванторы ?
2 Какая переменная считается свободной, а какая связанной?
3 Какие операции алгебры высказываний применимы к предикатам, определенным на одном и том же множестве?
Приложение к практическому занятию по ЭМЛ № 15
Кванторы
К предикатам, определенным на одном и том же множестве, можно применять операции алгебры высказываний: конъюнкции, дизъюнкцию, импликацию, эквивалентность, отрицание и получать новые предикаты.
Пример 1. если к предикатам «x = y» и «x < y» - обозначим их соответственно Р(х, y) и Q(x, y) – применить операцию дизъюнкции, то получим новый предикат Р(х, y) Q(x, y).
Помимо операций алгебры высказываний, в логике предикатов есть две операции, которые связаны с природой предикатов. Этот процесс выполнения этих операций называется навешиванием кванторов общности или существованием. Иногда эту операцию называют квантификацией ей переменных. Пусть дан предикат Р(х), зависящий от одной переменной и определенный на поле М.
Выражение (х) Р(х) означает высказывание, истинное только в том случае, когда предикат Р(х) истинен для всех предметов из поля М. Выражение (х)Р(х) читается «для всякого х, выполняется Р(х)», здесь символ - квантор общности.
О высказывании Р(х) говорят, что оно получено из предиката Р навешиванием квантора всеобщности по переменной х.
Выражение (х) Р(х) означает высказывание, истинное только в том случае, когда предикат Р(х) истинен хотя бы для одного предмета из поля М. Выражение (х)Р(х) читается «существует х, такой, что выполняется Р(х) »; символ - квантор существования.
|
Название
|
Прочтение
|
Обозна-чение
|
|
Квантор общности
|
«все», «всякий», «каждый», «любой»
|
|
|
Квантор существования
|
«хотя бы один», «найдется», «существует»
|
|
О высказывании Р(х) говорят, что оно получено из предиката Р навешиванием квантора существования по переменной х.
Рассмотрим примеры применения операций квантирования к предикатам.
Пример 2. Пусть даны предикаты над полем натуральных чисел:
а) , тогда – истинное выражение;
б) , тогда – ложное высказывание;
в) , тогда – истинное высказывание;
г) , тогда – ложное высказывание.
Для двуместных предикаты возможны следующие восемь комбинаций:
Итак, одноименные кванторы можно менять местами, а разноименные – нельзя.
Пример 3. : всякое число имеет противоположное – истинное высказывание,
: существует число, противоположное любому, - ложно.
Рассмотрим некоторые общие свойства введенных операторов.
В соответствии с определениями кванторов логическая переменная z в выражениях
уже не является функцией предметной переменной х.
Для того чтобы отметить отсутствие функциональной зависимости z от х, предметную переменную х в таких случаях называют связанной.
Несвязанные переменные называют свободными.
Пример 4. В предикате
переменные х и z – связанные, а y и u – свободные.
Пример 5. Задан предикат .
Запишите высказывание
Решение. Существуют х и y такие, что
Пример 6. Запишите приведенные ниже утверждения в символической форме, введя предикаты. В случае необходимости укажите предметную область
«На каждой улице будет праздник»
Решение. Предметная область для х – множество всех улиц. Область для y – множество всех праздников. .
Пример 7. Если , то утверждение
- ложно. Если универс – множество положительных целых чисел, то что можно сказать об истинности ?
Решение. Истинно, т.к. для любых x и y найдется такое значение z, что будет выполнятся условие .
Работу составила преподаватель Т.С. Пронина
Операции над предикатами