Студопедия
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Доказательство.

Читайте также:
  1. Доказательство.
  2. Доказательство.
  3. Доказательство.
  4. Доказательство.
  5. Закон Харди- Вайнберга, его математическое доказательство.
  6. Математическое доказательство.

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

А→В

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

Согласно Лемме1 можно сформулировать другое определение логического следствия, а именно:

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

G (F1, F2,…Fn)

(F1&F2&...&Fn) → G (*)

F1&F2&...&Fn (**)

Докажем необходимость

Предположим чтоG является логическим следствием F1, F2,…Fn. Требуется доказать что (*) – тавтология.

Пусть I – произвольная интерпретация.

Если все формулы F1, F2,…Fn истина на I

I(f1)=I(F2)=….I(Fn)=И и по определению логического следствия I(G)=И, то формула (*) – истина.

Если хотя бы одна из F принимает значение Л, то (*) все равно Истина(т.к. Л→И). Следовательно формула (*) - тавтология.

Докажем достаточность.

Предположим, что (*) - тавтология. Надо доказать что G является логическим следствием.

Для всякой интерпретации I, на которой все Fi истинны, формула (**) тоже истинна, и поскольку (*) - тавтология, G - тоже истинна..

Теорема Формула G является логическим следствием формул F1, F2,... Fn тогда и только тогда, когда формула F1&F2&...&Fn→ ךG является противоречием.

 

11. Силлогизмы с точки зрения формальной теории.

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

Схема силлогизма Название Пример
modus ponens (правило спуска) Если идет дождь, то на небе туча. Идет дождь, следователь на небе туча.
доказательство от противного Если заболел, то чихаю. Не чихаю, следовательно не болею.
дизъюнктивный силлогизм Мальчик или девочка. Не мальчик, следовательно девочка.
гипотетический силлогизм Если заболел, то чихнул. Если чихнул, то заразил, следовательно если заболел, то заразил.
простая конструктивная дилемма Если проспал, то опоздал, если не доехал, то опоздал. Если и то и то, то опоздал.
сложная конструктивная дилемма  
простая деструктивная дилемма  
сложная деструктивная дилемма  

12. Формальная теория для исчисления высказываний.

Дадим определение такой теории:

1. Алфавит: Ā={┐, →, (,), A, B…..}

2. Формулы:

• A,B,C - все пропозициональные буквы суть формулы;

• если А и В - формулы, то (ךA), (A→B) - тоже формулы.

3. Схемы аксиом:

B1: (A→ (B→ A)) → (А→В) → (А→С))

B2: (A→ (B → C))

B3: ((┐B → ┐A) → (┐B→A) → B))

4. Правила вывода:

Modus ponens:

R1:

 

R2: ∏Qp F (p) =F (Q)

 

5. Подстановка: из формулы F(A), содержащей букву А выводима другая формула F(G), полученная заменой А на G. Другие связки вводятся с помощью определений:

 

A&B = ┐(A→┐B)

AVB=┐A→B

А≡В=(А→В)&(В→А)

 

 

Докажем вывод в предложенной теории формулы A→A

 

1.Подставляем А вместо С в аксиому B1.

F1: (A→ (B→A)) → ((A→B) → (A→A))

2. Используем правило R1: в качестве первой посылки берем F1, а в качестве второй - аксиому (В1):

F2: (A → B) → (A → A)

3. В формулу F2 вместо В подставляем B → A:

F3: (A→ (B→ A)) → (A →A)

4. Используем R1: первая посылка - формула F3, вторая – аксиома (В2).

F4: A→A.

Свойства:

1) Все теоремы Исчисления Высказывания являются тавтологиями ׀=F

2) Исчисления Высказывания является полной теорией если в ней можно повторить либо формулу F либо ┐F

3) Исчисления Высказывания непротиворечивая теория если в ней недоказуемая формула F&┐F

 

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

Метод резолюций используется для проверки того факта, что F является тавтологией. Метод резолюций позволяет рассмотреть формулу ┐F и доказать, что это противоречие формула.

Описание метода:

Для того, чтобы доказать, что формула F является тавтологией, необходимо рассмотреть формулу ┐F и доказать, что это противоречие формула.

 

┐F приводится к конъюнктивной нормальной форме, которая представляет собой формулу, записанную в виде конъюнкций элементарных дизъюнкций: ┐F=D1&D2&Dn, таким образом, формируется множество дизъюнкций. Di,j – этого множества, содержащее переменную и её отрицание формируют треть D – РЕЗОЛЬВЕНТА.

Di=Di V Y

Dj=Dj V ┐Y

Di V Dj = Di’ V Dj’

Если Di = Y, Dj = ┐Y

Di V Dj = 

 

Неоднократно применяя правило резолюции к множеству дизъюнкций стремятся получить пустую резольвенту, что говорит о противоречии ┐F следовательно о тавтологии F. Если пустую резольвенту получить не удалось, то рассуждение не корректно.

 

Задача

В исходных формулах избавляемся от всех операций кроме отрицания и дизъюнкций.

(P →Q) = (┐P V Q)

F1: ┐(┐A) V ┐B = A V ┐B

F2: ┐(┐C) V ┐A = C V ┐A

F3: B

G: ┐C

Заменяем G на её отрицание. Получаем множество дизъюнкций

{ (A V ┐B), (C V ┐A), B, ┐C }

D1 D2 D3 D4

Образуем резольвенты

D5 = D1 V D2 = A V ┐B V C V ┐A = (┐B V C)

D6 = D4 V D5 = ┐B V C V ┐C = ┐B

D7 = D6 V D3 = ┐B V B = 

 

Задача

В хоккей играют настоящие мужчины, трус не играет в хоккей, я не играю в хоккей, значит я трус.

Х – я играю в хоккей

М - я мужчина

F1: М V ┐X, X→M

F2: M V ┐X

F3: ┐X

G: ┐M

 

Если взять ┐ => (M), то получим множество дизъюнкций, из которых не возможно получить ни одной резольвенты, значит высказывание некорректно.

 

 

14. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов.

Логика предикатов – это высказывание, зависящее от параметров. Таким образом, предикат - это высказывание-функция, значение (истина/ложь) которого зависит от параметров.

х >2 Р(х)= {ИЛ

х > y; P(2,6)= Л

P(6,0)= И

Предикатная форма может строится из следующих элементов:

1) х, у, ….. – переменные

2) Р(), Q() – предикаты

3) А, В, … - константы

4) ┐, &, V, →, ≡ логические связи

5) , - кванты (существование и т. д.)




Дата добавления: 2015-05-05; просмотров: 87 | Поможем написать вашу работу | Нарушение авторских прав

Алфавиты, слова, языки | Удаление и восстановление скобок в ПФ | Попытка док-ва Геделя. | Оценка сложности алгоритма | Классификация по сложности |


lektsii.net - Лекции.Нет - 2014-2025 год. (0.014 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав