Методы решений задач логики высказываний, логики предикатов и реляционной логики

Введение

В середине XX века развитие вычислительной техники привело к появлению логических электронных элементов, логических блоков и устройств вычислительной техники, что было связано с дополнительной разработкой таких областей логики, как проблемы логического синтеза, логическое проектирование и логического моделирования логических устройств и средств вычислительной техники. Эти проблемы изучает теория алгоритмов, основанная на математике, и математической логике в частности. Математическая логика нашла широкое применение в языках программирования. А в 80-х годах XX века начались исследования в области искусственного интеллекта на базе языков и систем логического программирования. Это направление является самым развивающимся и перспективным.

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

Задачами, которые будут решаться в работе, являются:

— ознакомиться с алгеброй логики высказываний и исчислением высказываний,.

— рассмотреть алгебру логики предикатов и исчисление предикатов,.

— изучить реляционную алгебру.

Для решения поставленных задач использовался теоретический материал научных работ Лаврова И. А., Максимовой Л. Л. и Пономарева В.Ф.

1 Логика высказываний.

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

{(A (BC));(DA);B}|-(DC).

F= A (BC) G=DA H=B J= DC.

Таблица 1 — Таблица истинности.

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

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

F = A (BC) = A (BC) = ABC.

J= DC = DC.

Формулы G и H остаются без изменения.

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

F = A (BC) = ABC = (A&(BC)) = (A&B&C) =.

= (A&B&C) (в базисе {, &}).

F = A (BC) = ABC (в базисе {, }).

G=DA = DA= (D&A) = (D&A) (в базисе {, &}).

G=DA (в базисе {, }).

J = DC = DC = (D&C) = (D&C) (в базисе {, &}).

J = DC = DC (в базисе {, }).

Формула H остается без изменения.

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

F = A (BC) = ABC (КНФ, ДНФ, СКНФ).

F=(A&B&C) (A&B&C) (A&B&C) (A&B&C) (A&B&C) (A&B&C) (A&B&C) (СДНФ, построенная с помощью таблицы истинности).

J= DC = DC (КНФ, ДНФ, СКНФ).

J = (D&C) (D&C) (D&C) (СДНФ, построенная с помощью таблицы истинности);

G=DA (КНФ, ДНФ, СКНФ).

G = (D&A) (D&A) (D&A) (СДНФ, построенная с помощью таблицы истинности) Формула H остается без изменения Доказать истинность заключения путём построения дерева доказательства Рисунок 1 -дерево доказательства Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):

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

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

F= A (BC) = ABC.

G=DA.

H=B.

J= (DC)= (DC)=D&C.

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

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

(A (BC));(AB);|-(AC).

F= A (BC) G= AB J= (AC).

Таблица 2 — Таблица истинности.

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

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

F = A (BC) = A (BC) = ABC.

G= AB=AB.

J= (AC) =AC.

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

F = A (BC) = ABC = (A&(BC)) = (A&B&C) =.

= (A&B&C) (в базисе {, &}).

F = A (BC) = ABC (в базисе {, }).

G= AB=AB= (A&B) = (A&B) (в базисе {, &}).

G= AB=AB (в базисе {, }).

J= (AC) =AC = (A&C) = (A&C) (в базисе {, &}).

J= (AC) =AC (в базисе {, }).

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

F = A (BC) = ABC (КНФ, ДНФ, СКНФ).

F=(A&B&C) (A&B&C) (A&B&C) (A&B&C) (A&B&C) (A&B&C) (A&B&C) (СДНФ, построенная с помощью таблицы истинности).

J= AB= AB (КНФ, ДНФ, СКНФ).

G=(A&B)(A&B)(A&B) (СДНФ, построенная с помощью таблицы истинности);

J= (AC) =AC (КНФ, ДНФ, СКНФ).

J=(A&C)(A&C)(A&C) (СДНФ, построенная с помощью таблицы истинности) Доказать истинность заключения путём построения дерева доказательства.

1) {A>(B>С)} |­ A>(B>С) {A} |­ A.

{ A>(B>C), A}|­ A>(B>С) { A>(B>C), A}|­ A.

{ A>(B>C), A}|­ B>С.

{A>B} |­ A>B {A} |- A.

{A>B, A} |- A>B {A>B, A} |- A.

{A>B, A} |- B.

3) { A>(B>C), A}|­ B>С {A>B, A} |- B.

{ A>(B>C), A, A>B} |- B>С { A>(B>C), A, A>B} |- B.

{ A>(B>C), A>B} |- С.

{ A>(B>C), A>B} |- A>С Рисунок 4 -Дерево доказательства Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):

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

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

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

2 Логика предикатов.

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

F = x (A (x) y (B (y)))> (B (y)>A (x)).

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

F = x (A (x) y (B (y)))> (B (y)>A (x))=.

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

=mn (A (m) &B (n)) V (B (y) V A (x))=.

=mn ((A (m)V B (y) V A (x)) & (B (n) V B (y) V A (x))).

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

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

F= n (A (a) V B (y) V A (x)) & (B (n) V B (y) V A (x)).

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

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

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

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

=x (A (x) V B (f (x))).

N = (B (y) A (x))=B (x)&A (x).

Д= { A (x) V B (f (x)), B (x), A (x)}.

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

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

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

F=x (A (x) >B (x))& y (B (x) >C (y))& z (C (y) >D (z)).

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

F=x (A (x) >B (x))& y (B (x) >C (y))& z (C (y) >D (z))=.

=v (A (x) V B (x))& y (B (x) VC (y))& z (C (y) V D (z))=.

=vwz ((A (v) V B (v))& (B (x) VC (w))& (C (y) V D (z)).

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

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

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

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

F= ((A (F (v)) V B (F (v)))& (B (x) VC (n))& (C (y) V D (F (v))).

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

F=x (A (x) >B (x))& y (B (x) >C (y))& z (C (y) >D (z)).

Если A=B=C=D=1.

A=B=C=D=0.

A=0,B=1,C=1,D=1.

A=0,B=0,C=1,D=1.

A=0,B=0,C=0,D=1, то F=1.

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

F=x (A (x) >B (x))& y (B (x) >C (y))& z (C (y) >D (z)).

Если A=B=C=D=1.

A=B=C=D=0.

A=0,B=1,C=1,D=1.

A=0,B=0,C=1,D=1.

A=0,B=0,C=0,D=1, то F=1.

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

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

1) (r1r2).

2) (r1r2).

3) (r1 r2).

4) Выполнить заданную композицию операций Таблица 3 — Таблица отношения r1.

Таблица 4- Таблица отношения r2.

Таблица 5 — Объединение r1 и r2.

Таблица 6 — Пересечение r1 и r2.

Таблица 7 — Вычитание из r1 r2.

r1>

Таблица 8- Тета соединение r1 и r2.

Р (r1A1,r1А2,r1А5,r2А6) (r1>

Таблица 9 — Проекция отношений r1 и r2.

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

1) (r1r2).

2) (r1r2).

3) (r1 r2).

Таблица 10 — Таблица отношения r1.

Таблица 11- Таблица отношения r2.

Таблица 12 — Объединение r1 и r2.

Таблица 13 — Пересечение r1 и r2.

Таблица 14 — Вычитание из r1 r2.

4) r1>=2), r1. A7=r2.A7=A7.

Таблица 15- Тета соединение r1 и r2.

((r1>

Таблица 16 — Таблица выбора кортежей r1 и r2.

Заключение

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

Цель данной курсовой была достигнута.

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

В ходе работы над курсовой работой была изучена научная и учебная литература по теме «Математическая логика и теория алгоритмов» и изучены материалы Интернет-ресурсов.

1) Олькина Е. В. Методические указания по оформлению пояснительных записок к дипломным, курсовым проектам (работам) и отчетов по практикам в соответствии с требованиями государственных стандартов./ Е. В. Олькина. — Орёл: Полиграфическая база ОрёлГТУ, 2011. — 54с. — 50 экз.

2) Пономарев В. Ф. Математическая логика. часть 1. Логика высказываний. Логика предикатов. Учебное пособие./[Текст] В. Ф. Пономарев — Калининград: КГТУ, 2009. — 140с.

3) Пономарев В. Ф. Математическая логика. часть 2. Логика реляционная. Логика нечеткая. Учебное пособие./ В. Ф. Пономарев — Калининград: КГТУ, 2011.