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

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

Натуральное исчисление выражений: правила вывода, понятия вывода, подтверждения, аксиомы.

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

Типы исчислений:

1. Аксиоматические. Начальные дедуктивные постулаты – теоремы и правила вывода.

2. Натуральные исчисления (естественные) Их Эвристические приемы поиска вывода в натуральном исчислении высказываний. задачка – моделировать естественные методы рассуждения, делая их корректными. Процедура поиска вывода в их проще чем в аксиоматических исчислениях. Формальные отличия от аксиоматических исчислений – нет аксиом. В качестве дедуктивных постулатов только правила вывода.

Метод сотворения исчисления:

1) Задается формальный язык

2) Задаются исходные постулаты

3) Задаются принципы и определения вывода

4) Задаются принципы и определения подтверждения

5) Определяется отношение выводимости

6) Выявляется класс Эвристические приемы поиска вывода в натуральном исчислении высказываний. теорем (доказуемых формул)

Построение традиционного исчисления выражений:

1) Использующийся формальный язык – язык традиционной логики выражений

2) Дедуктивные постулаты – правила перехода

Правила перехода бывают 2-ух видов

Прямые – правила дозволяющие перебегать от одной либо нескольких формул определенного типа к формулам определенного типа

А1,А2,…,Аn ├ В1,В2,…,Вn

Непрямые – от утверждения о выводимости перейти к утверждения другой выводимости

Г, А Эвристические приемы поиска вывода в натуральном исчислении высказываний. ├ В

Г ├ А В

В традиционном исчислении выражений употребляются только прямые переходы:

А, В -введение А&ВА&В-исключение

А&В конъюнкции А В конъюнкции

А В-введение А В, А -исключение

А В А В дизъюнкции В дизъюнкции

В-введение А В, А-исключение

С В импликации Вимпликации

В, В -введение А -исключение

С отрицания А отрицания

где С – последнее из неисключенных допущений

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


3) Выводы

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

Вывод формулы А изГ –вывод из Г, последняя формула которого совпадает с А

4) Подтверждения

Подтверждение формулы А – вывод формулы А из пустого огромного количества неисключенных допущений.

5) Выводимость

Формула А выводима из Г, если существует вывод из Г, последняя формула которого совпадает с А

6) Аксиомы

Формула А именуется аксиомой Эвристические приемы поиска вывода в натуральном исчислении высказываний., если ее может быть обосновать в традиционном исчислении выражений

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

Эвристики – подсказки, советы по выбору принципов рассуждения при поиске вывода

Если требуется выстроить вывод А1,А2,…,АnВ, то стратегия в общем виде такая:

Допущения – А1,А2,…,Аn

Цель – В

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

  1. импликативная формула С В.В данном случае прямой вывод:

Допущения – антецедент С

Цель консеквентВ

По правилу введения получаем С В

  1. формула с отрицанием С.В данном случае док-во от неприятного:

Допущения – С

Цель – противоречие В и В

По правилу введения получаем С

Вспомогательные операции. Используются только после 1 и 2 эвристик:

  1. Если имеется Эвристические приемы поиска вывода в натуральном исчислении высказываний. дизъюнктивная формула А В либо отрицание дизъюнкции (А В)

Допущения – А (в первом случае) либо А (во 2-м случае)

Цель в первом случае – В

Цель во 2-м случае – противоречие методом введения к А

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

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

Допущения - А

Цель – противоречие

После получения противоречия мы получаем формулу А, снимая отрицание получаем А, после этого по исключению получаем В

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

имена – знаки аргументов функций

предикаторы – знаки самих функций

предметные функторы – знаки предметных функций

логические связки – знаки истинностно-истинных функций

Полное заглавие: Традиционная односортная логика предикатов первого порядка.

Первого порядка

Так как переменные вводятся только для Эвристические приемы поиска вывода в натуральном исчислении высказываний. предметов (высший порядок – если переменные вводятся не только лишь для предметов, да и для параметров)

Односортная

Так как одна и та же область интерпретации - x yR(x,y) (В многосортной каждой переменной разрешается сравнить свою область интерпретации –

x (S(x) > y(P(y) & R (x,y)).

Традиционная по принципам:

1. Двузначность. Любая формула Эвристические приемы поиска вывода в натуральном исчислении высказываний. может принять ровно одно из 2-ух значений – И либо Л.

2. Экстенсиональность. Значение сложного выражения зависит только от значения входящих в него частей.

3. Постулат о непустоте предметной области.

Язык логики предикатов:

1)Алфавит

Нелогические знаки

Предметные (индивидные) константы – a, b, c,…

Предикаторные константы – Pn,Qn,Rn,… (n – местность предикатора)

Предметно-функциональные константы – fn,gn,hn,… (n – местность функтора)

Предметные переменные Эвристические приемы поиска вывода в натуральном исчислении высказываний. – x, y, z,...

Логические знаки

Пропозициональные связки – выражают логические функции

&– конъюнкция, – дизъюнкция, – отрицание, – импликация

Кванторы – выражают количественные соотношения

– общности, – существования

Технические знаки – ( ) ,

2)Правила образования

Термы – аналог имен

Всякая предметная переменная является термом

Всякая предметная константа является термом

Если fnn-местная предметная константа, а t1,t2,…,tn – термы,

то fn(t1,t2,…,tn) – терм

Ни что другое не является термом

Формулы – аналог предложений

Если Эвристические приемы поиска вывода в натуральном исчислении высказываний. Pn– n-местная предикаторная константа, а t1,t2,…,tn – термы,

то Pn (t1,t2,…,tn) – формула

Если А – формула, то А – тоже формула

Если А и В формулы, то

(А В) – формула, (А В) – формула, (А&В) – формула

Если А – формула, а х – предметная переменная, то

хА - формула

хА - формула

Ни что другое не является формулой

Понятия:

1. Вхождение α в формулу А.

xP(x,y,x) – 3 вхождения переменной хв формулу, одно Эвристические приемы поиска вывода в натуральном исчислении высказываний. вхождение переменной у

2. Область деяния квантора.

αA, αAА находится в области деяния квантора

3. Связанное/свободное вхождение.

Вхождение α именуется связанным, если и только если это вхождение α конкретно следует за квантором либо находится в области деяния квантора по переменной α.

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

4. Свободная/связанная переменная

Переменная свободна в формуле А, если и только если существует свободное вхождение α в А.

Переменная связана в формуле А, если и только если существует связанное вхождение α в А.

Пример: x( yP(x,y,z) R(x,y,z) )

х- связанная, y- связанная и свободная, z- свободная

5. Верная подстановка терма Эвристические приемы поиска вывода в натуральном исчислении высказываний.. А (α /t)

Подстановка терма t в формулу А именуется правильной если и только если:

Замещаются все свободные вхождения α в А.

Ни одно из замещаемых вхождений не находится в формуле А в

области деяния какого-либо квантора по переменной входящей в терм t.

Замкнутый терм – не содержит переменных

Замкнутая формула – не содержит свободных переменных

Интерпретация нелогических знаков:

U (универсум Эвристические приемы поиска вывода в натуральном исчислении высказываний. рассмотрения) – непустое огромное количество предметов, которые могут обозначаться нелогическими знаками. Интерпретация нелогических знаков будет связываться (релятивизироваться) с избранным универсумом. U=

Классы нелогических знаков:

- константы (предметные, предикаторные, предметно-функциональные)

- предметные переменные (равны типу значений предметным константам)

I (интерпретационная функция) – функция приписывания значения константе с учетом избранного U -модель Эвристические приемы поиска вывода в натуральном исчислении высказываний. языка

Интерпретация констант:

Предметные константы – аналоги имен. Значение имени – отдельный предмет, взятый из U. Функция Iкаждой предметной константе сопоставляет элемент огромного количества U

I: I (k) U

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

I: I (Пn) Un

Предметно-функциональные константы – аналоги предметных функторов. Значения – предметно-предметные функции, определенные на огромном количестве U

I: I(Фn) - функция вида Un → U.

Интерпретация предметных переменных:

Функция φ предметным переменным сопоставляет произвольные объекты огромного количества U такого же самого типа, что и константам.

I Эвристические приемы поиска вывода в натуральном исчислении высказываний.: φ (α) U

Выбрав U и I – задаем модель языка m = , где

U – случайное непустое огромное количество

I – семантическая функция приписывающая значение константам языка.

Модель - вероятная реализация языка.

Правила приписывания значений термам:

Значения термов – некие элементы из универсума.

Три типа термов:

α – предметные переменные

k – предметные константы

Фn (t1,t2,…,tn) – сложные многофункциональные термы

Значение терма t в модели m при приписывании значений Эвристические приемы поиска вывода в натуральном исчислении высказываний. φ:

Короткая запись- |t|mφ либо просто |t|φ

Для предметных переменных

| α | φ = φ (α)

Для предметных констант

| k | φ = I (k)

Для сложных термов

| Фn (t1,t2,…,tn) | φ = [ I(Ф)] ( | t1| φ,| t2| φ, ....| tn | φ)

4. Традиционная логика предикатов: правила приписывания значений формулам, понятия общезначимой и выполнимой формул, определение главных логических отношений меж формулами.
Значения, которые могут принимать формулы при интерпретации – правда (И) и Эвристические приемы поиска вывода в натуральном исчислении высказываний. ересь (Л)

Значения формул при интерпретации:

Атомарные формулы принимают значение Ив этом случае, если элементы огромного количества U, знаками которых являются термы t1,t2,…,tn, входящие в формулу, являются и элементами подмножества U, обозначенного предикатором Пn

| Пn (t1,t2,…,tn)| φ = И↔ <| t1| φ,| t2| φ, ....| tn | φ > I (Пn)

| Пn (t1,t2,…,tn)| φ = Л ↔ <| t1| φ,| t2| φ, ....| tn | φ > I (Пn )

Значение формулы Аобратно значению формулы Эвристические приемы поиска вывода в натуральном исчислении высказываний. А

| А| φ = И ↔ |А| φ = Л

| А| φ = Л ↔ |А| φ = И

Значение формулы А & В равно И в этом случае, если значение обоих формул, входящих в конъюнкцию, равно И, и равно Л во всех других случаях

|А & В| φ = И ↔ |А| φ = И &˚ |В| φ =И

|А & В| φ = Л ↔ |А| φ = Л ˚ |В| φ =Л

Значение формулы А В равно И в этом случае, если значение хоть одной Эвристические приемы поиска вывода в натуральном исчислении высказываний. из формул, входящих в нее, равно И

|А В|φ = И ↔ |А|φ = И ˚ |В|φ=И

|А В|φ = Л ↔ |А|φ = Л &˚ |В|φ=Л

Значение формулы А В равно И, если значение формулы антецедента равно Л либо значение консеквентна равно И

|А В|φ = И ↔ |А|φ = Л ˚ |В|φ=И

|А В|φ= Л ↔ |А|φ = И &˚ |В|φ=Л

Значение формулы α А равно И, если значение Эвристические приемы поиска вывода в натуральном исчислении высказываний. Хоть какой функции ψ,отличающейся от φ менее, чем приписыванием значения переменной α,равноИ

| α А|φ = И ↔ ˚ψ (ψ=αφ ˚ |A|ψ = И) ψ=αφ – приписывание ψ значения

| α А|φ = Л ↔ ˚ψ (ψ=αφ &˚ |A|ψ = Л)хорошего от φ менее, чем на α

Значение формулы Е α А, если значение ХОТЬ ОДНОЙ функции ψ,отличающейся от φ менее, чем приписыванием значения переменной α,равноИ

| α А|φ = И ↔ ˚ψ (ψ=αφ &˚ |A|ψ = И) ψ=αφ – приписывание ψ значения

| α А|φ = Л ↔ ˚ψ (ψ=αφ ˚ |A|ψ = Л Эвристические приемы поиска вывода в натуральном исчислении высказываний.)хорошего от φ менее, чем на α

Виды формул:

Закон (общезначимая формула) – это формула, принимающая значение И во всех моделях и при всех приписываемых значениях предметным переменным

╞ A ≡Df ˚U ˚I ˚φ |A|φ= И

Выполнимая формула – принимающая значение И в неких моделях и при неких приписываниях значений предметным переменным

Формула А выполнима Df ˚U ˚I ˚φ |A|φ= И

Неосуществимая формула – это формула, принимающая Эвристические приемы поиска вывода в натуральном исчислении высказываний. значение Л во всех моделях и при всех приписываемых значениях предметным переменным

Формула А неосуществима ≡Df ˚U ˚I ˚φ |A|φ= Л

Оспоримая формула - принимающая значение Л в неких моделях и при неких приписываниях значений предметным переменным

Формула А оспорима Df ˚U ˚I ˚φ |A|φ= Л

Формула А значима (истинна) в модели ≡Df ˚φ |A|φ = И

Формула Аобщезначима на огромном количестве U (U общезначима) ≡Df ˚I ˚φ |A|φ = И

Логические дела

Сопоставимость по истинности.

Формулы Эвристические приемы поиска вывода в натуральном исчислении высказываний. из Г совместимы по истинности в этом случае, если существует такая модель и такое приписывание значений переменным, при котором любая формула из Г воспримет значение И.

˚A (A Г ˚ ˚U ˚I ˚φ |A|φ = И )

Сопоставимость по ложности

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

˚A (A Г ˚ ˚U ˚I ˚φ |A|φ = Л)

Логическое следование.

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

Г ╞ B ↔ ˚U ˚I ˚φ ( ˚A (A Г ˚ |A|φ = И ) ˚ |В Эвристические приемы поиска вывода в натуральном исчислении высказываний.|φ = И)

Задачки, решаемые в логике предикатов перебором моделей

-обоснование выполнимости

- обоснование оспоримости

-соместимость по истинности и по ложности

Доказать общезначимости, невыполнимость, несопоставимость по И и Л либо отношение логического следования нереально.


evolyuciya-tehnologicheskih-ukladov-i-ciklichnost-innovacionnogo-razvitiya-ekonomiki.html
evolyuciya-tetrapod.html
evolyuciya-tvorenie-ili-promisl-v-zashitu-svyatootecheskogo-ucheniya-o-sotvorenii-mira-zhizni-i-cheloveka.html