Читайте также: |
|
Лемма 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 | Поможем написать вашу работу | Нарушение авторских прав |