О некоторых функциональных свойствах матриц с классическим отношением логического следования

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

Утверждение 1.

Пусть MJ3 (j Е {1, 2}) - импликативно-негативная трехэлементная матрица, где j - число элементов класса выделенных значений D. Отношение логического следования в MJ3 является классическим, если и только если её базовые операции отвечают следующим условиям:

х D3y (Ё D е.т.е х Е D и уD;

х D е.т.е х Е D.

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

Подсчитаем число возможных табличных определений Э3, отвечающих условию Теоремы 3.

Пусть v - оценка в М3. Всего существует 9 оценок у , отличающихся от v лишь значениями х и у. Так как х D3y D е.т.е х D и у Е D, число оценок у., при которых А' Э, v D, определяется следующей формулой: к х (3 - к). В силу Теоремы 3, это число всегда равно 2. Остается 7 оценок v. При каждой из них х D3y Е D.

Подсчитаем число возможных определений бинарных операций, заданных на {1, /г, 0} таких, что формула D q) не принимает выделенного значения лишь при двух v. Это число равняется (3 - к)2.

Теперь подсчитаем число возможных определений бинарных операций, заданных на {1, !4, 0} таких, что формула D q) принимает выделенное значение при семи различных v. Это число равняется к.

Таким образом, общее число определений бинарных операций, заданных на {1, !4, 0}, удовлетворяющих условию Теоремы 3, составляет к х (3 - к)2.

Проведем аналогичное построение для подсчета числа соответствующих табличных определений -у -уг D при к оценках v. Существует (3 - к)к соответствующих табличных определений, Е D при (3 - к) оценках v. Существует к2~к} соответствующих табличных определений. Всего существует (3 - к)к х к2~к} табличных определений унарных операций, заданных на {1, !4,0}, удовлетворяющих условию Теоремы 3. В силу Теоремы 3, это число всегда равно 2.

Теперь мы можем найти число возможных комбинаций табличных определений для бинарной и унарной операции, заданных на {1, !4, 0} и удовлетворяющих условию Теоремы 3. Это число равно 2 х х (3 - к)2).

В соответствии с полученной формулой, число трехэлементных матриц с одной бинарной и одной унарной базовой операцией таких, в которых классы формул, находящихся в отношении логического следования и классы общезначимых в данной матрице формул совпадают с классическими, составляет 8 и 256 для, соответственно, одного и двух выделенных значений. Из них 2 С-расширяющих для одного выделенного значения и 16 - для двух.

Наборы базовых операций для матриц с одним выделенным значением принимают следующий вид:

?а

1

Уг

0

-1®

1

Уг

0

-Iе

1

1

0

0

1

0

1

1

Уг

0

1

0

Уг

1

1

1

Уг

1

Уг

1

1

1

Уг

1

0

1

1

1

0

1

0

1

1

1

0

1

dy

1

Уг

0

D6

1

Уг

0

_,8

1

1

0

Уг

1

0

1

1

Уг

Уг

1

0

Уг

1

1

1

Уг

1

Уг

1

1

1

Уг

1

0

1

1

1

0

1

0

1

1

1

0

1

1

Уг

0

-1<р

р'

1

Уг

0

-,

1

1

0

0

1

Уг

1

1

Уг

0

1

Уг

Уг

1

1

1

Уг

1

Уг

1

1

1

Уг

1

0

1

1

1

0

1

0

1

1

1

0

1

Р'

1

Уг

0

->Ф

D6

1

Уг

0

-|Ф

1

1

0

Уг

1

Уг

1

1

Уг

Уг

1

Уг

Уг

1

1

1

Уг

1

Уг

1

1

1

Уг

1

0

1

1

1

0

1

0

1

1

1

0

1

Обозначим соответствующие матрицы как МаЕ, МР'Е, М7-Е, М^Е, Ma-V, М™, М6’*. Некоторые из перечисленных связок достаточно известны. Так, первый набор связок - это внешние импликаци и отрицание трехзначной логики Бочвара В3 [4]. Связка Рр была независимо описана в целом ряде работ [17, 28, 33].

Как известно (см., например [9]), классические импликация и отрицание образуют функционально полную систему связок, то есть с их помощью может быть выражена любая функция, заданная на {1; 0}. Интересно, что в случае с приведенными выше наборами связок ситуация совершенно иная.

Утверждение 2.

Используя базовые операции М°-е и М6, нельзя выразить никакие иные из описанных нами связок.

Доказательство. Ясно, что любая функция, выразимая в данных матрицах, имеет область значения {1; 0} или {1; !4} соответственно. Однако это неверно для остальных матриц.

Утверждение 3.

В выразимы связки Ма-е , и не выразимы базовые связки остальных матриц.

Доказательство. Импликация из Мие выражается следующим образом: х у = ->Ее(х Эр у). В то же время, все функции М^е имеют область значений {1; 0} при ограничении зан-чений переменных тем же множеством. Однако это неверно для остальных матриц.

Утверждение 4.

В выразимы связки Л/**, и не выразимы базовые связки остальных матриц.

Импликация из №•* выражается аналогично предыдущему случаю:

хЭ5у= -ф-ф(хЭру).

Теперь покажем, что через базовые операции нельзя выразить унарный оператор/, такой, что/(1) = 0.

Индуктивное допущение. Пусть/ нельзя выразить в используя менее к вхождений Эр и ->ф.

Теперь допустим, что/ можно выразить посредством суперпозиции g операций Эр и --ф, содержащей в точности к вхождений данных операций.

Случай 1. g(x) = ->фЛ(х). Тогда —• ФА( 1) = 0. Однако это невозможно в силу определения ->ф.

Случай 2. g(x) = h'(x) Dp h"(x).

  • (1) Л'(1) Э? h”(l) = 0 (по условию).
  • (2) Л'(1) = 1 и Л"(1) = 0 (по определению Эр).
  • (3) h"(V) = 0. Число вхождений Эр и --ф в h" меньше к. Противоречие с индуктивным допущением.

Индукция закончена. Оператор / не выразим в ММ. Однако этот оператор выразим в остальных матрицах: xZ)“ ->фх для xDy -,x для М79, ->Ех для остальных матриц.

Утверждение 5.

М8* функционально эквивалентна Ма-9. В этих матрицах выразимы базовые операции Ма-Е и М8-9, но не выразимы базовые операции, М^, Му-е, М^9, М7'9.

Доказательство. Функциональная эквивалентность М8>Е и Ма9, а также выразимость базовых операций М°-Е и ММ

х Z)ay = ->е-'е (х Э5у);

->фх = х D5 ->?х;

_XD8y= -Ф-Ф(хЗ“у);

-?х = хЭа ->фх.

Теперь покажем, что через базовые операции М8>: нельзя выразить унарный оператор/, такой, что/(!/г) ^/(0), содержащий не меньше одного вхождения базовой операции.

Индуктивное допущение. Пусть/ нельзя выразить в M8s, используя менее к {к > 1) вхождений D8 и -<?.

Допустим, что/ можно выразить посредством суперпозиции g операций Э8 и ->?, содержащей в точности к вхождений данных операций.

Случай 1. Пусть g(x) = --?/г(х)

  • (1) -’е/г(1/г) Ф --Л(О) (по условию).
  • (2) /?(х) содержит I (0 < I < к) вхождений базовых операций или Л(х) есть х (по условию).
  • (3) пусть h(x) есть х (допущение).
  • (4) -?1/2^?0 (из 1,3).
  • (5) ->?1/г = ->?0 (по определению -).
  • (6) Л(х) содержит / вхождений базовых операций (из 2-5).
  • (7) Л(!4) = Л(0) (из 6 по индуктивному допущению).
  • (8) -,?/г(!4) = ->?Л(0) (из 7 по определению ->?).
  • (9) неверно, что g(x) = ->Eh(x) (из 1, 8).

Случай 2. Пусть g(x) = h'(x) 3s h"(x).

  • (1) A'(!/2) 38 h"(y2) ± h$) 3s Л"(0) (по условию).
  • (2) h'(x) содержит I (0 < I < к) вхождений базовых операций или h'(x) есть х (по условию).
  • (3) h"(x) содержит т (0 < т < к) вхождений базовых операций или h"(x) есть х (по условию).
  • (4) пусть h'(x) есть х и h"(x) есть х (допущение).
  • (5) /2 З8 /2 # 0 З8 0 (из 1,4).
  • (6) У2 З8 У2 = 0 З8 0 (по определению З8).
  • (7) неверно, что h'(x) есть х и h"(x) есть х (из 5, 6).
  • (8) пусть h’(x) содержит Z вхождений и h"(x) содержит т вхождений базовых операций.
  • (9) h'(y2) = Л'(0) (из 8 по индуктивному допущению).
  • (10) h"(V2) = h"(0) (из 8 по индуктивному допущению).
  • (11) ^(УУ) З8 h''Q/У) = Л'(0) З8 Л"(0) (по определению З8).
  • (12) неверно, что h'(x) содержит I вхождений и h"(x) содержит т вхождений базовых операций (из 1, 11).
  • (13) пусть h'(x) содержит I вхождений базовых операций и h"(x) есть х (допущение).
  • (14) ЬУУ) З8 (УУ) # й'(0) З8 (0) (из 1,13).
  • (15) К(УУ) З8 (*/2) = У2 и й'(0) З8 (0) = 1, или кУУ) З8 (УУ) = 1 и Л'(0) З8 (0) = У2 (из 14 по определению З8).
  • (16) пусть Л'С/г) З8 (/г) = У2 и Л'(0) З8 (0) = 1 (допущение).
  • (17) К{УУ) = 1 (из 16 по определению З8).
  • (18) Л'(0) # 1 (из 16 по определению З8).
  • (19) ЬУУ) t h'(V) (из 17, 18).
  • (20) неверно, что НУУ) З8 (!4) = !4 и /г'(0) З8 (0) = 1 (из 19 и индуктивного допущения).
  • (21) ЪУУ) З8 2) = 1 и й'(0) З8 (0) = У2 (из 15, 20).
  • (22) AX1/2) 1 (из 21 по определению D8).
  • (23) Л'(0) = 1 (из 21 по определению D8).
  • (24) АХ*/2) ± (из 22, 23).
  • (25) неверно, что h'(x) содержит I вхождений базовых операций и h”(x) есть х (из 24 и индуктивного допущения).
  • (26) пусть h'(x) есть х и h"(x) содержит т вхождений базовых операций (допущение).
  • (27) /2 D8 А'Х'Л) = ‘Л и О D8 А"(0) = 1, или У2 D8 h"^ = 1 и О D8 А"(0) = (из 26 по определению Э8). Однако это невозможно в силу определения Z)8.
  • (28) неверно, что h'(x) есть х и h"(x) содержит т вхождений базовых операций (из 27).
  • (29) неверно, что g(x) = hx) D6 h"(x) (из 2, 3, 4, 12, 25, 28).

Таким образом, через базовые операции М6Е нельзя выразить унарный оператор/, такой, что/(1/г) //(0), содержащий не меньше одного вхождения базовой операции.

Однако такой оператор выразим в М^-Е, М7>Е, М^:

(х^х) D?x,(xD^x)D^x.

Утверждение 6.

МУЕ функционально эквивалентна М7,ч>. В этих матрицах также выразимы базовые связки всех остальных матриц.

Чтобы доказать данное утверждение достаточно следующих тождеств:

  • -><9х = х D7 ->Ех;
  • ->ех = х ->фх;

х^у = хТУ(-**уТУу) ;

хЭ8у= -ф-фТУ у).

Обобщая доказанные утверждения, можно заключить, что между матрицами МаЕ, №-Е, М7-Е, MSE, М^, Мм>, имеет место порядок по отношению выразимости базовых связок. Причём, М7'е и функционально эквивалентная ей М7-* выступают в роли максимума, и M5v есть несравнимые минимумы, а и Мд'Е,

функционально эквивалентная Mu-V представляют собой три несравнимых промежуточных элемента. Все это можно представить в виде следующей шестиэлементной решетки:

Му8

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

Однако, это означало бы, что класс тавтологий в Мул: не является классическим, что противоречит Утверждению 1.

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

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

Идемпотентность', х v х = х, х л х = х;

Коммутативность: х v у = у v х, х л у =у л х',

Ассоциативность', х v (у v z) = (х v у) v z, x л л z) = (х л у) л z;

Поглощение, х v (х л у) = х, х л (х v у) = х.

Так ли это для рассмотренных выше матриц? Выразим дизъюнкцию через импликацию и отрицание стандартным образом:

х v у = -‘х 3 у.

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

V1

1

Уг

0

V2

1

Уг

0

1

1

1

1

1

1

1

1

/2

1

0

0

Уг

1

Уг

0

0

1

0

0

0

1

Уг

0

V3

1

Уг

0

V4

1

Уг

0

1

1

1

1

1

1

1

1

/2

1

0

Уг

Уг

1

Уг

Уг

0

1

0

Уг

0

1

Уг

Уг

Операции v1 сответствует и Операции v2 сответству-ет №-е и ММ. Операции v3 сответствует М7'с и ММ Операции v4 сответствует Afг и ММ Теперь определим конъюнкцию через импликацию и отрицание:

хлу=-(хЗ-у).

В зависимости от выбранных -> и 3 возможны два варианта.

Л1

1

Уг

0

1

1

0

0

Уг

0

0

0

0

0

0

0

л2

1

Уг

0

1

1

Уг

Уг

Уг

Уг

Уг

Уг

0

Уг

Уг

Уг

Операция л1 соответствует Мае, ММ М7е, ММ Операция л2 соответствует ММ ММ, Мм ММ

мае

Ms-e

Ма^

X

V X = X

-

+

-

-

-

+

-

X

к х = х

-

-

-

-

-

-

-

X

v У = У v х

+

-

-

+

+

-

+

X

л у = у Л X

+

+

+

+

+

+

+ +

X

V V z) = (х V у) V

Z +

+

-

+

+

+

+

X

Л (у Л z) = (х Л у) л

Z +

+

+

+

+

+

+ +

X

V (х л у) = X

-

-

-

-

-

-

-

X

Л (х V у) = X

-

-

-

-

-

-

-

Таким образом, ни в одной из рассматриваемых матриц дизъюнкция и конъюнкция не обладают свойствами решеточ-

ных операторов.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >