Минимизация булевых многочленов

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

Лемма 1. Любая ДНФ p эквивалентна некоторой сокращенной ДНФ.

Сокращенную ДНФ формы p можно получить методом Квайна с помощью последовательного применения следующих двух видов операций:

1) операция склеивания, которая для конъюнктов q и булевых переменных x определяется по формуле:

;

2) операция поглощения, которая для конъюнктов q, булевых переменных x и значений определяется по формуле:

.

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

Тупиковые ДНФ с наименьшим числом вхождений в них булевых переменныхназываются минимальными ДНФ.

Лемма 2. Любая ДНФ p эквивалентна некоторой минимальной ДНФ.

Минимальная ДНФ формы p получается с помощью матрицы Квайна:

- столбцы матрицы помечаются конъюнктами формы p ;

- строки матрицы помечаются импликантами сокращенной ДНФ формы p ;

- на пересечении строки и столбца ставится символ *, если импликант является частью конъюнкта .

Тупиковые ДНФ - дизъюнкции тех минимальных наборов импликант, в строках которых имеются звездочки для всех столбцов матрицы Квайна.

Тупиковые ДНФ с наименьшим числом вхождений булевых переменных являются искомыми минимальными ДНФ формы p .

Следствие 3. Любая булева функция, не равная тождественно нулю, представима минимальной ДНФ и любая булева функция, не равная тождественно единице, представима минимальной КНФ.

Логика предикатов

Понятие предиката

Определение. Предикатом называется утверждение, содержащее переменные , которое превращается в высказывание при замене этих переменных конкретными объектами из некоторой области возможных значений.

Обозначаются предикаты

Переменные , называются предметными или индивидуальными переменными. Число предметных переменных в предикате называется его арностью или местностью.

Более точно, предикат P с n предметными переменными называется n-арным или n-местным предикатом и обозначается .

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

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

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

Такое n-арное отношение обозначается символом P⁺ и называется множеством истинности предиката P на множестве M.

Определение. Предикат на множестве M называется:

- тождественно истинным, если для любых значений высказывание истинно, т.е. P⁺=Mⁿ;

- тождественно ложным, если для любых значений высказывание ложно, т.е. P⁺ = Æ;

- выполнимым, если для некоторых значений высказывание истинно, т.е. P⁺ ¹ Æ;

- опровержимым, если для некоторых значений высказывание ложно, т.е. P⁺ ¹ Mⁿ.

Определение. Пусть предикаты одинаковой арности и рассматриваются на множестве M. Тогда:

- предикаты и называются эквивалентными, если P⁺ = Q⁺, т.е. при любых значениях высказывание истинно в том и только том случае, если истинно высказывание ;

- предикат называется следствием предиката , если P⁺ Ì Q⁺, т.е. при любых значениях из истинности высказывания следует истинность высказывания .

Алгебра предикатов

Высказывания являются утверждениями без предметных переменных, их можно рассматривать как 0-местные предикаты.

Значит, множество всех высказываний содержится в множестве всех предикатов и рассмотренные выше логические операции над высказываниями можно естественно продолжить на предикаты.

Отрицание n-местного предиката определяется как n-местный предикат , который при подстановке значений превращается в высказывание , являющееся отрицанием высказывания ;

Конъюнкция n-местных предикатов и определяется как n-местный предикат , который при подстановке значений превращается в высказывание , являющееся конъюнкцией высказываний и .

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

, ,

, ,

.

Для предикатов определены принципиально новые унарные операции – операции квантификации, или операции действия на предметные переменные кванторами.

Для каждой предметной переменной x рассматриваются два вида кванторов: – квантор общности по переменной x (читается «для всех x») и – квантор существования по переменной x (читается «существует x»).

Определение.

Результатом действия квантора общности по переменной x на одноместный предикат называется высказывание , которое истинно на множестве M допустимых значений переменной x в том и только том случае, если предикат тождественно истинен на этом множестве M.

Определение.

Результатом действия квантора существования по переменной x на одноместный предикат называется высказывание , которое истинно на множестве M допустимых значений переменной x в том и только том случае, если предикат выполним на этом множестве M.

Определение.

Результатом действия квантора общности по переменной x₁на n-местный предикат называется (n-1)-местный предикат , который зависит от переменных и который при значениях в том и только том случае истинен на множестве M допустимых значений переменной x₁, если при любых значениях высказывание истинно.

Определение.

Результатом действия квантора существования по переменной x₁на n-местный предикат называется (n-1)-местный предикат , который зависит от переменных и который при значениях в том и только том случае истинен на множестве M допустимых значений переменной x₁, если при некотором значении высказывание истинно.Квантор существования и единственности определяется как сокращение записи следующей формулы

.

Результат действия такого квантора на предикат обозначается и читается «существует и единственен x, для котороговыполняется »).

Ограниченный квантор существования определяется как сокращение записи следующей формулы

.

Результат действия такого квантора на предикат обозначается и и читается «существует x, удовлетворяющий , для котороговыполняется ».

Ограниченный квантор общности определяется как сокращение записи следующей формулы

.

Результат действия такого квантора на предикат обозначается и читается «для всех x, удовлетворяющих , выполняется ».

Определение.

Алгеброй предикатов называется множество всех предикатов P с логическими операциями и операциями квантификации , для всех предметных переменных x.

Не нашли, что искали? Воспользуйтесь поиском по сайту: