Алгебра логики

Материал из ПИЭ.Wiki

Перейти к: навигация, поиск

Теоретической основой построения ЭВМ являются специальные математические дисциплины. Одной из них является алгебра логики, или булева алгебра (Дж. Буль - английский математик прошлого столетия, основоположник этой дисциплины). Ее аппарат широко используют для описания схем ЭВМ, их оптимизации и проектирования.

Содержание

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

Алгебра логики — определенная часть математической логики, часто называемая исчислением высказываний.

Под высказыванием понимается всякое предложение, в котором содержится смысл утверждения (истинности) или отрицания (ложности). Одно и то же высказывание не может быть одновременно истинным и ложным или не истинным и не ложным. Отдельные высказывания можно обозначить заглавными буквами латинского алфавита А, В, С,... . Если высказывание (суждение) истинно, то, например, А=1. Если С=0, то высказывание С ложно. Рассматриваются только два значения высказывания: истинное или ложное (1 или 0). Такое условие алгебры логики приводит к соответствию между логическими высказываниями в математической логике и двоичными цифрами в двоичной системе счисления, что позволяет описывать работу схем и блоков машины и проводить их анализ и синтез с помощью алгебры логики.

Поставим в соответствие входным сигналам отдельных устройств ЭВМ значения переменных xi (i = 1,n), а выходным сигналам - значения функций yj (j= 1,m) (рис. 1).

Файл:Лог.PNG

Рис. 1. Представление схемы ЭВМ

В этом случае зависимостями

yj = ƒ(x1,x2,…,xi,…,xn), (1)

где: xi - i-й вход; n - число входов; yj – j-й выход; m число выходов в устройстве, можно описывать алгоритм работы любого устройства ЭВМ. Каждая такая зависимость уj является булевой функцией, у которой число возможных состоянии равно двум, а ее аргументы определены на множестве {0,1}. Алгебра логики устанавливает основные законы формирования и преобразования логических функций. Она позволяет представить любую сложную функцию в виде композиции простейших функций. Рассмотрим наиболее употребительные из них.

Известно, что количество всевозможных функций N от n аргументов выражается зависимостью N = 2^2^n (2)

При n=0 можно определить две основные функции (N=2), не зависящие от каких-либо переменных: у0 , тождественно равную нулю (y0 ≡ 0), и y1, тождественно равную единице (y1 ≡ 1). Технической интерпретацией функции y1 ≡1 может быть генератор импульсов. При отсутствии входных сигналов на выходе этого устройства всегда имеются импульсы (единицы). Функция y0 ≡ 0 может быть интерпретирована отключенной схемой, сигналы от которой не поступают ни к каким устройствам. При n=1 зависимость (2) дает N=4. Представим зависимость значений этих функций от значения аргумента х в виде специальной таблицы истинности (табл. 1).

Таблица 1

Таблица функций от одной переменной

Файл:ЛогТабл1.PNG

Таблицы истинности получили такое название, потому что они определяют значение функции в зависимости от комбинации входных сигналов. В этой таблице, как и ранее, y0 ≡ 0 и y1 ≡ 1.Функция у2 = х, а функция у3 = ¬х (инверсия x;).

Этим функциям соответствуют определенные технические аналоги. Схема, реализующая зависимость у2 = х, называется повторителем, а схема у3 = ¬х - инвертором.

При n=2, N=16, т.е. от двух переменных можно построить шестнадцать различных функций, которые представлены в табл. 2.

Таблица 2

Таблица функций от двух переменных

Файл:ЛогТабл2.PNG

Заметим, что в левой части таблицы перечислены всевозможные комбинации входных переменных ( x – наборы значений), а в правой - возможные реакции выходных сигналов (f 0 – f 15).


Классифицируем данные булевы функции по следующим подгруппам:

I. Функции с фиктивными аргументами

f 0 = 0 – константа 0

f 15 = 1 – константа 1

f 10 = x1 – аргумент х1

f 12 = x2 – аргумент х2

f 5 = ¬x1 – отрицание аргумента х1

f 3 = ¬x2 – отрицание аргумента х2

Определение: Отрицанием высказывания А называется новое высказывание, которое обозначается ¬А, читается «не А» и считается истинным только в том случае, когда само высказывание ложно. II. Аналоги операций над высказываниями

1) f 14 = x1 v x2 – дизъюнкция

Определение: Дизъюнкцией двух высказываний А, В называется новое высказывание, которое обозначается А v В, читается «А или В», считается ложным, когда обе части ложные.

Файл:ЛогТабл3.PNG

2) f 8 = x1 ^ x2 – конъюнкция

Определение: Конъюнкцией двух высказываний А, В называется новое высказывание, которое обозначается А В, читается «А и В» и считается истинным только в том случае, когда обе части истинны.

Файл:ЛогТабл4.PNG

3) f 13 = x1 -> x2 – импликация

Определение: Импликацией двух высказываний А и В называется новое высказывание, которое обозначается А -> В, читается «если А, то В» и считается истинным только в том случае, когда посылка высказывания (А) – истина, а заключение (В) – ложно.

Файл:ЛогТабл5.PNG

4) f 9 = x1 <-> x2 – эквиваленция Определение: Эквиваленцией двух высказываний А и В называется новое высказывание, которое обозначается А <-> В, читается «А тогда и только тогда, когда В» и считается истинным, когда А и В имеют одинаковые оценки.

Файл:ЛогТабл6.PNG

III. Функции, близкие к импликации

1) f 11 = x2 <- x1 – обратная импликация

2) f 2 = x1 ∆ x2 – функция запрета

Определение: Запретом двух высказываний А и В называется новое высказывание, которое обозначается А ∆ В, читается «отрицание импликации» и считается истинным, только в том случае, когда посылка высказывания (А) – истина, а заключение (В) – ложно.

Файл:ЛогТабл7.PNG

3) f 4 = x2 ∆ x1 – обратный запрет

IV. Стрелка Пирса

f 1 = x1 \|/ x2

Определение: Стрелкой Пирса называется функция двух переменных, которая обозначается x1 \|/ x2, читается «отрицание дизъюнкции» и считается истинной тогда и только тогда, когда оба аргумента ложны.

Файл:ЛогТабл8.PNG

V. Штрих Шеффера

f 7 = x1|x2

Определение: Штрихом Шеффера называется функция двух переменных, которая обозначается x1|x2, читается «отрицание конъюнкции» и считается ложной тогда и только тогда, когда оба аргумента истинны.

Файл:ЛогТабл9.PNG

VI. Сложение по модулю 2

f 6 = x1 + x2 Определение: Сложением по модулю 2 называется функция двух переменных, которая обозначается x1 + x2, читается «отрицание эквиваленции» и считается ложной тогда и только тогда, когда оба аргумента принимают одинаковые значения.

Файл:ЛогТабл10.PNG


Из перечисленных функций двух переменных можно строить сколь угодно сложные зависимости, отражающие алгоритмы преобразования информации, представленной в двоичной системе счисления. Алгебра логики устанавливает правила формирования логически полного базиса простейших функций, из которых могут строиться любые более сложные. Наиболее привычным базисом является набор трех функций: инверсия - ¬ , дизъюнкция - v, конъюнкция - ^ или &. Работа с функциями, представленными в этом базисе, очень похожа на использование операций обычной алгебры.

Алгебра логики устанавливает, что существуют и другие комбинации простейших логических функций, обладающих свойством логической полноты. Например, наборы логических функций {инверсия, дизъюнкция} и {инверсия, конъюнкция} также являются логически полными. Наиболее интересны минимальные базисы, включающие по одной операции {"отрицание дизъюнкции (¬v)"} и {"отрицание конъюнкции (¬^)"}. Однако работа с функциями, представленными в указанных базисах, требует от специалистов по проектированию ЭВМ определенных навыков.

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

Из определения вышеприведенных функций можно установить целый ряд простейших свойств:

Файл:ЛогЗ1.PNG


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

• коммутативный (переместительный):

Файл:ЛогЗ2.PNG

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

Файл:ЛогЗ3.PNG

Эти законы полностью идентичны законам обычной алгебры;

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

Файл:ЛогЗ4.PNG

• закон поглощения.

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

Файл:ЛогЗ5.PNG

• законы склеивания:

Файл:ЛогЗ6.PNG

где F - логическая функция общего вида, не зависящая от переменной х;

• закон свертки:

Файл:ЛогЗ7.PNG

• правило де Моргана:

Файл:ЛогЗ8.PNG

• избавление от импликации и эквиваленции:

Файл:ЛогЗ9.PNG

• избавление от стрелки Пирса:

Файл:ЛогЗ10.PNG

• избавление от штриха Шеффера:

Файл:ЛогЗ11.PNG

• избавление от запрета:

Файл:ЛогЗ12.PNG

• избавление от сложения по модулю 2:

Файл:ЛогЗ13.PNG

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

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


Понятие о минимизации логических функций

Проблема минимизации логических функций решается на основе применения законов склеивания и поглощения с последующим перебором получаемых дизъюнктивных форм и выбором из них оптимальной (минимальной). Существует большое количество методов минимизации логических функций. Все они отличаются друг от друга спецификой применения операций склеивания и поглощения, а также различными способами сокращения переборов. Среди аналитических методов наиболее известным является метод Квайна - МакКласки, среди табличных - метод с применением диаграмм Вейча. Графические методы минимизации отличаются большей наглядностью и меньшей трудоемкостью, однако их применение эффективно при малом числе переменных n ≤5.


Технический способ задания функции алгебры логики

Определение: Функциональным элементом называется всякое техническое устройство с n входами х1, х2, …, хn и одним выходом y, обладающим двумя устойчивыми состояниями, которые кодируются символами 0 и 1.

Файл:Лог1.PNG Файл:Лог2.PNG

Константа «0»                  Конъюнкция                  Запрет х1                 Повторение х1                 Запрет х2                 Повторение х2


Файл:Лог3.PNG Файл:Лог4.PNG

Сложение по модулю 2       Дизъюнкция          Стрелка Пирса              Эквиваленция             Отрицание х2              Импликация х1


Файл:Лог5.PNG Файл:Лог6.PNG

      Отрицание х1              Импликация х2         Штрих Шеффера      Константа «1»


Техническая интерпретация логических функций

По логическим выражениям проектируются схемы ЭВМ. При этом надо придерживаться определенной последовательности действий.

1. Словесное описание работы схемы.

2. Формализация словесного описания.

3. Запись функций в дизъюнктивной (конъюнктивной) совершенной нормальной форме по таблицам истинности.

4. Минимизация логических зависимостей с целью их упрощения.

5. Представление полученных выражений в выбранном логически полном базисе элементарных функций.

6. Построение схемы устройства.

7. Проверка работоспособности полученной схемы.


Литература:

А.П. Пятибратов, А.С. Касаткин, Р.В. Можаров. «Электронно-вычислительные машины в управлении». – СПб.: «Питер», 1997

Киркинский А.С. Функции алгебры логики: Учебное пособие./Алт. политехн. ин-т им.И.И.Ползунова. -Барнаул, 1989

Просмотры
Инструменты

Besucherzahler russian mail order brides
счетчик посещений
Rambler's Top100
Лингафонные кабинеты  Интерактивные доски  Интерактивная приставка Mimio Teach