лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4

• Название: Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
• Анкор: лекции по дм
• Дата: 08.02.2021
• Размер: 1.51 Mb.
• Имя файла: лекции.docx
• Тип: Документы; #174835
• страница: 32 из 40

f₁(x) – нулевая функция.

f₁(x)=0

f₂(x) – тождественная функция.

f₂(x)=х

f₃(x) – отрицание

–

f₃(x) =х

f₄(x) – единица.

f₄(x)=1

Булевы функции двух переменных

Обозначение функции		х1	х2		Наименование
Наборы	00	01	10	11	f= x1 x2
f1	0	0	0	1	запрет x2
f2	0	0	1	0	f= x1
f3	0	0	1	1	запрет x1
f4	0	1	0	0	тождественное x2
f5	0	1	1	0	сложение по модулю 2
f6	0	1	1	1	f= x1x2 (дизъюнкция)
f7	0	0	0	0	f= x1↓x2 (стрелка Пирса)
f8	1	0	0	1	f= x1x2 (эквивалентность)
f9	1	0	1	0	f=
f10	1	0	1	1	f= x2→x1
f11	1	1	0	0	f=(инверсия)
f12	1	1	0	1	f= x1→x2
f13	1	1	1	0	f=x1|x2
f14	1	1	1	1	f=1

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

Формулы. Реализация функций формулами. Равносильные формулы. Принцип двойственности.

Пусть F = {f₁, f₂,…,f_2n} – множество булевых функций. Формулой над F называется выражение вида: f[F] = f(t₁, t₂,…,t_n), f F,t_i – либо переменная, либо формула над F. Множество F – базис, функция f – главная (внешняя) функция (операция), t_i – подформулы. Обычно для элементарных булевых функций используют инфиксную форму записи. Устанавливают следующий приоритет: , &, , .  отрицание или инверсия, & – конъюнкция,  дизъюнкция,  импликация. Всякой формуле F однозначно соответствует функция f. Это соответствие задается алгоритмом интерпретации, который позволяет вычислить значение формулы при заданных значениях переменных. Зная таблицы истинности для функций базиса, можно вычислить таблицы истинности той функции, которую реализует данная формула.

Пример. Задана формула F₁ := (x₁ & x₂)  ((x₁ & )  (& x₂)).

Таблица истинности:

x1	x2	x1 &	& x2	(x1 & )  ( & x2)	x1 & x2	F1
0	0	0	0	0	0	0
0	1	0	1	1	0	1
1	0	1	0	1	0	1
1	1	0	0	0	1	1

Т.о. формула F₁ реализует дизъюнкцию.

Одна функция может иметь множество реализаций над базисом. Формула, реализующая одну и ту же функцию, называется равносильной. Отношение равносильностей формул является эквивалентностью.

Имеют место следующие равносильности:

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

Принцип двойственности. Пусть f(x₁,…,x_n)  P_n – булева функция. Тогда f^*(x₁,…,x_n)(с чертой сверху) = f^*(x₁,…,x_n)называется двойственной функцией f. f^**= f.