11. Основные понятия алгебры логики

Алгебра логики - это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.  Логическое высказывание - это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.  Считается, что если выражение ложно, то оно имеет значение 0, а если выражение истинно, то - 1. Чтобы обращаться к логическим высказываниям, им назначают имена А, В, С или x, y, z.  Слова и словосочетания "не", "и", "или", "если... , то", "тогда и только тогда" и другие называются логическими связками и позволяют из уже заданных высказываний строить новые высказывания.  Высказывания, образованные из других высказываний с помощью логических связок, называются составными. Высказывания, не являющиеся составными, называются элементарными.

Функцией алгебры логики f(x₁, x₂, ... ,x_n) от n - переменных x₁, x₂, ... ,x_n, принимающих значения 0 или 1, называется функция, принимающая значения 0 или 1.  Функция задается с помощью таблицы истинности.

Суперпозицией функций f₁,...,f_m называется функция f, полученная с помощью подстановок этих функций друг в друга, а формулойназывается выражение, описывающее эту суперпозицию.  Для записи формулы функции алгебры логики необходимо либо перечислить все ситуации, в которых она истинна, либо исключить все ситуации, в которых она ложна. 

12. Метод Куайна-Маккласки

Метод минимизации логических функций Куайна-Маккласки основан на том факте, что вынос общего множителя за скобки в формуле эквивалентен объединению двух строк в одну в таблице истинности. В комбинируемых строках должны совпадать все значения переменных, кроме одной - сравниваемые строки отличаются на одну единицу. Значение "не совпавшей" переменной безразлично и может быть обозначено звездочкой "*". Например, указанные ниже две строки

x1	x2	x3	f
1	0	1	1
1	1	1	1

можно заменить одной строкой:

x1	x2	x3	f
1	*	1	1

т. к. в этой строке значение переменной x₂ не влияет на значение функции.  Познакомимся с этим методом на примере минимизации логической функции, заданной таблицей истинности:

№ строки	x1	x2	x3	f
1	0	0	0	0
2	0	0	1	0
3	0	1	0	1
4	0	1	1	1
5	1	0	0	0
6	1	0	1	0
7	1	1	0	1
8	1	1	1	1

Запишем еще раз таблицу истинности для функции f с указанием для единичных наборов количества единиц в значениях переменных:

№ строки	x1	x2	x3	f	Кол-во единиц
1	0	0	0	0
2	0	0	1	0
3	0	1	0	1	1
4	0	1	1	1	2
5	1	0	0	0
6	1	0	1	0
7	1	1	0	1	2
8	1	1	1	1	3

Разобьем таблицу на группы строк с одинаковым количеством единиц, удалив из таблицы строки с нулевым значением функции:

№ строки	x1	x2	x3	f	Кол-во единиц
3	0	1	0	1	1
4	0	1	1	1	2
7	1	1	0	1	2
8	1	1	1	1	3

Сравним наборы значений переменных каждой предыдущей группы с последующей и объединим строки с общим множителем:

№ строки	x1	x2	x3	f	Кол-во единиц
3, 4	0	1	*	1	1
3, 7	*	1	0	1	1
4, 8	*	1	1	1	2
7, 8	1	1	*	1	2

Объединим строки с совпадающими позициями "крестиков":

№ строки	x1	x2	x3	f	Кол-во единиц
3, 4, 7, 8	*	1	*	1	1
3, 7, 4, 8	*	1	*	1	1

Из двух идентичных строк оставляем только одну:

№ строки	x1	x2	x3	f	Кол-во единиц
3, 4, 7, 8	*	1	*	1	1

В результате минимальная формула логической функции f будет иметь вид:  f=x₂