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

СОДЕРЖАНИЕ

 

Введение 4

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

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

3 Реляционная логика 21

Заключение 26

Список литературы 27

Введение

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

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

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

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

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

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

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

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

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

высказываний:

{A®(В®C); ØD ÚA;B}├ D®C

Обозначим F= A® (B®C), G=ØD ÚA, H=B, P= D®C

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

Таблица 1

A	B	C	D	A®(C®B)	ØD ÚA	D®C
	H			F	G	P
И	И	И	И	И	И	И
И	И	И	Л	И	И	И
И	И	Л	И	Л	И	Л
И	И	Л	Л	Л	И	И
И	Л	И	И	И	И	И
И	Л	И	Л	И	И	И
И	Л	Л	И	И	И	Л
И	Л	Л	Л	И	И	И
Л	И	И	И	И	Л	И
Л	И	И	Л	И	И	И
Л	И	Л	И	И	Л	Л
Л	И	Л	Л	И	И	И
Л	Л	И	И	И	Л	И
Л	Л	И	Л	И	И	И
Л	Л	Л	И	И	Л	Л
Л	Л	Л	Л	И	И	И

 

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

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

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

P = D®C = ØDÚC

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

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

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

P = D®C = ØDÚC

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

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

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

P= D®C= Ø(D&ØC)

G=ØD ÚA==Ø(D &ØA)

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

F = A®(B®C) = ØAÚØBÚC (КНФ, ДНФ, СКНФ)

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

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

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

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

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

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

ВП

1. {ØD} |- D {D} |- D

В^

{ØD,D} |- ØD {ØD,D} |- D

ВП

{ØD,D} |- ^

УØ

ВП

{ØD,D,ØA} |- ^ {A} |- A

В®

В®

{ØD,D} |- A {A,D} |-A

У Ú

{ØD,ØDÚA} |- D®A {A,ØDÚA} |- D®A {ØDÚA}|- ØDÚA

{ØDÚA} |- D®A

 

ВП

2. {ØDÚA} |- D®A {D} |- D

У®

{ØDÚA,D} |- D®A {D,ØDÚA} |- D

{D,ØDÚA} |- A

 

 

ВП

3. {A®(B®C)} |- A®(B®C) {D,ØDÚA} |- A

У®

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

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

 

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

 

ВП

4. { A®(B®C),D,ØDÚA } |- B®C {B} |- B

У®

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

В®

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

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

Рисунок 1, лист 2

 

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

B

A®(C®B)

ØD ÚA

D ®A

D ®(B®C)

ØD ÚØBÚC

B ®(D®C)

m.p.

D®C

 

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

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

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

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

G=ØDÚA

H=B

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

K= {ØAÚØBÚC; ØDÚA; B; D; ØC}

 

ØD ÚA

D

ØAÚØBÚC

B

ØAÚC

CÚØD

C

ØC

 

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

 

 

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

высказываний:

{A&BÚØA&ØB}├ (A®C)«(B®C)

Обозначим F= A&BÚØA&ØB и G=(A®C)«(B®C)

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

Таблица 2

A	B	C	A&B	ØA&ØB	A&B Ú ØA&ØB	A®C	B®C	(A®C)« (B®C)
					F			G
И	И	И	И	Л	И	И	И	И
И	И	Л	И	Л	И	Л	Л	И
И	Л	И	Л	Л	Л	И	И	И
И	Л	Л	Л	Л	Л	Л	И	Л
Л	И	И	Л	Л	Л	И	И	И
Л	И	Л	Л	Л	Л	И	Л	Л
Л	Л	И	Л	И	И	И	И	И
Л	Л	Л	Л	И	И	И	И	И

 

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

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

G =(A®C)«(B®C) = ( Ø(ØAÚC)ÚØ BÚC)&(Ø(ØBÚC)ØÚAÚC)=

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

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

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

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

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

G = (A®C)«(B®C)® =( ØAÚC)«(ØBÚC)=(Ø(ØAÚC)ÚØBÚC)&

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

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

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

G = (A®C)« (B®C) =( Ø(A&ØB))«(Ø(B&ØC)) = ((Ø(A&ØB))®

®(Ø(B&ØC))&((Ø(B&ØC))® Ø(A&ØB)=(Ø((Ø(A&ØB))&B&ØC)&

& Ø((Ø(B&ØC))&(A&ØB))) = A&ØC&ØB

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

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

=((A&B)ÚØA)&((A&B)ÚØB)=(ØAÚB)&(ØBÚA) (КНФ,СКНФ)

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

G = (A® C)«(B®C) =( Ø(ØAÚC)ÚØ BÚC)&(Ø(ØBÚC)ØÚAÚC)=

= A&ØC&ØB (КНФ)

G=(Ø(ØAÚC)ÚØBÚC)&(Ø(ØBÚC)ÚØAÚC)=Ø(Ø(ØAÚC)ÚØBÚC)Ú

ÚØ(Ø(ØBÚC)ÚØAÚC)=(ØA&ØC&B)Ú(ØB&ØC&A) (ДНФ)

G=(ØAÚBÚC)&(AÚØBÚC) (СКНФ)

G=(A&B&C)Ú(A&B&ØC)Ú(A&ØB&C)Ú(ØA&B&C)Ú(ØA&ØB&C)Ú

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

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

{A&B}├A&B

У& ––––––––––––

{A&B}├B {B®C}├B®C

ВП –––––––––––– ВП ––––––––––––

{A&B, B®C}├B {A&B, B®C}├B®C

m.p. ––––––––––––––––––––––––––––––––––––––––

{ A&B, B®C}├ C

ВП –––––––––––––––––––––––––––––––––

{A&B Ú A&B, B®C, A&B; A}├ C

В® –––––––––––––––––––––––––––––––––

{A&B Ú A&B, B®C, A&B}├ A®C (1)

{A&B}├A&B

У& ––––––––––––

{A&B}├A {A}├A

ВП –––––––––––– ВП ––––––––––––

{A&B; A}├A {A&B; A}├A

В^ ––––––––––––––––––––––––––––––––––––––

{A&B, A }├ ^

У^ –––––––––––––––

{A&B, A }├ С

Рисунок 4 – Дерево доказательств, лист 1

В® –––––––––––––––

{A&B}├ A®С

ВП ––––––––––––––––––––––––––––––––––––––

{A&B Ú A&B, B®C, A&B}├ A®C (2)

 

 

{A&B Ú A&B}├ A&B Ú A&B

ВП –––––––––––––––––––––––––––––––

{A&B Ú A&B, B®C}├ A&B Ú A&B (1) (2)

УÚ –––––––––––––––––––––––––––––––––––––––––––––––––––––––––

{A&BÚA&B, B®C}├ A®C

В® ––––––––––––––––––––––––––––––––––

{A&BÚA&B}├ (B®C) ® (A®C) (3)

 

{A&B}├A&B

У& ––––––––––––

{A&B}├A {A®C}├A®C

ВП –––––––––––– ВП ––––––––––––

{A&B, A®C}├A {A&B, A®C}├A®C

m.p. ––––––––––––––––––––––––––––––––––––––––

{ A&B, A®C}├ C

ВП –––––––––––––––––––––––––––––––––

{A&B Ú A&B, A®C, A&B, B}├ C

В® –––––––––––––––––––––––––––––––––

{A&B Ú A&B, A®C, A&B}├ B®C (4)

Рисунок 4,лист 2
{A&B}├A&B

У& ––––––––––––

{A&B}├B {B}├B

ВП –––––––––––– ВП ––––––––––––

{A&B, B}├B {A&B, B}├B

В^ ––––––––––––––––––––––––––––––––––––––

{A&B, B}├ ^

У^ –––––––––––––––

{A&B, B}├ С

В® –––––––––––––––

{A&B}├ B®С

ВП ––––––––––––––––––––––––––––––––––––––

{A&B Ú A&B, A®C, A&B}├ B®C (5)

 

{A&B Ú A&B}├ A&B Ú A&B

ВП –––––––––––––––––––––––––––––––

{A&B Ú A&B, A®C}├ A&B Ú A&B (4) (5)

УÚ –––––––––––––––––––––––––––––––––––––––––––––––––––––––––

{A&BÚA&B, A®C}├ B®C

В® ––––––––––––––––––––––––––––––––––

{A&BÚA&B}├ (A®C) ® (B®C) (3)

В«––––––––––––––––––––––––––––––––––––––––––

{A&BÚA&B}├ (A®C) « (B®C)

Рисунок 4,лист 3

 

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

A&BÚA&B

з-н дистрибутивности

(AÚB)&(AÚB)

у&

AÚB AÚB

B® B®

B®A A®B

ВÚ ВÚ

BÚC®AÚC AÚC®BÚC

B® B®

(B®C)®(A®C) (A®C)®(B®C)

 

(A®C)«(B®C)

 

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

 

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

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

F₁ = A&BÚA&B = (AÚB)&( AÚB);

B = ((A®C) « (B®C)) = ((AÚC) « (BÚC)) =

= (((AÚC) ® (BÚC))&((BÚC) ® (AÚC))) =

= ((A&C ÚBÚC)&(B&C ÚAÚC)) = (AÚC)&B&CÚ(BÚC)&A&C =

= (AÚBÚC)&(BÚA)&(BÚC)&(AÚC)&C = (AÚBÚC)&(AÚB)& C;

K = {AÚB; AÚB; AÚBÚC; AÚB; C}

AÚB AÚB

BÚB

B AÚBÚC

C AÚC

AÚBA AÚB

B B

 

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

 

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