4663

31

пропозициональные переменные А и В. Нетрудно видеть из таблицы 4, что, ко-

гда эти переменные принимают истинностное значение л, эта формула принима-

ет истинностное значение и. Но из таблиц 2 и 3 видно, что любая формула, со-

держащая лишь операции дизъюнкции и конъюнкции, при истинностных значе-

ниях л водящих в нее пропозициональных переменных, будет принимать истин-

ностное значение л.

2.1.3 Тождественно истинные и тождественно ложные формулы.

Определение. Формулу алгебры высказываний назовем тождественно ис-

тинной (тождественно ложной), если она эквивалентна формуле И(Л), то есть принимает истинностное значение и (л) при любых истинностных наборах вхо-

дящих в нее пропозициональных переменных.

Например, формула A A является тождественно истинной, а ее отрицание

A & A является тождественно ложной. И вообще, если формула U тождественно

истинная, то ее отрицание U является тождественно ложной формулой.

Тождественно истинные формулы фактически изображают правильные

схемы рассуждений. Например, рассуждать по схеме A A правильно (или дождь сегодня будет, или дождя сегодня не будет). А рассуждать по схеме

(A → B)→(B → A) («если из А следует В, то из В следует А»)

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

Проверим, является ли правильным вывод из следующих рассуждений.

Если Джон не встречал ночью Смита, то либо Смит убийца, либо Джон лжет. Если Смит не убийца, то Джон не встречал его ночью, а убийство произо-

шло после полуночи. Если убийство произошло после полуночи, то либо Смит убийца, либо Джон не лжет. Следовательно, Смитубийца.

В этом рассуждении можно выделить четыре высказывания:

А- Джон не встречал ночью Смита;

32

В- Смит убийца:

С- Джон лжет:

D- убийство произошло после полуночи.

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

U = (A → (B C)) & ( B → A & D) & (D → (B C ) → B

Если данная формула является тождественно истинной, то вывод, сделанный из рассуждений, правильный. Если же данная формула не является таковой, то истинность вывода зависит от истинности предпосылок. Но в данном рассужде-

нии ничего об этом не сказано.

Для проверки, является ли данная формула тождественно истинной, можно составить таблицу истинности формулы U (она в данном случае будет содержать

16 строчек) или воспользоваться законами, приведенными в таблице 6. Попробу-

ем пойти вторым путем. Будем иметь (в скобках указаны строчки таблицы 6,

которые использованы в соответствующих переходах):

U = (A → (B C)) & ( B → A & D) & (D → (B C ) → B ≡ (с.4)

≡( A → (B C)) & ( B → A & D) & (D → (B C ) B ≡ (с.3)

≡(A → (B C)) ( B → A & D) (D → (B C ) B ≡ (с.4)

≡ A & (B C) ) ( B & A & D ) (D & (B C ) B ≡ (с.1 и с.3)

≡A & B & C ( B & ( A D )) D & B & С B ≡ (с.7)

≡B & ( A & C A D D & С ) B ≡ (с.9 и с.10 )

≡B & ( A & C C C D & С ) B ≡ (с.2)

≡B & ( A & C И D & С ) B ≡ (с.11) ≡ B & И B ≡ (с.11) ≡ B B ≡ (с.2) ≡ И

Таким образом, приведенная схема рассуждений является тождественно истин-

ной формулой АВ и потому правомерно сделанное в ходе этих рассуждений за-

ключение.

2.1.4 ДНФ,КНФ,СДНФ,СКНФ.

Пусть А есть пропозициональная переменная. Через А1 будем обозначать са-

му эту переменную, а через А0 будем обозначать формулу A.

33

Замечание. Если обозначать истинностное значение и через 1, а истинност-

ное значение л через 0, то нетрудно видеть, что формула Аv ( в которой v может

принимать значение либо 0, либо или 1) будет принимать истинностное значение

1 только в том случае, когда истинностное значение переменной А совпадает со

значением показателя v. А формула Av будет принимать значение истина только

в том случае, когда истинностное значение переменной А противоположно зна-

чению показателя v.

Пусть далее А1,А2,А3,…, Аk есть некоторый набор пропозициональных пере-

менных. Элементарной конъюнкцией (элементарной дизъюнкцией) этих пере-

менных будем называть формулу вида

(дизъюнктивной) нормальной формой (КНФ (ДНФ)), если она имеет вид

V1 & V2 & ... & Vs (V1 V2 ... Vs ),где каждая формула Vi (i=1,2,..,s) является элементарной дизъюнкцией (конъюнкцией) каких-то пропозициональных пере-

менных, входящих в формулу U.

Например, формула (A B) &(A B C) &C является КНФ, а формула

( AB) ( ABC) C является ДНФ.

Из списка равносильных формул, приведенного в таблице 6 легко сделать вы-

вод о том, что всякую формулу алгебры высказываний можно привести к равно-

сильной ей ДНФ или КНФ. Причем при этом можно использовать следующий ал-

горитм.

Шаг 1. Все операции импликации и эквиваленции заменяем, пользуясь зако-

нами, приведенными в строчках 4 или 6 таблицы 6.

Шаг 2. Далее по необходимости, пользуясь законами, приведенными в строч-

ках 1 или 3. опускаем последовательно на одну ступень проведение операции от-

рицания.

34

Шаг 3. Для получения КНФ пользуемся законом, приведенным в строчке 8, а

для получения ДНФ пользуемся законом, приведенным в строчке 7.

Рассмотрим пример. Требуется преобразовать в КНФ формулу

U = ( A → B) & (C & (B ↔ A)

Записываем последовательность действий.

U = (A → B) & (C & (D → A))(шаг1) ≡ (A B) & (C & (D A))(шаг2) ≡

≡(A B) & (C (D A))(шаг2) ≡ (A B) & (C (D & A))(шаг2) ≡

≡(A B) & (C (D & A))(шаг3) ≡ (A B) & (C D) & (C A)

Определение. КНФ (ДНФ) называется совершенной конъюнктивной (дизъ-

юнктивной) нормальной формой (СКНФ (СДНФ)), если в каждой ее элементар-

ной дизъюнкции (элементарной конъюнкции) присутствуют все входящие в формулу пропозициональные переменные или их отрицания.

Например, формула ( A B C) & ( A B C) является СКНФ, а формула

( A & B & C) ( A & B & C) ( A & B & C) ( A & B & C) является СДНФ.

Утверждение. Для всякой формулы АВ, не являющейся тождественно лож-

ной (тождественно истинной), существует равносильная ей СДНФ (СКНФ).

Для нахождения СДНФ (СКНФ), равносильных заданной формуле АВ, можно исходить из предварительно построенных для данной формулы ДНФ или КНФ,

а можно отправляться от таблицы истинности данной формулы.

Остановимся на последнем подходе, например для нахождения СДНФ.

Пусть имеется формула U и А1,А2,…, Аk все пропозициональные переменные,

входящие в нее пропозициональные переменные. В силу сделанного выше заме-

чания элементарная конъюнкция

A1v1 & A2v2 & .. & Akvk

принимает истинностное значение 1только в том случае, когда истинностные значения переменных А1,А2,…, Аk совпадают со значениями показателей v1,v2,…,v k.

Отсюда следует, что если:

35

1) из таблицы истинности формулы U (которая не является тождественно ложной) выписать все наборы переменных А1,А2,…, Аk, при которых формула U

принимает значение 1;

2) для каждого такого набора составить элементарную конъюнкцию пере-

менных, в которых значения показателей совпадают с истинностными значе-

ниями этих переменных на этом наборе; 3) записать дизъюнкцию таких элементарных конъюнкций, то полученная

СДНФ будет эквивалентна формуле U.

Из законов де Моргана следует, что для нахождения СКНФ, эквивалентной формуле U, которая не является тождественно истинной надо:

1) из таблицы истинности формулы U выписать все наборы переменных

менных, в которых значения показателей противоположны истинностным зна-

чениями этих переменных на этом наборе;

3) записать дизъюнкцию таких элементарных дизъюнкций.

Рассмотрим пример. Составить СДНФ и СКНФ, равносильные формуле

U = A & (B → C) B & C .

Истинностные значения формулы U представлены в следующей таблице:

СДНФ для формулы U будет выглядеть следующим образом:

U≡A0&B0 &C1 A1&B0 &C0 A1&B0 &C1 A1&B1 &C1

или, если пользоваться символом операции отрицания

36

U≡ A&B&C A&B&C A&B&C A&B&C

СКНФ для формулы U будет выглядеть следующим образом:

U≡(A1 B1 C1)&(A1 B0 C1)&(A1 B0 C0)&(A0 B0 C1)

или, если пользоваться символом операции отрицания

U≡(A B C)&(A B C)&(A B C)&(A B C)

2.2Формальные системы.

2.2.1 Определение формальной системы.

Формальная система (ФС) это есть совокупность следующих четырех объ-

ектов: 1) алфавит; 2) совокупность правильно построенных формул (ППФ); 3) множество аксиом; 4) множество правил вывода.

Алфавит ФС это есть совокупность конечного или бесконечного числа символов. Символы делятся на 3 группы: буквы, символы операций,

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

ций и вспомогательных символов конечно, а количество букв может быть

(например, за счет индексов) бесконечным.

Любая конечная последовательность символов алфавита называется словом.

С помощью специальных синтаксических правил среди слов выделяются так называемые правильно построенные формулы (ППФ), причем существует эф-

фективная процедура, которая по произвольному слову определяет, является ли оно ППФ.

Множество аксиом есть выделенное подмножество ППФ. Это множество мо-

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

торая по произвольной ППФ определяет, является ли она аксиомой.

Правила вывода позволяют из имеющегося множества ППФ (утверждений)

получать новые ППФ, которые будут непосредственными следствиями этих утверждений.

Правильно построенная формула В называется выводимой в данной фор-

мальной системе (ФС) из совокупности ППФ {А1, А2,,…, Аn}, если существует последовательность ППФ В1, В2,,…, Вk, такая, что Вk совпадает с В и для любого

37

i=1,2 … k формула Вi либо является аксиомой ФС, либо совпадает с одной из

формул совокупности {А1, А2,,…, Аn}, либо является непосредственным след-

ствием некоторых ППФ множества {В1, В2,,…, Вi-1}, полученным применением к этим ППФ одного из правил вывода. При этом формулы А1, А2,,…, Аn называются

гипотезами или посылками.

Тот факт, что формула В выводима из совокупности ППФ {А1, А2,,…, Аn}

обозначается так:

А1, А2,,…, Аn A В.

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

ляются аксиомами или получаются из аксиом путем последовательного примене-

ния некоторых правил вывода, называются теоремами ФС. Тот факт, что форму-

ла В является теоремой ФС записывается так: A В.

Приведем простейший пример формальной системы. Пусть алфавит состоит всего из 3 символов: { ,+,=}, Правила построения ППФ следующие:

1)отдельно записанный символ является ППФ;

2)если слово u является ППФ, то слово u является также ППФ;

3)если слова u и v являются ППФ, то слова u+v и u=v являются также ППФ;

4)слово является ППФ, если его можно получить из слова применением ко-

нечного числа правил 2) и 3).

Пусть единственной аксиомой является слово = , а единственным правилом вывода является следующее правило:

из ППФ вида u=v выводится u+ =v .

Нетрудно видеть, что теоремой в данной ФС является любая ППФ вида

+ + +….+ = … ,

в которой слева и справа от знака «=» стоит одинаковое число знаков .

2.2.2 Исчисление высказываний.

В данном пункте развитую в п. 1 алгебру высказываний (АВ) постараемся представить в виде формальной системы, которую будем называть исчислением высказываний (ИВ) и в которой выводимыми окажутся только те правильно по-

38

строенные формулы, которые в алгебре высказываний являются тождественно истинными.

Алфавит ИВ состоит из: 1) букв латинского алфавита, возможно с числовыми индексами (эти буквы будут называться, как и в АВ, пропозициональными пере-

менными или атомами); 2) символов логических связок: ¬ (отрицание), (дизъ-

юнкция), &(коньъюнкция), →(импликация);3) вспомогательных символов: (,).

Правила образования ППФ:

1)Отдельно записанный атом есть ППФ (атомарная ППФ);

2)Если U и V ППФ, то ¬ (U), (U V), (U&V), (U→V), также являются ППФ.

3)Любая ППФ может быть построена путем применения конечного числа применений правил 2) из атомарных ППФ.

Как и в АВ, скобки, расположение которых однозначно определяется, можно опускать. Вместо записи ¬ (U), часто будем писать U .

Обратим внимание на то, что в данных правилах идет речь о синтаксисе по-

строения ППФ и символам логических связок на данном этапе не дается ника-

кого смыслового содержания.

Система аксиом в ИВ следующая (введена П.С.Новиковым):

5)(A→B) →((A→C)→(A→(B&C))); 9) (А→В)→(¬В→¬А);

10)A → A;

11)A → A.

Еще раз обратим внимания на тот факт, что здесь не идет речь ни о какой со-

держательной трактовке тех ППФ, которые выделяются в качестве аксиом фор-

мируемого ИВ .

Перед изложением правил вывода в ИВ дадим следующее определение.

Пусть U(X) некоторая ППФ и Х некоторый атом, входящий в эту формулу.

39

Пусть V есть другая ППФ. Одновременной заменой всех вхождений атома Х в

формулу U(X) на формулу V мы получим новую ППФ, которую будем обозначать

U(V) и которую будем называть результатом подстановки в U(X) вместо ато-

ма Х формулы V.

Правила вывода в ИВ. В ИВ существует два правила вывода: правило под-

становки и правило дедуктивного вывода (modus ponens).

Правило подстановки. Пусть U(X) некоторая ППФ и Х некоторый атом, вхо-

дящий в эту формулу. Пусть V есть также ППФ. Тогда:

Если U(X) есть теорема в ИВ, то U(V) есть также теорема в ИВ.

Правило подстановки позволяет на аксиомы 1)-11) ИВ смотреть не как на конкретные формулы с атомами А,В,С, а как на схемы аксиом, где вместо атомов могут стоять произвольные ППФ. Например, если вместо атома С в аксиоме 6

подставить формулу (С&D), то получим теорему ИВ:

(A → B) → ((A → (C & D)) → (A → (B & (C & D)))).

Правило дедуктивного вывода (modus ponens). Пусть U и U →V две пра-

вильно построенные формулы в ИВ. Тогда:

Если U и U →V являются теоремами в ИВ, то V также теорема в ИВ.

Будем теперь трактовать атомарные формулы, как высказывания, которые мо-

гут принимать два истинностных значения и или л, а связки операций ИВ

¬, , &, → как операции алгебры высказываний: отрицание, дизъюнкция,

конъюнкция и импликация с таблицами истинности, указанными в п. 1.

В таком случае каждую ППФ ИВ можно рассматривать как ППФ АВ. При этом оказывается справедливым следующее

Утверждение 1. Каждая теорема ИВ является тождественно истинной фор-

мулой алгебры высказываний.

Действительно. Нетрудно проверить, что все аксиомы ИВ являются тожде-

ственно истинными формулами АВ и что правила вывода в ИВ сохраняют свой-

ство формул быть тождественно истинными.

Кроме того, оказываются справедливыми следующие факты.

40

Утверждение 2 (свойство полноты системы аксиом). Каждая тождественно

истинная формула АВ является теоремой в ИВ.

Утверждение 3 (свойство непротиворечивости системы аксиом). В ИВ не

могут одновременно являться теоремами правильно построенные формулы U и

U .

Утверждение 4 (свойство независимости системы аксиом). Ни одна из аксиом ИВ не может быть выведена из остальных аксиом ИВ с помощью правил вывода данного исчисления.

. 2.3 Логика предикатов.

2.3.1 Понятие предиката.

Язык логики высказываний не вполне подходит для выражения понятий и ло-

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

ходе. Более выразительным является язык логики предикатов.

Пример рассуждения, невыразимого в логике высказываний.

«Все люди смертны. Сократ - человек. Следовательно, Сократ смертен».

Это рассуждение на языке логики высказываний можно записать тремя отдельными высказываниями. Однако никакой связи между ними установить не удается. Приведенное рассуждение на языке логики предикатов, как мы увидим в дальнейшем, легко записать в виде формулы, устанавливающей связь между двумя предикатами: «быть человеком'» и «быть смертным'»

Пусть имеется некоторое множество М. Через Мn будем обозначать n-ую прямую степень множества М, т.е. совокупность наборов {а1, а2,…, аn},

в которых каждое аi (i=1,…, n) есть некоторый элемент множества М.

Определение Функцию от n переменных x1, x2,…, x n, для которой Мn есть область определения и которая для каждого набора {а1, а2,…, аn} ее переменных принимает лишь два значения 0 или 1. будем называть

n-местным предикатом, определенным на множестве М и обозначать большими латинскими буквами Р,Q,R, S (быть с может с индексами) с указанием в скобках переменных, от которого он зависит. Например, запись P(x) обозначает одно-