Элементы математической логики. 2 страница

ВЫРАЖЕНИЕ ОДНИХ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ ЧЕРЕЗ ДРУГИЕ

1. Функция f ₈(x_1,x₂) = x₁®x₂ (импликация x₁ в x₂) может быть записана посредством функций дизъюнкции и отрицания

x₁>x₂= Úx ₂.

Доказательство осуществляется посредством таблиц истинности.

x1	x2		Ú x 2

2. Функцию эквивалентности f₇(x_1,x₂)=x₁~x₂ = x₁ºx₂ выразим посредством других функций x₁~x₂= ( Úx₂)&(x ₁Ú )

x 1	x 2	x1~x2
x 1	x 2			Úx 2	x1Ú	( Úx2)&(x 1Ú )

3. f ₁₁(x_1,x₂) = x₁ x₂=

x 1	x 2	x1 x2	x1~x2

или

f (x_1,x₂) = x₁ x₂=( & x₂) (x₁& )

x 1	x 2	x1 x2		( &x2)		(x1& )	( &x2) (x1& )

4. =x

x

5. x₁& x₂=

x 1	x 2

6. x₁ x₂=

x 1	x 2	x1 x2

x 1	x 2			&

7. x₁ x₂=

x 1	x 2	x1 x2

x 1	x 2			x2	x1

Свойства конъюнкции, дизъюнкции и отрицания

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

x₁&(x₂&x₃)= (x₁&x₂)&x₃,

x₁ (x₂ x₃)= (x₁ x₂) x₃,

переместительный

x₁ x₂= x₁ x₂,

x₁& x₂= x₁&x₂,

и распределительный законы. Кроме того, выполняется распределительный закон дизъюнкции относительно конъюнкции.

x₁ (x₂&x₃)= (x₁ x₂)& (x₁ x₃).

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

x 1	x 2	x 3	x2&x3	x1 (x2&x3)

x 1	x 2	x 3	x1 x2	x1 x3	(x1 x2)& (x1 x3)

Совпадение построенных таблиц доказывает наше утверждение.

Рассмотрим теперь ряд простых, но весьма важных соотношений

х х=х;

х&х=х.

х 1=1; х 0=х; х =1;

х&1=х. х&0=0. х& =0.

И как следствие получаем

х х … х=х,

х&х&…&х=х.

Как обобщение формул получаем следующие формулы, называемые формулами (законами) де Моргана

х₁ х₂ … х_n= ;

х₁&х₂&…&х_n= .

Свойства функций сложения по модулю 2, импликации, штриха Шеффера и стрелки Пирса (функции Вебба)

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

Для функции сложения по модулю 2 выполняются переместительный и сочетательный законы, а также распределительный закон относительно конъюнкции:

x₁ x₂= x₂ x₁;

x₁ (x₂ x₃)= (x₁ x₂) x₃;

x₁&(x₂ x₃)= (x₁&x₂) ( x₁&x₃).

Справедливы также очевидные соотношения

x x=0;

x 0=х;

x 1= ;

х =1.

Кроме того, выполняется формула х₁ х₂= x₁ x₂ x₁&x₂.

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

х®x=1;

x® = ;

x®1=1;

х®0= ;

0®х=1;

1®х=х;

х₁®х₂= ® ;

х₁®х₂® х₁= х₁.

Функции дизъюнкции и конъюнкции могут быть выражены через импликацию следующим образом:

х₁ х₂= ® х₂;

х₁&х₂= .

Для функции Шеффера и Вебба справедлив переместительный закон:

х₁ /х₂= х₂/х₁;

х₁¯х₂= х₂¯х₁.

Сочетательный закон для них не выполняется:

х₁/(х₂/х₃)¹(х₁/х₂)/х₃ ;

х₁¯( х₂¯х₃)¹ (х₁¯ х₂)¯ х₃.

Справедливы следующие очевидные соотношения, проверка которых аналогична приведенным выше примерам и осуществляется при помощи таблиц истинности:

х /х= , х¯ х= ;

х/ =1, х¯ =0;

х/1= , х¯1 =0;

х/0=1, х¯0= ;

х₁/х₂= = ;

х₁¯х₂= = & .

Функции Шеффера и Вебба связаны между собой соотношениями, аналогичными формулами де Моргана для функций конъюнкции и дизъюнкции:

х₁/х₂= ;

х₁¯х₂= .

ОСНОВНЫЕ КЛАССЫ ФАЛ

В качестве первого класса таких ФАЛ рассмотрим класс функций, сохраняющих константу нуль, т.е. таких функций, для которых справедливо равенство

f (0, 0, …, 0)=0

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

Аналогично класс функций, сохраняющих константу единица, будет определен, как класс функций, для которых выполняется равенство

f (1, 1,…, 1)=1

Этот класс состоит также из функций.

Определение Функция f*(x₁ ,…,x_n) называется двойственной к функции f (x₁ ,…,x_n), если выполняется равенство

f*(x₁ ,…,x_n)= .

Определение Функция . f (x₁ ,…,x_n) самодвойственный, если она совпадает с двойственной себе функцией, т.е. справедливо равенство

f (x₁ ,…,x_n )= .

Определение ФАЛ f(x₁,…,x_n ) называется линейной, если она представима в следующем виде

f (x₁ ,…,x_n )=с₀ с₁х_{1 …} с_nх_n,

где коэффициент с_i {0, 1}.

Число членов этого класса .

Определение ФАЛ f(x₁,…,x_n ) называется монотонной, если для любых двух наборов Х₁ и Х₂ таких, что Х₁³ Х₂ выполняется равенство

f (X₁)³f (X₂)

X₁=< >

X₂=< >.

Определение ФАЛ f(x₁,…,x_n ) называется симметричной, если она не изменяется при произвольной перенумерации аргументов.

f(x₁,…,x_n )= f(y₁,…,y_n ),

где (y₁,…,y_n) – любая перестановка аргументов (x₁,…,x_n ).

АНАЛИТИЧЕСКАЯ ЗАПИСЬ ФАЛ

Пусть имеется двоичный набор < >. Сопоставим ему число i, определяемое

i= + +…+ ,

число i называют номером набора < >.

Рассмотрим функцию F(x₁,…,x_n), определяемую следующим соотношением

1, если номер набора i

(0) F_i=

0, в противном случае.

Такую функцию называют характеристической функцией «единицы». Предположим, что удалось построить аналитическое выражение для функции F_i (как это можно сделать описывается ниже). Тогда справедлива следующая теорема.