6.6. Логическое следствие

Формула X алгебры высказываний называется логическим следствием формул X₁, X₂, ..., X_n, если импликация X₁X₂ ... X_n  X является тавтологией. В этом случае говорят, что из X₁, X₂, ..., X_n следует X и этот факт записывают в виде

.

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

X₁, X₂, ..., X_n  X.

Распространенными схемами правильных рассуждений являются следующие:

– условно-категорический силлогизм;

– условно-категорический силлогизм;

– гипотетический силлогизм.

6.6.1. Алгоритм проверки правильности рассуждений

Проверка правильности рассуждений или проверка того, что данная формула X является логическим следствием формул X₁, X₂, ..., X_n осуществляется по следующему алгоритму.

1. Образовать конъюнкцию посылок X₁, X₂, ..., X_n.

2. Составить импликацию X₁  X₂ ... X_n  X.

3. Полученную формулу исследовать на тождественную истинность: если она является тождественно истинной, то X является логическим следствием формул X₁, X₂, ..., X_n, иначе – не является.

Пример. Если два числа равны, то, как известно, их модули равны. Данные числа не равны. Можно ли из этого заключить, что их модули не равны?

Рассмотрим следующие элементарные высказывания: X= «Два числа равны», Y= «Модули чисел равны». Тогда высказыванию «Если два числа равны, то, как известно, их модули равны» соответствует формула XY, высказыванию «Данные числа не равны» – , высказыванию «Модули чисел не равны» – . Заметим, что вопрос задачи сводится к проверке правильности рассуждений, то есть является ли логическим следствием посылок и X  Y:

.

Составив таблицу истинности формулы (XY)  , можно увидеть, что она не является тождественно истинной, следовательно, рассуждения не являются правильными, и утверждение «Модули чисел не равны» не верно.

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

6.6.2. Алгоритм определения всех логических

следствий из данных посылок

1. Образовать конъюнкцию всех посылок X₁, X₂,..., X_n.

2. Полученную конъюнкцию привести к СКНФ.

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

Пример. Найти все следствия из посылок XY иXYX Y.

Образуем конъюнкцию посылок и найдем ее СКНФ.

(X Y)(X  Y  X Y)(X Y)(X  Y)(X Y)

(X Y)(X  Y) – СКНФ. Тогда следствиями являются XY; X  Y; (X Y)(X  Y).

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

6.6.3. Алгоритм определения всех посылок, логическим следствием которых является данная формула

1. Данную формулу привести к СКНФ.

2. Составить ее произведения с каждым из недостающих до соответствующей полной СКНФ множителей – по одному, по два и так далее (под полной понимается СКНФ тождественно ложной формулы с теми же переменными).

Пример. Следствием каких посылок является импликация XY?

Для импликации XY СКНФ имеет вид . Соответствующая полная СКНФ имеет вид

.

Образуем всевозможные произведения с недостающими сомножителями:

(X  Y)(X  Y)  Y;

(X  Y)(X Y)  XY;

(X  Y)(X Y) X;

(X  Y)( X  Y)  (X Y)  XY;

(X  Y)( X  Y) (X  Y)  XY;

(X  Y)  (X Y) (X Y)  XY;

(X  Y)( X  Y) (X  Y) (X Y)  0;

6.7. Минимизация булевых функций в классе ДНФ

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

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

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

Будем говорить, что функция f₁ своим значением С₁ накрывает значение С₂ функции f₂, если на некотором наборе (x , x , ..., x )=С₁

f₁(X , X , ..., X )=С₁; f₂(X , X , ..., X )=С₂ .

Функцию f₁ назовем импликантой функции f₂, если она своими нулями накрывает все нули функции f₂.

Справедливы следующие теоремы:

Теорема 6.7.1. Если f₁, f₂,...,f_n – импликанты переключательной функции f, то

f₁ f₂...f_n и f₁ f₂...f_n

также являются импликантами функции f.

Теорема 6.7.2. Если функция f₁ f₂...f_n есть импликанта функции f, то функции f₁, f₂, ..., f_n также являются импликантами функции f.

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

Пример.

Простыми импликантами функции

f= (X₁ X₂)( X₁ X₂)

являются функции X₁ X₂ и X₁ X₂.

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

ДНФ данной булевой функции, составленная из простых импликант, называется сокращенной ДНФ. Может случиться, что некоторые простые импликанты могут быть удалены и при этом значение функции не изменится ни на одном наборе. Такие простые импликанты называются лишними. Сокращенная ДНФ, из которой удалены все лишние импликанты, называется тупиковой ДНФ. Можно показать, что всякая тупиковая ДНФ является минимальной. Чтобы от сокращенной ДНФ перейти к минимальной, можно воспользоваться импликантной матрицей, в которой каждой строке соответствует простая импликанта, а каждому столбцу – конституента СДНФ данной переключательной функции. Импликантная матрица заполняется следующим образом: под конституентами, в которые входит данная простая импликанта, ставится «+», иначе «-». Каждая из конституент равна 1 лишь для одного набора аргументов. Для этого набора аргументов будут равны 1 те простые импликанты, которые расположены в строках, отмеченных «+». Поэтому, чтобы накрыть единицами все единицы данной булевой функции, достаточно оставить такие простые импликанты, чтобы в каждом столбце был хотя бы один «+».

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

склеиванием по переменной Х в СДНФ называется равносильное преобразование типа

(X F)( F)F;

поглощением в СДНФ называется равносильное преобразование типа

(F X)FF.

Следующая последовательность шагов описывает метод Квайна минимизации булевой функции.

Шаг 1. Привести булеву функцию к СДНФ.

Шаг 2. В СДНФ произвести все возможные склеивания, а затем поглощения. Полученная на этом шаге ДНФ является сокращенной – она состоит из минимальных по числу множителей конъюнкций, но среди конъюнкций могут оказаться лишние.

Шаг 3. Перейти от сокращенной ДНФ к минимальной, используя импликантную матрицу.

Пример. Определить МДФ для переключательной функции

Решение. Для определения МДФ булевой функции воспользуемся методом Квайна. Приведем булеву функцию к СДНФ:

Перейдем от СДНФ к ДНФ, используя операции склеивания и поглощения:

Построим импликантную таблицу

	+	+	-
	-	-	+

Чтобы накрыть единицами все единицы данной переключательной функции, достаточно оставить такие простые импликанты, чтобы в каждом столбце был хотя бы один “+”. Как видно, ни одно из слагаемых сокращенной формы исключить нельзя, поэтому МДФ имеет вид

6.8. Полнота систем булевых функций

Система функций {f₁, f₂,..., f_n} называется полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Возможность представления всякой булевой функции в ДНФ свидетельствует о том, что составляют полную систему булевых функций по отношению к множеству всех булевых функций, то есть множество булевых функций, реализуемых с помощью конъюнкции, дизъюнкции и отрицания, есть множество всех булевых функций. Возникает вопрос о построении других полных систем булевых функций. Очевидно, что полной окажется всякая система булевых функций, с помощью которой можно построить . Согласно свойству , то есть дизъюнкция может быть построена с помощью конъюнкции и отрицания. Следовательно, {, } составляют полную систему функций. Аналогично можно получить, что полную систему функций составляет {, }.

Пусть D={f₁, ..., f₅ } – произвольная система булевых функций, тогда справедлив следующий критерий полноты.

Теорема Поста. Система D булевых функций является полной тогда и только тогда, когда выполняется пять условий: существует функция f_iD, не сохраняющая константу 0; функция f_iD, не сохраняющая константу 1; нелинейная функция; несамодвойственная функция и немонотонная функция в системе D.

Функция f (X1,…,Хn) называется функцией, сохраняющей константу 0, если f (0,…,0)=0.

Функция f (X1,…,Хn) называется функцией сохраняющей константу 1, если f (1,…,1)=1.

Функция f *(X1,…,Хn) называется двойственной функцией f (X1,…,Хn), если .

f* (X1,…,Хn) = f (X1,…,Хn).

Функция f (X1,…,Хn) называется самодвойственной, если

f (X1,…,Хn) = f* (X1,…,Хn)

Функция f (X1,…,Хn) называется монотонной, если для любых двух наборов X= (X1,…,Хn) и Y= (Y1,…,Yn), таких, что X≤Y (для любого i, Xi≤Yi), имеет место неравенство

f (X1,…,Хn) ≤f(Y1,…,Yn).

Функция f (X1,…,Хn) называется линейной, если

f (X1,…,Хn) = C0+C1X1+…+CnXn

где Ci {0,1}, а + - операция сложения по модулю два.

Замечания.

1. Монотонность переключательной функции проверяется с помощью таблицы истинности.

2. Чтобы определить, является ли функция линейной, нужно построить многочлен Жегалкина.

Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше чем в первой степени. Каждая переключательная функция может быть представлена многочленом Жегалкина, причем такое представление единственно. В основе его лежит переход к операциям  и +, при этом

0+X=X; 1+X=X.

Чтобы построить многочлен Жегалкина нужно выполнить следующие действия:

3. В выражении для переключательной функции перейти к операциям ,  ;

4. X заменить на (1+X);

5. Выполнить логическое умножение и упростить формулу в соответствии со свойствами операций + и .

Пример 1.

Построим многочлен Жегалкина для булевой функции X₁X₂.

X₁ X₂ = X₁ X₂ = 1+(1+ X₁ )(1+X₂ )=1+1+ X₁ +X₂ + X₁ X₂ = X₁ +X₂ + X₁ X₂ .

Примеры:

X₁ X₂ , X₁ X₂ – функции, сохраняющие константу 0;

X₁ X₂ – функция, не сохраняющая константу 0;

X₁ X₂ , X₁ X₂ – функции, сохраняющие константу 1;

X₁ +X₂ – функция, не сохраняющая константу 1;

X₁+X₂+X₃ – самодвойственная функция, т.к.

f*( X₁ ,X₂ ,X₃ )=1+(1+ X₁)+(1+X₂)+(1+X₃ )= X₁+X₂ +X₃ = f( X₁ ,X₂ ,X₃ );

X₁+X₂ – несамодвойственная функция, т.к.

f*( X₁ ,X₂)=1+(1+ X₁)+(1+X₂)=1+X₁+X₂ f( X₁ ,X₂ );

X₁ X₂, X₁ X₂ – монотонные функции;

X₁ X₂ – немонотонная функция (определении монотонности нарушается на наборах (0, 0) и (1, 0)).

X₁ +X₂ – линейная функция;

X₁ X₂ = X₁ +X₂+X₁X₂ – нелинейная функция.

Пример 2.

Пусть К₀ – класс функций, сохраняющих константу 0; К₁ – класс функций, сохраняющих константу 1; К_м – класс монотонных функций; К_л – класс линейных функций; К_с – класс самодвойственных функций.

Докажем полноту системы {+,,1}.

Составим таблицу Поста следующего вида:

F	К0	К1	Км	Кл	Кс
X+Y	+	-	-	+	-
XY	+	+	+	-	-
1	-	+	+	+	-

В силу теоремы Поста для полноты системы необходимо и достаточно, чтобы в каждом столбце таблицы был хотя бы один “-”. Построенная таблица доказывает полноту системы {+,,1}.

Пример 3.

Является ли полной следующая система функций .

Для проверки полноты системы переключательных функций будем использовать критерий полноты – теорему Поста. Составим таблицу Поста.

f
	-	+	-	-	-
	-	-	-	+	+

.

в то время как так как

Для проверки монотонности воспользуемся таблицей истинности.

X	Y
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	0

Анализ показывает, что не являются монотонными функциями, так как

Для определения линейности функции построим многочлен Жегалкина.

Таким образом, - линейная функция, а - нет.

Определим являются ли исследуемые функции самодвойственными. Так как то - самодвойственная функция. В то время, как , и поэтому .

Для полноты системы необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один “-“. Построенная таблица доказывает, что система является полной.

С понятием полноты тесно связано понятие замыкания и замкнутого класса.

Пусть  - некоторое подмножество функций из Р₂. Замыканием  называется множество всех булевых функций, представимых в виде формул через функции множества . Замыкание множества  обозначается через [].

Класс (множество)  называется (функционально) замкнутым, если =[].

Можно показать, что функционально замкнутыми в Р₂ являются К₀, К₁, К_м, К_л, К_с .

В терминах замыкания и замкнутого класса можно дать другое определение полноты (эквивалентное исходному):  - полная система, если []=Р₂ .

Пусть {f₁ (X1,…,Хn),..., f_m (X1,…,Хn)} – конечная система булевых функций. Функция f(X1,…,Хn) называется элементарной суперпозицией функций f₁, f₂,.., f_m, если она может быть получена одним из следующих способов:

переименованием некоторой переменной X_i какой-нибудь функции f_i , то есть

f(X₁,..., X_n)= f_k(X₁,..., X_k-1, Y, X_k+1,..., X_n),

где Y может совпасть с любой из переменных X₁,..., X_n;

подстановкой некоторой функции f_r вместо какой-нибудь переменной X_k , то есть

f(X₁,..., X_n)= f_k(X₁,..., X_k-1, f_r(X₁,..., X_n), X_k+1,..., X_n),

где f_r  {f₁, f₂,...,f_m }.

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

Пример 4.

{, , } – не является независимой.

Независимая полная система функций называется базисом.

Другое определение базиса: система функций {f₁ (X1,…,Хn),..., f_m (X1,…,Хn)} из замкнутого класса  называется базисом, если она полна в , но всякая ее подсистема не является полной в .

Для Р2 существует 17 базисов, в каждом из которых нельзя вычеркнуть ни одну функцию без потери полноты. Среди них:

{} – базис Вебба;

{} – базис Шеффера;

{, 0} – импликативный базис;

{, } – конъюнктивный базис Буля;

{, } – дизъюнктивный базис Буля;

{+, , } – базис Жегалкина.

Для алгебры высказываний данный результат имеет следующее значение: каждому сложному высказыванию в базисе {, , } соответствует равносильное высказывание в любом из этих базисов.

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