Логические основы теории автоматов

Логической функцией Y называется функция, которая принимает двоичные значения на множестве двоичных аргументов.

y=f(x₁, x₂, ..., x_n)- логическая функция

- количество различных функций

n=1, К=4 у₁ = 0 у₂ = 1 у₃ = x у₄ = x

n=1, К=16 …

Алгебра логики оперирует базовыми функциями.

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

1. y₁ = х₁ • х₂ - конъюнкция (логическое умножение);

2. у₂ = x_l V x₂ - дизъюнкция (логическое сложение);

_

3. у₂ = х - инверсия (логическое отрицание).

С помощью этих функций можно выразить любую сколь угодно сложную функцию.

Логические элементы первых вычислительных машин реализовывались с помощью системы прямой логики.

Недостатки: физическая реализация требует три логических элемента.

Конъюнктор

Дизъюнктор

Инвертор

С появлением интегральных микросхем логические элементы стали иметь более сложный характер.

Система инверсной логики

отрицание конъюнкции

отрицание дизъюнкции

В этой системе используются два логических элемента: И-НЕ, ИЛИ-НЕ

Достоинства:

1. Всего два элемента.

2. Отрицание стоит на выходе, что усиливает сигнал на выходе. Это позволяет подключать к данному элементу большое количество других элементов (по сравнению с прямой логикой).