Предполные классы


Предполный класс в теории булевых функций — замкнутый класс булевых функций, обладающий следующим свойством — замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все P 2 {displaystyle P_{2}} . Множество предполных классов булевых функций исчерпывается списком:

  • Класс T 0 {displaystyle T_{0}} функций, сохраняющих константу 0:
    T 0 = { f ( x 1 , … , x n ) | f ( 0 , … , 0 ) = 0 } {displaystyle T_{0}=left{f(x_{1},dots ,x_{n})|f(0,dots ,0)=0 ight}} .
  • Класс T 1 {displaystyle T_{1}} функций, сохраняющих константу 1:
    T 1 = { f ( x 1 , … , x n ) | f ( 1 , … , 1 ) = 1 } {displaystyle T_{1}=left{f(x_{1},dots ,x_{n})|f(1,dots ,1)=1 ight}} .
  • Класс S {displaystyle S} самодвойственных функций:
    S = { f ( x 1 , … , x n ) | f ( x 1 ¯ , … , x n ¯ ) = f ( x 1 , … , x n ) ¯ } {displaystyle S=left{f(x_{1},dots ,x_{n})|f({overline {x_{1}}},dots ,{overline {x_{n}}})={overline {f(x_{1},dots ,x_{n})}} ight}} .
  • Класс M {displaystyle M} монотонных функций:
    M = { f ( x 1 , … , x n ) | ∀ i ( a i ≤ b i ) ⇒ f ( a 1 , … , a n ) ≤ f ( b 1 , … , b n ) } {displaystyle M=left{f(x_{1},dots ,x_{n})|forall i(a_{i}leq b_{i})Rightarrow f(a_{1},dots ,a_{n})leq f(b_{1},dots ,b_{n}) ight}} .
  • Класс L {displaystyle L} линейных функций — представимых полиномом Жегалкина первой степени:
    L = { f ( x 1 , … , x n ) | f ( x 1 , … , x n ) = a 0 ⊕ a 1 x 1 ⊕ ⋯ ⊕ a n x n , a i ∈ { 0 , 1 } } {displaystyle L=left{f(x_{1},dots ,x_{n})|f(x_{1},dots ,x_{n})=a_{0}oplus a_{1}x_{1}oplus dots oplus a_{n}x_{n},a_{i}in {0,1} ight}} .

Также говорят о предполноте одного замкнутого класса в другом. Класс A предполон в классе B, если замыкание класса A с любой функцией, принадлежащей B, но не принадлежащей A, порождает класс B. Например, класс M ∩ T 0 {displaystyle Mcap T_{0}} предполон в классах T 0 {displaystyle T_{0}} и M {displaystyle M} .

В многозначной логике предполные классы аналогично определяются как замкнутые классы, обладающие свойством — замыкание объединения этого класса с любой функцией из P k {displaystyle P_{k}} , не принадлежащей ему, порождает все P k {displaystyle P_{k}} . Но в случае k>2 на данный момент нет общего описания структуры предполных классов в отличие от двузначной логики.



Имя:*
E-Mail:
Комментарий: