4.2 Свойства суммы по модулю 2, импликации, функции Шеффера и Пирса

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

Таблица 4.3-Законы ∑mod2

Переместительный	x y = y x
Сочетательный	x (y z) = (x y) z
Распределительный относит. конъюн.	x & (y z) = (x & y) (x & z)

Имеют место также очевидные соотношения:

Таблица 4.4-Правила ∑mod2

1 2 3 4 5

x x = 0 x 0 = x x 1 = x = 1 x + y = x y xy

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

x → y → z ≠ y → x → z; (x → y) → z ≠ x → (y → z);

(x → y)z ≠ xz → yz.

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

xy = х + у = → у.

Очевидные соотношения для импликации.

Таблица 4.5-Импликация

1 2 3 4 5

x → x = 1 x → = x → 1 = 1 x → 0 = 0 → x = 1

6 7 8 9 10

1 → x = x x → y = → x → y → x = x xy = x + y = → y

Импликация обладает только свойством коммутативности (переместительный закон) в измененном виде x→y= → .

Для функций Шеффера и Пирса имеет место только переместительный закон x / у = y / х; x ↓ y = y ↓ x.

Правила выполнения функций штрих Шеффера и стрелка Пирса имеют следующие очевидные соотношения (cм. табл.4.6), проверка которых предоставляется студентам самостоятельно.

Таблица 4.6-Правила ЛФ штрих Шеффера и стрелка Пирса

№ n/n	Шеффера "НЕ-И"	Пирса "НЕ-ИЛИ"
1	x / x =	x ↓ x =
2	x / =1	x ↓ = 0
3	x / 1 =	x ↓ 1 = 0
4	x / 0 = 1	x ↓ 0 =
5	/ 0 = 1	↓ 0 = х
6	/ 1 = x	↓ 1 = 0
7	x/y= = +	x ↓ y = =
8	xy= =x/y/x/y	xy=(x↓x)↓(y↓y)= ↓
9	x+y= = = /	x+y=(x↓y)↓(x↓y)
10	x / y =	= ↓
11	x ↓ y =	= /

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

(х / у) / (х / z) = = ↓ (y ↓ z);

(x ↓ y) ↓ (x ↓ z) = = / (y / z);

(x / y) ↓ (x / z) = = ↓ (y / z);

(x ↓ y) / (x ↓ z) = = / (y ↓ z);

(x / y) ↓ (z / k) = ↓ ;

(x ↓ y) / (z ↓ k) = / .

Доказательство этих соотношений осуществляется на основании правила 7 таблицы 4.6. Докажем, например,

(x ↓ y) / (x ↓ z) = / = (x + y) + (x + z) =

=x + y + z = x + (y + z) = x + ( / ) = =

= / ( ) = / (y ↓ z).

Функции Шеффера и Пирса связаны между собой соотношениями (10, 11 таблицы 4.6), аналогичными формулам де Моргана для функций конъюнкции и дизъюнкции.

Для доказательства этого, используют формулу 7.

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

Особое значение имеет знак инверсии, который выполняет также роль скобок.

Например, выражению

соответствует последовательность операций:

-инвертирование отдельных переменных ;

-логическое умножение ;

-сложение под нижним общим знаком инверсии;

-инвертирование результата полученного под нижним общим знаком инверсии;

-сложение результата под нижним общим знаком инверсии с , инвертирование.

4.3 Основные классы функций алгебры логики

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

4.3.1 Класс функций, сохраняющих значение нуль при нулевых значениях всех переменных

f (0, 0, ... ,0) = 0.

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

Будем обозначать их буквой K₀ - "коституэнта нуля".

4.3.2 Класс функций, сохраняющих значение единица при единичных значениях всех переменных

f (l, l, ... , 1) = 1.

Этот класс также составляет половину всех элементарных ФЛ и обозначается K₁ - "конституэнта единицы".

4.3.3 Класс самодвойственных функций

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

f (x₁, x₂, …, х_n) = ( , , … , ).

Самодвойственная функция от n аргументов полностью определяется на половине наборов значений аргументов. Обозначим S.

4.3.4 Линейная функция

Функция f(x₁, x₂, …, х_n) называется линейной, если она представима в следующем виде:

f = c₀ c₁x₁ … c_nx_n,

где коэффициент c_i может принимать значения {0, 1}. Обозначим через L. Число членов этого класса равно 2ⁿ⁺¹.

4.3.5 Монотонная функция

Функция f (x₁, x₂, …, х_n) называется монотонной, если для любых двух наборов (кортежей) и , таких что при ≥ имеет место неравенство:

f ( ) ≥ f ( ).

Обозначается буквой М.

4.3.6 Симметричная функция

Функция f (x₁, x₂, …, х_n) называется симметричной, если она не изменяется при произвольной перенумерации аргументов

f (x₁, x₂, …, х_n) = f (z₁,z₂,…,z_n),

где (z₁,z₂,…,z_n) –любая перестановка переменных.

Класс таких функций будем обозначать C.

5 АНАЛИТИЧЕСКАЯ ЗАПИСЬ ФУНКЦИЙ ЛОГИКИ

5.1 Аналитические формы представления ЛФ

Нами был рассмотрен табличный способ задания ФЛ, при котором каждому набору значений переменных x₁, x₂, …, х_n в таблице истинности указывается значение самой логической функции {0,1}. Однако, этот способ не пригоден для анализа и преобразований функций, в частности, с целью ее минимизации. Поэтому, используют аналитическую запись функций в виде логических формул, получаемых из тех же таблиц истинности по определенным правилам их записи. Рассмотрим некоторые определения.

Определение. Дизъюнктивный терм (макстерм) - терм, связывающий все переменные, представленные в прямой или инверсной форме, знаком дизъюнкции. В литературе: "конституэнта нуля". Например: F(x) = + х₂ + х₃ + х₄.

Определение. Конъюнктивный терм (минтерм) - терм, связывающий все переменные, представленные в прямой или инверсной форме, знаком конъюнкции. В литературе: "конституэнта единицы". Например: F(x) = x₁х₂ .

Рангом терма r называется число, определяющее количество переменных, входящих в данный терм. Например, для минтерма х₂х₃ r = 4; макстерма +х₂+х₃ r = 3.