Человеческое мышление


Похожие статьи:

Популярные записи


  • Исчисление высказываний и алгебра высказываний. Основные проблемы исчисления высказываний.

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

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

    Теорема 5.5. Любая теорема исчисления высказываний ЧВ является тождественно истинным высказыванием тавтологией.

    Доведение. Тождественная истинность всех аксиом легко проверяется непосредственно построением соответствующих таблиц истинности для каждой из них рекомендуем это сделать самостоятельно.

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

    Если A P1, P2.., Pn - тождественно истинная формула, то для произвольного набора значений A1, A2.., An ее пропозицийних переменных A A1, A2.., An является истинной. Следовательно, тождественно истинной будет и любая формула A, что получается из формулы A путем подстановки вместо пропозицийних переменных P1, P2.., Pn произвольных формул B1, B2...., Bn, поскольку последние могут приобретать лишь значения 0 или 1.

    Докажем, что когда формулы A и A B является тождественно истинными, тогда формула B, какую мы достаем из них по правилу вывода, также являемся тождественно истинными. Допустим противоположное: пусть B не является тождественно истинной формулой, то есть существует набор значений ее переменных, на котором она приобретает значение 0. Тогда подставим этот набор в формулу A B, поскольку A является тавтологией, то достанем выражение 10, значением которого является 0. Последнее противоречит предположению о тождественной истинности формулы A B.

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

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

    Теорема 5.6. Любая тождественно истинная формула алгебры высказываний является теоремой исчисления высказываний ЧВ.

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

    1. Проблема несуперечности.

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

    Исчисление есть Непротиворечивым, если невозможно одновременно вывести из аксиом исчисление как формулу A, так и ее отрицание A.

    Следствие 5.1. Исчисление высказываний ЧВ является непротиворечивой формальной теорией.

    Действительно, если формула A выводная в исчислении высказываний, то формула A не может быть выводной, потому что за теоремой 5.5 формула A является тождественно истинной в алгебре высказываний, а формула A - тождественно ошибочной. Следовательно, A не может быть теоремой исчисления высказываний ЧВ.

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

    Iнша проблема, которая возникает при исследовании разных исчислений высказываний, : или любая тождественно истинная формула алгебры высказываний будет выводной в заданном исчислении? Это вопрос и являет собой Проблему полноты для исчисления высказываний.

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

    Следствие 5.2. Исчисление высказываний ЧВ является полным.

    Справедливость этого утверждения непосредственно выплывает из теоремы 5.6.

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

    3. Проблема развязности.

    Розв'язувальним методом для формальной теории T называют метод, с помощью которого для произвольной формулы A из T можно за конечное число шагов определить, будет <ли i> A теоремой, или нет.

    Исчисление T называют Развязным, если для T существует розв'язувальний метод, в противном разе - формальная теория T есть нерозв'яною.

    Следствие 5.3. Исчисление высказываний ЧВ является развязной теорией.

    Доведение. Пусть A - произвольная формула исчисления ЧВ. Построим для нее таблицу истинности и рассмотрим ее последний столбик. Если он содержит лишь единицы, то A - тождественно истинная формула и за теоремой 5.6 является теоремой ЧВ. В противном разе последний столбик таблицы истинности содержит хотя бы один нуль, A - не тавтология и значит, A не является теоремой.

    Понятно, что все эти действия можно предпринять за конечное число шагов.

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

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

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

    Можно доказать, что системы аксиом исчислений высказываний ЧВ и ЧВ1 являются независимыми.

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