Эффективная подготовка к государственным междисциплинарным экзаменам для студентов технических специальностей (стр. 59 )

3) Цепочка β называется выводимой из α, если существует конечная цепочка вывода: α ->ξ0; ξ0 -> ξ1; ξ1-> ξ2; …, ξn -> β, где ξi – цепочка нетерминальных символов Є (V* U W*).

α ->G β: β выводима из α в грамматике G.

4) Языком L, порождаемым грамматикой G, называется множество всех цепочек, выводимых из аксиомы грамматики.

5) Грамматики G1 и G2 эквивалентны, когда они порождают один и тот же язык.

Операции над языками.

Пусть L0 - язык, заданный грамматикой G0={V0, W0, R0, I0}, a Є V0;

L1- язык, заданный грамматикой G1={V1, W1, R1, I1};

1. Подстановка.

Подстановка языка L в L0 вместо символа а–операция, сопоставляющая языкам L0 и L1 язык L=L0 (а->L1), состоящий из всех цепочек языка L0, в которых вместо символа а подставлена некоторая цепочка из L1.

Пример:

L=L0(a->L1)

L=L0(a1->L1, a2->L2…ak->Lk)

L0=(a,(a+a), (a+a+a) )

L1=(b, bb, bbb )

L=(b, bb,…,b+b,(b+b+b)…)

2.Конкатенация.

Конкатенация языков L0 и L1- это операция, сопоставляющая языки L0 и L1 языку L, который состоит из цепочек, представляющих собой парное сцепление цепочек языков L0 и L1.

Пример:

L0=(a,(a+a),…)

L1=(b, bb, …)

L=L0L1={ab, abb,…, (a+a)b, (a+a)bb…}

Введем обозначение кратной конкатенации

L&L= L^2;

L&L&L= L^3; …

3. Итерация.

Язык L*, его подмножество будет определяться равенством

L* = [ ε ] U L U L2 U.. U Ln = { ε } U n i=1 Li

Замечание: не следует смешивать язык, содержащий ε (пустую цепочку), с пустым языком, не содержащим ни одной цепочки. ε – не есть отсутствие правил. Язык, содержащий ε – не пустой.

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

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

Определение: функция, принимающая значения от 0 до k-1, аргументы которой также принимают значения из этого множества, называется функцией k-значной логики.

Булева функция - функция двухзначной логики.

В k-значной логике выделяется ряд элементарных функций, например:

1) квазиконьюнкция

2) квазидизъюнкция

3) сумма по модулю k {x1Å x2}mod k

4) произведение по модулю k {x1Äx2}mod k

значение функции равно остатку от деления произведения x1 x2 на k

5) функция Вебба {max(x1, x2)+1}mod k

6) цикл (циклическое отрицание)

7) функция инверсии

8) характеристические функции:

Построим таблицы, задающие все введенные элементарные функции 3-х значной логике.

В 3-х значной логике функциями const являются 0,1,2.

x1	x2	&	V	x1 ¯ x2	Å	Ä
0	0	0	0	1	0	0
0	1	0	1	2	1	0
0	2	0	2	0	2	0
1	0	0	1	2	1	0
1	1	1	1	2	2	1
1	2	1	2	0	0	2
2	0	0	2	0	2	0
2	1	1	2	0	0	2
2	2	2	2	0	1	1

Закодируем аргументы следующим образом: 0 = 00, 1 = 01, 2 = 10.

Для записи и передачи любого троичного переменного необходимо использовать две двоичные переменные v1, v2. При этом функции Ψi(x) будут кодироваться следующим образом:

X	n1	n2	Ψ0’	Ψ0’’	Ψ1’	Ψ1’’	Ψ2’	Ψ2’’
0	0	0	0	1	0	0	0	0
1	0	1	0	0	0	1	0	0
2	1	0	0	0	0	0	0	1
*	1	1	*	*	*	*	*	*

удобно доопределить Ψi’ на наборе <1,1> нулями, тогда получим:

Ψ0’=Ψ1’=Ψ2’=0; Ψ0’’= v1 & v2; Ψ1’’= v1 & v2; Ψ2’’= v1 & v2;

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

Практически в полупроводниковых схемах для трехзначной функции положительным потенциалом считается потенциал >= 1.5 В.

Нулевым потенциалом считается потенциал по модулю <=0.6.

Отрицательным - потенциал <= -1.5 В.

Пример: рассмотрим кодирование ф-й X1Å X2, X1ÄX2

X1	X2	X1Å X2	X1ÄX2
V1	V2	V3	V4	f1	f2	f3	f4
0	0	0	0	0	0	0	0
0	0	0	1	0	1	0	0
0	0	1	0	1	0	0	0
0	0	1	1	*	*	*	*
0	1	0	0	0	1	0	0
0	1	0	1	1	0	0	1
0	1	1	0	0	0	1	0
0	1	1	1	*	*	*	*
1	0	0	0	1	0	0	0
1	0	0	1	0	0	1	0
1	0	1	0	0	1	0	1
1	0	1	1	*	*	*	*
1	1	0	0	*	*	*	*
1	1	0	1	*	*	*	*
1	1	1	0	*	*	*	*
1	1	1	1	*	*	*	*

Таким образом, функцию f(x1,x2) можно представить следующим образом:

f(x1,x2)=<f1(v1,v2,v3,v4), f2(v1,v2,v3,v4)>

f1= v1 & v2 & v3 & v4 V v1 & v2 & v3 & v4 V v1 & v2 & v3 & v4

f2= v1 & v2 & v3 & v4 V v1 & v2 & v3 & v4 V v1 & v2 & v3 & v4

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

v2	v1	v1	v4
		*	*
1	*	*	*	v4
v2		*	*
	1		1	v4
v3	v3	v3

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