microbik.ru
  1 2 3 ... 11 12
^

Законы алгебры логики



АЛ базируется на нескольких аксиомах, из которых выводят основные законы для преобразований с логическими переменными. Каждая аксиома представлена в двух видах, что вытекает из принципа дуальности логических операций, согласно которому операции конъюнкции и дизъюнкции допускают взаимную замену, если одновременно поменять 1 на 0, 0 на 1, знак  на , а знак  на .

Аксиомы операции отрицания: , .

Аксиомы операций конъюнкции и дизъюнкции:

1а) 00=0 1б) 11=1

2а) 10=01=0 2б) 01=10=1

3а) 11=1 3б) 00=0

Законы АЛ вытекают из аксиом и также имеют две формы выражения а) и б).

  1. Переместительный закон

а) ab=ba б) ab=ba

  1. Сочетательный закон

а) a(bc)=(ab)c=abc б) a(bc)=(ab)c=abc

  1. Закон тавтологии

а) aa=a б) aa=a

  1. Закон обращения: если a=b, то

  2. Закон двойной инверсии: =a

  3. Закон нулевого множества

а) a0=0 б) a0=a

  1. Закон универсального множества

а) a1=a б) a1=1

  1. Закон дополнительности

а) a =0 б) a =1

  1. Распределительный закон

а) a(bc)=ab+a б) a(bc)=(ab)( ac)

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

а) aab=a б) a(ab)=a

  1. Закон склеивания

а) (ab)(a)=a б) a.b a.=a

  1. Закон инверсии (закон Де Моргана)

а) б)

или после инвертирования

в) г)


    1. ^

      Произвольные функции и логические схемы



Поскольку значениями логических функций могут быть только 0 или 1, то любые логические функции можно использовать как аргументы других логических функций, т.е. строить из простых функций более сложные. Пусть в таблице 1.2. задана произвольная функция Y трех аргументов, и ее нужно выразить с помощью простых функций НЕ, И, ИЛИ.

Очевидно, что Y = 1, когда или ac = 1 (строка 1), или (строка 3), или (строка 6), или (строка 7).


Таблица 1.2.



Аргументы

Функция



Аргументы

Функция




a

b

c

Y




a

b

c

Y

0

0

0

0

0

4

1

0

0

0

1

0

0

1

0

5

1

0

1

1

2

0

1

0

0

6

1

1

0

1

3

0

1

1

1

7

1

1

1

1


Все это можно записать в виде одного общего аналитического выражения: (1.1)

Полученное аналитическое выражение называют совершенной дизъюнктивной нормальной формой (СДНФ). СДНФ состоит из элементарных конъюнкций, соединенных знаками дизъюнкций. Конъюнкцию называют элементарной, если в нее не входит по несколько одинаковых букв. Число элементарных конъюнкций в СДНФ обязательно равно числу единичных значений функции в таблице истинности. В каждую элементарную конъюнкцию СДНФ входят обязательно все аргументы функции в прямой или инверсной форме.

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

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

НЕ, И; НЕ, ИЛИ; И-НЕ и ИЛИ-НЕ.

Для построения логической схемы, реализующей функцию, заданную таблицей истинности, обычно удобнее аналитическая форма представления функции. В данном случае - это выражение (1.1). Схема, реализующая (1.1), показана на рис. 1.6. Она состоит из трех ярусов. В первом ярусе расположены инверторы. Очевидно, что максимальное число инверторов не превышает числа аргументов. Во втором ярусе расположены элементы И, реализующие входящие в формулу элементарные конъюнкции. Число входов каждого элемента равно числу аргументов реализуемой функции, а число элементов- числу элементарных конъюнкций в формуле. В третьем ярусе схемы стоит элемент ИЛИ, число входов которого равно числу дизъюнкций в формуле.


Рис.1.6. Логическая схема, реализующая (1.1).



<< предыдущая страница   следующая страница >>