Закон исключенного третьего

Основные понятия алгебры логики

Алгебра логики (алгебра Буля)

Алгебра логики изучает связь между переменными параметрами, принимающими только два значения:

"1" - логическая единица или "0" - логический нуль.

Если х ¹ 1, то х = 0, если х ¹ 0, то х = 1.

Логическая функция у=f(х₁,х₂,...,х_n) задана, когда каждому набору х однозначно сопоставляется у. Количество функций, образуемых n переменными равно.

Если n = 1, то N = 4: у₁ = 0,

у₂ = 1,

у₃ = х,

у₄ = /х.

Для двух переменных n = 2 и N = 16.

В таблице 6 приведены некоторые из возможных функций при n=2

х1	х2	у1	у2	у3	у4

Таблица 6 – Логические функции двух переменных

6.1.3. Аксиомы алгебры логики

х+0=х	х×0=0	х0=х
х+1=1	х×1=х	х1=х
х+х=х	х×х=х	хх=0
х+х=1	х×х=0	хх=1

Таблица 7 – Аксиомы алгебры логики

Их можно проверить подставляя вместо х 0 или 1.

6.2.4. Правила Де-Моргана:

Любые логические функции могут быть построены с использованием только элементов "И-НЕ" или только элементов "ИЛИ-НЕ". Переход от операции "И" к операции "ИЛИ", а также обратный переход осуществляется с помощью законов дуальности (теорема де Моргана):

В предыдущей строке показана типичная ошибка,когда полагают,что произведение инверсий равно инверсии произведения этих же переменных.

Закон поглощения

х₁+х₁×х₂ = х₁(1+х₂) = х₁×1 = х₁ х₁ “поглощает” х₂

6.2.5. Минимизация путем алгебраических преобразований

Пусть функция задана в виде таблицы:

х1	х2	х3	У

Таблица 8 – Функция, заданная в виде таблицы

Каждая строка таблицы представляет собой конъюнкцию переменных. Если значение переменной в данной строке равно 0, то переменная берется с инверсией.

Реализация полученного выражения с помощью элементов ”2и-не”:

Рисунок 2.5 – Реализация функции, заданной таблицей

6.1.6. Минимизация с помощью диаграмм Карно

Правило построения диаграммы Карно

Для n переменных заполняется прямоугольная таблица, содержащая 2ⁿ клеток так, чтобы в соседних клетках конъюнкции отличались не более, чем одним сомножителем.

Если минимизируемая функция при данном наборе переменных равна 1, то в соответствующую клетку ставится 1 (нули можно не ставить). В прямоугольной таблице единицы обводятся контурами и записывается функция в виде суммы произведений, описывающих контуры. Число клеток внутри контура 2^к (1,2,4,8...).

Следует покрыть все единицы возможно меньшим числом возможно более крупных блоков. Каждому блоку сопоставляется конъюнкция, записываемая следующим образом:

1)Если блок целиком лежит в единичной области переменной х_i, то она включается в конъюнкцию без инверсии, если в нулевой области, то с инверсией.

2) Если блок делится точно пополам между нулевой и единичной областями х_i,то х_i в конъюнкцию не включается (склеивание по х_i).

Других расположений правильно выбранного блока быть не может.

Например:

а) для двух переменных,заданных таблицей

б) для трех переменных:

6.3. Цифровые коды

6.3.1. Двоичный позиционный код

В обыденной жизни применяется десятичная система счисления, в которой используется 10 цифр от 0 до 9 и число представлено как сумма степеней числа 10. Например, число 1407 представляет сокращенную запись суммы 1*10³ +4*10² +0*10¹ +7*10⁰. В цифровой электронике чаще всего используется двоичная система счисления.

Двоичная (бинарная) система основана на степенях числа 2, оперирует только с двумя символами (цифрами): 0 и 1. Двоичная цифра (символ 0 и 1) является единичной элементарной информаци­ей, которая называется битом. Биты объединяются в слова определенной длины, слово длиною в 8 бит называется байтом, В насто­ящее время наиболее распространены системы с байтовой организацией данных. Поскольку в двоичной системе используется два символа, она имеет основание 2 и значения, которые должны быть приписа­ны отдельным позициям (веса), являются степенями числа 2.

Целые числа без знака в двоичной системе счисления представляются следующим образом:

a_m2^m+a_m-12^m-1+....+a₄ 2⁴+a₃ 2³+a₂ 2²+a₁ 2¹+a₀ 2°,где a_i=0,или 1

Наименьшая значащая цифра (младший разряд числа) здесь рас­положена справа, а слева последовательно каждая цифра представ­ляет собой более высокий разряд, более высокую степень числа 2. Например, код 1011 представляет число

1*2³+0*2²+1*2¹+1*2⁰=8+2+1=11

При сдвиге целого числа на одну позицию влево производится умножение на два, а при сдвиге на одну позицию вправо производит­ся деление на 2, что обусловлено основанием этой системы счисле­ния.

Перевод чисел из двоичной системы счисления в десятичную

Перевод выполняется путем сложения весов тех разрядов, в которых имеются единицы. Например:

Веса 2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰

Переводимое число 1 0 0 1 1 0 1 1

= 128 + 0 + 0 + 16 +8 + 0 + 2 + 1 =155

Дата добавления: 2014-01-07