Материал: 5540

высказываний непротиворечиво, если существует по меньшей мере одно такое распределение истинностных значений простым компонентам, что все А одновременно получают значение 1. Противоречивость множества высказываний есть отрицание его непротиворечивости. Так, {А1 , А2 ,..., Аm } есть противоречивое множество, если при всяком распределении истинностных значений простым компонентам по меньшей мере одно из А получает значение 0.

Противоречие есть формула, которая всегда принимает

высказываний:

АВ, В С, С D, А D, D .

Решение. Примем их как систему посылок и исследуем, какие выводы можно из них сделать.

Мы заключаем, что множество противоречиво.

Задача 3.18. Исследуйте противоречивость систем посылок:

а) А (В С), D Е G, G (H I ), C E H.

б) А B С D, D E G, A G .

76

Противоречия играют важную роль в методе косвенного доказательства (доказательства от противного). Основой такого

8) А В, С D, А С В D.

77

Глава 4. ЛОГИКА ПРЕДИКАТОВ

4.1 Основные понятия

Логика предикатов представляет собой развитие логики высказываний. С помощью формул логики высказываний можно описать и исследовать структуру сложных высказываний, установить их истинность или ложность в зависимости от истинности или ложности входящих в неё простых высказываний. Для описания внутренней логической структуры простых высказываний используется понятие предиката (лат. praedicatum – логическое сказуемое).

Пусть имеется ряд простых высказываний: Р1 : «Иван читает Достоевского», Р2 : «Пётр читает Достоевского»,

. . .

Рn : «Степан читает Достоевского».

Вместо высказываний Р1, Р2, ..., Рn мы могли бы ввести одноместный предикат Р(х), для которого переменная х принимала бы значения из предметной области М = {Иван, Пётр, ..., Степан}, а сама предикатная функция переводилась бы словами Р(х): «х читает Достоевского».

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

Сразу же напишем обобщение, а именно распространение сказанного на высказывательные функции со многими переменными. Вот несколько примеров:

R(x, y) : "x2 y2 0";

Q(x, y, z) : "x2 y2 z2".

n-местный предикат – это функция Р(х1, х2, ..., хn) от n переменных, принимающих значения из некоторых заданных предметных областей, так

78

что x1 M1 , x2 M 2 , ..., xn M n , а функция Р принимает два логических значения – «истинно» или «ложно»:

переменные, которые обозначают строчными буквами латинского алфавита х, у, z. Эта функция приобретет значение 1 или 0 только при подстановке в высказывательную функцию вместо предметных переменных их конкретных значений. Конкретные значения аргументов высказывательной функции называют предметными постоянными, которые обозначают строчными буквами латинского алфавита а, в, с, .

Если высказывательная функция содержит один аргумент, то задан одноместный предикат, если она содержит n аргументов, то – n-местный предикат. Одноместный предикат, как правило, описывает наличие какого-либо признака у предмета, а n-местный предикат наличие отношений между n предметами. Следует еще раз обратить внимание, что когда все предметные переменные замещены предметными постоянными, тогда предикат превращается в высказывание.

Для удобства в число значений n включаем и 0, понимая под 0- местным предикатом высказывание, т.е. предикат, в котором нет переменных для замены.

Пример 4.1. В следующих высказываниях выделите входящие в них предикаты и запишите эти высказывания с помощью символики исчисления предикатов.

1. Снег белый.

Решение. Φ(снег), где Φ(х) обозначает предикат: «х – белый». 2. Два меньше трёх.

Решение. Φ(2, 3), где Φ(х, у): «х < y».

Предикат Р(х1, х2, ..., хn), заданный на множествах М1, М2, ..., Мn, называется:

а) тождественно истинным, если при любой подстановке вместо переменных х1, х2, ..., хn любых конкретных предметов а1, а2, ... , аn из

79

множеств М1, М2, ..., Мn соответственно он превращается в истинное высказывание Р(а1, а2, ... , аn);

б) тождественно ложным, если при любой подстановке конкретных предметов из множеств М1, М2, ... , Мn соответственно он превращается в ложное высказывание;

в) выполнимым (опровержимым), если существует по меньшей мере один набор конкретных предметов а1, а2, ... , аn из множеств М1, М2, ... , Мn соответственно при подстановке которых вместо соответствующих предметных переменных в предикат Р(х1, х2, ... , хn) последний превратится в истинное (ложное) высказывание Р(а1, а2, ... , аn).

Отметим некоторые достаточно очевидные закономерности взаимосвязей между предикатами различных типов:

1)каждый тождественно истинный предикат является выполнимым, но обратное неверно;

2)каждый тождественно ложный предикат является опровержимым, но обратное неверно;

3)каждый нетождественно истинный предикат будет опровержимым, но, вообще говоря, не будет тождественно ложным;

4)каждый нетождественно ложный предикат будет выполнимым, но, вообще говоря, не будет тождественно истинным.

Два n-местных предиката Р(х1, х2, ... , хn) и Q(х1, х2, ... , хn), заданных над одними и теми же множествами М1, М2, ... , Мn, называются

высказывание Р(а1, а2, ... , аn) в том и только в том случае, когда этот набор предметов превращает второй предикат в истинное высказывание

Q(а1, а2, ... , аn).

Утверждение о равносильности (эквивалентности) двух предикатов Р и Q символически будем записывать так: Р Q.

Задача 4.1. Заданы предикаты:

P(x, y, z) : "x2 y2 z2";

Q(x, y) : " y (x 4) /( x 4)";

80