Переключательные функции одного и двух аргументов

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

 

Кафедра информатики

РЕФЕРАТ

На тему:

 

«Переключательные функции одного и двух аргументов»

МИНСК, 2008

1.Переключательные функции одного аргумента.

 

Существует четыре переключательные функции одного аргумента, которые приведены в табл. 1.

Таблица 1

Переключательные функции одного аргумента

x f(x)	0	1	Условное обозначение	Название функции
f0(x)	0	0	0	Константа нуль
f1(x)	0	1	x	Переменная x
f2(x)	1	0		Инверсия x
f3(x)	1	1	1	Константа единица

Функция f₀(x) тождественно равна нулю. Она называется константой нуль и обозначается f₀(x)=0.

Функция f₁(x) повторяет значения аргумента и поэтому тождественно равна переменной x.

Функция f₂(x) принимает значения, противоположные значениям аргумента: если x=0, то f₂(x)=1; если x=1, то f₂(x)=0. Эту функцию называют инверсией x или отрицанием x и вводят для нее специальное обозначение f₂(x)= .

Функция f₃(x) тождественно равна единице. Она называется константой единица и обозначается f₃(x)=1.

 

2. Переключательные функции двух аргументов.

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

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

f₀(x,y) = 0 — константа нуль;

f₁₅(x,y) = 1 — константа единица;

f₃(x,y) = x —переменная x;

f₅(x,y) = y —переменная y;

f₁₂(x,y) = —инверсия x;

f₁₀(x,y) = —инверсия y;

Таблица 2

Переключательные функции двух аргументов

x	0	0	1	1	Название функции	Обозначение
y	0	1	0	1
f0(x,y)	0	0	0	0	Константа нуль	0
f1(x,y)	0	0	0	1	Произведение (конъюнкция)	x∙y; xÙy;x&y
f2(x,y)	0	0	1	0	Функция запрета по y	xDy
f3(x,y)	0	0	1	1	Переменная x	x
f4(x,y)	0	1	0	0	Функция запрета по x	yDx
f5(x,y)	0	1	0	1	Переменная y	y
f6(x,y)	0	1	1	0	Сумма по модулю 2 (логическая неравнозначность)	xÅy
f7(x,y)	0	1	1	1	Логическое сложение (дизъюнкция)	x+y; xÚy
f8(x,y)	1	0	0	0	Операция Пирса (стрелка Пирса)	x¯y
f9(x,y)	1	0	0	1	Эквивалентность (логическая равнозначность)	x~y
f10(x,y)	1	0	1	0	Инверсия y
f11(x,y)	1	0	1	1	Импликация от y к x	y®x
f12(x,y)	1	1	0	0	Инверсия x
f13(x,y)	1	1	0	1	Импликация от x к y	x®y
f14(x,y)	1	1	1	0	Операция Шеффера (штрих Шеффера)	x½y
f15(x,y)	1	1	1	1	Константа единица	1

Рассмотрим некоторые переключательные функции двух аргументов.

Функция f₁(x,y) называется конъюнкцией, или логическим умножением. Таблица истинности этой функции совпадает с таблицей умножения двух одноразрядных двоичных чисел. Можно ввести функцию n аргументов, соответствующую произведению n одноразрядных двоичных чисел. Такая переключательная функция равна единице тогда и только тогда, когда все ее аргументы равны единице. Для конъюнкции справедливы следующие соотношения:

x × 0 = 0;

x × 1 = x;

x × x = x;

x × y = y × x;

x × = 0.

Функция f₇(x,y) называется дизъюнкцией или логическим сложением. Эта функция равна нулю только в том случае, когда все ее аргументы равны нулю. Можно ввести функцию n аргументов, соответствующую логическому сложению n одноразрядных двоичных чисел. Такая переключательная функция равна нулю тогда и только тогда, когда все ее аргументы равны нулю. Для конъюнкции справедливы следующие соотношения:

x Ú 0 = x;

x Ú 1 = 1;

x Ú x = x;

x Ú y = y Ú x;

x Ú = 1.

Таблица истинности функции f₆(x,y) совпадает с таблицей сложения двух одноразрядных двоичных чисел по модулю два. Можно ввести функцию n аргументов, соответствующую сумме по модулю два n одноразрядных двоичных чисел. Такая переключательная функция определяется следующим условием: она равна единице, если число аргументов, равных единице, нечетно, и равна нулю, если число таких аргументов четно. Приведем некоторые соотношения для суммы по модулю два:

x Å 0 = x;

x Å 1 = ;

x Å x = 0;

x Å x Å x = x;

x Å y = y Å x.

Рассмотренные шестнадцать функций двух аргументов (будем называть их элементарными) позволяют строить новые переключательные функции следующим образом:

·  путем перенумерации аргументов;

·  путем подстановки в функцию новых функций вместо аргументов.

Функцию, полученную из функций f₁, f₂, …, f_k путем применения (возможно многократного) этих двух правил, будем называть суперпозицией функций f₁, f₂, …, f_k. Например, имея элементарные функции инверсии, конъюнкции, дизъюнкции, импликации, запрета, сложения по модулю два, можно составить новую переключательную функцию:

f (x,y,z) = ((Úy)Dz)Å((y®z)×x).

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

Пример 1. Представить в виде таблицы функцию

f (x,y,z) = ((Úy)Dz)Å((y®z)×x).

Решение. Функцию f (x,y,z) будем представлять последовательно, записывая в столбцы табл. 1.5 промежуточные результаты, получаемые после выполнения каждой операции:

Таблица 3

Таблица истинности функции f (x,y,z) = ((Úy)Dz)Å((y®z)×x).

x	y	z		(Úy)	(Úy)Dz)	(y®z)	(y®z)×x	((Úy)Dz)Å((y®z)×x)
0	0	0	1	1	1	1	0	1
0	0	1	1	1	0	0	0	0
0	1	0	1	1	1	1	0	1
0	1	1	1	1	0	1	0	0
1	0	0	0	0	0	1	1	1
1	0	1	0	0	0	0	0	0
1	1	0	0	1	1	1	1	0
1	1	1	0	1	0	1	1	1

3. Представление переключательной функции в виде многочленов.

 1. Конституенты. В п. 2 был рассмотрен один из возможных способов представления переключательной функции – задание ее в виде таблицы истинности. В этом разделе будем решать обратную задачу, а именно представление переключательной функции, заданной таблицей истинности, через элементарные функции, образующие базис.

Рассмотрим переключательные функции, называемые конституентами.

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

Из определения следует, что число различных конституент единицы среди функций n аргументов равно 2ⁿ. Конституенты единицы обозначаются так: K_i(x₁, …, x_n), где i – номер набора, на котором конституента равна единице. Например, запись K₇(x₁, x₂, x₃, x₄) означает функцию четырех аргументов, равную единице на наборе (0111).

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

K₇(x₁, x₂, x₃, x₄) = .

Чтобы записать в виде произведения конституенту K_i(x₁, …, x_n), можно воспользоваться следующим правилом: записать n-разрядное двоичное число (n – число аргументов), равное i, и конъюнкцию n переменных; над переменными, места которых совпадают с позициями нулей в двоичном числе i, поставить знак отрицания.

Пример 2. Записать конституенту, равную единице на двенадцатом наборе для функции пяти переменных.

Решение. Пятиразрядное двоичное число, равное двенадцати, записывается в виде: 01100. Запишем произведение пяти аргументов, располагая их в порядке возрастания индексов: x₁×x₂×x₃×x₄×x₅. Сопоставляя это произведение с двоичным числом 01100, определяем, что знаки отрицания необходимо поставить над первым, четвертым и пятым аргументами:

K₁₂(x₁, x₂, x₃, x₄, x₅) =.

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

Из определения следует, что число различных конституент нуля среди функций n аргументов равно 2ⁿ. Конституенты нуля обозначаются так: M_i(x₁, …, x_n), где i – номер набора, на котором конституента равна нулю. Конституента нуля может быть выражена через дизъюнкцию всех аргументов, каждый из которых входит в произведение со знаком отрицания или без него.

Чтобы записать в виде произведения конституенту M_i(x₁, …, x_n), можно воспользоваться следующим правилом: записать n-разрядное двоичное число (n – число аргументов), равное i, и дизъюнкцию n переменных; над переменными, места которых совпадают с позициями единиц в двоичном числе i, поставить знак отрицания.

Пример 3. Записать конституенту нуля, равную нулю на двадцать пятом наборе для функции пяти переменных.

Решение. Пятиразрядное двоичное число, равное двадцати пяти, записывается в виде: 11001. Запишем дизъюнкцию пяти аргументов, располагая их в порядке возрастания индексов: x₁Úx₂Úx₃Úx₄Úx₅. Сопоставляя это произведение с двоичным числом 11001, определяем, что знаки отрицания необходимо поставить над первым, вторым и пятым аргументами:

M₂₅(x₁, x₂, x₃, x₄, x₅) =.