yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.9. Формализация и доказательство логического следования

Математическая логика

4.9. Формализация и доказательство логического следования

Пример. 4.1. На области определения "люди" заданы высказывания:

1. Все старые члены конгресса - юристы.              

2. Все женщины-юристы восхищаются каким-нибудь судьей.

3. Только судьи восхищаются судьями.

4. Все судьи восхищаются веема судьями.

Что думает судья Джонс по поводу своей старой тещи, которая является членом конгресса ? Ответ: Джоне восхищается своей тещей.

Построение доказательства начинается с формализации исходных предложений. Пусть х - предметная переменная, которая принимает значения из области определения. Введем предикаты: J(x): х г судья; L(х): х - юрист; С(х): х - член парламента; W(x): х - женщина; А(х,у): х восхищается у. Формализуем посылки:

1. x(O(x)&C(x) L(x))                        Все старые члены конгресса-юристы,

2. x(W(x)&Ax) y(J(y)&A(x,y)))    Все  женщины-юристы восхищаются каким-нибудь судьей.

3. xy(J(y)&A(x,y) J(x))     Только судьи восхищаются судьями.

4. x(J(x) y(J(y) A(x,y)))       Все судьи восхищаются всеми судьями.

Константы: 5. J(D) - судья Джонс, 6. W(T)&O(T)&C(T) - старая теща, член парламента. 1. Доказать: A(D,T) - судья Джонс восхищается тещей.

1. Доказательство методом от противного.

Предположим, что судья Джойс не восхищается тещей, т. е. [A(D,T)|=F. Тогда из того, что x(J(x) y(J(y) A(x,y))) |=T следует, что это истинно и: для Джонса и тещи: |j(D)  (J(T)- A(D,T)) |=T, откуда следует, что теща не судья: |J(T)|=F. |x(O(x)&C(x) L(x)) |=T, что справедливо и для тещи: |О(Т}&С(Т) |=Т, а поскольку |О(Т)|=Т . |О(T) |=Т, т. е. теща старая и член парламента, то |L(Т)|=Т, т. е. она юрист. Поскольку |x(W(x)&L(x) y(J(y)&A(x.y))) |=T, то |W(T) |=T&L(T) J(D)&A(T,D)|=T, где |W(T)|=T, |L(T)|=T, |J(D)|=T, следовательно, JA(T,D)|=T. Это уже противоречит нашему предположению, следовательно судья Джонс восхищается своей тещей.

Из посылки |J(D)&A(T,D)J(T)| следует также дополнительный вывод: |J(T)|=T, т. е., оказывается, теща тоже судья.

Формальный вывод:

1.  х(О(х)&С(х) Lх))                                                Г.1

2.  x(W(x)&L(x) y(J(y)&A(x,y)))              Г.2

3.  xy(J(y)&A(x,y) J(x))                            Г.3

4.  x{J(x) y(J(y) A(x,y)))                       Г.5

5.  W(T)&О(T)&C(T)                                             Г.6

     6.  J(D) y(J(y) A(D.y))                             УК(4)

7  y(J(y) A(D(y))                                           МР(5,7)

8.  J(T) A(D,T)                                                  УК(8)

9.  O(T)&C(T) L(T)                                           УК(1)

10. O(T)&C(T)                                                       уд.&(6)

11.  L(T)                                                                 МР(11, 10)

12. (W(T)&L(T) y(J{y)&A{T,y))                  УК(2)

13. W(T)                                                                 уд. &(6)

14. W(T)&L(T)                                                       МР(13,15)

15. J(a)&A(T,a)                                                      ЭК(16)

16. J(a)&A(T.a) J(T)                                          УК(3)

17. J(T)                                                                   МР(18,19)

18. A(D,T)                                                              МР(8, 19)

Пример 4.2. Некоторые студенты любят своих преподавателей. Никто не любит невежественных людей,  следовательно,  ни один преподаватель не является   невежественным.   Пусть    Р(х)    -    х    -    студент     D(x)    -    х преподаватель, Q(x) - х - невежественный, L(x,y) - х любит у. Посылки-

Fl: x(P(x)& y(D(y) Lx,y)))

F2: x(P(x) y(Q(y) ¬Lx,y)))

Следствие: G: y(D(y) ¬Q(y))

По определению |F1|=T, |F2|=Т. Предположим |G|=F

|y(D(y) ¬Q(y)) |существует у=а, такое что   |D(a) ¬Q(a)|=F |D(a) |=T, |¬Q(a) |=F|Q(a) |=T

F1: x(P(x)&(D(a) L(x,a))) |=Tx=b, |P(b)&(D(a) L(b,a)) |=T|P(b) |=T и |D(a) L(b,a) |=T

F2:   x(P(x)  (Q(a) ¬L(x.a))) |=T     x=b,   |P(b)  (Q(a) ¬L(b,a)) |=T,  из Fl: |P(b)|=T, следовательно |Q(а) ¬L(b,а)| =Т

Так    как     |D(a) |=T    и    |Q(a) |=T,    то    получаем,    что    истинны    оба утверждения: |TL(b,a) |=T и |Т¬L(b,a) |=Т, т. е. L(b,а)|=Т и Полученное противоречие доказывает логическое следование.

Формальный вывод:

1. x(P(x)& y(D(y) L(x,y)))                         Г1

2. х(Р(х) у(Q(y) ¬L(x,y)))                    Г2

3. х Р(х)                                                              Г3      4. Р(b)                                                                    ЭК(3)

5. (P(b)& y(D(y) L(b,y)))                              УК(1)

6. y(D(y) L(b,y))                                           МР(4,7)

7. P(b) у(Q(y) ¬L(b, y)))                          УК(2)

8. y(Q(y) ¬L(b,y)))                                        МР(4, 7)

9. (Q(z) ¬L(b, z))                                               УК(8)

10. D(z) L(b,z)                                                  УК(6)

11.L(b, z)) ¬Q(z)                                               контрапозиция (9)

12.D(z) ¬Q(z)                                                    силлогизм (10, 11)

13. y(D(y) ¬Q(y))                                          Gen(12)

 

 

 

 

30