Глава 4. Основы математической логики 169

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

Пример: 169

Пример: 170

4.1.1. Алгебра высказываний 171

4.1.1.1. Логические операции 171

4.1.1.2. Правила записи сложных формул. 174

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

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

F =(A(BC))&(BD)&((D&A) C). 174

AB; AC; CD; D 175

B. 175

Приведенные примеры позволяют сформулировать некоторые правила записи сложных суждений: 177

F=((F₁(F₂))F₃)F₄; 178

F=(F₁(F₂))F₃F₄; 178

F=F₁(F₂)F₃F₄; 178

F=F₁F₂F₃F₄; 178

4.1.1.3. Законы алгебры высказываний 178

F(F_j). 179

Любая замена переменной или формулы определяется правилом подстановки. 179

_А ^В (ACA) 179

4.1.1.4. Эквивалентные преобразования формул 179

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

F= (F₁F₂)(( F₂F3)((F₁F₂) F₃); 180

F=F₁F₂F₂F₃F₁F₂F₃; 180

F=( F₁F₁) F₂F₂F₃ F₃; 180

F=F₂F₂F₃ F₃; 180

F=F₂(F₂F3) (F₃ F₃); 180

F=F₂(F₂F3); 180

F=(F₂F₂)F₃; 180

F=(F₁F₂)(F₃F₄)(F₁F₂)(F₃F₄); 180

F=F₁F₂(F₃F₄)  F₁F₂(F₃F₄); 180

F=( F₁ F₁) F₂(F₃F₄); 180

F=F₂(F₃F₄). 180

Следовательно, (F₁F₂)(F₃F₄)(F₁F₂)(F₃F₄)=F₂(F₃F₄) 180

F=А(AВ)АСАВС; 180

F=А (АВ)АСАВС; 180

F=А (АВ)AАСАВС; 181

F=А((АВ) АСВС); 181

F=А((АВ) С(АВ)); 181

4.1.1.5. Нормальные формы формул 182

В алгебре высказываний используют две нормальные фор­мы: дизъюнктивную (ДНФ) и конъюнктивную нормальные формы формулы (КНФ). 182

Так сформирована КНФ. 183

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

4.1.2.1. Интерпретация формул 183

4.1.2.2. Аксиомы и правила введения и удаления логических связок 185

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

Известна система из трех аксиом, использующая две логических связки “” и “” или система из пяти аксиом, использующая логические связки “” и “”. 185

Однако наибольшей популярностью пользуется счистема из двенадцити аксиом, использующая логические связки “”, ””, “” и ””. Эта система позволяет наиболее удобно и за меньшее число шагов организовать вывод заключения. 185

А1. F₁(F₂F₁); 185

А2. (F₁ F₂) ((F₂ F₃)) (F₁ F₃)); 185

А3. (F₁ F₂)F₁; 185

А4. (F₁ F₂)F₂; 185

А5. F₁(F₂(F₁F₂)); 185

А6. F₁(F₁F₂); 185

А7. F₂(F₁F₂); 185

А8. (F₁F₃)((F₂F₃)((F₁F₂)F₃)); 185

А9. (F₁F₂)(( F₁ F₂) F₁); 185

A10. (F₁F₂)((F₁F₃)(F₂F₃)); 185

A11. (F₁ F₂)((F₁F₃)(F₂F₃)); 186

А12.  F₁  F₁. 186

А2. (F₁ F₂)(( F₁( F₂ F₃))( F₁ F₃)). 186

А8. (F₁ F₃)(( F₂  F₃)(( F₁  F₂) F₃)) 186

4.1.2.3. Метод дедуктивного вывода 188

Выводом формулы В из множества формул F₁; F₂; . . . F_n называется такая последовательность формул, что любая F_i есть либо аксиома, либо выводима из множества предшествующих ей формул F₁; F₂; . . . F_n. 188

b) если F_j и (F_iF_j) выводимые формулы, то F_i также выводимая формула: 189

(F_iF_j) 189

B; AB 189

Пример. доказать истинность заключения: 190

C A. 190

191

Ниже показан процесс дедуктивного вывода заключения. 191

F₁=(DBE) - посылка; 191

F₂=E - посылка; 191

F₆=(СD) - заключение по F₄ и правилу П2; 191

F₇=(BA) - заключение по F₅ и правилу П2; 191

F₈=(DB) - заключение по F₃ и закону де Моргана; 191

Пример: доказать истинность заключения: 191

((A  B) С); (С(D  M )); (MN); (( D)( N)) 191

F₁₃=A - заключение по F₁₂ и правилу П2. 192

4.1.2.4. Принцип резолюции 192

Шаг 1: принять отрицание заключения, т.е.  В; 193

Пример: доказать истинность заключения 193

ABN. 193

CDM=(CD)M=(CDM) –посылка (один дизъюнкт); 194

Пример: доказать истинность заключения 195

(AB)(CD); (DBM); M 195

(AC). 195

197

4. 2. Логика предикатов 197

4.2.1. Алгебра предикатов 201

Если F₁ и F₂ формулы, то (F₁ ); (F₁ F₂); (F₁F₂); (F₁F₂ );(F₁F₂ ) также формулы. 201

4.2.1.1. Законы алгебры предикатов 205

x(F(x))x(F(x))=и, для {;} 205

x(F(x))x(F(x))=л, для {;} 205

4.2.1.2. Предваренная нормальная форма формулы 206

Алгоритм приведения формулы к виду ПНФ: 206

Пример: F=x₁x₂(P₁(х₁)x₃ (P₂(х₁, x₃)P₃(x₂, x₃))). 206

K={ P₁(х₁); P₂(х₁; x₃); P₃(x₂;x₃)). 207

Пример: F=(_x(P₁ (х)_y(P₂ (y)P₃ (z))))(_y(P₄ (x; y)P₅.(z))). 207

4.2.1.3 Сколемовская стандартная форма формулы 208

Алгоритм приведения формулы к виду ССФ: 208

Пример: F=_x1_x2_x3_x4_x5_x6((P₁(x₁, x₂)P₂(x₃, x₄, x₅))P₃(x₄, x₆)). 208

заменить предметную переменную x₆ на функцию f₂(x₂, x₃, x₅): 208

F=_x2_x3_x5((P₁(a, x₂)P₂(x₃, f₁(x₂, x₃), x₅))P₃(f₁(x₂, x₃), 208

f₂(x₂, x₃, x₅))). 209

Множество дизъюнктов матрицы: 209

К={(P₁(a, x₂)P₂(x₃, f₁(x₂, x₃), x₅)); P₃(f₁(x₂, x₃), f₂(x₂, x₃, x₅))}. 209

заменить предметную переменную x₆ на функцию f₂(x₂, x₃, x₅): 209

F=_x2_x3_x5((P₁(a, x₂)P₂(x₃, f₁(x₂, x₃), x₅))P₃(f₁(x₂, x₃), 209

f₂(x₂, x₃, x₅))). 209

Множество дизъюнктов матрицы: 209

К={(P₁(a, x₂)P₂(x₃, f₁(x₂, x₃), x₅)); P₃(f₁(x₂, x₃), f₂(x₂, x₃, x₅))}. 209

4. 2. 2. Исчисление предикатов 209

Логический вывод заключения есть теорема: 211

4.2.2.1. Правила подстановки 211

Если в формулу F(х), содержащую свободную переменную x, выполнить всюду подстановку вместо x терма t , то получим формулу F(t). 211

Этот факт записывают так: 211

x ^t F(x) 212

F(t). 212

Подстановка называется правильной, если в формуле всюду вместо свободной переменной x выполнена подстановка терма t.. 212

Например, 212

_x1^x2x₃(P₁(x₁, x₃)P₂(x₂)) 212

x₃(P₁(x₂, x₃)P₂(x₂)). 212

Это - правильная подстановка, так как x₁ –свободная переменная. 212

212

_x1^{f(x2, t)} x₃(P₁(x₁, x₃) P₂(x₂)) 212

x₃(P₁(f(x₂, t), x₃) P₂(x₂)). 212

Это - правильная подстановка, так как x₁ –свободная переменная. 212

. _x3^x2x₃(P₁(x₁, x₃) P₂(x₂)) 212

x₃(P₁(x₁, x₂) P₂(x₂)). 212

Это - неправильная подстановка, т.к. x₃ –связанная _x3. 212

_x2^x3x₃(P₁(x₁, x₃) P₂(x₂)) 212

x₃(P₁(x₁, x₃) P₂(x₃)). 212

Это - неправильная подстановка, т.к. предикат P₂(x₃) попадает в область действия квантора x₃. 212

4.2.2.2. Правила введения и удаления кванторов 213

П1. Если дана формула (F₁(t)F₂(x)) и F₁(t) не содержит свободной переменной x, то формула (F₁(t)x(F₂(x))) выводима в исчислении предикатов, т.е. 213

(F₁(t) F₂(x)) 214

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

4.2.2.3. Правила заключения 215

b) если F₂ и (F₁F₂) выводимые формулы в исчислении предикатов, то F₁ также выводима. Это - правило modus tollens (m.t): 215

F₂; (F₁F₂) 215

F1. 215

4.2.2.4. Метод дедуктивного вывода 215

4.2.2.5. Принцип резолюции 218

F₂=_x(P₁(x)_y(P₄ (y)P₃(x; y)))=_x_y(P₁(x)(P₄ (y)P₃(x; y)))= 219

_x_y(P₁(x)P₄ (y)P₃(x; y))); 219

F₃=_y(P₂ (y)P₄(y))=_y((P₂(y)P₄(y)))=_y(P₂(y)P₄(y))=P₂(b)P₄(b). 219

4.2.2.6. Логическое программирование 221

4.3. Логика реляционная 224

4.3.1 Реляционная алгебра 227

4.3.1.1. Унарные операции 229

4.3.1.2. Бинарные операции 232

4.3.1.3. Правила реляционной алгебры 235

r’=(r₁><r₂)= (r₂><r₁) - операция соединения коммутативна; 236

4.3.2. Реляционное исчисление 236

если r - имя отношения, а t - терм, то r(t) –элементарная формула; 236

4.3.3. Языки реляционной логики 238

4.4. Нечеткая логика 241

4.4.1. Нечеткое исчисление 241

4.4.2. Экспертные системы 244

Вопросы и задачи 247

b) (((((AB)A)B)C)C); 247

c) (A(BC))(AC)(AB). 247