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

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

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

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

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

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

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

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

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

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

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

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

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

Обозначается или Х и читается как «не икс».

Если высказывание Х истинно, то – ложно, и наоборот.

	Х

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

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

Сложное высказывание Х₁ Х₂ истинно, если истинно хотя бы одно из входящих в него простых высказываний.

Х1	Х2	Х1 Х2

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

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

Сложное высказывание Х₁ Х₂ истинно только в том случае, когда истинны оба входящих в него простых высказывания.

Х1	Х2	Х1 Х2

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

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

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

Х1	Х2	Х1 →Х2

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

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

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

Х1	Х2	Х1 ↔Х2

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

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

Сложное высказывание Х₁ Х₂ истинно тогда и только тогда, когда истинно одно высказывание, и ложно во всех остальных случаях.

Х1	Х2	Х1 Х2

Приоритет выполнения логических операций: , , , →, ↔,

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

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

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

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

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

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

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

для 1-го столбца 2ⁿ/2¹

для 2-го столбца 2ⁿ/2² и т.д.

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

Пример:

Составить таблицу истинности для сложного высказывания F(A, B, C) = ((B A) C) A

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

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

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

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

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

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

А	В	С	B А или (2 1)	(B A) C или (4 3)	A или (1)	F(A, B, C) или((B A) C) A или (5 6)

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

Общее число различных значений логических функций от n аргументов равно .

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

Х1
Х2
F0					Константа «ноль»	F(X1, X2)=0
F1					Конъюнкция	F(X1, X2)= Х1 Х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 Х2
F7					Дизъюнкция	F(X1, X2)= Х1 Х2
F8					Стрелка Пирса	F(X1, X2)= Х1 ↓ Х2=
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=
F15					Константа «единица»	F(X1, X2)=1

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

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

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

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

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

Совершенной КНФ(СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием). Например, (X₁ X₂ X₃) (X₁ X₂ X₃).

Совершенной ДНФ(СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием). Например, (X₁ X₂ X₃) (X₁ X₂ X₃).

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

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

1. Выбрать те наборы аргументов, на которых f(X₁, X₂,…X_n)=1.

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

3. Все конъюнктивные члены соединить знаком дизъюнкции ( ).

Пример:

X1	X2	f(X1,X2)

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

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

1. Выбрать те наборы аргументов, на которых f(X₁, X₂,…X_n)=0.

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

3. Все дизъюнктивные члены соединить знаком конъюнкции ( ).

Пример:

X1	X2	f(X1,X2)

Пример:

X1	X2	X3	f(X1, X2, X3)

СДНФ:

СКНФ:

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

Пример:

X1	X2	f(X1, X2)

Из таблицы с помощью способа записи функции по нулям следует, что СКНФ той же функции дизъюнкции будет иметь вид:

СДНФ функции:

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

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

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

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

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

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

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

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

1. Переместительный (коммутативный):

2. Сочетательный (ассоциативный):

3. Распределительный (дистрибутивный):

4. Двойственности (де Моргана):

5. Двойного отрицания:

6. Поглощения:

7. Склеивания:

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

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

Пример:

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

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

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

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

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

	Y
X

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

		X
Z
		Y

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

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

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

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

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

Пример:

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

X	Y	Z	F(X, Y, Z)

СДНФ:

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

		X
Z
		Y

Или:

		X
Z
		Y

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

Две оставшихся единицы находятся на соседних клетках второй строки, поэтому соответствующие им конъюнкции и заменяются одной .

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