Билет 15.

Минтермы, макстермы и их свойства.

Минтермом ранга n с номером j - называется конъюнкция n логических переменных, каждая из которых входит ровно 1 раз в прямой или инверсной форме, причем j- номер минтерма, соотв. двоичному набору с номером j в котором каждая переменная, входящая в прямой форме соответствует единице, а в инверсной – 0.

Свойства:

1) любой минтерм n-ого ранга с номером j равен единице на одном единственном наборе, номер которого равен номеру минтерма.

пример

на любом другом наборе получится 0

2) Дизъюнкция всех минтермов n ранга равна 1.

Макстермом ранга n с номером j называется n местная ФАЛ в форме дизъюнкции n логических переменных, каждая из которых входит ровно 1 раз в прямой или инверсной форме, причем j= (противоположный набор), где j соответствует двоичному набору в котором каждая переменная, входящая в прямой форме соотв. единице, а в инверсной – 0.

Свойства:

1) любой макстерм n-ого ранга с номером j равен нулю на одном единственном наборе, номер которого противоположен номеру макстерма. получается j= Например для 5 макстерма нужен набор j= . Он же получается инверсией значений на пятом наборе.

2) Конъюнкция всех макстермов n-ого ранга равна нулю.

Билет 16.

Разложение ФАЛ.

Любую ФАЛ можно представить с помощью конъюнкции, дизъюнкции и отрицания.

1)Любая ФАЛ кроме константы 0 может быть представлена в форме дизъюнкции минтермов максимального ранга, соответствующих наборам на которых эта функция равна единице.

f(x1,x2,…,xn)= Это будет СДНФ. Если функция представлена в виде дизъюнкции минтермов не обязательно максимального ранга, то она просто дизъюктивная нормальная форма (ДНФ)

2) Любую ФАЛ, кроме константы единицы может быть представлена в форме конъюнкции макстермов максимального ранга равных нулю, на наборах противоположных наборам T0.

f(x1,x2,…,xn)= (можно брать наборы на которых функция равна нулю и инвертировать все значения переменной.) Если функция представлена в виде конъюнкции макстермов не обязательно максимального ранга, то она просто конъюктивная нормальная форма (КНФ). ДНФ из СДНФ получается склейками и поглощениями.

3) Полиномиальная форма

Используют запись в полиномиальной форме, вместо дизъюнкции используют .

При записи в форме СДНФ для каждого набора j из T1 равен 1 будет только 1 минтерм, вместо дизъюнкции можно , т.е.

f(x1,x2,…,xn)= = все инверсии можно заменить Это СПНФ.

Билет 17.

СДНФ, построение и свойства.

Любая ФАЛ кроме константы 0 может быть представлена в форме дизъюнкции минтермов максимального ранга, соответствующих наборам на которых эта функция равна единице.

f(x1,x2,…,xn)= Это будет СДНФ. Если функция представлена в виде дизъюнкции минтермов не обязательно максимального ранга, то она просто дизъюктивная нормальная форма (ДНФ)