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

Введение


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

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

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

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

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

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

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

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


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


{(A®(B®C));( ØDÚA);B}|-(D®C)

F= A®(B®C) G=ØDÚA H=B J= D®C


Таблица 1 - Таблица истинности

ABCDB®CA®(1)ØDÚAD®CH(1)FGJ00001111000111000010111100111101010001110101010001101111011111011000111110011110101011111011111111000011110100101110111111111111

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

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


F = A® (B®C) = ØAÚ(BàC) = ØAÚØBÚC= D®C = ØDÚC


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

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


F = Aà(BàC) = ØAÚØBÚC = Ø(ØØA&Ø(ØBÚC)) = Ø(A&ØØB&ØC) =

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

F = Aà(BàC) = ØAÚØBÚC (в базисе {Ø, Ú})=ØDÚA = ØDÚA=Ø (ØØD&ØA) = Ø(D&ØA) (в базисе {Ø, &})=ØDÚA (в базисе {Ø, Ú})

J = DàC = ØDÚC = Ø (ØØD&ØC) = Ø(D&ØC) (в базисе {Ø, &})

J = DàC = ØDÚC (в базисе {Ø, Ú})


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

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


F = 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&B&C) (СДНФ, построенная с помощью таблицы истинности)

J= D®C = ØDÚC (КНФ, ДНФ, СКНФ)

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

G=ØDÚA (КНФ, ДНФ, СКНФ)

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


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

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


Рисунок 1 -дерево доказательства


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

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


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

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


F= A® (B®C) = ØAÚØBÚC=ØDÚA=B

ØJ= Ø(D®C)= Ø(ØDÚC)=D&ØC


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


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


(A®(B®C));(A®B);|-(A®C)= A®(B®C) G= A®B J= (A®C)


Таблица 2 - Таблица истинности

ABCB®CA®(1)A®BA®C00011110011111010011101111111001100101110111000101111111

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

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


F = A® (B®C) = ØAÚ(BàC) = ØAÚØBÚC= A®B=ØAÚB= (A®C) =ØAÚC


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


F = Aà(BàC) = ØAÚØBÚC = Ø(ØØA&Ø(ØBÚC)) = Ø(A&ØØB&ØC) =

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

F = Aà(BàC) = ØAÚØBÚC (в базисе {Ø, Ú})= A®B=ØAÚB=Ø (ØØA&ØB) = Ø(A&ØB) (в базисе {Ø, &})= A®B=ØAÚB (в базисе {Ø, Ú})= (A®C) =ØAÚC =Ø (ØØA&ØC) = Ø(A&ØC) (в базисе {Ø, &})= (A®C) =ØAÚC (в базисе {Ø, Ú})


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


F = 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&ØB&ØC) (СДНФ, построенная с помощью таблицы истинности)

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

J= (A®C) =ØAÚC (КНФ, ДНФ, СКНФ)=(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

) { 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))=

=$m"n (¬A(m) &¬B(n)) V (B(y) V A(x))=

=$m"n ((¬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))=

="v$w$z ((Ø 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=B=C=D=0=0,B=1,C=1,D=1=0,B=0,C=1,D=1=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=B=C=D=0=0,B=1,C=1,D=1=0,B=0,C=1,D=1=0,B=0,C=0,D=1 , то F=1

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


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


1) (r1Èr2)

) (r1Çr2)

) (r1 \ r2)

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


Таблица 3 - Таблица отношения r1

А1А2А5А6a3 b434а4 b141a2b232a3 b321

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

А1А2А5А6a1 b212a2 b323a2 b232a3b321

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

А1А2А5А6a3 b434а4 b141a2b232a3 b321a1 b212

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

A1A2A5A6a2 b232a3b321

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

А1А2А5А6a3 b434а4 b141

r1>q<r2 ,r1A5=r2A6


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

r1.А1r1.А2r1.А5r1.А6r2.А1r2.А2r2.А5r2.А6a3 b434a2 b323a2b232a2 b323a3 b321a1 b212a3 b321a2 b232

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


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

r1.А1r1.А2r1.А5r2.А6a3 b433a2b233a3 b322a3 b322

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


1) (r1Èr2)

) (r1Çr2)

) (r1 \ r2)

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

A3A4A7A8 c1 d212 c1d223c1d121c2d214

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

A3A4A7A8C3D434c4d141c1d121c2d214

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

A3A4A7A8 c1 d212 c1d223 c1d121c2d214c3d434c4d141

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

A3A4A7A8c1d121c2d214

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

A3A4A7A8 c1 d212 c1d223

4) r1>q<r2, d(A7>=2), r1.A7=r2.A7=A7

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

r1.А3r1.А4r1.А7r1.А8r2.А3r2.А4r2.А7r2.А8 c1 d212c2d214 c1d223c1d121c1d121c1d121c2d214c2d214

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


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

r1.А3r1.А4r1.А7r1.А8c1 d123c1 d123c1 d123c1 d121c1 d121c1 d121

Заключение

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

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

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

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

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

Литература


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

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

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


Теги: Методы решений задач логики высказываний, логики предикатов и реляционной логики  Курсовая работа (теория)  Математика
Просмотров: 36645
Найти в Wikkipedia статьи с фразой: Методы решений задач логики высказываний, логики предикатов и реляционной логики
Назад