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

Х*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