Автоматов

Учебное пособие

Художественный редактор A.B. Антипов

Корректор Г.Н. Середина Компьютерная верстка И.Г. Долгой

Изд. лиц. № 071461 от 26.06.97.

Подписано в печать 17.10.2000. Формат 60x901/16. Гарнитура Тайме. Печать офсетная. Усл. печ. л. 7,0. Тираж 2000 экз. Заказ № 1722

Издательская группа «Юристь»

101000, Москва, Лубянский пр., д. 7, стр. 1

Тел.: (095) 928-4840, 925-9019

Отпечатано с готовых диапозитивов

в Щербинской типографии 113623, Москва, ул. Типографская, 10

ОСНОВЫ ТЕОРИИ БУЛЕВЫХ

ФУНКЦИЙ И КОНЕЧНЫХ

АВТОМАТОВ

УЧЕБНОЕ ПОСОБИЕ

Таганрог 2000

УДК: 512.932(075.8)+519.713(075.8)

З.А. Мелихова, О.А. Мелихова. Основы теории булевых функций и конечных автоматов: Учебное пособие. Таганрог: Изд-во ТРТУ, 2000. 65 стр.

Данное пособие является обобщением многолетнего опыта преподавания профессором Мелиховым Аскольдом Николаевичем и авторами этого пособия следующих дисциплин: «Дискретная математика», «Математические основы дискретной техники», «Теория конечных автоматов».

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

Табл. 26. Ил. 38.. Библиогр.: 7 назв.

Рецензенты:

С.Ю. Аваков, к.т.н., доцент, член-корреспондент РАЕН, ректор Таганрогского института управления и экономики,

Г.В. Горелова, д.т.н., профессор кафедры управления и экономики Таганрогского института управления и экономики.

1. НОРМАЛЬНЫЕ И КАНОНИЧЕСКИЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ

1.1. Разложение булевых функций по переменным

Пусть имеем функцию Для переменной х₁ введем обозначение:

где σ_i - некоторый параметр, принимающий значение 0 или 1.

Таким образом:

При таком обозначении любая произвольная конъюнкция:

тогда и только тогда, когда

во всех остальных случаях она равна 0. Аналогично для дизъюнкции:

тогда и только тогда, когда

в остальных случаях эта дизъюнкцияравна 1.

Теорема 1. Любую булеву функцию x_m+1,..., x_n), где 1≤m≤n, можно представить в следующей форме:

где означает, что дизъюнкция берется по всем

наборам символов (от всех нулей до всех единиц).

Такое представление булевой функции называется разложением булевой функции по т переменным.

Пример. Пусть имеется некоторая функция Разложение этой функции по переменной х₁, имеет вид:

Разложение
по x₁, х₂ имеет вид:

1.2. Совершенные дизъюнктивная и конъюнктивная нормальные формы булевой