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

В алгебре логике 8 законов

 

 

1. Переместительный (закон коммунитивности) – для сложения и умножения

 

Х₁^Х₂ = Х₂^Х₁             Х₁*Х₂ = Х₂ *Х₁

 

  2. Сочетательный    (закон ассоциативности) для сложения и умножения)

 

    (Х₁^Х₂)^Х₃=Х₁^(Х₂^Х₃)

    (Х₁*Х₂)*Х₃=Х₁(Х₂*Х₃)

 

3.  Распределителный  (закон дистрибутивности) – для (     ^)

 

1-й закон

 

(Х₁ ^ Х₂) *Х₃ = Х₁*Х₃ ^ Х₂*Х₃ правило раскрытия скобок

 

2-й закон

(Х₁^Х₂) ^Х₃ = (Х₁*Х₃) ^ (Х₂^Х₃) правило взятия вскобки

 

4. Тождества (закон товтологии)

 

Х^Х^Х^…..^Х = Х

Х*Х*Х*….*Х = Х

 

5. Повторения

                  

 Х*Х = 1

Логическое произведения любого высказывания и его отрицание всегда ложно

 

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

Х^Х = 1

Логическая сумма любого высказывания и его отрицания всегда истина

 

7. Достаточного основания

1 ^ Х₁ ^ Х₂ ^ Х₃ = 1

Если в логической сумме высказывания хотябы одно истинно, то сложное высказывание истинно.

 

8. Двойное отрицания

 

Х = Х

 

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

1. Старшинства операций Последовательность выполнения логических операций

 

- отрицание

-умножение

- сложение

2. Двойственности (де Моргана или инверсии)

     Х₁^Х₂ = Х₁*Х₂

     Х₁*Х₂ = Х₁^Х₂

Справедливо для n-переменных

 

1. Склеивание (по некоторой переменной)

F(X_1,X₂) = X₁*X₂^X₁*X₂ = [СОГЛАСНО ЗАКОНА ДИСТРИБУТИВНОСТИ]=

       =X₁(X₂^X₂) = [ИСКЛЮЧЕННОГО ТРЕТЬЕГО] =X₁ («склеивание» по переменной Х₂)

 

      F(X_1,X₂) = (X1^X2) (X₁^X₂) = [закон дистрибутивности] =

      = X₁*X₁^X₁*X₂^X₁*X₂^X₂*X₂ =  X₁^X₁*X₂^X₁*X₂ = X₁^X₂ = X₁

                                                                  з-н противоречия           склеивание по Х₂   тождество

 

     

1. «Поглощение»

      

           F(Х_1,Х₂)=Х₁^Х₁*Х₂ = [дистрибутивный закон]=Х₁(1^Х₂)=[достаточного основания]= Х₁*1=Х₁

«поглощение произведения Х₁*Х₂ переменной Х₁

 

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

Х*1=Х   Х^1=1

Х*0=0    Х^0=Х

0=1         1=0

0=0         1=1

 

Следствия

Х₁^Х₂= Х₁^Х₂=Х₁*Х₂;       Х₁*Х₂=Х₁*Х₂=Х₁^Х₂

 

 

- возможность выражать дизъюнкцию через конъюнкцию и отрицание

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

 

Представление ФАЛ

 

 

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

 

Существует много способов описания ЦА.

 

- табличный

- с помощью ФАЛ (аналитический);

- секвенциальное

- с помощью граф-схем и логических схем алгоритмов и др.

 

 

Первый способ представлен в табл. 1 и Табл. 2. В них каждому из возможных наборов переменных ставится в соответствие значение функции (0 или 1) Этот способ нагляден и может быть применен для представления функции любого числа переменных. Однако для больших n  такая форма уже не компактна, т.к. таблица будет громоздкой. Кроме того, в табличной форме преобразование данных затруднено.

 

Таблица, описывающая работу ЦА, называется таблицей истинности. Ее построение является чаще всего лишь первым этапом при проектировании сложных ЦА, в том числе и ЭВМ.

Проще выглядит аналитическая запись переключательной функции в виде формул.

 

Прежде рассмотрим элементарные понятия

 

Терм – языковое выражение, обозначающее объекты. Симтатически характеризуется тем, что термы можно подставлять вместо переменных в другие выражения языка – термы и формулы, получая при этом соответственно новые термы и формы.

 

Минтермом – или конституэнтой еденицы называют функцию принимающие еденичное значение при фиксированном наборе аргументов.

Макстермом – или конституэнтой нуля называют функцию принимающую нулевое значение при фиксированном наборе аргументов.

 

Например

 

		F(X1,X2)
X1	X2
0	0	Макстермы      Минтермы   1
0	1	0
1	0	0
1	1	1

                    

 

Суммарное число минтермов и макстермов совпадает с числом наборов различных аргументов.

Элементарная конъюнкция (дизъюнкция) – это конъюнкция (дизъюнкция), в которой конъюнктивно (дизъюнктивно), связано конечная множество логических переменных и их отрицания

Например Х₁^Х₂^Х₃ или Х₁*Х₂*Х₃*Х₄

             r = 3               r = 4

  Число переменных, составляющих элементарную конъюнкцию (дизъюнкцию), называется ее рангом r

Рассмотрим различные формы аналитической записи переключательной функции.

Нормальные формы -  представляют лишь дизъюнкции элементарных конъюнкций или             конъюнкцию элементарных конъюнкций.

 

 Нормальная форма, представляет дизъюнкций элементарных конъюнкций   

F_диф. (Х₁,Х₂,Х₃)= Х₁*Х₂*Х₃^Х₁*Х₂, называется ДИФ нормальная форма, представленная конъюнкций элементарных дизъюнкций

 

F_диф. (Х₁,Х₂,Х₃)=(Х₁^Х₂)(Х₁^Х₃)(Х₁^Х₂), называется КНA