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

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 4Следующая ⇒

В алгебре логике 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

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры