Всего на сайте:
303 тыс. 117 статей

Главная | Математика

Основы булевой алгебры  Просмотрен 25

ХХ Основы булевой алгебры

 

Хх.1 Основные понятия и определения

 

Булева алгебра (БА) – раздел математической логики.

Основным понятием БА является высказывание (В). Под высказыванием понимают любое предложение, про которое можно однозначно сказать, истинно оно или ложно. Высказывания подразделяются на простые и сложные.

Под простым В понимают одно единственное предложение, про которое можно сказать истинно оно или ложно. Например: «Дважды два – пять», «Курица – не птица», «Путин – президент РФ».

Сложным В является предложение, состоящее из нескольких простых предложений (простых В), связанных между собой какими либо логическими связями. Под логическими связями понимаются грамматические союзы типа «НЕ», «И», «ИЛИ», «ЕСЛИ …, ТО …», и т.д.

Под булевой функцией (БФ) понимают сложное высказывание. Это такая функция, которая принимает лишь два значения (0 или 1). БФ всегда конечна и обозначается f, F. Простые высказывания, входящие в БФ, называются переменными или аргументами и обозначаются x, y, z, … В БА нет линейных коэффициентов, нет деления, корня, логарифма и т.д. В БА, как правило, используется двоичная арифметика, да и то не в полном объеме.

Есть два типа реализации БФ: положительная логика и отрицательная логика. В положительной логике 0 (ложь) соответствует низкому уровню сигнала, а 1 (истина) – высокому. Соответственно в отрицательной логике – наоборот.

БФ одной переменной называется симвилярной функцией. Существуют четыре симвилярные функции. Они приведены в таблице ХХ.1.

Таблица ХХ.1 Симвилярные БФ

 

N     Обозначение Название
        Константа нуль
      Повторение
      Отрицание (инверсия)
        Константа единица
     

 

Хх.2 БФ двух переменных

 

БФ двух переменных называются бинарными.

Существует шестнадцать бинарных функций. Они приведены в таблице хх.2.

Таблица хх.2 БФ двух переменных

 

x y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
                  
                  
                  
                  
                 

 

F0=0; F1= ;

F2= ; F3= ;

F4= ; F5= ;

F6= ; F7= ;

F8= ; F9= ;

F10= ; F11= ;

F12= ; F13= ;

F14= ; F15=1.

 

Из всех возможных бинарных БФ выделяются нижеследующие основные.

Константа 0F0.

Константа 1F15.

Дизъюнкция (функция «ИЛИ», операция «ИЛИ», «ИЛИ», включающее «ИЛИ», соединение, логическое сложение) – БФ, таблица истинности (ТИ) которой соответствует F14 в таблице хх.2. Обозначается с помощью знака «+» или «Ú», например F=x+y (F=xÚy). Условное обозначение логического элемента (ЛЭ), реализующего дизъюнкцию (дизъюнктора), изображено на рисунке хх.1.а, а его временные диаграммы на рисунке хх.2.а.

Конъюнкция (функция «И», операция «И», «И», логическое умножение) – БФ, ТИ которой соответствует F8 в таблице хх.2. Обозначается так же, как произведение в обычной алгебре или с помощью знака «&» («Ù»), например F=x&y (F=xy). Условное обозначение ЛЭ, реализующего конъюнкцию (конъюнктора), изображено на рисунке хх.1.б, а его временные диаграммы на рисунке хх.2.б.

  
 
 


Отрицание (инверсия) и повторение – БФ, ТИ которых были приведены в таблице хх.1. Отрицание обозначается чертой, которая ставится над переменной. Например, отрицание переменной х, читаемое «НЕ х», записывается в виде . Условное обозначение ЛЭ, реализующего отрицание (инвертора), изображено на рисунке хх.1.в, а его временные диаграммы на рисунке хх.2.г. Условное обозначение ЛЭ, реализующего повторение (повторителя), изображено на рисунке хх.1.г.

Сложение по модулю два (исключающее «ИЛИ») – БФ, ТИ которой соответствует F6 в таблице хх.2. Обозначается с помощью знака «Å», например F=xÅy. Условное обозначение ЛЭ, реализующего сложение по модулю два, изображено на рисунке хх.1.д, а его временные диаграммы на рисунке хх.2.в.

Стрелка Пирса (функция «ИЛИ – НЕ») – БФ, ТИ которой соответствует F1 в таблице хх.2. Обозначается с помощью знака «¯». Условное обозначение ЛЭ, изображено на рисунке хх.1.е.

Штрих Шеффера (функция «И – НЕ») – БФ, ТИ которой соответствует F7 в таблице хх.2. Обозначается с помощью знака «/». Условное обозначение ЛЭ, изображено на рисунке хх.1.ж.

Равнозначность (эквивалентность) – БФ, ТИ которой соответствует F9 в таблице хх.2. Обозначается с помощью знака «º» или «~».

Импликация от х к у – БФ, ТИ которой соответствует F11 в таблице хх.2. Обозначается с помощью знака «®».

 

Предыдущая статья:Инструкция по работе с карточками Следующая статья:Хх.3 Понятие о СДНФ и СКНФ
page speed (0.0201 sec, direct)