Учебное пособие предназначено для студентов-бакалавров, по направлениям "Информатика и вычислительная техника", "Программная инженерия", "Информационная безопасность", студентов, обучающихся по специальности "Применение и эксплуатация автоматизированных систем специального назначения" и схожим направлениям и специальностям на начальном периоде обучения.
Вычислительная техника базируется на логических, арифметических и схемотехнических основах. Без их знания, а особенно без представления их взаимосвязи невозможно представить те глубинные процессы, которые в настоящее время обеспечивают взрывное характер развития этой области науки и техники.
Для изучения данного учебного пособия, с одной стороны, не требуется каких-либо специальных знаний, но, с другой стороны, пособие призвано показать, как традиционные понятия и алгоритмы, преломляются при проектировании реальных вычислительных устройств в зависимости от тех целей, которые перед этим устройством ставятся: минимизация оборудования или используемой элементной базы, минимизация времени выполнения какой-либо команды или упрощения используемого устройства управления, АЛУ и других критериев.
В пособии приводятся основные понятия алгебры логики. Особое внимание уделяется тем элементарным логическим функциям, которые находят наибольшее распространение в ЭВМ: конъюнкция, дизъюнкция, штрих Шеффера, стрелка Пирса, сумма по модулю два и их основным эквивалентностям.
Рассматриваются различные подходы к одному из важнейших для вычислительной техники вопросов математической логики – минимизации логических функций. Рассмотрены вопросы минимизации функций алгебры логики на основе теоремы Квайна, минимизирующих карт (диаграмм Вейча), метода Квайна – МакКласки, а также минимизации не полностью определённых логических функций.
Дано схемотехническое представление элементов, выполняющих основные операции функций алгебры логики, а также некоторых других основных элементов ЭВМ, знание функционирования которых позволит лучше понять выполнение арифметических операций в компьютере, а также функционирование компьютера в целом.
При рассмотрении арифметических основ ЭВМ даны понятия системы счисления, определены правила перевода смешанных чисел между различными системами счисления. Особое внимание уделено часто встречающемуся в вычислительной технике механизму быстрого перевода чисел между системами счисления с основаниями, связанными между собой соотношениями p = q±2, например, 16=24. Представлены диапазоны, погрешности и, соответственно, области применения чисел с фиксированной запятой, фиксированной точкой, плавающей запятой.
Рассмотрены формы представления чисел в прямом, обратном и дополнительном кодах и методики выполнения основных арифметических операций в различных кодах, а также особые случаи, возникающие при выполнении этих операций. Показано, как влияет использование того или иного алгоритма выполнения арифметической операции на структуру ЭВМ и ее производительность.
Весь материал проиллюстрирован большим количеством примеров, которые позволят на практике закрепить изложенные в пособии теоретические положения.
Знание изложенного материала поможет в дальнейшем легче осваивать дисциплины, связанные с аппаратной реализацией современных средств вычислительной техники: схемотехнику, построение запоминающих устройств, интерфейсы, архитектуру микропроцессоров и другие курсы.
Высказыванием называется утверждение, о котором можно определенно сказать, истинно оно или ложно. Высказываний одновременно истинных и ложных не бывает.
Высказывания бывают простыми и сложными. Простые отдельные высказывания – это логические переменные, их принято обозначать буквами латинского алфавита. Логическая (булева) переменная –эта такая величина x, которая может принимать только два значения: "Истина" или "Ложь". Например, если простое высказывание x истинно, то x = true, если же ложно, то x = false.
Для простоты последующей обработки логических выражений, переменные чаще всего выражают цифрами:
x = 1, если высказывание истинно, и
x = 0, если высказывание ложно.
В дальнейшем мы будем именно такой формой представления логических переменных.
Функция ƒ(x1, x2, ..., xn) называется логической (переключательной), или булевой, если она, так же как и ее аргументы xi, может принимать только два значения: "истина" или "ложь".
Логические функции могут быть описаны различными способами:
Рассмотрим эти формы представления функции алгебры логики (ФАЛ).
Чаще всего встречаются табличная форма представления логической функции (в виде таблицы истинности) и ее аналитическое представление (например, в виде дизъюнктивных или конънктивных форм). Рассмотрим некоторые формы представления ФАЛ.
Прежде всего, определимся с понятием "элементарная логическая функция". Чаще всего,это понятие в литературе никак не расшифровывается. В дальнейшем мы будем понимать под "элементарной логической функцией" ФАЛ от аргументов, каждый из которых, в свою очередь, не является логической функцией и которые имеют своё собственное обозначение.
Таблица истинности указывает значение логической функции при всех значениях наборов аргументов. Ниже мы рассмотрим элементарные логические функции от одной и двух переменных.
Все возможные элементарные логические функции от одной переменной представлены в Табл. 1.1:
| Функция | x | Наименование функции | Обозначение функции | |
|---|---|---|---|---|
| x=0 | x=1 | |||
| ƒ0 | 0 | 0 | Константа "ноль" | ƒ(x)=0 |
| ƒ1 | 0 | 1 | Тождественная функция | ƒ(x)=x |
| ƒ2 | 1 | 0 | Отрицание | $$f(x)=\overline{x}$$ |
| ƒ3 | 1 | 1 | Константа "единица" | ƒ(x)=1 |
Здесь интерес представляет лишь одна функция – отрицание. Опишем ее основные свойства:
$$\overline{0}= 1$$ $$\overline{1}= 0$$ $$\overline{\overline{x}}= x$$Последнее свойств можно описать как "отрицание отрицания есть утверждение".
Все возможные логические функции от двух переменных представлены в Табл. 1.2:
№ функции | Значение функции на наборах логических переменных | Наименование функции | Обозначение функции | |||
x=0 y=0 | x=1 y=0 | x=0 y=1 | x=1 y=1 | |||
ƒ0 | 0 | 0 | 0 | 0 | Константа "ноль" | ƒ(x,y)=0 |
ƒ1 | 0 | 0 | 0 | 1 | Конъюнкция | ƒ(x,y)=xy $$f(x,y)=x \wedge y$$ $$f(x,y)= x \cdot y$$ ƒ(x,y)=xy |
ƒ2 | 0 | 0 | 1 | 0 | Запрет по y | xΔy |
ƒ3 | 0 | 0 | 1 | 1 | x | ƒ(x,y)=x |
ƒ4 | 0 | 1 | 0 | 0 | Запрет по x | yΔx |
ƒ5 | 0 | 1 | 0 | 1 | y | ƒ(x,y)=y |
ƒ6 | 0 | 1 | 1 | 0 | Сумма по mod2(неравнозначность) | $$f(x,y)=x \oplus y$$ |
ƒ7 | 0 | 1 | 1 | 1 | Дизъюнкция | ƒ(x,y)=x v y ƒ(x,y)=x+y |
ƒ8 | 1 | 0 | 0 | 0 | Стрелка Пирса (Вебба) | ƒ(x,y)=x↓y ƒ(x,y)=xОy |
ƒ9 | 1 | 0 | 0 | 1 | Равнозначность | ƒ(x,y)=x≡y ƒ(x,y)=x∞y |
ƒ10 | 1 | 0 | 1 | 0 | Инверсия y | ƒ(x,y)=^y $$f(x,y)=\overline{y}$$ |
ƒ11 | 1 | 0 | 1 | 1 | Импликация от y к x | ƒ(x,y)=y→x |
ƒ12 | 1 | 1 | 0 | 0 | Инверсия x | ƒ(x,y)=^x $$f(x,y)=\overline{x}$$ |
ƒ13 | 1 | 1 | 0 | 1 | Импликация от х к y | ƒ(x,y)=x→y |
ƒ14 | 1 | 1 | 1 | 0 | Штрих Шеффера | ƒ(x,y)=x/y |
ƒ15 | 1 | 1 | 1 | 1 | Константа "единица" | ƒ(x,y)=1 |
Общее количество функций от n переменных равно: $$2^{2^{n}}$$
Уже на примере этой таблицы, где мы можем перечислить все возможные логические функции от двух переменных, видно, что существуют переменные, от которых ФАЛ меняет свое значение на каких-либо наборах, и переменные, при изменении которое значение функции не меняетсяни на каких наборах переменных.
В первом случае переменную называют фиктивной, а во втором – существенной.
Так, например, для функции ƒ12(x,y) логическая переменная x является существенной, а логическая переменная y – фиктивной.
Рассмотрим теперь логические функции, играющие наибольшую роль в вычислительной технике, и их основные свойства.
Эквивалентность ФАЛ.
Логические функции являются эквивалентными, если их значения совпадают для всех допустимых наборов аргументов. Так как аргументами ФАЛ являются логические переменные, которые могут принимать только два значения ("Истина" либо "Ложь", которые, как было сказано выше, обычно обозначаются "1" и "0"), то доказательство эквивалентности логических функций сводится к сравнению их таблиц истинности.
| х | y | xy |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Основные свойства:
0 0 = 0
0 1 = 0
1 1 = 1
0 x = 0
1 x = x
$$x \And \overline{x} = 0$$
x x ... x = x
x y = y x
x y z = (x y) z = x (y z)
Для более легкого запоминания этой функции следует придерживаться правила: функция конъюнкции ложна, если ложен хотя бы один из ее операндов. Это правило действует для функции, содержащей произвольное число операндов. Если обозначать значение "истина" как "1", а значение "ложь" как "0", то эта функция будет похожа на математическую функцию умножения. Поэтому ее зачастую называют функцией логического умножения.
Отметим, что для конъюнкции, так же как и для следующей рассматриваемой функции – дизъюнкции – действуют ассоциативный (сочетательный) и коммуникативный (переместительный) законы.
В то же время для некоторых других логических функций тот или иной закон не действует. Некоторые из примеров таких функций мы рассмотрим ниже.
Покажем, например, что $$x \And \overline{x} = 0$$.
Как уже говорилось ранее, основным доказательством эквивалентности двух функций служит тот факт, что они имеют одинаковые таблицы истинности на всех наборах аргументов.
Но в данном случае можно поступить проще. Так как функция зависит только от одной логической переменной, которая может принимать только значения "0" или "1" и, то в рассматриваемом выражении один из операндов всегда будет равен "0" (при x =0 $$\overline{x} =$$"1", а при x = 1 $$\overline{x} = 0$$).Учитывая, что 0 x = 0, получаем, что рассматриваемые функции эквивалентны.
| х | y | x v y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Основные свойства:
0 v 0 = 0
0 v 1 = 1
1 v 1 = 1
0 v x = x
1 v x = 1
$$x \vee \overline{x} = 1$$x v x = x
x v x v...v x = x
x v y = y v x
x v y v z = (x v y) v z = x v (y v z)
Для более легкого запоминания этой функции следует придерживаться правила: функция дизъюнкции истинна, если истенен хотя бы один из ее операндов. Это правило действует для функции, содержащей произвольное число операндов. Если обозначать значение "истина" как "1", а значение "ложь" как "0", то эта функция для двух операндов будет похожа на математическую функцию поразрядного сложения. Поэтому ее зачастую называют функцией логическогосложения. Хотя здесь следует иметь в виду, что в логическом сложении сигнал переноса в более старший разряд не вырабатывается.
| х | y | x / y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Основные свойства:
0/0 = 1
0/1 = 1
1/1 = 0
0/x = 1
$$1/x = \overline{x}$$x/y = y/x
x/(y/z) ≠ (x/y)/z
Иногда ФАЛ "Штрих Шеффера" называют операцией "И-НЕ". И действительно, для двух переменных это так. Но если мы будем использовать большее количество переменных, то соотношение нарушается.
И, в то же время, для трёх и более переменных таблица истинности ФАЛ "Штрих Шеффера" совпадает с таблицей истинности функции "И-НЕ". Поэтому иногда в литературе можно встретить мнение о том, что операция "Штрих Шеффера" применима лишь для двух переменных. В остальных случаях следует говорить об операции "И-НЕ", при которой сначала выполняется конъюнкция всех переменных, от которых зависит ФАЛ, а затем проводится операция "НЕ" над полученным результатом.
Таким образом, для любого числа переменных функция "Штрих Шеффер" истинна, если хотя бы один из используемых аргументов ложен.
Покажем, что логическая функция x/(y/z) не эквивалентна ФАЛ (x/y)/z, то есть, что функции штрих Шеффера не действует сочетательный закон. Для этого построим таблицу истинности для первой и второй ФАЛ.
| x | y | z | x/y | (x/y)/z |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| x | y | z | y/z | x/(y/z) |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
Как мы видим, таблицы истинности для первой и второй функций не совпадают, то есть эти функции не эквивалентны.
Также приведём таблицу истинности ФАЛ "И-НЕ" для трех переменных.
| x | y | z | xyz | "И-НЕ"(x,y,z) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
| х | y | x↓y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
В некоторых источниках можно встретить разночтения в названии и обозначении этой ФАЛ. Иногда ее называют элементом Вэбба, иногда обозначают вертикально вверх направленной стрелкой. Мы в дальнейшем эту логическую функцию будем называть стрелкой Пирса и обозначать стрелкой, направленной вертикально вниз.
Свойства
0↓0 = 1
0↓1 = 0
1↓1 = 0
0↓x =x
1↓x = 0
x↓y=y↓x
x↓(y↓z) ≠ (x↓y)↓z
В отношении этой функции можно сказать примерно то же самое, что было сказано по поводу ФАЛ "Штрих Шеффера": для функции от двух переменных она эквивалентна функции "ИЛИ-НЕ". В то же время ассоциативный закон для нее не выполняется.
Прервем на немного рассмотрение отдельных функций и расскажем о правилах, которые зачастую помогаю существенно упростить то или иное логическое выражение.
Правила де Моргана
x1 x2 ... xn = x1 v x2 v ... xn
x1 v x2 v ... xn = x1 x2 ... xn
Или, описывая эти преобразования словесно, можно сказать, что "отрицание конъюнкций есть дизъюнкция отрицаний" и, в свою очередь, "отрицание дизъюнкций есть конъюнкция отрицаний".
Этими правилами мы будем в дальнейшем часто пользоваться.
При минимизации логических функций используются следующие эквивалентные преобразования.
Операция склеивания:
$$xy \vee x \overline{y} = x$$ $$(x\vee y) \And (x\vee\overline{y}) = x$$Операция неполного склеивания:
$$xy\vee x\overline{y} = x\vee xy\vee x\overline{y} $$ $$(x\vee y)\And (x \vee\overline{y}) = x \And (x\vee y)\And (x\vee\overline{y})$$Операция поглощения:
x v xy = x
x v xy = x
Казалось бы, что операция неполного склеивания не имеет отношение к минимизации, так как получаемое выражение больше исходного. Однако, эта операция играет очень важную роль при минимизации, что бы позднее покажем.
А пока покажем эквивалентность, например, одной из операций склеивания:
$$(x\vee y) \And (x\vee \overline{y}) = x$$ $$f_{1} = (x\vee y) \And (x\vee \overline{y})$$Ее таблица истинности имеет вид:
| х | y | x v y | $$\overline{y}$$ | $$x \vee \overline{y}$$ | ƒ1(x,y) |
| 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
Это соответствует таблице истинности ƒ2(x,y) = x.
А теперь рассмотрим еще одну функцию, играющую важную роль в арифметических и логических основах ЭВМ.
Таблица истинности:
| x | y | $$x \oplus y$$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Свойства:
$$0 \oplus 0 = 0$$ $$0 \oplus 1 = 1$$ $$1 \oplus 1 = 0 $$ $$0 \oplus x = x$$ $$1 \oplus x =\overline{x}$$ $$x \oplus y = y \oplus x$$ $$(x \oplus y) \oplus z = x \oplus (y \oplus z)$$Если об остальных рассмотренных выше логических функциях мы еще поговорим подробнее в следующих лекциях, то функцию "Сумма по модулю 2" (неравнозначность) хотелось бы поговорить здесь поподробнее, так она является основой для реализации устройств контроля и защиты информации, что будет рассматриваться позднее в соответствующих разделах учебного плана.
Рассмотрим ее применение на примере передачи информации.
Пусть мы хотим передать некоторые данные, например, код 11001100. Перед началом передачи код дополняется контрольным разрядом, который дополняет количество единиц в нем до четного числа (в некоторых реализациях – до нечетного числа). В нашем примере контрольный разряд будет равен 0. Фактически на этом этапе выполняется операция суммирования по модулю 2 с учетом последнего представленного свойства этой ФАЛ. Контрольный разряд передается вместе с основным кодом.
Если в процессе передачи произойдет искажение одного разряда (например, последний разряд кода примет значение 1), то приемное устройство примет код 11001101 и контрольный разряд "0", равный исходному (там искажения нет). Приемное устройство вычисляет контрольный разряд от принятого кода (теперь он будет равен "1"), сравнивает его с принятым контрольным разрядом (они не совпадают) и сообщает об ошибке в передаче данных. Обычно после этого передача повторяется.
Для защиты передаваемой информации необходимо использовать так называемый ключ защиты, который должен быть у пере-дающей и принимающей стороны. Пусть в нашем случае таким ключом защиты будет код 01101101. Суммируя по модулю 2 поразрядно передаваемый код и код защиты, получим, что передаваться будет код 10100001, который отличается от исходного кода. Даже если в случае несанкционированного доступа эта информация будет перехвачена, она ничего не даст злоумышленнику. В то же время, принимающая сторона, имея тот же самый ключ защиты, восстановит исходную информацию.
Логическая функция может быть представлена несколькими способами, каждый из которых наиболее эффективен для той или иной области применения. Рассмотрим ситуацию, когда логическая функция представлена в виде суперпозиции элементарных логических функций, а для последующей ее обработки, например, для построения некоторого схемотехнического устройства, необходимо иметь представление функции в виде таблицы истинности.
Пример 1.1. Представить таблицу истинности следующей логической функции:
$$f(x,y,z) = \overline{x} z \oplus \overline {y \overline{z} \vee xyz}$$Сначала примем во внимание приоритеты логических операций.
Логические операции выполняются в следующем порядке:
Естественно, что порядок выполнения операций можно изменять посредством применения скобок.
Проведем в соответствии с этим порядком вычисление указанной выше функции.
| x | y | z | $$\overline{x}$$ | $$\overline{x}z$$ | $$\overline{z}$$ | $$y\overline{z}$$ | xyz | $$y\overline{z}\vee xyz$$ | $$\overline{y\overline{z}\vee xyz}$$ | $$\overline{x} z \oplus \overline{y \overline{z} \vee xyz}$$ |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
В лекции рассматриваются основные понятия математической логики: высказывание, логическая переменная, логическая функция. Приведены элементарные логические функции от одной и двух переменных. Даны основные свойства тех из них, которые наиболее часто востребованы при построении средств вычислительной техники: конъюнкции, дизъюнкции, штриха Шеффера, стрелки Пирса и некоторых других. Представлены некоторые эквивалентности логических функций. Показ порядок вычисления логических функций путем построения для них таблицы истинности.
Учебное пособие предназначено для студентов-бакалавров, по направлениям "Информатика и вычислительная техника", "Программная инженерия", "Информационная безопасность", студентов, обучающихся по специальности "Применение и эксплуатация автоматизированных систем специального назначения" и схожим направлениям и специальностям на начальном периоде обучения.
Вычислительная техника базируется на логических, арифметических и схемотехнических основах. Без их знания, а особенно без представления их взаимосвязи невозможно представить те глубинные процессы, которые в настоящее время обеспечивают взрывное характер развития этой области науки и техники.
Для изучения данного учебного пособия, с одной стороны, не требуется каких-либо специальных знаний, но, с другой стороны, пособие призвано показать, как традиционные понятия и алгоритмы, преломляются при проектировании реальных вычислительных устройств в зависимости от тех целей, которые перед этим устройством ставятся: минимизация оборудования или используемой элементной базы, минимизация времени выполнения какой-либо команды или упрощения используемого устройства управления, АЛУ и других критериев.
В пособии приводятся основные понятия алгебры логики. Особое внимание уделяется тем элементарным логическим функциям, которые находят наибольшее распространение в ЭВМ: конъюнкция, дизъюнкция, штрих Шеффера, стрелка Пирса, сумма по модулю два и их основным эквивалентностям.
Рассматриваются различные подходы к одному из важнейших для вычислительной техники вопросов математической логики – минимизации логических функций. Рассмотрены вопросы минимизации функций алгебры логики на основе теоремы Квайна, минимизирующих карт (диаграмм Вейча), метода Квайна – МакКласки, а также минимизации не полностью определённых логических функций.
Дано схемотехническое представление элементов, выполняющих основные операции функций алгебры логики, а также некоторых других основных элементов ЭВМ, знание функционирования которых позволит лучше понять выполнение арифметических операций в компьютере, а также функционирование компьютера в целом.
При рассмотрении арифметических основ ЭВМ даны понятия системы счисления, определены правила перевода смешанных чисел между различными системами счисления. Особое внимание уделено часто встречающемуся в вычислительной технике механизму быстрого перевода чисел между системами счисления с основаниями, связанными между собой соотношениями p = q±2, например, 16=24. Представлены диапазоны, погрешности и, соответственно, области применения чисел с фиксированной запятой, фиксированной точкой, плавающей запятой.
Рассмотрены формы представления чисел в прямом, обратном и дополнительном кодах и методики выполнения основных арифметических операций в различных кодах, а также особые случаи, возникающие при выполнении этих операций. Показано, как влияет использование того или иного алгоритма выполнения арифметической операции на структуру ЭВМ и ее производительность.
Весь материал проиллюстрирован большим количеством примеров, которые позволят на практике закрепить изложенные в пособии теоретические положения.
Знание изложенного материала поможет в дальнейшем легче осваивать дисциплины, связанные с аппаратной реализацией современных средств вычислительной техники: схемотехнику, построение запоминающих устройств, интерфейсы, архитектуру микропроцессоров и другие курсы.
Высказыванием называется утверждение, о котором можно определенно сказать, истинно оно или ложно. Высказываний одновременно истинных и ложных не бывает.
Высказывания бывают простыми и сложными. Простые отдельные высказывания – это логические переменные, их принято обозначать буквами латинского алфавита. Логическая (булева) переменная –эта такая величина x, которая может принимать только два значения: "Истина" или "Ложь". Например, если простое высказывание x истинно, то x = true, если же ложно, то x = false.
Для простоты последующей обработки логических выражений, переменные чаще всего выражают цифрами:
x = 1, если высказывание истинно, и
x = 0, если высказывание ложно.
В дальнейшем мы будем именно такой формой представления логических переменных.
Функция ƒ(x1, x2, ..., xn) называется логической (переключательной), или булевой, если она, так же как и ее аргументы xi, может принимать только два значения: "истина" или "ложь".
Логические функции могут быть описаны различными способами:
Рассмотрим эти формы представления функции алгебры логики (ФАЛ).
Чаще всего встречаются табличная форма представления логической функции (в виде таблицы истинности) и ее аналитическое представление (например, в виде дизъюнктивных или конънктивных форм). Рассмотрим некоторые формы представления ФАЛ.
Прежде всего, определимся с понятием "элементарная логическая функция". Чаще всего,это понятие в литературе никак не расшифровывается. В дальнейшем мы будем понимать под "элементарной логической функцией" ФАЛ от аргументов, каждый из которых, в свою очередь, не является логической функцией и которые имеют своё собственное обозначение.
Таблица истинности указывает значение логической функции при всех значениях наборов аргументов. Ниже мы рассмотрим элементарные логические функции от одной и двух переменных.
Все возможные элементарные логические функции от одной переменной представлены в Табл. 1.1:
| Функция | x | Наименование функции | Обозначение функции | |
|---|---|---|---|---|
| x=0 | x=1 | |||
| ƒ0 | 0 | 0 | Константа "ноль" | ƒ(x)=0 |
| ƒ1 | 0 | 1 | Тождественная функция | ƒ(x)=x |
| ƒ2 | 1 | 0 | Отрицание | $$f(x)=\overline{x}$$ |
| ƒ3 | 1 | 1 | Константа "единица" | ƒ(x)=1 |
Здесь интерес представляет лишь одна функция – отрицание. Опишем ее основные свойства:
$$\overline{0}= 1$$ $$\overline{1}= 0$$ $$\overline{\overline{x}}= x$$Последнее свойств можно описать как "отрицание отрицания есть утверждение".
Все возможные логические функции от двух переменных представлены в Табл. 1.2:
№ функции | Значение функции на наборах логических переменных | Наименование функции | Обозначение функции | |||
x=0 y=0 | x=1 y=0 | x=0 y=1 | x=1 y=1 | |||
ƒ0 | 0 | 0 | 0 | 0 | Константа "ноль" | ƒ(x,y)=0 |
ƒ1 | 0 | 0 | 0 | 1 | Конъюнкция | ƒ(x,y)=xy $$f(x,y)=x \wedge y$$ $$f(x,y)= x \cdot y$$ ƒ(x,y)=xy |
ƒ2 | 0 | 0 | 1 | 0 | Запрет по y | xΔy |
ƒ3 | 0 | 0 | 1 | 1 | x | ƒ(x,y)=x |
ƒ4 | 0 | 1 | 0 | 0 | Запрет по x | yΔx |
ƒ5 | 0 | 1 | 0 | 1 | y | ƒ(x,y)=y |
ƒ6 | 0 | 1 | 1 | 0 | Сумма по mod2(неравнозначность) | $$f(x,y)=x \oplus y$$ |
ƒ7 | 0 | 1 | 1 | 1 | Дизъюнкция | ƒ(x,y)=x v y ƒ(x,y)=x+y |
ƒ8 | 1 | 0 | 0 | 0 | Стрелка Пирса (Вебба) | ƒ(x,y)=x↓y ƒ(x,y)=xОy |
ƒ9 | 1 | 0 | 0 | 1 | Равнозначность | ƒ(x,y)=x≡y ƒ(x,y)=x∞y |
ƒ10 | 1 | 0 | 1 | 0 | Инверсия y | ƒ(x,y)=^y $$f(x,y)=\overline{y}$$ |
ƒ11 | 1 | 0 | 1 | 1 | Импликация от y к x | ƒ(x,y)=y→x |
ƒ12 | 1 | 1 | 0 | 0 | Инверсия x | ƒ(x,y)=^x $$f(x,y)=\overline{x}$$ |
ƒ13 | 1 | 1 | 0 | 1 | Импликация от х к y | ƒ(x,y)=x→y |
ƒ14 | 1 | 1 | 1 | 0 | Штрих Шеффера | ƒ(x,y)=x/y |
ƒ15 | 1 | 1 | 1 | 1 | Константа "единица" | ƒ(x,y)=1 |
Общее количество функций от n переменных равно: $$2^{2^{n}}$$
Уже на примере этой таблицы, где мы можем перечислить все возможные логические функции от двух переменных, видно, что существуют переменные, от которых ФАЛ меняет свое значение на каких-либо наборах, и переменные, при изменении которое значение функции не меняетсяни на каких наборах переменных.
В первом случае переменную называют фиктивной, а во втором – существенной.
Так, например, для функции ƒ12(x,y) логическая переменная x является существенной, а логическая переменная y – фиктивной.
Рассмотрим теперь логические функции, играющие наибольшую роль в вычислительной технике, и их основные свойства.
Эквивалентность ФАЛ.
Логические функции являются эквивалентными, если их значения совпадают для всех допустимых наборов аргументов. Так как аргументами ФАЛ являются логические переменные, которые могут принимать только два значения ("Истина" либо "Ложь", которые, как было сказано выше, обычно обозначаются "1" и "0"), то доказательство эквивалентности логических функций сводится к сравнению их таблиц истинности.
| х | y | xy |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Основные свойства:
0 0 = 0
0 1 = 0
1 1 = 1
0 x = 0
1 x = x
$$x \And \overline{x} = 0$$
x x ... x = x
x y = y x
x y z = (x y) z = x (y z)
Для более легкого запоминания этой функции следует придерживаться правила: функция конъюнкции ложна, если ложен хотя бы один из ее операндов. Это правило действует для функции, содержащей произвольное число операндов. Если обозначать значение "истина" как "1", а значение "ложь" как "0", то эта функция будет похожа на математическую функцию умножения. Поэтому ее зачастую называют функцией логического умножения.
Отметим, что для конъюнкции, так же как и для следующей рассматриваемой функции – дизъюнкции – действуют ассоциативный (сочетательный) и коммуникативный (переместительный) законы.
В то же время для некоторых других логических функций тот или иной закон не действует. Некоторые из примеров таких функций мы рассмотрим ниже.
Покажем, например, что $$x \And \overline{x} = 0$$.
Как уже говорилось ранее, основным доказательством эквивалентности двух функций служит тот факт, что они имеют одинаковые таблицы истинности на всех наборах аргументов.
Но в данном случае можно поступить проще. Так как функция зависит только от одной логической переменной, которая может принимать только значения "0" или "1" и, то в рассматриваемом выражении один из операндов всегда будет равен "0" (при x =0 $$\overline{x} =$$"1", а при x = 1 $$\overline{x} = 0$$).Учитывая, что 0 x = 0, получаем, что рассматриваемые функции эквивалентны.
| х | y | x v y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Основные свойства:
0 v 0 = 0
0 v 1 = 1
1 v 1 = 1
0 v x = x
1 v x = 1
$$x \vee \overline{x} = 1$$x v x = x
x v x v...v x = x
x v y = y v x
x v y v z = (x v y) v z = x v (y v z)
Для более легкого запоминания этой функции следует придерживаться правила: функция дизъюнкции истинна, если истенен хотя бы один из ее операндов. Это правило действует для функции, содержащей произвольное число операндов. Если обозначать значение "истина" как "1", а значение "ложь" как "0", то эта функция для двух операндов будет похожа на математическую функцию поразрядного сложения. Поэтому ее зачастую называют функцией логическогосложения. Хотя здесь следует иметь в виду, что в логическом сложении сигнал переноса в более старший разряд не вырабатывается.
| х | y | x / y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Основные свойства:
0/0 = 1
0/1 = 1
1/1 = 0
0/x = 1
$$1/x = \overline{x}$$x/y = y/x
x/(y/z) ≠ (x/y)/z
Иногда ФАЛ "Штрих Шеффера" называют операцией "И-НЕ". И действительно, для двух переменных это так. Но если мы будем использовать большее количество переменных, то соотношение нарушается.
И, в то же время, для трёх и более переменных таблица истинности ФАЛ "Штрих Шеффера" совпадает с таблицей истинности функции "И-НЕ". Поэтому иногда в литературе можно встретить мнение о том, что операция "Штрих Шеффера" применима лишь для двух переменных. В остальных случаях следует говорить об операции "И-НЕ", при которой сначала выполняется конъюнкция всех переменных, от которых зависит ФАЛ, а затем проводится операция "НЕ" над полученным результатом.
Таким образом, для любого числа переменных функция "Штрих Шеффер" истинна, если хотя бы один из используемых аргументов ложен.
Покажем, что логическая функция x/(y/z) не эквивалентна ФАЛ (x/y)/z, то есть, что функции штрих Шеффера не действует сочетательный закон. Для этого построим таблицу истинности для первой и второй ФАЛ.
| x | y | z | x/y | (x/y)/z |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| x | y | z | y/z | x/(y/z) |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
Как мы видим, таблицы истинности для первой и второй функций не совпадают, то есть эти функции не эквивалентны.
Также приведём таблицу истинности ФАЛ "И-НЕ" для трех переменных.
| x | y | z | xyz | "И-НЕ"(x,y,z) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
| х | y | x↓y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
В некоторых источниках можно встретить разночтения в названии и обозначении этой ФАЛ. Иногда ее называют элементом Вэбба, иногда обозначают вертикально вверх направленной стрелкой. Мы в дальнейшем эту логическую функцию будем называть стрелкой Пирса и обозначать стрелкой, направленной вертикально вниз.
Свойства
0↓0 = 1
0↓1 = 0
1↓1 = 0
0↓x =x
1↓x = 0
x↓y=y↓x
x↓(y↓z) ≠ (x↓y)↓z
В отношении этой функции можно сказать примерно то же самое, что было сказано по поводу ФАЛ "Штрих Шеффера": для функции от двух переменных она эквивалентна функции "ИЛИ-НЕ". В то же время ассоциативный закон для нее не выполняется.
Прервем на немного рассмотрение отдельных функций и расскажем о правилах, которые зачастую помогаю существенно упростить то или иное логическое выражение.
Правила де Моргана
x1 x2 ... xn = x1 v x2 v ... xn
x1 v x2 v ... xn = x1 x2 ... xn
Или, описывая эти преобразования словесно, можно сказать, что "отрицание конъюнкций есть дизъюнкция отрицаний" и, в свою очередь, "отрицание дизъюнкций есть конъюнкция отрицаний".
Этими правилами мы будем в дальнейшем часто пользоваться.
При минимизации логических функций используются следующие эквивалентные преобразования.
Операция склеивания:
$$xy \vee x \overline{y} = x$$ $$(x\vee y) \And (x\vee\overline{y}) = x$$Операция неполного склеивания:
$$xy\vee x\overline{y} = x\vee xy\vee x\overline{y} $$ $$(x\vee y)\And (x \vee\overline{y}) = x \And (x\vee y)\And (x\vee\overline{y})$$Операция поглощения:
x v xy = x
x v xy = x
Казалось бы, что операция неполного склеивания не имеет отношение к минимизации, так как получаемое выражение больше исходного. Однако, эта операция играет очень важную роль при минимизации, что бы позднее покажем.
А пока покажем эквивалентность, например, одной из операций склеивания:
$$(x\vee y) \And (x\vee \overline{y}) = x$$ $$f_{1} = (x\vee y) \And (x\vee \overline{y})$$Ее таблица истинности имеет вид:
| х | y | x v y | $$\overline{y}$$ | $$x \vee \overline{y}$$ | ƒ1(x,y) |
| 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
Это соответствует таблице истинности ƒ2(x,y) = x.
А теперь рассмотрим еще одну функцию, играющую важную роль в арифметических и логических основах ЭВМ.
Таблица истинности:
| x | y | $$x \oplus y$$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Свойства:
$$0 \oplus 0 = 0$$ $$0 \oplus 1 = 1$$ $$1 \oplus 1 = 0 $$ $$0 \oplus x = x$$ $$1 \oplus x =\overline{x}$$ $$x \oplus y = y \oplus x$$ $$(x \oplus y) \oplus z = x \oplus (y \oplus z)$$Если об остальных рассмотренных выше логических функциях мы еще поговорим подробнее в следующих лекциях, то функцию "Сумма по модулю 2" (неравнозначность) хотелось бы поговорить здесь поподробнее, так она является основой для реализации устройств контроля и защиты информации, что будет рассматриваться позднее в соответствующих разделах учебного плана.
Рассмотрим ее применение на примере передачи информации.
Пусть мы хотим передать некоторые данные, например, код 11001100. Перед началом передачи код дополняется контрольным разрядом, который дополняет количество единиц в нем до четного числа (в некоторых реализациях – до нечетного числа). В нашем примере контрольный разряд будет равен 0. Фактически на этом этапе выполняется операция суммирования по модулю 2 с учетом последнего представленного свойства этой ФАЛ. Контрольный разряд передается вместе с основным кодом.
Если в процессе передачи произойдет искажение одного разряда (например, последний разряд кода примет значение 1), то приемное устройство примет код 11001101 и контрольный разряд "0", равный исходному (там искажения нет). Приемное устройство вычисляет контрольный разряд от принятого кода (теперь он будет равен "1"), сравнивает его с принятым контрольным разрядом (они не совпадают) и сообщает об ошибке в передаче данных. Обычно после этого передача повторяется.
Для защиты передаваемой информации необходимо использовать так называемый ключ защиты, который должен быть у пере-дающей и принимающей стороны. Пусть в нашем случае таким ключом защиты будет код 01101101. Суммируя по модулю 2 поразрядно передаваемый код и код защиты, получим, что передаваться будет код 10100001, который отличается от исходного кода. Даже если в случае несанкционированного доступа эта информация будет перехвачена, она ничего не даст злоумышленнику. В то же время, принимающая сторона, имея тот же самый ключ защиты, восстановит исходную информацию.
Логическая функция может быть представлена несколькими способами, каждый из которых наиболее эффективен для той или иной области применения. Рассмотрим ситуацию, когда логическая функция представлена в виде суперпозиции элементарных логических функций, а для последующей ее обработки, например, для построения некоторого схемотехнического устройства, необходимо иметь представление функции в виде таблицы истинности.
Пример 1.1. Представить таблицу истинности следующей логической функции:
$$f(x,y,z) = \overline{x} z \oplus \overline {y \overline{z} \vee xyz}$$Сначала примем во внимание приоритеты логических операций.
Логические операции выполняются в следующем порядке:
Естественно, что порядок выполнения операций можно изменять посредством применения скобок.
Проведем в соответствии с этим порядком вычисление указанной выше функции.
| x | y | z | $$\overline{x}$$ | $$\overline{x}z$$ | $$\overline{z}$$ | $$y\overline{z}$$ | xyz | $$y\overline{z}\vee xyz$$ | $$\overline{y\overline{z}\vee xyz}$$ | $$\overline{x} z \oplus \overline{y \overline{z} \vee xyz}$$ |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
В лекции рассматриваются основные понятия математической логики: высказывание, логическая переменная, логическая функция. Приведены элементарные логические функции от одной и двух переменных. Даны основные свойства тех из них, которые наиболее часто востребованы при построении средств вычислительной техники: конъюнкции, дизъюнкции, штриха Шеффера, стрелки Пирса и некоторых других. Представлены некоторые эквивалентности логических функций. Показ порядок вычисления логических функций путем построения для них таблицы истинности.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.