Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

где

1. Теория булевых функций.

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

Определение.

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

1) оно имеет n ≥ 1 упорядоченных отростков сверху – входы и один отросток снизу – выход (см. рис. 5.1);

Рис. 5.1. Функциональный элемент.

2) на входы этого устройства могут подаваться сигналы, принимающие два значения, которые условно обозначают через 0 и 1;

3) при каждом наборе сигналов на входах устройство на выходе в тот же момент, в который поступили сигналы на входы, выдает один из сигналов 0 или 1;

4) набор сигналов на входах однозначно определяет сигнал на выходе, то есть если в различные моменты времени на входы поступили равные наборы сигналов, то в эти моменты на выходе будет один и тот же сигнал.

Заметим, что с каждым функциональным элементом с n выходами сопоставима булева функция от n переменных f (x₁, x₂,…, x_n), определяемая следующим образом: входу с номером ставится в соответствие переменная x_i и с каждым набором (а₁, а₂,…, а_n) значений этих переменных сопоставляется число f (а₁, а₂,…, а_n), равное 0 или 1 в зависимости от того, какой сигнал вырабатывается на выходе при подаче этого набора сигналов на выходы данного функционального элемента.

В этом случае о функции f (x₁, x₂,…, x_n) будем говорить, что данный функциональный элемент ее реализует, и такой элемент будем изображать так, как показано на рис.5.2.

Рис. 5.2. Реализация функционального элемента булевой функции f (x₁, x₂,…, x_n).

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

1) , ∧, ∨; 3) , ∨; 5) х ∣ у;

2) , ∧; 4) 1, ∧, ; 6) х ↓ у

и т.д.

Замечания.

1. Учитывая, что существуют определённые аналитические преобразования одного логического базиса в другой, можно изображать схемы в любом логическом базисе и преобразовывать их в другие. Базис, состоящий из логических функций , ∧, ∨ называется нормальным; из логических функций ù, ∨ или ù, ∧ – неполным нормальным; из стрелки Пирса х ↓ у – базисом Вебба; из штриха Шеффера х ∣ у – базисом Шеффера.

Как известно, базис Вебба и базис Шеффера связаны с нормальным базисом следующими аналитическими соотношениями:

х ∣ у = ∨ ; и обратно, = х ∣ х; х ∨ у = (х ∣ х)∣(у ∣ у);

х ↓ у = ∧ ; и обратно, = х ↓ х; х ∧ у =(х ↓ х) ↓ (у ↓ у).

Переход от схемы в нормальном базисе к базисам Шеффера и Вебба и обратно, например, можно отобразить в следующей таблице (таблица 5.1).

Таблица 5.1.

2. Логические функции, кроме их реализации функциональными схемами, реализуются также контактными, релейно-контактными и интегральными схемами.

3. Одна и та же схема (функциональная, контактная, релейно-контактная, интегральная) может быть реализована большим или меньшим числом функциональных базисных элементов (функций), для уменьшения которых, реализующих одну и ту же булеву функцию, разработана теория минимизации нормальных форм.

47.Основные понятия булевых функций.

Теорема.

Число всех различных булевых функций от n аргументов равно .

Доказательство:

Число различных наборов переменных x₁, x₂, … , x_n, где x_i {0,1} равно k=2ⁿ. Так как каждая булева функция принимает только 2 значения: 0 или 1, то число всех булевых функций от n переменных равно , что и требовалось доказать.

Определение.

Операцией сложения по модулю два, которая обозначается знаком , на множестве из двух элементов 0 и 1 называется операция со следующим законом композиции:

для a имеет место

a  a ≐ 0 ; a  0 0  a a .

Определение.

Элементарными булевыми функциями называются следующие функции:

e₁(x) 0 – нуль-функция;

e₂(x) 1 – единица-функция;

e₃(x) x – функция x;

e₄(x) = ù x – отрицание x;

e₅(x, y) ≐ – конъюнкция x и y;

e₆(x, y) ≐ – дизъюнкция x и y;

e₇(x, y) ≐ x  y – импликация x и y;

e₈(x, y) ≐ x  y – эквиваленция x и y;

e₉(x, y) x  y – сложение по модулю два x и y.

Замечания.

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

Таблица

2. Заметим, что

1) x  y = ù ( x  y), то есть e₉(x, y) = e₄(e₈(x, y)), то есть функция xy является суперпозицией функций xy и ù x.

2) – суперпозиция функций и , каждая из которых от двух переменных.

3) 0 = ù ( ù x); 1= ù x.

Приоритеты логических операций.

Операция ù имеет больший приоритет, чем ;

Операция имеет больший приоритет, чем ;

Операция  имеет больший приоритет, чем ;

Операция имеет больший приоритет, чем ;

Операция  имеет больший приоритет, чем .

Примеры функций, являющихся суперпозициями элементарных функций.

g₁(x₁, x₂, x₃, x₄) ≐  ù x₄

g₂(x₁, x₂, x₃) ≐ ù x₂)

g₃(x₁, x₂) ≐ ù

Определение.

Пусть

1) u – переменная, при этом пусть u⁰= ù u, а u¹=u;

2) a_i {0,1} , ;

3) u₁, u₂, … , u_n – переменные, причём не обязательно различные.

Тогда формула называется элементарной конъюнкцией, а – элементарной дизъюнкцией.

Примеры.

1. Элементарными конъюнкциями будут следующие формулы:

x, y, ù x, x  y, x₁  x_1, , , , .

2. Элементарными дизъюнкциями будут следующие формулы:

x, y, ù y, x  y, x  x  x, , , , .

Ясно, что каждая элементарная конъюнкция и каждая элементарная дизъюнкция являются суперпозициями функций ù x, x  y и x  y.

Замечание.

Принимая для переменной u , что и , замечаем, что u^a = 1  u = a, a {0,1}.

В этом случае :

1) функция

K_n(x_1, x₂,…, x_n) = (1)

такая, что K_n(a_1, a₂,…, a_n) = 1 и K_n(b_1, b₂,…, b_n) = 0, если

(b_1, b₂,…, b_n)  (a_1, a₂,…, a_n);

2) функция

d_n(x_1, x₂,…, x_n)= (2)

такая, что d_n( ) = 0 и d_n(b_1, b₂,…, b_n) = 1, если

(b_1, b₂,…, b_n)  ( ).

При этом в формулах (1) и (2) все переменные попарно различны.

Теорема.

Каждая булева функция является суперпозицией следующих функций: отрицания, конъюнкции и дизъюнкции.

Доказательство:

Первое доказательство.

Обозначим множество всех булевых функций через P₂. Если данная функция f P₂ является константой, равной нулю, то, согласно соотношению 0 = ù (x ù x) или 0 = x ù x, утверждение справедливо. В противном случае, существуют такие наборы (a_1, a₂,…, a_n), что f(a_1, a₂,…, a_n)=1. Для каждого такого набора (a_1, a₂,…, a_n) образуем элементарную конъюнкцию , которая имеет значение 1 только на наборе (a_1, a₂,…, a_n). Тогда

f(x_1, x₂,…, x_n) = , (3)

где дизъюнкции берётся по всем таким наборам (a_1, a₂,…, a_n), что f(a_1, a₂,…, a_n) = 1. Так как правая часть равенства (3) является суперпозицией требуемых функций, то теорема доказана.

Второе доказательство.

Если функция f P₂ является константой равной 1, то, согласно 1= x ù x или 1=ù (x ù x), утверждение справедливо. В противном случае, существуют такие наборы (a_1, a₂,…, a_n), что f(a_1, a₂,…, a_n)  1, или, что то же самое, f(a_1, a₂,…, a_n) = 0. Таким образом, функция f(x_1, x₂,…, x_n) может быть представлена в виде

f(x_1, x₂,…, x_n) = , (4)

где конъюнкция берётся по всем таким наборам (a_1, a₂,…, a_n), что

f(a_1, a₂,…, a_n)=0. Правая часть равенства (4) опять, как и в первом доказательстве, является суперпозицией требуемых функций. Теорема доказана.

Определение.

Правая часть равенства (3) называется совершенной дизъюнктивной нормальной формой (кратко СДНФ) функции f(x_1, x₂,…, x_n).

Замечание.

СДНФ существует только для тех булевых функций, которые не являются константами, равными нулю.

Определение.

Правая часть равенства (4) называется совершенной конъюнктивной нормальной формой (СКНФ) функции f(x_1, x₂,…, x_n).

Замечание.

СКНФ существует только для тех булевых функций, которые не являются константами, равными единице.

Определение.

Конъюнкция всех аргументов функции (с отрицанием и без отрицания) называется полной и обозначается буквой K с соответствующим индексом. Индексом в обозначении служит номер набора или двоичное число, а также соответствующее ему десятичное, полученное при замене каждой переменной x_i символом 1, а переменной ù x_i – символом 0.

Определение.

Дизъюнкция всех аргументов функции (с отрицанием и без отрицания) называется полной и обозначается (в литературе) буквой D с соответствующим индексом. Индексом служит инверсионный номер набора или двоичное число, а также соответствующее ему десятичное, полученное при замене каждой переменной x_i символом 0, а переменной ù x_i – символом 1.

Примеры.

1. x₁x₂ – номер набора –11₂ = 3₁₀, полная конъюнкция обозначается K₃.

2. – номер набора – 010₂ = 2₁₀, полная конъюнкция обозначается K₂.

Характеристики

Список файлов лекций