Свойства булевых функций.

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

Количество булевых функций от n переменных равно

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

от двух переменных , и.т.д

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

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

1) упрощение формул, т.е. получение эквивалентных формул с меньшим числом символов;

2) приведение формул к ДНФ и в том числе к СДНФ;

3) приведение формул к КНФ и в том числе к СКНФ.

При упрощении формул используют следующие свойства:

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

л) (законы склеивания)

Свойства импликации, эквивалентности и отрицания:

Равенства, выражающие одни булевы функции через другие

Примеры:

1. Упростите выражение с помощью свойств булевых функций

Решение:

2. Решите булево уравнение

Решение: Составим таблицу истинности для левой и правой частей уравнения

x

Из таблицы видно, что значения истинности левой и правой частей уравнения не совпадают ни при каких значениях переменных. Таким образом, данное уравнение не имеет решения.

3. Решите булево уравнение

Решение: Составим таблицу истинности для левой и правой частей уравнения

Из таблицы видно, что значения истинности левой и правой частей уравнения совпадают при и . Таким образом, данное уравнение имеет решение (1;0).

IV. АЛГЕБРА ПРЕДИКАТОВ.

Основные понятия.

n-местным предикатом (или функцией- высказыванием от n переменных) определённым на множествах называют выражение, содержащее n переменных , превращающееся в высказывание при подстановке вместо этих переменных конкретных элементов из множеств соответственно.

Обозначают n-местный предикат или, или, или, и.т.д.

Высказывание будем считать 0-местным предикатом.

Так как высказывания могут принимать два значения 0- ложь или

1- истина, то и значение предиката может быть либо 0, либо 1.

Примеры:

1. Одноместный предикат, заданный (определённый) на множестве действительных чисел R , при конкретных значениях переменной x принимает разные значения:

2.Двухместный предикат, заданный (определённый) на множестве действительных чисел R , при конкретных значениях переменной x принимает разные значения:

3.n-местный предикат, заданный (определённый) на множестве действительных чисел R , является истинным при любом наборе переменных x.

4. n-местный предикат, заданный (определённый) на множестве действительных чисел R , является ложным при любом наборе переменных x.

Пусть некоторый n-местный предикат на множестве М. Этот предикат называется:

1) тождественно-истинным, если для любого набора значений аргументов его значение равно 1. (Пример 3);

2) тождественно-ложным, если для любого набора значений аргументов его значение равно 0. (Пример 4);

3) выполнимым, если существует хотя бы один набор значений аргументов, при котором его значение равно 1;

4) опровержимым, если существует хотя бы один набор значений аргументов, при котором его значение равно 0.

Каждый рассматриваемый предикат является или тождественно-истинным, или тождественно-ложным, или выполнимым (опровержимым).

Множеством истинности предиката , заданного на множествах , называется совокупность всех упорядоченных n-систем таких, что данный предикат обращается в истинное высказывание при подстановке

Обозначают

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

Предикат называется следствием предиката , заданного на тех же множествах , что и , если он обращается в истинное высказывание на всех тех наборах значений переменных, на которых в истинное высказывание обращается предикат , т.е. .

Пример.Найдите область истинности предикатов: , , , .

Решение: , таким образом ,