Рk(х1, х2, ., хk): Мk → {1,0}.

Например, если Х — множество действительных чисел, то х² > 1 — одноместный предикат.

Если X, У — множества действительных чисел, то ху = 5 — двуместный предикат.

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

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

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

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

Например, если к предикатам «х = y» и «х < у» — обозначим их соответственно Р(х, у) и Q(x, у) — применить операцию конъюнкции, то получим новый предикат Р(х, у) Q(x, у).

Применение предикатов в алгебре

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

Типичным примером является уравнение, например, х²-Зх+2=0. Свободная переменная может принимать здесь любое числовое значение. Для некоторых чисел х (а именно х = 1, х = 2 ) утверждение, содержащееся в этом уравнении, истинно, в остальных оно ложно. В подобных случаях, когда истинность или ложность предиката зависит только от значения, принимаемого свободной переменной х, множество допустимых значений х можно рассматривать как множество логических возможностей U, а множество всех значений этой переменной, при которых высказывание истинно — как его множество истинности.

В приведенном выше примере множество U состоит из всех действительных чисел, а множеством истинности является множество {1,2}.

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

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

Если U — множество действительных чисел, то множество истинности неравенства х < 0 состоит из всех отрицательных действительных чисел. Множество же истинности неравенства х > -3 состоит из всех действительных чисел, больших, чем -3. Если мы потребуем, чтобы эти неравенства выполнялись одновременно, то множеством истинности будет множество, являющееся пересечением двух исходных множеств, т.е. все действительные числа между -3 и 0.

Понятие множества истинности предиката позволяет выяснить, чем разнятся между собой уравнения и тождества. Когда мы решаем уравнение, мы тем самым ищем один из элементов множества истинности этого уравнения или все его элементы. Если же мы доказываем тождество, то тем самым утверждаем, что оно справедливо для всех х. Таким образом, тождество представляет собой уравнение, множеством истинности которого является универсальное множество U, т. е. является логически истинным или тождественно истинным.

Предикаты P и Q, определенные на X, называются равносильными, если P(х₁, х₂,..., х_п) ≡ Q(х₁, х₂,..., х_п) для любого набора (х₁, х₂,..., х_п) предикатных переменных на X

Пусть P - предикат, определенный на X. Отрицанием предиката P называется предикат, обозначаемый определенный P (неP) на X следующим образом:

P(х₁, х₂,..., х_п) = P(х₁, х₂,..., х_п)

Пример. P(х₁, х₂) = P(х₁, х₂) = "Натуральное число х₁ делится (без остатка) на натуральное число х₂ ". P(4, 2) = 0, P(5, 3) = 1,

Пусть P и Q предикаты, определенные на X.

Дизъюнкцией (конъюнкцией, импликацией, эквиваленцией) предикатов P и Q называется предикат, определенный на X обозначаемый P Q, P Q, P Q, P Q, и определяемый следующим образом:

P Q(х₁, х₂,..., х_п) ≡ P(х₁, х₂,..., х_п) Q(х₁, х₂,..., х_п)

P Q(х₁, х₂,..., х_п) ≡ P(х₁, х₂,..., х_п) Q(х₁, х₂,..., х_п)

P Q(х₁, х₂,..., х_п) ≡ P(х₁, х₂,..., х_п) Q(х₁, х₂,..., х_п)

P Q(х₁, х₂,..., х_п) ≡ P(х₁, х₂,..., х_п) Q(х₁, х₂,..., х_п)

Булева алгебра предикатов

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

Теорема. (Свойства логических операций для предикатов).

Множество n -местных предикатов, определенных на X, образуют булеву алгебру предикатов, т.е. для них справедливы основные равносильности булевой алгебры.

1. - закон двойного отрицания

2. - коммутативность дизъюнкции;

3. - коммутативность конъюнкции;

4. - ассоциативность дизъюнкции;

5. - ассоциативность конъюнкции;

6. - дистрибутивность дизъюнкции относительно конъюнкции;

7. - дистрибутивность конъюнкции относительно дизъюнкции;

8. ; - законы де Моргана;

9. ; - идемпотентность;

10. ; ; ; - законы единицы и нуля

- идемпотентность;

11. ; - закон поглощения

12. ; - закон поглощения

13. - закон исключенного третьего

14. - закон противоречия

Кванторы

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

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

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

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

1) х² = х х, тогда ( х) (х² = х х) — истинное высказывание;

2) х + 2 = 7, тогда ( х) (х+2 = 7) — ложное высказывание; а ( х) (х + 2 = 7) — истинное высказывание;

3) х + 2 = х, тогда ( х) (х + 2 = х) — ложное высказывание.

Название	Прочтение	Обозначение
Квантор общности	«все», «всякий», «каждый», «любой»
Квантор существования	«Хотя бы один», «найдется», «существует»

Квантор общности — это оператор, приводящий в соответствии любому заданному предикату у = Р(х) такую двузначную логическую переменную z, которая принимает значение 1 тогда и только тогда, когда у = 1 при всех значениях х.

Квантор существования — это оператор, приводящий в соответствии любому одноместному предикату у = Р(х) такую двузначную логическую переменную z, которая принимает значение 0 тогда и только тогда, когда у = 0 при всех значениях х.

Рассмотрим некоторые общие свойства введенных операторов. В соответствии с определениями кванторов логическая переменная z в выражениях

z = ( х)Р(х)

z = ( х)Р(х)

уже не является функцией предметной переменной х.

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

Например, в предикате

( х) A(х,y) ( z) B(z,v)

переменные х и z — связанные, а у и v — свободные.

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

Формулы логики предикатов

Наряду с определенными предикатами — для которых истинность или ложность известны для каждого набора значений свободных предметных переменных, будем рассматривать переменные предикаты, для которых не определены значения. Будем обозначать переменные предикаты большими буквами из конца латинского алфавита с приписанными предметными переменными или без них:

Дата добавления: 2015-07-07