Логические основы функционирования компьютеров

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

В основе алгебры логики лежат понятия зависимой и независимой переменных (функции и аргумента). Их отличия от соответствующих понятий обычной алгебры в том, чтопеременные могут принимать лишь одноиз двух значений: 0 или 1. Пусть x₁, х₂,..., х_n- двоичные аргументы, тогда функция y= f(x₁...x_n)является двоичной функцией двоичных аргументов, которая также может принимать значение либо 0, либо 1. Данная функция задается или аналитически, либо таблично. При табличном представлении значение функции должно быть задано на всех возможных наборах значений аргумента. Общее число этих наборов равно 2ⁿ,где n - число аргументов, а общее число всех возможных двоичных функций n двоичных аргументов будет 2²ⁿ.

Существует всего четыре функции одного двоичного аргумента, которые можно представить таблично или аналитически. Функция Y₀, принимающая нулевые значения на всех наборах, называ­ется константой нуля Y₀=0 (Y₀ тождественна 0).

Функция Y₁, значения которой совпадают со значениями аргу­мента, называется тавтологией, или повторением, и записывается ана­литически

Y₁= X (Y₁тождественна X).Функция, значения которой противоположны значениям аргумента, называется инверсией, или отри­цанием. В таблице такой функцией является Y₂=(Y₂тождествен­на не X).Черта над аргументом означает отрицание или инверсное значение. Значение Y₃ не изменяется при изменениях аргумента и всегда тождественно единице Y₃=1 Это функция константа единицы.

Рассмотрим двоичные функции двух (п=2) двоичных аргументов. Всего таких функций 16, каждая из которых определена на 2²=4 на­борах значений аргумента.

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

Функция Y₁=X₁ Λ X₂соответствует операции логического умно­жения и называется конъюнкцией. Знак Λ (или &) обозначает действие логического умножения. Иногда она обозначается как «·». Это действие выполняет устройство, которое называется автомат "И”. На схемах это устройство обозначается так:

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

Функция Y₇ = X₁ v X₂похожа (за исключением последней строки на операцию арифметического сложения и соответствует операции логического сложения (v - знак логического сложения). Данная функция называется дизъюнкцией и обращается в нуль только тогда, когда аргументы равны нулю, и в единицу - во всех остальных случаях. Это действие выполняет автомат "ИЛИ", имеющий следующее обозначение

Функции Y₁₂= ₁ и Y₁₀= ₂ соответствуют операции инверсии ( или отрицания) и выполняются автоматом "НЕ", со следующим обозначением.

Но если операции "И" и "ИЛИ" могут выполняться над произвольным числом аргументов n > 2, то операция «НЕ» всегда выполняется над одним аргументом.

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

Y₈=

Y₄=

Y₂=

Y₁=

Аналитически их записывают по следующему правилу. Из таблицы выбирается строка, в которой функция принимает единичное значение и для нее записывается конъюнкция всех аргументов. Если в строке аргумент имеет нулевое значение, то над ним выполняется еще операция отрицания.

Аналитическое выражение для любой заданной таблично двоичной функции можно записать с помощью совершенной дизъюнктивной нормальной формы (СДНФ). СДНФ - это дизъюнкция конституент единицы, записанных для тех наборов двоичных аргументов, на кото­рых функция принимает единичное значение. Пусть функция у= f(x₁,x₂,x₃) задана в виде нижеприведённой таблицы.

Аналитическая запись данной функции в СДНФ будет представлять дизъюнкцию трех конституент еди­ницы, записанных для 3,5и 6строк таблицы, т.е.

Y=

Таким образом, с помощью трех функций и соответствующих им трех логических действий можно записать или формально выразить любую логическую функцию. Другими словами, в алгебре логики опре­делено только три логических действия, никаких других действий нет. Порядок выполнения действий: сначала выполняется инверсия, затем конъюнкция и последним - дизъюнкция. Если есть скобки, то сначала выполняются операции в скобках.

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

x v 0 = x x v 1 =1 x v x = x x v = 1

x Λ 0 = 0 x Λ 1 = x x Λ x = x x Λ = 0

= x x v x v … v x = x x Λ x Λ … Λ x = x

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

Основные законы алгебры логики:

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

X₁V X₂=X₂V X₁

2. Сочетательный закон. Значение логического выражения не зависит от последовательности действий над логическими переменными.

X₁ X₂ X₃ = X₁ ( X₂ X₃) = (X₁ X₂) X₃

X₁ v X₂ v X₃ =(X₁ v X₂) V X₃ = X₁ v (X₂ v X₃)

3. Первый распределительный закон: X₁ (X₂ v X₃) = X₁X₂ v X₁X₃

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

4. Второй распределительный закон: X₁ v X₂X₃ = (X₁ v X₂)(X₁ v X₃)

5. Закон инверсии. Этот закон базируется на теореме де Моргана, которая формулируется следующим образом. При замене в исходной,
логической функции аргументов их отрицаниями, знаков логического
сложения знаками логического умножения, а знаков логического умножения знаками логического сложения получается функция, являющаяся
инверсной от исходной :

Указанные соотношения и законы позволяют проводить анализ и синтез логических схем, одним из этапов которых является построе­ние СДНФ. Рассмотрим способы образования СДНФ для заданных анали­тически логических выражений.

Первый способ заключается в том, что для заданной аналитичес­ки функции строится таблица истинности, из которой по рассмотрен­ному выше правилу записывается СДНФ.

Пример. Построить СДНФ для функции

Функция содержит три аргумента, для которых в таблице истин­ности заполняем 2³=8 строк. Подставляя входные наборы аргументов в заданную функцию, определяем значения Y.

Так, для первой строки Проводя ана­логичные действия для всех строк, заполняем столбец Y. Столбец для Y мог быть заполнен и исходя из анализа исходной функции. Так, функция Y будет принимать значение 1 в том случае, если X₃= 1 либо . Последнее тождество возможно, когда либо X₁ =0, либо X₂=0. Т.е. Y=1 на тех наборах, когда либо X₁=0,либо X₂ =0,либо X₃=1. Составив таблицу, СДНФ запишем как дизъюнкцию семи консти­туент единицы:

Второй способ образования СДНФ заключается в том, что:

· на основании теоремы де Моргана инверсии дизъюнкций и конъюнкций заменяются на конъюнкции и дизъюнкции инверсий аргу­ментов;

· раскрываются скобки во всех логических выражениях;

· образуются конституенты единицы домножением членов, не содержащих X_i , i= 1,2, … , n на с последующим раскрытием ско­бок;

· упорядочиваются соответствующие индексы во всех наборах аргументов.

Пример. Получить СДНФ для функции

Пользуясь теоремой де Моргана и проводя упрощения, получим

Домножим все члены на недостающее значение аргументов:

Раскрывая скобки и приводя подобные, СДНФ получим в виде