🗊Презентация Формальные логические теории

ФОРМАЛЬНЫЕ ЛОГИЧЕСКИЕ ТЕОРИИ Глава 2, стр. 20

Формальные теории Построение и истолкование математической теории, когда каждое понятие более или менее соответствует некоторому явлению окружающей нас действительности, называется содержательным истолкованием теории. Соответствие законов, связей и отношений объектов формальной модели элементам реального мира называется адекватностью. Степень адекватности определяет, применимы ли полученные в результате формального вывода результаты к конкретным проблемам в реальном мире. Любая формальная теория определяется заданием четырех ее элементов: алфавита, множества формул, множества аксиом, множества правил вывода

Алфавит, формулы, аксиомы Алфавит формальной теории — это конечное множество символов. Если множество всевозможных цепочек над алфавитом обозначить , то множество F формул формальной теории — это некоторое подмножество , т.е. F ⊆ . Множество A аксиом — это некоторое подмножество множества ее формул. Аксиомы, если число их конечно, задаются перечислением. Если число аксиом бесконечно, то они должны быть заданы некоторыми конечными правилами, позволяющими эффективно распознавать аксиомы среди прочих формул. Правила вывода должны давать возможность по некоторому набору формул и формуле C установить, выводима ли формула C из формул . Правила вывода обычно записываются в виде , или , или В этом случае говорят, что формула C является непосредственным следствием формул или непосредственно выводима из них.

Правила вывода Правила вывода должны давать возможность по некоторому набору формул и формуле C установить, выводима ли формула C из формул . Правила вывода обычно записываются в виде , или , или В этом случае говорят, что формула C является непосредственным следствием формул или непосредственно выводима из них. Доказательством в рамках формальной теории является последовательность утверждений, приводящих от исходных утверждений, принимаемых за истинные, к их логическим следствиям. Выводом формулы C в формальной теории называется конечная последовательность формул , где , а каждая из формул Ci для i = 1; :::; n — это либо аксиома формальной теории, либо непосредственное следствие каких–либо предыдущих формул этой последовательности в соответствиии с одним из правил вывода

Доказательство, вывод Доказательством в рамках формальной теории является последовательность утверждений, приводящих от исходных утверждений, принимаемых за истинные, к их логическим следствиям. Выводом формулы C в формальной теории называется конечная последовательность формул , где , а каждая из формул для i = 1,…,n — это либо аксиома формальной теории, либо непосредственное следствие каких–либо предыдущих формул этой последовательности в соответствиии с одним из правил вывода Особенно следует отметить, что при построении любой формальной теории мы имеем дело только с конечными множествами. Рассматриваемые нами теории будут строиться на основе финитного метода.

Исчисление высказываний Логика интересуется прежде всего истинностью или ложностью высказываний. Высказывания могут быть тождественно истинными, тождественно ложными, имеющими переменное значение истинности. В алфавит исчисления высказываний входят большие латинские буквы (с возможными индексами) для обозначения высказываний. Эти символы будем называть переменными высказываниями. Все тождественно истинные высказывания с точки зрения математической логики эквивалентны. Это же можно сказать и для тождественно ложных высказываний. Как и булевой алгебре, для тождественно истинного высказывания в формальном логическом исчислении вводится обозначение ”истина” ( или true или T ), а для тождественно ложного — обозначение ”ложь” (или false или F ). Соответствующие обозначения входят в алфавит логической формальной теории — исчисления высказываний.

Алфавит исчисления высказываний В алфавит входят также обозначения логических операций (или логических связок) и знаки круглых скобок ”(” и ”)”. В качестве логических связок в исчислении высказываний рассмотрим четыре операции: Мы будем строить исчисление таким образом, чтобы его интерпретация была максимально естественной с точки зрения логических операций булевой алгебры. Поэтому наши логические связки носят обычные названия операций булевой алгебры: & —конъюнкция или логическое умножение, — дизъюнкция или логическое сложение, — импликация или логическое следование, : — отрицание. Иных символов, кроме выше перечисленных символов, в исчислении высказываний нет.

Множество формул исчисления высказываний Определение 2.1. Формула исчисления высказываний — это одна из следующих конструкций: а) переменное высказывание есть формула; б) если fi и fl есть формулы, то формулами являются также в) никаких других формул в исчислении высказываний нет. Итак, если мы не говорим об интерпретации, то формулы исчисления высказываний — это просто последовательности символов, удовлетворяющие определенным правилам записи. Например, слова

Множество формул исчисления высказываний Формулы исчисления высказываний иначе называются пропозициональными формами, а частный случай формулы — переменные высказывания и константы true, false — пропозициональными переменными и пропозициональными константами соответственно. Правильные формулы исчисления высказываний будем обозначать маленькими буквами греческого алфавита с возможными индексами. Задачей логики является определение смысла каждой формулы. Если каждое высказывание в формуле может быть проинтерпретировано как истинное или ложное, определены правила выполнения операции над соответствующими значениями, то можно вычислить значение каждой формулы для заданных значений переменных высказываний.

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

Множество аксиом исчисления высказываний Множество аксиом исчисления высказываний зададим следующими тремя схемами аксиом: Аксиомы A1 – A3 записаны только с использованием операций импликации и отрицания. Операции дизъюнкции и конъюнкции в аксиомах отсутствуют. Как мы только что выяснили, можно построить исчисление высказываний и только на основе операций импликации и отрицания. Часто в множество операций вводят еще одну операцию — эквивалентность, правила для которой имеют вид:

Множество аксиом исчисления высказываний Заметим, что исчисление высказываний удовлетворяет требованиям строгости работы с бесконечностью, т.к. в исчислении рассматриваются только конечные наборы символов и конечное число операций между ними, конечное число аксиом и конечное число правил вывода. Множество аксиом мы можем дополнить еще одной аксиомой: Определение 2.2. Аксиома, не выводимая из остальных аксиом, называется независимой от этих аксиом, а система аксиом, в которой ни одна аксиома не выводится из остальных, называется независимой системой аксиом. В противном случае система аксиом называется зависимой. Можно доказать, что система аксиом A1 — A5 исчисления высказываний независима.

Правила вывода исчисления высказываний В исчислении высказываний имеется единственное правило вывода, согласно которому формула является непосредственным следствием формул и , каковы бы не являлись формулы и . Это правило записывается в виде схемы Оно называется правилом заключения или правилом modus ponens и кратко обозначается MP.

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

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

Теорема о дедукции исчисления высказываний Теорема 2.2 ( о дедукции). Пусть Г — некоторый список формул и — одна формула. Тогда если Доказательство. Сначала сформулируем теорему подробнее следующим образом: если формула выводима из списка гипотез , дополненного формулой , то формула выводима из списка гипотез . Теперь рассмотрим имеющийся по условию теоремы вывод из . Пусть этот вывод представляет собой последовательность формул Индукцией по i покажем, что формула выводима из списка гипотез Рассмотрим всевозможные варианты вывода очередной формулы .

Теорема о дедукции исчисления высказываний Теорема 2.2 ( о дедукции). Пусть Г — некоторый список формул и — одна формула. Тогда если Доказательство (продолжение). В соответствии c определением выводимости существует всего четыре варианта вывода : а) — аксиома, б) — гипотеза из , в) — гипотеза , г) — непосредственное следствие из некоторых и по правилу MP. Заметим, что для первого шага вывода при i = 1 возможны только первые три варианта из вышеперечисленных. Рассмотрим общий случай — перечисленные четыре варианта.

Теорема о дедукции исчисления высказываний Доказательство (продолжение). а) Если — аксиома, то продолжим вывод: ( аксиома), () ( аксиома A1), ( правило МР). При любом i в выводе не участвует формула , таким образом, в соответствии с определением выводимости можем считать, что доказан вывод б) Если — гипотеза из , то вывод строится точно также, за тем исключением, что основанием для первого шага является принадлежность множеству . в) Если — гипотеза , то вывод мы выполнили при доказательстве теоремы 2.1. Таким образом, доказали и, следовательно, в соответствии с определением выводимости получили вывод .

Теорема о дедукции исчисления высказываний Доказательство (продолжение). г) Если — непосредственное следствие из некоторых и по правилу MP: , , . Воспользуемся индукцией: значения m и k меньше значения i, следовательно, в соответствии с индуктивным предположением из выводимы формулы и . Фактически, в силу равенства , которое существует по причине применимости правила MP в выводе, выводима формула Продолжим этот вывод: Следовательно, и в этом четвертом случае существует вывод

Теорема о дедукции исчисления высказываний Доказательство (продолжение). Таким образом, рассмотрев всевозможные варианты вывода, мы установили, что для любого i для всех вариантов вывода из и мы указали способ продолжения вывода для того, чтобы получить вывод . Таким образом, из выводима и формула , совпадающая с . □

Правило силлогизма Теорема 2.3. В соответствии с формулировкой торемы у нас есть две гипотезы и . Пусть эти две гипотезы составляют множество гипотез . Рассмотрим вспомогательную гипотезу и рассмотрим вывод: 1) ( гипотеза), 2) ( гипотеза), 3) ( дополнительная гипотеза), 4) ( правило MP из 1 и 3), 5) ( правило MP из 2 и 4), Таким образом, доказали В соответствии с теоремой о дедукции получаем .□ Полученное при доказательстве теоремы 2.3 правило выводимости можно записать как

Независимость системы аксиом Теорема 2.4. Система аксиом A1 — A5 независима