Лекция 12 основы математической логики

Язык математики и определение

Именная форма – это комбинация знаков, которая превращается в имя, если вместо части переменных подставить имена. Данная часть переменных называется свободными переменными, остальные называются связанными переменными. Если в именной форме отсутствуют свободные и связанные переменные, то именная форма сама является именем.

Пример:

Именная форма	Свободные переменные	Связанные переменные	Примечание
0	---	---	Имя
	---	---	=3,14
-		---
X^2+Y^3	X,Y	---
	---	n
	a,b	x
	a,b,f	x	f-переменная обозначающая функцию.

Определение: Высказывание – это то, о чём осмысленно спросить, истинно оно или ложно.

Пример: То, что я сейчас написал в тетради – ложно. Это не является высказыванием!

Основные операции над высказыванием:

Если обозначить истинность символом 1, а ложность 0, то операции над высказываниями можно задать с помощью таблиц Кэли.

Бинарные операции дизъюнкция и конъюнкция задаются следующими таблицами:

ДИЗЪЮНКЦИЯ:

V	0	1
0	0	1
1	1	1

КОНЪЮНКЦИЯ:

	0	1
0	0	0
1	0	1

Бинарная операция импликация:

A B	0	1
0	1	0
1	1	1

АВ

Операция эквиваленция:

	0	1
0	1	0
1	0	1

Унарная операция отрицания:

	0	1
	1	0

Основные логические законы

ОБЩИЙ ПРИНЦИП:Пусть два выражения составленные из переменных и одних и тех же логических связок принимают одинаковые значения, если любым способом заменить переменные нулями или единицами, тогда, если в этих выражениях переменные любым способом заменить высказываниями, то получится два эквивалентных высказывания.

Основные Булевские тождества:

а а = а аb = bа

а (bс) = (аb)с

а Vа = а аVb = bVа

а V(bVс) = (аVb)Vс

а (bVс) = (аb)V(ас)

а V(bс) = (аVb)(аVс)

 а = а

закон Де Моргана:

 (а b) = (а)V(b)

 (а Vb) = (а)(b)

а (а) = 0 аV(а) = 1

а 1 = а аV0 = а

аb =аVb

а b = (аb)(bа)

аb = (b)(а)

Докажем одно из этих тождеств:

 (а  b) = (а) V (b)

а	b	а b	 (а b)	а	b	(а)V(b)
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Докажем справедливость доказательства от противного доказательство от противного, т.е. а b= (b)(а)

а	b	а b	а	b	(b)(а)
0	0	1	1	1	1
0	1	1	1	0	1
1	0	0	0	1	0
1	1	1	0	0	1