Математическая логика и ТА (Рудаков С.А

Введение

Обратимся к Википедии.

Логика (др.-греч. λογική — раздел философии, «наука о правильном

мышлении», «искусство рассуждения» от λόγος — «речь», «рассуждение», «мысль») — наука о формах, методах и законах интеллектуальной познавательной деятельности, формализуемых с помощью логического языка. Поскольку это знание получено разумом, логика также определяется как наука о формах и законах правильного мышления. Поскольку мышление оформляется в языке в виде рассуждения, частными случаями которого являются доказательство и опровержение, логика иногда определяется как наука о способах рассуждения или наука о способах доказательств и опровержений. Логика как наука изучает способы достижения истины в процессе познания опосредованным путём, не из чувственного опыта, а из знаний, полученных ранее, поэтому её также можно определить как науку о способах получения выводного знания.

Логика служит одним из инструментов почти любой науки.

Математи́ческая ло́гика (теоретическая логика, символическая логика) — раздел математики, изучающий доказательства и вопросы

оснований математики.

Некоторые выдержки о математической логике.

«Предмет современной математической логики разнообразен.»

С. И. Адян, Математическая энциклопедия, М.: «Советская энциклопедия»,

т.3, с. 568, 571.

Согласно определению Н. И. Кондакова, «математическая логика — вторая, после традиционной логики, ступень в развитии формальной логики,

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

Н. И. Кондаков, Логический словарь-справочник, М.: «Наука», 1975, с. 259.

Это определение соответствует определению	С. К. Клини:
1

математическая логика — это «логика, развиваемая с помощью математических методов». С. К. Клини, Математическая логика, М., 1973,

с.12.

Также А. А. Марков определяет современную логику «точной наукой,

применяющей математические методы». А. А. Марков, Большая советская энциклопедия, Изд. 3, Предмет и метод современной логики.

Все эти определения не противоречат, а дополняют друг друга.

1 Классическая логика ФЛЭШ

1.1. Логика высказываний

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

Высказывание — это

(a)грамматически правильное повествовательное предложение,

(b)однозначно понимаемое,

(c)про которое можно сказать, что оно либо истинно, либо ложно.

Например:

«Киев — столица России», «Париж — столица Франции».

Первое высказывание является ложным, второе — истинным.

Замечание. Понятия "ложь", "истина" -- неопределяемые, имеют социальную природу. Высказывание может иметь потенциально некоторое значение "ложь" либо "истина", но неизвестно какое. Например, "На Марсе есть жизнь". В логике существуют различные обозначения:

"ложь" - "0", "F", "Л", "┴";

"истина" - "1", "T", "И", "┬ ".

Возьмем два высказывания:

А = «На улице идет дождь»,

В = «Над моей головой раскрыт зонтик».

Замечание. Использование знака равенства в логике требует

2

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

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

Мы ввели буквенные обозначения для высказываний (также как в алгебре введены буквы как обозначения цифр).

Буквы латинского алфавита ( возможно, с числовыми индексами),

используемые для обозначения высказываний будем называть

пропозициональными переменными или, просто, переменными (proposition - суждение).

Эти примеры высказываний (или похожие) используются как простые и понятные во многих учебниках по математической логике (). Однако не все приведенные предложения могут быть приняты безоговорочно за высказывания. В штате Техас существует свой Париж - нарушен пункт (b)

определения . Если вы звоните по телефону и сообщаете истинную фразу

«На улице идет дождь», то ваш собеседник, выглянув в окно, может также высказать истинное утверждение «На улице не идет дождь». Предложение A

не является высказыванием в силу того же пункта (b) . Предложения

«Казнить нельзя помиловать» или «йыча кепрт смитьбю» не являются высказываниями в силу нарушения пункта (a). Предложение "x < 7" не является высказыванием из-за пункта (c) определения.

В последующих примерах мы будем предполагать наличие контекста,

придающего предложениям свойства (b), (c) определения высказывания.

Свойство (a) должно выполняться безусловно. Например, используя предложение А = «На улице идет дождь» в качестве высказывания будем предполагать, что четко определены местоположение улицы и объем выпавших осадков, соответствующих дождю.

1.1.2 Операции

С помощью пяти логических связок отрицание (-), дизъюнкция (V),

конъюнкция (&), импликация (=>), эквивалентность (~) можно образовать

3

следующие сложные высказывания:

отрицание: -А = «На улице не идет дождь»;

дизъюнкция: -A V В = «На улице не идет дождь или над моей головой раскрыт зонтик»;

конъюнкция: А & -В = «На улице идет дождь и над моей головой не раскрыт зонтик»;

импликация: А => В = «Если на улице идет дождь, то над моей головой раскрыт зонтик»;

эквивалентность: В ~ А = «Над моей головой раскрыт зонтик

тогда и только тогда, когда на улице идет дождь».

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

Таблица 1 Таблицы истинности

A	B	A&B	AVB	A=>B	A~B		A	-A
0	0	0	0	1	1		0	1
0	1	0	1	1	0		1	0
1	0	0	1	0	0
1	1	1	1	1	1

Для словесной формулировки этих определений достаточно описать на родном языке одну-две строки из таблиц:

Конъюнкция двух высказываний – это высказывание истинное тогда и только тогда, когда оба высказывания истинны.

Дизъюнкция двух высказываний – это высказывание ложное тогда и только тогда, когда оба высказывания ложны.

Импликация двух высказываний – это высказывание ложное тогда и только тогда, когда посылка истинна, а следствие – ложно.

Эквиваленция (эквивалентность) двух высказываний – это высказывание истинное тогда и только тогда, когда оба высказывания истинны.

Отрицание высказывания - это новое высказывание истинное тогда и только тогда, когда исходное высказывание ложно.

4

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

AVB=>C. Это высказывание станет однозначным, если договориться о приоритете операций или расставить скобки в соответствии с порядком выполнения операций. Например, высказывание (AVB)=>C отличается от высказывания AV(B=>C), что видно из строк 5, 7 таблицы истинности для этих высказываний (см. таб. 2)

Таблица 2 Таблица истинности для высказываний

(AVB)=>C и AV(B=>C)

№	A	B	C	AVB	(AVB)=>C	B=>C	AV(B=>C)
1	0	0	0	0	1	1	1
2	0	0	1	0	1	1	1
3	0	1	0	1	0	0	0
4	0	1	1	1	1	1	1
5	1	0	0	1	0	1	1
6	1	0	1	1	1	1	1
7	1	1	0	1	0	0	1
8	1	1	1	1	1	1	1

1.1.3 Формулы и булевы функции

Индуктивное определение формулы (булевой формулы):

пропозициональная переменная есть (атомарная) формула;

если А и В формулы, то A&B, АVВ, А=>В формулы;

если А формула, то -А формула.

Пропозициональную переменную или её логическое отрицание

называют литералом.

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

5

во вложенных скобках. Порядок выполнения операций в формулах определяется также соглашением о приоритете логических операций:

1.Действия в скобках.

2.Отрицание.

3.Конъюнкция.

4.Дизъюнкция.

5.Импликация.

6.Эквивалентность.

Пример. –A V B & A V C => –B ~ B V C & A V –C. Расставим скобки:

(((–A) V (B & A) V C) => (–B)) ~ (B V (C & A) V (–C)). В следующей таблице отражен порядок выполнения операций (для упрощения записи скобки для отрицания опустили):

1.	–A		–B			–C
2.	B & A					C & A
3.	–A V (B & A) V C				B V (C & A) V –C
4.	(–A V (B & A) V C) => –B
5.	((–A V (B & A) V C) => –B) ~ (B V (C & A) V –C)

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

Формулы удобно представлять как функции от пропозициональных переменных. Если в формулу Y входят переменные X1, X2,..., Xn, то будем обозначать Y=Y(X1, X2,..., Xn).

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

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

Пример. (–A V B) & (A V C) & (–B) & (B V C) & (A V –C).

Теория, которая изучает формулы, определенные выше, назы-

вается алгеброй высказываний. В алгебре высказываний каждая

6

пропозициональная переменная, каждая формула принимает одно из двух значений - 0 (ложь) либо 1 (истина). Конкретно, значение,

принимаемое формулой при каждом наборе значений переменных, от которых она зависит, можно найти, построив таблицу истинности наподобие той, что приведена в таблице 2. Если в формулу входит K

переменных, то в таблице истинности будет 2K строк (в таблице 2

содержится 23=8 строк).

Функция f(X1, X2,...,Хп ) такая, что ее переменные и она сама могут принимать только два значения — 0 либо 1 — называется булевой функцией.

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

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

2n строках.

Таблица 3 Задание булевой функции

X1	X2	...	Хп	f(X1, X2,...,Хп)
0	0	0	0	f(0, 0,...,0)
0	0	0	1	f(0, 0,...,1)
...	...	...	...	...
1	1	1	0	f(1, 1,...,0)
1	1	1	1	f(1, 1,...,1)

Всего возможно задать 22n зависящих от n булевых переменных.

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

Теорема 1.1 Для любой булевой функции существует формула,

зависящая от тех же переменных, принимающая такие же

значения.

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

7

Положим f(X1, X2,...,Хп ) = ( f(0, 0,...,0)&(-X1)&(- X2)&...(-Хп ))V ( f(0, 0,...,1)&(-X1)&(- X2)&...( Хп ))V...

( f(1, 1,...,0)&(X1)&( X2)&...(-Хп ))V( f(1, 1,...,1)&(X1)&( X2)&...( Хп )).

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

1.1.4 Релейно-контактные схемы

Каждой булевой функции можно поставить в соответствие так на-

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

Элементам схемы (проводникам электрического тока) соответствуют пропозициональные переменные.

Релейно-контактная схема имеет вход и выход.

На входе подан ток.

Если через элемент схемы проходит ток, то значение соответствующей пропозициональной переменной равно 1, в противном случае – 0.

A

A

B

B

AVB

A&B

a)

b)

Рисунок 1 Релейно-контактные схемы дизъюнкции и конъюнкции

Релейно-контактная схема строится в предположении, что пропозициональная переменная X — это замыкающий контакт в элек-

трической схеме, который замкнут при подаче тока X, т.е. X = 1, и разомкнут

при его отсутствии, X = 0.

Дизъюнкции	A V B соответствует параллельное соединение
	8

(замыкающих) контактов (рис. 1 а)), a конъюнкции A & B —

последовательное соединение (рис. 1 b)).

Из простейших схем легко собираются произвольные релейно-

контактные схемы. Например, на рис. 2 приведена схема для пропозициональной формулы f(X,Y,Z,U,W) = (X&W&(-Z V У))V(U&-X).

-Z

X W

Y

U -X

Рисунок 2 Релейно-контактная схема для булевой функции f(X,Y,Z,U,W) = (X&W&(-Z V У))V(U&-X)

1.1.5 Равносильные формулы или логические законы

Две формулы A(X1 ,X2,..., Хn) и B(X1 ,X2,..., Хn) называются рав-

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

входящих в них переменных X1 ,X2,..., Хn. Для равносильных формул будем использовать обозначение А = В. Знак "=" позволит производить замену формул на равносильные. В алгебре высказываний часто используются следующие равносильные формулы, которые называют логическими

законами:

коммутативности

A&B=B&A конъюнкции,

AVB=BVA дизъюнкции;

ассоциативности

A&(B&C)= (A&B)&C конъюнкции,

AV(BVC)= (AVB)VC дизъюнкции;

идемпотентности

A&A= A конъюнкции,

9

AVA=A дизъюнкции;

дистрибутивности

A&(BVC)= (A&B)V(A&C) конъюнкции относительно дизъюнкции,

сравним, в алгебре, для чисел, A*(B+C)= (A*B)+(A*C),

AV(B&C)= (AVB)&(AVC) дизъюнкции относительно конъюнкции,

но, в алгебре, для чисел, A+(B*C)≠ (A+B)*(A+C);

поглощения

A&0=0,

AV0=A,

A&1=A,

AV1=1;

двойного отрицания

-(-A)=A;

де Моргана

-(A&B)=-AV-B - отрицание конъюнкции есть дизъюнкция отрицаний,

-(AVB)=-A&-B - отрицание дизъюнкции есть конъюнкция отрицаний;

противоречия

A & -A= 0;

исключенного третьего

A V –A = 1;

представления импликации

(A=>B) = (-A V B) через дизъюнкцию,

-(AVB) = -A&-B через конъюнкцию.

Все!

Упражнения

1. Доказать логические законы с помощью таблиц истинности.

Пример 1. Доказательство закона де Моргана: -(A&B)=-AV-B -

10