	Главная \| Случайная страница \| Контакты \| Мы поможем в написании вашей работы!

Доказательство. Необходимость. От противного

⇐ Предыдущая 102 103 104 105 106107108 109 110 111 Следующая ⇒

Необходимость. От противного. Пусть и .

Введем обозначение: i – один из индексов 0, 1, *, ≤, L.

Тогда , но по таблице

Таблица принадлежности некоторых булевых функций рассмотренным замкнутым классам:


+	-	-	+	+
-	+	-	+	+
-	-	+	-	+
+	+	-	+	-

Таким образом, рассмотренные классы , , , , попарно различны, не пусты и не совпадают с ().

Функции двух переменных z = f(x,y).

Различных функций двух переменных существует уже шестнадцать. Эти функции, их названия и обозначения приведены в табл. 4.1. Число этих функций равно 2⁴= 16. Перенумеруем и расположим их тоже в естественном порядке.

Таблица 4.1

х	Название функции	Обозначение	Класс
y	T0	T1	S	M	L
f₀(x,y)	Константа “0”		+			+	+
f₁(x,y)	Конъюнкция	x ∧ y, xy	+	+		+
f₂(x,y)	Операция запрета по y	x	+
f₃(x,y)	Переменная x	x	+	+	+	+	+
f₄(x,y)	Операция запрета по x	y	+
f₅(x,y)	Переменная y	y	+	+	+	+	+
f₆(x,y)	Сумма по модулю 2	x ⊕ y	+				+
f₇(x,y)	Дизъюнкция	x ∨ y	+	+		+
f₈(x,y)	Операция Пирса	x ↓ y
f₉(x,y)	Равнозначность	x ∼ y		+			+
f₁₀(x,y)	Инверсия y				+		+
f₁₁(x,y)	Импликация от y к x	y → x		+
f₁₂(x,y)	Инверсия x				+		+
f₁₃(x,y)	Импликация от x к y	x → y		+
f₁₄(x,y)	Операция Шеффера	x / y
f₁₅(x,y)	Константа “1”			+		+	+

Таблица принадлежности некоторых булевых функций рассмотренным замкнутым классам:

K₀	K₁	S	M	L
+	-	-	+	+
-	+	-	+	+
-	-	+	-	+
+	+	-	+	-

Таким образом, рассмотренные классы K₀, K₁, S, M, L попарно различны, не пусты и не совпадают с P₂.

⇐ Предыдущая 102 103 104 105 106107108 109 110 111 Следующая ⇒

Дата публикования: 2014-11-04; Прочитано: 366 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!

studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...