Синтез цифровых автоматов. Захаров Н.Г - 129 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

128
Функтор Обозначение Смысловое значение
Унарные
операции
(операция отрицания)
⊃
_____
1
имплицирует ____
2
(операция импликации)
( ____
1
⊃ ____
2
) ∧ ( ____
2
⊃
⊃ ____
1
) (операция эквиваленции)
∨
_____
1
ad _____
2
(сложение, дизъюнкция)
Бинарные
операторы
∧
_____
1
con _____
2
(умножение, конъюнкция)
При n = 1, 2, 3 n-арный функтор называется соответственно унарным, бинарным, тернарным.
В автоматах для задания преобразования информации применяются различные
формальные языки:
язык регулярных функций;
язык исчисления предикатов;
язык временных логических функций;
язык логических алгоритмов и т. д.
Пример. В формальных системах структура языка обычно связана с высказыва-
ниями, подразумеваемыми смыслом языка. Под высказыванием понимают всякое ут-
верждение, о котором можно вполне определенно и объективно сказать, истинно оно
или ложно. Однако наряду с высказываниями встречаются выражения, грамматиче-
ски имеющие форму высказываний, но содержащие предметные переменные некото-
рых множеств. Такие выражения называются предикатами или функциями-
высказываниями. Подобные выражения можно получить из любых высказываний, за-
менив в них обозначения предметов предметными переменными множеств, к кото-
рым принадлежат эти предметы. Поэтому под предикатом (praedicatum, означает
«сказуемое») также понимают переменное высказывание, истинное значение которо-
го зависит от параметров (переменных).
Например, предложение «2 – простое число» есть высказывание. Если «2» за-
менить предметным переменным n множества натуральных чисел, то полученное вы-
ражение «n – простое число» грамматически имеет ту же форму, но не является вы-
сказыванием.
Словарь. Конечное множество элементов называют словарем, элементы слова-
ря – символами, а последовательности символов словаря – цепочками или предложе-
ниями. Тогда языком будет называться множество предложений.
Пример. Пусть V – словарь, L – язык над словарем V, а V* – множество всех
возможных цепочек, составленных из символов словаря V.
Тогда, если V = {a, b, c}, получим V* = {ε, a, b, c, aa, ab, cba, ccaba, ...}, где ε –
пустая цепочка, т. е. цепочка, вовсе не содержащая символов. Очевидно, что хотя V
конечно, V* – бесконечное счетное множество. Язык – это просто некоторое под-
множество V*: L ⊆ V*. Всего языков над словарем V (как подмножеств счетного
множества V*) бесконечное число.
Алфавит. Если V* – множество, то и словарь V также представляет собой
множество. Поэтому множество V часто называют алфавитом, а любое множество
цепочек L ⊆ V* называют формальным языком, определенным на алфавите V.
Итерации алфавита V

Страницы