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

Синтаксическая непротиворечивость – нельзя доказать формулу вместе с ее отрицанием.

Доказать: ┐ ˚ E˚ ( |--A & ˚ |-- ┐ A)

Доказательство: методом сведения к абсурду

+1. E˚ ( |--A & ˚ |-- ┐ A)

2. |-- B & ˚ |-- ┐ B (из 1 по правилу исключения квантора существования)

3. |-- B (из 2 по правилу исключения & )

4. |-- ┐ B (из 2 по правилу исключения & )

5. V˚ A (|--A > ˚ |= A) ( метатеорема о семантической непротиворечивости)

6. |-- B > ˚ |= B (из 5 по правилу исключения квантора всеобщности)

7. |-- ┐ B > ˚ |= ┐ B (из 5 по правилу исключения квантора всеобщности)

8. |= B (из 6 и 3)

9. |= ┐ B (из 7 и 4)

10. ┐ B - тожд-лож

11. |=/= ┐ B

12. ┐ ˚ E˚ ( |--A & ˚ |-- ┐ A)

исключаются пункты с 1 по 11.

 

Свойство синтаксической полноты. Нельзя присоединить в качестве новой аксиомы недоказуемую в исчислении формулу

V˚ A (S |-/-A > ˚ E˚ B ( S+A |-- B & ˚ S+A |-- ┐ B)

Наличие этого свойства обусловлено тем, как строится исчисление: 1. С бесконечным числом аксиом и правилом вывода mp;

2) С конечным числом аксиом, правилом вывода mp и правилом подстановки.

Классическое исчисление высказываний будет максимальным, синтаксически полным, только при таком построении, когда есть конечное число аксиом и есть правило подстановки.

 

В качестве S рассматривается классическое исчисление высказываний с конечным числом аксиом, правилом mp и правилом подстановки

Доказательство:

+1. S |-/-A

2. |= A > ˚ S |--A (метатеорема о семантической полноте)

3. |=/= А (из 1 и 2, по правилу modus tolens)

4. Есть строчка в таблице, где формула принимает значение «ложь»

Если γ 1, γ 2, …γ n - пропозициональные переменные, входящие в состав формулы А, то существует набор значений этих переменных α 1, α 2, …α n, при котором формула А ложна.

5. Осуществляем подстановку в формулу А вместо переменных каких-то формул:

вместо γ i (итой переменной) будем подставлять или: γ i v ┐ γ i, если α i = и

или: γ i & ┐ γ i, если α i=л

В результате подстановки получаем формулу А*

6. Если формула А ложна на наборе α 1, α 2, …α n, то А* - тождественно-ложна (лемма)

7. А* - тожд-лож (из 6 и 4)

8. |= ┐ А* (из 7 в силу свойств отрицания)

9. S |-- ┐ А* (из 8, с использованием метатеоремы о семантической полноте)

10. S+A |-- ┐ А* (из 9)

11. S+A |-- A (т к А – аксиома)

12. S+A |-- А*

13. S+A |-- А* & ˚ S+A |-- ┐ А* (из 10 и 12)

14. Е˚ В (S+A |-- В & ˚ S+A |-- ┐ В) (из 13, правило введения Е˚ )

15. S |-/-A > ˚ E˚ B ( S+A |-- B & ˚ S+A |-- ┐ B) (из 14, правило введения > ˚ )

16. V˚ A (S |-/-A > ˚ E˚ B ( S+A |-- B & ˚ S+A |-- ┐ B) (из 15, введение V)

Исключить пункты с 1 по 14

 

 

Классическая логика предикатов: язык, интерпретация нелогических символов, понятие модели, правило приписывания значений термам

Очень богатая логическая теория. Классическая односортная логика предикатов первого порядка.

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

Если переменные только предметные – первый порядок (высший – если переменные не только предметы, но и свойства) Односортные логики предикатов – одна и та же область интерпретации - VxEyR(x, y). (Многосортные: каждой переменной разрешается свою область интерпретации, свою область значений сопоставить – Vx (S(x) > Ey(P(y) & R (x, y)).

Классические по принципам:

1. Двузначность. Каждая формула может принять ровно одно из двух значений – и или л.

2. Экстенсиональность. Значение сложного выражения зависит только от значения входящих в него частей.

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

 

Язык.

Алфавит: нелогические символы 3 типов:

- предметные константы a, b, c, d

- предикаторные константы Pⁿ, Qⁿ, Sⁿ

- предметно-функциональные константы fⁿ, gⁿ, hⁿ

Логические символы: пропозициональные связки &, v, >, ┐; +кванторы V, E.

Технические символы: (, ), ^,

Правила образования выражений.

Термы: 1. предметные константы

2. предметные переменные

3. сложные темы. Фⁿ (t1, t2, … tn)

Формулы: 1. Атомарные. Пⁿ (t1, t2, … tn)

2. Образованные с помощью связок &, v, >, ┐

3. Vα A, где А – формула, а α – предметная переменная

4. Eα A, где А – формула, а α – предметная переменная

 

Можно использовать только один квантор, выразив один через другой: Eα A ≡ Df ┐ Vα ┐ A

Vα A ≡ Df ┐ Eα ┐ A

Понятия:

1. Вхождение α в формулу А. VxP(x, y, x) – 3 вхождения переменной х

2. Область действия квантора. Vα A, Eα A – А – область действия квантора

3. Связанное вхождение. Вхождение называется связанным, если и только если это вхождение α непосредственно следует за квантором или находится в области действия квантора по переменной α.

Свободное вхождение. Вхождение называется свободным, если и только если это вхождение не следует за квантором и не находится в области действия никакого квантора по переменной α.

4. Переменная свободна в формуле А, если и только если существует свободное вхождение α в А.

Переменная связана в формуле А, если и только если существует связанное вхождение α в А.

Vx(EyP(x, y, z) v R(x, y, z) )

х- связанная

y- связанная и свободная

z- свободная

 

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

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

1. Замещаются все свободные вхождения α в А.

2. Ни одно из замещаемых вхождений не находится в формуле А в области действия какого-нибудь квантора по переменной входящей в терм t.

 

Замкнутый терм – не содержит переменных

Замкнутая формула – не содержит

 

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

1. Задать правила интерпретации нелогических символов.

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

3. Введение понятия закона

4. Определение основных логических отношений.

 

Процедуре интерпретации нелогических символов предшествует выбор предметной области. Это область интерпретации (универсум рассмотрения) U. Эта область должна быть непустой, т е содержать хотя бы один элемент. U – любое непустое множество. Интерпретация нелогических символов будет связываться (релятивизируются) с выбранным универсумом.

Группы нелогических символов: - константы (предметные, предикаторные, предметно-функциональные)

- предметные переменные (равны типу значений предметных констант)

Правила интерпретации нелогических символов. Интерпретация констант осуществляется с помощью интерпретационной функции (Семантическая функция). Знакам сопоставляет их значения. Приписывает значение константам языка.

Предметные константы – аналоги имен. Значение имени – отдельный предмет, взятый из U. Функция каждой предметной константе сопоставляет предмет, взятый из предметной области.

I (k) ( U

Предикаторные константы – аналоги предикаторов, которые в качестве значений имеют свойства или отношения. Если трактовать предикаторы экстенсионально, то значением предикатора будет некоторое множество (если предикатор одноместный, то в качестве значения можно рассматривать некоторое множество индивидов; если предикатор 2-хместный, значением будет множество каких-то пар)

I (Пⁿ) ( Uⁿ

Предметно-функциональные константы – аналоги предметных функторов. Значения – предметные функции (одноместные – отец; многоместные – множество картежей. I (Фⁿ) есть функция вида Uⁿ → U.

Выбрав U и I – задаем модель языка m = < U, I>, где U – произвольное непустое множество, а I – семантическая функция приписывающая значение константам языка. = Возможная реализация языка.

 

Предметные переменные. Функция φ предметным переменным сопоставляет объекты того же самого типа, что и сопоставляет константам.

φ (α ) ( U

Правила приписывания значений термам. Значения термов – некоторые элементы из универсума.

Три типа термов:

1. α – предметные переменные

2. k – предметные константы

3. Фⁿ (t1, t2, …tn) – сложные функциональные термы

Значение терма t в модели m при приписывании значений φ: |t|^m _φ (m можно не писать) тогда |t|_φ .

1. | α | _φ = φ (α )

2. | k | _φ = I (k)

3. |Фⁿ (t1, t2,...tn) |φ = [ I(Ф)] ( |t1| _{φ ,} |t2| _{φ , ....}|tn| _φ )

 

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

Правила приписывания значений формулам. Возможные значения формул – истина и ложь

Формулы: Приписывание значений:

 

1. Атомарные |Пⁿ (t1, t2,...tn)|φ = и ↔ < |t1| _φ, |t2| _{φ, ....}|tn| _φ > ( I (Пⁿ)

|Пⁿ (t1, t2,...tn)|φ = k ↔ < |t1| _φ, |t2| _{φ, ....}|tn| _φ > не ( I (Пⁿ)

 

2. ┐ А |┐ А|φ = и ↔ |А|φ = л

|┐ А|φ = л ↔ |А|φ = и

 

3. А & В |А & В|φ = и ↔ |А|φ = и & ˚ |В|φ =и

|А & В|φ = л ↔ |А|φ = л v˚ |В|φ =л

 

4. А v В |А v В|φ = и ↔ |А|φ = и v˚ |В|φ =и

|А vВ|φ = л ↔ |А|φ = л & ˚ |В|φ =л

 

5. А > В |А > В|φ = и ↔ |А|φ = л v˚ |В|φ =и

|А > В|φ = л ↔ |А|φ = и & ˚ |В|φ =л

 

6. V α А | V α А|φ = и ↔ V˚ ψ (ψ =_α φ > ˚ |A|ψ = и) (ψ =_α φ – приписывание ψ отличается от φ не более, чем значением α )

| V α А|φ = л ↔ Е˚ ψ (ψ =_α φ & ˚ |A|ψ = л)

 

7. Е α А | Е α А|φ = и ↔ Е˚ ψ (ψ =_α φ & ˚ |A|ψ = и)

| Е α А|φ = л ↔ V˚ ψ (ψ =_α φ > ˚ |A|ψ = л)

 

Закон (общезначимая формула) – это формула, принимающая значение истина во всех моделях и при любых приписываемых значениях предметным переменным

|= A ≡ _Df V˚ U V˚ I V˚ φ |A|φ = и (в модели < U, I> )

Формула А выполнима ≡ _Df Е˚ U Е˚ I Е˚ φ |A|φ = и (в модели < U, I> ). ≡ _Df Существует модель и приписывание значений предметным переменным при которых формула А истинна.

Формула А невыполнима ≡ _Df V˚ U V˚ I V˚ φ |A|φ = л (в модели < U, I> )

Формула А опровержима ≡ _Df Е˚ U Е˚ I Е˚ φ |A|φ = л (в модели < U, I> )

А значима (истинна) в модели < U, I> ≡ _Df V˚ φ |A|φ = и (в модели < U, I> )

А общезначима на множестве U (U общезначима) ≡ _Df V˚ I V˚ φ |A|φ = и (в модели < U, I> )

 

Логические отношения

Совместимость по истинности. Формулы из Г совместимы по истинности ≡ существует такая модель и такое приписывание значений переменным, при котором каждая формула из Г примет значение истина.

V˚ A (A ( Г > ˚ Е˚ U Е˚ I Е˚ φ |A|φ = и )

Совместимость по ложности V˚ A (A ( Г > ˚ Е˚ U Е˚ I Е˚ φ |A|φ = л)

Логическое следование. Для всякой модели и для веского приписывания значений переменным, при котором каждое значение из Г примет значение истина формула В тоже должна принять значение истина.

Г |= B ↔ V˚ U V˚ I V˚ φ (V˚ A (A ( Г > ˚ |A|φ = и ) > ˚ |В|φ = и)

 

123Следующая ⇒

Поделиться: