Логическое и функциональное программирование (стр. 6 из 16)

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

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

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

. Тогда получим следующее представление таблицы:

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

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

Выполняя в дизъюнктивном представлении импликантной таблицы все элементарные поглощения

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

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

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

То есть получим 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 – число аргументов функции, - степень двойки для группы элементов. При составлении импликанты исключаются переменные, для которых единица имеется и в части отрицания для переменной и в части, где отрицание отсутствует. Необходимо выбрать группы так, чтобы их количество было минимально, и все единицы в таблице входили бы в группы (выбираются группы с максимальным ). Полученные импликанты связываются знаком дизъюнкции.

Пример:

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

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

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

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

Связка : = Ù / Ú / ^ / ® / »

Семантика исчисления высказываний определяется с помощью таблиц истинности.

К правилам вывода относятся:

1.

Если посылка А есть истина, то и заключение В есть истина.

2.Исключение И:

Знание того, что А и В есть истина, должно означать, что А есть истина и В есть истина.

3.Интродукция ИЛИ:

Если А есть истина, то А или В есть истина. То же самое имеет место, если В есть истина.

4.Интродукция И:

Если А есть истина и В есть истина, то А И В есть истина.

5.Двойное отрицание:

Если А есть не не истина, то А есть истина.

6.Единичная резолюция:

Если А или В есть истина и не В, то А есть истина. Точно также, если не А, то В – истина.

7.Резолюция:

Если А или В и не В или С, то, поскольку В не может быть истинно и ложно одновременно, должно быть А или С истинно.

Пример: Имеется следующая информация.

Если аккумулятор машины разряжен, то машина не заводится. Если машина Ивана не заводится и текущее время оказывается позже восьми часов утра, то Иван опоздает на поезд. Однажды после восьми утра аккумулятор Ивана оказался разряженным.

Используя логические правила вывода, доказать, что Иван опоздает на поезд.

В символьных обозначениях информация может быть представлена в следующем виде:

P: аккумулятор разряжен.

Q: машина не заводится.

R: время после восьми утра.

S: Иван опоздал на поезд.

Правило 1: P®Q.

Правило 2. QÙR ® S.

Известно, что P и R есть истина. Задачей является доказать S. Доказательство строится следующим образом:

1. P – дано.

2. R – дано.

3. Q следует из 1 и правила 1 по правилу modesponens.

4. QÙR следует из 3 и 2 по правилу интродукции И.

5. S следует из 4 и правила 2 по правилу modesponens.

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

Практические задания

Задание 1

Даны логические функции:

Получить значения этих функций с помощью таблиц истинности. Преобразовать к алгебраическому виду и определить значения для x =1, y =1, z = 0. Преобразовать к виду с использованием только операций дизъюнкции, конъюнкции и отрицания. Упростить. Привести к СДНФ и СКНФ. Восстановить СДНФ и СКНФ по таблице истинности. Построить импликантную таблицу и определить сокращенную ДНФ с использованием метода Петрика. Минимизировать с использованием алгоритма Квайна и диаграммы Вейча.