Математические и логические основы информатики (стр. 4 из 6)

Например, булевская функция y=f(x,y,z), задаваемая формулой логики высказываний x&yÚØx&ØyÚz может быть задана в виде следующей суперпозиции функций от одной и двух переменных: y=f8(f8(f2(x,y),f9(x,y)),φ2(z)).

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

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

- число наборов истинностных значений, на которых определена булевская функция от n переменных, составляет 2n (при n=1 это число составляет 2, при n=2 - 4);

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

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

А отсюда можно сделать предположение о том, число N различных булевских функций от n переменных равно числу различных двоичных наборов длины 2n, то есть:

При n=1 это число равно 4, при n=2 - 16, n=3 - 256, n=4 - 65536 и т.д.

Полные системы булевских функций

В предыдущем пункте было отмечено, что можно выразить любую булевскую функцию от n переменных в виде суперпозиции (взаимной подстановки) булевских функций от одной и двух переменных. В свою очередь эти функции задаются формулами, содержащими логические операции: отрицание(Ø), конъюнкцию (&),строгую дизъюнкцию (Å), дизъюнкцию(Ú), импликацию(É), эквиваленцию (~).

Но как известно из логики высказываний, операции логики высказываний строгая дизъюнкция (Å), импликация (É), эквиваленция (~) могут быть выражены через дизъюнкцию (Ú), конъюнкцию (&) и отрицание (Ø).

В свою очередь, дизъюнкция (Ú) может быть выражена через конъюнкцию (&) и отрицание (Ø), а конъюнкция (&) - через дизъюнкцию (Ú) и отрицание (Ø).

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

Более того, можно определить логическую операцию, через которую выражаются все шесть операций: отрицание (Ø), конъюнкция (&), дизъюнкция (Ú), строгая дизъюнкция (Å), импликация (É), эквиваленция (~). Таковой, например, является операция, соответствующая сложному союзу "не А или не В" ("или" соединительное). Эта операция обозначается символом ô(например, АôВ) и получила название штрих Шеффера. Штрих Шеффера определяется с помощью следующей таблицы:

X	Y	XôY
Л	Л	И
Л	И	И
И	Л	И
И	И	Л

Как легко видеть, штрих Шеффера представляет собой отрицание конъюнкции: XôYºØXÚØYºØ(X&Y).

Можно убедиться, что ØXºXôX.

А отсюда: X&YºØ( XôY) º (XôY) ô( XôY).

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

Есть еще одна логическая операция, аналогичная штриху Шеффера и называемая стрелкой Пирса. Она обозначается символом и представляет собой отрицание дизъюнкции (или конъюнкцию отрицаний): XYºØ(XÚY) ºØX&ØY.

Можно убедиться, что ØXºXX.

А отсюда: XÚYºØ( XY) º (XY) ( XY).

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

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

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

S0 = {φ3(x), f2(x,y), f8(x,y)} - отрицание, конъюнкция, дизъюнкция.

S1 = {φ3(x), f2(x,y)} - отрицание, конъюнкция.

S2 = {φ3(x), f8(x,y)} - отрицание, дизъюнкция.

S3 = {f15(x,y)} - отрицание конъюнкции (штрих Шеффера).

S4 = {f9(x,y)} - отрицание дизъюнкции (стрелка Пирса).

S5 = {φ3(x), f14(x,y)} - отрицание, импликация.

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

Общий критерий функциональной полноты системы булевских функций, выражающий необходимые и достаточные условия, носит название критерия Поста-Яблонского.[6] Его изложение выходит, к сожалению, за рамки настоящего пособия.

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

Рассмотрим так называемые схемы из функциональных элементов (комбинационные схемы), вычисляющие (реализующие) булевские функции.

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

1) оно имеет n³1 упорядоченных входов и один выход;

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

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

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

С каждым функциональным элементом с n входами сопоставим булевскую функцию от n переменных f(x1,x2,…,xn), определяемую следующим образом: входу с номером i(i = 1, 2, … , n) ставится в соответствие переменная xi и с каждым набором <a1, a2, … , ai, …, an> этих переменных (aiÎ{0,1}) сопоставляется число f(a1, a2, … , ai, …, an), равное 0 или 1 в зависимости от того, какой сигнал вырабатывается на выходе при подаче этого набора сигналов на входы данного функционального элемента. О функции f(x1,x2,…,xn) будем говорить, что данный функциональный элемент ее реализует.

В дальнейшем мы будем рассматривать функциональные элементы, реализующие полную систему логических операций: конъюнкцию, дизъюнкцию, отрицание. Эти элементы представлены на рис.2.18.

Теперь определим понятие "схема из функциональных элементов в базисе {&, Ú, Ø}" и понятия ее выходов и входов. Определение будет носить индуктивный характер (подобно тому, как выше определялось понятие формулы логики высказываний).

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

2. Если S1 - схема из функциональных элементов и два ее входа соединены вместе, то получающаяся конструкция S будет схемой из функциональных элементов. Входами S являются все несоединенные входы S1 и еще один вход, соответствующий двум соединенным входам схемы S1, а выходом схемы S - выход S1.

3. Если S1 и S2 - две схемы из функциональных элементов, то конструкция S, получающаяся соединением какого-либо входа схемы S2 с выходом схемы S1, также будет схемой из функциональных элементов. Входами схемы S будут все входы схемы S1 и все входы схемы S2, за исключением того, который соединен с выходом схемы S1, а выходом S является выход схемы S2.

4. Если в схеме из функциональных элементов S1 ее вход соединить с выходом некоторого функционального элемента из S1 без образования цикла для какого-либо функционального элемента (то есть его выход не должен соединяться, быть может, через другие функциональные элементы из S1 с его входом), то получившаяся конструкция S является схемой из функциональных элементов. Выходом S будет выход S1, а входами S - все входы S1, кроме того, который соединен с выходом функционального элемента. На рис.2.21 приведен пример подобной схемы:

Определение схемы из функциональных элементов завершено.

Теперь определим булевскую функцию, реализуемую данной схемой.

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

2. Если схема S1 реализует булевскую функцию f(x1,x2,…,xn), то схема S, построенная в п.2 определения схемы из функциональных элементов, реализует булевскую функцию, полученную из f(x1,x2,…,xn) отождествлением переменных, отвечающих объединенным входам схемы S1.

3. Пусть схема S1 реализует булевскую функцию f(x1,x2,…,xn), а схема S2 - булевскую функцию g(y1,y2,…,ym). Считаем, что все переменные x1,x2,…,xn,y1,y2,…,ym попарно различны. Тогда схема S, построенная в п.3 определения схемы из функциональных элементов, реализует булевскую функцию g(y1, y2, …, yi-1, f(x1,x2,…,xn), yi-1, … , ym), то есть функцию, получаемую путем подстановки в функцию g(y1,y2,…,ym) вместо аргумента yi, сопоставленного входу схемы S2, соединенному с выходом S1, функции f(x1,x2,…,xn).

4. Булевская функция, реализуемая схемой S, построенной в п.4 определения схемы из функциональных элементов, получается из булевской функции, реализуемой схемой S1, операцией, типа описанной в п. 3 настоящего определения. Например, приведенная на рис.2.21 схема реализует функцию f(x1,x2,x3,x4) = Ø( x1&Øx2&(Øx3Úx4)).

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

Поскольку, как отмечалось выше, любую булевскую функцию от n переменных можно выразить в виде суперпозиции функций, образующих полную систему булевских функций (в частности, S0 = {φ3(x), f2(x,y), f8(x,y)} - отрицание, конъюнкция, дизъюнкция), то значит, что и любая булевская функция может быть реализована соответствующей схемой из функциональных элементов.