Конспект по матлогике

Оглавление

Логическая связка – операция над высказываниями или символ, обозначающий её Валентность – истинное значение или ложное

Валентность логических связок

| ¬( & ) ¬ ¬ – символ Шеффера

↓ ¬( ) ¬ & ¬ – стрелка Пирса

(¬ )

( ) & ( )

¬( )

Двузначная логика Поста

Многозначная логика

{1, … , } -значная логика N – абсолютная истина

1 – абсолютная ложь

¬ = − + 1

& = min( , )

= max( , )

2.Понятие пропозициональной формулы и кванторная

пропозициональной формулы

Пропозициональная переменная – идентификатор (является именем утверждения), принимающий значение «И» или «Л» Бинарная логическая связка: &, , , , |, ↓

Сигнатура – набор операций, принятых в данной системе аксиом (< 1, … , >)

Пропозициональная формула:

1)Логическая константа («И», «Л»)

2)Пропозициональная переменная

2

3)¬ , где – пропозициональная формула

4)( )1, где , – пропозициональные формулы, – бинарная логическая связка

Кванторная пропозициональная формула (QBF):

1)Логическая константа («И», «Л»)

2)Пропозициональная переменная

3)¬ , где – пропозициональная формула

4)( ), где , – кванторные пропозициональные формулы, – бинарная логическая связка

5), , где – кванторная пропозициональная формула, – пропозициональная переменная, « » и « »– кванторы (других кванторов быть не может)

Постоянная пропозициональная формула – пропозициональная формула, не содержащая пропозициональных переменных

Параметрической пропозициональная формула – пропозициональная формула, содержащая пропозициональных переменных

3. Теорема о представлении булевой функции через 3 логических связки

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

Любая пропозициональная формула определяет булеву функцию:– пропозициональная формула1, … , – различные пропозициональные переменные

1, … , – булева функция « » (λ-исчисление)

( 1, … , ) = [ ] 11,…,,…, ( – n-местная подстановка)

Теорема Любую булеву функцию можно выразить через 3 логических связки: < ¬, &, >

□

В семантической таблице функции ( 1, … , ) ищем все строки, в которых результат функции «И» и для каждой из них выписываем формулу вида ( 1 1)& … &( ) , где 1, … , – последовательность логических констант в рассматриваемой строке. Затем объединяем эти формулы ( ) многократными дизъюнкциями 1 … . В итоге 1 … ( 1, … , )

■

4. Теорема о представлении булевой функции через 2 логические связки

Законы де Моргана: ¬( & ) ¬ ¬ и ¬( ) ¬ & ¬

Теорема Любую булеву функцию можно выразить через 2 логических связки: < ¬, > или < ¬, & >

□

1 Это минимальное количество скобок для сохранения однозначности. Дополнительные скобки будут лишними, а в случае, если отпустить эти, то из-за приоритета логических связок выражение потеряет первоначальный смысл. Например, конъюнкция выражений и будет & и не совпадает с ( )&( )

3

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

В секвенциальном исчислении высказываний допустимыми являются: 1) Обратные правила

Переход: предположим правило (&̅ →) допустимо на не более чем − 1-ом применении правила. Докажем, что тогда оно допустимо и на -ом тоже

a)Если по (& →), то убираем из вывода , , так как получено из = где <

b)Если по другому правилу, то в посылках этой секвенции (и всех предыдущих) вместо & пишем и эти секвенции получаем по (&̅ →)

sl′ sl′′

si

sj

■

2) Правила сокращения повторений

6

3) Правила перестановки

4) Правила добавления

5) Правило сечения

Γ1Γ2→Δ1 2 Γ1 Γ2→Δ1 2

Γ1Γ2→Δ1 2

Все правила, допустимые в секвенциальном исчислении высказываний, кроме правил сокращения повторений, допустимы и в секвенциальном исчислении предикатов Для правил сечения все секвенции должны быть чистыми

Вывод – последовательность секвенции, каждая из которых либо аксиома, либо получается из предыдущих по одному из правил вывода Секвенция выводима, если она является последней секвенцией некоторого вывода

Вывод секвенции S – вывод с последней секвенцией, совпадающей с S Формула выводима, если выводима секвенция « → » Тавтология – формула, всегда являющаяся «И» Противоречие – формула, всегда являющаяся «Л»

Пропозициональная формула выполнима, если она когда-то истинна

Исчисление полно, если любая истинная формула выводима Исчисление непротиворечиво, если не существует формулы, которая выводима и её отрицание выводимо

Теорема Формульный образ аксиомы является тавтологией

□

■

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

секвенция – аксиома

□

Рассмотрим 1 … → 1 … – секвенция, не содержащая логических связок, формульный образ которой – тавтология Предположим, что это не аксиома , ≠ (не равны графически), но ¬ 1 … ¬ 1 …= И – тавтология

Предположим, что { 1, … , И Φ(… ) = Л?! все различными быть не могут аксиома

1, … , Л

■

Теорема Для любого правила вывода формульный образ заключения равносилен конъюнкции формульных

образов посылок

□

( )&( ¬ ) = &¬

■

Теорема

7

Секвенция выводима в секвенциальном исчислении высказываний её формульный образ – тавтология Теорема

Секвенциальное исчисление высказываний полно и непротиворечиво

9. Терм в сигнатуре. Свобода для подстановки терма вместо всех вхождений переменных

Предметная переменная – переменная, принимающая в качестве своего значения имена объектов

Терм в сигнатуре < 1, … , >:

1)Имя предметной константы

2)Предметная переменная

3)( 1, … , ), где 1, … , – термы, – имя n-местной функции

Различные формы записи функции:

Префиксная (cos( ))

Инфиксная ( + )

Постфиксная ( !)

Позиционная (юнкция)

Терм свободен для подстановки в формулу вместо свободных вхождений предметной переменной , если он не содержит предметных переменных, в области действия квантора по которым имеются свободные вхождения

Следствия из определения:

1)свободен для подстановки вместо в

2)Если не входит свободно в , то терм свободен для подстановки в вместо

3)Если терм не содержит переменных, имеющих связанные вождения в , то свободен для подстановки в вместо переменной

10.Атомарная формула. Бескванторная атомарная формула. Предикатная формула

Если 1, … , – термы, – имя n-местного предиката ( 1, … , ) – атомарная формула

Бескванторная предикатная формула:

1)Атомарная

2), – предикатные формулы, – бинарная логическая связка ¬ , ( ) – бескванторные предикатные формулы

Кванторная предикатная формула:

1)Бескванторная предикатная формула

2)– предикатная формула, – предметная переменная , – кванторные предикатные формулы

8

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

11.Семантическая обоснованность исчисления предикатов. Полнота пропозиционального секвенциального исчисления

Теорема (о семантической обоснованности)

Если секвенция выводима, то её логическая интерпретация равнозначна «И»

□

Индукция по длине вывода секвенции База: 1 секвенция – аксиома

Переход:

Если посылки равнозначны «И», то, по теореме из «Вопрос 8»2, вывод равнозначен «И» Например для (→ &):

Иначе И и И ( & ) И

■

Теорема (Поста о полноте исчислений высказываний)

Всякая секвенция, равнозначная «И», выводима вычислимыми секвенциями

□

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

Переход: есть логические связки и не аксиома, тогда секвенция получена по правилу вывода из 1 или

из 1 и 2.

В 1 и 2 меньше логических связок(потому что правила вывода в секвенциальном исчислении добавляют логические связки) и они выводимы (по индукционному предположению) их логическая интерпретация равнозначна «И» наша логическая интерпретация равнозначна «И» (по предыдущей теореме)

■

Теорема (о семантической обоснованности секвенциального исчисления предикатов)

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

12.Аксиомы равенства и согласованности с ними

Аксиомы равенства:

1)( = ) – рефлексивность

2)( = = ) – симметричность

3)( = & = = ) – транзитивность

Аксиомы согласованности с равенством:

1)( = ( ( , ) = ( , ))), где – функция

2)′ ′( = ′& = ′ ( ′ ′))

2 О том, что формульный образ заключения равносилен конъюнкции формульных образов посылок. В любом случае доказательство подразумевает под собой проверку корректности всех правил вывода

9

Теория первого порядка – теория с равенством, если в её сигнатуре имеется выделенный двуместный

( = )

предикат «=» и выводимы следующие формулы:{ ( = ( [ ] )) для любой формулы этой

теории При наличии вышеперечисленных аксиом эти условия выполняются

13.Аксиомы элементарной теории чисел

Сигнатура: < 0, , +, ,^, =>– инкремент, следующее число

0, (0), ( (0)), ( ( (0))) , … – натуральные числа

Аксиомы Пеано:

1)(( + 0) = )

2)(( + ( )) = ( + ))

3)(( 0) = 0)

4)(( ( )) = + )

5)(( ^0) = (0))

6)(( ^ ( )) = ( ^ ) )

7)¬( ( ) = 0)

8)( ( ) = ( ) = )

9)(0) & ( ( ) ( ( ))) ( )

14.Первая теорема Гёделя о неполноте арифметики

Замкнутая формула – формула, не содержащая свободные вхождения переменных

Теорема Если формальная арифметика непротиворечива, то в ней можно указать замкнутую формулу , такую

что невыводима и ¬ невыводима в формальной арифметике

□

– цепочка знаков " " – её номер в -ичной система счисления при достаточно большом , Гёделева нумерация

"{ }" = для − числа {}: {{" "} = для − строки

Предположим – формула с 1 свободной переменной

Построим формулу с 1 свободной переменной такую, что ¬ (" ") (" ")

и (" ") ¬ (" ")

– формула выводима– – номер вывода

(" ") ( (" ") ( ≤ & ¬ (" "))) где = {" "}

Проверка :

1)¬ (" ") ¬ (" ") так как непротиворечива (" ") = И

2)(" ") ¬ ¬ (" ") (" ") = Л

Теперь (" ") ¬ (" ") не может быть чтобы обе были выводимы обе невыводимы

■

15.Вторая теорема Гёделя о неполноте арифметики (формулировка)

¬( (0 = 1)) – consis

Теорема

Если consis выводима, то арифметика противоречива

10