Матрицы с двумя выделенными значениями

Определим отображение гр множества {1, 'Л, 0} на само себя следующим образом: гр! = {<1, !4>, , <0, 0>}. Пусть М23 - трехэлементная логическая матрица с двумя выделенными значениями. Будем обозначать посредством М23 матрицу, полученную из М2 заменой базовых операций М2 на следующие:

^=>п,Т = 'Ф1('Ф1(^)=>31(у))-

Теорема И.

Пусть М2 - трехэлементная логическая матрица и Г е.т.е. Г |=м В. Для каждого множества -формул Г, для каждой L3 -формулы В верно следующее: VAVv: если А -формула и v - оценка в М2, то v - оценка в М2^ и |А| = 0, е.т.е |А| v 3>* = 0.

В силу определения оценки, оценка в М2 есть отображение множества пропозициональных переменных языка на множество-носитель М2. Однако множества-носители М2 и М2^ совпадают. Следовательно, каждая оценка в М2 есть оценка в .

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

У1. VAVv: если |А| ^3 = 0, то |А| ^3,1р = 0;

У2. VAVv: если |А| = 0, то |А| ^3 = 0.

Докажем У1 индукцией по построению формулы.

Пусть У1 верно для формул, которые содержат менее, чем п вхождений связок. Тогда достаточно доказать, что У1 верно, если -формула А содержит в точности п вхождений связок и графически совпадает с формулой -,С либо с формулой DDE.

Случай 1. Пусть -формула А содержит в точности п вхождений связок и графически совпадает с формулой С.

  • (1) неверно, что У1 (допущение).
  • (2) 3(-C)3v: |_,С| f = 0 и |-С| / 0 (из (1)).
  • (3) пусть “'С* и у* - такие -формула и оценка, что |_,С*| = О и |_,С*|^3'4Ф 0 (из (2), исключение кванторов).
  • (4) |_,С*| Jf3 = 0 (из (3)).
  • (5) |С*| ^3 ± 0 (из (4) и того факта, что Г |= В, е.т.е. Г 1=^ В).
  • (6) |С*| v*3'4Ф 0 (из (5), по индуктивному допущению).

д/,2

  • (7) ф,|С*| 'ч’ Ф 0 (из (6), по определению ф]).
  • (8) -,3ф)|С*|^Здр = 0 (из (7) и того факта, что Г|=^2В, е.т.е. Г к в и -? есть базовая операция М).

.4/2

  • (9) ipj-yipJC*! v+,lp = О (из (8), по определению фД
  • (10) ф-3 ipjc*! = -JC*| (по определению ^).
  • (11) ЬС*|^ = 1(из(10), (9)).
  • (12) |-С*|^#1(из (3)).
  • (13) неверно, что (1) (из (12), (11)).

Случай 2. Пусть -формула А содержит в точности п вхождений связок и графически совпадает с формулой DDE. Докажем, что У1 выполняется для А.

  • (1) неверно, что У1 (допущение).
  • (2) 3(D D E)3v: |D D Е| = 0 и |D D E| ± 0 (из (1)).
  • (3) пусть D* D E* и v* - такие L -формула и оценка, что |D* D Е*| '/* = 0 и |D* D E*| ^3'40 (из (2), исключение кванторов).
  • (4) |D*DE*|"j! = 0(h3 (3)).
  • (5) |D*| / 0 и E*| Jf’ = 0 (из (4) и того факта, что Г |= у1 В, е.т.е. Г |=„2 В и D3 есть базовая операция М23).
  • (6) |D*| "гг0(из(5)).
  • (7) |D*| v*3',p # 0 (из (6), по индуктивному допущению).
  • (8) ipJD*| Jf3* Ф 0 (из (7), по определению грД
  • (9) |Е*|"’ = 0(из(5)).
  • (10) |Е*|^/3'4’ = 0 (из (9), по индуктивному допущению).
  • (11) гр1|Е*|^3,4’ = 0 (из (9), по определению гр Д
  • (12) гр1|В*| D3 гр1|Е*|^3,4’ = 0 (из (11), (8) и того факта, что

Г Им? В е те- Г В и D3 есть базовая операция ).

  • (13) гр1(гр1|В*| Э3 гр,|Е*| ^31’ ) = 0 (из (12), по определению гр^.
  • (14) |D*| Jf3’’1’ D^ |Е*| ^3'4’ = 0 (из (13), по определению Э^).
  • (15) |D* ?E*|^3,'t’= 0 (из (14), по определению значения -формулы).
  • (16) |D*DE*|"!* /0 (из (3)).
  • (17) неверно, что (1) (из (16), (15)).

У1 доказано.

Докажем У2 аналогичным образом. Пусть У2 верно для формул, которые содержат менее, чем п вхождений связок. Тогда достаточно доказать, что У2 верно, если -формула А содержит в точности п вхождений связок и графически совпадает с формулой -’С либо с формулой DDE.

Случай 1. Пусть L3 -формула А содержит в точности п вхождений связок и графически совпадает с формулой -1 С.

  • (1) неверно, что У1 (допущение).
  • (2) 3ec)3v: ГС|# 0 и ГС| = 0 (из (1)).
  • (3) пусть -,С* и v* - такие -формула и оценка, что |-€*| и3 ± 0 и |_,С*|^3,'Р = 0 (из (2), исключение кванторов).
  • (4) |^*| ^ 0 (из (3)).
  • (5) |С*| Jf3 = 0 (из (4) и того факта, что Г |=w. В, е.т.е. Г |= л/ В).

м2 3

  • (6) |С*| = 0 (из (5), по индуктивному допущению).
  • (7) ф1|С*| J**’’1’ = 0 (из (6), по определению ф^.
  • (8) -’3ф1|С*|^3'4Ф 0 (из (7) и того факта, что r^w2B, е.т.е. Г |= Л/ В и -’з есть базовая операция М).
  • (9) xp^ipJC*! Ф 0 (из (8), по определению ф^.
  • (10) ^Гз^11с*1 ?4' = (по определению -ф).
  • (11) ЬС*|^^0(из(10), (9)).
  • (12) |-€*|"’’ = 0(из(3)).
  • (13) неверно, что (1) (из (12), (И)).

Случай 2. Пусть -формула А содержит в точности п вхождений связок и графически совпадает с формулой DDE. Докажем, что У2 выполняется для А.

  • (1) неверно, что У1 (допущение).
  • (2) 3(D D E)3v: |D D E| f + 0 и |D D E| "« = 0 (из (1)).
  • (3) пусть D* D E* и v* - такие -формула и оценка, что

|D* ZD Е*| Jf3 0 и |D* ZD E*| = 0 (из (2), исключение кванторов).

  • (4) |D*Z)E*| "’’’ = () (из (3)).
  • (5) |D* D E*| = ip/ipJD*!D3 Ф,|Е*| ) (по определе

нию ЭД

  • (6) тр, |D*| Jf1'’ Э3 зр!|E*| = 0 (из (5), по определению фД
  • (7) ip,|D*| J.’’’ Ф 0 и ip,|E*|"w = 0 (из (7) и того факта, что Г LjВ е т е- г К2 в и эз есть базовая операция М).
  • (8) |D*| ^ЗчФ 0 (из (7), по определению ф t).
  • (9) |Е*| Jf34’ = 0 (из (7), по определению ф^.

(10) |D*| v*3 0 (из (8), в силу индуктивного допущения).

м2

  • (11) |E*|v*3 = 0 (из (9), в силу индуктивного допущения).
  • (12) |D* D E*|J!3 = 0 (из (11), (10) и того факта, что Г В, е.т.е. Г |=м В и D есть базовая операция М3).
  • (13) |D*DE*|^3 = 1 (из (3)).
  • (14) неверно, что (1) (из (13), (12)).

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

Аналогично Теореме 10, из данной теоремы вытекает, что, если г 1=м?ве т-е- г Им, В,т0 г Им? В, е.т.е. Г |=м .

iVJ3 2 1V13 лр 2

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

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