Автор: Пользователь скрыл имя, 26 Октября 2011 в 21:07, шпаргалка
Шпаргалка по логике в системах искусственного интеллекта
2 курс, специальность ПО, факультет СКИТ
Этапы развития логики
1-й этап связан с работами Аристотеля (384-322 гг. до н.э.). Он дал систематическое изложение логики ( формальная логика или Аристотелева логика).
2-й этап - появление математической или символической логики.
3-й этап –этап парадоксов.
Определение высказывания:
Высказывания - предложения естественного языка, в которых содержится информация о предмете, факте, явлении, событии или процессе, и которые могут быть
оценены как истинные или ложные (напр. повествовательные предложения). Пример: “Колумб открыл Америку” – истина; “Киев – столица Узбекистана” - ложь.
Иногда истинность/ложность высказывания зависит от контекста.
Правила образования ППФ:
1) А - ППФ;
2) если А и В – ППФ, то (A), (А&В), (А В), (А В), A↔B – также ППФ.
3) других ППФ не существует.
Конъюнкцией двух высказываний А и В, называется высказывание А&В которое истинно тогда и только тогда, когда истинны одновременно оба высказывания (союз и)
Дизъюнкцией двух высказываний А и В называется высказывание А\/В, которое ложно тогда и только тогда, когда ложны одновременно оба высказывания (союз или)
Импликацией двух высказываний А и В, называется высказывание А-В, которое ложно тогда и только тогда, когда высказывание А истинно а В ложно. В обычной речи если..то
Эквивалентностью двух высказываний А и В называется высказывание А↔В, которое истинно тогда и только тогда, когда оба данных высказывания имеют одинаковые значения, т.е. либо оба истинны, либо оба ложны (тогда и только тогда)
Отрицанием высказывания А называется высказывание А\, которое истинно тогда и только тогда, когда А ложно
Интерпретация формулы - высказывание, получаемое из формулы подставлением конкректных высказываний/значений вместо переменных
ДНФ – дизъюнкция конъюнктов ( )/
КНФ – конъюнкция дизъюнктов ( ).
Алгоритм приведения формулы к ДНФ/КНФ:
1. Выражают все логические операции в формуле через дизъюнкцию, конъюнкцию и отрицание.
2. Используя
законы Де-Моргана переносят
3. Используют
закон дистрибутивности
4. Сократить полученную ДНФ/КНФ, применяя законы склеивания и поглощения.
5. Удалить
одинаковые дизьюнкты/
Одночлен называется совершенным, если каждая входящая в него переменная входит в него ровно один раз со знаком отрицания или без него.
СДНФ некоторой формулы называется дизъюнкция конституант единицы среди которых нет одинаковых.
СКНФ некоторой формулы называется конъюнкция некоторых конституант нуля среди которых нет одинаковых.
Алгоритм построения по таблицам истинности СДНФ/СКНФ:
1. Выбрать строку, на которой формула = 1/0.
2. Получить совершенный коньюнкт/дизьюнкт, включая в него с отрицанием те переменные, которые в этой интерпретации равны 0/1.
3. Перейти к следующей строке, на которой формула = 1/0.
4. После
перебора всех строк составить
СДНФ/СКНФ из полученных
Классификация формул
Формула F(X1,X2,…,Xn) называется выполнимой (опровержимой), если существует её истинная (ложная) интерпретация/выполняется хотя бы на одном наборе.
Формула F(X1,X2,…,Xn) называется тавтологией (противоречием), если любая её интерпретация истинна (ложна). Если тавт. то ╞F(X1,X2,…,Xn)
Равносильность
Две формулы F(X1,X2,…,Xn),G(X1,X2,…,Xn), будем называть равносильными, если для любых конкретных высказываний А1,А2,….,Аn их интерпретации совпадают, т.е. F(А1,А2,…,Аn)=G(A1,A2,…An) //формулы равносильны, если совпадают их таблицы истинности.
-Другие замечательные тождества.
Связь операций:
A=>B ≡ 7A V B
A↔B = (A→B) & (В→А)
A & В ≡ 7(A => 7B)
A v В ≡
7A→B
Любая
формула равносильными
Из определений д.н.ф. и к.н.ф. видно, что в любой д.н.ф., к.н.ф. участвуют только операции вида ‾,\/,&, причём отрицание может встречаться только над переменными. Отсюда равносильными преобразованиями ф-лы F(X1,X2,…,Xn) привод. Её к к.н.ф., д.н.ф. явл-ся :
Логическое следование: Формула G(x1,x2,…,xn) называется логическим следствием формулы F(x1,x2,…,xn), если для любых конкрет. высказываний А1,А2,…,Аn из истинности F(A1,…,An) следует истинность G(А1,А2,…,Аn). Обознач.:F├ G
Хорновский дизъюнкт - это дизъюнкт, содержащий не более одной литеры без отрицания. Хорновский дизъюнкт называется точным, если он содержит одну позитивную литеру. Если он не содержит позитивных литер, то называется негативным. Унитарный позитивный хорновский дизъюнкт представляет собой некоторый факт.
Задача проверки выводимости сводится к проверке на тождественную истинность. Существует несколько десятков методов и алгоритмов установления тождественной истинности логической формулы.
Идея: при
последовательных подстановках значений
переменных можно уменьшить длину
формулы, исходя из совокупности проведённых
проверок истинности F, и тем самым
сокращать число переменных для проверки.
Вводится понятие дерева испытаний, которое
по сути дела представляет собой граф
всех интерпретаций проверяемой формулы
. Квайн назвал его «семантическим
деревом». Пример: Пусть необходимо проверить
общезначимость формулы
. ИДЗ: ППФ
Метод резолюций для логики высказываний
Метод резолюций можно
Литеры A и ~A называются контрарными, а множество {A, ~A} – контрарной парой.
Допустим, что в дизъюнкте C1 существует литера L1 , контрарная литере L2 в дизъюнкте C2. Вычеркнем литеры L1 и L2 из дизъюнктов C1 и C2 соответственно и построим дизъюнкцию оставшихся дизъюнктов. Построенный дизъюнкт называется резольвентой дизъюнктов C1 и C2. Резольвента двух дизъюнктов является их логическим следствием. Резольвента двух единичных дизъюнктов (если она существует) – пустой дизъюнкт.
Резолютивный вывод C из множества дизъюнктов S есть такая конечная последовательность C1, C2, ..., Ck дизъюнктов, в которой каждый Ci (i=1, ..., k) или принадлежит S, или является резольвентой дизъюнктов, предшествующих Ci и Ck=C.
Метод семантической резолюции предусматривает, что при образовании каждой следующей резольвенты используется один дизъюнкт множества S1и один дизъюнкт множества S2 .
Свойства дедуктивных теорий:
Противоречивость
Теория, в которой множество теорем покрывает всё множество формул (все формулы являются теоремами, «истинными высказываниями»), называется противоречивой. В противном случае теория называется непротиворечивой. Выяснение противоречивости теории — одна из важнейших и иногда сложнейших задач формальной логики. После выяснения противоречивости теория, как правило, не имеет дальнейшего ни теоретического, ни практического применения.
Полнота
Теория называется полной, если в ней для любой формулы F выводима либо сама F, либо ее отрицание . В противном случае, теория содержит недоказуемые утверждения (утверждения, которые нельзя ни доказать, ни опровергнуть средствами самой теории), и называется неполной.
Независимость аксиом
Отдельная аксиома теории считается независимой, если эту аксиому нельзя вывести из остальных аксиом. Зависимая аксиома, по сути, избыточна, и ее удаление из системы аксиом никак не отразится на теории. Вся система аксиом теории называется независимой, если каждая аксиома в ней независима.
Разрешимость
Теория называется разрешимой, если в ней понятие теоремы эффективно, то есть существует эффективный процесс (алгоритм), позволяющий для любой формулы за конечное число шагов определить, является она теоремой или нет.
Проблемы аксиоматического исчисления высказываний.
Проблема разрешимости исчисления высказываний
Теорема Проблема разрешимости для исчисления высказываний разрешима.
Док-во:
любая формула исчисления высказываний - формула алгебры высказываний, и, следовательно, можно рассматривать ее логические значения на различных наборах значений входящих в нее переменных
Проблема непротиворечивости исчисления высказываний
Определение Логическое исчисление называется непротиворечивым, если в нем не доказуемы никакие две формулы, из которых одна является отрицанием другой.