Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2



страница1/5
Дата02.01.2013
Размер0.5 Mb.
ТипДокументы
  1   2   3   4   5
Мухачев В.П.
Генценовский исчисления натурального вывода. Специфика поиска (построение) вывода в них.


§1. Исчисление NJ.
Определение 2.1. NJ — вывод состоит из формул, расположенных в виде дерева.
Определение 2.2. Допущения — это исходные формулы вывода, каждой из которых в выводе поставлена в соответствие в точности одна Н-фигура заключения (при этом данная исходная формула стоит «выше» нижней формулы этой Н-фигуры заключения.)

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

В соответствии со сказанным, конечная формула вывода не зависит ни от каких допущений.
СХЕМЫ ФИГУР ЗАКЛЮЧЕНИЯ
Введение конъюнкции: Удаление конъюнкции:


Введение дизъюнкции: Удаление дизъюнкции:


Введение импликации: Удаление импликации:


Введение отрицания: Удаление отрицания:


Введение произвольного высказывания:


Введение квантора всеобщности: Удаление квантора всеобщности:


Введение квантора существования: Удаление квантора существования:


Собственной переменной некоторой фигуры заключения (соответственно gif" name="object18" align=absmiddle width=27 height=20>) мы называем свободную предметную переменную, обозначенную в соответствующей схеме посредством а; предполагается, что она существует, т.е. связанная предметная переменная, обозначенная посредством x, входит в формулу обозначенную посредством Fx.

Ограничение на переменные:

NJ-вывод должен удовлетворять еще следующим условиям:

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

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

Пояснения к схемам фигур заключения и

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

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

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

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

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

&+: Словами это заключение можно выразить так: "Если имеют место два высказывания А и В, то имеет место и сложное высказывание (АВ)".

&-: Если доказано (имеет место) высказывание АВ, то имеет место высказывание А, или имеет место высказывание В. Этот факт отражается наличием двух схем заключения.

+: Если доказано высказывание А или высказывание В, то имеет место и высказывание (АВ), этот факт также отражается наличием двух схем заключения.

- (разбор случаев): Если доказано (АВ), то можно вести доказательство разбором случаев. Предположим сначала, что имеет место А, и из него выведем С. Если далее из предложения о том, что имеет место В, снова вывели С, то С вообще имеет место уже независимо от обоих допущений.

+: Если В доказано с использованием допущения А, то (уже без этого допущения из А следует В, т.е (АВ)).

-: Это правило есть уже известный modus ponens. Если доказано А и доказано АВ, то имеет место и В.

+: Если из допущения А следует нечто ложное (Л), то А не является истинной, т.е. имеет место А.

-: А и А означает "противоречие", а таковое не может соответствовать действительности (закон противоречия). Это формально отражено в фигуре заключения , где знак Л означает "противоречие", "ложность".

ВПВ: Если имеет место нечто ложное, то имеет место любое высказывание.

+: Если F доказано для любого «для произвольного а», то имеет место xFx. Предположение, что а «совершенно произвольно», может быть точнее выражено так: Fa не зависит ни от какого допущения, в которое входит предметная переменная а.

-: Это правило совершенно очевидно. Если доказано, что для всех х каждого класса имеет место Fx, то и для произвольно выбранного а из этого класса верно, что Fx

+: Если Fa доказано «для произвольного а», то можно утверждать, что существует «такой х, что Fx;

-: Имеем xFx. Далее рассуждаем так: пусть а— именно такой объект, для которого имеет место F, т.е. допустим, что имеет место Fa. (В качестве а надо брать такую переменную, которая не входит в xFx. Если опираясь на это допущение, мы докажем некоторое высказывание С, которое уже не содержит а и не зависит ни от каких других допущений, содержащих а, то С доказано независимо от допущения Fa.
Введенные обозначения отдельных фигур заключения показывают, что имеется заслуживающая внимания систематизация их. С каждым из логических знаков , , , , ,  связана одна фигура "введения" и одна фигура «удаления» его как внешнего знака формулы. Наличие двух фигур заключения &- и + представляет собой незначительное чисто внешнее отклонение. Введения представляют собой, так сказать, "определения" соответствующих знаков, а удаления являются лишь следствиями этих определений. Это можно выразить следующим образом: при удалении некоторого знака формула, которой это касается, и знак, о котором идет речь, могут использоваться лишь в том значении, которое они получают при введении данного знака.

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



Пример для конъюнкции:


Исходные формулы А и В получаются двумя шагами в результате последовательного применения правил &+ и &-.

Из указанной систематизации фигур заключения выпадает отрицание. Однако, отрицание можно исключить из нашего исчисления, если рассматривать А как сокращение для АЛ. Это допустимо, так как если в некотором NJ-выводе уничтожить все знаки , заменив каждую формулу вида А формулой АЛ, то получится снова NJ-вывод (при этом фигуры заключения + и - станут частными случаями + и -), и обратно: если в некотором NJ-выводе каждое АЛ заменить на А, то получится опять NJ-вывод.

Схема фигур заключения ВПВ занимает среди схем особое место, она относится не к логическому знаку, а к знаку высказывания Л.
***

§3.Как построить вывод в исчислении NJ.
Напомним еще раз некоторые определения. Формула А называется теоремой в исчислении NJ, если она имеет вывод в исчислении NJ и не зависит ни от каких допущений.

"Вывод с конечной формулой А мы будем называть также выводом формулы А" (стр. ).

"NJ- вывод состоит из формул располагающихся в виде дерева" (стр.)

Дерево вывода содержит:

1) исходные формулы; они являются допущениями, и отличаются от всех других формул тем, что не являются нижними формулами никаких фигур заключения;

2) конечную формулу; она является той формулой, вывод которой мы строим, причем она не входит ни в одну фигуру заключения в качестве верхней формулы;

3) промежуточные формулы; они появляются в выводе в результате применения фигур заключения и, следовательно, могут быть как нижними, так и верхними формулами фигур заключения.
Поиск вывода в натуральном исчислении обладает рядом особенностей, описание которых удобнее ввести не в определение вывода, а в процедуру, сформулированную на основании разбора различных примеров. Поэтому данный параграф мы посвятим рассмотрению примеров, характеризующих разные тактики поиска вывода.
Пример 1. Это случай построения вывода сверху вниз:


Исходными формулами этого вывода являются формулы p и q, т.е. мы допускаем, что имеют место два высказывания. Обозначим их порядковыми номерами 1 и 2. Знак "+" указывает, что на этом шаге мы вводим допущения.

Поскольку имеют место два высказывания, то в соответствии с правилами исчисления NJ мы можем получить формулу pq. Этот факт мы отражаем с помощью фигуры заключения "введения конъюнкции" и вывод пока имеет вид:

введение конъюнкции
Далее, так как при построении формулы pq мы используем допущение q, то этот факт мы фиксируем посредством применения фигуры заключения "введение импликации".


Сравните правило и его конкретное применение в нашем примере.

Здесь вместо берем q, а вместо В берем p&q.

Выражение "" обозначает часть вывода.

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

Далее, поскольку при построении формулы p&q мы использовали допущение p, то этот факт мы отражаем также с помощью фигуры заключения "введение импликации".

Сравните:

.
Здесь в качестве берем p, в качестве В - , а вместо АВ имеем .

Итак, формула является теоремой в исчислении NJ, поскольку она имеет NJ- вывод и не зависит ни от каких допущений.
Пример 2.

Рассмотрим иную ситуацию. Пусть нам предъявлено некоторое содержательное рассуждение, например: "Если идет дождь, то при выходе из дома мы берем зонтик. Если мы взяли зонтик, то можем обойтись без шляпы. Следовательно, если идет дождь, то мы можем обойтись без шляпы". Это рассуждение мы представим в нашем языке L в виде следующей формулы: . И теперь, чтобы выяснить, является ли это содержательное рассуждение правильным, нам необходимо проверить, является ли указанная формула теоремой в NJ-исчислении (т.е. можно ли построить NJ-вывод данной формулы, не зависящий от допущений.)
  1   2   3   4   5

Похожие:

Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 iconКлассическое определение вероятности. Комбинаторные методы решения задач
Цель: выработать умение решать задачи на определение классической вероятности с использованием основных формул комбинаторики
Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 iconПриме Например, представим систему, которая состоит из трех подсистем. Соответственно, и требования могут быть разбиты на три части. Это можно представить в виде дерева следующим образом
Извлекаемые из документации требования представляются в виде дерева требований. Каждый узел-родитель в этом дереве является обобщением,...
Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 icon2001 Дифференциальное исчисление функции одной переменной. Производная функции, ее геометрический и физический смысл. Определение
Определение. Производной функции f(x) в точке х = х0 называется предел отношения приращения функции в этой точке к приращению аргумента,...
Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 iconПринципиальная схема сеточного метода решения детерминированного эквивалента стохастической задачи управления портфелем финансовых инструментов
Х переменных в динамике. Ключевая идея состоит в генерировании множества сценариев реализации случайных параметров в виде дерева...
Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 iconОпределение и свойства предела последовательности. Определение
Определение: задать числовую последовательность – это значит сопоставить каждому номеру действительное число
Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 iconРешение задач на вывод формул органических веществ. Алгоритм решения задач на вывод формул органических веществ
Обозначить формулу вещества с помощью индексов Х,у,z и т д по числу элементов в молекуле. Если продуктами горения являются со2 и...
Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 iconУрок по теме «Функция квадратного корня»
В последствии появилось определение функции, данное Эйлером 1751 год, затем — у Лакруа в 1806 году — уже практически в современном...
Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 iconА. Определение: множество неограниченно. Определение: последовательность удовлетворяет критерию Коши. Определение: последовательность не удовлетворяет критерию Коши. Определение точной верхней грани. Определение точной нижней грани

Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 icon«Определение степени с целым показателем»
Образовательная: дать определение дроби с целым показателем, научить представлять степень с целым отрицательным показателем в виде...
Исчисление nj. Определение nj — вывод состоит из формул, расположенных в виде дерева. Определение 2 icon§ Определение доказуемой (выводимой) формулы
Следующим этапом в построении исчисления высказываний является выделение класса доказуемых (выводимых) формул
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org