Решение задач по логике и исчислению высказываний
Порядок формирования таблицы истинности. Упрощение посылок и заключений, приведение их к базисному множеству. Доказательство истинности заключения методом дедуктивного вывода и резолюции с построением соответствующих графов. Исчисление предикатов.
| Рубрика | Философия |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 21.11.2012 |
| Размер файла | 137,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Введение
Целью данной работы является закрепление материала, полученного в теоретических курсах, закрепление навыков самостоятельной работы с теоретическим материалом, применение знаний к решению конкретных задач.
Задачей работы является решение (на основе приобретенных знаний и изучения специальной и нормативно-методической литературы) задач по логике и исчислению высказываний, логике и исчислению предикатов, реляционной логике.
1 Решение задач по алгебре и исчислению высказываний
1. Выполнить задания по алгебре высказываний и исчислению высказываний:
Вариант 22: {A; AB} | - (C&A) (B&C)
Обозначим:
1=А; 2=B; 3=C; 4=AB; 5=C&A; 6= B&C; 7= 56;
a. Построить таблицу истинности:
|
A |
B |
C |
12 |
3&1 |
2&3 |
56 |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
В таблице истинности жирным шрифтом выделены столбцы с посылками, а жирным и курсивом выделено заключение. Смотря на те строчки, в которых истины все посылки одновременно (в данном случае это первая и вторая, которые выделены жирной рамкой), видно, что заключение также истинно. Поэтому можно сделать вывод, что данное заключение выводимо из данного множества посылок.
б. Упростить посылки и заключения, т.е. привести их к базисному множеству {, &, } с минимальным числом операций:
F1 = A - эта формула остается без изменений;
F2 = AB = AB;
F3 = (C&A) (B&C) = (C&A) (B&C) = C A (B&C);
в. Привести посылки и заключение к базисам {, &} и {, }:
Базис {, &}:
F1 = A - эта формула остается без изменений;
F2 = AB = (A&B);
F3 = (C&A) (B&C) = ((C&A) & (B&C)) = (C & A & (B&C));
Базис {, }:
F1 = A - эта формула остается без изменений;
F2 = AB = AB;
F3 = (C&A) (B&C) = (C&A) (B&C) = C A (B&C) = C A (BC);
г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ:
КНФ:
F1 = A - эта формула остается без изменений;
F2 = AB = (AB) &;
F3 = (C&A) (B&C) = (C&A) v (B&C) = (C VA) V (B&C) =
= (CV A) V (B&C) = (C V A V B)&(CVAVC) =(CV AVB)&
&(A);
ДНФ:
F1 = A - эта формула остается без изменений;
F2 = AB = ((A&B)) ;
F3 = (C&A) (B&C) = ((C&A) & (B&C)) = ((C&A) (B&C));
СКНФ:
СКНФ строится по значениям «л» заключения в таблице истинности;
F3 = (C&A) (B&C) = (ABC)&;
СДНФ:
СДНФ строится по значениям «и» заключения в таблице истинности;
F3 = (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);
д. Доказать истинность заключения путём построения дерева доказательства:
{A; AB} | - (C&A) (B&C);
У.
(3) (4)
В.&
В.
е. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):
Построим граф дедуктивного вывода.
Известно, что {A>B}| - (A&C)>(B&C), {B}| - A>B;
A A >B
m.p.
B
A >B
(A &C)>(B&C)
(A &C)>(C&B)
Рисунок A.1 - Граф дедуктивного вывода
Ж. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты):
Приведем посылки и отрицание заключения к виду КНФ:
F1 = A;
F2 = AB = AB;
J= (C&A) (B&C) = ((C&A) (B&A)) = C&A&(BC);
K = {A, AB, C, A, BC} = {A, AB, C, BC};
Построим граф вывода пустой резольвенты:
A AB C BC
B
A
Рисунок А.2 - Граф вывода пустой резольвенты
Вариант 39: {AB, CB, D(AC), D} | - B
Обозначим:
1=А; 2=B; 3=C; 4=D; 5=AB; 6= CB; 7= AC; 8=47
|
A |
B |
C |
D |
12 |
32 |
13 |
47 |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
В таблице истинности жирным шрифтом выделены столбцы с посылками, а жирным и курсивом выделено заключение. Смотря на те строчки, в которых истины все посылки одновременно (в данном случае это первая, третья, девятая, которые выделены жирной рамкой), видно, что заключение также истинно. Поэтому можно сделать вывод, что данное заключение выводимо из данного множества посылок.
Б. Упростить посылки и заключения, т.е. привести их к базисному множеству {, &, } с минимальным числом операций:
F1=А - формула остается без изменений;
F2=B - формула остается без изменений;
F3=C - формула остается без изменений;
F4=D - формула остается без изменений;
F5=AB = AB;
F6= CB = CB;
F7= AC - формула остается без изменений;
F8=D(AC) = DAC;
в. Привести посылки и заключение к базисам {, &} и {, }:
Базис {, }:
F1=А - формула остается без изменений;
F2=B - формула остается без изменений;
F3=C - формула остается без изменений;
F4=D - формула остается без изменений;
F5=AB = AB;
F6= CB = CB;
F7= AC - формула остается без изменений;
F8=D(AC) = DAC;
Базис {, &}:
F1= А - формула остается без изменений;
F2= B - формула остается без изменений;
F3= C - формула остается без изменений;
F4= D - формула остается без изменений;
F5= AB = (A&B);
F6= CB = (C&B);
F7= AC = (A&C);
F8= D(AC) = DAC = (D&A&C);
г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ:
КНФ:
F1= А - формула остается без изменений;
F2= B - формула остается без изменений;
F3= C - формула остается без изменений;
F4= D - формула остается без изменений;
F5= AB = (AB)&;
F6= CB = (CB)&;
F7= AC = (AC)&;
F8= D(AC) = (DAC)&;
ДНФ:
F1= А - формула остается без изменений;
F2= B - формула остается без изменений;
F3= C - формула остается без изменений;
F4= D - формула остается без изменений;
F5= AB = (A&B) ;
F6= CB = (C&B) ;
F7= AC = (A&C) ;
F8= D(AC) = D(A&C) ;
СКНФ:
СКНФ строится по значениям «л» заключения в таблице истинности;
F2= (ABCD) & (ABCD) & (ABCD) & & (ABCD) & (ABCD) & (ABCD) & & (ABCD) & (ABCD) & (ABCD);
СДНФ:
СДНФ строится по значениям «и» заключения в таблице истинности;
F2= (A&B&C&D) (A&B&C&D) (A&B&C&D) (A&B&C&D) (A&B&C&D) (A&B&C&D) (A&B&C&D)
(A&B&C&D);
д. Доказать истинность заключения путём построения дерева доказательства:
{AB, CB, D(AC), D} | - B
У.
У.
У.
е. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):
Построим граф дедуктивного вывода.
AB CB D(AC) D
m.p.
AC
m.p.
AB
m.p.
B
Рисунок A.3 - Граф дедуктивного вывода
ж. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты):
Приведем посылки и отрицание заключения к виду КНФ:
F4= D - формула остается без изменений;
F5= AB = AB;
F6= CB = CB;
F8= D(AC) = DAC;
J = F2= B;
K={D, AB, CB, DAC, B}
Построим граф вывода пустой резольвенты:
B AB CB DAC D
AС
AB
B
Рисунок А.4 - Граф вывода пустой резольвенты
2 Выполнить задание по алгебре предикатов и исчислению предикатов:
истинность предикат доказательство резолюция
Вариант 22: F= x (B(x)) y (A(y) B(x))
а. Привести выражение к виду ПНФ:
F= x (B(x)) y (A(y) B(x)) = x (B(x)) V y (A(y) B(x)) =
= x (B(x)) V y (A(y) V B(x)) = v (B(v)) V w (A(w) V B(x)) =
= vw (B(v) V A(w) V B(x));
б. Привести выражение к виду ССФ:
Для приведения к виду ССФ воспользуемся алгоритмом Сколема, поэтому будут проведены следующие замены:
v = a, где a - предметная постоянная
w = b, где b - предметная постоянная
В результате получится следующее выражение:
F= B(a) V A(b) V B(x);
в. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):
Представим нашу формулу в следующем виде:
{x (B(x))} | - y (A(y) B(x))
Построим граф дедуктивного вывода для доказательства выводимости заключения из данного множества посылок:
x (B(x))
У
B(x)
A(y) B(x)
B
y (A(y) B(x))
Рисунок A.5 - Граф дедуктивного вывода
г. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты):
F= (x (B(x)) y (A(y) B(x))) = (x (B(x)) V y (A(y) V B(x))) =
= x (B(x)) & y (A(y) V B(x)) = x (B(x)) & y (A(y) & B(x)) =
= v (B(v)) & w (A(w) & B(x)) = vw (B(v) & A(w) & B(x));
Д= {B(v), A(w), B(x)};
Построим граф вывода пустой резольвенты:
B(v) B(x) A(w)
B(v) (B(v) V A(w)) x ?v
B(v) V B(v) V B(v) V A(w)
Рисунок А.6 - Граф вывода пустой резольвенты
Вариант 39:
F= x (B(x) A(y)) & (B(x) y (A(y) C(z))) z (B(x)C(z));
а. Привести выражение к виду ПНФ:
F= x (B(x) A(y)) & (B(x) y (A(y) C(z))) z (B(x)C(z)) =
= (x (B(x) A(y)) & (B(x) y (A(y)C(z)))) V z (B(x)C(z)) =
= x (B(x) A(y)) V (B(x) y (A(y)C(z))) V z (B(x)C(z)) =
= x (B(x) VA(y)) V (B(x) V y (A(y) V C(z))) V z (B(x) V C(z)) =
= x (B(x) VA(y)) V (B(x) & y (A(y) V C(z))) V z (B(x) V C(z)) =
= x (B(x)& A(y)) V (B(x) & y (A(y) & C(z))) V z (B(x) V C(z)) =
= v (B(v)& A(y)) V (B(x) & w (A(w) & C(z))) V t (B(x) V C(t)) =
= vwt((B(v)& A(y)) V B(x) & (A(w) & C(z)) V (B(x) V C(t));
б. Привести выражение к виду ССФ:
Для приведения к виду ССФ воспользуемся алгоритмом Сколема, поэтому будут проведены следующие замены:
v = a, где a - предметная постоянная;
w = b, где b - предметная постоянная;
t = d, где d - предметная постоянная;
В результате получится следующее выражение:
F= (B(a)& A(y)) V B(x) & (A(b) & C(z)) V (B(x) V C(d));
в. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):
Представим нашу формулу в следующем виде:
{x (B(x) A(y)); B(x) y (A(y) C(z))}| - z (B(x)C(z))
Построим граф дедуктивного вывода для доказательства выводимости заключения из данного множества посылок:
x (B(x) A(y)) B(x) y (A(y) C(z))
У У
B(x) A(y) B(x) (A(y) C(z))
B(x) C(z)
В
z (B(x)C(z))
Рисунок A.7 - Граф дедуктивного вывода
г. Доказать истинность заключения методом резолюции (с построением
графа вывода пустой резольвенты):
F= (x (B(x) A(y)) & (B(x) y (A(y) C(z))) z (B(x)C(z))) =
= (((x (B(x) A(y))) & (B(x) y (A(y) C(z)))) V z (B(x)C(z))) =
= (x (B(x) A(y)) V (B(x) y (A(y) C(z))) V z (B(x) V C(z))) =
= x (B(x) A(y)) & (B(x) y (A(y) C(z))) & z (B(x) V C(z)) =
= x (B(x) V A(y)) & (B(x) V y (A(y) V C(z))) & z (B(x)& C(z)) =
= v (B(v) V A(y)) & (B(x) V w (A(w) V C(z))) & d (B(x)& C(d)) =
= vwd((B(v) V A(y)) & (B(x) V A(w) V C(z)) & (B(x)& C(d));
Д= {B(x); C(d); B(v) V A(y); B(x) V A(W) V C(z)};
Построим граф вывода пустой резольвенты:
B(x) C(d) B(v) V A(y) B(x) V A(W) V C(z)
y ?w x ?v
x ?v B(v) V A(w) V A(w) V C(z) V B(v)
z ?d
B(v) V C(d) V C(d)
Рисунок А.8 - Граф вывода пустой резольвенты
3. Реляционная алгебра
Выполнить следующие бинарные операции и составить результирующие таблицы.
1) (r1r2)
2) (r1r2)
3) (r1 \ r2)
4) Выполнить заданную композицию операций
Вариант №48
Таблица r1
|
А3 |
А4 |
А7 |
А8 |
|
|
с1 |
d2 |
1 |
2 |
|
|
с2 |
d3 |
2 |
3 |
|
|
с1 |
d1 |
2 |
1 |
|
|
с2 |
d2 |
1 |
4 |
Таблица r2
|
А3 |
А4 |
А7 |
А8 |
|
|
c3 |
d4 |
3 |
4 |
|
|
c1 |
d2 |
1 |
2 |
|
|
c1 |
d1 |
2 |
1 |
|
|
c2 |
d2 |
1 |
4 |
1) (r1r2)
|
А3 |
А4 |
А7 |
А8 |
|
|
c1 |
d2 |
1 |
2 |
|
|
c2 |
d3 |
2 |
3 |
|
|
c1 |
d1 |
2 |
1 |
|
|
c2 |
d2 |
1 |
4 |
|
|
c3 |
d4 |
3 |
4 |
2) (r1r2)
|
A3 |
A4 |
A7 |
A8 |
|
|
c1 |
d2 |
1 |
2 |
|
|
c2 |
d3 |
2 |
3 |
|
|
с1 |
d1 |
2 |
1 |
3) (r1 \ r2)
|
А3 |
А4 |
А7 |
А8 |
|
|
с2 |
d3 |
2 |
3 |
4) r1><r2, d (r1.A7)= d(r2.A7)
|
r1A3 |
r1A4 |
r1A7 |
r1A8 |
r2A3 |
r2A4 |
r2A7 |
r2A8 |
|
|
с1 |
d2 |
1 |
2 |
c1 |
d2 |
1 |
2 |
|
|
с1 |
d2 |
1 |
2 |
c2 |
d2 |
1 |
4 |
|
|
с2 |
d3 |
2 |
3 |
c1 |
d1 |
2 |
1 |
|
|
с1 |
d1 |
2 |
1 |
c1 |
d1 |
2 |
1 |
|
|
с2 |
d2 |
1 |
4 |
c1 |
d2 |
1 |
2 |
|
|
с2 |
d2 |
1 |
4 |
c2 |
d2 |
1 |
4 |
5) (r1.A1, r2.A2, r1A5,r2.A6)(r1><r2, d (r1.A7)=d(r2.A7))
|
r1A3 |
r1A4 |
r1A7 |
r1A8 |
r2A3 |
r2A4 |
r2A7 |
r2A8 |
|
|
с1 |
d2 |
1 |
2 |
c1 |
d2 |
1 |
2 |
|
|
с1 |
d2 |
1 |
2 |
c2 |
d2 |
1 |
4 |
|
|
с2 |
d3 |
2 |
3 |
c1 |
d1 |
2 |
1 |
|
|
с1 |
d1 |
2 |
1 |
c1 |
d1 |
2 |
1 |
|
|
с2 |
d2 |
1 |
4 |
c1 |
d2 |
1 |
2 |
|
|
с2 |
d2 |
1 |
4 |
c2 |
d2 |
1 |
4 |
Вариант №31
Таблица r1
|
А1 |
А2 |
А5 |
А6 |
|
|
a4 |
b1 |
4 |
1 |
|
|
a1 |
b1 |
4 |
3 |
|
|
a3 |
b3 |
2 |
1 |
|
|
a4 |
b4 |
1 |
4 |
Таблица r2
|
А1 |
А2 |
А5 |
А6 |
|
|
a1 |
b2 |
1 |
2 |
|
|
a2 |
b3 |
2 |
3 |
|
|
a1 |
b1 |
4 |
3 |
|
|
a2 |
b2 |
3 |
2 |
1) (r1r2)
|
А1 |
А2 |
А5 |
А6 |
|
|
a4 |
b1 |
4 |
1 |
|
|
a1 |
b1 |
4 |
3 |
|
|
a3 |
b3 |
2 |
1 |
|
|
a4 |
b4 |
1 |
4 |
|
|
a1 |
b2 |
1 |
2 |
|
|
a2 |
b3 |
2 |
3 |
|
|
a2 |
b2 |
3 |
2 |
2) (r1r2)
|
А1 |
А2 |
А5 |
А6 |
|
|
a1 |
b1 |
4 |
3 |
3) (r1 \ r2)
|
А1 |
А2 |
А5 |
А6 |
|
|
a4 |
b1 |
4 |
1 |
|
|
a3 |
b3 |
2 |
1 |
|
|
a4 |
b4 |
1 |
4 |
4) r1><r2, d(A5)= 4; r1.A5=r2.A5
|
r1A1 |
r1A2 |
r1A5 |
r1A6 |
r2A1 |
r2A2 |
r2A5 |
r2A6 |
|
|
a4 |
b1 |
4 |
1 |
a1 |
b1 |
4 |
3 |
|
|
a1 |
b1 |
4 |
3 |
a1 |
b1 |
4 |
3 |
5) (r1.A1, r2.A4, r2A5,r1.A6) (r1><r2, d(A5)= 4)
|
r1A1 |
r1A6 |
r2A5 |
|
|
a4 |
1 |
4 |
|
|
a1 |
3 |
4 |
Заключение
В результате проделанной работы, били закреплены практические навыки решения задач по математической логике. Было решено 2 варианта заданий по математической логике и исчислению высказываний, математической логике и исчислению предикатов, реляционной логике.
Литература
1) Игошин, В.И. Математическая логика и теория алгоритмов: Учеб. пособие для вузов [Текст] / В.И. Игошин. - М.: Академия, 2004 г.
Размещено на Allbest.ru
Подобные документы
Проблема истинности. Критерии истинного знания. Принцип верификации в позитивизме. Ограниченность верификационного критерия. Критерий фальсификации К. Поппера. Основные подходы в понимании и отражении проблемы истинности.
курсовая работа [27,8 K], добавлен 26.01.2007Определение признаков понятия "безопасность". Принципы деления обязательства на односторонние, альтернативные, долевые и солидарные по правилам соразмерности и непрерывности. Установление отношений между суждениями А и В при помощи таблицы истинности.
контрольная работа [120,8 K], добавлен 05.01.2012Объединенная классификация суждений, их схемы и принятые в логике обозначения. Составление таблицы истинности, разбор силлогизма. Логический вывод сложной деструктивной дилеммы. Формально-логический закон и его нарушение. Логическая схема умозаключения.
контрольная работа [36,2 K], добавлен 04.08.2013Предмет логики, ее значение и виды. Особенности определения истинности сложного суждения по таблице истинности. Построение фигуры категорического силлогизма на основании посылки: "Все люди – смертны". Путь формирования логической культуры мышления.
контрольная работа [12,2 K], добавлен 07.12.2009Доказательство как процесс обоснования истинности любого утверждения с помощью уже установленных истин. Тезис, аргумент и демонстрация. Сориты (сокращенные полисиллогизмы) аристотелевского типа и гоклиниевского. Типы умозаключений и виды доказательств.
контрольная работа [19,3 K], добавлен 10.02.2009Силлогизм - дедуктивное умозаключение, в котором из двух категорических высказываний выводится одно новое. Диаграмма Эйлера для терминов: государство, республика, монархия. Построение таблицы истинности для формулы. Определение фигуры и модуса силлогизма.
контрольная работа [80,2 K], добавлен 29.03.2010Исследование логической категории и основных способов аргументации как полного или частичного обоснования, какого либо утверждения с использованием других утверждений. Сущность доказательства как установления истинности положения логическими средствами.
реферат [14,8 K], добавлен 27.12.2010Доказательство – логическая операция по обоснованию истинности суждений с помощью других истинных суждений. Опровержение - вид доказательного процесса, направленного на уже существующие доказательства для того, чтобы показать их несостоятельность.
контрольная работа [23,2 K], добавлен 21.05.2008Основные законы и принципы логики. Логические таблицы истинности. Определение правильности умозаключения методом от противного, вида понятия по количественной характеристике его объема. Собирательные и несобирательные, конкретные и абстрактные понятия.
контрольная работа [125,1 K], добавлен 29.08.2012Предмет и цели изучения логики. Понятие и основные концепции истины. Решение задач с помощью "кругов Эйлера". Формализация сложного суждения и построение таблиц истинности. Определение пар суждений, находящихся в отношении противоречия и подчинения.
контрольная работа [116,4 K], добавлен 16.10.2016
