Предикаты и логические операции над ними

Для формализации естественного языка часто недостаточно высказываний. Это хорошо видно на таком классическом примере.

 

Каждый человек смертен. Так как Сократ человек, то он смертен». Это утверждение можно представить формулой алгебры высказываний

,

где : «Каждый человек смертен», : «Сократ – человек», : «Сократ – смертен», или соответствующей формулой алгебры высказываний

.

Построим таблицу истинности этой формулы:

.

Отсюда вывод: формула алгебры высказываний не общезначимая, а значить высказывание не является логическим выводом из и , что неверно.∎

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

Дадим определение предиката.

Пусть – произвольное множество. Отображение

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

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

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

Множество

называется областью истинности предиката . Очевидно, что

.

Если , то предикат – тождественно истинный, а если (пустому множеству) – тождественно ложный.

Пусть множество . Отображение (функция)

называется n-местным предикатом , , , …, .

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

Высказывания логики высказываний можно интерпретировать как 0-местные предикаты.

Пример 1

1) Истинное высказывания «11 – простое число» – 0-местный предикат.

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

3) Утверждение «Число больше числа » – двухместный предикат .

Предметная область

.

– одноместный предикат, определен на множестве (тождественно ложный предикат).

– одноместный предикат, определен на множестве .

– ложное высказывание (0-местный предикат).

Множество истинности предиката .

4) Утверждение «» – одноместный предикат . Предметная область предиката – множество действительных чисел, множество истинности предиката – множество корней квадратного уравнения. ∎

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

Конъюнкцией двух предикатов и , определенных на множестве , называют предикат с областью истинности

Дизъюнкцией предикатов и называют предикат с множеством истинности

Отрицанием предиката называют предикат с областью истинности

– разницей множеств и (дополнение множества к множеству ).

Импликацией предикатов и называют предикат с областью истинности

.

Пример 2

На множестве

заданы предикаты « не делится на 5», « – четное число», « – простое число», : « кратно 3». Определить области истинности предикатов , , .

Выполнение.

, ,

, .

,

.

,

,

,

,

. ∎

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

Пример 3

На множестве определены два предиката: : « – простое число» и : « – нечетное число». Составить их таблицы истинности. Предикаты и равносильны? А если они определены на множествах и ?

Выполнение. Таблица истинности предикатов на множестве :

Область истинности предиката , область истинности предиката . Эти области совпадают и поэтому предикаты на множестве равносильны.

Таблица истинности предикатов на множестве :

Область истинности предиката , область истинности предиката . Эти области не совпадают и поэтому предикаты на множестве неравносильны. Поскольку , то является логическим выводом .

Таблица истинности предикатов на множестве :

Область истинности предиката , область истинности предиката . Эти области не совпадают и поэтому предикаты на множестве неравносильны. Поскольку , то является логическим выводом .

Пример 4

Даны два двухместных предиката на множестве ( – множество действительных чисел):

: «», : «».

Является ли один из предикатов логическим выводом другого?

Выполнение. Область определения и область истинности предиката :

(на рис.1.1 – заштрихованая),

(на рис.1.2 – жирная линия)

Рис 1.1. Область определения и область истинности предиката

Область определения и область истинности предиката (рис. 1.2):

,

Рис.1.2. Область определения и область истинности предиката

Видно, что , то есть является выводом .

КВАНТОРНЫЕ ОПЕРАЦИИ

Пусть – предикат, определенный на множестве . Высказывание – это высказывание, которое истинно, если предикат истинный для каждого (то есть, если он тождественно истинный), и ложно в противоположном случае. Естественным языком высказывание формулируется так: «Для всех предикат – истинный предикат ()». Знак называется квантором всеобщности.

Высказывание – это высказывание, которое истинно, если существует такое , при котором предикат истинный, и ложно в противоположном случае (то есть, когда предикат является тождественно ложным). Естественным языком высказывание формулируется так: «Существует , для которого предикат – истинный предикат ()». Знак называется квантором существования.

Кванторы и относятся к кванторным операциям, при которых предикату ставится в соответствие высказывания и соответственно.

Пример 1

Пусть на множестве определены предикаты : « – простое число» и : « – парне число». Тогда высказывания:

ложно;

ложно;

истинно;

истинно;

ложно;

истинно. ∎

Пусть множество конечно. Тогда

Итак, кванторные операции и являются обобщением логических операций конъюнкции и дизъюнкции соответственно.

Переменная предиката называется свободной переменной, а эта же переменная в высказываниях и является связанной переменной. Значение предиката зависит от , значения высказываний и не зависят. Кванторные операции и по переменной связывают эту переменную.

Кванторные операции применяются и к многоместным предикатам. Применение кванторных операций к двухместному предикату по переменной , например, ставит ему в соответствие одноместный предикат или , который зависит от , и не зависит от . Итак, связывание переменных уменьшает количество аргументов предиката (уменьшает порядок предиката).

К двухместным предикатам можно применять кванторные операции и по двум переменным. В результате получим восемь высказываний:

;

;

;

;

;

;

;

;

ФОРМУЛЫ АЛГЕБРЫ ПРЕДИКАТОВ

Формулы алгебры предикатов строятся из атомарных формул (атомов). Для записи атомов алгебры предикатов используются:

· символы истинностных значений ( и );

· символы переменных высказываний ( …);

· символы предметных переменных ()

· символы предметных констант (элементов предметной области);

· символы предикатов;

· функциональные символы;

· символы логических операций;

· символы кванторных операций;

· вспомогательные символы: скобки, запятые.

Аргументы n -местного предиката называются термами. Терм рекурсивно определяется следующим образом:

· предметные переменные и предметные константы – термы;

· если -местный предикат и – термы, то также терм.

Формулой алгебры предикатов называют любое выражение, содержащее символику 1-7 и удовлетворяющее таким условиям:

· атом – формула;

· если и – формулы, то , , тоже формулы при условии, что одна и та же предметная переменная не есть в свободной, а в связанной и наоборот;

· если – формула, то и – формула;

· если – формула, что содержит предметную переменную , то и – формулы, причем, если в – свободная переменная, то в и она выступает в качестве связанной переменной.

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

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

Подслово формулы , которое само является формулой, называют подформулой формулы .

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

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

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

Пример 1

Которые из приведенных ниже слов являются формулами алгебры предикатов?

1) ;

2) ;

3) ;

Выполнение.

1) не является формулой, потому что квантор существования употребляется для связанной переменной, что недопустимо;

2. является формулой алгебры предикатов. Здесь – символ переменной высказывания, – символ логической операции, – символ кванторной операции, – символы предметных переменных, – предикатный символ, скобки и запятая – вспомогательные символы.

3. – не является формулой, потому что предметная переменная – связанная в первом операнде логической операции дизъюнкции и свободная в другом, что недопустимо.

Пример 2

Пусть двухместный предикат : «число n делится на число m». Предметная область этого предиката – область натуральных чисел. Тогда одноместный предикат:

· : «число n делится на 3»;

· : «число n делится на 2»;

· : «число n делится на 4»;

· : «число n делится на 6», : «число n делится на 12».

Вычислить значения формул алгебры предикатов:

a) ;

b) .

Выполнение.

a) :

o : «Число n делится на 2 и на 3, то есть, делится на 6»;

o : «Если число n делится на 6, то оно делится на 12».

В итоге:

,

(число делится на 6, но не делится на 12).

:

o : «Число n делится на 2 и на 4, то есть, оно делится на 4»;

o : «Число n не делится на 6».

o : «Если число n делится на 4, то оно не делится на 6».

Число делится на 4, но не делится на 6. Поэтому

. ∎