- •Оглавление
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •§1.2. Отображения и соответствия
- •Операции над соответствиями
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •§1.3. Бинарные отношения и их свойства
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •§1.4. Логика высказываний
- •Логические операции над высказываниями
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •§1.5. Логика предикатов
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
Вопросы и упражнения для самостоятельной работы
Найти значение истинности следующих высказываний:
а) ; б);
в) .
Построить таблицы истинности для следующих формул:
а) .; б);
в) ; г);
д) ; е).
Найти среди указанных ниже формул тавтологии (тождественно истинные формулы):
а) ; б); в);
г) ; д).
Используя таблицы истинности, доказать эквивалентность следующих пар формул:
а) и; б)и;
в) и.
С помощью метода резолюций доказать, что из формул логически следуют формулы
а) ; б); в); г).
Верно ли, что из логически следует а); б); в)? Доказать с помощью метода резолюций или опровергнуть с помощью таблицы истинности.
Верно ли, что из логически следует а); б); в)? Доказать с помощью метода резолюций или опровергнуть с помощью таблицы истинности.
§1.5. Логика предикатов
Будем говорить, что на множестве задан-местныйпредикат от переменных , если каждому набору этих переменных из множествапоставлено в соответствие значение истинности. Высказывания можно трактовать какнульместные предикаты, то есть постоянные предикаты, не зависящие от переменных.
Переменные в предикатах называются предметными.Областью истинности предикатаназывается множество тех наборов предметных переменных, для которых этот предикат истинен.
Предикат на множественазывается:
а) тождественно истинным (ложным), если(соотв.);
б) выполнимым (опровержимым),если(соотв.).
Квантор существования () превращает одноместный предикатв высказывание, принимающее значение «истина», если в множественайдется хотя бы один элемент, для которогоистинно. Обобщение: превращает-местный предикат в-местный.
Квантор общности () превращает одноместный предикатв высказывание, принимающее значение «истина», если. Обобщение: превращает-местный предикат в-местный.
Примеры
1. Найти области истинности предикатов,,, где
, .
Решение.Область истинности предиката— это круг (с границей) радиуса 5 с центром в начале координат; предиката— область вне круга (с границей) радиуса 2 с центром в начале координат; предиката— внешность круга (без границы) радиуса 5 с центром в начале координат; предиката— внутренность круга (без границы) радиуса 2 с центром в начале координат.
Предикат — это система двух неравенств:
Областью истинности в данном случае будет кольцо (с границами) между окружностями радиусов 2 и 5 с центром в начале координат.
Значение предиката равно единице, когда выполнено одно из двух неравенств:
Областью истинности в данном случае будет вся плоскость.
Предикат ложен только в случае, когда, а, т.е. на множестве. Следовательно, область истинности в данном случае — это область вне круга (с границей) радиуса 2 с центром в начале координат.
2. Найти значение истинности высказываний,,,, где предикат, определен на множестве натуральных чисел и означает: «имеет нетривиальный общий делитель с».
Решение.Формула— это высказывание, утверждающее, что любые два натуральных числа имеют нетривиальный общий делитель. Это высказывание ложно, т.е..
Формула — это высказывание, утверждающее, что существуют два натуральных числа, имеющие нетривиальный общий делитель. Оно истинно, т.е..
Формула — это высказывание, утверждающее, что для любого числанайдется число, имеющее нетривиальный общий делитель с. Оно истинно (например, подойдет число), значит,.
Формула — это высказывание, утверждающее, что для некоторого числалюбое другое числоимеет с ним нетривиальный общий делитель. Оно ложно, т.е..
3.Определить истинность, ложность либо выполнимость следующих формул:
а) ; б);
в) ; г).
Решение.а)— выполнимая формула. Например, рассмотрим предикат, заданный на множестве натуральных чисел с нулем. Существует подстановка, при которой эта формула становится истинной:. Таким образом, существует область, в которой эта формула выполнима, а значит, она просто выполнима.
б) — выполнимая формула. Пусть, например,на множестве. Тогда приформулаистинна, а при других значенияхложна. Значит, она выполнима.
в) — тождественно истинная формула. Действительно, при подстановке любой константылюбой областипредикатлибо истинен, т.е., тогдаи(истинно), либо ложен, т.е., тогдаи(истинно).
г) — тождественно ложная формула, поскольку она ложна в любой области. Доказательство аналогично предыдущему.