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

 

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

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

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

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

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

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

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

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

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

Кванторы

Помимо операций алгебры высказываний, в логике предикатов есть 2 операции, которые связаны с природой предикатов. Пусть дан предикат P(x), зависящий от одной переменной и определённый на поле M.

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

б) Выражение (∃ x)P(x) означает высказывание, истинное только в том случае, когда предикат P(x) истинен хотя бы для одного предмета из поля M. Выражение (∃ x)P(x) читается «существует x, что P(x)»; символ ∃ - квантор существования.

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

1) , тогда (∀ x) ( =x*x) – истинное высказывание

2) , тогда (∀ x) (x+2=7) – ложное высказывание; а (∃ x) (x+2=7) – истинное высказывание

3) x+2=x, тогда (∀ x) (x+2=x) – ложное высказывание

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

 

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

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

Рассмотрим некоторые общие свойства введенных операторов.

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

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

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

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

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

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

 

 

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

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

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

Например, — формула логики предикатов.

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

Сформулируем следующие правила.

(1) Формула логики предикатов называется атомарной, т. е. элемен­тарной, если в ней нет связанных переменных.

(2) Пусть F — формула, тогда F — тоже формула. Свободные и связан­ные переменные формулы F — это соответственно свободные и связанные переменные формулы F.

(3) Пусть F и G — формулы, причем в них нет предметных перемен­ных, которые были бы связаны в одной формуле и свободны в другой.

Тогда F/\G, F\/G, F→ G, F↔ G — формулы, в которых свободные переменные формул F и G остаются свободными, а связанные — связан­ными.

(4) Пусть F — формула, содержащая свободную переменную х. Тогда , (∃ x)F — тоже формулы, в которых переменная х связана, а осталь­ные свободные переменные, входящие в F, остаются свободными.

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

Значение формулы определено лишь тогда, когда задана какая-то ин­терпретация входящих в нее символов. Под интерпретацией понимают систему М = (M, f), состоящую из непустого множества М и соответ­ствия f, которое сопоставляет каждой формуле определенный предикат. При заданной интерпретации предметные переменные пробегают множе­ство М, а логические символы и символы кванторов имеют свой обычный смысл.

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. A. эксплуатируемые вручную или с применением ручного труда; без применения ручного труда (механические, автоматические и др.).
2. MS Excel 2007-2010. Применение стиля ячейки
3. Анализ кривых безразличия и их применение.
4. Архитектурно-строительные чертежи, разработанные с применением автоматизированных программ.
5. Бетонирование с применением противоморозных химических добавок.
6. Возникновение и применение свободного (конькового) стиля
7. Возникновение, развитие и первоначальное применение лыж
8. Вопрос 15 Налоговые вычеты: понятие, применение в отношении различных налогов
9. Вопрос 2. Сущность и применение товарной категории.
10. ВОПРОС 40. Применение права как особая форма его реализации.
11. ВОПРОС 40. Применение права как особая форма его реализации.
12. Вопрос 45. Применение права: понятие, стадии.