Общезначимые правила

| | 0 Comment

Введение в математическую логику

Лектор: Мати Рейнович Пентус
2005/2006

  • Программа экзамена (HTML, PostScript, pdf)
  • Предварительный вариант конспекта лекций (PostScript, pdf)
  • Список вспомогательной литературы для подготовки к экзамену
  • Литература
    • Рекомендуемая литература
    • Конспекты из Интернета
    • Дополнительная литература
  • Программа экзамена

    Логика высказываний

    Алфавит, буква, слово в алфавите. Высказывания и высказывательные формы. Логические операции. Формулы логики высказываний. Соглашения о скобках. Подформулы в логике высказываний. Истинностное значение формулы при данной оценке пропозициональных переменных. Таблица истинности формулы. Тавтологии, выполнимые формулы, тождественно ложные формулы, их взаимосвязь. Эквивалентность (равносильность) формул логики высказываний. Законы логики высказываний в форме равносильностей. Теорема о подстановке в логике высказываний. Теорема об эквивалентной замене в логике высказываний. Логическое следование в логике высказываний.

    Приведение формул логики высказываний к нормальным формам (ДНФ, КНФ, СДНФ, СКНФ). Выражение одних логических операций через другие. Штрих Шеффера, стрелка Пирса. Полные системы булевых функций.

    Логика предикатов

    Предикаты. Язык первого порядка: сигнатура, алфавит, термы, атомарные формулы, формулы, подформулы. Примеры: язык теории множеств, язык теории групп. Свободные и связанные вхождения индивидных переменных. Свободные индивидные переменные формулы. Замкнутые термы. Замкнутые формулы. Подстановка терма вместо переменной. Интерпретация сигнатуры. Истинность замкнутой формулы в данной интерпретации. Предикаты, выразимые в данной интерпретации.

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

    Предварённые формулы. Приведение формул к предварённой форме.

    Понятие изоморфизма интерпретаций. Лемма о значениях терма в изоморфных интерпретациях. Лемма о значениях формулы в изоморфных интерпретациях. Доказательство невыразимости предиката с помощью автоморфизмов. Невыразимость сложения целых чисел в сигнатуре упорядоченного множества.

    Модель множества замкнутых формул. Логическое следование в логике первого порядка. Теория первого порядка, её аксиомы и теоремы. Понятие совместной теории. Пример совместной теории, пример несовместной теории. Элементарная теория данной интерпретации. Понятие полной теории. Теории первого порядка с равенством. Примеры: теория полугрупп, теория групп, теория частично упорядоченных множеств, теория линейно упорядоченных множеств. Нормальные модели. Построение для каждого натурального k формулы, для которой произвольное множество тогда и только тогда является носителем какой-нибудь её нормальной модели, когда оно имеет мощность не более k (не менее k; ровно k).

    Исчисление высказываний

    Аксиомы и правила классического исчисления высказываний. Выводимые формулы. Вывод из гипотез. Вывод формулы A->A в классическом исчислении высказываний. Теорема о корректности классического исчисления высказываний. Теорема о дедукции для классического исчисления высказываний. Свойства выводимости из гипотез. Теорема о полноте классического исчисления высказываний.

    Исчисление предикатов

    Аксиомы и правила классического исчисления предикатов. Выводимые формулы. Вывод из замкнутых гипотез. Общезначимость аксиом классического исчисления предикатов. Теорема о корректности классического исчисления предикатов. Обобщённая теорема о корректности классического исчисления предикатов. Теорема о дедукции для классического исчисления предикатов.

    Теорема Гёделя о полноте классического исчисления предикатов (без доказательства). Теорема компактности для логики предикатов. Локальная теорема Мальцева. Теорема о существовании нормальной модели совместной теории первого порядка. Неразличимость конечного и бесконечного.

    Теория алгоритмов и арифметика

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

    Разрешимые множества. Свойства объединения, пересечения и дополнения разрешимых множеств. Сигнализирующее множество алгоритма. Полухарактеристическая функция. Полуразрешимые множества. Вычислимые последовательности. Перечислимые множества. Канторовская нумерующая функция для пар натуральных чисел. Нумерация кортежей фиксированной длины. Нумерация словарного пространства. Проекция множества. Пять эквивалентных определений перечислимого множества. Теорема Чёрча-Поста (критерий разрешимости). Свойства объединения и пересечения перечислимых множеств. Перечислимость области определения и области значений вычислимой функции. Теорема о графике вычислимой функции.

    Кодирование программ посредством слов в алфавите программ. Лямбда-обозначения. Существование универсальной машины Тьюринга. Универсальные функции. Построение вычислимой универсальной функции для класса всех вычислимых k -местных числовых функций. Пример вычислимой функции, не имеющей тотального вычислимого продолжения. Существование неразрешимого перечислимого множества.

    Главные универсальные функции. Главность вычислимой универсальной функции, построенной по нумерации машин Тьюринга. Задача распознавания свойств вычислимых функций по их программам. Теорема Райса.

    Плотные линейно упорядоченные множества без первого и последнего элемента

    Элиминация кванторов в элементарной теории стандартного линейного порядка на множестве рациональных чисел. Элементарная эквивалентность интерпретаций. Элементарная эквивалентность всех плотных линейно упорядоченных множеств без первого и последнего элемента.

    Понятие разрешимой теории. Разрешимо аксиоматизируемые теории. Теорема о полной разрешимо аксиоматизируемой теории. Разрешимость теории плотных линейно упорядоченных множеств без первого и последнего элемента.

    lpcs.math.msu.su

    Большая Энциклопедия Нефти и Газа

    Общезначимая формула

    Целью логики высказываний является описание класса всех общезначимых формул при данной интерпретации. Одним из способов такого описания является построение В. При этом в качестве аксиом выбираются нек-рые общезначимые формулы, а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы. Наиболее часто при построении В. [16]

    Целью логики предикатов является описание класса всех общезначимых формул . При этом в качестве аксиом выбираются нек-рые общезначимые формулы, а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы. [17]

    Этим доказано, что множество всех интуиционистски общезначимых формул содержит все интуиционистски доказуемые омлы. [18]

    Дизъюнкция всех конъюнкций ветвей дерева Т является общезначимой формулой . [19]

    В этом разделе мы докажем, что всякая общезначимая формула выводима в исчислении предикатов. [20]

    В логике предикатов первого порядка при построении замкнутой таблицы для общезначимой формулы допускается повторное использование 7-формул на одной и той же ветви. [21]

    Как и формулы исчисления высказываний, формулы исчисления предикатов делятся на три класса: общезначимые формулы , которые истинны при всех интерпретациях, невыполнимые, которые ложны при всех интерпретациях, и нейтральные ( или просто выполнимые), которые истинны только при некоторых интерпретациях. В противоположность тому, что имело место для исчисления высказываний, эти три класса не являются рекурсивными: не существует детерминированного алгоритма, который определял бы, к какому классу принадлежит произвольная формула исчисления предикатов. Вполне естественно, что формула исчисления предикатов выполнима, если она истинна хотя бы при одной интерпретации. [22]

    Формула логики высказываний ( предикатов), которая истинна во всех интерпретациях, называется общезначимой формулой . Аналогично формула логики высказываний ( предикатов), которая ложна во всех интерпретациях, называется противоречием. [23]

    Исчисление высказываний корректно, если любая выводимая формула оказывается общезначимой, и полно, если любая общезначимая формула выводима в этом исчислении. [24]

    С помощью понятия схемы модели для известной системы аксиом и правил вывода в логике ветвящегося времени сформулирован эффективный алгоритм построения вывода общезначимых формул из аксиом. [25]

    Утверждается, что если А — любая формула, полученная заменой метапеременных на их значения в любой из схем аксиом А1 — А8, то / i ( A) будет общезначимой формулой . Для этого достаточно убедиться, что для любой пз этих схем / г ( А) так же получается из данной схемы, как и А. [26]

    По теореме 2.1 это эквивалентно тому, что ( ( Я — Ч — QV ( R / S))) / P / — S) — — Q — общезначимая формула . [27]

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

    ОБЩЕЗНАЧИМОСТЬ — свойство логической формулы, состоящее в том, что эта формула истинна при любой интерпретации входящих в нее нелогич. Всякая общезначимая формула выражает логический закон. Из Геделя теоремы о полноте следует, что все общезначимые предикатные формулы и только они выводимы в классич. [29]

    Целью логики предикатов является описание класса всех общезначимых формул. При этом в качестве аксиом выбираются нек-рые общезначимые формулы , а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы. [30]

    www.ngpedia.ru

    Общезначимые правила

    Теорема: φ(A1,…,An) – тождественно истинной формула ИВ, φ1,…,φn – формулы ИП в степени Σ.

    Теорема: М,Д – алгебраические системы сигнатуры Σ, φ: М→Д, то для любой формулы φ(х1,…,хn) сигнатуры Σ и любых a1,…,аn є А М|=φ( a1,…,аn) Д|= φ (f(a1),…,f(аn))

    Г – множество формул сигнатуры Σ.

    Х – множество свободных переменных из Г

    Г называется выполнимым, если существует Ш= , x є X |→ax єM, так что Ш|=Г.

    При этом Ш называется моделью для множества Г.

    xy ((x≤y ^ ¬ x≈y) → z (x≤z ^ z≤y ^ ¬ x≈z ^ ¬ z≈y))

    Г ‘ имеет лишь бесконечные модели

    Г называется локально выполнимым, если люб. кон. F0 ≤ Г выполнимо.

    Теорема Мальцева: Любое локально выполнимое множество формулы выполнимо.

    Следствие: Если для любого n є N из множества Г имеет модель мощности ≥ k, то Г имеет бесконечную модель.

    Зафиксируем некоторую произвольную сигнатуру  и опр-им исчисление предикатов сигнатуры ( ИП  ). Аксиомами ИП  явл. следующие секвенции:

    1. φ ├ φ, φ-формула ИП 

    2. ├ x ≈ x, x –переменная

    3. x ≈ y, (φ) Z X├(φ) Z Y, x,y,z-переменные, φ-формула ИП  , удовлетворяющего условию на запись (φ) Z x и (φ) Z Y

    Правила вывода ИП  таковы:

    1.; 2. ; 3. ; 4. ; 5.

    6. ; 7. ; 8. ; 9.

    10. ;11. ;12. ;

    13. , где x не входит в члены Г свободно; 14. ; 15.

    16. , где х не входит в и члены Г свободно.

    Следующие секвенции доказуемы:

    1. ├ x1,…,xn φ

    2.x1, … , xn ψ├ (ψ)x1,…, xn

    Теорема о дедукции. Если Г U <φ,ψ>– мн-во формул ИП  , то из Г,φ-|ψ следует Г-| φ→ψ.

    Теорема Гёделя о полноте. Формула φ исчисления ИП  доказуема тогда и толь тогда, когда φ тождественно истинна.

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

    S=(├ ¬x ≈ x)(тождественно ложная формула)

    => ╞S => по т. о полноте S недоказуемо => ИП  непротиворечиво.

    Теорема о существовании модели. Для любого непротиворечивого мн-ва формул г сигнатуры 

    существует некоторая модель W╞ Г.

    Тождественно истинные формулы:

    Вопрос 10. Основные эквивалентности .

    эквивалентно в , если док-ма секв. |-и|- в .

    .

    , если для док-в секв. |-и|- использются правила 1)-12)

    В справедливы все эквивалентности ИВ:

    а)

    б)

    в) \

    г) > перем. х не входит свободн. в

    д) |

    е) /

    ж) \

    з) / >у не входит в свободн. и никакое вхождение х не находится под квантором или .

    Теорема о замене.

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

    Пренексные и клазуальные нормальные формы.

    Ф-ла называется безкванторной если не содержит кванторов. Бескванторная ф-ла находится в ДНФ (КНФ), если получается из ф-лы ИВ, находящейся в ДНФ (КНФ), заменой проп. перем. на фтомарные ф-лы сигн. .

    Ф-ла находится в пренексной (клазуальной) нормальной форме, если имеет след. вид:

    , где ;— бескванторная ф-ла находящаяся в ДНФ (КНФ).

    (ПНФ, КлНФ — пренексные и клазуальные нормальные формы).

    Для любой ф-лы сигн. существует эквиалентная ф-ла сигн. , находящаяся в ПНФ (К1НФ).

    Алгоритм приведения к НФ.

    удаление :

    использование з-на де Моргана, з-ны двойного отрицания и св-ва а), б) пред. предл.,

    Привести ф-лу Х к ПНФ.

    — ПНФ, КлНФ.

    studfiles.net

    Исчисление предикатов

    Выберем множество истинностных значений [math]V[/math] . Также, выберем некоторое предметное множество [math]D[/math] . n-местным предикатом мы назовем функцию из [math]D^n[/math] в [math]V[/math] . Как и раньше, мы ограничимся классическим множеством [math]V[/math] — истина и ложь, но оставляем потенциальную возможность его расширить.

    Предикаты могут быть 0-местными, в этом случае это хорошо нам известные пропозициональные переменные, принимающие какие-то истинностные значения, в происхождение которых мы не вникаем.

    Рассмотрим следующий известный пример: каждый человек смертен, Сократ — человек, следовательно, Сократ — смертен. Мы можем формализовать это выражение с помощью предикатов: множество [math]D[/math] — это будет множество всех существ, [math]S(x)[/math] — предикат «быть смертным», [math]H(x)[/math] — предикат «быть человеком». Тогда фраза в полу-формальном виде выглядит так: Для каждого [math]x[/math] , такого, что [math]H(x)[/math] верно [math]S(x)[/math] , поэтому поскольку [math]H[/math] (Сократ), значит, что имеет место [math]S[/math] (Сократ).

    Чтобы построить новое исчисление, нам требуется указать 3 компонента: язык, аксиомы и правила вывода.

    Язык [ править ]

    Добавим к языку исчисления высказываний новые конструкции с предикатами и получим язык исчисления предикатов. Вот расширенная грамматика:

    Добавились 3 новых сущности:

    (a) индивидные переменные — мы будем записывать их маленькими латинскими буквами из начала алфавита

    (b) предикаты (они обобщили пропозициональные переменные)

    (c) кванторы: всеобщности ( [math] \forall [/math] ) и существования ( [math] \exists [/math] ).

    neerc.ifmo.ru

    Тема. Исчисление высказываний


    Лекция 10. Общие принципы построения формальной теории. Интерпретация, общезначимость, противоречивость, логическое следствие


    Общие принципы построения формальной теории

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

    1. Определяется множество формул, или правильно построенных выражений, образующее язык теории.
    2. Выделяется подмножество формул, называемых аксиомами теории.
    3. Задаются правила вывода теории.

    Выводом формулы B из формул A1,…,An называется последовательность формул F1,…,Fm: Fm=B, а любая Fi есть либо аксиома, либо одна из формул A1,…,An , либо Fi непосредственно выводима из F1,…,Fi-1, по одному из правил вывода. Совокупность объектов, которые дают аксиомам содержательный смысл, называют интерпретацией данной системы аксиом. Аксиомы и правила вывода стараются выбирать таким образом, чтобы формальная теория имела содержательный смысл.
    В соответствии с этими общими принципами построено и исчисление высказываний.
    Определим высказывание как утвердительное предложение, которое может быть либо истинным (И) либо ложным (Л).

    Например, высказываниями являются следующие предложения:

    Снег – белый.
    Я – человек.

  • Алфавит исчисления высказываний есть объединение трех множеств AU< ù , Ù , Ú , ® >U , где
    A — множество пропозициональных переменных, т.е. переменных, значениями которых служат высказывания;
    < ù , Ù , Ú , ® >— множество логических связок;
    — множество вспомогательных знаков.
  • Формулы
  • 1) a , где a Î A – формула;
    2) если A и B — формулы, то ( ù A),(A Ú B),(A Ù B),(A ® B)- формулы.

    Поскольку значениями пропозициональных переменных являются высказывания, которые, в свою очередь, принимают значения либо И, либо Л, то и переменная также принимает два значения — И либо Л.

    Интерпретация, общезначимость, противоречивость, логическое следствие

    Определение. Интерпретацией формулы F называют приписывание значений И или Л входящим в нее переменным.

    Определение. Формула F истинна в некоторой интерпретации тогда и только тогда, когда она получает значение И в данной интерпретации.
    Проверка истинности формул является одной из основных задач исчисления высказываний. Эта задача может быть решена путем введения аксиом и правил вывода.
    Однако, введя аксиомы и правила вывода, можно заметить, что зависимость истинности формулы F исчисления высказываний от истинности, входящих в нее элементарных высказываний в точности соответствует зависимости значения логической функции, представляемой формулой F, от значений переменных этой функции. Иначе говоря, если задана формула F(a1,…,an) и задана ее интерпретация, то для выяснения истинности ее нужно вычислить как логическую функцию на наборе ( d 1,…, d n), где d i=1 , если ai и d i=0, если ai. Если F( d 1,…, d n)=1, то F=И, если F( d 1,…, d n)=0, то F=Л.
    Поэтому вводить аксиомы и правила вывода мы не будем, а воспользуемся изученным аппаратом логических функций.

    Определение. Формула F называется общезначимой тогда и только тогда, когда она истинна при всех интерпретациях (необщезначима в противном случае).

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

    — общезначима, непротиворечива

    — необщезначима,

    — противоречива, необщезначима.

    Определение. Пусть даны формулы F1,…,Fn и формула G. G есть логическое следствие формул F1,…,Fn и тогда и только тогда, когда для всякой интерпретации I, в которой F1 Ù … Ù Fn истинна, G также истинна. (F1,…,Fn называется посылками).

    Теорема 10.1. G есть логическое следствие F1,…,Fn тогда и только тогда, когда формула ((F1 Ù … Ù Fn) ® G) общезначима.
    Доказательство. Обозначим H= ((F1 Ù … Ù Fn) ® G).
    Необходимость. Пусть G — логическое следствие F1,…,Fn. Если Fi=И,, то , следовательно Н=И. Если некоторое Fi в интерпретации I, то F1 Ù … Ù Fn в этой интерпретации, следовательно при G= И или G=Л обязательно H=И, т.е. H – общезначима.
    Достаточность. Пусть H –общезначима. Тогда если F1 Ù … Ù Fn в интерпретации I, то G=И в этой интерпретации, т.е. G — логическое следствие.

    Теорема 10.2. G есть логическое следствие F1,…,Fn тогда и только тогда, когда формула (F1 Ù … Ù Fn Ù ( ù G)) противоречива.
    Доказательство Из теоремы 10.1. G -логическое следствие Û ((F1 Ù … Ù Fn) ® G) общезначима, т.е. — противоречива.Но

    Пример10.1.
    Если конгресс отказывается принять новые законы, то забастовка не будет окончена, кроме может быть случая, когда она длится более года и президент фирмы уйдет в отставку. Допустим, что конгресс отказывается действовать, забастовка оканчивается и президент фирмы не уходит. Длилась ли забастовка более года?
    Ответ на этот вопрос может быть дан с помощью исчисления высказываний.
    Обозначим элементарные высказывания через пропозициональные переменные:

    p: конгресс отказывается действовать;
    q: забастовка оканчивается;
    r: президент фирмы уходит в отставку;
    s: забастовка длится более года.

    Тогда рассматриваемое высказывание может быть записано на языке исчисления высказываний следующим образом:

    Используя теорему 10.2, получаем

    и, следовательно, заключение G является верным.

    web-local.rudn.ru

    Это интересно:

    • Как создать и оформить свой сайт Как создать свой сайт бесплатно Здравствуйте, уважаемый посетитель! Вы здесь, чтобы узнать, как сделать сайт самому, наполнить его посетителями, а может и заработать при этом денег? Тогда Вы оказались в нужном месте. Как сделать сайт самому бесплатно На вопрос "Как […]
    • Правила тега META - теги: описание и правила создания МЕТА - тег используется в пределах заголовка страницы и предназначен для того, чтобы включить любую полезную информацию, не определенную другими HTML тегами. Такая информация может быть извлечена серверами / клиентами для […]
    • Виды последствий преступления Виды последствий преступления Объективная сторона преступления – совокупность установленных уголовным законом признаков вне txt fb2 ePub html на телефон придет ссылка на файл выбранного формата Шпаргалки на телефон — незаменимая вещь при сдаче экзаменов, подготовке к […]
    • Договорное право учебно методическое пособие Учебно-методическое пособие по дисциплине «Договорное право» подготовлено в соответствии с требованиями Федерального Государственного образовательного стандарта по специальности «Юриспруденция». Пособие предназначено в помощь как студентам, так и преподавателям, […]
    • Оквэд услуга нотариуса ОКВЭД 2 – код 69.10 – Деятельность в области права Согласно расшифровке кодов ОКВЭД 2, указанной во введении к классификатору ОК 029-2014 (КДЕС ред 2), группа деятельности с кодом 69.10 входит в следующие группировки ● раздел M - ДЕЯТЕЛЬНОСТЬ ПРОФЕССИОНАЛЬНАЯ, НАУЧНАЯ И […]
    • Школа комфортного пребывания Частная общеобразовательная школа №5 Школа находится в экологически чистом районе на юго-западе столицы в благоустроенном, уютном здании. Показать на карте В распоряжении школы Спортивная площадка Детские игровые комплексы Круглосуточная охрана […]
    • Как оформить колыбельную Литературное чтение. Колыбельные песни как жанр устного народного творчества. 2-й класс Мы считаем, что разработка основ проектирования личностно-ориентированного урока важна как для устранения педагогических сложностей, связанных с реализацией самой классно-урочной […]
    • Рсв-1 только стаж Как заполнить уточненный РСВ-1 за периоды до 2017 года В строке 120 раздела 1 и разделе 4 приведите сумму перерасчета страховых взносов. Разделы 6 заполните по тем сотрудникам, по которым скорректировали сведения. В подразделе 6.1 в графах 1–3 укажите фамилию, имя и […]