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

Начать. Это бесплатно
или регистрация c помощью Вашего email-адреса
Исчисление высказываний создатель Mind Map: Исчисление высказываний

1. Алфавит

1.1. Пропозициональные буквы

1.2. Логические знаки: ¬, ∧, ∨, ⊕, →, ↔

1.3. Скобки: "(", ")"

2. Таблицы истинности

2.1. Задача

2.1.1. установление истинностного значения формулы, если даны истинностные значения входящих в неё переменных

2.2. Понятие таблицы

2.2.1. Основные формулы

2.2.1.1. ¬X

2.2.1.2. X ∨ Y

2.2.1.3. X→Y

2.2.1.4. X ∧ Y

2.2.2. М:Vars → β, где β - множество всех истинных значений {0, 1}, Vars - множество переменных

3. Аксиомы

3.1. I-1: X→(Y→X)

3.2. I-2: (X→(Y→Z))→((X→Y)→(X→Z))

3.3. II-1: X∧Y →X

3.4. II-2: X∧Y→Y

3.5. II-3: X→(Y→(X∧Y))

3.6. III-1: X→(X∨Y)

3.7. III-2: Y→(X∨Y)

3.8. III-3: (X→Z)→((Y→Z)→((X∨Y)→Z))

3.9. IV-1: ¬X→(X→Y)

3.10. IV-2: (X→Y)→((X→¬Y)→¬X)

3.11. IV-3: X∨¬X

4. Правила вывода

4.1. Правило силлогизма

4.2. Правило контрапозиции

4.3. Правило сложного заключения

4.4. Правило снятия двойного отрицания

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

5. Тождественно истинные формулы (тавтологии)

5.1. Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных

5.1.1. законы де Моргана

5.1.1.1. ⊨¬(p∨q)↔(¬p∧q¬)

5.1.1.2. ⊨¬(p∧q)↔(¬p∨q¬)

5.1.2. закон контрапозиции

5.1.2.1. ⊨(p→q)↔(¬q→p¬)

5.1.3. законы поглощения

5.1.3.1. ⊨p∨(p∧q)↔p

5.1.3.2. ⊨p∧(p∨q)↔p

5.1.4. законы дистрибутивности

5.1.4.1. ⊨p∧(q∨r)↔(p∧q)∨(p∧r)

5.1.4.2. ⊨p∨(q∧r)↔(p∨q)∧(p∨r)

5.1.5. и другие

6. Вывод

6.1. Понятие вывода

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

6.1.1.1. Является одной из формул Н

6.1.1.2. Является доказуемой формулой

6.1.1.3. Получается по правилу заключения из двух предшествующих членов последвательности

6.2. Свойства вывода

6.2.1. Всякий начальный отрезок из совокупности Н есть вывод из Н

6.2.2. Всякий член вывода из Н является формулой, выводимой из Н

6.2.3. Если между двумя соседними членами вывода из Н записать некторый вывод из Н, то полученная последовательность формул будет выводом из Н

6.2.4. Для того чтобы формула В была выводима из Н необходимо и достаточно чтобы существовал вывод этой формулы из Н

6.2.5. Если совокупность формул Н является подмножеством W, то всякий вывод из Н является выводом из W

7. Формула

7.1. Относительно любой последовательности знаков алфавита языка логики высказываний можно решить, является она формулой или нет. Если эта последовательность может быть построена в соответствии со следующими тремя пунктами определения формулы, то она формула, если нет, то не формула

7.1.1. пропозициональная переменная (A, B и т.д.) есть формула

7.1.2. если A - произвольная формула, то ¬A тоже формула

7.1.3. если A и B - произвольные формулы, то (A∧B), (A∨B) и (A→B) — тоже формулы

7.2. Теория исчислений. Доказумая формула - это...

7.2.1. всякая аксиома

7.2.2. формула, полученная из доказуемой правилом подстановки

7.2.3. формула, полученная из доказуемых правилом заключения

8. Законы Логики

8.1. I: Закон перестановки посылок ⊨ (x→(y→z)) →(y→(x→z))

8.2. II: Закон соединения посылок ⊨ (x→(y→ z)) →(x∧y→z)

8.3. III: Закон разъединения посылок ⊨ ( x∧y→z) →(x→(y→z))

8.4. IV: ⊨ х→(¬x→y)

8.5. V: Закон исключенного третьего: ⊨ x∨¬x

9. Алгоритм задания

9.1. Задания конечного множества символов (Алфавит ФС)

9.2. Установление процедур построения формул

9.3. Установление множества аксиом

9.4. Установление конечного множества правил вывода

9.5. Решение аксиоматической проблемы

9.5.1. Проблема противоречивости

9.5.2. Проблема полноты

9.5.3. Проблема независимости аксиом

9.5.4. Проблема разрешимости