Выполнение компьютерной программы сводится к последовательности выполнения команд - базисных операций, выполняемых процессором компьютера. Сегодняшние процессоры компьютера мощные и могут выполнять достаточно сложные команды. Для нашего анализа разумно вернуться к корням компьютерных вычислений и обсудить простейшие базисные операции, достаточные для построения компьютера. Таких операций три: АND, ОR, NОТ. Первые две - бинарные операции над двумя аргументами, операция NОТ - унарная, у нее один аргумент.
Логика является источником этих операций. Значения бита интерпретируются как True/Fa1se, где х = 1 интерпретируется как "х истинно" (Тrue), а х = 0 означает "х - ложно" (Fa1se). Тогда х АND у означает "х и у оба истинны", х ОR у означает "или х - истинно, или у - истинно, или х и у оба истинны". Эти операции называются булевыми операциями, названными так в честь Джорджа нуля - математика 19-го столетия, положившего начало оснований символической логики.
Приведем следующие истинностные таблицы этих логических операций:
Далее будем использовать более короткую нотацию "$$х \bigwedge y$$ " для " х AND у", " $$х \bigvee y$$ " для "х ОR у" и "$$\bar x$$" для "NОТ х". Функция АND называется также конъюнкцией, ОR - дизъюнкцией.
Утверждение. Операции Булевой логики удовлетворяют следующим свойствам - законам логики:
(1) $$\overline{x \bigwedge y}=\bar x \bigvee \bar y$$,
(2) $$\overline{x \bigvee y}=\bar x \bigwedge \bar y$$,
(З) $$\bar \bar x=x$$,
(4) $$x \bigwedge (y \bigvee z)=(x \bigwedge y) \bigvee (x\bigwedge z)$$,
(5) $$x \bigvee (y \bigwedge z)=(x \bigvee y) \bigwedge (x \bigvee z)$$.
Доказательство этих свойств оставляем в качестве упражнения.
При вычисления логических выражений важен порядок выполнения операций. Полагается, что AND выполняется раньше, чем OR, также как в арифметических выражениях умножение имеет более высокий приоритет чем сложение. Так что выражение $$x \bigwedge y \bigvee z \bigwedge w$$ понимается как $$(x \bigwedge y) \bigvee (z \bigwedge w)$$, а выражение $$x \bigvee y \bigwedge z \bigvee w$$ эквивалентно $$x \bigvee (y \bigwedge z) \bigvee w$$.
Пример. Давайте выразим функцию х = у через функции базиса. По определению эквивалентности (равенства), либо оба х и у имеют значение Тruе, либо оба - Fa1se. Это можно выразить так:
Пример. Давайте выразим функциями базиса отношение между числами: 2-битное целое $$х_1х_0$$ больше чем 2-битное целое $$у_1у_0$$. Построенная логическая функция должна давать 1, если $$х_{1х0} > у_1у_0$$ и 0 в противном случае. Неравенство выполняется, если $$х_1 > у_1$$ либо $$х_1 = у_1$$ и $$х_0 > у_0$$ Неравенство "$$х_1 > у_1$$" означает, что $$х_1 = 1$$ и $$у_1 = 0$$. Выражение для равенства было приведено в предыдущем примере. Комбинируя, получим формулу булевой алгебры, вычисляющую эту функцию:
$$x_1 \bigwedge \bar y_1 \bigvee (x_1 \bigwedge y_1 \bigvee \bar x_1 \bigwedge \bar y_1) \bigwedge x_0 \bigwedge \bar y_0$$Как ранее отмечалось, любое классическое вычисление может рассматриваться как функция $$f : В_n \to В_k$$ . Такая функция может быть заменена k функциями $$f_1,f_2, \dots, f_k$$ , где каждая функция $$f_i$$ определена на $$В_n$$ и производит вывод в $$В_1 = \{0,1\}$$. Функция $$f_1$$ вычисляет первый бит функции f, функция $$f_2$$ вычисляет второй бит функции f , и так далее. По этой причине сосредоточим наше внимание на вычисления функция
Мы утверждаем, что любую булеву функцию можно выразить через элементарные функции {АND, OR, NOT}. В электронике булевы функции реализуются электрическими схемами, где присутствие напряжения в проводе представляет 1, а отсутствие - О. Представьте себе, что у нас есть набор ящичков, реализующих элементарные функции {АND, OR, NОТ}. Ящичек для АND имеет два провода на входе и один на выходе. Следствием нашего утверждения является то, что, используя элементарные ящички - стандартные схемные элементы (gates - "стандартный элемент"), можно построить процессор компьютера. Фактически так и строятся компьютеры сегодня за тем исключением, что вместо использования отдельных стандартных элементов для каждой элементарной булл
Покажем теперь на примере, как можно, используя элементарные функции {АND, OR, NОТ} выразить функцию $$f : В_3 \to В_1$$, заданную следующей таблицей истинности:
Рассмотрим вторую строку таблицы, которая говорит, что функция имеет значение 1, когда х = 0, у = 0, z = 1. Если построить конъюнкцию: $$\bar x \bigwedge \bar y \bigwedge z$$, то она также будет иметь значение 1 на этом наборе переменных и будет иметь значение 0 на всех остальных наборах значений х, у, z. Рассмотрим и все другие строки таблицы, где функция f имеет значение 1. Это происходит, когда (х = 0, у = 1, z = 1) и (х = 1, у = 0, z = 0). Конъюнкции, которые генерируют 1 для этих наборов переменных, имеют вид: $$\bar x \bigwedge y \bigwedge z$$ и $$x \bigwedge \bar y \bigwedge \bar z$$
Если теперь построить дизъюнкцию трех сформированных конъюнкций, то получим:
$$(\bar x \bigwedge \bar y \bigwedge z) \bigvee (\bar x \bigwedge y \bigwedge z) \bigvee (x \bigwedge \bar y \bigwedge \bar z)$$Это выражение называется совершенной дизъюнктивной нормальной формой (ДНФ) функции f . ДНФ генерирует для всех наборов х, у, z такие же значения, которые представлены в таблице истинности функции f . Ясно, что этот подход работает для любой булевой функции. Мы получили следующую
Теорема. Любая булева функция $$f : В_n \to В_1$$ может быть выражена через элементарные функции {АND, OR, NOT} в виде ДНФ.
При проектировании логической схемы следует минимизировать число логических элементов, что позволяет уменьшить стоимость, затраты энергии, увеличить быстродействие. ДНФ, способные реализовать любую булеву функцию, обычно не дают оптимального решения. Проиллюстрируем это на следующем примере.
Рассмотрим функцию f , которая реализует сложение двух 2-битных целых: $$f (х_1х_0, у_1у_0) = х_{1х0} + у_{1у0} = z_2z_1z_0$$. Эта функция принимает 4 бита на входе (мы отделяем запятой два бита только для удобства чтения) и возвращает 3 бита на выходе. Поскольку сумма двух 2-битных значений может давать 3-битный результат, то на выходе всегда возвращаются 3 бита. Например, 3+2 = 5, что в бинарном представлении имеет вид: 11+10 = 101, f (1110) = 101.
Используя сложение целых в бинарной форме, функцию f можно задать следующей таблицей:
Мы можем функцию f рассматривать как три функции, каждая из которых вычисляет один бит результата: $$z_2(х_1х_0, у_1у_0),\; z_1(x_1x_0, y_1y_0),\; z_0(x_1x_0, y_1y_0)$$.
Давайте оценим сложность ДНФ для этих трех функций. В качестве меры сложности примем сумму конъюнкций и дизъюнкций в ДНФ. Для простоты будем пренебрегать числом отрицаний в ДНФ (эта операция менее дорогая в реализации).
Для функций $$z_1$$ и $$z_0$$ значение 1 встречается в 8 строках таблицы, для функции $$z_2 -6$$ раз. Следовательно, сложность ДНФ для функций $$z_1$$ и $$z_0$$ равна 8 х 3+ 7 = 31, а для функции $$z_2 - 23$$.
Сложность ДНФ неоправданно велика, поскольку не учитывает никакую внутреннюю логику, свойственную функции.
Например, $$z_0$$ вычисляет сумму последних битов, которая определяет ее четность, зависящую от четности аргументов суммы. Сумма двух четных - четна, четного и нечетного - нечетна, двух нечетных - четна. Следовательно, $$z_0$$ зависит только от $$х_0$$ и $$у_0$$ и может быть задана следующей формулой:
$$z_0=(\bar x_0 \bigwedge y_0) \bigvee (x_0 \bigwedge \bar y_0)$$Сложность выражения в этой формуле равна 3, что значительно меньше 31- сложности ДНФ для $$z_0$$.
Когда нам нужно сложить два больших числа, то мы не пользуемся "таблицей сложения", как это было сделано в примере сложения 2-битных чисел, а пользуемся методом сложения "в столбик". Этот метод работает и для бинарных чисел, например, сложение 45 + 57 = 102 в бинарной форме имеет вид:
Переносы указаны в верхней строке.
Представим выше приведенную булеву формулу для сложения двух битов по модулю 2 следующей схемой: Для упрощения диаграмм представим
данную схему как один стандартный элемент "+ ". Тогда булева функция: а + b + с mod 2 может быть реализована схемой:
Еще одна операция, которая нам необходима для реализации длинного сложения "столбиком", - это вычисление переноса, который появляется, когда мы складываем 3 бита (два входных бита и бит переноса из предыдущего разряда). Заметьте, что при сложении а + b + с перенос появляется только тогда, когда по крайней мере два бита имеют значение 1, так что функция переноса может быть задана следующим выражением: $$(а \bigwedge b) \bigvee (а \bigwedge с) \bigvee (b \bigwedge с)$$ со сложностью 5. Функцию можно упростить и представить в виде: $$а \bigwedge (b \bigvee с) \bigvee (b \bigwedge с)$$ со сложностью 4. Схема для функции переноса имеет вид:
Теперь мы можем представить схему сложения двух 2-битных целых. Для упрощения диаграммы схемы для функции: а + b + с mod 2 и функции переноса будем рассматривать как стандартные элементы:
Заметьте, вычисление переноса для частного случая а + b дается формулой $$а \bigwedge b$$.
В заключение приведем схему для вычисления $$z_2, z_1, z_0$$ в $$х_{1х0} + у_{1y0} = z_2z_1z_0$$.
Вычисляя сложность данного стандартного элемента, можно видеть, что общая сложность этой схемы равна 1 + 3 + 6 + 4 = 14, что много лучше, чем 31 + 31 +23 = 85 - сложности, задаваемой ДНФ.
Выполнение компьютерной программы сводится к последовательности выполнения команд - базисных операций, выполняемых процессором компьютера. Сегодняшние процессоры компьютера мощные и могут выполнять достаточно сложные команды. Для нашего анализа разумно вернуться к корням компьютерных вычислений и обсудить простейшие базисные операции, достаточные для построения компьютера. Таких операций три: АND, ОR, NОТ. Первые две - бинарные операции над двумя аргументами, операция NОТ - унарная, у нее один аргумент.
Логика является источником этих операций. Значения бита интерпретируются как True/Fa1se, где х = 1 интерпретируется как "х истинно" (Тrue), а х = 0 означает "х - ложно" (Fa1se). Тогда х АND у означает "х и у оба истинны", х ОR у означает "или х - истинно, или у - истинно, или х и у оба истинны". Эти операции называются булевыми операциями, названными так в честь Джорджа нуля - математика 19-го столетия, положившего начало оснований символической логики.
Приведем следующие истинностные таблицы этих логических операций:
Далее будем использовать более короткую нотацию "$$х \bigwedge y$$ " для " х AND у", " $$х \bigvee y$$ " для "х ОR у" и "$$\bar x$$" для "NОТ х". Функция АND называется также конъюнкцией, ОR - дизъюнкцией.
Утверждение. Операции Булевой логики удовлетворяют следующим свойствам - законам логики:
(1) $$\overline{x \bigwedge y}=\bar x \bigvee \bar y$$,
(2) $$\overline{x \bigvee y}=\bar x \bigwedge \bar y$$,
(З) $$\bar \bar x=x$$,
(4) $$x \bigwedge (y \bigvee z)=(x \bigwedge y) \bigvee (x\bigwedge z)$$,
(5) $$x \bigvee (y \bigwedge z)=(x \bigvee y) \bigwedge (x \bigvee z)$$.
Доказательство этих свойств оставляем в качестве упражнения.
При вычисления логических выражений важен порядок выполнения операций. Полагается, что AND выполняется раньше, чем OR, также как в арифметических выражениях умножение имеет более высокий приоритет чем сложение. Так что выражение $$x \bigwedge y \bigvee z \bigwedge w$$ понимается как $$(x \bigwedge y) \bigvee (z \bigwedge w)$$, а выражение $$x \bigvee y \bigwedge z \bigvee w$$ эквивалентно $$x \bigvee (y \bigwedge z) \bigvee w$$.
Пример. Давайте выразим функцию х = у через функции базиса. По определению эквивалентности (равенства), либо оба х и у имеют значение Тruе, либо оба - Fa1se. Это можно выразить так:
Пример. Давайте выразим функциями базиса отношение между числами: 2-битное целое $$х_1х_0$$ больше чем 2-битное целое $$у_1у_0$$. Построенная логическая функция должна давать 1, если $$х_{1х0} > у_1у_0$$ и 0 в противном случае. Неравенство выполняется, если $$х_1 > у_1$$ либо $$х_1 = у_1$$ и $$х_0 > у_0$$ Неравенство "$$х_1 > у_1$$" означает, что $$х_1 = 1$$ и $$у_1 = 0$$. Выражение для равенства было приведено в предыдущем примере. Комбинируя, получим формулу булевой алгебры, вычисляющую эту функцию:
$$x_1 \bigwedge \bar y_1 \bigvee (x_1 \bigwedge y_1 \bigvee \bar x_1 \bigwedge \bar y_1) \bigwedge x_0 \bigwedge \bar y_0$$Как ранее отмечалось, любое классическое вычисление может рассматриваться как функция $$f : В_n \to В_k$$ . Такая функция может быть заменена k функциями $$f_1,f_2, \dots, f_k$$ , где каждая функция $$f_i$$ определена на $$В_n$$ и производит вывод в $$В_1 = \{0,1\}$$. Функция $$f_1$$ вычисляет первый бит функции f, функция $$f_2$$ вычисляет второй бит функции f , и так далее. По этой причине сосредоточим наше внимание на вычисления функция
Мы утверждаем, что любую булеву функцию можно выразить через элементарные функции {АND, OR, NOT}. В электронике булевы функции реализуются электрическими схемами, где присутствие напряжения в проводе представляет 1, а отсутствие - О. Представьте себе, что у нас есть набор ящичков, реализующих элементарные функции {АND, OR, NОТ}. Ящичек для АND имеет два провода на входе и один на выходе. Следствием нашего утверждения является то, что, используя элементарные ящички - стандартные схемные элементы (gates - "стандартный элемент"), можно построить процессор компьютера. Фактически так и строятся компьютеры сегодня за тем исключением, что вместо использования отдельных стандартных элементов для каждой элементарной булл
Покажем теперь на примере, как можно, используя элементарные функции {АND, OR, NОТ} выразить функцию $$f : В_3 \to В_1$$, заданную следующей таблицей истинности:
Рассмотрим вторую строку таблицы, которая говорит, что функция имеет значение 1, когда х = 0, у = 0, z = 1. Если построить конъюнкцию: $$\bar x \bigwedge \bar y \bigwedge z$$, то она также будет иметь значение 1 на этом наборе переменных и будет иметь значение 0 на всех остальных наборах значений х, у, z. Рассмотрим и все другие строки таблицы, где функция f имеет значение 1. Это происходит, когда (х = 0, у = 1, z = 1) и (х = 1, у = 0, z = 0). Конъюнкции, которые генерируют 1 для этих наборов переменных, имеют вид: $$\bar x \bigwedge y \bigwedge z$$ и $$x \bigwedge \bar y \bigwedge \bar z$$
Если теперь построить дизъюнкцию трех сформированных конъюнкций, то получим:
$$(\bar x \bigwedge \bar y \bigwedge z) \bigvee (\bar x \bigwedge y \bigwedge z) \bigvee (x \bigwedge \bar y \bigwedge \bar z)$$Это выражение называется совершенной дизъюнктивной нормальной формой (ДНФ) функции f . ДНФ генерирует для всех наборов х, у, z такие же значения, которые представлены в таблице истинности функции f . Ясно, что этот подход работает для любой булевой функции. Мы получили следующую
Теорема. Любая булева функция $$f : В_n \to В_1$$ может быть выражена через элементарные функции {АND, OR, NOT} в виде ДНФ.
При проектировании логической схемы следует минимизировать число логических элементов, что позволяет уменьшить стоимость, затраты энергии, увеличить быстродействие. ДНФ, способные реализовать любую булеву функцию, обычно не дают оптимального решения. Проиллюстрируем это на следующем примере.
Рассмотрим функцию f , которая реализует сложение двух 2-битных целых: $$f (х_1х_0, у_1у_0) = х_{1х0} + у_{1у0} = z_2z_1z_0$$. Эта функция принимает 4 бита на входе (мы отделяем запятой два бита только для удобства чтения) и возвращает 3 бита на выходе. Поскольку сумма двух 2-битных значений может давать 3-битный результат, то на выходе всегда возвращаются 3 бита. Например, 3+2 = 5, что в бинарном представлении имеет вид: 11+10 = 101, f (1110) = 101.
Используя сложение целых в бинарной форме, функцию f можно задать следующей таблицей:
Мы можем функцию f рассматривать как три функции, каждая из которых вычисляет один бит результата: $$z_2(х_1х_0, у_1у_0),\; z_1(x_1x_0, y_1y_0),\; z_0(x_1x_0, y_1y_0)$$.
Давайте оценим сложность ДНФ для этих трех функций. В качестве меры сложности примем сумму конъюнкций и дизъюнкций в ДНФ. Для простоты будем пренебрегать числом отрицаний в ДНФ (эта операция менее дорогая в реализации).
Для функций $$z_1$$ и $$z_0$$ значение 1 встречается в 8 строках таблицы, для функции $$z_2 -6$$ раз. Следовательно, сложность ДНФ для функций $$z_1$$ и $$z_0$$ равна 8 х 3+ 7 = 31, а для функции $$z_2 - 23$$.
Сложность ДНФ неоправданно велика, поскольку не учитывает никакую внутреннюю логику, свойственную функции.
Например, $$z_0$$ вычисляет сумму последних битов, которая определяет ее четность, зависящую от четности аргументов суммы. Сумма двух четных - четна, четного и нечетного - нечетна, двух нечетных - четна. Следовательно, $$z_0$$ зависит только от $$х_0$$ и $$у_0$$ и может быть задана следующей формулой:
$$z_0=(\bar x_0 \bigwedge y_0) \bigvee (x_0 \bigwedge \bar y_0)$$Сложность выражения в этой формуле равна 3, что значительно меньше 31- сложности ДНФ для $$z_0$$.
Когда нам нужно сложить два больших числа, то мы не пользуемся "таблицей сложения", как это было сделано в примере сложения 2-битных чисел, а пользуемся методом сложения "в столбик". Этот метод работает и для бинарных чисел, например, сложение 45 + 57 = 102 в бинарной форме имеет вид:
Переносы указаны в верхней строке.
Представим выше приведенную булеву формулу для сложения двух битов по модулю 2 следующей схемой: Для упрощения диаграмм представим
данную схему как один стандартный элемент "+ ". Тогда булева функция: а + b + с mod 2 может быть реализована схемой:
Еще одна операция, которая нам необходима для реализации длинного сложения "столбиком", - это вычисление переноса, который появляется, когда мы складываем 3 бита (два входных бита и бит переноса из предыдущего разряда). Заметьте, что при сложении а + b + с перенос появляется только тогда, когда по крайней мере два бита имеют значение 1, так что функция переноса может быть задана следующим выражением: $$(а \bigwedge b) \bigvee (а \bigwedge с) \bigvee (b \bigwedge с)$$ со сложностью 5. Функцию можно упростить и представить в виде: $$а \bigwedge (b \bigvee с) \bigvee (b \bigwedge с)$$ со сложностью 4. Схема для функции переноса имеет вид:
Теперь мы можем представить схему сложения двух 2-битных целых. Для упрощения диаграммы схемы для функции: а + b + с mod 2 и функции переноса будем рассматривать как стандартные элементы:
Заметьте, вычисление переноса для частного случая а + b дается формулой $$а \bigwedge b$$.
В заключение приведем схему для вычисления $$z_2, z_1, z_0$$ в $$х_{1х0} + у_{1y0} = z_2z_1z_0$$.
Вычисляя сложность данного стандартного элемента, можно видеть, что общая сложность этой схемы равна 1 + 3 + 6 + 4 = 14, что много лучше, чем 31 + 31 +23 = 85 - сложности, задаваемой ДНФ.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.