Гумаров Р.Н.

Введение

В данной работе рассматриваются функции к-значной логики.

Пусть E₂ = {0,1}

Определение 1. Отображение f:E₂ⁿ → E₂ называется n-местной булевой функцией.

В дальнейшем множество всех булевых функций будем обозначать P₂. Произвольная n-местная булева функция f(х₁,х₂,…,х_n) может быть задана с помощью таблиц следующего вида:

Теорема 1. Число p2 (n) всех функций из P₂ зависящих от n  переменных  х₁, х₂, .... , х_n равно

Далее рассмотрим примеры булевых функций.

1)одноместные

f₂(x)=x тождественная функция

f₃(х)=

f₄(x)=1- константа 1

2) двух местные

f₆(х₁,х₂)= х₁&х₂ конъюнкция

f₁₁(х₁,х₂)= х₁+х₂ mod 2

f₁₂(х₁,х₂)= х₁х₂ дизъюнкция

f₁₃(х₁,х₂)= х₁ ↓ х₂ стрелка Пирса(анти дизъюнкция)

f₁₄(х₁,х₂)= х₁ ~ х₂ эквиваленция

f₁₈(х₁,х₂)= х₁ → х₂ импликация

f₁₉(х₁,х₂)= х1|х2 штрих Шеффера(анти конъюнкция)

f₂₀(х₁,х₂)=1 константа 1

Свойства элементарных булевых функций.

1.Коммутитавность

х₁&х₂=х₂&х₁

х₁х₂=х₂х₁

х₁+х₂=х₂+х₁

х₁|х₂=х₂|х₁

х₁↓х₂=х₂↓х₁

х₁~х₂=х₂~х₁

2.Ассоцитиативность

(х₁&х₂) &х₃ = х₁&(х₂&х₃)

(х₁х₂) х₃ = х₁ (х₂х₃)

сейчас выполним проверку

х1	х2	х3	х1х2	(х1х2) х3
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 1 1 1 1 1 1	0 1 1 1 1 1 1 1

3.Дистрибутивность

(х₁&х₂) &х₃= (х₁х₃)& (х₂х₃)

(х₁х₂) &х₃= (х₁&х₃)  (х₂&х₃)

4.=х

5. (х&x) =х

(х&) =0

(х&0) =0

(хvx) =х

В дальнейшем множество всех функций к-значной логики будем обозначать P_k

Замечание. При к=2, мы получаем множество P₂ всех булевых функций.

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

х1…хn-1 хn	f (х1…хn-1, хn)
0 …. 0 0 0 …….. 0 1 ……………………. 0 ……. 0 к-1 0 …… 1 0 ………………. К-1 ….к-1 к-1	F(0 …. 0 0) F(0 …….. 0 1) ……………………. F(0 ……. 0 к-1) F(0 …… 1 0) ………………. F(К-1 ….к-1 к-1)

Теорема. Число всех функций из P_k , зависящих от n переменных х₁,…., х_n равно .

Например, Уже в P₃ число функций от двух переменных равно 3⁹ = 19683, т.е. это множество практически необозримо.

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

1)

х
0 1 2	1 2 0

х
0 1 2 3	1 2 3 0

к=2

Nx=3-1-x=2-x

Nx=4-1-х=3-х

k=3

1. 
   Коммутативность
   

x₁,х₂ mod k= x₂,х₁ mod k

max(x₁,х₂)= Max(x₂,х₁)

x₁+х₂ mod k= x₂+х₁ mod k

2. 
   Ассоциативность
   

Min (Min(x₂,х₁), х₃)= Min (х_1,Min(x₂,х₃))

(x₁,х₂ mod k) х₃ mod k= x₁(x₂,х₃ mod k) mod k

Max (Max(x₂,х₁), х₃)= Max (х_1,Max(x₂,х₃))

((x₁+х₂ mod k)+ х₃) mod k= (x₁+(x₂+х₃ mod k)) mod k

3. 
   Дистрибутивность
   

(х₁х₂) х₃=(х₁х₃) (х₂х₃)

4. 
   х=1*I₁(x) 2* I₂(x) …(к-1) I_к-1(x)
   
5. 
   х₁= х₁(I₀(x₂) … I_к-1(x₂))
   
6. 
   I₀(x) I_j(x)= при j=0, при j
   

(к-1)х=х; 0*х=0;