Замечание.

1. Если, применяя к формуле дистрибутивные преобразования на основании первого дистрибутивного закона мы получим формулу , то переход от двойственной формулы ^* к двойственной формуле ^* осуществляется дистрибутивными преобразованиями на основании второго дистрибутивного закона.

2. Переход от ^*к ^*называется преобразованием, двойственным преобразованию, переводящему в .

Теорема. (Формулы разложения Клода Шеннона.)

Для любой булевой функции f(x_1, x₂,…, x_n) имеют место следующие разложения по переменным x_1, x₂,…, x_k {1 k  n}:

f(x_1, x₂,…, x_n) = , (7)

где 1) 1 k  n;

2) дизъюнкция берётся по всем наборам (a₁, a₂,…, a_k), {a_i{0,1}}, .

Это разложение называется дизъюнктивным разложением булевой функции f(x_1, x₂,…, x_n) по переменным x_1, x₂,…, x_k {1 k  n}.

,(8)

где 1)  1 k  n;

2) конъюнкция берётся по всем наборам (a₁, a₂,…, a_k), {a_i{0,1}},

Это разложение называется конъюнктивным разложением булевой функции f(x_1, x₂,…, x_n) по переменным x_1, x₂,…, x_k , {1 k  n}.

Оба соотношения (7) и (8) также называются формулами разложения Клода Шеннона.

Доказательство:

При k = 1 формулы (7) и (8) имеют следующий вид:

; (9) . (10)

Докажем формулу (9).

При x₁ = 1 имеем:

 – равенство очевидно.

При x₁ = 0 имеем:

 – равенство очевидно.

Таким, образом доказана справедливость соотношения (9). Подобным образом можно разложить функцию по другой переменной, например по x₂. Тогда для формулы (9) это разложение имеет вид:

. (11)

Подставляя, где записано разложение по x₁, значение x₂=1 и затем x₂=0, легко убедится в справедливости и соотношения (11). Если продолжить процесс разложения по остальным переменным (до k включительно (1 k  n)), то получим соотношение (7). Аналогично доказывается формула (8). Теорема доказана.

Замечания.

1. При k = n дизъюнктивное разложение булевой функции {формула (7)} имеет вид:

……………………………….. (12)

а конъюнктивное разложение {формула (8)} имеет вид:

………………………………………. (13)

2. Из полученных соотношений видно, что дизъюнктивное разложение булевой функции при k = n { см. формулу (12)} есть не что иное, как совершенная дизъюнктивная нормальная форма {см. формулу (3)}, а конъюнктивное разложение булевой функции при k = n {см. формулу (13)} есть совершенная конъюнктивная нормальная форма {см. формулу (4)}. Таким образом, СДНФ и СКНФ являются частными случаями равенств (7) и (8), являющихся соответственно дизъюнктивным и конъюнктивным разложениями булевой функции f(x_1, x₂,…, x_n) по переменным x_1, x₂,…, x_k , {1 k  n}.

4. Основные свойства булевых функций. Замечание.

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

Таблица 5.04

x1	0	0	1	1	Название	Аналитическое выражение	Определение	Примечание
x2	0	1	0	1
f0	0	0	0	0	Никогда		Функция при всех комбинациях аргумента имеет нулевое значение.
f1	0	0	0	1	Конъюнкция	y = x1x2	Эта функция принимает значение 1 только при истинности обоих высказываний.
f2	0	0	1	0	Запрет по x2	= x1  x2	Функция повторяет значение x1, если x2 = 0.
f3	0	0	1	1	Повторение x1		Функция повторяет значение x1
f4	0	1	0	0	Запрет по x1	=	Функция повторяет значение x2, если x1 = 0.
f5	0	1	0	1	Повторение x2		Функция повторяет значение x2
f6	0	1	1	0	Сложение		Функция равна 1 только в случае различного значения аргументов (искл. “или”)
f7	0	1	1	1	Дизъюнкция		Функция равна 1 в случае истинности хотя бы одного высказывания
f8	1	0	0	0	Отрицание дизъюнкции (стрелка Пирса)		Функция равна 1 только в случае ложности всех высказываний.
f9	1	0	0	1	Эквивалентность		Функция равна 1 только при одинаковых значениях аргументов.
f10	1	0	1	0	Отрицание x2 или инверсия x2		Функция принимает значение противоположное x2
f11	1	0	1	1	Импликация от x2 к x1		Функция равна 0  x2 = 1 и x1 = 0
f12	1	1	0	0	Инверсия x1		Функция принимает значение противоположное x1
f13	1	1	0	1	Импликация от x1 к x2		Функция равна 0  x1 = 1 и x2 = 0
f14	1	1	1	0	Отрицание конъюнкции (штрих Шеффера)		Функция равна 0  истинны оба аргумента
f15	1	1	1	1	Всегда		Функция всегда принимает значение 1

6. Элементы теории доказательств.

1. Естественная дедукция.

Логические заключения, которые используют люди в своих рассуждениях, определяются рядом элементарных правил, сформулированных ещё Аристоте­лем. Формализация этих правил приводит к различным формальным системам для логических языков.

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

Фор­мальная система для языка логики предикатов первого порядка, называется естественной дедукцией (natural deduction).

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

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

Работы в этом направлении начинал ученик Лукасевича Ясковский, но первую общепринятую систему естественной дедукции в 1935 году предложил в своей диссертации Генцен.

Аксиом в естественной дедукции нет, а правила вывода можно разделить на две группы: пра­вила введения (обозначаются буквой i — «introduce» — слева соответствующий значок отсутствует, справа присутствует), и правила исключения (обозначают­ся буквой е — «eliminate», справа соответствующий значок отсутствует, слева присутствует) для каждого логического значка и квантора .

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

исключение «и» ├

исключение «и» ├

введение «и» ├

введение «или» слева ├

введение «или» справа ├

исключение «или» Если ├ и ├,

то ├

Последнее правило можно прочесть так: если С доказано с использованием допущения А, и С доказано с использованием допущения В, и при этом мы знаем, что верно , то можно считать доказанным С (уже без предположений о верности A и В).

В последнем правиле использовалось следующее обозначение: посылка в квадратных скобках означает, что её можно исключить из рассмотрения. Мож­но представить себе это как «обрывание» листьев дерева вывода, соответству­ющих тем посылкам, которые можно исключить. Индексом около квадратных скобок показывается то место в дереве, где «оборванный лист» был использо­ван (то есть посылки, заключенные в квадратные скобки, стали ненужными). Дерево вывода можно читать так: необорванные листья доказывают корень.

Запись в виде дерева весьма компактна, но не всегда легко читаема. Зато запись в строчку (с подробными комментариями), как правило, легко читается, но редко получается компактной.

правило исключения импликации ├

правило введения импликации если ├,

то ├