Глава 2. Логические исчисления

Вариант 2.

Задание 1. Доказать или опровергнуть данные логические следствия, используя два метода: анализ таблицы истинности; от противного.

• ╞ ;

• ╞ .

1. ╞ ;

Построение таблицы истинности:

				a		b		c		d
А	В	С	D		B D		A→B		ABC		ABD		C→a	C→b	A C D	c d
0	0	0	0		0		1		0		0		1	1	0	0
0	0	0	1		1		1		0		0		(1	1	1)	0←
0	0	1	0		0		1		0		0		0	1	1	0
0	0	1	1		1		1		0		0		(1	1	1)	0←
0	1	0	0		1		1		0		0		1	1	0	0
0	1	0	1		1		1		0		0		(1	1	1)	0←
0	1	1	0		1		1		0		0		(1	1	1)	0←
0	1	1	1		1		1		0		0		(1	1	1)	0←
1	0	0	0		0		0		0		0		(1	1	1)	0←
1	0	0	1		1		0		0		0		(1	1	1)	0←
1	0	1	0		0		0		0		0		0	0	1	0
1	0	1	1		1		0		0		0		1	0	1	0
1	1	0	0		1		1		0		0		(1	1	1)	0←
1	1	0	1		1		1		0		1		(1	1	1)	1 +
1	1	1	0		1		1		1		0		(1	1	1)	1 +
1	1	1	1		1		1		1		1		(1	1	1)	1 +

Вывод: Формула не является логическим следствием, т.к. есть случаи, когда все гипотезы равны 1, правая часть равна 0.

Метод от противного:

Предположим, что F = = 0 и попробуем обратить все гипотезы в 1.

_{ABC ABD = 0, тогда ABC = 0 и ABD = 0}

_{1) C = 0, D = 0, тогда A 0 0 = 1, значит A = 1.}

_{2) C→(B D), 0→(B 0) = 1, B = 0 или B = 1.}

_{3) С→(A→B), 0→(1→B) = 1, B = 0 или B = 1.}

_{Вывод: Даже при F = 0, мы можем обратить все гипотезы в 1, это означает, что формула F не является логическим следствием.}

2. ╞ .

Метод от противного.

Предположим, F = = 0, тогда хотя бы одна из гипотез должна неизбежно обращаться в 0.

= 0, тогда A =0; BC = 0

1) A=0, B=0, гипотеза A = 0

2) A=0, C=0, гипотеза A=0

3) B=1, C =0, гипотеза B→C=0

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

Построение таблицы истинности:

				a		b				F
A	B	C	A		BC		B→C		A	a b
0	0	0	0		0		1		0	0
0	0	1	0		0		1		0	0
0	1	0	0		0		0		0	0
0	1	1	0		1		1		0	1
1	0	0	1		0		(1		1)	1 +
1	0	1	1		0		(1		1)	1 +
1	1	0	0		0		0		1	0
1	1	1	0		1		(1		1)	1 +

Вывод: Логическое высказывание верно, т.к. в случаях, когда все гипотезы равны 1, формула F=1.

Задание 2. Ввести необходимые обозначения и записать каждое из высказываний как формулу исчисления предикатов. Обосновать справедливость (ложность) заключения при помощи диаграмм Эйлера-Венна.

Перья есть только у птиц. Ни одно млекопитающее не является птицей. Значит, все млекопитающие лишены перьев.

Решение:

A(x) = "x имеет перья";

В(х) = "х - птица";

С(х) = "х - млекопитающее"

Запишем высказывание как формулу исчисления предикатов:

?

( х)(А(х)→В(х)); ( х)(С(х)→ В(х)) ( х)(С(х)→ А(х))

Построим диаграмму Эйлера-Венна:

U - множество всех зверей

А - множество имеющих перья

В - множество птиц

С - множество млекопитающих ?

А В; ВС = АС =

Вывод:

А В; ВС = АС =

Задание 3. Пусть предметная область , «x делится на y». Рассмотреть все варианты одновременной квантификации переменных двухместного предиката . Определить истинность получаемых выражений.

1. ( ( ) Q(x,y) = Л (x = 7; y = 3)

Два любые натуральные числа делятся друг на друга.

2. ( )( ) Q(x,y) = И (x = 4, y = 2)

Существуют два натуральные числа, одно из которых делится на другое.

3. ( ( ) Q(x,y) = И (x - любое, y = 1)

Для любого x найдется такой y, что x будет делиться на y.

4. ( )( ) Q(x,y) = Л

Существует такое натуральное число, которое делится на любой натуральный y

5. ( )( ) Q(x,y) = И (y - любое, x = 2y)

Для любого натурального y, найдется натуральное x, которое делится на него.

6. ( )( Q(x,y) = И (x - любое, y = 1)

Существует натуральное у, делящее любой x.