Файл: В. Ф. Пономарев математическая логика.doc

г) “если я поеду автобусом и автобус опоздает, то я опоздаю на работу; если я опоздаю на работу и стану огорчаться, то я не попадусь на глаза моему начальнику; если я не сделаю в срок важную работу, то я начну огорчаться и попадусь на глаза моему начальнику. Следовательно, если я поеду автобусом, а автобус опоздает, то я сделаю в срок важную работу [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) Выполнить подстановку:

1. 
   _А ^BC(АB);
   
2. 
   _(BA  ^(BC))_А ^{(BA)} (ABC);
   
3. 
   _А^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).

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

1. 
   составить таблицу истинности; 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)

---

2. ЛОГИКА ПРЕДИКАТОВ

Если объект высказывания, т.е. о чем говорится в предложении, не определен, то это предложение называют высказывательной функцией. Аргументами высказывательной функции являются предметные переменные, которые обозначают строчными буквами латинского алфавита х, у, z Эта функция приобретет значение "и" или "л" только при подстановке в высказывательную функцию вместо предметных переменных их конкретных значений. Конкретные значения аргументов высказывательной функции называют предметными постоянными, которые обозначают строчными буквами латвийского ал­фавита а, в, с,  .

Высказывательную функцию иначе называют предикатом (лат. praedicatum - логическое сказуемое).

Например,

а) если на множестве натуральных чисел задать высказывательные функции или предикаты

Р₁(x):= "x - простое число",

P₂(6, y):="y меньше 6",

P₃(6, y, z):="z есть частное от деления числа 6 на y",

где z и y есть предметные переменные (целые числа), а 6 – предметная постоянная (целое число), то высказываниями будут

P₁(3) = и, P₁(4) = л,

P₂(6,2) = и, P₂(6,7) = л,

P₃(6,2,3) = и, P₃(6,2,5) = л,

б) если на множестве имен индивидов, университетов и специальностей задать высказывательные функции или предикаты

P₄(x):="х - студент",

P₅(x, КГТУ):="студент х университета КГТУ",

P₆(x, y, прикладная информатика):= "студент x университета y, обучающийся по специальности "прикладная информатика””,

где x и y есть предметные переменные, а КГТУ и “прикладная информатика” – предметные постоянные, то высказываниями будут

P₄(Петров) = и, P₄(Сидоров) = л,

P₅(Петров, КГТУ) = и, P₅(Сидоров, КГТУ) = л,

P₆(Петров, КГТУ, "прикладная информатика") = и,

P₆(Сидоров, КГТУ, "прикладная информатика") = л.

При ограничении области определения предметных переменных вводят операторы, которые называют кванторами.

Суждение, в котором утверждается или отрицается наличие каких-либо признаков или отношений у части предметных переменных области определения, называют частным суждением. Как правило, эти суждения на естественном язы­ке отражают словами “один”, "несколько", "часть" и т.п. Для формализации таких суждений используют логическую операцию, ограничивающую область определения предиката. Этот оператор по­лучил название квантора существования, который обозна­чают так: “_x”. Предикат записывают после квантора существования в круглых скобках

---

_x(Р_n(x)) На естественном языке эта запись означает: “существуют такие элементы х, что Рn(х) истинно (или ложно)".

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

_x, _y, _z,...(P_n(x, y, z, ...)).

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

Р(х₁,x₂ ,x₃,  x_n) = Рⁿ (х).
Например,

_x(P₁(x)):= "cуществуют целые числа, которые являются простыми". Это условие выделяет на множестве целых чисел подмножество X = {2, 3, 5, 7, 11, 13, 17,...}, для которого предикат P₁(x) принимает значение “и”.

_y(P²₂(6,y)):="существуют числа y, которые меньше 6". Это условие выделяет на множестве целых чисел подмножество

Y= {1, 2, 3, 4, 5}, для которого предикат P₂(6,y) принимает значение “и”.

_y(P³₃(6,2,z)):="существует число z, которое является частным от деления 6 на 2". Это условие выделяет на множестве целых чисел единственное число Z=3, для которого предикат P₃(6,2,z) принимает значение “и”.

Если P₇(x):="x имеет зачетную книжку", то

_x(P₄(x)&P₇(x)):= "существуют студенты (x), которые не имеют зачетной книжки";

_x_y(P²₅(x,y)& P₇(x)):="существуют студенты (x) некоторых университетов (y), которые не имеют зачетной книжки".

Суждение, в котором утверждается или отрицается наличие каких-либо признаков или отношений для всех предметных переменных области определения, называют общими суждениями. Как правило, эти сужде­ния в естественном языке отмечают словами "все", "каждый", "любой" и т.п. Для формализации этих суждений используют логическую операцию над всей областью определения предиката. Оператор этой логической операции получил название квантора всеобщности, который обозначают так: _x. Предикат записывают после квантора всеобщности в круглых скобках

_x(Р_n(x)) . На естественном языке эта формальная запись означает: “для всех х истинно (или ложно) значение Р_n(х)".

Если общее суждение распространяется на несколько предметных переменных, то перед предикатом записывают все предметные переменные, по которым есть общее суждение, т.е.

_x, _y, _z,... (P_n(x, y, z, ...)).

Например,

_x(P₄(x)&P₇

---

(x)):= "все (или каждый) студенты (x) имеют зачетную книжку";

_x(P₅(x, КГТУ)&P₇(x)):="все (или каждый) студенты (x) университета КГТУ имеют зачетную книжку";

_xy(P₅(x,y)&P₇(x)):="все (или каждый) студенты (x) всех (или каждого) университетов (y) имеют зачетную книжку";

_x(P³₆(x, КГТУ, "прикладная информатика")&P₇(x)):= "все (или каждый) студенты (x) университета КГТУ, обучающиеся по специальности "прикладная информатика", имеют зачетную книжку";

_xz(P³₆(x, КГТУ, z)&P₇(x)):= "все (или каждый) студенты (x) университета КГТУ, обучающиеся на всех специальностях (z), имеют зачетную книжку";

x_y_z(P³₆(x,y,z)&P₇(x)):= "все (или каждый) студенты (x) всех (или каждого) университетов (y), обучающиеся на всех (или каждой) специальностях (z), имеют зачетную книжку".

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

Например,

_xy(P²₂(x, y)):= "для всех целых чисел x существует меньшее число y".

_x_y_z(P³₃(x, y, z)):="для всех целых чисел x и y существует число z, которое является частным от деления x на y".

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

Например,

_y(P²₂(x,y)):="для всех целых чисел x существуют меньшие числа y". В этом примере x – свободная, а y –связанная переменные.

x z(P³₆(x,y,z)&P₇(x)):= “есть студенты университета, которые не имеют зачетной книжки”. В этом примере x и z –связанные, а y –свободная переменные.

_x _y (Р²₁ (x; y)  _z (Р₂(z)) все пред­метные переменные связаны.

_z (Р₁(z)_x(Р²₂(x; z))(Р²₂(z; y)(Р²₂(x; z)) предметные переменные x и z связанные, а y – свободная.

Р₁ (z)(_x (Р²₂( x; z ))_y (Р²₂(z; y))) предметные переменные x, y-связанные, а z – свободная.

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

Если высказывательная функция содержит один аргумент, то задан

---

одноместный предикат, если она содержит n аргументов, то - n-местный предикат. Одноместный предикат, как правило, описывает наличие какого-либо признака у предмета, а предмета, а n-местный предикат наличие отношений между n предметами.

Пример: Если P₁(х) – одноместный предикат “ быть простым числом", то для х=5 имеем высказывание “верно, что 5-простое число" или Р₁(5)=и, а для x=4 имеем высказывание “неверно, что 4-простое число" или Р₁(4)=л.

Пример: Если Р₄(х) – одноместный предикат "быть студентом", то для х=”Петров” имеем высказывание “верно, что Петров - студент" или Р₄(Петров)=и, а для x=”Сидоров” имеем высказывание “неверно, что Сидоров – студент” или P₄(Сидоров)=л.

Пример: Если Р²₈(х; у) – двухместный предикат "студент x находится в аудито­рии y", то для х="Петров" и у="аудитория_382" имеем Р(Петров, аудитория_382) имеем высказывание "Студент Петров находится в ауди­тории 382", или Р²₈(Петров, аудитория 382)=и.

Пример: Если Р³₉(х; у; z) - предикат "z равен сумме чи­сел х и у", то для х=5 имеем высказывательную функцию “существуют такие z и y, что z равен сумме 5 и y” или _y_zР³₉(5; у; z), для х=5 и у=2 имеем высказывательную функцию “существует такое z, которое равно сумме 5 и 2 или _zР³₉(5; 2; z), а для х=5, у=2 и z =7 имеем высказывание Р³₉(5; 2; 7).

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

Между элементами области определения может быть задана некоторая структура или установлены какие-то функциональные отношения. Тогда функциональный символ f указывает на задание этого отношения между предметными переменными и/или предметными постоянными области определения, а для обозначения числа аргументов этого отношения ис­пользуют верхние индексы, т.е. fⁿ(x₁, x₂,...x_n).

Например, дату для Prolog-программы можно рассматривать как структуру, заданную на предметных переменных: число, месяц и год. В этом случае функциональным символом является слово “дата”, а аргументами число, месяц и год, т.е.

“дата(число, месяц, год)”.

Для предметных постоянных эта структура формирует выражение (например, “дата (1 января 2001)”), при подстановке которого в предикат определяет истинность или ложность высказывания.

Треугольник на плоскости также можно рассматривать для Prolog-программы как структуру на предметных переменных, описывающих координаты вершин треугольника. Тогда функциональным символом является слово “треугольник”, а аргументами этой функции - вершина(координаты_x,y), вершина(координаты x,y), вершина(координаты_x,y), т.е.

---