Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекции (Горбатова Ю. В.).docx
Скачиваний:
3
Добавлен:
01.05.2025
Размер:
356 Кб
Скачать
☆

Классическая логика предикатов (клп)

Язык КЛП:

  • Алфавит

    • a, b, c, d, a1 … - индивидуальные константы (имена собственные)

    • X, y, z, x1… - индивидуальные переменные (имена нарицательные)

    • f′, g′ - функторы

    • P1, Q1, R1, S1, R2 – предикаты

    • ˥, &, V, - пропозициональные связки

    • Ǝ, - кванторы

    • ), ( - технические символы

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

Пример: Аристотель – a отец Аристотеля - f′(a)

Предикаты – термины, выражающие в языке предметно-истинностные функции (свойства и отношения)

  • Определение правильно построенного терма:

    • Всякая индивидуальная константа – это ППТ

    • Всякая индивидуальная переменная – это ППТ

    • Если Фn – n-местный предметный фактор, а t₁, t₂, t₃, …, tn – правильно построенные термы, то Фn (t₁, t₂, t₃, …, tn) – это ППТ

    • Ничто иное не является ППТ

  • Определение правильно построенной формулы (ППФ)

    • Если П - n-местный предикат, а t₁, t₂, t₃, …, tn – это ППТ, тогда П n(t₁, t₂, t₃, …, tn) – ППФ

    • Если A – ППФ, то ˥A – ППФ

    • Если A и B – ППФ, то (A&B), (AVB), (A B) – ППФ

    • Если A и B – ППФ, α – индивидуальная переменная, то ƎαA, αA – ППФ

    • Ничто иное не является ППФ

Пример:

4 = a - f1(a) 5 = b 4+5 - g2(a, b) √ = f1 +5 - g2(f1(a), b) + = g2 (4+4)+(5+5) - g2(g2(a, a), g2(b, b))

В формулах вида αA и ƎαA формула A называется областью действия квантора по переменной α.

В произвольной формуле каждая индивидуальная переменная имеет некоторое число вхождений.

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

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

Терм называется замкнутым, если он не содержит в своем составе ликвидных переменных.

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

  1. Закон подчинения αA ƎαA

  2. Закон противоречия ˥ ( αA&˥ αA)

  3. Закон непустоты предметной области

  4. ƎαA V ˥ ƎαA

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

Дедуктивное рассуждение – рассуждение, в котором между высказываниями, принятыми в качестве исходных, и заключением сохраняются отношения логического следования.

Аналитические таблицы (ат)

Логические теории бывают разрешимыми (КЛВ) и неразрешимыми (КЛП).

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

Метод от противного: |=A допустим: ˥A

Особенности АТ

  1. Аналитическая таблица состоит из отмеченных формул (к которым добавили знак t или f)

  2. АТ двумерна – это дерево отмеченных формул. Цепь АТ – последовательность, без пропусков, вхождений отмеченных формул, начинающаяся с самой верхней формулы таблицы (кроме дерева) до 1 из самых нижних формул.

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

Правила редукции:

t (A&B)

f (A&B)

t A, t B

f A

f B

t (A V B)

f (A V B)

t A

t B

f A, f B

t (A B)

f (A B)

f A

t B

t A f B

t ˥A

f ˥A

f A

t A

t αA (α)

f αA (α)

t A (k)

где A (k) – результат замены всех свободных вхождений α в A на произвольной замкнутый терм k

f A (k)

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

t ƎαA (α)

f ƎαA (α)

t A (k)

f A (k)

Аналитическая таблица – конечное или бесконечное дерево отмеченных формул. Цепь называется замкнутой, если в ней встречается две отличные формулы tC и fC. АТ называют замкнутой, если каждая ее цепь является замкнутой.

Формула A является общезначимой (|=A) если и только если существует замкнутая аналитическая таблица, начальная цепь которой начинается с отмеченной формулы fA.

A₁, A₂, A₃, …, An |=B если и только если существует замкнутая аналитическая таблица, начальная цепь которой начинается с отмеченных формул tA₁,t A₂,t A₃, …,t An fB.

Натуральные исчисления. Исчисления высказываний.

Правила редукции (вывода):

  1. &в:

  2. Vв:

  3. в: (последняя посылка вывода)

  4. &и:

  5. Vи:

  6. ˥в:

  7. и:

  8. ˥и:

Вывод – это непустая конечная последовательность формул C₁, C₂, C₃, …, Cn, удовлетворяющая следующим условиям:

  1. Каждая Ci является либо посылкой, либо получена из предыдущей формулы по одному из правил вывода

  2. Если в выводе принимались правила B или ˥B, то все формулы, начиная с последней посылки вплоть до результата применения этого правила, считаются исключенными из вывода и не участвуют в дальнейшем построении вывода.

Доказательство – вывод из пустого множества не исключенных посылок.

  • B – введение импликации

˥B – введение отрицания

Силлогистика

Аристотель (384 - 322 до н. э.)

Силлогистика – это логическая теория, изучающая простые категорические атрибутивные высказывания (ПКАВ) и отношения между ними.

Состав ПКАВ:

  1. Квантор

  2. Термины:

    • S – субъект высказывания, логическая подлежащее, тот объект, о котором идет речь

    • P – предикат, логическое сказуемое, то, что говорится о субъекте, предицируется субъектом

  3. Связка (есть, является, суть, -)

Пример: Все мишки любят мед

предикат

являются

квантор

субъект

S

Виды высказываний

  1. По количеству:

    1. единичные – субъект которых указывает ровно на один предмет

    2. множественные – субъект которых указывает более чем на один предмет

      1. общие – субъект говорит обо всех элементах класса S

      2. частные – субъект говорит о некоторых (возможно, всех) элементах класса S

  2. По качеству:

    1. Утвердительные – перед связкой не стоит частица «не»

    2. Отрицательные – перед связкой стоит частица «не»

Affirmo - утверждаю

Nego – отрицаю

Отсюда обозначения (гласные буквы приведенных выше слов)

Общеутвердительные – все S являются P (a) общеотрицательные - все S не являются P (e) частноутвердительные - некоторые S являются P (i) частноотрицательные - некоторые S не являются P (o) единичноутвердительные – a является P единичноотрицательные – a не является P

На единичные букв не хватило. Ну и ладно, всё равно это частный случай общих.

Язык силлогистики

  • Алфавит

    • S, P, M, S₁ - термины

    • a, e, i, o – логические константы

    • ~ - терминное отрицание («не»)

    • ˥, &, V, - пропозициональные связки

    • ), ( - технические символы

  • Определение правильно построенного терма (ППТ)

    • Всякий термин является ППТ

    • Если α – ППТ, то ~α – ППТ

    • Ничто иное не является ППТ

  • Определение ППФ

    • Если α и β – это ППТ, то α a β, α i β, α e β, α o β – ППФ

    • Если A – ППФ, то ˥A – ППФ

    • Если A и B – ППФ, то (A&B), (AVB), (A B) – ППФ

    • Ничто иное не является ППФ