Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Московский государственный университет приборостроения и информатики

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

lekcii_dm

.pdf

Скачиваний:

Добавлен:

09.04.2015

Размер:

2.19 Mб

Скачать

☆

<<< < Предыдущая 6 7 8 9 10 11 12 13 14 15 16 17 1819 / 3019 20 21 22 23 24 25 26 27 28 29 30 > Следующая >>>

1.(X Y )&Z двойственна X &Y Z .

2.X Y &(X Y &Z) двойственна X &Y X &Y Z .

3.X &Y Y &Z U &V двойственна (X Y )&(Y Z )&(U V ).

Замечание.

Как для операций, так и для формул отношение двойственности взаимно, то есть если * двойственна , то и, наоборот, двойственна

Лемма.
Если формулы	(X1, X2,…, Xn) и							*(X1, X2,…, Xn)		двойственны,	а
X1, X2,…, Xn – все	входящие	в них					элементарные			высказывания,	то
		*(		,		,...,			).
(X1, X2,…, Xn) равносильна		*(	X1	,	X2	,...,		Xn	).

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

Доказательство непосредственно следует из законов де Моргана.

Следствие из леммы.

Частным случаем леммы являются следующие соотношения:

X1 X2	... Xn	X1	X2	...	Xn	;	(5)
				...		.
X1 X2	... Xn	X1	X2	...	Xn	.	(6)

Они являются обобщением законов де Моргана и называются законами Клода Шеннона.

Задание.

Доказать законы Клода Шеннона и лемму.

181

Теорема (закон двойственности).

Если и равносильны, то и двойственные им формулы *и * также равносильны.

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

Пусть (X1, X2,…, Xn) и (X1, X2,…, Xn) – равносильные формулы, а X1, X2,…, Xn – входящие в них элементарные высказывания. Тогда, в силу леммы, *(X1, X2,…, Xn) равносильна (X1,X2,...,Xn ), а*(X1, X2,…, Xn)

равносильна (X1,X2,...,Xn ).

Из равносильности формул (X1, X2,…, Xn) и (X1, X2,…, Xn)

следует равносильность формул (X1,X2,...,Xn )и (X1,X2,...,Xn ), так

как в силу определения равносильности

(X1, X2,…, Xn) и

(X1, X2,…, Xn)

принимают

одинаковые

значения при

любых значениях

переменных

при значениях

,...,

X1, X2,…,

Xn,

а,

следовательно, и

(

,...,

)

(

,...,

) также

Следовательно,

формулы

равносильны, далее, в силу леммы формула

*(X1, X2,…, Xn) равносильна

(

,...,

формуле

а формула

*(X1, X2,…, Xn) равносильна

формуле (

,...,

). Следовательно,

формулы

*(X1, X2,…, Xn) и

*(X1, X2,…, Xn)

равносильны между собой, что и требовалось доказать.

Замечание.

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

182

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

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

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

Для любой булевой функции f(x1, x2,…, xn) имеют место следующие

разложения по переменным x1, x2,…, xk {1 k n}:
1.
	xa1xa2	...axk f (a ,...,a ,x			,...,x )
f(x1, x2,…, xn) = (a1,a2,...,an )	1 2	k	1	k k 1	n , (7)

где 1) 1 k n;

2) дизъюнкция берётся по всем наборам (a1, a2,…, ak), {ai {0,1}},

i 1,k .

Это разложение функции f(x1, x2,…, xn)

f (x1,x2,...,xn ) (a1

называется дизъюнктивным разложением булевой по переменным x1, x2,…, xk {1 k n}.

	(x	a1	x	a2	... x	ak	f (a ,a		,...,a ,x	,...,x ))
,a2,...,an )	1		2		k		1	2	k k 1	n	,(8)

где 1) 1 k n;

2) конъюнкция берётся по всем наборам (a1, a2,…, ak), {ai {0,1}},

i 1,k

Это разложение называется конъюнктивным разложением булевой функции f(x1, x2,…, xn) по переменным x1, x2,…, xk , {1 k n}.

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

183

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

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

f (x1,x2,...,xn ) x1 f (1,x2,...,xn )

f (0,x2,...,xn );

(9)

f (x1,x2,...,xn ) (

f (1,x2,...,xn ))(x1

f (0,x2,...,xn )).

(10)

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

При x1 = 1 имеем:

f (1,x2,...,xn ) 1 f (1,x2,...,xn ) 0 f (0,x2,...,xn )

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

При x1 = 0 имеем:

f (0,x2,...,xn ) 0 f (1,x2,...,xn ) 1 f (0,x2,...,xn )

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

Таким, образом доказана справедливость соотношения (9). Подобным

образом можно разложить функцию по

другой

переменной, например

по x2. Тогда для формулы (9) это разложение имеет вид:

f (x1,x2,...,xn ) x1x2 f (1,1,...,xn ) x1

f (1,0,...,xn )

x2 f (0,1,...,xn )

f (0,0,...,xn ).

(11)

Подставляя, где записано разложение по x1, значение x2=1 и затем x2=0,

легко убедится в справедливости

соотношения

(11).

Если продолжить

процесс разложения по

остальным

переменным

(до

k включительно

(1 k n)), то получим соотношение (7). Аналогично доказывается формула

(8). Теорема доказана.

Замечания.

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

f (x1,x2,...,xn ) x1x2 ... xn 1xn f (1,1,...,1,1)x1x2 ... xn 1xn f (1,1,...,1,0)

184

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

x1x2 ... xn 1 xn f (1,0,...,0,0)

x1 x2 ... xn 1 xn f (0,0,...,0,0) ,

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

f (x1,x2,...,xn ) (x1 x2 ... xn 1 xn f (1,1,...,1,1))


(	x1		x2	...	xn 1	xn f (1,1,...,1,0))
……………………………………….							(13)
(		x2		... xn 1		xn f (1,0,...,0,0))
	x1
(x1 x2				... xn 1		xn f (0,0,...,0,0)) .

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

5.04. Основные свойства булевых функций.

Замечание.

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

185

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

Таблица 5.04

Назва-

Аналитическое

Определение

Примечание

ние

выражение

Функция при

y (x1 x2)(x1

)

всех

Нико-

комбинациях

гда

аргумента

(x1 x2)(x1 x2)

имеет нулевое

значение.

Эта функция

принимает

Конъ-

значение 1

только при

юнк-

y = x1x2

истинности

ция

обоих

высказыва-

ний.

Функция

y x1x2

Запрет

повторяет

y x1 x2

по x2

значение x1,

= x1 x2

если x2 = 0.

По-

Функция

вторе-

y x1

x1x2 x1

повторяет

ние x1

значение x1

Функция

Запрет

повторяет

y x2 x1

по x1

значение x2,

=x2 x1

если x1 = 0.

186

По-

Функция

вторе-

x2 x1x2

повторяет

ние x2

значение x2

Функция

равна 1 только

в случае

Сло-

y x1x2 x1x2

различного

жение

x1 x2

значения

аргументов

(искл. “или”)

Функция

Дизъ-

равна 1 в

x x

случае

юнк-

истинности

x1 x2

ция

хотя бы

одного

высказывания

Отри-

Функция

цание

дизъ-

равна 1 только

юнк-

в случае

ции

x1 x2

ложности всех

(стрел

высказыва-

ка

ний.

Пирса)

Экви-

Функция

y x1x2

равна 1 только

ва-

при

лент-

одинаковых

x x

ность

значениях

аргументов.

Отри-

Функция

цание

принимает

f10

x2 или

значение

инвер-

противопо-

сия x2

ложное x2

187

Им-

Функция

f11

плика-

y x

равна 0 x2 =

ция от

1 и x1 = 0

x2 к x1

Ин-

Функция

принимает

f12

версия

значение

противопо-

ложное x1

Им-

Функция

f13

плика-

x x

равна 0 x1 =

ция от

1 и x2 = 0

x1 к x2

Отри-

цание

Функция

конъ-

юнк-

x1x2

равна 0

ции

x1 x2

истинны оба

(штрих

аргумента

Шеф-

фера)

Функция

Всегда

всегда

принимает

x1x2

значение 1

188

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

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

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

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

Формальная система для языка логики предикатов первого порядка,

называется естественной дедукцией (natural deduction).

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

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

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

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

189

«eliminate», справа соответствующий значок отсутствует, слева присутствует) для каждого логического значка и квантора , , , , , .

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

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

A B ├A

A B

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

A B ├B

A B

введение «и» A,B ├A B

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

A B

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

B A

A 1

B 1

B A

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

Если A ├C и B ├C ,

то A B ├C

Последнее правило

можно прочесть так: если

доказано с

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

Впоследнем правиле использовалось следующее обозначение: посылка

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

190

<<< < Предыдущая 6 7 8 9 10 11 12 13 14 15 16 17 1819 / 3019 20 21 22 23 24 25 26 27 28 29 30 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
02.05.2019181.25 Кб3Lector5(Stud).doc
#
09.08.2019179.71 Кб5Lector6(Stud).doc
#
02.12.20189.5 Mб78lectures.doc
#
14.04.2019378.37 Кб3LECTURS.doc
#
08.11.201811.89 Mб31lekcii_dm.doc
#
09.04.20152.19 Mб44lekcii_dm.pdf
#
22.09.20192.46 Mб24lekcii_termodinamika.doc
#
22.12.201871.61 Кб31Lektsia_11.docx
#
24.11.2019398.34 Кб6Lektsia_13.doc
#
09.04.201516.75 Mб46Lektsii.doc
#
09.04.2015781.82 Кб43Lektsii_po_ekonomike_organizatsy (1).doc