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

Главная arrow Математика, химия, физика arrow Дискретная математика

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


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

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

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

Тв =<А, Т7, В, Я>,

где

алфавит А:

а, Ь,йу Ь|

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

_ 5 9 >

СВЯЗКИ

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

формулы Р:

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

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

аксиомы В:

А : —> (В —> А))

Л2 : ((А -> (В -» С)) -> ((А -> В)->(А -> С)))

4, : ((В ^>А)^> ((В А) В))

правило вывода /?:

МП////Г Л ПНР И с

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

^ ІУіиііиЬ ригІСг

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

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

И(А) = ЖА);

к(А -> В) = к(А) -> И(В).

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

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

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

Задача 4.1. Найти значение формулы Я = (А —> В) —> А —> В при интерпретации И(А) = И(В) = 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) —» А))

противоречием.

Решение.

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

Таблица 4.2

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

А

(А^А)

(А^А)

—> А) —> —> А)

0

1

0

0

1

1

0

0

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

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

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

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

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

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

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

А(......х......)(В//х).

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

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

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

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

1. Подставим в аксиому А2 вместо ВА-^А, вместо С подставим А: (.А((АА)А)) -> ((А(А -> А))(А -> А)).

Но(Д —> ((А —> А) —> А)) — это аксиома А1, и по правилу заключения получаем

(А->(А^ А)) ->(А^ А).

Но (А —> (А —> А)) — это аксиома А1, и по правилу заключения получаем (А —> А).

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

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

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

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

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

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

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

Используем теорему о дедукции при доказательстве теоремы.

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

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

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

  • 1. А —> В гипотеза.
  • 2. В —^ С — гипотеза.
  • 3. А тоже гипотеза.
  • 4. В выводимо по правилу заключения из 1 и 3.
  • 5. С выводимо по правилу заключения из 2 и 4.
  • 6. Следовательно, Д —> ?, >СДЬСипо теореме о дедукции

А —> В, В —> С Ь А —> С.

Мы доказали свойство транзитивности импликации.

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

А & В — А —> В:

А V В = А —> В

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

А © В = {А —> В) —> А —> В.

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

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

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

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

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

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

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

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

Продолжим рассмотрение нашей задачи 4.1.

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

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

= А&сВ/А/В = В/А/В = .

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

При А = О

Я = В)А —>В = (0—>В)—>0—>В =

= Я 0 В = В V В = .

При А = 1

Я = (Л -» Я) -» А -> В = (I -э В) -э 1 -> В =

= 1 1 В = ^ В = .

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

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

ла/

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

В частности, по Гильберту—Аккерману, исчисление высказываний обладает следующими компонентами.

алфавит А:

а, 6, , 6|

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

v, ”, (А —> В = А v В)

связки

(,)

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

формулы F.

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

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

аксиомы В:

А V А —> А

А —> А V В

А V В —> В V А

(В —> С) —> (А V В —> А V С)

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

/І, Л —> В

--Modus _ ponens

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

А согласно Россеру, исчисление высказываний можно задать следующим образом.

алфавит/1:

Q, b, Я і, Ь

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

(А —> В = (А & В))

связки

(,)

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

формулы F:

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

если А, В формулы, то (А), (А & В) формулы

аксиомы В:

А ^ А&А

А&В -> А

(А-> В) -> ((В & С) -> (С & А))

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

А, Л —> В

--Modus _ ponens

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

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