Числення висловлень: відмінності між версіями

[неперевірена версія][перевірена версія]
Вилучено вміст Додано вміст
Немає опису редагування
Основні проблеми числення висловлень
Мітки: перше редагування Візуальний редактор
Рядок 154:
Якщо для деякого задання істинності <math>I\;</math> формула <math>A\;</math> набуває значення 1, то кажуть, що формула <math>A\;</math> задовольняє задання <math>I\;</math>. Формула, що задовольняє усі можливі задання істинності (як формула <math>\neg (p \or q) \to (p \to r)</math> з прикладу) називається [[тавтологія|тавтологією]]. Якщо <math>\Sigma\;</math> — деяка [[множина]] формул то кажуть, що дана множина задовольняє задання істинності, якщо це задання задовольняє кожна формула цієї множини. Якщо для деякої формули <math>A\;</math> з того, що множина <math>\Sigma\;</math> задовольняє заданню істинності випливає що <math>A\;</math> задовольняє цьому заданню то формула <math>A\;</math> називається [[логічна імплікація|логічним наслідком]] множини <math>\Sigma\;</math>(позначається <math>\Sigma \vDash A</math>). У випадку якщо множина <math>\Sigma\;</math> є пустою, формула є тавтологією.
 
== Основні проблеми числення висловлень ==
== Повнота і несуперечливість ==
Для обгрунтування будь-якої аксіоматичної теорії необхідно розглянути наступні 4 проблеми:
Числення висловлень називається повним якщо будь-яка тавтологія є теоремою даного числення. Якщо зворотно будь-яка теорема числення висловлень є тавтологією то числення називається несуперечливим.
# Несуперечливості
# Повноти
# Незалежності
# Розв’язності
 
=== Проблема несуперечливості ===
В усіх наведених вище прикладах Числення висловлень є повними і несуперечливими.
'''''Означення:''''' Нехай задано деяку формальну аксіоматичну теорію. Говорять, що побудована модель цієї теорії, якщо всім символам алфавіту надано деякого конкретного змісту, який описує певну неформальну теорію і відношення між елементами цієї теорії.
 
Формальна аксіоматична теорія називається категоричною, якщо будь-які її 2 моделі ізоморфні між собою, тобто між ними можна встановити взаємно-однозначну відповідність.
 
Формальна аксіоматична теорія називається несуперечливою відносно своєї моделі, якщо будь-яка теорема, що доводиться в формальній теорії є істинним твердженням для моделі.
 
Формальна аксіоматична теорія числення висловлень називається внутрішньо несуперечливою, якщо в цій теорії не можна довести деяку теорему (формулу) разом з її запереченням.
 
Формальна аксіоматична теорія називається синтаксично несуперечливою якщо в ній існує хоча б якась формула, яка не являється теоремою.
 
'''''Теорема: '''''Формальна аксіоматична теорія числення висловлень є несуперечливою відносно своєї моделі алгебри висловлень.
 
'''''Наслідок: ''''' 
# Числення висловлень – внутрішньо-несуперечлива теорія.
# Числення висловлень – синтаксично-несуперечлива теорія.
'''''Теорема:''''' Формальна аксіоматична теорія числення висловлень є категоричною.
 
=== Проблема повноти ===
Формальна аксіоматична теорія числення висловлень називається вузькою у вузькому розумінні, якщо приєднання до системи аксіом цієї теорії хоча б однієї формули, яка не є теоремою веде до того, що теорія стає внутрішньо-суперечливою.
 
Формальна аксіоматична теорія числення висловлень є повною у широкому розумінні або повною відносно своєї моделі, якщо будь-яка формула істинна в моделі є теоремою в цій теорії, або якщо будь-яку тотожно істинну формулу можна довести.
 
'''''Теорема:''''' Формальна аксіоматична теорія числення висловлень є повною відносно своєї моделі алгебри висловлень.
 
'''''Теорема:''''' Числення висловлень – це формальна аксіоматична теорія, повна у вузькому розумінні.
 
=== Проблема незалежності ===
'''''Означення:''''' Нехай задано деяку формальну аксіоматичну теорію, говорять, що деяка аксіома цієї теорії є незалежною, якщо її не можна довести методами самої теорії, як теорему.
 
Система аксіом формальної аксіоматичної теорії називається незалежною системою аксіом, якщо всі аксіоми є незалежними.
 
'''''Теорема:''''' Система аксіом числення висловлень є незалежною.
 
'''''Доведення:''''' ''Для доведення незалежності деякої аксіоми числення висловлень використовують наступний підхід:'' будують таку модель формальної аксіоматичної теорії, в якій справджуються всі аксіоми окрім даної. Якщо доводиться, що така модель ізоморфна стандартній моделі формальної аксіоматичної теорії, то робиться висновок, що аксіома не є незалежною, якщо ж такого ізоморфізму немає – незалежна.
 
'''''Приклад:''''' В якості моделі формальної аксіоматичної теорії візьмемо
 
'''a∧b ≡ b, '''все інше не змінюємо, покажемо, що ІІ<sub>2</sub> і ІІ<sub>3</sub> справджуються, а ІІ<sub>1 </sub>ні.
 
ІІ<sub>2  </sub>a∧b → b
 
|- b → b
 
ІІ<sub>3  </sub>(a → b) → (( a→ c ) → ( a → b∧c ))
 
|-  ( a→ b ) → (( a → c ) → ( a → c))
 
ІІ<sub>1 </sub>a∧b → a
 
b → a
 
'''''Доведено'''''
 
=== Проблема розв’язності ===
Полягає в тому щоб довести існування алгоритму, який для будь-якої формули числення висловлень визначає чи можна її довести чи ні.
 
'''''Теорема:''''' Проблема розв`язності числення висловлень є розв`язною.
 
'''''Теорема 1:''''' Будь-яка тотожно істинна формула алгебри висловлень є теоремою числення висловлень.
 
'''''Доведення: '''''Нехай A - довільна формула числення числення висловлень. Побудуємо для неї таблицю істинності і розглянемо її останній стовпчик. Якщо він містить лише одиниці, то A - тотожно істинна формула і за теоремою 1 є теоремою числення висловлень. В іншому випадку (останній стовпчик таблиці істинності містить хоча б один нуль), A - не тавтологія і значить, A не є теоремою.
== Див. також ==
* [[Математична логіка]]