Поняття про інформацію та її види. Три підходи до вивчення теорії


с. 1 с. 2 с. 3 ... с. 10 с. 11

Буква, слово, алфавіт. Переваги, фізична реалізація та форми представлення дволітерних алфавітів.

Буква – сигнал, який поступає на вхід ЦА в момент часу ti (проміжна, вихідна)

Слово – послідовність вхідних букв.

Алфавіт – це множина всіх букв, які відрізняються.

A
X Y

Для задания конечного автомата фиксируются три конечных множества (алфавита):

- множество возможных входных сигналов: X = {x1, x2, ..., xm};

- множество возможных выходных сигналов: Y = {y1, y2, ..., yk};

- множество возможных внутренних состояний автомата:A = {a0, a1, ..., an}.

Причини застосування двозначного алфавіту:



  1. У внутрішньому алфавіті кожна буква з двох являє зоною чи смугою.




  1. Відрізняються стани не тільки кількісно, але і якісно.

  2. Арифметичні та логічні операції виконуються простіше в двохбуквених алфавітах.

  3. Простіше реалізовуються пристрої памяті.

Фізичне представлення


Механічне

Біологічні

Хімічний

Електрика

Оптичні

Акустичний

Тепловий

Квантові

Форми представлення



  1. Потенціальна (статична) 4. Фазова




  1. Імпульсна (динамічна)





  1. Частотні

Алгебра логіки. Поняття про аналіз і синтез. Операції суперпозиції та перестановки.


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

Функция f(x1, x2, ..., xn) называется логической (переключательной), или булевой, если она, так же как и ее аргументы xi, может принимать только два значения: 0 или 1.

Логическая (булева) переменная эта такая величина x, которая может принимать только два значения: 0 или 1.

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



Совокупность значений аргументов логической функции называется набором (или точкой) и может обозначаться, в частности, как х1, х2,..., хn, где xi равно нулю или единице (i = 1, 2, ..., n). Очевидно, что набор значений аргументов фактически представляет собой некоторое двоичное число. Каждому набору значений аргументов приписывается номер, равный двоичному числу, которое соответствует значению данного набора. Например, для четырех аргументов 0, 0, 0, 0 - нулевой набор; 0, 0, 0, 1 - первый набор;
0, 0, 1, 0 - второй набор; 1, 0, 1, 0 - десятый набор и т.д.

Суперпозиція

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

xyz=x (yz), xyz=x(yz), xyzx(yz)

Перестановка

xy= yx, xy=yx, xyyx




Змінна, набір, функції алгебри логіки (ФАЛ) нуля, однієї та двох змінних



Совокупность значений аргументов логической функции называется набором (или точкой) и может обозначаться, в частности, как х1, х2,..., хn, где xi равно нулю или единице (i = 1, 2, ..., n). Очевидно, что набор значений аргументов фактически представляет собой некоторое двоичное число. Каждому набору значений аргументов приписывается номер, равный двоичному числу, которое соответствует значению данного набора. Например, для четырех аргументов 0, 0, 0, 0 - нулевой набор; 0, 0, 0, 1 - первый набор;
0, 0, 1, 0 - второй набор; 1, 0, 1, 0 - десятый набор и т.д.

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



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

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

Например, для одного аргумента имеем 21, т.е. 2 набора и 22 , 4, т.е. четыре логические функции от одной переменной, которые приведены в таблице 7.1.

Т а б л и ц а 7.1


x

f0(x)

f1(x)

f2(x)

f3(x)

0

1

0

0

1

1

1

0

1

0

В связи с тем, что функция f0(x) равна единице при любых значениях аргумента, то эта функция называется абсолютно истинной (константа единицы), тогда функция f1(x) - абсолютно ложная функция (константа нуля). Функция f2(x), повторяющая абсолютное значение логической переменной, - тождественная функция: f2(x)  x.

Функция f3(x), принимающая значение, обратное значению x, - логическое отрицание (инверсия), или функция НЕ (NOT), которая обозначается одним из следующих способов:
f3(x) =  x = x.
Логическое отрицание или инверсия некоторой логической переменной, например переменной А, это также логическая переменная, принимающая значение обратное значению переменной А, и обозначаемая как А. Если А =1, то А = 0, если же А = 0, то А = 1. Но нужно учесть, что часто посредством отрицания, т.е. инверсии переменной просто обозначают случай, когда ее значение равно нулю.

ФАЛ 2-х

Дизъюнкция (логическое сложение) или функция ИЛИ (OR) - это функция f7(x1, x2), которая истинна тогда, когда истинна хотя бы одна из ее переменных. Условные обозначения этой функции:

f7(x1, x2) = x1 + x2 = x1  x2 = x1 ! x2

Это читается следующим образом: функция истинна, т.е. равна единице, когда аргумент x1 = 1, т.е. истинен, или аргумент x2 = 1, или же оба аргумента истинны одновременно.

Т а б л и ц а 7.2



Функция

x1x2

Примечание




00

01

10

11




f0

0

0

0

0

f0

константа нуль

f1

0

0

0

1

x1  x2

конъюнкция

f2

0

0

1

0

x1 x2

запрет x2

f3

0

0

1

1

x1x2  x1x2 = x1

переменная x1

f4

0

1

0

0

x1  x2

запрет x1

f5

0

1

0

1

x1x2  x1x2 = x2

переменная x2

f6

0

1

1

0

x1  x2

сложение по модулю 2

f7

0

1

1

1

x1  x2

дизъюнкция

f8

1

0

0

0

x1  x2

функция Пирса

f9

1

0

0

1

x1  x2

равнозначность

f10

1

0

1

0

x1x2  x1x2 =x2

инверсия x2

f11

1

0

1

1

x2  x1

импликация

f12

1

1

0

0

x1 x2 x1x2 =x1

инверсия x

f13

1

1

0

1

x1  x2

импликация

f14

1

1

1

0

x1 / x2

функция Шеффера

f15

1

1

1

1

f1

константа единица


Конъюнкция (логическое умножение) или функция И (AND) - это функция f1(x1, x2), которая истинна тогда, когда все ее переменные одновременно истинны. Эту функцию условно обозначают следующим образом:

f1(x1, x2) = x1  x2 = x1  x2 = x1 & x2

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

Функция (штрих) Шеффера или функция И-НЕ - это функция f14(x1, x2), которая ложна тогда, когда все переменные истинны. Условное обозначение этой фнкции:

f14(x1, x2) = x1/x2

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

Функция (стрелка) Пирса (Вебба) или функция ИЛИ-НЕ - это функция
f8(x1, x2), которая истинна только тогда, когда все переменные ложны. Условное обозначение этой функции:

f8(x1, x2) = x1  x2 = x1 O x2.

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

Импликация или функция ЕСЛИ-ТО (IF-THEN) это функция f13(x1, x2), которая ложна тогда и только тогда, когда x1 истинно и x2 ложно. Аргумент х1 называется посылкой, а х2 - следствием. Ее условное обозначение

f13(x1, x2) = x1  x2.



Исключающее ИЛИ (XOR) - это функция f6(x1, x2), которая обозначается знаком . Эта операция, как видно из таблицы, реализует функцию неравнозначности, т.е. фактически реализуется процедура суммирования по модулю 2, которая обозначается знаком :

f6(x1, x2) = x1  x2 = x1  x2



Все рассмотренные функции являются элементарными.

Из всех приведенных выше определениий ясно, что в алгебре логики все знаки действий:  или &,  или +, ,  и т.д, в отличии от обыкновенной алгебры, являются знаками логических связок, т.е. логических действий, а не знаками арифметических действий.

Введем еще три специфических понятия алгебры логики.

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

Логическая переменная xi действительна, если значение логической функции f(x1, x2, ..., xn) изменяется при изменении xi. В противном случае эта переменная для данной функции фиктивна, т.е. не является ее аргументом.

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

Как будет показано в дальнейшем, любые логические операции над логическими переменными можно свести к определенной совокупности элементарных логических функций, например, таких как И, ИЛИ, НЕ и исключающе ИЛИ.

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


И ИЛИ Искл. ИЛИ НЕ

01011010 0101010 0101010 01011010

11110000 1111000 1111000 10100101

01010000 1111010 1010010


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

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




с. 1 с. 2 с. 3 ... с. 10 с. 11

скачать файл