Элементы алгебры логики презентация

Элементы алгебры логики Алексеев В.В. Саров 2016

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

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

Абстрактные ЦА рассматриваются как " черный ящик ", имеющий один вход и один выход, т. е. отвлекаются от структуры ЦА и его входных Х (t) и выходных Y (t) сигналов. Абстрактные ЦА рассматриваются как " черный ящик ", имеющий один вход и один выход, т. е. отвлекаются от структуры ЦА и его входных Х (t) и выходных Y (t) сигналов. - входной - выходной - состояний

Тогда закон функционирования абстрактного автомата может быть задан уравнениями: (1) - где  (s, x) - функция переходов автомата ; p (x, s) - функция выходов автомата ; s0- начальное состояние автомата . (Автомат Мили)

ЦА, выходные сигналы в которых зависят только от состояния автомата и не зависят от значения входных сигналов, называются автоматами Мура ЦА, выходные сигналы в которых зависят только от состояния автомата и не зависят от значения входных сигналов, называются автоматами Мура (2) где  [ s (t) ] -сдвинутая функция выхода.

ЦА, имеющая более одного внутреннего состояния, называются автоматами с памятью. Частный случай абстрактных ЦА - автоматы с одним внутренним состоянием. Такие тривиальные автоматы называют автоматами без памяти или комбинационными схемами. Закон функционирования таких автоматов будет определяться одним уравнением: ЦА, имеющая более одного внутреннего состояния, называются автоматами с памятью. Частный случай абстрактных ЦА - автоматы с одним внутренним состоянием. Такие тривиальные автоматы называют автоматами без памяти или комбинационными схемами. Закон функционирования таких автоматов будет определяться одним уравнением: Y (t) =  [ x(t)]

Функции алгебры логики и их основные свойства. Основные определения Основное понятие АЛ - высказывание. Высказывание - некоторое предложение, о котором можно утверждать, что оно истинно или ложно. Логическая (Булева) переменная - такая величина X, которая может принимать только два значения: X = { 0, 1 }.

3. Логическая функция ( функция алгебры логики - ФАЛ ) - функция 3. Логическая функция ( функция алгебры логики - ФАЛ ) - функция  , принимающая значение, равное нулю или единице на наборе логических переменных . Пусть и 4. Функцией алгебры логики (ФАЛ) называется функция, дающая однозначное отображение X в Y, т.е.

5. Если две ФАЛ и принимают на всех возможных наборах значений аргументов одинаковые значения, то функции 1 и 2 называются равносильными (равными), т.е.: 5. Если две ФАЛ и принимают на всех возможных наборах значений аргументов одинаковые значения, то функции 1 и 2 называются равносильными (равными), т.е.: = 6. Функция существенно зависит от аргумента , если имеет место соотношение:

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

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

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

Правая часть соотношения есть разность между числом всех ФАЛ и суммой всех ФАЛ, существенно зависящих от любого числа аргументов, меньших чем n. Правая часть соотношения есть разность между числом всех ФАЛ и суммой всех ФАЛ, существенно зависящих от любого числа аргументов, меньших чем n. Вместо рекуррентного соотношения можно найти прямое выражение для значений:

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

Элементарные функции алгебры логики n=1. Число ФАЛ равно 4:

Элементарные ФАЛ 2-х переменных n=2; Число ФАЛ равно 16.

имеем 10 различных функций, существенно зависящих от аргументов x1 и x2 .

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

2. дизъюнкция (логическое сложение, или функция ИЛИ) истинна тогда, и только тогда, когда истинны или x1, или x2, или обе переменные.

3. Функция сложения по модулю 2 (или функция разноименности, или функция исключающее ИЛИ) истинна тогда и только тогда когда x1x2.

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

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

6. функция Пирса ( Вебба ) истинна тогда и только тогда, когда х1 и х2 ложны.

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

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

2. 3.

4. 4. 5.

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

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

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

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

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

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

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

Свойства функции сложения по модулю два Функция сложения по модулю два обладает следующими свойствами: коммутативности (переместительный закон)

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

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

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

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