Mat_Logika_Algebra_i_ischislenie_vyskazyvany

21

ция над списком переменных этой формулы.

Аналогично логическим формулам некоторые системы булевых функ-

ций образуют полные системы. Это следующие множества:
1.	M0 = {¬; ; }. 2. M1 = {¬; }. 3. M2 = {¬; }. 4. M3 ={¬; } .
5.	M4 = { | }. 6. M5 = {↓ }. 7. M6 = { 1, , }.

Для 5–ой системы – M4 полноту можно доказать, если с помощью штриха Шеффера представить отрицание и, например, конъюнкцию:

¬x = x | x;	x1 x2 = ¬( x1 | x2 ) = ( x1 | x2 ) | ( x1 | x2 ).
Для 6–ой системы – M5:
¬x = x ↓ x;	x1 x2 = ¬( x1 ↓ x2 ) = ( x1 ↓ x2 ) ↓ ( x1 ↓ x2 ).

	Свойства операций системы M6
Если ввести временные обозначения: на + и на • (обычное умноже-
ние), то
1) X+Y= Y+X;	X•Y= Y•X;

2)(X+Y)+Z= X+(Y+Z); (X•Y) •Z= X• (Y•Z);

3)X• (Y+Z)= X•Y+X•Z;

4)	X+X= 0;	X•X= 1;
5)	0+X=X;	0•X= 0;

6)1•X= X.

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

Многочлены Жегалкина

Представление булевой функции с помощью функций последней систе-

мы называют полиномом или многочленом Жегалкина.

22

Полнота системы M6 вытекает из представления ¬x = x 1. Отсюда следует, что любая булева функция представима в виде

(i1,...,in )ai1,...,in xi1 ... xin

где коэффициенты равны 0 или 1.

С введенными выше временными обозначениями: на + и на •, многочлен Жегалкина – это сумма константы: 0 или 1, и различных одночленов, в которые все переменные входят в степени не выше первой:

∑	xi1 xi2 •... • xik + a ,
1≤i1 <i2 <...<ik ≤n

где a {0;1} и каждый набор индексов у переменных отличен от других на-

боров.

Теорема. (об единственности представления булевой функции полиномами Жегалкина).

Каждой булевой функции соответствует единственный полином Жегалкина над списком переменных функции.

Доказательство То, что можно представить любую булеву функцию многочленом Же-

галкина вытекает из полноты системы { 1, , }.

Мощность множества всех n–местных булевых функций равна 2(2n ). Если количество различных многочленов Жегалкина равно этой же величине, то имеет место и единственность.

Любой одночлен можно представить в виде x1α1 ... xnαn , где показатель степени равен 0 или 1. Число различных одночленов из n переменных равно

2n (на каждом месте переменная либо есть – показатель степени равен 1, либо нет – показатель степени равен 0). Одночлен с нулевыми показателями степе-

23

ни – 1.

Каждый многочлен можно рассматривать как сумму всех одночленов, умножаемых на коэффициент, равный 0 или 1. Число различных многочленов

равно 22n (на каждом из 2n мест одночлен либо есть – коэффициент равен 1, либо нет – коэффициент равен 0). ■

Упражнение.

Представить многочленами Жегалкина булевы функции, порождаемые формулами:

(А&В) ; (А В) ; (А В) ; (А В).

Примеры.

Для одной переменной: X+1; X; 1; 0. Сначала присутствуют оба одночлена, затем – по одному, в конце оба отсутствуют.

Для двух переменных:

f9

(4)

f12

(3)

f11

(3)

f14

(3)

f13

(2)

f4

(2)

f5

(2)

f1

(1)

XY+X+Y+1

XY+X+1

XY+Y+1

X+Y+1

XY+1

X+1

Y+1

1

f10

(3)

f7

(2)

f8

(2)

f15

(2)

f6

(1)

f2

(1)

f3

(1)

f0

(0)

XY+X+Y

XY+X

XY+Y

X+Y

XY

X

Y

0

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

24

2.ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

2.1.Аксиоматические теории Аксиоматическая теория (АТ) считается определенной, если:

1)Задано непустое счетное множество символов этой теории – алфавит σ . При этом конечные последовательности символов алфавита называют словами или выражениями в АТ.

2)Выделено некоторое множество слов, называемых формулами АТ.

3)Определено некоторое подмножество формул, которые называются аксио-

мами АТ.

4)Задано конечное множество {R1,..., Rm }– отношений между формулами,

называемых правилами вывода.

Формула A называется непосредственным следствием формул

A1,...,Ak по правилу Rj, если формулы A1,...,Ak и A находятся в отноше-

нии Rj.

Последовательность формул A1,...,An , называется выводом в АТ, если каждая формула последовательности Ai является:

•либо аксиомой АТ,

•либо непосредственным следствием предыдущих формул A1,...,Ai−1

по одному из правил вывода Rj.

Формула A называется теоремой в АТ, если существует ее вывод в АТ, заканчивающийся этой формулой, т.е. найдется последовательность формул A1,..., An , являющаяся выводом, и An = A .

Пусть Γ – некоторое множество формул теории АТ.

Формула A называется следствием Γ или выводимой из Γ, если су-

ществует ее вывод в АТ – A1,...,An , удовлетворяющий условиям:

25

1)каждая формула последовательности Ai является:

•либо аксиомой АТ,

•либо формулой из Γ,

•либо непосредственным следствием предыдущих формул A1,...,Ai−1

по одному из правил вывода Rj.

2)вывод заканчивается этой формулой, т.е. An = A .

Обозначается – Γ├─A.

Если Γ ={B1,...,Bk }, то будем обозначать – B1,...,Bk ├─A. Форму-

лы B1,...,Bk , являющиеся элементами Γ, называют гипотезами или посыл-

ками вывода.

Замечание. Т.к. из определений вытекает, что теорема A – это формула, вы-

водимая из аксиом без применения гипотез, то ее обозначение – ├─A.

Простейшие свойства выводимых формул

Теорема.

Пусть Γ ={D1,...,Dk } – некоторое множество формул теории АТ, а

A,B,C произвольные формулы теории АТ. Тогда верны следующие свойст-

ва выводимых формул теории АТ:

Св.1. Если Γ├─A и Γ Γ1, то Γ1 ├─A.

Св.2. Если Γ├─A, то Γ,B├─A.

Св.3. Γ,A├─A.

Св.4. Если Γ,B,C├─A, то Γ,C,B├─A.

Св.5. Если Γ├─A и для любой Di Γимеет место Γ1 ├─Di , то Γ1 ├─A.

Св.6. (удаление выводимой гипотезы). Если Γ,B├─A и Γ├─B,

то Γ├─A.

26

Св.7. Если Γ├─A, Γ├─B и A,B├─C, то Γ├─C.

Доказательство этих свойств вытекает из определений выводимых фор-

мул. Для Св.1. в качестве вывода из Γ1 можно взять вывод из Γ, а Св.2. –

частный случай Св.1. Для Св.3 вывод, очевидно, состоит из одной формулы

A. Св.4. очевидно, т.к. множество гипотез не зависит от порядка своих эле-

ментов. Для Св.5. в выводе A из Γ, любое вхождение гипотезы Di Γ заме-

няется на ее вывод из Γ1 . В результате получим последовательность формул,

являющуюся выводом A из Γ1 . Аналогично доказательство для Св.6 и 7. ■

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

Аксиоматическая теория Чёрча

Построим простейшую аксиоматическую теорию, которую будем называть аксиоматической теорией Чёрча (АТЧ), в соответствии с требованиями из параграфа 2.1.

Замечание. Алонзо Чёрч (Church Alonzo, 1903 г.р.) американский логик и математик, внесший большой вклад в развитие математической логики и теории автоматов.

1) Алфавит АТЧ – σ =σ1 σ2 σ3, где

σ1 ={A, B,..., A1, A2 ,...} – множество пропозициональных переменных

(ПП);

σ2 ={¬, } – пропозициональные связки (ПС);

σ3 ={"(", ")" } - вспомогательные символы (открывающая и закрываю-

щая круглые скобки) для указания области действия связок. 2) Множество формул АТЧ задается индуктивным способом:

27

а) любая пропозициональная переменная из σ1 суть формула;

б) Если A – формула, то (¬A) – формула;

в) Если A и B – формула, то (A B) – формула г) других формул в АТЧ нет.

3)Для любых формул A,B,C следующие формулы являются аксиомами:

А1. (A (B A)).

А2. ((A (B C)) ((A B) (A C))).

А3. (((¬A) (¬B)) (B A)).

4)В АТЧ единственное правило вывода – «modus ponens» (в переводе с латинского – «правило отделения»; читается – модус поненс):

формула B есть непосредственное следствие формул A и (A B) .

Будем записывать это правило в виде:

MP : A, (A B).

B

Замечание 1. МР имеет своим источником тавтологию (см. стр. 9)

( A & ( A B)) B .

Замечание 2. Можно говорить о наличии еще одного правила: правила под-

становки, т.е. если F (A) – выводимая формула, заменив все вхождения формулы A на произвольную формулу B, получим также выводимую фор-

мулу F (B). Это вытекает из условия: «для любых формул A,B,C …».

Замечание 3. Все аксиомы являются тавтологиями (см. основные тавтологии на стр. 8).

Замечание 4. В дальнейшем в целях сокращения записей будем опускать внешние скобки формул; будем считать, что связка действует раньше связ-

28

ки , т.е. формула ¬A B , означает то же, что и (¬A) B , а формула

A ¬B – то же, что A (¬B).

Для всех аксиоматических теорий, имеющих правило вывода «modus ponens» верно следующее простейшее свойство:

Св.8. Если Γ├─A и Γ├─A B, то Γ├─B.

Пусть A1, A2 , ..., An = A – вывод формулы A из Γ; а вывод A B

из Γ – B1, B2 , ..., Bm = A B. Тогда A1, A2 , ..., An , B1, B2 , ..., Bm ,B –

вывод B из Γ. Последняя (m+n) – я формула получена применением МР к

An и Bm . ■

2.2.Теоремы аксиоматической теории Чёрча

Вэтом и следующем параграфе под символами A, B, C будем понимать формулы A, B,C, соответственно, а не только пропозициональные пере-

меннные. В скобках после каждой формулы записывается правило, на основании которого она помещена в последовательность вывода. Сейчас это могут быть аксиомы – А1, А2, А3 и правило вывода «modus ponens» – МР. После построения вывода очередной теоремы возможна ссылка на нее в виде Тn, где n – номер теоремы.

Т1. ├─ A A.

1. ( A (( A A) A)) (( A ( A A)) ( A A)) (А2).

Применили схему аксиомы А2, взяв в качестве B формулу (A A), а

вместо C формулу A.

2. A (( A A) A) (А1).

Применили схему аксиомы А1, взяв в качестве B формулу (A A). 3. ( A ( A A)) ( A A) (МР к 2, 1).

29

Применили «modus ponens» к предыдущим формулам 2 и 1 (последовательность номеров формул именно такая: формула 2 является посылкой в формуле 1).

4. A ( A A) (А1).

Применили схему аксиомы А1, взяв вкачестве B формулу A.

5.A A (МР к 4, 3).

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

Т2. Если ├─ A, то для любой формулы B имеет место: ├─ B A.

Пусть A1, A2 , ..., An = A – вывод формулы A. Чтобы получить вывод формулы B A дополним вывод формулы A еще двумя формулами:

n+1) A (B A) (А1). n+2) B A (МР к n, n+1). ■

Т3. ├─ ¬A ( A B).

1. (¬B ¬A) ( A B) (А3).

Применили схему аксиомы А3, взяв вкачестве B формулу A и наоборот.

2.¬A ((¬B ¬A) ( A B)) (Т2 к 1).

3.(¬A ((¬B ¬A) ( A B)))

((¬A (¬B ¬A)) (¬A ( A B))) (А2).

Применили схему аксиомы А2, взяв в качестве A формулу ¬A, в качестве

B– формулу ¬B ¬A, а в качестве C – формулу A B .

4.(¬A (¬B ¬A)) (¬A ( A B)) (МР к 2, 3).

5.¬A (¬B ¬A) (А1).

6.¬A ( A B) (МР к 5, 4). ■

30

Т4. ├─ ¬¬A (¬¬A A) .

1. (¬A ¬¬¬A) (¬¬A A) (А3).

Применили схему аксиомы А3, взяв в качестве B формулу ¬¬A.

2.¬¬A ((¬A ¬¬¬A) (¬¬A A)) (Т2 к 1).

3.(¬¬A ((¬A ¬¬¬A) (¬¬A A)))

((¬¬A (¬A ¬¬¬A)) (¬¬A (¬¬A A))) (А2).

Применили схему аксиомы А2, взяв в качестве A формулу ¬¬A, в качестве B – формулу ¬A ¬¬¬A, а в качестве C – формулу ¬¬A A.

4.(¬¬A (¬A ¬¬¬A)) (¬¬A (¬¬A A)) (МР к 2, 3).

5.¬¬A (¬A ¬¬¬A) (Т3, в качестве B формула ¬¬¬A).

6.¬¬A (¬¬A A) (МР к 5, 4). ■

Т5. ├─ ¬¬A A.

1.¬¬A (¬¬A A) (Т4).

2.(¬¬A (¬¬A A)) ((¬¬A ¬¬A) (¬¬A A)) (А2).

3.(¬¬A ¬¬A) (¬¬A A) (МР к 1, 2).

4.¬¬A ¬¬A (Т1).

5.¬¬A A (МР к 4, 3). ■

Т6. ├─ A ¬¬A.

1.(¬¬¬A ¬A) ( A ¬¬A) (А3).

2.¬¬¬A ¬A (Т5).

3.A ¬¬A (МР к 2, 1). ■

Теорема о дедукции

Теорема.

Если из множества гипотез Γ и формулы A выводима формула B , то из