Полный одноразрядный двоичный сумматор

Алгоритм построения ДНФ

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

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

3) Избавиться от знаков двойного отрицания.

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

Алгоритм построения КНФ

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

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

3) Избавиться от знаков двойного отрицания.

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

 

9)Если в какой-то простой конъюнкции недостает переменной, например, Z, вставляем в нее выражение:,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

-Y-ZV-X-Y-Z

Таким образом, из ДНФ получили СДНФ.

Если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение: (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):

-YV-Z)

Таким образом, из КНФ получена СКНФ.

Булевы функции

1)

Унарные функции

При n = 1 число булевых функций равно 2²¹ = 2² = 4. Определение этих функций содержится в следующей таблице.

Таблица значений булевых функций от одной переменной:

x		x̅	x
	тождественный ноль, тождественная ложь, тождественное "НЕТ"
x̅, x, x'	отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)
x	тождественная функция, логическое "ДА", "YES"(англ.)
	тождественная единица, тождественная истина, тождественное "ДА", тавтология

Бинарные функции

При n = 2 число булевых функций равно 2^2² = 2⁴ = 16.

x

y

x ↓ y

x ← y

x

x → y

y

x ⊕ y

x | y

x & y

x ≡ y

y

x → y

x

x ← y

x ∨ y

тождественный ноль, тождественная ложь, тождественное "НЕТ"

x ↓ y, x ИЛИ-НЕ y, ИЛИ-НЕ(x, y), x NOR y, NOR(x, y)

НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса

x < y, x ← y, x LT y, LT(x, y)

меньше, инверсия обратной импликации

x, НЕ1(x, y), NOT1(x, y), x', x

отрицание (негация, инверсия) первого операнда

x > y, x → y, x GT y, GT(x, y)

больше, инверсия прямой импликации

y, НЕ2(x, y), NOT2(x, y), y', y

отрицание (негация, инверсия) второго операнда

x ⊕ y, x +2 y, x ≠ y, x >< y, x <> y, x XOR y, XOR(x, y)

сложение по модулю 2, не равно, измена, исключающее «или»

x | y, x NAND y, NAND(x, y), x И-НЕ y, И-НЕ(x, y)

НЕ-2И, 2И-НЕ, антиконъюнкция, штрих Ше́ффера

x & y, x · y, xy, x ∧ y, x AND y, AND(x, y), x И y, И(x, y), min(x, y)

2И, конъюнкция

x ≡ y, x = y, x EQV y, EQV(x, y), x ~ y, x ↔ y

равенство, эквивалентность

y, ДА2(x, y), YES2(x, y)

второй операнд

x → y, x ≤ y, x ⊃ y, x LE y, LE(x, y)

меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)

x, ДА1(x, y), YES1(x, y)

первый операнд

x ← y, x ≥ y, x ⊂ y, x GE y, GE(x, y)

больше или равно, обратная импликация (от второго аргумента к первому)

x ∨ y, x + y, x ИЛИ y, ИЛИ(x, y), x OR y, OR(x, y), max(x, y)

2ИЛИ, дизъюнкция тождественная единица, тождественная истина, тождественное "ДА", тавтология

5) Система булевых функций называется полной, если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством P 2. Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций: Функции, сохраняющие константу T 0 и T 1; Самодвойственные функции S; Монотонные функции M; Линейные функции L. Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с P 2, целиком содержится в одном из этих пяти так называемых предполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию. Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.

 

Определение. Алгеброй Жегалкина называется алгебра над множеством логических функций и переменных, сигнатура которой содержит две бинарные операции & и , и две нульарные операции – константы 0 и 1.

В алгебре Жегалкина выполняются следующие соотношения:

1. x y = y x;

2. x (y z) = x y x z;

3. x x = 0;

(1.4)

4. x = 1;

5. x 0 = x.

Эти соотношения легко проверить табличным способом. Кроме перечисленных соотношений в алгебре Жегалкина выполняются соотношения булевой алгебры относительно конъюнкции и констант

.

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

1. = x 1.

Это соотношение проверяется непосредственной подстановкой 0 и 1 в обе части равенства.

x y = x y x y.

Доказательство: x y = = 1 = (x 1)(y 1) 1 =

= x y x y 1 1 = x y x y.

3. x ’ y = x y x 1.

Доказательство: Используем выражение для импликсации в (1.3). Тогда:

x ’ y = y = y y = (x 1) y (x 1) y =

= x y y x 1 y = x y x 1.

4. x / y = x y 1.

Доказательство: Используем выражение для x / y в (1.3). Тогда:

x / y = = xy 1.

5. x “ y = x y x y 1.

Доказательство: Используем выражение для x “ y в (1.3). Тогда:

x “ y = = (x 1)(y 1) = x y x y 1.

6. x ~ y = 1 x y.

Доказательство: Легко проверить, что x ~ y = x y . Тогда:

x ~ y = x y (x 1)(y 1) = x y x y x y 1 = 1 x y.

Определение. Полиномом Жегалкина для n логических переменных называется полином, являющийся суммой константы и различных одночленов, в которые все пере-

менные входят не выше, чем в первой степени:

a x x … x , (1 d k d n)

причем в каждом наборе (i ,, i ) все i различны, а суммирование по mod 2 ведется по некоторому множеству таких не совпадающих наборов.

Например, 1 x x x , x x x x x x - некоторые полиномы Жегалкина для двух и трех переменных соответственно.

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

В полученной формуле нужно раскрыть скобки и произвести упрощения, используя соотношения (1.4), а также следующие соотношения: x & x = x и x·1 = x. Полученное выражение и будет полиномом Жегалкина для данной формулы.

Пример. Найти полином Жегалкина для функции: f(x, y) = (x y)( x z).

Полученное выражение и есть полином Жегалкина.

 

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

f1 f2 = f1 f2, (1.5)

справедливое при f1f2 = 0. Используем соотношение (1.5) для нахождения полинома Жегалкина в следующих примерах.

Пример. Найти полином Жегалкина для функции: f(x, y) = x y .

Сделаем следующие преобразования:

f(x,y) = x y = x y = x y (x 1)(y 1) =

= x y x y x y 1 = 1 x y - полиномом Жегалкина.

Пример. Найти полином Жегалкина для функции: f(x, y) = x z.

Сделаем следующие преобразования:

f(x,y) = x z = x z = x (y 1) (x 1) z =

= x y x x z z = x z x y x z. - полиномом Жегалкина.

Теорема. Для любой логической функции существует полином Жегалкина и притом единственный.

Доказательство: Существование полинома доказано вышеприведенным алгоритмом получения полинома из логической формулы. Для доказательства единственности надо показать, что между множеством всех логических функций от n переменных и множеством всех полиномов Жегалкина от n переменных существует взаимно однозначное соответствие.

Полином Жегалкина можно найти методом неопределенных коэффициентов. Рассмотрим этот метод на следующим примере.

Пример. Найти полином Жегалкина для функции заданной векторно:

f(x,y) = (0, 1, 1, 0).

Составим таблицу 1.14 задания данной функции.

Таблица 1.14

x	y	f

Полином Жегалкина для функции двух переменных ищем в следующем виде:

f(x, y) = a0 a1·x a2·y a3·xy (1.6)

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

Подставляя набор переменных(0,0) в (1.6) получим:

. a = 0.

Аналогично для набора (0,1) получим: . a = 1.

Для набора (1,0) получим: a = 1.

Для набора (1,1) получим: a = 0.

Подставляя в (1.6) найденные значения коэффициентов получим искомый полином для данной функции:

f(x, y) = x y.

Замечание. Можно показать, что переменная x будет фиктивной для некоторой функции тогда и только тогда, когда полином Жегалкина для нее не содержит переменной x

 

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

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

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

 

13) Лемма о нелинейной функции.

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

Доказательство:
Пусть f(x₁,…, x_n) – нелинейная функция, тогда полином Жигалкина для нее содержит слагаемое, в котором присутствует произведение каких-то переменных x_i*x_j. Пусть для простоты это будет произведение х₁х₂. Произведя группировку слагаемых в полиноме Жегалкина для f относительно x₁х₂, х₁, х₂, функцию f представим в виде f(x₁,…, x_n)=x₁*x₂*h₀(x₃,..,x_n)+ {собрали все слагаемые с x₁*x₂ и вынесли x₁*x₂ за скобки. В скобках осталась сумма h₀(x₃,…,x_n), в которой переменных x₁, x₂ нет} + x₁*h₁(x₃,…, x_n) + x₂*h₂(x₃,…, x_n) + h₃(x₃,…, x_n)

Функция h₀(x₃,…, x_n)≠0, в противном случае многочлен Жигалкина слагаемых с произведением x₁x₂ не имеет, тогда существует набор (a₃,…, a_n) из 0 и1, для которого h₀(a₃,…, a_n)=1. Пусть на этом наборе h₁(a₃,…, a_n)=a h₂(a₃,…, a_n)=b h₃(a₃,…, a_n)=c. Тогда функция g(x₁,x₂)=f(x₁,x₂,a₃,…, a_n)=x₁*x₂+a*x₁+b*x₂+c. Построим функцию h(x₁,x₂) = g(x₁+bx₂+a) = (x₁+b)(x₂+a)+a(x₁+b)+b(x₂+a)+c = x₁*x₂+a*x₁+b*x₂+a*b+a*x₁+a*b+b*x₂+a*b+c = x₁*x₂+a*b+c=x₁*x₂+d, d=a*b+c
Если d=0, то h(x₁,x₂)=x₁*x₂, конъюнкция получена. Если d=1, то h(x₁,x₂)=x₁*x₂+1 ⇒ x₁*x₂=⌐h(x₁,x₂), что и требовалось доказать.

 

 

16) Релейно-контактные схемы (их часто называют переключательными схемами) широко используются в технике автоматического управления.

 

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

 

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

2) соединяющие их проводники;

3) входы в схему и выходы из нее (клеммы, на которые подается электрическое напряжение). Они называются полюсами.

 

Простейшая схема содержит один переключатель Р и имеет один вход А и один выход В. Переключателю Р поставим в соответствии высказывание р, гласящее: - “Переключатель Р замкнут ”. Если р истинно, то импульс, поступающий на полюс А, может быть снят на полюсе В без потери напряжения, то есть схема пропускает ток. Если р ложно, то переключатель разомкнут и схема тока не проводит. Таким образом, если принять во внимание не смысл высказывания, а только его значение, то можно считать, что любому высказыванию может быть поставлена в соответсвие переключательная схема с двумя полюсами (двухполюсная схема).

 

Формулам, включающим основные логические операции, также могут быть поставлены в соответствие переключательные схемы.

 

 

Так, конъюнкции двух высказываний ставится в соответствие схема:

а дизъюнкции - схема:

Так как любая формула может быть записана в ДНФ или КНФ, то ясно, что каждой формуле алгебры логики можно поставить в соответствие некоторую РКС, а каждой РКС можно поставить в соответствие некоторую формулу алгебры логики.

Пример 1. По данной формуле составить РКС .

Решение. Упростим данную формулу с помощью равносильных преобразований:

 

 

 

Тогда РКС для данной формулы имеет вид:

 

Пример 2. Упростить РКС:

Решение. Составим по данной РКС формулу (функцию проводимости) и упростим ее:

(к последним двум слагаемым применили закон поглощения).

Тогда упрощенная схема выглядит так:

 

 

18) Полусумматор — логическая схема, имеющая два входа и два выхода (двухразрядный сумматор, бинарный сумматор). Полусумматор используется для построения двоичных сумматоров. Полусумматор позволяет вычислять сумму A+B, где A и B — это разряды двоичного числа, при этом результатом будут два бита S,C, где S — это бит суммы по модулю, а C — бит переноса. Однако, как можно заметить, для построения схемы двоичного сумматора (трёхразрядный сумматор, тринарный сумматор) необходимо иметь элемент, который суммирует три бита A, B и C, где C — бит переноса из предыдущего разряда, таким элементом является полный двоичный сумматор, который как правило состоит из двух полусумматоров и логического элемента 2ИЛИ. Представляет собой объединение двух бинарных (двухоперандных) двоичных логических функций: сумма по модулю два - S и разряд переноса при двоичном сложении - C.

Полный одноразрядный двоичный сумматор

Одноразрядные двоичные сумматоры строятся по самым различным схемам. Рассмотрим функционирование одноразрядного сумматора, составленного из двух полусумматоров. Полусумматор - это устройство, производящее сложение двух одноразрядных двоичных чисел без учета переноса предыдущего разряда. Составим таблицу истинности полусумматора и полного одноразрядного двоичного сумматора (таблица 1.2).

A_i, B_i – двоичные цифры i разряда, P_i-1 – перенос из (i-1) разряда, Si – сумма, получившаяся в i разряде, Pi - перенос из i разряда в (i+1) разряд.

Первые четыре строчки таблицы 1.2 представляют собой таблицу истинности полусумматора.

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

Из таблиц истинности логических элементов и полусумматора видно, что для получения суммы двух одноразрядных двоичных чисел необходимо использовать логический элемент исключающее ИЛИ, а для получения переноса – логический элемент 2И. Схема полусумматора, построенного на указанных логических элементах, приведена на рисунке 1.31.

Схема полного одноразрядного сумматора построенного на двух полусумматорах приведена на рисунке 1.32. Один полусумматор используется для сложения i-го разряда двоичных чисел, а второй полусумматор складывает результат первого полусумматора с переносом из (i-1) разряда.

Показать самостоятельно, что для получения переноса в полном одноразрядном двоичном сумматоре необходимо сигналы переносов от полусумматоров подать на входы логического элемента 2ИЛИ, на выходе которого получится перенос из полного одноразрядного двоичного сумматора.

Рассмотрим следующий пример. Пусть А_i=0, В_i=1, P_i-1=1. В соответствии с таблицами истинности логических элементов 2И и исключающее ИЛИ на выходе элемента DD2.1 будет логический нуль, а на выходе DD1.1 – логическая единица. На входах Х1, Х2 логического элемента DD1.2 сигналы логических единиц, следовательно на выходе этого элемента логический нуль. На выходе элемента DD2.2 сигнал логической единицы. На входе Х1 элемента DD3.1 сигнал логической единицы. Логическая единица на входе логического элемента 2ИЛИ является активным логическим уровнем и, следовательно, на выходе элемента DD3.1 будет сигнал логической единицы. В результате получим сумму в i-ом разряде, равную нулю, а перенос из i-го разряда равный единице.

Самостоятельно проанализировать работу полного одноразрядного двоичного сумматора для нескольких других примеров.

В главе 2 рассматривается микросхема К155ИМ3, содержащая четырехразрядный двоичный сумматор. Сердцем процессора является арифметико-логическое устройство (АЛУ). АЛУ на микросхеме К155ИП3 изучается с помощью стенда по методике, рассмотренной в главе 2.

 

 

19) Шифратор (кодер) — (англ. encoder) логическое устройство, выполняющее логическую функцию (операцию) — преобразование позиционного n-разрядного кода в m-разрядный двоичный, троичный или k-ичный код.

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

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

где
— число входов,
— число выходных двоичных разрядов.

Троичный шифратор выполняет логическую функцию преобразования унарно n-ичного однозначного (одноединичного или однонулевого) кода в троичный. При подаче сигнала («1» в одноединичном коде или «0» в однонулевом коде) на один из n входов на выходе появляется троичный код номера активного входа.

Число входов и выходов в полном троичном шифраторе связано соотношением:

, где
— число входов,
— число выходных троичных разрядов.

Число входов и выходов в полном k-ичном шифраторе связано соотношением:

, где
— число входов,
— число выходных k-ичных разрядов,
— основание системы счисления.

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

Логика предикатов

1) Понятие ``предикат'' обобщает понятие ``высказывание''. Неформально говоря, предикат – это высказывание, в которое можно подставлять аргументы. Если аргумент один – то предикат выражает свойство аргумента, если больше – то отношение между аргументами.