ГОУВПО

“Воронежская государственная технологическая академия”

Кафедра информационных технологий,

моделирования и управления

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

Методические указания к практическим занятиям

по дисциплине "Математическая логика

и теория алгоритмов"

Для бакалавров, обучающихся по направлению

230400 – "Информационные системы"

дневной и сокращенной формы обучения

Данные методические указания рассчитаны на 2 практических занятия (4 часа). Цель занятий – изучить основы исчисления высказываний и научиться выводить формулы в алгебре и исчислении высказываний.

Введение

Широкое использование аксиоматического метода в построении математических теорий стало одной из важных причин появления и развития математической логики. При таком подходе выбирается система основных неопределяемых понятий и отношений между ними, далее, постулируется система свойств основных понятий и отношений, называемых аксиомами. Новые понятия теории вводятся через основные или ранее определенные, а утверждения выводятся из аксиом или из ранее доказанных утверждений.

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

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

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

1. Выводимость

Пусть задано множество формул от высказывательных переменных

( ), ( ), . . . , ( ). (1)

Это множество формул назовем системой посылок.

Определение. Формула ( ) называется выводимой из системы формул (1) в алгебре высказываний, что обозначается , . . ,  , тогда и только тогда, когда формула

(2)

является ТИ-высказыванием, т.е.

 .

Из определения следует, что если конъюнкция

(3)

тождественно истинна, то из такой системы посылок (1) выводимы только тождественно истинные формулы, которые выводимы из любой системы посылок. Если же конъюнкция (3) тождественно ложна, то из системы посылок (1) выводима любая формула.

Если формула выводима из системы формул (1), то из истинности всех формул системы при некоторых значениях высказывательных переменных следует истинность формулы при тех же значениях переменных.

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

1. Если  и  то  .

2. Если  и ~ , то  .

Проверка выводимости формулы из системы посылок (1) непосредственно по определению, т.е. путем доказательства тождественной истинности формулы (2), достаточно громоздко. Рассмотрим более простой способ доказательства выводимости формулы из системы посылок (1), для которых конъюнкция (3) не является ни ТИ-высказыванием, ни ТЛ-высказыванием.

Теорема 1.1. Формула ( ) тогда и только тогда выводима из системы формул (1), когда все полные элементарные дизъюнкции формулы входят в СКН-форму , эквивалентную формуле (3) относительно высказывательных переменных .

Так как теорема 1 формулирует необходимое и достаточное условие выводимости формулы, то на основе нее можно сформулировать алгоритм доказательства выводимости формулы.

1. Из системы посылок (1) строится конъюнкция (3).

2. Находим СКН-форму от высказывательных переменных для формулы (3).

3. Строим СКН-форму для формулы и проверяем вхождение полных элементарных дизъюнкций СКН-формы для формулы в СКН-форму для формулы (3).

Задание 1. Доказать выводимость  .

Решение.

1. Обозначим = X, = . Строим их конъюнкцию .

2. Найдем СКН-форму эквивалентную этой конъюнкции.

V

3. Получим СКН-форму для формулы B .

Так как обе дизъюнкции входят в СКН-форму , то выводимость доказана.

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

Кроме того, воспользовавшись теоремой 1, можно построить все СКН-формы выводимые из данной системы посылок. Для этого требуется небольшая модификация алгоритма доказательства выводимости формулы. После построения СКН-формы для формулы (3) необходимо

3. Из полных элементарных дизъюнкций полученной СКН-формы строим различные комбинации конъюнкций. Эти конъюнкции и будут исчерпывать все СКН-формы, выводимые из системы посылок (1).

Задание 2. Найти все формулы, выводимые из системы посылок задания 1.

Решение. Построим различные комбинации полных элементарных дизъюнкций формулы .

1. 

2. 

3. 

4. 

5. 

6. 

7. 

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

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

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

является ТИ-высказыванием. В силу определения выводимости, это означает, что формула выводима из формул и .