Логика предикатов

Основные понятия логики предикатов

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

называются предикатами. Логика предикатов представляет собой развитие логики высказываний.

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

Предикат с одной переменной называется одноместным предикатом, с двумя – двуместным, а предикат, содержащий переменных, называется n–местный предикатом.

–местный предикат – это функция от переменных, принимающих значения из некоторых заданных предметных областей, так, что , а функция принимает два логических значения – «истина» и «ложь». Таким образом, предикат является функцией типа , где множества называются предметными областями предиката; – предметными переменными предиката; – двоичное множество. Если предикатные переменные принимают значения на одном множестве, то .

В качестве примера рассмотрим три высказывания:

– «Рубль – валюта России»,

– «Доллар – валюта России»,

– «Доллар – валюта США».

Высказывания и истинны, высказывание – ложно. Если вместо конкретных наименований валюты в выражениях , , подставить предметную переменную и определить ее на множестве наименований денежных единиц Î{ рубль, доллар, марка, крона и т.д. }, то получим одноместный предикат, например, – « – валюта России».

Если в выражениях (или аналогичных им) вместо конкретных наименований валюты и государства подставить переменные и , где Î{Россия, США, Англия, и т. д.}, получим двухместный предикат – « – валюта ». Приписав и конкретные значения, получим высказывание, обладающее свойством «истинно» или «ложно».

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

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

Пример. Предикат – двухместный предикат, предметной областью которого могут служить любые множества действительных чисел. Высказывание 6>5 истинно, а высказывание 4>8 ложно.

Пример. Великая теорема Ферма, не доказанная до сих пор, утверждает, что для любого целого числа >2 не существует натуральных чисел , удовлетворяющих равенству . Если этому равенству поставить в соответствие предикат , истинный только тогда, когда равенство выполняется, а через обозначить предикат « – натуральное число», то теорема Ферма равносильна утверждению: «выражение истинно для любых чисел ».

Пример. Определим следующие предикаты:

Предикат тождества . тогда и только тогда, когда .

Предикат делимости . тогда и только тогда, когда делится на .

Предикат суммы . тогда и только тогда, когда .

Тогда предикатные формулы

,

,

,

,

имеют следующие словесные формулировки:

· «если делится на и делится на , то делится на »,

· «если каждое слагаемое , суммы целых чисел делится на некоторое число , то и сумма делится на это число»,

· «число не делится на число и неверно, что их сумма равна »,

· «от перестановки мест слагаемых и сумма не меняется».