Лекции по математической логике1. Элементы математической логики

• Название: Элементы математической логики
• Анкор: Лекции по математической логике1.doc
• Дата: 03.11.2017
• Размер: 2.19 Mb.
• Имя файла: Лекции по математической логике1.doc
• Тип: Документы; #10077
• Категория: Математика
• страница: 2 из 8

Пример. Пусть требуется представить в виде таблицы следующую функцию

f (x₁,x₂,x₃)={[( x₂) (x₁ x₂)] (x₁x₂)}x₃.

Будем строить ФАЛ последовательно.

x1	x2	x3		x2	x1x2	[ ]	x1x2	{ }	f (x1,x2,x3)
0	0	1	1	0	1	1	0	0	1
0	0	0	1	1	1	1	0	0	1
0	1	1	1	0	0	0	1	0	1
0	1	0	1	1	0	1	1	1	1
1	0	1	0	1	0	1	1	1	0
1	0	0	0	0	0	0	1	0	1
1	1	1	0	1	0	1	0	0	1
1	1	0	0	0	0	0	0	0	1

ВЫРАЖЕНИЕ ОДНИХ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ ЧЕРЕЗ ДРУГИЕ

1. 
   Функция f ₈(x_1,x₂) = x₁x₂ (импликация x₁ в x₂) может быть записана посредством функций дизъюнкции и отрицания
   

x₁>x₂=x ₂.

Доказательство осуществляется посредством таблиц истинности.

x 1	x 2	x1x2
0	0	1
0	1	1
1	0	0
1	1	1

x1	x2		 x 2
0	0	1	1
0	1	1	1
1	0	1	0
1	1	1	1

2. 
   Функцию эквивалентности f₇(x_1,x₂)=x₁x₂= x₁x₂ выразим посредством других функций x₁x₂= (x₂)&(x ₁ )
   

x 1	x 2	x1x2
0	0	1
0	1	0
1	0	0
1	1	1
x 1	x 2			x 2	x1	(x2)&(x 1 )
0	0	1	1	1	1	1
0	1	1	1	1	0	0
1	0	0	0	0	1	0
1	1	0	0	1	1	1

3. 
   f ₁₁(x_1,x₂) = x₁ x₂=
   

x 1	x 2	x1x2	x1x2
0	0	0	1	0
0	1	1	0	1
1	0	1	0	1
1	1	0	1	0

или

f(x_1,x₂) = x₁ x₂=(& x₂) (x₁&)

x 1	x 2	x1x2		(&x2)		(x1&)	(&x2) (x1&)
0	0	0	1	0	1	0	0
0	1	1	1	1	0	0	1
1	0	1	0	0	1	1	1
1	1	0	0	0	0	0	0

4. 
   =x
   

x
0	1	0
1	0	1

5. 
   x₁& x₂=
   

x 1	x 2	x1& x2
0	0	0
0	1	0
1	0	0
1	1	1

x 1	x 2
0	0	1	1	1	1
0	1	1	1	1	0
1	0	0	0	0	1
1	1	0	0	1	1

6. x₁ x₂=

x 1	x 2	x1 x2
0	0	0
0	1	1
1	0	1
1	1	1

x 1	x 2			&
0	0	1	1	1	0
0	1	1	0	0	1
1	0	0	1	0	1
1	1	0	0	0	1

7. x₁x₂=

x 1	x 2	x1x2
0	0	0
0	1	1
1	0	1
1	1	0

x 1	x 2			x2	x1
0	0	1	1	1	1	0
0	1	1	0	1	0	1
1	0	0	1	0	1	1
1	1	0	0	1	1	0

Свойства конъюнкции, дизъюнкции и отрицания

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

x₁&(x₂&x₃)= (x₁&x₂)&x₃,

x₁ (x₂x₃)= (x₁x₂)x₃,

переместительный

x₁ x₂= x₁x₂,

x₁& x₂= x₁&x₂,

и распределительный законы. Кроме того, выполняется распределительный закон дизъюнкции относительно конъюнкции.

x₁ (x₂&x₃)= (x₁x₂)& (x₁x₃).
Проверим справедливость этого закона путем сравнения таблиц для функций, стоящих в левой и правой частях рассматриваемого соотношения.

x 1	x 2	x 3	x2&x3	x1 (x2&x3)
0	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	1	1	1	1
1	0	0	0	1
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

x 1	x 2	x 3	x1x2	x1x3	(x1x2)& (x1x3)
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	1	1	1
1	1	1	1	1	1