Техника доказательств:

f:RR f(x)=2x

ПРИМЕР 1

Доказать, что _х,уR f(x+y)=f(x)+f(y)

Доказательство: возьмем любые два вещественных числа х и у, тогда

f(x+y)=f(x)+f(y)

ПРИМЕР 2

Доказать единственность нейтрального элемента в группе А по умножению (А*х). Предположим, что имеется два различных нейтральных элемента, левосторонний e и правосторонний e’, т.е. :

х ех=х (1)

х xе’=х (2)

Поскольку формула (1) справедлива для любого х, то возьмём в качестве х значение е’ (х=е’), получим ее’=е’. Поскольку формула (2) справедлива для любого х, то возьмём х равный е, получим ее’=е

Теорема.

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

Доказательство.

а=в=с=– может быть либо рациональным, либо иррациональным. Если с – рационально, то теорема доказана. Если с– иррационально, то возьмём в качестве а=, в=, когда а^в=. Теорема доказана.

Алгебра логики. Логические операции и операции на множествах

Определение:

Одноместным предикатом на множестве А называется функция, принимающая на этом множестве 2 значения: 0 и 1.

Пусть - некоторое подмножество множества А. Определим функцию следующим образом:Данный предикат называется характеристической функцией множества Х.

Пусть Р(А)– множество всех подмножеств множества А, – множество всех отображений из А в В.

Теорема.

Отображение множества , построено следующим образом:

–биективное отображение .

Доказательство.

Построим обратное отображение. Пусть - некоторый предикат из. Положимт.е.,т.е. мы задали отображение. Покажем, что данное отображениеобратно отображению, сформулированному в условии теоремы. Для этого необходимо показать, что:

1);

2),.

1) – по определению характеристической функции.

2) Рассмотрим произвольный элемент ,Т.о.ч.т.д.

Пусть Р(х)– высказывательная форма с единственным свободным параметром х, обозначающим элементы множества А.

Пример:

Пусть А– множество целых чисел, а такое, что х – четное число.

Определим функцию следующим образом: – область истинности высказывания Р. В этом случае является характеристической функцией множества Х.

Можно сказать, что высказывательные формы P и Q эквивалентны, если их характеристические функции исовпадают.

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

Область истинности для высказывания Р– это множество ,.

Определение:

n-местный предикат на множестве А– это функция, определенная на множестве , принимающая значения {0,1}.

Определение:

n-местное отношение на множестве А– это подмножество множества .

Замечание: n-местный предикат на А– это одноместный предикат на .

Между n-местными отношениями на А и n-местными предикатами на существуют взаимнооднозначные отношения.,.

Пусть имеется высказывательная форма с n элементами , тогдаn-местный предикат и область истинностиR для высказывания P могут каждый однозначно определить эту форму.

Операции над подмножествами и одноместными предикатами

Пусть отображение f и g - одноместные предикаты; определим следующие операции над ними:

1.

2.

3. ;

4. -тождественно равно 0 на А;

5. -тождественно равно 1 на А;

Теорема.

Пусть X и Y – 2 произвольных подмножества множества А, тогда:

1. ;

2. ;

3. , где;

4. ;

5. ;

Доказательство.

1. Рассмотрим произвольное :

===

2. Рассмотрим произвольное :

===

3.

Следствие:

Пусть имеется булево тождество, в которое входят только связки ,,

, тогда, если вместо переменных подставить произвольные подмножества множества А и заменить на, а 0 и 1 наи А, то получится верное равенство.

Операция - исключающее или.

Для множеств X и Y определяется операция “симметрическая разность” . На самом деле операциянад предикатами соответствует операциинад множествами.

Булевы функции

Определение.

БФ от n переменных– это отображение .

Теорема.

Каждую БФ можно выразить через операцию V,, .

Доказательство.

Пусть f:{0,1}ⁿ {0,1} – БФ от n переменных

1) Если (x₁,x₂,…,x_n){0,1}ⁿ f(x₁…x_n)=0,то f(x₁…x_n)=x₁ (x₁)

2) Пусть функция f тождественно

Рассмотрим ,x{0,1}. Обозначим x^ =

Для любого набора (₁,₂,…,_n), для которого функция f принимает значение 1, мы рассмотрим выражение вида:

x₁^1x₂^2…x_n^n

Дизъюнкция всех этих выражений даёт булеву функцию f

Докажем это:S={(₁…_n) {0,1}ⁿ|f(₁…_n)=1 }

Тогда g(x₁…x_n)= V(x₁^1x₂^2…x_n^n) (₁…_n)S

g(x₁…x_n)=f(x₁…x_n)

Определим, при каких значениях x₁…x_n функция g=1 (₁…_n)S,такой что X₁^1Х₂^2…Х_n^n=1

X₁^1Х₂^2…Х_n^n=1  _i Х_i=_i.

Т.е. g(x₁…x_n)=1 для тех и только тех наборов, которые входят в множества S.

С другой стороны, f(x₁…x_n)=1 для тех и только для тех, которые входят в множество S.

Т.е. функции f и g принимают значения 1 и 0 на одних и тех же наборах  f=g.

Следствие:

Каждую БФ можно выразить, используя только 2 операции:  или 

Замечание:

Представленная в теореме функция g называется совершенной дизъюнктивной нормальной формой (СДНФ). Исходя из тождества =x строится совершенная конъюнктивная нормальная форма. Возьмём СДНФ:

V

Тогда ¬V= ^(¬)=

(₁…_n): (₁…_n):

f(₁…_n)=1 f(₁…_n)=1

= 

f(x₁…x_n)= ( f(x₁…x_n))

f(x₁…x_n)= ( f(x₁…x_n))

Пусть ρ(x₁…x_n)=  f(x₁…x_n), тогда ρ(x₁…x_n)=

ρ(x₁…x_n)=  (₁…_n): f(₁…_n)=0

f=-(ρ(x₁…x_n))= ()=

= (₁…_n): f(₁…_n)=0

Минимизация булевых функций

Булева функция может быть задана в виде булевых переменных, соединенных знаками операций (т.е. в виде некоторой формулы). Под сложностью булевой функции будем понимать количество вхождений символов переменных в формулу, описывающую эту функцию.

ПРИМЕР:

Сложность булевой функции

=15, а сложность функции =3. В то же время обе эти формулы описывают одну и ту же булеву функцию.

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

Определение:

Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции некоторых конъюнкций: (для удобства знакопускаем).

Определение:

Минимальной ДНФ (МДНФ) функции f называется ДНФ, содержащая минимально возможное число вхождений символов переменных среди всех ДНФ, реализующих f.

Определение:

Булева функция является импликантом функции, если для всякого наборазначений аргументов выполнено неравенство:. Данное условие может быть записано в эквивалентном виде:=.

Определение:

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