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

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

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

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

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

Вариант 22: {A; AB} | - (C&A) (B&C)

Обозначим:

1=А; 2=B; 3=C; 4=AB; 5=C&A; 6= B&C; 7= 56;

a. Построить таблицу истинности:

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

б. Упростить посылки и заключения, т. е. привести их к базисному множеству {, &, } с минимальным числом операций:

F₁ = A — эта формула остается без изменений;

F₂ = AB = AB;

F₃ = (C&A) (B&C) = (C&A) (B&C) = C A (B&C);

в. Привести посылки и заключение к базисам {, &} и {, }:

Базис {, &}:

F₁ = A — эта формула остается без изменений;

F₂ = AB = (A&B);

F₃ = (C&A) (B&C) = ((C&A) & (B&C)) = (C & A & (B&C));

Базис {, }:

F₁ = A — эта формула остается без изменений;

F₂ = AB = AB;

F₃ = (C&A) (B&C) = (C&A) (B&C) = C A (B&C) = C A (BC);

г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ:

КНФ:

F₁ = A — эта формула остается без изменений;

F₂ = AB = (AB) &

F₃ = (C&A) (B&C) = (C&A) v (B&C) = (C VA) V (B&C) =

= (CV A) V (B&C) = (C V A V B)&(CVAVC) =(CV AVB)&

&(A);

ДНФ:

F₁ = A — эта формула остается без изменений;

F₂ = AB = ((A&B)) ;

F₃ = (C&A) (B&C) = ((C&A) & (B&C)) = ((C&A) (B&C));

СКНФ:

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

F₃ = (C&A) (B&C) = (ABC)&

СДНФ:

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

F₃ = (C&A) (B&C) = (A&B&C) (A&B&C) (A&B&C) (A&B&C) (A&B&C) (A&B&C) (A&B&C);

д. Доказать истинность заключения путём построения дерева доказательства:

{A; AB} | - (C&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 — Граф дедуктивного вывода Ж. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты):

Приведем посылки и отрицание заключения к виду КНФ:

F₁ = A;

F₂ = AB = AB;

J= (C&A) (B&C) = ((C&A) (B&A)) = C&A&(BC);

K = {A, AB, C, A, BC} = {A, AB, C, BC};

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

A AB C BC

B

A

Рисунок А.2 — Граф вывода пустой резольвенты Вариант 39: {AB, CB, D (AC), D} | - B

Обозначим:

1=А; 2=B; 3=C; 4=D; 5=AB; 6= CB; 7= AC; 8=47

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

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

F₁=А — формула остается без изменений;

F₂=B — формула остается без изменений;

F₃=C — формула остается без изменений;

F₄=D — формула остается без изменений;

F₅=AB = AB;

F₆= CB = CB;

F₇= AC — формула остается без изменений;

F₈=D (AC) = DAC;

в. Привести посылки и заключение к базисам {, &} и {, }:

Базис {, }:

F₁=А — формула остается без изменений;

F₂=B — формула остается без изменений;

F₃=C — формула остается без изменений;

F₄=D — формула остается без изменений;

F₅=AB = AB;

F₆= CB = CB;

F₇= AC — формула остается без изменений;

F₈=D (AC) = DAC;

Базис {, &}:

F₁= А — формула остается без изменений;

F₂= B — формула остается без изменений;

F₃= C — формула остается без изменений;

F₄= D — формула остается без изменений;

F₅= AB = (A&B);

F₆= CB = (C&B);

F₇= AC = (A&C);

F₈= D (AC) = DAC = (D&A&C);

г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ:

КНФ:

F₁= А — формула остается без изменений;

F₂= B — формула остается без изменений;

F₃= C — формула остается без изменений;

F₄= D — формула остается без изменений;

F₅= AB = (AB)&

F₆= CB = (CB)&

F₇= AC = (AC)&

F₈= D (AC) = (DAC)&

ДНФ:

F₁= А — формула остается без изменений;

F₂= B — формула остается без изменений;

F₃= C — формула остается без изменений;

F₄= D — формула остается без изменений;

F₅= AB = (A&B) ;

F₆= CB = (C&B) ;

F₇= AC = (A&C) ;

F₈= D (AC) = D (A&C) ;

СКНФ:

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

F₂= (ABCD) & (ABCD) & (ABCD) & & (ABCD) & (ABCD) & (ABCD) & & (ABCD) & (ABCD) & (ABCD);

СДНФ:

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

F₂= (A&B&C&D) (A&B&C&D) (A&B&C&D) (A&B&C&D) (A&B&C&D) (A&B&C&D) (A&B&C&D)

(A&B&C&D);

д. Доказать истинность заключения путём построения дерева доказательства:

{AB, CB, D (AC), D} | - B

У.

У.

У.

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

Построим граф дедуктивного вывода.

AB CB D (AC) D

m.p.

AC

m.p.

AB

m.p.

B

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

Приведем посылки и отрицание заключения к виду КНФ:

F₄= D — формула остается без изменений;

F₅= AB = AB;

F₆= CB = CB;

F₈= D (AC) = DAC;

J = F₂= B;

K={D, AB, CB, DAC, B}

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

B AB CB DAC D

AС

AB

B

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

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

истинность предикат доказательство резолюция Вариант 22: F= x (B (x)) y (A (y) B (x))

а. Привести выражение к виду ПНФ:

F= x (B (x)) y (A (y) B (x)) = x (B (x)) V y (A (y) B (x)) =

= x (B (x)) V y (A (y) V B (x)) = v (B (v)) V w (A (w) V B (x)) =

= vw (B (v) V A (w) V B (x));

б. Привести выражение к виду ССФ:

Для приведения к виду ССФ воспользуемся алгоритмом Сколема, поэтому будут проведены следующие замены:

v = a, где a — предметная постоянная

w = b, где b — предметная постоянная В результате получится следующее выражение:

F= B (a) V A (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 — Граф дедуктивного вывода г. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты):

F= (x (B (x)) y (A (y) B (x))) = (x (B (x)) V y (A (y) V B (x))) =

= x (B (x)) & y (A (y) V B (x)) = x (B (x)) & y (A (y) & B (x)) =

= v (B (v)) & w (A (w) & B (x)) = vw (B (v) & A (w) & B (x));

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

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

B (v) B (x) A (w)

B (v) (B (v) V A (w)) _x ?^v

B (v) V B (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)) =

= (x (B (x) A (y)) & (B (x) y (A (y)C (z)))) V z (B (x)C (z)) =

= x (B (x) A (y)) V (B (x) y (A (y)C (z))) V z (B (x)C (z)) =

= x (B (x) VA (y)) V (B (x) V y (A (y) V C (z))) V z (B (x) V C (z)) =

= x (B (x) VA (y)) V (B (x) & y (A (y) V C (z))) V z (B (x) V C (z)) =

= x (B (x)& A (y)) V (B (x) & y (A (y) & C (z))) V z (B (x) V C (z)) =

= v (B (v)& A (y)) V (B (x) & w (A (w) & C (z))) V t (B (x) V C (t)) =

= vwt ((B (v)& A (y)) V B (x) & (A (w) & C (z)) V (B (x) V C (t));

б. Привести выражение к виду ССФ:

Для приведения к виду ССФ воспользуемся алгоритмом Сколема, поэтому будут проведены следующие замены:

v = a, где a — предметная постоянная;

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

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

В результате получится следующее выражение:

F= (B (a)& A (y)) V B (x) & (A (b) & C (z)) V (B (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= (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)))) V z (B (x)C (z))) =

= (x (B (x) A (y)) V (B (x) y (A (y) C (z))) V z (B (x) V C (z))) =

= x (B (x) A (y)) & (B (x) y (A (y) C (z))) & z (B (x) V C (z)) =

= x (B (x) V A (y)) & (B (x) V y (A (y) V C (z))) & z (B (x)& C (z)) =

= v (B (v) V A (y)) & (B (x) V w (A (w) V C (z))) & d (B (x)& C (d)) =

= vwd ((B (v) V A (y)) & (B (x) V A (w) V C (z)) & (B (x)& C (d));

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

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

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

_y ?^w _x ?^v

_x ?^v B (v) V A (w) V A (w) V C (z) V B (v)

_z ?^d

B (v) V C (d) V C (d)

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

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

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

1) (r₁r₂)

2) (r₁r₂)

3) (r₁ r₂)

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

Вариант № 48

Таблица r₁

Таблица r₂

1) (r₁r₂)

2) (r₁r₂)

3) (r₁ r₂)

4) r₁>2, d (r1.A₇)= d (r₂.A₇)

5) _{(r1.A1, r2. A2, r1A5,r2.A6)}(r₁>2, d (r1.A₇)=d (r₂.A₇))

Вариант №31

Таблица r₁

Таблица r₂

1) (r₁r₂)

2) (r₁r₂)

3) (r₁ r₂)

4) r₁>2, d (A₅)= 4; r₁.A₅=r₂.A₅

5) _{(r1.A1, r2. A4, r2A5,r1.A6)} (r₁>2, d (A₅)= 4)

Заключение

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

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