3. 
- «все люди любят всех людей».
4.
- «существует человек, который кого-то любит» .
5.
- «существует человек, который любит всех людей».
6.
- «для всякого человека существует человек, который его любит» или «каждого человека кто-то любит».
Из приведенного выше примера можно сделать вывод о том, что перестановка кванторов общности и существования меняет смысл высказывания, т.е. кванторы общности и существования не обладают в общем случае свойством коммутативности. Итак, одноименные кванторы можно менять местами, разноименные кванторы менять местами нельзя.
Тема 4.4 Понятие предикатной формулы.
Напомним некоторые из определений и введем понятие формулы логики предикатов аналогично тому, как это было сделано в логике высказываний.
Зададим сначала алфавит символов, их которых будем составлять формулы:
предметные переменные: х, у, z, xi, yi,zi (i – натуральное число);
предикатные буквы: P, Q, R, …;
символы операций – отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции;
кванторы общности и существования;
вспомогательные символы – скобки, запятая.
Определение.
Всякий нуль-местный предикатный символ – формула.
Всякий n–местный предикатный символ – формула.
Если F – формула, а - предметная переменная, то F) и (F) – формулы.
Если F1 и F2 – формулы, то - формулы.
Никаких других формул в логике предикатов нет.
Определение. Формулы, определенные в п. 1 и 2, называются элементарными. Формулы, не являющиеся элементарными, называют составными.
Пример
Р; Q(x, y, z); R(x1, x2) – элементарные формулы.
х (Р(x, y, z); x (y (P(x, y, z))); - составные формулы.
Формула F в формулах вида F) и (F) называется соответственно областью действия квантора или .
Вхождение переменной в формулу называется связанным, если оно находится в области действия квантора по этой переменной или является вхождением в этот квантор; вхождение, не являющееся связанным, называется свободным (область действия квантора всегда однозначно определяется по виду формулы).
Переменная называется свободной в формуле, если хотя бы одно ее вхождение в этой формуле свободно.
Формулы без свободных предметных переменных называются замкнутыми, а формулы, содержащие свободные переменные – открытыми.
Тема 4.5 Равносильность предикатов. Исчисление предикатов.
Пусть формулы А и В имеют одно и то же множество свободных переменных.
Формулы А и В равносильны в данной интерпретации, если на любом наборе значений свободных переменных они принимают одинаковые значения (т. е. если формулы выражают в данной интерпретации один и тот же предикат).
Формулы А и В равносильны на множестве М, если они равносильны во всех интерпретациях, заданных на множестве М..
Формулы А и В равносильны в логике предикатов, если они равносильны на всех множествах (АВ).
Укажем несколько правил перехода от одних формул к другим, им равносильным.
Для формул логики предикатов сохраняются все равносильности и правила равносильных преобразований логики высказываний.
Утверждение. Всякую формулу логики предикатов, содержащую символы и , можно преобразовать в равносильную ей формулу, не содержащую этих символов.
Кроме этого, существуют следующие правила:
Перенос квантора через отрицание
Вынос квантора за скобки
Перестановка одноименных кванторов
х у А(х, у) у х А(х, у),
х у А(х, у) у х А(х, у).
Переименование связанных переменных.
Заменяя связанную переменную формулы А другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора получаем формулу, равносильную А.
Формула А, равносильная формуле В, и не содержащая символов , , а также составных формул под знаком отрицания, называется приведенной формой формулы В.
Теорема. Для любой формулы существует равносильная ей приведенная формула, причем множества свободных и связанных переменных этих формул совпадают.
Пример. Преобразовать в приведенную форму формулу .
Решение.
Приведенная формула называется нормальной (ПНФ), если она не содержит символов кванторов или все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы.
Пример. Преобразовать в ПНФ формулы:
1. ;
2. .
Решение.
1.
2.
Самостоятельная работа №9.
Тема 4.6 Бинарные отношения и их свойства.
Декартовым произведением двух множеств называется .
Бинарным отношением между множествами А и В называется всякое подмножество их декартового произведения.
Бинарное отношение – множество, состоящее из двоек чисел.
Если тогда бинарным отношением между А и В будет 2mn.
Среди всех бинарных отношений выделяют две и дают им следующие названия:
универсальное бинарное отношение – состоит из всех элементов множества .
нулевое бинарное отношение – не содержит ни одного элемента и совпадает с пустым множеством.
Бинарным отношением на множестве А называется любое подмножество
Обратным бинарным отношением к бинарному отношению Р называется множество Р-1: .
Свойства бинарных отношений:
Бинарное отношение Р на множестве А называется рефлексивным, если для любого элемента х множества А, двойка чисел .
Бинарное отношение Р называется симметричным, если из того что двойка чисел следует, что .
Бинарное отношение Р называется антисимметричным если из того, что двойка чисел и следует, что .
Бинарное отношение называется транзитивным, если из того, что и следует, что .
Бинарное отношение Р называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Самостоятельная работа №10.
Контрольная работа
Вариант 1
Первый уровень сложности – задачи №№ 1,2,3 – оценка “удовлетворительно”
Второй уровень сложности – любые четыре задачи – оценка “хорошо”
Третий уровень сложности – все задачи – оценка “отлично”
1. Найти области истинности следующих предикатов:
а). « на множестве действительных чисел R »
б). « на множестве действительных чисел R »
в). «  на множестве действительных чисел»
2. Дана формула  . Являются ли вхождения переменной x свободными?
3. Высказывательная форма x+y=z , с переменными, упорядоченными по алфавиту и принимающими значения из множества однозначных натуральных чисел, задаёт предикат F(x,y,z) . Выпишите тройки чисел, компоненты которых находятся в отношении F.
4. Задано бинарное отношение  . Определите свойства заданного бинарного отношения (рефлексивность, симметричность, антисимметричность и транзитивность).
5. Пусть бинарные отношения P и S определены на М, где М-множество всех людей следующим образом:
P= {(x,y) | x,y M,x является отцом y}
S= {(x,y) | x,y M,x - дочь y}
Описать явно следующие отношения:
а). PS b)  c).  d) 
Вариант 2
Первый уровень сложности – задачи №№ 1,2,3 – оценка “удовлетворительно”
Второй уровень сложности – любые четыре задачи – оценка “хорошо”
Третий уровень сложности – все задачи – оценка “отлично”
1. Найти области истинности следующих предикатов:
а). « x,y  - множество действительных чисел»
б). « на множестве действительных чисел R »
в). «  если  и  »
2. Дана формула  . Являются ли вхождения переменной x связанными?
3. Высказывательная форма « x – среднее арифметическое y и z » , с переменными, упорядоченными по алфавиту и принимающими значения из множества однозначных натуральных чисел, задаёт предикат F(x,y,z) . Выпишите тройки чисел, компоненты которых находятся в отношении F.
4. Задано бинарное отношение  . Определите свойства заданного бинарного отношения (рефлексивность, симметричность, антисимметричность и транзитивность).
5. Пусть бинарные отношения P и S определены на М, где М-множество всех людей следующим образом:
P= {(x,y) | x,y  M, x является отцом y}
S= {(x,y) | x,y M, x - дочь y}
Описать явно следующие отношения:
а).  b) c).  d) 
Вариант 3
Первый уровень сложности – задачи №№ 1,2,3 – оценка “удовлетворительно”
Второй уровень сложности – любые четыре задачи – оценка “хорошо”
Третий уровень сложности – все задачи – оценка “отлично”
1. Найти области истинности следующих предикатов:
а). « x - множество действительных чисел»
б). « на множестве натуральных чисел N »
в). «  на множестве натуральных чисел N »
2. Дана формула . Являются ли вхождения переменных x и y связанными?
3. Высказывательная форма « y равен квадратному корню из произведения чисел x и z » , с переменными, упорядоченными по алфавиту и принимающими значения из множества однозначных натуральных чисел, задаёт предикат F(x,y,z) . Выпишите тройки чисел, компоненты которых находятся в отношении F.
4. Задано бинарное отношение  . Определите свойства заданного бинарного отношения (рефлексивность, симметричность, антисимметричность и транзитивность).
5. Пусть бинарные отношения P и S определены на М, где М-множество всех людей следующим образом:
P= {(x,y) | x,y M, x является матерью y}
S= {(x,y) | x,y M, x - сын y}
Описать явно следующие отношения:
а). PS b) c). SP d) 
Вариант 4
Первый уровень сложности – задачи №№ 1,2,3 – оценка “удовлетворительно”
Второй уровень сложности – любые четыре задачи – оценка “хорошо”
Третий уровень сложности – все задачи – оценка “отлично”
1. Найти области истинности следующих предикатов:
а). « x,y - множество действительных чисел»
б). « на множестве действительных чисел R »
в). «  на множестве действительных чисел»
2. Дана формула . Являются ли вхождения переменной y связанными?
3. Высказывательная форма « x+y делится нацело на z » , с переменными, упорядоченными по алфавиту и принимающими значения из множества однозначных натуральных чисел, задаёт предикат F(x,y,z) . Выпишите тройки чисел, компоненты которых находятся в отношении F.
4. Задано бинарное отношение  . Определите свойства заданного бинарного отношения (рефлексивность, симметричность, антисимметричность и транзитивность).
5. Пусть бинарные отношения P и S определены на М, где М-множество всех людей следующим образом:
P= {(x,y) | x,y M, x является отцом y}
S= {(x,y) | x,y M, x - дочь y}
Описать явно следующие отношения:
а).  b)  c).PS d) 
Раздел 5. ОТОБРАЖЕНИЯ. ПОДСТАНОВКИ.
|
