Решение задач по логике и исчислению высказываний - Курсовая работа

В таблице истинности жирным шрифтом выделены столбцы с посылками, а жирным и курсивом выделено заключение. A - эта формула остается без изменений; Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода): Построим граф дедуктивного вывода. Упростить посылки и заключения, т.е. привести их к базисному множеству {O, &, U} с минимальным числом операций: F1=А - формула остается без изменений; Привести посылки и заключение к базисам {O, &} и {O, U}: Базис {O, U}: F1=А - формула остается без изменений;В результате проделанной работы, били закреплены практические навыки решения задач по математической логике.

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

Задачей работы является решение (на основе приобретенных знаний и изучения специальной и нормативно-методической литературы) задач по логике и исчислению высказываний, логике и исчислению предикатов, реляционной логике.

1 Решение задач по алгебре и исчислению высказываний

1. Выполнить задания по алгебре высказываний и исчислению высказываний: Вариант 22: {A; AAB} | - (C&A) a (B&C)

Обозначим: 1=А; 2=B; 3=C; 4=AAB; 5=C&A; 6= B&C; 7= 5a6;

a. Построить таблицу истинности: A B C 1a2 3&1 2&3 5a6

1 2 3 4 5 6 7

1 1 1 1 1 1 1

1 1 0 1 0 0 1

1 0 1 0 1 0 0

1 0 0 0 0 0 1

0 1 1 1 0 1 1

0 1 0 1 0 0 1

0 0 1 1 0 0 1

0 0 0 1 0 0 1

В таблице истинности жирным шрифтом выделены столбцы с посылками, а жирным и курсивом выделено заключение. Смотря на те строчки, в которых истины все посылки одновременно (в данном случае это первая и вторая, которые выделены жирной рамкой), видно, что заключение также истинно. Поэтому можно сделать вывод, что данное заключение выводимо из данного множества посылок. б. Упростить посылки и заключения, т.е. привести их к базисному множеству {O, &, U} с минимальным числом операций: F1 = A - эта формула остается без изменений;

F2 = AAB = OAUB;

F3 = (C&A) a (B&C) = O(C&A) U (B&C) = OC U OA U (B&C);

в. Привести посылки и заключение к базисам {O, &} и {O, U}: Базис {O, &}: F1 = A - эта формула остается без изменений;

F2 = AAB = O(A&OB);

F3 = (C&A) a (B&C) = O((C&A) & O(B&C)) = O(C & A & O(B&C));

Базис {O, U}: F1 = A - эта формула остается без изменений;

F2 = AAB = OAUB;

F3 = (C&A) a (B&C) = O(C&A) U (B&C) = OC U OA U (B&C) = OC U U OA U O(OBUOC);

г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ: КНФ: F1 = A - эта формула остается без изменений;

F2 = AAB = (OAUB) &;

F3 = (C&A) a (B&C) = O (C&A) v (B&C) = (OC VOA) V (B&C) =

= (OCV OA) V (B&C) = (OC V OA V B)&(OCVOAVC) =(OCV OAVB)& &(OA);

ДНФ: F1 = A - эта формула остается без изменений;

F2 = AAB = (O(A&OB)) U;

F3 = (C&A) a (B&C) = O((C&A) & O(B&C)) = O(O(C&A) U (B&C));

СКНФ: СКНФ строится по значениям «л» заключения в таблице истинности;

F3 = (C&A) a (B&C) = (AUOBUC)&;

СДНФ: СДНФ строится по значениям «и» заключения в таблице истинности;

F3 = (C&A) a (B&C) = (A&B&C) U (A&B&OC) U (A&OB&OC) U U (OA&B&C) U (OA&B&OC) U (OA&OB&C) U (OA&OB&OC);

д. Доказать истинность заключения путем построения дерева доказательства: {A; AAB} | - (C&A) a (B&C);

У.

(3) (4)

В.& В.

е. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода): Построим граф дедуктивного вывода.

Известно, что {A>B}| - (A&C)>(B&C), {B}| - A>B;

A A >B

m.p.

B

A >B

(A &C)>(B&C)

(A &C)>(C&B)

Рисунок A.1 - Граф дедуктивного вывода

Ж. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты): Приведем посылки и отрицание заключения к виду КНФ: F1 = A;

F2 = AAB = OAUB;

OJ= (C&A) a (B&C) = O (O(C&A) U (B&A)) = C&A&(OBUOC);

K = {A, OAUB, C, A, OBUOC} = {A, OAUB, C, OBUOC};

Построим граф вывода пустой резольвенты:

A OAUB C OBUOC

O B

OA

Рисунок А.2 - Граф вывода пустой резольвенты

Вариант 39: {AAB, CAB, Da(AUC), D} | - B

Обозначим: 1=А; 2=B; 3=C; 4=D; 5=AAB; 6= CAB; 7= AUC; 8=4a7

A B C D 1a2 3a2 1U3 4a7

1 2 3 4 5 6 7 8

1 1 1 1 1 1 1 1

1 1 1 0 1 1 1 1

1 1 0 1 1 1 1 1

1 1 0 0 1 1 1 1

1 0 1 1 0 0 1 1

1 0 1 0 0 0 1 1

1 0 0 1 0 1 1 1

1 0 0 0 0 1 1 1

0 1 1 1 1 1 1 1

0 1 1 0 1 1 1 1

0 1 0 1 1 1 0 0

0 1 0 0 1 1 0 1

0 0 1 1 1 0 1 1

0 0 1 0 1 0 1 1

0 0 0 1 1 1 0 0

0 0 0 0 1 1 0 1

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

Б. Упростить посылки и заключения, т.е. привести их к базисному множеству {O, &, U} с минимальным числом операций: F1=А - формула остается без изменений;

F2=B - формула остается без изменений;

F3=C - формула остается без изменений;

F4=D - формула остается без изменений;

F5=AAB = OAUB;

F6= CAB = OCUB;

F7= AUC - формула остается без изменений;

F8=Da(AUC) = ODUAUC;

в. Привести посылки и заключение к базисам {O, &} и {O, U}: Базис {O, U}: F1=А - формула остается без изменений;

F2=B - формула остается без изменений;

F3=C - формула остается без изменений;

F4=D - формула остается без изменений;

F5=AAB = OAUB;

F6= CAB = OCUB;

F7= AUC - формула остается без изменений;

F8=Da(AUC) = ODUAUC;

Базис {O, &}: F1= А - формула остается без изменений;

F2= B - формула остается без изменений;

F3= C - формула остается без изменений;

F4= D - формула остается без изменений;

F5= AAB = O(A&OB);

F6= CAB = O(C&OB);

F7= AUC = O(OA&OC);

F8= Da(AUC) = ODUAUC = O(D&OA&OC);

г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ: КНФ: F1= А - формула остается без изменений;

F2= B - формула остается без изменений;

F3= C - формула остается без изменений;

F4= D - формула остается без изменений;

F5= AAB = (OAUB)&;

F6= CAB = (OCUB)&;

F7= AUC = (AUC)&;

F8= Da(AUC) = (ODUAUC)&;

ДНФ: F1= А - формула остается без изменений;

F2= B - формула остается без изменений;

F3= C - формула остается без изменений;

F4= D - формула остается без изменений;

F5= AAB = O(A&OB) U;

F6= CAB = O (C&OB) U;

F7= AUC = O (OA&OC) U;

F8= Da(AUC) = O DUO(OA&OC) U;

СКНФ: СКНФ строится по значениям «л» заключения в таблице истинности;

F2= (AUOBUCUD) & (AUOBUCUOD) & (AUOBUOCUD) & & (AUOBUOCUOD) & (OAUOBUCUD) & (OAUOBUCUOD) & & (OAUOBUCUOD) & (OAUOBUOCUD) & (OAUOBUOCUOD);

СДНФ: СДНФ строится по значениям «и» заключения в таблице истинности;

F2= (A&B&C&D) U (A&B&C&OD) U (A&B&OC&D) U U (A&B&OC&OD) U (OA&B&C&D) U (OA&B&OC&D) U (OA&B&C&OD) U

U (OA&B&OC&OD);

д. Доказать истинность заключения путем построения дерева доказательства: {AAB, CAB, Da(AUC), D} | - B

У. a

У. a

У. a е. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода): Построим граф дедуктивного вывода.

AAB CAB Da(AUC) D

m.p.

AUC

m.p.

AUB m.p.

B

Рисунок A.3 - Граф дедуктивного вывода ж. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты): Приведем посылки и отрицание заключения к виду КНФ: F4= D - формула остается без изменений;

F5= AAB = OAUB;

F6= CAB = OCUB;

F8= Da(AUC) = ODUAUC;

O J = OF2= OB;

K={D, OAUB, OCUB, ODUAUC, OB}

Построим граф вывода пустой резольвенты: OB OAUB OCUB ODUAUC D

AUC

AUB

B

Рисунок А.4 - Граф вывода пустой резольвенты

2 Выполнить задание по алгебре предикатов и исчислению предикатов: истинность предикат доказательство резолюция

Вариант 22: F= "x (B(x)) ® $y (A(y) ® B(x)) а. Привести выражение к виду ПНФ: F= "x (B(x)) ® $y (A(y) ® B(x)) = O"x (OB(x)) V $y (A(y) ® B(x)) =

= $x (OB(x)) V $y (OA(y) V B(x)) = $v (OB(v)) V $w (OA(w) V B(x)) =

= $v$w (OB(v) V OA(w) V B(x));

б. Привести выражение к виду ССФ: Для приведения к виду ССФ воспользуемся алгоритмом Сколема, поэтому будут проведены следующие замены: v = a, где a - предметная постоянная w = b, где b - предметная постоянная

В результате получится следующее выражение: F= OB(a) V OA(b) V B(x);

в. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода): Представим нашу формулу в следующем виде: {"x (B(x))} | - $y (A(y) ® B(x))

Построим граф дедуктивного вывода для доказательства выводимости заключения из данного множества посылок:

"x (B(x))

У "

B(x)

A(y) ®B(x)

B $

$y (A(y) ® B(x))

Рисунок A.5 - Граф дедуктивного вывода г. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты):

OF= O("x (B(x)) ® $y (A(y) ® B(x))) = O(O"x (B(x)) V $y (OA(y) V B(x))) =

= "x (B(x)) & O$y (OA(y) V B(x)) = "x (B(x)) & "y (A(y) & OB(x)) =

= "v (B(v)) & "w (A(w) & OB(x)) = "v"w (B(v) & A(w) & OB(x));

Д= {B(v), A(w), OB(x)};

Построим граф вывода пустой резольвенты: B(v) OB(x) A(w)

B(v) ®(B(v) V A(w)) x ?v

OB(v) V OB(v) V B(v) V A(w)

Рисунок А.6 - Граф вывода пустой резольвенты

Вариант 39: F= "x (B(x) ® A(y)) & (B(x) ® "y (A(y) ® C(z))) ® $z (B(x)®C(z));

а. Привести выражение к виду ПНФ: F= "x (B(x) ® A(y)) & (B(x) ® "y (A(y) ® C(z))) ® $z (B(x)®C(z)) =

= O("x (B(x) ® A(y)) & (B(x) ® "y (A(y)®C(z)))) V $z (B(x)®C(z)) =

= O"x (B(x) ® A(y)) V O(B(x) ® "y (A(y)®C(z))) V $z (B(x)®C(z)) =

= O"x (OB(x) VA(y)) V O(OB(x) V "y (OA(y) V C(z))) V $z (OB(x) V C(z)) =

= O"x (OB(x) VA(y)) V (B(x) & O"y (OA(y) V C(z))) V $z (OB(x) V C(z)) =

= $x (B(x)& OA(y)) V (B(x) & $y (A(y) & OC(z))) V $z (OB(x) V C(z)) =

= $v (B(v)& OA(y)) V (B(x) & $w (A(w) & OC(z))) V $t (OB(x) V C(t)) =

= $v$w$t((B(v)& OA(y)) V B(x) & (A(w) & OC(z)) V (OB(x) V C(t));

б. Привести выражение к виду ССФ: Для приведения к виду ССФ воспользуемся алгоритмом Сколема, поэтому будут проведены следующие замены: v = a, где a - предметная постоянная;

w = b, где b - предметная постоянная;

t = d, где d - предметная постоянная;

В результате получится следующее выражение: F= (B(a)& OA(y)) V B(x) & (A(b) & OC(z)) V (OB(x) V C(d));

в. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода): Представим нашу формулу в следующем виде: {"x (B(x) ® A(y)); B(x) ® "y (A(y) ® C(z))}| - $z (B(x)®C(z))

Построим граф дедуктивного вывода для доказательства выводимости заключения из данного множества посылок:

"x (B(x) ® A(y)) B(x) ® "y (A(y) ® C(z))

У " У "

B(x) ® A(y) B(x) ® (A(y) ® C(z))

B(x) ®C(z)

В $

$z (B(x)®C(z))

Рисунок A.7 - Граф дедуктивного вывода г. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты): F= O("x (B(x) ® A(y)) & (B(x) ® "y (A(y) ® C(z))) ® $z (B(x)®C(z))) =

= O(O(("x (B(x) ® A(y))) & (B(x) ® "y (A(y) ® C(z)))) V $z (B(x)®C(z))) =

= O(O"x (B(x) ® A(y)) V O(B(x) ® "y (A(y) ® C(z))) V $z (OB(x) V C(z))) =

= "x (B(x) ® A(y)) & (B(x) ® "y (A(y) ® C(z))) & O$z (OB(x) V C(z)) =

= "x (OB(x) V A(y)) & (OB(x) V "y (OA(y) V C(z))) & "z (B(x)& OC(z)) =

= "v (OB(v) V A(y)) & (OB(x) V "w (OA(w) V C(z))) & "d (B(x)& OC(d)) =

= "v"w"d((OB(v) V A(y)) & (OB(x) V OA(w) V C(z)) & (B(x)& OC(d));

Д= {B(x); OC(d); OB(v) V A(y); OB(x) V OA(W) V C(z)};

Построим граф вывода пустой резольвенты:

B(x) OC(d) OB(v) V A(y) OB(x) V OA(W) V C(z)

y ?w x ?v x ?v OB(v) V A(w) V OA(w) V C(z) V OB(v) z ?d

OB(v) V C(d) V OC(d)

Рисунок А.8 - Граф вывода пустой резольвенты

3. Реляционная алгебра

Выполнить следующие бинарные операции и составить результирующие таблицы.

1) (r1Er2)

2) (r1Cr2)

3) (r1 \ r2)

4) Выполнить заданную композицию операций

Вариант №48

Таблица r1

А3 А4 А7 А8 с1 d2 1 2 с2 d3 2 3 с1 d1 2 1 с2 d2 1 4

Таблица r2

АЗА4А7А8 c3 d4 3 4 c1 d2 1 2 c1 d1 2 1 c2 d2 1 4

1) (r1Er2)

АЗА4А7А8 c1 d2 1 2 c2 d3 2 3 c1 d1 2 1 c2 d2 1 4 c3 d4 3 4

2) (r1Cr2)

A3A4A7A8 c1 d2 1 2 c2 d3 2 3 с1 d1 2 1

3) (r1 \ r2)

АЗА4А7А8 с2 d3 2 3

4) r1>q<r2, d (r1.A7)= d(r2.A7) r1A3 r1A4 r1A7 r1A8 r2A3 r2A4 r2A7 r2A8 с1 d2 1 2 c1 d2 1 2 с1 d2 1 2 c2 d2 1 4 с2 d3 2 3 c1 d1 2 1 с1 d1 2 1 c1 d1 2 1 с2 d2 1 4 c1 d2 1 2 с2 d2 1 4 c2 d2 1 4

5) p(r1.A1, r2.A2, r1?A5,r2.A6)(r1>q<r2, d (r1.A7)=d(r2.A7)) r1A3r1A4r1A7r1A8r2A3r2A4r2A7r2A8 с1 d2 1 2 c1 d2 1 2 с1 d2 1 2 c2 d2 1 4 с2 d3 2 3 c1 d1 2 1 с1 d1 2 1 c1 d1 2 1 с2 d2 1 4 c1 d2 1 2 с2 d2 1 4 c2 d2 1 4

Вариант №31

Таблица r1

А1 А2 А5 А6 a4 b1 4 1 a1 b1 4 3 a3 b3 2 1 a4 b4 1 4

Таблица r2

А1А2А5А6 a1 b2 1 2 a2 b3 2 3 a1 b1 4 3 a2 b2 3 2

1) (r1Er2)

А1А2А5А6 a4 b1 4 1 a1 b1 4 3 a3 b3 2 1 a4 b4 1 4 a1 b2 1 2 a2 b3 2 3 a2 b2 3 2

2) (r1Cr2)

А1А2А5А6 a1 b1 4 3

3) (r1 \ r2)

А1А2А5А6 a4 b1 4 1 a3 b3 2 1 a4 b4 1 4

4) r1>q<r2, d(A5)= 4; r1.A5=r2.A5 r1A1 r1A2 r1A5 r1A6 r2A1 r2A2 r2A5 r2A6 a4 b1 4 1 a1 b1 4 3 a1 b1 4 3 a1 b1 4 3

5) p(r1.A1, r2.A4, r2?A5,r1.A6) (r1>q<r2, d(A5)= 4) r1A1 r1A6 r2A5 a4 1 4 a1 3 4

В результате проделанной работы, били закреплены практические навыки решения задач по математической логике. Было решено 2 варианта заданий по математической логике и исчислению высказываний, математической логике и исчислению предикатов, реляционной логике.

1) Игошин, В.И. Математическая логика и теория алгоритмов: Учеб. пособие для вузов [Текст] / В.И. Игошин. - М.: Академия, 2004 г.

Размещено на .ru