Математическая логика: часть 1 - Учебное пособие (Пономарев В.Ф.)

1.6 описание высказываний на языке prolog

          Для программирования задач исчисления высказываний используют язык программирования Prolog.Само название Prolog есть сокращение, означающее программирование в терминах логики.

Пролог-программа состоит из предложений, которые бывают трех типов: факты, правила и вопросы.

Факты есть высказывания, которые заканчиваются точкой и имеют значение только “и”. Структура такого предложения описана предикатом или n-местным отношением, все аргументы которого есть термы или предметные постоянные. Предметные постоянные на языке PROLOG называют атомами. Термы описывают структуру или какие-то функциональные отношения между атомами. Предметные постоянные всегда начинаются со сточной буквы латинского алфавита и представляют собой последовательность букв, цифр и знака подчеркивания.

Например,

простое_число(3).

Это есть высказывание A1 (см. с. 5), структура которого описана предикатом P1(x):=”x-простое число”, где x=3 есть атом.

частное_от_деления(6, 2, 3).

Это есть высказывание Е (см. с.6), структура которого описана предикатом P3(x, y, z):=”z есть частное от деления числа x на y”, где x=6, y=2, z=3 есть атомы.

студент_университета,_обучающийся_по_специальности(Петров, КГТУ, прикладная информатика").

Это есть высказывание, структура которого описана предикатом

P6(x, y, z):= "студент x университета y, обучающийся по специальности z”, где x=”Петров”, y=”КГТУ”, z=”прикладная информатика” есть атомы.

родословная русских князей X века:

отец(игорь, святослав).

отец(святослав,владимир).

отец(владимир, борис).

отец(владимир,глеб).

дед(игорь, владимир).

дед(святослав, борис).

дед(святослав, глеб).

брат(борис,глеб).,

 

где игорь, святослав, владимир, борис, глеб есть атомы.Правила есть предложения, истинность которых зависит от истинности условий: “если истинны условия (посылки), то истинно и заключение (вывод)”.

На языке Prolog эти правила записывают так:

<заключение>:- <условия>.

Символ “:-“ соответствует символу обратной импликации ”¬”.

Левую часть правила называют головой предложения, а правую – телом предложения. В теле предложения перечисляют условия, определяющие вывод заключения. Если условия имеют между собой конъюнктивную связь, то между ними ставится запятая  “,”. Если условия в правиле имеют между собой дизъюнктивную связь, то между ними ставится точка с запятой (“;”). Голова предложения всегда сдвинута влево относительно перечня условий. Каждое условие начинается с новой строки.

Например, для родословной русских князей X века имеем:

дед(игорь, владимир):-

отец(игорь, святослав),

отец(святослав, владимир).

Это - высказывание о том, что если игорь был отцом святослава, а святослав – отцом владимира, то игорь был дедом владимиру.

дед(святослав, борис); дед(святослав, глеб):-отец(святослав,владимир),

отец(владимир, борис);

отец(святослав,владимир),

 отец(владимир,глеб).

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

брат(борис, глеб):-.

родитель (владимир, борис),

 родитель (владимир,глеб).

Это есть высказывание о том, что если владимир был отцом бориса и отцом глеба, то борис и глеб были братьями

 

.        

 

         

Контрольные вопросы

1) Запишите символически следующие суждения:

а) “вертолет является средством передвижения по воздуху, имеет двигатель, пилотскую кабину, систему управления, несущий винт, по­мещение для пассажиров или грузов”;

б) “подготовка специалистов высокой квалификации возможна лишь на базе всемерного развития вузовской науки, усиления связи вузов­ской, академической и отраслевой науки, обеспечения единства науч­ной и учебной работы, широкого привлечения студентов к научным ис­следованиям" ;

в) "хлеба уцелеют в различных климатических и погодных усло -виях тогда и только тогда, когда будут выполнены все мелиоративные работы; если хлеба не уцелеют, то фермеры обанкротятся и оставят фермы; следовательно, необходимо выполнить все мелиоративные работы"[15].

г) “если я поеду автобусом и автобус опоздает, то я опоздаю на работу; если я опоздаю на работу и стану огорчаться, то я не попадусь на глаза моему начальнику; если я не сделаю в срок важную работу, то я начну огорчаться и попадусь на глаза моему начальнику. Следовательно, если я поеду автобусом, а автобус опоздает, то я сделаю в срок важную работу [1]”.

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

 а) (AÚB)&(AÚùB)=A;

б) (AÚB)&(BÚC)&(CÚA)=(A&B)Ú(B&C)Ú(C&A);

в) (AÚB)&(AÚC)&(BÚD)&(CÚD)=((A&D)Ú(B&C)).

3) Приведите к дизъюнктивной и конъюнктивной нормальным формам: а) а)(((A®B)®(C®ùA))®(ùB®ùC));

б) (((((A®B)®ùA)®ùB)®ùC)®C);

в) (A®(B®C))®(A®ùC)®(A®ùB).

4) Выполнить подстановку:

Аò B&C(АÚB);

(ùB®ùA ò (BÚC))Аò (ùB®ùA) (A®BÚC);

АòB (A®B) ® (ùB®ùA)

4) Докажите выводимость заключения методов дедукции:

а)       (AÚB); (A®C); (B®D)

( C Ú D ).

б)      (ùAÚB); (C®ùB)   

( A® ù C ).

в)      ((AÚB)®(C&D)); ((DÚE)®F) 

(A®F).

5) Докажите выводимость заключения по принципу резолюции:

а)      ( AÚB); (A®B); (B®A)  

(A&B).

б)      (A®B); (C®D); (AÚC); (A®ùD); (C®ùD)  

(D«ùB).

в)      (A®B); (C®ùB)  .

(A®ùC).

 

 

Расчетно-графическая работа

составить таблицу истинности; 2) доказать истинность заключения методом дедукции и нарисовать граф дедуктивного вывода; 3) доказать истинность заключения по принципу резолюции и нарисовать граф вывода пустой резольвенты.

 

Вариант

Доказать истинность заключения

1.

(B®A); (B®(ùAÚC)) |¾ (B®(ùBÚC))

2

(ùAÚB); (CÚùB) |¾ (A®C)Ú(A®ùC)

3.

(ùAÚùB) |¾ (ù B®A)Ú(А®С)

4.

(A®B) |¾ ((ùBÚC)®(ùAÚC))

5

(A®B); (C®D) |¾ (A&C®B&D)

6

(A®B); (ù A®B) |¾ BÚ (A®C)

7.

(B®A); (B®(A®C)) |¾ (B®C)

8.

(A®B) |¾ (ùC®A)®( ùC®B)

9

(A®B); (A®(ùBÚC)) |¾ (A®C)

10.

(A&BÚùA&ùB) |¾ (A®C)«(B®C)

11.

(A®(B®C));(A®B);A |¾ C

12.

(A&B®C) |¾ (A®(B®C))

13.

(B®(A®C)); (B®A) |¾ (B®(B®C))

14

(A&BÚC&D); (A®ù A) |¾ C

15.

(A®(B®C)); (ù DÚA);B |¾ (D®C)

16.

(AÚB); (A®C); (B®D) |¾ CÚD

17.

(A®B); (C®B); (D®(AÚC)); D |¾ B

18.

(A®B); (B®C); (C®D) |¾ (A®D)

19

(B®(A®C)); (B®A) |¾ (B®(B®C))

20

(A®(C®B)); (ù DÚA); C; D |¾ D®B

21

(A«B) |¾ (CÚA)«(CÚB)

22.

A; (A®B) |¾ (C&A®B&C)

23

(A®B); ù (BÚC) |¾ ù A

24

(A®(B®C)); (ù DÚA);B |¾ (D®C)

25

(AÚC); (A®B);A |¾ (AÚC)®(BÚC)

26

(A®(B®C)); (A®B) |¾ (A®C)

27

(ù AÚB); (C®ù B) |¾ A®ù C

28

C; (A®B) |¾ ((C®A)®(C®B))

29

(A®(B®C)) |¾ ((A&B)® C)

30

(A®B) |¾ A&C®B&C

31.

(A®(B®C)); (ù DÚA);B |¾ (D®C)

32.

(A®B); (B®C); (C®D) |¾ (A®D)

33.

(B® (A®C)); (B®A) |¾ (B®C)

34.

(A®B) |¾ (A&C)®B&C)

35.

(B®(A®C)); (B®A) |¾ (B®(B®C))

36.

(A®(B®C); (A®B) |¾ (A®(A®C))

37.

(B®(A®C)); (B®A) |¾ (B®(B®C)

38.

(A®C); (B®A) |¾ (ù C&B)

39.

(A®B); (C®B); (D®(AÚC)); D |¾ B

40.

(A®B)|¾ (ù AÚù CÚB&C)

41.

(B®(A®C)); (B®A) |¾ (B®(B®C))

42.

(A&B®C) |¾ (A®(B®C))

43

(A®(B®C)); (ù DÚA);B |¾ (D®C)

44.

(A®(B®C));(A®B);A |¾ C

45.

(A®(B®C)); (A®B) |¾ (A®C)

46.

(A®(B®C)) |¾ (B®(A®C))

47.

(A®B); (B®C); (C®D) |¾ (A®D)

48.

(A®B) |¾ (AÚC)®(BÚC)

49.

(A®B); B |¾ ù A&ù CÚBÚC

50.

(A«B) |¾ (A®C)«(B®C)