Выводимость формул в исчислении высказываний

Символы, формулы, аксиомы исчисления высказываний. Правила вывода

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

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

Символы исчисления высказываний состоят из знаков трех категорий:

Большие латинские буквы А, В, С, . X, Y, Z, . которые назовем переменными высказываниями.

Символы операций исчисления Ù, Ú, ®, ¾ (знак конъюнкции, дизъюнкции, следования и отрицания).

Других символов система исчисления высказываний не содержит.

Формулой в исчислении высказываний является некоторая последовательность символов. Но не всякая последовательность символов есть формула. Например, последовательности А→В (С→) и (А В) не являются формулами. Определение формулы в исчислении высказываний задается следующим образом:

1. Всякое переменное высказывание есть формула.

2. Если a, b есть формулы, то выражения вида (aÙb), , , (aÚb), (a®b) также являются формулами.

Зададим в исчислении высказываний класс исходных истинных формул-аксиом.

I.	1.	А®(В®А);
2.	(А® (В®С))®((А®В)®(А®С);
II.	1.	АÙВ®А;
2.	АÙВ®В;
3.	(А®В)®((А®С)®(А®ВÙС));
III.	1.	А®АÚВ;
2.	В®АÚВ;
3.	(А®С)®((В®С)(АÚВ®С)).
IV.	1.	;
2.	;
3.	.

Правила вывода позволяют из данной системы аксиом получать другие истинные формулы исчисления высказываний. Назовем формулу исчисления высказываний ложной, если ее отрицание истинно. Будем обозначать истинные формулы буквой R, ложные – F.

К основным правилам вывода относятся два:

1) Правило заключения.

Если a и (a®b) – истинные формулы, то b также истинна. Это предложение можно записать в виде

.

2) Правило подстановки

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

Формула называется выводимой в исчислении высказываний, если ее можно получить, применяя правила вывода к аксиомам исчисления высказываний. Утверждение, что формула b выводима, записывают так:

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

Упражнение 2.3.3

Докажем, что выводима формула А®А, т.е. А®А.

1. Запишем аксиому 2 из группы I.

2. Применим к ней правило подстановки , т.е.

.

3. Заметим, что a есть истинная формула, как аксиома из группы I, т.е. имеем истинные формулы a и a®b. Применим правило заключения и получим (А®В)®(А®А).

4. Применим правило подстановки к полученной формуле, заменив высказывание В на :

.

5. Но , есть аксиома 2 из группы IV. Применим к полученной формуле правило заключения , т.е. -А®А.

Говорят, что формула b выводима из формул a₁, a₂, . a_n, если формулу b можно вывести путем правила заключения, приняв за исходные формулы a₁, a₂, . a_n и все истинные в исчислении высказываний формулы. Выводимость формулы b из формул a₁, a₂, . a_n записывают в виде a₁, a₂, . a_n, b.

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

Если формула b выводима из формул a₁, a₂, . a_n, то выводимой является формула a₁®(a₂®(. (a_n®b). )), т.е.

.

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

1. Правило силлогизма. Если формулы (a®b) и (b®g) истинны, то формула (a®g), т.е.

;

2. Правило перестановки посылок. Если формула (a® (b®g)) истинна, то истинной является формула (b® (a®g)), т.е. ;

3. Правило соединения посылок. Если истинной является формула (a®(b®g)), то истинной будет формула (aÙb®g), т.е. .

Проблемы непротиворечивости, полноты,
независимости аксиом исчисления высказываний

Используем алгебру высказываний как некоторую модель исчисления высказываний. Формулы исчисления высказываний будем трактовать как формулы алгебры высказываний. Для этого все буквы, входящие в алфавит исчисления высказываний, будем считать переменными высказываниями в содержательном смысле, т.е. переменными, принимающими значения И и Л. Символы алфавита Ù, Ú, ®, ¾ , — будем понимать как логические связки алгебры высказываний.

При этом справедлива следующая теорема.

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

Доказательство первой части теоремы можно провести непосредственной проверкой.

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

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

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

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

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

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

Теорема I. Исчисление высказываний непротиворечиво.

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

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

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

Эта задача представляет собой проблему полноты исчисления высказываний в широком смысле.

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

Для исчисления высказываний проблема полноты решается положительно.

Теорема II. Система исчисления высказываний является полной.

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

Для любой логической системы возникает проблема независимости аксиом данного исчисления. Зададимся вопросом, можно ли какую-либо аксиому исчисления вывести из остальных аксиом с помощью правил вывода данной системы. Если это возможно, то аксиому, выводимую из других аксиом, можно вычеркнуть из списка аксиом данного исчисления. Аксиома, невыводимая из остальных аксиом, называется независимой из этих аксиом. Система аксиом, в которой ни одна аксиома не выводима из остальных, называется независимой системой аксиом.

Эта проблема для исчислений решается положительно.

Теорема III. Система аксиом исчисления высказываний независима.

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

Логика предикатов

Для определения понятия предиката рассмотрим следующие примеры.

1. Пусть N – множество натуральных чисел, и буквой P обозначено свойство натурального числа быть простым. Если x представляет собой произвольный элемент из N, тогда выражение «натуральное число x является простым», которое можно записать в виде P(x), уже не является высказыванием, т.к. значение истинности данного утверждения зависит от x. По существу P(x) означает переменное (неопределенное) высказывание, которое становится определенным, когда x заменено определенным элементом из N. Например, P(3) = 1, P(4) = 0. Иначе говоря, P(x) представляет собой функцию, определенную на множестве натуральных чисел и принимающую только два значения: 0 и 1.

2. Пусть Z – множество целых чисел и P – свойство пары чисел иметь одинаковый знак. Тогда P(x,y) будет означать: «целые числа x и y имеют одинаковый знак». Это неопределенное высказывание становится определенным, если x и y заменить конкретными числами. Например, P(2,3)=1, P(-1,5)=0. Неопределенное высказывание P(x,y) представляет собой функцию двух переменных.

3. Пусть A и B – множество точек, C – множество прямых на евклидовой плоскости, а P(a,b,c) обозначает: «прямая c проходит через точки a и b». В этом примере мы имеем дело с функцией трех переменных, причем a и b принимают значения из множества точек, а c принимает значения из множества прямых евклидовой плоскости.

Определение 1. Предикатом называется функция, отображающая множество произвольной природы во множество <0,1>, или (ложно, истинно).

Обратимся теперь к определению предиката в общем случае.

Определение 2. Пусть N=₁,N₂,N₃,…,N_n> – конечный набор множеств. Всякая функция P(X₁,…,X_n), ставящая в соответствие каждому набору из n элементов ₁,a₂,…,a_n), где a_iÎN_i, какой-либо из элементов булевой алгебры <0,1>называется n-местным предикатом на N. Множество N_i называется предметной областью для переменной x_i. Переменные x₁,…,x_n называются предметными переменными. Некоторые из множества N_i могут совпадать.

Если при отображении P образом набора (a₁,a₂,…a_n) является единица, то записывают.

и говорят, что значение предиката P для набора (a₁,…,a_n) является истинным. Если же образом (a₁,…,a_n) является нуль, то записывают

и говорят, что значение предиката P для набора (a₁,…,a_n) является ложным.

n – местный предикат при n = 1 называется унарным, при
n = 2 – бинарным и при n=3 тернарным. Для общности введем еще понятие 0-местного предиката, а именно, 0-местным предикатом называется любе истинное или ложное высказывание.

Поскольку предикаты принимают значения из (0,1), то над ними можно производить все логические операции, рассматриваемые нами в алгебре высказываний (-, Ù, Ú, ®, «), сохраняя за ними те же определения. Кроме операций алгебры высказываний, мы будем употреблять еще две новые операции, которые связаны с особенностями предикатов и выражают собой утверждения всеобщности и существования.

Пусть P(x) – одноместный предикат, заданный на некотором множестве M. Если переменная x обозначает любой элемент из множества M, то P(x) является неопределенным высказыванием.

Операция " ставит в соответствие неопределенному высказыванию P(x) высказывание "xP(x), которое читается так: «для любого x имеет место P(x)» и по определению является истинным тогда и только тогда, когда P(x) истинно для любого элемента xÎM. Переход от неопределенного высказывания P(x) к высказыванию "xP(x) называется операцией навешивания квантора общности по предметному переменному x.

Операция $ ставит в соответствие неопределенному высказыванию P(x) высказывание $xP(x), которое читается так: «существует такое x, что имеет место P(x)» и по определению является истинным тогда и только тогда, когда P(x) истинно хотя бы для одного элемента xÎM. Переход от неопределенного высказывания P(x) к высказыванию $xP(x) называется операцией навешивания квантора существования по предметному переменному x.

В первом случае мы говорим, что предметная переменная x связана в предикате P(x) квантором всеобщности, во втором случае – квантором существования.

Определим операции навешивания квантора для общего случая n-местного предиката P(x₁,…,x_n). Операции навешивания кванторов " и $ по переменному x₁ (в общем случае по переменному x_i, где I= ) ставит в соответствие предикату P(x₁,…,x_n) (n-1) – местные предикаты

Истинностные значения этих предикатов определяются для фиксированных наборов значений предметных переменных x₂,…,x_n следующим образом:

"x₁P(x_1,a_2…,a_n)=

$x₁P(x_1,a_2…,a_n)=

В общем случае, если k Примеры.

Рассмотрим предикат Д(x₁,x₂) – «число x₁ делится на число x₂», определенный на множестве натуральных чисел. Тогда операция навешивания кванторов приводит к следующим утверждениям:

1. "x₁Д(x_1, x₂) – «для любого x₁ имеет место Д(x₁,x₂)», т.е. всякое x₁ делится на x₂. Этот предикат принимает значение истины только для х₂=1.

2. $x₁ Д(x_1, x₂) – «существует x_1, которое делится на x₂». Этот предикат принимает значение истины для любого значения x₂.

3. "x₁"x₂Д(x_1, x₂) – «для всякого x₁ и для всякого x₂ имеет место делимость x₁ на x_2. Это высказывание является ложным.

4. $x₁"x₂Д(x_1, x₂) – «существует x₁, которое делится на всякое x₂» – ложное высказывание.

5. "x₂$x₁Д(x_1, x₂) – «для всякого x₂ существует x₁ такое, что x₁ делится на x₂» – истинное высказывание.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 8796 — | 7156 — или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Математическая логика для чайников

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

Есть трудности с задачами? МатБюро поможет вам: контрольные по алгебре логики на заказ, сдача тестов алгебре логики.

Другие примеры решений по математической логике:

Исчисление высказываний: решения задач онлайн

Задача 1. Упростить формулы исчисления высказываний.

$$ (ar s vee ar y veear v)(s veear v)(ar y vee q vee s)(ar s vee y)(ar q vee ar y vee v)(s vee v vee y)(ar s vee ar qvee v) $$

Задача 2. Ниже приведены по три клаузы в одном варианте. Каждую клаузу необходимо доказать следующими методами: Квайна, редукций, резолюций.

$$ A o (B o C), A o(B vee C) Rightarrow A o C $$

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

Задача 4. Доказать в исчислении высказываний (буквы обозначают произвольные формулы):

$$(
eg X vee (Y vee
eg Z)) vdash (
eg (Z o
eg X) o
eg (Y o
eg X)) $$

Задача 5. Выполнить исследование логического суждения по заданному варианту, для этого:
— составить таблицу истинности (число строк равно 2n, где n – число пропозициональных переменных, а число столбцов равно сумме числа пропозициональных переменных, посылок, заключения, а также конъюнкции всех посылок и импликации заключения согласно теореме; выделить в таблице истинности штриховкой строки, в которых истинны все посылки и заключение; дать комментарии,
— доказать истинность логического суждения методом дедукции и методом резолюции; нарисовать графы вывода методом дедукции и методом резолюции.

$$ (A o B), (C o
eg B), (C &
eg D) p
eg (
eg A o D)$$

Задача 6. Доказать в исчислении высказываний (буквы обозначают произвольные формулы):

$$(X o Z) o ((Y o Z) o ((X vee Y) o Z))$$

Задача 7. Ниже приведена легенда. Запишите с использованием 4 – 6 различных букв клаузу, отвечающую содержанию легенды, для чего сформулируйте необходимые посылки и два следствия: одно истинное, другое ложное.
Любой марксист — диалектик, но не всякий диалектик — марксист. Любой марксист — материалист, но не всякий материалист — марксист. Гегель был диалектик, но не материалист. Фейербах был материалист, но не диалектик. Итак, если бы Гегель и Фейербах могли объединиться в один кружок, то Маркс уже не понадобился бы.

Вернёмся к построению формальной системы ИП. Нам осталось определить аксиомы и правила вывода. При этом мы хотим, чтобы ИП давала адекватную формализацию описанной выше семантики (интерпретации формул). Другими словами, необходимо обеспечить корректность (все аксиомы должны быть истинными в любой интерпретации, т. е. быть общезначимыми; применение правил вывода к общезначимым формулам даёт общезначимую формулу) и полноту (общезначимые формулы должны быть выводимы).

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

Аксиомы и правила вывода

Вот один из возможных списков аксиом исчисления

Список состоит из схем аксиом исчисления высказываний и двух «кванторных» схем аксиом. Аксиомы исчисления высказываний общезначимы в силу утверждения 3.38. Некоторые формулы схем (А4), (А5) не являются общезначимыми, см. примеры 3.46, 3.44. Но при дополнительных условиях, которые сформулированы в утверждениях 3.48, 3.45, получаются только общезначимые формулы.

Правил вывода в ИП два. Во-первых, это правило modus ponens:

если выводимы формулы А и А—>В, то выводима формула В.

Второе описывает работу с кванторами. Оно называется правилом обобщения (Gen):

если выводима формула А, то выводима формула / хА.

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

Теорема 3.52 (корректность исчисления предикатов).

В ИП выводимы только общезначимые формулы.

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

Общезначимость аксиом (А1 -АЗ) следует из утв. 3.38. Общезначимость аксиом (А4 А5) следует из утверждений 3.48, 3.45.

Если при некоторой оценке переменных формулы А, А—>В истинны, то и формула В также истинна, при этой оценке переменных. Поэтому правило modus ponens из общезначимых формул выводит только общезначимые.

Остается проверить, что правило обобщения сохраняет общезначимость. Действительно, из общезначимости А следует, что в любой интерпретации при любой оценке переменных она истинна. Но тогда по определению интерпретации квантора формула V хА также истинна в любой интерпретации при любой оценке переменных. ?

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

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

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

Лемма 3.53. Пусть А, А2, .А_п — формулы исчисления предикатов, а Ф(х. х_п) — тавтология., в котирую входят переменные Х, . ,х_п. Тогда формула Ф(Л]. А_п) выводима в исчислении предикатов.

Доказательство этой леммы очевидно — нужно подставить в вывод формулы Ф в исчислении высказываний вместо переменных Х <формулы А_г. Полученная последовательность формул будет выводом в исчислении предикатов.