Реферат: Логико-лингвистические модели предикации и предикативности



Министерство высшего образования Российской Федерации

Ульяновский Государственный технический университет


Кафедра «Вычислительная техника»


Реферат
на тему:


Логико-лингвистические модели предикации и предикативности


Выполнил: студент группы ЭВМдм-51

Шембергер А. В.

Научный руководитель: Соснин П. И.


Ульяновск 2002


План реферата
Реферат 1
Введение

Прежде чем начинать рассказывать о логико-лингвистических моделях предикации и предикативности, стоит определить, что же понимается непосредственно под понятиями “предикация” и “предикативность”.

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

Итак, высказывания с упоминанием предикации:

Предикация - динамическая многомерная структура языка — онтологическая (экзистенциальная) сущность (”природа”) коммуникации. ...Предикация суть поток преобразований собственно языковых и ”до-(пост)языковых” структур [6].

Структурная схема предложения есть языковая форма предикации... Категория предикации едина для всех языков; она - принадлежность языка вообще [11].

Если все мышление и конкретное, и абстрактное - образно, то под предикацией предлагается понимать минимальный акт познания, сводящийся к формированию некоторого нового образу, который представляется человеку как уточненный вариант определенного уже существовавшего образа, т. е. ранее установленного знания [7].

В традиции Просвещения полноценной формой познания является суждение. Акт суждения состоит в предикации, т. е. в полагании значимости приписывания предикатов. В этой традиции значимое конституирование суждений считается зависящим от “материальных” (восприятие) и “формальных” (концепты) условий. Допредикативный опыт, по Э. Гуссерлю, есть сфера приобретения суждением содержания. Мы толкуем это понятие несколько шире, считая, что допредикативный опыт связан не только с определенным состоянием чувственного содержания, но и с оформленностью «практических схем». Согласно философскому пониманию, царившему вплоть до 30х г. XX в., предикация представляет собой основной элемент человеческого познания и речи. Отсюда, предикативные действия приписывания/отрицания суть основополагающие действия различения [5].

Семантические роли в предложении распределяются предикацией, отражающей структуру события [1].

Сказуемое иначе называется предикат..., а самый процесс выражения мысли посредством ”сказуемостных” слов и форм - предицированием, или предикацией [13].

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

Предикативность - универсальная лингвистическая категория, она выражает конвенциональное отношение между набором необходимых признаков “означенного”, “отраженного” предложения и его коммуникативной автономностью в потоке речи. Она не может отождествляться с отдельными характеристиками отдельных высказываний на национальных языках (время, наклонение глагола и пр.) ...Предикативность суть система отношений, выражающая осознание коммуникантами завершенности (и авторизованности) ”выдаваемой на поверхность” идеи. Структурно коммуникативная автономность создается на базе компенсирующего баланса между интонацией и целостностью предикативной оппозиции [6].

Такие конструкции обладают... наличием несамостоятельной предика-тивности, помещающейся за пределами формального сказуемого [10].

Соединение подлежащего со сказуемым создаёт предикативную основу предложения, обеспечивающую возможность соотнести предложение в целом с тем или иным фактом действительности, который локализуется во времени и пространстве [14].

Название текста предикативно: оно “руководит” вторичным членением действительности, созданием ее образного двойника в тексте [16].

Всякому предложению свойственна ”предикативность” - то, что делает предложение предложением... “Предикативностью” здесь называется та расчлененность на два компонента, т.е. субъект и предикат суждения [13].

Объединяя все представленные определения и высказывания, договоримся:

называть предикацией минимальный акт познания, процесс выражения мысли посредством “сказуемостных форм”;

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

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

Определим теперь понятие и сущность логико-лингвистических моделей.

Одной из центральных проблем построения систем (представления, описания) управления сложными объектами, обладающими характерными свойствами является построение модели знаний системы об объекте управления и интерпретатора, работающего с этой моделью. Построение модели знаний в свою очередь опирается на наличие специального языка представления знаний (ЯПЗ), без которого эта модель не может функционировать. Этот язык по своим изобразительным возможностям должен быть достаточно богат, чтобы адекватно отображать в модели знаний сведения о структуре объекта и среды, а также о протекающих в них процессах. Такое требование сближает ЯПЗ с естественным языком. Структура ЯПЗ оказывается близкой к структуре естественного языка. Зачастую в качестве ЯПЗ используют просто некоторое подмножество естественного языка, необходимое для управления объектом данной природы. Однако в отличие от естественного языка ЯПЗ должен обладать большей формальностью, логичностью. В противном случае реализовать его в системе управления будет чрезвычайно трудно. Так как модель знаний M в качестве языка будет использовать язык, подобный ЯПЗ, процедурный блок механизма порождения решений (МПР), использующий в своей работе данные модели знаний, должен также оперировать с информацией, записанной на ЯПЗ. Это означает, что процедуры, реализуемые в блоке МПР (по крайней мере, та их часть, которая связана с обработкой и использованием информации, хранящейся в M), должны носить логический, символический характер. Если же предполагается адаптация этих процедур, то и адаптатор должен “понимать” ЯПЗ.

Все сказанное порождает тезис о том, что системы управления сложными объектами, для которых обычные системы управления, базирующиеся на обработке только количественной информации, оказались непригодными, должны строиться как логико-лингвистические. В логико-лингвистических моделях управления логические средства обработки используются для преобразования данных, представленных в лингвистической форме.
^ Основные элементы языков представления знаний предикатного типа
Языки с явно выраженными бинарными отношениями обладают рядом достоинств при описании знаний в системе управления, но для них до сих пор не разработаны эффективные процедуры принятия решений. В отличие от реляционных, предикатные языки (ПрЯ) такой эффективной процедурой обладают. Поэтому, несмотря на то, что представление знаний об объекте управления и среде, в которой он функционирует, в ПрЯ зачастую менее наглядно, чем в реляционных, они все-таки находят широкое применение в логико-лингвистических моделях управления.

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

В определенном смысле исчисление предикатов первого порядка является расширением исчисления высказываний (пропозициональной логики). В состав базовых элементов ПрЯ входят все базовые элементы (пропозициональные символы) исчисления высказываний.

Предикаты бывают одно- и многоместные. Одноместные предикаты отражают некоторые свойства признаков, присущие определенному субъекту или классу субъектов. Примерами одноместных предикатов могут служить утверждения типа: “Металлорежущий станок функционирует”, “Красная шелковая рубашка нравится ему больше всего”. Одноместные предикаты будем записывать как P(x). Здесь P есть предикативный символ, а x - символ предикатной переменной. Для первого утверждения, приведенного выше, P имеет смысл “функционировать”, а x соответствует некоторому “металлорежущему станку”, о котором идет речь в этой фразе. Для второго высказывания P имеет смысл признака “нравиться больше всего”, а x соответствует целому классу понятий “красных шелковых рубашек”.

Многоместные предикаты отражают отношения, которые существуют между группой элементов. Например, фраза “В лесу растут грибы ” соответствует двуместному предикату Q(x, y), в котором символ Q трактуется как отношение “расти в определенном месте”, а предикатные переменные x и y соответствуют элементам “грибы” и “лес”.

Если приписать каждой предикативной переменной свою область определения, то полное задание n-местного предиката будет выглядеть как P(x1, x2, ..., xn); x1X1, ... xnXn. Если некоторое множество Xi состоит только из одного элемента, то соответствующая предикатная переменная xiявляется предикатной константой. В этом случае вместо xi на соответствующем месте в записи предиката допускается написание непосредственно значения этой переменной. Эти утверждения могут относиться ко всем элементам множеств Xi или к конкретным представителям этих множеств. В последнем случае на место предикатных переменных необходимо поставить любые из этих конкретных представителей. Такая операция называется означиванием предикатной переменной. Означивание всех предикатных переменных приводит к тому, что предикатное утверждение превращается в обычное высказывание.

При записи предикатных выражений могут встретиться два важных для практики случая. В первом из них некоторая предикатная переменная может приобретать всю совокупность элементов соответствующего ей множества Xi. В языке это соответствует тому, что в утверждении предикатного типа появляется выражение вида “Для всех xi ...”. Для фиксации этого положения в исчислении предикатов используется специальный символ, называемый квантором общности. Квантор общности, обозначаемый как , пишется перед предикатом, а справа от квантора выписывается предикатная переменная, к которой он относится. Например, рассмотрим утверждение вида “Медведи любят рыбу”. Если при этом X есть множество медведей, о котором идет речь (например, X={бурый медведь, белый медведь}), то это утверждение можно записать как xP(x), где предикатный символ P трактуется как свойство ”любить рыбу”.

Другой важный случай соответствует такой ситуации, когда предикатное высказывание относится к некоторым элементам из Xi, но к каким именно неизвестно. Имеющаяся информация такова, что есть уверенность в существовании хотя бы одного элемента из Xi, относительно которого предикатное высказывание имеет место. Для этого случая используется квантор существования, обозначаемый как . Справа от него пишется предикатная переменная, к которой он относится. В языке квантору существования соответствует конструкция типа “Существует xi ... такой, что”. Например, имеется высказывание “Все время какой-то прибор выключается”. Если множество приборов, о которых идет речь в данной ситуации есть H={прибор№1, прибор№2, прибор №3}, то предикатное утверждение можно записать в следующем виде: hQ(h), где Q соответствует “Выключаться”.

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

Опишем ПрЯ первого порядка. Другими словами, опишем множество базовых элементов этого языка и способов образования правильно построенных производных элементов. В дальнейшем этот ПрЯ будем обозначать через L. В качестве исходных базовых элементов выступают четыре типа таких элементов.

Константы (индивидуальные символы). Это, как правило, имена некоторых объектов типа: “Петров”, ”17”, ”№7”, “Ульяновск” и т. п. В общем виде константы – это фиксированные элементы из множеств Xi.

Переменные (переменные символы). Это малые латинские буквы, начиная с t, с индексами или без них, служащие для обозначения предикатных переменных. Например, y, z4, tk

Функциональные символы. Это символы, обозначаемые буквами f, g, h и малыми греческими буквами с индексами или без них, служащие для выражения функциональных зависимостей между объектами. Иногда вместо греческих букв используются слова русского языка, не содержащие заглавных букв. Примерами функциональных символов могут служить слова: “сложить”, “найти”, “вымочить” и т. п. Другими словами, функциональным символам соответствуют некоторые императивы реляционных языков.

Предикатные символы, обозначаемые либо заглавными буквами, либо словами русского языка, состоящими из заглавных букв. Например, РАВНО, СТРОИТ и т.п.

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

Правила образования термов имеют следующий вид:

Любая константа есть терм.

Любая переменная есть терм.

Если  есть n-местный функциональный символ, а t1 , tk2 ,..., tn есть термы, то (t1 , tk2 ,..., tn) также терм.

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

Примерами термов являются: сложить (x, 7); сложить (сложить (x, 7), z); найти (v); найти (найти (v)).

Если P есть n-местный предикатный символ, а t1 , tk2 ,..., tn - термы, то P(t1 , tk2 ,..., tn) есть атом. Примерами атомов могут служить: РАВНО (y, 5); ВЫГОДНЕЕ(вариант №1, вариант№2), СТРОИТ(t1 , tk2 ,..., tn).

В ПрЯ используются и присущие ему знаки операций отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности ().

Дадим определение формулы:

Атом есть формула (атомарная формула).

Если  и  - формулы, то () также формулы.

Если  есть формула, а переменная x - входящая в нее, то x и x также формулы.

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

Запишем в виде предикатной формулы афоризм Козьмы Пруткова: “Нет столь великой вещи, которую не превзошла бы величиной еще большая. Нет вещи столь малой, в которую не поместилась бы меньшая”. Обозначим вещи переменными x, y, z. Перефразируем афоризм, не меняя его смысла, но исключив его стилистическую привлекательность: “Для каждой вещи x существует вещь y, большая ее. Для каждой вещи x существует вещь z, меньшая ее”. После этого легко записать предикатную формулу для исходного афоризма:  x  y БОЛЬШЕ(x, y)   x  z МЕНЬШЕ(x, z).

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

Каждой переменной xi задается область ее значений Xi. Объединение этих областей X=Xi называется универсумом. Каждая константа интерпретируется некоторым символом из X. Другими словами, интерпретация функциональных символов определяется по интерпретации термов, входящих в качестве аргументов в эту функцию. Каждому предикатному символу приписывается интерпретация, совпадающая с отображением Xn в Q,, где Q={И, Л}. Формула xiP, где P- некоторый предикат, интерпретируется как истинная, если предикат P истинен при всех интерпретациях xi. Другими словами, P остается истинным, когда xi принимает любое значение из области Xi. Формула  xi P) где P- некоторый предикат, интерпретируется как истинная, если предикат P истинен хотя бы при одной интерпретации xi. Другими словами, среди значений xi из области Xi, найдется хотя бы одно значение, для которого P является истинным.

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

Интерпретация кванторов общности и существования позволяет найти зависимость, связывающую эти кванторы. Рассмотрим формулу x(P(x))). Высказывание, стоящее в скобках, будет интерпретироваться как ложное, если среди значений x найдется хотя бы одно x* такое, что P(x*) является ложным. Тогда относительно P можно сформулировать следующее: “Найдется хотя бы одно значение x такое, что P(x) является истинным”. Но это утверждение эквивалентно истинности формулы x(P(x)). Отсюда следует, что x(P(x)))= x(P(x)), где знак равенства понимается как знак равносильности (т. е. совпадения интерпретации данных формул при любых интерпретациях термов и функциональных символов, входящих в них). Аналогично можно показать, что имеет место соотношение xP(x))= x(P(x)).

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

 x  y P(x, y).

Зададим общую область для значений переменных x, y:D={1,2}.

Допустим, что предикат P принимает значения истинности для x и y в области D (табл. 1).

Таблица 1

P(1, 1)

P(1, 2)

P(2,1)

P(2, 2)

И

Л

И

Л


Из этой таблицы видно, что если x=1, то найдется такое значение y (а именно, y=1), при котором P(1, y) истинно. Если же x=2, то при y=1 предикат P(2, y) принимает значение И. Следовательно, для всех значений переменной x в заданной области D имеется хотя бы одно значение переменной y в этой же области, при котором P(x, y) истинно. Таким образом, формула xyP(x, y) в заданной интерпретации истинна.

В качестве еще одного примера возьмем рассмотренную выше запись афоризма Козьмы Пруткова. Проанализируем ее возможную интерпретацию. Зададим область значений для переменных x, y и z как двухэлементное множество D={1,2}.

Далее для предиката МЕНЬШЕ(x, y) зададим отображение Dn в D с помощью таблицы 2.

Таблица 2

МЕНЬШЕ(1, 1)

МЕНЬШЕ(1, 2)

МЕНЬШЕ(2,1)

МЕНЬШЕ(2, 2)

Л

И

Л

И



А для предиката БОЛЬШЕ(x, z) – с помощью таблицы 3

Таблица 3

БОЛЬШЕ(1, 1)

БОЛЬШЕ(1, 2)

БОЛЬШЕ(2,1)

БОЛЬШЕ(2, 2)

Л

Л

И

Л



Из таблиц 2 и 3 видно, что не для всех значений x в области D найдется такой y, когда оба предиката истинны. Для первого из них таблица 2 только при одном значении x (когда x=1) находится значение y (когда y=2) такое, что значение выражения МЕНЬШЕ(1,2) есть И. Следовательно, формула xy МЕНЬШЕ(x, y) в данной интерпретации ложна. Аналогично из таблицы 3 можно определить, что формула xz БОЛЬШЕ(x, z) в этой интерпретации ложна. Следовательно, и значение истинности всей формулы есть Л.

Рассмотрим формулу, содержащую кроме предикатов, функциональный смысл и константу:

(x)(P(x)R(g(x), a)).

Зададим следующую интерпретацию:

D={1,2}, a=2;

g(1)=2, g(2)=1;

P(1) есть И; P(2) есть Л.

Тогда R (g(x), a) можно задать в виде таблицы 4.

Таблица 4

R(1, 1)

R(1, 2)

R(2,1)

R(2, 2)

И

И

И

Л

Такую интерпретацию обозначим буквой I. Когда значение переменной x равно 1, имеет место равенство

P(x)R(g(x), a)= P(1)R(g(1), 2)= P(1)R(2, 2).

В принятой интерпретации P(1) принимает значение И, а R(2, 2) – Л; таким образом, они не равносильны. При данном значении переменной x рассматриваемая формула является ложной.

Проверим истинность формулы при x=2. В этом случае P(2) интерпретируется как Л, а R(1, 2) как И. Таким образом, в этом случае эквивалентность интерпретируется как Л. Поскольку при любых значениях x имеется ложное утверждение под квантором существования, то и вся формула, включающая этот квантор, интерпретируется как ложная.


^ Общезначимость и противоречивость
В пропозициональной логике формула называется общезначимой, если она интерпретируется как истинная при любой интерпретации входящих в нее переменных. Примером общезначимой формулы исчисления высказываний может служить формула (a & b) ( (a  b)). Это легко проверить, задав все четыре возможных комбинации, интерпретирующие а и b, и, убедившись, что во всех случаях формула интерпретируется как истинная. Аналогично определяется общезначимость формул в исчислении предикатов. Формула является общезначимой, если она интерпретируется как истинная при любой возможной интерпретации входящих в нее термов и функциональных переменных.

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

Между общезначимостью и противоречивостью формул имеют место следующие связи:

формула общезначима тогда и только тогда, когда ее отрицание противоречиво;

если формула общезначима, то она непротиворечива (но не наоборот);

если формула противоречива, то она не общезначима (но не наоборот).

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

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

(AB) (A B);

(A B) (B A);

(AB)(BA);

(A (B  C)) ((A B)  C);

(A(BC))((AB)C);

(A (BC)) ((A B)( A C));

(A (BC)) ((A B) ( A C));

(AИ) И;

(AЛ) A;

(AИ) A;

(AЛ) Л;

(A) И;

(A) Л;

)А;

;

;





В качестве примера покажем, что формула непротиворечива при условии, что x и y определены на некоторой области D.

Введем обозначения:

1=; 2=; =12.

Преобразуем вторую формулу, выведя знак отрицания из под знака квантора  и заменив его квантором общности:

2=(yP(y)).

Если в некоторой области значения переменных x и y совпадают, то, очевидно, что формула  всегда ложна. Действительно, если x=y, то формула xP(x)& (xP(x))) ложна, так как это равносильно выражению A&(A)=Л. Рассмотрим случай, когда x и y в заданной области принимают разные значения.

Пусть y приняло такое значение, что (y) оказался истинным. Это означает, что при таком значении y предикат P(y) ложен. Так как x принимает значения из того же самого множества D, что и y, следовательно, ложно утверждение xP(x) (оно не выполняется для рассматриваемого значения y).

Если же 2 никогда не принимает истинного значения, то формула всегда интерпретируется как ложная, так как A&Л=Л.

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

В качестве очередного примера покажем, что формула = является общезначимой. Так как =12, где 1=xP(x); 2=, то для истинности  достаточно найти такую интерпретацию, при которой была бы истинна любая из формул 1 или 2 (или обе вместе). Но 1 и 2 связаны между собой следующим образом:

2=1.

Отсюда на основании соотношения 12 (из 18 соотношений) можно получить: =12=11=И.

Приведенные примеры проверки общезначимости и противоречивости чрезвычайно просты. Для общего случая эти процедуры проводить весьма нелегко, так как число различных предикатов бесконечно, а, следовательно, бесконечно и число возможных их интерпретаций. А никаких других общих приемов для решения подобных задач нет. Положение несколько упрощается при использовании предикатных описаний в реальных управленческих задачах. В этих случаях всегда имеется фиксированное множество различных предикатных символов и конечное число интерпретаций (так как множества Xi в конкретных приложениях всегда конечны и заданы). Поэтому для практических случаев перебор всегда конечен (хотя и может быть весьма большим по объему). Это позволяет использовать при доказательстве общезначимости и противоречивости формул (это оказывается нужным при поиске управленческих решений) обычные процедуры сокращения, характерные для алгоритмов решения переборных задач.

Например, требуется определить, является ли общезначимой формула xP(x), совпадающая по смыслу с утверждением: “Все агрегаты отремонтированы”.

Если речь идет о реальном производстве, для которого множество агрегатов задано (например, D={агрегат №1, агрегат №2, ..., агрегат №805}), то нужно проверить истинность исходной формулы путем определения истинности 805 высказываний вида “Агрегат №i отремонтирован”. Если все эти высказывания истинны, то исходная формула “общезначима“. Конечно, такое определение общезначимости не совпадает с тем, о котором говорилось выше, поэтому это слово взято в кавычки. Но на практике об этом можно не помнить.


^ Логическое следование и теорема дедукции
Итак, был введен синтаксис языка L. Теперь построим процедуры, связанные с правилами вывода этого исчисления. Будем говорить, что формула Q логически следует из формулы P, если для всех интерпретаций, в которых P истинна, формула Q также истинна. Факт логического следования будем обозначать так: P|Q. Логическое следование по существу, описывает некоторый элементарный шаг процедуры вывода новых формул.

Формулу ^ P часто называют посылкой или основанием, а формулу Q – следствием или заключением.

В более общей форме логическое следствие может иметь такой вид: P1 , P2 ,..., Pk |Q. Эта запись означает, что при всех интерпретациях, при которых истинны одновременно все Pi , где i=1, 2, ..., k, истинна и формула Q. Если система аксиом состоит только из общезначимых формул, то при наличии правил вывода типа логического следования из этих общезначимых формул будут выводиться также лишь общезначимые формулы.

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

Теорема дедукции. ^ Формула Q является логическим следствием формул P1 , P2 ,..., Pk тогда и только тогда, когда формула (P1&P2& ... &Pk)Q является общезначимой.

Следствием этой теоремы является тривиально следующее из нее утверждение: формула Q является логическим следствием формул P1 , P2 ,..., Pk тогда и только тогда, когда формула P1&P2& ... &Pk&является противоречивой.

Рассмотрим пример. Даны три формулы: 1 = x(A(x)(x)); 2 = x(B(x) & D(x)); 3 = x((x) & D(x)).

Докажем, что 3 есть логическое следствие формул 1и 2. Пусть найдена такая интерпретация, что 1 и 2 истинны в ней. Это означает, что найдется x=a такой, что B(a) & D(a) является истинной. При этом (а) ложно. Перепишем 1, заменив импликацию дизъюнкцией в соответствии с соотношениями из 18 приведенных ранее:

1 = x((x) (x)).

При x=a 1 истинна, а (a) ложно. Отсюда следует, что (a) является истинным. Из истинности же 2 при x=a вытекает, что D(x) является истинным. Таким образом, при x=a формула 3 является истинной. А поскольку интерпретация, при которой 1 и 2 истинны, была произвольной, то доказано, что 3 логически следует из 1 и 2.

Пример. Докажем тот же факт, что и в предыдущем примере, использовав теорему дедукции. Для этого покажем, что формула (1&2)  3 является общезначимой. Последовательно получаем:

1 & 2 = (x(A(x)  (x))) & (x(B(x) & D(x))).

Если 1&2 ложна, то по свойству импликации (1&2)3является истинной. Поэтому рассмотрим лишь тот случай, когда 1&2 является истинной. Надо показать, что в этом случае 3 также является истинной, ибо это обеспечивает истинность импликации. Но это установлено в предыдущем примере. Поэтому (1&2)3 является общезначимой, и 3 есть логическое следствие 1 и 2.

Пример. Дана формула 1 = (x). Требуется показать, что из нее не следует формула 2 = x((x)).

Зададим некоторую область значений для переменной x, например D={1, 2}. Покажем, что нужное утверждение следует уже из анализа этой простейшей области значений переменной. Рассмотрим четыре возможные интерпретации предикат P(x), которые сведем в таблице 5.

Таблица 5

I

X

P(x)

(x)

x((x))

I1

1

2

Л

Л

И

И

И 

И

И

I2

1

2

Л

И

И

Л

Л 

И

Л

I3

1

2

И

Л

Л

И

Л 

Л

И

I4

1

2

И

И

Л

Л

Л 

Л

Л

Из этой таблицы видно, что только при интерпретации I1 не нарушаются условия логического следования. Поэтому 2 не следует из 1.

Пусть даны формулы 1 = x(P(x)  Q(x)); 2 = P(a); 3 = Q(a).

Покажем, что 3 логически следует из 1 и 2. Пусть I есть интерпретация, при которой 1&2 является истинной. Тогда в этой интерпретации 1 и 2 по отдельности также истинны. Преобразуем 1 к виду 1 = x((x)  Q(x)).

Пусть в интерпретации I формула 3 оказалась ложной. Это означает, что при x=a должна быть ложной 1, так как (a) является ложным (по предложению 2, а, следовательно, P(a), являются истинными). Полученное противоречие подтверждает вывод об истинности 3 при истинности 1 и 2. Это значит, что 3 логически следует из 1 и 2.
^ Нормальные формы в логике первого порядка
В этом параграфе введем специальные формы аналитических представлений в логике предикатов первого порядка. Эти представления аналогичны каноническим формам представления в логике высказывания: дизъюнктивной и конъюнктивной нормальным формам. Напомним, что высказывание представлено в дизъюнктивной нормальной форме (ДНФ), если оно записано в следующем виде:

F = F1  F2  ...  Fm.

При этом высказывания Fi имеют вид:

Fi1  Fi2  ...  Fir,

причем каждое Fij есть или буква (базовый элемент), или буква с отрицанием. Примером ДНФ может служить:

F = abh  c.

Высказывание представлено в конъюнктивной нормальной форме (КНФ), если оно записано в следующем виде:

F = F1  F2 & ... & Fl.

При этом высказывания Fi имеют вид:

Fi1  Fi2  ...  Fis,

причем каждое Fij есть или буква, или буква с отрицанием.

Примером КНФ может служить:

F = (a   h) & (b  ).

Аналоги этих представлений есть и в логике предикатов первого порядка. Будем говорить, что формула Ф представлена в предваренной нормальной форме (ПНФ), если она представлена в следующем виде:

Ф = ʞ1x1ʞ2x2...ʞnxnM,

где каждый ʞixi – квантор общности xi или квантор существования xi, а M – формула, не содержащая кванторов. Например,

Ф = xz(R(x) & Q(z)).

Часть записи в ПНФ, предшествующая M, называется префиксом. Формула M, не содержащая кванторов, называется матрицей.

Для преобразования формулы к ПНФ используются эквивалентные преобразования, указанные в примере 3-8, а также специальные правила вынесения кванторов в префиксную часть (вынесение кванторов за скобки). Эти правила имеют следующий вид (пусть F есть формула, не содержащая x):

ʞxR(x) F = ʞx(R(x) F);

ʞxR(x) F = ʞx(R(x) F);

если G и Q – формулы, содержащие переменную x, то

xG(x) & (xQ(x)) = x(G(x) & Q(x));

xG(x)  (xQ(x)) = x(G(x)  Q(x));

Правило 3 отражает тот факт, что при наличии связанных переменных квантор общности может быть вынесен за скобки (т. е. формула может быть преобразована в ПНФ), если в этой формуле кванторы соединены операцией конъюнкции. Такая же возможность есть и для кванторов существования, если они соединены в формуле операцией дизъюнкции (правило 4).

Существенно, что квантор  не может быть выражен через дизъюнкцию, а квантор  – через конъюнкцию, т. е. формулы

A1: xG(x)  xQ(x)

и

A2: x(G(x)  Q(x))

не эквивалентны, как не эквивалентны формулы

A1: xG(x)  xQ(x)

и

A2: x(G(x)  Q(x))

Тем не менее, есть возможность преобразования двух последних формул в ПНФ, если прибегнуть к искусственному приему, суть которого заключается в том, что некоторая связанная переменная x одного квантора меняется переменной y, но такой, которая не входит в область значений переменной другого квантора, т. е. не встречается в G(x).

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

Пусть имеется формула  = xG(x)xQ(x). Преобразуем  путем переименования всех вхождений x в формулу, являющуюся второй частью в дизъюнкции. Тогда получим  = xG(x)yQ(y). Используем первое из перечисленных выше правил эквивалентных преобразований:

 = xy(G(x)Q(y)).

Стандартизируем формулу, описывающую афоризм К. Пруткова:

 = xyP(x, y)&xzQ(x, z).

Вынесем за скобки x:

 = x(yP(x, y)&(zQ(x, z))).

Здесь кванторы существования y и z связаны знаком конъюнкции, что на первый взгляд препятствует выносу этих кванторов за скобки. Но на самом деле в формуле yP(x, y) только y – связанная переменная, а в формуле zQ(x, z) связанной переменной является z. Поэтому вполне можно и здесь вынести кванторы y и z за скобки, приведя к предваренной нормальной форме:

 = xyz(P(x, y)&Q(x, z)).
^ Описание ситуаций в предикатной форме
Рассмотренный предикатный язык, подобно языку реляционного типа, может служить для описания ситуаций, складывающихся на объекте управления и среде, в которой этот объект функционирует. Приведем несколько примеров, описывающих следующую ситуацию:

К причалу №1 подходит судно “Свирь”, пришедшее с грузом леса. Портальный кран №8 занят на разгрузке судна “Беломорск” на причале №2. Этой же операцией занят портальный кран №5. Портальный кран №6 свободен, но не может быть перемещен на причал №1 из-за крана №5.

Будем последовательно вводить необходимые предикаты, и описывать наблюдаемую ситуацию. Введем предикаты P1(x, y) и P2(x, z). Первый предикат будет истинным, если судно x приближается к причалу y. Областью определения переменной x будет служить множество, состоящее из всех названий судов, а областью определения y – множество всех номеров причалов. Второй предикат будет истинным, если судно x имеет груз z. Областью значений переменной z будут всевозможные значения грузов. При этих предположениях первой фразе описания наблюдаемой ситуации “К причалу №1 подходит судно ‘Свирь’, груженое лесом”, будет соответствовать следующая предикатная запись:

P1(“Свирь”, №1)& P2(“Свирь”, лес).

Введем предикат P1(u, x), который является истинным, если портальный кран u занят на операции разгрузки судна x. Областью значений u является все множество названий для портальных кранов. Введем также предикат P4(u, y), который является истинным, если портальный кран u находится на причале y. Тогда вторая фраза описания наблюдаемой ситуации: “Портальный кран №8 занят на разгрузке судна ‘Беломорск’ на причале №2” на предикатном языке выглядеть так:

^ P3(№8, “Беломорск“)&P4(№8, №2).

Третьей фразе “Этой же операцией занят портальный кран №5” соответствует описание:

P3(№5, “Беломорск“).

Введем предикат P5(u), который истинен, если портальный кран u свободен. Кроме того, введем предикат P6(u, y), который принимает истинное значение, когда портальный кран u можно передвигать на причал y. Наконец, введем предикат P7(u1, u2) определены на том же множестве значений, что и u. Этот предикат является истинным, если портальный кран u1 является препятствием для портального крана u2. С учетом введенных предикатов последняя фраза описания ситуации “Портальный кран №6 свободен, но не может быть перемещен на причал №1 из-за крана №5” может быть представлен как

P5(№6)& P6(№6, №1)&P7(№5, №6).

Конъюнкция записей для всех фраз описания приводит к полной записи наблю
еще рефераты
Еще работы по разное