Перечень литературы и наглядных пособий

Вопросы лекции

 

1. Основные законы и правила алгебры логики

2. Способы представления ФАЛ

3. Минимизация переключательных функций

4. Комбинационные схемы.(автомат Мили), их анализ и синтез. Понятие о конечном автомате (автомат Мура)

 

 

Перечень литературы и наглядных пособий

1. [ 7 ] стр. 50 – 79

2. [ 2 ] стр. 177- 199

Перечень заданий на самостоятельную подготовку.

 

1. Изучить метод минимизации при помощи диаграмм Вейча

 

[ 1 ] стр. 50 – 79

   [ 2 ] стр. 177- 199

   [ 6 ] стр. 33 – 62

 

                                                                                 Время - 1 час.

 

                   Преподаватель:

 

 

Логические основы ЭВМ.

Понятие о цифровом автомате.

 

 

Преобразование информации в ЭВМ осуществляют цифровые автоматы (ЦА), которые бывают двух типов

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

 

-информаторы;

-дешифраторы;

-суматоры;

-преобразователи кодов;

-схемы контроля и т.п.;

 

б) с памятью (покопливающиеся или последовательные схемы, ЦА, полный автомат (автомат Мура). Они используются для построения

- триггерных устройств;

- регистров;

- счетчиков;

- распределителей импульсов и др.

 

Y(t)

X(t)

КС

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

 

                                                                                      

 

X(t) = X₁ X₂ X₃... X_N     

Y(t) =  Y₁ Y₂ Y₃... Ym       

 

Y(t) = F (X(t),t);

 

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

X(t)

Y (t) = F (X(t), Q(t),t); Y(t) =Y₁ Y₂ Y₃... Ys     

 

 

Переход от условий работы ЦА к его функционированию с памятью аппарата логики или булевой алгебры, которая является одной из ветвей мат. логики.

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

 

 

                                            3. Основные понятия алгебры логики.

Впервые идею о возможности формировать процесс логическим рассуждении высказал Аристотель. Позже к ней вернулся Лейбниц. Однако по-настоящему математическая логика была разработана Булем (1815- 1864 г.г.)

Его работы развили Э.Пост, К. Шеннон, В. Глушков, С. Яблонский и др.

 

Логика – это наука о законах и формах мышления.

 

 

Математическая логика – наука о применении матаматических методов для решения логических задач. Она служит теоретической основой построения ЭВМ и цифровых устройств.

Основное понятие алгебры логики – высказывания.

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

 

Высказывания м. б.

- простыми – не зависят от других высказывания

- сложные – образующиеся из двух и более простых высказываний.

 

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

Высказывания оценивают только по их истинности или ложности.

Считают, что высказывания = 1, если оно истинно и = 0, если ложно. Т.о. логическая (булева) переменная – это такая величина Х, которая может применять только значения 0 или 1 т.е.

Х Є {0,1}

Высказывание абсолютно истинно, если логическая величина принимает значение Х=1 при любых условиях

Например «Земля планета Солнечной системы»

Взысказывание абсолютно ложно, если логическая величина принимает значение х=0 при любых условиях. Например «Земля спутник Марса» Кроме того, существуют взысказывания, которые могут быть истинными или ложными в зависимости от определенных условий (например» на улице идет дождь»)

Логическая функция – (функция алгебры логики) это функция вида F (X₁ X₂ … X_N), принимающие значение, равна 0 или1 на наборе логических переменных X₁ X₂ … X_N называется  набором аргументов.

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

 

Например: для F (X₁ X₂ X₄) При Х₁=0, Х₂=1, Х₃=1 и Х₄= 1

Тогда для данного кортежа аргументов функция м.б. записана так. (0,1,1,1)

Менять местами в кортеже 0 и1 нельзя, т.к. будет другой кортеже аргументов и ему будет соответствовать другая ФАЛ.

Кортеже удобно изображать в виде n- значного двоичного числа, каждый разряд которого равен значению одного из аргументов (наз. 0111) Тогда количество возможных различных наборов (кортежей) равно количеству чисел, которые м.б. изображены с помощью n двоичных разрядов, т.е. k = 2ⁿ

Т.к. ФАЛ принмает значение 0 или 1, то общее число ФАЛ N=2^k

Следовательно, Общее число функций, Которые могут быть образованы от n аргументов, равно                           n

                       N=2²

 

Одноместная ФАЛ

n=1        k=2ⁿ = 2¹ = 2     N=2² = 4   ФАЛ

 

 

Табл. 1

X	F1	F2	F3	F4
0	1	0	0	1
1	1	0	1	0
Название ФАЛ	Абсолютно истинная ФАЛ (константа единицы)	Абсолютно ложная ФАЛ (константа нуля)	Тождественная ФАЛ Fз (x)= x	Функция логического отрицания (НЕ) F4(X)=X инверсия

 

                                                               _{n  2}

N= 2 K=2ⁿ=2²=4                     N = 2² =2² = 16

 

1. Константа нуля F₁ = 0 F₁ = всегда ложна, Независимо от высказывания (обозначается F₀)

 

1. Конъюнкция – логическое умножение (и) F₂ = истина только тогда, Когда истины X₁ и Х₂ одновременно.

F₂(X₁ X₂) = X₁*X₂ = X₁&X₂ = X₁^X₂

 

3. Запрет Х₂       F₃=(X₁,X₂)=X₁*X₂=X₁ΔX₂

 

4. Повторение  X₁ F₄=(X₁,X₂)=X₁*X₂ ^ X₁*X₂=X₁

 

                                      F₄= истина только в том случае, когда Х₁ истина, от Х₂ не зависит.

                                    Элемент задержки Х₁

 

5. Запрет Х₁ F₅ (X₁,X₂) = X₁*X₂ = XΔX₁

                                     F₅ – истина только, когда Х₂ истина, а Х₁ ложна.

 

6. Повторение Х₂ F₆(X₁,X₂) = X₁*X₂^X₁*X₂ = X₂

 

                      F₆ истина только тогда, когда Х₂ истина, от Х₁ не зависит

                      Элемент задержки Х₂

 

7. Неравнозначность или сложение по модулю 2 (Н2)

 

                     F₇ = (X_1,X₂) = X₁+X₂=X₁X₂^X₁*X₂

                                 F₇ = истина тогда, когда истина или Х₁, или Х₂ в отдельности.

     

8. Дизъюнкция – логическое сложение

 

                          F₈ истинно тогда, когда истинны или Х₁ или Х₂ или обе переменные              вместе

                          F₈= (X₁,X₂) = X₁+X₂= X₁^X₂

   

9. Функция Пирса (Вебба)

                      

                          F₉= (X_1,X₂)= X₁^X₂ = X₁*X₂ = X₁ X₂ = X₁ 0 X₂

               Др. название стрелка Пирса, функция ИЛИ – НЕ, отрицание конъюнкции

Математически Пирс и Вебб, независимо друг от друга изучавшие свойства этой функции, создали алгебру, названную алгеброй Пирса (Вебба)

 

 

10. Равнозначность

                  

                         F₁₀(X₁,X₂) = X₁∞X₂ = X₁ = X₂

                                      

                                      F₁₀  истина только тогда, Когда переменные равнозначны (эквивалентны             друг другу.

                        Другое название эквивалентность.

 

11. Инверсия X₂  

                           

                         F₁₁(X₁,X₂) = X₁*X₂^X₁*X₂=X₂= X₂

 

                         F₁₁  истина только тогда, когда X₂ ложна и ложна, когда Х₂ истина

 

 

12. Импликация Х₂ в X₁

                                     

                                    F₁₂ = X₁^X₂ (= X₁*X₂)

                      F₁₂ = (X₁,X₂)= X₂  X₁

 

                      F₁₂ истина только тогда Х₂ истина, а Х₁ ложна

            

Если Х₂ истина то Х₁ ложно (следствии за истиной лжи)

Логическое следование.

 

 

13.Инверсия Х₁

                      

                        F₁₃(X₁,X₂) =X₁*X₂ ^X₁*X₂= X₁= X₁

                                  

                     F₁₃  истина тогда Х₁  ложно и ложна, когда Х₂ истина.

 

14. Импликация Х₁ вХ₂

                        F₁₄= X₁^X₂ (X₁*X₂)

 

                       F₁₄ (X_1,X₂) = X₁      X₂

 

                                   F₁₄ ложна тогда когда X₁  истина, и Х₂ ложна

 

15. Функция Шеффера

           

                      F₁₅ (X_1,X₂) = X₁/X₂ = X₁& X₂ = X₁^X₂

 

                     F₁₅  ложна только тогда, когда Х₁ и Х₂  одновременно истины

Другое название штрих Шеффера, И- НЕ

Немецкий математик Шеффер на основе этой ФАЛ создал алгебру (Шеффера)

 

 

16. Константа единицы   F₁₆ = 1

 

                                               F₁₆ всегда истина, независимо от высказывания.

 

Все функции в таблице 2 элементарные функции.

 

                         

 

 

Аксиомы алгебры логики

Х*1=Х   Х^1=1

Х*0=0    Х^0=Х

0=1         1=0

0=0         1=1

 

Следствия

Х₁^Х₂= Х₁^Х₂=Х₁*Х₂;       Х₁*Х₂=Х₁*Х₂=Х₁^Х₂

 

 

- возможность выражать дизъюнкцию через конъюнкцию и отрицание

- конъюнкцию через дизъюнкцию и отрицание

 

Представление ФАЛ

 

 

1. Основные определения

 

Существует много способов описания ЦА.

 

- табличный

- с помощью ФАЛ (аналитический);

- секвенциальное

- с помощью граф-схем и логических схем алгоритмов и др.

 

 

Первый способ представлен в табл. 1 и Табл. 2. В них каждому из возможных наборов переменных ставится в соответствие значение функции (0 или 1) Этот способ нагляден и может быть применен для представления функции любого числа переменных. Однако для больших n  такая форма уже не компактна, т.к. таблица будет громоздкой. Кроме того, в табличной форме преобразование данных затруднено.

 

Таблица, описывающая работу ЦА, называется таблицей истинности. Ее построение является чаще всего лишь первым этапом при проектировании сложных ЦА, в том числе и ЭВМ.

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

 

Прежде рассмотрим элементарные понятия

 

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

 

Минтермом – или конституэнтой еденицы называют функцию принимающие еденичное значение при фиксированном наборе аргументов.

Макстермом – или конституэнтой нуля называют функцию принимающую нулевое значение при фиксированном наборе аргументов.

 

Например

 

		F(X1,X2)
X1	X2
0	0	Макстермы      Минтермы   1
0	1	0
1	0	0
1	1	1

                    

 

Суммарное число минтермов и макстермов совпадает с числом наборов различных аргументов.

Элементарная конъюнкция (дизъюнкция) – это конъюнкция (дизъюнкция), в которой конъюнктивно (дизъюнктивно), связано конечная множество логических переменных и их отрицания

Например Х₁^Х₂^Х₃ или Х₁*Х₂*Х₃*Х₄

             r = 3               r = 4

  Число переменных, составляющих элементарную конъюнкцию (дизъюнкцию), называется ее рангом r

Рассмотрим различные формы аналитической записи переключательной функции.

Нормальные формы -  представляют лишь дизъюнкции элементарных конъюнкций или             конъюнкцию элементарных конъюнкций.

 

 Нормальная форма, представляет дизъюнкций элементарных конъюнкций   

F_диф. (Х₁,Х₂,Х₃)= Х₁*Х₂*Х₃^Х₁*Х₂, называется ДИФ нормальная форма, представленная конъюнкций элементарных дизъюнкций

 

F_диф. (Х₁,Х₂,Х₃)=(Х₁^Х₂)(Х₁^Х₃)(Х₁^Х₂), называется КНA

 

Набора