Шпаргалка по "Логике"

Этапы развития логики

1-й  этап связан с работами  Аристотеля (384-322 гг. до н.э.). Он дал систематическое изложение логики ( формальная логика или  Аристотелева логика).

• Формальная логика связана с анализом  умозаключений.
• Аристотель  ввел понятие силлогизма, т.е. рассуждения, в котором из заданных двух суждений выводится третье.

2-й  этап - появление математической или символической логики.

• Математическая логика возникла на стыке двух наук: традиционной или философской логики и математики.
• Основы ее заложил немецкий ученый и философ Готфрид Вильгельм Лейбниц (1646-1716) (нем). Он создал алгебру высказываний.
• Джордж Буль (анг)(1815-1864). Буль считается основоположником математической логики как самостоятельной дисциплины.
• В его работах  логика обрела свой алфавит, орфографию и грамматику.

3-й  этап –этап парадоксов.

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

Определение высказывания:

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

оценены как истинные или ложные (напр. повествовательные предложения). Пример: “Колумб открыл Америку” – истина; “Киев – столица Узбекистана” - ложь.

Иногда  истинность/ложность высказывания зависит  от контекста.

Правила образования ППФ:

1) А - ППФ;

2) если  А и В – ППФ, то (A), (А&В), (А В), (А В), A↔B – также ППФ.

3) других  ППФ не существует.

Конъюнкцией двух высказываний А и В, называется высказывание А&В которое истинно тогда и только тогда, когда истинны одновременно оба высказывания (союз и)

Дизъюнкцией двух высказываний А и В называется высказывание А\/В, которое ложно тогда и только тогда, когда ложны одновременно оба высказывания (союз или)

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

Эквивалентностью двух высказываний А и В называется высказывание А↔В, которое истинно тогда и только тогда, когда оба данных высказывания имеют одинаковые значения, т.е. либо оба истинны, либо оба ложны (тогда и только тогда)

Отрицанием высказывания А называется высказывание А\, которое истинно тогда и только тогда, когда А ложно

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

ДНФ – дизъюнкция конъюнктов ( )/

КНФ – конъюнкция дизъюнктов ( ).

Алгоритм  приведения формулы  к ДНФ/КНФ:

1. Выражают  все логические операции в  формуле через дизъюнкцию, конъюнкцию  и отрицание.

2. Используя  законы Де-Моргана переносят все  отрицания к переменным и сокращают  двойные отрицания.

3. Используют  закон дистрибутивности конъюнкции/дизьюнкции  относительно дизъюнкции/коньюнкции, преобразуют формулу так, чтобы  все конъюнкции/дизьюнкции встречались  раньше дизъюнкции/коньюнкции.

4. Сократить  полученную ДНФ/КНФ, применяя  законы склеивания и поглощения.

5. Удалить  одинаковые дизьюнкты/коньюнкты.

Одночлен  называется совершенным, если каждая входящая в него переменная входит в него ровно один раз со знаком отрицания или без него.

СДНФ некоторой формулы называется дизъюнкция конституант единицы среди которых нет одинаковых.

СКНФ некоторой формулы называется конъюнкция некоторых конституант нуля среди которых нет одинаковых.

Алгоритм  построения по таблицам истинности СДНФ/СКНФ:

1. Выбрать  строку, на которой формула = 1/0.

2. Получить совершенный коньюнкт/дизьюнкт, включая в него с отрицанием те переменные, которые в этой интерпретации равны 0/1.

3. Перейти  к следующей строке, на которой  формула = 1/0.

4. После  перебора всех строк составить  СДНФ/СКНФ из полученных коньюнктов/дизьюнктов.

Классификация формул

Формула F(X1,X2,…,Xn) называется выполнимой (опровержимой), если существует её истинная (ложная) интерпретация/выполняется хотя бы на одном наборе.

Формула F(X1,X2,…,Xn) называется тавтологией (противоречием), если любая её интерпретация истинна (ложна). Если тавт. то ╞F(X1,X2,…,Xn)

Равносильность

Две формулы  F(X1,X2,…,Xn),G(X1,X2,…,Xn), будем называть равносильными, если для любых конкретных высказываний А1,А2,….,Аn их интерпретации совпадают, т.е. F(А1,А2,…,Аn)=G(A1,A2,…An) //формулы равносильны, если совпадают их таблицы истинности.

-Другие замечательные тождества.

Связь операций:

A=>B ≡ 7A V B

A↔B  = (A→B) & (В→А)

A & В ≡ 7(A => 7B)

A v В ≡ 7A→B  
 

Любая формула равносильными преобразованиями может быть приведена к д.н.ф.(к.н.ф.)

Из определений  д.н.ф. и к.н.ф. видно, что в любой  д.н.ф., к.н.ф. участвуют только операции вида ‾,\/,&, причём отрицание может  встречаться только над переменными. Отсюда равносильными преобразованиями ф-лы  F(X1,X2,…,Xn) привод. Её к к.н.ф., д.н.ф. явл-ся :

1. X→Y≡(X\)\/Y, X↔Y≡((X\)\/Y)&((Y\)\/X)
2. (X&Y)\≡(X\)\/(Y\), (X\/Y)\≡(X\)&(Y\)
3. X&(Y\/Z)≡X&Y\/X&Z (X\/(Y&Z)≡(X\/Y)&(X\/Z))

Логическое  следование: Формула G(x₁,x₂,…,x_n) называется логическим следствием формулы F(x₁,x₂,…,x_n), если для любых конкрет. высказываний А₁,А₂,…,А_n из истинности F(A₁,…,A_n) следует истинность G(А₁,А₂,…,А_n). Обознач.:F├ G

Хорновский  дизъюнкт - это дизъюнкт, содержащий не более одной литеры без отрицания. Хорновский дизъюнкт называется точным, если он содержит одну позитивную литеру. Если он не содержит позитивных литер, то называется негативным. Унитарный позитивный хорновский дизъюнкт представляет собой некоторый факт.

Задача  проверки выводимости сводится к проверке на тождественную истинность. Существует несколько десятков методов и алгоритмов установления тождественной истинности логической формулы.

1. Алгоритм Квайна (Квайн. 1960 г. США):

Идея: при  последовательных подстановках значений переменных можно уменьшить длину  формулы, исходя из совокупности проведённых проверок истинности F, и тем самым сокращать число переменных для проверки. Вводится понятие дерева испытаний, которое по сути дела представляет собой граф всех интерпретаций проверяемой формулы . Квайн назвал его «семантическим деревом». Пример: Пусть необходимо проверить общезначимость формулы . ИДЗ: ППФ 
 

Метод резолюций для  логики высказываний

       Метод резолюций можно применять  к любому множеству дизъюнктов  с целью проверки их невыполнимости (противоречивости). Идея принципа резолюции заключается в проверке, выводим ли из дизъюнктов, составляющих КНФ K(X₁, X₂,…,X_n,), пустой дизъюнкт. Вывод конструируется последовательным построением резольвент. Выводимость из КНФ пустого дизъюнкта означает ее противоречивость.Рассмотрим сначала метод резолюций для логики высказываний.

    Литеры A и ~A называются контрарными, а множество {A, ~A} – контрарной парой.

    Допустим, что в дизъюнкте C1 существует литера L1 , контрарная литере L2 в дизъюнкте C2. Вычеркнем литеры L1 и L2 из дизъюнктов C1 и C2 соответственно и построим дизъюнкцию оставшихся дизъюнктов. Построенный дизъюнкт называется резольвентой дизъюнктов C1 и C2. Резольвента двух дизъюнктов является их логическим следствием. Резольвента двух единичных дизъюнктов (если она существует) – пустой дизъюнкт.

    Резолютивный вывод C из множества дизъюнктов S есть такая конечная последовательность C1, C2, ..., Ck дизъюнктов, в которой каждый Ci (i=1, ..., k) или принадлежит S, или является резольвентой дизъюнктов, предшествующих Ci и Ck=C.

Метод семантической резолюции предусматривает, что при образовании каждой следующей резольвенты используется один дизъюнкт множества S₁и один дизъюнкт множества S₂ .

Свойства  дедуктивных теорий:

Противоречивость

Теория, в которой множество теорем покрывает всё множество формул (все формулы являются теоремами, «истинными высказываниями»), называется противоречивой. В противном случае теория называется непротиворечивой. Выяснение противоречивости теории — одна из важнейших и иногда сложнейших задач формальной логики. После выяснения противоречивости теория, как правило, не имеет дальнейшего ни теоретического, ни практического применения.

Полнота

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

Независимость аксиом

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

Разрешимость

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

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

• Всякая аксиоматическая теория для ее обоснования требует рассмотрения четырех проблем:
• проблемы разрешимости,
• проблемы непротиворечивости,
• проблемы полноты,
• проблемы независимости.

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

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

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

Док-во:

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

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

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

• Иначе говоря, аксиоматическое исчисление называется непротиворечивым, если в нем не существует такая формула А, что доказуема как формула А, так и формула не А.
• Если в исчислении обнаруживаются доказуемые формулы вида А и не А, то такое исчисление называется противоречивым.