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

/

Введение

В середине 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><r2 ,r1A5=r2A6

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

Р (r1A1,r1А2,r1А5,r2А6) (r1><r2 ,r1A5=r2A6)

Таблица 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><r2, d(A7>=2), r1.A7=r2.A7=A7

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

((r1><r2 r1.A7=r2.A7=A7 d(r1.A3)=c1)

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

Заключение

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

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

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

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

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

Литература

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

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

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