Шпаргалка по предмету "Математическая логика"

Узнать цену работы по вашей теме


Исчисление предикатов. Алгебра предикатов. Основные логические операции.

Пусть дан алфавитT = T1  T2  T3  T4  T5  T6  T7, гдеT1 = {x; y; z; …} – предметные переменные;T2 = {a; b; c; …} – предметные постоянные;T3 = {, &, , , } – лог. связки;T4 = {f1i; f2j; f3k; …} – функциональные символы;T5 = {P1i; P2j; P3k; …} – предикатные символы;T6 = {; } – кванторы;T7 = {;; (; )} – вспомогательные символы. Функциональные символы определяют функциональные отношения между предметными переменными и предметными постоянными и формируют термы по правилу: 1) всякая предметная переменная и предметная постоянная есть терм; 2) если fin – n-местный функциональный символ и t1, t2, … tn – термы, то fin(t1, t2, … tn) также есть терм; 3) никаких других термов нет. Предикатные символы, применённые к термам, порождают элементарные формулы по правилу: если Pin – предикатный символ и t1, t2, … tn – термы, то Pin(t1, t2, … tn) – элементарная формула. Обычные формулы исчисления предикатов определяются по правилу: 1) всякая элементарная формула есть формула, т. е. Fi = Pin(t1, t2, … tn); 2) если F1 и F2 – формулы, то (F 1); (F1 & F 2); (F1  F 2); (F1  F 2); (F1  F 2) также формулы; 3) если F – формула, а x – предметная переменная, то x(F) и x(F) также формулы; 4) никаких других формул нет. Всякая формула, содержащая только предметные постоянные, есть формула исчисления высказываний. Простейшими логическими операциями над предикатами являются отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция. Использование этих логических связок не определяет связывания предметных переменных. Отрицание (F(t1, t2, … tn)) – одноместная операция, посредством которой из данной формулы F(t1, t2, … tn) получают её отрицание. Конъюнкция (F1(t11, t12, … t1n) & F2(t21, t22, … t2n)) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F(t11, t12, … t1n, t21, t22, … t2n) = F1 & F2 с числом предметных переменных и постоянных, равным их объединению у исходных формул. Полученная формула имеет значение true т. и только т., когда обе исходные формулы F1 и F2 имеют значение true. Дизъюнкция (F1(t11, t12, … t1n)  F2(t21, t22, … t2n)) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F(t11, t12, … t1n, t21, t22, … t2n) = F1  F2 с числом предметных переменных и постоянных, равным их объединению у исходных формул. Полученная формула имеет значение true т. и только т., когда хотя бы одна из исходных формул имеет значение true. Импликация (F1(t11, t12, … t1n)  F2(t21, t22, … t2n)) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F(t11, t12, … t1n, t21, t22, … t2n) = F1  F2 с числом предметных переменных и постоянных, равным их объединению у исходных формул. Полученная формула имеет значение false т. и только т., когда F1 имеет значение true, а F2 – false. Эквиваленция (F1(t11, t12, … t1n)  F2(t21, t22, … t2n)) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F(t11, t12, … t1n, t21, t22, … t2n) = F1  F2 с числом предметных переменных и постоянных, равным их объединению у исходных формул. Полученная формула имеет значение true т. и только т., когда обе формулы F1 и F2 имеют одно и то же значение true или false. 1 3) Исчисление предикатов. Правила записи сложных суждений. Рассмотренные лог. операции при использовании термов, предикатов и кванторов позволяют формировать внутреннюю структуру предложения и формировать сложные суждения. см. вопрос 3)1) за квантором общности чаще всего следует лог. связка импликации, а за квантором существования – конъюнкции; 2) если формула содержит подформулу, то внутренняя формула не должна содержать кванторов, связывающих ту же переменную, что и квантор формулы; 3) предикат и функция должны иметь одно и то же количество аргументов всюду в формуле; 4) значения всех предметных переменных и постоянных должны принадлежать одной области определения предиката или функции; 5) если в одной формуле есть кванторы общности и существования, то при формализации суждений следует стремиться поставить квантор существования слева всей формулы. 1 4) Исчисление предикатов. Законы эквивалентных преобразований. Прежде всего в это множество входят все законы исчисления высказываний (см. вопрос 4), обеспечивающие преобразование формул при наличии кванторов общности и существования. Закон коммутативности справедлив только для одноимённых кванторов:xy(F2(x, y)) = yx(F2(x, y));xy(F2(x, y)) = yx(F2(x, y));но xy(F2(x, y)) ≠ yx(F2(x, y));xy(F2(x, y)) ≠ yx(F2(x, y));Перестановка разноимённых кванторов недопустима. Закон дистрибутивности существенно зависит от имени квантора и типа логической связки:x(F1(x)) & x(F2(x)) = x(F1(x) & F2(x));x(F1(x))  x(F2(x)) = x(F1(x)  F2(x));но x(F1(x))  x(F2(x)) ≠ x(F1(x)  F2(x));x(F1(x)) & x(F2(x)) ≠ x(F1(x) & F2(x));Закон де Моргана определяет двойственные преобразования формул при наличии кванторов:x(F(x)) = x(F(x))x(F(x)) = x(F(x))В алгебре предикатов, как и в алгебре высказываний, логические связки упорядочены по силе и первоочерёдности исполнения следующим порядком: ; &; ; ; . Вспомогательные символы в исчислении предикатов имеют то же значение, что в исчислении высказываний. Если формула алгебры предикатов F имеет вхождением подформулу Fi, т. е. F(t1; t2; … Fi; …), для которой существует эквивалентная её подформула Fj, т. е. Fi  Fj, то возможна подстановка в формулу F всюду подформулы Fj вместо формулы Fi без нарушения истинности формулы:F(t1; t2; … Fi; …) = F(t1; t2; … Fj; …)1 5) Исчисление предикатов. Пренексная нормальная форма (ПНФ) формулы. Для облегчения анализа сложных суждений оказывается удобным приведение формулы алгебры предикатов к нормальной форме. В алгебре предикатов необходимо предварительно отделить кванторы от логических формул, т. е. сформировать кванторную и безкванторную части формулы (ПНФ). В последующем бескванторную часть формулы можно преобразовать к КНФ или ДНФ формулы. Суть предварительного преобразования формулы к виду ПНФ состоит в том, что все кванторы формулы выносят влево, используя законы алгебры предикатов. В результате этих алгебраических преобразований может быть получена формула вида: F = >|x1>|x2…>|xn(M), где >|xi - кванторы существования или общности, т. е. >|  {; }, а M – безкванторная часть формулы. Часть формулы >|x1>|x2…>|xn называют префиксом ПНФ, а M – матрицей ПНФ. Алгоритм преобразования формулы к виду ПНФ: 1) Исключить всюду логические связки  и  по правилам эквивалентных преобразований. 2) Продвинуть отрицание до атомарной формы по закону де Моргана. 3) Переименовать связанные переменные по правилу: “найти самое левое вхождение предметной переменной такое, что это вхождение связано некоторым квантором, но существует ещё одно вхождение этой же переменной; затем сделать замену связанного вхождения на вхождение новой переменной”, операцию повторять пока возможна замена связанных переменных. 4) Вынести кванторы влево согласно закону дистрибутивности и по аксиомам лог. связки двух формул, одна из которых не содержит свободной переменной, связанной в другой формуле каким-либо квантором. 1 6) Исчисление предикатов. Сколемовская стандартная форма формулы. Наличие разноимённых кванторов усложняет анализ суждений. Поэтому можно рассмотреть более узкий класс формул, содержащий только кванторы общности, т. е. F = x1x2…xn(M)Для устранения кванторов существования разработан алгоритм Сколема, вводящий сколемовскую функцию для связи предметной переменной квантора существования с другими предметными переменными. Алгоритм Сколема: 1) представить формулу F в виде ПНФ; 2) найти наименьший индекс i квантора существования такой, что все предшествующие в префиксе кванторы есть кванторы общности:a) если i = 1, т. е. квантор xi находится на первом месте префикса, то вместо переменной, связанной квантором существования, подставить всюду предметную постоянную ai, отличную от встречающихся предметных постоянных в матрице формулы, а квантор существования вычеркнуть в префиксе;b) если i > 1, т. е. квантор xi находится не на первом месте префикса, а перед квантором существования стоит часть префикса, состоящая только из кванторов общности, то выбрать (i – 1)-местный функциональный символ, отличный от функциональных символов матрицы M и выполнить замену предметной переменной xi, связанной квантором существования на функцию f(x1; x2; … xn) и квантор существования вычеркнуть в префиксе;c) найти следующий индекс квантора существования и перейти к исполнению шага 2. Если таких индексов нет, то конец. Бескванторную часть формулы теперь можно преобразовать а виду КНФ или ДНФ. Чаще всего требуется выполнить преобразование к виду КНФ для логического вывода по принципу резолюции. Формулу, полученную в результате введения сколемовской функции и преобразованную в КНФ, т. е. F = x1x2…xn(D1 & D2 & …), называют сколемовской стандартной формой формулы. В этой формуле Di – дизъюнкты, xi – предметные переменные. Каждый член дизъюнкта называют литерой.


Не сдавайте скачаную работу преподавателю!
С помощью нашего сервиса Вы можете собрать свою коллекцию шпаргалок по нужному предмету, и распечатать готовые ответы в удобном для вырезания виде. Для этого начните собирать ответы, добавляя в "Мои шпаргалки".

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме:

Делаем шпаргалки правильно:
! Шпаргалки для экзаменов Какие бывают шпаргалки, как их лучше подготовить и что писать.
! Делаем правильную шпаргалку Что представляет собой удобная и практичная шпаргалка, как ее сделать.
! Как воспользоваться шпаргалкой В какой момент лучше достать шпаргалку, как ей воспользоваться и что необходимо учесть.

Читайте также:
Сдаем экзамены Что представляет собой экзамен, как он проходит.
Экзамен в виде тестирования Каким образом проходит тестирование, в чем заключается его суть.
Готовимся к экзаменам Как правильно настроиться, когда следует прекратить подготовку и чем заниматься в последние часы.
Боремся с волнением Как преодолеть волнение, как внушить себе уверенность.
Отвечаем на экзамене Как лучше отвечать и каким идти к преподавателю.
Не готов к экзамену Что делать если не успел как следует подготовиться.
Пересдача экзамена На какое время назначается пересдача, каким образом она проходит.
Микронаушники Что такое микронаушник или "Профессор .. ллопух ...".

Виды дипломных работ:
выпускная работа бакалавра Требование к выпускной работе бакалавра. Как правило сдается на 4 курсе института.
магистерская диссертация Требования к магистерским диссертациям. Как правило сдается на 5,6 курсе обучения.