1.Постановка задачи минимизации формул алгебры логики.

Минимизация формул – вводится мера сложности (цена), среди всех возможных записей находится та, которая имеет минимальную стоимость.

При записи формул используются логические операции:,&. Операции сопоставляется ее цена с1, с2, с3,…

При записи некоторой формулы пусть операция встречается n1, n2, …, n5. Всего операции m=5. Стоимость операции :

Постановка задач: среди всех эквивалентных формул данной формулы найти ту, которая имеет минимальную стоимость.

Один из полных наборов операций: &, .

Считается, что стоимость операции .

Стоимость операции & и v одинакова.

Минимальная стоимость, где минимально кол-во & и v.

В качестве меры сложности (стоимости) принимается число вхождения букв. Считается, что любая переменная записывается как одна буква, поэтому число вхождения букв - число упоминаний переменных, а не число самих переменных.

Минимальная нормальная дизьюктивная форма – нормальная дизьюктивная форма, которая подобна исходной и имеет минимальное кол-во букв.

Минимальная нормальная форма – нормальная форма, которая минимальна среди двух классов: дизъюнкции и конъюнкции.

2.Сокращенные нормальные дизъюнктивные формы. Алгоритм Квайна.

Приведение к нормальной дизъюнктивной форме – тоже самое, что и минимизация.

Алгоритм Квайна:

1.Приведение к совершенно нормальной форме;

2.Приведение к сокращенной;

3. Получение всех тупиковых форм;

4. Выбор минимальной формы из числа тупиковых.

1. Основная идея сокращенной нормальной дизъюнктивной формы заключается в использовании боле коротких элементарных произведений, чем элементарных произведений максимальной длины.

Число элементов в элементарном произведении – длина.

Х1	Х2	f
0	0	1
1	0	0
0	1	0
1	1	0

- конституента 1 – максимальная длина.

Элемен. произведением длины n-1 (n – число переменных) имеет в таблице истинности две единицы: =

Элем. произведение длины n-k имеет единиц в таблице истинности.

Пример. F1=F1=

X1	X2	f1
0	0	1
1	0	1
0	1	0
1	1	1

Пусть имеются 2 формулы: f и . Пусть на конкретном наборе значений истинностиf принимает значения а1, а2, -а2. Говорят, чтоf накрывает своими значениями а1, а2, функцию . Функциявходит в функциюf , если она своими нулями накрывает все нули f.

F
0	0
1	0
0	0
1	1

- входит вf.

Если входит вf, то - импликантаf. импликация всегда «И».

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

Способов приведения к сокращенной нормальной дизъюнктивной форме много, но сама форма единственная.

Приведение по алгоритму Квайна:

Операция склеивания:

Операция неполного склеивания:

Операция поглощения:

Теорема Квайна:

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