Неразрешимость логики первого порядка - Курсовая работа

формальный неразрешимость логика остановка Философы сформулировали наиболее важные идеи искусственного интеллекта, но для преобразования его в формальную науку потребовалось достичь определенного уровня математической формализации в трех фундаментальных областях: логика, вычисления и вероятность. Истоки идей формальной логики можно найти в работах философов древней Греции, но ее становление как математической дисциплины фактически началась с трудов Джорджа Буля (1815-1864), который детально разработал логику высказываний, или булеву логику. Рассмотреть понятие машины Тьюринга и доказать неразрешимость проблемы остановки. 3. Формальная теория считается определенной, если: - задано конечное или счётное множество произвольных символов (конечные последовательности символов называются выражениями теории); - имеется подмножество выражений, называемых формулами; - выделено подмножество формул, называемых аксиомами; - имеется конечное множество отношений между формулами, называемых правилами вывода. Дедуктивная теория считается заданной, если: - задан алфавит (множество) и правила образования выражений (слов) в этом алфавите; - заданы правила образования формул (правильно построенных, корректных выражений); - из множества формул некоторым способом выделено подмножество T теорем (доказуемых формул). 2) нелогические - множество предикатных символов, с которым связана арность, то есть число возможных аргументов P(n), Q(m), …, P1(n), P2(n); - символы пропозициональных переменных X, Y, Z, …, X1, X2, … (можно считать, что символы пропозициональных переменных - это нульместные предикатные символы); - символы предметных переменных x, y, z, …, x1, x2,…; - символы предметных констант a, b, c, …, a1, a2, … n-местным предикатом P (x1, x2,…, xn) называется функция P: M1ЧM2Ч…ЧMn > {1,0}, определенная на наборах длины n элементов некоторого множества M= M1ЧM2Ч…ЧMn и принимающая значения в области {1,0}. Отрицанием предиката P(x1, x2,…, xn), определенного на множестве M1ЧM2Ч…ЧMn называется предикат ¬P(x1, x2,…, xn), определенный на том же множестве, который на наборе (a1, a2,…, an) M1ЧM2Ч…ЧMn Конъюнкцией предикатов P(x1, x2,…, xn), определенного на множестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P Q(x1, x2,…, xn, y1, y2,…, ym) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn Дизъюнкцией предикатов P(x1, x2,…, xn), определенного на множестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P Q(x1, x2,…, xn, y1, y2,…, yn) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn Импликацией предикатов P(x1, x2,…, xn), определенного на множестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P > Q(x1, x2,…, xn, y1, y2,…, yn) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn Эквивалентностью предикатов P(x1, x2,…, xn), определенного на множестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P(x1, x2,…, xn) - Q (y1, y2,…, yn) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn Операцией связывания квантором общности переменной xi в n-местном предикате P(x1, x2,…, xn)), определенном на множестве M1ЧM2Ч…ЧMn, называется операция, в результате которой получается n-1-местный предикат xi P(x1, x2,…, xi-1, xi 1,…, xn), который при значениях x1 = a1, …, xi-1 = ai-1, xi-1 = ai-1, …, xn = an истинен, если при любых значениях xi = ai высказывание P(a1, a2,…, an) истинно.