Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Аналогичным образом можно построить процесс приведения КНФ к совершенному виду. Для этой цели к входящей в КНФ произвольной элементарной дизъюнкции q, не содержащей, например, переменной , добавляется равный нулю элемент . Затем к полученному выражению применяется второй дистрибутивный закон:

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

Пример: Выражение привести к СДНФ и СКНФ.

1.

2.

Синтез логических выражений.

Используя таблицу истинности любой логической формулы, можно определить ее в СДНФ или СКНФ. Для построения СДНФ в таблице истинности необходимо выбрать строки, в которых функция принимает значение 1 и сформировать конституанту 0. Переменная будет находиться в этой конституанте без знака отрицания, если она принимает значение 1 в этой строке и с отрицанием в противном случае. Соединить полученные конституанты знаком дизъюнкции.

Для получения СКНФ ищутся строки, в которых функция принимает значение 0. Строятся конституанты 1. Переменная берется со знаком отрицания, если она равна 1 и наоборот. Конституанты соединяются знаком конъюнкции.

Пример: Дана таблица истинности. Построить СДНФ и СКНФ.

x	y	z	f
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

СДНФ:

СКНФ:

Минимизация булевых функции

Под минимизацией булевых функций понимается нахождение наиболее простого представления этой функции в виде суперпозиции функций, составляющих какую-нибудь фиксированную функционально полую систему S булевых функций. Наиболее простым обычно считается представление, содержащее наименьшее возможное число суперпозиций. При решении задачи минимизации важную роль играет понятие импликанты.

Булева функция называется импликантой функции , если на любом значении переменных , на котором значение g равно 1, значение f также равно 1.

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

Дизъюнкция любого множества импликант одной и той же функции является импликантой этой функции.

Дизъюнкция всех простых импликант булевой функции совпадает с этой функцией и называется сокращенной дизъюнктивной нормальной формой.

Сокращенная нормальная форма является более экономной, чем СДНФ. Однако часто допускает дальнейшее упрощение за счет того, что некоторые из простых импликант могут поглощаться дизъюнкцией других простых импликант. Например, в сокращенной ДНФ простая импликанта yz поглощается дизъюнкцией остальных элементов формы: .

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

Приведение к минимальной нормальной форме от сокращенной ДНФ можно осуществит с помощью импликантной таблицы. Импликантная таблица представляет собой прямоугольную таблицу, строки которой обозначаются различными простыми импликантами, а столбцы конституантами единицы, на которых функция обращается в единицу.

На пересечении p-й строки k-го столбца импликантной таблицы ставится * тогда и только тогда, когда импликанта составляет некоторую часть конституанты k. Для примера:

	*	*
			*	*
				*	*
		*			*

Система S простых импликант булевых функций f называется приведенной, если эта система полна и никакая ее часть не является полной системой импликант функции f. Дизъюнкция всех простых импликант, составляющих S, называется приведенной или тупиковой дизъюнктивной нормальной формой. Всякая минимальная ДНФ является тупиковой ДНФ.

Выделение приведенной системы простых импликант может быть проведено на основе импликантной таблицы. Для этой цели надо выбрать минимальные системы строк таблицы так, чтобы для каждого столбца среди выбранных строк нашлась хотя бы одна строка содержащая звездочку. Этот метод является методом перебора и практически применим для простых импликантных таблиц. В случае сложных таблиц можно применять алгебраический метод Петрика.

Суть этого метода заключается в том, что по импликантной таблице строится некоторое выражение, называемое конъюнктивным представлением этой таблицы. Для этого производится обозначение всех простых импликант различными буквами (например, A, B, C, …). После этого для каждого столбца импликантной таблицы строится дизъюнкция

всех букв, обозначающих строки, на пересечении которых со столбцом стоит *. Беря произведение полученных q для всех столбцов, конъюнктивное представление таблицы. Обозначим для нашего примера : . Тогда получим следующее представление таблицы:

Если в конъюнктивном представлении раскрыть все скобки в соответствии с законом дистрибутивности, получим дизъюнктивное представление.

Простые импликанты, символы которых в любой фиксированный терм дизъюнктивного представления составляют полную систему простых импликант функции.

Выполняя в дизъюнктивном представлении импликантной таблицы все элементарные поглощения и устраняя повторения в соответствии с тождествами АА=А и АА = А, приходим к приведенному дизъюнктивному представлению импликантной таблицы.

Термам этого представления соответствуют все приведенные системы простых импликант функции.

В примере получим:

То есть получим 2 приведенные системы простых импликант (A, B, C) и (A, B, D). Им соответствуют две тупиковые ДНФ исходной функции:

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

1.Минимизируемая булева функция f от произвольного числа n переменных записывается в СДНФ f₀.

2.Начиная с f₀, строим последовательность ДНФ f₀, f₁, . . ., f_i, . . . до тех пор пока две какие либо ДНФ f_k и f_k+1 не совпадут между собой. Переход от формы f_i к f_i+1 по следующему правилу: в форме f_i выполняются все операции неполного склеивания

Применимые к элементарным произведениям длины n = . После этого исключаются все те элементарные произведения длины , которые могут быть исключены на основании формулы элементарного поглощения:

.

3.Результатом алгоритма Квайна к функции f является заключительная ДНФ f_k.

Для любой булевой функции f результатом применения алгоритма Квайна к СДНФ будет сокращенная ДНФ этой функции.

Пример:

Операцию неполного склеивания можно применить к 1 и 3 элементу формулы, к 1 и 2, а также к 1 и 4. В результате получим:

Применяя формулу поглощения, получим:

Поскольку операция неполного склеивания дальше неприменима, f₁ – сокращенная ДНФ.

Диаграмма Вейча

Диаграммы Вейча фактически представляют собой другую запись таблиц истинности и в простейшем случае для булевых функций двух, трех и четырех переменных имеют вид:

Для осуществления минимизации в таблице необходимо выделить смежные элементы, которыми являются для матрицы A элементы и . Причем, операция сложения выполняется по модулю n, где n – размерность матрицы. Таким образом, элементы из первой и последней строки, из первого и последнего столбца могут быть смежными. Затем выбираются группы смежных элементов, количество которых должно быть степенью двойки. Эти группы определяют импликанты. Причем количество сомножителей в импликанте определяется как , где n – число аргументов функции, - степень двойки для группы элементов. При составлении импликанты исключаются переменные, для которых единица имеется и в части отрицания для переменной и в части, где отрицание отсутствует. Необходимо выбрать группы так, чтобы их количество было минимально, и все единицы в таблице входили бы в группы (выбираются группы с максимальным ). Полученные импликанты связываются знаком дизъюнкции.

Пример:

F=

Синтаксис, семантика и правила вывода в исчислении высказываний

Синтаксис исчисления высказываний определяется правилами грамматики:

Предложение : = Элементарное предложение / Сложное предложение

Сложное предложение : = Предложение Связка Предложение / ^Предложение / (Предложение)

Характеристики

Список файлов книги