Теория алгоритмов. Зюзысов В.М. - 33 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Наша цель показать, что формула исчисления высказываний является тавтологией
тогда и только тогда, когда она есть теорема. В одну сторону это доказывается совсем
просто.
Теорема 12.
1. Любая аксиома в исчислении высказываний является тавтологией.
2. Любая теорема в исчислении высказываний является тавтологией.
Доказательство. То, что каждая аксиома A1–A3 является тавтологией,
легко
проверить с помощью таблиц истинности. Для доказательства пункта 2 теоремы,
предварительно докажем, что правило MP, примененное к тавтологиям, приводит к
тавтологиям.
Действительно, пусть при произвольном распределении истинностных значений
формулы A и A⊃B являются тавтологиями. Тогда формула A истинна и, по свойствам
импликации, B истинно. Следовательно, B – тавтология.
Теорема 13. (Пост, 1921)
Если формула A логики высказываний является
тавтологией, то A – теорема в исчислении высказываний.
Интерпретация формул исчисления высказываний проста − область интерпретации
состоит из двух значений «истина» и «ложь»; поэтому пропозициональная переменная
принимает только значения И и Л и интерпретация составной формулы вычисляется по
известным законам с помощью логических операций над истинностными
значениями.
Поскольку любая формула содержит только конечное число пропозициональных
переменных, то формула обладает только конечным числом различных интерпретаций.
Следовательно, исчисление высказываний является, очевидно, разрешимой формальной
теорией.
Легко убедиться, что исчисление высказываний является формально
непротиворечивой теорией. Действительно, все теоремы исчисления высказываний суть
тавтологии. Отрицание тавтологии не есть тавтология. Следовательно, никакая формула
не может быть выведена вместе со своим отрицанием.
3.4 Теории первого порядка
Языки первого порядка
Чтобы описания математических объектов и математические рассуждения сделать
точными в математической логике используются искусственные языки. Самый
распространенный вид таких языков – так называемые логико-математические языки
первого порядка. Каждый язык первого порядка задается своей сигнатурой – набором из
трех множеств: множество констант; множество функциональных символов
(функторов); множество предикатных символов. При этом с
каждым предикатным или
функциональным символом однозначно связано некоторое натуральное число –
количество аргументов (местность, арность) этого символа. Функциональный или
предикатный символ, местность которого равна k, называется k-местным.
Во всяком языке первого порядка имеется счетный набор переменных. Используя
переменные и константы как аргументы функциональных символов, строят термы.
Причем этот процесс рекуррентный, и
из существующих термов, сделав их аргументами
каких-то функциональных символов можно построить новые термы. Термы играют роль
имен объектов.
Элементарные формулы определяются как выражения вида P(t
1
, t
2
,…, t
k
), где P
есть k-местный предикатный символ, а t
1
, t
2
,…, t
k
– термы. Используя знаки логических
операций ¬ (отрицание), ∨ (дизъюнкция), ∧ (конъюнкция), ⊃ (импликация), ∼
(эквиваленция), ∀ (квантор общности), ∃ (квантор существования) из элементарных
формул строятся более сложные формулы.
Языки первого порядка используются для записи математических утверждений,
причем для каждой конкретной области математики, или, как говорят математической

Страницы