Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ВОПРОС 1 Двузначная логика. Булевы функции.
Пусть х принимает 2 значения 0 и 1 (), такая переменная называется булевой.
Множество Х состоящее из - множество булевых переменных.
Функция называется булевой если все ее переменные булевы и она принимает значения 0 и 1
Способ задания булевой функции:1)Задать булеву ф-ию можно таблицей:
2) Функцию f можно задать набором ее значений
P2 – множество всех булевых функций.
P2(n) - множество булевых функций, зависящих от n переменных.
Число наборов 0 и 1 длины К равно 2К
Т-ма 1 Число булевых функций зависящих от n-перемененных равно , доказательство следует из второго способа задания функции
Способы задания элементарных функций:
Основные свойства элементарных функций:
=
(**)
(вообще )
Опр. Наборы и называют соседними по i-ой компоненте (i=1), если они отличаются только в i-ой компоненте
Пример: ; ;
и - соседние по второй компоненте; и- соседние по первой компоненте; и- не соседн.
Опр. Переменная xi функции называется существенной если найдутся 2 набора соседние по i-ой компоненте такие что , в противном случае переменная называется не существенной(фиктивной)
|
xyz |
||
|
000 |
0 |
0 |
|
001 |
1 |
0 |
|
010 |
1 |
0 |
|
011 |
0 |
0 |
|
100 |
1 |
0 |
|
101 |
0 |
0 |
|
110 |
0 |
1 |
|
111 |
1 |
1 |
Пример:
Для f1:
x – существенная, т.к.
y – существенная, т.к.
z – существенная, т.к.
Для f2:
x1 – существенная, т.к.
y – существенная, т.к.
z – фиктивная, т.к. на всех парах соседних по 3-ей компоненте значения функций равны.
Пусть булева функция задана таблицей -фиктивная переменная функции f; в таблице функции f вычеркнем столбец соответствующей переменной и все строки вида все строки в i-ой позиции которых записана 1. Получим новую таблицу, которую задает . Будем говорить, что функция g получена из f удалением фиктивной переменной xi, а о функции f будем говорить, что она получена путем введения - в g
Опр. Две функции равны, если одна получается из другой путем добавления или удалением фиктивной переменной.
|
0 0 0 |
0 |
|
0 0 1 |
0 |
|
0 1 0 |
0 |
|
0 1 1 |
0 |
|
1 0 0 |
0 |
|
1 0 1 |
0 |
|
1 1 0 |
1 |
|
1 1 1 |
1 |
Пример: Получаем функию
|
0 0 |
0 |
|
0 1 |
0 |
|
1 0 |
0 |
|
1 1 |
1 |
=
Существуют два типа булевых функций не имеющих существенных переменных: Фугкции первого типа равны константе 0, второго типа = 1
Формула. Пусть множество - состоит из конечного числа функций, P2 – множество всех булевых функций. - M подмножество P2
Пример: ,
1) -формула
2) ;;;;;
Формулам сопоставим функцию
Опр. Две формулы называются эквивалентными, если соответствующие им функции равны.
СДНФ
Опр. Выражение (где ) называется элементарной конъюнкцией
Опр. Выражение где Кi-элементарная конъюнкция называется дизъюнктивной нормальной формой (ДНФ)
Опр. Выражение (где ) называется элементарной дизъюнкцией
Опр. Выражение где Кi-элементарная дизъюнкция называется конъюктивной нормальной формой (КНФ)
Замечание
Т-ма для любой верно - Совершенная ДНФ(СДНФ)
Пусть булева функция ; возьмем набор значения переменных, вычислим значение формулы и слева и справа от = на наборе
|
0 0 |
0 |
|
0 1 |
1 |
|
1 0 |
1 |
|
1 1 |
0 |
Пример: f=представить в виде СДНФ
=-СДНФ
То есть в степень выбираем те значения у которые функция равны 1.