Все шпоры по матлогике

(1)

Логика – это наука о законах и формах познающего мышления.

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

Матлогика – это логика использует мат. методы ми применяется в математике.

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

Компоненты формальных теорий:

А) Алфавит

Б) Формулы (вместе – формальный язык)

В)Аксиомы (система)

Г) Правила вывода – по этим правилам из одних верных формул, получаются другие верные формулы.

Опр1: ВЫСКАЗЫВАНИЕ – это утверждение, языковое предложение (не обязательно человека), это может быть выражен не алгоритм. Высказывание может быть либо true либо false.

Новое высказывание, построенное из элементарных высказываний, называется составным высказыванием.

Элементарные высказывания обозначаются пропозициональными переменными: A, B, C, либо с индексами A1, A2…..

Логические связки: ┐, ∩(&), V, →.

Опр1: ┐ ОТРИЦАНИЕ высказывания ┐A – истинно только тогда, когда А ложно. Читается как «не А», «неверно что А».

Опр2: ∩(&) КОНЬЮНКЦИЯ двух высказываний A & B – истинна тогда и только тогда, когда оба высказывания одновременно истинны. (A и B)

Опр3: V ДИЗЮНКЦИЯ двух высказываний A V B – ложна тогда и только тогда, когда оба высказывания одновременно ложны. (A и B)

Опр4: → ИМПЛИКАЦИЯ двух высказываний A → B – ложна тогда и только тогда, когда А истинно, а B ложно. («из А в B», «если A, то B»)

(2) Опр1: ФОРМУЛА (пропозициональная формула) – это составное (в том числе и элементарное высказывание), которое, используя алфавит пропозициональных переменных, строится согласно следующим правилам синтаксиса :

1.  Любая пропозициональная переменная – формула.

2.  Если A и B – то формулами будут являться ┐A, ┐B, A∩B(A&B), AVB, A→B

3.  Формулами будут являться только лишь те высказывания, которые построены по правилам 1 и 2

Опр2: ИНТЕРПРЕТАЦИЯ формулы А – определенное значение истинности формулы А, при подстановки истинностных значений, входящих в нее, пропозициональных переменных.

Пример таблицы истинности для формул:

(3) Опр1: Формула называется выполнимой, если она в некоторой интерпретации принимает значение логической единицы (1)

Опр2: Формула называется опровержимой, если она в данной интерпретации принимает значение логического нуля (0)

Опр3: Формула называется «общезначимой», «тождественно истинной» или «тавтологией» , если она во всех интерпритациях приримает истинное значение (1)

Опр4: Формула называется «невыполнимой»или «противоречивой» , если она во всех интерпретациях ложна (0)

Т1: Пусть А некоторая формула, тогда

1) если А тавтология, то ┐А противоречие, и наоборот.

2) если А противоречие, то ┐А тавтология, и наоборот.

3) если А тавтология, то неверно, что А противоречие, но не наоборот.

4) если А противоречие, то неверно, что А тавтологие, но не наоборот.

Док-во следует из определения

Т2: Если формулы А и (┐А→В) тавтологии, то В тавтология (частный случай правила вывода Modus Ponens)

Док-во методом от противного

а) I(B) = 0

б) I(A) = 1

в) I (А→В) = 1, то условие а противоречит б и в, так как по таблице истинности из 1 → 0 должен быть 0, а у нас 1, противоречие исходному предположению

Наиболее важные тавтологии:

1.  (А→А ) Закон исключенного третьего

2.  А→(В→А), (Аксиома ИВ А1)

3.  Ценное рассуждение (А→В) →((В→С) →(А→С))

4.  (A→(B→C))→((A→B)→(A→С)) (Аксиома ИВ А2)

5.  { ( A&B)→A; (A&B)→B }

6.  A→(B→(A&B))

7.  A→(A v B)=A→(┐┐A v B) =A→(┐A→B)=B→(A→B)

8.  Аксиома ИВ А3 (┐B→┐A)→((┐B→A)→B)

9.  Закон Пирса(((A→B)→A)→A)

(4) Опр1: Формула B является логическим следованием формулы A, если B — истинно при всех истинных интерпретациях формулы A.

Обозначается A=>B

Опр2: Формулы A и B эквивалентны, если они являются логическим следствием друг друга., иначе говоря, если совпадают их значения истинности во всех интерпретациях

Обозначается AóB или A∞B

Основные эквивалентности:

1.  A&B=B&A ; AvB=BvA (коммутативность или перестановка)

2.  A&A=A ; AvA=A (идемпотентность)

3.  (A&B)&C=A&(B&C) ; (AvB)vC= Av(BvC) (ассоциативность)

4.  A&(BvC)=(A&B)v(A&V) ; Av(B&C)= (AvB)&(AvC) (дистрибутивность)

5.  A&(AvB)=A ; Av(A&C) поглощение

6.  ┐┐A=A инволютивность

7.  ┐(A&B) = ┐A v ┐B ; ┐(AvB)=

┐A&┐B (Привила де’Моргана)

8.  (A&B)v(A&┐B)=A&(Bv┐B)=A&1=A ;(AvB)&(Av┐B)=Av(B&┐B)=Av0=A

9.  (A→B)= ┐AvB

10. (AóB)=(A→B)&(B→A)= (┐AvB)&(┐BvA)= ┐A & ┐B v A&B

10.  AvB= ┐┐AvB= ┐A→B

11.  A&B= ┐┐A& ┐┐B =

┐(┐A v ┐B )= ┐(A→B)

12.  Av0=A ; A&0=0

13.  Av1=1 ; A&1=A

14.  A v ┐A=1 (тавтология)

15.  A & ┐A=0 (противоречие)

Т1:

P­1 & P­2 & …… P­n =>Q

Эта формула является логическим следованием тогда и только тогда, когда эта формула является тавтологией.

Док-во:

1)  Необходимость:

Логическое следование является необходимым условием тавтологии. I(P­1 & P­2 & …… P­n)=1 (*) – так как эта формула является логическим следованием (по определению) должны выполняться интерпретации:

А)I(Q)=1 (**) ;I(P­1 & P­2 & …… P­n =>Q)=1

Б) I(P­1 & P­2 & …… P­n =>Q)=0

При любой интерпретации I(Q)=(1 или 0)

Видно, что эта формула тавтология.

2)  Достаточность:

Наоборот, дана тавтология, доказать логическое следование.

Достаточно приравнять интерпретации

I(P­1 & P­2 & …… P­n )=1 (*) и I(Q)=1 (**) (согласно определению лог. След.);

I(Q)=1 иначе это не тавтология.

Т2: P­1 & P­2 & …… P­n =>Q

Эта формула является логическим следованием тогда и только тогда, когда P­1 & P­2 & …… P­n & ┐Q является противоречием.

Док-во:

Доказывается на основе предыдущей теоремы, с использованием основной эквивалентности A&B= ┐(A→B)

(5) Опр1: Формальные теории — вначале разрабатывались для формализации логики и теории доказательства. Основа матлогики – ФТ.

Состав произвольной формальной теории Г:

1)  Множество А – символов алфавита (как конечное, так и бесконечное)

2)  F – множество слов в алфавите А. Эти слова иначе называются формулами. F может быть бесконечным.

Замечание1: Множества F и A обозначают ЯЗЫК – семантику.

3)  Множество B принадлежащее F – образует аксиомы (система аксиом)

4)  R – множество отношений r. R принадлежит R, и принадлежит Fn+1. R – называют правилами вывода.

Замечание2: Множество F строится индуктивным способом

Замечание3: Множество B может быть как конечным так и бесконечным, если оно бесконечно, то оно строится с помощью конечного множества схем аксиом и правил порождения конкретных аксиом.

Замечание4: Множество правил вывода R как правило конечно.

Опр2: Формула G называется выводимой формулой из формул F1 … Fn, по правилу вывода r, если существует такое правило вывода r, что (F1 … Fn, G) принадлежит r:

где G – заключение, F – послание.

Опр3: Выводом формулы G из формул F1…Fn формальной теории Г, называется последовательность формул, E1,E2…Ek, где Ek=G, а любая Ei(i<k) может быть:

1)  Ei=Fj, j=1,n

2)  Ei – какая либо из аксиом

3)  Ei – выводима непосредственно из Ej1,Ej2…Ejm, где jm<i

Символическое обозначение вывода: F1,F2…Fn├ Г G

Опр3: Вывод формулы G только лишь из аксиом называется Теоремой

Посылки в выводе называются гипотезами.

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

Если верен вывод , то верен и

Опр4: Интерпретацией ФТ в область интерпретаций М, будем называть отображение множества F во мн-во M:

I:F→M Если соответствующее высказывание является истинным, то говорят что формула выполняется в данной интерпретации

Опр4: I – называется моделью ФТ, если все ее теоремы выходят в интерпретацию I.

(6) Опр9: Формула G называется логическим следствием множества формул Г если формула G выполняется в любой модели Г

Опр: ФТ Г – называется семантически непротиворечивой, если ни одна ее теория не является противоречием.

Опр: ФТ Г – называется формально не противоречивой если в ней не являются одновременно выводимыми формулы F и ┐F

МЕТАТЕОРЕМА I : Модель для ФТ Г существует тогда и только тогда, когда Г семантически не противоречива.

МЕТАТЕОРЕМА II : ФТ Г формально не противоречиво тогда и только тогда, когда она семантически не противоречива

Опр: ФТ Г называется полной (или адекватной) если любому истинному высказыванию относительно М соответствует теорема в ФТ Г

Опр:Если для множества М существует формальная, полная и непротиворечивая теория, то М – называется аксиоматизируемым множеством (формализуемым множеством)

Опр:Система аксиом (аксиоматизация) формально не противоречивой теории Г называется независимой, если никакая из аксиом не выводима из остальных аксиом Г по правилу этой теории Г.

Опр: ФТ Г называется разрешимой, если существует алгоритм, который для любой формулы этой теории способен определить является ли эта формула теоремой этой теории.

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

(7) Опр1: Исчисление высказываний – это Формальная Теория L, в которой:

1)  Алфавит, кроме лог. связок, (┐, →, (, )):

a, b,c, d,e…..

A, B,C, D,E…

2)  Формулы:

a.  Любые переменные — это формулы

b.  Если A и B – формулы, то ┐A, ┐B, A→B – формулы

c.  Аксиомы А1,А2,А3:

А1: A→(B→A) – аксиома упрощения

А2: (A→(B→C))→((A→B)→(A→C)) – аксиома самодистрибутивности

А3: ((┐B→┐A)→((┐B→A)→B))

MP:= “Modus Ponens” (лат. «Правило вывода»)

Опр2: Если в формуле С:=А(X1…Xn) вместо переменных х1…хn осуществить групповую подстановку {Bi||Xi}i=1, то таким образом полученная формула называется частным случаем формулы A(X1…Xn), а само выражение называется УНИФИКАТОРОМ.

Опр3: Если формула C, является частным случаем формул A и C:=D(x1…xn), то формула C называется совместным частным случаем формул A и B, а сами формулы A и B называются унификаторами. Формула A набор??? называется общим унификатором, возможен он не один.

Наименьший унификатор называется наиболее общим унификатором.

Опр4: Набор формул B1…Bn называется частным случаем набор A1…An, если для любая формула Bi является частным случаем формулы Аi на одном и том же наборе подстановок.

Опр5: Набор C1…Cn является совместным частным случаем наборов A1..An и B1…Bn, если любая формула Ci является частным случаем формул Ai и Bi.

(8) Другие аксиоматизации:

1)  Гильберта — Аккерчона

2)  Россера

3)  Клини

4)  Никода

5)  Лучасевича

6)  Енсена

7)  Новикова

Аксиомы Клини:

A1: (A→(B→A))

A2: ((A→(B→C))→((A→B)→(A→C))

A3: (A→(AvB))

A4: (B→(AvB))

A5: ((A&B)→A)

A6: ((A&B)→B)

A7: ((A→B)→((A→ ┐B)→ ┐A))

A8: ((A→C)→((B→C)→((AvB)→C)))

A9: (A→(B→(A&B)))

A10: ┐┐A=A

Т1:

1)  Используя аксиому А1 и подстановку B:= A→A т. е. получим A→((A→A)→A)

2)  Используя аксиому A2 и подстановку {B:=A→A; C:=A} получим (A→((A→A)→A) → (A→(A→A)) → (A→A)

3)  Применяем MP

4)  Используя аксиому А1 и подстановку B:=A получим A→(A→A)

5)  Применяем MP

Т2:

1)  A – гипотеза

2)  A├A→(B→A)

3) 

Смысл теорем в получении произвольного правила вывода из правила MP, в качестве доказанной выводимости, которая называется введение имплекации, им. Условное обозначение:

(9) Т1 Теорема дедукции: Формула B – выводима из формулы A (доказуема) тогда и только тогда, когда выводима формула A→B. Если , то и наоборот.

I Доказательство прямой теоремы.

Необходимо доказать:

Если →последовательность формул, имеем вывод → имеем последовательность выводимых формул.

E1……En=B

Здесь возможны следующие частные случаи:

1)  E1-Аксиома

2)  E1 принадлежит Г

3)  E1=A

Доказательство метода математической дедукции, в соответствии с которым необходимо проверить, доказать вывод, , а так-же опирается на индуктивные предположени

,

на базе которого

Док. Вывода

1)  E1 – аксиома

2) 

3) 

E1,E1→(A→E1),A→E1

Доказательство 1-2 выглядит одинаково с помощью теоремы 2

1) ,

,

(подстановка {E1||A, A||B})

2) Аналогично первому

3) Для третьего случая используем теорему 1

Добавление лишних гипотез не меняет свойств выводимости

Доказаны все случаи 1, 2, 3 для стартового этапа метода математической индукции!

Верны индуктивные предположения:

, где i, j<k

E1,E2…Ei-1,Ei…Ek…En=B

Ek из последовательности вывода E1…E2 , т. е. из формул Ei и Ej, согласно основному правилу MP

Ej=Ei→Ek

, этот особый случай обозначим за (4’), а первые 3 случая абсолютно аналогично, как и для начального этапа.

Первые 3’ пункта доказываются по аналогии с пунктами, доказанными ранее, а для доказательства четвертого пункта используем аксиому А2(самодвойственность) с подстановкой {Ej||B, Ek||C}.

A2: (A→(B→C))→((A→B)→(A→C))

После подстановки получаем:

Еще раз применим MP:

Получим вывод в конечной форме которого:

Г, А├А→Ek

По методу математической индукции исходя из пунктов 1 и 2 справедлив вывод для любого К, даже k=n:

Г, А├А→En=B

ПРЯМАЯ ТЕОРЕМА ДОКАЗАНА!

II Обратная теорема

Дано: Г├А→B, необходимо доказать Г, A├B

1)  A – гипотеза

2)  A→B выводима по условию теоремы

3)