Логические основы построения ЭВМ

Начало исследований в области формальной логики было положено работами Аристотеля в IVв. до н.э.

Аппарат алгебры логики (булевой алгебры) создан в 1854г. Джорджем Булем, как попытка изучения логики мышления математическими методами.

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

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

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

Высказывание – любое утверждение, в отношении которого можно однозначно сказать истинно оно или ложно.

Исходные высказывания называют простыми, а образованные из них другие высказывания – сложными.

Значение истинности (True) обозначают 1, значение ложности (False) – 0.

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

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

Истинность полученных высказываний зависит от исходных высказываний и использованных для их преобразования логических операций.

1. Инверсия («НЕ», NOT) – отрицание.

Обозначается Логические основы построения ЭВМ - student2.ru или Х и читается как «не икс».

Если высказывание Х истинно, то Логические основы построения ЭВМ - student2.ru – ложно, и наоборот.

Логические основы построения ЭВМ - student2.ru Х

2. Дизъюнкция («ИЛИ», OR) – логическое сложение.

Обозначается Логические основы построения ЭВМ - student2.ru или |

Сложное высказывание Х1 Логические основы построения ЭВМ - student2.ru Х2 истинно, если истинно хотя бы одно из входящих в него простых высказываний.

Х1 Х2 Х1 Логические основы построения ЭВМ - student2.ru Х2

3. Конъюнкция («И», AND) – логическое умножение.

Обозначается Логические основы построения ЭВМ - student2.ru или &

Сложное высказывание Х1 Логические основы построения ЭВМ - student2.ru Х2 истинно только в том случае, когда истинны оба входящих в него простых высказывания.

Х1 Х2 Х1 Логические основы построения ЭВМ - student2.ru Х2

4. Импликация – логическое следование.

Обозначается →

Сложное высказывание Х1 → Х2 ложно, если Х1 = 1, а Х2 = 0, и истинно во всех остальных случаях.

Х1 Х2 Х1 →Х2

5. Эквиваленция – равнозначность.

Обозначается ~ или ↔

Сложное высказывание Х1 ↔ Х2 истинно, если Х1 и Х2 = 0 или 1, и ложно во всех остальных случаях.

Х1 Х2 Х1 ↔Х2

6. Сумма по mod 2 – неравнозначность.

Обозначается Логические основы построения ЭВМ - student2.ru

Сложное высказывание Х1 Логические основы построения ЭВМ - student2.ru Х2 истинно тогда и только тогда, когда истинно одно высказывание, и ложно во всех остальных случаях.

Х1 Х2 Х1 Логические основы построения ЭВМ - student2.ru Х2

Приоритет выполнения логических операций: , Логические основы построения ЭВМ - student2.ru , Логические основы построения ЭВМ - student2.ru , →, ↔, Логические основы построения ЭВМ - student2.ru

Логические выражения вычисляются с помощью таблиц истинности.

Правила составления таблицы истинности:

1. Определить n – число переменных, входящих в сложное высказывание.

2. Число строк в таблице истинности равно 2n + 2(строки заголовка)

3. Определить k – число логических операций.

4. Число столбцов в таблице истинности равно n + k.

5. Столбцы переменных заполнить всеми возможными значениями простых переменных

для 1-го столбца 2n/21

для 2-го столбца 2n/22 и т.д.

6. Определить значения логического выражения в соответствии с порядком выполнения логических операций.

Пример:

Составить таблицу истинности для сложного высказывания F(A, B, C) = ((B Логические основы построения ЭВМ - student2.ru A) Логические основы построения ЭВМ - student2.ru C) Логические основы построения ЭВМ - student2.ru A

Число переменных n = 3. Тогда число строк в таблице = 23 + 2 = 10

Число логических операций k = 4. Тогда число столбцов = n + k = 7

Заполняем первые три столбца значениями переменных:

А столбец 2n/21 = 8/2 = 4 – чередование 4 нулей и 4 единиц.

B столбец 2n/22 = 8/4 = 2 – чередование 2 нулей и 2 единиц.

С столбец 2n/23 = 8/8 = 1 – чередование 1 нуля и 1 единицы.

А В С B Логические основы построения ЭВМ - student2.ru А или (2 Логические основы построения ЭВМ - student2.ru 1) (B Логические основы построения ЭВМ - student2.ru A) Логические основы построения ЭВМ - student2.ru C или (4 Логические основы построения ЭВМ - student2.ru 3) A или (1) F(A, B, C) или((B Логические основы построения ЭВМ - student2.ru A) Логические основы построения ЭВМ - student2.ru C) Логические основы построения ЭВМ - student2.ru A или (5 Логические основы построения ЭВМ - student2.ru 6)

Функцией алгебры логики (ФАЛ) от набора входных переменных F(X1, X2,…,Xn) называется функция, которая на каждом из этих наборов принимает либо 0-е значение либо 1-е значение.

Общее число различных значений логических функций от n аргументов равно Логические основы построения ЭВМ - student2.ru .

ФАЛ от 2-х аргументов:

Х1  
Х2  
F0 Константа «ноль» F(X1, X2)=0
F1 Конъюнкция F(X1, X2)= Х1 Логические основы построения ЭВМ - student2.ru Х2
F2 Запрет по Х2 F(X1, X2)= Х1 ∆ Х2
F3 Переменная Х1 F(X1, X2)= Х1
F4 Запрет по Х1 F(X1, X2)= Х2 ∆ Х1
F5 Переменная Х2 F(X1, X2)= Х2
F6 Сложение по mod 2 F(X1, X2)= Х1 Логические основы построения ЭВМ - student2.ru Х2
F7 Дизъюнкция F(X1, X2)= Х1 Логические основы построения ЭВМ - student2.ru Х2
F8 Стрелка Пирса F(X1, X2)= Х1 ↓ Х2= Логические основы построения ЭВМ - student2.ru
F9 Эквиваленция F(X1, X2)= Х1 ↔ Х2
F10 Инверсия Х2 F(X1, X2)= Х2
F11 Импликация от Х2 к Х1 (левая) F(X1, X2)= Х2 → Х1
F12 Инверсия Х1 F(X1, X2)= Х1
F13 Импликация от Х1 к Х2 F(X1, X2)= Х1 → Х2
F14 Штрих Шеффера F(X1, X2)= Х1 | Х2= Логические основы построения ЭВМ - student2.ru
F15 Константа «единица» F(X1, X2)=1

Табличное представление логических функций является наглядным, но при большом числе n переменных становится очень громоздким. Значительно проще выглядит аналитическая запись ФАЛ в виде формул.

Широкое распространение получили так называемые нормальные формы представления ФАЛ. В их основе лежат элементарные дизъюнкции и конъюнкции.

Элементарная дизъюнкция представляет собой дизъюнкцию конечного числа переменных и их инверсий. Например, X Логические основы построения ЭВМ - student2.ru Y, X Логические основы построения ЭВМ - student2.ru Y, X Логические основы построения ЭВМ - student2.ru Y. Конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой(КНФ). Например, F(КНФ)= (X Логические основы построения ЭВМ - student2.ru Y) Логические основы построения ЭВМ - student2.ru (X Логические основы построения ЭВМ - student2.ru Y).

Элементарная конъюнкция представляет собой конъюнкцию конечного числа переменных и их инверсий. Например, X Логические основы построения ЭВМ - student2.ru Y, X Логические основы построения ЭВМ - student2.ru Y, X Логические основы построения ЭВМ - student2.ru Y. Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой(ДНФ). Например, (X Логические основы построения ЭВМ - student2.ru Y) Логические основы построения ЭВМ - student2.ru (X Логические основы построения ЭВМ - student2.ru Y).

Одну и ту же ФАЛ можно представить различными ДНФ и КНФ. Однозначность представления ФАЛ возможна при записи их в совершенных нормальных формах.

Совершенной КНФ(СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием). Например, (X1 Логические основы построения ЭВМ - student2.ru X2 Логические основы построения ЭВМ - student2.ru X3) Логические основы построения ЭВМ - student2.ru (X1 Логические основы построения ЭВМ - student2.ru X2 Логические основы построения ЭВМ - student2.ru X3).

Совершенной ДНФ(СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием). Например, (X1 Логические основы построения ЭВМ - student2.ru X2 Логические основы построения ЭВМ - student2.ru X3) Логические основы построения ЭВМ - student2.ru (X1 Логические основы построения ЭВМ - student2.ru X2 Логические основы построения ЭВМ - student2.ru X3).

СДНФ образуется на тех наборах переменных, на которых функция равна 1. Те переменные, которые в данном наборе равны 0, записываются с отрицанием (инверсией), а которые равны 1 – без отрицания.

Переход от табличной формы функции к СДНФ или правило записи функции по единицам:

1. Выбрать те наборы аргументов, на которых f(X1, X2,…Xn)=1.

2. Выписать все конъюнкции ( Логические основы построения ЭВМ - student2.ru ) для этих наборов. Если при этом Xi имеет значение «1», то этот множитель пишется в прямом виде, если «0», то с отрицанием.

3. Все конъюнктивные члены соединить знаком дизъюнкции ( Логические основы построения ЭВМ - student2.ru ).

Пример:

X1 X2 f(X1,X2)

Логические основы построения ЭВМ - student2.ru

СКНФ образуется на тех наборах переменных, на которых функция равна 0. Те переменные, которые в данном наборе равны 1, записываются с отрицанием (инверсией), а которые равны 0 – без инверсии.

Правило перехода от табличной формы задания функции к СКНФ или правило записи функции по нулям:

1. Выбрать те наборы аргументов, на которых f(X1, X2,…Xn)=0.

2. Выписать все дизъюнкции ( Логические основы построения ЭВМ - student2.ru ) для этих наборов. Если при этом Xi имеет значение «0», то этот множитель пишется в прямом виде, если «1», то с отрицанием.

3. Все дизъюнктивные члены соединить знаком конъюнкции ( Логические основы построения ЭВМ - student2.ru ).

Пример:

X1 X2 f(X1,X2)

Логические основы построения ЭВМ - student2.ru

Пример:

X1 X2 X3 f(X1, X2, X3)

СДНФ: Логические основы построения ЭВМ - student2.ru

СКНФ:

Логические основы построения ЭВМ - student2.ru

Способ получения СДНФ из СКНФ и обратно.

Пример:

X1 X2 f(X1, X2)

Из таблицы с помощью способа записи функции по нулям следует, что СКНФ той же функции дизъюнкции будет иметь вид: Логические основы построения ЭВМ - student2.ru

СДНФ функции: Логические основы построения ЭВМ - student2.ru

Получаем две формы одной и той же функции:

Логические основы построения ЭВМ - student2.ru

Общее число членов в этих двух формах равно сумме нулей и единиц функции, то есть равно 2n.

Если в исходной форме функции, записанной в СКНФ или СДНФ, содержится z членов, то в другой ее форме (т.е. СДНФ или СКНФ) их будет (2n-z).

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

Алгебра логики определяется следующей системой аксиом:

Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru

Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru

Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru

Если в аксиомах произвести взаимную замену операций дизъюнкции и конъюнкции, а также элементов 0 и 1, то из одной аксиомы данной пары получается другая. Это свойство называется принципом двойственности.

С помощью аксиом можно получить ряд тождеств:

Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru

Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru

Законы алгебры логики:

1. Переместительный (коммутативный): Логические основы построения ЭВМ - student2.ru

2. Сочетательный (ассоциативный): Логические основы построения ЭВМ - student2.ru

3. Распределительный (дистрибутивный): Логические основы построения ЭВМ - student2.ru

4. Двойственности (де Моргана): Логические основы построения ЭВМ - student2.ru

5. Двойного отрицания: Логические основы построения ЭВМ - student2.ru

6. Поглощения: Логические основы построения ЭВМ - student2.ru

7. Склеивания: Логические основы построения ЭВМ - student2.ru

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

Первичное упрощение ФАЛ заключается в преобразовании функций так, чтобы она содержала только операции «НЕ», «И», «ИЛИ».

Логические основы построения ЭВМ - student2.ru

Пример:

Логические основы построения ЭВМ - student2.ru

Логические основы построения ЭВМ - student2.ru

Методы минимизации логических функций:

1. Метод непосредственных преобразований основан на последовательном исключении переменных исходного выражения на основе законов алгебры логики.

2. Метод минимизирующих карт Карно.

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

Карты Карно для двух аргументов:

  Y Логические основы построения ЭВМ - student2.ru
X Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru
Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru

Карты Карно для трех аргументов:

  Логические основы построения ЭВМ - student2.ru X
Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru
Z Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru
  Логические основы построения ЭВМ - student2.ru Y Логические основы построения ЭВМ - student2.ru

В клетки карт Карно заносятся единицы для тех наборов переменных, для которых минимизируемая функции принимает единичное значение (по заданной таблице истинности).

Правила применения карт Карно:

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

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

3. Конъюнкции, соответствующие оставшимся единицам, сохраняются без изменения.

Пример:

Задана таблица истинности F(X, Y, Z)

X Y Z F(X, Y, Z)

СДНФ: Логические основы построения ЭВМ - student2.ru

Карты Карно для этой функции:

  Логические основы построения ЭВМ - student2.ru X
Логические основы построения ЭВМ - student2.ru       Логические основы построения ЭВМ - student2.ru
Z   Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru Логические основы построения ЭВМ - student2.ru
  Логические основы построения ЭВМ - student2.ru Y Логические основы построения ЭВМ - student2.ru

Или:

  Логические основы построения ЭВМ - student2.ru X
Логические основы построения ЭВМ - student2.ru      
Z  
  Логические основы построения ЭВМ - student2.ru Y Логические основы построения ЭВМ - student2.ru

В правом крайнем столбце этой карты соседним единицам соответствуют конъюнкции Логические основы построения ЭВМ - student2.ru и Логические основы построения ЭВМ - student2.ru , которые заменяются одной конъюнкцией на ранг меньше с одинаковыми показателями инверсии аргументов, т.е. Логические основы построения ЭВМ - student2.ru .

Две оставшихся единицы находятся на соседних клетках второй строки, поэтому соответствующие им конъюнкции Логические основы построения ЭВМ - student2.ru и Логические основы построения ЭВМ - student2.ru заменяются одной Логические основы построения ЭВМ - student2.ru .

Минимизированная СДНФ:

Логические основы построения ЭВМ - student2.ru

Наши рекомендации