Лекции по математической логике и теории алгоритмов (стр. 3 из 10)

(a₁,,a₂,...,a_n)§(b₁,b₂,...,b_n) следует, что f(a₁,,a₂,...,a_n)§f(b₁,b₂,...,b_n).

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

Критерий полноты(Теорема Поста). Система S булевых функций является полной тогда и только тогда, когда она включает хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную, нелинейную и немонотонную.

В таблице 1.7 приведены свойства, которыми обладают элементарные булевы функции (символ * - отмечает свойство, которым обладает данная функция).

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

Построим некоторые часто используемые в приложениях базисы.

Таблица 1.7

Назва- ние	Обозн .	Не сохранимость константы 0	Не сохранимость константы 1	Не Самодвойс т венность	Не Линей - ность	Не Моното н-ность
Конст.0	0	*	*
Конст.1	1	*	*
Отриц.	Ÿ	*	*	*
Конъюн .	&	*	*
Дизъюн .	¤	*	*
Имплик .	Ø	*	*	*	*
Эквивал .	~	*	*	*
Сумма по мод_2	∆	*	*	*
Штрих Шеффе ра	|	*	*	*	*	*
Стрелка Пирса	∞	*	*	*	*	*

1. Система функций S1={Ÿ,⁄,¤} образует базис. Для приведения булевой функции к виду содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности: x → у = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , x

y = x ∨ y , x ↓ y = x & y .

2. Система S2={Ÿ,&} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем

использовать соотношение x ∨ y = x ⋅ y .

3. Система S3={Ÿ,¤} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем

использовать соотношение x ⋅ y = x ∨ y .

4. Система S4={1,&,∆} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношения x = 1⊕ x , x ∨ y = x ⊕ y ⊕ x ⋅ y .

5.

Система S5={|} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S2 а затем использовать соотношения x ⋅ y = x y , x = x x .

6. Система S6={∞} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S3 а затем

использовать соотношения x ∨ y = x ↓ y , x = x ↓ x .

7. Система S7={Ø,0} образует базис.

Пример 1.7.1. Записать функцию x¨(y∆z) в базисе S1={Ÿ,⁄,¤}. x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⋅ z ∨ y ⋅ z)

Глава II. Булева алгебра.

Множество всех булевых в базисе S1={ÿ, &, ⁄} образуют булеву алгебру. Таким образом в булевой алгебре все формулы записываются при помощи трех связок: Ÿ, &, ¤. Частично свойства этой алгебры мы рассмотрели в главе I (см., например, основные эквивалентности). В этой главе рассматриваются свойства, специфичные для булевой алгебры и поэтому везде в этой главе мы будем иметь дело только с тремя функциями:ÿ, &, ⁄.

§2.1. Нормальные формы.

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

Если х - логическая переменная, а σœ{0,1} то выражение x _σ = x если_еслиσσ == 10 или x _σ = 10 если_если x x =≠σσ , x называется литерой. Литеры x и Ÿx называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Например, формулы x ⋅ y ⋅ z и x ⋅ y ⋅ x ⋅ x являются конъюнктами, формулы x ∨ y ∨ z и x ∨ y ∨ x - дизъюнктами, а формула z является одновременно и конъюнктом и дизъюнктом.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов.

Более просто: ДНФ - это сумма произведений, а КНФ - это произведение логических сумм Примеры.

1. xÿy¤yÿz¤x ― это ДНФ (сумма произведений).

2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z ―это КНФ (произведение сумм).

3. x ∨ y ∨ z ∨ w ― это ДНФ и КНФ (одновременно).

4. x ⋅ y ⋅ z ⋅ w ― это ДНФ и КНФ (одновременно).

5. (x¤x¤y)·(y¤z¤x)·z ― это КНФ.

6. x⋅y⋅z и x⋅y⋅x⋅x ― это ДНФ.

7.

x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z ― это не нормальная форма (не ДНФ и не КНФ).

Пусть функция f записана в базисе S1. Данная функция приводится к нормальной форме следующим путем:

1) используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным;

2) применяем правило снятия двойного отрицания: ŸŸx=x;

3) далее использовать законы дистрибутивности, причем необходимо использовать первый закон дистрибутивности для приведения к ДНФ

H1&(H2¤H3)=(H1&H2)¤(H1&H3) , и второй закон дистрибутивности для приведения к КНФ. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).

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

Пример 2.1.1. Для приведения к ДНФ используем 1-ый закон дистрибутивности.

x⋅y⋅x⋅y⋅z⋅(y∨z)=x⋅y⋅(x∨y∨z)⋅(y∨z)=(x⋅y⋅x∨x⋅y⋅y∨x⋅y⋅z)⋅(y∨z)= -это КНФ

= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = -это другая КНФ

= x ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⋅ y⋅z =

= x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z -это ДНФ

Пример 2.1.2. Для приведения к КНФ необходимо использовать второй закон дистрибутивности.

x ∨ y ⋅ x ⋅ y ∨ z = x ∨ y ⋅ (x ⋅ y ⋅ z) = x ∨ y ⋅ (x ∨ y) ⋅ z =

=x∨y⋅z⋅(x∨y)=(x∨y⋅z)⋅(x∨x∨y)=(x∨y)⋅(x∨z)⋅(1∨y)=

= ( x ∨ y ) ⋅ ( x ∨ z ) это КНФ

§2.2. Совершенные нормальные формы.

Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ). Примеры: Пусть задана функция трех переменных f(x,y,z).

1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z- это совершенная ДНФ.

2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z)- это совершенная КНФ.

3. ( x ∨ y ) ⋅ ( x ∨ z )- это не совершенная КНФ, т.к. например, в первую сумму не входит переменная z.

4. xÿyÿz - это совершенная ДНФ. Теорема 2.2.1.

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

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

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

Решение рассмотрим на примере функции f(x,y,z) заданной таблично (таб.2.2) при n=3.

Пример 2.2.1. По данной таблице истинности (таб.2.2) построить СДНФ.