Доказательство. 2 страница

Пусть лемма доказана для любой формулы, включающей не более n логических связок. Рассмотрим формулу Ф_n+1 включающую n+1 логическую связку. Пусть связка последнего уровня (последняя в порядке применения) это j_j^*(f₁, f₂,…, f_l), где f₁,…, f_l – формулы, включающие не более n логических связок, для них лемма выполняется по индуктивному допущению, следовательно, существует удовлетворяющие условию леммы f₁¹, f₂¹,…, f₁^l, f₂^l, такие что f_i=<f₁ⁱ,f₂ⁱ>. Опять-таки, по определению диалогового произведения имеем: j_j^*(<f₁¹,f₂¹>,<f₁²,f₂²>,…,<f₁^l,f₂^l>)=<j_i^’(f₁¹,f₁²,…,f₁^l), f_i^’’(f₂¹,f₂²,…,f₂^l)>=<Ф₁,Ф₂>.

Следствие 3.2. Пусть формула Ф общезначима в логиках L₁ и L₂, тогда она общезначима и в логике L₁°L₂ и наоборот.

Доказательство. Вытекает из леммы 3.4.

Таким образом, выводимость в L₁°L₂ напрямую следует из выводимости в L₁ и L₂. Однако, достаточно ли этого? Будет ли система функций для L₁°L₂ функционально полной?

Лемма 3.5. Любая система функций, дистрибутивных относительно декартова произведения нетривиальных логик L₁´L₂, не полна функционально.

Доказательство. Выберем в логиках L₁ и L₂ по два значения (это можно сделать, так как логики нетривиальны), обозначим их T₁, F₁, T₂ и F₂ соответственно. Рассмотрим унарную функцию j(<x,y>), определённую на L₁´L₂, которая принимает значение <T₁,T₂> тогда и только тогда, когда x=T₁ и y=T₂, а во всех других случаях она принимает <F₁,F₂>.

Предположим противное, пусть существует такая система функций {j₁,…, j_k}, что j представима их композицией. Тогда, согласно лемме 3.4, существуют такие j₁^*,j₂^*, что j (<x,y>) = <j₁^*,j₂^*>. Из определения j вытекает: j₁^*(T₁) = T₁, j₂^*(F₂) = F₂. Следовательно, j (<T₁,F₂>) = <T₁,F₁> С другой стороны, согласно определению, j<T₁,F₂>) = <F₁,F₂>. Следовательно, допущение неверно и лемма доказана.

Итак, система функций диалогового произведения не является функционально полной: не хватает «смешивающих», не дистрибутивных относительно L₁´L₂ операций, результат которых не может быть декомпозирован на базовые логики. Примером такой функции может служить операция возражения (₂ вL_min). Если в формулу входит такая операция, то, очевидно, ее вывод нельзя будет основывать на выводе в базовых логиках.

Определение 3.27. Выбранными истинностными значениями многозначной логики L назовем два произвольно выбранных значения T и F таких, что T ¹ F.

Определение 3.28. Обобщенной операцией «и» назовем произвольную операцию Ù такую, что для любых X Î L выполняется: T Ù X = X, F Ù X = F.

Определение 3.29. Обобщенной операцией «или» назовем произвольную операцию Ú такую, что для любых X Î L выполняется: T Ú X = T, F Ú X = X.

Определение 3.30. Пусть существуют многомерные логики L₁ и L₂. Пусть на обеих логиках определены выбранные истинностные значения: на L₁ - T₁ и F₁, на L₂ - T₂ и F₂, соответственно. Операцией смешивания назовем такую операцию &: L₁´L₂® L₁´L₂, что

&(<x,y>) = <T₁,T₂> если x=T₁ и y=T₂,

<F₁,F₂> если x¹T₁ или y¹T₂ (в противном случае).

Теорема 3.2. Пусть существует система функций W, которая является базисом диалогового произведения конечнозначных логик L₁°L₂, тогда W È{&} будет являться функционально полной системой операций определенных на L₁´L₂.

Доказательство. Докажем теорему сперва для унарных операций. Пусть существует произвольная функция y(<x,y>), докажем что ее можно построить путем композиции функций из W È{&}. Рассмотрим произвольные значения x=x_i, y=y_j. При помощи композиции функций из W можно построить следующие дистрибутивные относительно декартова произведения логик функции:

j₁ⁱ(<x,y>) = <T₁,F₂>, если x=x_i j₂ ^j(<x,y>) = <F₁,T₂>, если y=y_j

<F₁,F₂>, если x¹х_i <F₁,F₂>, если y¹y_j

Функции j₁ⁱ и j₂^j дистрибутивны относительно L₁´L₂ так как представимы в виде j₁ⁱ(<x,y>) = <j₁^i*(x),F₂> и j₂^j(<x,y>) = <F₁,j₂^j*(y)>, где j₁^j*(x), j₂^j*(y) – характеристические функции соответствующих логик.

Выберем функции, являющиеся обобщенными операциями «и» и «или»:

<x₁,y₁>Ù<x₂,y₂> = <x₁Ùx₂,y₁Ùy₂>

<x₁,y₁> Ú <x₂,y₂> = <x₁ Ú x₂,y₁ Ú y₂>

Рассмотрим функцию j_<xi,yj>(<x,y>) = j₁ⁱ(<x,y>)&j₂^j(<x,y>). Эта функция принимает значение <T₁,T₂>, если x=x_i и y=y_j, и значение <F₁,F₂> во всех остальных случаях. Теперь построим

y^*(x,y) = Ú_{" <x0,y0>ÎL1xL2}(j_<x0,y0>(<x,y>)Ù<x₀,y₀>).

Функция y^*(x,y) совпадает с y(x,y) при любых <x₀,y₀> Î L₁ x L₂

Теорема доказана для унарных функций.

Пусть теперь теорема выполняется для n-арных функций, требуется доказать, что она справедлива для n+1-арных функций.

Рассмотрим произвольную функцию y(x₁,x₂,…x_n,x_n+1). Согласно индуктивному допущению функция y(x₁,x₂,…x_n,<x₀,y₀>) выразима при помощи композиции операций из W È{&} для любых <x₀,y₀> Î L₁ x L₂, то есть существует формула F_<x0,y0>, такая что y(x₁,x₂,…x_n, <x₀,y₀>) представима в виде F_<x0,y0>.

y(x₁,x₂,…x_n,x_n+1) = Ú _DÎL1´L2 (F_<x0,y0>Ùj_<x0,y0> ), где j_<x0,y0> строится также как и в случае для унарных функций.

Теорема доказана.

Итак, добавление единственной смешивающей функции & к множеству функций, дистрибутивных относительно декартова произведения логик, позволяет строить произвольные логические функции на множестве L₁´L₂.

Определение 3.31. Полным диалоговым произведением L₁ÄL₂ логик L₁ и L₂ назовём следующее отображение

Ä:(L₁,{j₁,…, j_n},T₁)´(L₂,{y₁,…,y_m},T₂) ® (L₁´L₂,{j₁^*,…,j_k^*}È{&},T₁´T₂), такое что {j₁^*,…,j_k^*} – базис для функций, дистрибутивных относительно L₁´L₂.

Как осуществить вывод в L₁ÄL₂? Решить проблему построения вывода для полного диалогового произведения логик поможет метод комбинированного вывода на базе аналитических таблиц.

Для построения комбинированного вывода на полном диалоговом произведении логик необходимы: правила табличного вывода для базовых логик и специальные правила вывода для “&”. Также, с целью повышения удобства, возможно использование дополнительных правил вывода для других не дистрибутивных относительно произведения логик связок.

Процедура построения аналитической таблицы для формулы F в L₁ Ä L₂.

1. Индексируем все k вхождений связки & в формулу F. После чего, в F будут встречаться &₁, &₂,…&_k ровно по одному разу.

2. Представим формулу покоординатно в виде <F₁,F₂>. Для этого все дистрибутивные относительно Ä связки *(X₁,X₂,…,X_n) расписываем в виде <*₁(X₁,X₂,…,X_n), *₂(X₁,X₂,…,X_n)>, где *₁,*₂ – соответствующее дистрибутивное представление; а недистрибутивные связки &_i(X) просто заменяем <&_i(X), &_i(X)>.

3. Строим деревья вывода по методу аналитических таблиц для обеих частей получившегося кортежа, для всех вариантов означивания <D₁,D₂><F₁,F₂>. При этом для связок &_i применяем следующие правила (см. рис 3.6).

T&X		D&X		F&X
T&x		х		F& x	F& x	F& x^*
T&^*x				FX	DX	TX
TX

Рис 3.6. Специальные табличные правила для операции смешивания &; последнее правило включает ветви для всех D ¹ F, D ¹ T; х – означает, что ветвь замкнута.

Определение 3.32. Деревья вывода D₁F₁ и D₂F₂, считаются сопряженными, если проверяемая означенная формула есть <D₁,D₂>F. Две ветви сопряженных деревьев считаются сопрягаемыми, если для каждого вхождения D¹_j&_i^* в одну из ветвей, не существует вхождения D²_j&_i в другую ветвь, такого что D¹_j¹D²_j

4. После построения деревьев вывода для всех возможных вариантов означивания выполняем следующую процедуру:

4.1. Для всех открытых ветвей ищем сопрягаемые им открытые ветви.

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

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

5. Если деревья вывода замкнуты для всех вариантов означивания, кроме одного, то формула всегда принимает значения в соответствии с этим вариантом.

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

Теорема 3.3 Формула F может принимать значение <D₁,D₂> тогда и только тогда, когда в деревьях вывода D₁F₁ и D₂F₂ существуют сопрягаемые открытые ветви. F₁ и F₁ построены в соответствии с приведённым выше алгоритмом.

Доказательство. Необходимость. Пусть формула F может принимать значение <D₁,D₂>, т.е. существует такой сетап s₁, что s₁(F) = <D₁,D₂>.

Рассмотрим сетап s₁. В соответствии с методом аналитических таблиц для многозначной логики, этому сетапу должна соответствовать пара открытых ветвей деревьев D₁F₁ иD₂F₂. Допустим противное, они не сопрягаемы, т.е. существует вхождение D¹_j&_i^* в одну из ветвей, и существует вхождение D²_j&_i в другую ветвь, такое что D¹_j¹D²_j. Это означает что для j-того вхождения символа & интерпретация подформулы F, к которой применяется этот символ, есть D²_j. В силу табличного правила для &, это невозможно, так как тогда не будет достигнуто требуемое значение D¹_j. Получили противоречие, следовательно необходимость доказана.

Достаточность. Рассмотрим пару открытых сопрягаемых ветвей D₁F₁ и D₂F₂. Выписав все атомарные литеры, входящие в эти ветви, получаем их частичную интерпретацию. Выберем произвольную интерпретацию оставшихся атомарных литер. Получим сетап s₁, s₁(F) = <D₁,D₂>. Теорема доказана.

Как уже было отмечено, несмотря на то, что операция & является достаточной для перехода к полной системе функций, использование также и других недистрибутивных относительно произведения логик операций может упростить построение и вывод формул в таких логиках. В связи с этим, в методе комбинированного табличного вывода возможно использование специальных правил и для других вариантов недистрибутивных связок. В качестве примера рассмотрим связку Ø_&, представляющую собой обобщённое возражение. Пусть дано диалоговое произведение двух одинаковых логик LÄL. Операция Ø_& определяется следующим образом: Ø_&<x,y> = <y,x>. Пусть для определённости L = {T,F,I}, тогда специальные правила вывода для Ø_& будут выглядеть так:

TØ&X		FØ&X		IØ&X
TØ&x	FØ&x	IØ&x		TØ&x	FØ&x	IØ&x		TØ&x	FØ&x	IØ&x
TØ&^*x	TØ&^*x	TØ&^*x		FØ&^*x	FØ&^*x	FØ&^*x		FØ&^*x	FØ&^*x	FØ&^*x
TX	FX	IX		TX	FX	IX		TX	FX	IX

Рис 3.7. Специальные табличные правила для операции возражения Ø_&.

В завершении параграфа, отметим еще один момент, связанный с операцией диалогового произведения логик. Несмотря на то, что эта операция является бинарной, она весьма легко обобщается на случай конечного числа аргументов, а именно: Ä_n(L₁,L₂,…,L_n) = L₁ÄL₂Ä…ÄL_n. Это позволяет рассматривать и описывать диалоги не только между двумя, но также и любым другим конечным числом агентов-участников.

3.5. Модализированные логики диалога

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

В [15],[16] показана связь модальностей и интенциональных характеристик агентов, а также разработана модель, позволяющая описывать модальные характеристики высказывания при помощи аппарата многозначных логик.

Это представление удобным образом укладывается в систему многозначных диалоговых логик. Для формирования модальных диалоговых логик можно использовать произведение модальных логик контрагентов.

Рассмотрим примеры таких логик (см. рис. 3.8)

àF  

ÿT  

ÿF

àT  

T

F

T

F

N

(V, T)

(V, F)

(Y, F)

(Y, T)

(Y, N)

(W, T)

(W, N)

(W, F)

(V, N)

(a)

(б)

(в)

(г)

(д)

(V, T)

(Y, T)

(Y, N)

(V, N)

(V, F)

(Y, F)

Рис 3.8 Примеры модальных (многозначных) логик агентов-участников диалога: a-двузначная, а-трёхзначная, б-четырёхзначная, в-шестизначная, г-девятизначная, д-бесконечнозначная (нечёткая)

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

Рассмотрим еще один пример такой логики, восьмизначную логику возможности. Множество ее истинностных значений представлено на следующем рисунке (3.9).

ÿF  

àF  

àT  

ÿT  

N  

U  

R  

B  

Рис 3.9 Восьмизначная логика возможности L_p8.

Рассмотрим интерпретацию истинностных значений.

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

Значение	Интерпретация
N	Полная неопределённость: «ничего неизвестно»
B	Полное противоречие: «необходима и истина и ложь одновременно»
àF	Потенциальная ложь: «возможна ложь»
àT	Потенциальная истина: «возможна истина»
ÿF	Однозначная ложь: «необходима ложь»
ÿT	Однозначная истина: «необходима истина»
U	Неопределённость: «возможна как истина, так и ложь»
R	Бивалентность: «либо всегда истина, либо всегда ложь»

Кроме описания модальности логика L_p8 обладает еще одним достоинством. Она позволяет описывать простые квантифицируемые значения на основе многозначности. Введем следующее определение.

Пусть имеем некоторое множество единичных сетапов W. Рассмотрим предикат P(x), где x Î W. Агент A может обладать следующими знаниями относительно значения предиката P(x):

Нет никакой информации – запишем P = N,

$xP(x)=F – запишем P = àF,

$xP(x)=T – запишем P = àT,

"xP(x)=F – запишем P = ÿF,

"xP(x)=T – запишем P = ÿT,

$x$y(P(x)=T)&(P(y)=F) – запишем P = U,

("xP(x)=T)Ú("yP(y)=F) – запишем P = R,

("xP(x)=T)&("yP(y)=F) – запишем P = B.

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

В силу того, что L_p8 является решёткой, возможна дефиниция операций дизъюнкции и конъюнкции как взятия наибольшей нижней и наименьшей верхней граней, соответственно. Операцию отрицания определим следующим образом:

Таблица 3.12 Операция отрицания в логике L_p8

Х	Х	X	X
N	B	ÿF	àT
B	N	ÿT	àF
àF	ÿT	U	R
àT	ÿF	R	U

Обратим внимание, что семантика операции строго сохраняется при переходе к форме с кванторами:

$xP(x)="xP(x): àT = ÿF,àF = ÿT

"xP(x)= $xP(x): ÿT = àF, ÿF = àT

$x$y(P(x)&P(y)) = "x"y(P(x)ÚP(y)): U = R

("xP(x)Ú"yP(y)) = $x$y (P(x)&P(y)): R = U

Определим множество формул логики первого порядка, сводимых к исчислению L_p8. Очевидно, что любая формула логики предикатов первого порядка представима в L_p8, если все кванторы стоят непосредственно перед предикатами, в этом случае можно переобозначить:

$xP(x) Þ Р Î {àF, àT, ÿF, ÿT}

"xP(x) Þ Р Î {ÿF, ÿT}

Пусть Q_1…Q_n Î {$,"} - кванторы

Q₁x₁Q₂x_2…Q_nx_nP(x₁,x₂,…,x_n) Þ РÎ {àF, àT, ÿF, ÿT}, если $Q_i = $, iÎ1…n

Q₁x₁Q₂x_2…Q_nx_nP(x₁,x₂,…,x_n) Þ РÎ {ÿF, ÿT}, если "Q_i = ", iÎ1…n

Далее простой перебор возможных значений переменных, образованных из предикатов, позволяет определить общезначимость формулы (ÿT), тождественную ложность (ÿF), выполнимость (àT) и пр.

Определение 3.33. Назовем ППФ логики предикатов первого порядка сводимой к L_p8, если возможна описанная выше проверка.

В любой ППФ логики первого порядка возможно внесение кванторов по следующим правилам:

Qx(P(x)ÚQ) = QxP(x)ÚQ (3.27)

Qx(P(x)&Q) = QxP(x)&Q (3.28)

Q₁xQ₂y (P(x)ÚQ(y)) = Q₁xP(x)ÚQ₂xQ(x) (3.29)

$x(P(x)ÚQ(x)) = $xP(x)Ú$xQ(x) (3.30)

"x(P(x)&Q(x)) = "xP(x)&"xQ(x) (3.31)

где Q,Q₁,Q₂ Î {$,"} – кванторы

С другой стороны внесение кванторов невозможно в следующих случаях:

$x(P(x) &Q(x)) ¹ $xP(x)&$xQ(x) (3.32)

"x(P(x)ÚQ(x)) ¹ "xP(x)Ú"xQ(x) (3.33)

Соответственно, несводимые к L_p8 ППФ это такие формулы, в которых встречаются указанные выше выражения.

Основное преимущество L_p8 раскрывается при использовании в автономном агенте. Пусть существует набор фактов d₁,d₂,…,d_n, где d_i = (P_i(a_j) = D_i), где D_i Î {T,F}. Изначально всем переменным среды p₁,p₂,...,p_n устанавливается значение N, при поступлении факта d_i, переменная p_i, соответствующая предикату P_i принимает значение àF, если D_i = F, или àT в противном случае. Также существует набор достоверных знаний b₁, b₂,…,b_n, где b_i = (p_i = L_i), где L_i Î {N,B,àT,àF,ÿF,ÿT,U,R}, эти знания могут быть получены из надёжных источников, заданы первоначально или получены в результате вывода. При поступлении b_i, p_i устанавливается в L_i.

Определим операции конъюнкции и дизъюнкции как взятие точной верхней и нижней граней соответственно, на их основании определим импликацию материально.

Таблица 3.13 Операция конъюнкции в логике L_p8

хÙy	N	àF	àT	R	ÿF	ÿT	U	B
N	N	àF	àT	R	ÿF	ÿT	U	B
àF	àF	àF	U	ÿF	ÿF	B	U	B
àT	àT	U	àT	ÿT	B	ÿT	U	B
R	R	ÿF	ÿT	R	ÿF	ÿT	B	B
ÿF	ÿF	ÿF	B	ÿF	ÿF	B	B	B
ÿT	ÿT	B	ÿT	ÿT	B	ÿT	B	B
U	U	U	U	B	B	B	U	B
B	B	B	B	B	B	B	B	B

Таблица 3.14 Операция дизъюнкции в логике L_p8

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