Элементы алгебры логики

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

цифровым автоматом называется устройство, предназначенное для преобразования цифровой (дискретной)

различают автоматы синхронного и асинхронного действия.

Для идеализированных ЦА не учитывается

Абстрактные ЦА рассматриваются как " черный ящик ", имеющий один вход

Тогда закон функционирования абстрактного автомата может быть задан уравнениями:
(1)
-

ЦА, выходные сигналы в которых зависят только от состояния автомата и

ЦА, имеющая более одного внутреннего состояния, называются автоматами с памятью. Частный

Функции алгебры логики и их основные свойства.

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

3. Логическая функция ( функция алгебры логики - ФАЛ ) -

5. Если две ФАЛ и принимают на всех возможных наборах значений

7. ФАЛ называют не полностью определенными или не- доопределенными, если на

Теорема:

Число различных ФАЛ, зависящих от n аргументов конечно и

Теорема:

Число ФАЛ, существенно зависящих от n аргументов, определяется следующим рекуррентным соотношением:

Правая часть соотношения есть разность между числом всех ФАЛ и суммой

Пример:

Найти число ФАЛ, существенно зависящих от 3-х переменных.
Имеем:

Элементарные функции алгебры логики

n=1. Число ФАЛ равно 4:

Элементарные ФАЛ 2-х переменных

n=2; Число ФАЛ равно 16.

конъюнкция (логическое умножение, или функция И) истинна тогда и только тогда,

дизъюнкция (логическое сложение, или функция ИЛИ) истинна тогда, и только тогда,

3.

Функция сложения по модулю 2 (или функция разноименности, или функция

4.

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

5.

импликация х1 в х2 ложна тогда и только тогда, когда

6.

функция Пирса ( Вебба ) истинна тогда и только тогда, когда

7.

Функция Шеффера ложна только тогда и только тогда, когда х1и

Выражение одних элементарных функций через другие.

1.

2.
3.

4.
5.

Свойства элементарных ФАЛ.

Свойства конъюнкции, дизъюнкции, отрицания

Свойство ассоциативности (сочетательный закон):
Свойство коммутативности (переместительный закон):

3. Свойство дистрибутивности (распределительный закон):
для конъюнкции относительно дизъюнкции:
для дизъюнкции относительно конъюнкции:
Действительно:

Законы Де-Моргана:

1.
2.

Законы (правила) поглощения:

1.
2.

Из логических функций устанавливается

правило склеивания:
правило вычеркивания:

Знание свойств, законов и правил элементарных ФАЛ необходимо для аналитического описания

Свойства функции сложения по модулю два
Функция сложения по модулю два

ассоциативности (сочетательный закон):
дистрибутивности (распределительный закон):
справедливы правила:

Функции НЕ, ИЛИ, НЕ могут быть выражены через функцию сложения по

Свойства функции импликации
Для функции импликации справедливы следующие правила:

Функции НЕ, ИЛИ, И выражаются через импликацию следующим образом: