Логика высказываний – очень узкая логическая система. Есть такие типы логических рассуждений, которые не могут быть осуществлены в рамках логики высказываний, например:

1. Всякий друг лица А есть друг лица В. С не есть друг В, следовательно, С не есть друг А.
2. Простое число два – четное. Следовательно, существуют простые четные числа.

Корректность этих умозаключений основана на внутренней структуре самих предложений и на смысле слов «всякий» и «существует».

Рассмотрим предложения, зависящие от параметров, например: «х – четное число», «х меньше y », «x +y =z », «u и v – братья». Если в первых трех предложениях заменить x ,y и z некоторыми числами, а в последнем подставить имена членов некоторой семьи, то полученные высказывания могут быть истинными или ложными. Например, для х =5, y =2, z =7, u – Петр, v – Иван получим: «5 – четное число», «5 меньше 2», «5+2=7», «Петр и Иван – братья».

Предложения такого типа называются предикатами. Точнее, предикатом P(x 1 ,…,x n) называется функция, переменные которой принимают значения из некоторого множества М, а сама она принимает два значения: истинное (И) и ложное (Л), т.е. P(x 1 ,…,x n):М {И,Л}.

Предикат от n аргументов называют n-местным предикатом и обозначают полностью P (n) (x 1 ,…,x n) , если нужно подчеркнуть число аргументов. Высказывания считают нуль-местными предикатами.

Над предикатами можно производить обычные логические операции. В результате получаются новые предикаты

Например:

1. Пусть P (1) (x) означает предикат «х делится на 2», а Q (1) (х) – предикат «х делится на 3». Тогда выражение P (1) (x) &Q (1) (х) означает предикат «х делится на 2 и х делится на 3», т.е. определяет предикат делимости на 6.

2. Пусть S (2) (х,у) означает предикат «х=у ». Он принимает значение И тогда и только тогда, когда х=у . В этом случае выражение ┐S (2) (х,х) ÞS (2) (х,у) определяет предикат, принимающий значение И при любых х и у.

Кроме операций логики высказываний будем применять еще операции связывания квантором.

Квантор всеобщности. Пусть Р(х) – предикат, принимающий значение И или Л для каждого х ÎМ. Тогда под выражением "хР(х) будем подразумевать высказывание истинное, когда Р(х) истинно для каждого элемента х из М, и ложное – в противном случае. Символ "х называется квантором всеобщности и запись "хР(х) читается так: «для всех х Р(х) ». Это высказывание уже не зависит от х.

Квантор существования. Пусть Р(х) – предикат. Под выражением $х Р(х) будем понимать высказывание истинное, если существует элемент множества М, для которого Р(х) истинно, и ложное – в противном случае. Символ $ х называется квантором существования и запись $ хР(х) читается так: «существует х , такое, что (или для которого) Р(х) » .

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

1. $ х (P (1) (x) &Q (1) (х)) – истинное высказывание;
2. " х (P (1) (x) &Q (1) (х)) – ложное высказывание;
3. " х,у (┐S (2) (х,х) ÞS (2) (х,у)) – истинное высказывание.

Введем теперь строгие определения для исчисления предикатов.

(Чистое) исчисление предикатов (первого порядка) - это формальная теория К, в которой оп­ределены следующие компоненты.

1. Алфавит:

связки основные ┐,

дополнительные &,

служебные символы (,) Î (, ’ , ’ ,)

кванторы всеобщности

существования

предметные константы

переменные

предметные предикаты P, Q, . . .

функторы f, q,. . .

С каждым предикатом и функтором связано некоторое натуральное число, которое называется арностью, или иногда местностью.

2. Формулы имеют следующий синтаксис:

Формула = (атом

| ┐ (формула | ( формула

(фор­мула ) | (переменная формула

| перемен­ная формула

Атом = предикат ( список термов )

Список термов = терм | терм ,

Список термов терм = константа |

Переменная | функтор ( спи­сок термов )

При этом должны быть выполнены следующие контекстные условия: в терме f (t 1 ,. . .,t n) функтор f должен быть n - местным. В атоме (или атомарной формуле) P(t 1 ,. . .,t n) предикат Р должен быть n - местным.

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

Например, рассмотрим формулу x (Р(х) y Q(x,y)) и ее подформулы. В подформулу y Q(x,y) пере­менная х входит свободно, а оба вхождения переменной у связаны (квантором существования). Таким образом, эта подформула не замкнута. С другой стороны, то же самое вхождение пере­менной х в подформулу Q(x,y) является связанным вхождением в формуле x (Р(х) y Q(x,y)) . В этой формуле все вхождения всех переменных связаны, а потому формула замкнута.

Язык теории L не содержит кванторов, поэтому понятия свободного и связанного вхождения пе­ременных не применимы непосредственно. Обычно для удобства полагают, что все формулы тео­рии L замкнуты.

Формулы вида А и ┐А, где А - атом, называются литеральными формулами (или литералами). В формулах x А и x А подформула А называется областью действия квантора по х.

Обычно связки и кванторы упорядочивают по приоритету следующим образом: ┐, ,$, &, , . Лишние скобки при этом опускают. Терм t называется свободным для переменной х в формуле А, если никакое свободное вхождение переменной х в формулу А не лежит в области действия никакого квантора по переменной у, входящей в терм t. В частности, терм t свободен для любой переменной в формуле А , если ника­кая переменная терма не является связанной переменной формулы А.

Например:

а) терм у свободен для переменной х в формуле Р(x) , но тот же терм у не свободен для пере­менной х в формуле y P{x).

б) терм f(x, z) свободен для переменной х в формуле y P(x,y) Q(x), но тот же терм f(x, z) не свободен для переменной х в формуле

z y P(x,y) Q(x).

Переход от предиката Р(х) к " х Р(х) или $ х Р(х) называется связыванием переменной х , или навешиванием квантора на переменную х , или квантификацией переменной х.

Выражение " х Р(х) и $ х Р(х) не зависят от х и при фиксированных Р и предметного множества М имеет вполне определенные значения, представляя вполне конкретные высказывания относительно всех х в предметной области М.

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

Навешивая кванторы на многоместные предикаты и вообще на любые логические выражения, мы тем самым и определяем область действия квантора $ х или " х и все вхождения х в эти выражения являются связными.

Рассмотрим решение некоторых примеров.

Пример 4.4. Пусть N (х) – предикат «х – натуральное число». Рассмотреть варианты навешивания кванторов, интерпретировать и определить их истинность.

Решение. " х N(х) –«все числа натуральные». Это высказывание истинно на любом множестве натуральных чисел и ложно, если М содержит хоть одно ненатуральное число (например, целое отрицательное).

Пример 4.5. Пусть предикат Р(х,у) описывает отношение «х любит у » на множестве людей. Проанализировать варианты навешивания кванторов и дать интерпретацию.

Решение . Используя взаимно однозначное соответствие между отношениями предикатами, можно проиллюстрировать решение схемами (рис. 4.1.).

Рис. 4.1. Иллюстрация влияния кванторов

Интерпретация:

" х $ y Р(х,у) – «для любого х существует у , которого он любит».

$ у " х Р(х,у) – «существует такой у , которого любят все х ».

" х "уР(х,у ) - «все х любят всех у ».

$ х $ у Р(х,у) – « найдется х , который любит кого-то из у » или «найдется человек, который кого-то любит».

$ х " у Р(х,у) – «существует х , который любит всех у ».

" у $ х Р(х,у) – «для любого из у найдется х , который его любит».

Аксиомы (логические): любая система аксиом исчисления высказываний, плюс

P 1: x A(x) A(t),

P 2: A(t) x A(x),

где терм t свободен для переменной х в формуле А.

Правила вывода:

где формула А содержит свободные вхождения переменной х, а формула В их не содержит.

Исчисление предикатов, которое не содержит предметных констант, функторов, предикатов и собственных аксиом, называется чистым. Исчисление предикатов, которое содержит предметные константы и/или функторы и/или предикаты и связывающие их собственные аксиомы, называется прикладным.

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

Соответствие между предикатами, отношениями и функциями

n – местный предикат можно рассматривать как функцию Р (х 1 ,…х n) от n переменных х i Î М i , где М i - предметные области, а РÎВ={0,1}={И,Л}. Таким образом, предикат Р (х 1 ,…х n) является функцией типа Р: М 1 ´М 2 ´… ´М n ®В , или, если предметная область едина для всех переменных, то имеем Р: М n ®В .

Из рассмотренного очевидно, что для любых М и n существует однозначное соответствие между n-местными отношениями R ÍМ n и предикатами Р (х 1 ,…х n) , М n ®В :

Каждому n – местному отношению R соответствует предикат Р (х 1 ,…х n) такой, что Р (а 1 ,…а n)=1, если и только если (а 1 ,…а n)ÎR;

Всякий предикат Р (х 1 ,…х n) определяет отношение R такое, что (а 1 ,…а n)ÎR , если и только если Р (а 1 ,…а n)=1.

При этом R задает область истинности предиката P.

Рассмотрим теперь функцию f (х 1 ,…, х n), f : М n ®M . Тогда можно видеть, что всякой функции f: М n ®M соответствует предикат Р (х 1 ,…х n +1), Р: М n +1 ®В , такой что Р(а 1 ,…а n +1)=1 , если и только если f (а 1 ,…а n)=а n +1 .

Понятие предиката шире понятия функции (см. рис. 4.1.), поэтому обратное соответствие (от (n+1 )-местного предиката к n–местной функции) возможно не всегда, а только для таких предикатов, для которых выполняется условие, связанное с однозначностью функции:

Р(а 1 ,…а n +1)=0 ® ("а¢ n +1 ÎМ|а¢ n +1 ¹а n +1 Р(а 1 ,…а¢ n +1)=0. (4.3.)

Аналогичное соответствие имеется между подмножеством отношений {R¢}Ì{R} и множеством функций {f} . Для этого класса отношений выполняется условие

(а 1 ,…а n +1)ÎR¢ ® ("а¢ n +1 ÎМ|а¢ n +1 ¹а n +1 (а 1 ,…а¢ n +1)ÎR¢). (4.4.)

Пример 4.6. Каким отношениям и функциям соответствуют предикаты, определенные на множестве натуральных чисел?

1. Предикат суммы S: N 3 ®В:

S(х 1 ,х 2 ,х 3)=1 тогда и только тогда, когда х 1 +х 2 =х 3 .

2. Предикат порядка Q:N 2 ®В:

Q (х 1 ,х 2)=1 тогда и только тогда, когда х 1 £х 2 .

Цель семинара:

Рассмотреть практическое применение логики предикатов.

План занятия:

Рассматривается тема логика предикатов на которую отводится 2 часа семинарских занятий.

Задача 1. Каким отношениям и функциям соответствуют следующие предикаты, определённые на множестве натуральных чисел:

1. Предикат тождества Е:N 2 →B:

E(a 1 ,a 2)=1 тогда и только тогда, когда a 1 =a 2 .

2. Предикат порядка Q:N 2 →B:

Q(a 1 ,a 2)=1 тогда и только тогда, когда a 1 ≤ a 2.

3. Предикат делимости D:N 2 →B:

D(a 1 ,a 2)=1 тогда и только тогда, когда a 1 делится на а 2 .

4. Предикат суммы S:N 3 →B:

S(a 1 ,a 2 ,a 3)=1 тогда и только тогда, когда a 1 +a 2 =a 3.

5. Предикат произведения П:N 3 →B:

П(a 1 ,a 2 ,a 3)=1 тогда и только тогда, когда a 1 *a 2 =a 3 .

Решение .

1. Двухместному предикату тождества Е-“x 1 ”=”x 2 ” взаимно однозначно соответствуют:

а) двухместное отношение R 1 – «быть равным», R 1 N 2:(a 1 ,a 2) R 1 тогда и только тогда, когда E(a 1 ,a 2)=1;

б) одноместная функция (операция) тождества f 1 (x 1)=x 2 , а именно: f 1 (x)=x, f:N→N.

2. Двухместному предикату порядка Q-“x 1 ≤ x 2 ” взаимно однозначно соответствует двухместное отношение R 2 - «быть не больше», R 2 N 2:(a 1 ,a 2) R 2 тогда и только тогда, когда Q(a 1 ,a 2)=1.

Однако функции f(x 1)=x 2 для предиката порядка Q(x 1 ,x 2) не существует, так как не выполнено условие Р"(а 1 ,а 2 ,…а n ,а n +1)=0 при одинаковых значениях переменной x 1 существует не единственно значение переменной x 2 , при котором предикат Q истинен. Например, Q(2,4)=1 и Q(2,6)=1, однако 4≠6.

3. Двухместному предикату делимости D-“x 1 делится на х 2 ” взаимно однозначно соответствует двухместное отношение R 3 - “делится”, R 3 N 2:(a 1 ,a 2) R 3 тогда и только тогда, когда D(a 1 ,a 2)=1.

Однако функции f(x 1)=x 2 для предиката делимости D(x 1 ,x 2) не существует, так как не выполнено условие Р"(а 1 ,а 2 ,…а n ,а n +1)=0, например D(6,2)=1 и D(6,3)=1, однако 2≠3.

4. Трехместному предикату суммы S- “х 1 +х 2 =х 3 ” взаимно однозначно соответствуют:

а) трёхместное отношение R 4 N 3: (a 1 ,a 2, a 3) R 4 тогда и только тогда, когда S(a 1 ,a 2 ,a 3)=1;

б) двухместная функция (операция арифметики)- сложение f 2 (x 1 ,x 2), а именно х 1 +х 2 =х 3 .

5. Трёхместному предикату произведения П- “x 1 *x 2 =x 3 ” взаимно однозначно соответствуют:

а) трёхместное отношение R 3 N 3: (a 1 ,a 2, a 3) R 5 тогда и только тогда, когда П (х 1 ,х 2 ,х 3)=1;

б) двухместная функция (операция арифметики)- умножение f 3 (x 1 ,x 2)=x 3 , а именно х 1 *х 2 =х 3.

Взаимная однозначность соответствия между S и f 2 (П и f 3), обусловлена выполнением для предиката S(П) условия Р"(а 1 ,а 2 ,…а n ,а n +1)=0 для каждой системы элементов a 1 ,a 2 N существует единственный элемент а 3 N такой, что S(a 1 ,a 2 ,a 3)=1 (соответственно для П(a 1 ,a 2 ,a 3)=1).

Задача 2. Проиллюстрировать на примере предиката делимости, определённого в задаче 1, понятия переменного высказывания, истинного высказывания, ложного высказывания.

Решение .

Предикат делимости D(x 1 ,x 2)- это переменное (двухместное) высказывание, предметной областью которого могут служить любые множества действительных чисел, например множество N.

D(6,2)- высказывание, значение которого есть истина, т.е. истинное высказывание.

D(5,2)- ложное высказывание.

D(3,х), D(х,2)- переменные (одноместные) высказывания, истинность которых зависит от того, каким числом будет замещён символ x, но D(а,1)- истинное высказывание, так как для любого элемента а N имеет место: D(а,1)=1 (любое натуральное число делится на единицу).

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

Решение .

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

«если а делится на b и b делится на с, то а делится на с», состоит из трёх простых высказываний D(a,b), D(b,c) и D(a,c). Следовательно, транзитивное свойство делимости можно записать в виде составного высказывания (логической формулы):

«если D(a,b) и D(b,c), то D(a,с) или (D(a,b) & D(b,c)) → D(a,c).

Задача 4. Дать словесные формулировки следующих составных высказываний (предложений):

1. S(a,b,c) & D(a,d) & D(b,d)→D(c,d), где S и D- предикаты суммы и делимости соответственно (см.пример 1);

2. D(a,b) & S(a,b,c);

3. S(a,b,c) ~ S(b,a,c);

4. P 1 ~ P 2 , где P 1 – предикат «число 3n является чётным»; Р 2 - предикат «число n является чётным».

Решение .

1. «Если каждое слагаемое a,b суммы целых чисел делится на некоторое число d, то и сумма с делится на это число»:

S(a,b,c) & D(a,d) & D(b,d)→D(c,d).

2. «Число а не делится на число b, и неверно, что их сумма равна с»: D(a,b) & S(a,b,c).

3. «От перестановки мест слагаемых a и b сумма с не меняется»- свойство коммутативности арифметической операции сложения: S(a,b,c) ~ S(b,a,c).

4. «Число 3n является чётным тогда и только тогда, когда n является чётным»: P 1 ~ P 2.

Эквивалентность может быть выражена и другими словесными формулировками, в том числе:

· «из того, что Р 1 , следует то, что Р 2 , и обратно»;

· «из того, что Р 2 , следует то, что Р 1 , и обратно»;

· «условия Р 1 необходимо и достаточно для того, чтобы Р 2 »;

· «Р 2 необходимо и достаточно, чтобы Р 1 »;

· «Р 1 , если и только если Р 2 »;

· «Р 2 , если и только если Р 1 »;

· «условия Р 1 и Р 2 эквивалентны»;

· «Р 2 тогда и только тогда, когда Р 1 » и др.

Задача 5. Пусть х определён на множестве людей М, а Р(х)- предикат «х-смертен». Дать словесную формулировку предикатной формулы

Решение .

Выражение означает «все люди смертны». Оно не зависит от переменной х, а характеризует всех людей в целом, т.е. выражает суждение относительно всех х множества М.

Задача 6. Пусть Р(х)- предикат «х-чётное число», определённый на множестве М. Дать словесную формулировку высказывания определить его истинность.

Решение .

Исходный предикат Р(х)- «х- чётное число» является переменным высказыванием: при подстановке конкретного числа вместо переменной х он превращается в простое высказывание, являющееся истинным или ложным, например при подстановке числа 5 превращается в высказывание «5-чётное число», являющееся ложным. Высказывание означает «в М существует четное число». Поскольку множество М, на котором задан предикат Р(х), не определено в условии (в таком случае говорят, что задача сформулирована не вполне корректно), доопределим М.

Пусть предикат Р(х) определён на множестве натуральных чисел N, т.е. , тогда высказывание - истинно. В общем случае высказывание истинно на любом множестве М, содержащем хотя бы одно чётное число, и ложно на любом множестве нечетных чисел.

Задача 7. Пусть N(х)- предикат «х-натуральное число». Рассмотреть варианты навешивания кванторов. Проинтерпретировать полученные высказывания и определить их истинность.

Решение .

Высказывание «все числа- натуральные» истинно на любом множестве натуральных чисел и ложно, если М содержит хотя бы одно ненатуральное число, например целое отрицательное;

Высказывание «существует натурально х» истинно на любом множестве М, содержащем хотя бы одно натуральное число, и ложно- в противном случае.

Задача 8. Записать предикатной формулой предложение «Любой человек имеет отца».

Решение .

Для построения предикатной формулы используем два предиката «х- человек» и «у- отец х» и для удобства восприятия обозначим их соответственно: ЧЕЛОВЕК (х) и ОТЕЦ (у). Тогда предложение «Любой человек имеет отца» в предикатной форме имеет вид:

Заметим, что если предикат ОТЕЦ(у,х) определён на множестве людей, то выражение «любой человек имеет отца» можно записать проще:

Задача 9. Пусть предикат Р(х,у) описывает отношение «х любит у» на множестве людей. Рассмотреть все варианты навешивания кванторов на обе переменные. Дать словесную интерпретацию полученных высказываний.

Решение .

Обозначим предикат «х любит у» через ЛЮБИТ (х,у). Предложения, соответствующие различным вариантам навешивания

ЛЮБИТ(х,у)- «для любого человека х существует человек у, которого он любит» или «всякий человек кого-нибудь любит» (рис. а);

ЛЮБИТ (х,у)- «существует такой человек у, что его любят все х» (рис. б)ж

ЛЮБИТ (х,у)- «все люди любят всех людей» (рис. в);

ЛЮБИТ (х,у)- «существует человек, который кого- то любит» (рис. г);

ЛЮБИТ (х,у)- «существует человек, который любит всех людей» (рис. д);

ЛЮБИТ (х,у)- «для всякого человека существует человек, который его любит» (рис. е).

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

Задача 10. Пусть Q(x,y)- предикат порядка «х≤у». Рассмотреть различные варианты квантификации его переменных. Определить истинность получаемых выражений для разных случаев интерпретации области определения М предиката, х, у М.

Решение .

Одноместный предикат от у: « для любого х имеет место х≤у». Если М- бесконечное множество неотрицательных целых чисел, то этот предикат ложен; на любом конечном множестве натуральных чисел предикат истинен в единственной точке, представляющей наибольшее число в М. При подстановке любого другого у из М этот предикат обращается в ложное высказывание;

Одноместный предикат от х: «для любого у имеет место х≤у». Если М-множество неотрицательных целых чисел, то этот предикат истинен в единственной точке х=0 и ложен при подстановке вместо х любого числа из М;

Одноместный предикат от у: «существует число в М, которое не больше у». Если М- любое непустое множество чисел, то данный предикат превращается в истинное высказывание при подстановке какого- либо у из М.

Одноместный предикат от х: « существует число в М, которое не меньше х». На любом непустом множестве М чисел данный предикат превращается в истинное высказывание при подстановке какого- либо х из М.

Высказывание « для любых х и у выполняется х≤у» ложно на любом множестве, состоящем более, чем из одного элемента, и истинно на множестве с одним элементом;

Высказывание «существуют такие х и у, что х≤у» истинно на любом непустом множестве;

Высказывание «для любого числа х существует число у, не меньше чем х» истинно на любом непустом множестве;

Высказывание «существует у такой, что для любого х х≤у»утверждает, что в М имеется единственный максимальный элемент;

Высказывание «существует х такой, что он не больше любого у» утверждает, что в М имеется единственный минимальный элемент.

Высказывание «для любого числа у существует число х, не больше, чем у» истинно на любом непустом множестве

Задача 11. Рассмотреть все возможные варианты навешивания кванторов на предикат D(х,у)- «х делится на у», определенный на множестве натуральных чисел N. Дать словесные формулировки полученных высказываний и определить их исьтинность.

Решение .

Операции навешивания кванторов приводят к следующим формулам:

Одноместный предикат «всякое натуральное число из N делится на натуральное число у из N»; истинный только для одного значения свободной переменной у=1;

Переменное высказывание «существует натуральное число, которое делится на у», истинное для любого значения свободной переменной у, взятой из множества N;

Переменное высказывание «натуральное число х делится на всякое натуральное число у», ложное для любого значения свободной переменной х, взятой из N;

Переменное высказывание «существует натуральное число, которое делит натуральное число х», истинное для любого значения свободной переменной х;

Высказывания «для любых двух натуральных чисел имеет место делимость одного на другое» ложные;

Высказывания «существуют такие два натуральных числа, что первое делится на второе», истинны;

Высказывание «существует натуральное число, которое делится на любое натуральное», ложное;

Высказывание « для всякого натурального числа найдется такое натуральное, которое делится на первое», истинное;

Окончательно получим префиксную нормальную форму для исходной предикатной формулы.

Рассмотрим предложение

Это предложение не является высказыванием, так как о нем нельзя сказать, истинно оно или ложно. Оно называется предикатом или условием (на х и у). Приведем другие примеры предложений с переменными:

Есть простое число;

Есть четное число;

Меньше у,

Есть общий делитель у, z.

Будем считать, что допустимыми значениями переменных у и z являются натуральные числа. Если в предложениях заменить переменные их допустимыми значениями, то получатся высказывания, которые могут быть как истинными, так и ложными. Например,

2 есть простое число;

3 есть четное число;

5 меньше 7;

3 есть общий делитель 6 и 12.

ОПРЕДЕЛЕНИЕ. Предложения с переменными, дающие высказывания в результате замены свободных переменных их допустимыми значениями, называются предикатами.

Предложения могут служить примерами предикатов.

По числу входящих свободных переменных различают предикаты одноместные, двухместные, трехместные и т. д. Предикаты (2) и (3) - одноместные, предикаты (1) и (4) - двухместные, предикат (5) - трехместный. Высказывания будем считать нульместными предикатами.

Заменяя в одноместном предикате (2) переменную натуральными числами, будем получать высказывания:

0 есть простое число;

1 есть простое число;

2 есть простое число;

3 есть простое число и т. д.

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

Одноместный предикат можно рассматривать как условие на объекты данного вида; двухместный - как условие на пары объектов данного вида и т. д.

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

Обозначать предикаты будем большими буквами латинского алфавита (возможно, с нижними индексами) с указанием в скобках всех свободных переменных, входящих в этот предикат. Например, - обозначение двухместного предиката, - трехместного и - обозначение -местного предиката.

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

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

При задании частичного порядка, если пара элементов (a ,b ) принадлежит U , то говорят, что a предшествует b . Если никакой из этих двух элементов другому не предшествует, но говорят, что они не сравнимы.

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

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

Итальянский экономист Вильфредо Парето (1848-1923) предложил использовать в таких задачах конструкцию, которая в его честь называется границей Парето (Pareto frontier). Мы ее сейчас опишем.

Подмножество PF множества A называется его границей Парето для частичного порядка U , если любые два элемента PF не сравнимы, а любому другому элементу из A предшествует какой-либо элемент из PF .

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

В алгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности.

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

Например, в рассуждении “Всякий ромб – параллелограм; АВСD – ромб; следовательно, АВСD - параллелограм ” посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части.

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

Субъект – это то, о чем что-то утверждается в высказывании;

предикат – это то, что утверждается о субъекте.

Например, в высказывании “7 - простое число”, “7” – субъект, “простое число” – предикат. Это высказывание утверждает, что “7” обладает свойством “быть простым числом”.

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму “х – простое число”. При одних значения х (например, х=13, х=17) эта форма дает истинные высказывания, а при других значениях х (например, х=10, х=18) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1;0}. Здесь предикат становится функцией субъекта и выражает свойство субъекта.

Областью значений предиката является двухэлементное множество B={true, false}. При этом сами переменные x 1 ,...,x n называются предметными переменными, т.е. их значения не являются логическими (не принадлежат множеству B).

Понятие ``предикат"" обобщает понятие ``высказывание"". Неформально говоря, предикат – это высказывание, в которое можно подставлять аргументы. Если аргумент один – то предикат выражает свойство аргумента, если больше – то отношение между аргументами.

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

Определение 1.Логика предикатов, раздел математической логики, изучающий логические законы, общие для любой области объектов исследования (содержащей хоть один объект) с заданными на этих объектах предикатами (т. е. свойствами и отношениями).

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

В классическом исчислении предикатов употребляются следующие знаки: 1) т. н. предметные переменные - буквы х, у, z ,..., которые содержательно рассматриваются как неопределённые имена объектов исследования теории; 2) предикатные переменные - знаковые комплексы вида P m , Q n , R l ,... (m, n, l - натуральные числа), причём, например, Q n означает произвольное n-местное отношение между объектами; 3) знаки для логических связок: конъюнкции &, дизъюнкции , импликации É, отрицания ù, означающие соответственно «... и...», «... или...», «если..., то...», «неверно, что...»; 4) знаки для кванторов " (квантор всеобщности), $ (квантор существования), означающие соответственно «для всех...» и «существует... такое, что...»; 5) запятая, скобки (для уточнения строения формул).

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

В обычном языке носителями таких характеристик служат слова типа «все», «каждый», «некоторый», «существует», «имеется», «любой», «всякий», «единственный», «несколько», «бесконечно много», «конечное число», а также все количественные числительные. В формализованных языках, составной частью которых является исчисление предикатов, для выражения всех подобных характеристик оказывается достаточным кванторов двух видов: Квантор всеобщности (оборот «для всех х», обозначается через " x, и Квантор существования («для некоторых х», обозначения: $ x.

С помощью кванторов можно записать четыре основных формы суждений традиционной логики: «все А суть В » записывается в виде " x [A (x )É ÉB (x )], «ни одно A не есть B » - в виде " x [A (x )É B (x )], «некоторые А суть B » - в виде $ x [A (x )&B (x )], «некоторые А не суть В » - в виде $ x [A (x )& B (x )] (здесь А (х ) означает, что х обладает свойством A) .

Часть формулы, на которую распространяется действие каких-либо Квантора, называется областью действия этого Квантора (её можно указать с помощью скобок). Применение Квантора уменьшает число свободных переменных в логическом выражении и превращает (если Квантор не «фиктивный», т. е. относится к переменной, действительно входящей в формулу) трёхместный предикат в двухместный, двухместный - в одноместный, одноместный - в высказывание.

Определение 3. Одноместным предикатом Р(x) называется произвольная функция переменной x, определенная на множестве M и принимающая значение из множества {1; 0}.

Определение 4. Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество или иначе: или так: Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности I P для него есть множество всех простых чисел.

Предикат Q(x) – “sin(x)=0” определен на множестве R, а его множеством истинности является

Предикат F(x) – “диагонали параллелограма x взаимно перпендикулярны” определен на множестве всех параллелограмов, а его множеством истинности является множество всех ромбов.

Из приведенных примеров видим, что одноместные предикаты выражают свойства предметов (субъектов).

Определение 5. Предикат Р(х), определенный на множестве М, называется тождественно истинным , если его множество истинности совпадает с областью определения, т. е. I p =M.

Определение 6. Предикат Р(х), определенный на множестве М, называется тождественно ложным , если его множество истинности является пустым множеством, т. е. I p =0.

Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношениямежду предметами.

Примером бинарного отношения, т. е. отношения между двумя предметами, является отношение “меньше ”. Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой “х

Определение 7. Двухместным предикатом Р(x,y) называется функция двух переменных x и y, определенная на множестве М=М 1 хМ 2 и принимающая значения из множества {1;0}.

В числе примеров двухместных предикатов можно назвать такие предикаты: Q(x, y) – “x=y” - предикат равенства, определенный на множестве RхR=R 2 ; F(x,y) – “х параллелен y”, “прямая х параллельна прямой y”, определенный на множестве прямых, лежащих на данной плоскости.

Совершенно аналогично вводится понятие трехместного предиката. Приведем пример трехместного предиката (функции трех переменных): S(x,y,z) – “x+y=z”. Подстановка в него х=3 превращает его в двухместный предикат: S(y,z) – “3+y=z”, а подстановка х=3, z=2 – в одноместный предикат S(y) – “3+y=2”.Подстановка же S(2,3,5) превращает его в истинное высказывание, а S(1,7,4)– в ложное.

Аналогично определяется и n-местный предикат (функция n переменных). Пример п- местного предиката:

R(x 1 , x 2 ,…,x n): a 1 x 1 +…+a n x n =0,

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

При n=0 будем иметь нульместный предикат – это логическая (пропозициональная) переменная, принимающая значения из множества {1;0}.

Исторически понятие о предикате явилось следствием логического анализа высказываний естественного языка, т. е. выяснения их логической структуры, выяснения того, какой логикой может быть выражен (формализован) смысл этих высказываний. Идея выделения логической структуры речи, в отличие от грамматической, для нужд логической дедукции принадлежит Аристотелю. В аристотелевской и в последующей «традиционной» логике П. понимался в узком смысле как один из двух терминов суждения, а именно тот, в котором нечто говорится о предмете речи - субъекте. Форма сказывания - предикативная связь - сводилась при этом к атрибутивной связи, т. е. выражала «присущность» предмету некоторого признака. Аристотель выделял 4 типа признаков, способных играть роль предиката.: родовые, видовые, собственные и случайные. Это т. н. предикабилии - типы сказуемых.

Основой для «функциональной» точки зрения на предикат служат в естественных и в искусственных (точных) языках выражения вида повествовательных предложений, содержащие неопределённые термины - неопределённые имена предметов: переменные (параметры) в записи утверждений в математическом языке, например х + 2 = 4; слова «нечто», «некто», «кто-либо» и пр., играющие в естественном языке роль переменных в выражениях типа: «Некто человек», «Кто-то любит кого-то», «Если кто-либо человек, то он смертен» и т.п. Записав эти выражения некоторым единым способом, например заменяя неопределённые термины пробелами, аналогично тому, как это делается в опросных бланках, «-+ 2 = 4», «-человек», «- любит -», «Если - человек, то - смертен», или же принимая запись с помощью переменных в качестве основной, «x + 2 = 4», «x человек», «х любит у », «Если х человек, то х смертен», легко заметить нечто общее между ними. Во-первых, наличие неопределённых терминов делает эти и подобные им выражения, вообще говоря, неопределёнными как в смысле того, что в них утверждается, так и в смысле их истинностного значения; во-вторых, всякое подходящее указание на область значений неопределённых терминов и одновременная квантификация или замена неопределённых терминов их значениями преобразует соответствующие выражения в осмысленные высказывания. В современной логике выражения, имеющие вид повествовательных предложений и содержащие неопределённые термины, получили общее название пропозициональных функций, или, сохраняя традиционный термин, предикатов. Как и числовые функции, предикаты. являются соответствиями. Неопределённые термины играют в них обычную роль аргументов функции, но, в отличие от числовых функций, значениями предикатов. служат высказывания. В общем случае, отвлекаясь от какого-либо определённого языка и сохраняя только функциональную форму записи, предикат от n переменных (от n неопределенных терминов) выражают формулой P (x 1 ,..., x n ), где n ³ 0. При n = 0 предикат совпадает с высказыванием, при n = 1 предикат будет свойством в узком смысле (1-местным предикатом), при n = 2 - свойством «пары» (2-местным предикатом, или бинарным отношением), при n = 3 - свойством «тройки» (3-местным предикатом, или тернарным отношением) и т.д.

Примеры предикатов:

1. Возьмём высказывания: `` Сократ - человек "", `` Платон - человек "". Оба эти высказывания выражают свойство ``быть человеком"". Таким образом, мы можем рассматривать предикат `` быть человеком "" и говорить, что он выполняется для С0ократа и Платона.

2. Возьмём высказывание: `` расстояние от Иркутска до Москвы 5 тысяч километров "". Вместо него мы можем записать предикат `` расстояние "" (означающий, что первый и второй аргумент этого предиката находятся на расстоянии, равном третьему аргументу) для аргументов `` Иркутск "", `` Москва "" и `` 5 тысяч километров "".

3. Высказывание "у каждого человека есть отец" можно записать:

"x $ y (человек(x) Éотец(y,x))

3. Выражение "Джон владеет красной машиной" записывается, например, так:

$ x (владеет(Джон, x) Éмашина(x) &красный(x))

4. Выражение «все простые числа больше чем x» можно записать

" y (P (y ) É Q (x, y )). , где

· P (x ) выражает условие ``x является простым числом"",

· Q (x, y ) выражает условие ``x меньше чем y"".

5. Выражение "у всех людей общий отец".

$ y "x (человек(x) É отец(y,x))