Билеты МЛиТА
.docx-
Понятия формальной системы и дедуктивной теории. Основные определения теории формальных систем. Свойства формальных систем. Примеры.
Опр. Формальная система (или формальная теория) - результат строгой формализации теории, предполагающей полную абстракцию от смысла слов используемого языка, причем все условия, регулирующие употребление этих слов в теории, явно высказаны посредством аксиом и правил, позволяющих вывести одну фразу из других.
Формальная теория считается определенной, если:
- задано конечное или счётное множество произвольных символов (Алфавит);
- имеется подмножество выражений, называемых формулами;
- выделено подмножество формул, называемых аксиомами;
- имеется конечное множество отношений между формулами, называемых правилами вывода.
Опр. Аксиомы-подмножество формул(выражений)
Опр. Правила вывода –позволяют получить из множества формул получить новые формулы.
Опр. Выводимость : ф-ла В явл. выводимой в рамках некоторой формальной теории Т ,если существует ее вывод в рамках этой Т.
Опр. Теория для которой существует эффективный алгоритм, позволяющий узнать по формуле выводима ли она –называется эффективно разрешимой теорией.
Дедуктивная теория – формальная теория, которая задается след. образом:
-
Задан алфавит (множество) и правила образования выражений в этом алфавите.
-
Заданы правила образования формул (правильно построенных, корректных выражений).
-
Из множества формул некоторым способом выделено подмножество T теорем (доказуемых формул).
Разновидности дедуктивных теорий
-
Задание аксиом и правил вывода(Таким способом задается формальная теория (формальная аксиоматическая теория, формальное (логическое) исчисление).)
-
Задание только аксиом(Геометрия Евклида)
-
Задание только правил вывода(Теория молнията, теория естественного вывода)
Свойства дедуктивных теорий
-
Противоречивость(Теория, в которой множество теорем покрывает всё множество формул)
-
Полнота(Теория называется полной, если в ней для любой формулы F выводима либо сама F, либо ее отрицание .)
-
Независимость аксиом(Отдельная аксиома теории считается независимой, если эту аксиому нельзя вывести из остальных аксиом.)
-
Разрешимость(Теория называется разрешимой, если существует эффективный алгоритм, позволяющий для любой формулы за конечное число шагов определить, является она теоремой или нет.)
Примеры: Исчисление высказываний (логика высказываний, теория L),Теория первого порядка (теория K), и частный случай — логика первого порядка (исчисление предикатов, теория K1),Формальная арифметика (теория S).
-
Опр.Теория в которой все ф-лы выводимы -непротиворечивая теория.
-
Алгебра высказываний. Основные определения и понятия. Ранг формулы. Примеры подсчета ранга формулы.
Алгебра высказываний изучает способы построения высказываний из уже имеющихся высказываний, закономерности таких способов сочетания высказываний. В алгебре простым высказываниям ставятся в соответствии логические переменные (А, В, С и т.д.). Высказывание- утверждение на естественном языке о котором можно сказать истинно оно или ложно.
Основные операции алгебры высказываний:
1.Инверсия (отрицание);
Отрицание–это логическая операция, которая каждому простому
высказыванию ставит в соответствие составное высказывание,
заключающееся в том, что исходное высказывание отрицается.
2.Конъюнкция (логическое умножение);
Конъюнкция-это логическая операция, ставящая в соответствие
каждым двум простым высказываниям составное высказывание,
являющееся истинным тогда и только тогда, когда оба исходных
высказывания истинны.
3.Дизъюнкция (логическое сложение);
Дизъюнкция- это логическая операция, которая каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны и истинным, когда хотя бы одно из двух образующих его высказываний истинно.
4.Импликация (логическое следование и
эквивалентность (логическое равенство).
Импликация-это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда посылка (первое высказывание) истинно, а следствие (второе высказывание) ложно.
Эквивалентность– это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.
В курсе математической логики дается следующее определение формулы алгебры высказываний:
-
Переменные являются формулами.
-
Если A и B — формулы, то выражение A<связка>B являются формулой.
-
Всякая формула есть либо переменная или образуется из переменных последовательным применением правила 2.
(?)Ранг ф-лы – это число сопостав. фор-л по след правилам:
-
Ранг атомарный(прост.ф-ла/буква=0)
-
Если у имеются ф-лы F и G рангов n1 и n2 мост. То р-г ф-л (F^G) равен (F→(G)) max(n1 , n2)
-
Логическое значение сложного высказывания в алгебре высказываний. Логическая эквивалентность и ее свойства. Признак логической эквивалентности. Основные эквивалентности алгебры высказываний.
Сложное высказывание –это логическая функция, которая устанавливает соответствие между одним или несколькими высказываниями, которые называются аргументами функции, и высказыванием которое называется значением функции.
Теорема о интерпретации сложной формулы:
Логическое значение сложной формулы F(A1…An) равно значению формулы F(x1….xn) на наборе I(A1)…I(An).
1) Определение 4.1. Формулы F(X1,X2,…,Xn) и G(X1,X2,…,Xn) алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них пропозициональных переменных логические значения получающихся из формул F и G высказываний совпадают.
2)I(A)- значение ф-лы А при интерпретации
Опр. Назовем F(x1…xn) G(x1…xn) равносильными(лог. эквивалентными), если I(F)=I(G)для любой интерпретации I.
Пример: F=A→B ↔ G=¬A∨B
A |
B |
F |
G |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
Сущность признака состоит в выявлении тесной связи между понятием равносильности формул и понятием тавтологии. Теорема 4.2 (признак равносильности формул). Две формулы F и G алгебры высказываний равносильны тогда и только тогда, когда формула F↔G является тавтологией. Следствие 4.3. Отношение равносильности между формулами алгебры высказываний:
а) рефлексивно: F≅F; б) симметрично: если
F1≅F2, то F2≅F1; в) транзитивно: если
F1≅F2и F2≅F3, то F1≅F3, т.е. отношение равносильности является отношением эквивалентности.
коммутативность
• A∧B≅B∧A
• A∨B≅B∨A;
Ассоциативность
• A∧(B∧C)≅(A∧B)∧C;
• A∨(B∨C)≅(A∨B)∨C;
Дистрибутивность
• A∧(B∨C)≅(A∧B)∨(A∧B);
• A∨(B∧C)≅(A∨B)∧(A∨C);
Правила поглощения:
• A∧(A∨B)≅A;
• A∨(A∧B)≅A;
Законы Де-Моргана
• ¬(A∧Q)≅¬A∨¬B;
• ¬(A∨B)≅¬A∧¬B;
Снятие 2го отрицания
-
¬¬А≅А
Идемпотентность
-
A∧A≅A
-
A∨A≅A;
Свойства констант
-
A∨1≅1, A∧1≅A;
-
A∨0≅A, A∧0≅0.
Закон исключения третьего и закон противоречия
A∧¬A≅0, A∨¬A≅1;
Правило склеивания
(A∨ B) ∧ (A∨¬B) ≅A
(A∧ B) ∨ (A∧ B) ≅A
-
Классификация формул алгебры высказываний. Соответствие между формулами алгебры высказываний и формализованного исчисления высказываний. Основные тавтологии алгебры высказываний (с хотя бы одной проверкой).
Опр. Фор-ла АВ, истина в любой интерпретации называется тавтологией.
Опр. Фор-ла АВ, ложная при любой интерпретации называется противоречивой.
Опр. Фор-ла АВ, истина хотя бы в одной интерпретации называется выполнимой.
Опр. Фор-ла АВ, ложная хотя бы в 1 интерпретации называется опровержимой.
В основе формализованного исчисления высказываний лежат понятия, относящиеся к так называемой области синтаксиса, т.е. понятия, представляющие собой некие абстрактные, лишенные смысла знаки и формальные действия с ними: алфавит, формула, аксиома, правило вывода, доказательство, теорема. Эти понятия принято называть синтаксическими. В то же время алгебра высказываний пронизана содержательным смыслом: за каждой переменной стоит конкретное высказывание нашего языка, каждая формула может превращаться в конкретное составное высказывание, некоторые формулы могут превращаться только в истинные высказывания (тавтологии) и т.д. В данной сфере, являющейся областью семантики, каждое понятие наполнено каким-то внутренним содержанием, смыслом. Понятия истины и лжи, тождественной истинности и тождественной ложности формул, равносильности и логического следования формул считаются понятиями семантическими.
Формулы ИВ можно интерпретировать как формулы алгебры высказываний. Для этого будем трактовать переменные ИВ как переменные алгебры высказываний, т.е. переменные в содержательном смысле, принимающие два значения: 1 и 0.
Т.3.1. Каждая формула, доказуемая в исчислении высказываний, является тождественно истинной (тавтологией) в алгебре высказываний.
Т.3.2. Каждая тождественно истинная формула (тавтология) алгебры высказываний доказуема в исчислении высказываний.
Теоремы 3.1 и 3.2 - формулировка свойств полноты исчисления высказываний.
Т.3.3. Формула тогда и только тогда доказуема в исчислении высказываний (является теоремой исчисления), когда она является тавтологией алгебры высказываний.
Основные тавтологии:
а) закон исключенного третьего A∨¬A ; б) закон отрицания противоречия ¬(A∧¬A); в) закон двойного отрицания ¬¬A↔A; г) закон тождества A→A; д) закон контрапозиции (A→B)↔(¬B→¬A); е) закон силлогизма (правило цепного заключения) ((A→B)∧(B→C))→(A→C); ж) закон противоположности (A↔B)↔(¬A↔¬B); з) правило добавления антецедента ("истина из чего угодно") A→(B→A); и) правило "из ложного что угодно" ¬A→(A→B); к) правило modus ponen (A∧(A→B))→B; л) правило modus tollens ((A→B)∧¬B)→¬A; м) правило перестановки посылок (A→(B→C))↔(B→(A→C)); н) правило объединения (и разъединения) посылок (A→(B→C))↔((A∧B)→C); о) правило разбора случаев ((A→C)∧(B→C))↔((A∨B)→C); п) правило приведения к абсурду ((¬A→B)∧(¬A→¬B))→A, (¬A→(B∧→B))→A
-
Формализованное исчисление высказываний. Основные определения и понятия формализованного исчисления высказываний. Примеры теорем в формализованном исчислении высказываний и выводимости из гипотез.
Зададим формальную систему связанную с ИВ:
-
Алфавит, служебные символы, связки: основные и дополнительные.
-
Правило построения ф-л(Переменные являются формулами. Если A и B — формулы, то выражение A<связка>B формула. )
-
Аксиома-выделенное из множества формул подмножество.
-
Правило вывода - множество отношений из множества формул,позволяющие из аксиом получить теоремы формальной теории.
Опр. Вывод в теории ИВ,это такая последовательность формул которая удовлетворяет требованиям: 1. F1 аксиома 2. F1….. Fn аксиомы или следствия из предыдущих шагов вывода 3. Fn теорема
Опр. Т выводима, если существует ее вывод в И; Т выводима↔ теорема Т.
Опр. Гипотеза-некоторое утверждение ФИВ необязательно являющиеся аксиомами, но на которые мы можем опираться при док-ве тех или иных утверждений ФИВ по нашему условию.
Пусть верно А : А ⊢(В→А)
1. А {гипотеза} 2. А→(В→А) {А1} 3. В→А {mp 1,2}
Опр. Выводим F из множества гипотез G-послед. ф-л F1….Fn где
1. F1 – аксиома или гипотеза
2. F2 …Fn – гипотезы ,аксиомы полученные из пред. шагов по правилам вывода
3. Fn =F
16. Чистое ИП(1 порядка)- формальная теория K,в которой определены след.компоненты.
1.Алфавит и связки: основные→¬ дополнительные&∨
2.Служебные символы(,)
3.Кванторы:всеобщности ∀ и существования Ǝ
4.Предметные константы(a,b…,a1,b1) и переменные(x,y…)
5.Предметные предикаты(P,Q,..) функциональные символы(f;g,..)
С каждым предикатом и функ.буквой связано некоторое натуральное число,которое называется арностью,местностью,вместимостью.