Булева алгебра и логические схемы компьютера

АО "Медицинский университет Астана"

Кафедра информатики, математики с курсом биостатистики

 

 

 

 

 

 

 

 

 

СРС

на тему: «Булева алгебра и  логические схемы компьютера»

 

 

 

                                                                           

                                                                   

    

 

 

 

 

 

 

 

 

 

   Выполнили: Бельгебаев  Ж.К. Нариман С.А,

                                                                             Группа: 136

Факультет: ОМ

                                                                            Проверила: Жунисова У.М.

 

 

 

                                             

 

 

 

 

 

Астана 2014 г.

СОДЕРЖАНИЕ

 

1.Введение…………………………………………………………………………3

2.Основная часть…………………………………………………………………..4

2.1.Булева алгебра и логические схемы компьютера…………………………...4

2.2.Основные функции математической логики: конъюнкция, дизъюнкция, инверсия…………………………………………………………………………...4

2.3.Таблицы значений логических функций…………………………………….5

2.4.Задание функций с помощью формул……………………………………….6

2.5.Функционально полная система логических функций……………………..7

2.6.Использование логических функций для создания запоминающего элемента (триггера)……………………………………………………………...12

2.7.Основные элементы ЦВМ и АВМ………………………………………….16

3.Заключение……………………………………………………………………..19

4.Литература……………………………………………………………………..20

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. ОСНОВНАЯ ЧАСТЬ

 

2.1.Булева алгебра и логические схемы компьютера

 

Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

Что же собой представляет алгебра логики? Во-первых, она изучает методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Во-вторых, булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два значения: 0, либо 1.

Что такое простое логическое высказывание? Это фразы типа «два больше одного», «5.8 является целым числом». В первом случае мы имеем истину, а во втором ложь. Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.

 

2.2.Основные функции математической логики: конъюнкция, дизъюнкция, инверсия.

 

Так как же связываются между собой простые логические высказывания, образуя сложные? В естественном языке мы используем различные союзы и другие части речи. Например, «и», «или», «либо», «не», «если», «то», «тогда». Пример сложных высказываний: «у него есть знания и навыки», «она приедет во вторник, либо в среду», «я буду играть тогда, когда сделаю уроки», «5 не равно 6». Как мы решаем, что нам сказали правду или нет? Как-то логически, даже где-то неосознанно, исходя из предыдущего жизненного опыта, мы понимаем, что правда при союзе «и» наступает в случае правдивости обоих простых высказываний. Стоит одному стать ложью и все сложное высказывание будет лживо. А вот, при связке «либо» должно быть правдой только одно простое высказывание, и тогда все выражение станет истинным.

Булева алгебра переложила этот жизненный опыт на аппарат математики, формализовала его, ввела жесткие правила получения однозначного результата. Союзы стали называться здесь логическими операторами.

Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Часто конъюнкцию обозначают &, дизъюнкцию - ||, а отрицание - чертой над переменной, обозначающей высказывание.

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

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

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

 

2.3.Таблицы значений логических функций (таблица истинности)

 

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

 

 

2.4.Задание функций с помощью формул

 

Любую формулу алгебры логики можно рассматривать как функцию, определенную на множестве B={1, 0}, где 1 соответствует значению “И”, а 0 – значению “Л”.

Функцией алгебры логики (логической функцией) или булевой функцией f(x1,x2,...,xn) называется отображение f : B n®B, определенное на множестве упорядоченных наборов элементов множества B и принимающее значения из этого множества. Обозначим через Pn - множество булевых функций n переменных.

Логическую функцию  n переменных f(x1,x2,...,xn) можно задать таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части - значения функции на этих наборах.

x1    x2              .  .  .              хn-1xn	f(x1, x2 ,   . . .    хn-1 , xn)
0      0          .  .  .            0    0 0      0          .  .  .            0    1 0      0          .  .  .            1    0 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 1      1          .  .  .            1    0 1      1          .  .  .            1    1	f(0,0, . . . ,0,0) f(0,0, . . . ,0,1) f(0,0, . . . ,1,0) .  .  .  .  .  .  .  . f(1,1, . . . ,1,0) f(1,1, . . . ,1,1)

 

При любом фиксированном упорядочении наборов булева функция n переменных полностью определяется вектор-столбцом своих значений, размерность которого равна числу наборов значений функции, то есть 2n . Поэтому число различных функций n переменных равно числу различных двоичных векторов длины 2n, то есть  , т.е. | | =  . Нулем (единицей) булевой функции назовем упорядоченный набор значений переменных, на котором  значение функции равно 0 (1).

Пусть F={ } – множество булевых функций, называемое базисом. Формулой   над базисом F (обозначается  [F]) называется выражение вида  [F]= , где  F. Таким образом, всякая формула является суперпозицией базисных функций, для ее представления обычно применяется инфиксная форма записи с логическими операциями  ~. Каждой формуле однозначно соответствует некоторая булева функция f, в этом случае говорят, что формула   реализует функцию f, однако, как будет показано ниже, такая реализация не единственна.

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

Логических функций одной переменной четыре: две нуль-местные (j0(х), j3(х)) - константы 0 и 1, значения которых не зависят от значения переменной, и две одноместные функции - тождественная и отрицание.

Х	j0	j1	j2	j3
0	0	0	1	1
1	0	1	0	1

 

Тождественная функция "повторяет" значение х: j1(х)=х. Функция отрицание возвращает значение, противоположное значению х: j2(х)= ¬х.

Логических функций двух переменных шестнадцать:

х1	Х2	j0	j1	j2	j3	j4	j5	j6	j7	j8	j9	j10	j11	j12	j13	j14	j15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

 

 

 

2.5.Функционально полная система логических функций.

 

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

 

1) "И-ИЛИ-НЕ" (базис конъюнкции, дизъюнкции, инверсии)

2) "И-НЕ"           (базис Шеффера)

3) "ИЛИ-НЕ"     (базис Пирса или функция Вебба).

 

 
         Элементы, реализующие операцию "И-НЕ", “ИЛИ-НЕ” и “Исключающее ИЛИ” на принципиальных  и  структурных схемах изображаются так:

 

Примеры реализации логических операций в базисах “И-НЕ” и “ИЛИ-НЕ”.

 

 
Реализация операции “НЕ”:

 

 
Реализация операции “И”:

 

 

Реализация операции “ИЛИ”:

Пример реализации комбинационного устройства в базисе "И-НЕ". Пусть задана функция, реализуемая комбинационным устройством, в аналитической форме

.

Используя закон де Моргана и с учетом закона двойного инвертирования, запишем эту функцию в виде

.

 

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

 

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

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

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

Переключательные схемы

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

Вентили, триггеры и сумматоры