f 0 (x)
f 1 (x)
f 2 (x)
f 3 (x)
0
0
0
1
1
1
0
1
0
1
Функція f 0 ( x ) називається константою нуля, а функція f 3 ( x ) - константою одиниці. Функція f i ( x ) , що повторює значення логічної змінної, - тотожна функція ( f i ( x ) = x ), а функція f 2 ( x ) , приймаюча значення, зворотні значенням змінної х , - логічне заперечення або інверсія (НЕ) ( f 2 ( x ) =).
Елементи алгебри логіки мають наступні операції:
Кон'юнкція (І, логічне множення) - твір двох висловлювань Р і Q, результатом якого є істина, якщо обидва висловлювання істинними і брехня у всіх інших випадках.
Диз'юнкція (АБО, логічна сума) - сума двох висловлювань Р і Q; результатом є хибне висловлювання, якщо обидва висловлювання помилкові, і істинне у всіх інших випадках.
Інверсія (заперечення) - запереченням висловлювання Р називається висловлення істинне, якщо саме висловлювання Р помилкове, або навпаки.
Для функції двох змінних, згідно ф. (1), існує чотири унікальні набору змінних. Функції відрізняються один від одного набором значень 0 і 1 в чотирьох розрядах коду значень функції. Загальна кількість функцій на п-місцевому або п-розрядному наборі змінних дорівнює: (3). p> Дві функції рівносильні один одному, якщо вони приймають на всіх можливих наборах змінних одні й ті ж значення. p> Аналітично це властивість описується наступною формулою:
f 1 ( x n -1 , x n -2 sub> , ..., x 0 ) = f 1 ( x n -1 , x n -2 , ... x 0 ) (4)
Обидві функції в ф. (4) можуть мати різні форми аналітичної запису, але практично найбільш вигідною буде найпростіша форма запису.
Система булевих функцій W називається функціонально повною, якщо для будь булевої функції п-змінних f (x n -1 , х n -2 , .. ., х 0 ) може бути побудована рівносильна їй функція комбінуванням булевих змінних x n -1 , х n -2 , ..., х 0 і функцій системи W, взятих в будь-якому кінцевому кількості примірників кожна. Така система булевих функцій (W) називається базисом. p> Таким чином, базис - повна система функцій алгебри логіки (ФАЛ), за допомогою якої будь-яка ФАЛ може бути представлена ​​суперпозицією вихідних функцій W.
Базисом є система функцій І (кон'юнкція), АБО (диз'юнкція), НЕ, (інверсія), властивості яких були вперше вивчені Дж. Булем.
Базис є мінімальним, якщо видалення з нього хоча б однієї функції перетворює систему ФАЛ в неповну. Базис І, АБО, НЕ - надлишковий. p> Для абстрактного математичного опису цифрового автомата як кодопреобразователя використовується уявлення 6-елементного безлічі S = {А, Х, У, d, l, a 1 ,}.
Поняття множини - поняття, яке не має визначення. Безлічі мають свої підмножини, воно може бути кінцевим і нескінченним. Впорядкованим буде безліч, в якому кожен елемент має своє місце.
Безліч буде складатися з наступних елементів:
А = {а 1 ..., а п } -Безліч станів автомата,
X = {х 1 ..., х п } - безліч вхідних сигналів,
Y = {у 1 .. ., У п } - безліч вихідних сигналів,
d - функція переходів абстрактного цифрового автомата,
l - функція виходів абстрактного цифрового автомата,
a 1 - початковий стан автомата (a i належить А).
Для однозначного управління цифровим автоматом необхідно, щоб він починав роботу з певного початко...