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

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

Л. Ю. Девяткин

abstract. In this paper a number of functional properties of implicative-negative three-valued logical matrices with the classical cosequence relation is described.

Ключевые слова: классическая пропозициональная логика, трехзначная логика, отношение логического следования, логические матрицы

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

Дадим ряд необходимых определений.

ОПРЕДЕЛЕНИЕ 1 (Алфавит пропозиционального языка LD-). Алфавиту пропозиционального языка LD- принадлежат только следующие символы: бинарная логическая связка D, унарная логическая связка пропозициональные переменные pi,p2, p3,..., а также скобки.

ОПРЕДЕЛЕНИЕ 2 (L^-формула). Каждая пропозициональная переменная pi есть L^-.-формула. Если A — L^-.-формула, то —A есть L^-формула. Если A и B — L^-формулы, то A D B есть L^-формула. Ничто иное не L^-формула.

ОПРЕДЕЛЕНИЕ 3 (Логическая матрица). Будем называть логической матрицей M = (U, F, D), где U — непустое множество, D — непустое подмножество U, интерпретируемое как множество выделенных значений, F — множество операций, заданных на U.

Если не указано иное, будем рассматривать матрицы, в которых множество F содержит в точности одну бинарную и одну унарную базовые операции.

ОПРЕДЕЛЕНИЕ 4 (Оценка L^-формулы в M). Оценку v произвольной L^-формулы A в M (символически — \A\M) определим обычным образом: \p\M € U, если p есть пропозициональная переменная; если A и B есть L^-формулы, а ^ и ~ есть соответственно бинарная и унарная базовые операции M, то \A Э B\M = \A\M ^ \B\M, \—A\M =~\A\M.

ОПРЕДЕЛЕНИЕ 5 (Логический закон). LD--формула A является законом в логической матрице M, е.т.е. \A\M € D при каждой оценке v в M.

ОПРЕДЕЛЕНИЕ 6 (Отношение логического следования). LD--формула B логически следует из множества посылок Г в M (символически Г \=m B), е.т.е. не существует оценки v в M, при которой все формулы из Г принимают выделенное значение, а формула B принимает невыделенное значение.

ОПРЕДЕЛЕНИЕ 7 (Классическое отношение логического следования в M). Пусть логическая матрица M2 = ({1, 0}, Э+, —+, {1}) есть матрица для классической пропозициональной логики, а Э+ и —+ определяются стандартными таблицами истинности для импликации и отрицания. Пусть M3 = ({1,1, 0}, Э*, —*, {1}) есть произвольная матрица с трехэлементным множеством-носителем, на котором заданы одна бинарная и одна унарная базовые операции. Будем говорить, что отношение логического следования в M3 является классическим, если и только если выполняется следующе условие: Г =m2 B, е.т.е. Г =m3 B.

Можно доказать следующую теорему [2]:

ТЕОРЕМА 1. Отношение логического следования в M3 является классическим, только когда базовые связки M3 отвечают следующим условиям: x Э* y = 1, е.т.е. x € {1, 0} или y = 1, в противном случае x Э* y € {1, 0}; *x = 1, е.т.е. x € {|, 0}, в противном случае —*x € {1, 0}.

Существует восемь наборов связок, отвечающих данному условию:

1 2 0

1 1 2 0 1 0 0 1 1 1 1 1 1

-€

1 1 2 0 0 1 1

эв 1 2 0

1 1 2 0 1 2 0 1 1 1 1 1 1

-€

1 1 2 0 0 1 1

э7 1 2 0

1 1 2 0 1 0 2 1 1 1 1 1 1

€ —1

1 1 2 0 0 1 1

э6 1 2 0

1 1 2 0 1 1 1 1 2 2 1 1 1 1 1 1

€ —1

1 1 2 0 0 1 1

1 2 0

1 1 2 0 1 0 0 1 1 1 1 1 1

-ф

1 1 2 0 1 2 1 1

эв 1 2 0

1 1 2 0 1 2 0 1 1 1 1 1 1

-ф

1 1 2 0 1 2 1 1

э7 1 2 0

1 1 2 0 1 0 2 1 1 1 1 1 1

-ф

1 1 2 0 1 2 1 1

э6 1 2 0

1 1 2 0 1 1 1 1 2 2 1 1 1 1 1 1

-ф

1 1 2 0 1 2 1 1

Таким образом, может быть построено восемь логических матриц с трехэлементным множеством-носителем, в которых отношение логического следования является классическим. Обозначим их соответственно как ммв'€, м37'€, м6/, мв'ф, М^'ф, М3'ф. Некоторые из перечисленных связок достаточно известны. Так, первый набор связок — это внешние импликаци и отрицание трехзначной логики Бочвара В3 [1]. Связка эв была независимо описана в целом ряде работ [4, 5, 6].

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

УТВЕРЖДЕНИЕ 1. Используя базовые операции М^'€ и М6'ф, нельзя выразить никакие иные из описанных нами связок.

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

УТВЕРЖДЕНИЕ 2. В ыЦ'е выразимы связки Ы3' и не выразимы базовые связки остальных матриц.

Доказательство. Импликация из Ы3*'€ выражается следующим образом: х Эа у = —е—е(х Эв у). В то же время все функции Ыв'е имеют область значений {1, 0} при ограничении значений переменных тем же множеством. Однако это неверно для остальных матриц. д.Е.Б.

УТВЕРЖДЕНИЕ 3. В Ыв'ф выразимы связки и не выразимы базовые связки остальных матриц.

Доказательство. Импликация из выражается аналогично предыдущему случаю: х Эг у = —ф—ф(х Эв у).

Покажем, что через базовые операции Ыв'ф нельзя выразить унарный оператор f1, такой, что f :(1) = 0.

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

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

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

Случай 2. д(х) = Н'(х) Эв Н''(х).

1. Н'

2. Н'

3. Н''(1) = 0. Число вхождений Эв и в Н'' меньше к. противоречие с индуктивным допущением.

Индукция закончена. Оператор f1 невыразим в Ыв'ф. Однако этот оператор выразим в остальных матрицах: х Эа —фх для ыаф, х Э1 —фх для Ы™, —ех для остальных матриц.

д.Е.Б.

УТВЕРЖДЕНИЕ 4. Ы^'е функционально эквивалентна . В этих матрицах выразимы базовые операции и и

не выразимы базовые операции ыв'е, Ыв'ф, Ы™ и Ы1'ф.

Доказательство. Функциональная эквивалентность Mи M'a'ф и выразимость базовых операций M£'е и М^'ф:

• x Da y = —e—e(x y);

• —фх = x —ex;

• x Ds y = —v—v(x Da y);

• —Êx = x Da —фx.

Теперь покажем, что через базовые операции нельзя выразить унарный оператор f1, такой, что f 1(2) = f 1(0), содерже-щий не меньше одного вхождения базовой операции.

Индуктивное допущение. Пусть f1 нельзя выразить в используя менее к (к > 1) вхождений D и —е.

Допустим, что f1 можно выразить посредством суперпозиции g операций D и —е, содержащей в точности к вхождений данных операций.

Случай 1. Пусть g

1. —eh

2. h

3. Пусть h

4. —е 1 = —е0

5. — 2 = —е0

6. h

7. h

8. —€h

9. Неверно, что g

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

1. h'

2. Ь'

3. Ь''

4. Пусть Ь'

5. 2 э6 1 = 0 э6 0

6. 2 э6 1 = 0 э6 0

7. Неверно, что Ь'

8. Пусть Ь'(ж) содержит I вхождений и Ь''(ж) содержит т вхождений базовых операций.

9. Ь'

10. Ь''

11. Ь'

12. Неверно, что Ь'(ж) содержит I вхождений и Ь''(ж) содержит т вхождений базовых операций (из 1, 11).

13. Пусть Ь'

14. Ь'

15. Ь'

16. Пусть Ь'

17. Ь'

18. Ь'

19. Ь'

20. Неверно, что Ь'

21. Ь

22. Ь

23. Ь

24. Ь

25. Неверно, что Ь'

26. Пусть Ь

27. 2 3й Ь'( 1) = 1 и 0 3й Ь''(0) = 1, или 2 3й Ь"( 1) = 1 и 0 3й Ь''(0) = 1 (из 26 по определению 3й). Однако это невозможно в силу определения 3й.

28. Неверно, что Ь'

29. Неверно, что д

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

Однако такой оператор выразим в ыв'е, Ыв'ф, Ы™ (х 3е х) 3е х, (х 31 х) 31 х. д.Е.Б.

УТВЕРЖДЕНИЕ 5. функционально эквивалентна .

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

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

• —фх = х 31 —ех

• —ех = х 31 —фх

• х 3в у = х 37

• х 3й у = -ф-ф

д.Е.Б.

Обобщая доказанные утверждения, можно заключить, что между матрицами Ма'€, М^'€, М^'€, М6'€, М3а'ф, мвв'ф, М^'ф, м3'ф имеет место порядок по отношению выразимости базовых связок. Причем, М3^'€ и функционально эквивалентная ей М3,'ф выступают в роли максимума, М3а'€ и М3,)'ф есть несравнимые минимумы, а и М6' , функционально эквивалент-

ная М3а'ф представляют собой три несравнимых промежуточных элемента.

УТВЕРЖДЕНИЕ 6. Набор базовых операций М^'€ не является функционально полным в Р3.

Доказательство. Покажем, что через операции -€ и э1 невыразим унарный оператор / 1(ж), такой что /1( 1) = 1 и /1(0) = 0.

Индуктивное допущение. Пусть /1 нельзя выразить в М3^'€, используя менее к вхождений э1 и -€.

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

Случай 1. Пусть д

1. -€Ь

2. Ь

3. Ь

4. Пусть Ь

5. -Ъ*

6. Ь*(1) = 1 и Ь*(0) = 0 (из 5 по определеню -е). Однако это противоречит индуктивному допущению. Следовательно, неверно, что Ь(ж) имеет вид -Ь*(ж).

7. Ь

8. Ь'

9. Ь'

10. Ь

11. Пусть Ь'

12. -е-еЬ'

13. -е-еЬ'

14. -е-еЬ'

15. Ь

16. -еЬ''

17. -еЬ''

18. -еЬ''

Случай 2. Пусть д

1. Ь'

2. Ь'

3. Ь'

4. Пусть Ь'

5. —еЬ'

6. —еЬ'

7. '

8. Ь''

9. —е—еЬ''

10. —€—€Ь"

11. —е—еЬ''(х) содержит т(т < к) операций. Однако это противоречит индуктивному допущению и Случаю 1 настоящего доказательства.

Таким образом, набор базовых операций не является функционально полным в Рз. Q.Е.D.

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

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

• Идемпотентность: х V х = х, х Л х = х;

• Коммутативность: х V у = у V х, х Л у = у Л х;

• Ассоциативность: х V (у V г) = (х V у) V г, х Л (у Л г) = (х Л у) Л г;

• Поглощение: х V (х Л у) = х, х Л (х V у) = х.

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

х V у = —х Э у.

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

V1 1 2 0

1 1 2 0 1 1 1 1 0 0 1 0 0

V2 1 2 0

1 1 2 0 1 1 1 1 2 0 1 2 0

V3 1 2 0

1 1 2 0 1 1 1 1 0 2 1 0 2

V4 1 2 0

1 1 2 0 1 1 1 1 1 1 1 2 2 1 1 1 1 2 2

Операции V1 сответствуют Ы^'^ и Ы^'^. Операции V2 сответ-ствуют Ыв'€ и Ыв'ф. Операции V3 сответствуют Ы^'€ и . Операции V4 сответствуют Ы3'е и Ы3'ф.

Теперь определим конъюнкцию через ипликацию и отрицание:

х Л у = —(х Э —у). В зависимости от выбранных — и Э возможны два варианта.

Л1 1 2 0

1 1 2 0 1 0 0 0 0 0 0 0 0

Операции Л1 соответствуют Л2 соответствуют Ы£'ф, Ыв'ф,

Л2 1 2 0

1 1 2 0 1 1 1 1 2 2 1 1 1 2 2 2 1 1 1 2 2 2

г«'£, Ыв'е, Операции

мГ Mt

x V x = x — + — —

x Л x = x — — — —

x V y = y V x + — — +

x Л y = y Л x + + + +

x V (y V z) = (x V y) V z + + — +

x Л (y Л z) = (x Л y) Л z + + + +

x V (x Л y) = x — — — —

x Л (x V y) = x — — — —

м1'ф

x V x = x — + — —

x Л x = x — — — —

x V y = y V x + — — +

x Л y = y Л x + + + +

x V (y V z) = (x V y) V z + + — +

x Л (y Л z) = (x Л y) Л z + + + +

x V (x Л y) = x — — — —

x Л (x V y) = x — — — —

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

Литература

[1] Бочвар Д.А. Об одном трехзначном исчислении и его применении к анализу парадоксов классического расширенного функционального исчисления // Математический сборник. Т. 4, № 2. 1938. C. 287-308.

[2] Девяткин Л.Ю. Многозначные изоморфы классической пропозициональной логики. Кандидатская диссертация на соискание ученой степени кандидата философских наук. М., 2008. C. 29.

[3] Мендельсон Э. Введение в математическую логику. М., 1984. С. 33.

[4] Avron A. Natural 3-valued logics — characterization and proof theory // The Journal of Symbolic Logic. Vol. 56. № 1. P. 276-294.

[5] Monteiro A. Construction des algebres de Lukasiewicz trivalentes dans les algebres de Boole monadiques, I // Mathematica Japonica. Vol. 12. P. 1-23.

[6] Slupecki J., Bryl J. and Prucnal T. Some remarks on the three-valued logic of J. Jukasiewicz // Studia Logica. Vol. 21. P. 45-70.