Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика. Сборник задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ФОРМАЛЬНЫЕ ТЕОРИИ И ИСЧИСЛЕНИЯ

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

Теоретические сведения

Для определения формальной теории необходимо задать [21

Т = <Д, В, /?>,

где

  • • множество Д символов, образующих алфавит;
  • • множество слов /’в алфавите Д, которые называются формулами;
  • • подмножество В формул В е Р, которые называются аксиомами;
  • • множество Я отношений на множестве формул Я е ,Г'г+1, которые называются правилами вывода.

Алфавит может быть конечным или бесконечным.

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

Множества Д и /’по совокупности определяют язык формальной теории, или сигнатуру.

Множество аксиом может быть конечно или бесконечно. Бесконечное множество аксиом, как правило, задают в виде конечного множества схем и правил порождения из этих схем конкретных аксиом.

Множество правил вывода обычно конечно.

Для каждой формальной теории важнейшими понятиями являются следующие свойства:

  • • выводимость;
  • • интерпретация;
  • • общезначимость;
  • • разрешимость;
  • • непротиворечивость;
  • • полнота;
  • • независимость.

Выводимость. Пусть /], У^, ..., У7,,, б — формулы теории Г, т.е. , Р2, У7,,, СеР. Если существует такое правило вывода У?, что

7!, У^, /V,, б) є У?, то говорят, что формула б непосредственно

выводима из формул Рь Р2, ..., Рп по правилу вывода /?:

Рі Рі* ••••> Рп

где формулы У^, У^, Рп называются посылками, а формула С — заключением.

Вывод формулы б из формул Р, Р2, ..., Рп — это такая последовательность формул Р, У^, У7,, что Р„ = С, а любая формула — либо

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

Если в теории Р существует вывод формулы б из формул /], Р2, то записывают

Т7!, Р2, ..., Рп Ь б, где У7!, Р2, ..., Рп — гипотезы.

Теорема — формула, выводимая только из аксиом, без гипотез.

Интерпретацией формальной теории Т в область интерпретации М называется функция, которая каждой формуле ^теории Т однозначно сопоставляет некое содержательное высказывание относительно объектов множества М, И: Р —» М. Это высказывание может быть истинно или ложно или не иметь истинностного значения. Но если оно истинно, то говорят, что формула выполняется в данной интерпретации.

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

Те = <А, У7, В, У?>,

где

алфавит А:

а, Ь,Ь

пропозициональные переменные

» >

связки

(,)

служебные символы

формулы Р:

любая пропозициональная переменная есть формула

если/1, В — формулы, то (А), (А —> В) — формулы

аксиомы В:

А1 : (А —> (В —> А))

А2 : ((А -> (В -> С)) -> ((А —> —> (Э —> С)))

А3 : ((В А) ((В -4 А) -> В))

правило вывода R

правило заключения

^ iVlULUAb pUHVrlb

Приписывание значений 0 или 1 атомарным формулам, которые входят в состав сложных, называется интерпретацией.

Формализуя определение, мы говорим, что функция h называется интерпретацией, если для любых формул Ли В исчисления высказываний h удовлетворяет следующим условиям:

И(А) = Щ);

h(A -> В) = И(А) -> И(В).

Формула Л исчисления высказываний истинна при некоторой интерпретации h тогда и только тогда, когда h(A) = 1. В противном случае говорят, что А ложна при интерпретации h.

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

Например, формула а —> а является тавтологией, а —> а — противоречием.

Формула общезначима (тавтология), если она истинна в любой интерпретации.

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

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

Формула R доказуема тогда и только тогда, когда она является аксиомой либо получается из доказуемых формул А и А —> В путем применения правила заключения.

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

Правило подстановки является обобщением различных интерпретаций и расширяет набор правил вывода.

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

Пусть А — некая формула, выводимая (доказуемая) в исчислении высказываний, х — переменная, В — любая формула исчисления высказываний. Тогда формула, которая получается из формулы Л путем подстановки в нее вместо переменной х формулы В, выводима (доказуема):

Л(......х.....)(В // х).

Попробуем применить правило подстановки для доказательства следующей теоремы.

Теорема 4.2. Выводимость А —> А

Формула А —>А выводима в исчислении высказываний.

Теорема 4.3. Связь между исчислением высказываний и алгеброй высказываний

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

Из этой теоремы как следствия вытекает ряд утверждений.

  • 1. Каждая аксиома — тождественно истинная.
  • 2. Правило подстановки, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.
  • 3. Правило заключения, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.

Следующая терема очень полезна при доказательстве теорем, так как расширяет понятие выполнимости.

Теорема 4.4. Теорема дедукции

Если Г — множество формул исчисления высказываний, А и В — формулы из Г, и из А выводима В, А- В, то в исчислении высказываний выводима формула А —> /?, Г Ь А —> В.

Теорема 4.5. Транзитивность импликации

Из А —> В, В —> С Ь А—> С выводима в исчислении высказываний.

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

А & В = А —> В ',

А V В = А —>

(А = В) = (А В)&(В -> А);

А® В = (А -> В) -> А -> В.

Рассмотрим основные результаты исследования исчисления высказываний.

Разрешимость. Проблема разрешимости для исчисления высказываний разрешима.

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

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

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

Независимость. Система аксиом исчисления высказываний независима.

При исследовании формул на доказуемость применяют следующие методы проверки тождественной истинности.

  • 1. С помощью таблиц истинности, когда приходится вычислять значения формулы во всех интерпретациях.
  • 2. Алгебраический метод, который базируется на применении законов булевой алгебры. В этом случае мы упрощаем формулу до тех пор, пока она либо не станет равна 1, либо 0, либо мы не сведем к простой формуле (например, минимальной ДНФ), по которой видно, что это не тавтология.
  • 3. Метод Квайна. В этом случае разлагаем формулу Я по первой переменной, придавая значение 0 и 1, получая более простые формулы Я0 и Ях. Затем разлагаем их по второй переменной и т.д. Возможно, на каком-то шаге мы увидим тавтологию или противоречие. В общем случае метод Квайна менее трудоемок, чем использование таблиц истинности с их полным перебором возможных значений переменных.

Рассмотрим следующую формулу Я.

Алгебраический метод дает следующий результат:

Я = (А^В)^А^В = (Ач В) -э АВ =

= A& BvAvB=BvAvB = 1.

Метод Квайна дает следующее решение.

При А - О

Я = (А^В)^А^В = (0^В)^0^В =

= /ГТ0 -» Я = Я V Я = 1.

При А - 1

Л = (Л-»Я)->Л-»Я = (1->Я)-П->Я = = 1 —> 1 —> Я = 1 V Я = 1.

Во всех трех случаях наша формула является тавтологией.

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

Задачи

Задача 4.1. Найти значение формулы /? = (Л—>?)—>,4—>/? при интерпретации И(А) = И(В) = 1.

Решение.

Правильное решение можно получить двумя способами — непосредственной подстановкой либо через таблицу истинности.

Непосредственная подстановка дает следующий результат:

Я = (А^В)^А^В = ( I —» 1) —» 1 —» 1 =

= (0 —> 1) —> 1 -> 1 = 1 -> 1 —>1 = 1—>1 = 0—»1 = 1.

В нашем примере формула Я истинна при интерпретации И(А) = = И(В) = 1.

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

В задаче 4.1 таблица истинности показывает, что заданная формула Я является тавтологией (табл. 4.1).

Таблица 4.1

Таблица истинности для задачи 4.1

А

В

А В

В)А

В)А

-> В) -> А -> В

0

0

0

1

0

1

0

1

1

0

1

1

1

0

1

1

0

1

1

1

1

1

0

1

Задача 4.2. Исследовать, является ли формула Я : ((А —> А) —>

—> —> А)) противоречием.

Решение.

Построим таблицу истинности и проверим ложность формулы при всех интерпретациях (табл. 4.2).

Исследуемая формула Я при всех интерпретациях равна нулю, следовательно, она является противоречием.

Таблица истинности для задачи 4.2

А

-» /1)

М -> >4))

(Д -> Д) -> (Д А)

0

1

0

0

1

1

0

0

Задача 4.3. Даны следующие формулы. Определить, какие из них являются тавтологиями:

Я : (А (В А));

Д2 :(Д ->(Д А));

ЯЗ :(Л -> А);

Л4 : (й -»(Я -» А));

Я5:(А^(А^ А)).

Задача 4.4. Даны следующие формулы. Определить, какие из них являются тавтологиями:

Я :(А -»(?-» Д));

Я2 : ((В -» й) -» ((В -> А)В));

ЯЗ : ((5 -> А) ->((5 -> Д) -> 5));

/?4 : ((В ->А)-> ((В ^>А)^> В))

Я5 : ((В -> Д) -» ((5 -» й) -> 5)).

Задача 4.5. Даны следующие формулы. Определить, какие из них являются тавтологиями:

Я

((Л

—>

О)

—>

((И

—>

5)

—>

—>

С)));

Я2

«А

—»

С))

—>

((^4

5)

—>

С)));

ЯЗ

((А

—>

—>

С))

—>

((^

—>

5)

—>

—>

С)));

Я4

((А

—>

—>

С))

—>

((А

—>

5)

—>

—>

С)));

Я5

((А

—>

—>

О)

—>

((А

5)

—>

С))).

Задача 4.6. Даны следующие формулы. Определить, какие из них НЕ являются НИ противоречиями, НИ тавтологиями:

Я1: -> А));

Д2 : (Д (Д А));

ЯЗ : (А -> А);

Я4 : -»(ВА));

Я5 : -> -> А)).

Задача 4.7. Даны следующие формулы. Определить, какие из них НЕ являются НИ противоречиями, НИ тавтологиями:

Я :(А -»(?-» Д));

Я2 : ((ВА) -» ((5 -> Д) -» 5));

ЛЗ : ((5 -> Д) ->((5 -> А) -> 5));

Л4 : ((? -> Д) ->((5 -> А) -> 5));

Л5 : ((5 -» Д) -»((5 -» Д) -> 5)).

Задача 4.8. Даны следующие формулы. Определить, какие из них НЕ являются НИ противоречиями, НИ тавтологиями:

я

((А

->

О)

—»

((И

->

Л)

—>

->

С)));

Я2

((А

—>

—>

С))

—>

((й

—>

5)

—>

—>

С)));

ЯЗ

((А

—>

—»

С))

—>

((А

—>

5)

—>

—>

С)));

Я4

((А

—>

—>

С))

—>

((А

->

5)

—>

С)));

Я5

((А

—>

—>

О)

—>

((А

Л)

—>

О)).

Задача 4.9. Даны следующие формулы. Определить, какие из них являются противоречиями:

Я: ((А -»(ВА)) -> (Д -> Д));

Л2 : ((Д ->(Д -> Д)) -> Д -» Д);

ЛЗ : ((Д -> Д) ->(Д -> Д));

Л4 : (Д -» -» Д));

Л5 : (Д —> (Д —> Д)).

Задача 4.10. Даны следующие формулы. Определить, какие из них являются противоречиями:

я

(«А

О)

((>4

Л)

—>

С)))

—>

д

И);

Я2

Ш

—>

—>

С))

—>

((й

—>

5)

—>

—>

С)))

—>

д

—>

>4);

ЯЗ

(((А

—>

—>

С))

—>

((>4

—>

В)

—>

(/1

—>

С)))

—>

д

—>

А)',

Я4

(((А

->

—>

С))

(04

—>

В)

—>

С)))

д

А);

Я5

(((А

->

С))

((>4

—>

В)

—>

С)))

—»

д

А).

Задача 4.11. Какие три аксиомы формируют аксиоматику исчисления высказываний?

Л : —»(В -> А))-

Л2 ; ((А ^(В^ С)) -> ((Л -> В) -> (Л -> С)));

Л3 : ((* -> Л) -> ((Я -> Л) -> В))-

А2 : А © В = (А —> В) —> А —» В;

А:А&В = А^В-

А2 : А V i? = А —> В;

АЗ:(А = В) = (А ^ В) & (В ^ А).

 
<<   СОДЕРЖАНИЕ   >>