Реферат: Логико-лингвистические модели предикации и предикативности
Министерство высшего образования Российской Федерации
Ульяновский Государственный технический университет
Кафедра «Вычислительная техника»
Реферат
на тему:
Логико-лингвистические модели предикации и предикативности
Выполнил: студент группы ЭВМдм-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); x1X1, ... xnXn. Если некоторое множество 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) истинно. Таким образом, формула xyP(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) есть И. Следовательно, формула xy МЕНЬШЕ(x, y) в данной интерпретации ложна. Аналогично из таблицы 3 можно определить, что формула xz БОЛЬШЕ(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 формул являются общезначимыми:
(AB) (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 (BC)) ((A B) ( A C));
(AИ) И;
(AЛ) A;
(AИ) A;
(AЛ) Л;
(A) И;
(A) Л;
)А;
;
;
В качестве примера покажем, что формула непротиворечива при условии, что x и y определены на некоторой области D.
Введем обозначения:
1=; 2=; =12.
Преобразуем вторую формулу, выведя знак отрицания из под знака квантора и заменив его квантором общности:
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 формула является ложной, следовательно, она противоречива.
В качестве очередного примера покажем, что формула = является общезначимой. Так как =12, где 1=xP(x); 2=, то для истинности достаточно найти такую интерпретацию, при которой была бы истинна любая из формул 1 или 2 (или обе вместе). Но 1 и 2 связаны между собой следующим образом:
2=1.
Отсюда на основании соотношения 12 (из 18 соотношений) можно получить: =12=11=И.
Приведенные примеры проверки общезначимости и противоречивости чрезвычайно просты. Для общего случая эти процедуры проводить весьма нелегко, так как число различных предикатов бесконечно, а, следовательно, бесконечно и число возможных их интерпретаций. А никаких других общих приемов для решения подобных задач нет. Положение несколько упрощается при использовании предикатных описаний в реальных управленческих задачах. В этих случаях всегда имеется фиксированное множество различных предикатных символов и конечное число интерпретаций (так как множества 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 – формула, не содержащая кванторов. Например,
Ф = xz(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). Используем первое из перечисленных выше правил эквивалентных преобразований:
= xy(G(x)Q(y)).
Стандартизируем формулу, описывающую афоризм К. Пруткова:
= xyP(x, y)&xzQ(x, z).
Вынесем за скобки x:
= x(yP(x, y)&(zQ(x, z))).
Здесь кванторы существования y и z связаны знаком конъюнкции, что на первый взгляд препятствует выносу этих кванторов за скобки. Но на самом деле в формуле yP(x, y) только y – связанная переменная, а в формуле zQ(x, z) связанной переменной является z. Поэтому вполне можно и здесь вынести кванторы y и z за скобки, приведя к предваренной нормальной форме:
= xyz(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).
Конъюнкция записей для всех фраз описания приводит к полной записи наблю
еще рефераты
Еще работы по разное
Реферат по разное
Факультет права Реферат. По дисциплине : «Информатика и математика» На тему: «Законодательство о товарных знаках»
17 Сентября 2013
Реферат по разное
Задачи на делимость чисел в егэ 17 Разностные уравнения 18
17 Сентября 2013
Реферат по разное
План: україна І первісне виникнення мов. Історія української літературної мови у висвітленні І. Огієнка
17 Сентября 2013
Реферат по разное
Секция: Историческое краеведение Исследовательский
17 Сентября 2013