Размещено на http://www.allbest.ru/

Содержание

Введение

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

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

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

4. Построение таблицы истинности для логической формулы

4.1 Обоснование выбора структур данных

4.2 Описание алгоритма решения задачи

4.3 Описание пользовательского интерфейса

Заключение

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

Приложение А (обязательное) Листинг программы



Введение

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

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



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

Рассмотрим вариант 19.

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

Таблица 1 - Таблица истинности логического выражения

A	B	C
			2	F	G	3	H
0	0	0	1	1	1	1	1
0	0	1	1	1	1	1	1
0	1	0	1	1	0	0	0
0	1	1	1	1	0	1	1
1	0	0	0	1	1	1	1
1	0	1	1	1	1	1	1
1	1	0	0	0	1	0	0
1	1	1	1	1	1	1	1

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

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



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

F= ( B ( A C)) = ¬ B (A C) = (¬ (BA ¬ C)

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

(КНФ, ДНФ, СКНФ)

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

(КНФ, ДНФ, СКНФ)

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

(КНФ, ДНФ, СКНФ)

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

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

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

(1)

На основании аксиомы имеем:

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

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

Если , то

Если , то , если , тогда имеем следующее выражение:

Если , то

Если , то , если , тогда имеем следующее выражение:

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

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

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

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

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

Рассмотрим вариант 49.

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

Таблица 2 - Таблица истинности суждения

A	B	C
	G		F	1	2	H
0	0	0	1	1	0	1
0	0	1	1	0	1	1
0	1	0	1	1	1	1
0	1	1	1	0	1	1
1	0	0	0	0	0	0
1	0	1	0	0	1	1
1	1	0	1	0	1	1
1	1	1	1	0	1	1

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

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

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

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

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

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

(КНФ, ДНФ, СКНФ)

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

(КНФ, ДНФ, СКНФ)

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

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

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

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

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

Построим граф дедуктивного вывода, представленный на рисунке 5.

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

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

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

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

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



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

Рассмотрим вариант 19.

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

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

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

w=a,

где a - предметная постоянная

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

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

Представим нашу формулу в следующем виде:

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

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

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

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

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

Рассмотрим вариант 49.

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

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

с=f(z),

где f(z) - предметная постоянная

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

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

Представим формулу в следующем виде:

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



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

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

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

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



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

Рассмотрим вариант 19.

В данном подразделе курсовой работы, бинарные операции и составление результирующих таблиц, будут выполнятся над двумя отношениями заданными следующими условиями: r₁: (3,1), (4,2), (7,5), (8,8), r_2: (3,3), (4,4), (7,5), (8,8).

Составление отношения r₁ и r₂ получается из заданного по условию отношения путем удаления соответствующих заданию пар элементов (столбец, строка).

В результате данных операций получаются отношения, представленные в таблицах 3 и 4.

предикат логический формула алгоритм

Таблица 3 - Отношение r₁ Таблица 4 - Отношение r₂

r1
A1	A2	A5	A6
а3	b4	3	4
а4	b1	4	1
а2	b2	3	2
а3	b3	2	1
r2
A1	A2	A5	A6
a1	b2	1	2
a2	b3	2	3
a2	b2	3	2
a3	b3	2	1

а. r'= r₁r₂

В результате операции объединения получается отношение, представленное в таблице 5.

Таблица 5 - Результат выполнения операции r'= r₁r₂

r'
A1	A2	A5	A6
а3	b4	3	4
а4	b1	4	1
а2	b2	3	2
а3	b3	2	1
a1	b2	1	2
a2	b3	2	3

б. r'= r₁r₂

В результате операции пересечения получается отношение, представленное в таблице 6.

Таблица 6 - Результат выполнения операции r'= r₁r₂

r'
A1	A2	A5	A6
а2	b2	3	2
а3	b3	2	1

в. r'= r₁ \ r₂

В результате операции разности получается отношение, представленное в таблице 7.

Таблица 7 - Результат выполнения операции r'= r₁ \ r₂

r'
A1	A2	A5	A6
а3	b4	3	4
а4	b1	4	1

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

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

r'= р_{(r1.A1, r2.A2, r1.A5, r2.A6)}(r₁>^И<r₂, r₁.A₅=r_2.A₆).в

Данное задание представляет собой композицию двух операций, поэтому для ее выполнения требуется получить сначала промежуточное отношение, представляющее собой результат выполнения операции условного соединения над отношениями r₁ и r₂. Результирующее отношение представлено в таблице 8. После этого необходимо выполнить операцию проекции над полученным отношением, выбрав заданные по условию операции атрибуты отношения. Результат выполнения операции проекции представлен в таблице 9.

Таблица 8 - Результат выполнения операции r'= r₁>^И<r₂, r₁.A₅=r_2.A₆

r'
r1.A1	r1.A2	r1.A5	r1.A6	r2.A1	r2.A2	r2.A5	r2.A6
a3	b4	3	4	a2	b3	2	3
a2	b2	3	2	a2	b3	2	3
a3	b3	2	1	a1	b2	1	2

Таблица 9 - Результат выполнения операции r'= р_{(r1.A1, r2.A2, r1.A5, r2.A6)}(r₁>^И<r₂, r₁.A₅=r_2.A₆)

r'
r1.A1	r1.A5	r2.A2	r2.A6
a3	3	b3	3
a2	3	b3	3
a3	2	b2	2

Рассмотрим вариант 49

В данном подразделе курсовой работы, бинарные операции и составление результирующих таблиц будут выполнятся над двумя отношениями заданными следующими условиями: r₁: (1,1), (2,2), (5,7), (6,8), r_2: (1,2), (2,5), (5,7), (6,8).

Составление отношения r₁ и r₂ получается из заданного по условию отношения путем удаления соответствующих заданию пар элементов (столбец, строка).

В результате данных операций получаются отношения, представленные в таблицах 10 и 11.

Таблица 10 - Отношение r₁ Таблица 11 - Отношение r₂

r1
A3	A4	A7	A8
с1	d2	1	2
с2	d3	2	3
с1	d1	2	1
с2	d2	1	4
r2
A3	A4	A7	A8
c3	d4	3	4
c1	d2	1	2
c2	d3	2	3
c2	d2	1	4

а. r'= r₁r₂

В результате операции объединения получается отношение, представленное в таблице 12.

Таблица 12 - Результат выполнения операции r'= r₁r₂

r'
A3	A4	A7	A8
с1	d2	1	2
с2	d3	2	3
с1	d1	2	1
с2	d2	1	4
c3	d4	3	4

б. r'= r₁r₂

В результате операции пересечения получается отношение, представленное в таблице 13.

Таблица 13 - Результат выполнения операции r'= r₁r₂

r'
A3	A4	A7	A8
с1	d2	1	2
с2	d3	2	3
с2	d2	1	4



в. В результате операции разности получается отношение, представленное в таблице 14.

Таблица 14 - Результат выполнения операции r'= r₁ \ r₂

r'
A3	A4	A7	A8
с1	d1	2	1

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

В данном пункте требует выполнить следующую композицию операций: r'= д((r₁>^И<r₂, (r₁.A₇=r_2.A₇)), d(r_1.A3)=c₁)

Данное задание представляет собой композицию двух операций, поэтому для ее выполнения требуется получить сначала промежуточное отношение, представляющее собой результат выполнения операции условного соединения над отношениями r₁ и r₂. Результирующее отношение представлено в таблице 15. После этого необходимо выполнить операцию выборки над полученным отношением, выбрав заданные по условию операции кортежи отношения. Результат выполнения операции выборки представлен в таблице 16.

Таблица 15 - Результат выполнения операции r'= r₁>^И<r₂, r₁.A₇=r_2.A₇

r'
r1.A3	r1.A4	r1.A7	r1.A8	r2.A3	r2.A4	r2.A7	r2.A8
с1	d2	1	2	с1	d2	1	2
с1	d2	1	2	с2	d2	1	4
c2	d3	2	3	с2	d3	2	3
с1	d1	2	1	с2	d3	2	3
c2	d2	1	4	с1	d2	1	2
c2	d2	1	4	с2	d2	1	4



Таблица 16 - Результат выполнения операции r'= д((r₁>^И<r₂, (r₁.A₇=r_2.A₇)), d(r_1.A3)=c₁)

r'
r1.A3	r1.A4	r1.A7	r1.A8	r2.A3	r2.A4	r2.A7	r2.A8
с1	d2	1	2	с1	d2	1	2
с1	d2	1	2	с2	d2	1	4
с1	d1	2	1	с2	d3	2	3



4. Построение таблицы истинности для логической формулы

4.1 Обоснование выбора структур данных

Для решения нашей задачи можно воспользоваться такими структурами данных как строки, ведь именно в них помещается исходное выражение и постфиксная форма выражения.

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

4.2 Описание алгоритма решения задачи

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

1. Ввод пользователем произвольной логической формулы.

2. Перевод введенной формулы из инфиксной формы записи в префиксную форму записи.

3. Заполнение таблицы истинности.

4. Вывод таблицы истинности на экран.

4.3 Описание пользовательского интерфейса

Пользовательский интерфейс программы представляет окно командной строки, для ввода логической формулы представлен на рисунке 11



Рисунок 11 - окно ввода формулы

Результаты работы программы представлены на рисунке 12 и на рисунке 13.

Рисунок 12 - пример выполнения программы



Рисунок 13 - пример выполнения программы



Заключение

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

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



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

1. Игошин, В.И. Математическая логика и теория алгоритмов :учеб. пособие для вузов / Владимир Иванович Игошин . - М. :Академия , 2004. - 446, [1] с. (Высшее профессиональноеобразование).

2. Кондаков, Н. И. Введение в логику: [Текст] / Н. И. Кондаков. - М.: Наука, 1967. - 467 с.

3. Лавров, И. А. Задачи по теории множеств, математической логике и теории алгоритмов/ И. А. Лавров, Л. Л. Максимова. -М.:Физматлит, 2002. - 240 с.

4. Лихтарников, Л.М. Математическая логика: [Текст] / Л.М. Лихтарников, Т.Г. Сукачева. - СПб.: Лань, 1999. - 288 с.

5. Никольская, И.Л. Математическая логика. Учебник / И.Л. Никольская. - М.: Высшая школа, 1981. - 127с.

6. Шапорев, С. Д.Математическая логика. Курс лекций и практических занятий: Учебник/С.Д. Шапорев. - СПб.: БХВ-Петербург, 2005. - 416 с.



Приложение А

(обязательное)

Листинг программы

Program Tabl_ist;

uses crt;

const BoolToInt : array [ boolean ] of integer = ( 0, 1 ) ; //Перевод булевых значений в числа

IntToBool : array [ 0..1 ] of boolean = ( false, true ) ; //Перевод чисел в булево значение

type

//Элемент стека

PElem = ^Elem;

Elem = record

value: string;

next:PElem;

end;

var

Top_ : PElem; //Указатель на вершину стека

str : string; //Строка, в которую помещается исходное выражение

help_str:string; //Вспомогательная строка

post_str : string; //Строка содержащая постфиксную форму выражения

kol_per : integer; //Количество переменных в выражении

pow:integer; // 2 в степени kol_per хранит количество строк в таблице

cap : array of string; //каждый элемент это отдельное подвыражение из основного выражения

tabl : array [,] of integer; // матрица, в которой будет храниться таблица истиности

//Приорететы выполнения операций

function price(ch:string):integer;

begin

case ch[1] of

'(' : price:=0;

'+' : price:=3;

'=' : price:=1;

'>' : price:=2;

'!' : price:=5;

'*' : price:=4;

end;

end;

//Занесение элемента в стек

procedure push(ch:string);

var p:PElem;

begin

new(p);

p^.value:=ch;

p^.next:=Top_;

Top_:=p;

end;

//Чтение элемента из стека

function pop():string;

var p:PElem;

begin

pop:=Top_^.value;

p:=Top_;

Top_:=Top_^.next;

dispose(p);

end;

//Проверка на наличие в стеке элементов

function void(): boolean;

begin

result:= Top_ = nil;

end;

//Заполнение таблици истинности с помощью постфиксной формы выражения

procedure zapolnenie();

var

i,j,stl1,stl2: integer;

procedure pr(z:string);

begin

SetLength(cap,Length(cap)+1);

SetLength(tabl,(Length(tabl) div pow)+1,pow);

stl2:=StrToInt(pop());

stl1:=StrToInt(pop());

push(IntToStr(High(cap)));

cap[High(cap)]:='('+cap[stl1]+z+cap[stl2]+')';

end;

begin

for i:=1 to Length(post_str) do

begin

case post_str[i] of

'A'..'Z' :

begin

push(IntToStr(Pos(post_str[i],help_str)-1));

end;

'+' :

begin

pr(' + ');

for j:=0 to pow-1 do

tabl[High(cap),j]:=BoolToInt[(IntToBool[tabl[stl2,j]]) or (IntToBool[tabl[stl1,j]])];

end;

'*' :

begin

pr(' * ');

for j:=0 to pow-1 do

tabl[High(cap),j]:=BoolToInt[(IntToBool[tabl[stl2,j]]) and (IntToBool[tabl[stl1,j]])];

end;

'=' :

begin

pr(' = ');

for j:=0 to pow-1 do

tabl[High(cap),j]:=BoolToInt[((not (IntToBool[tabl[stl1,j]])) or (IntToBool[tabl[stl2,j]])) and ((not (IntToBool[tabl[stl2,j]])) or (IntToBool[tabl[stl1,j]]))];

end;

'>' :

begin

pr(' > ');

for j:=0 to pow-1 do

tabl[High(cap),j]:=BoolToInt[(not (IntToBool[tabl[stl1,j]])) or (IntToBool[tabl[stl2,j]])];

end;

'!' :

begin

SetLength(cap,Length(cap)+1);

SetLength(tabl,Length(tabl)+1,pow);

stl1:=StrToInt(pop());

push(IntToStr(High(cap)));

cap[High(cap)]:='!'+cap[stl1];

for j:=0 to pow-1 do

tabl[High(cap),j]:=BoolToInt[not(IntToBool[tabl[stl1,j]])];

end;

end;

end;

end;

//Реализаця алгоритма Дейкстры для перевода выражения в постфиксную форму

function Deykstri():boolean;

var

ch:string;

flag:boolean;

i:integer;

begin

Deykstri:=false;

for i:=1 to Length(str) do

begin

flag:=false;

case str[i] of

'A'..'Z' :

begin

post_str:=Concat(post_str,str[i]);

if pos(str[i],help_str)=0 then begin inc(kol_per); help_str:=Concat(help_str,str[i]); end;

end;

'*','+','=','!','>' :

begin

flag:=true;

if void then push(str[i]) else

while flag do

begin

if void then

begin

push(str[i]);

break;

end;

ch:=pop();

if price(str[i])>=price(ch) then

begin

push(ch);

push(str[i]);

flag:=false;

end

else post_str:=Concat(post_str,ch);

end;

end;

'(' :

begin

push('(');

end;

')' :

begin

flag:=false;

repeat

if not void then

begin

ch:=pop();

if ch<>'(' then post_str:=Concat(post_str,ch);

end

else flag:=true;

until (ch='(') or flag;

Deykstri:=flag;

if flag then begin writeln('Ошибка при расстановке скобок! Проверьте выражение и попробуйте снова'); Deykstri:=true; end;

end;

end;

end;

if not flag then

while not void do

begin

ch:=pop();

if ch='(' then begin writeln('Ошибка при расстановке скобок! Проверьте выражение и попробуйте снова'); Deykstri:=true; break; end

else post_str:=post_str+ch;

end;

end;

//Заполнение матрици начальными значениями

procedure start_values();

var

i,j,k:integer;

flag:boolean;

begin

for i:=0 to kol_per-1 do

begin

cap[i]:=help_str[i+1];

flag:=true;

for j:=0 to Round(Exp((i+1)*Ln(2)))-1 do

begin

if flag then flag:=false else flag:=true;

for k:=0 to pow div Round(Exp((i+1)*Ln(2)))-1 do

tabl[i,j*(pow div Round(Exp((i+1)*Ln(2))))+k]:=BoolToInt[flag];

end;

end;

end;

//Вывод таблици истинности на экран

procedure pokaz();

var

i,j: integer;

begin

for i:=0 to High(cap) do write(cap[i]+' ');

writeln();

for j:=0 to pow-1 do

begin

for i:=0 to High(cap) do

begin

write(tabl[i,j]+' ' : Length(cap[i])+2);

end;

writeln();

end;

end;

//Основной код программы

begin

repeat

writeln('Введите выражение, при этом используя следующие операции: ');

writeln('> импликация');

writeln('* конъюнкция');

writeln('+ дизъюнкция');

writeln('= эквивалентность');

writeln('! отрицание');

writeln('Используемые переменные - {A..Z} и {a..z}');

writeln();

post_str:='';

str:='';

help_str:='';

kol_per:=0;

Top_:=nil;

readln(str);

str:=Trim(str);

str:=UpperCase(str);

writeln();

if not Deykstri() then

begin

pow:=Round(Exp(kol_per*Ln(2)));

SetLength(tabl, kol_per, pow);

SetLength(cap,kol_per);

start_values();

zapolnenie();

pokaz();

end;

writeln('--------------------------------------');

until (false);

end.

Размещено на Allbest.ru