yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Глава 4. ТЕОРИЯ ПРЕДИКАТОВ ПЕРВОГО ПОРЯДКА

Математическая логика

Глава 4. ТЕОРИЯ ПРЕДИКАТОВ ПЕРВОГО ПОРЯДКА

4.1. Основные понятия

Рассмотрим умозаключение: Все люди смертны (А). Сократ - человек (BJ. Следовательно. Сократ смертен (С). Очевидно, что С следует из А и В, однако, логическое следование А, В |= С недоказуемо в алгебре высказываний. Причина заключается во внутренней структуре высказываний.

Внутреннюю структуру высказывания можно разделить на субъект и предикат, где субъект есть подлежащее, предикат определяет свойство субъекта. Например, Сократ - это субъект, а предикат определяет свойство его быть человеком. Заменив субъект на переменную х, получим предикат, определенный на множестве людей: "х есть человек". Обозначим его Р(х). Подставляя на место переменной х объекты из ее области определения, получаем высказывания. Таким образом, одноместный предикат, определенный на некотором множестве объектов, задает свойство, которым эти объекты могут обладать или не обладать. При подстановке на свободное место предиката какого-либо объекта из его области определения предикат обращается в высказывание, истинное или ложное. Таким образом, предикат разбивает это множество на две области: область истинности и ложности.

Определение 4.1. Одноместным предикатом Р(х.), определенным на множестве М, называется выражение, которое после подстановки в него вместо х предмета из области определения М обращается в высказывание.

Определение 4.2. Область определения предиката называется предметной областью. Элементы из области определения называются предметными постоянными.

Определение 4.3. Переменная, от которой зависит предикат, называется предметной переменной.

Двуместный предикат задает отношение между двумя объектами из области определения. Например, Р(х,у): х>у, x.yR. Предикат задает отношение "больше" на множестве действительных чисел. Подставив в него значения, получим высказывание: 5>2=Т, 6.8>10=F. Если подставить только значение ', =1, получим одноместный предикат: х>1, который задает свойство действительный чисел быть (или не быть) больше единицы. Определим следующий предикат: S(x,y): "х родился в у году", х{люди}, yN. Предикат задает отношение на множестве людей и множестве целых чисел. В общем случае n-местный предикат определяет n-местное отношение.

Определение 4.4. N-местаым предикатом, определенным на множествах Ml, M2,..., Мn, называется выражение, которое обращается в высказывание при замене каждой предметной переменной на элемент из ее области определения. Если все предметные переменные определены на одном и том же множестве, то предикат называется однородным.

Операции над предикатами.

Предикат можно рассматривать как функцию, определенную на некотором множестве объектов и принимающую два значения, Т и F, т. е. как булеву функцию. Поэтому над предикатами определены все булевы операции: ¬, &, v, , , а также две новые операции - операции навешивания кванторов  - всеобщности и  - существования. Определим понятие формулы.

Определение терма.

•    Каждая   предметная  переменная   или  предметная   постоянная   есть терм.

•    Функциональный символ f(t1,...tn), где t1,...,tn - термы, есть терм.

•    Других термов нет.

Определение формулы.

•    P1n(t1,...,tn),   где   Р1n  -   предикатный   символ,   t1,...,tn   -   термы,   есть атомарная формула.

•    Если А и В - формулы их- предметная переменная, то формулами являются (¬А), (АВ), (xA), (хА).

•    Других формул нет.

Выражении А&В, AvB, AB определяются так же, как в исчислении L.

Если Р(х) определяет некоторое свойство на множестве М, то формула xP(x) обозначает высказывание: "для всякого предмета хМ свойство Р(х) выполняется", или "все х обладают свойством Р(х)". Формула хР(x) означает: "существует по крайней мере один предмет х, обладающий свойством Р(х)", или: "некоторые х обладают свойством Р(х)". Предикат Р(х), на который распространяется действие квантора, называется областью действия квантора. Переменные, по которым "навешивается квантор и попадающие в его область действия, называются связанными переменными. Переменные, лежащие вне области действия квантора, называются свободными. Область действия квантора ограничивается скобками, если она содержит более одного предиката. Формула, не содержащая свободных переменных,     называется     замкнутой.     Замкнутые     формулы     являются высказываниями.

Пример. x(P(x) Q(x, y)), оба вхождения х - связанные, у- свободная переменная. xP(x) yQ(x, y) - первое вхождение х - связанное, второе -свободное, у - связанная переменная. xy(P(x)  Q (x, y)) - замкнутая формула.

Кванторы  и  связаны друг с другом по принципу двойственности (по законам де Моргана): ¬x A)  (xA), т. е. свойство А выполняется не для всех х тогда и только тогда, если существует такое х, для которого оно не выполняется.

 

24