Сделай Сам Свою Работу на 5
Главная | Контакты

Соответствие между предикатами и функциями





Предикаты и высказывания

Под н-местным предикатом понимается произвольное высказывание.

Выражения P(a1, …,an), где a1, …,an ÎM, будем понимать как высказывание «P(a1, …,an) = 1» или как «P(a1, …,an) истинно», а выражение P(x1, …,xn), где x1, …,xn — переменные, как переменное высказывание

!!! P(x1, …,xn) — это логическая переменная, а x1, …,xn — нелогические переменные.

Соответствие между n–местными отношениями и n–местными предикатами

a)каждому n–местному отношению R соответствует предикат P такой, что P(a1, …,an) = 1, если и только если (a1, …,an) Î R;

б) всякий предикат P(x1, …,xn) определяет отношение R такое, что (a1, …,an) Î R, если и только если P(a1, …,an) = 1.

Соответствие между предикатами и функциями

Всякой функции f(x1, …, xn), f: Mn ® M соответствует предикат P(x1, …, xn, xn+1), P:Mn+1 ® B,такой, что P(a1, …,an, an+1) = 1, если и только если f(a1, …,an) = an+1.

Понятие предиката шире понятия функции, поэтому обратное соответствие (от (n + 1)-местного предиката к n-местной функции) возможно не всегда, а только для таких предикатов P¢ для которых выполняется условие: если P¢(a1, …,an, an+1) = 1, то для любого a¢n+1 ¹ an+1 P¢(a1, …,an, a¢n+1) = 0.

32. Синтаксис языка логики предикатов: алфавит, термы, атомы, правила построения формул.



Язык логики первого порядка строится на основе сигнатуры, состоящей из множества функциональных символов F и множества предикатных символов P. С каждым функциональным и предикатным символом связана арность, то есть число возможных аргументов. Допускаются как функциональные, так и предикатные символы арности 0. Первые иногда выделяют в отдельное множество констант. Кроме того, используются следующие дополнительные символы

Символы переменных (обычно и т. д.),

Пропозициональные связки: ,

Кванторы: всеобщности и существования ,

Служебные символы: скобки и запятая.

Перечисленные символы вместе с символами из P и F образуют Алфавит логики первого порядка. Более сложные конструкции определяются индуктивно:

Терм есть символ переменной, либо имеет вид где f — функциональный символ арности n, t1 tn термы. А́рность предиката количество их аргументов, или операндов.

Атом имеет вид , где р — предикатный символ арности n , а , t1 tn — термы.



Предикатные формулы строятся с помощью логических операций и скобок.


33, 34, 35

33. Кванторные операции. Свободные и связанные вхождения переменных. Логический квадрат.

· Пусть P(x) — предикат, определенный на M

· «для всех x из M P(x) истинно» обозначается "x P(x) Знак "x называется квантором общности; другое его обозначение (x).

· Высказывание «существует такой x из M, что P(x) истинно» обозначается $x P(x). Знак $ x называется квантором существования.

· Переход от P(x) к "x P(x) или $x P(x) называется связыванием переменной x, а также навешиванием квантора на переменную x (или на предикат P), иногда — квантификацией переменной x.

· Переменная, на которую навешен квантор, называется связанной; несвязанная переменная называется свободной.

34. Численные кванторы. Ограниченные кванторы.

Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Предика́т (n-местный, или n-арный) — это функция с областью значений {0,1} (или «Истина» и «Ложь»), определённая на n-й декартовой степени множества M. Таким образом, каждую n-ку элементов M он характеризует либо как «истинную», либо как «ложную».

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



35. Множество истинности предикатов. Равносильность и следование предикатов.

Предикатом называется предложение, содержащее одну или несколько переменных, при подстановке в которые конкретных значений, предложение обращается в высказывание. ВЫСКАЗЫВАНИЕ- это повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Две формулы А и В являются равносильными на области М, если они принимают одинак логические значения при всех значениях входящих в них переменных, отнесенных к области М.Иначе, предикаты P(x1, …,xn) и Q(x1, …,xn) равносильны тогда и только тогда, когда P+ = Q+.Предикат Q(x1, …,xn) заданный над множествами M1 , M2,… , Mn называется следствием предиката P(x1, …,xn), заданного над теми же множествами, если он превращается в истинное высказывание на всех тех наборах значение предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат P(x1, …,xn).

Иначе, предикат Q является следствием предиката P (P Þ Q) тогда и только тогда, когда P+Í Q+.


36, 37, 38

36. Семантика языка логики предикатов, интерпретация формул. Три ситуации при логической интерпретации формул логики предикатов. Проблемы получения истинных формул и проверки формулы на истинность. Эквивалентные соотношения логики предикатов.

Превращение формулы логики предикатов в высказывание при подстановке вместо предикатных переменных конкретных предикатов, определенных на некотором выбранном множестве M, и, далее, вместо предметных переменных конкретных предметов, называется интерпретацией этой формулы на множестве M.

1. Если в М для F существует такая интерпретация, что F становится истинным (ложным) высказыванием, то формула F называется выполнимой (опровержимой) в области М. Если существует область М, где F выполнима, то F называется просто выполнимой.

2. Если формула F выполнима в М при любых интерпретациях, то она называется тождественно истинной в М. Формула, тождественно истинная в любых М называется тождественно истинной или общезначимой или тавтологией.

3. Если формула F невыполнима в М, она называется тождественно ложной в М. Если F невыполнима ни в каких М, она называется тождественно ложной или противоречием.

Формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения.

37. Приведенная нормальная форма. Процедура получения приведенной нормальной формы.

Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются только операции Ø, Ù, Ú, причем знаки отрицания относятся лишь к предикатным переменным и к высказываниям.

Теорема 1. Для всякого предиката существует равносильная ему приведенная нормальная форма.

Доказательство. Действительно, все операции в данной предикатной формуле можно выразить через конъюнкцию, дизъюнкцию и отрицание (например, в виде ДНФ). Если после этого некоторые отрицания будут относиться к частям формулы, содержащим кванторы, то отрицания можно “снять” с кванторов согласно равносильностям, а “снять” отрицания с конъюнкций и дизъюнкций можно, следуя законам де Моргана. После всех описанных преобразований предикат, очевидно, будет представлен в приведенной форме.

38. Предваренная нормальная форма. Процедура получения предваренной нормальной формы.

Предваренной нормальной формой (ПНФ) для формулы логики предикатов называется такая ее приведенная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т.е. это формула вида (Q1x1)(Q2x2)…(Qmxm)(F(x1, …, xn)), где Qi есть один из кванторов " или $ (i = 1,…,m), m £ n, причем (F(x1, …, xn) не содержит кванторов и является приведенной формулой.

1) Используя формулы P1 ~ P2 = (P1 ® P2) & (P2 ® P1), P1 ® P2 = Ø P1 Ú P2

заменить ®, « на &, Ú, Ø.

2) Спустить символы отрицания непосредственно на символы предикатов

3) Для формул, содержащих подформулы вида "xP1(x) Ú "xP2(x), $xP1(x) Ú $xP2(x),

ввести новые переменные, позволяющие использовать эквивалентные соотношения

4) С помощью эквивалентных соотношений получить формулы в виде ПНФ

39. Проблема разрешимости для общезначимости и выполнимости формул логики предикатов. Теорема Черча. Частные случаи.

Формула А логики предикатов называется выполнимой в области М, если существуют значения переменных, входящих в эту формулу и отнесенных к области М, при которых формула А принимает истинные значения. Формула А называется тождественно истинной в области М, если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области. Формула А называется общезначимой, если она тождественно истинная на всякой области.

Не существует алгоритма, позволяющего распознать общезначимость, нейтральность или невыполнимость произвольной формулы исчисления предикатов. Пример формулы, выполнимой на бесконечном множестве и невыполнимой ни на каком конечном множестве("x)($y)(P(x, y)) Ù ("x)(ØP(x, х)) Ù ("x)("y)("z)[(P(x, y) Ù P(y, z)) ® P(x, z)].

40. Методы доказательства в логике предикатов.

Метод интерпретаций или методом моделей — доказательство формул, содержащих переменные, путем непосредственной постановки в них констант.

Множество истинных формул порождается из исходных формул (аксиом) с помощью формальных процедур — правил вывода.

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

Множества, порожденные такими формальными методами, называются формальными системами.


41, 42

41. Исчисление предикатов как формальная система. Формальный вывод в исчислении предикатов. Правило переименования свободных переменных. Правило переименования связанных переменных.

Формальная система — это совокупность абстрактных объектов, не связанных с внешним миром, в котором представлены правила оперирования множеством символов в строго синтаксической трактовке без учета смыслового содержания, то есть семантики. Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката.Предикатом называется предложение, содержащее одну или несколько переменных, при подстановке в которые конкретных значений, предложение обращается в высказывание.ВЫСКАЗЫВАНИЕ- это повествовательное предложение, о котором можно сказать, что оно истинно или ложно.

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

Выводом формулы G в исчислении предикатов называется конечная последовательность формул B1, . . ., Bm такая, что каждая из формул Bi либо есть аксиома, либо получается из некоторых предшествующих ей формул по одному из перечисленных правил вывода, и Bm совпадает с G. Формула G выводима в исчислении предикатов, или является теоремой, если можно построить вывод этой формулы.

Правило переименования свободных переменных

Из выводимости формулы F(x), содержащей свободные вхождения x, ни одно из которых не находится в области действия квантора по у, следует выводимость F(y).

1) |– F(x) — по условию

2) F(x) ® (G ® F(x)) — А1, в качестве G выбираем любую доказуемую формулу, не содержащую свободных вхождений x.

3) (G ® F(x)) — из 1 и 2 по МР

4) G ® "x F(x) — правило обобщения к 3

5) "x F(x) — МР к 4 и G

6) F(y) — МР к РА1 и 5 (ч.т.д.)

Правило переименования связанных переменных

"x F(x) |– "y F(y), $x F(x) |– $y F(y) при условии, что F(x) не содержит свободных вхождений y и содержит свободные вхождения x, ни одно из которых не входит в область действия квантора по y.

1) |–"x F(x) — по предположению

2) "x F(x) ® F(y) — аксиома РА1

3) "x F(x) ®"y F(y) (правило обобщения к 2)

4) "y F(y) — МР к 1 и 3

42. Выводимость и истинность в логике предикатов. Эквивалентные преобразования.

Теорема 1. Всякая доказуемая формула исчисления предикатов тождественно-истинна (общезначима)

Теорема 2. Всякая общезначимая предикатная формула доказуема в исчисления предикатов.

Теорема 3.Пусть F(А) — формула, в которой выделено вхождение формулы А; F(В) — формула, полученная из F(А) заменой этого вхождения А формулой В. Тогда если |- А ~ В, то |- F(А) ~ F(В).

Благодаря теореме 3) можно получать доказуемые эквивалентности в исчислении, не строя их непосредственного вывода.

1) если |- А ~ В, то |- А ® С ~ В® С и |- С® А ~ С® В;

2) если |- А ~ В, то |- А Ú С ~ В Ú С и |- СÚ А ~ С Ú В;

3) если |- А ~ В, то |- А & С ~ В & С и |- С & А ~ С & В;

4) если |- А ~ В, то |- Ø А~Ø В;

5) если |- F(x) ~ G(x), то |- "x F(x) ~ "x G(x);

6) если |- F(x) ~ G(x), то |- $x F(x) ~ $x G(x).


43, 44, 45, 46

43. Предваренная, сколемовская и клаузальная формы. Алгоритм получения клаузальной формы.

Формула, имеющая вид Q1x1 Q2x2 …QnxnF, где Q1, Q2, …, Qn — кванторы; F — формула, не имеющая кванторов, и являющаяся областью действия всех n кванторов, называется предваренной формулой, или формулой в предваренной форме.

Сколемовская форма – это такая предварённая форма, в которой исключены кванторы существования.

Сколемовское преобразование (исключение $-квантификации):

сопоставить каждой $-квантифицированной переменной список "-квантифицированных переменных, предшествующих ей, а также некоторую ещё не использованную функциональную константу, число мест у которой равно мощности списка.

В матрице формулы заменить каждое вхождение каждой $-квантифицированной переменной на некоторый терм. Этот терм является функциональной константой со списком аргументов, соответствующих предшествующим "-квантифицированным переменным и называется сколемовской функцией.

Устранить из формулы все $-квантификации.

Клаузальная форме это сколемовская стандартная форма, у которой матрица имеет вид КНФ.

44. Метод резолюций в логике предикатов. Унификация. Условия унификации. Множество рассогласований. Алгоритм унификации для нахождения наиболее общего унификатора. Алгоритм метода резолюций применительно к логике предикатов.

Для того чтобы, было возможно применить метод резолюций для определения выполнимости множества предикатов необходимо произвести операцию УНИФИКАЦИИ, то есть конкретизировать как область определения предиката, так и объекты всех предикатов заданного множества. Унификатором двух термов называется подстановка, которая делает термы одинаковыми. Алгоритм метода резолюций применительно к логике предикатов:

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

2) находится подстановка, при которой какой-либо литерал одного предложения становится дополнительным к какому-либо литералу другого предложения, и эта подстановка производится в оба предложения;

3) литералы, дополнительные друг к другу вычеркиваются;

4) если имеются одинаковые литералы, то все они, кроме одного в каком-либо предложении, вычеркиваются;

5) дизъюнкция литералов, оставшихся в обоих предложениях, и есть резольвента.

Определим основные компоненты алгоритма унификации (нахождения наиболее общего унификатора) двух термов.

1. Константы унифицируемы, когда они совпадают

2. Переменные унифицируемы со всеми (константы, переменные, термы)

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

45. Принцип логического программирования.

Логическая программа — множество аксиом и правил, задающих отношения между объектами.

Вычисление логической программы — вывод следствий из программы.

Логика языка ограничена хорновскими дизъюнктами и снабжена резолюцией как единственным правилом вывода.

 

46. Применение логики предикатов в логико-математической практике.

1. Запись на языке логики предикатов различных математических предложений.

2. Применение ЛП к логико-математической практике — построение доказательств различных теорем, основанное на теории логического следования.

3. Приложение логики предикатов к теории множеств, к анализу Аристотелевой силлогистики.

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

· Необходимо осмыслить предложение.

· Отчетливо выделить в нем посылки и следствие (если это теорема).

· Очерчивать более широкий круг понятий и четко выделять ограничивающее условие (если это определение).


47, 48, 49

47. Классификация высказываний по Аристотелю.

Содержание любого простого высказывания («категорического суждения») может быть сведено к утверждению о наличии или отсутствии у предметов определенных свойств. Утверждения могут относиться как к отдельным предметам, так и к классам предметов; быть утвердительными и отрицательным.

Шесть типов простых высказываний

· единичноутвердительные единичноотрицательные

· общеутвердительные общеотрицательные

· частноутвердительные частноотрицательные

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

· A — общеутвердительные

· E — общеотрицательные

· I — частноутвердительные

· O — частноотрицательные

48. Методы рассуждений. Аристотелева силлогистика. Теоретико-множественная интерпретация аристотелевой силлогистики

Аристотель выделил важнейший тип дедуктивных умозаключений — силлогизмы.

Аристотелев силлогизм — схема логического вывода, состоящая из 3 простых высказываний 1 из 4-х указанных видов A, E, I, O: 2 первых — посылки, 3 — заключение.

Структура умозаключения. В них рассматриваются 3 свойства (термины): , , . Первая посылка (большая) — простое высказывание, связывающее и . Вторая посылка (малая) связывает и . Следствие связывает и , причем в следствии выступает в качестве субъекта, а — в качестве предиката. В зависимости от расположения может быть 4 вида фигуры силлогизмов.

49. Принцип полной дизъюнкции в предикатной форме

Теорема об обратимости импликаций

Пусть справедливо следующее (m ³ 2):

("x)(P1(x) ® Q1(x)), ("x)(P2(x) ® Q2(x)), ... , ("x)(Pm(x) ® Qm(x)).

Причем для посылок известно, что истинно утверждение ("x)(P1(x) Ú P2(x) Ú ... Ú Pm(x)), а следствия попарно исключают друг друга, т.е. истинны все высказывания Ø($x)(Qi(x) Ù Qj(x)) (i, j=1,…, m, i ¹ j).

Тогда справедливы и обратные импликации:

("x)(Q1(x) ® P1 (x)), ("x)(Q2(x) ® P2(x)), ... , ("x)(Qm(x) ® Pm(x)).

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

Теорема.

Пусть справедливо следующее:

("x)(P(x) ® Q1(x)), ("x)(ØP(x) ® Q2(x)), причем следствия Q1(x) и Q2(x) исключают друг друга, т.е. истинно высказывание Ø($x)(Q1(x) Ù Q2(x)).

Тогда справедливы обратные теоремы:

("x)(Q1(x) ® P(x)), ("x)(Q2(x) ® ØP(x)).


50, 51, 52

50. Метод (полной) математической индукции.

Специальный метод, применяемый для доказательства истинности утверждений типа ("x Î N)(P(x)), т.е. ("x) (x Î N ® P(x)). Такие утверждения выражают тот факт, что некоторое свойство P присуще каждому натуральному числу.

Формальная основа — аксиома индукции, выражающая свойства естественного отношения порядка, имеющегося на множестве всех натуральных чисел.

Если свойством P обладает число 1 и для всякого натурального числа из того, что оно обладает этим свойством, следует, что и непосредственно следующее за ним натуральное число также обладает им, то и всякое натуральное число обладает свойством P.

Символически: (P(1) Ù ("x) (P(x) ® P(x+1))) ®("y)(P(y)).

Логическая схема доказательства методом математической индукции:

(1) P(1) — устанавливается проверкой; (2) ("x) (P(x) ® P(x+1)) — доказывается;

(3) P(1) Ù ("x) (P(x) ® P(x+1)) — из (1) и (2) по правилу введения конъюнкции;

(4) (P(1) Ù ("x)(P(x) ® P(x+1))) ®("y)(P(y)) — аксиома индукции; (5) ("y)(P(y)) — из (3) и (4) по МР.

P(1) — основание индукции;

предположение об истинности P(x) — предположение индукции;

доказательство истинности P(x+1) — шаг индукции.

51. Необходимые и достаточные условия

Пусть некоторая теорема имеет вид

("x) (P(x) ® Q(x)). Это означает, что предикат P(x) ® Q(x) тождественно истинен, т.е. его множество истинности (P® Q)+ = U =(Ø P)+ È Q+ . Следовательно, P+ Í Q+, а значит предикат Q(x) является следствием предиката P(x).

("x) (P(x) ® Q(x)) означает, что условие P(x) является достаточным для Q(x), а Q(x) — необходимым для P(x).

52. Понятия формальной системы и формального вывода. Аксиоматическая (формальная) теория и принципы ее построения.

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

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

Формальная теория состоит из:

1. Множества знаков, образующих алфавит языка теории.

2. Множества слов, составленных из знаков алфавита, называемых формулами.

3. Подмножества формул всего множества формул, называемых аксиомами.

4. Множества правил вывода, с помощью которых из формул получают другие формулы.

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


53, 54

53. Вывод и выводимость в формальной теории. Разрешимые и неразрешимые формулы. Доказательство и доказуемость. Теорема формальной теории.

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

Формальная теория состоит из:

1. Множества знаков, образующих алфавит языка теории.

2. Множества слов, составленных из знаков алфавита, называемых формулами.

3. Подмножества формул всего множества формул, называемых аксиомами.

4. Множества правил вывода, с помощью которых из формул получают другие формулы.

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

Пусть — формулы теории. Если существует такое правило вывода , что ( ) принадлежит , то говорят, что непосредственно выводима из по правилу вывода . ( — посылки, — заключение).

Выводом формулы из формул в формальной теории называется такая последовательность формул , что , а любая другая либо является аксиомой, либо исходной формулой, либо непосредственно выводима из ранее полученных формул. Если выводима из в теории , то — гипотезы. Теорема (доказуемая формула?) — формула, выводимая только из аксиом, без гипотез.

Формальное доказательство формулы в теории — конечная последовательность формул

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

Последняя формула в доказательстве называется теоремой. Используется символическая запись для теорем:

( читается как «доказуемо » или « теорема». Знак введен в 1879 г. немецким логиком Готлобом Фреге).

Формальная теория разрешима, если существует алгоритм, который для любой формулы теории определяет, является лм эта формула теоремой теории.

54. Основные свойства формальных систем: непротиворечивость, полнота, разрешимость. Полнота и непротиворечивость исчисления высказываний. Полнота и непротиворечивость исчисления предикатов.

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

Теория, в которой множество теорем покрывает всё множество формул (все формулы являются теоремами, «истинными высказываниями»), называется противоречивой. В противном случае теория называется непротиворечивой.

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

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

Исчисление высказываний (ИВ) – формальная теория.

ИВ называется непротиворечивым, если не все формулы в нем доказуемы.

Множество формул Ф называется полным, если можно доказать либо Ф├ В, либо Ф├ В.

А что такое полнота исчисления предикатов? Это утверждение о том, что любая общезначимая формула выводима в исчислении предикатов, то есть . То есть вывести можно всё, что истинно всегда и везде.

Или сильная форма утверждения о полноте исчисления предикатов (когда добавляются аксиомы теории). .

Непротиворечивость - ни одна формула не может быть выведена одновременно со своим отрицанием.


55, 56

55. Прикладные исчисления предикатов. Формальная арифметика. Теорема Генцена о непротиворечивости формальной арифметики.

Формальная арифметика – эгалитарное прикладное исчисление, в котором дополнительно имеются:

· предметная константа 0

· двуместные операции + и * и одноместная операция ‘.

· знак равенства =

· нелогические аксиомы равенства и следующие нелогические аксиомы арифметики:

где А – любая формула, а t, t1, t2 – любые термы (переменные для объектов).

Теорема Генцена: непротиворечивость формальной арифметики доказывается в более широкой формальной теории, содержащей арифметику и принцип трансфинитной индукции.

56. Теоремы о неполноте формальных систем, смысл и значение теорем Геделя для практической информатики.

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

2. Для любой формально рекурсивно перечислимой (то есть эффективно генерируемой) теории <math>T</math>, включая базовые арифметические истинностные высказывания и определённые высказывания о формальной доказуемости, данная теория <math>T</math> включает в себя утверждение о своей непротиворечивости тогда и только тогда, когда теория <math>T</math> противоречива.

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

Теорема Гёделя имеет другую интерпретацию в рамках информатики. В логике первого порядка теоремы вычисляются перечислимым способом — можно создать программу, которая сгенерирует валидное доказательство для любого высказывания. Можно спросить, является ли строгим свойство рекурсивности? Т. е. можно ли написать программу, которая для произвольного утверждения скажет, истинно оно или ложно. Теорема Гёделя утверждает, что в общем случае такую программу написать невозможно.


57, 58, 59, 60, 61

57. Неклассические логики.

Неклассические логики — широкая область логических исследований, выходящая за пределы или, наоборот, сужающая область исследований классических логики высказываний и логики предикатов.

1. Интуиционистская логика — логика, для которой не выполняется один из основных законов классической логики: закон исключенного третьего, т.е. .

2. Нечеткая логика — в которой допускается непрерывное множество значений истинности высказываний, и применяются специальные логические операции (связки).

3. Модальная логика — логика, в которой есть модальности (модальные операторы) кроме стандартных логических связок, переменных и / или предикатов.

4. Временные логики — модальные логики. Они строятся добавлением к логике высказываний новых законов, отражающих свойства времени.

5. Алгоритмические логики — созданы для описания семантики языков программирования.

6. Многозначная логика — тип формальной логики, характерный наличием более 2 возможных значений.

58. Интуиционистская логика.

Интуиционистская логика — неклассическая логика, для которой не выполняется один из основных законов классической логики — закон исключенного третьего, т.е. .

Отказ от этого закона приводит к признанию существования «третьей возможности». Но в таком случае, естественно, приходим к запрету доказывать теоремы методом от противного. Последнее приводит к отказу от аксиомы: .

При доказательстве от противного предполагают, что верно на самом деле , и затем приходят к некоторому противоречию. Это показывает, что «не верно» А, т.е. «верно» . последнее позволяет утверждать, что «верно» А. Иначе говоря, имеем утверждение .

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

Нечеткая логика — неклассическая логика, в которой допускается непрерывное множество значений истинности высказываний, и применяются специальные логические операции (связки).

 







Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.